Using Bullet for collision of two 3d tetrahedronal meshes?

[massing]

Hi there!

ATM I am investigating the use of Bullet in a finite element framework where we have to collide two 3D meshes. To be more precise
we have a 3D mesh consisting of tetrahedrons and a 3D meshes consisting of triangles. Then a collision map should be computed,
mapping indices of cells of the first mesh to the indices of the cells (of the second mesh) they are intersected by.
This can simply done by traversing the two bounding box tree by a standard tree traversal algorithm. So my basic question is whether this could in principal
be realized within the Bullet framework, I could not find any documentation that tetrahedronal also are supported.
Any pointers are very welcome!

Cheers,
Andre

[Erwin Coumans]

Hi,

You can represent a tetrahedral mesh as a btCompoundShape with convex child shapes as btConvexHullShape each with 4 vertices.

The 3d triangle mesh can be represented by the btBvhTriangleMeshShape, assuming it doesn't move (static, mass=0), if that's OK.

It is OK to update the vertex position, just make sure to call the void btCompoundShape::recalculateLocalAabb() and refresh the contact manifolds (if you use them).
As an alternative to contact manifolds, you can manually keep track of new contact points using a contact callback to get the triangle and/or tetrahedron index. See Bullet/Demos/ConvexDecompositionDemo for the index/contact callback (see MyContactCallback), you need to update it, the callback assumes two compound shapes, in your case you have a compound and a trimesh.

Alternatively, the btSoftBody can deal with tetrahedral meshes, and they can collide with 3d triangle meshes. One of the soft body demos shows them in action. See the Bullet/Demos/SoftDemo and use the ] key to switch to the next demo. I would first try the btCompoundShape/btBvhTriangleMeshShape though. Bullet uses a dynamic AABB tree acceleration structure that can be incrementally updated, as the nodes deform/change.

There are probably some more details needed, but this could get you started. By the way, for Bullet 3.x I'm also planning to add finite element method based simulation, so I will look into it further.
Thanks,
Erwin

[massing]

Hi,

thanks for the fast reply! A short question about the performances of your suggested approaches. My 3D tetrahedronal mesh has about 2 M tets
in the worst case and the 3D triangle surface about 15 k triangles. Will that it be possible to collide them in a reasonable amount of time (which means, say about < 5 sec on a rather fast laptop, to be very imprecise ) ? As I wrote I am first of all interested in the mapping describing which tetrahedrons are overlapped by which triangles, so no direct/complicated collision response is needed.

For now the triangle mesh is indeed static but the ultimate goal is to have that mesh moving (and the the tet mesh fixed/static).

Since I mainly work with FEM I am bit curious about what kind of finite element simulation you have in mind?

Thanks for help so far!
Cheers
Andre

[Erwin Coumans]

2M tets is a lot, can you share some test model?

I plan to use corotational linear implicit FEM, like Pixelux DMM, and extracted the code from OpenTissue. You can check the work-in-progress here:

https://github.com/erwincoumans/experiments

see the dynamics/corotational folder. You can use premake to generate build system files.
Thanks,
Erwin

[massing]

Hi again!

Unfortunately I have been traveling the last couple of days, so I could not reply as fast as you did Anyway thanks for the quick reply.
So, yes of course I like provide some test model if your interested in. The mesh format is special to our finite library DOLFIN (http://fenicsproject.org/)
but there is a converter script for various type of mesh formats. I just had a look at the benchmarks for a paper we are writing right now, and in fact
it was a 3D tetrahedronal mesh M1 consisting of 6.9 M tets which was collided with mesh M2 consisting of a 0.2 M tets or 15 K surface triangles.
To be a bit more precise there are two task:
First find all tetrahedrons in M1 which are intersected by the *surface* of M2 and collect the corresponding indices of the involved elements
Secondly, find all cells in M1 which are completely (as in zero measure outside) covered/included in the domain described by mesh 2.
So it is some sort of culling if I understood it correctly. ATM the I am using AABB trees either from the computational geometry libraries CGAL or. GTS. Finding the collision map goes rather
fast (it takes ca. 6 sec.vs. 100 sc for the whole simulation), but I would really like to implement a bullet based version to compare performances.

Our project is very interested in finding an appropriate collision detection framework which covers a broad scope of typical techniques and which is flexible enough
to extend our library. For instance time-dependent problems with one moving mesh and one fixed mesh is what we actually have in mind (with the same collision task as described above)
As far as I understood it bullet can take advantage of temporal coherence? And the insertion method for building the bbtree seems to be the right approach when dealing with meshes which might be adapted
over time..? But I have to emphasis that I come from a very different community so I might misunderstand some key concepts, so please tell me I am talking nonsense

Corotational linear implicit FEM was new to me, just glanced at a thesis right now, that's looks really interesting. So is your approach to take the Multibody Body Dynamics parts / FEM parts
from openTissue and use bullet instead of the collision tools provided by openTissue?

Kind regards,
Andre