Subdivision Surfaces – Notizen

Subdivision Surfaces – Notizen

Allgemeine Motivation und Kontext

• Geometrische Modellierung benötigt manchmal mehr als Polygonnetze: glatte Flächen statt nur Dreiecks-/Vektormodelle.
• NURBS (Non Uniform Rational B-Splines) bieten glatte Oberflächen, können jedoch Probleme bei topologischen Anpassungen haben:
  • Eine einzelne NURBS-Patch ist oft eine topologische Scheibe, ein Rohr oder ein Torus.
  • Um komplexe Geometrie zu modellieren, sind viele NURBS-Patches nötig.
  • Beim Verformen einer aus NURBS-Patches bestehenden Fläche können an Nähten Kracks auftreten.
• Subdivision Surfaces bieten eine Alternative bzw. Ergänzung durch stetige Verfeinerung der Kontrollelemente zu einer glatten Grenzfläche.

Subdivision Surfaces – Kernaussagen

• Allgemeine-Definition: Generalisierung von Splines zu Flächen (und Kurven) durch beliebige Kontrollnetze.
• Merkmale:
  • Beliebige Topologien der Kontrollnetze (durchschnittlich in der Praxis mit sogenannten extraordinary points).
  • Stetige Verfeinerung (Subdivision) führt gegen eine glatte Grenzfläche.
  • Verbindung zwischen Splines und Netzen: Splines lassen sich als Grenzwerte von Subdivision-Schemata verstehen.
• Relevanz: Ermöglicht robuste, flexiblere Modellierung mit guter Kontrollintuitivität.

Berühmtes Beispiel: Geri’s Game (Pixar)

• Subdivision Surfaces wurden genutzt, um:
  • Geri’s Hände und Kopf zu modellieren.
  • Kleidung (Jacke, Hose, Hemd, Krawatten, Schuhe).
  • Referenz zur Arbeit von DeRose et al. (SIGGRAPH ’98).
• Gegenüberstellung: Geri’s Hand modelliert mit NURBS vs. Subdivision (zeigt Stärken der Subdivision bei feinen Details und glatten Übergängen).

Scharfe Kanten/Creasen

• Scharfe Kanten (Edges) bzw. Creases mit variabler Schärfe können glatte Modelle problematisch machen, z. B. bei NURBS.
• Subdivision kann solche Merkmale explizit durch Crease- bzw. Schärfe-Parameter handhaben.
• Signifikante, wichtige Oberflächenmerkmale lassen sich detailliert darstellen.

Subdivision in der Praxis – Warum Subdivision?

• Eigenschaften und Vorteile:
  • Anwendbar auf Netze beliebiger Topologie durch sogenannte extraordinary points.
  • Skalierbarkeit und Level-of-Detail (LOD) Rendering.
  • Numerische Stabilität.
  • Einfach implementierbar mit kompaktem Support.
  • Affine Invarianz.
  • Glatte Grenzflächen als Grenzwert einer Refinement-Folge.
• Relevante Ressourcen: Pixar OpenSubdiv als Open-Source-Implementierung.

Subdivision in 1-D – Einstiegskonzept

• Grundidee: Aus einer Kontrollpolygonale wird eine glatte Kurve durch sukzessive Verfeinerung erzeugt.
• Einfaches Beispiel – Stückweise lineare Subdivision (Approximating):
  • Neue Punkte entstehen als Mittelpunktsbildung zwischen benachbarten Kontrollpunkten, alte Punkte bleiben erhalten.
