3D Circle Reconstruction from Ellipses

Keywords: 3D circle reconstruction, traffic sign reconstruction, ellipse fitting

I came to the idea of publishing this software part I have been working on during my Master’s Thesis. During my time at SIMTech, I was working on robotics, 3D reconstruction of workpieces, and path teaching using Augmented Reality (AR).

A part of our project was the task of reconstructing a 3D circle based on its (elliptical) projection on several camera images. Assume you have several 2D ellipses representing the projection of this 3D circle taken from different positions, you want to find the 3D circle that matches the projections as good as possible. Several papers are available for this problem, but some of them either require additional knowledge, such as the circle’s base plane, or are very scientific, and are too complex for a simple engineer to understand them. In the end, I used the method presented in the paper referenced below:

Soheilian, B.; Brédif, M., “Multi-view 3D Circular Target Reconstruction with Uncertainty Analysis”, ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. 2, Issue 3, pp 143-148, 2014

In my opinion, it is a very good paper and their approach is very advanced, but due to the amount of information in this paper it can be a bit difficult to understand for usual engineers or programmers. That was the reason why I decided to publish my implementation of it and try to explain the approach proposed by Soheilian and Brédif a bit more in detail. The major difference between my implementation and the one presented by Soheilian and Brédif is that their approach also optimizes the extrinsic camera parameters and the 2D ellipse data to provide the best results, while my method assumes that the camera’s parameters (extrinsic and intrinsic) are known and perfect.

The projection of a 3D circle on a camera image is an ellipse, so these projections pose the base for the reconstruction approach. In this document, I will not focus on how to detect ellipses on a camera image or how to find the best fitting ellipse, as this part of the algorithm is rather simple. From my experience, a simple Canny edge detector with subsequent contour detection, followed by an ellipse detection and filtering usually works quite good. To fit an elipse into a detected contour on a camera image, I used an improved version of the basic Fitzgibbon et al. algorithm to make it numerically stable. This commonly used algorithm is also described here:

Halí?, R; Flusser, J., “Numerically Stable Direct Least Squares Fitting Of Ellipses”, Institute of Information Theory and Automation, Prague, 1998.

In the subsequent paragraphs, I assume that you have already detected and found the best fitting ellipses that belong to the same 3D circle on different images.

What Do I need to know?

In the following text, I assume that you are already familiar with the following mathematical things. If you’re not, you may consider having a short look at the internet to understand it or you keep reading. Some things are not as complicated as they look like at first glance- after all, its no rocket science!

• Camera pinhole projection model. I assume that you know what the intrinsic and extrinsic parameters are and how their matrices look like.
• Matrix operations, multiplications, inverse, etc.
• 2D ellipse representation. You need to know how to express an ellipse as the solution of a conic equation.
• Quadrics and their duals (you don’t need to have a good understanding of it. I don’t have it either. It is enough to know what a quadric is and to know that a quadric has a dual).
• Eigenvectors and Eigenvalues.

So lets get started!

Algorithm Implementation Details

Unprojecting a circle from several orientations is a highly non-trivial task and requires a skillful approach to mathematically express the relationship between the projections and the original 3D circle, using the lowest number of unknowns possible, while keeping an unconstrained approach. For this document, a simplified version of the algorithm presented in this research paper published by Soheilian and Brédif has been used.

This algorithm encodes all information of the circle in six unknowns, the circle center C and the circle’s normal vector N.

With N and C, the orientation and position of the plane supporting the circle is fully described. The radius of the circle is encoded in the normal vector by defining the normal vector N length to be equal to the radius R. The proposed parameterization is the minimal parameterization of 3D circles and is both unambiguous and unconstrained, so no additional conditions are required to be set up.

The idea of the algorithm is to describe the ellipse and the 3D circle as quadrics. To simplify the calculation effort, both quadrics are transformed to their dual quadric. Taking the conic equation of a 2D ellipse, the quadric for an ellipse can be calculated:

This can be rewritten as follows:

E is a 3×3 symmetric matrix and represents the ellipse as point quadric. With this point-based conic, the dual conic E* of this quadric based on all tangent lines of E can be calculated.

As a conic equation can be scaled without changing its validity, the determinant can be ignored and the adjugate matrix of E can be used to describe the dual conic of E. By additionally adding the ellipse constraint of

 and scaling the conic equation in such a way that

  is fulfilled, the dual quadric E*  can be calculated based on the ellipse parameters as follows:

To describe a circle in 3D space, Soheilian and Brédif propose to start with a quadric representation of a sphere and flatten it over time. Their approach starts with the equation of an origin-centered sphere. Rewriting the sphere equation as a quadric yields:

In the next step, the sphere   

is flattened over time by scaling the z coordinate. At t = 0, the quadric represents the same sphere. For 

we get a disc of radius r at z = 0. The dual quadric of this 3D circle is gained as follows:

Using homogeneous coordinates, this circle can be translated and rotated using a transformation matrix

containing the 3×3 rotation matrix 

and translation vector C. As defined previously, the radius information of the 3D circle is encoded in the length of the normal vector, thus we can write:

Transforming the dual quadric results in a quadric that fully describes a circle in 3D space. In the following formulas, vectors are now treated as a matrix with a single column to omit the vector arrow.

Further simplification yield:

With I₃ being a 3×3 identity matrix. By using the notation for the cross product

Q*(C,N) can be rewritten as follows, where  

denotes the matrix encoding the cross product  

:

Ann ellipse is the projection of a 3D circle using a projection matrix P. Similarly, a dual quadric Q* is imaged as a dual conic E*:

The projection matrix P is the product of the camera’s intrinsic and extrinsic parameters and can be decomposed as

