Graphische Datenverarbeitung 2

  • Termin: Mo, 9:50 - 11:30, S3|05-74
  • Vorlesungsbeginn: Mo, 18.04.2005
  • Klausur: 14.7.2005 von 13.30-15.30 Uhr in Raum S3|11-08
  • Homepage
  • Kommentar im VV

Themenübersicht

1. Parametrische Kurven und Flächen

  • Explizite Darstellung
  • Implizite Darstellung
  • Parametrisierung nach Bogenlänge
  • Interpolation
    • Langrange-Polynom
    • Hermite-Interpolation
    • Radiale Basisfunktionen (RBF)
  • Approximation
    • Methode der kleinsten Fehlerquadrate
    • Bezierkurven
      • Algorithmus von de Casteljau
    • B-Splines
    • Bezier-Splines

2. Parametrische Flächen, Hinweise zur 2. Übung

  • Parametrisierte Fläche: liefert (x, y, z)-Koordinaten
    • Parameterkurven: nur eine Veränderliche
  • Tensorproduktfläche
    • Interpolation: Lagrange-Basis
    • Approximation: Bernstein-Basis, Bezier-Tensorproduktfläche
      • Algorithmus von de Casteljau
    • Gewichtete kleinste Fehlerquadrate
      • Moving Least Squares

Parametrische Kurven und Flächen (Fortsetzung)

  • Approximation (Fortsetzung)
    • B-Spline-Kurve
    • De-Boor-Algorithmus

3. Implizite Kurven und Flächen

  • Definition Implizite Fläche
    • Normalenvektor durch Gradienten gegeben
  • Mengenoberationen
    • Vereinigung: Minimum
    • Durchschnitt: Maximum
  • Kegelschnitte, Quadriken (algebraische Flächen)
    • affin invariant
    • dargestellt als g(x, y, w) = (x, y, w) × M × (x, y, w)T
      (M ist eine 3×3-Matrix)
      • Hauptachsenform: Einträge nur auf der Diagonalen
      • charakterisierbar anhand der Eigenwerte der Matrix
  • Glatte Mengenoperationen durch:
    • Vereinigung: g ∪ f = 1/(1 + α) × (g + f - sqrt(g2 + f2 - 2αgf))
    • Schnitt: g ∩ f = 1/(1 + α) × (g + f + sqrt(g2 + f2 - 2αgf))
  • Blobs (Äquipotentialflächen)
    • Mengenoperationen
    • Beschränkter Träger
  • Skelette
    • Distanzfläche
    • Verallgemeinerte Zylinder
    • Faltungsflächen

4. Tesselinerung impliziter Kurven und Flächen

  • Problem: Nullstellenmenge impliziter Flächen kann nicht explizit berechnet werden
  • 3D-Tesselierung: Marching Cubes
  • 3D-Tetraedernetz
  • Grid-Snapping
  • Erkennen von Ecken und Kanten, zusätzliche Punkte einfügen

5. Implizite Flächen auf Punktdaten

  • Um f = 0 zu vermeiden, werden Nebenbedingungen benötigt
    • definiere innen und außen
    • Normalen liefern Nebenbedingung: f(pi + αni) = α
  • Bestimmung impliziter Funktionen
    • mittels Radialer Basisfunktionen (RBF)
      • Nur Teil der Punkte verwenden, sukzessiv mehr Punkte zur Verbesserung hinzu nehmen
    • mittels Moving Least Squares (MLS)
    • Hoppe: lineare Distanzfunktion (Distanzfeld) pro Punkt mit Hilfe der Normalen, Distanz ist Minimum über alle lokalen Distanzfunktionen
    • Verbesserung von Hoppe: MLS lokaler Distanzfunktionen (gewichtetes Mittel der Distanzwerte)

6. Polygonale Netze

  • Definitionen
    • geomtrischer Graph
    • Kanten
    • Polygon
    • Polygonnetz
    • Polyeder
    • Orientierung
    • Orientierbarkeit
    • Geschlecht
  • Euler-Pointcare-Formel:
    • χ(M) = v - e + f
    • V - e + f = w(1 - g)
  • Datenstrukturen für Polyeder
    • 9 mögliche Nachbarschaftsbeziehungen: V <=> E <=> F
    • Winged Edge
    • Full Winged Edge
    • Erweiterte Full Winged Edge
    • Halbkanten-Datenstruktur
  • Kompression der Konnektivität
    • Dreiecksstreifen
    • Cut-Border-Algorithmus
      • 5 Operationen
      • effitiente Speicherung mittels Hoffmann-Kodierung
    • Valenz-Kodierung
      • Theorie: maximal schlechtes Dreiecksnetz benötigt ~3,24 Bit/V
  • Kompression der Geometrie

7. Vereinfachung polygonaler Netze

  • Ziel: Level of Detail
  • Kriterien für Vereinfachung bzw. zur Bewertung der Qualität
    • geometrischer Abstand (Hausdorff)
      • einseitiger Hausdorffabstand
    • parametrischer Abstand
    • optimale Lösung: NP-vollständig
    • Fehlerquadriken
    • Algorithmus
  • Simplifizierung
    • Operationen:
      • Entfernen von Kanten
      • Entfernen von Knoten
      • Entfernen von Dreiecken
    • Triangulieren der Lücke: Constrained Dela??? (Dreiecksumkreis-/innenkreis)
  • Progressive Level of Detail: Speicherung
  • Vertex-Clustering

8. Polygonale Netze, Multiskalendarstellung

  • Dynamische LoD's
    • Blickpunktsabhängig
    • Beleuchtungsabhängig
  • Netz-Hierarchie
    • flache Hierarchie (wenige Stufen) wünschenswert
    • Konstruktion
    • Komplexität
    • Progressive Kompression
      • 4-Färbbarkeit ebener Graphen
  • Netz-Topologien
    • reguläre Netze
    • Verfeinerungsoperatoren
    • Umwandlung in semi-reguläre Netze
      • Vereinfachung
      • Parametrisierung
      • Reguläre Verfeinerung
  • Subdivision-Flächen
    • Midpoint-Subdivision
    • Corner Cutting
    • Tensorierung
    • Analyse von Unterteilungsschemata
    • Tangenten
    • Bestimmung einer Glättungsregel
    • Loop-Subdivision
    • Modifiziertes Butterfly-Schema
    • Catmull-Clark-Unterteilung

Zuletzt geändert am 13 Juli 2005 22:51 Uhr von chrschn