Martin Schifko
ABSTRACT
We present an algorithm for robust Boolean operations of triangulated solids, which is suitable for real-word industrial applications involving meshes with large numbers of triangles. In order to avoid potential robustness problems, which may be caused by (almost) degenerate triangles or by intersections of nearly co-planar triangles, we use filtered exact arithmetic, based on the libraries CGAL and GNU Multi Precision Arithmetic Library. The method consists of two major steps: First we compute the exact intersection of the meshes using a sweep plane algorithm. Second we apply mesh cleaning methods which allow us to generate output which can safely be represented using floating point numbers. The performance of the method is demonstrated by several examples which are taken from applications at ECS Magna Powertrain.
- Ayala, D., Brunet, P., R. Juan, and I. Navazzo. 1985. Object representation by means of nonminimal division quadtrees and octrees. ACM Trans Graph. 4, 41--59. Google Scholar
Digital Library
- Bernstein, G., and Fussel, D. 2009. Fast, exact, linear Booleans. Comput. Graph. Forum 28 5, 1269--1278.Google ScholarCross Ref
- Brönnimann, H., Burnikel, C., and Pion, S. 2001. Interval arithmetic yields efficient dynamic filters for computational geometry. Discrete Appl. Math. 109, 1--2, 25--47. Google ScholarDigital Library
- Campen, M., and Kobbelt, L. 2010. Exact and robust (Self-) intersections for polygonal meshes. In Proc. Eurographics, Eurographics Assoc. to appear.Google Scholar
- CGAL, 2009. Computational Geometry Algorithms Library. http://www.cgal.org/, last accessed: Oct 27, 2009.Google Scholar
- Chang, J.-W., Wang, W., and Kim, M.-S. 2010. Efficient collision detection using a dual OBB-sphere bounding volume hierarchy. Comp. -Aided Design 42, 50--57. Google ScholarDigital Library
- Dokken, T. 2008. The GAIA project on intersection and implicitization. In Geometric modeling and algebraic geometry, B. Jüttler and R. Piene, Eds. Springer, Berlin, 5--29.Google Scholar
- Fabri, A., and S. Pion. 2006. A generic lazy evaluation scheme for exact geometric computations. In Proc. 2nd Library-Centric Software Design, 75--84.Google Scholar
- Fortune, S. 1998. Vertex-rounding a three-dimensional polyhedral subdivision. In Proc. ACM Symp. Comp. Geom., 116--125. Google ScholarDigital Library
- GNU Multiple Precision Arithmetic Library. http://gmplib.org/, last accessed: Nov 12, 2009.Google Scholar
- Guttman, A. 1984. R-trees: A dynamic index structure for spatial searching. In ACM SIGMOD International Conference on Management of Data, 47--57. Google ScholarDigital Library
- Hachenberger, P., and Kettner, L. 2005. Boolean operations on 3d selective Nef complexes: Optimized implementation and experiments. In ACM Symposium on Solid and Physical Modeling (SPM 2005), 163--174. Google ScholarDigital Library
- Hoffmann, C. M. 2005. Geometric and Solid Modeling: an Introduction. Springer.Google Scholar
- Hubbard, P. 1996. Approximating polyhedra with spheres for time-critical collision detection. ACM Transactions on Graphics 15, 179--210. Google ScholarDigital Library
- Jimenez, P., Thomas, F., and Torras, C. 2001. 3D collision detection: a survey. Comput. Graphics 25, 269--285.Google ScholarCross Ref
- Laidlaw, D. H., Trumbore, W., and Hughes, J. 1986. Constructive solid geometry for polyhedral objects. SIGGRAPH Computational Graph. 20, 161--170. Google ScholarDigital Library
- Lo, S., and Wang, W. 2003. An algorithm for the intersection of quadrilateral surfaces by tracing of neighbours. Comput. Methods Appl. Mech. Eng. 192, 2319--2338.Google ScholarCross Ref
- Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A., and Theodoridis, Y. 1989. R-Trees: Theory and Applications. Morgan Kaufmann.Google Scholar
- Park, S. C. 2004. Triangular mesh intersection. The Visual Computer 20, 448--456. Google ScholarDigital Library
- Pavic, D., Campen, M., and Kobbelt, L. 2010. Hybrid Booleans. Computer Graphics Forum. to appear.Google Scholar
- Sugihara, K., and Ira, M. 1989. A solid modelling system free from topological inconsisteny. J. Inf. Process. 12, 380--393. Google ScholarDigital Library
- Teschner, M., Heidelberger, B., Müller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proceedings of VMV'03, 47--54.Google Scholar
- Thibault, W. C., and Naylor, B. 1987. Set operations on polyhedra using binary space partitioning trees. SIGGRAPH Comput. Graph 21, 153--162. Google ScholarDigital Library
- Thibault, W. C. 1987. Application of binary space partitioning trees to geometric modeling and ray-tracing. PhD thesis, Georgia Institute of Technology. Google ScholarDigital Library
- Thomas, M., and Prosolvia, C. 1997. A fast triangle-triangle intersection test. J. Graphics Tools 22, 25--30. Google ScholarDigital Library
- Tropp, O., Tal, A., and Shimshoni, I. 2006. A fast triangle to triangle intersection test for collision detection. Computer Animation and Virtual Worlds 17, 527--535. Google ScholarDigital Library
Index Terms
- Industrial application of exact Boolean operations for meshes
Recommendations
Boolean operations on arbitrary polygonal and polyhedral meshes
A linearithmic floating-point arithmetic algorithm designed for solving usual boolean operations (intersection, union, and difference) on arbitrary polygonal and polyhedral meshes is described in this paper. This method does not dis-feature the inputs ...
5-6-7 meshes
GI '12: Proceedings of Graphics Interface 2012We introduce a new type of meshes called 5-6-7 meshes. For many mesh processing tasks, low- or high-valence vertices are undesirable. At the same time, it is not always possible to achieve complete vertex valence regularity, i.e., to only have valence-6 ...
Adaptive LOD editing of quad meshes
AFRIGRAPH '10: Proceedings of the 7th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in AfricaWe present a method for editing the LOD of quad meshes, which supports both adaptive refinement and adaptive coarsening. Starting at a base mesh, we generate a quad-dominant mesh which is consistent with the Catmull-Clark subdivision. Consistency is ...
Comments