with K being the matrix of intrinsic parameters, R being the 3×3 rotation matrix of the extrinsic parameters and S being the original translation vector. If a 4×4 matrix of extrinsic parameters containing both the rotation and translation is given, S can be calculated by decomposing the transformation matrix into a rotation and translation matrix:

Now, S can be easily calculated by reversing the rotation of T:

With both the extrinsic and intrinsic parameters known, the relationship between the 3D circle and the imaged ellipse can be solved as follows by defining M = KR:

To calculate the row and column values of the dual conic, above equation can be rewritten for each matrix element if the matrix M is row-wise splitted:

i, j  represent the row and column of the matrix, respectively. The dot represents the dot product while the x represents the cross product.

To compare the calculated projection of this circle to the estimated ellipse parameters Eobs* gained from the image contours, Eobs*  must, up to a scalar factor, verify E*. As a conic equation can be scaled without affecting the described ellipse, an additional unknown homogeneous scale has to be calculated. Above equation yields six equations, out of which one has to be used to calculate the unknown scale factor, resulting in five equations. As the used model of the 3D circle has six unknown parameters, this means that at least two ellipsoid projections of the same circle must be known to solve this set of equations.

By scaling the parameters of the observed ellipse so that Eobs*33 = 1, the cost vector for the least-squares optimization can be written as follows:

 vec() represents a vector, containing the five different elements of the matrix E*  or  Eobs*, respectively. A possible arrangement can be:

For each ellipse, five equations can be set up. The system of equations can be solved iteratively using the Gauß-Newton algorithm. Given N projections of the circle, the Jacobi matrix is a 5*Nx6 matrix. Introducing the 3×3 matrices  

F features the following derivatives:

Keeping the order used for vec() defined above; the first five rows of the Jacobi matrix can be set up as follows. Each image of the 3D circle represents five rows in the Jacobi matrix.

The solution vector

can then be calculated in several iteration steps using the well-known Gauß-Newton algorithm. In the end, the algorithms returns the orientation and radius of the 3D circle if a set of ellipses and the corresponding camera parameters (extrinsic and intrinsic) are given.

At the moment, the implementation of the algorithm assumes that the intrinsic parameters of the camera do not change; however, simple adaptions to the algorithm can be made to make it suitable for stereo cameras.

The algorithm was successfully tested using a MATLAB throw-away implementation before it was integrated into the C++ software project.

You can download the MATLAB script for this algorithm here:

http://www.icefire-editions.com/misc/website_data/Circle_Perspective_Projection_Equation_Solver.m

To run this script, you’ll need some helper functions that can be found here:

You can also find these scripts on my GitHub:

https://github.com/Danaozhong/sw.matlab.3d_circle_from_2d_ellipses

Note: I receive a lot of requests, that there is a bug in these scripts and they don’t compile, but unfortuntely, since graduation I no longer possess a valid MATLAB license; and can therefore not fix the code. In case this code helped you and you were able to fix it, I would be very grateful if you would send me a fixed version, or altenatively, just do a Pull Request on my GitHub. Thank you very much!

It took me several days to figure out this algorithm, so fixing the few syntax errors here should be a piece of cake!

3D Triangle Collision Detection

I wrote this over 10 years ago in high school when I wrote my first 3D game. I still need to copy in the graphics, but I hope it is useful for someone!

Facharbeit

im Leistungsfach Mathematik

(fächerübergreifend zur Informatik)

Thema:

„Entwicklung eines 3D-PC-Spiels: MBDAK III“

 Clemens Zangl

Schuljahr 2006/2007

MSS 12

Max-Slevogt-Gymnasium Landau

Inhaltsverzeichnis

1. Einleitung   …………………………………………………………………………………………………………………	3
1.1. Die Geschichte der 3D-Spiele  ……………………………………………………………………………………	3
1.2. Die Idee und Geschichte der MBDAK-Serie ………………………………………………………………..	4
2. Hauptteil  ……………………………………………………………………………………………………………………	5
2.1. Grundlegender Aufbau und technische Planung   ………………………………………………………….	5
2.1.2. Was ist eine 3D-Engine?  ………………………………………………………………………………………..	5
2.2. 3D-Mathematik   ……………………………………………………………………………………………………….	6
2.2.1. Welche Arten von Mathematik benötigen wir für ein 3D-Spiel?  ………………………………….	6
2.2.2. Kollisionsberechnung   ……………………………………………………………………………………………	6
2.2.2.1. Geschichte der Mathematik in PC-Spielen  ……………………………………………………………..	6
2.2.2.2. Kugel-Kollisionen oder Sphere-Collisions  ……………………………………………………………..	7
2.2.2.3. Dreiecks-Kollisionen oder Triangle-Collisions  ……………………………………………………….	8
2.2.3. Dreieck-Transformation  …………………………………………………………………………………………	10
2.2.3.1. Wann müssen Dreiecke transformiert werden?  ……………………………………………………….	10
2.2.3.2. Rotieren, Drehen, Rollen von komplexen Dreiecksmustern  ……………………………………..	10
2.2.3.3. Skalieren von Dreiecken  ………………………………………………………………………………………	11
2.2.3.4. Verschieben von Dreiecken  ………………………………………………………………………………….	12
3. Schluss und weitere Ausblicke  ……………………………………………………………………………………..	12

1. Einleitung

Diese Facharbeit beschäftigt sich mit dem Thema, wie man ein 3D-Computer-Spiel erstellt, angefangen bei der grundlegenden Planung, weiterführend über die in einem solchen Spiel benötigten mathematischen Berechnungen und Algorithmen,  bis hin zu der Ausführung der letztendlichen Programmierung.

