Spielewelten mit Raycasting: Mathematik

In diesem Kapitel besprechen wir die mathematischen Grundlagen, wie sie für Raycasting gebraucht werden. Das Kapitel ist wirklich sehr mathematisch und und enthält viele Informationen über Dreiecke und Geometrie. Wir brauchen jedoch das gesamte hier dargestellte mathematische Rüstzeug für die Darstellung unserer Spielewelten.

KoordinatensystemBearbeiten

Möchte man in der Mathematik ausdrücken, wo sich etwas befindet, reicht es nicht aus, dorthin zu zeigen. Mehr noch möchte man genau sagen können, wo zum Beispiel auf dem Tisch eine Tasse steht. Beispielweise steht die Tasse 30 cm vom linken Rand und 50 cm vom unteren Rand entfernt. Damit kann man eine bestimmte Tasse leicht wiederfinden, auch wenn der Tisch über und über mit Tassen bedeckt ist.

 
Der Punkt P befindet sich 7 Kästchen rechts und 9 Kästchen oberhalb vom Koordinatenursprung

Genau so funktioniert das auch mit einem Blatt Papier. Malt man irgendwo einen Punkt hin, und legt fest, dass man von links unten zählt, kann man jedem mitteilen, wo sich der Punkt auf dem Blatt Papier befindet, indem man den Abstand von zwei Rändern (links und unten) bestimmt.

Der untere linke Punkt heißt dann Koordinatenursprung.

Diesen Koordinatenursprung kann man überall auf das Blatt malen und von dort aus zählen. In der Mathematik hat man sich darauf geeinigt, ein solches rechtwinkliges Koordinatensystem[1] entweder in der Mitte vom Papier, oder am linken unteren Rand beginnen zu lassen


 
Koordinatensystem des Computers

Der Computer verwendet ein etwas anderes Koordinatensystem. Zum einen zählt er seine Abstände nicht in Zentimetern, und zum anderen ist sein Koordinatenursprung in der linken oberen Ecke. Seine natürlichen Koordinaten sind Pixel, also Farbpunkte auf dem Bildschirm.

Dreieck und WinkelBearbeiten

 
Dreieck, Winkelfunktionen und Pythagoras

Von den vielen verschiedenen Dreiecken, die es so gibt, benutzen wir beim Raycasting nur das rechtwinkelige Dreieck, das also einen Winkel hat, der 90° groß ist.

Für die Länge der Seiten gilt folgender Zusammenhang, den man auch als Satz des Pythagoras bezeichnet

  •  

Man bildet hier also Quadrate um die einzelnen Seiten und stellt fest, dass das größte Quadrat gleich der Summe der beiden kleineren Quadrate ist.


Die Winkelsumme in unserem Dreieck ist 180°. Es gilt also

  •  

Bezogen auf die Winkel in unserem Dreieck gelten die folgenden trigonometrischen Zusammenhänge:

  •  
  •  
  •  



 
Einige Winkel zwischen Strahlen

Auch im Koordinatensystem auf dem Papier finden wir Winkel vor. Es gibt Winkel zwischen den einzelnen Koordinatenachsen, die wir mir rot und blau gekennzeichnet haben, wie auch zwischen den Achsen und einer gedachten Verbindungslinie zu einem Punkt (grüner Strahl). Der grüne Strahl wird uns später als Blickrichtung begegnen, dabei interessiert uns aber nur der Winkel, in den unsere Spielfigur schaut.


 
Steigungsdreieck der Geraden QP

Innerhalb unseres Koordinatensystems finden wir ebenfalls ein Dreieck vor, wen wir zwei Punkte P und Q einzeichnen, und eine Verbindungslinie zwischen diesen beiden Punkten malen. Dann ist der vertikale Abstand dy eine kleine Seite, der horizontale Abstand dx eine kleine Seite und die grüne Verbindungslinie die lange Seite. Hier gilt selbstverständlich ebenfalls der Satz des Pythagoras wie auch alles, was wir bisher über Dreiecke gesagt haben.

