Partitionierung des binären Raums: Erkundung der binären Raumpartitionierung: Grundlagen und Anwendungen in der Bildverarbeitung

Von Fouad Sabry

Was ist binäre Raumpartitionierung

In der Informatik ist die binäre Raumpartitionierung (BSP) eine Methode zur Raumpartitionierung, die einen euklidischen Raum mithilfe von rekursiv in zwei konvexe Mengen unterteilt Hyperebenen als Partitionen. Durch diesen Unterteilungsprozess entsteht eine Darstellung der Objekte im Raum in Form einer Baumdatenstruktur, die als BSP-Baum bekannt ist.

Ihr Nutzen

(I) Einblicke und Validierungen zu den folgenden Themen:

Kapitel 1: Binärraumpartitionierung

Kapitel 2: Binärbaum

Kapitel 3: Rendering (Computergrafik)

Kapitel 4: Scanline-Rendering

Kapitel 5: Bestimmung verdeckter Oberflächen

Kapitel 6: Quadtree

Kapitel 7: Octree

Kapitel 8: Raumpartitionierung

Kapitel 9: K-d-Baum

Kapitel 10: Clipping (Computergrafik)

( II) Beantwortung der häufigsten öffentlichen Fragen zur Partitionierung des Binärraums.

(III) Beispiele aus der Praxis für die Verwendung der Partitionierung des Binärraums in vielen Bereichen.

Wer dieses Buch ist für

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über das Grundwissen oder die Informationen für jede Art der binären Raumpartitionierung hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 4. Mai 2024

Buchvorschau

Kapitel 1: Partitionierung des binären Speicherplatzes

Binary Space Partitioning (BSP) ist eine Methode zur Raumaufteilung in der Informatik, bei der ein euklidischer Raum rekursiv in zwei konvexe Mengen unterteilt wird, wobei Hyperebenen als Partitionen verwendet werden. Diese Vorgehensweise erzeugt eine Repräsentation von Objekten innerhalb des Raums in Form eines BSP-Baums, einer baumartigen Datenstruktur.

1969 wurde die binäre Raumaufteilung im Kontext der 3D-Computergrafik entwickelt. Die Erkennung von Kollisionen in der Robotik und in 3D-Videospielen, Raytracing und andere Anwendungen, bei denen es um die Manipulation komplizierter räumlicher Situationen geht.

Der generische Prozess, bei dem eine Szene rekursiv in zwei Teile aufgeteilt wird, bis die Partitionierung eine oder mehrere Anforderungen erfüllt, wird als binäre Speicherpartitionierung bezeichnet. Es kann als eine Verallgemeinerung anderer räumlicher Baumstrukturen betrachtet werden, wie z. B. k-d-Bäume und Quadtrees, in denen die Hyperebenen, die den Raum unterteilen, nicht an den Koordinatenachsen ausgerichtet sind. In der Computergrafik werden beim Rendern von Szenerien aus planaren Polygonen die Trennebenen in der Regel so gewählt, dass sie mit den Ebenen übereinstimmen, die durch die Polygone in der Szene definiert sind.

Die genaue Auswahl der Partitionierungsebene und die Kriterien für das Stoppen des Partitionierungsprozesses variieren je nach Verwendungszweck des BSP-Baums. Beim Rendern von Computergrafiken wird die Szene beispielsweise so lange unterteilt, bis jeder Knoten des BSP-Baums nur noch Polygone enthält, die in beliebiger Reihenfolge gezeichnet werden können. Wenn Back-Face-Culling verwendet wird, hat jeder Knoten eine konvexe Menge von Polygonen, aber beim Rendern von doppelseitigen Polygonen enthält jeder Knoten des BSP-Baums nur ebenenbasierte Polygone. Bei der Kollisionserkennung oder Raytracing kann eine Szene in Primitive unterteilt werden, für die Kollisions- oder Strahlenschnitttests einfach sind.

Die Computergrafik erforderte die Partitionierung des binären Raums, um schnell dreidimensionale Szenen aus Polygonen zu rendern. Der Algorithmus des Malers erzeugt Polygone in der Reihenfolge des Abstands vom Betrachter, von hinten nach vorne, und übermalt den Hintergrund und vorherige Polygone mit jedem Objekt, das dem Betrachter näher ist. Diese Methode hat zwei Nachteile: die Zeit, die benötigt wird, um Polygone in umgekehrter Reihenfolge zu sortieren, und die Wahrscheinlichkeit von Fehlern in Polygonen, die sich überlappen. Fuchs und Co-Autoren zeigten, dass die Konstruktion eines BSP-Baums diese beiden Probleme löste, indem er eine schnelle Methode zum Sortieren von Polygonen in Bezug auf einen bestimmten Blickwinkel (linear in der Anzahl der Polygone in der Szene) bereitstellte und überlappende Polygone unterteilte, um Fehler im Zusammenhang mit dem Painter-Algorithmus zu vermeiden. Ein Nachteil der Binärraumpartitionierung ist die Zeit, die für die Generierung eines BSP-Baums benötigt wird. Vor dem Rendern oder anderen Echtzeitoperationen in einer Szene wird es daher in der Regel einmal auf statischer Geometrie als Vorberechnungsphase durchgeführt. Das direkte Verschieben von Objekten in einen Baum ist aufgrund der Kosten für die Erstellung eines BSP-Baums schwierig und ineffizient.