Die Schwerpunkte werden dabei auf die Berechnungen von Kollisionen und den Transformationen von Körpern im dreidimensionalen Raum gesetzt. Weitere Aspekte, die die Umsetzung einer möglichst dynamischen Grundlage als Basis für das Spiel enthalten,  lassen sich zwar nicht direkt in ein Schulfach einordnen, sind jedoch für die Entwicklung unumgänglich, weshalb ich diesen ebenfalls einen Bereich gewidmet habe.

Umgesetzt werden diese Themen in der Programmiersprache Delphi 7 unter Zuhilfenahme von DirectX 8 in einem Flugsimulatorspiel mit dem Namen „MBDAK III“, in welchem es zunächst einmal das einfache Prinzip gibt, mit seinem Flugzeug in der virtuellen Welt nicht abzustürzen – das bedeutet, nicht mit einem der vielen Berge oder Hochhäuser zu kollidieren. Das Thema mag vielleicht etwas makaber klingen, schliesslich sind die Ereignisse vom 11. September 2001 noch lange nicht in Vergessenheit geraten und die Idee, ein Flugzeug in ein Hochhaus fliegen zu lassen, macht das Spielprinzip leicht angreifbar – der einfache Grund für diese Wahl ist, dass die Struktur eines Hochhauses aufgrund seiner einfachen Form wesentlich einfacher umzusetzen ist als eine weite, von Bäumen gespickte Naturlandschaft. Weiterhin steht in diesem Projekt die Mathematik und nicht das Spielprinzip im Vordergrund.

Um die grundlegenden Kenntnisse im Bezug auf dreidimensionale Spiele zu erlangen, ist es notwendig, dass wir uns zunächst einmal ein wenig in die Geschichte der „3D-Games“ einlesen:

1.1. Geschichte der 3D-Spiele

Die Anfänge der 3D-Spiele auf PC-Basis in den Jahren 1991/1992 lassen sich eigentlich kaum als 3D-Spiele bezeichnen. Damals waren 3D-Simulationen lediglich auf großen Arcade-Simulationsspielhallenautomaten oder Spielekonsolen wie der Sony Playstation  bekannt, doch in diesen Jahren entstanden die ersten Versuche dreidimensionaler Grafiken auf PC-Basis: Diese ergaben grob pixelige, vom Hauptprozessor generierte Grafiken, welche sich im Schneckentempo über den Bildschirm quälten – aber dennoch staunende Gesichter hervorriefen. Doch die Technik reifte schnell heran, sodass sich aus den sogenannten „Dia-Shows“ nach und nach brauchbar schnelle Simulationen entwickelten: So entstand im Jahre 1993 der „Großvater“ der 3D-Spiele: „Doom“ von id-Software konnte zum ersten Mal in der Geschichte der PCs als 3D-Spiel mit seiner grafischen Aufmachung überzeugen und somit viele Computer-Benutzer auf längere Zeit fesseln. Natürlich waren aufgrund des Rechenanspruchs einer solchen 3D-Simulation die Anforderungen an die damalige Hardware sehr hoch, sodass man „Doom“ nur auf den neusten PCs brauchbar spielen konnte – man benötigte mindestens einen Intel i486DX mit 33 Mhz[1]. Dennoch ließen sich viele Benutzer davon nicht vom Spielen abhalten: Sie übertakteten ihre Rechner bis auf die oberste Leistungsgrenze und erneuerten ihre Hardware, um auf ihnen dieses Spiel spielen zu können, was zu einem gesteigerten Umsatz in der Hardwareindustrie führte. Dadurch lief die Entwicklung nach mehr Rechenleistung wesentlich schneller ab und im Jahr 1996 fand ein weiteres Ereignis statt, ohne das 3D-Spiele niemals den Stellenwert bekommen hätten, den sie heute inne haben: Die Firma 3Dfx entwickelte in San José, Kalifornien, einen 3D-Hardware-Grafikkarte mit dem Namen „Voodoo Graphics“. Es handelte sich hierbei um eine Beschleunigerkarte, welche auf einem separaten Prozessor alle 3D-Berechnungen dem Hauptprozessor abnahm. Die Folgen waren revolutionär: Erstens liefen 3D-Spiele so wesentlich schneller, da der Hauptprozessor entlastet wurde und der Grafikchip solche Berechnungen in atemberaubender Geschwindigkeit erledigen konnte, zweitens sahen die Ergebnisse durch bestimme Bildverbesserungsmethoden auf dem Monitor wesentlich besser aus. Ich verfalle bei diesem Gedanken gerne in Nostalgie, denn auch ich weiß noch, wie ich aus dem Staunen nicht mehr herauskam, als ich die ersten Voodoo-generierten 3D-Simulationen sah. Ein weiterer Vorteil dieser Beschleunigerkarten war das neue, standardisierte, 3D-Interface, zu deutsch der Schnittstelle, die ein Programmierer verwendet, um der Grafikkarte zu „sagen“, dass sie beispielsweise nun einen Würfel anzeigen soll. Dadurch konnte man innerhalb weniger Minuten bereits eine 3D-Simulation auf den Bildschirm bringen, während man früher erst einmal ein Programm schreiben musste, welches die grundlegenden Funktionen zur Erstellung einer 3D-Simulation enthalten musste. Dieses Prinzip hat sich bis heute durchgesetzt: Zu der Firma 3Dfx gesellten sich nVidia, ATI, S3 und Matrox – alle bauten auf der selben Basis und 3D-Schnittstelle auf. Obwohl die Gründerfirma 3Dfx im Jahr 2000 von nVidia aufgekauft worden ist, wurden bis heute viele, viele technische Verbesserungen unternommen, um 3D-Simulationen noch realistischer und noch schneller gestalten zu können. So sind die neusten Grafikchips etwa 100-mal schneller als die Voodoo Graphics.

Für die Entwicklung unseres 3D-Spiels werden wir die Vorzüge dieser Entwicklung nutzen, deshalb habe ich MBDAK III für die oben genannte 3D-Schnittstelle („DirectX“) optimiert.

