Hardware Accellerated Voronoi
Author
Has anyone implemented this? I''m curious if the low resolution and aliasing causes problems, and how it affects the range you can map.
wrong forum
well it sort of is and sort of isn''t. I think he posted the question here because someone brought the subject up in another recent thread (an AI thread), so I guess the OP has a better chance of getting answered if the thread remains here.
well it sort of is and sort of isn''t. I think he posted the question here because someone brought the subject up in another recent thread (an AI thread), so I guess the OP has a better chance of getting answered if the thread remains here.
It is quite reasonable to post a question about Voronoi diagrams in the AI forum, since they are useful for several common Game AI tasks.
Timkin
Timkin
Author
To be more specific, Voroni diagrams seem to be very useful in motion planning because they define a clear path through an arbitrary collection of obstacles. The diagrams seem to be expensive to compute (though I've never implemented it, and I'm sure they could be precomputed) but there's a technique where the diagram can approximated by rendering on 3d hardware and extrapolating based on the depth buffer (or color values or something?)
Anyway, it seems like rendering those diagrams could be really fast, and if they were, could be used for motion planning on-the-fly in an environment where individual agents are moving and trying to avoid eachother all the time.
My question was related to the fact that the resulting 2d bitmap approximation of the Voroni diagram would be considerably less accurate than the precise diagrams created with a sweep-line algorithm. If you try to map too large an area on too small a bitmap, you can run into problems with aliasing and so on. But, at the same time, it could be useful for higher-level motion planning when overall geometry is known, but position of individual entities are not. Then, on a smaller scale, it could be used for each agent to plan a path to the end of its "viewing frustum" or whatever.
I'm not intuitively familiar with Voroni diagrams, but I find them really interesting and am curious if anyone has any experience with them. GameDev: Arena is the impetus for my curiosity at the moment, BTW
[edited by - Martel on September 4, 2003 11:13:06 AM]
Anyway, it seems like rendering those diagrams could be really fast, and if they were, could be used for motion planning on-the-fly in an environment where individual agents are moving and trying to avoid eachother all the time.
My question was related to the fact that the resulting 2d bitmap approximation of the Voroni diagram would be considerably less accurate than the precise diagrams created with a sweep-line algorithm. If you try to map too large an area on too small a bitmap, you can run into problems with aliasing and so on. But, at the same time, it could be useful for higher-level motion planning when overall geometry is known, but position of individual entities are not. Then, on a smaller scale, it could be used for each agent to plan a path to the end of its "viewing frustum" or whatever.
I'm not intuitively familiar with Voroni diagrams, but I find them really interesting and am curious if anyone has any experience with them. GameDev: Arena is the impetus for my curiosity at the moment, BTW
[edited by - Martel on September 4, 2003 11:13:06 AM]
No problem bucheron... this is a question that could be asked and answered in another forum... but that doesn''t mean it''s out of place here.
Martel, I don''t have personal experience with Voronoi diagrams, although I do recall reading on them during my PhD research (and deciding that I didn''t need to implement them). You should find ample literature to read in the robotics community, in particular in robotic vision and vision assisted guidance systems. Generally speaking though, Voronoi diagrams are a method of skeletonisation , so you might find useful, comparative techniques in that area. One thing to remember though is that you cannot guarantee that the path on the Voronoi diagram is in general, the shortest path.
Good luck in your endeavour,
Timkin
Martel, I don''t have personal experience with Voronoi diagrams, although I do recall reading on them during my PhD research (and deciding that I didn''t need to implement them). You should find ample literature to read in the robotics community, in particular in robotic vision and vision assisted guidance systems. Generally speaking though, Voronoi diagrams are a method of skeletonisation , so you might find useful, comparative techniques in that area. One thing to remember though is that you cannot guarantee that the path on the Voronoi diagram is in general, the shortest path.
Good luck in your endeavour,
Timkin
Implementing Voronoi diagrams is no small task. The easiest way I know of doing this is computing the Delaunay triangulation (dual of the Voronoi diagram, mostly the same information) by edge-flipping. Start with an arbitrary triangulation and then for every pair of triangles that share a side you compute if that is the correct triangulation of the cuadrilateral (a very simple test, based on Ptolemy''s Theorem). If not, flip the common edge. I think that algorithm has an average running time that is linear in the number of points.
Another method of computing the Dealunay triangulation is adding the points one by one, removing the existing triangles that contain the new point in the circumscript circle and adding triangles that have the new point as a vertex and a side of the just-created "hole" as opposite side.
Yet another method would be to add a third coordinate to each point, like this:
(x, y) |-> (x, y, x^2+y^2)
The [3D] convex hull of the resulting will project to the Delaunay triangulation. Well, you have to filter the triangles that have the wrong orientation, but that''s pretty trivial. The really hard part is implementing a 3D convex hull algorithm.
The hardware-accelerated 2D computation of the Voronoi diagram is based on drawing paraboloids centered on each point, using the Z-buffer to find out what is the closest point to any pixel. The paraboloid can be stored as a texture and will be fast to render. The fill-rate required is probably too high, though. I think I saw this method on the OpenGL 1.2 Red book.
After I wrote all that, I just found a great link:
http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html
Another method of computing the Dealunay triangulation is adding the points one by one, removing the existing triangles that contain the new point in the circumscript circle and adding triangles that have the new point as a vertex and a side of the just-created "hole" as opposite side.
Yet another method would be to add a third coordinate to each point, like this:
(x, y) |-> (x, y, x^2+y^2)
The [3D] convex hull of the resulting will project to the Delaunay triangulation. Well, you have to filter the triangles that have the wrong orientation, but that''s pretty trivial. The really hard part is implementing a 3D convex hull algorithm.
The hardware-accelerated 2D computation of the Voronoi diagram is based on drawing paraboloids centered on each point, using the Z-buffer to find out what is the closest point to any pixel. The paraboloid can be stored as a texture and will be fast to render. The fill-rate required is probably too high, though. I think I saw this method on the OpenGL 1.2 Red book.
After I wrote all that, I just found a great link:
http://www.gris.uni-tuebingen.de/gris/proj/dt/dteng.html
Since you can get data back from the frame buffer of a video card perhaps using this instead of the CPU could be a goer?
I believe he''s referring to <a href=http://portal.acm.org/citation.cfm?id=311567&coll=ACM&dl=ACM&CFID=12121416&CFTOKEN=31117499>this</a> paper from UNC in ''99.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
