Level of Detail for 3D Graphics

David Luebke, Martin Reddy, Jonathan D. Cohen, Amitabh Varshney, Benjamin Watson, Robert Huebner9781558608382, 1558608389

Level of detail (LOD) techniques are increasingly used by professional real-time developers to strike the balance between breathtaking virtual worlds and smooth, flowing animation. Level of Detail for 3D Graphics brings together, for the first time, the mechanisms, principles, practices, and theory needed by every graphics developer seeking to apply LOD methods.Continuing advances in level of detail management have brought this powerful technology to the forefront of 3D graphics optimization research. This book, written by the very researchers and developers who have built LOD technology, is both a state-of-the-art chronicle of LOD advances and a practical sourcebook, which will enable graphics developers from all disciplines to apply these formidable techniques to their own work.* Is a complete, practical resource for programmers wishing to incorporate LOD technology into their own systems.* Is an important reference for professionals in game development, computer animation, information visualization, real-time graphics and simulation, data capture and preview, CAD display, and virtual worlds.* Is accessible to anyone familiar with the essentials of computer science and interactive computer graphics.* Covers the full range of LOD methods from mesh simplification to error metrics, as well as advanced issues of human perception, temporal detail, and visual fidelity measurement.* Includes an accompanying Web site rich in supplementary material including source code, tools, 3D models, public domain software, documentation, LOD updates, and more.

---