1.2. Die Idee und Geschichte der MBDAK-Serie

Wenn man die Beschreibung des Spiels aufmerksam gelesen hat, wird man des Öfteren den Namen „MBDAK“ gelesen haben. „MBDAK“ ist eine Buchstabenkombination ohne tiefere Bedeutung und gleichzeitig der Titel meiner bekanntesten Spieleserie. Die Idee besteht darin, dass eine kleine Gruppe Helden die letzte Hoffnung der Menschheit darstellt, um die Welt vor ausserirdischen und bösartigen Wesen zu retten. Zugegeben, dieses Spielprinzip ist nicht sonderlich passend für das Thema einer Facharbeit, aber ich will betonen, dass das Spieleprinzip in dieser Arbeit nicht im Vordergrund steht. Weiterhin handelt es sich hierbei ja um eine Flugsimulation und diese trägt den Namen MBDAK nur aus historischen Gründen.

Entstanden ist MBDAK im Jahr 2001 als eine Comicserie, zu der ich daraufhin ein kleines Werbespiel entwickeln wollte. Letztendlich wurde das Comic zur Werbung für das Spiel, das damals bereits 6000 Zeilen umfasste und in meinem Freundeskreis bald zu einem der am liebsten gespielten Spiele wurde. Die Fortsetzung von MBDAK entwickelte ich im Frühjahr 2005 im Rahmen eines Wettbewerbes der Fachhochschule Karlsruhe: So entstand das 18.000-Zeilen-Spiel MBDAK II, welches viele Feautures, unter anderem auch Netzwerkspielmöglichkeit bieten konnte – tatsächlich gewann das Spiel in dem Wettbewerb Informatik auch einen kleinen Preis.

Nun wage ich im Rahmen dieser Facharbeit mein erstes 3D-Spiel – das Spielprinzip wird hierbei noch in vielen Richtungen offen gelassen.

2. Hauptteil

2.1. Grundlegender Aufbau und technische Planung

Ein Spiel dieser Ausmaße benötigt eine vorausgehende, detaillierte und gut überlegte Planung. Dazu müssen wir uns zunächst einmal überlegen, welche Features wir bieten wollen. In unserem Fall sieht die Liste so aus:

• Einzelspielerspielmöglichkeit
• Mehrspielermöglichkeit, über das Netzwerk oder Internet
• Ein Startmenü
• Ein Umgebungseditor

Anhand dieser Optionen können wir bereits eine grundlegende Modul-Basis erstellen. Da wir dem Spieler die  Möglichkeit geben wollen, eigene Welten zu erschaffen, führt kein Weg an einem dynamischen Levelsystem vorbei: Das bedeutet, dass wir ein spezielles Scripting-System erstellen, mit dem wir unserem Hauptprogramm mitteilen, welche Karte wir jetzt spielen wollen. Das Programm analysiert das Script und baut daraus die virtuelle Welt zusammen. Die Objekte dieser Simulationen sind dabei aus vielen, vielen Dreiecken aufgebaut, da man aus diesen nahezu alle Objekte realitätsnah nachbilden kann[2] – diese muss das Scriptprogramm auslesen können und für die Simulation oder andere Berechnungen, wie beispielsweise die Kollisionsberechnung, nutzen können. Weiterhin können wir unser Spiel bereits auf die Möglichkeit hin programmieren, mehrere Flugzeuge gleichzeitig anzuzeigen, da wir ja auch eine Mehrspielermöglichkeit über das Netzwerk bieten wollen – je nachdem, wie viele Spieler sich gerade in einer Welt bewegen, werden unterschiedlich viele Flugzeuge angezeigt.

Das oben genannte Scriptsystem muss so flexibel sein, dass wir die 3D-Welt grundlegend verändern können, ohne unser Programm neu zu erstellen oder zu kompilieren. Dazu müssen wir uns zunächst einmal dem Prinzip einer 3D-Engine zuwenden:

2.1.2. Was ist eine 3D-Engine?

Vielerorts hört man heutzutage auf der Spieler-Szene den Begriff 3D-Engine oder dessen Kurzform Engine: Beispielsweise liest man des öfteren in PC-Zeitschriften oder Internet-Foren von neuen Spielen: „Dieses [hier angebotene] Spiel basiert auf der Doom3 Engine“. Doch was genau ist denn jetzt eigentlich eine solche 3D-Engine?

Übersetzt bedeutet dieses Wort so viel wie ein Motor für dreidimensionale Ansprüche. Ein Motor wird normalerweise dazu genutzt, um Dinge anzutreiben, analog dazu muss in der Computerspielwelt eine 3D-Engine eine virtuelle 3D-Simulation betreiben. Üblicherweise muss diese dabei möglichst flexibel sein, um sie noch für spätere Spielegenerationen oder Erweiterungen (auch bekannt als Add-Ons) nutzen zu können, ohne den „Motor“ selber nachzubearbeiten. Das bedeutet, dass eine Engine in der  Lage sein muss, ein komplett umgeändertes Spieldesign zu verstehen – angefangen bei dem Namen, über die 3D-Modelle bis hin zu den Spielzielen. Es ist selbsterklärend, dass ein Programm selten so flexibel sein kann, um allen Entwicklern als Basis für ein neues Computerspiel gerecht zu werden – deshalb tragen die 3D-Engines ihr Spieleprinzip bereits mit: So gibt es verschiedene „3D-Motoren“ für beispielsweise Strategiespiele, Rollenspiele, Ego-Shooter oder Simulationsspiele.  Unsere 3D-Engine wird demnach auf eine Flugsimuation hin optimiert.

2.2. 3D-Mathematik

