Created 2005-01-03 Modified 2007-02-01
Chelton Evans
Chelton's Convex Mesh Algorithm
Intro
Offline Algorithm
Presort the Points
Reconstruction
Linear Tessellation Algorithm
Definitions
Data Structures
The Linked Simplex Data Structure and Winding
The Linked Simplex Data Structures Operators
Testing Adjacent Shapes for Convexity
Example of 3D Mesh
A Linked Simplex Mesh with Virtual Simplex State
Mesh Consistency
Indexed Simplex Sets - Tessellations
Linked Indexed Simplex Sets
Converting a Indexed Simplex Set to a Linked Indexed Simplex Set
Orientation and Movement
2D Orientation and Movement
3D Orientation and Movement
3D Operators
Surface Transversal Operators
Movement of cp Operators
Boundary Transversal Operators and Operators in General
Are Operators Needed for this Algorithm
Operator Names and Symbols
Rotation
Greedy Search and Randomness and Complexity
Searching in a Convex Mesh
Searching in a Static Convex Mesh can be made Constant in Time
Robustness and Numerical Stability
Mesh Topology
Mesh Minimizer Stability
Hilbert Curve
Adding A Point
Adding a Point Inside the Convex Mesh
Split in 2D
Split in 3D
Adding a Point Outside the Convex Mesh
Fan 2D
Fan 3D
Point Visibility
Mesh Minimization
Why Mesh Minimization is Necessary
Mesh Operators
The Flip Operator
Two Adjacent Tetrahedrons to Three
The Inverse of Two Adjacent Tetrahedrons to Three
Atrocious Triangles with Correction
The General Binary Simplex Operator
A General Recursive Binary Simplex Operator
Circum-Circle Minimization Operator
Delaunay Triangulation Operator
Minimize the Whole Mesh
Marching Algorithms
Generalized Marching Triangle Algorithm
Generalized Marching Tetrahedron Algorithm
AdaptivelySampledDistanceField
Algorithm
Convex Hull
Writing the Algorithm
The Incremental Algorithm
C++ Implementations
<TODO>
Complexity
Experiments
References
This algorithm is definitely very similar to the incremental algorithm, and could be seen as a variation of it. However this algorithm creates a tessellation whereas the incremental algorithm computes the convex hull and deleting interior points. This potentially new algorithm says how the newly created simplexes interact with the existing mesh as a general binary operation between two usually adjacent simplexes.
Different types of meshes can be constructed. The tessellation has been generalized so that a user defined binary operator minimizes and reconfigures the mesh. By defining different operators different mesh tessellations can be made.
The complexity of the algorithm is that of the incremental algorithm. While it does not delete interior points. J.O'Rourke[4] explains how the incremental algorithm can be modified with a presorting stage to be an O(n log n) algorithm. When the sorting can be made in linear time then this becomes a linear tessellation algorithm.
A general tessellation algorithm is being designed. The generality is that it has some commonality for any number of dimensions. However you still need to find a minimizer or some way of choosing a better tessellation from the existing tessellation. All the algorithm does is say which faces to interact with.
The boundary is the convex hull so tessellations are also convex hull producing algorithms. As the surface or boundary can be transversed not only are the points on the hull computed but a surface can be generated because of the linked simplexes, which is something other basic hull algorithms can not do. See Convex Hull.
The algorithm is iterative or an on-line algorithm where the points are fed to it, rather than working on a whole group of points at a time. See how this algorithm can be converted to an Offline Algorithm.
This algorithm uses a new data structure which I call linked simplexes or linked triangles in 2D, linked tetrahedrons in 3D. The structure has operators and the simplexes winding is stored. This data structure is general and can be used as a generalized mesh structure. It is a hybrid of existing data structures in the sense that it is easy to construct hyperplanes from the data structure, and the use of integer indexes to points and simplexes has the points and simplexes as vectors. Unlike other data structures this is very easy to visualize.
Instead of thinking predominantly in points and lines as other tessellation algorithms do you are now free to think of the mesh from the simplexes perspective.
It is clear that this data structure and operators could be used in simplex meshes in general. So these could be of interest to the Computational Geometry community.
Historically tessellations that process the whole group of points at a time have the best complexity. The algorithms are classified as off-line algorithms.
As this algorithm has a state or pointer to the last insertion into the mesh, this can be used in conjunction with other algorithms to create offline algorithms.
Inserting a new point near an the current point is very quick because the search time is constant. By presorting the points and then feeding them in to the algorithm, the new point is always neighboring the current point and hence insertion is constant in time. So insertion over all the points is O(n).
Complexity: O(nlogn) + O(n) = O(nlogn)
This is a fantastic result. It now reduces or changes the problem to how well a data set can be sorted, which a lot of people have spent time developing this. For example for randomly distributed data a bin sort could be used giving the tessellation an O(n) complexity!
To summarize the algorithm is now a two stage process - presorting the data points so iterating them they are sequentially next to each-other, then the second stage has these points fed into the mesh algorithm.
For a simple first stage sorter see Simple Sort.
Complexity: O(sort) + O(n)
An important application using the incremental algorithm is to reconstruct a tessellation in linear time. The idea is simple, do the tessellation and store the order of points such that when the points are transversed each is next to or near the previous point. The construction time for the point is then constant and a linear tessellation algorithm is ensured.
For example imagine that you have terrain tessellation for a game. Then solving the order of insertion points means that the terrain can be recomputed in linear time.
This can be taken further as there may be applications where the exact reconstruction is necessary. The linked simplex data structure solves this problem by saving the mesh links so if you can afford the extra memory the problem of reconstruction is completely solved.
When the ordering of the points can be done in linear time then the tessellation can be done in linear time.
I have written a bucket sort which uses hash tables to sort the data structure generally in linear time. To avoid the worst case complexity of this sorting which is O(n^2) the sort was made a hybrid and defaults to another sort O(nlogn) in this case. See bucket.
Loosley marching refers to interating over the meshes simplexes. Historically these algorithms were more focused on rectangular data structures but they work better on simplex data structures than their rectangular counterparts.
These are surface displaying algorithms which given a point field find the intersecting points of the mesh and the field as a particular value.
For a more detailed explanation see Marching Triangles, Squares, Cubes, Tetrahedrons.
Consider marching triangles with non-uniform points.
For example in 2D the points have a third height field. In the target example the hight was given a function where when the function was zero a point was on a circle. Then this function is a field. Next when the random 2D point was input the height field was calculated on that point.
Here is the result of random points and applying the marching triangles algorithm over a balanced mesh.
"Computing 3D Geometry Directly from Range Images" by Sarah F. Frisken and Ronald N. Perry, Mitsubishi Eleectric Research Laboritory, Technical Report 2001-TR2001-10, March 27,2001
Can generalized marching simplexes be used to generate Adaptively Sampled Distance Field(ADF) there by resulting in significant savings in memory and computation?
I believe it can. Investigate such possible algorithms.
I guess you are throwing away information that is unnecessary which could be throwing away sample points where the curvature is low. This on top of deleting within the mesh could lead to practical geometry set algorithms.
When a point is added it is searched for inside the convex mesh. The current simplex (cp) is a pointer to a simplex in the mesh. This pointer changes or moves through the mesh and is a virtual simplex.
This takes time and in the worst case is quadratic - inserting O(n) points in O(n) simplexes. The search terminates when the new point being inserted is inside the current cp or the cp is on the boundary and the new point is viewable to it.
Mesh minimization or mesh balancing speeds the greedy search up. The greedy search looks at any neighboring simplex. If it is closer to the solution the cp now points to it. The greedy search works in both balanced and unbalanced meshes. I believe it to be much faster in balanced meshes though I have not found where to find this result in the literature.
Also of interest are randomized techniques of searching which I believe could give the optimal search time as they have done with other data structures([2] page 3).
A basic strategy could be to randomly sample the vector k times choosing the closest to the target as a starting point and then applying the greedy search. k would depend on the total number of points or simplexes in the mesh. I believe that this question has probably been already answered and that it leads to the best algorithm complexity possible. <TODO>Find out more.
Formally called convex inclusion it is the act of searching the data structure, typically for a point associated with a simplex.
The searching algorithm uses half spaces to minimize where a point belongs in the mesh. This is in contrast to a norm which calculates the distance to the point, and selects the minimum distance to choose the next simplex to move to.
The algorithm used a greedy search where it takes O(n) time on an unbalanced mesh and I believe is less than O(n) time in a balanced mesh.
Assume that the grid is a balanced one. ie as more and more points are added to it it gets refined and more accurate.
The data structure could also be used as a static data structure where only searching is done then the search time can be made constant with a modified bucket sort.
In 2D we construct a grid of k by k points that is divided in equal intervals on the x and y axes and covers the mesh.
Now we pre-process each point by searching for it in the mesh and associating that point with the corresponding simplex it is minimized to.
To ensure constant search time we must guarantee that that the search is bounded and small. For example given an arbitrary point to search for ensure that at most 5 moves are made before the simplex where the point lies in is found. This itself asks us some interesting questions. For a uniform distribution how many intervals would be required to achieve this. In practice if memory is cheap just increase the number of intervals till the search length becomes constant.
We can refine the grid as much as we like to achieve this. For example doubling the number of intervals along the axes. However this is quadratic in memory usage. An alternative could be to make your own index functions which compute the grid indexes where the distributions along the axes are not linear.
In refining the grid we can use the previous grid points as starting points for the new search. So the new points should be found in constant time. It is quadratic in the number of intervals and not the data set, which could be useful in applications where the data set is not static but occasionally dynamic. ie the data structure is updated and once again used for constant search times. The update to the data structure is minimized.
This type of search does not use a current simplex in the random search, but rather randomly looks at a simplex as a point and compares it to the target point.
If the midpoint of a simplex is used as a center of a simplex then the distance to this center and the target could be used to measure if one point is closer to the target point than the other point as its distance would generally (but not always) be less.
After choosing k such points find the one with the minimum distance to the target and then perform a greedy search to the target.
Let this greedy search be done in w moves. The cost of the search can be expressed as k + w.
The question I have for this type of search which was not yet implemented is this. For a uniform distribution of points and a DT balanced mesh what is the optimal value of k to minimize k+w, where k(n).
This is to be tested. Randomly generate a target point x and a random starting location within the mesh. Choose a value of k and sample and compare for the nearest point to x, then apply the greedy search algorithm.
Vary the space n=200, 400, 800, 1600, ... points. If w(n)=log n when k=0, is this improved when k=1, k=2, ... ?
Plot k vs w.
Counting and averaging the number of search moves as the number of points varies. Assuming a uniform random distribution.
For an unbalanced mesh the search time was approximately 3.5/5.5=.636 gives O(n^0.636). The following is the data set and the {(log n),(log average moves)} graph.
200 38.76 400 56.485 800 85.85 1600 143.155 3200 205.608 6400 307.857 12800 466.682 25600 816.406
minb=1 mesh. The search time was approximately 2.5/5.5=.455 gives O(n^0.455).
200 21.59 400 25.9475 800 37.7013 1600 52.0006 3200 73.4328 6400 102.015 12800 142.394 25600 203.631
There are n points to be inserted. Then the search time through the convex mesh and then the boundary. With some thought and maybe excluding a pathological case the boundary is constant. If this is so then the boundary is also constant in 3D too.
So the real question of the algorithms complexity is finding out how long it spends minimizing itself in the convex mesh. O(n^.5) is my guess, but it could be O(log(n)) or somewhere in between.
The arguments for the boundary are that adding a new point simplifies the boundary in general. eg k new triangles formed then k-2 less edges on the boundary. Except when k=1, the boundary has the same or reduced number of edges. This is only a sketch. Further on the assumption that an insignificant number of boundary insertions are made compared to the convex mesh the boundary time can be discarded. This is an incredibly strong argument and for practical purposes does mean the boundary computational cost is discarded.
The algorithm follows step by step the 2D version. The convex mesh is 3D instead of 2D, same with the boundary ... The minimization of the length of the diagonal is replaced with minimizing the area between adjacent tetrahedrons.
Choose a configuration of tetrahedrons that minimizes the area bordering the two adjacent tetrahedrons - exactly the same as the 2D counterpart.
I did not finish the implementation of generalized marching tetrahedrons. Time was a factor but the truth was that it took me too long to get over the previous algorithm where I was minimizing the vertex and encountering local minimums.
Initialize the mesh by adding a simplex with the first few points. Let cp point to this simplex.
Iterate over the remaining points. x is the current point.
repeat
If x is not within the cp then
Find a visible face to the point. If the face points to another simplex let cp point to it.
until cp not changed
Case 1: x is inside cp
Use x to split the simplex cp, creating new simplexes. Connect the simplexes together.
Case 2: x is outside the boundary and cp is on the boundary.
Create a fan of simplexes with point x as the pivot and all the visible faces. Connect this fan with the mesh.
Minimize the mesh by minimizing each new simplex insertion into the mesh. Two shapes share a border. If the combined shapes form a convex shape then test all possible configurations such that the border between the two points not on the border is minimized. If possible replace the configuration with the more minimal one.
The algorithm maintains a convex boundary as points are inserted. The minimization balances the data structure and is done as the points are added. So while it does have two loops I do not believe that it has O(n^2) complexity because insertion within the mesh is a balanced insertion. This looks like being extremely difficult to prove. Insertion outside the mesh simplifies the boundary and I assert that it is not possible to generate a sequence of points that for O(n^2) insertion, again this is really difficult to prove but I believe it to be significantly easier that the other proof. As an initial estimate I would say a couple of months work perhaps and an extremely highly risky. But then again what do I know about topology - not much.
The insertion could also be changed to do more work. It could be an open question as to weather the insertion could be changed to produce the same mesh with the same set of points as generalized Delaunay triangulation.
For example if the triangle is split and two neighboring triangles about the new point are minimized with their configurations changed, then their common boundary/edge could be re-minimized. Does this produce a better or more balanced mesh?
The algorithm can be easily modified for different forms of decimation. For example if you wanted to compute the boundary only do not split the mesh.
Other forms of decimation my include just wanting to approximate the boundary better. If you only split the triangle for points near the boundary and simplify the mesh after wards, inserting into the mesh could be constant in time, hence you have an O(n) algorithm to build your hull boundary.
An application of this could be a way of constructing surfaces in 3D. By keeping the points on either side of the surface in the mesh and throwing away other points. Now could this be used to subtract one similar mesh from another. ie volume subtraction in 3D.
The advantage of using simplexes as the building blocks for the mesh becomes clear when you see that the meshes from simplexes do not have artifacts or generate artifacts. Compare the marching tetrahedrons and marching cubes algorithms. The meshes generated for the marching cubes have holes or need complicated decision logic to stop them having holes. By contrast the marching tetrahedrons algorithm has no holes. Holes are mesh artifacts.
So the general meshing question does not have to deal with these - potentially problematic holes.
Whether this could be realized efficiently is also an open question. I believe such algorithms on these structures are possible.
By default the convex hull is computed. Further the surface can be extracted so the hull is also a linked data structure in one dimension lower than the tessellation simplexes.
While the complexity can be made optimal for offline algorithms, on line algorithms have to go through the search which I believe is currently greater than O(log(n)). Further some tessellation algorithms can have O(n) expected complexity which is faster than their theoretical limit, by taking advantage of the data distribution.
The algorithm can be modified to compute the complex hull faster. An obvious step is to ignore a point already inside the convex hull so the split part of the algorithm is not executed.
Another optimization is to delete any internal point within the mesh after inserting a new point on the hull. While this sounds simple it appears to be complicated. <TODO> So the mesh only consists of points on the hull.
This may possibly lead to worst case log(n) search times. Another strategy may be to identify inner simplexes in the mesh which have no neighbors with points on the hull, and if possible delete and re tessellate. I believe this to be some work however it might lead to a more balanced mesh with in general faster search times than the previous suggestion of deleting points inside the mesh.
These extensions are on top of the original algorithm, because the updated mesh would be rebalanced where it borders with the original mesh were changed. It is perhaps high risk where there could be a lot of work for a high gain or nothing at all. If I had the time and ability I would probably do it.
Initialize H4 to tetrahedron (p0,p1,p2,p3).
for i = 4,..,n-1 do
for each face f of Hi-1 do
Compute volume of tetrahedron determined by f and pi.
Mark f visible iff volume < 0.
If no faces are visible
then Discard pi (it is inside Hi-1).
else
for each border edge e of Hi-1 do
Construct con face determined by e and pi.
for each visible face f do
Delete f.
Update Hi.
After I had thought up the algorithm I wondered where it came from. The teacher had no idea and was not interested.
Several months later I found the Incremental Algorithm which is similar to my algorithm. Here are where they differentiate.
Randomized Incremental Algorithm
This algorithm was first described by K.L. Clarkson and P.W. Shor in 1989. I used the description found in Computational Geometry by de Berg, van Kreveld, Overmars, and Schwarzkopf
Incremental Convex Hull from e-book web site Computational Geometry Rashid Bin Muhammad .
Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator Triangulation Algorithms and Data Structures
A variational formulation of the fast marching eikonal solver - massive but potentially good.
The order of how things are built in the algorithm can effect the outcome. Further I built in debug code which was critical in finding errors.
Visual debug for testing the operators. eg rotate the cp. This is perhaps critical because once you have movement then the algorithm is much easier
Constrained Triangulation - After mesh has been generated, re triangulate with line constraints. See [1].
Then by iterating about the line you can cut out areas. eg form non-convex shapes.
Random point insertion in mesh. The code was compiled without debug code and optimized.
| Method | Complexity | n Points in time(s) |
| 2D Delaunay Triangulation | n^1.4 |
100 0 200 0.02 400 0.03 800 0.06 1600 0.14 3200 0.32 6400 0.77 12800 1.91 25600 4.94 51200 13.08 102400 34.95 204800 95.27 |
Assuming a DT mesh the voronoi diagram can be constructed. There are many algorithms to do this, here is one.
Let fp be a vector the size of the points where the index corresponds with a point and the value with a simplex. Initially all the points have 0 value.
Iterate over the simplexes. For each simplex vi iterate over its points pk. If fp[pk] == 0 then let fp[pk] = vi . So all the points point to a simplex that has that point.
Since each point corresponds with a voronoi region, iterate about that point constructing the voronoi region.
Vertexes on the hull boundary have to consider their neighboring regions as voronoi polygons have one extra edge on the boundary than interior voronoi polygons. For example voronoi regions on the hull boundary are not finite. Have the algorithm treat these regions differently.
The voronoi diagram is constructed in O(n) time.