Geometric Data Structures for Computer Graphics

✍ Scribed by Elmar Langetepe, Gabriel Zachmann

• Publisher: CRC Press
• Year: 2006
• Tongue: English
• Leaves: 362
• Category: Library

✦ Synopsis

Data structures and tools from computational geometry help to solve problems in computer graphics; these methods have been widely adopted by the computer graphics community yielding elegant and efficient algorithms. This book focuses on algorithms and data structures that have proven to be versatile, efficient, fundamental, and easy to implement. The book familiarizes students, as well as practitioners in the field of computer graphics, with a wide range of data structures. The authors describe each data structure in detail, highlight fundamental properties, and present algorithms based on the data structure. A number of recent representative and useful algorithms from computer graphics are described in detail, illuminating the utilization of the data structure in a creative way.

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Dedication
Table of Contents
Preface
1: Quadtrees and Octrees
1.1 Definition
1.2 Complexity and Construction
1.3 Height Field Visualization
1.4 Isosurface Generation
1.5 Ray Shooting
1.6 3D Octree
1.7 5D Octree
2: Orthogonal Windowing and Stabbing Queries
2.1 Interval Trees
2.2 Segment Trees
2.3 Multi-Level Segment Trees
2.4 Kd-Trees
2.5 Range Trees
2.6 The (Axis-Parallel Box/Axis-Parallel Box) Windowing Problem
2.7 Texture Synthesis
2.8 Shape Matching
3: BSP Trees
3.1 Rendering without a Z-Buffer
3.2 Representing Objects with BSPs
3.3 Boolean Operations
3.4 Construction Heuristics
4: Bounding Volume Hierarchies
4.1 Construction of BVHs
4.2 Updating for Morphing Objects
4.3 Collision Detection
5: Distance Fields
5.1 Computation and Representation of DFs
5.2 Applications of DFs
6: Voronoi Diagrams
6.1 Definitions and Properties
6.2 Computation
6.3 Generalization of the Voronoi Diagram
6.4 Applications of the Voronoi Diagram
6.5 Voronoi Diagrams in Computer Graphics
7: Geometric Proximity Graphs
7.1 A Small Collection of Proximity Graphs
7.2 Classification
7.3 Surfaces Defined by Point Clouds
7.4 Intersection Detection between Point Clouds
8: Kinetic Data Structures
8.1 General Terminology
8.2 Static Segment Tree
8.3 Kinetic Segment Tree
8.4 Kinetic BSP in the Plane
9: Degeneracy and Robustness
9.1 Examples of Instability in Geometric Algorithms
9.2 Formal Definition of Robustness and Stability
9.3 Geometric Computing and Arithmetic
9.4 Robust Expressions and Predicates
9.5 Degeneracy
9.6 Imprecise Arithmetic Approach
9.7 Practical Recommendations and Existing Packages
10: Dynamization of Geometric Data Structures
10.1 Example of Dynamization
10.2 Model of the Dynamization
10.3 Amortized Insert and Delete
10.4 Dynamization for Worst-Case Performance
10.5 Application to Search Query Data Structures
Bibliography
Index