Level of Detail for 3D Graphics

Table of Contents

Foreword

Preface

About the Authors

Part I: Generation

1. Introduction

Coverage and audience

History

Simplifications in computer graphics

LOD Frameworks

Discrete LOD

Continuous LOD

View-dependent LOD

LOD in practice

Polygonal meshes

Topology

Fidelity metrics

2. Mesh Simplification

Overview

Fidelity-based Simplification

Budget-based Simplification

Local Simplification Operations

Edge-Collapse

Mesh Foldover

Topological Inconsistency

Vertex-Pair Collapse

Triangle Collapse

Cell Collapse

Vertex Removal

Polygon Merging

General Geometric Replacement

Comparing the Local Simplification Operators

Global Simplification Operators

Volume Processing

Low Pass Filtering

Morphological Operators

Alpha-hull-based Topology Simplifications

When is Topology Simplification Desirable?

When is Topology Simplification Unacceptable?

Simplification Frameworks

Non-Optimizing

Greedy

Lazy

Estimating

Independent

Interleaved Simplification Operators

Conclusions

3. Simplification Error Metrics

Why Measure Error

Guide and Improve Simplification Process

Know the Quality of the Results

Know When to Show a Particular LOD

Balance Quality Across a Large Environment

Key Elements

Geometric Error

Hausdorff Distance

Mapping Distance

Maximum Versus Average Error

Screen-space Error

Attribute Error

Colors

Normals

Texture Coordinates

Combining Errors

Incremental and Total Error

Optimization

Range of Approaches

Vertex-Vertex Distance

Uniform Grid-based Vertex Clustering

Hierarchical Grid-based Vertex Clustering

Floating Cell-based Vertex Clustering

Vertex-Plane Distance

Maximum Supporting Plane Distance

Error Quadrics

Vertex-Surface Distance

Mesh Optimization and Progressive Meshes

Metro

Surface-Surface Distance

Simplification Envelopes

Tolerance Volumes

Mappings on the Surface

Mappings in the Plane

Mappings in Texture Space

Image Metric

Part II: Application

4. Runtime Frameworks

LOD Selection Factors

Distance

Size

Priority

Hysteresis

Environmental Conditions

Perceptual Factors

Fixed Frame Rate Schedulers

Reactive Fixed Frame Rate

Predictive Fixed Frame Rate

View-Independent LOD

Continuous LOD

View-Dependent LOD

Overview

The Vertex Hierarchy

Variations on the Vertex Hierarchy

View-dependent Criteria

Tracking Mesh Dependencies

Explicit Dependencies

Implicit Dependencies

Global Simplification

Blending Between Transitions

Alpha Blending

Geomorphs

5. Catalog of Useful Algorithms

Vertex Clustering

Overview

Vertex importance

Clustering vertices and filtering degenerate triangles

Displaying degenerate triangles

Advantages and disadvantages

Floating-cell clustering

Simplifying massive models

Vertex Decimation

Overview

Classification of vertices

Decimation criteria

Triangulation

Advantages and disadvantages

Topology-modifying continuous LOD

Quadric Error Metrics

Overview

Recap: measuring surface error with quadrics

Candidate vertex pairs

Details of the algorithm

Accounting for vertex attributes

Image-driven Simplification

Overview

Image Metrics

Evaluating Edge Cost

Fast Image Updates

Skip Strips

An aside: the vertex cache

Triangulation of Polygonal Models

6. Gaming Optimizations

Introduction

The Game Environment

Constant framerate

Very low memory

Multiple Instantiations

Scalable Platforms

Fill-Rate vs. Triangle Rate

Average Triangle Size

Game-specific difficulties with LOD

Modeling Practices

Vertex Representation

Texture Compositing

Non-standard Geometry

Hardware Transformation & Lighting

Static and Dynamic Geometry

Cache Coherence and Triangle Strips

Vector-Unit packetization

Classic LOD Suitability to games

Discrete-level LOD

Shared Vertex Format

Separate Vertex Format

Automated vs. Manual Processing

Continuous LOD

Run-time processing for CLOD

Complications with CLOD

Degenerate Faces

CLOD and Degenerating Strips

Higher-order surfaces

Shadow LOD

Non-Geometric Level of Detail

Shader LOD

Effect Scaling

Vertex processing LOD

Lighting LOD

Transformation LOD

Object Priority

Lighting

Imposters

Pre-Rendered Texture Imposters

Render-to-texture

Geometric Imposters

Selection and Metrics

Distance Selection

Game-specific Metrics

LOD Blending

Conclusion

7. Terrain Level of Detail

Introduction

Multiresolution Techniques for Terrain

Top-Down and Bottom-Up

Regular Grids and TINs

Quadtrees and Bintrees

Tears, Cracks, and T-Junctions

Paging, Streaming, and Out-of-Core

Texture-Mapping Issues

Paging of Large Textures

Hardware Support for Large Textures

Detail Textures

Catalog of Useful Terrain Algorithms

Continuous LOD for Height Fields

The ROAM Algorithm

Real-Time Generation of Continuous LOD

View-Dependent Progressive Meshes for Terrain

Multi-Triangulation

Visualization of Large Terrains Made Easy

Georeferencing Issues

Ellipsoids

Geoids

Datums

Coordinate Systems

Geospatial File Formats

Terrain data on the Web

Conclusions

Part III: Advanced Issues

8. Perceptual Issues

Motivation

Some Perceptually Motivated LOD Criteria

Eccentricity Level of Detail

Velocity Level of Detail

Depth of Field Level of Detail

Applicability of Gaze-Directed Techniques

The Need For Better Perceptual Models

Introduction to Vision

The Visual System

The Eye

The Retina

The Retinal Ganglion Cells

The Visual Cortex

Sensitivity to Visual Detail

Spatial Resolution

Variation Across the Retina

Temporal Sensitivity

The Multichannel Model

Measuring Visual Sensitivity

Contrast Gratings and Spatial Frequency

The Contrast Sensitivity Function

An Aside: Visual Acuity

Applicability of the CSF Model

Other Visual Phenomena

Factors Affecting Visibility

Hyperacuity

The Blind Spot

Saccades

Visual Masking

Temporal Thresholds