Premium
Robust Computation of Intersection Graph between Two Solids
Author(s) -
Nakamura Hiroyuki,
Higashi Masatake,
Hosaka Mamoru
Publication year - 1997
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/1467-8659.00144
Subject(s) - intersection (aeronautics) , intersection graph , graph , point (geometry) , face (sociological concept) , computation , computer science , line (geometry) , line segment , algorithm , mathematics , theoretical computer science , combinatorics , line graph , geometry , artificial intelligence , social science , sociology , engineering , aerospace engineering
We propose a new robust algorithm for Boolean operations on solid models. The algorithm produces a consistent intersection graph between two input solids whose geometrical data are represented in floating point numbers. In order to prevent numerical calculation errors and inaccuracy of input data from causing inconsistency of the output, we put higher priority on symbolical connectivity of the edge‐face intersection points than their numerical nearness. Each edge‐face intersection point is symbolically represented using face names, which generate connectivity relations between the intersection points and the intersection line segments. The symbols with the same connectivity are made into clusters. The intersection line segments connected together at their end clusters form the intersection graph of two solids. Inconsistency of the connectivity of the clusters is detected and the intersection graph is corrected automatically. We describe the algorithm in detail for polyhedral solids, discuss extension to curves solids, and show its effectiveness by some examples of Boolean operations for two solids whose faces intersect at a very small angle.