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

5 replies to this topic

Posted 28 December 2012 - 03:56 AM

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

See my game dev blog: http://gamedev4hobby.blogspot.fi/

Posted 28 December 2012 - 06:55 AM

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

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

If you

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.**

Niko Suni

Posted 28 December 2012 - 06:57 AM

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

My Art: http://l-spiro.deviantart.com/gallery/4844241/Realism My Music: https://soundcloud.com/l-spiro

L. Spiro Engine: http://lspiroengine.com

L. Spiro Engine Forums: http://lspiroengine.com/forums

L. Spiro Engine: http://lspiroengine.com

L. Spiro Engine Forums: http://lspiroengine.com/forums

Posted 28 December 2012 - 07:02 AM

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.**

Niko Suni

Posted 28 December 2012 - 02:12 PM

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.

See my game dev blog: http://gamedev4hobby.blogspot.fi/

Posted 28 December 2012 - 02:14 PM

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

See my game dev blog: http://gamedev4hobby.blogspot.fi/