“Mesh arrangements for solid geometry”
Conference:
Type:
Title:
- Mesh arrangements for solid geometry
Session/Category Title: GEOMETRY
Presenter(s)/Author(s):
Moderator(s):
Abstract:
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.
References:
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
