Archived

This topic is now archived and is closed to further replies.

Martel

Hardware Accellerated Voronoi

Recommended Posts

Martel    122
Has anyone implemented this? I''m curious if the low resolution and aliasing causes problems, and how it affects the range you can map.

Share this post


Link to post
Share on other sites
fup    463
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.

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites
Martel    122
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]

Share this post


Link to post
Share on other sites
Timkin    864
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

Share this post


Link to post
Share on other sites
alvaro    21266
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Neoshaman    180
how far can we go by using a video card strenght to other things than graphic?? i''m interesting by ripping some power of the video acceleration for other stuff...

>>>>>>>>>>>>>>>
be good
be evil
but do it WELL
>>>>>>>>>>>>>>>

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Hmm cards are suited to perform matrix transformations upon large static data sets. Now with shader languages they can perform more complex operations as well. With cards texture operators, it might be possible to generate influence maps with thousands of individual effector fields. Extracting and interperting the data would be somewhat of a challenge. Also although different cards support the same operations, the''re not guarenteed to match.

It''s defintely an intresting idea.

-ddn

Share this post


Link to post
Share on other sites