# Marching tetrahedra (or cubes) on a non-orthogonal 3D grid

I have data for points of a 3D grid. The points of the grid are generated from three nonorthogonal vectors: each grid point has coordinates $\mathbf{q}_{ijk} = i \mathbf{a} + j \mathbf{b} + k \mathbf{c}$, where $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{c}$ are nonorthogonal, noncoplanar vectors. (In cristallography, it's called a triclinic system)

So, my question is: how would you adapt the marching tetrahedra (or marching cubes, if easier) to this case? Has this been treated already somewhere, is there software for that (I haven't found any).

-

## 1 Answer

Nothing in Marching Cubes (or Marching Tetrahedra, AFAIK) actually requires that the grid be cubical or even orthogonal; the algorithms are inherently topological (or arguably, combinatorial) in nature. The heart of Marching Cubes is really just a table matching the $2^8$ combinations of positive/negative function values at the cube corners to a set of topological triangulations that are consistent with the 'simplest' isosurface of a function taking on those values (e.g., when only one vertex is positive we have a single triangle, with vertices along the three edges connecting the positive vertex to its neighbors), and those triangulations are invariant under linear transformations - which is all your skewed grid represents.

-
I would agree for marching cubes. For tetrahedra, however, there is a choice to be made of how the tetrahedra are chosen, and I wonder what choice makes the more sense for a skewed grid. – F'x Dec 4 '10 at 9:30
While this answer is correct (you can skew the cubes (and even the space packing tetrahedra)) however you wish without affecting the algorithm. However Marching Cubes has some ambiguities that were resolved in the "Marching Cubes 33" paper. Marching tetrahedra does not have the ambiguity problem, and if you use a body-centered cubic layout for your tets, you can easily fill space that way. – bobobobo Jun 22 '13 at 15:52