Implementing Metric Operators of a Spatial Query Language for 3D Building Models: Octree and B-Rep Approaches

A spatial query language for building information models enables the spatial analysis of buildings and the extraction of partial models that fulfill certain spatial constraints. Among other features, the developed spatial query language includes metric operators, i.e., operators that reflect distance relationships between spatial objects, such as mindist, maxdist, isCloser and isFarther. The paper presents formal definitions of the semantics of these operators by using point set theory notation. It further describes two possible implementation methods: the first one is based on a discrete representation of the operands' geometry by means of the hierarchical, space-partitioning data structure octree. The octree allows for the application of recursive algorithms that successively increase the discrete resolution of the spatial objects employed and thereby enables the user to trade off between computational effort and the required accuracy. By contrast, the second approach uses the exact boundary representation (B-Rep) of both spatial objects resulting in precise distance measurements. Here, the bounding facets of each operand are indexed by a so-called axis-aligned bounding boxes tree (AABB tree). The algorithm uses the AABB-tree structure to identify candidate pairs of facets, for which an exact but expensive distance algorithm is employed. The article compares both approaches by means of detailed investigations on the runtime performance of the developed algorithms.