Created 2004-07-17 Modified 2007-01-01
Chelton Evans
Marching Triangles, Squares, Cubes, Tetrahedrons
Non-Uniqueness
Uniform Grids
Displaying Contours with Marching Triangles
Simple Marching Tetrahedrons
Marching Tetrahedrons with Minimum Tetrahedrons
Non-Uniform Grids
Integration
In 2D Area Calculation with Splines
References
These methods belong to scientific visualization and are used to plot lines in 2D and surfaces in 3D. However they can be used for other things such as area or volume calculations. This is because they divide the space into shapes. The algorithm applies itself to each shape in the space.
Consider a space of points. A point is classified as either above or not above a c value. In diagrams the point is given a color to say which one of two states the point is in. Between two points a line can be constructed. If the two points are different colors ( one of the points is above and the other is not above the c value ) then somewhere on the line is a c value.
By interpolation (usually linear) the c value may be guessed. Its a good guess and as the distance between the points is reduced the guess gets more accurate. ie limiting to the true situation.
Geometry is used: the sample points define the geometry. From the sample points the intersection points are generated. The geometry says how to interpret the sample points.
The geometry is usually a primitive shape. eg marching squares has the square as the geometry. Marching triangle uses the triangle as a primitive shape. Marching refers to iterating over some space.
My first introduction to the marching algorithms was through uniform grids. Indeed its good to look at the two dimensional versions first before you look at the three dimensions because the pattern is obvious. Squares in 2D generalize to cubes in 3D, triangles in 2D generalize to tetrahedrons in 3D.
Divide the volume up into slices. Each slice is then divided into cubes, which are then divided into triangles.
Marching Cubes is often implemented because everybody knows what a cube is and its easy to divide space into cubes. The simplest marching tetrahedrons algorithm is to divide a cube into tetrahedrons.
I came across a paper[2] on the Internet which minimized the number of tetrahedrons in the cube to five. To match up their are two cube decompositions, which alternate in the grid of cubes. Make the decision on whether i+j+k is odd or even as to which cube decomposition the cube in the grid is.
If you have not noticed the cubes color lines should match when joining two cubes.
This grid structure reduces the number of tetrahedrons by about 15% from the previous Simple Marching Tetrahedrons data structure as each cube has five instead of six tetrahedrons. This means about 15% less triangles need to be processed.
These are really interesting, so interesting that I have spent about a year looking at tessellations. It all came about when I asked the question what is good geometry for marching methods and why?
Firstly freeing yourself from a fixed grid is critical. It is only in specific certain situations that experimental data would fit the grid. The other major factor was surface artifacts. I had forever being hearing my boss moan about artifacts on surfaces that well in my naivety thought that they would not be a good thing. So when I discovered that the marching triangles and tetrahedrons did not have severe artifact problems like marching cubes and squares, I turned my attention(obsession) to these things. (Marching with primitive shapes does not remove the uncertainty or necessarily make a better numeric approximation, but a smooth surface helps in calculations, visual appearance, ambiguity, ... )
The other major find was that marching triangles/tetrahedrons works with any set of points. You have decoupled the grid geometry from the shape geometry. There are still a few surprises to be found, but these can be overcome with a balanced mesh. See triangle for C++ implementation and algorithm development.
The shape chosen to be the basic shape of the algorithm determines how ambiguities result. For example marching squares has three possibilities that can occur with two colors alternating. There are ways of looking at neighboring squares to help determine which of the three possible choices is best but that is too complicated for me.
Marching triangles over a square grid divides each square in two. With marching triangles there are no ambiguous cases. Because there is no ambiguity a better curve results. There are twice as many shapes to consider you get a much better result. The boundary region will not have artifacts or holes in the boundary.
In 3D the situation is similar. There is less computation with a cube but much more ambiguity and I believe marching cubes leaves holes in the boundary. By contrast marching tetrahedrons does not. The cube can be divided into 6 tetrahedrons so a rough guess that marching tetrahedrons is about 3 times more expensive than the cube but more accurate too. A way to compare there results is to vary their cubes sizes such that both are producing the same number of boundary triangles. Then compare the computational costs, memory use, ... The easiest and perhaps best solution is to just implement marching tetrahedrons the best solution.
Triangles and tetrahedrons are the most primitive 2D and 3D objects. By using these better boundaries are found, the algorithm is much less complicated to implement because there are reduced cases to consider.
Beware of pathological data. For most grids/volumes use right angled shapes. For right angled data such as walls there could be serious issues.
Since there is no ambiguity the curves constructed are smooth and without artifacts. Compare this with marching squares.
More cases to consider and ambiguity needs to be resolved. In practice choose one of the ambiguous cases and use it for all such situations.
The marching algorithms success is in their spectacular visual display of surfaces. While this gets the press, there is no doubt that the marching algorithms are useful for summing areas and volumes too. For example we may wish to extract the surface area information of a surface, the same marching algorithm would be used but instead of displaying the surface it calculates its area instead.
You do not have to think much to imagine multiple ways of summing areas/volumes. In some situations fixed size primitive shape tessellations could be used for fast area calculations. Or maybe decimation on the inner hull points so there is much less shapes to sum.
Cutting up the triangle with a straight line always seems to lead to an underestimate of the area. While the boundary intersection points of the curve are found by linear interpolation along the triangle edges, the curve itself can be interpolated with splines and the area calculation make more exact.
Assuming we have some way to calculate the normals at each of the points the basic spline can be calculated, see 2D Vector Curve Fitting.