Title Page

Contents

ABSTRACT 11

CHAPTER 1. INTRODUCTION 14

1.1. Physically-based simulation: An Overview 14

1.2. Motivation and Thesis Concerns 15

1.3. Main Contribution of the Thesis 18

1.4. Thesis Overview 20

1.5. Summary of Abbreviations and Notations 21

CHAPTER 2. LITERATURE REVIEW 24

2.1. Game Engines and Tools 24

2.2. GPU Parallel Computing Architecture 28

2.3. Time Integration Method 31

2.4. Mass-Spring System Method 34

2.5. Position-based Dynamics 35

2.6. Sparse Linear System Solving 38

2.7. Cloth Simulation 39

2.8. Deformable Object Simulation 40

CHAPTER 3. GPU-BASED LINEAR SYSTEM SOLVING 44

3.1. Sparse Matrix 44

3.1.1. Row-major Format 45

3.1.2. ELLPACK Format 46

3.1.3. Coordinate Format 47

3.1.4. Compressed Sparse-Row Format 48

3.2. Conjugate Gradient Iterative Solver 48

3.3. Implementation 50

3.4. Results and Discussion 56

CHAPTER 4. GPU-BASED CLOTH SIMULATION 60

4.1. Preliminary 60

4.1.1. First-Order Constraint Enforcement 60

4.1.2. Position-based Dynamic: Specific Constraints 64

4.2. Mass-Spring-based Cloth Simulation Implementation 68

4.2.1. Mass-spring System on the Compute Shader 68

4.2.2. Constraint Enforcement on the Compute Shader 70

4.2.3. Adaptive Constraint Activation and Deactivation (ACAD) Method on the Compute Shader 77

4.3. Position-based Dynamic Cloth Simulation Implementation 79

4.4. Results and Discussion 84

4.4.1. Mass-spring Model & Constraint Enforcement: Performance Result 84

4.4.2. Position-based Dynamic Cloth Simulation: Performance Result 93

CHAPTER 5. GPU-BASED DEFORMABLE 3D OBJECT SIMULATION 99

5.1. Preliminary 99

5.1.1. Volume Preservation Constraint for mass-spring model 99

5.1.2. Volume Constraint for Position-based Dynamic 102

5.2. Mass-Spring-based Deformable Object Simulation Implementation 104

5.3. Position-based Dynamic Deformable Object Simulation Implementation 110

5.4. Results and Discussion 111

5.4.1. Mass-spring Model & Volume Preservation Constraint: Performance Result 113

5.4.2. Position-based Dynamic for Deformable Object Simulation: Performance Result 119

CHAPTER 6. CONCLUSION 126

6.1. Summary and Research Findings 126

6.2. Limitation 129

6.3. Future Work and Potential Research Direction 131

REFERENCES 133

국문요약 147

〈Table Ⅰ-1-1〉 The list of acronyms and abbreviations used in the thesis 21

〈Table Ⅰ-1-2〉 The list of primary mathematic notations and symbols used in the thesis 22

〈Table Ⅲ-4-1〉 The information of the sparse matrices for performance comparison 56

〈Table Ⅲ-4-2〉 The comparison of CPU and GPU Speedup Ratios for parallel conjugate gradient using compute shader with different sparse... 59

〈Table Ⅳ-2-1〉 The information of buffer to use in the constraint enforcement algorithm 73

〈Table Ⅳ-2-2〉 The information of compute shaders to use in the constraint enforcement algorithm 73

〈Table Ⅳ-3-1〉 The information of compute shaders to use in the PBD-based cloth simulation 80

〈Table Ⅳ-3-2〉 List of GPU buffers used to perform the PBD-based cloth simulation in compute shader 81

〈Table Ⅳ-4-1〉 CPU-based mass-spring model performance comparison 85

〈Table Ⅴ-2-1〉 List of GPU's buffer for GPU-based volume preservation constraint on MSM 106

〈Table Ⅴ-2-2〉 List of kernel programs to perform volumepreservation constraint on MSM approach 107

〈Table Ⅴ-4-1〉 Experimental environment for the proposed simulation 112

〈Table Ⅴ-4-2〉 The 3D models used in this simulation are used for performance comparisons 119

〈Table Ⅴ-4-3〉 Comparisons of deformable object simulations using CPU-based and GPU-based approaches on Unity3D & OpenGL 121

〈Figure Ⅱ-1-1〉 The comparison of the user interface of (Top) Unity engine and (Bottom) Unreal engine 26

〈Figure Ⅱ-2-1〉 The comparison between CPU and GPU architecture 29

〈Figure Ⅱ-2-2〉 The computing space of the compute shader architecture 31

