Created 2005-01-03 Modified 2009-04-11
Chelton Evans
Chelton's Convex Mesh Algorithm : Definitions
Chelton's Convex Mesh Algorithm: Home
A simplex is the simplest shape of a particular dimension. A simplex in 2D is a triangle, in 3D is a tetrahedron. The plural of simplex is simplexes.
Define a face as a boundary opposite a vertex.
Define a neighbor as a link to another primitive shape of the same dimension. The exception is where there is no neighbor and so the link is null or zero. The faces link to other faces. Each face has a neighbor.
Let a primitive shape be a linked data structure. Let each simplex have a link to its neighbor for each face. Call one or more of these linked data structures a simplex mesh. Let the mesh have a virtual simplex. There is only one virtual simplex in a simplex mesh, and it exists when the mesh is non-empty. It is superimposed on an existing mesh simplex. However its orientation is independent of the shape it sits on top of. Let a mesh have a cp which is a pointer to a current simplex in the mesh and hence points to the virtual simplex too.
Each primitive shape has an orientation which is the order in which its vertexes occur.
Let a convex mesh be a mesh where any two points in the mesh are visible to each other. ie all the points on the line connecting these two points are also in the mesh. The convex mesh is a representation of a convex polygon with the linked simplexes data structure.
Let a boundary also be a list of simplexes which are linked together. I am using this term loosely and mixing it in with the mathematical boundary, because this can be directly obtained from it. Further I often call a boundary a surface as it is the outer boundary or face.
For example in 2D a boundary is a curve, in 3D a boundary is a surface. For generality I called movement on the boundary surface operators whether they are in 2D or 3D.
Another type of a boundary is the outside boundary with neighbors that are null. In this sense we have a collection of linked simplexes which together form the boundary, but may be only connected on the surface - or more formally they all share N points with another simplex in the collection in N dimensional space.
These are examples of 2D and 3D meshes respectively. I developed data structures for the mesh primitives. The mesh primitives link together to form the mesh.
The structure generalizes to any dimension. Notice that face i is defined to be opposite point i.
Further the winding is defined by the order of the first n points in dimension n. In 2D the primitive has anticlockwise winding for points 0,1. In 3D the primitive from the perspective of outside the tetrahedron has the first three points define a anticlockwise winding triangle. Viewing the face from outside the tetrahedron. All other faces have their winding defined by assuming the first three points are anticlockwise.
This lets the tetrahedron be defined as an ordered list of four points. The links are called neighbors and are defined to be the face opposite the associated point.
For the tetrahedron the back faces have a clockwise winding.
With this data structure and mesh operators on the data
structure are naturally defined. These help with algorithms
and allow the mesh to be exploited. For example I used
the getanticlockwiseface operator on D3 mesh
primitive when re-tessellating the mesh, I avoided recalculating
three points clockwise or anticlockwise nature and extracted
it from the mesh. Here are some of the D3 tetrahedron operators.
pi[] - access a point piInverse - find the local index of the point ni[] - access a neighbor niInverse - find the local index of the neighbor getanticlockwiseface - gets local indexes of the face opposite the associated pointI am going to present some slightly unusual notation for these operators. Instead of a dot to indicate multiplication I will use it to mean access. Programmers will recognize such a notation immediately, as this is what is done in practice when writing computer programs. I am going to assume the reader is ok with this.
Let x be an instance of a linked simplex { p0, p1,...pN, n0,...nN } in dimension N. All these elements are indexes into point and simplexes vectors, so ni and pi are integers.
Let operator x.pi access or get the index pi.
Let operator x.ni access or get the neighbor index ni.
Let the local index be 0 <= i < N.
Let operator x.pi-1 be the inverse of pi and given the point pi return the local index associated with that point.
Let operator x.ni-1 be the inverse of ni and given the neighboring simplex ni return the local index associated with the neighbor.
If the inverse does not exist I leave the result undefined. In practice you can capture such situations and make sure they never happen.
These operators can take advantage of the face being opposite the point with the same index.
These operators are used for extracting information from the mesh. In the mesh we have no guarantees of the orientation of the simplexes. Using these operators we can find the orientation. These are used by most of the algorithms in this paper.
The winding of the points can be determined from the ordering. Label the indexes from 0 onwards.
Let k be the index which is dropped. The following formula gives the anticlockwise winding of N points in dimension N.
Drop the k'th index. If Odd(N+k) then reverse the remaining order of the indexes.
For example in 2D the test is Odd(2+k) = Odd(k). In 3D the test is Odd(3+k) = Even(k).
| Dimension 2 | {0,1,2} |
| k | permutation |
| 0 | {12} |
| 1 | {20} |
| 2 | {01} |
| Dimension 3 | {0,1,2,3} |
| k | permutation |
| 0 | {321} |
| 1 | {023} |
| 2 | {310} |
| 3 | {012} |
This could also be viewed as an operator - given the local index k find the anticlockwise ordering opposite k.
An example of this is finding the anticlockwise face opposite a point. In practice the maths is avoided and a case statement considers all the possibilities.
I believe this will work in higher dimensions. If the anticlockwise ordering generalizes in this way then this result is useful for someone building such an operator in higher dimensions.
Convexity is very important in mathematics and geometry. If an object is convex, any two points inside the object have all the points between them inside the object if it is a convex object.
The first test involves half-spaces which are visually easy to understand. Is the point viewable from the half space?
The second test is more geometric and may be computationally faster. It reduces n half space queries in n dimensions to one line intersection with one half space in n dimension. The boundary borders the two shapes.
Another test for partial convexity uses the data structure indexing in to integers. By looking at two shapes if they share neighbors other than each other and the mesh is convex then the two shapes can not be convex.
While this test is partial and captured less than 10% of the non-convex cases for one trial I did, it may be developed further for certain meshes that are more balanced and its performance could increase. It essentially does the arithmetic with integers without the need to use non-integer arithmetic such as constructing planes, finding their intersections, ... It is for this reason that it is of interest because if the information can be got from the mesh alone there may not be a need recompute it or use non-integer arithmetic.
Here is an example where I used this property to identify a corrupted mesh. I was expecting tetrahedrons 6 and 7 to be convex. Since they share neighbor 16 they can't be convex.
p0 p1 p2 p3 n0 n1 n2 n3
6: 9 1 3 16 9 13 16 7
7: 1 9 3 4 3 0 16 6
Zero is used to indicate no point or tetrahedron. This is a mesh with a few unused points. The fourth coordinate in points is also unused. It holds the value of a some function of the other three coordinates.
ptsz=10 1 (0,1,0,0) 2 (0,-1,0,0) 3 (1,0,0,0) 4 (-0.2,0,-0.7,0) 5 (-0.5,0.1,0.7,0) 6 (0.566198,-0.211234,0.680375,0) 7 (-0.604897,0.823295,0.59688,0) 8 (-0.444451,0.536459,-0.329554,0) 9 (0.257742,-0.0452059,0.10794,0) visz=6 1 4 3 5 1 0 0 0 2 2 5 3 4 9 3 4 5 1 3 2 4 3 9 2 5 4 0 4 2 5 4 9 2 3 5 0 5 2 3 5 9 2 4 3 0
What makes this data structure useful is that it has a current state, exactly like a current pointer in a linked list data structure. In addition to pointing to a simplex in the mesh, the cp also has a virtual simplex imposed on it. The virtual simplex can be rotated and moved freely about the mesh without changing the links.
Consequently the mesh links are static. For example moving through the mesh does not change these links.
Operators are defined with respect to the cp and virtual simplex. In 2D the virtual simplex is a triangle, in 3D a tetrahedron. Different representations of the virtual simplex are possible. I used an ordered list of local indexes to points because my first implementation used a representation that was difficult to extract the inverse of extracting the current state.
Firstly the question for a data structure is what is my orientation at this particular moment. A list of anticlockwise points gives this. Next the reverse or inverse question is given a boundary of points set the orientation to it.
An example where the inverse is used is in the move operators moving from one simplex to another in the mesh. The virtual simplexes base is set to the boundary of the previous tetrahedron with each move. As the orientation of the simplex mesh is unknown it is extracted from the mesh, and used to build the new virtual simplex.
The mesh structure has two arrays or vectors, one holding the data points and another the array of linked simplexes. Zero is used to indicate no point and no neighbor respectively. So the vectors start counting from 1 instead of zero.
The mesh is itself a new data structure. Operators can be written on it, for example I wrote algorithms for transforming two adjacent tetrahedrons to three, and its inverse on the mesh. So its quite general.
Other parts of the algorithm such as the fan use the operators which this data structure supports.
Offline algorithms use the cp to their advantage by inserting close to a previously inserted point.
The mesh is both a continuous and discrete data structure. It is a discrete data structure as points and simplexes are indexed with integers. The mesh is made up of a vector of such simplexes. So there are two separate areas of mesh consistency. One is that the points have been interpreted properly and in this sense this is the problem viewed with real number arithmetic. ie Constructed hyperplanes are valid and do not suffer from numerical stabilities.
However logical consistency in the mesh is not concerned with such issues, only that the mesh itself is consistent. This is the mesh viewed as a discrete data structure and can be expressed as mesh conditions.
Here in code the first two are expressed with the use of the linked simplex operators. Here is a routine which checks for logical mesh integrity.
Let vi[] be an array of simplexes.
Consider the integrity of the k'th simplex in N dimension
tessellation.
...
// Look at each neighbor for links.
for (uint i=0, nb; i<N; ++i)
{
nb = vi[k].ni[i];
if (nb==0)
continue;
bool res;
// Each point bordering neighbor must also be one
// of the neighbors own points.
for (uint w=0; w<N; ++w)
{
if (w==i)
continue;
vi[nb].piInverse( res, vi[k].pi[w] );
if (res==false)
return false;
}
// The neighbor must have a pointer back to k.
vi[nb].niInverse( res, k );
if (res==false)
return false;
}
The use of indexes to represent polygons is normal, and often implied. Data that uses points can also be represented using an integer index to the points and describing the data in terms of integers. In computer science these are referred to as indexed face sets.
However in tessellations I use face to refer to a simplex boundary and not the simplex itself. So I have named these data structures as indexed simplex sets. Unlike indexed face sets or general polygons the simplexes have a constant number of faces and points in their particular dimension. Further their faces to points is a one to one relationship.
Indexed Simplex Sets most remarkable property is that they can describe any tessellation. When you consider all the tessellation algorithms they all output sets of points. With slight modification every tessellation algorithm can output the points as a list and a list of the tessellation polygons in integers.
So indexed simplex sets are ideal for comparing and exchanging tessellation data. In particular outputting triangles in 2D and tetrahedrons in 3D.
Each simplex is a list of points indexing into a point vector.
{p0,p1,..,pN} where N is the dimension, pk is an integer index into a vector P of points in N dimension.
Here is an example of a tessellation in 2D being described by Indexed Simplex Sets. First there is a vector of the points, then a vector of triangles.
9 0 0 0 0 1 -0.996295 0.143588 2 0.834309 -0.754583 3 -0.544901 0.70803 4 -0.027826 -0.784223 5 0.808631 0.324033 6 -0.569744 0.251656 7 -0.323728 -0.439014 8 0.528323 0.626514 9 0 0 0 0 1 6 3 1 2 5 4 2 3 7 8 6 4 7 1 4 5 8 7 5 6 5 7 4 7 7 6 1 8 6 8 3
Through integer indexes points can be uniquely identified. For example in non integer arithmetic comparing two points may give the incorrect result subject to rounding errors. However if the points have integer arithmetic exact arithmetic is calculated and the result will be exact. So integer indexes in geometry aid algorithm design by removing possible non-uniqueness issues and making algorithms more reliable.
The other restriction I would like is to define Indexed Simplex Sets as having an anticlockwise point ordering. This is generally easily calculated except in degenerate cases. However such a property allows mathematical operators to be easily defined and gives the data structure some bite.
If the tessellation of the Indexed Simplex Set is correct then it can be transformed into a Linked Index Simplex Set. Wherever simplexes share a common face they have the point opposite the face point to the other simplex.
This data structure has special properties such that operators for transversing and querying the mesh are easily defined. Algorithms are then free to use these operators for implementation which is fundamentally different to the current situation where each algorithm largely stands on its own. ie general operators of movement and mesh transversal are not assumed.
Here is the same tessellation as before expressed as a Linked Indexed Simplex Set.
{p0,p1,..,pN, n0,n1,..,nN, } where N is the dimension, pk is an integer index into a vector P of points in N dimension and nk is an integer index into a vector V of simplexes in N dimension.
9 0 0 0 0 1 -0.996295 0.143588 2 0.834309 -0.754583 3 -0.544901 0.70803 4 -0.027826 -0.784223 5 0.808631 0.324033 6 -0.569744 0.251656 7 -0.323728 -0.439014 8 0.528323 0.626514 9 0 0 0 0 0 0 0 1 6 3 1 0 7 8 2 5 4 2 0 0 6 3 7 8 6 8 7 5 4 7 1 4 0 6 7 5 8 7 5 6 0 3 6 5 7 4 4 2 5 7 7 6 1 1 4 3 8 6 8 3 0 1 3
Zero is a special number in that in the context of a point it refers to a non existent point, and in the context of a neighbor it refers to an unconnected face which has no neighbor. In the graph it shows the origin too.
Linked Index Simplex Sets contain Indexed Simplex Sets as a subset. For example deleting all the neighbors data structure leaves a Index Simplex Set.
Here is an O(n) time algorithm for converting a non-linked Indexed Simplex Set to a linked one. The significance of this is that it costs no more (other than a constant factor) to use the linked data structure in time. Since the linked data structure provides mathematical operators and many properties for building and implementing algorithms why not use it (after the initial cost in implementing these operators).
This algorithm relies on sorting indexes of integers to the point and simplex indexes. Since the sort is on integers we can use the Radix sort which is O(n).
Create a mapping of points to simplexes {pi,tk}. Sort this on pi.
Consider a subset where pi is constant. Generate another mapping where {pa,tk} : a is not equal to i and tk contains pi. Sort on pa.
For 2D problems this leaves adjacent simplexes next to each other and having the same point in common. For 3D another similar sort is required. This is I believe a divide and conquer strategy .
Consider our tessellation example the points mapped to triangles mapping is as follows.
Points Triangles
1 1 4 7
2 2
3 1 8
4 2 4 6
5 2 5 6
6 1 3 7 8
7 3 4 5 6 7
8 3 5 8
Consider the first point. Triangle 1 without point 1 gives {3,1}, {6,1}. Triangle 4 gives {4,4}, {7,4}. Triangle 7 gives {6,7}, {7,7}. Ordering these by the point.
{3,1}
{4,4}
{6,1}
{6,7}
{7,4}
{7,7}
Discard 3 and 4, connect 1 and 7 on edge(1,6), connect 4 and 7 on edge(1,7).
The easiest way to compare tessellations is visually. Give the algorithms the same input and compare the meshes generated.
Another comparison is looking at their meshes. Particularly when the two meshes share the same point vector. Their simplexes can be compared for equality in constant time.
Indexed Simplex Sets and Linked Index Simplex Sets can be compared by converting on to the other. If both are Linked Index Simplex Sets then the comparison is O(n). First find a common simplex which takes O(n) time. Then transverse the respective meshes and although the simplexes are indexed differently if the meshes are equal the geometry will be the same and the points will correlate.