Polygon soup with polygon soup collision detection

[colinvella]

I have a polygon soup geometry object whose elemental triangles are organised using a BVH. I have implemented reasonably robust collision detection code with boxes, spheres, cylinders and even convex polyhedrons, based on the fact that the latter geometry is a fully closed oriented manifold for which it is always possible to compute a penetration depth.

I wish however to implement collision detection between two instances of polygon soup geometry. I realise I can do this by testing the triangles of one instance with those of the other, using the respective BVHs to limit the combinatorial explosion. However I have my doubts on the robustness of the resulting tests. How does one ensure reasonable contact point data with normals and penetration depths? For the most part my triangle soups will be loaded from a model file that is generally well behaved, but I cannot assume this.

Would anyone please provide suggestions or point me to some appropriate papers and literature?

Cheers,
Colin

[Dirk Gregorius]

I think the general solution are signed distance maps. Look e.g. for the non-convex stacking paper by Erin Guendelman. Still I doubt that this will work in real-time applications. Ageia had something like this called PMAPS iirc, but now it is deprecated. I would suggest to go with convex decomposition.

[Pierre]

Yeah, PMAPS (with P = Penetration, not "Pierre" as a few people asked me!) were similar to distance maps (at least the theoretical aspects. The implementation had a few twists).

It works ok for certain meshes, as seen in that old demo of mine (http://www.codercorner.com/PhysicsTest.zip). However it doesn't work well for large open meshes and it consumes too much memory - even when compressed efficiently it's still too much.

So, yeah, I'd also suggest decomposing into convex parts.

[colinvella]

I have so far tried pre-computing penetration depths (positive inside, negative outside) and associated normals for the eight vertices of each AABB node constituting the BVH I am using to organise the triangles. For each vertex I basically locate the closest enclosed triangle and use its distance from the vertex and the triangle 'outward' normal. For any general point I then compute depth and a normal by trilinear interpolation of the samples assoviated with the node containing the test point

I was thinking of simply computing them on the fly as I would typically have only a few triangles per node anyway, once I descend into leaf-node testing.

Unfortunately convex decomposition is not always an option as I may be modelling an arbitrary environment which may not be a closed manifold. I basically need something that quantifies and qualifies the 'inside' of a mesh as reasonably as possible.

[goruka]

Ok, this is a question on the subject that now got me curious..

Is there any info or know techniques for convex decomposition? This is the first time i hear this term formally..

I remember that many years ago, i decided to add nonconvex support to an old engine i was working on by transforming the nonconvex mesh into convex sub-meshes... for this i used an algorithm similar to BSP
(although with priority in balance more than number of splits) and then the resulting tree i'd go from every leaf to the root creating a convex objects each time from the sets of planes in the middle. This worked fine, but as you can imagine, a lot of small convex polygons were created.. so i ended up eliminating those not connected to the original surface....so my question is are there better ways to tackle on this problem?

Cheers

[Nathanael]

Is there any info or know techniques for convex decomposition? This is the first time i hear this term formally...

The simplest way that I'm aware of is to recursively split the mesh with itself, (complete convex decomposition), then merge resulting convex sets based on some heuristic (aspect ratio, vertex count, etc..). That's very fast, one drawback is the creation of T-junctions that may need to be eliminated depending the application.

Let 'A' be a set of planes 'P' and features(vertice/faces) 'F'
-->If we can find a plane 'Q' in 'P' that split 'A' in two non empty parts
---->Split 'A' with 'Q' and store left/right parts in 'I' and 'J'
---->Repeat the procedure for 'I' and 'J'
-->Else
---->Done, 'A' is convex, store it in the leaves list.

As for the choice of splitting planes, random selection do just fine, else the first cuts are the most important for the quality of the end result, so it is worth spending some cycles the make 'good' choice for the first few levels.

Nathanael.