Binary Space Partitioning
Konzept
In der Informatik ist die binäre Raumaufteilung (BSP) eine Methode zur Raumaufteilung, bei der ein euklidischer Raum rekursiv in zwei konvexe Mengen unterteilt wird, indem Hyperebenen als Partitionen verwendet werden. Dieser Unterteilungsprozess führt zu einer Darstellung von Objekten innerhalb des Raums in Form einer Baumdatenstruktur, die als BSP-Baum bezeichnet wird.
Die binäre Raumaufteilung wurde 1969 im Zusammenhang mit 3D-Computergrafik entwickelt. Die Struktur eines BSP-Baums ist beim Rendering nützlich, da sie auf effiziente Weise räumliche Informationen über die Objekte in einer Szene liefern kann, z. B. die Anordnung der Objekte von vorne nach hinten in Bezug auf einen Betrachter an einem bestimmten Ort. Weitere Anwendungen von BSP sind: geometrische Operationen mit Formen (konstruktive Festkörpergeometrie) im CAD, Kollisionserkennung in der Robotik und in 3D-Videospielen, Raytracing und andere Anwendungen, die den Umgang mit komplexen räumlichen Szenen erfordern.