Triangle

• CE's Convex Tesselation Algorithm
• Polygon Meshes
• Marching Triangles, Squares, Cubes, Tetrahedrons
• Goals
• History
• Conclusion
• TODO

Intro

STATUS: Broken. Bleeding. I have redesigned the code more as a library and hence this project will need to be rewritten. This is to be an integrated solution so different tessellations have similar tools and interfaces. This code has been broken for 12 months. 2007-02-01.

I started this to apply marching tetrahedrons to a structure of points that was not a grid. Very soon it became clear that tessellating any collection of points into tetrahedrons, and then applying marching tetrahedrons was the way to go.

This lead me to become interested in tessellation, and I have made a tessellation algorithm. Someone else has probably done it before, but I really wanted to know how some things worked.

The resulting algorithm is still being documented and developed. See CE's Convex Tesselation Algorithm

Source

Files

Doxygen

[zero@localhost triangle]$ ./main
Marching Triangles/Tetrahedrons Project
  by Chelton Evans
 
$./main head=true
   Heart with Marching Tetrahedrons.
$./main circle=true
   Circle with random tessellation and Marching Triangles.
$./main circleu=true
   Circle with Marching triangles with uniform grid.
$./main develope=true
   Development environment for algorithm.

Algorithm Properties/Goals

From the outset I had a vision for the algorithm

• Develop the algorithm in 2D
• Generalize from 2D to 3D
• Use the most primitive objects: triangles for 2D, tetrahedrons for 3D
• Construction from non-uniform or random point structure and tessellate the points.
• In general not be O(n^2) in space. Instead by fast and potentially adaptable to O(1) constant time insertion.
• Find a way of transversing triangular data structures.
• Apply marching triangles/tetrahedrons for 2D/3D.

History

Ordered newest to oldest entries.

