A Caltech Library Service

Accurate triangulations of deformed, intersecting surfaces

Von Herzen, Brian and Barr, Alan H. (1987) Accurate triangulations of deformed, intersecting surfaces. In: SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM , New York, NY, pp. 103-110. ISBN 0-89791-227-6.

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:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© 1987 ACM.
Subject Keywords:Algorithms, Restricted quadtrees, adaptive sampling of parametric surfaces
Classification Code:1.3.5 [Computer Graphics]: Computational Geometry and Object Modeling- curve, surface, solid, and object representations; geometric algorithms, languages and systems; J.6 [Computer Applications]: Computer-Aided Engineering- computer-a
Record Number:CaltechAUTHORS:20161102-164702924
Persistent URL:
Official Citation:Brian Von Herzen and Alan H. Barr. 1987. Accurate triangulations of deformed, intersecting surfaces. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques (SIGGRAPH '87), Maureen C. Stone (Ed.). ACM, New York, NY, USA, 103-110. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71700
Deposited On:03 Nov 2016 17:01
Last Modified:11 Nov 2021 04:49

Repository Staff Only: item control page