Mesh Arrangements for Solid Geometry
Qingnan Zhou, Eitan Grinspun, Denis Zorin, Alec Jacobson

1Motivation: Fabrication2

Motivation: Fabrication2

Motivation: Fabrication

2

Thingi10K Dataset

3

Thingi10K Dataset
84% Without Degeneracies

4

Thingi10K Dataset
84% Without Degeneracies
78% Manifold

5Thingi10K Dataset
84% Without Degeneracies
78% Manifold
74% Single Component

6Thingi10K Dataset
84% Without Degeneracies
78% Manifold
74% Single Component
69% Without Coplanar Intersections

7

Thingi10K Dataset
84% Without Degeneracies
78% Manifold
74% Single Component
69% Without Coplanar Intersections
55% Without self-intersections

8

Problem Statement
Input

9

Problem Statement
Input

Output Solid10

Problem Statement
Input

Mesh Arrangement

Output Solid

11

Previous Works: CGAL

12

Previous Works: CGAL
Input Mesh

Polyhedron

Nef Polyhedron

13

Previous Works: Cork, QuickCSG
Expected Output

Actual Output=14

Input and Output
Valid Input

Valid Output

15

Winding Number[Jacobson et al. 2013]16

Winding Number[Jacobson et al. 2013]16

Winding Number[Jacobson et al. 2013]17

Winding Number[Jacobson et al. 2013]17

Winding Number

18

Winding Number

0119Winding Number

0011219

Winding Number

10012012-1119

Definitions
PWN Mesh:
A mesh that induces Piecewise-constant Winding Numbers.

20

Definitions
PWN Mesh:
A mesh that induces Piecewise-constant Winding Numbers.
Solid Mesh:A PWN mesh that• induces 0/1 winding number field• without self-intersection or degeneracies
21

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

22

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Vertex Non-manifold23

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Vertex Non-manifold

Edge Non-manifold

24

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Vertex Non-manifold

Edge Non-manifold

Degenerated Faces

25

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Vertex Non-manifold

Edge Non-manifold

Degenerated Faces

Self-intersection
26

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Self-intersection

Vertex Non-manifold

Edge Non-manifold

Degenerated Faces

Nested Components
27

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Self-intersection

Vertex Non-manifold

Nested Components

Edge Non-manifold

Degenerated Faces

Overlapping Faces
28

PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Self-intersection

Vertex Non-manifold

Nested Components

Edge Non-manifold

Overlapping Faces

Degenerated Faces

Open29PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.
ClosedMultiple Components

Self-intersection

Vertex Non-manifold

Nested Components

OpenEdge Non-manifold

Overlapping Faces

Degenerated Faces

Open30PWN MeshPWN Mesh: A mesh that induces Piecewise-constant Winding Numbers.

Multiple Components

Self-intersection

Vertex Non-manifold

Nested Components

Edge Non-manifold

Overlapping Faces

Degenerated Faces

Topologically Open31

Valid Input
10,000 Meshes from Thingiverse
86% PWN Meshes
51% Solid
50% Polyhedron

32

Input and Output
Input: PWN Meshes

Output: Solid Mesh33

Input and Output
Input: PWN Meshes

Mesh Arrangment

Output: Solid Mesh34

Mesh Arrangement

35

Mesh Arrangement36Mesh Arrangement37

Mesh Arrangement(1, 0, 0)38

Mesh Arrangement(1, 0, 0)(0, 1, 0)39

Mesh Arrangement(1, 0, 0)(0, 0, 0)(0, 1, 0)40

Mesh Arrangement(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)41

Mesh Arrangement(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)

42

Mesh Arrangement(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)

43Mesh Arrangement(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)44

Algorithm
Input Meshes

45

Algorithm
Input Meshes

Resolving(Self-)Intersections

45

Algorithm
Input Meshes

Resolving(Self-)Intersections

Extracting
Cells

45

Algorithm
Input Meshes

Resolving(Self-)Intersections

Extracting
Cells

Propagating
Winding Numbers(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)45

Algorithm
Resolving(Self-)Intersections

Extracting
Cells

Propagating
Winding Numbers(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)

46

Resolving (Self-)Intersections

47

Resolving (Self-)Intersections
Pitfall: CDT is not unique, overlapping triangle needs to be consistently resolved!

Inconsistent!

48

Algorithm
Resolving(Self-)IntersectionsExtractingCells

Propagating
Winding Numbers(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)49

