ACM SIGGRAPH Computer Graphics · 1987 · 118 citations · 14 references
ArchitectureComputer Science3D ModelingComputational GeometryGeometric ModelingGeometric ApproximationGeometry ProcessingSubdivision SurfacesSurface IntersectionsSurface ModelingSurface ReconstructionAdaptive SamplingAdaptive SubdivisionParametric SurfacesSubdivisionSubdivision TechniqueSurface SubdivisionTriangulation AlgorithmsTriangulations
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.
14
An improved illumination model for shaded display
Turner Whitted · Communications of the ACM · 1980 · 1.8K citations · Full text
Optimal Search in Planar Subdivisions
David Kirkpatrick · SIAM Journal on Computing · 1983 · 751 citations
Free-form deformation of solid geometric models
Thomas W. Sederberg, Scott R. Parry · 1986 · 685 citations
Global and local deformations of solid primitives
Alan H. Barr · ACM SIGGRAPH Computer Graphics · 1984 · 473 citations · Full text