2.2.1. Welche Arten von Mathematik benötigen wir für ein 3D-Spiel?

Die wichtigste Berechnung, welche wir in einem 3D-Spiel benötigen, ist eine Kollisionsberechnung zweier Objekte im dreidimensionalen Raum. Trotz der mittlerweile sehr schnellen PC-Prozessoren spielt die Effizienz eines solchen Algorithmus eine große Rolle: So ist es bei einer Kollisionsberechnung auch heutzutage immer noch unmöglich, jedes Dreieck[3] einzeln auf Kollision zu prüfen – bei dieser Rechenlast würde jeder Rechner überfordert werden. Deshalb teilt man den Kollisionsalgorithmus in zwei Bereiche auf: Zunächst wird jedes größere Objekt, beispielsweise ein Haus oder ein Flugzeug, von einer Kugel überzogen, welche man dann zunächst einmal untereinander auf Kollision überprüft. Wenn sich zwei solcher „Spheres“ schneiden, überprüft man jedes Dreieck der in den Kugeln eingeschlossenen Objekte auf Kollision – somit lässt sich der Rechenaufwand so weit reduzieren, dass eine solche Berechnung in Echtzeit durchgeführt werden kann. Ein weitere Technik, die sich zum Reduzieren des Rechenaufwands durchgesetzt hat, ist das Verwenden stark vereinfachter 3D-Modelle für die Kollisionsberechnung, während man gleichzeitig komplexe Figuren durch die Grafikkarte anzeigen lässt. Zur Umsetzung benötigen wir zunächst einmal eine Funktion, mit der es möglich  ist, die Kollision zweier Kugeln festzustellen als auch ein Algorithmus, mit welchem sich die Kollision zwischen zwei Dreiecken bestimmen lässt. Weitere Bereiche, in welchen die Mathematik eine größere Rolle spielt, ist die Transformation, also die Verschiebung, Rotation und Skalierung von 3D-Modellen. So ist es beispielsweise notwendig, ständig die Koordinaten sich bewegender Objekte neu zu berechnen, um diese anschliessend für eine Kollisionsberechnung oder eine Schattenberechnung nutzen zu können.

2.2.2. 3D-Kollisionsberechnungen

2.2.2.1. Geschichte der Mathematik in 3D-Spielen

Ein Computer ist ohne Mathematik nicht vorstellbar – im Grunde tut er ja auch nichts anderes, als jede Sekunde Millionen von mathematischen Berechnungen zu erledigen. Es steckt demzufolge viel Leistung in solchen Prozessoren – so viel, dass sie von einem „normalen“, durchschnittlichen Programm gar nicht erst vollständig in Anspruch genommen wird. Deshalb sind Computerspiele nahezu die einzigen Programme, welche die Leistung eines Privat-Rechners bis an die Grenzen belasten. Analog mit der Entwicklung der  Prozessoren entwickelte sich auch die Mathematik in PC-Spielen.

So waren die ersten PC-Spiele reine zweidimensionale Spiele, weshalb zunächst auch nur zweidimensionale Kollisionen berechnet werden mussten – diese wird nahezu immer vereinfacht auf Basis zweier Rechtecke geprüft. Jedes dieser Rechtecke enthält dabei ein Spielobjekt, wie beispielsweise eine Spielfigur oder eine Wand. Im Falle einer solchen Kollision müssen daher folgende Bedingungen erfüllt sein[4]:

• Der rechte Rand des ersten Rechtecks muss sich weiter rechts als der linke Rand des zweiten Rechtecks befinden.
• Der linke Rand des ersten Rechtecks muss sich weiter links als der rechte Rand des zweiten Rechtecks befinden.
• Der untere Rand des ersten Rechtecks muss sich weiter unten als der obere Rand des zweiten Rechtecks befinden.
• Der obere Rand des ersten Rechtecks muss sich weiter oben als der untere Rand des zweiten Rechtecks befinden.

Im Programmcode (in diesem Fall Delphi 7) wird eine solche Abfrage folgendermassen umgesetzt:

If (X1 + Width1 >= X2) and (X1 <= X2 + Width2) and (Y1 + Height1 >= Y2) and (Y1 <= Y2 + Height2) then Result := True else Result := False;

X1 entspricht hierbei der linken X-Koordinate des ersten Rechtecks, X2 der linken X-Koordinate des zweiten Rechtecks. Analog dazu verhält es sich mit den Y1/Y2-Werten und der Y-Koordinate. Width und Height gibt die Breite und Höhe des jeweiligen Rechrecks an.

Interessant war auch die Kollisionsberechnung in den ersten 3D-Spielen: Hierbei hatte man ganz einfach fest definiert, dass die Wände alle senkrecht und in einem 90°-Winkel zueinander stehen müssen – dadurch konnte man eine dreidimensionales Kollisionsproblem auf eine zweidimensionale Ebene reduzieren – so ließ sich das Problem mit dem oben genannten Rechteckskollisionsverfahren lösen. Solche Spiele nannte man auch 2,5-D-Spiele, da es sich ja eigentlich nicht um richtige 3D-Spiele handelte – „Doom“  war beispielsweise ein solches 2,5-D-Spiel.

Die Entwicklung ließ jedoch nicht lange auf sich warten und wie die Rechenleistung der Prozessoren größer und größer wurde, wurden die Kollisionsrechtecke kleiner und die Welten komplexer, bis schliesslich die ersten Spiele eine wahre 3D-Kollisionsberechnung nutzten, unter anderem auch das legendäre „Tomb Raider“, erschienen im Jahr 1996 von EIDOS. Dieser Algorithmus, welcher im Grunde auf zwei Berechnungen basiert, so zum einen eine Kugel-Kollision (auch „Sphere-Collisions“ genannt) und zum anderen eine Dreieckskollision („Triangle-Collisions“), hat sich bis heute kaum geändert und ist nach wie vor die wohl wichtigste Berechnung in Computerspielen.

