Vertex Tree

A vertex tree is the structure used to gain vertex position information in a logical format.  The vertex tree includes every vertex of a 3-D triangular mesh.  The construction of a vertex tree can proceed in several different ways.  For example, one way to construct a vertex tree is to simply choose a random vertex as the root vertex.  The next vertex to include would be the vertex which is of minimum Euclidean distance from the root vertex and is connected by an edge (an edge connects vertices within the mesh).  Subsequent vertices would be included in the vertex tree in a similar manner.  However, Gabriel Taubin et al indicated that this results in too many branches in the vertex tree, which is not desirable.  This is because the less branches in the tree, the better the compression ratio.  As a result, a method which is fast and tends to minimize the amount of branches in the tree, and creates cyclical rings is by using a layering method.

To layer a mesh, a starting vertex is chosen - the root.  This single vertex is the first boundary.  Therefore, all triangles (and edges) which have the root vertex as an endpoint comprise the first layer.  Now, each of the triangles in the first layer have 2 other vertices as an endpoint (besides the root).  These vertices then comprise the second boundary.  Therefore, proceeding in a similar manner, the second layer consists of all triangles/edges (not in the first layer) which have a vertex in the second boundary.  This process continues until the entire mesh is layered.  An example of a layering (for the fandisk model) is shown below.  The first triangle layer is white (the triangle chosen as the root of the triangle tree is black).  Edges which separate layers are termed cut edges, while edges within a layer are termed marching edges.
 
 

Once the layering is completed, one can then use the layering scheme to construct the vertex tree.  The root of the vertex tree is already known (it is the vertex which formed the first boundary).  Therefore, an edge which connects the root vertex to a vertex of the second boundary is chosen, and added to the tree.  Then, one simply walks along the second boundary (in either a clockwise or counter-clockwise manner), picking up edges/vertices and adding them to the vertex tree.  Once all vertices of the second boundary have been used, an edge is chosen which separates the second and third boundary (the second layer) to be included in the tree.  This procedure continues until all vertices have been used.  The vertex tree for the fandisk model (with the above layering scheme) is shown below.  Note that all vertices within the first layer are chosen before vertices of the second layer are picked up, and that for the most part, cyclical rings are constructed using this method.
 
 

The way the vertex tree is stored is as follows.  The vertex tree consists of 3 tag fields for each run in the tree.  Each run has a length, a last bit, and a leaf bit associated with it.  The length is simply the length of a run.  The last bit indicates if the current run is the last run which starts at the "current" vertex.  Therefore, suppose a vertex, X, is a branching vertex that has 3 children (so therefore it has three subsequent runs that start at itself).  The first and second runs starting at vertex X would have a 0 for the last bit (as it still has one more run to go), while the 3rd run starting at vertex X would have a 1 for the last bit.  The leaf bit indicates if a run ends in a leaf vertex or not.  If this value is a 0, then that run does not end in a leaf vertex (and thus ends in a branching vertex), while a 1 indicates that that run ends in a leaf bit.  This then constitutes the makeup of the vertex tree.  To store the vertex tree efficiently, an adaptive bit method is used.

It should be noted that the vertex tree generated by this method is not necessarily a binary one (in a binary tree, a node in the tree can have at most 2 children).  In other words, some vertices may have more than 2 children.  However, the triangle tree, the other structure cmesh generates, is a binary tree.
 
 
 
 

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