1 of 148

3D MESH COMPRESSION

Supervisor: Mustafa ORAL Abbas ELMAS

Investigation of Single-Rate Triangular

Algorithms

2 of 148

Outline

3D Mesh

Usage Areas
Basics
Representation

Mesh Data Structures
3D Mesh Compression

Connectivity
Geometry

Quantization
Prediction

Our Contribution
General-Purpose Compression
Performance Results

2

3 of 148

Movies

3

“Rustboy” animated short by Brian Taylor

4 of 148

Engineering

4

“Audi A8” created by Roland Wolf

5 of 148

Architectural Visualization

5

“Atrium” created by Karol Myszkowski and Frederic Drago

6 of 148

Product Catalogues

6

“Bedroom set-model Assisi” created by Stolid

7 of 148

Historical Study

7

scanning of “Michelangelo’s David” courtesy of Marc Levoy

8 of 148

Computer Games

8

screenshot of “The village of Gnisis”, The Elder Scrolls III

9 of 148

3D Object Representation

Raw Data

Point Cloud
Range Image
Polygon Soup

Surfaces

Mesh
Subdivision
Parametric
Implicit

Solids

Voxels
BSP tree
Cell complex

High-level Structure

CSG
Scene Graph
Skeleton
Sweep
Generative model

9

10 of 148

3D Object Representation

Raw Data

Point Cloud
Range Image
Polygon Soup

Surfaces

Mesh
Subdivision
Parametric
Implicit

Solids

Voxels
BSP tree
Cell complex

High-level Structure

CSG
Scene Graph
Skeleton
Sweep
Generative model

10

11 of 148

Taxonomy of 3D Object

11

12 of 148

Mesh Basics

12

13 of 148

Approximation

13

Piecewise linear approximation

Error is O(h²)

14 of 148

Manifold & Non-Manifold

14

15 of 148

Manifold Mesh

15

Every edge is shared by exactly 2 faces

manifold mesh without boundary

with boundaries

boundary edges are incident to 1 face

16 of 148

Orientability

16

Oriented CCW:

{(C,D,A), (A,D,B), (C,B,D)}

Face Orientation

clockwise or counterclockwise order in which the vertices are listed

defines direction of face normal

17 of 148

Orientability

17

Oriented CW:

{(C,A,D), (D,A,B), (B,C,D)}

Face Orientation

clockwise or counterclockwise order in which the vertices are listed

defines direction of face normal

18 of 148

Orientability

18

Not oriented:

{(C,D,A), (D,A,B), (C,B,D)}

Face Orientation

clockwise or counterclockwise order in which the vertices are listed

defines direction of face normal

19 of 148

Closed vs. Open

19

20 of 148

Mesh Zoo

20

21 of 148

Mesh Representation

Each triangle represented by 3 vertices.

Each vertices represented by 3 coordinates

Each coordinate is represented by a 32 bit float

Not mentioned the …

Colors, normals, textures, motions etc.

21

22 of 148

Mesh Representation

22

v -1.921780 0.334600 -1.851650

v -1.870020 -0.147810 -1.590690

v -1.804130 -0.552500 -1.695600

v -1.765380 -0.799380 -1.719970

v -1.673300 -1.075550 -1.538570

v -0.909274 -2.233340 -0.669400

v -0.523504 -2.452820 -0.553910

v -0.094598 -2.490290 -0.357730

v -1.367100 -1.671460 -1.087440

v -1.621700 -1.004640 -1.284810

v -1.484120 -1.143750 -1.013800

v -1.267090 -1.382210 -0.773020

v -1.132620 -1.754880 -0.703400

v -0.997273 -2.029990 -0.613760

v -0.606300 -2.349870 -0.249120

v -0.292278 -2.454410 -0.194550

v -0.749425 -2.149810 -0.277870

v -0.524425 -2.174190 -0.015380

v -0.378640 -2.351140 -0.031840

f 5 9 10

f 10 9 11

