How to setup the ESP32 to visualize OBDII Data…

This manual describes how to use an ESP32 as an extension to the existing OBDIIC&C device, available for the Honda Insight ZE1. This device will not add any new features, but will allow you to visualize the OBDII data on your smartphone.

If you are looking for a tutorial on how to read data from an OBDII connector, this ist the wrong place.

First, you’ll need an ESP32. Connect the ESP32 via a Micro USB cable to your PC. Install the drivers, if necessary. The ESP32 should be recognized as a COM port:

Download the ESP32 Flash Download Tool from the website:

https://www.espressif.com/en/products/hardware/esp32/resources

Select “Tools” -> Flash Download Tools (ESP8266 & ESP32) .

After downloading, start the flash download tool.

Select “ESP32 DownloadTool”.

The main window will pop up. Configure as follows:

SPI flashing, 32Mbit flash, 40 MHz SPI speed.

Add the binary to the list of files to flash, and set a start address of 0x0. Also make sure to choose the correct COM port. After setting up everything correctly, press „START“.

If everything works OK, the download should take about ~ five minutes.

After reset the target, you should see some debug output in the serial interface, looking like this:

How to Connect the ESP32 to the OBDIIC&C

To make sure the ESP32 can talk with the OBDIIC&C, we need to connect three wires:

  • GND
  • UART Rx
  • UART Tx

However, the logic levels of the two MCUs are different. The PIC uses 5V TTL logic for the UART, the ESP32 3.3V. Additionally, the logic levels are inverted.

Hence, you need two transistors to adapt the signal levels, and invert the logic levels at the same time. Have a look at the example schematics below to understand how to wire things up:

How to connect the ESP32 to the OBDIIC&C data logging port

Note that the pins of the ESP32 used for UART communication are D22 and D23, not the pins labeled “RXD” and “TXD” next to it (this is a different UART channel). The ESP32 supports connecting the second UART to any pin of the device. The first UART peripheral is available via USB or the RXD and TXD pins, and is used for flashing an debugging. The second UART, on pin 22 and 23, is used to communicate with the OBDIIC&C.

Please double-check the pinout on the “headphone” plug on the OBDIIC&C, make sure to measure which pin is GND first.

3V3 are directly available on the ESP32, 5V you’ll need to get from the OBDIIC&C.

Downloads

Below, you will find the download link to the ESP32 software:

Honda Insight ZE1 OBDII Smartphone App

I’ve been using Peters OBDII C&C for quite a while now, and while I like it’s features, it lacks the intuitiveness of a modern smartphone app. So I thought it’s about time to improve this!

System Architecture

Two MCUs are working together to read the OBDII data from the car, and transmit it vie BLE (Bluetooth Low Energy). The data is transmitted to the smartphone, where it is visualized.

The two controllers are one PIC and one ESP32, the PIC is programmed by Peter, and used to interface the OBD, while the ESP32 is programmed by me, used for forwarding the data to the smartphone.

Both MCUs communicate via UART.

See a first running demo of it here:

Nissan Rz1 Digital Cluster Conversion

A few years ago, I modified a LHD Nissan Sunny B12 Coupé Rz1 and fitted a RHD JDM digital clusters, and uploaded a short video of it on youtube.

I received a lot of questions on this modification, and decided to publish the knowledge I gained here.
Most importantly, here is the pinout.

Pinout Comparison of the RHD JDM loom and the LHD EUDM/USDM loom

Connector Pinout

The connectors are drawn on the left side. Basically, you see five connectors here. Connector “A”, “B”, and “C” under the header “Digitaltachostecker” describe the connector of the digital cluster. Connector “A” is the large one that powers the talltales and warning lights, connector “B” is the hard-to-find black one, that provides all the actual digital signals. The three-pin connector “C” can not be found on the cluster, but is the connector on the tachometer sensor in the engine bay (you need that part too).

The connectors labeled with “EU stecker” refer to the ones that you will find in your LHD Rz1s that came with analog clusters. You should most likely find them in your car if you remove the cluster.

In case you have a low-end spec B12 that came without a rpm gauge (some U.S. Sentras maybe?), your connector layout is probably different again.

The drawings show the connectors (sockets) on the cluster, as if you look on the backside of the cluster. They do not show the connectors on the harness!

The first problem you’ll face is that you need to get the small connector “B”, which, if it is not attached to your digital cluster, is pretty much unobtanium. You could try to find the original part number or a the part number from the supplier who made this connector, or in the worst case, replace the connector with a diffent type of similar size / pin cont and just solder everything together.
The white, larger connector “A” is physically identical to connector “A” of your LHD harness, but with a different pinout.

