Standard library: a simple octree-based clustering algorithm

Routines for building a VDS vertex tree using a VERY simple octree-based clustering scheme.

vdsClusterOctree
Build an octree over the given leaf nodes using vdsClusterNodes()
vdsClusterNodes() provides a flexible interface for constructing the VDS vertex tree, but many users may simply to use this standard simple clustering routine based on a tight octree partitioning of the scene. Given a list of pointers to vdsNodes, vdsClusterOctree() will find a bounding cube, divide the nodes into eight sublists based on what octant of the cube they fall into, and recursively divide the sublists. Nodes are clustered according to this partitioning in a bottom-up fashion, so that the root of the resulting tree corresponds to the initial list given to vdsClusterNodes(), the children of the root correspond to the initial sublists, and so on. Representative vertices for each node are assigned by averaging the position, color, and normal of contributing vertices.

Tight octree clustering is very fast. It is also robust to topological degeneracies, since only vertex positions are taken into account. However, the geometric and visual fidelity of tight octree clustering can be lower than that of more careful algorithms. For a relatively simple-to-code alternative, check out Mesh Simplification Using Quadric Error Metrics, a SIGGRAPH 97 paper by Michael Garland and Paul Heckbert. Papers by Erikson and Manocha, Hoppe, and Lindstrom have since extended the Quadric Error Metrics idea in several ways.

See Also:
cluster.c

alphabetic index hierarchy of classes