Mouse Selection Sorting

[Alpha Omega]

I am thinking of an algorithm to detect when an user selects an object with the mouse.

1. Using an AABB Octree store all objects, objects contain triangles, and triangles contain points.
2. Fire a ray from the camera to the mouse location, convert screen coords to a 3D ray.
3. Traverse the Octree, testing for existing leaf nodes, then testing for intersection with the ray.

This algorithm is not well optimum for overlaying items that are close together. The algorithm would need to sort all positive tests and return the intersection of minimum length. It would be better if the algorithm tested the closest object in the tree first.

Would sorting the nodes in the Octree for each ray cast be more efficient than checking for all intersections and then sorting the returned nodes?

Is there a better algorithm for this?

*edited grammar

[chronologicaldot]

I was under the impression irrlicht already had something for this, though maybe that algorithm is not optimized.

I can't think of a better method than your suggestion aside from performing the shortest distance test at the same time as the get-the-objects test. Of course, I'm not sure how you intend to implement it either.

Try writing the algorithms out in pseudo code first and see which one seems the quickest.

Sorry my post isn't more helpful.

[Alpha Omega]

Based on my research k-dr trees seem more efficient for this kind of thing.

[Mel]

There is a paper written by the teachers of the University of Granada about octree traverse, i guess that for efficient node picking. It is implemented in the Unreal Engine III, so it may of some use.

http://lsi.ugr.es/curena/inves/wscg00/

[Alpha Omega]

I am going to use this because it has a built in sort method that always returns the first intersection so no sorting is needed. It is easier to digest in my opinion.

http://diglib.eg.org/EG/DL/WS/EGGH/EGGH89/061-073.pdf