Implementing metric operators of a spatial query language for 3D building models: Octree and b-rep approaches

Andŕ Borrmann, Stefanie Schraufstetter, Ernst Rank

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)34-46
Number of pages13
JournalJournal of Computing in Civil Engineering
Volume23
Issue number1
DOIs
StatePublished - 2009

Keywords

  • Algorithms
  • Information models
  • Spatial analysis

Fingerprint

Dive into the research topics of 'Implementing metric operators of a spatial query language for 3D building models: Octree and b-rep approaches'. Together they form a unique fingerprint.

Cite this