Begrenzungsintervall Hierarchie

Ein Begrenzungsintervall Hierarchie ist eine Teilungsdatenstruktur ähnlich der von Begrenzungsvolumen Hierarchien oder kd-Bäume. Begrenzungsintervall Hierarchien können in Hochleistungsstrahlverfolgung verwendet werden und kann besonders nützlich für dynamische Szenen zu sein.

Die BIH wurde zum ersten Mal unter dem Namen der SKD-Bäume, von Ooi et al., Und Buchsbaum vorgestellt vorgestellt, unabhängig von Zachmann erfunden.

Überblick

Begrenzungsintervall Hierarchien weisen viele der Eigenschaften der beiden Begrenzungsvolumen Hierarchien und kd-Bäumen. Während die Konstruktion und Lagerung der BIH ist vergleichbar mit der von BVH die Traversierung BIH ähneln denen einer kd-Bäume. Darüber hinaus sind BIH auch binäre Bäume wie kd-Bäumen. Schließlich sind BIH-Achse ausgerichtet sind, wie ihre Vorfahren. Obwohl eine allgemeine nicht-achsenparallele Ausführung des BIH möglich sein sollte, würde es höchstwahrscheinlich weniger wünschenswert aufgrund der verringerten numerische Stabilität und eine Zunahme in der Komplexität der Strahldurchquerung.

Das Hauptmerkmal der BIH ist die Speicherung von 2 Ebenen pro Knoten, die überlappenden Kindern ermöglicht, aber zur gleichen Zeit mit einer Bestellung auf die Kinder entlang einer Dimension / Achse.

Es ist auch möglich, einfach die BIH Datenstruktur für die Bauphase, sondern durchqueren den Baum in einer Weise, ein traditionelles ausgerichtete Achse Begrenzungsrahmen Hierarchie tut. Dies ermöglicht es, einige einfache Geschwindigkeit bis Optimierungen für große Strahlenbündel während Speicher / Cache-Nutzung gering.

Einige allgemeine Eigenschaften von Begrenzungsintervall Hierarchien, wie beschrieben, sind:

  • Sehr schnelle Bauzeiten
  • Geringen Speicherbedarf
  • Einfache und schnelle Durchquerung
  • Sehr einfache Konstruktion und Durchlauf-Algorithmen
  • Hoher numerischer Präzision bei der Konstruktion und Traversal
  • Flatter-Baumstruktur im Vergleich zu kd-Bäumen

Geschäftstätigkeit

Construction

Um jeden möglichen Raum Partitionierungsstruktur eine Form der Heuristik wird häufig verwendet, zu konstruieren. Aus diesem die Oberfläche Heuristik, die gemeinhin mit vielen Partitionierungsschemata verwendet werden, ist ein möglicher Kandidat. Eine andere, verein Heuristik ist die durch die nur erfordert eine Achse ausgerichtete Begrenzungsrahmen, anstatt den vollen Satz von Grundelementen, so dass es viel besser geeignet für eine schnelle Konstruktion beschrieben "global" Heuristik.

Die allgemeine Konstruktionsschema für ein BIH:

  • Berechnung der Szenenbegrenzungsrahmen
  • Verwendung einer Heuristik, um eine Achse und eine Teilungsebene Kandidaten senkrecht zu dieser Achse zu wählen
  • Sortieren der Objekte in der linken oder rechten Kind in Abhängigkeit von der Begrenzungsbox des Objekts
  • Berechnung der maximalen Begrenzungswert aller Objekte auf der linken und die minimale Begrenzungswert von denen auf der rechten Seite für diese Achse
  • zusammen mit 2 Bits die geteilten Achse in einem neuen Knoten kodiert speichern diese 2 Werte
  • fahren Sie mit Schritt 2 für die Kinder

Potenzielle Heuristiken für die Teilungsebene Kandidatensuche:

  • Klassische Musik: wählen Sie die längste Achse und die Mitte des Knotens Begrenzungsrahmen auf dieser Achse
  • Klassische Musik: wählen Sie die längste Achse und einer Trennebene durch den Median der Objekte
  • Globale Heuristik: wählen Sie die Trennebene auf Basis eines globalen Kriteriums in Form eines regelmäßigen Gitters
  • Fläche Heuristik: Berechnung der Oberfläche und Menge der Gegenstände für Kinder, über die Menge aller möglichen Trennebene Kandidaten, dann wählen Sie das mit den geringsten Kosten

Ray-Traversal

Die Durchquerung Phase ähnelt ein kd-Baum-Traversal: Man muss 4 einfachen Fällen zu unterscheiden, in denen die Strahlen

  • gerade schneidet die linke Kind
  • gerade schneidet die rechte Kind
  • schneidet sowohl Kinder
  • schneidet weder Kind

Für den dritten Fall, in Abhängigkeit von der Strahlrichtung des Bauteils gleich der geteilten Achse des aktuellen Knotens, fährt der Traversierung zuerst mit der linken oder rechten Nachfolger und der andere wird auf einen Stapel abgelegt.

Querung wird fortgesetzt, bis ein Blattknoten gefunden wird. Nach dem Schneiden der Gegenstände in dem Blatt, wird das nächste Element aus dem Stapelspeicher entnommen. Wenn der Stapel leer ist, wird der nächste Schnittpunkt aller bohrt Blätter zurückgegeben.

Es ist auch möglich, einen 5. traversal Fall hinzuzufügen, aber die auch erfordert eine etwas kompliziert Bauphase. Durch Vertauschen der Bedeutungen des linken und rechten Ebene eines Knotens, ist es möglich, auf beiden Seiten eines Knotens abgeschnitten leeren Raum. Dies erfordert ein zusätzliches Bit, die in dem Knoten gespeichert sind, um diesen besonderen Fall während dem Verfahren zu erfassen. Umgang mit diesem Fall, während der Durchquerung Phase ist einfach, wie der Strahl

  • gerade schneidet die einzige Kind des aktuellen Knotens oder
  • schneidet nichts

Immobilien

Numerische Stabilität

Alle Operationen während der Hierarchie Bau / Sortierung der Dreiecke sind min / max-Operationen und Vergleiche. Damit kein Dreieck Clipping ist zu tun, wie es der Fall bei kd-Bäume und ein Problem für die Dreiecke, die nur leicht einen Knoten kreuzen werden können werden. Selbst wenn das kd Umsetzung sorgfältig geschrieben werden, können numerische Fehler in einem nicht-detektierten Schnitt führen und damit Wiedergabefehler aufgrund der verpassten ray-Objektschnitt.

Erweiterungen

Anstelle der Verwendung von zwei Ebenen pro Knoten getrennte Geometrie ist es auch möglich, eine beliebige Anzahl von Ebenen verwenden, um eine n-äre BIH erstellen oder mehreren Ebenen einer binären Standard BIH zur besseren Objekttrennung zu erzielen.

(0)
(0)
Kommentare - 0
Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha