Created 2006-11-08 Modified 2007-01-01
Chelton Evans
Adaptive Tessellation
Intro
Standard Adaptive Tessellation
2D
3D
Simplex Splitting with Stitching
2D Splitting and Stitching
Linked Triangles Simple Adaptive Tessellation
Linked Tetrahedrons Simple Adaptive Tessellation
References
The major use of adaptive tessellation is with realizing parametric surfaces with discrete triangular meshes. For example if the gradient is changing rapidly then the surface is changing and it needs to be more finely tessellated.
While this is one view another is very different. The aim here is to generalize adaptive tessellation for 2 and 3 dimensions. A common theme of this is splitting a surface with a point. For a 2D object the surface is a 1D line. For a 3D object the surface is a triangle.
When the volume is represented not as a surface but as a tetrahedron mesh there comes a need to tessellate the mesh hence the need for the next highest dimension. Hence there is a need for adaptive tessellation in the third and higher dimensions.
All the combinations of points splitting the surface are considered. So case by case a situation is resolved.
Iterate through the meshes simplexes
Let xi be the current simplex.
Find the points splitting xi's surfaces.
Identify the geometric case
(for example 2D has 4 cases).
Split xi and send the simplexes back to be reprocessed.
Since a point is on the surface it is between other points so we often look at the points and use some measure to see if we need to tessellate. Contrast this with a higher level algorithm which may look at the simplexes as a whole.
The major advantage of this approach is that it does not matter what order the simplexes are processed in because if two simplexes share a surface the split on the surface is identical. (However a small point is that we do not want to duplicate or create a point twice as we could have a round off errors if two neighboring simplexes do not share a common point on their boundary.)
Here are the possible cases that need to be programmed for when tessellating a triangular surface. See [1].
Here are some rough notes. First I look at the 2D case and consider how to tessellate the tetrahedron with one of these cases on one face. Since we could then reprocess the tetrahedrons defining all possibilities of splitting a tetrahedron on one face and then iterating through all combinations of faces of the tetrahedron will handle all cases.
There is however a new case in 3D. In 2D when no points split the surface there was the possibility of an inner point splitting the triangle. In 3D this inner point could either be on the triangle face or within the tetrahedron resulting in the tetrahedron being split into 3 and 4 tetrahedrons respectively.
The idea of treating every simplex equally by considering its neighboring points is good but not necessary. With linked simplex meshes and or relaxing the condition so more than one pass is possible. For example consider splitting on and individual simplex and then re stitching.
However for linked simplex meshes it is more likely that operators will be used so the mesh is always consistent and the adaptive tessellation uses these operators to split the mesh.
Linked Triangles can have operators defined for the mesh. These can be used to build other higher level operators. The 2D Splitting and Stitching operator simply divides a triangle in four. Here is the same operator on a 2D linked simplex mesh. The primary operator is one that can split a simplex in the mesh on a boundary given a point. The mesh consistency is preserved so the operator itself manages the reconnecting the links and making the new simplexes.
The basic implementation of the algorithm is to have a vector of linked triangles. From the start of the vector to the end each triangle is tested with some condition to determine if it should be divided or not. If it is divided push the newly formed triangles to the end so that they can be reprocessed and delete the current triangle. The division is explained in the previous diagram.
Notice how the general division operator was defined with several smaller more primitive point splitting operators and finally the flip operator.
Since all the individual operators are in constant time so is this division operator. Hence it is fast. While the literature is dominated with savings of algorithms saving multiplications and divisions, for algorithms with large numbers of points or whatever the cost is the algorithms complexity - so constant operators do not change the complexity and hence are fast.
It is my opinion that previous programmers and mathematicians have not understood this - probably because it is not a penny pinching or greedy philosophy. However the notion of complexity is now much better understood it just has not been discussed in algorithm choices. For example in tessellation while Delaunay is generally the best constant operator, many other mesh balancing operators are possible. In matrix pivoting partial pivoting has the sample complexity with full pivoting and is equal in almost every condition. So both the algorithm's time complexity and outcome are equal and hence I would say that both algorithms have the same complexity.
I am not sure how to go about doing this. Let the exterior be divided as in the 2D case and come up with a tessellation for the tetrahedron.
If a minimum number of tetrahedrons is used then there the tetrahedron is divided into 8 but there are three possible permutations to choose from.
If a center point is introduced the tetrahedron can be divided into 12. The advantage here is that the result is symmetric so no choice of permutation is neccary.
For the linked tetrahedrons mesh the operators would be used so that mesh is consistenct. So once the algorithm is sorted out the general linked simplex operators are used to implement it.
