Dynamic distance analysis : new geometric data structures and algorithms for the real-time calculation of tolerance violating regions in the digital mockup process

In vielen Industriezweigen, zum Beispiel in der Automobilindustrie, werden Digitale Versuchsmodelle (Digital MockUps) eingesetzt, um die Konstruktion und die Funktion eines Produkts am virtuellen Prototypen zu überprüfen. Ein Anwendungsfall ist dabei die Überprüfung von Sicherheitsabständen einzelner Bauteile, die sogenannte Abstandsanalyse. Ingenieure ermitteln dabei für bestimmte Bauteile, ob diese in ihrer Ruhelage sowie während einer Bewegung einen vorgegeben Sicherheitsabstand zu den umgebenden Bauteilen einhalten. Unterschreiten Bauteile den Sicherheitsabstand, so muss deren Form oder Lage verändert werden. Dazu ist es wichtig, die Bereiche der Bauteile, welche den Sicherhabstand verletzen, genau zu kennen. rnrnIn dieser Arbeit präsentieren wir eine Lösung zur Echtzeitberechnung aller den Sicherheitsabstand unterschreitenden Bereiche zwischen zwei geometrischen Objekten. Die Objekte sind dabei jeweils als Menge von Primitiven (z.B. Dreiecken) gegeben. Für jeden Zeitpunkt, in dem eine Transformation auf eines der Objekte angewendet wird, berechnen wir die Menge aller den Sicherheitsabstand unterschreitenden Primitive und bezeichnen diese als die Menge aller toleranzverletzenden Primitive. Wir präsentieren in dieser Arbeit eine ganzheitliche Lösung, welche sich in die folgenden drei großen Themengebiete unterteilen lässt.rnrnIm ersten Teil dieser Arbeit untersuchen wir Algorithmen, die für zwei Dreiecke überprüfen, ob diese toleranzverletzend sind. Hierfür präsentieren wir verschiedene Ansätze für Dreiecks-Dreiecks Toleranztests und zeigen, dass spezielle Toleranztests deutlich performanter sind als bisher verwendete Abstandsberechnungen. Im Fokus unserer Arbeit steht dabei die Entwicklung eines neuartigen Toleranztests, welcher im Dualraum arbeitet. In all unseren Benchmarks zur Berechnung aller toleranzverletzenden Primitive beweist sich unser Ansatz im dualen Raum immer als der Performanteste.rnrnDer zweite Teil dieser Arbeit befasst sich mit Datenstrukturen und Algorithmen zur Echtzeitberechnung aller toleranzverletzenden Primitive zwischen zwei geometrischen Objekten. Wir entwickeln eine kombinierte Datenstruktur, die sich aus einer flachen hierarchischen Datenstruktur und mehreren Uniform Grids zusammensetzt. Um effiziente Laufzeiten zu gewährleisten ist es vor allem wichtig, den geforderten Sicherheitsabstand sinnvoll im Design der Datenstrukturen und der Anfragealgorithmen zu beachten. Wir präsentieren hierzu Lösungen, die die Menge der zu testenden Paare von Primitiven schnell bestimmen. Darüber hinaus entwickeln wir Strategien, wie Primitive als toleranzverletzend erkannt werden können, ohne einen aufwändigen Primitiv-Primitiv Toleranztest zu berechnen. In unseren Benchmarks zeigen wir, dass wir mit unseren Lösungen in der Lage sind, in Echtzeit alle toleranzverletzenden Primitive zwischen zwei komplexen geometrischen Objekten, bestehend aus jeweils vielen hunderttausend Primitiven, zu berechnen. rnrnIm dritten Teil präsentieren wir eine neuartige, speicheroptimierte Datenstruktur zur Verwaltung der Zellinhalte der zuvor verwendeten Uniform Grids. Wir bezeichnen diese Datenstruktur als Shrubs. Bisherige Ansätze zur Speicheroptimierung von Uniform Grids beziehen sich vor allem auf Hashing Methoden. Diese reduzieren aber nicht den Speicherverbrauch der Zellinhalte. In unserem Anwendungsfall haben benachbarte Zellen oft ähnliche Inhalte. Unser Ansatz ist in der Lage, den Speicherbedarf der Zellinhalte eines Uniform Grids, basierend auf den redundanten Zellinhalten, verlustlos auf ein fünftel der bisherigen Größe zu komprimieren und zur Laufzeit zu dekomprimieren.rnrnAbschießend zeigen wir, wie unsere Lösung zur Berechnung aller toleranzverletzenden Primitive Anwendung in der Praxis finden kann. Neben der reinen Abstandsanalyse zeigen wir Anwendungen für verschiedene Problemstellungen der Pfadplanung.In many branches of industry, for example in the automobile industry, digital mockups are used to inspect the construction and the functionality of a product by using virtual prototypes. One application case is the inspection of safety distances between components. This is called the distance analysis. Engineers detect whether the safety distance between a component and its environment is kept in its resting position and during motion. In case the safety distance isrnviolated, the geometry of the components have to be reengineered or the components have to be placed to another position. Knowing the regions of the components that violate the safety distance is important for this task. rnrnIn this work we present a real-time solution to calculate the regions between two geometric objects, which violate the safety distance. The objects are given as a set of primitives (e.g. triangles). At any time we calculate the set of all primitives that violate the safety distance for a given transformation. This set is called the set of all tolerance violating primitives. We present in this work a holistic solution which is divided into the following three big topics.rnrnIn the first part of this work we consider algorithms to test two triangles on tolerance violation. We present different approaches of triangle-triangle tolerance tests. Thereby we show that triangle-triangle tolerance tests achieve a significantly better performance than previously used distance calculations. The focus of our work is a novel tolerance test that works in dual space. Our novel approach proves to be the most efficient approach in all our benchmarks to calculate all tolerance violating triangles.rnrnThe second part of this work is focused on data structures and algorithms to calculate all tolerance violating primitives between two geometric objects in real-time. We develop a new data structure that combines a flat hierarchical part and some uniform grids. In order to ensure high performance, it is important to consider the required safety distance carefully in both, the design of the data structure and the design of the query algorithms. Therefore we present solutions that quickly obtain the pairs of primitives that have to be tested. Moreover, we develop strategies to detect primitives as tolerance violating without even calculating the costly primitive-primitive tolerance test. In our benchmarks we use complex geometric objects consisting of many hundreds of thousands primitives. We show with these benchmarks, thatrnour solution is able to calculate all tolerance violating primitives in real-time.rnrnIn the third part we present a novel memory optimized data structure that maintains the cell contents of the uniform grids used before. We call this data structure shrubs. Previous approaches to reduce the memory consumption of uniform grids are related to hashing methods. But hashing methods do not reduce the memory consumption of the cell contents. In our application case the cell content of neighboring cells is often similar. Based on this, our approachrnreduces the memory consumption of the cell contents of a uniform grid. It is able to compress the memory lossless until one fifth of its original size and to decompress it at runtime.rnrnFinally we show how our solution to calculate all tolerance violating primitives finds application in practice. Beside the pure distance analysis, we show that our solution is applied to different problems in the field of motion planning