Honda CRZ ZE2 CAN Bit Assignment Sheet

A while ago I hooked a CAN logger to a friends CRZ, and reverse-engineered it a bit. Hope it helps for your projects 😉

Vehicle CAN

Message IDBitLengthDescription
0x13F816ThrottlePosition raw
0x13F4032ThrottlePosition counter
0x16408Headlight switch
0x1644816Vehicle speed
0x17C2416Engine RPM
0x19111Transmission reverse SW
0x19121Transmission neutral SW
0x374328Trunk open
0x13688VTEC SW
0x13608fuel cutoff


Message IDBitLengthDescription
0x111816IMA Motor RPM
0x169816IMA motor current (mA)
0x2312416IMA SOC

“Can not find free FPB Comparator!” when using OpenOCD…

The last two days, I had a very interesting problem that I thought is worth sharing. I am developing a project on an STM32 microcontroller. My toolchain uses Eclipse, which uses GDB, which in turn controls OpenOCD, which does all the low-level stuff so that I can flash and debug. That worked very well for a long time. Until yesterday.

What did I do? I added a new class to my project, which at some point would be dynamically allocated. I kept the method bodies all empty, so nothing should happen. But after flashing the code to the target, the debugger crashed with the message:

Can not find free FPB Comparator!
can’t add breakpoint: resource not available

This error message was already familiar to me – it usually happens when you have too many breakpoints listed in Eclipse, and when you start the debug session, it will automatically add all these breakpoints. If you have listed more breakpoints than the MCU supports (six), this message appears. But here, my breakpoint list was completely empty.

Strange! I had no idea what was going on here, so my first trial and error approach was to reduce the flash and RAM footprint of my app, but even after implementing some optimizations here and there, the problem remained the same. The fun fact was that if I commented out that class, debugging worked again! But once my class was back, even with empty function bodies, the debugger stopped working!

So I decided to have a closer look. Using the telnet interface of OpenOCD, I was able to halt and continue the MCU, so debugging in general was technically still working. Reading and writing from and to memory was also working.

After reading a lot about the FPB, I understood a bit better how this works: The Flash Patch and Breakpoint (FPB) unit is a set of registers of the ARM MCU, which consists of several comperators – one for each breakpoint. Each comperator basically stores one program ( FP_COMPx). If the currently executed address matches what is written inside this register, the execution will be stopped and you can debug.

So I decided to have a look at the hardware registers itself. Since I couldn’t use Eclipse for debugging anymore, I had to use Telnet. If you have an OpenOCD server running, it will listen on port 4444 for a telnet connection. Via this connection, I was able to read out the memory of the FPB registers, located at address 0xE0002000:

mdw 0xe0002000 20
0xe0002000: 00000261 20000000 48001239 4800164d 480019b1 480021a1 48005d0d 48006851
0xe0002020: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
0xe0002040: 00000000 00000000 00000000 00000000

Starting from the third register (0x48001239), there is a list of six registers filled with some addresses. That explains the error that we see from OpenOCD, the questio now is, who is writing to these registers?

A lot of further research revealed me that it is possible to open OpenOCD in debug mode, by passing parameter “-d3” to it. This even works in Eclipse:

With this additional debug output, I could actually see what secretly happens after flashing. I saw about six of these blocks:

Debug: 17205 11732 gdb_server.c:3153 gdb_input_inner(): received packet: ‘m8001238,2’
Debug: 17206 11732 gdb_server.c:1438 gdb_read_memory_packet(): addr: 0x0000000008001238, len: 0x00000002
Debug: 17207 11732 target.c:2210 target_read_buffer(): reading buffer of 2 byte at 0x08001238
Debug: 17208 11732 hla_target.c:777 adapter_read_memory(): adapter_read_memory 0x08001238 2 1

This is actually the part where the breakpoints were set, and I could see the breakpoints were actually explicitly requested by someone! But why? And why on earth would Eclipse set so many breakpoints? I decided to check the addresses in the Linker file.

The locations usually looked somewhat like this:

All of these blocks somehow had a function with the string “main”, and it was the same case with my recently added C++ class, which also had a member function named “main”. That was when I understood, that Eclipse automatically sets a breakpoint at main() after startup! And for some reasons, it is setting this breakpoint also to classes that have a member function with the name main. It was just because I added one more class with a “main” function, that the number of possible breakpoints was exceeded, and the debugger wouldn’t work anymore.

You could debate if it is good style to have functions named “main” in your code. For me, it was OK because they are not only class members, but also somewhere in their own namespace, and should therefore be restricted. Turns out this was not always the case.

So if you encounter this problem, make sure to reduce the number of functions named “main” in your system!

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

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

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