“Approximate Boolean operations on free-form solids” by Biermann, Kristjansson and Zorin

  • ©Henning Biermann, Daniel Kristjansson, and Denis Zorin




    Approximate Boolean operations on free-form solids



    In this paper we describe a method for computing approximate results of boolcan operations (union, intersection, difference) applied to free-form solids bounded by multiresolution subdivision surfaces.
    We present algorithms for generating a control mesh for a multiresolution surface approximating the result, optimizing the parameterization of the new surface with respect to the original surfaces, and fitting the new surface to the geometry of the original surfaces. Our algorithms aim to minimize the size and optimize the quality of the new control mesh. The original control meshes are modified only in a neighborhood of the intersection.
    While the main goal is to obtain approximate results, high-accuracy approximations are also possible at additional computational expense, if the topology of the intersection curve is resolved correctly.


    1. A. Agrawal and A. Requicha. A paradigm for the robust design of algorithms
      for geometric modeling”. Computer Graphics Forum, 13(3):33–44, 1994.
      R. E. Bank. PLTMG: A Software Package for Solving Elliptic Partial Differential
      Equations – Users’ Guide 7.0, volume 15 of Frontiers in Applied Mathematics.
      SIAM Books, Philadelphia, 1994.
    2. R. E. Barnhill, G. Farin, M. Jordan, and B. R. Piper. Surface/surface intersection.
      Computer Aided Geometric Design, 4(1-2):3–16, July 1987.
      Henning Biermann, Adi Levin, and Denis Zorin. Piecewise smooth subdivision
      surfaces with normal control. Proceedings of SIGGRAPH 2000, July 2000.
    3. C. Burnikel, S. Funke, and M. Seel. Exact arithmetic using cascaded computation. ACM Symposium on Computational Geometry, (14):175–193, 1998.
    4. Christoph Burnikel, Kurt Mehlhorn, and Stefan Schirra. On degeneracy in geometric computations. In Proceedings of the Fifth Annual ACM-SIAM Symposium
      on Discrete Algorithms (Arlington, VA, 1994), pages 16–23, New York, 1994.
    5. Katrin Dobrindt, Kurt Mehlhorn, and Mariette Yvinec. A complete and efficient algorithm for the intersection of a general and a convex polyhedron. In
      Algorithms and data structures (Montreal, PQ, 1993), pages 314–324. Springer,
      Berlin, 1993.
    6. D. Epstein, N. Gharachorloo, F. Jansen, J. Rossignac, , and C. Zoulos. Multiple
      depth-buffer rendering of csg. Technical report, IBM Research Report, 1989.
    7. D. A. Field. Laplacian smoothing and delaunay triangulations. Comm. Applications: Numerical Methods, (4):709–712, 1988.
    8. Lori Freitag, Mark Jones, and Paul Plassmann. A parallel algorithm for mesh
      smoothing. SIAM J. Sci. Comput., 20(6):2023–2040 (electronic), 1999.
    9. Jack Goldfeather, Jeff P. M. Hultquist, and Henry Fuchs. Fast constructivesolid geometry display in the pixel-powers graphics system. Computer Graphics
      (Proceedings of SIGGRAPH 86), 20(4):107–116, August 1986. Held in Dallas,
    10. Igor Guskov, Kiril Vidimce, Wim Sweldens, and Peter Schr ˘ oder. Normal meshes. ¨
      Proceedings of SIGGRAPH 2000, pages 95–102, July 2000.
    11. Mark Halstead, Michael Kass, and Tony DeRose. Efficient, fair interpolation
      using Catmull-Clark surfaces. In Computer Graphics Proceedings, Annual Conference Series, pages 35–44. ACM Siggraph, 1993.
    12. Christoph M. Hoffmann. Geometric and solid modeling: a introduction. San
      Mateo, California: Morgan Kaufmann, 1989.
    13. Hugues Hoppe, Tony DeRose, Tom Duchamp, Mark Halstead, Huber Jin, John
      McDonald, Jean Schweitzer, and Werner Stuetzle. Piecewise smooth surface
      reconsruction. In Computer Graphics Proceedings, Annual Conference Series,
      pages 295–302. ACM Siggraph, 1994.
    14. Josef Hoschek and Dieter Lasser. Fundamentals of computer aided geometric
      design. A K Peters Ltd., Wellesley, MA, 1993. Translated from the 1992 German
      edition by Larry L. Schumaker.
    15. Leif P. Kobbelt, Katja Daubert, and Hans-Peter Seidel. Ray tracing of subdivision
      surfaces. Eurographics Rendering Workshop 1998, pages 69–80, June 1998.
      Held in Vienna, Austria.
    16. Shankar Krishnan and Dinesh Manocha. An efficient surface intersection algorithm based on lower-dimensional formulation. ACM Transactions on Graphics,
      16(1):74–106, January 1997. ISSN 0730-0301.
    17. Aaron W. F. Lee, Wim Sweldens, Peter Schroder, Lawrence Cowsar, and David ¨
      Dobkin. Maps: Multiresolution adaptive parameterization of surfaces. Proceedings of SIGGRAPH 98, pages 95–104, July 1998.
    18. A. Levin. Combined subdivision schemes for the design of surfaces satisfying
      boundary conditions. Computer Aided Geometric Design, 16(5):345–354, 1999.
    19. Ming Lin and Stefan Gottschalk. Collision detection between geometric models:
      A survey. Proceedings of IMA Conference on Mathematics of Surfaces, 1998.
    20. Lars Linsen. Schneiden und vereinen von kontrollnetzen (intersection and merging of control meshes.). Master’s thesis, Universitat Karlsruhe, 1997. in German. ¨
      Nathan Litke, Adi Levin, and Peter Schroder. Trimming for subdivision surfaces. ¨
      Technical report, Caltech, 2000.
    21. Michael Lounsbery, Tony DeRose, and Joe Warren. Multiresolution analysis for
      surfaces of arbitrary topological type. Transactions on Graphics, 16(1):34–73,
      January 1997.
    22. Lee Markosian, Jonathan M. Cohen, Thomas Crulli, and John F. Hughes. Skin: A
      constructive approach to modeling free-form shapes. Proceedings of SIGGRAPH
      99, pages 393–400, August 1999. Held in Los Angeles, California.
    23. K. Pulli and M. Lounsbery. Hierarchical editing and rendering of subdivision
      surfaces. Technical Report UW-CSE-97-04-07, Dept. of CS&E, University of
      Washington, Seattle, WA, 1997.
    24. Ari Rappoport and Steven Spitz. Interactive boolean operations for conceptual
      design of 3-d solids. Proceedings of SIGGRAPH 97, pages 269–278, August
      1997. Held in Los Angeles, California.
    25. J. Rossignac and A. Requicha. Solid modeling. In J. Webster, editor, Encyclopedia of Electrical and Electronics Engineering. John Wiley and Sons, 1999.
    26. T. Sederberg and T. Nishita. Geometric hermite approximation of surface patch
      intersection curves. Computer Aided Geometric Design, 8(2):97–114, 1991.
    27. R. Seidel. The nature and meaning of perturbations in geometric computing.
      Discrete Comput. Geom., 19(1):1–17, 1998.
    28. Jonathan Richard Shewchuk. Adaptive precision floating-point arithmetic and
      fast robust geometric predicates. Technical report, Carnegie Mellon University,
    29. Jos Stam. Exact evaluation of catmull-clark subdivision surfaces at arbitrary
      parameter values. Proceedings of SIGGRAPH 98, pages 395–404, July 1998.
      Held in Orlando, Florida.
    30. A. James Stewart. Local robustness and its application to polyhedral intersection.
      Internat. J. Comput. Geom. Appl., 4(1):87–118, 1994.
    31. Gabriel Taubin. A signal processing approach to fair surface design. In Robert
      Cook, editor, SIGGRAPH 95 Conference Proceedings, Annual Conference Series, pages 351–358. ACM SIGGRAPH, Addison Wesley, August 1995.
    32. Denis Zorin, Peter Schroder, and Wim Sweldens. Interactive multiresolution ¨
      mesh editing. Proceedings of SIGGRAPH 97, pages 259–268, August 1997.

ACM Digital Library Publication:

Overview Page: