E-raamat: Level of Detail for 3D Graphics

Foreword		ix
Preface		xix
About The Authors		xxiii
PART I Generation
Introduction		3	(16)
Coverage and Organization		6	(1)
History		7	(1)
Simplifications in Computer Graphics		8	(1)
Lod Frameworks		9	(4)
Discrete LOD		9	(1)
Continuous LOD		10	(1)
View-Dependent LOD		10	(2)
LOD in Practice		12	(1)
Polygonal Meshes		13	(4)
Topology		14	(3)
Fidelity Metrics		17	(2)
Mesh Simplification		19	(28)
Overview		19	(2)
Fidelity-Based Simplification		20	(1)
Budget-Based Simplification		20	(1)
Local Simplification Operators		21	(7)
Edge Collapse		21	(2)
Vertex-Pair Collapse		23	(1)
Triangle Collapse		24	(1)
Cell Collapse		24	(1)
Vertex Removal		25	(1)
Polygon Merging		25	(1)
General Geometric Replacement		26	(1)
Comparing the Local Simplification Operators		27	(1)
Global Simplification Operators		28	(10)
Volume Processing		29	(3)
Alpha-Hull-Based Topology Simplifications		32	(5)
When Is Topology Simplification Desirable?		37	(1)
When Is Topology Simplification Unacceptable?		37	(1)
Simplification Frameworks		38	(8)
Nonoptimizing		39	(1)
Greedy		40	(1)
Lazy		41	(1)
Estimating		42	(1)
Independent		43	(1)
Interleaved Simplification Operators		44	(2)
Conclusions		46	(1)
Simplification Error Metrics		47	(40)
Why Measure Error?		48	(2)
Guide and Improve the Simplification Process		48	(1)
Know the Quality of the Results		48	(1)
Know When to Show a Particular LOD		49	(1)
Balance Quality across a Large Environment		49	(1)
Key Elements		50	(11)
Geometric Error		50	(5)
Attribute Error		55	(5)
Combining Errors		60	(1)
Incremental and Total Error		60	(1)
Range of Approaches		61	(21)
Vertex-Vertex Distance		61	(4)
Vertex-Plane Distance		65	(4)
Vertex-Surface Distance		69	(3)
Surface-Surface Distance		72	(9)
Image Metric		81	(1)
Conclusions		82	(5)
PART II Application
Run-Time Frameworks		87	(34)
LOD Selection Factors		88	(8)
Distance		88	(2)
Size		90	(1)
Priority		91	(2)
Hysteresis		93	(1)
Environmental Conditions		94	(1)
Perceptual Factors		94	(2)
Fixed-Frame Rate Schedulers		96	(8)
Reactive Fixed-Frame Rate		96	(2)
Predictive Fixed-Frame Rate		98	(6)
View-Dependent Lod		104	(10)
Overview		104	(1)
The Vertex Hierarchy		105	(2)
Variations on the Vertex Hierarchy		107	(1)
View-Dependent Criteria		107	(3)
Tracking Mesh Dependencies		110	(3)
Global Simplification		113	(1)
Blending Between Transitions		114	(5)
Alpha Blending		114	(2)
Geomorphs		116	(3)
Conclusions		119	(2)
A Catalog of Useful Algorithms		121	(30)
Vertex Clustering		122	(6)
Overview		122	(1)
Vertex Importance		122	(1)
Clustering Vertices and Filtering Degenerate Triangles		123	(1)
Displaying Degenerate Triangles		124	(1)
Advantages and Disadvantages		124	(1)
Floating-Cell Clustering		125	(2)
Simplifying Massive Models		127	(1)
Vertex Decimation		128	(5)
Overview		129	(1)
Classification of Vertices		129	(1)
Decimation Criteria		130	(1)
Triangulation		130	(1)
Advantages and Disadvantages		130	(1)
Topology-Modifying Continuous LOD		131	(2)
Quadric Error Metrics		133	(3)
Overview		133	(1)
Recap: Measuring Surface Error with Quadrics		133	(1)
Candidate Vertex Pairs		134	(1)
Details of the Algorithm		135	(1)
Accounting for Vertex Attributes		135	(1)
RSimp: Reverse Simplification		136	(3)
Overview		136	(1)
Normal Variation Error Metric		137	(1)
Cluster Splitting		137	(1)
Advantages and Disadvantages		138	(1)
Simplifying Massive Models		139	(1)
Image-Driven Simplification		139	(3)
Overview		140	(1)
Image Metrics		141	(1)
Evaluating Edge Cost		142	(1)
Fast Image Updates		142	(1)
Skip Strips		142	(4)
An Aside: The Vertex Cache		146	(1)
Triangulation of Polygonal Models		146	(4)
Conclusions		150	(1)
Gaming Optimizations		151	(34)
Introduction		152	(1)
The Game Environment		152	(5)
Constant Frame Rate		152	(1)
Very Low Memory		153	(1)
Multiple Instantiations		153	(1)
Scalable Platforms		154	(1)
Fill Rate Versus Triangle Rate		154	(2)
Average Triangle Size		156	(1)
Game-Specific Difficulties with Lod		157	(6)
Modeling Practices		157	(3)
Hardware Transformation and Lighting		160	(1)
Static and Dynamic Geometry		161	(1)
Cache Coherence and Triangle Strips		162	(1)
Vector Unit Packetization		162	(1)
Classic Lod Suitability to Games		163	(8)
Discrete LOD		163	(3)
Continuous LOD		166	(3)
Higher-Order Surfaces		169	(1)
Shadow LOD		169	(2)
Nongeometric Level of Detail		171	(4)
Shader LOD		171	(1)
Vertex-Processing LOD		172	(2)
Object Priority		174	(1)
Lighting		175	(1)
Imposters		175	(5)
Prerendered Texture Imposters		176	(2)
Render-to-Texture		178	(1)
Geometric Imposters		179	(1)
Selection and Metrics		180	(2)
Distance Selection		180	(1)
Game-Specific Metrics		180	(1)
LOD Blending		181	(1)
Conclusions		182	(3)
Terrain Level of Detail		185	(46)
Introduction		186	(1)
Multiresolution Techniques for Terrain		187	(13)
Top Down and Bottom Up		187	(1)
Regular Grids and TINs		188	(2)
Quadtrees and Bintrees		190	(3)
Tears, Cracks, and T-Junctions		193	(1)
Paging, Streaming, and Out of Core		194	(4)
Texture-Mapping Issues		198	(2)
Catalog of Useful Terrain Algorithms		200	(18)
Continuous LOD for Height Fields		200	(2)
The Roam Algorithm		202	(4)
Real-Time Generation of Continuous LOD		206	(2)
View-Dependent Progressive Meshes for Terrain		208	(3)
Multitriangulation		211	(2)
Visualization of Large Terrains Made Easy		213	(5)
Georeferencing Issues		218	(7)
Ellipsoids		218	(2)
Geoids		220	(2)
Datums		222	(1)
Coordinate Systems		222	(3)
Geospatial File Formats		225	(1)
Terrain Data on the Web		226	(2)
Conclusions		228	(3)
PART III Advanced Issues
Perceptual Issues		231	(48)
Motivation		232	(1)
Some Perceptually Motivated Lod Criteria		232	(7)
Eccentricity Level of Detail		233	(2)
Velocity Level of Detail		235	(1)
Depth-of Field Level of Detail		236	(1)
Applicability of Gaze-Directed Techniques		237	(2)
The Need for Better Perceptual Models		239	(1)
Introduction to Vision		239	(9)
The Visual System		239	(1)
The Eye		240	(5)
The Visual Cortex		245	(1)
Sensitivity to Visual Detail		245	(2)
The Multichannel Model		247	(1)
Measuring Visual Sensitivity		248	(16)
Contrast Gratings and Spatial Frequency		248	(2)
The Contrast Sensitivity Function		250	(1)
An Aside: Visual Acuity		250	(2)
Applicability of the CSF Model		252	(3)
Other Perceptual Phenomena		255	(8)
Further Reading		263	(1)
Managing Lod Through Visual Complexity		264	(1)
Modeling Contrast Sensitivity		265	(7)
Incorporating Velocity into the Model		266	(1)
Incorporating Eccentricity into the Model		267	(2)
Modeling Visual Acuity		269	(1)
Incorporating the Display into the Model		269	(1)
Visualizing the Effect of the Perceptual Model		270	(2)
Example Implementations		272	(5)
Perceptually Modulated LOD		272	(1)
Imperceptible Gaze-Directed Simplification		273	(2)
Perceptually Optimized 3D Graphics		275	(2)
Conclusions		277	(2)
Measuring Visual Fidelity		279	(22)
Why Measure Fidelity?		280	(1)
Experimental Measures		280	(6)
Search Performance		280	(1)
Naming Times		281	(2)
Subjective Ratings		283	(1)
Threshold Testing		284	(1)
Comparing Experimental Measures		285	(1)
Automatic Measures for Static Imagery		286	(5)
Digital Measures		286	(1)
Single-Channel Measures		287	(1)
Multi-Channel Measures		288	(1)
Evaluating Measure Accuracy		289	(2)
Applications in Graphics		291	(1)
Automatic Measures for Run-Time Lod		291	(3)
Fidelity Measurement for Run-Time Lod		292	(1)
Contrast Sensitivity in Run-Time Lod		292	(2)
Automatic Measures for Simplification		294	(1)
Evaluation of Lod Techniques and Measures		295	(3)
Search with Low Fidelity Peripheries		295	(1)
Visual Fidelity Measures and Simplification		295	(3)
Conclusions		298	(3)
Temporal Detail		301	(30)
Introduction		301	(1)
Measuring Temporal Detail		302	(7)
Frame Rate and Refresh Rate		303	(2)
System Latency and Responsiveness		305	(2)
Two Example Systems		307	(2)
Controlling Temporal Detail		309	(6)
Frame-Only Manipulation		309	(1)
Latency-Only Manipulation		310	(2)
Frame-Latency Manipulation		312	(1)
Comparing and Using Manipulations		313	(2)
Temporal Detail and User Performance		315	(9)
Perceptual Limits		315	(1)
Open- and Closed-Loop Tasks		316	(1)
Closed-Loop Tasks as Dynamic Control Systems		317	(2)
Designing for Successful Dynamic Control		319	(2)
Temporal Detail and Complex Tasks		321	(3)
Trading Off Temporal and Visual Detail		324	(2)
A Practical Summarization		326	(3)
Conclusions		329	(2)
Glossary of Terms		331	(18)
References		349	(22)
Index		371

