rainbow hat geschrieben:Meine Gruppe hat einige Schwierigkeiten mit den ersten beiden Übungsaufgaben. Die Informationen in den Folien sind ja mehr als dürftig.
Zunächst zwei Sachen, die ich schon den Assistenten per Mail gefragt habe, aber bisher keine Antwort habe:
- Aufgabe 1 zum k-d-Tree:
Ein Erklärung dazu findet sich auf den Folien leider nicht, daher habe ich Wikipedia bemüht:
http://en.wikipedia.org/wiki/Kd-tree
Das Vorgehen hier ist im Prinzip klar, die Frage ist nur: Wie funktioniert das, wenn meine Objekte keine Punkte sind (wie im Bsp auf Wikipedia), sondern Figuren wie in der Übung? Nimmt man einfach die Mittelpunkte und geht dann vor, als hätte man nur Punkte?
Oder geht es ganz anders?
- Aufgabe 2.1:
Was genau will man hier mit der Unterteilung erreichen?
In den Folien wird ein nichtkonvexes Polygon solange unterteilt, bis man eine Partitionierung aus konvexen Teil-Polygonen hat. Dann kann man den Painters-Algorithmus anwenden.
Wie ist das jetzt in er Übung? Was ist hier das nichtkonvexe Objekt, das wir erst zerlegen sollen?
----------------------
Noch zu 1:
Ich will gerade den Quadtree konsturieren, und dabei ist mir aufgefallen, dass das doch hier gar nicht so funktionieren kann wie in den Folien. Wenn ich runde Objekte habe, muss ich ja bis auf Pixelebene runter zerteilen, bis ich jedem Quadrat eindeutig schwarz oder weiß zuordnen kann.
Das kann doch nicht der Sinn der Aufgabe sein??
Übrigens ist die Abbildung nicht quadratisch. Quadrate gibts also schonmal gar nicht. Soll mir ja egal sein, ich komme auch mit Rechtecken klar. Nur stiftet das wieder unnötig Verwirrung.
Kann mir irgendjemand einen Tipp zu dem Haufen Probleme geben? Ich wäre hocherfreut.

Ok, ich versuch's mal:
@ kd-Tree: Wir sind hier in HCS, nicht in FGdI, also würde ich mal sagen, mach es [zwar nicht Pi mal Daumen, aber doch] einfach intuitiv: Das Beispiel ist nämlich m.E. (hab jetzt nicht nachgemessen) sogar so gemacht, dass man die Raumunterteilungs-Grenzen genau so legen kann, dass sie die Bounding Boxes der Objekte überhaupt nicht berühren, also entfällt das Problem mit den Mittelpunkten - zumindest wenn man mit einer Unterteilung in x-Richtung startet.
Einer alternative Antwort: Wenn du es genau nimmst, besteht ein 3D-Objekt im Computer immer aus Punkten (und Linien... und Polygonen... also auf jeden Fall aus sehr eckigen und punktartigen Gebilden), zumindest in heutigen Grafikkarten, also kannst du einfach die Objekte durch eine minimale Anzahl an Punkten definieren und dann den Tree konstruieren. Beim Kreis... nun ja, die minimale Punktzahl wäre eigentlich
\(\infty\)... da entsteht also u.U. auf diese Weise ein Problem
Wenn du eine verbindliche Antwort willst, warte aber lieber auf die eMail vom Assistenten.
@ Painters Algorithm: Wenn man den von den Folien nimmt, dann frage ich mich ehrlich gesagt auch, wieso die Aufgabe so explizit auf den BSP-Tree Bezug nimmt - schließlich ist [m.E.] der Painters Algorithm von der Art und Weise der Raumunterteilung völlig unabhängig: Es geht ja nur um die z-Werte der Polygone. Das einzige "Problem" ist eventuell, dass in diesem Beispiel alle Polygone, da man von vorne auf sie schaut, zu Linien entarten... sprich der Output sähe von dem Viewpoint aus recht langweilig aus.
@ BSP tree: Der ist nicht an konvexe Polygone gebunden. Du kannst jeden beliebigen Raum unterteilen, auch den
\(\mathbb{R}^2\). Siehe z.B.
http://de.wikipedia.org/wiki/Binary_Space_Partitioning
@ Quadtree: Wir hatten das damals in GdI2... ist aber offenbar aus dem Stoff rausgefallen, sonst wüsstest du das ^^: Der Name "Quad" kommt nicht von Quadrat, sondern daher, dass man im 2-Dimensionalen den Raum in 4 Teile (Rechtecke) einteilt. Im 3-Dimensionalen wird er so logischerweise zum "Oct"-Tree, wegen der 8 Teile (Quader).
wikipedia hat geschrieben:Ein Quadtree ist in der Informatik eine spezielle Baum-Struktur, in der jeder innere Knoten vier Kinder haben kann. Das Wort Quadtree leitet sich von der Zahl der Kinder eines inneren Knotens ab (quad (vier) + tree (Baum) = Quadtree).
Desweiteren geht es hier wohl, wenn ich das richtig verstanden habe, auch wieder nur um die Unterteilung. Du sollst gar keine Pixel einfärben, sondern terminieren, sobald jeder Quadrant nur noch ein oder kein Objekt enthält. (Aber ohne Anspruch auf Korrektheit.)