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

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.
   ACM.
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,
   Texas.
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,
    1996.
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.