Ist also Punkt P eine Spielfigur und Q ein Stückchen Wand, dann können wir nun ausrechnen, wie groß der Abstand PQ zwischen der Spielfigur und der Wand ist:

  •  



In technisch-wissenschaftlichen Anwendungen, wie auch in Computerbereich, rechnet man Winkel zumeist nicht in Grad aus, sondern in Radiant. Während ein Vollkreis in Dezimalgrad den Winkel von 360° hat, hat er in Radiant den Winkel  .

Zum Umrechnen gibt es folgende Formel, wobei d ein Winkel in Dezimalgrad (DEG auf dem Taschenrechner) und r ein Winkel in Radiant (RAD auf dem Taschenrechner) ist:

  •  
Beispiel: d = 90° bedeuten   also
  also
 
Beispiel: Die Winkelsumme in einem Dreieck ist gerade  .

Wir werden im nächsten Kapitel Funktionen kennen lernen, die uns die Umrechnung zwischen diesen beiden Winkeleinheiten abnehmen.

Ein StrahlensatzBearbeiten

 
Der Strahlensatz

Die Geometrie in einem Dreieck lässt sich leicht erweitern, wenn man ein Dreieck in ein anderes hinein malt, dann verhalten sich die Dreiecke ähnlich zueinander. In der Abbildung haben wir zwei Dreiecke, nämlich das Dreieck a1h1 und a2h2. Beide Dreiecke teilen sich einen Winkel (u, nicht eingezeichnet) und die lange Seite, beide Dreiecke haben einen rechten Winkel. Es gilt hier also

  •  

sowie

  •  

Setzt man diese Gleichungen gleich, was man darf, weil der Winkel u ja von beiden Dreiecken geteilt wird, dann gilt:

  •  

Wir werden dieses beim Raycasting benutzen, um die Wände zu zeichnen. Die echte Wandhöhe werden wir dabei kennen, ebenso den Abstand von der Wand wie auch den Abstand von unserem Monitor. Damit können wir die Zeichenhöhe der Wand leicht ausrechnen.

Beispiel: Eine Wand in einem Zimmer ist immer gleich hoch, egal, wie weit wir davon entfernt stehen. Wenn wir näher herangehen, erscheint die Wand auch größer, sind wir weiter weg, erscheint sie kleiner. Dabei können wir uns vorstellen, dass eines der Dreiecke im Auge entsteht, etwa auf unserer Netzhaut. Das andere Dreieck ist der echte Abstand zur Wand und die echte Höhe der Wand, die sich nicht verändert.
Beispiel:Wenn wir unseren Arm mit hochgestelltem Daumen ausstrecken, dann können wir ein Dreieck bilden, dass die Armlänge und die Daumenhöhe beinhaltet. Mit unserem Daumen können wir ein Gebäude verdecken, dessen Höhe wir vielleicht kennen. Dann können wir mit dem Strahlensatz ausrechnen, wie weit das Gebäude entfernt steht.

Über Strahlensätze[2] kann man noch mehr schreiben, aber wir beschränken uns in dem Buch wirklich nur auf die Dinge, die für Racasting wichtig sind.

Ganzahlige Division und RestBearbeiten

Teilt man, wie in der Grundschule, eine Zahl durch eine andere und tut so, als gäbe es keine reellen Zahlen (Zahlen mit Komma), dann kommt bei einigen Divisionen ein Rest heraus. Beispielsweise ist

  •   Rest 2
  •   Rest 0
  •   Rest 1
  • und so weiter.

Den Teil, bei dem man den Rest nicht berücksichtigt nennt man ganzzahlige Division.

In der Grundschule wusste man noch nichts über Zahlenmengen, die solche Operationen wie das Teilen vollständig ermöglichen.

