“Mesh arrangements for solid geometry”

  • ©Pan Li, Bin Wang, Feng Sun, Xiaohu Guo, Caiming Zhang, and Wenping Wang




    Mesh arrangements for solid geometry

Session/Category Title: GEOMETRY




    Many high-level geometry processing tasks rely on low-level constructive solid geometry operations. Though trivial for implicit representations, boolean operations are notoriously difficult to execute robustly for explicit boundary representations. Existing methods for 3D triangle meshes fall short in one way or another. Some methods are fast but fail to produce closed, self-intersection free output. Other methods are robust but place prohibitively strict assumptions on the input, e.g., no hollow cavities, non-manifold edges or self-intersections. We propose a systematic recipe for conducting a family of exact constructive solid geometry operations. The two-stage method makes no general position assumptions and does not resort to numerical perturbation. The method is variadic, operating on any number of input meshes. This generalizes unary mesh-repair operations, classic binary boolean differencing, and n-ary operations such as finding all regions inside at least k out of n inputs. We demonstrate the superior effectiveness and robustness of our method on a dataset of 10,000 “real-world” meshes from a popular online repository. To encourage development, validation, and comparison, we release both our code and dataset to the public.


    1. Attene, M. 2010. A lightweight approach to repairing digitized polygon meshes. The Visual Computer. Google ScholarDigital Library
    2. Attene, M. 2014. Direct repair of self-intersecting meshes. Graphical Models. Google ScholarDigital Library
    3. Banerjee, R. P., and Rossignac, J. R. 1996. Topologically exact evaluation of polyhedra defined in CSG with loose primitives. Comput. Graph. Forum.Google Scholar
    4. Barki, H., Guennebaud, G., and Foufou, S. 2015. Exact, robust, and efficient regularized booleans on general 3d meshes. Computers and Mathematics with Applications. Google ScholarDigital Library
    5. Bernstein, G., and Fussell, D. 2009. Fast, exact, linear booleans. In Proc. SGP. Google ScholarDigital Library
    6. Bernstein, G., 2013. Cork boolean library. https://github.com/gilbo/cork.Google Scholar
    7. Bieri, H., and Nef, W. 1988. Elementary set operations with d-dimensional polyhedra. In Proc. IWCGA. Google ScholarDigital Library
    8. Campen, M., and Kobbelt, L. 2010. Exact and robust (self-) intersections for polygonal meshes. Comput. Graph. Forum.Google Scholar
    9. Campen, M., and Kobbelt, L. 2010. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Comput. Graph. Forum.Google Scholar
    10. Campen, M., Attene, M., and Kobbelt, L., 2012. A practical guide to polygon mesh repairing. Eurographics Tutorial.Google Scholar
    11. CARVE, 2014. Carve: An efficient and robust library for boolean operations on polyhedra. http://carve-csg.com/.Google Scholar
    12. CGAL, 2015. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.Google Scholar
    13. Douze, M., Franco, J.-S., and Raffin, B. 2015. QuickCSG: Arbitrary and faster boolean combinations of n solids. Tech. Rep. 01121419, Inria Research Centre Grenoble, Rhone-Alpes.Google Scholar
    14. Edelsbrunner, H., and Mücke, E. P. 1990. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph.. Google ScholarDigital Library
    15. Fortune, S. 1997. Vertex-rounding a three-dimensional polyhedral subdivision. Discrete Comput. Geom.Google Scholar
    16. Granados, M., Hachenberger, P., Hert, S., Kettner, L., Mehlhorn, K., and Seel, M. 2003. Boolean operations on 3d selective nef complexes: Data structure, algorithms, and implementation. In Proc. ESA.Google Scholar
    17. Jacobson, A., Kavan, L., and Sorkine-Hornung, O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph.. Google ScholarDigital Library
    18. Jacobson, A., Panozzo, D., et al., 2016. libigl: A simple C++ geometry processing library. http://libigl.github.io/libigl/.Google Scholar
    19. Mei, G., and Tipper, J. C. 2013. Simple and robust boolean operations for triangulated surfaces. arXiv preprint arXiv:1308.4434.Google Scholar
    20. Milenkovic, V. J., and Nackman, L. R. 1990. Finding compact coordinate representations for polygons and polyhedra.Google Scholar
    21. Museth, K., Breen, D. E., Whitaker, R. T., and Barr, A. H. 2002. Level set surface editing operators. ACM Trans. Graph.. Google ScholarDigital Library
    22. Naylor, B., Amanatides, J., and Thibault, W. 1990. Merging bsp trees yields polyhedral set operations. In Proc. SIGGRAPH. Google ScholarDigital Library
    23. Pavic, D., Campen, M., and Kobbelt, L. 2010. Hybrid Booleans. Comput. Graph. Forum.Google Scholar
    24. Sacht, L., Jacobson, A., Panozzo, D., Schüller, C., and Sorkine-Hornung, O. 2013. Consistent volumetric discretizations inside self-intersecting surfaces. Proc. SGP. Google ScholarDigital Library
    25. Sacks, E., and Milenkovic, V. 2014. Robust cascading of operations on polyhedra. Computer-Aided Design (Tech. Note). Google ScholarDigital Library
    26. Sugihara, K., and Iri, M. 1992. Construction of the Voronoi diagram for one million generators in single-precision arithmetic. Proc. of the IEEE.Google Scholar
    27. Thibault, W. C., and Naylor, B. F. 1987. Set operations on polyhedra using binary space partitioning trees. In Proc. SIGGRAPH. Google ScholarDigital Library
    28. Varadhan, G., Krishnan, S., Sriram, T., and Manocha, D. 2004. Topology preserving surface extraction using adaptive subdivision. In Proc. SGP. Google ScholarDigital Library
    29. Wang, C. C. L. 2011. Approximate boolean operations on large polyhedral solids with partial mesh reconstruction. IEEE TVCG. Google ScholarDigital Library
    30. Xu, S., and Keyser, J. 2013. Fast and robust booleans on polyhedra. Computer-Aided Design. Google ScholarDigital Library
    31. Zhao, H., Wang, C. C., Chen, Y., and Jin, X. 2011. Parallel and efficient boolean on polygonal solids. The Visual Computer. Google ScholarDigital Library
    32. Zhou, Q., Panetta, J., and Zorin, D. 2013. Worst-case structural analysis. ACM Trans. Graph.. Google ScholarDigital Library

ACM Digital Library Publication: