×

Accelerated robust Boolean operations based on hybrid representations. (English) Zbl 1505.65138

Summary: Constructive Solid Geometry (CSG) is one of the popular techniques that is widely applied in 3D modeling. It combines primitive solids using Boolean operations. However, the trade-off between efficiency and robustness of Boolean evaluation is difficult to balance. Previous methods sacrifice either efficiency or robustness to achieve advantages in one perspective. Recent works attempt to achieve excellent performance in both aspects through replacing the conventional vertex-based representations (V-reps) with plane-based representations (P-reps) of polyhedrons. Different from V-reps, the P-reps use plane coefficients as meta-data and can lead to benign robustness. However, methods using P-reps have disadvantages in efficiency compared to methods using V-reps. In this paper, we proposed a Boolean evaluation approach that absorbs both the efficiency of V-reps based methods and robustness of P-reps based methods. We design a Boolean evaluation method combining P-reps with V-reps. The P-reps information is utilized for exact predicate computation while information in V-reps is collected for fast topology query and coarse tests. Our proposed approach is variadic: it evaluates a Boolean expression regarding multi-input meshes as a whole rather than a tree of decomposed binary operations. We conduct massive experiments and compare our results with those generated by the state-of-the-art methods. Experimental results show that our approach is robust for solid inputs and has advantages in performance compared to some previous non-robust methods.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