In der Mathematik macht man sich diese Rechenweise zu nutze, in dem man ihr einen Namen gibt und Rechengesetze entwickelte, die das Rechnen mit natürlichen Zahlen ermöglicht.

Modulo-Rechnung ist dabei diejenige Technik, die nach dem Rest einer solchen Division fragt, also

  •   - der Rest bei der ganzzahligen Division durch 3 ist 2
  •   - es gibt bei der Division durch 3 keinen Rest
  •   - der Rest bei der ganzzahligen Division ist 1
  •   - der Rest bei der ganzzahligen Division ist 2
  • und so weiter

Modulo-Rechnung kennen Sie aus dem Alltag von Uhren, da benutzen sie es täglich. Wenn es beispielsweise 21 Uhr ist und Sie schlafen 9 Stunden, dann ist es nicht etwa 30 Uhr, sondern 6 Uhr. Schreibt man das etwas formeller auf, dann sieht das so aus:

  •  .

Wir benutzen das später bei Winkeln, die kleiner als 360° sein sollen. Wir addieren also immer zwei Winkel modulo 360.

 
Abstand eines Punktes vom Rand

In der rechten Beispielgrafik ist ein Punkt P(x ; y) in einem Feld eingezeichnet. Die Feldgröße beträgt jeweils 64 Pixel. Der Abstand a vom linken Feldrand ist daher:

  •  

und der Abstand b zum rechten Feldrand beträgt:

  •  

Wir bekommen also mit Hilfe der Modulo-Rechnung die Abstände zwischen einem Punkt und zwei benachbarten Feldern heraus. Dieses machen wir uns später zu nutze, wenn wir eine Spielfigur frei über ein schachbrettartiges Spielfeld laufen lassen und schauen, wie weit die Spielfigur vom Rand eines einzelnen Feldes entfernt ist.

Die Nummer des Feldes auf dem Schachbrett, vom linken Rand aus gemessen, ist dann übrigens

  •  

wobei hier die ganzzahlige Division gemeint ist.

LandkartenBearbeiten

Fertigt man Zeichnungen von Dingen oder Gebieten[3] an, dann sind diese Zeichnungen meist kleiner als das Original. Stellen Sie sich einfach ein Foto von einem Fußballfeld vor, von oben aufgenommen. Bei solchen Abbildungen möchte man oft berücksichtigen, dass die Dinge untereinander den gleichen Abstand haben, wie im Original, also alle Dinge um den gleichen Faktor verkleinert oder vergrößert werden. Hierzu bietet sich analog zum zweiten Strahlensatz die Verhältnisrechnung an:

  •  

Hierbei bedeutet a die echte Entfernung eines Fußballspielers vom linken Fußballfeldrand, A ist die Länge des echten Fußballfeldes. b ist die Entfernung genau dieses Fußballspielers auf dem Foto vom linken Rand des Fußballfeldes, B ist die Länge des Fußballfeldes auf dem Foto.

Beispiel: Ein Fußballspieler steht 10 m vom Tor entfernt, das Fußballfeld ist 100 m lang. Auf dem 40 cm langen Fernsehbild, welches das Fußballfeld bei einer Übertragung zeigt, ist der Spieler 4 cm vor dem Tor zu sehen.
Beispiel: Eine bestimmte Modelleisenbahn hat einen Maßstab von 1:220. Also 1 m Modelleisenbahn sind in echt 220 m. Sie können nun ausrechnen, wie lang die Modelleisenbahn sein muss, um beispielsweise das Schienennetz von Berlin zeigen zu können.

In diesem Buch benutzen wir diese Rechnung, um ein riesengroßes Spielfeld verkleinert auf dem Bildschirm zeigen zu können.

AnmerkungenBearbeiten

  1. Es gibt noch viele andere
  2. Es gibt drei Stück, von denen wir hier nur den für uns wichtigen zweiten Strahlensatz beschrieben haben.
  3. Das Thema wird etwas komplizierter, wenn man die Erdkrümmung berücksichtigt