Propeller Clock

This project started in 2010 as a university project with the goal do develop a rotation clock. Main objectives of the project was to develop an induction power supply using a MOSFET H bridge and and to layout a PCB. The PCB contains a 8051 microcontroller and ten OSRAM RGB LEDs as well as an optical reflex coupler. The board is mounted on a rotateable motor, which propels the board to 40 rotations per second. Based on the input data of the reflex coupler, the microcontroller then calculates the current position and switches the LEDs on or off so that the user sees a stable image.

Layout of the PCB.

The PCB features a power supply that suported AC/DC inputs, ranging from 7 to 20V, while delivering a stable 5V DC current used to power the 8051 microcontroller soldered onto the PCB. The board is powered using induction. A MOSFET H bridge is used to power the primary coil, while the secondary coil is mounted on the rotateable part. Programming started in Assembler (requirement of university), but will be finished in C. The project is not yet completed – the PCB works as expected and the induction power supply is working, but the current mechanical setup is not fast enough to create a stable image. Development is still ongoing (only problem is time 🙂 ).


Data sheets:

Technical drawings:


Project documentation on my university’s website:

3D circles Technology

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 I3 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:

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

You can also find these scripts on my GitHub:

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!


My 3D Flight Simulator – Written in Delphi

There was a time before I became a die-hard fan of C++. Back then in high school, I believed – for some reasons – that learning Delphi was a good idea. Even worse, I thought it would make an excellent choice to write 3D games!

Even worse, I didn’t even stop when tutorials recommended to use hacked OpenGL headers, that “somehow” worked with Delphi. It took a lot of effort to take off, but it shows that you can build cool stuff, even if your choice of programming language is not the best. Even today, I am still much more interested too see awesome projects coming into life, instead of participating in the endless discussions about which programming language is now the best to learn!

Back then in 2007, I was inspired by games such as GTA3, UT99, and SNES Star Wing – and after reading a book “how to write a 3D engine”, I decided that my next game would be a 3D engine for flight simulator games!

The name of the game is MBDAK 3, which is a complex German acronym, and can be roughly translated to “carnage the invaders, until the doctors arrive”. In this project, I focussed on creating an engine of highest flexiblity. It was the first time I came in contact with dynamic linked libraries, and the engine supports an abstracted rendering and audio layer, and is therefore independent on the actually used 3D API. Both the graphical and the audio subsystem are encapsulated in separate DLL files. Different implementations of these DLLs allow the use of different graphic libraries. Implementations were done for the Direct3D and OpenGL API, thus it is possible to change the 3D rendering API by just exchanging the DLLs. The sound subsystem uses the FMOD audio library, which is also stored in an encapsulated dynamic library file.

The layout of the game is also completely configured in xml files to describe the environemnt. Each level iteself consists of a set of building blocks, the so called level entities (i.e. scyscrapers, cranes, streets and other level elements). Each entity provides a file containing the 3D data for rendering and a collision model file, and several attributes (destroyable, material properties, additional data for light and particle effects). Each entity can then be placed multiple times at any position in the 3D scene. The properties of the aircraft flown by the player is also configured in these xml files: its weapon arsenal and other important attributes (starting position, position light data, etc) are all configurable. This was done to provide a maximum of flexibility in the level design.

The collision detection works using a tree structure: the first level of the tree is the subdivion of the environment into large invisible cubes. The collision detection algorithm only takes the cube(s) into account, that are currently accessed by the player. Only objects within this cube are then considered for collision detection. The second stage of collision detection is done using spheres, where each entitiy has a sphere that encompasses it. Only if the sphere of the player and another object overlap, collision detection is done on a triangle level. The triangle models used for collision detection are greatly simplified variants of the original model, in order to keep the number of necessary computations to a minimum.

3D collision detection using spheres, encompassing the triangle meshes of the entities

Another important goal during the development of this engine was to make the simulation as realistic as possible and to become familiar with the latest rendering technologies at that time. The engine therefore uses MipMapping texture filters, fog and dynamic lighting and uses dynamic real-time shadow calculation using the Carmack’s Reverse method. However, interesting things such as bump mapping or shaders were not been used. The reason for this was first, because compatibility with non-T&L-capable video cards (I am a huge fan of old 3dfx video cards and the game was developed on a Voodoo5) was desired and second, because of the lack of time. I still had to go to school at this time.

I would like to thank Mr. Plöchinger, also known as DungeonKeeper1 in the german VoodooAlert board, for providing the MBDAK 3 soundtrack! The 3D models were partially created by myself using Milkshape 3D, while some others were extracted from older computer games. For this reason, I unfortunately cannot publish this game.

Abilities of the 3D Engine

  • Selectable 3D API: Direct3D 8, OpenGL und 3dfx Glide are supported
  • Support of real-time dynamic stencil buffer shadows
  • MipMapping texture filters
  • Dynamic environment loading systen
  • Collision detection using separate collision models based on a combination of octree data organisation and spheres / triangle collision detection for best performance
  • A simple particle system supporting alpha blending and z ordering

Shown below are several screenshots of the current development stage. Unfortunately, I cancelled the project after two years of development due to other priorities (studying). Besides that, creating 3D simulations using Delphi was not the smartest choice and the quality of the source code was miserable as only structures and no classes were used.

MBDAK 3 - Flugsimulator
MBDAK 3 with highest details: real-time shadow calculation, fog, particles and hightest texture quality

Screenshot of the main menu
MBDAK 3 menu intro. Graphics were hand-drawn, scanned and colorized… with Microsoft Paint.

Menu screen starfield simulator
MBDAK 3 menu. Graphics were done with Adobe Fireworks. The little preview window in the top left corner is inspired by Nintendo’s Starwing. It contains a little starfield simulator.


Source Code

You can find the ugly, terribly documented source code on my GitHub:


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!


im Leistungsfach Mathematik

(fächerübergreifend zur Informatik)


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

 Clemens Zangl

Schuljahr 2006/2007

MSS 12

Max-Slevogt-Gymnasium Landau


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 Geschichte der Mathematik in PC-Spielen  …………………………………………………………….. 6 Kugel-Kollisionen oder Sphere-Collisions  …………………………………………………………….. 7 Dreiecks-Kollisionen oder Triangle-Collisions  ………………………………………………………. 8
2.2.3. Dreieck-Transformation  ………………………………………………………………………………………… 10 Wann mĂĽssen Dreiecke transformiert werden?  ………………………………………………………. 10 Rotieren, Drehen, Rollen von komplexen Dreiecksmustern  …………………………………….. 10 Skalieren von Dreiecken  ……………………………………………………………………………………… 11 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 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. 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. 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 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. 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; 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. 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

[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