### Transcription of Mesh Simplification - Computer graphics

1 **mesh** **Simplification** Applications Oversampled 3D scan data ~150k triangles ~80k triangles 2. Applications Overtessellation: E. g iso iso-surface surface extraction 3. Applications Multi-resolution Multi resolution hierarchies for efficient geometry processing level-of-detail (LOD) rendering 4. Applications Adaptation to hardware capabilities 5. Size-Quality Size Quality Tradeoff error size 6. Problem Statement Given: Find: such that 1. and is minimal, or 2. and is minimal Respect additional fairness criteria normal deviation, triangle shape, scalar attributes, etc. 7. **mesh** Decimation Methods Vertex clustering Incremental decimation Resampling **mesh** approximation 8. Vertex Clustering Cluster Generation Computing p g a representative p **mesh** generation Topology changes 9. Vertex Clustering Cluster Generation Uniform 3D grid Map vertices to cluster cells Computing a representative **mesh** generation Topology changes 10. Vertex Clustering Cluster Generation Hierarchical approach Top-down or bottom-up Computing a representative **mesh** generation Topology changes 11.

2 Vertex Clustering Cluster Generation Computing p g a representative p Average/median vertex position Error quadrics **mesh** generation Topology changes 12. Computing a Representative Average vertex position 13. Computing a Representative Median vertex position 14. Computing a Representative Error quadrics 15. Error Quadrics Patch is expected to be piecewise flat Minimize distance to neighboring g g triangles'. g p planes 16. Error Quadrics Squared distance of point p to plane q: 17. Error Quadrics Sum distances to planes qi of vertex'. vertex neighboring triangles: Point p p* that minimizes the error satisfies: 18. Comparison average median di error quadric di 19. Vertex Clustering Cluster Generation Computing p g a representative p **mesh** generation Clusters p {p0,..,pn}, q {q0,..,qm}. Topology changes 20. Vertex Clustering Cluster Generation Computing p g a representative p **mesh** generation Clusters p {p0,..,pn}, q {q0,..,qm}. Connect (p,q) if there was an edge (pi,qj). Topology changes 21.

3 Vertex Clustering Cluster Generation Computing p g a representative p **mesh** generation Topology changes If different sheets pass through one cell Can be non non-manifold manifold 22. Outline Applications Problem Statement **mesh** Decimation Methods Vertex Clustering Incremental Decimation Extensions 23. Incremental Decimation 24. Incremental Decimation General Setup Decimation operators p Error metrics Fairness criteria Topology Topolog changes 25. General Setup Repeat: pick **mesh** region pp y decimation operator apply p Until no further reduction possible 26. Greedy Optimization For each region evaluate quality after decimation enqeue(quality region). enqeue(quality, Repeat: get best **mesh** region from queue apply decimation operator update p q queue Until no further reduction possible 27. Global Error Control For each region evaluate quality after decimation enqeue(quality region). enqeue(quality, Repeat: get best **mesh** region from queue if error < . apply pp y decimation operator p update queue Until no further reduction possible 28.))

4 Incremental Decimation General Setup Decimation operators p Error metrics Fairness criteria Topology Topolog changes 29. Decimation Operators What is a "region". region ? What are the DOF for re-triangulation? g Classification Topology-changing vs. topology-preserving Subsampling vs. filtering Inverse operation progressive meshes 30. Vertex Removal Select a vertex to be eliminated 31. Vertex Removal Select all triangles sharing this vertex 32. Vertex Removal Remove the selected triangles triangles, creating the hole 33. Vertex Removal Fill the hole with new triangles 34. Decimation Operators Vertex Removal V t Insertion Vertex I ti Remove vertex Re-triangulate R ti l t hhole l Combinatorial degrees of freedom 35. Decimation Operators Edge Collapse Vertex Split Merge two adjacent vertices Define new vertex position Continuous degrees g of freedom Filter along the way 36. Decimation Operators Half-Edge Collapse Restricted Vertex Split Collapse C ll edge d iinto t one end d point i t Special case of vertex removal Special case of edge collapse No degrees of freedom Separates global optimization from local optimization 37.

5 Half-Edge Half Edge Collapse 38. Half-Edge Half Edge Collapse 39. Half-Edge Half Edge Collapse 40. Half-Edge Half Edge Collapse 41. Half-Edge Half Edge Collapse 42. Half-Edge Half Edge Collapse 43. Half-Edge Half Edge Collapse 44. Half-Edge Half Edge Collapse 45. Half-Edge Half Edge Collapse 46. Half-Edge Half Edge Collapse flip ! 47. Incremental Decimation General Setup Decimation operators p Error metrics Fairness criteria Topology Topolog changes 48. Local Error Metrics Local distance to **mesh** Compute average plane No comparison to original geometry 49. Global Error Metrics Error quadrics Squared distance to planes at vertex No bound on true error Q3 = Q1+Q2. Q1. Q2 v3. p1 p2. solve v3TQ3v3 = min piTQipi = 0, i={1,2}. < ? okk 50. Incremental Decimation General Setup Decimation operators p Error metrics Fairness criteria Topology Topolog changes 51. Fairness Criteria Rate quality of decimation operation Approximation error Triangle shape Dihedral angles g Valence balance.

6 52. Fairness Criteria Rate quality after decimation Approximation error r1. Triangle shape Dihedral angles g Valence balance .. r2. 53. Fairness Criteria Rate quality after decimation Approximation error Triangle shape Dihedral angles g Valence balance .. 54. Fairness Criteria Rate quality after decimation Approximation error Triangle shape Dihedral angles g Valence balance Color differences .. 55. Fairness Criteria Rate quality after decimation Approximation error Triangle shape Dihedral angles g Valence balance Color differences .. 56. Fairness Criteria Rate quality after decimation Approximation error Triangle shape Dihedral angles g Valence balance Color differences .. 57. Fairness Criteria Rate quality after decimation Approximation error Triangle shape Dihedral angles g Valence balance Color differences .. 58. Incremental Decimation General Setup Decimation operators p Error metrics Fairness criteria Topology Topolog changes 59. Topology Changes ? Merge vertices across non non-edges edges Changes **mesh** topology Need spatial neighborhood information Generates non-manifold meshes Vertex Contraction Vertex Separation 60.

7 Topology Changes ? Merge vertices across non non-edges edges Changes **mesh** topology Need spatial neighborhood information Generates non-manifold meshes manifold non-manifold 61. Comparison Vertex clustering fast, but difficult to control simplified **mesh** topology changes, non-manifold meshes g global error bound,, but often not close to optimum p Incremental decimation with quadric error metrics good trade-off between **mesh** quality and speed explicit control over **mesh** topology restricting normal deviation improves **mesh** quality 62.