[osg-users] 3D accurate pathfinding

Gerwin de Haan gerwindehaan at gmail.com
Sat Mar 28 06:59:20 PDT 2009


Hi Harold,

I know that people at Utrecht University (The Netherlands) are
actively working on the type of problems you describe. Maybe their
corridor map method is something for you:

"Current applications require a path planner that is fast (to ensure
real-time interaction with the environment) and flexible (to avoid
local hazards). In addition, paths need to be natural, i.e. smooth and
short. We propose a new framework, the Corridor Map Method, which
meets these requirements. "

check out some publications here:
http://people.cs.uu.nl/roland/index.html

good luck,
Gerwin

On Sat, Mar 28, 2009 at 1:46 PM, Harold Comere <osgforum at tevs.eu> wrote:
> Hi all,
>
> First, my english is not fluent, so i apologize for all mistakes i will do and hope i will success to explain my problem :)
>
> Well, i'm currently working on a project where i have to implement any kind of efficient real time pathfinding in osg scene.
> The goal is to go from a space point to another one ( or to an osg node but it is similar ) avoiding collisions and detecting when there is not path to go there.
>
> The real problem is that :
> 1) Algorithm must work for static scene but could be extended easily to dynamic scenes.
>
> 2) Algorithm must work in some specific kind of situation :
> - In space, huge empty areas and some complex "small" objects as satellite.
> - In pipe network. It means able to pass through pipes if needed.
> - In a factory, lot of rooms ( and why not pipes :p )
>
> 3) The algorithm must return a path, or nothing if no path found, then the camera will follow the path, that to have to do computations once.
>
> Well, i worked on it for about 2 weeks now and i didnt found any efficient way to do it.
>
> Static / Dynamic constraint prevents preprocessing that build any kind of graph to use common path finding algorithm ( as A* and other ).
> For a dynamic scene a way to use pathfinding algorithms could be to build the pathfinding graph each time the "goto" function is called. But to get an accurate path finding detection, we have to consider the whole scene ( specially in factory case ), that is pretty hard to do it in interactive time.
>
> Pipes network constraint prevents of working with bounding volumes ( bounding sphere, AABB, OBB, convex hull ). I didnt succeed to find a way to build hierarchical space subdivision that could help greatly with geometry collision detection.
>
> A simple way to solve my issue could be ray tracing collision detection. But this dont guarantee to find a good path, and it make hard to detect there is not path... And after some tests, using the osg::LineSegmentIntersector take about 5 ms on my scene, so i use only 200 rays to find a path it already cost 1s that's to much for real time application needs.
> Maybe by specifing to the IntersectionVisitor only the node where is the camera, could be reduce computing times, but i dont think that's a suitable solution..
>
> Well, i'm a bit stuck and lack of ideas for now ...
> I have began to use osg 2 weeks ago, so maybe is there any kind of osg cool stuff wich could be usefull to do it that i ignore ?
>
> Thanks for your attention :)
>
> Regards,
> Harold
>
> ------------------
> Read this topic online here:
> http://forum.openscenegraph.org/viewtopic.php?p=9392#9392
>
>
>
>
>
> _______________________________________________
> osg-users mailing list
> osg-users at lists.openscenegraph.org
> http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
>



More information about the osg-users mailing list