Main Page Class Hierarchy Compound List File List Compound Members

csTesselator Class Reference

A general purpose tesselation mechanism. More...

#include <tesselat.h>

List of all members.

Static Public Methods

int Tesselate (const GridCell &, csVector3 *vertices)

Detailed Description

A general purpose tesselation mechanism.

To use, simply fill a grid cell struct with the required corner positions and values. Allocate at least 15 vertices in the vertices buffer and hand it to tesselate. It will return the filled buffer and the number of vertices it contains. The buffer will contain up to 15 vertices in multiples of three, each representing a triangle. The normals point inward, so to obtain a concave hull from the list, assign the vertices in order to a triangle. To obtain a convex hull, swap two of the vertices (1 and 3 does nicely). The algorithm is just about bullet proof, however there are a few simple rules to using the algorithm:

If you feed it NaNs in the grid cell value, it will produce NaNs in the output vertex list. It won't barf, but your app might.
If you don't allocate at least fifteen vertices for the vertex list, then you will get a segmentation fault (eventually).
The grid cell does not have to be a perfect cube. It could be a frustum for example.

The grid cell does have a specific vertex order. The following is a list of the vertex order (cube extends from <0,0,0> to <1,1,1>).

     p[0]: (0,1,1)
     p[1]: (1,1,1)
     p[2]: (1,1,0)
     p[3]: (0,1,0)
     p[4]: (0,0,1)
     p[5]: (1,0,1)
     p[6]: (1,0,0)
     p[7]: (0,0,0)

The method behind the tesselator is a very simple structure of a point interpolation algorithm and two tables containing the edge results of the cube filter and a triangle interpretation table to complete the mapping. Upon entry ( after initializing values ), the algorithm first evaluates each corner of the grid cell to test if it is greater or less than zero. For each corner that is less than zero, an index flag is set on the edge index (cubeindex). It is probably not without coincidence that the number of corner flags in a cube neatly fits into a single byte.

The edge table represents a vertex outcome based on the the corner map it was supplied. It is a twelve bit mapping respresenting each edge of the cube. The order is specifc, and these are the edge vertices. (This table is based on the one earlier on.)

  bit 0: p[0] - p[1]
  bit 1: p[1] - p[2]
  bit 2: p[2] - p[3]
  bit 3: p[3] - p[0]
  bit 4: p[4] - p[5]
  bit 5: p[5] - p[6]
  bit 6: p[6] - p[7]
  bit 7: p[7] - p[4]
  bit 8: p[0] - p[4]
  bit 9: p[1] - p[5]
  bit 10: p[2] - p[6]
  bit 11: p[3] - p[7]
 *

For each state where one vertex is greater than zero and its nieghbour is is less than zero, a corresopnding flag is set by the edge table. After all edges that incur an intersection are set, the next step is interpolating the intersection vertices. The interpolation algorithm uses the values of each corner (GridCell.val[]) to produce a linear estimate of where the intersection with the edge occurs. This is not 100% accurate, but does provide a nice approximation.

The triangle table is a scripted set of triangle maps based on the cube index. It contains 256 mappings with up to five triangles. The sixteenth element of every mapping is -1, to terminate the mapping. In many cases, the map table is filled with terminations after two or three triangles. Now although there are only twelve resultant vertices from the interpolation unit, in some cases, a given edge vertex may be used up to four times in a given mapping, resulting in a maximum of fifteen vertices in the output.

Examples of fast methods to fill the grid cell can be found in the MetaBall mesh plugin and the metagen mesh plugin (CS/plugins/mesh/metaball/object/process.cpp and CS/plugins/mesh/metagen/object/mgproc.cpp, respectively).

The documentation for this class was generated from the following file:

tesselat.h