CG/2014-Nachklausur, Aufgabe 8d about kit-musterloesungen

[MartinThoma]

Ich bin mir nicht ganz sicher, wie Gitter funktionieren. Bisher habe ich mir das so vorgestellt:

1. Gegeben ist eine Szene
2. Man schaut sich die AABB der Szene an und unterteilt sie in z.B. fix 100 Teile pro Achse.
3. Für jede Zelle hat man eine Liste an pointern, die auf die Objekte zeigen welche dort drin sind.

Ist das so richtig?

Falls ja, würde ich sagen Gitter sind wegen (2) an die Geometrie angepasst.

[StephanGocht]

In 2D hat man einfach ein einfach kästchenpapier und darauf dreiecke. Für jedes kästchen merkt man sich welche dreiecke dort sind: Das kästchen liegt komplett im Dreieck oder eine Kante schneidet das Kästchen. U.u. ist eine genaue prüfung zu aufwändig dann kann man (optional) auch die AABB anschauen statt dem Dreieck. Dann ist leichter zu entscheiden ob das dreieck im kästchen ist oder nicht. In beiden Fällen ändert sich aber nicht die Struktur des Gitters in abhängigkeit von den Dreiecken.

Das wäre nur bei adaptiven Gittern der Fall: dort würde man feststellen mäh innerhalb des einen Kästchen sind immernoch zu viele dreiecke, lasst nochmal feiner unterteilen -> Ein Kästchen was wie milimeterpapier aussieht und damit noch kleinere kästchen hat. Das wäre dann adaptiv.

[s-bach]

@MartinThoma: Ja, ich stimme dir zu.
Folie 77 deutet jedoch an, dass man verschachtelte Gitter braucht um "adaptiv" zu sein und ein reguläres Gitter ist kein verschachteltes Gitter.
Ich denke da wird nicht so genau hin geguckt, sondern eher vergleichend betrachtet.
Ich vermute, man kann sagen das die Adaptivität bei einem regulären Gitter nicht größer als ohne räumliche Datenstrukturen ist.

[matthiasplappert]

Habe bei dieser Teilaufgabe auch eher an reguläre Gitter gedacht, und diese sind definitiv nicht adaptiv. Ist aber, wieder einmal, nicht eindeutig gestellt, welche Gitter nun gemeint sind.