“BoolSurf: Boolean Operations on Surfaces” by Riso, Nazzaro, Puppo, Jacobson, Zhou, et al. …
Conference:
Type(s):
Title:
- BoolSurf: Boolean Operations on Surfaces
Session/Category Title: Geometric Operations
Presenter(s)/Author(s):
Abstract:
We port Boolean set operations between 2D shapes to surfaces of any genus, with any number of open boundaries. We combine shapes bounded by sets of freely intersecting loops, consisting of geodesic lines and cubic Bézier splines lying on a surface. We compute the arrangement of shapes directly on the surface and assign integer labels to the cells of such arrangement. Differently from the Euclidean case, some arrangements on a manifold may be inconsistent. We detect inconsistent arrangements and help the user to resolve them. Also, we extend to the manifold setting recent work on Boundary-Sampled Halfspaces, thus supporting operations more general than standard Booleans, which are well defined on inconsistent arrangements, too. Our implementation discretizes the input shapes into polylines at an arbitrary resolution, independent of the level of resolution of the underlying mesh. We resolve the arrangement inside each triangle of the mesh independently and combine the results to reconstruct both the boundaries and the interior of each cell in the arrangement. We reconstruct the control points of curves bounding cells, in order to free the result from discretization and provide an output in vector format. We support interactive usage, editing shapes consisting up to 100k line segments on meshes of up to 1M triangles.
References:
1. Adobe inc. 2021. Adobe Illustrator. Adobe inc. https://adobe.com/products/illustrator
2. A. Amirkhanov. 2022. CDT: Constrained Delaunay Triangulation. https://github.com/artem-ogre/CDT
3. M. Attene. 2020. Indirect Predicates for Geometric Constructions. Computer-Aided Design 126 (2020), 102856:1–102856:9.
4. G. Barill, N. G. Dickson, R. Schmidt, D. I. W. Levin, and A. Jacobson. 2018. Fast winding numbers for soups and clouds. ACM Trans. Graph. 37, 4 (2018), 43:1–43:12.
5. G. Bernstein and D. Fussell. 2009. Fast, Exact, Linear Booleans. In Proc. of the Symp. on Geom. Proc. 1269–1278.
6. M. Campen and L. Kobbelt. 2010. Exact and Robust (Self-)Intersections for Polygonal Meshes. Comp. Graph. Forum 29, 2 (2010), 397–406.
7. G. Cherchi, M. Livesu, R. Scateni, and M. Attene. 2020. Fast and Robust Mesh Arrangements using Floating-point Arithmetic. ACM Trans. Graph. 39, 6 (2020), 250:1–250:16.
8. F. de Goes, M. Desbrun, M. Meyer, and T. DeRose. 2016. Subdivision exterior calculus for geometry processing. ACM Trans. Graph. 35, 4 (2016), 133:1–133:11.
9. T.K. Dey and H. Schipper. 1995. A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Computational Geometry 14 (1995), 93–110.
10. X. Du, Q. Zhou, N. Carr, and T. Ju. 2021. Boundary-Sampled Halfspaces: A New Representation for Constructive Solid Modeling. ACM Trans. Graph. 40, 4 (2021), 53:1–53:15.
11. J. Erickson and K. Whittlesey. 2005. Greedy optimal homotopy and homology generators. In Proc. 16th ACM-SIAM Symp. Disc. Alg., Vol. 5. 1038–1046.
12. Steven Fortune and Christopher J. Van Wyk. 1993. Efficient exact arithmetic for computational geometry. In SCG ’93.
13. W. Fulton. 1995. Algebraic Topology: A First Course. Springer, New York, USA.
14. M. Granados, P. Hachenberger, L. Hert, S. adn Kettner, K. Mehlhorn, and M. Seel. 2003. Boolean operations on 3d selective NEF complexes: Data structure, algorithms, and implementation. In Proc. 11th Europ. Symp. on Alg. LNCS, Vol. 2832. Springer, 174–186.
15. B. Grünbaum and G. C. Shephard. 1990. Rotation and winding numbers for planar polygons and curves. Trans. AMS 322, 1 (1990), 169–187.
16. A Hatcher. 2002. Algebraic Topology. Cambridge, UK.
17. Y. Hu, T. Schneider, X. Gao, Q. Zhou, A. Jacobson, D. Zorin, and D. Panozzo. 2019. TriWild: Robust Triangulation with Curve Constraints. ACM Trans. Graph. 38, 4 (2019), 52:1–52:15.
18. Y. Hu, Q. Zhou, X. Gao, A. Jacobson, D. Zorin, and D. Panozzo. 2018. Tetrahedral Meshing in the Wild. ACM Trans. Graph. 37, 4, Article 60 (2018), 14 pages.
19. A. Jacobson, L. Kavan, and O. Sorkine-Hornung. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4 (2013), 33:1–33:12.
20. A. Johnson. 2014. Clipper – an open source freeware library for clipping and offsetting lines and polygons. http://www.angusj.com/delphi/clipper.php
21. D. Knuth. 1986. Metafont: the Program. Addison-Wesley.
22. B. Levy. 2016. Robustness and efficiency of geometric programs: The Predicate Construction Kit (PCK). Computer-Aided Design 72 (2016), 3–12.
23. C. Mancinelli, G. Nazzaro, F. Pellacini, and E. Puppo. 2022. B/Surf: Interactive Bézier Splines on Surfaces. IEEE Trans. VIs. Comp. Graph (2022). to appear.
24. Claudio Mancinelli and Enrico Puppo. 2022. Vector graphics on surfaces using straightedge and compass constructions. Computers & Graphics 105C (2022), 46–56.
25. M. Mcintyre and G. Cairns. 1993. A new formula for winding number. Geometriae Dedicata 46, 2 (1993), 149–159.
26. B. Naylor, J. Amanatides, and W. Thibault. 1990. Merging BSP Trees Yields Polyhedral Set Operations. SIGGRAPH Comput. Graph. 24, 4 (1990), 115–124.
27. G. Nazzaro, E. Puppo, and F. Pellacini. 2021. geoTangle: Interactive Design of Geodesic Tangle Patterns on Surfaces. ACM Trans. Graph. 41, 2 (2021), 12:1–12:17.
28. Diego Nehab and Hugues Hoppe. 2008. Random-access rendering of general vector graphics. ACM Transactions on Graphics (TOG) 27, 5 (2008), 1–10.
29. Ganesh Ramanarayanan, Kavita Bala, and Bruce Walter. 2004. Feature-based textures. Technical Report. Cornell University.
30. B. L Reinhart. 1960. The winding number on two manifolds. Annales de l’Institut Fourier 10 (1960), 271–283.
31. N. Sharp and K. Crane. 2020. You Can Find Geodesic Paths in Triangle Meshes by Just Flipping Edges. ACM Trans. Graph. 39, 6 (2020), 249:1–15.
32. B. R. Vatti. 1992. A Generic Solution to Polygon Clipping. Commun. ACM 35, 7 (1992), 56–63.
33. B. Wang, Z. Ferguson, T. Schneider, X. Jiang, M. Attene, and D. Panozzo. 2021. A Large-Scale Benchmark and an Inclusion-Based Algorithm for Continuous Collision Detection. ACM Trans. Graph. 40, 5, Article 188 (2021), 16 pages.
34. R. Wein, E. Berberich, E. Fogel, D. Halperin, M. Hemmer, O. Salzman, and Zukerman B. 2021. CGAL 5.3.1 – 2D Arrangements. https://doc.cgal.org/latest/Arrangement_on_surface_2/index.html
35. S.-Q. Xin, Y. He, and C.-W. Fu. 2012. Efficiently Computing Exact Geodesic Loops within Finite Steps. IEEE Trans. Vis. Comp. Graphi. 18, 6 (2012), 879–889.
36. Q. Zhou, E. Grinspun, D. Zorin, and A. Jacobson. 2016. Mesh arrangements for solid geometry. ACM Trans. Graph. 35, 4 (2016), 39:1–39:15.
37. Q. Zhou and A. Jacobson. 2016. Thingi10K: A Dataset of 10,000 3D-Printing Models. arXiv:1605.04797
