Übung 10: Bäume

[rainbow]

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.

[kain]

Hallo, ich hätte da auch eine Frage.

Langt es, wenn man in der ersten Aufgabe einfach nur das Bild einteilt?
Ist die Aufgabe erfüllt, wenn man nur zwei Folien mit den Abbildungen hat?

@rainbow

So wie ich das verstanden habe, muss man die Objekte sozusagen "einramen", indem man das Bild einteil.
Beim Kd-Tree sind die waagr. und senkr. linien frei wählbar, so das jedes Objekt zwischen den Linien ist.
Beim Quad-Tree muss der Abstand der waagr. und senkr. linien gleich sein. Hier hat man eher ein Raster.

Bin mir aber nicht sicher...

[Red*Star]

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

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

[rainbow]

@kain

Langt es, wenn man in der ersten Aufgabe einfach nur das Bild einteilt?
Ist die Aufgabe erfüllt, wenn man nur zwei Folien mit den Abbildungen hat?

Wir müssen noch die dazugehörigen Bäume hinmalen, würde ich mal sagen. Viel mehr aber nicht.

So wie ich das verstanden habe, muss man die Objekte sozusagen "einramen", indem man das Bild einteil.
Beim Kd-Tree sind die waagr. und senkr. linien frei wählbar, so das jedes Objekt zwischen den Linien ist.

Da bin ich mir auch unsicher, weil der englische und deutsche Wikipedia-Artikel sich an entscheidenden Stellen unterscheiden: Der deutsche teilt so, dass die Linien zwischen den Objekten sind, der englische so, dass die Linien die Objekte (=Punkte) gerade schneiden. (Guckt euch das mal an.)
Welche Version richtig ist? Keine Ahnung.

@red*star

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.

Ja, genau da liegt ja mein Problem! Theroetisch/mathematisch gesehen funktioniert das bei einem Kreis ja gar nicht, weil er eben nicht eckig ist und man durch Unterteilung mit Geraden in den Kästchen am Rand immer sowohl Punkte inner- und außerhalb des Objektes hat. Solang man die Anzahl der Unterteilungen nicht gegen unendlich laufen lässt, wird das also nichts.
Da wir nun Computer haben, wird man etwas früher fertig, nämlich wenn man das Bild bis auf die einzelnen Pixel runtergerastert hat. Das erscheint mir aber immer noch verdammt viel Arbeit.

Wo liegt der Denkfehler??

[oliver_g]

Hat sich erledigt, ist trotz der Unstimmigkeiten zwischen Folien und Übungsblatt wohl der k-d Tree gemeint. Wäre allerdings hilfreich, wenn man sich an eine Schreibweise halten würde und nicht alles wid durcheinandermischt.

[Gskill]

Bei 1.1 + 1.2 bin ich einfach hin, hab das Bild in Photoshop eingefügt, mit Hilfe von Linealen und Hilflinien knallhart an der Mitte einen Strich gezogen. Also bei der 1.1 einfach das Objekt in der Mitte senkrecht spalten, dann im linken Teil waagerecht spalten, dann wieder senkrecht, dann wieder waagerecht und fertig. Beim Quad-Tree einfach waagerecht und senkrecht mittig spalten, dann in einem dieser vier neuen Teilobjekte dasselbe nochmal - fertig.
Screenshot gemacht und in die Slides eingefügt.

Das müsste es eigentlich schon gewesen sein, allerdings hab ich das Gefühl, dass das zu leicht war. Doch wie der Kommilitone schon sagt: Wir sind hier nicht in FGdI ^^

Edit: Und von einem Unterteilungsbaum oder Pixelwertzuweisung ist nirgendwo in der Aufgabenstellung die Rede meine ich ^^

[rainbow]

Dann hast du aber noch nicht die eigentlichen Bäume. Oder hast du die dann noch extra gemacht? Was hast du beim Quadtree in die Knoten geschrieben? Schwarz/grau/weiß wie in den Folien geht ja dann nicht, aus den von mir schon genannten Gründen.

Vom Assistenten kam übrigens der Hinweis, die Folien vom letzten Jahr anzusehen, da da mehr drinsteht: http://www.mis.tu-darmstadt.de/node/9
Die zwei Folien, die es da mehr gibt, hatte ich aber vorher schon bei Wikipedia gefunden. Naja.

[kain]

So wie ich den HCS-Sprechstunde Tutor verstanden habe, soll man bei der 1 gar keine Bäume zeichnen, sondern einfach nur das Bild einteilen. So ganz sicher bin ich mir da aber auch nicht.

[Red*Star]

So wie ich das verstanden habe, muss man die Objekte sozusagen "einramen", indem man das Bild einteil.
Beim Kd-Tree sind die waagr. und senkr. linien frei wählbar, so das jedes Objekt zwischen den Linien ist.

