“Accurate triangulations of deformed, intersecting surfaces” by Von Herzen and Barr

  • ©Brian Von Herzen and Alan H. Barr

Conference:


Type:


Title:

    Accurate triangulations of deformed, intersecting surfaces

Presenter(s)/Author(s):


Abstract:


    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.

References:


    1. Barr, Alan H., “Geometric Modeling and Fluid Dynamic Analysis of Swimming Spermatozoa,” Ph.D. Thesis, Rensselaer Polytechnic Institute, 1983.
    2. Barr, Alan H. Local and Global Deformations of Solid Primitives. Proceedings of SIGGRAPH’84 (Minneapolis, Minnesota, July 23-27, 1984). In Computer Graphics 18, 3 (July 1984), 21-30. 
    3. Barr, Alan H. Ray Tracing Deformed Surfaces. Proceedings of SIGGRAPH’86(Dallas, Texas, August 18-22, 1986). In Computer Graphics 20, 4 (August 1986), 287-296. 
    4. Blinn, Jim, “Computer Display of Curved Surfaces,” Ph.D. Thesis, University of Utah, 1978. 
    5. Carlson, Wayne E. An algorithm and data structure for 3D Object Synthesis using Surface Patch Intersections. Proceedings of SIGGRAPH’82 (Boston, Massachusetts, July 26-30, 1982). In Computer Graphics 16, 3 (July, 1982), 255. 
    6. Catmull, Ed, “Computer Display of Curved Surfaces,” IEEE Conference Proceedings on Computer Graphics, Pattern Recognition and Data Structures, May 1975, p. 11.
    7. Kay, Tim and Jim Kajiya. Ray Tracing Complex Scenes. Proceedings of SIGGRAPH86 (Dallas, Texas, August 18-22, 1986). In Computer Graphics 20, 4 (August 1986), 269. 
    8. Kirkpatrick, David, “Optimal Search in Planar Subdivisions,” SIAM J. Comput., Volume 12, Number 1, February 1983, p. 28.
    9. Lane, Jeff and Loren Carpenter, “A Generalized Scan Line Algorithm for the Computer Display of Parametrically Defined Surfaces,” Computer Graphics and Image Processing, Volume 11, 1979, p. 290.
    10. Lane, Jeff and Richard F. Riesenfeld, “A Theoretical Development for the Computer Generation and Display of Piecewise Polynomial Surfaces,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume PAMI-2, Number 1, January 1980, pp. 35-46.
    11. Lin C. C., and L. A. Segel, Mathematics Applied to Deterministic Problems in the Natural Sciences. Macmillan Publishing Co., Inc., New York, 1974, pp. 56-57.
    12. Rao, S. S., “Optimization Theory and Applications,” Wiley Eastern Limited, New Delhi, India, 1984, pp. 248-249.
    13. Samet, Hanan “Neighbor Finding Techniques for Images Represented by Quadtrees,” Computer Graphics and Image Processing, Volume 18, 1982, p. 37.
    14. Samet, Hanan “The Quadtree and Related Hierarchical Data Structures,” Computing Surveys 16, 2 (June 1984), 187-260. 
    15. Schmitt, Francis, Brian Barsky, Wen-Hui Du. An Adaptive Subdivision Method for Surface-Fitting from Sampled Data. Proceedings of SIGGRAPH86 (Dallas, Texas, August 18-22, 1986). In Computer Graphics 20, 4 (August 1986), 179-188. 
    16. Schweitzer, D., and E. S. Cobb. Scanline Rendering of Parametric Surfaces. Proceedings of SIGGRAPH’82 (Boston, Massachusetts, July 26- 30, 1982). In Computer Graphics 16, 3 (July, 1982), 265. 
    17. Sederberg, Tom and Scott Parry. Free-Form Deformation of Solid Geometric Models. Proceedings of SIGGRAPH’86 (Dallas, Texas, August 18-22, 1986). In Computer Graphics 20, 4 (August 1986), 151-160. 
    18. Snyder, John M. and Al Barr, “Ray Tracing Complex Models Containing Surface Tessellations,” Proceedings of SIGGRAPH’87 (Anaheim, California, July 27-31, 1987). In Computer Graphics 21, 3 (July 1987),. 
    19. Wamock, J. E., “A Hidden-Line Algorithm for Halftone Picture Representation,” Ph.D. thesis, University of Utah, 1969.
    20. Whitted, Turner, “An Improved Illumination Model for Shaded Display,” Communications ACM, Volume 23, Number 6, June 1980, p. 343. 

ACM Digital Library Publication:


Overview Page: