Schnittpunkt eines Strahls mit einem Terrain

Zur Berechnung des Schnittpunkts eines Strahls mit einem Terrain ist es wichtig die Menge der zu prüfenden Dreiecke zu minimieren, da ein Terrain in der Regel aus sehr vielen Flächen besteht. Ein sehr guter und schneller Weg dies zu erreichen besteht darin, den Weg des Strahls mitzuverfolgen und alle auf dem Weg für einen Schnittpunkt infrage kommenden Dreiecke zu testen.

Der erste Schnittpunkt den wir finden ist so auf jeden Fall auch der dem Strahl-Startpunkt am nächsten liegende Punkt - was in der Regel der gesuchte Schnittpunkt ist.

Der Weg des Strahls wird verfolgt, indem sowohl dessen Eintritt in, als auch dessen Austritt aus dem Terrain in Heightmap-Koordinaten berechnet werden und zwischen diesen beiden Punkte mit dem Bresenham-Algorithmus eine gerade Linie gezogen wird.

So erhalten wir genau den Bereich, den der Strahl im Terrain zurücklegt und innerhalb dessen ein Schnittpunkt gefunden werden muss falls einer existiert:

Strahlverfolgung mit Bresenham

Von der Seite betrachtet sieht man den Verlauf des Strahls und die Schnittpunkte mit dem Terrain:

Seitenansicht der Strahlverfolgung

Die Kreise markieren jeweils den Ein- und Austrittspunkt des Strahls in die achsenparallele Bounding Box (AABoundingBox). Die Quadrate zeigen die so gefundenen Schnittstellen.

Sollte der Strahl innerhalb der Bounding Box beginnen, so wird der Startpunkt des Strahls als Startpunkt für die Strahlverfolgung verwendet.