You got your hands on some plugs? Good, then you can already solder everything together, and your digital cluster should already party come to life. PRM, turn indicators, telltales (except exhaust temperature), temperatur gauge and fuel should come to life.

Vehicle Speed Sensor

The next difficult task it to get a speed sensor. The analog clusters uses a mechanical speedo cable that connects the gearbox to the speedo pointer – that is 100% mechanical oldschoolness!

For the digital cluster, NISSAN chose to go half they way – they still use a mechanical cable, about 50 cm long, that connects the gearbox to an electrical sensor. That sensor converts the motion into PWM signals, that are electrically supplied to the cluster. For the conversion, you will need both the cable and the sensor. If you don’t have these parts, then the installation will be a bit more difficult. They will plug&play fit to any gearbox.
The digital sensor is connected with two cables, C2 and C3, to the main plug of the cluster. So you will need to add two wires from your engine bay to your cluster.

If I remember correctly, the speedo singal is triggered twice per revolution. If you don’t have a sensor, you might want to use a function generator and try to get your cluster displaying something. If you are struggling here, feel free to leave a comment, then I will look up the technical details.

From the youtube comments on my channel, I understood that there seem to be different types of sensors, depending on which engine / gearbox your donor car had. It is likely that non-matching gearboxes will provide false readings on the speedo! If this is the case, then you would need to invest more engineering into the problem, e.g. use a small microcontroller to correct the signal.

I once tried to fit a digital sensor from the B13/N14 series into an E16i gearbox, but they wouldn’t fix plug&play. The main problem was that while the diameter was the same, the axis of the sensor was slightly offset. With some fiddling you might be able to mount them, though.
These sensors might fit for the GA16i gearbox, though. If you tried going this way, please leave a comment and share your experiences! it would definitely be cleaner looking than the OEM B12 parts.

You will have to figure out a solution to mount the speedo sensor in your engine bay, as the LHD / RHD firewalls are different. I suggest to use a little metal plate to mount the sensor to, and then adapt that to the firewall.

Incorrect mounting with too much tension on the cable might lead to the speedo not working at all, faster wear-out or not working at all.

Fuel Level Sensor

A problem which is not yet solved, it the fuel gauge. The fuel sensors used in the JDM digital cluster cars have a different characteristic.

The analog clusters use an 8V voltage regulator, which is connected to the fuel gauge and the fuel sensor in series. The resistor value of the LHD fuel sensor is as follows:

Resistor Value [Ohm]10100
Displayed Fuel Level100% (full)0% (empty)

The digital cluster characteristic is quite different. I used a JDM cluster and measured the fuel input. The fuel sensor is supplied by 5V, and depending on the resistor values, the following fuel level is displayed:

Resistor Value [Ohm] Number of bars
14,9 14 (full)
20,414 (full)
23,613
30,613
7810
1058
2166
3004
4003
6002
7171
8091
10000 (empty)

With this information, you should be able to build your own adapter for the fuel sensor.

Nissan Sunny B12 E16i Seitenschaden

Eckdaten:
1986er Nissan Sunny B12 Coupé, rostfreie Karosserie, Oldtimerzulassung, zeitgenössisches Tuning

Unfallschaden Seitenwand links, Streifschaden hinter der Tür links.

Notwendige Arbeiten:

  • Richten der Seitenwand
  • Lackierung Seitenwand links + Verspoilerung links (neuwertige vorhanden) + Dach
  • Einbau neuer Windschutzscheibe (vorhanden)

Zustand vor Demontage der Seitenverspoilerung:

Die Tür wurde bereits getauscht und lässt sich mit minimast erhöhtem Kraftaufwand schließen.

Detailansicht Seitenschaden:

Under der schwarzen Gummikappe ist ein Bohrloch, welches auch zugeschweißt werden müsste.
Der Türsensor liegt aufgrund des Schadens nicht mehr an der Tür an.
Der untere Schwellerbereich ist rostfrei, und nicht beschädigt. Die Beschädigungen betreffen ausschließlich die Seitenwand. Der Wagen ist mit Mike Sanders Fett hohlraumversiegelt. Bei Bedarf kann diese mit einem Heißluftfön entfernt werden.
Spalt zur Tür (Tür wurde getauscht)
Under der runden Gummikappe befindet sich ein Bohrloch (Vorbesitzer…)
Sicht von vorne

Die Verkleidungen auf der Innenseite werden entfernt, sodass problemloser Zugang zu der Seitenwand von beiden Seiten aus gewährleistet ist. Die Seitenwand ist auch vom Innenraum gut erreichbar.

Vielen Dank fürs Lesen!

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 🙂 ).

Downloads

