Frage zum Quadtree Prüfungs-Beispiel

[Heavy]

Also wie funktioniert das Beispiel???
Das Bsp. vom Skript hab ich verstanden...aber wie soll ich das Gebilde des PO-Beispiels in ein Quadtree-Baum umsetzen??

In der Angabe steht noch drin dass der Raster nicht dazugehört, also muss ich die weiße Flächen weglassen?! :confused:

Übrigens wie zählt man die Quadranten? Von 0 oder 1 beginnend?
Im Skript steht aber von 0-3....

[MichiK]

Am besten, wenn das Bsp zur Prüfung kommt, schreibst du einfach dazu, wie du die Quadranten zählst. ob links herum oder rechtsherum, oder mit ABCD, oder 0123, oder 1234 bleibt dir überlassen. Nur dazuschreiben sollte man es.

[Kuschelmaus]

also zumindest den punkt a) hab ich so verstanden:

ich teil amal des ganze in vier quadranten. dann schau ich ma jeden quadranten einzeln an. wenn schwarze und weiße felder vorhanden sind, muß ich weiter teilen, also wieder durch vier. erst wenn ein quadrant ganz schwarz is, muß ich nicht weiter teilen und kann den quadrant in meiner liste schwarz anmalen. wenn ma fertig is entsteht dann so ein baum.

hm, kann das wer nachvollziehn? und wenn ja, is auch richtig? :p

[Kenny]

also ich muss ganz stolz sagen, das QUADTREE is das einzige, was ich bis jetzt von den testfragen verstanden hab und lösen konnte!

du teilst einfach immer rekursiv in immer kleinere quadrate auf, und schaust dabei wo welche schwarz sind:

dh im ersten schritt

1 2 3 4 (oder wie auch immer du sie nummerierst)

wenn im 1, also zb das linke obere viertl der figur, schwarze vorkommen, musst dieses viertl weiter aufteilen

also pfeil vom 1 runter zum nächsten level, wieder:

1 2 3 4

wenn jetzt im linken oberen viertel des linken oberen noch mehr details sind und darin noch ein schwarzes vorkommt, musst noch eine stufe weiteraufteilen

die quadranten die komplett weiß sind, sind immer schon fertig, du brauchst nur weiter aufteilen wenn schwarze vorkommen

das is eigentlich schon alles dazu.. recht simpel :)


@ kuschelmaus hast du das z-buffer bsp schon verstanden, siehe meine frage im anderen thread... ??

[leadpen]

Soda, hab das mal durchgemacht:
Die Reihenfolge der Quadranten ist:

12
34

Ich bräuchte Hilfe beim 2D-CSG Baum (hab null Ahnung wie sowas geht, aus dem Buch und den Folien werd ich nicht schlau).

lG, leadpen

[Kenny]

stimmt, wie der CSG baum funktioniert hab ich auch nüsse ahnung !?

[12gauge]

Also ich hab das CSG Bsp probiert. Siehe Grafik.
Gibts dazu eigentlich einen Algorithmus wie man am besten vorgeht, oder vertraut man auf die eigene Intuition?
Meine Lösung beruht auf Intuition *gg*

mfg, 12gauge

[Kenny]

kannst du bitte kurz erklären, worums da überhaupt geht und wie man das macht?
(ruhig auch nur mit intuition, intuition is immer gut)

hab nämlich noch +überhaupt keine ahnung von dem kapitel leider..

[12gauge]

Du versuchst mittels möglichst weniger Quadrate und der Mengenoperationen (Vereingung, Schnitt etc.) die vorgegebene Figur nachzubauen...allerdings hab ich das vollkommen intuitiv gemacht...verbrauchen einige der Berechnungen mehr und andere weniger Rechenleistung? Sind diverse Operationen vorzuziehen? Ist die Größe der Quadrate Relevant?
Könnte mal MichiK oder sonst wer eine kleine Erläuterung, oder zumindest ein "stimmt/stimmt nicht" abgeben?

[magic7]

@12gauge:

Meine Lösung gleicht Deiner ziemlich, habe nur ein paar Sachen
in anderer Reihenfolge. Ich denke auch, dass das so funktioniert.

Einziges Problem: in der Angabe steht "minimale" Endknoten!
Wir haben beide 11 Stk., doch ohne definitiven Algorithmus ist
es Zufall (äh, natürlich geniales konstruieren), den minimalen
Fall zu erwischen!
:ausheck:
Noch eine Idee?

Liebe Grüße
-Markus

--
Markus Proske
proske@vmars.tuwien.ac.at

[wolk]

@12gauge

in deiner grafik glaub ich ist auf der rechten seite ein fehler
und zwar dürfen die endknoten nur quadrate sein -> bei dir ist aber ein rechteck dabei
7/8 9/4 ist kein quadrat

glaub ich jedenfalls

[12gauge]

Mein Fehler ... da gehört natürlich (7/2) (9/4) hin...sorry

[wolk]

FRAGE:

CSG-Baum
nach Intuition oder nach Algorithmus ?

wenn nach Algorithmus -> nach welchem ? um die "minimalen" endknoten zu erhalten

mfg wolk

[Stoefln]

Auch wenns jetzt schon 2 jahre her ist:
Hat noch irgendwer rausgefunden wie man einen CSG-BAum mit min. Knotenanzahl erhält?