Collision detection for curved rigid objects in the context of dynamics simulations

Abstract

In this thesis we present methods for detecting collisions between moving rigid bodies whose boundaries are composed of segments of curved surfaces and curves. The surface types that we consider are algebraic surface of degree one and two (quadrics) as well as the torus. The curves that we allow are conic sections and intersection curves between quadrics. We distinguish two different kinds of collision detection. The static collision detection decides whether two stationary objects overlap whereas the dynamic collision detection checks for two moving objects whether they collide during a given time interval. To make these mehtods applicable for interactive dynamics simulations, both the efficiency and the robustness of the algorithms play a decisive role. In order to meet these requirements we reduce all computations to the problem of finding the roots of polynomials in one variable. There are efficient and robust algorithms for this task. Since their running time and numerical stability depend heavily on the degrees of the polynomials, we keep these as low as possible. For instance, we show for two special types of objects that the problem of static collision detection can be reduced to determining the roots of the dynamic behaviour of rigid bodies. In this context we develop an approach to simulate the rolling motion of an object on an arbitrary suface.

In dieser Doktorarbeit stellen wir Verfahren vor, mit deren Hilfe man Kollisionen zwischen sich bewegenden starren Körpern erkennen kann, deren Oberflächen sich aus gekrümmten Flächen- und Kurvenstücken zusammensetzen. Als Flächentypen betrachten wir dabei algebraische Flächen der Ordnungen eins und zwei (Quadriken) sowie den Torus. Als Kurven erlauben wir Kegelschnittkurven und Schnittkurven zwischen Quadriken. Wir unterscheiden zwei verschiedene Arten der Kollisionserkennung. Die statische Kollisionserkennung entscheidet, ob sich zwei stationäre Objekte überlappen, während die dynamische Kollisionserkennung für sich bewegende Objekte feststellt, ob diese während eines gegebenen Zeitintervalls kollidieren. Um die Anwendbarkeit dieser Verfahren bei interaktiven Dynamiksimulationen zu gewährleisten, spielen sowohl die Effizienz als auch die numerische Robustheit der Algorithmen eine entscheidene Rolle. Um dem Rechnung zu tragen, führen wir alle Berechnungen darauf zurück, die Nullstellen von Polynomen in einer Variablen zu bestimmen. Für dieses Problem sind effiziente und robuste Algorithmen bekannt. Da deren Laufzeitverhalten und numerische Stabilität stark von den Graden der betrachteten Polynome abhängt, halten wir diese so gering wie möglich. So zeigen wir zum Beispiel für zwei spezielle Klassen von Objekten, dass das Problem der statistischen Kollisionserkennung darauf zurückgeführt werden kann, die Nullstellen von Polynomen zu berechnen, deren Grade höchstens vier sind. Ein weiterer Aspekt den wir in dieser Arbeit behandeln ist die Simulation der Dynamik starrer Körper. In diesem Zusammenhang leiten wir ein Verfahren her, mit dem der Vorgang des Rollens eines Körpers auf einer beliebigen Oberfläche simuliert werden kann.