Sign in to follow this  
JiiPee

D3DXIntersect mathod performance

Recommended Posts

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:

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

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this