Hello Peter,

Funny that there are so many intersection questions lately.

1) The current KdTree implementation is just for sorting triangle geometry at node leaves. Perhaps it would be useful to to have a KdTree organize the scene graph nodes themselves, based on bounding volumes? Or are bounding volume tests generally good enough (and it's up to the user to be clever about organizing the scene graph?)

A bouding volume hierarchy is generally pretty fast. There have been publications lately on how a good BVH can be as fast as a badly balanced kd-tree, and well balancing a kd-tree brings additional performance concerns for dynamic scenes, and so a BVH is generally preferable for dynamic scenes.

Of course, this assumes your scene graph is organized spatially, which is not always the case (or even most of the time). Subgraphs may be spatially organized (i.e. a vehicle will be under a group, parts of the vehicle's engine will be under a group that's under the vehicle's group, etc.) but in many cases I've seen, all or most distinct objects will be directly under the scene root (all buildings, all vehicles, all characters, etc.). It would be better to group a few close-by buildings under a group, then a few of those clusters under another group, etc. to get a better hierarchy. But this is the same concern as when you want to optimize frustum culling performance. If the kd-tree or the cull visitor has to test lots and lots of individual objects, it will be slower than testing clusters and discarding the whole cluster if it can.

So the answer IMHO would be that in any case, you will want to try and build a good scene graph (both for culling performance and intersection performance). Whether you want to make a global kd-tree for the whole scene will depend on how dynamic your scene is, and if you can take the time to implement it so that only parts that change need updating.

2) I need to do line-of-sight tests where I am only interested in whether any intersection exists, and not what those intersections are. This allows for a "trap door" optimization where the search process terminates on the first positive intersection. Is there a way to do that with the current osgUtil::IntersectionVisitor, or do I need to modify it to serve this purpose?

This is not implemented currently. It's another one of those little projects I'd like to do eventually. It's what some publications call "test-intersection" vs "find-intersection".

Test-intersection: If all you want to know is if something intersects (for example, for shadow tests in raytracing) some shortcuts can be taken.

Find-intersection: If you really want to find all objects that intersect (and potentially then sort by distance so you can get the closest one) (for example, for the main rays in raytracing) then you'd do it more or less the way it's done right now.

If you want to implement test-intersection, you could subclass IntersectionVisitor/LineSegmentIntersector, or you could do it directly in these classes as an option and then submit it to OSG. :-)

Hope this helps,

Jean-Sebastien Guay    jean-sebastien.g...@cm-labs.com
osg-users mailing list

Reply via email to