Created 2005-01-03 Modified 2009-04-11
Chelton Evans
Chelton's Convex Mesh Algorithm : Adding a Point
Chelton's Convex Mesh Algorithm: Home
Since a mesh is map up of linked simplexes, adding a point inside a convex mesh means splitting an existing simplex.
For the searching algorithm to be as simple as possible have a point belong to a simplex if it is inside or on its boundary. This decision makes sense because if you defined a point to be inside the simplex only the mesh while fully connected would not have the inner mesh boundaries between simplexes as part of the mesh.
This relates to robustness and numerical stability because the algorithm can go into infinite recursion if it can not find where to insert the point. So while defining a point as belonging to a simplex if it is on the boundary or inside the simplex guarantees all space in the convex mesh is part of at least on simplex. Simplexes only overlap at the boundary of other simplexes. The search algorithm will terminate.
The simplexes together form a cover of all the points and space enclosed within the points.
The mesh is always consistent because once a point is found it is made part of the mesh. For applications which use the simplexes as containers for other data you would have to test the boundary condition - but there is a completely different use than in this paper.
Also have the algorithm reject a point if it was previously entered as the point is already in the mesh. This is actually not that difficult. In my algorithm if an index point is inserted and is already part of the data structure infinite recursion occurs. I believe that this sort of a thing is an implementation issues - just modify the algorithm to fix it. <TODO>TEST
Since the convex mesh is tessellated by triangles in general inserting a new point inside the mesh splits an existing triangle into three other triangles.
Since the convex mesh is tessellated by tetrahedrons in general inserting a new point inside the mesh splits an existing tetrahedron into four other tetrahedrons.
This splitting operation can be generalized.
| Dimension | Number of Primitive Shapes | Shape Name |
| 1 | 2 | Line |
| 2 | 3 | Triangle |
| 3 | 4 | Tetrahedron |
| n | n+1 | n-simplex |
With the linked data structure we need to extract the information from the mesh, build the new tetrahedrons, and change the pointers of tetrahedrons.
The idea is really simple. Iterate across the boundary or surface of the convex mesh and connect any face that is viewable to the new point to the surface face, iterating across the original convex boundary only.
This produces a fan. Since the algorithm has a current virtual simplex, have this on the boundary and use the surface operators to transverse the surface. Linking from the surface to the new fan is done as the last step after the fan is constructed.
Have a process list of simplex faces to be processed, and a dead list. Any faces that can not see the point are added to the dead list, as well as connected simplexes which see all neighbors except the surface - which is done in the last step.
While neighbors are not dead add them to the process list. Evaluate the process list by popping the simplex face, determining if its neighbors are viewable and constructing them, pushing them to the process list, else send them to the dead list.
I had a function mapping a simplex face to a newly formed simplex.
Adding a point w to the tessellation where w is outside the convex tessellation. The cp is on the boundary and the virtual simplex base is visible to point w.
This is a general algorithm for two or more dimensions.
Define a new data structure SF for Simplex Facet which is made up of an integer pair id and face where id refers to the simplex and face the local coordinate of the simplexes face.
This new data structure is needed when we consider the situation of moving on the surface where the cp does not change but the facet does. In this situation the cp does not uniquely identify the face.
Let stot be a mapping of SF to uint where SF is the facet on the old boundary and the uint points to the newly formed simplex.
Let dead be a table of SF where other SF elements will be tested for membership. After a SF has been processed in the process stack it is pushed into the dead table, and so are SF which are not visible to point w. dead is named so that there is no transversal there.
Let process be a stack of SF's which are viewable to w and have yet to be fully linked in N-1 dimensional group.
Let vs, vi and cp refer to the tessellation variables of the same name.
The addspike routine adds a simplex to the tessellation relative to the current cp and if its base is viewable to point w. The associated SF is placed in the process stack.
addspike()
while (process stack is not empty)
{
pop the process stack to k.
Iterate around simplex k.id moving to the neighbors
such that the orientation of k to the neighbor is
known and this geometry is used to link the newly
formed simplexes as needed. Movement is restricted
to the movement on the surface of the existing mesh,
using the surface operators.
}
Connect and Minimize the Mesh
Iterate over stot linking the old mesh to the new one.
Iterate over stot applying the minimizer to the old and
new associated simplexes.
Linking is done in three stages and in two groups of {1,N-1} dimensions.
The linking process is generic in all dimensions, but specific to the geometry of the dimension. Here is the linking code.
bool const d3fan::link(uintc from, uintc fromni, uintc vslocalpi)
{
cpf = tess.cpsimplexfaceget();
// Is the cp on the boundary or already processed?
if (dead.find(cpf)!=dead.end())
return false;
// Does the triangle already exist?
if (stot.find(cpf)==stot.end())
{
// This is a new surface triangle.
if (tess.surfaceviewable(w)==false)
{
dead.insert(cpf);
return false;
}
addspike();
}
// Get the point on the surface base opposite the central
// triangle.
uint p2 = vi[cpf.id].pi[ vs.v[vslocalpi] ];
uintc z = stot[cpf];
vi[from].ni[fromni] = z;
d3tri & x(vi[z]);
x.ni[ x.piInverse(p2) ] = from;
return true;
}
This creates a triangle fan.
The fan algorithm simplifies in 2D because there are only two possible directions to go - left and right on the surface. So once iteration starts in a particular direction around the boundary the direction stays constant.
One way is to have the cp on the boundary and can see the new point w, and move on the surface left as long as point w is viewable. Then move on the surface right constructing the fan until point w is no longer viewable from the virtual triangles base.
The general fan generating algorithm does not process like this, but is similar for any dimension.
Consider a current simplex facet being processed. Here are the surface transversal operators to iterate around the simplex facet currently being processed.
While the mesh point indexes are unknown, the virtual indexes from moving about a simplex facet are. These are used to get local indexes and link up the simplexes.
Here is a look at implementing the generic fan's process stack in 2D. You can see the surface operators used to move and the specific geometry implemented.
uint sz = process.size();
for ( ; sz!=0; sz = process.size() )
{
k = process[ sz-1 ];
process.pop_back();
dead.insert(k);
// The current triangle must have vs's base viewable to w.
tess.cpsimplexfaceset(k);
assert(tess.surfaceviewable(w));
for (uint i=0; i<2; ++i)
p[i] = vi[cp].pi[ vs.v[i] ];
kt = stot[k];
tess.surfaceleft();
link(kt,vi[kt].piInverse(p[1]),0);
tess.surfaceright();
tess.surfaceright();
link(kt,vi[kt].piInverse(p[0]),1);
}
Because of the need to transverse the surface and there being no guarantee on how the tetrahedrons are orientated care must be taken with the implementation.
Here are the surface transversal operators to iterate around the simplex facet currently being processed.
While the mesh point indexes are unknown, the virtual tetrahedron indexes are .
Using the point access operators on the virtual tetrahedron the points can be extracted from the mesh to construct the new tetrahedron, independent of the surface tetrahedrons orientation.
For the case where a tetrahedron has been partially constructed and is visited by another tetrahedron being processed there is no knowledge of the tetrahedrons orientation. So again use the operators to get the opposite surface tetrahedron point, then use the point inverse to get the local index and hence the local index to the pointer to K. This demonstrates how to use the operators and how they solved an orientation problem inherit in the mesh.
Much of the algorithms use logic that determines if a point is visible to a boundary. The boundary partitions the space in two. ie which side of the boundary does the point lie. This is calculated in real arithmetic as whether a point can be less than 0, the point is equal to 0, or greater than zero.
The following diagram is an example of point visibility in 2D. A new point is being inserted into the mesh and is viewable to at least one of the triangles edges as the point is outside the triangle.
This test is commonly computed with the determinant. In 3D this corresponds with the volume of a tetrahedron, so in the incremental algorithm a point is compared to one of the hull faces and if the volume is negative then the new point is outside the hull. See J. O'Rourke [3] where he gives the determinant.
I would assume in 2D they would refer to negative area for the same thing.
This is not the only way to calculate visibility, instead I use vector mathematics or with the dot product. First shift the point in question by a point on the face, then dot this with a vector perpendicular with the face.
A list of ordered points can be used to construct the hyperplanes. For example in 2D two points can define a line. I construct a normal to the line pointing left of the first point relative to the second one.
Both methods are really half spaces as they partition the region in two. They do the calculation in constant time and hence have equivalent complexity and are very well known.