1
$\begingroup$

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 Answers 1

3

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.

  • 0
    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.2010-12-04
  • 0
    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](http://users.polytech.unice.fr/~lingrand/MarchingCubes/algo.html) that were [resolved in the "Marching Cubes 33" paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.7139). 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.2013-06-22