Erweiterter Octree

Erweiterter Octree mit Hilfe von optimierten Bounding Spheres

In einem vorhergehenden Artikel habe ich über einer der häufigsten Funktionen in einem Raytracer geschrieben (Performanz-Test Cuda vs CPU, Teil 1). Diesmal widme ich mich mit dem Finden der notwendigen Dreiecke bzw. Polygone für den Schnitttest, also den Schritt davor. Diese Aufgabe gehört auch zu den häufigsten Funktionen in einem Raytracer.

Die Dreiecke gliedere ich in einen Octree. Da ein Schnittest mit einem Strahl und den Bounding Boxes viel Zeit in Anspruch nimmt, nehme ich stattdessen die schnelleren Bounding Spheres.

Erweiterter Octree mit Hilfe von optimierten Bounding Spheres Erweiterter Octree mit Hilfe von optimierten Bounding Spheres

1.1 Methode, um unnötige Schnitttests zu reduzieren

Bounding Spheres haben einen Nachteil, sie bilden Überlappungen mit ihren Nachbarn. In dem Beispielbild (siehe A) würde ein Strahl, der nur das linke untere Quadrat schneidet, in recht häufigen Fällen auch den oberen Kreis schneiden und somit weitere Dreiecke einem unnötigen Schnitttest zuführen. Mit meiner Methode (siehe B1-B3) lassen sich unnötige Schnitttest nicht ganz eliminieren, jedoch erheblich reduzieren.

Abgesehen davon bilden Bounding Boxes wohl keine Überlappungen, aber führen häufig auch zu unnötigen Schnitttests, da sich die Geometrie der Objekte in einer Szene selten Axial ausrichtet. Optimierte Bounding Sphere erstellen

Es bieten sich mehrere Möglichkeiten an, eine optimierte Bounding Sphere zu erstellen. Ich werde den weniger aufwendigen Weg beschreiben. Hierzu können 4 Situationen eintreten:

  • A -› Polygon innerhalb Sphere
  • B -› Polygon innerhalb Sphere (Sonderfall)
  • C -› Polygon schneidet Sphere
  • D -› kein Polygon (somit Leer, wird deswegen nicht weiter betrachtet)

Optimierte Bounding Sphere erstellen Optimierte Bounding Sphere erstellen

1.2 Methoden, um optimierte Bounding Spheres zu berechnen

Im ersten Fall bilden alle Vertices im Schnitt einen neuen Mittelpunkt und der entfernteste Punkt vom neuen Mittelpunkt den Radius der neuen Sphere. Hierbei kann aber ein Sonderfall eintreten (siehe B), die Sphere schneidet die Ursprungs-Sphere. Es wird der Ursprungsmittelpunkt genommen und als Radius der entfernteste Punkt vom Ursprungsmittelpunkt.

Bleibt noch der Fall C, wenn ein (oder mehrere) Polygon(e) die Ursprungs-Sphere schneidet, wird keine neue Sphere berechnet.