2.2.2.2. Kugel-Kollisionen oder Sphere-Collisions

Die Berechnung einer Sphere-Kollision ist denkbar einfach: Wir erstellen zunächst einmal einen Vektor von Mittelpunkt der einen Kugel zu dem der anderen und berechnen dessen Länge, von der wir die Radien der beiden Kugeln abziehen. Ist das Ergebnis negativ, findet eine Kollision statt[5]. In der Theorie sieht diese Berechnung so aus:

Berechnung der Vektorlänge:

Die drei a-Werte entsprechen dabei den X/Y/Z-Werten des Vektors.

Nun ist es nur noch notwendig, beide Radien von dieser Länge abzuziehen.

Die entsprechende virtuelle Umsetzung dieser Berechnung ist in der Funktion „SphereCollision“ des Quelltextes im Anhang zu finden.

 2.2.2.3. Dreiecks-Kollisionen oder Triangle-Collisions

Eins vorweg: Die Idee für diese Dreiecks-Kollisionsberechnung entstammt der Webseite „Scherfgen-Software[6]“. Ich möchte allerdings anmerken, dass der auf dieser Seite angeführte Algorithmus fehlerhaft ist und somit nicht funktionabel ist, abgesehen davon ist er in C++ programmiert. Ich habe deshalb lediglich die theoretischen Berechnungen korrigiert und diese dann vollständig neu programmiert. Im Grunde ist bei dieser Berechnung die Schnittgerade der beiden Dreiecke gesucht – gegeben sind für diese Funktion pro Dreieck je drei Koordinatenpunkte.

Im Grunde wird dieser Algorithmus nach folgenden Schema ablaufen:

• Überprüfung, ob beide Dreiecke auf der Schnittgerade ihrer Ebenen liegen
• Bestimmung der Schnittpunkte der Dreiecke auf der Schnittgeraden
• Überprüfung der Abschnitte der Schnittgeraden

Auch an diesen Stellen müssen wir möglichst effizient rechnen – deshalb überprüft man vor der Bestimmung der Schnittgeraden, ob die drei Punkte des Dreiecks allesamt auf einer Seite der Ebene des anderen Dreiecks liegen. Wenn dies der Fall ist, schneiden sich die Dreiecke nicht – wir können die Berechnung an dieser Stelle also einfach abbrechen[7].

Die Ebenendarstellung wird in der Normalendarstellung erfolgen, das heißt, wir benötigen pro Ebene eine Lagekonstante ( d ) un den orthogonalen Vektor ().

Den orthogonalen Vektor berechnet sich aus den Richtungsvektoren von einem Dreieckpunkt zu den beiden anderen () mithilfe das Kreuzprodukts.

Die Lagekonstante d berechnen wir folgendermassen:

Der Punkt x entspricht hierbei einem beliebigen Punkt der Dreiecksebene.

Anschliessend berechnen wir den Abstand jedes Punktes des einen Dreiecks von der Ebene des anderen, dies ist mit der folgenden Formel möglich:

Die drei n-Variablen entsprechen hierbei den einzelnen Parametern des orthogonalen Ebenenvektors, x entspricht einem Punkt des zu überprüfenden Dreiecks, während d die Lagekonstante der Ebene ist.

Wenn für ein Dreieck alle Punkte dasselbe Vorzeichen haben, können wir die Berechnung getrost abbrechen – es liegt somit unter keinem Fall eine Kollision vor. Zur Einsparung von Rechenzeit verzichtet man üblicherweise auf den Nenner der Abstandsformel, da dieser keinen Einfluss auf das Vorzeichen hat und der Abstand selber ohne große Bedeutung ist.

Wenn die Überprüfung auf beiden Dreiecken negativ ausfällt, schneidet die Ebenenschnittgerade auf jeden Fall auch  beide Dreiecke. Dabei ist allerdings noch zu beachten, dass die Dreiecke immer noch in einem gewissen Abstand voneinander stehen können und sich somit nicht schneiden würden[8]. Deshalb ist es zunächst notwendig, die Schnittgerade zu bestimmen, um dann darauf den Start- und den Endpunkt jedes Dreiecks einzutragen und diese Werte miteinander zu vergleichen.

Die Berechnung der Schnittgeraden basiert darauf, dass wir die zunächst einmal den Dreieckspunkt suchen, welcher alleine auf einer Dreiecksseite ist (also dessen Abstandsvorzeichen von den der beiden anderen Punkte abweicht). Von diesem Punkt ziehen wir anschliessend eine Gerade zu den beiden anderen Punkten – somit ist sichergestellt, dass diese Geraden die Ebene des anderen Dreiecks schneiden. Den Schnittpunkt berechnen wir, indem wir diese Geraden in die Ebenengleichung einsetzen[9]:

p entspricht hierbei dem Aufpunkt der Gerade, a der Multiplikator des Geradenrichtungsvektors x, während der orthogonale Ebenenvektor und d die Lagekonstante der Ebene ist.

Aufgelöst nach a ergibt sich:

Mithilfe dieses Wertes lässt sich der Schnittpunkt der Geraden mit der Ebene finden. Wir wiederholen dieses Verfahren für alle Punkte der Dreiecke und erhalten somit vier Punkte, von denen zwei jeweils einen Dreiecksanfang und -ende auf der Schnittgerade beschreiben. Für die Schnittgerade ist es daher sinnvoll, einen dieser Punkte als Aufpunkt zu nehmen, während wir aus den anderen den Richtungsvektor bestimmen. Um nun die Abstände unter den einzelnen Punkten zu bestimmen, ist es notwendig, die dreidimensionale Gerade auf eine Dimension zu reduzieren, das heißt wir beachten nur eine der drei Koordinatenachsen, um die Schnittproblematik zu lösen – das Ergebnis ist dabei immer noch korrekt, während wir die Berechnung gleichzeitig wesentlich leichter durchführen können. Dazu suchen wir uns zunächst den größten Wert aus den drei Koordinatenpunkten des Richtungsvektor, und reduzieren die Abstandsberechnung auf diese Dimension.

