KIT-Musterloesungen
KIT-Musterloesungen copied to clipboard
MartinThoma
CG/2014-Hauptklausur, Aufgabe 6
Bei der Aufgabe 6c sind mir zwei Punkte aufgefallen die glaube ich nicht so stimmen.
Aussage 2 ist Falsch, da bei einer BVH die Dreiecke immer nur in maximal einem Blatt enthalten sind. Somit werden sie maximal einmal getestet und kein Mailboxing ist notwendig.
Aussage 3 ist Falsch. Zumindest habe ich keine Aussage zum Speicherbedarf gefunden. Die Anzahl der nötigen Schnitttests hängt jedoch logarithmisch von der Anzahl der Primitve ab. vgl. Foliensatz 5 Folie 48.
Aufgabe 6d:
Aussage 3 trifft auch auf BVHs zu. vgl. Folie 98
Aussage 2 ist Falsch, da bei einer BVH die Dreiecke immer nur in maximal einem Blatt enthalten sind.
Ich bin mir zu 80% sicher, dass BVHs auch ein Objekt in mehreren Blättern zulassen. Siehe z.B. Folie 47.
Aussage 3 ist Falsch. Zumindest habe ich keine Aussage zum Speicherbedarf gefunden. Die Anzahl der nötigen Schnitttests hängt jedoch logarithmisch von der Anzahl der Primitve ab. vgl. Foliensatz 5 Folie 48.
Oh... "Speicheraufwand", nicht "rechenaufwand". Fies. Wie hoch ist dann der Speicheraufwand?
Aussage 3 trifft auch auf BVHs zu. vgl. Folie 98
Danke, ich habs gerade behoben :-)
Ich bin mir zu 80% sicher, dass BVHs auch ein Objekt in mehreren Blättern zulassen. Siehe z.B. Folie 47.
Mh auf Folie 47 sind alle Primitive in einem eigenen Knoten. Man sieht zwar, dass sich die Hüllkörper räumlich überschneiden, aber da der BVH nicht den Raum unterteilt sondern die Primitive sind die beiden Dreiecke in der Mitte (wie auch im Baum zu sehen) jeweils nur in einem der beiden Hüllkörper und somit jeweils nur einem Blatt enthalten.
Edit: Folie 47 zeigt, dass die räumliche Überschneidung dazu führt, dass man nicht den richtigen Schnitt als erstes findet.
Oh... "Speicheraufwand", nicht "rechenaufwand". Fies. Wie hoch ist dann der Speicheraufwand?
Zum Speicheraufwand habe ich nichts in den Folien und auch nichts bei einer kurzen Netzrecherche gefunden. Also keine Ahnung so ziemlich. Vermutlich war das eine Trickfrage.^^
Edit: Nach nem bisschen Nachdenken: Da die BVH durch einen Binärbaum dargestellt wird, dürfte der Speicheraufwand wohl der selbe sein wie für einen Binärbaum. Weiß nur gerade nicht mehr wie der war.
Ok, gehen wir es mal durch:
Wie ist die Laufzeitkomplexität eines Schnittests mit einer optimalen BVH mit n Primitiven?
Wir haben BVHs als Binärbäume durchgenommen. Wie man in den Folien sieht können sich die Hüllkörper überschneiden. Die Frage ist also, wie das im worst case aussieht. Dazu habe ich mal versucht einen schweren Fall zu konstruieren: https://github.com/MartinThoma/KIT-Musterloesungen/tree/master/CG/Fragen/BVH
Ich bin mir aber nicht mal sicher, ob das wirklich ein schwerer Fall ist, da die inneren Dreiecke ja nur von rechts unten aus sichtbar sind...
Die Frage ist also schwer zu beantworten.
Wieviel Speicher benötigt ein optimaler BVH mit n Primitiven?
Ich glaube das läuft im Grunde auf die Frage hinaus, wie viel speicher man braucht um n Objekte in einem ausbalancierten Binärbaum zu speichern:
- n Objekte (bzw. refernzen zu n Objekten)
- Innere Knoten: Jeder innere Knoten hat 2 Kinder. Es gibt n-1 innere Knoten. Daher kommt hier 2*(n-1) hinzu
- => 2n -2 + n = 3n => Linearer Speicherplatzbedarf.
edit: Jeder innere Knoten benötigt natürlich noch die Geometrie des Hüllkörpers. Nehmen wir mal AABBs an, da ist es pro innerer Knoten eine Konstante. Ändert also nichts an der Linearität.
Noch mal zu BVH:
Übungsfolien 3, p3-6: Da steht dass die Unterteilung <= und >= wäre, was sich auf den Mittelpunkt der AABB bezieht. Aus dem Gefühl hätte ich aber auch gesagt, dass es keinen Sinn macht ein Object in zwei Knoten zu haben, da ja jeder Strahl sowieso durch beide AABBs der potentiellen Kindknoten geht.
Gruß, Fabian
Nimmt man die Folie 42 aus dem Foliensatz 5 steht dort:
Aufbau der Hierarchie
- bestimme die Bounding Box der Objekte
- teile die Objekte in zwei Gruppen auf
- verfahre so rekursiv weiter (z.B. bis nur noch m Objekte in jeder Gruppe enthalten sind, hier m = 1)
Da hier Objekte in Gruppen sortiert werden ist jedes Primitiv/Objekt nur in einer der Gruppen enthalten und wird somit maximal einmal auf einen Schnitt überprüft. Somit ist kein Mailboxing nötig (was ja die Frage war) :).
Bei deinem Beispiel musst du bedenken, dass der Strahlursprung auch zwischen deinen Primitiven platziert sein kann. Also beispielsweise irgendwo zwischen dem rosa dem dunkelgrün und dem roten. Wie jetzt die optimale/richtige Aufteilung in in eine BVH ist, hängt auch von der Wahl des Unterteilungskriteriums also beispielsweise SAHs oder Object-Median.
Sollte Aussage 4 bei Aufgabe 6d nicht auch auf Octree zutreffen, immerhin ist das nichts anderes als ein "besseres" Gitter?
