Unterteilungsalgorithmen

Unterteilungsalgorithmen sind sehr einfache und schnelle Algorithmen, um aus einem Polygon, d. h. aus einem Polygonzug oder aus einem polygonalen Netz, eine Folge von immer feiner werdenden Polygonen zu erzeugen, die sehr schnell gegen eine Kurve oder Fläche konvergiert. Ohne großen Aufwand lassen sich auf diese Art beliebig geformte Flächen recht intuitiv generieren. Weil die Konstruktion glatter Freiformflächen mit anderen Methoden um vieles komplizierter ist, erfreuen sich Unterteilungsalgorithmen großerer Beliebtheit in der Computergraphik. Aufwendig ist es hingegen, die Eigenschaften einer Unterteilungsfläche mathematisch zu analysieren. Dafür wurden eine Reihe von Methoden entwickelt. Sie werden in dieser Vorlesung vorgestellt ebenso wie verschiedene Unterteilungsalgorithmen und Klassen von Unterteilungsalgorithmen.

Zur Vorlesung gibt es eine Übung, ein Praktikum und ein Seminar.

Inhalt
1 Der Lane-Riesenfeld-Algorithmus (Skript)
2 Sationäre Unterteilung von Polygonzügen (Skript)
3 Unterteilung regelmäßiger Vierecksnetze (Skript Stand 15.6.)
4 Unterteilung von Box- und Halbboxsplines (Skript)
5 Stationäre Unterteilung beliebiger Netze (Skript komplett)

Korrekturen am Skript
25.5.: S. 21 (4)
30.5.: S. 5, letzter Satz
02.6.: S. 55 alternativ zu S. 56 hinzugefügt
08.6.: S. 55+56 Begriff Nullschema hinzugefügt.
08.6.: S. 28 Nullschemata berücksichtigt

 

Literatur
H. Prautzsch, W. Boehm, M. Paluszny: Bézier and B-Spline Techniques, Springer-Verlag, 2002.
Warren, Weimer (2001) Subdivision Methods for Geometric Design: A constructive Approach. Morgan Kaufmann.
Andersson, Stewart (2010) Introduction to the Mathematics of Subdivision Surfaces. SIAM
Sabin (2002) Subdivision Surfaces. In Farin, Hoschek, Kim (eds) Handbook of Computer-Aided Geometric Design. Chapter 12.
Zorin et al. (2000) Subdivision for Modeling and Animation. SIGGRAPH Course Notes

Speziell zu Kapitel 1
Chaikin (1974): An algorithm for high speed curve generation. Comput. Graph. Image Process. 3. 346-349.
Lane, Riesenfeld (1980). A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-2(1):35-46.
Tony DeRose explains univariate subdivision.

Speziell zu Kapitel 2
Sabin (2010) Analysis and Design of Univariate Subdivision Schemes. Springer.

Speziell zu Kapitel 3
Nira Dyn and David Levin: Subdivision Schemes in Geometric Modellinghttp://www.math.tau.ac.il/~niradyn/papers/dynlevin.pdfSubdivision for Modeling and Animation (Siggraph 2000 Course Notes)http://mrl.nyu.edu/publications/subdiv-course2000
Cavaretta, Dahmen, Micchelli (1991) Stationary subdivision. Memoirs of the American Mathematical Society 93 (453). 1-186.

Speziell zu Kapitel 5
Catmull, Edwin Earl, Clark , James Henry: Recursively generated B-spline surfaces on arbitrary topological meshes. Comp. aided Design 10, (1978) 350-355.
DeRose; Kass; Truong (1998) "Subdivision surfaces in character animation". Proceedings of the 25th annual conference on Computer graphics and interactive techniques - SIGGRAPH 85-94.
Peters, Reif (2008) Subdivision Surfaces. Springer.