Data sheets: http://mic.hit-karlsruhe.de/projekte/WS10_PropClock/images/Datenblaetter_prop.zip

Technical drawings:

http://mic.hit-karlsruhe.de/projekte/WS10_PropClock/images/Konstruktionszeichnungen/huelse_aussen_spule.pdf

http://mic.hit-karlsruhe.de/projekte/WS10_PropClock/images/Konstruktionszeichnungen/huelse_innen_spule.pdf

Links

Project documentation on my university’s website: http://mic.hit-karlsruhe.de/projekte/WS10_PropClock/

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:

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

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

http://www.texelography.com/misc/website_data/helper_scripts.zip

MBDAK 3 – A 3D Flight Simulator

MBDAK 3 is one of my software projects that I wrote in the years 2007 and 2008. It is a 3D engine designed for flight simulator games written in Delphi 7. In this project, I focussed on creating an engine of highest compatibility and flexiblity. It was the first time I came in contact with dynamic linked libraries which I have used to create a flexible interface to the 3D and the sound 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 8 and OpenGL API, thus it is possible to change the 3D output API by just exchanging the DLLs. This is no problem as both provide the same interface. The sound subsystem uses the FMOD audio library, which is also stored in an encapsulated dynamic library file.

The levels are stored in text files. 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, which is mostly a simplified version of the 3D data 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. Other data which is being configured in the level file is the type of aircraft the player is flying, its weapon arsenal and other important attributes (starting position, position light data, etc). This was done to provide a maximum of flexibility in the level design.

Another important goal during the development of this engine was to make the simulation as realistically 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, most importantly, is able to perform dynamic real-time shadow calculation with the help of the stencil buffer 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.

Download

Documentation

You can download the documentation of the project “MBDAK 3” under the following link:

Facharbeit Facharbeit “Entwicklung eines 3D-Spieles” and its attachement  Anhang containing the graphics.

If you have any questions please contact me under “Imprint”.

3D Triangle Collision Detection

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

Facharbeit

im Leistungsfach Mathematik

(fächerübergreifend zur Informatik)

Thema:

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

 Clemens Zangl

Schuljahr 2006/2007

MSS 12

Max-Slevogt-Gymnasium Landau

Inhaltsverzeichnis

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

1. Einleitung

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

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

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

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

1.1. Geschichte der 3D-Spiele

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

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

1.2. Die Idee und Geschichte der MBDAK-Serie

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

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

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

2. Hauptteil

2.1. Grundlegender Aufbau und technische Planung

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

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

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

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

2.1.2. Was ist eine 3D-Engine?

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

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

2.2. 3D-Mathematik

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

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

2.2.2. 3D-Kollisionsberechnungen

2.2.2.1. Geschichte der Mathematik in 3D-Spielen

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

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

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

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

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

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

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

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

2.2.2.2. Kugel-Kollisionen oder Sphere-Collisions

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

Berechnung der Vektorlänge:

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

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

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

 2.2.2.3. Dreiecks-Kollisionen oder Triangle-Collisions

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

Im Grunde wird dieser Algorithmus nach folgenden Schema ablaufen:

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

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

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

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

Die Lagekonstante d berechnen wir folgendermassen:

Der Punkt x entspricht hierbei einem beliebigen Punkt der Dreiecksebene.

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

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

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

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

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

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

Aufgelöst nach a ergibt sich:

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

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

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

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

In allen anderen Fällten tritt keine Kollision auf.

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

 2.2.3. Dreiecks-Transformation

2.2.3.1. Wann müssen Dreiecke transformiert werden?

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

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

Eine Transformation kann aus folgenden Elementen bestehen:

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

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

2.2.3.2. Rotieren, Drehen und Rollen von komplexen Dreiecksmustern

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

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

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

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

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

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

Im Programmquelltext umgesetzt sieht diese Berechnungen wie folgt aus:

If Pitch <> 0 then begin

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

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

end;

2.2.3.3. Skalieren von Dreiecken

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

Mit diesem Algorithmus wäre auch unsere Skalierungsfunktion abgeschlossen.

2.2.3.4. Verschieben von Dreiecken

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

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

3. Schluss und weitere Ausblicke

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

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

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


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

[2]    Siehe Anhang, Abbildung 2

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

[4]    Siehe Anhang, Abbildung 1

[5]    Siehe Anhang, Abbildung 3

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

[7]    Siehe Anhang, Abbildung 4

[8]    Siehe Anhang, Abbildung 5 und 6

[9]    Siehe Anhang, Abbildung 7

[10]  Siehe Anhang, Abbildung 8 bis 12

[11]  Siehe Anhang, Abbildung 13