A Caltech Library Service

Accurate triangulations of deformed, intersecting surfaces

Von Herzen, Brian and Barr, Alan H. (1987) Accurate triangulations of deformed, intersecting surfaces. ACM SIGGRAPH Computer Graphics, 21 (4). pp. 103-110. ISSN 0097-8930. doi:10.1145/37402.37415.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


A quadtree algorithm is developed to triangulate deformed, intersecting parametric surfaces. The biggest problem with adaptive sampling is to guarantee that the triangulation is accurate within a given tolerance. A new method guarantees the accuracy of the triangulation, given a "Lipschitz" condition on the surface definition. The method constructs a hierarchical set of bounding volumes for the surface, useful for ray tracing and solid modeling operations. The task of adaptively sampling a surface is broken into two parts: a subdivision mechanism for recursively subdividing a surface, and a set of subdivision criteria for controlling the subdivision process. An adaptive sampling technique is said to be robust if it accurately represents the surface being sampled. A new type of quadtree, called a restricted quadtree, is more robust than the traditional unrestricted quadtree at adaptive sampling of parametric surfaces. Each sub-region in the quadtree is half the width of the previous region. The restricted quadtree requires that adjacent regions be the same width within a factor of two, while the traditional quadtree makes no restriction on neighbor width. Restricted surface quadtrees are effective at recursively sampling a parametric surface. Quadtree samples are concentrated in regions of high curvature, and along intersection boundaries, using several subdivision criteria. Silhouette subdivision improves the accuracy of the silhouette boundary when a viewing transformation is available at sampling time. The adaptive sampling method is more robust than uniform sampling, and can be more efficient at rendering deformed, intersecting parametric surfaces.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 1987 ACM.
Subject Keywords:Algorithms, Restricted quadtrees, adaptive sampling of parametric surfaces
Issue or Number:4
Record Number:CaltechAUTHORS:20161102-165218680
Persistent URL:
Official Citation:Brian Von Herzen and Alan H. Barr. 1987. Accurate triangulations of deformed, intersecting surfaces. SIGGRAPH Comput. Graph. 21, 4 (August 1987), 103-110. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71701
Deposited On:03 Nov 2016 16:59
Last Modified:11 Nov 2021 04:49

Repository Staff Only: item control page