3D-Kompression
FH Giessen-Friedberg
3D-Kompression
Multimedia-Seminar, WS 2001/2002
Michael Weyel
3D-Kompression
Inhalt
•
•
•
•
•
•
Aufbau von 3D-Modellen
Motivation
Level of Detail
Progressive Meshes
Quadric Error Metric
Ausblick
FH Giessen-Friedberg
3D-Kompression
FH Giessen-Friedberg
Aufbau von 3D-Modellen
• Häufigste Darstellungsform : Polygonales
Modell
• Bestandteile : Punkte (Vertices) und
Flächen (Faces)
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Aufbau von 3D-Modellen
• Vertex-Eigenschaften:
–
–
–
–
–
Position ( x, y, z )
Farbe ( r, g, b )
Normalenvektor ( nx, ny, nz )
Texturkoordinaten ( tu, tv )
...
• Flächen-Eigenschaften:
– Materialkonstante
– Normalenvektor
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Aufbau von 3D-Modellen
• Vorteile der polygonalen Darstellung
– Weit verbreitet und akzeptiert
– Flexibel
– Durch Hardware unterstützt
• Nachteile der polygonalen Darstellung
– Wirklich „runde“ Oberflächen nicht
darstellbar
– U.u. viele Vertices und Faces pro Modell
nötig
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Aufbau von 3D-Modellen
1000 Faces
424000 Faces
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Aufbau von 3D-Modellen
• Andere Darstellungsmöglichkeiten
– Parametric Spline Surfaces
– NURBS
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Motivation
• Grafikanwendungen brauchen viel
Rechenzeit
• 3D-Modelle häufig zu detailliert
• Polygondichte nicht angepasst
• Verwendete Hardware unterschiedlich
• Übertragungszeit bei OnlineAnwendungen
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Motivation
• Anzahl der Objekte wird nicht
berücksichtigt
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Motivation
• Entfernung der Objekte zum
Betrachter wird nicht berücksichtigt
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Speicherung oder Real-Time-Erzeugung
mehrer Detailstufen eines 3D-Modells
• Anzeige der einzelnen Detailstufen nach
vorgegebenen Kriterien
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Ziel : Erzeugung eines
„Multiresolution Model“
• Unterschieden wird in
– Discrete Multiresolution ( Verwendung
von festen Vereinfachungsstufen )
– Continuous Multiresolution
(Kontinuierliche Vereinfachung oder
Verfeinerung)
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Discrete Multiresolution
– Renderer entscheidet zur Laufzeit,
welche Detailstufe angezeigt wird
(Dist, AoI, ...)
– Übergang darf nicht
rechenzeitaufwendig sein
– Problem: „popping artifacts“
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Discrete Multiresolution
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Discrete Multiresolution
– Lösungsansätze
• LoD-Blending (Alpha Blending)
• Geomorphing
• Geschwinddigkeit beider Verfahren
Hardwareabhängig
– DM-Verfahren rückläufig, weitere
Nachteile vorhanden
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Continuous Multiresolution
– Vereinfachung der Oberfläche zur
Laufzeit
– Vereinfachung wird in sehr kleinen
Schritten vorgenommen
– Es muss nur das Ausgangsmodell
gespeichert werden ( zusätzlich, je
nach Verfahren, die
Vereinfachungsschritte )
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Continuous Multiresolution
– Ermöglicht „variables“ und
„blickwinkelabhängiges“ LoD
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Mögliche Verfahrensweisen:
– Manuelle Bearbeitung
– Automatische Erzeugung der
Detailstufen
– Zwei Ansätze :
• Refinement ( Verfeinerung )
• Decimation ( Dezimierung )
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Refinement
– Ausgangspunkt : Stark vereinfachtes Modell
– Hinzufügen von Elementen
– Anwendungsbereiche :
• Vereinfachung von 2D-Kurven ( DouglasPeucker-Algorithmus )
• Vereinfachung von Höhen-Feldern z = f(x,y)
( „Greedy insertion“ )
– Nachteil : Original und vereinfachtes
Ausgangsmodell nötig
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Decimation
– Ausgangspunkt : Detailreiches Modell
– Wegnehmen oder Verschmelzen von
Elementen
– Anwendungsbereiche
• Vereinfachung von beliebigen
Oberflächen
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Decimation
– Vertex Clustering
• Legen eines Gitters „in“ das Modell
• Verschmelzen aller Vertices im selbem
Gitterbereich
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Decimation
– Vertex Clustering
• Vorteile
– Schnell
– Arbeitet gut, wenn Modell
„überdetailliert“
– Unterstützt „Non-Manifold Surfaces“
• Nachteile
– Vereinfachungen meist qualitativ
schlecht
– Ergebnis hängt stark von der
Unterteilung und Platzierung des
Gitters ab
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• (Non-) Manifold Surfaces
– Die Nachbarn jedes Punktes (außer
Grenzpunkte) liegen so, dass sie einen
geschlossenen Fächer bilden und jede
Kante innerhalb dieses Fächers hat 2
Nachbarn
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Decimation
– Vertex Clustering
• Vorteile
– Schnell
– Arbeitet gut, wenn Modell
„überdetailliert“
– Unterstützt „Non-Manifold Surfaces“
• Nachteile
– Vereinfachungen meist qualitativ
schlecht
– Ergebnis hängt stark von der
Unterteilung und Platzierung des
Gitters ab
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Decimation
– Vertex Decimation
• Einen Vertex löschen
• Retriangulation des entstandenen Loches
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
• Decimation
– Vertex Decimation
• Vorteile
– Relativ effizient
– Gut bei „rauhen“ Oberflächen
• Nachteile
– Topologie des Modells bleibt immer
bestehen
– Schlecht bei „weichen“ Oberflächen
– Unterstützt keine „Non-Manifold
Surfaces“
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• (Non-) Manifold Surfaces
– Die Nachbarn jedes Punktes (außer
Grenzpunkte) liegen so, dass sie einen
geschlossenen Fächer bilden und jede
Kante innerhalb dieses Fächers hat 2
Nachbarn
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
• Decimation
– Iterative Contraction
• 2 Arten : Egde Contraction, Vertex
Contraction
• „Zusammenziehen“ einer Kante oder
zweier unabhängiger Punkte
3D-Kompression
FH Giessen-Friedberg
Level of Detail ( LoD )
• Decimation
– Iterative Contraction
• Vorteile
– Unterstützt „Non-Manifold Surfaces“
– Topologie kann geändert werden
– Mittlerweile weit verbreitet
• Nachteile
– Je nach verwendetem Algorithmus
langsam
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Progressive Meshes
• Iterative Edge Contraction – Verfahren
von Hugues Hoppe (96)
• Aufwendige Vereinfachung eines
Modells
• Effiziente Verfeinerung und Speicherung
möglich
• Algorithmus beachtet auch „Aussehen“
des Modells
• Verfeinerung mittels „Vertex-Splitting“
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Progressive Meshes
• Effiziente Speicherung der Werte
• 2 Möglichkeiten für Edge Contraction
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Progressive Meshes
• Vereinfachung basiert auf„Energiefuntion“
• E(M)=Edist(M)+Espring(M)+Escalar(M)+Edisc(M)
• Ermitteln dieses Wertes für jeden möglichen
Vereinfachungsschritt
• Edist + Espring : Erhaltung der
Oberflächengeometrie
• Escalar : Erhaltung der skalaren VertexKomponenten
• Edisc : Erhaltung der Diskontinuitäten
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Progressive Meshes
• Vorteile
– Effizient (RAM, Zeit für Verfeinerung)
– Progressive Transmission möglich
– Gute Ergebnisse
• Nachteile
– Vereinfachung dauert lange (Modell
„cessna“ von 13,546 Faces auf 150
Faces in 23 Minuten auf Indigo2/150
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
Progressive Meshes
FH Giessen-Friedberg
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Quadric Error Metric
• Iterative Vertex Contraction –
Verfahren von Michael Garland (99)
• Schnell bei optisch guten Resultaten
• Vertices v1 und v2 werden in v3
zusammengeführt
• Quadric Error Metric leicht
erweiterbar
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Quadric Error Metric
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
• Ablauf des Algorithmus:
– Kandidaten von Vertexpaaren für die
Zusammenlegung auswählen
– „Kosten“ für jede Zusammenlegung bestimmen
– Alle Kandidaten in Heap-Speicher ablegen,
geringste Kosten zuoberst
– Solange gewünschte Vereinfachung nicht erreicht:
• Ersten Vertexpaar vom Heap entfernen
• Diese Vertices zusammenlegen
• Kosten für umliegende Vertexpaare neu berechnen
3D-Kompression
FH Giessen-Friedberg
Quadric Error Metric
• Kostenberechnung:
– Basiert auf Beachtung lokaler Unterschiede
– Abstandsmessung eines Punktes zu den
Ebenen, welche seine Nachbarn aufspannen
– Bildung einer Matrix aus den
Normalenvektoren dieser Ebenen
– Schnelle Berechnung, da nicht jeder Abstand
(Vertex-Ebene) einzeln berechnet werden
muss
– Detailunabhängig durch Gewichtung
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
Quadric Error Metric
• Beachtung der Flächengröße
• Beachtung der Grenzlinien
FH Giessen-Friedberg
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Quadric Error Metric
• Vorteile:
– Sehr schnell (Modell „Bunny“ von
69,451 Faces auf 150 Faces in 7 sec!!
auf PPro/200)
– Einfach erweiterbar
– Progressive Transmission möglich
• Nachteile:
– Andere Techniken können bessere
Ergebnisse liefern ( aber langsamer )
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Quadric Error Metric
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg
Ausblick
•
•
•
•
•
Similarity of Appearance
Area of Interest
Adaptive Refinement
Noise Reduction
Verbesserung und Verfeinerung der
vorhandenen Algorithmen (z.B.
Symmetrieerkennung, effizientere
Behandlung von sehr großen
Modellen(>1,000,000 Faces) )
•
Aufbau von 3DModellen
•
Motivation
•
Level of Detail
•
Progressive
Meshes
•
Quadric Error
Metric
•
Ausblick
3D-Kompression
FH Giessen-Friedberg

Aufbau von 3D