linktessbuild

Intro

STATUS: Escalate.

Many other tessellation algorithms can be used to construct tessellations. The majority have no concept of linking the simplexes. Here is an algorithms that creates a linked simplex mesh from an existing tessellation in O(n) time.

This gives a way of comparing tessellations and making them more useful by reading them into a more general data structure.

This also uses a core question of given a face which simplex does it belong to. So a general simplex to face data structure will be constructed and used in several other algorithms.

The tessellation as input is given as a list of points. The points must be unique so that if two simplexes share a border then they share exactly the same points. Label the simplexes from 1 onwards.

For a balanced mesh this algorithm is linear in time. This is important as it will not change the complexity of other algorithms using it. Generally other algorithms which do so have at least linear time complexity.

Spec

Implement a linked list. Each link will hold an integer which is a pointer to a simplex.

Construct an array of link pointers the same size as the number of points.

Iterate over the tessellation given in the input. Each simplex has its id added to the points list of integer indexes. So given a point we know exactly what simplexes have the point.

Once the points to simplexes data structure is constructed, iterate over the simplexes. For each simplex iterate over its faces. If the face is not already connected test if another simplex also shares this face.

For example in 2D a face is a line. Points 5 and 7 make up a line of simplex 3. Lookup the points list of 5 and 7. Compare these lists and find their intersection - the common points to both lists. This should be a constant time operation as the tessellation is balanced this comparison has a maximum number of elements to consider.

The lookup showed that simplexes 3 and 8 shared these points hence these simplexes border each other. Then connect the two simplexes. Find the point opposite the face and set its neighbor to the other simplex.

A dynamic structure can also be implemented where new points and tessellations are added (to the end of the point list). This extends the problem and is useful to the mesh building algorithm.

Source

Files

Doxygen