Extracting Cells

50

Extracting Cells

51

Extracting Cells

52

Extracting Cells

53Extracting Cells

54

Extracting Cells

55

Extracting Cells

56

Extracting Cells

Rounding

57

Extracting Cells

58

Extracting Cells

59

Extracting Cells

60

Extracting Cells
Patch 1
Cell 1Patch 2Cell 2Patch 3Cell kPatch n61

Algorithm
Resolving(Self-)Intersections

ExtractingCellsPropagatingWinding Numbers(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)62

Propagating Winding Numbers

63

Propagating Winding Numbers(0, 0, 0)64

Propagating Winding Numbers(0, 0, 1)(0, 0, 0)(0, 1, 0)(1, 0, 0)(0, 0, 1)(0, 1, 0)65

Propagating Winding Numbers(1, 0, 1)(0, 0, 1)(0, 0, 0)(0, 1, 0)(1, 0, 0)(0, 0, 0)(0, 0, 1)(0, 0, 0)(0, 1, 1)(1, 1, 0)(0, 0, 0)(0, 1, 0)66

Propagating Winding Numbers(1, 1, 1)(0, 1, 0)(1, 0, 1)(0, 0, 1)(0, 1, 0)(1, 0, 0)(0, 0, 0)(0, 0, 1)(0, 0, 0)(0, 0, 1)(1, 0, 0)(0, 0, 0)(0, 1, 1)(1, 1, 0)(0, 0, 0)(0, 1, 0)67

Propagating Winding Numbers(1, 0, 1)(1, 1, 1)(0, 1, 0)(1, 0, 1)(0, 0, 1)(0, 1, 0)(1, 0, 0)(0, 0, 0)(0, 0, 1)(0, 0, 0)(0, 0, 1)(1, 0, 0)(0, 0, 0)(0, 1, 1)(1, 1, 0)(0, 0, 0)(0, 1, 0)68Propagating Winding Numbers(0, 0, 0)(1, 0, 0)(0, 1, 0)(0, 0, 1)(1, 1, 0)(0, 1, 1)(1, 0, 1)(1, 1, 1)

69Results: Self Union
Check 1: produced an output
our method
CGAL
Carve
QuickCSG
Cork
Attene

100%
73.4%

99.9%
99.9%
94.1%
98.3%
70

Results: Self Union
Check 2: output is closed
our method
CGAL
Carve
QuickCSG
Cork
Attene

100%
73.4%
66.0%

99.4%93.6%
98.2%
71

Results: Self Union
Check 3: output is PWN
our method
CGAL
Carve
QuickCSG
Cork
Attene

100%
73.4%
66.0%

95.2%
93.6%
98.2%
72

Results: Self Union
Check 4: output is self-intersection free
our method
CGAL
Carve
QuickCSG
Cork
Attene

100%
51%
60%
62%
61%
70%
73

Results: Self Union
1000

ours

Cork

100

QuickCSG

10
Running time
Unit: second

1.7
1

0.25

0.22

0.1
0.01
0.001

0.05

0.06

CGAL
Carve
74

Results: [Barki et al. 2015] Dataset75

Results: [Barki et al. 2015] Dataset

1404 results for all possible pairs.
76

Results: [Barki et al. 2015] Dataset77

Results: [Barki et al. 2015] Dataset78

Results: [Barki et al. 2015] Dataset

79

Results: [Barki et al. 2015] Dataset

80

Results: [Barki et al. 2015] Dataset81

Results: [Barki et al. 2015] Dataset82

Results: [Barki et al. 2015] Dataset

83Results: [Barki et al. 2015] Dataset

84

Results: [Barki et al. 2015] Dataset

85

Results: [Barki et al. 2015] Dataset

86

Results: [Barki et al.] Dataset

87

Result: Reverse Boolean?

Credit: nervoussystem, 2014\=88

Result: Reverse Boolean?

Credit: nervoussystem, 2014\=89

Results: Bunny Carvex10,00090

Results: Bunny Carve91

Results: Swept Volume

92

Results: Swept Volume

92

Results: CNC Milling93

Results: CNC Milling

93

Conclusion

94

Future Works• Boost performance with adaptive techniques.

• Repairing non-PWN meshes

95Resources
Source Code

Dataset: Thingi10K

https://github.com/libigl/libigl

PyMesh
https://github.com/qnzhou/PyMesh

https://ten-thousand-models.appspot.com/

96