TY - JOUR
T1 - Implementing metric operators of a spatial query language for 3D building models
T2 - Octree and b-rep approaches
AU - Borrmann, Andŕ
AU - Schraufstetter, Stefanie
AU - Rank, Ernst
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - Algorithms
KW - Information models
KW - Spatial analysis
UR - http://www.scopus.com/inward/record.url?scp=58149213711&partnerID=8YFLogxK
U2 - 10.1061/(ASCE)0887-3801(2009)23:1(34)
DO - 10.1061/(ASCE)0887-3801(2009)23:1(34)
M3 - Article
AN - SCOPUS:58149213711
SN - 0887-3801
VL - 23
SP - 34
EP - 46
JO - Journal of Computing in Civil Engineering
JF - Journal of Computing in Civil Engineering
IS - 1
ER -