CGAL; Cork; OBBTree; ESOLID
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Banerjee, R. P.; Rossignac, J. R., Topologically exact evaluation of polyhedra defined in CSG with loose primitives, Comput. Graph. Forum, 15, 4, 205-217, (1996)
[2] Barki, H.; Guennebaud, G.; Foufou, S., Exact, robust, and efficient regularized booleans on general 3D meshes, Comput. Math. Appl., 70, 6, 1235-1254, (2015)
[3] Bernstein, G., Cork Boolean library, (2013)
[4] Bernstein, G.; Fussell, D., Fast, exact, linear booleans, Comput. Graph. Forum, 28, 5, 1269-1278, (2009)
[5] Biermann, H.; Kristjansson, D.; Zorin, D., Approximate Boolean operations on free-form solids, (ACM SIGGRAPH, (2001)), 185-194
[6] Campen, M.; Kobbelt, L., Exact and robust (self-) intersections for polygonal meshes, Comput. Graph. Forum, 29, 2, 397-406, (2010)
[7] Chew, L. P., Constrained Delaunay triangulations, Algorithmica, 4, 1-4, 97-108, (1989) · Zbl 0664.68042
[8] Cignoni, P., Visualization and computer graphics library, (2015)
[9] Douze, M.; Franco, J.-S.; Raffin, B., Quickcsg: arbitrary and faster Boolean combinations of n solids, (2015), Inria-Research Centre Grenoble-Rhône-Alpes; INRIA, PhD thesis
[10] Fang, S.; Bruderlin, B.; Zhu, X., Robustness in solid modelling: a tolerance-based intuitionistic approach, Comput. Aided Des., 25, 9, 567-576, (1993) · Zbl 0779.65099
[11] Feito, F. R.; Ogáyar, C. J.; Segura, R. J.; Rivero, M., Fast and accurate evaluation of regularized Boolean operations on triangulated solids, Comput. Aided Des., 45, 3, 705-716, (2013)
[12] Fortune, S., Polyhedral modelling with exact arithmetic, (Proceedings of ACM Symposium on Solid Modeling and Applications, (1995)), 225-234
[13] Fortune, S., Polyhedral modelling with multiprecision integer arithmetic, Comput. Aided Des., 29, 2, 123-133, (1997)
[14] Fortune, S.; Van Wyk, C. J., Efficient exact arithmetic for computational geometry, (Annual Symposium on Computational Geometry, (1993)), 163-172
[15] Frisken, S. F.; Perry, R. N., Simple and efficient traversal methods for quadtrees and octrees, J. Graph. Tools, 7, 3, 1-11, (2002) · Zbl 1098.68940
[16] Gottschalk, S.; Lin, M. C.; Manocha, D., Obbtree: a hierarchical structure for rapid interference detection, (Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, (1996), ACM), 171-180
[17] Granados, M.; Hachenberger, P.; Hert, S.; Kettner, L.; Mehlhorn, K.; Seel, M., Boolean operations on 3D selective nef complexes: data structure, algorithms, and implementation, (ESA, vol. 3, (2003), Springer), 654-666 · Zbl 1266.68201
[18] Hable, J.; Rossignac, J., Blister: GPU-based rendering of Boolean combinations of free-form triangulated shapes, ACM Trans. Graph., 24, 3, 1024-1031, (2005)
[19] Hachenberger, P.; Kettner, L., Boolean operations on 3D selective nef complexes: optimized implementation and experiments, (Proceedings of the 2005 ACM Symposium on Solid and Physical Modeling, (2005), ACM), 163-174
[20] Hachenberger, P.; Kettner, L., 3D Boolean operations on nef polyhedra, (CGAL Editorial Board, CGAL User and Reference Manual. CGAL, 3, (2006))
[21] Hu, C.-Y.; Patrikalakis, N. M.; Ye, X., Robust interval solid modelling. part I: representations, Comput. Aided Des., 28, 10, 807-817, (1996) · Zbl 1387.65011
[22] Hu, C.-Y.; Patrikalakis, N. M.; Ye, X., Robust interval solid modelling. part II: boundary evaluation, Comput. Aided Des., 28, 10, 819-830, (1996) · Zbl 1387.65012
[23] Keyser, J.; Culver, T.; Foskey, M.; Krishnan, S.; Manocha, D., Esolid - a system for exact boundary evaluation, Comput. Aided Des., 36, 2, 175-193, (2004)
[24] Keyser, J.; Krishnan, S.; Manocha, D., Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic. I: representations, Comput. Aided Geom. Des., 16, 9, 841-859, (1999) · Zbl 0997.65039
[25] Keyser, J.; Krishnan, S.; Manocha, D., Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic. II: computation, Comput. Aided Geom. Des., 16, 9, 861-882, (1999) · Zbl 0997.65040
[26] Kobbelt, L., 2010. WebBSP 0.3 Beta.; Kobbelt, L., 2010. WebBSP 0.3 Beta.
[27] Laidlaw, D. H.; Trumbore, W. B.; Hughes, J. F., Constructive solid geometry for polyhedral objects, ACM SIGGRAPH Comput. Graph., 20, 4, 161-170, (1986)
[28] Lin, Y.-H.; Li, Y.-F.; Zio, E., A reliability assessment framework for systems with degradation dependency by combining binary decision diagrams and Monte Carlo simulation, IEEE Trans. Syst. Man Cybern. Syst., 46, 11, 1556-1564, (2016)
[29] Möller, T., A fast triangle-triangle intersection test, J. Graph. Tools, 2, 2, 25-30, (1997)
[30] Naylor, B.; Amanatides, J.; Thibault, W., Merging BSP trees yields polyhedral set operations, ACM SIGGRAPH Comput. Graph., 24, 4, 115-124, (1990)
[31] Ogayar, C. J.; Feito, F. R.; Segura, R. J.; Rivero, M., GPU-based evaluation of Boolean operations on triangulated solids, (SIACG 2006: Ibero-American Symposium in Computer Graphics, (2006))
[32] Ogayar, C. J.; Segura, R. J.; Feito, F. R., Point in solid strategies, Comput. Graph., 29, 4, 616-624, (2005)
[33] Ogáyar-Anguita, C. J.; García-Fernández, Á.; Feito-Higueruela, F. R.; Segura-Sánchez, R. J., Deferred boundary evaluation of complex CSG models, Adv. Eng. Softw., 85, 51-60, (2015)
[34] Pavić, D.; Campen, M.; Kobbelt, L., Hybrid booleans, Comput. Graph. Forum, 29, 1, 75-87, (2010)
[35] Preparata, F. P.; Shamos, M. I., Computational geometry: an introduction, (1985), Springer-Verlag New York, USA, Technical report · Zbl 0759.68037
[36] Priest, D. M., Algorithms for arbitrary precision floating point arithmetic, (Proceedings of the IEEE Symposium on Computer Arithmetic, 1991, (1991)), 132-143
[37] Requicha, A. A.G., Mathematical models of rigid solid objects, (1977), University of Rochester Rochester, NY, USA, Technical report
[38] Requicha, A. A.G., Representations for rigid solids: theory, methods, and systems, ACM Comput. Surv., 12, 4, 437-464, (1980)
[39] Requicha, A. A.; Voelcker, H. B., Boolean operations in solid modeling: boundary evaluation and merging algorithms, Proc. IEEE, 73, 1, 30-44, (1985)
[40] Sargeant, T., Carve CSG Boolean library, (2011)
[41] Segal, M., Using tolerances to guarantee valid polyhedral modeling results, ACM SIGGRAPH, 24, 4, 105-114, (1990)
[42] Shewchuk, J. R., Adaptive precision floating-point arithmetic and fast robust geometric predicates, Discrete Comput. Geom., 18, 3, 305-363, (1997) · Zbl 0892.68098
[43] Shewchuk, J. R., Lecture notes on geometric robustness, (Interpolation, Conditioning, and Quality Measures. Eleventh International Meshing Roundtable, (1999))
[44] Smith, J. M.; Dodgson, N. A., A topologically robust algorithm for Boolean operations on polyhedral shapes using approximate arithmetic, Comput. Aided Des., 39, 2, 149-163, (2007)
[45] Sugihara, K.; Iri, M., A solid modelling system free from topological inconsistency, J. Inf. Process., 12, 4, 380-393, (1989) · Zbl 0794.68163
[46] Thibault, W. C., Application of binary space partitioning trees to geometric modeling and ray-tracing, J. Am. Med. Assoc., 184, (1987)
[47] Thibault, W. C.; Naylor, B. F., Set operations on polyhedra using binary space partitioning trees, ACM SIGGRAPH Comput. Graph., 21, 4, 153-162, (1987)
[48] Tilove, R.; Requicha, A. A., Closure of Boolean operations on geometric entities, Comput. Aided Des., 12, 5, 219-220, (1980)
[49] Updegrove, A.; Wilson, N. M.; Shadden, S. C., Boolean and smoothing of discrete polygonal surfaces, Adv. Eng. Softw., 95, 16-27, (2016)
[50] Varadhan, G.; Krishnan, S.; Sriram, T.; Manocha, D., Topology preserving surface extraction using adaptive subdivision, (Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, (2004), ACM), 235-244
[51] Wang, C. C., Approximate Boolean operations on large polyhedral solids with partial mesh reconstruction, IEEE Trans. Vis. Comput. Graph., 17, 6, 836-849, (2011)
[52] Zhao, H.; Wang, C. C.; Chen, Y.; Jin, X., Parallel and efficient Boolean on polygonal solids, Vis. Comput., 27, 6, 507-517, (2011)
[53] Zhou, Q.; Grinspun, E.; Zorin, D.; Jacobson, A., Mesh arrangements for solid geometry, ACM Trans. Graph., 35, 4, 39, (2016)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.