Hi, I''m trying to do a convex hull - convex hull collision detection algorythm... I''ve been lookin on the net and I found a lot of docs, most of them useless (too much maths, or too little) when reading about them I found terms like "rule of the separating axis", "voronoi diagrams" and other exotic terms... The way I am planning to do the algorythm is the next: for every convex hull, I do a loop for all its faces, and check if all the vertices of the other convex hull are in the outer side of the plane, if I find a plane with all the vertices in the outer side, no collision occurred and exit. If both loops failed on both convex hulls there was a collision between them. Is this method correct? is there a faster method? thanks

are you looking to generate convex hull or just collision b/w them. If so OPCODE can do very fast poly collision test.

Use the V-Clip algorithm (google it). There''s a java implementation here: http://www.cs.ubc.ca/~lloyd/java/vclip.html

I''m trying to detect collision detection between convex hulls.

I already know about the v-clip (voronoi clipping) papers, the problem is that I''m not so deep in math terminology to understand the full document.

Also have Linn-Canny documents, opcode libraries and other stuff...

But usually most of these documents I''ve seen are too academic, or too bogus to understand...

What I would like is an overview explanation about how convex hull collision detection works, if it is possible, for the voronoi-clip algo, so I can have a general idea about how it works. Something like "for every face, do that, for every vertex, do this"...

Your algorithm will work. (It''s actually the basic collision detection algorithm). And you may not even have to run the loop twice (once for each object) as if object A doesn''t penetrate object B we can be relatively sure object B doesn''t penetrate object A either(1) .
However, the downfall of this technique is it has a complexity of n^2 (mathematically speaking that is, but don''t get scared). It means that if surface A has x vertices and surface B has y polygons you will has to do x*y comparisons. So say you add a single vertex to surface A your will have to do y extra comparisons.
Bottom line this is a lot and it''s unreliable (number of comparisons grows wildly with small changes to the scene).

Most algorithms you''ll find look for ways to reduce the number of polygon/surfaces that have to be compared against each other. You might want to try working with bounding boxes and only testing two surfaces if thier bounding boxes penetrate each other.

I read up Voronoi diagrams but the impression I got is that it would have to be seriously modified in order to run real time. (I could be wrong)

I recomend you read up bounding boxes and octtrees. You might be interested in the BSP algorithm as well. A lot of graphics engines use it to sort the world for rendering and you could easily modify it to simplify object collision however it is a bit mathematical.

P/s
Don''t avoid mathematics (Heck it''s the name of the Forum). I recommend you pick up as much of it as you can along the way. It''s invaluable to programming.


1) Although, you should be careful cuz a set of vertices does not define the entire object. It is quite possible for a vertex from A to penetrate a plane from B without any of B''s vertices even touching A. It all depends on the shape of your objects and level of accuracy you want. It''s even possible for two obects to penetrate each other even though none of the vertices are penetrating.

Phew!! Long post. Hope there was something usefull somewhere in that mess

---------------------------------------------------
There are two things he who seeks wisdom must understand...
Love... and Wudan!

No your algo is false. You forget the edge/edge collisions and even the rare cases of vertex/vertex or plane/plane collsions.

The Voronoi diagram of a convex hull is not so difficult to understand.

For each face of your polytope, each of its edges draw a plane perpedicular to the face that holds the edge. You see it ? Ez. You have a kind of cylinder closed by the face at one end. What is this volume ? It contains all the points that will necessarilly be nearer to this face (a clipped plane) than to any other 0d (vertex), 1d(edge) or 2d(face) facet of your convex hull. Now apart these cylinders, check the other semi infinite convex volumes you have delimited with all these "border" planes. You'll find the volumes nearest to each of your convex hull vertices, and the volumes nearest to each of your convex hull edges.

I can't make it clearer. All this 3D space partition is called the voronoi diagram of the convex hull. You can now link each volume to each other. Each link will be a partition (border) plane. For instance if you follow a smoothly moving point it will be easy to check which partition plane it crosses first and directly find the next sub volume (Voronoi cell) which directly gives you the facet (vertex edge or face) currently nearest to your point.

For convex/convex test it's a bit more complex but all exact algos in fact use the Voronoi diagram hidden or not. All in all it's using space/time coherency and a precomputed graph to do only the miminum geometric tests required.

BTW a proof that it's not so hard to understand is that I found the idea alone before I ever heard of Voronoi. That's a pure patient deductive resolution of the problem. Maybe this also helped me to reckonize and understand quickly the issue when I first read about Voronoi diagrams.

[edited by - Charles B on July 4, 2003 6:23:10 PM]

quote:

---

Original post by Charles B
BTW a proof that it's not so hard to understand is that I found the idea alone before I ever heard of Voronoi. That's a pure patient deductive resolution of the problem. Maybe this also helped me to reckonize and understand quickly the issue when I first read about Voronoi diagrams.

---

You and me both. And I thought I was being inovative. Bah. But I agree, it's a great method. I personally haven't read about Voronoi diagrams, as I only used the concept in a limited way to find the rough mimimum distance between two non-overlapping convex polyhedra, but it was a very neat concept.

[edited by - Zipster on July 5, 2003 3:02:13 AM]

So this confirms I am not a genius or else we''re surrounded by geniuses in these threads )

Hmm, put that way Voronoi does seem a lot more straight forward but does that mean if you have say five objects you are constantly keeping track of the set of closest faces each of the objects have with all the others?

Isn''t that computationally expensive?

Although you might be able to combine it with some other system which only tests objects that are at risk of colliding.

quote:

---

No your algo is false. You forget the edge/edge collisions and even the rare cases of vertex/vertex or plane/plane collsions.

---

Well, I still say it can work depending on the level of accuracy needed and the way the models are designed (not all problems have to be solved by code you know) vertex/vertex and plane/plane collision can always be resolved into multiple vertex/plane collisions. and usually when two edges collide a vertex will be colliding soon after.
Alternatively you could just add a test for edge/edge collision and the algorithm will be perfect. (That''s what I used)


---------------------------------------------------
There are two things he who seeks wisdom must understand...
Love... and Wudan!

quote:

---

Original post by Charles B
No your algo is false. You forget the edge/edge collisions and even the rare cases of vertex/vertex or plane/plane collsions.

The Voronoi diagram of a convex hull is not so difficult to understand.

For each face of your polytope, each of its edges draw a plane perpedicular to the face that holds the edge. You see it ? Ez. You have a kind of cylinder closed by the face at one end. What is this volume ? It contains all the points that will necessarilly be nearer to this face (a clipped plane) than to any other 0d (vertex), 1d(edge) or 2d(face) facet of your convex hull. Now apart these cylinders, check the other semi infinite convex volumes you have delimited with all these "border" planes. You''ll find the volumes nearest to each of your convex hull vertices, and the volumes nearest to each of your convex hull edges.

[edited by - Charles B on July 4, 2003 6:23:10 PM]

---

Ok, now I think I understand the basics of voronoi diagram.

So, tell me if this is correct:

for a polytope, I subdivide its surrounding space with planes, and, to know if something is inside/outside, I chech all the vertices of the second polytope against all the areas defined by the subdivision planes: if I find a vertex that it is not in any of these areas, it has to neccesarily be inside the polytope.

So, if I want to check a vertex, I only have to check in which area it is, and for a two convex hull, I only have to check all the vertices of one of them against all the areas of the other.

right?