5 replies to this topic

[JiiPee]

Does anybody know how optimized D3DXIntersect method is? Is there any sense to create own intersection test algorithm?

[Nik02]

The said function is optimized for the general case - it cannot assume anything about the geometry of the intersected mesh. In addition, it needs to interpret the data from a vertex buffer, which causes at least one level of pointer dereferencing (indirect random memory access). Also, being a dll function (as opposed to a native function in the same module as the caller), calling it requires one additional address mapping operation.

The actual functionality of the intersection calculation is fairly well optimized, though.

If you can make assumptions about the spatial partitioning of the mesh, you can probably write a better function yourself. The basic logic (assuming nothing about the geometry) is as follows:

Let "intersections" be an empty list of triangle indices and distances from the origin of the probe ray
Let "mindist" be a float that is initialized to maximum value of float
Let "mintri" be an index of the nearest found triangle so far

For each triangle in mesh
Check for intersection between ray and current triangle
If (ray intersects triangle)
{
store current triangle index and intersection distance to "intersections" collection
if (mindist is larger than current intersection distance)
{
set mindist = current intersection distance
set mintri = current triangle
}
}
return interections, mindist and mintri; each are potentially empty or unchanged, if intesections were not found

Edited by Nik02, 28 December 2012 - 06:57 AM.

[L. Spiro]

Is there any sense to create own intersection test algorithm?

Yes. By creating your own you are not tied to the D3DX library.
Reason enough for me.


L. Spiro

[Nik02]

Good opportunity for optimizing the intersection algorithm itself is to calculate an axis-aligned bounding box of the mesh in advance; it is then easy to determine whether or not it is even possible that the ray would intersect any of the triangles. Ray-AABB intersection is very fast. The D3DX function does not do this, as it may be expensive to calculate the bounding box itself, and it cannot assume that a given mesh is unchanged between the calls to it (but you can, if it is your mesh and you know it is static).

Edited by Nik02, 28 December 2012 - 07:04 AM.

[JiiPee]

Is there any sense to create own intersection test algorithm?

Yes. By creating your own you are not tied to the D3DX library.
Reason enough for me.


L. Spiro

 

Yes, but sometimes using time to unnecessary optimization is bad considering the project schedule. Or if I'm very smart, I could say bad for the ROI ;)

 

I try to find reasons why to do or not to do my own test algorithm. If common opinion is, that the DX algorithm suxs, then it's probably smart to create own at very beginning because you have to do it anyway. If the common opinion is, that weel it's ok, then I think I'll stick with it and perhaps create it, if the algorithm seems to be bottle neck.

[JiiPee]

Nice answers Nik02. I'll have to consider those options.