Subdivision "odd" und "even"

[barnie]

Mal abgesehen davon, dass mir aus der einen Folie zu dem Thema nicht klar wird, woher die Gewichte des Loop-Algorithmus kommen könnten, stellt sich mir eine noch etwas essenziellere Frage: Worauf bezieht sich hier "odd" und "even"? Falls es sich um eine Nummerierung handelt, dann würde mich interessieren, wie hier die Nummern gewählt werden und was in diesem Fall überhaupt einen geraden von einem ungeraden Knoten so unterscheidet, dass man ihn derart unterschiedlich behandeln muss. Auch würde mich interessieren, ob sich das "odd" und "even" auf einen existierenden Knoten bezieht oder auf einen neu einzufügenden und was im "odd" Fall passiert (der "even"-Fall ist ja rechts unten im Bild dargestellt, oder ist das etwa beides?)

Wo man das mit dem "Box"-Spline her wissen soll, weiß ich auch nicht. Ich dachte der Loop-Algorithmus konvergiert auf einen quadratischen B-Spline oder war das Chaikin? Fragen über Fragen... Mit der Subdivision-Aufgabe komme ich jedenfalls überhaupt nicht klar. Wo in den Folien steht was von Boehm? (Ja in den Zeilfelderfolien steht was davon, das ist immerhin mehr als nichts.)

(Ich hab mich damit jetzt heute schon ungefähr 4-5 Stunden auseinandergesetzt und als nächstes würde ich die Thesis von Loop lesen, die ist aber ein bissel lang - da lese ich am Mittwoch Abend noch.)

[thomas_kalbe]

Hallo,

mit even sind hier die Vertices des Ursprungnetzes gemeint, mit odd die neu eingefügten.
Auf der unteren Abbildung sind die even Vertices diejenigen mit Exponent k,
die odd's sind die mit Exponent k+1.
Das Loop-Verfahren fügt in jedem Schritt neue Vertices ein (die odd's), verschiebt aber auch gleichzeitig
die alten nach der angegebenen Formel (even).
In der unteren Abbildung sieht man übrigens links das Netz vor dem Subdivision-Schritt, rechts nach dem
Subdivision-Schritt, am Beispiel eines regulären Vertex.
Auf der nächsten Folie sind dann noch die Schritte, die bei der Verfeinerung mit Wurzel(3) durchgeführt werden,
zu sehen.
Dass die Positionen der alten Vertices ebenfalls modifiziert werden, ist bei den meisten Subdivision-Verfahren der Fall.
Siehe z.B. die Folie vor loop-Subdivision, wo das tetraederartige Gebilde unterteilt wird. In a) ist die Ursprungsversion
zu sehen, in d) nach diversen Unterteilungsschritten.

Knoteneinfügen für Splines war auch auf den Splinefolien irgendwo, der Name Boehm fiel aber nicht --
er hat diesen Algorithmus entdeckt:
--> http://www.amueller.de/wb/

Die Aufgabe ist aber eigentlich "self-contained", alle benötigten
Formeln stehen schon da, man muss sie nur richtig anwenden sowie die Angaben "äquidistant", "quadratisch"
und "in der Mitte des Knotenintervalls" richtig deuten. Die Formeln für den Randfall können wir getrost ignorieren,
da die Kurve geschlossen ist.

Also:
\(\alpha_i = (t-t_i) / (t_{i+n} - t_i)\)

Da die Information, dass n den Grad darstellt und dieser quadratisch ist, gegeben war erhalten wir
im Zähler t_i+2 - t_i
Jetzt noch die Information genutzt, dass der Knotenvektor äquidistant ist, können wir diese Distanz z.B. dx nennen:
t_i+1 - t_i = dx, für alle i.
Damit t_i+2 - t_i = 2dx.

Im Nenner setzen wir t in der Mitte des Knotenintervalls ein (war als Information gegeben), und erhalten
somit für t - t_i = 1/2 dx.

Jetzt: (1/2dx) / 2dx = (1/2) / 2 = 1/4.

Dies in die Formel für die d_i hoch Sternchen eingesetzt erhalten wir genau die Gewichte.
qed.

Loop führt - bei regulären vertices - übrigens im Limit auf einen quartischen, C^2-stetig differenzierbaren Box-Spline.
Quadratisch ist falsch.

Woher die Gewichte kommen können, sollte gerade die Übungsaufgabe am sehr einfach nachzuvollziehenden
Chaikin demonstriert werden. Geht dann für andere Verfahren auf ähnliche Weise, nur komplizierter.



In der Klausur wird übrigens allgemein auch recht viel zeichnerisch konstruiert und nicht unbedingt irgendwelche
Indizes bis ins letzte Detail auswendig gelernt abgefragt.

gruss,
thomas

[thomas_kalbe]

Hi,

ich habe mich bei obigen Post leicht geirrt, der Exponent der Vertices beschreibt nur das Level, also
aus Level k vertices werden Level k+1 Vertices -- hat mit odd und even nichts zu tun.
Alles übrige stimmt. In der Abbildung auf der Loop-Folie, unten, ist z.B. ist x_0^k --> x_0^k+1 even.
Die neuen Vertices auf den Kanten sind die odd's.
Verwirrenderweise sind die x_i, i = 1,2,...,6 links ebenfalls even.
Rechts kommen neue Vertices hinzu. Ungeschickterweise haben diese dann ebenfalls die Indizes 1 bis 6 --
es sind aber nicht die gleichen Vertices wie links, sondern eben die neu hinzugekommenen Odds auf den Kanten
des Ursprungnetzes.
Die x_i^k in der linken Abbildung sind rechts noch als unausgefüllte Kreise zu sehen.
Didaktisch etwas ungeschickt... kommt davon, wenn man nicht alle Abbildungen selbst macht.

gruss,
thomas

[TuxedoMask2002]

Meinst du in deinem ersten Post oben wirklich, dass wir das für den Zähler erhalten, oder soll da Nenner stehen? Und dann wo Nenner steht Zähler?

[thomas_kalbe]

äh, ja klar, andersrum. Danke für den Hinweis.
Wobei ich hoffentlich jetzt wirklich behaupten kann "alles andere stimmt"...

[barnie]

hätt ich mich mal lieber mehr mit Wurzel3 auseinandergesetzt...
nunja, den ersten Schritt konnte ich, das entfernen der alten Kanten, leider nicht