David Luebke David is an Assistant Professor in the Department of Computer Science at the University of Virginia. His principal research interest is the problem of rendering very complex scenes at interactive rates. His research focuses on software techniques such as polygonal simplification and occlusion culling to reduce the complexity of such scenes to manageable levels. Luebke's dissertation research, summarized in a SIGGRAPH '97 paper, introduced a dynamic, view-dependent approach to polygonal simplification for interactive rendering of extremely complex CAD models. He earned his Ph.D. at the University of North Carolina, and his Bachelors degree at the Colorado College. Dr. Martin Reddy holds a Ph.D. in Computer Science and has over 30 years of experience in the software industry. He is a Fellow of the IEEE, a Fellow of the AAIA, and a Distinguished Member of the ACM. He has published 10 patents, over 40 professional articles, and 2 books. Martin was co-founder and CTO of the AI startup, PullString, where he oversaw the development of the company's technology until it was acquired by Apple in 2019. While at Apple, Martin was a software architect responsible for the architecture and APIs of major components of the Siri virtual assistant. Before that, Dr. Reddy worked for 6 years at Pixar Animation Studios where he was a lead engineer for the studio's in-house animation system. He worked on several Academy Award Winning and Nominated films, such as "Finding Nemo", "The Incredibles", "Cars", "Ratatouille", and "Wall-E". He was also the hair model for Mr Incredible. Martin began his career at SRI International where he worked on a distributed 3D terrain visualization system and co-authored the geospatial functionality in the VRML and X3D ISO standards. Martin was awarded Alumnus of the Year by his alma mater, Strathclyde University.

