Sampling Deformed, Intersecting Surfaces with Quadtrees

Abstract

A quadtree algorithm is developed to render deformed, intersecting parametric surfaces with inside-outside functions. The task of adaptively sampling a surface may be broken into two parts: a subdivision mechanism for recursively subdividing a surface, and a set of subdivision criteria for determining where to subdivide. A surface quadtree is a collection of parametric samples arranged in a quadtree. A restricted quadtree is a quadtree whose neighboring elements must be the same size within a factor of two. Restricted surface quadtrees are shown to be an effective recursive subdivision mechanism. The quadtree samples are concentrated along silhouette and intersection boundaries, and in regions of high curvature, using several subdivision criteria. The recursive subdivision algorithm that finds the sample points is proven to have a complexity of O(n) along boundary curves, where n is the linear resolution of the boundary in parameter space. A new proximity subdivision criterion concentrates samples where two surfaces potentially intersect. An extended modeling hierarchy that includes deformations is demonstrated with several examples. The initial implementation using surface quadtrees is moderately more efficient and substantially more robust than uniform Sampling techniques; surface quadtrees are potentially much more efficient and robust than uniform sampling at rendering deformed, intersecting surfaces.