Table of contents :
Level of Detail fro 3D Graphics……Page 1
Foreword……Page 10
Contents……Page 12
Coverage and Audience……Page 20
Why We Wrote this Book……Page 21
Acknowledgments……Page 22
About the Web Site……Page 23
About the Authors……Page 24
Generation……Page 26
Introduction……Page 28
1.1 Coverage and Organization……Page 31
1.2 History……Page 32
1.3 Simplifications in Computer Graphics……Page 33
1.4.1 Discrete LOD……Page 34
1.4.3 View-Dependent LOD……Page 35
1.4.4 LOD in Practice……Page 37
1.5 Polygonal meshes……Page 38
1.5.1 Topology……Page 39
1.6 Fidelity Metrics……Page 42
2.1 Overview……Page 44
2.1.2 Budget-Based Simplification……Page 45
2.2.1 Edge Collapse……Page 46
2.2.2 Vertex-Pair Collapse……Page 48
2.2.4 Cell Collapse……Page 49
2.2.6 Polygon Merging……Page 50
2.2.7 General Geometric Replacement……Page 51
2.2.8 Comparing the Local Simplification Operators……Page 52
2.3 Global Simplification Operators……Page 53
2.3.1 Volume Processing……Page 54
2.3.2 Alpha-Hull–Based Topology Simplifications……Page 57
2.3.4 When Is Topology Simplification Unacceptable?……Page 62
2.4 Simplification Frameworks……Page 63
2.4.1 Nonoptimizing……Page 64
2.4.2 Greedy……Page 65
2.4.3 Lazy……Page 66
2.4.4 Estimating……Page 67
2.4.5 Independent……Page 68
2.4.6 Interleaved Simplification Operators……Page 69
2.5Conclusions……Page 71
Simplification Error Metrics……Page 72
3.1.2 Know the Quality of the Results……Page 73
3.1.4 Balance Quality across a Large Environment……Page 74
3.2.1 Geometric Error……Page 75
3.2.2 Attribute Error……Page 80
3.2.4 Incremental and Total Error……Page 85
3.3.1 Vertex–Vertex Distance……Page 86
3.3.2 Vertex–Plane Distance……Page 90
3.3.3 Vertex–Surface Distance……Page 94
3.3.4 Surface–Surface Distance……Page 97
3.3.5 Image Metric……Page 106
3.4 Conclusions……Page 107
Application……Page 110
Run-Time Frameworks……Page 112
4.1.1 Distance……Page 113
4.1.2 Size……Page 115
4.1.3 Priority……Page 116
4.1.4 Hysteresis……Page 118
4.1.6 Perceptual Factors……Page 119
4.2.1 Reactive Fixed-Frame Rate……Page 121
4.2.2 Predictive Fixed-Frame Rate……Page 123
4.3.1 Overview……Page 129
4.3.2 The Vertex Hierarchy……Page 130
4.3.4 View-Dependent Criteria……Page 132
4.3.5 Tracking Mesh Dependencies……Page 135
4.3.6 Global Simplification……Page 138
4.4.1 Alpha Blending……Page 139
4.4.2 Geomorphs……Page 141
4.5 Conclusions……Page 144
A Catalog of Useful Algorithms……Page 146
5.1.2 Vertex Importance……Page 147
5.1.3 Clustering Vertices and Filtering Degenerate Triangles……Page 148
5.1.5 Advantages and Disadvantages……Page 149
5.1.6 Floating-Cell Clustering……Page 150
5.1.7 Simplifying Massive Models……Page 152
5.2 Vertex Decimation……Page 153
5.2.2 Classification of Vertices……Page 154
5.2.5 Advantages and Disadvantages……Page 155
5.2.6 Topology-Modifying Continuous LOD……Page 156
5.3.2 Recap: Measuring Surface Error with Quadrics……Page 158
5.3.3 Candidate Vertex Pairs……Page 159
5.3.5 Accounting for Vertex Attributes……Page 160
5.4.1 Overview……Page 161
5.4.3 Cluster Splitting……Page 162
5.4.4 Advantages and Disadvantages……Page 163
5.5 Image-Driven Simplification……Page 164
5.5.1 Overview……Page 165
5.5.2 Image Metrics……Page 166
5.6 Skip Strips……Page 167
5.7 Triangulation of Polygonal Models……Page 171
5.8 Conclusions……Page 175
Gaming Optimizations……Page 176
6.2.1 Constant Frame Rate……Page 177
6.2.3 Multiple Instantiations……Page 178
6.2.5 Fill Rate Versus Triangle Rate……Page 179
6.2.6 Average Triangle Size……Page 181
6.3.1 Modeling Practices……Page 182
6.3.2 Hardware Transformation and Lighting……Page 185
6.3.3 Static and Dynamic Geometry……Page 186
6.3.5 Vector Unit Packetization……Page 187
6.4.1 Discrete LOD……Page 188
6.4.2 Continuous LOD……Page 191
6.4.4 Shadow LOD……Page 194
6.5.1 Shader LOD……Page 196
6.5.2 Vertex-Processing LOD……Page 197
6.5.3 Object Priority……Page 199
6.6 Imposters……Page 200
6.6.1 Prerendered Texture Imposters……Page 201
6.6.2 Render-to-Texture……Page 203
6.6.3 Geometric Imposters……Page 204
6.7.2 Game-Specific Metrics……Page 205
6.7.3 LOD Blending……Page 206
6.8 Conclusions……Page 207
Terrain Level of Detail……Page 210
7.1 Introduction……Page 211
7.2.1 Top Down and Bottom Up……Page 212
7.2.2 Regular Grids and TINs……Page 213
7.2.3 Quadtrees and Bintrees……Page 215
7.2.4 Tears, Cracks, and T-Junctions……Page 218
7.2.5 Paging, Streaming, and Out of Core……Page 219
7.2.6 Texture-Mapping Issues……Page 223
7.3.1 Continuous LOD for Height Fields……Page 225
7.3.2 The ROAM Algorithm……Page 227
7.3.3 Real-Time Generation of Continuous LOD……Page 230
7.3.4 View-Dependent Progressive Meshes for Terrain……Page 232
7.3.5 Multitriangulation……Page 235
7.3.6 Visualization of Large Terrains Made Easy……Page 237
7.4.1 Ellipsoids……Page 242
7.4.2 Geoids……Page 244
7.4.4 Coordinate Systems……Page 246
7.5 Geospatial File Formats……Page 249
7.6 Terrain Data on the Web……Page 250
7.7 Conclusions……Page 252
Advanced Issues……Page 253
Perceptual Issues……Page 255
8.2 Some Perceptually Motivated LOD Criteria……Page 256
8.2.1 Eccentricity Level of Detail……Page 257
8.2.2 Velocity Level of Detail……Page 259
8.2.3 Depth-of-Field Level of Detail……Page 260
8.2.4 Applicability of Gaze-Directed Techniques……Page 261
8.3.1 The Visual System……Page 263
8.3.2 The Eye……Page 264
8.3.4 Sensitivity to Visual Detail……Page 269
8.3.5 The Multichannel Model……Page 271
8.4.1 Contrast Gratings and Spatial Frequency……Page 272
8.4.3 An Aside: Visual Acuity……Page 274
8.4.4 Applicability of the CSF Model……Page 276
8.4.5 Other Perceptual Phenomena……Page 279
8.4.6 Further Reading……Page 287
8.5 Managing LOD Through Visual Complexity……Page 288
8.6 Modeling Contrast Sensitivity……Page 289
8.6.1 Incorporating Velocity into the Model……Page 290
8.6.2 Incorporating Eccentricity into the Model……Page 291
8.6.4 Incorporating the Display into the Model……Page 293
8.6.5 Visualizing the Effect of the Perceptual Model……Page 294
8.7.1 Perceptually Modulated LOD……Page 296
8.7.2 Imperceptible Gaze-Directed Simplification……Page 297
8.7.3 Perceptually Optimized 3D Graphics……Page 299
8.8 Conclusions……Page 301
Measuring Visual Fidelity……Page 303
9.2.1 Search Performance……Page 304
9.2.2 Naming Times……Page 305
9.2.3 Subjective Ratings……Page 307
9.2.4 Threshold Testing……Page 308
9.2.5 Comparing Experimental Measures……Page 309
9.3.1 Digital Measures……Page 310
9.3.2 Single-Channel Measures……Page 311
9.3.3 Multi-Channel Measures……Page 312
9.3.4 Evaluating Measure Accuracy……Page 313
9.4 Automatic Measures for Run-Time LOD……Page 315
9.4.2 Contrast Sensitivity in Run-Time LOD……Page 316
9.5 Automatic Measures for Simplification……Page 318
9.6.2 Visual Fidelity Measures and Simplification……Page 319
9.7 Conclusions……Page 322
10.1 Introduction……Page 325
10.2 Measuring Temporal Detail……Page 326
10.2.1 Frame Rate and Refresh Rate……Page 327
10.2.2 System Latency and Responsiveness……Page 329
10.2.3 Two Example Systems……Page 331
10.3.1 Frame-Only Manipulation……Page 333
10.3.2 Latency-Only Manipulation……Page 334
10.3.3 Frame-Latency Manipulation……Page 336
10.3.4 Comparing and Using Manipulations……Page 337
10.4.1 Perceptual Limits……Page 339
10.4.2 Open- and Closed-Loop Tasks……Page 340
10.4.3 Closed-Loop Tasks as Dynamic Control Systems……Page 341
10.4.4 Designing for Successful Dynamic Control……Page 343
10.4.5 Temporal Detail and Complex Tasks……Page 345
10.5 Trading Off Temporal and Visual Detail……Page 348
10.6 A Practical Summarization……Page 350
10.7 Conclusions……Page 353
Glossary of Terms……Page 355
References……Page 373
Index……Page 395
End Of Book……Page 414