Modern graphics systems require processing tremendously complex geometric
descriptions of scenes, e.g. data collected by a laser range scanner. This
complexity is desirable for modeling scenes accurately, but can be difficult
for computer algorithms to handle efficiently.
This paper presents a way to cluster faces on polygonal surfaces
hierarchically, an algorithm to construct such a hierarchy, and an error
metric to guide the algorithm.
The algorithm in this paper is relatively efficient although there may be more
efficient ways to compute fitting planes that can speed up the algorithm. The
fitting planes used for segmentation are sometimes tilted in unintuitive ways.
The current algorith uses PCA to compute fitting planes, and PCA does not
always orient local frames in a way that minimizes bounding box sizes in
regions where a surface is relatively flat.
When partitioning a surface into a small number of clusters, large irregularly
shaped regions may develop. But for large numbers of clusters, the algorithm
adapt well to the shape, being broad in smooth areas and narrower in curved
areas. The hierarchical nature of this paper's segmentation algorithm makes
it useful for radiosity computations.