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
binary tree.

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