Jonathan D. Cohen is an Assistant Professor in the Department of Computer Science at The Johns Hopkins University. He earned his Doctoral and Masters degrees from The University of North Carolina at Chapel Hill and earned his Bachelors degree from Duke University. His interests include polygonal simplification and other software acceleration techniques, parallel rendering architectures, collision detection, and high-quality interactive computer graphics. Jons e-mail address is cohen@cs.jhu.edu. Amitabh Varshney Amitabh is an Associate Professor in the Department of Computer Science at the University of Maryland. His research interests lie in interactive computer graphics, scientific visualization, molecular graphics, and CAD. Varshney has worked on several aspects of level-of-detail simplifications including topology-preserving and topology-reducing simplifications, view-dependent simplifications, parallelization of simplification computation, as well as using triangle strips in multiresolution rendering. Varshney received his PhD and MS from the University of North Carolina at Chapel Hill in 1994 and 1991 respectively. He received his B. Tech. in Computer Science from the Indian Institute of Technology at Delhi in 1989. Benjamin Watson Ben is an Assistant Professor in Computer Science at Northwestern University. He earned his doctoral and Masters degrees at Georgia Tech's GVU Center, and his Bachelors degree at the University of California, Irvine. His dissertation focused on user performance effects of dynamic level of detail management. His other research interests include object simplification, medical applications of virtual reality, and 3D user interfaces. Robert Huebner Robert is the Director of Technology at Nihilistic Software, an independent development studio located in Marin County, California. Prior to co-founding Nihilistic, Robert has worked on a number of successful game titles including "Jedi Knight: Dark Forces 2" for LucasArts Entertainment, "Descent" for Parallax Software, and "Starcraft" for Blizzard Entertainment. Nihilistic's first title, "Vampire The Masquerade: Redemption" was released for the PC in 2000 and sold over 500,000 copies worldwide. Nihilistic's second project will be released in the Winter of 2002 on next-generation game consoles. Robert has spoken on game technology topics at SIGGRAPH, the Game Developer's Conference (GDC), and Electronic Entertainment Expo (E3). He also serves on the advisory board for the Game Developer's Conference and the International Game Developer's Association (IGDA).