Dynamic vertex tree maintenance

Routines for controlling simplification at run-time.

Fold the given node
Unfold the given node
Fold the entire subtree rooted at the given node
Unfold the given node, recursively unfolding the node's ancestors first if necessary
Adjust the active boundary of the vertex tree
Traverse given vertex tree top-down, adjusting the boundary
These routines form the heart of the run-time view-dependent simplification processs. They maintain the vertex tree dynamically at render time, as opposed to statically during the tree-building preprocess.

The VDS vertex tree spans the entire model, organizing every vertex of every polygon into one global hierarchy encoding all simplifications VDS can produce. Leaf nodes each represent a single vertex of the original model; internal nodes represent the merging of multiple vertices from the original model into a single vertex called the proxy. A proxy is associated with each node in the vertex tree.

Folding a node merges the vertices supported by the node into its proxy, and unfolding a node reverses the process. Folding and unfolding a node always affects certain triangles. One set of triangles will change in shape as a corner shifts during fold and unfold operations. Another set of triangles, called the node's subtris, will disappear when the node is folded and reappear when the node is unfolded. Since subtris do not depend on the state of other nodes in the vertex tree, they can be computed offline and accessed very quickly at runtime. This is the key observation behind VDS.

Unfolded nodes are labeled Active; folded nodes are labeled Inactive. During operation the active nodes constitute a cut of the vertex tree, rooted at the root node, called the active tree. Folded nodes with active parents are a special case; these nodes form the boundary of the active tree and are labeled Boundary (Figure 6). Since the location of the boundary nodes determines which vertices in the original model have been collapsed together, the path of the boundary nodes across the vertex tree completely determines the current simplification.

To fold a node, use vdsFoldNode(); to unfold a node, use vdsUnfoldNode(). Note that by definition, only Boundary nodes can be unfolded and only Active nodes whose children are all labeled boundary can be folded. For convenience, the vdsFoldSubtree() function recursively folds a given node after first folding all nodes in the subtree rooted below that node.

Usually, the VDSlib user will want to examine all nodes in the vertex tree, applying some criterion to each node to decide whether the node should be folded or unfolded. The vdsAdjustTreeTopDown() call traverses a vertex tree depth-first, applying a user-specified callback function to determine whether to fold, unfold, or leave each node.

Since all folds and unfolds by definition occur at Boundary nodes, it is also possible to simply walk across the active boundary, applying the fold criterion to whether to unfold a Boundary node, fold its parent, or leave both nodes. The vdsAdjustTreeBoundary() call does just this; the boundary path across the vertex tree is maintained as a doubly-linked list of nodes. If the active boundary is not expected to change much from call to call, this function is more efficient than vdsAdjustTreeTopDown().

See Also:

alphabetic index hierarchy of classes