Triangle Tree


The triangle tree is the second tree structure generated by cmesh.  It, like the vertex tree, comprises vital geometry information about a given mesh.  The triangle tree is a tree which includes each triangle in a mesh once and only once.  It, along with the marching pattern, allow a mesh's information to be compressed losslessly.

The triangle tree is constructed in a manner similar to the vertex tree.  However, unlike the vertex tree, the triangle tree is a binary tree.  This means that a node within the tree can have at most 2 children.  The procedure of constructing a triangle tree is as follows.

As noted before, layering a mesh alleviates the determination of the vertex tree.  In addition, layering a mesh alleviates determination of the triangle tree.  During the layering process, triangles are put into a specific layer.  Therefore, one picks a triangle to be the root of the tree.  From here, one traverses each layer in either a clockwise or counter-clockwise manner, picking up triangles along the way.  One should not proceed to the a subsequent layer until all triangles in the current layer are included.  An example of a layering and vertex and triangle tree for a fandisk model are shown below.  The first triangle of the triangle tree is black, while the other triangles in the first layer are white.  Note that the vertex tree, in conjunction with the layering scheme, helps in the determination of the triangle tree.

        

                                The original fandisk model                                              The layering of the fandisk model
 

                                            

The vertex tree (black lines) and the triangle tree (white/black lines)


The triangle tree also includes what is termed the marching pattern.  Since the triangle tree is essentially a seuence of triangle strips, the difference between one triangle and the next triangle is a single vertex.  This is because adjacent triangles share two endpoints (or vertices).  As a result, by using a structure termed the bounding loop (which can be constructed using the vertex tree), one can determine which is the next vertex within the vertex tree that comprises the next triangle.  This can be done using a single bit (0 or 1) for each triangle.

The storage of the triangle tree is as follows.  Each run of triangles has a length.  Furthermore, due to the triangle tree being a binary structure, a triangle which ends a run is either a branching triangle or a leaf triangle.  A leaf triangle is a triangle which has no children, while a branching triangle will have 2 children.  Therefore, all that is needed to be stored, in addition to the marching pattern for each run, is the LENGTH value and LEAF bit.  A leaf bit value of 0 means the run does not end in a leaf triangle (thus it ends in a branching triangle), while a leaf bit value of 1 indicates the current run does end in a leaf triangle.  Like the vertex tree, and adaptive bit method is used for efficient storage of the triangle tree.  For more information about this structure, click HERE and then choose the technical report #RC-20340 entitled "Geometric Compression Through Topological Surgery".
 
 

If you have any questions or comments, email me at scottm@meru.cecs.missouri.edu