Zur einfacheren Handhabung der daraus resultierenden Werte ist es nun wichtig, die einzelnen Punkte des Dreiecks nach ihrer Größe zu sortieren – damit wären eventuelle Probleme beseitigt, falls ein Dreieck um 180° gedreht sein sollte.

Anhand dieser Punkte können folgende Kollisionsereignisse auftreten[10]:

• Der Anfangspunkt von Dreieck 2 ist kleiner als der Anfangspunkt von Dreieck 1, während gleichzeitig der Endpunkt von Dreieck 2 größer ist als der Endpunkt von Dreieck 1 (=Dreieck1 liegt in Dreieck 2)
• Der Anfangspunkt von Dreieck 2 ist kleiner als der Endpunkt von Dreieck 1, ist allerdings größer als der Anfangspunkt von Dreieck 1 (die linke Ecke von Dreieck 2 befindet sich in Dreieck 1)
• Der Endpunkt von Dreieck 2 ist größer als der Anfangspunkt von Dreieck 1, ist allerdings kleiner als der Endpunkt von Dreick 1 (die rechte Ecke von Dreieck 2 befindet sich in Dreieck 1)

In allen anderen Fällten tritt keine Kollision auf.

Mit dieser Dreiecks-Kollisionsfunktion ist die Kollisionsüberprüfung abgeschlossen. Sie finden die Dreiecksüberprüfungsfunktion im Quelltext im Anhang unter dem Namen „BerechneKollision()“.

 2.2.3. Dreiecks-Transformation

2.2.3.1. Wann müssen Dreiecke transformiert werden?

Der zweite Hauptteil dieser Facharbeit beschäftigt sich mit der Berechnung von Dreieck-Transformationen. Diese sind von zentraler Bedeutung bei der Entwicklung von PC-Spielen, da alle virtuellen Modelle, beispielsweise das eines Flugzeuges, erst an die entsprechende Position transformiert werden müssen. 3D-Welten bestehen im Grunde aus mehreren einzelnen Objekten mit einem eigenen Nullpunkt, welche dann an ihre Position im Hauptkoordinatensystem transferiert werden müssen. Zwar werden die von der Grafikkarte ausgegebenen Objekte bereits von der 3D-Schnittstelle berechnet, doch lassen sich aufgrund des besonderen Formats die dadurch errechneten Werte nicht verwenden – obwohl diese sehr wichtig wären für beispielsweise die Kollisionsberechnung oder eine Schattenberechnung. Es führt also kein Weg daran vorbei, diese Funktionen selber zu schreiben.

Auch diese Funktion muss effizient und schnell rechnen, da diese für jedes anzuzeigende Objekt in jedem neu erzeugtem Bild neu aufgerufen werden muss – es entsteht also eine große Rechenlast für die CPU (dem Hauptprozessor). Deshalb berechnet man nur die Objekte neu, welche sich bewegt haben können und verwendet bei statischen Objekten wie beispielsweise Bäumen oder Häuser die vorherigen Werte.

Eine Transformation kann aus folgenden Elementen bestehen:

• Skalierung der Objekte
• Rotation der Objekte um die X/Y/Z-Achse (Rotieren, Drehen und Rollen)
• Verschieben der Objekte auf bestimme Koordinaten

Da die Rotation und die Skalierung eines Objektes einen festgelegten Nullpunkt benötigen, ist es notwendig, diese beiden Transformationen vor der Verschiebung durchzuführen.

2.2.3.2. Rotieren, Drehen und Rollen von komplexen Dreiecksmustern

Wir werden uns zunächst dem Rotieren, Drehen und Rollen von Objekten zuwenden. Im Grunde handelt es sich dabei um Rotationen um die X-,Y- oder Z-Achse. Um dies nun zu ermöglichen, benötigen wir zunächst einmal die Punkte der einzelnen Dreiecke. Die Anzahl der Punkte würde demnach die Anzahl der Dreiecke multipliziert mit 3 ergeben. Nun gibt es allerdings bereits Methoden, um wertvolle Speicherbandbreite zu sparen und somit den Rechenaufwand zu senken. Deshalb ist es üblich, die Informationen über die Dreiecke und die Koordinatenpunkte getrennt zu speichern: So werden die Koordinaten in einen sogenannten Index-Buffer geschrieben, wobei der Vertex-Buffer pro Dreieck je drei Verweise auf Elemente in dem Index-Buffer beherbergen. Der Vorteil dieser Methode liegt auf der Hand: Punkte mit identischen Koordinaten müssen nicht zusätzlich berechnet werden – man spart demnach viel Rechenleistung. Für unsere Algorithmen werden wir also nur den Index-Buffer durchlaufen und dort alle Punkte bearbeiten. In MBDAK III habe ich mir der Einfachheit halber die Verwendung des Index- und Vertex-Buffers gespart, dennoch werde ich im Rahmen dieser Facharbeit die Transformationsalgorithmen für diese Technik anpassen.

Auch hier müssen wir auf die Reihenfolge der Rotationen achten: Da die Objekte festgesetzte Vorder- und Rückseiten besitzen (normalerweise verläuft so ein Objekt auf der X-Achse von vorne nach hinten, während die Z-Achse die Breite eines Objektes beschreibt), müssen wir die Rotation um die Y-Achse zuletzt durchführen, da sonst die Informationen über die Vorder- und Rückseite verloren gehen würden.

