BREP-INDEX: A MULTIDIMENSIONAL SPACE PARTITIONING TREE
George Vaněček · International Journal of Computational Geometry & Applications · 1991
In this paper we present the Brep-index, a multidimensional space partitioning data structure that provides quick spatial access to the vertices, edges and faces of a boundary representation (Brep), thus yielding a single unified representation for polyhedral solids. We give an algorithm for the construction of the Brep-index and prove its correctness. We show that its size is Ω(v+e+f), where v, e, and f are the number of vertices, edges, and faces of the Brep. The lower bound can be achieved for some Breps by compressing the structure using simple rewrite rules. We then demonstrate robust point and line/Brep classification methods given an implementation that uses finite-precision arithmetic.