search

MartinThoma / KIT-Musterloesungen

Musterlösungen für Klausuraufgaben am KIT
50 stars 30 forks source link

CG/2014-Hauptklausur, Aufgabe 6 #13

Open dudanueben opened 8 years ago

dudanueben commented 8 years ago

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

MartinThoma commented 8 years ago

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 :-)

dudanueben commented 8 years ago

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.

MartinThoma commented 8 years ago

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:

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.

fwinnen commented 8 years ago

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

dudanueben commented 8 years ago

Nimmt man die Folie 42 aus dem Foliensatz 5 steht dort:

Aufbau der Hierarchie

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.

AndreasSchmidt91 commented 8 years ago

Sollte Aussage 4 bei Aufgabe 6d nicht auch auf Octree zutreffen, immerhin ist das nichts anderes als ein "besseres" Gitter?