Deshalb fangen wir mit der Rotation um die Z-Achse an (der sogenannten „Pitch“, der Steigung):

Die Z-Werte der Punkte bleiben hierbei immer identisch, deshalb müssen wir nur die X- und Y-Werte bearbeiten. Die Berechnung verläuft folgendermassen ab:

a entspricht hierbei dem Steigungswinkel, während x und y den X- und Y-Wert des Punktes beinhalten. Weil bei einem Winkel von 0° der Cosinus = 1 ist, behält der Punkt so seine ursprünglichen Koordinaten, während bei ein Winkel von 90° lediglich der Sinus einen Einfluss hat – die Werte werden bei diesem Winkel sozusagen vertauscht[11].

Nach diesem Prinzip verlaufen auch alle anderen Rotationen – es ist lediglich wichtig, die Reihenfolge zu beachten: Zuerst die Rotation um die X- und Z-Achse und zuletzt die Rotation über die Y-Achse.

Im Programmquelltext umgesetzt sieht diese Berechnungen wie folgt aus:

If Pitch <> 0 then begin

      TempVertexA.X := TempVertex.X * cos(Pitch)+TempVertex.Y * sin(Pitch);

      TempVertexA.Y := TempVertex.Y * cos(Pitch)-TempVertex.X * sin(Pitch);

end;

2.2.3.3. Skalieren von Dreiecken

Die Skalierungsfunktion ist ebenfalls sehr einfach. Auch hier gehen wir jeden Punkt des Index-Buffers durch und multiplizieren einfach die Länge des Vektors zu diesem Punkt mit dem Skalierungsfaktor. Vereinfacht ergibt sich so:

Mit diesem Algorithmus wäre auch unsere Skalierungsfunktion abgeschlossen.

2.2.3.4. Verschieben von Dreiecken

Das eigentliche Verschieben von Dreiecken ist die Transformationsoperation, welche zuletzt durchgeführt wird. Gegeben haben die die Liste des Index-Buffers unseres 3D-Modelles und den Transformationspunkt in dem Hauptkoordinatensystem. Auch hier gehen wir jeden Punkt des Objekt-Index-Buffers durch, addieren zu diesen Punkten den Transformationspunkt und kopieren diese veränderte Index-Buffer-Liste in den Index-Buffer des Hauptkoordinatensystems. Anschliessend müssen wir die Dreiecke selber, also den Vertex-Buffer kopieren. Dazu müssen wir die Verweise auf den Index-Buffer ändern, da dieser sich ja jetzt geändert hat.

P entspricht hierbei irgendeinem Punkt aus dem Index-Buffer, während X dem Transformationspunkt in den Hauptkoordinatensystem entspricht.

3. Schluss und weitere Ausblicke

Damit hätten wir die Themen dieser Facharbeit abgeschlossen. Leider konnte ich aufgrund der geballten Komplexität des Hauptthemas nur einen kleinen Einblick in die große Faszination der Spieleentwicklung bieten, doch hoffe ich, dass ich Ihnen einen groben Überblick vermitteln konnte. Für mich persönlich steht die Entwicklung von MBDAK III noch ganz am Anfang: Ich werde noch viele Features integrieren, so sollen sich später noch fremde, computergesteuerte Raumschiffe vollig problemlos in dem „virtual space“ bewegen können, ein Netzwerkspiel möglich werden und allgemein noch viele, viele Eigenschaften an dem äusseren Erscheinungsbild verbessert werden – dazu gehören eine Schattenberechnung, ein funktionstüchtiges Menü  und vielleicht noch Triebwerksgeräusche und -flammen. Wie sein Vorgänger MBDAK II will ich dieses MBDAK III vollkommen „open source“ machen, damit andere Menschen sich meinen Quelltext als Grundlage nehmen können und sich daran weiterbilden können.

Als ich vor drei Jahren bereits versuchen wollte, ein 3D-Spiel zu entwickeln, fehlten mir noch die nötigen Kenntnisse für eine Kollisionsberechnung – demzufolge ist dieses Projekt damals im Sand verlaufen. So wie mir damals geht es heute vielen Nachwuchsprogrammieren mit Zielen: Das Problem mit der Kollisionsberechnung ist bekannt und es lassen sich kaum und noch weniger leicht verständliche Lösungen für diese Problematik im Internet finden. Ich habe deshalb vor, diese Facharbeit im Internet zu veröffentlichen und sie so jedermann zugänglich zu machen, um heutigen Jungprogrammieren bei den Problemen zu helfen, welche  mir damals mein Projekt im Sand verlaufen lassen haben. 

Deshalb widme ich diese Arbeit allen jungen Programmieren, welche, noch bevor sie in der Schule etwas von Logarithmen gehört haben, sich bereits mit der Vektorrechnung im 3D-Raum beschäftigen und somit ihrer Zeit wohl weit voraus sind.

---

[1]          zum Vergleich: heutige Prozessoren arbeiten wesentlich effizienter und laufen auf knappen 4000 Mhz

[2]    Siehe Anhang, Abbildung 2

[3]    Wir erinnern uns: Alle virtuellen 3D-Objekte sind aus Dreiecken zusammengebaut. Siehe Anhang, Abbildung 2

[4]    Siehe Anhang, Abbildung 1

[5]    Siehe Anhang, Abbildung 3

[6]    Siehe http://www.scherfgen-software.net/index.php?action=tutorials&topic=collision_3

[7]    Siehe Anhang, Abbildung 4

[8]    Siehe Anhang, Abbildung 5 und 6

[9]    Siehe Anhang, Abbildung 7

[10]  Siehe Anhang, Abbildung 8 bis 12

[11]  Siehe Anhang, Abbildung 13