Created 2006-01-14 Modified 2007-01-01
Chelton Evans
Clipping in a Linked Simplex Mesh
Intro
Algorithm
Global View of Clipping in 2D
Resolving Ambiguous Cases
Ambiguity Resolution in 2D
Ambiguity Resolution in 3D
C++ clipping implementation
Mesh Subtraction
Mesh B
Points in the Same Space
General Mesh Subtraction Complexity
Restriction of Contact
Virtual Grinding
Sweep Move
This is a general purpose mesh clipping algorithm on the linked simplex mesh. It is designed to be robust. It will work for convex and non-convex tessellations. The algorithm can be implemented in any dimension.
The processing requirements depend on the partition and the algorithm implemented. For example if a point in the partition (mesh B) can be found in constant time and the mesh being subtracted (mesh A) has n simplexes then O(n).O(1) = O(n) can be achieved by iterating over mesh A and clipping. Generally the memory requirements will be linear with processing of simplexes.
When I started writing this I considered the partition to be a half space. However any partition can be used and this was generalized by requiring the partition to be able to say which side a given point is on and given two points interpolate the partition boundary.
Since the mesh simplexes can be made smaller, in the limiting sense the partitions boundary can be calculated as the mesh simplexes approach zero in their generalized volume( 2D then the area goes to zero, 3D then the volume goes to zero).
Consequently we can use partitions that can be analytic, for example a circle. So while whenever the partition is realized it is a simplex mesh this realization need not be done till the point where the partition is used.
Further different partitions have different complexities.
Ideally partitions will have O(1) or constant time isInside()
test as this would then make the clipping linear in time. However if the
partition is represented as a convex simplex mesh its lookup time is O(log n)
for a balanced partition mesh. This topic is so serious that it will not be
solved till O(1) lookup time is achieved and is known as the
Inclusion in a Polygon problem. While I have not
done it the algorithm I proposed in the link could give convex polygons
a constant access time. Since clipping is fundamental to integration
this could determine the success or failure of the clipping algorithm
based on how long it takes to identify if a point is inside a region and
then which simplex it is in.
Let vbi correspond to point i. Classify all points as either outside the partition (white points) or not (black points).
vbi = H(pi)
Iterate through the simplexes.
If a simplex has all white points then delete the simplex. Continue.
If a simplex has all black points then accept the simplex. Continue.
The simplex must have both white and black points to reach here. Find the intersection points of the simplex and the partition. Insert them into the mesh as a one point cut. These points cut the partition. Classify the points as black.
Black points can have two possibilities : either they are on the partition or not. These are treated as separate cases when it comes to processing because they result in different geometry. So given k black points from a m white balls, k black balls case this results in k separate cases to consider. eg m white balls, no black balls on boundary, m white balls and 1 back on the boundary, ...
Push the newly formed simplexes to the end of the simplex stack so that they will be processed later in this algorithms iteration.
Looking at the clipping algorithm applied to a mesh we see that if a triangle intersects the partition it is cut up and the ambiguity resolved. Hence the clipping algorithm interprets a triangle as being outside (having one or more of its points outside the partition) and deletes it else the triangle is accepted.
Iterate through the simplex points counting how many black balls and white balls there are to determine the general case. For each of these cases consider when the black ball is on the partitions boundary or not. The partition has been represented in the diagrams as a vertical line.
The implementation of these cases is more difficult than suggested by the diagrams for a few reasons. split1D needs to take a simplex as an argument and repeated application of split1D generates new simplexes so the implementation must manage this. For example I implemented the split1D operator to overwrite deleted simplexes and push any new simplexes to the end of the simplex stack.
At first I did diagrams that corresponded to the code in a one-one fashion and I still use these. But here to focus on the cutting I simply refer to the operator used for the split. From this perspective it is clear how the split1D operator is being used to cut up simplexes in higher dimensions. For example cutting with a line is achieved with two split1D operations.
In 2D the triangles are split and reprocessed. A point on the boundary is treated differently than one inside. The In 2D split1D operator is used to cut up the triangle. See also Cutting a Triangle with a Line.
Let A and B be two meshes
Consider A - B -> A operation
Subtracting one mesh from another can be an incredibly simple or complicated operation. It is not necessarily symmetrical in that the two meshes could have different properties. For example in some situations having the subtracting mesh convex leads to one type of mesh subtraction which takes advantage of the convexity.
Other implementations can treat mesh subtraction more simply by having uniform point grids (marching squares/cubes), defining subtraction on individual cells and iterating over all the cells. The problem here is the cells uniformity. Here the cell is a simplex with no set size or shape. There is however nothing to say that by placing uniform grids with pointers into the simplexes and using the same technique.
There is also a problem with the two meshes having different granularity. For mesh A the general case will lead it to having possibly balances but different sized simplexes as the mesh is ideally adaptive in the sense that mesh sculpturing has the possibility of creating very complex geometric objects.
By mesh sculpturing I mean the repeated application of subtracting mesh B from A where B has been translated and rotated in any fashion for each subtraction.
The idea of the partition colors points outside the partition as white else they are black. The interface specifies that the partition has to be able to calculate the intersection point between any two oppositely colored balls. When the partition is a mesh as in the case of mesh subtraction then how to find this intersection point becomes interesting.
While all the simplexes of the mesh being subtracted are iterated over this mesh does not need a uniform granularity of simplex sizes. It is not good that it does this iteration but other techniques could be used such as having bounding boxes to reduce the number of simplexes iterated over.
Since the mesh is a vector of simplexes and we can re order them I am thinking of a data structure on top of the vector which is a tree of partitions that has indexes into the mesh and re orders the simplexes in the mesh. The partitions simply split the simplexes into two equally sized groups. For example if simplexes 1..10 are split into two groups {1,5,6,3,4} and {2,7,8,9,10} by a partition, swap the simplexes so the groups become {1,2,3,4,5} and {6,7,8,9,10}. The partition data structure needs only remember the indexes 1,5 for the first half and 6,10 for the second.
If the simplexes being subtracted from are optimally being iterated over then there is now the issue of iteration over the subtracting mesh. There is also animation. Apply any transforms to the subtracted mesh and keep the subtracting meshes points constant (actually the reverse where mesh A's points are constant and B's are transformed could be more efficient assuming A has many more points than B). So by now most of the processing being done concerns itself with mesh B.
These situations generally use Inclusion in a Simplex Mesh as part of their computation.
My first attempt at mesh to mesh subtraction failed. Essentually the clipping algorithm needs all the points global and I was classifying only points in mesh A against mesh B.
I took this path to develope an efficient algorithm that needed only a one-way lookup where a point in one mesh is used to find the simplex it resides in in the other.
If the granuality in mesh A is made finer so its simplexes are less in size than mesh B the algorithm works but this is the opposite of what is wanted from a clipping algorithms because mesh B can be pre computed and access operations made more efficient because it is static whereas mesh A we want an adaptive mesh - forcing mesh A to have the same sized simplexes or smaller would kill the algorithms performance.
So the general solution is to keep mesh A adaptive by adding new points to mesh A that cut it up. Then the classification of points works. This will involve a two way relationship between the meshes an now all of mesh B's points have to be found in mesh B or not and which simplexes they intersect with.
Let mesh A have m points and mesh B have n points. Since the number of simplexes is linearly proportional to the number of points discussion is simplified to m or n points.
The following assumes the most general form of mesh subtraction where all of the points in one mesh are found in the other, point wise cuts are implemented ...
A - B done in time
O(m).O(n)
This is bad because it exhibits a quadratic relationship. ie a linear increase in m and n results in a quadratic increase in time. For real time applications quadratic is not only bad it is a killer and unaceptable (or limiting if accepted).
The first optimization is to use bounding boxes on mesh A. While all of the points in mesh A may have to be investigated, in other situations only a subset log(m) need to be considered. See Bounding Boxes and Half Spaces and Trees.
For a small chunk being subtracted,
A - B done in time
O(log(m)).O(n)
If mesh A and B can be restricted to a finite number of continuous intersections then mesh A can be accessed in constant time. This is useful for the virtual grinding. For example restrict a move to only allow one connected group of simplexes of mesh B to cut mesh A.
Perhaps I have described this in a too complicated way. Simply put if you know that two meshes intersect and since both are linked simplexes then iterate over one (mesh B) to cut mesh A.
This hinges on finding at least one point to start the cutting in mesh A given the cutting simplex in mesh B. While this is usually a O(log(m)) operation of finding the point in mesh A since it is done only once then it can be considered a finite operation and hence done in constant time.
This is monumental because it now allows us to reach a linear clipping algorithm.
Let mesh A have m points and mesh B have n points.
A - B done in time
O(1).O(n) = O(n)
Bounding boxes could also be used to improve the time to O(log(n)) for situations where there is no or little intersection between meshes A and B.
With bounding boxes A - B done in time
O(n) or O(log(n))
Moving a partition through time and clipping defines virtual grinding. As the step in time goes to zero their is less space between partition moves. In the limit there is no space between moves.
For example consider moving the triangle partition in time and subtracting it from a mesh. Holes will be left. Subtracting the partition in time is not enough.
This can be implemented in many ways but essentially it fills in the volume as the partition is moved through time.
Here is the simplest sweep algorithm I could think up. It goes to the macroscopic viewpoint that of the simplex. Since a partition is made up of simplexes, consider an individual simplex being swept through time.
Interpret the space between moves as the convex hull of the simplex in two points in time. Subtract this convex hull from mesh A the mesh being subtracted from.
This is applied to every simplex in mesh B the subtracting mesh. It is general in the sense that if a path is defined (eg a spline) for the simplex to follow for a more accurate sweep the algorithm in no way changes, instead sampling is done more frequently.
A variation could be to not use simplex operations but subtract the resulting hull from mesh A. As the hull of two simplexes is a finite operation it is calculated in constant time.
Another type of sweep is to subtract the partition at the discrete intervals and construct a sweep volume. The algorithm here does not do this but has only the sweep move. Whether the algorithm I am proposing is viable or efficient I do not know.
If the partition is represented as a mesh with constant access time then storing the previous partition's mesh position could be used to cull the simplexes which have already been swept. This is perhaps a complicated algorithm but may work for partitions with adaptive meshes. If this works then the partition could be optimized in the number of simplexes it contains.
Let the partition have n simplexes then the culling of the partition is O(n). The remaining simplexes would then be used to subtract from the mesh. Let mesh A have m simplexes and assume that a point can be found in O(log m) time (some balanced tree lookup table). Then a move in time could cost O(n)O(log m) = O(n log m ).
This is a lot of work to achieve this algorithm but it appears possible. Further the quadratic cost of a move can be avoided. However for more accurate paths the time between moves is reduced and the number of sample points increases. Let k be the sample points in time then the cost of the simulation is O( k n log m ).
It is surprising that the partition creates simplexes which are then subtracted from mesh A in light that I was originally designing the clipping algorithm to iterate over simplexes in mesh A (O(m)) and subtract from mesh B in constant time. As this is subtracting in the opposite simplexes. Note that this way could also be made more efficient with a lookup tree to get O(log m) clipping. Clipping and sweeping are related and can use the same data structures but are different.