BSP-Bäume werden häufig in 3D-Videospielen verwendet, insbesondere in Ego-Shootern und Titeln mit Indoor-Umgebungen. Doom (id Tech 1), Quake (id Tech 2 Variante), GoldSrc und Source sind Spiele-Engines, die BSP-Bäume verwenden. In ihnen werden BSP-Bäume, die die statische Geometrie der Szene enthalten, häufig in Verbindung mit einem Z-Puffer verwendet, um bewegliche Elemente wie Türen und Charaktere korrekt in die Hintergrundszene einzublenden. Die binäre Raumpartitionierung erleichtert zwar das Speichern und Abrufen von räumlichen Informationen über die Polygone einer Szene, löst jedoch nicht das Problem der Bestimmung der sichtbaren Oberfläche.

Die Standardanwendung eines BSP-Baums besteht darin, doppelseitige Polygone ohne Back-Face-Culling mit der Painter-Methode zu rendern. Jedes Polygon hat eine Vorder- und eine Rückseite, die frei gewählt werden können und sich nur auf die Struktur des Baumes auswirken, nicht auf das gewünschte Ergebnis.

Wählen Sie ein Polygon aus der Liste P aus.

Fügen Sie P zur Liste der Polygone am Knoten N im BSP-Baum hinzu.

Für jedes zusätzliche Polygon in der Liste:

Wenn sich dieses Polygon vollständig vor der Ebene befindet, die P enthält, fügen Sie es der Liste der Knoten vor P hinzu.

Wenn sich dieses Polygon vollständig hinter der Ebene befindet, die P enthält, fügen Sie es der Liste der Knoten hinter P hinzu.

Wenn das Polygon von der Ebene gekreuzt wird, die P enthält, teilen Sie es in zwei Polygone und fügen Sie sie zu den Listen der Polygone hinter bzw. vor P hinzu.

Fügen Sie dieses Polygon der Liste der Polygone am Knoten N hinzu, wenn es in der Ebene mit P liegt.

Wenden Sie dieses Verfahren auf die Polygonliste vor P an.

Wenden Sie diese Methode auf die Polygonliste hinter P an.

Dieses Diagramm zeigt, wie dieser Ansatz verwendet werden kann, um eine Liste von Linien oder Polygonen in einen BSP-Baum umzuwandeln. Bei jedem der acht Schritte (i.-viii.) wird die vorhergehende Methode auf die Liste der Zeilen angewendet, und ein neuer Knoten wird dem Baum hinzugefügt.

Da Linien oder Polygone, die die Partitionierungsebene kreuzen, in zwei Teile geteilt werden müssen, ist die endgültige Anzahl von Polygonen oder Linien in einer Struktur häufig größer (und manchmal erheblich größer) als die ursprüngliche Liste. Es ist vorzuziehen, dieses Wachstum zu begrenzen und gleichzeitig ein faires Gleichgewicht im endgültigen Baum zu erhalten. Die Entscheidung, welches Polygon oder welche Linie als Partitionierungsebene verwendet werden soll (in Schritt 1 der Methode), ist entscheidend für die effektive Erstellung eines BSP-Baums.

Ein BSP-Baum wird in linearer Zeit durchlaufen, und zwar in einer Reihenfolge, die durch die spezifische Funktion des Baums vorgegeben ist. Um das Polygon P am Beispiel des Renderns doppelseitiger Polygone mit der Malertechnik angemessen zu erstellen, müssen zuerst alle Polygone hinter der Ebene, in der P liegt, gezeichnet werden, gefolgt von Polygon P und schließlich Polygone vor P. Wenn alle Polygone in einer Szene dieser Darstellungsreihenfolge entsprechen, wird die Szene in der richtigen Reihenfolge gerendert. Mit dem folgenden Algorithmus kann diese Vorgehensweise durch iteratives Durchlaufen eines BSP-Baums realisiert werden. Rendern Sie von einem gegebenen Standpunkt V aus einen BSP-Baum, Wenn der aktuelle Knoten ein Blattknoten ist, zeichnen Sie die Polygone des aktuellen Knotens.

Wenn sich die Anzeigestelle V vor dem aktuellen Knoten befindet, fährt der Algorithmus fort:

Rendern Sie den polygonhaltigen, untergeordneten BSP-Baum hinter dem aktuellen Knoten.

Rendern von Polygonen, die sich am aktuellen Knoten befinden

Rendern Sie den polygonhaltigen untergeordneten BSP-Baum vor dem aktuellen Knoten.

Wenn sich der Betrachtungsort V hinter dem aktuellen Knoten befindet:

Rendern Sie den polygonhaltigen untergeordneten BSP-Baum vor dem aktuellen Knoten.

Rendern von Polygonen, die sich am aktuellen Knoten befinden

Rendern Sie den polygonhaltigen, untergeordneten BSP-Baum hinter dem aktuellen Knoten.

Ist dies nicht der Fall, muss die Betrachtungsposition V genau auf der Ebene liegen, die mit dem aktuellen Knoten verbunden ist. Dann:

Rendern Sie den polygonhaltigen untergeordneten BSP-Baum vor dem aktuellen