A Caltech Library Service

Sampling Deformed, Intersecting Surfaces with Quadtrees

Herzen, Brain P. Von (1985) Sampling Deformed, Intersecting Surfaces with Quadtrees. California Institute of Technology . (Unpublished)

See Usage Policy.

Other (Adobe PDF (3MB))
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1985.5179-tr-85
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26955
Deposited By: Imported from CaltechCSTR
Deposited On:25 Jul 2002
Last Modified:03 Oct 2019 03:19

Repository Staff Only: item control page