Comments (6)
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 :-)
from kit-musterloesungen.
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.
from kit-musterloesungen.
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.
from kit-musterloesungen.
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
from kit-musterloesungen.
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.
from kit-musterloesungen.
Sollte Aussage 4 bei Aufgabe 6d nicht auch auf Octree zutreffen, immerhin ist das nichts anderes als ein "besseres" Gitter?
from kit-musterloesungen.
Related Issues (20)
- CG/2013-Nachklausur Aufgabe 5a Mailboxing HOT 2
- CG/2016-Hauptklausur Aufgabe 6 a) Punkt 7
- Nachklausur2016 Aufgabe6
- CG/2012-Hauptklausur Aufgabe 1b
- CG/2016-Nachklausur, Aufgabe 3 d) HOT 1
- CG/2016-Hauptklausur, Aufgabe 6 a)
- CG/2013-Nachklausur Aufgabe 9a HOT 1
- CG/2013-Nachklausur Aufgabe 7c HOT 1
- CG/2014-Nachklausur Aufgabe 8 HOT 3
- CG/2014-Nachklausur Aufgabe 10 HOT 2
- CG/2011-Hauptklausur Aufgabe 3c
- CG/2013-Nachklausur Aufgabe 6b
- CG/2013-Nachklausur Aufgabe 8 1. Punkt
- CG/2015-Hauptklausur Aufgabe 6 falsch
- CG/2011-Nachklausur Aufgabe 1d)
- CG/2015-Nachklausur Aufgabe 4b (Tippfehler) HOT 1
- CG/2015-Nachklausur Aufgabe 4c HOT 2
- CG/2015-Hauptklausur Aufgabe 5 c (4) HOT 3
- cg/Hauptklausur 2012, Aufgabe 8 HOT 1
- CG/2013-Nachklausur Aufgabe 1 - Schattenstrahlen
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from kit-musterloesungen.