Definition und Umsetzung einer Anfragesprache mit räumlich-topologischen Operatoren für die Analyse und Partitionierung von Bauwerksmodellen
Final Report Abstract
Im abgeschlossenen Projekt konnte erfolgreich eine räumliche Anfragesprache für digitale Bauwerksmodelle entwickelt werden. Mit Hilfe dieser Anfragesprache ist es möglich, Bauwerksmodelle hinsichtlich geometrisch-topologischer Zusammenhänge zu analysieren sowie anhand von räumlichen Kriterien zu zerlegen. Diese Funktionalität vereinfacht nicht nur die Mensch-Maschine-Kommunikation, sondern erleichtert auch den Datenaustauch zwischen verschiedenen Programmen. Im ersten Schritt wurde eine räumliche Algebra entwickelt, die die räumlichen Typen Point, Line, Surface und Body sowie die für sie verfügbaren metrischen, direktionalen und topologischen Operatoren umfasst. Für die formale Definition der räumlichen Typen kamen Methoden der Punktmengentheorie und der Punktmengentopologie zum Einsatz, welche die eindeutige Beschreibung des Inneren, des Randes und des Äußeren der jeweiligen Objekttypen ermöglichen. Für die Spezifikation der direktionalen Operatoren wurden zwei neue formale Richtungsmodelle entwickelt, das Halbraum-basierte Modell und das projektionsbasierte Modell. Bei der Definition topologischer Operatoren kam das 9-Intersection Model zum Einsatz, das erfolgreich vom 2D- auf den 3D-Raum übertragen werden konnte. Zur Implementierung der oben genannten metrischen, direktionalen und topologischen Operatoren wurden Algorithmen entwickelt, die auf der hierarchischen, raumpartitionierenden Datenstruktur Oktalbaum als Geometrierepräsentation aufsetzen. Dabei werden die Operanden jeweils in einem separaten Oktalbaum codiert und die resultierenden Bäume im folgenden in Form einer simultanen, rekursiven Breitensuche abgearbeitet. Auf jeder Hierarchieebene werden Oktantenpaare gebildet und diese bestimmten Tests unterworfen, die sich je nach untersuchtem Operator unterscheiden. Das Ergebnis des Tests bestimmt, ob die Rekursion mit positivem oder negativem Ergebnis abgebrochen wird oder eine weitere Verfeinerung notwendig ist. Die maximale Rekursionstiefe wird durch den Nutzer festgelegt, der auf diese Weise zwischen der erforderlichen Genauigkeit und dem benötigten Rechenaufwand abwägen kann. Die entwickelten Algorithmen erlauben eine unscharfe Betrachtung räumlicher Beziehungen. Diese ist von Vorteil, weil digitale Bauwerksmodelle häufig geometrischer Imperfektionen aufweisen. Der entwickelte Oktalbaum-Ansatz arbeitet implizit tolerant gegenüber derartigen Ungenauigkeiten und ermöglicht gleichzeitig ein einheitliches und konsistentes Vorgehen für metrische, direktionale und topologische Operatoren. Gleichzeitig erfolgten erste Entwicklungen alternativer Algorithmen, die nicht auf einer Oktalbaumrepräsentation der Operanden aufbauen, sondern stattdessen die originäre Boundary Representation (BRep) einsetzen. Dabei wurde ein Abstandsalgorithmus entwickelt, der klassische Methoden der Abstandsbestimmung (GJK-Algorithmus) mit hierarchischen Ansätzen zur Verwaltung der Boundary-Facetten (AABB-Baum) kombiniert. Ein zweiter alternativer Abstandsalgorithmus verwendet die aus der linearen Optimierung bekannte Active Set-Methode. Hinsichtlich der Einbettung der räumlichen Operatoren in eine deklarative Anfragesprache wurden zwei konkurrierende Ansätze untersucht. Zum einen wurde die objekt-relationale Anfragesprache SQL:1999 eingesetzt, die eine Erweiterung der Basisdatentypen um nutzerdefinierte, komplexe Datentypen mit Memberfunktionen erlaubt. Entsprechend wurden die räumlichen Typen als komplexe Datentypen definiert und die für sie verfügbaren räumlichen Operatoren als zugehörige Memberfunktionen. Die zuvor beschriebenen Algorithmen zur Auswertung der entsprechenden räumlichen Operatoren wurden mit Hilfe von Stored Procedures umgesetzt, also Prozeduren, die auf Serverseite gespeichert und ausgeführt werden. In einem alternativen Ansatz wurde der Einsatz eines In-Memory-Datenbanksystems geprüft, dessen auf SQL-92 beruhende Anfragesprache keinerlei objekt-relationale Features aufweist, jedoch grundlegende Möglichkeiten zur Erweiterung des Sprachumfang durch nutzerdefinierte Prozeduren bietet. Zwar gehen dadurch die Vorteile des objekt-orientierten Ansatzes wie Typsicherheit und Polymorphie verloren, gleichzeitig wird durch den Verzicht auf die für den untersuchten Anwendungsfall irrelevanten Datenbank-Funktionalitäten wie Persistenz und Netzwerkfähigkeit eine deutlich höhere Performanz erzielt. Die Tragfähigkeit der entwickelten Konzepte und die Funktionstüchtigkeit der entwickelten Algorithmen wurde durch Implementierung eines Software-Prototyps nachgewiesen. Dieser bietet eine interaktive 3D-Visualisierung des zu untersuchenden digitalen Bauwerksmodells, vereinfachte Möglichkeiten zur Formulierung einer Anfrage sowie eine Visualisierung des Anfrageergebnisses. Die Ergebnisse dieses Projekts wurden in einer Vielzahl von Veröffentlichungen dokumentiert, darunter ein Buchkapitel und vier Aufsätze in etablierten Fachzeitschriften. Die am Projekt beteiligten Wissenschaftler erkennen verstärkten Bedarf zur Erforschung einer raum-zeitlichen Anfragesprache für digitale Bauwerksmodelle. Durch die Integration von zeitlichen Operatoren in die im vorliegenden Projekt entwickelte räumliche Anfragesprache würden sich weitreichende Möglichkeiten der Analyse und formalen Prüfung von 4D- Bauwerksmodellen eröffnen. Derartige 4D-Modelle werden durch Kombination von 3D-Bauwerksmodellen mit Ablaufplänen generiert, die händisch oder mittels eine Bauablaufsimulation erzeugt wurden. Die Korrektheit der generierten 4D-Modelle ließe sich hinsichtlich raum-zeitlicher Kriterien mit Hilfe einer raum-zeitlichen Anfragesprache prüfen. Andere Anwendungsgebiete einer raumzeitlichen Anfragesprache liegen im Bereich der Auswertung 4D-Modellen, die z.B. archäologische oder bauhistorische Forschungsergebnisse widerspiegeln. Ebenfalls weiteren Forschungsbedarf sehen die Antragsteller in der Entwicklung von alternativen Algorithmen zur Implementierung von räumlichen Operatoren, die die entwickelten oktalbaumbasierten Algorithmen ersetzen oder ergänzen können. Wünschenswerter Weise würden diese Algorithmen direkt auf der Boundary Representation der Operanden arbeiten. Zwar gehen auf diese Weise die Vorteile der Fuzzifizierung räumlicher Beziehungen verloren, auf der anderen Seite sind jedoch erhebliche Laufzeitgewinne zu erwarten. Erste Schritte in diese Richtung wurden bereits im abgeschlossenen Projekt unternommen.
Publications
- Topological analysis of 3D building models using a spatial query language. Advanced Engineering Informatics 23(4). pp. 370–385
A. Borrmann, E. Rank
- Extended formal specifications of 3D Spatial Data Types. Technical Report. Technische Universität München. Munich, Germany, 2006
A. Borrmann
- Towards a 3D Spatial Query Language for Building Information Models. In: Proc. of the 11th Int. Conf. on Computing in Civil and Building Engineering (ICCCBE-XI). Montreal, Canada. 2006
A. Borrmann, C. van Treeck, E. Rank
- An iterative, octree-based algorithm for distance computation between polyhedra with complex surfaces. In: Proc. of the Int. ASCE Workshop on Computing in Civil Engineering. Pittsburgh, USA. 2007
A. Borrmann, S. Schraufstetter, C. van Treeck and E. Rank
- An octree-based implementation of directional operators in a 3D Spatial Query Language for Building Information Models. In: Proc. of the 24th CIB-W78 Conference on Information Technology in Construction. Maribor, Slovenia. 2007
A. Borrmann, S. Schraufstetter, C. van Treeck and E. Rank
- Computerunterstützung verteilt-kooperativer Bauplanung durch Integration interaktiver Simulationen und räumlicher Datenbanken. Dissertation. Lehrstuhl für Bauinformatik. Technische Universität München. 2007. zgl. Shaker-Verlag, Aachen 2008. ISBN 978-3-8322-7086-5
A. Borrmann
- Konzept und Umsetzung einer räumlichen Anfragesprache für digitale Bauwerksmodelle. In: Tagungsband des Forum 3D - 3D-Technologien an der Technischen Universität München. München, 2007
S. Schraufstetter, A. Borrmann
- Eine räumliche Anfragesprache für dreidimensionale Bauwerksmodelle. In: Tagungsband des 13. Münchner Fortbildungsseminar Geoinformationssysteme. München, 2008
A. Borrmann
- Topological operators in a 3D Spatial Query Language for Building Information Models. In: Proc. of the 12th Int. Conf. on Computing in Civil and Building Engineering (ICCCBE-XII). Beijing, China, 2008
A. Borrmann, E. Rank
- Using Geometrical and Topological Modeling Approaches in Building Information Modeling. In: Proc. of the 7th European Conference on Product and Process Modelling (ECPPM’08). Sophia-Antipolis, France, 2008
N. Paul, A. Borrmann
- Implementing Metric Operators of a Spatial Query Language for 3D Building Models: Octree and B-Rep Approaches. Journal of Computing in Civil Engineering 23 (1), pp. 34–46. 2009
A. Borrmann, S. Schraufstetter, E. Rank
- Nicht-konvexe Abstandsbestimmung und Quadratische Programmierung. Tagungsband des Forum Bauinformatik. Karlsruhe, 2009
N. Paul
- Query Support for BIMs using Semantic and Spatial Conditions. In: Underwood. J. & Isikdag. U. (Eds). Handbook of Research on Building Information Modeling and Construction Informatics: Concepts and Technologies, Information Science Reference. Hershey, PA, USA. 2009. ISBN 978-1-60566-928-1
A. Borrmann, E. Rank
- Spatial constraints in collaborative design processes. In: Proc. of the Int. Conf. on Intelligent Computing in Engineering (ICE’09). Berlin, Germany, 2009
A. Borrmann, J. Hyvärinen, E. Rank
- Specification and implementation of directional operators in a 3D spatial query language for building information models. Advanced Engineering Informatics 23 (1), pp. 32–44. 2009
A. Borrmann, E. Rank
- Using Geometrical and Topological Modeling Approaches in Building Information Modeling. ITCon Vol 14. pp. 705-723. 2009
N. Paul, A. Borrmann