• Mathematisch (vereinfachte Darstellung):
  • Initiale Punkte seien \{p_i\}
  • Neue Punkte nach einer Verfeinerung: \(p'i = \frac{pi + p_{i+1}}{2}\)
  • Ebenso für die y-Koordinaten: \(y'i = \frac{yi + y_{i+1}}{2}\)
• Ziel: Eine neue Kontrolleform, deren Grenzkurve glatt ist.

Subdivision Curves – Typen

• Approximating (Annähernd):
  • Splitting-Schritt: Jede Kante wird in zwei geteilt.
  • Averaging-Schritt: bestehenden Vertex wird verschoben nach einer einfachen Regel.
  • Neuer Start-Zyklus – wieder Split/ averaging – schrittweise Annäherung an eine glatte Grenzkurve.
• Interpolating (Interpolierend):
  • Old vertices bleiben erhalten.
  • Neue Punkte werden durch das Fitten eines kubischen Polynoms durch die alten Punkte bestimmt.
  • Grenzkurve ist C^1-kontinuierlich.
  • Typisches Vier-Punkte-Verfahren (4-point scheme): neue Punkte werden durch Nachbarpunkte bestimmt.
• Corner Cutting (Eckenabschneiden):
  • Neue Punkte werden an 1/4- und 3/4-Stellen jeder Kante eingefügt, alte Punkte werden entfernt, neue Kantenpunkte verbunden.
  • Grenzkurve ist eine quadratische B-Spline (C^1, aber nicht C^2 an allen Stellen).

4-Punkte-Verfahren (Interpolierend)

• Prinzip: Vier Punkte bestimmen ein kubisches interpolierendes Polynom.
• Neuer Punkt zwischen zwei alten Punkten wird durch Nachbarschaftskoeffizienten bestimmt.
• Typische Formulierung (Interpolierendes Vier-Punkte-Verfahren):
  • Neuer Zwischenpunkt zwischen pi und p{i+1}:
    $p^{*}<em>{i+1/2} = \frac{-p</em>{i-1} + 9p<em>i + 9p</em>{i+1} - p_{i+2}}{16}.$
• Eigenschaften: Old vertices bleiben erhalten; Grenzkurve ist C^1.

B-Splines – Wiederholung und Refinement

• B-Splines als wiederholte Faltung einer Box-Funktion – grundlegende Definition:
  • Beispiel-Box-Faltung liefert B-Spline-Kernels, z. B. $B(t) = B(t) * B(t)$-Art, mit entsprechenden Normalisierungen.
• Allgemeine Eigenschaften von B-Splines:
  • Allgemeine Grad-Definition: Grad n, stückweise Polynome.
  • Lokale Unterstützung.
  • B-Splines von Grad n sind C^{n-1}-stetig.
• Refinement-Relation (Skalierung und Verschiebung):
  • Eine B-Spline ist eine Kombination aus verschobenen/refinierten Kopien derselben Basis:
    $B^{n}(t) = \sum<em>k a</em>k B^{n}(2t - k)$
  • Lineare B-Spline-Beispiele: eine einfache glatte Darstellung unter Verwendung von Masken wie $\frac{1}{2}[1\;1]$ oder \([1, 4, 6, 4, 1]) in der kubischen Form, skaliert entsprechend.
• Refinement-Gleichungen – Kurvenrefinement:
  • Kurven als Gewichtung der Basisfunktionen: $Y(t) = \sum<em>i p</em>i B_i(t)$
  • Refinement durch neue Kontrollpunkte: $\mathbf{p}' = S \mathbf{p}$ und $B(t) = B(2t) S$, wobei S eine Refinement-Matrix ist.
• Praktische Konsequenz: Subdivision kann als Refinement der Kontrolpunkte oder als Refinement der Basisfunktionen interpretiert werden – oft beides gleichzeitig.

Subdivision Masken und das Subdivision Zoo

• Notation (Typen von Vertices):
  • Regular vertices vs. extraordinary vertices.
  • Triangles: Valenz 6 (Rand 4).
  • Quads: Valenz 4 (Rand 3).
  • Even vertices = "alte" Vertices, Odd vertices = "neue" Vertices.
  • Edge- und Face-Vertices: unterschiedliche Masken.
  • Rand- und Crease-Vertices.
• Masken als grafische Repräsentationen der Subdivision-Schemata: unterschiedliche Masken je Vertex-Typ.
• Subdivision Zoo – Klassifikation:
  • Primal vs Dual:
  • Primal: Kanten- bzw. Eckpunkte eingefügt (neue Polygon-Flächen entstehen durch Einfügen von Vertices).
  • Dual: Ecken abgeschnitten (ein Vertex wird durch mehrere neue ersetzt).
  • Triangles vs Quads:
  • Triangulierte Netze spezialisieren andere Schemata als Quad-Layouts.
  • Approximating vs Interpolating:
  • Approximating: Kontrollpunkte behalten, neue Punkte in der Nähe der Kurve platziert.
  • Interpolating: Kontrollpunkte bleiben auf der Grenzkurve.

Wichtige Subdivision Schemes

• Primal (Netzart):
  • Loop (triangle meshes, approximierend, glatte Grenzflächen – G2 allgemein, C1 an extraordinary Points)
  • Catmull-Clark (quad meshes, approximierend, glatte Grenzflächen – G2 allgemein, C1 an extraordinary Points, C2 sonst)
• Dual / Interpolating:
  • Doo-Sabin (dual, approximierend, G1 – C0 an extraordinary Points, C1 ansonsten; einzige zusätzliche Randmaske bei Rand)
  • Butterfly (4–7-Vertex-Regeln, interpolierend, G1 – C1 ansonsten)
  • Kobbelt (Interpolierend, weniger verbreitet)
• Kurze Notizen:
  • Loop: Primär Triangle-Meshes; G2 Grenzstetigkeit (außer an extraordinary points) – Interpolation nicht garantiert.
  • Catmull-Clark: Primär Quad-Meshes; G2 Grenzstetigkeit – C1 an extraordinary points, C2 sonst.
  • Doo-Sabin: Dual-Variante, G1 – C0 an extraordinary points, C1 ansonsten; Randmasken sind einfacher implementierbar.
  • Butterfly: Interpolierend, G1 – C1 ansonsten.

Unterschiedliche Rand- und Extraordinary-Vertex-Strategien

• Regular vertices have standard valence (z. B. 6 für Dreiecke, 4 für Quads).
• Extraordinary vertices haben andere Valenzen, woraus spezielle Masken abgeleitet werden.
• Rand-vertices / Crease-vertices benötigen spezielle Masken bzw. Randbedingungen.

Auswirkungen und Praxis-Vergleich

• So wer gewinnt? – Richtlinien aus der Vorlesung:
  • Loop und Catmull-Clark liefern gute Ergebnisse, wenn keine Interpolation gefordert ist.
  • Loop ist besonders gut für dreieckige Netze.
  • Catmull-Clark ist besonders gut für Quad-Netze.
  • Interpolierende Schemes (z. B. Butterfly, Kobbelt) eignen sich, wenn man Originalkontrollpunkte beibehalten möchte, haben aber andere Glättungs-Eigenschaften.
• Allgemeine Eigenschaften von Subdivision:
  • Flexible Modellierung, Topologie-Unabhängigkeit, beweisbar glatte Grenzflächen
  • Intuitive Interaktion mit Kontrollpunkten
  • Skalierbarkeit und Level-of-Detail (LOD) Rendering
  • Adaptive Approximation möglich
  • Kompakte Repräsentation, einfache und effiziente Implementierung
• Praxisressourcen: Pixar OpenSubdiv – https://graphics.pixar.com/opensubdiv/overview.html

Notationen und Begrifflichkeiten (Zusammenfassung)

• Regular vertices: valence 6 (Dreiecke) bzw. 4 (Quads), Rand-Vertices: reduzierte Valenz.
• Extraordinary vertices: Valenz ungleich der Regular-Valenz.
• Odd vs Even vertices: in vielen Schemata unterscheiden sich "alte" vs. "neue" Vertices.
• Edge-Vertex vs. Face-Vertex: unterschiedliche Masken und Verfeinerungsregeln für Ecken-/Kanten-Vertices.
• Masken: Explizite Gewichte, die neue Punkte aus alten Punkten ableiten.
• Kontinuität: C0, C1, C2 – glatte Grenzflächen zwischen Teilen des Netzes; Loop/Catmull-Clark liefern üblicherweise C1/C2 je nach Kontext.

Gleitende Formeln und typische Gleichungen

• 1-D Streckensubdivision (Approximating): $p'<em>i = \frac{p</em>i + p_{i+1}}{2}$
  • Für Koordinaten: $x'<em>i = \frac{x</em>i + x<em>{i+1}}{2}, \quad y'</em>i = \frac{y<em>i + y</em>{i+1}}{2}$
• Interpolierendes Vier-Punkte-Verfahren (4-point scheme):
  $p^{*}<em>{i+1/2} = \frac{-p</em>{i-1} + 9p<em>i + 9p</em>{i+1} - p_{i+2}}{16}$
• Corner Cutting (1/4- und 3/4-Punkte):
  • Punkt bei 1/4: $q^{(1)}<em>i = 0.75\, p</em>i + 0.25\, p_{i+1}$
  • Punkt bei 3/4: $q^{(2)}<em>i = 0.25\, p</em>i + 0.75\, p_{i+1}$
  • Grenzkurve ist eine quadratische B-Spline.
• B-Splines – Refinement-Relation (Masken-Beispiel):
  • Linearer B-Spline: Maskenbeispiel (Maske) $\frac{1}{2}\begin{bmatrix}1 &amp; 1\end{bmatrix}$
  • Quadratischer/quasi-cubic Koeffizientenfluss: $\frac{1}{8}\bigl(1,\,4,\,6,\,4,\,1\bigr)$
• Allgemeine Refinement-Gleichung für B-Spline-Kurven: $\mathbf{Y}(t) = \sum<em>i p</em>i B<em>i(t)$$B</em>i^{(//n)}(t) = \sum<em>j S</em>{ij} B_j^{(//n)}(2t)$$\mathbf{p}' = S\mathbf{p}, \quad B(t) = B(2t)S$
  • Dies zeigt: Refinement der Kurve ist linear in den Kontrollpunkten und der Basis

Praktische Hinweise

• Beim Modellieren mit Subdivision ist es oft sinnvoll, je nach Topologie (Triangle vs Quad) das passende Schema zu wählen:
  • Dreiecksnetze → Loop (oft gute Glätte, G2 u. U. an innenliegenden extraordinary Points)
  • Quad-Netze → Catmull-Clark (robust, gute Topologie-Glättung)
• Wenn Interpolation gewünscht ist, kommen interpolierende Schemata wie Butterfly oder Kobbelt ins Spiel, oft mit anderen Glättungseigenschaften.
• Für reale Implementierungen empfiehlt sich der Einsatz etablierter Bibliotheken bzw. Open-Source-Implementierungen (z. B. Pixar OpenSubdiv).

Verweis & weiterführende Ressourcen

• Pixar OpenSubdiv – Überblick und Implementierung: https://graphics.pixar.com/opensubdiv/overview.html
• DeRose et al. SIGGRAPH ’98 (NURBS vs. Subdivision, Sharp Creases, etc.)
• SIGGRAPH-Forschung zu Geri’s Game (Subdivision Nutzung) – Kontext zur Praxisanwendung