📐 Converting Geometry to Tetrahedral mesh.

[Usnul]

Susanne, converted into a bunch of tetrahedrons

Slightly more interesting example, a bedroom scene with complex and highly convex objects

But Alex, why convert a geometry into a bunch of tetrahedrons?

I’m glad you asked, I was afraid you wouldn’t. Tetrahedrons have a massive advantage when it comes to analysis. Because tetrahedron is the simplest volume-enclosing 3d shape.

If you want to do physics with a random 3d mesh - you generally can’t. And not because I withhold permission, by all means - you have my blessing. The problem is that it’s very hard. However, checking for collisions with convex shapes is much easier.

Some shapes area already convex, such as a sphere, or a box. But most real-world meshes are not fully convex. Many physics engine cheat, and shrink-wrap a mesh into a convex hull. This lets you do physics on the mesh, but you lose an enormous amount of detail. Let me demonstrate in 2D. Let’s pretend this is a chair

And here’s what the convex hull of it would look like

Imagine you try to drop a ball onto the chair now

The ball bounces off an invisible slope. Siminarly, try to place a ball underneath

The chair will hover in the air above for a moment and tip over on the side

So… tetrahedrons are awesome, because they allow you to describe the shape exactly, while keeping the convex property, so you can do collision detection.

Tetrahedral mesh itself is also super useful for finite element methods, that is - imagine you wanted to propagate a force or heat through an object. Tetrahedral mesh has a notion of neighbours

Incidentally, soft-body dynamics often is implemented using this exact method.

If anyone is specifically interested, it’s under /core/geom/3d/tetrahedra/compute_tetrahedral_mesh_from_surface in Meep Engine.

The work is heavily built on top of tetrahedral mesh generation system I already built in the past for light probe volumes.

Related topics:

• Gentle Light Probing
• Tetrahedral Mesh Generation with points
• Soft body physics in 3D on three.js.
• Finite element analysis web app - #2 by Antonio

[red-reddington]

@Usnul I always learn something from your posts. The consistency and technical quality are exceptional. Thank You!

[PavelBoytchev]

I think CSG would love working with tetrahedrated models.

For traversing tetrahedrons, do you use some form of DCFL with half-faces (a 3D version of DCEL used for meshes)?

[Usnul]

@PavelBoytchev

For traversing tetrahedrons, do you use some form of DCFL with half-faces (a 3D version of DCEL used for meshes)?

Something like that, here’s the actual format:

     vertex_id_a :: uint32
     vertex_id_b :: uint32
     vertex_id_c :: uint32
     vertex_id_d :: uint32
     neighbour_a :: uint32         - neighbour tetrahedron, opposite to vertex A
     neighbour_b :: uint32         - neighbour tetrahedron, opposite to vertex B
     neighbour_c :: uint32         - neighbour tetrahedron, opposite to vertex C
     neighbour_d :: uint32         - neighbour tetrahedron, opposite to vertex D

There’s a slight quirk to it, neighbours are encoded, we reserve 2 lower bits for encoding opposing apex index:

MSB -> [tet_id:30bit][opposite_corner_index:2bit] <- LSB

Hope that helps. I pack everything in binary, unless it wasn’t clear

There are advantages to doing so, in that you get blazing-fast traversal and tiny memory footprint, but it’s a lot harder to implement than a native JavaScript object & references approach.

It’s all still JS, just somewhat weird-looking JS with a speed near that of C

Anyway, tangent’s aside, the structure is a graph essentially. It is expected that you would use it together with some vertex data. Here’s an example of position-based vertices:

/**
     * Note that this method does not guarantee to find the containing tet in case of concave mesh, that is - if there is a gap between the starting tet and the countaining tet
     * @param {number} x
     * @param {number} y
     * @param {number} z
     * @param {number[]} points Positions of vertices of tetrahedrons
     * @param {number} [start_tetrahedron]
     * @returns {number} index of tetra or -1 if no containing tetra found
     */
    walkToTetraContainingPoint(x, y, z, points, start_tetrahedron = 0){
....
}

As you can see, we need to supply points, which is a side channel. Lets us keep tetrahedral mesh “pure” and usecase agnostic.