Accelerated robust Boolean operations based on hybrid representations

Bin SHENG, Bowen LIU, Ping LI, Hongbo FU, Lizhuang MA, Enhua WU

Research output: Contribution to journalArticle

Abstract

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. Copyright © 2018 Elsevier B.V. All rights reserved.
LanguageEnglish
Pages133-153
JournalComputer Aided Geometric Design
Volume62
Early online dateMar 2018
DOIs
Publication statusPublished - 2018

Fingerprint

Boolean Operation
Vertex of a graph
Robustness
Metadata
Constructive Solid Geometry
Topology
Binary operation
3D Modeling
Evaluation
Evaluation Method
Geometry
Polyhedron
Predicate
Trade-offs
Mesh
Query
Experiments
Evaluate
Experimental Results
Coefficient

Citation

Sheng, B., Liu, B., Li, P., Fu, H., Ma, L., & Wu, E. (2018). Accelerated robust Boolean operations based on hybrid representations. Computer Aided Geometric Design, 62, 133-153. doi: 10.1016/j.cagd.2018.03.021

Keywords

  • Boolean operations
  • Plane-based geometry
  • Constructive solid geometry
  • PG student publication