Für ein Seminar über Computergrafik habe ich einen Vortrag über Binary Space Partitioning (BSP) Trees gehalten. Hier finden sich alle Unterlagen dazu. In a seminar about computer graphics, I gave a talk about the usage of Binary Space Partitioning (BSP) Trees. This page contains the presentation slides and a short article about them. They (and the rest of this page) are written in German, but you may want to take a look at my demonstration program which is in English. The demo is released under a BSD licence (sorry, RMS).

Seminarunterlagen

Zusätzlich zur Seminarausarbeitung stelle ich hier noch meine Präsentation zur Verfügung. Ich decke zwei wichtige Anwendungen von BSP Trees ab: Hidden Surface Removal und Schattenberechnung (statisch und dynamisch). Wer einen ähnlichen Artikel oder Vortrag vorzubereiten hat, darf meine Materialien gerne als Referenz heranziehen.

In meinem Vortrag habe ich mich hauptsächlich mit BSP Trees zur Schattenberechnung beschäftigt. Da ich hierfür keine sinnvollen Demonstrationsprogramme gefunden habe, schrieb ich noch ein entsprechendes Programm in C++, das OpenGL mit GLUT verwendet, um den klassischen Algorithmus zum Hidden Surface Removal mit BSP Trees durchzuführen. Ebenso beherrscht das Programm Shadow Volume BSP Trees zur einfachen Berechnung von Schatten.

Das Programm steht unter einer BSD-Lizenz. Sie ist im Quelltext genauer beschrieben und erlaubt im Wesentlichen eine Nutzung für jeden Zweck, solange meine Urheberschaft erhalten bleibt. Ich möchte das Programm gerne allen Interessierten zur Verfügung stellen und hoffe, dass es zur Bereicherung eines Vortrages oder einer Seminararbeit beitragen kann.

Demo

Die Eiligen können das Programm schon mal herunterladen. Weiter unten gibt es noch ein paar Informationen und Bilder. Ich erhebe keinen Anspruch auf eine besonders realistische Darstellung, hoffe aber, den Geist der 1980er und 1990er Jahre eingefangen zu haben. You can download the program or read on for more information. I did not strive for realistic graphics, but hoped to capture the spirit of the 1980s and 1990s.
Bedienungshinweise für das Programm werden auf der Kommandozeile ausgegeben (auf Englisch). Eine kurze Erklärung zum Datenformat findet sich in der Seminarausarbeitung, im Quelltext sowie in den Beispieldaten selbst. Zum Kompilieren des Programms: Usage information is printed to the command-line. A short description about the data format is available within the source code and the data files. To compile the program:
  • GLUT installieren
  • make; ./bsp (FreeBSD, Linux)
  • make -f Makefile.mac; ./bsp (Apple)
Das Programm wird für Apple-Rechner ohne die Mausfunktionen kompiliert. Dies ist nötig, da sonst Fehler bei der Auswertung der Bewegungen auftreten würden. Hierbei handelt es sich meines Erachtens um einen Bug in der Implementierung von glutWarpPointer.
  • Install GLUT
  • make; ./bsp (FreeBSD, Linux)
  • make -f Makefile.mac; ./bsp (Apple)
For Apple computers, the mouse functions will be deactivated, because I got erroneous mouse movements otherwise. I think this is a bug in the implementation of glutWarpPointer.
1st screenshot for BSP demo 2nd screenshot for BSP demo