Regular Triangulations of Cube

Question

I want to figure out which triangulations of the cube (i.e., partitions into tetrahedra using only the $8$ given vertices) are regular, but I'm not sure how to easily tell whether a given triangulation is regular. Is there some condition I can check relatively quickly to see if a particular triangulation is regular?

Edit: A triangulation of the cube is regular if there exists a convex piecewise-linear function from the cube to $\mathbb R$ such that the projection of the boundaries of the regions of linearity onto the cube gives the triangulation.

Answer 1

I have no solution at present, but I think that turning to barycentric coordinates (or tetrahedral coordinates) would be very beneficial. This system is used by two applied maths communities: "finite elements computing" and - increasingly - "computer graphism".

It means converting the cartesian formulation (x,y,z) into a formulation with (a,b,c,d) (normalized by $a+b+c+d=1$ that can be given a physical interpretation as "weights").

What is their principle? Being given a point M inside (or outside) ABCD, its barycentric (or tetrahedral) coordinates are the (unique!) (a,b,c,d)=(a,b,c,1-a-b-c) such that M is the weighted average of $A$ with weight $a$, $B$ with weight $b$... This is written: M=aA+bB+cC+dD;

This could be done either by fixing a reference tetrahedron and computing all with respect to it, or define a system of barycentric coordinates with respect to each tetrahedron of your "tetrahedrization" ; Barycentric coordinates behave well with respect to linearity and convexity.

3 references among many:

A nice presentation that can be found on the internet : Cupisz_Robert_Light_Probe_Interpolation.pdf

A lot of pointers can be found in : https://gist.github.com/paniq/8bdec20d00d08810f081

See also the article: "Barycentric coordinates for convex sets" by Warren, Schaefer, Hirani, Desbrun, in Advances in Computational Mathematics (2007) 27: 319-338

Answer 2

Telling whether a given triangulation is regular amounts to feasibility of a certain linear program: your variables are the values of the piece-wise linear function at the vertices. Inequalities express the fact that linearly interpolating the values at vertices on each simplex of your given triangulation the result is a convex function. There is one such inequality for each pair of adjacent tetrahedra.

A more combinatorial sufficient (but not always necessary) condition is that all lexicographic triangulations are regular. It turns out that all triangulations of the 3-cube are lexicographic, hence they are all regular. The same is not true for the $4$-cube.

Some references: both the chapter on Triangulations from the Handbook of Discrete and Computational Geometry, and my book on triangulations both have a section on triangulations of cubes.