〈Figure Ⅱ-4-1〉 A property of the spring in the mass-spring system 34

〈Figure Ⅲ-1-1〉 An example of matrix with 5 rows and 5 column 45

〈Figure Ⅲ-1-2〉 An example of Row-major Format 46

〈Figure Ⅲ-1-3〉 An example of ELLPACK Format 46

〈Figure Ⅲ-1-4〉 An example of COO Format 47

〈Figure Ⅲ-1-5〉 An example of CSR Format 48

〈Figure Ⅲ-3-1〉 OpenGL memory layout qualifiers' rule 51

〈Figure Ⅲ-3-2〉 Flowchart of the proposed parallel Conjugate Gradient method using compute shader 52

〈Figure Ⅲ-4-1〉 Performance comparison between GPU and CPU-based CG method with different sparse matrix format and measured in milliseconds 58

〈Figure Ⅳ-1-1〉 The structure of spring network for cloth simulation 60

〈Figure Ⅳ-1-2〉 A property of the stretch constraint 65

〈Figure Ⅳ-1-3〉 A property of the bending constraint 67

〈Figure Ⅳ-2-1〉 A flowchart of cloth simulation using constraint enforcement method with compute shader 71

〈Figure Ⅳ-2-2〉 Algorithm of parallel sum reduction in shared memory 77

〈Figure Ⅳ-2-3〉 A flowchart of cloth simulation using the proposed ACAD method with compute shader 78

〈Figure Ⅳ-3-1〉 A flowchart of cloth simulation using the PBD method with compute shader 80

〈Figure Ⅳ-4-1〉 Performance results between GPU-based Mass-spring model for Unity3D and OpenGL 86

〈Figure Ⅳ-4-2〉 Performance results between GPU-based constraint enforcement for Unity3D and OpenGL 87

〈Figure Ⅳ-4-3〉 The difference of the cloth's behavior using the mass-spring system method with different Kₛ 89

〈Figure Ⅳ-4-4〉 The comparison of the behavior of the cloth model using the constraint enforcement method with and... 90

〈Figure Ⅳ-4-5〉 The comparison of the behavior of the cloth model using the ACAD method with different coefficient Kₛ 91

〈Figure Ⅳ-4-6〉 The result of the cloth's response to a significant force applied to it 92

〈Figure Ⅳ-4-7〉 The result of the cloth model using mass-spring system method and the ACAD method with a... 93

〈Figure Ⅳ-4-8〉 Performance results between CPU-based PBD method for Unity3D and OpenGL and measure in frame... 94

〈Figure Ⅳ-4-9〉 Performance results between GPU-based PBD method and Unity's Cloth implement on Unity3D and... 95

〈Figure Ⅳ-4-10〉 The different of the cloth's behavior using different stiffness of the stretching constraint parameter 96

〈Figure Ⅳ-4-11〉 The different of the cloth's behavior using different stiffness of the bending constraint parameter 97

〈Figure Ⅳ-4-12〉 The difference of the cloth's behavior using different numbers of iterations to solve the constraints 97

〈Figure Ⅳ-4-13〉 The snapshot of the cloth model collide with the sphere object 98

〈Figure Ⅴ-1-1〉 The transformation procedure of a surface mesh into a volumetric mesh... 103

〈Figure Ⅴ-3-1〉 Flowchart of deformable object simulation using the PBD method with compute shader 111

〈Figure Ⅴ-4-1〉 The 3D objects used in this proposed simulation 113

〈Figure Ⅴ-4-2〉 Performance comparison of deformable object simulation using CPU-based and GPU-based MSM and VPC approaches for Unity3D... 114

〈Figure Ⅴ-4-3〉 Snapshots of the proposed simulation using different numbers of stiffness coefficients to control the... 115

〈Figure Ⅴ-4-4〉 The maximum volume loss of free-fall simulation 116

〈Figure Ⅴ-4-5〉 Snapshot during the free-fall simulation utilizing MSM (indicated in red), and VPC (indicated in blue) 117

〈Figure Ⅴ-4-6〉 Our proposed method (blue) and the MSM(red) were compared regarding its ability to handle deformable... 118

〈Figure Ⅴ-4-7〉 Snapshot of cube twisting simulation with MSM method (red) and our proposed method (blue) 119

〈Figure Ⅴ-4-8〉 Performance comparison of deformable object simulation using CPU-based... 120

〈Figure Ⅴ-4-9〉 Volume error over the simulation time in the free-fall simulation of the Bunny and Armadillo model with different iteration... 122

〈Figure Ⅴ-4-10〉 Snapshots of the simulation using the Bunny model with different number iteration 124

〈Figure Ⅴ-4-11〉 Snapshots of the simulation using the Armadillo model with different number iteration 125