Created 2005-01-03 Modified 2009-04-11
Chelton Evans
Chelton's Convex Mesh Algorithm : Mesh Minimization
Chelton's Convex Mesh Algorithm: Home
Lets define mesh minimization or mesh balancing as the process of forming better shaped simplexes.
For example in 2D if there are two different possible configurations of two adjacent triangles, choose the one that minimizes their boundary (and hence makes them all tend towards being rounded).
As an analogy consider the problem of approximating Pi. Algorithms that approximate Pi approach or become closer to the true value of Pi as the number of iterations or algorithm steps increases. Loosely this is the limit theorem.
The same should occur for mesh minimization. As the number of points used by the algorithm increases we would expect an increase in the accuracy of the grid.
This is definitely a measurable quantity. Apply a known function (for example as a circle in 2D) and generate data points with that function. Next use a marching triangles, tetrahedrons, ... algorithm to approximate the function in the given space. These algorithms are linear interpolation on the simplexes.
Compare the approximate curve with the known curve. As the number of points increases the difference between the true curve and the approximate curve should become arbitrary small. This is a generalization of the limit theorem. Some distance function between the true and approximate curve would need to be found. eg their area.
If a mesh generating algorithm has this property then let it be called a balancing or minimizing mesh tessellation algorithm.
From the previous discussion it should be clear that for the algorithm to be useful it must have the previous property that as the number of points inserted increases a more balanced mesh is formed in the limiting sense.
Consider an example of an atrocious mesh - one which has no mesh balancing. As a point is inserted the edges generated at that moment are forever stay the same. Since interpolation interpolates across the edges the interpolated point at that edge never changes no matter how many other points are inserted.
For a practical demonstration see marching triangles applied to a 2D unbalanced mesh. Many of the triangles are too long, and no amount insertion of new points improves the mesh.
A similar situations happen in 3D. As I found out the marching algorithms need a balanced mesh.
Mesh minimization also helps with insertion. Its faster to transverse inside the convex mesh. And the algorithms complexity is changed.
When the mesh is edited links need to be broken and reformed. All minimization makes a decision and then we need operations to change the mesh.
I focus on operations between two adjacent simplexes because this is how the general algorithm interacts with the mesh. It is also natural to look at the maths in this way.
In general the operators act on adjacent simplexes that together form a convex object. This is because transforming one configuration into another needs to be reversed. The operators applied to non-convex shapes simply corrupt the mesh. So it is a requirement these basic operators only be applied to adjacent simplexes which together are convex.
In 2D this is straight forward. Consider two adjacent triangles. There is two possible combinations and choosing the right one is a job for the minimizer algorithm. However there is only one operator which is symmetric. Applying the same operator twice on the same adjacent triangles returns the mesh to its previous state.
However in 3D it is apparently much more complicated.
Two adjacent tetrahedrons that form a convex shape have an operation which like the 2D counterpart changes the tessellation and is reversible. However unlike the situation in 2D, in 3D the number of tetrahedrons is not preserved with this transformation.
This is significant because it makes comparing the before and after meshes very difficult. Which is what minimization algorithms need to do so there is really something different here.
| Operator Symbol | Dimension | Description |
| TF | 2 | Transform or Flip two adjacent triangles. |
| T2->3 | 3 | Divide two adjacent tetrahedrons into three with a common axis. |
| T2->3-1 | 3 | Divide three tetrahedrons with a common axis into two. |
This is a well known operation which I will call an operator because there are more of them. The flip operator has a special property in that it is its own inverse. Applying the flip operator twice to the same pair of adjacent triangles leaves the mesh unchanged.
The linked mesh data structure allows the flip operator to be defined. Extract the information from the mesh and use the data structures operators to transform the mesh to its new state.
I found this harder to code. Extracting the information from the mesh by rotating about the central axis using TD operator. Luckily this works the same for clockwise and anticlockwise rotation about the axis.
The ai tetrahedrons are in the order of the rotation.
When I was designing the algorithm the teacher was extremely negative, and took every opportunity for the devils advocate role, calling the tessellation atrocious triangles. I took the view that this could be corrected at a later point in time, which is what I did and hence the name.
When implementing marching triangles the triangle tessellation effects a marching algorithms results. No amount of additional points will correctly display a curve by marching triangles if a triangle happens to cut the curve completely. See Mesh Before and After Minimization.
Consider when the tessellation splits an existing triangle there will always exist a triangle with a border on one of the original triangles sides. This length needs to decrease for marching triangles to be more accurate, as marching triangles interpolates on triangles edges. As this length will always exist no amount of additional points will help the curve approximation.
This is not what you want from an algorithm. You would expect that as the number of points increases the algorithm would yield better results and get closer in approximation to the true situation.
So what is the simplest thing to do to get that limiting property into the algorithm. First I identified the problem, and then picked the simplest solution. That involved two triangles.
Consider two joined triangles. The greatest error occurs with flat triangles. There are two possible ways to triangulate 4 points, why not minimize the diagonal length. Since this a side length used in a marching interpolation it should yield better results when minimized.
Here is such a minimization. Both diagonals were calculated and it was found that the current arrangement was not minimal, so the left triangle was transformed into the right triangle.
The minimization can only occur if the two triangles joined form a convex shape. ie the quadrilateral is a convex polygon.
To determine if the quadrilateral is convex, three points are always convex let the lines from a common vertex opposite the new point extend and be used to test if the new point falls inside the convex mesh. This is simpler than I made it sound, some would even say trivial.
The algorithm I developed is a variation on the incremental algorithm. However the incremental algorithm does not say how the new simplexes interact with the existing mesh. However when you see my pictures of mesh interactions of the new simplexes and the existing mesh you will see the obvious - that there is a one to one relationship with a new simplex and one already existing simplex in the mesh. See Minimize the Whole Mesh.
Since the old mesh interacts with the new mesh - through a minimization between two simplexes we can call this a binary operation. Even though both simplexes connect with others and can change other simplexes, its just a general way of looking at the relationship, not carving in stone. Indeed the generality is in what is not said. Because by deriving other operators from this we can build other tessellation algorithms.
In 2D the binary operator is an operation between two possibly adjacent triangles. The boundary between them is a 1D line. I say possibly because by the time the two simplexes are evaluated with the operator the mesh could have changed.
In 3D the binary operator is an operation between two possibly adjacent tetrahedrons with their boundary being a 2D triangle.
A simple pattern emerges where two N dimension simplexes have a binary operator which changes the mesh. The simplexes likely share a N-1 dimensional simplex border.
This boundary operator is used like as a basic operation which derived operators implement.
I defined this operator to return a value of true or false depending on whether it changed the mesh or not.
A point about these operators are that their complexity is constant in time. There is nothing to say that this is required but the most used mesh minimization operator is Circum-Circle and Circum-Sphere operators which are constant in time.
This has consequences in that we can not expect a speedup in algorithms using different binary simplex operators, only that their meshes will be different.
Now an argument could say take the best (DT) and forget the rest however in 3D space there appear to be some really challenging situations when even these do not perform well enough. But for most practical purposes there would generally only need the operators used to build DT.
Now that we have a mesh minimizer operator it is easy to say lets keep applying this operator till the mesh is left unchanged.
Lets define another general operator to do this job. It is really a form of stack processing. Have a vector of simplexes. Because its a binary operator push both simplexes onto the vector. Process the vector by popping a simplex and minimizing it with its neighbors, if a minimizer operator changes the mesh (returns a true value) then push both simplexes onto the mesh to be processed. Keep popping the process vector and repeating the process until the process vector is empty.
This operator will not work with just any minimizer - the minimizer must terminate or have a unique minimum state. Else infinite recursion will occur.
For certain binary simplex operators experimental timing results suggest that the recursive operator has the same time complexity of its own minimization operator.
This did surprise me. A possible explanation is that if the mesh is already balanced, adding new simplexes to the mesh does not change it that much (constant time again) so the complexity of some operators is equivalent to the complexity of the same operator inserted into the general recursive binary simplex operator.
Sloan[1] described a mesh minimization for Delaunay triangles. If the adjacent point lies within the circle passing through the triangles points then flip the triangles. However this operator can be used on its own for mesh generation.
Sloan[1] page 23, refers to an existing Delaunay triangulation which inserts by the Circum circle Minimization and then processed to repeat this with the surrounding boundary, until it remains unchanged. Essentially triangles are pushed and processed on to the stack.
A Delaunay Triangulation operator can be built with the Circum-Circle operator inserted into the general recursive binary operator.
Ok so now we have a way of better triangle tessellation, how would this be applied to the algorithm. It turns out easy with in general every new triangle formed undergoing minimization with an existing triangle. This minimization is not recursive so the algorithm complexity does not change.
For a practical example of the minimization effects, consider a tessellation used as input for the marching triangles algorithm. The blue is the tessellation, the yellow is the target curve and red is the marching triangles algorithm to approximate the yellow curve.
Both tessellations have the same input. The left is before applying the minimization and the right is after minimization.
Looking at the two tessellations(blue) you will see a huge difference. The minimized tessellation has much more balanced, rounded, fatter or whatever triangles. The non-minimized tessellation has longer and thinner triangles.