Re: [osg-users] line intersection performance
This is an old thread I found when I was searching. It may not be in the forums so I have included the original text below as a quote. I am trying to implement something like this, in order to compute hit tests on a line. I don't need to know which objects intersected the line, or get a list of objects/intersections out, just need to know Is there an intersection or not. The original posts are included below. Would anyone know how I might go about implementing this? /// A couple of other questions related to intersection performance: ... 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? Thanks, Peter Hi Jean-Sébastien, Jean-Sébastien Guay wrote: 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. In my case I am reading OpenFlight files produced by a third party, so I don't have much control over whether it was constructed efficiently or not. Since the terrain will be static, my thought was to build a mostly static KdTree of scene graph nodes separate from the normal rendering state graph and to be used for culling and intersection tests. I believe a number of other 3D engines use this approach. However my question was really whether something like this already existed in OSG, to which the answer is no. 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. :-) I do need this feature, so I will look into implementing it in osgUtil::IntersectionVisitor. This should be as simple as setting a flag, I think, and modifying the traversal to return as soon as an intersection is found. I will let the list know how it goes. Thanks, Peter /// ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
Hello Andrew, I am trying to implement something like this, in order to compute hit tests on a line. I don't need to know which objects intersected the line, or get a list of objects/intersections out, just need to know Is there an intersection or not. The original posts are included below. Would anyone know how I might go about implementing this? I think I had mentioned the files to check in that thread, but if not, have a look at the code in osgUtil::IntersectionVisitor, osgUtil::LineSegmentIntersector and associated classes (some of which are in the source files only). It should be pretty simple to use those as guidance and just return true whenever it can be decided without error that the intersection will succeed. Also if you remove all the calculations that are done in the case an intersection was successful (node path copy, local intersection point and normal, etc.) you might gain a bit too. Note that if you can survive by doing an approximate test, then you could also implement your own subclasses of LineSegmentIntersector/IntersectionVisitor that would only check bounding volumes. That would be much quicker than testing the geometry. If you do need exact tests, then make sure you enable kd-trees for your geometries, this will help greatly. If you end up doing this, please do it in a way that can be re-integrated into OSG since I expect other people will be interested in using this kind of test. Hope this helps, J-S -- __ Jean-Sebastien Guayjean-sebastien.g...@cm-labs.com http://www.cm-labs.com/ http://whitestar02.webhop.org/ ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
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, J-S -- __ Jean-Sebastien Guayjean-sebastien.g...@cm-labs.com http://www.cm-labs.com/ http://whitestar02.webhop.org/ ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
Hi Peter, On Fri, Apr 24, 2009 at 6:21 PM, Peter Amstutz peter.amst...@tseboston.com wrote: A couple of other questions related to intersection performance: 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 good scene graph will be built up in the same structure as a KdTree, it's just coarse grained .i.e. at whole node/geometry level rather than individual triangles like the KdTree does. Given this there really isn't too much to be gained by trying to graft a KdTree into the scene nodes themselves. 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? Not at present. I see that JS expands on this topic so I won't comment further. Robert. ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
Hi Jean-Sébastien, Jean-Sébastien Guay wrote: 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. In my case I am reading OpenFlight files produced by a third party, so I don't have much control over whether it was constructed efficiently or not. Since the terrain will be static, my thought was to build a mostly static KdTree of scene graph nodes separate from the normal rendering state graph and to be used for culling and intersection tests. I believe a number of other 3D engines use this approach. However my question was really whether something like this already existed in OSG, to which the answer is no. 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. :-) I do need this feature, so I will look into implementing it in osgUtil::IntersectionVisitor. This should be as simple as setting a flag, I think, and modifying the traversal to return as soon as an intersection is found. I will let the list know how it goes. Thanks, Peter ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
On Fri, Apr 24, 2009 at 7:45 PM, Peter Amstutz peter.amst...@tseboston.com wrote: Hi Jean-Sébastien, Jean-Sébastien Guay wrote: 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. In my case I am reading OpenFlight files produced by a third party, so I don't have much control over whether it was constructed efficiently or not. Since the terrain will be static, my thought was to build a mostly static KdTree of scene graph nodes separate from the normal rendering state graph and to be used for culling and intersection tests. I believe a number of other 3D engines use this approach. However my question was really whether something like this already existed in OSG, to which the answer is no. If your data is stored in a flat group the osgUtil::Optimizer spatialize groups visitor will be able to build a quad tree for you. Robert. ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
Robert Osfield wrote: If your data is stored in a flat group the osgUtil::Optimizer spatialize groups visitor will be able to build a quad tree for you. Oh excellent, just what I had in mind :-) Thanks, Peter ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] line intersection performance
Hello Peter, However my question was really whether something like this already existed in OSG, to which the answer is no. Indeed. And in your use case I agree that a kd-tree would be pretty efficient. Perhaps we could have a scheme where kd-trees can be turned on or off for particular subgraphs, so that static parts of the scene will use them and dynamic parts will use the BVH. I do need this feature, so I will look into implementing it in osgUtil::IntersectionVisitor. This should be as simple as setting a flag, I think, and modifying the traversal to return as soon as an intersection is found. I will let the list know how it goes. Yep, that should do it. J-S -- __ Jean-Sebastien Guayjean-sebastien.g...@cm-labs.com http://www.cm-labs.com/ http://whitestar02.webhop.org/ ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
