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 woring 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 projection on several camera images. Assuming I have several 2D ellipses representing the projection of this 3D circle taken from different positions, I 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, requiring a lot of time to understand it. The method I present on this page is based on the following paper:
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. The algorithm I’ve used to find the
best fitting ellipse on a camera image is presented in this research
paper. The algorithm is basically an improved version of the Fitzgibbon
et al. method to make it numerically stable.
Halí?, R; Flusser, J., “Numerically Stable
Direct Least Squares Fitting Of Ellipses”, Institute of Information
Theory and Automation, Prague, 1998.
I assume that you 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. Somethings things are not as complicated as they first look
like – 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 with
the lowest number of unknowns as 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
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 length to be equal to the radius.
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 I3 being a 3×3 identity matrix. By using the notation for the cross product
Q* 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 gained from the image contours, E* must, up to a
scalar factor, verify E*obs. 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:
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!
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:
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