f 11 9 12

f 12 9 13

f 13 9 14

f 14 9 6

f 16 15 7

f 7 15 6

f 6 15 17

f 17 15 18

f 18 15 19

f 19 15 16

f 16 8 20

f 20 21 19

f 19 21 18

f 18 21 22

f 22 21 23

f 23 21 24

f 24 21 20

23 of 148

Data Structures

What should be stored?

Geometry: 3D coordinates
Connectivity: adjacency relationship
Attributes:

normal, color, texture

per vertex, per edge, per face

23

24 of 148

Data Structures

What should it support?

Rendering
Geometry Queries

Vertices of face #7?

Which faces are adjacent to face #3?

Modification

Remove / Add / Split / Collapse

24

25 of 148

Data Structures

Face Set
Indexed Face Set
Adjacency Matrix
Adjacency Lists
Winged-Edge
Half-Edge
Corner Table

25

26 of 148

Face Set

26

Simple
STL File

No Connectivity
Redundancy

27 of 148

Indexed Face Set

27

Connectivity

No Neighbourhood

28 of 148

Indexed Face Set

28

list of vertices

x₀y₀z₀

x₁y₁z₁

x₂y₂z₂

x₃y₃z₃

x₄y₄z₄

. . .

x_ny_nz_n

list of faces

1 4 2

29 of 148

Indexed Face Set

29

list of vertices

x₀y₀z₀

x₁y₁z₁

x₂y₂z₂

x₃y₃z₃

x₄y₄z₄

. . .

x_ny_nz_n

list of faces

1 4 2

2 3 0

4 0 5

3 4 5

5 0 2

. . .

30 of 148

Adjacency Matrix

30

If there is an edge between v_i and v_j then A_ij = 1

Can represent non‐manifold meshes
No connection between a vertex and its adjacent faces

31 of 148

Adjacency Lists - Full

31

32 of 148

Adjacency Lists - Partial

32

33 of 148

Winged-Edge

33

34 of 148

Half-Edge

34

Winged-Edge

Optimized Winged-Edge

Half-Edge

35 of 148

Corner Table

35

36 of 148

Corner Table

36

37 of 148

Corner Table

Pros:

All queries in O(1) time
Most operations are O(1)
Convenient for rendering

Cons:

Only triangular, manifold meshes
Redundancy

37

38 of 148

3D MESH COMPRESSION

38

39 of 148

Mesh Compression

Minimal information need to be stored:

Where are the vertices located?

=> Mesh Geometry

How are the vertices connected?

=> Mesh Connectivity

39

40 of 148

40

41 of 148

41

42 of 148

Compression Algorithms

Geometry Compression�Deering
Topological Surgery �Taubin & Rossignac
Triangle Mesh Compression�Touma & Gotsman
The Cut-Border-Machine�Gumhold & Straber
Edgebreaker�Rossignac
Valence Driven Connectivity Encoding�Alliez & Desbrun
Angle Analyzer�Lee
TFAN�Mamou

42

Java3D

MPEG – 4

Virtue3D ?

Open3DGC

Draco

Harry

43 of 148

Other algorithms

Generalized Triangle Strip

Deering, ’95 - Chow ’97

Spanning Tree

Taubin and Rossignac ’98 - Diaz-Gutierrez et al. ‘05

Layered Decomposition

Bajaj et al. ‘99

Valence-Driven

Touma and Gotsman ’98 - Alliez and Desbrun ‘01
Isenburg and Snoeyink ’00 - Kalberer et al. ’05
Mamou et al. ‘09

Triangle Conquest

Gumhold and Staber ’98 - Rossignac ‘99
Lee et al. ‘02

43

44 of 148

Geometry Compression�Deering

Convert triangle mesh data to generalized triangle mesh
Quantization of positions, colors, normals
Delta encoding of quantized values
Huffman tag-based variable-length encoding of deltas
Output binary output stream with Huffman table initializations and geometry compression instructions

44

45 of 148