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.
The original Fandisk model The layering of the fandisk model
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 fandisk model's Vertex Tree
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
If you have any questions or comments, email me at firstname.lastname@example.org