Convex-Convex collision detection issues

[Dirk Gregorius]

Yeah this makes sense because all the parallel edges have different representations on the unit sphere. In other words, they have different adjacent faces. So the quick edge-edge test only helps for shapes that have few parallel edges, like a tetrahedron.

Does this also mean that we might need to test the same direction twice, since they have different representations on the unit sphere.

You can compute the line-line distance using the edge vertices.

Indeed, but only if the edges build a Minkowski face on the unit face. Otherwise I need to query for the extremal vertices in this direction. Right?

[Erin Catto]

Does this also mean that we might need to test the same direction twice, since they have different representations on the unit sphere.

Sad but true. At least it is O(1).

Indeed, but only if the edges build a Minkowski face on the unit face. Otherwise I need to query for the extremal vertices in this direction. Right?

No, if the edge pair does not cross on the unit sphere, then you can skip that pair.

[Dirk Gregorius]

Sad but true. At least it is O(1).

At least we can skip edge directions that are parallel to face normals

No, if the edge pair does not cross on the unit sphere, then you can skip that pair.

Right, I was more thinking about how to find the distance in a setup like Pierre's example code. Here you cannot guarantee that the edges are extremal in the edge direction (or cross on the unit sphere) and therefore you must query.

[Dirk Gregorius]

Erin,

you mentioned that you used the QuadEdge data structure for your implementation. I used a DCEL mesh instead and both have similar high memory requirements I guess. For the unit sphere test we would only need two additional indices into a normal array per edge. Are you still planning to continue to use a QuadEdge structure?

BTW:
Tokamak has also an interesting implementation of the mentioned paper.

[Erin Catto]

You can compress the QuadEdge structure quite a bit by limiting the number of features. This way you can use bytes for indices (and don't use pointers). I also recommend storing data as simple arrays. This gets around padding issues for SIMD types.

For example:

Code: Select all

struct SubEdge
{
   uint8 index; // 0-3
   uint8 next; // next edge in circular list for tail feature
   uint8 tailFeature; // vertex or face depending on index being odd or even.
};

struct Polytope
{
   int32 edgeCount;
   SubEdge* edges; // 4x the number of real edges

   int32 vertexCount;
   Vec3* vertices;
   uint8* vertexEdges; // one for each vertex

   int32 faceCount;
   Vec4* facePlanes;
   uint8* faceEdges; // one for each face
};

A box would take:

4 + 12 * 4 * 3 + 4 + 8 * 16 + 8 + 4 + 6 * 16 + 6 = 394 bytes

Since we are likely to be limited by the edge count, we can probably combine index and tailFeature into a single byte.

4 + 12 * 4 * 2 + 4 + 8 * 16 + 8 + 4 + 6 * 16 + 6 = 346 bytes

On the other hand, having no topology takes:

4 + 8 * 16 + 4 + 6 * 16 = 232 bytes

So there is about a 50% tax for having topology.

The nice thing about the Quad-Edge structure is that you can quickly:
- find all the edges/vertices on a face
- find all the edges/faces connected to a vertex
- find all the faces adjacent to a face
- find all the vertices adjacent to a vertex

It seems that the DCEL has trouble with some of these. For example, can you quickly find all the edges attached to a vertex? For the quad-edge structure it is just traversal of a circular list.