Da bin ich mir auch unsicher, weil der englische und deutsche Wikipedia-Artikel sich an entscheidenden Stellen unterscheiden: Der deutsche teilt so, dass die Linien zwischen den Objekten sind, der englische so, dass die Linien die Objekte (=Punkte) gerade schneiden. (Guckt euch das mal an.)
Welche Version richtig ist? Keine Ahnung.

Es machen wohl beide Varianten Sinn, in Abhängigkeit vom Anwendungsbeispiel. Für eine hierarchische Raumunterteilung, an deren Blättern man die Objekte finden muss (nur das macht m.E. bei 3D-Grafik Sinn), ist die Variante mit den Trennern *zwischen* den Objekten zu nehmen. Da bin ich mir fast 100%ig sicher.

@red*star

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.

Ja, genau da liegt ja mein Problem! Theroetisch/mathematisch gesehen funktioniert das bei einem Kreis ja gar nicht, weil er eben nicht eckig ist und man durch Unterteilung mit Geraden in den Kästchen am Rand immer sowohl Punkte inner- und außerhalb des Objektes hat. Solang man die Anzahl der Unterteilungen nicht gegen unendlich laufen lässt, wird das also nichts.
Da wir nun Computer haben, wird man etwas früher fertig, nämlich wenn man das Bild bis auf die einzelnen Pixel runtergerastert hat. Das erscheint mir aber immer noch verdammt viel Arbeit.

Wo liegt der Denkfehler??

Hast du meinen Kommentar zu den \(\infty\)-Punkten des Kreises zu ernst genommen? Der Kreis ist [soweit ich das verstanden hab] eines von den Objekten, die am Ende in den Blättern des Baumes stehen sollen. Das ist das Problem mit diesen blöden Kanoniken: Es wird tonnenweise Stoff reingeballert, den dann am Ende niemand mehr versteht, weil er viel zu knapp abgefasst ist - bzw. weil die Begriffe vertauscht und verwurschtelt wurden. Die GdI2-Folien damals waren zwar nicht unbedingt begriffs-konsistenter, aber wenigstens etwas ausführlicher. Darin heißt der Quadtree, der mehr Ähnlichkeit mit der Variante hat, die *wir* [wahrscheinlich] erstellen sollen "Point-Quadtree". Ich hab die Folien trotzdem mal angehängt, vielleicht hilft es irgendwas beim Verständnis.
Wenn ich nicht ganz falsch liege, ist es so: Natürlich kann man einen Quad/Octtree auch für die Darstellung von Bildern benutzen, wie z.B. im dt. Quadtree-wikipedia-Artikel, aber da *hier* in der Übungsaufgabe kein endlich aufgelöstes Bild gemeint sein kann (für eine Übungsaufgabe ist eine Auflösung von 227x200 Pixel wohl ein *bisschen* viel Arbeit, wie du schon selbst bemerkt hast), sondern eine Raum-Szene, denke ich eher, dass du einen Quadtree zeichnen sollst, in dessen Blättern am Ende die Objekte vorkommen. Eventuell mit Doppelnennungen, falls eines in zwei oder mehr Quadranten vorkommt.

edit:
PS:
Folie 31 in
http://tahiti.mis.informatik.tu-darmsta ... peline.pdf
zeigt es ja doch ganz gut.

Und @Gskill:
Prinzipiell korrekt, was du da gemacht hast, würde ich sagen [genaueres werden wir dann Freitag erfahren ]. Aber ich denke, du solltest wirklich noch den Baum dazuzeichnen. Sicherheitshalber

[rainbow]

So etwa wie in der Folien vom alten Skript habe ich es jetzt auch gemacht. Trotzdem ist nicht richtig klar, wann man mit dem Unterteilen aufhört. Ich habe jetzt für mich die Regel genommen, dass ich nicht mehr weiter unterteile, sobald ein Rechteck zum größten Teil mit einem Objekt ausgefüllt ist (oder natürlich, wenn es leer ist). Damit habe ich aber immerhin schon eine Baumtiefe von 4, was den Baum ziemlich groß gemacht hat.

Finde es halt ungünstig, das als Entscheidungsregel zu bezeichnen: "...terminieren, sobald jeder Quadrant nur noch ein oder kein Objekt enthält", weil es eben einfach nicht funktioniert, sobald die Objekte nicht alle rechteckig sind. Und wie genau man dann in anderen Fällen einteilt, hätte man wirklich mal in den Folien anmerken können, so dass hier keiner raten muss.

[Gskill]

[...] Und wie genau man dann in anderen Fällen einteilt, hätte man wirklich mal in den Folien anmerken können, so dass hier keiner raten muss.

Willkommen in den ("Press-")Kanoniken ^^