• Faceted normals because I could not see the surface geometry without them. The same heat shape using marching tetrahedrons over a uniform grid.
• Implemented marching tetrahedrons with uniform grid. Because need general marching tetrahedrons working before 3D tessellation. A sphere and heart shape implemented for testing marching tetrahedrons. I would like normals but no time.
• Documentation of algorithm in 2D. This proved that the algorithm will work in 3D because there is no real difference. e.g. transversing boundary in 2D is traveling across a line, in 3D a surface. The obvious difference is complexity, but essentially the algorithm is the same.
• Corrected the tessellation, see 2D: Atrocious Triangles with Correction . The first image has the same data points as the previous example, but the curve much better approximates the circle. So this was a real improvement. The red curves are continuous, the apparent discontinuity is removed under magnification where another point is found. The method works correctly there is no error here.
• Tessellation problem. The yellow is the target curve. The red is what is actually drawn by marching triangles. Blue is the triangle tessellation. The good new is that marching triangles definitely works. Closed loops are formed which is expected. The bad news is that the tessellation is critical. By having points of the same color connected by a line the target curve is sliced in half. I am now confident that marching triangles and tetrahedrons will work on an arbitrarily tessellated grid providing the tessellation is balanced.
• Implemented a greedy minimization. Looked at the left triangle then the right. If the face of the triangle pointed in the direction of the point a move was made. There was no comparison as to which direction was better, the left was chosen to be tested first for convenience. This was a much simpler algorithm. At each move the current triangle was tested to see if the point was inside it. When no more moves were possible the current triangle was at the minimum or on the boundary.
• Minimization solution. Minimize on the distance of the target point to the triangles line segment. This should simplify the algorithm and do away with local minimums experienced in the previous problem.
• Minimization problem. Here is a case where the target point has not been identified by the minimization algorithm. The minimization algorithm works by moving left or right to a new minimum vertex distance or moving about the minimum vertex. However in this case it can not move away from the local minimum. The target point is 4.93583, 7.7822 and is labeled yellow in the diagram. The cp is rotating clockwise about 5.0,6.0 .
• Transversal over tri data structure. Called a transverser, the client gives it initial tri's and it follows the links. The client also configures the boundary. The transverser is very general because it can iterate over any tri structure. It forwards the work to a client supplied functional object which processes the triangle. Code reference include/transverser.h .
• Minimize cp to nearest point problem. See tritess::minimizevertex(unsigned int const targ) . Not only was a point minimized to the nearest point, in the event that the point was outside the convex tri structure the cp was placed on the boundary (base vertex on boundary). So another mini-algorithm to get the visible edges can be written. Transversal along the boundary was supported, see tritess::boundaryorientaboutvertexright().
• Area integration implemented on a uniform grid. Provided inversion of area. Similar to marching triangles I identified the different cases the area of the triangles is summed. Code reference include/trimarcharea.h .
• Marching triangles implemented on a uniform grid.
• Implemented the triangle shape data structure. I discovered that you could move through a convex triangle tessellated region with only left and right turning options. No need for a third direction - a binary transversal. This simplifies the minimization problem by simplifying transversal. The triangle is oriented with the base as red and the top green. You can transverse left or right relative to the base.
• Investigated mesh simplification. By looking at bad meshes and the perfect mesh(Delaunay triangulation) I came to the following conclusion that bad meshes have large numbers of edges about some points. If a hex grid is ideal then each point should have 6 edges. A mesh balancing algorithm could be thought up analogous to tree balancing where if a vertex has greater than 7 or 8 edges the vertex is rebalanced. Further if this was a constraint at insertion the job is easier. Consequently I am happy to develop with the atrocious mesh in light that as an optimization the mesh problem can be fixed. For a brute force solution you could develop another algorithm to presort the points first before feeding to the insertion algorithm (O(n^2) complexity). The points are fed in such a way that between new insertions the time is constant(have pointer to last insertion point and minimize from there).
• Investigated triangular meshes and the quality of the mesh. The algorithm I am planning is fast but produces atrocious meshes, but in theory could reach constant time (with indexing added).
• Created new data structure from a shapes perspective. See Polygon Meshes
• Problem with non-convex boundaries : difficult to build. Resolved to use convex regions for simplicity, which by default have convex boundaries. Convexity makes finding a minimum easy because you are guaranteed traversal towards the minimum is possible for every step till termination.
• Meeting with Geoff.
• Discovered a connection with boundary representations and mathematics. Non-convex boundaries can be represented as equations. See tri
• Identified two types of meshes : ones where all the points are retained and others which simplify - triangular decimation. For example if only the boundary is of intersect (building a volume) no need to keep points inside the region. For applications with massive data simplification of some sort is necessary.
• Insertion of a new point in either one of two regions : the inside or outside regions. The inside is tessellated by the basic shape. e.g. triangles for 2D.

Algorithm Extensions

A wish list perhaps, many possibilities.

• decimation to actively reduce point size while algorithm evaluates taking advantage of a cutoff value. The tessellation is no longer independent of the cutoff or function value.
• Minimize(or maximize, whichever is best) the number of intersection points along the boundary by re tessellating along the boundary. Could be a final stage of the algorithm for increased accuracy in area calculations.
• Add some form of indexing into the convex region to really speed things up. f(x,y) -> i where i is a triangle near the minimum could potentially turn the algorithm to O(n).
• Adding a dimension: if every triangle was given a virtual link to another triangle in the mesh then minimization in the mesh could be sped up. e.g. consider left, right and virtual triangle links for best transversal.

Conclusion

I have really enjoyed the project and despite the risks am very happy with the result.

New data structures were explored that proved themselves. The algorithms were made using these data structures.

Many issues were canvased. e.g. I had concerns over continuity of the surface which proved to be non-existent. I used convexity in the data structure which the conventional data structure does not exploit.

Early on in development I discovered the link between convex and non-convex boundary representations as AND and OR operations, something which I have never before come across. Indeed this could have made a project in its own right and came about though the long process of developing the algorithm where I was looking at a point in a region before I settled on the region being convex. See tri.

TODO

• Cleanup.