Geometric data structures for computer graphics

Gabriel Zachmann Elmar Langetepe1568812353, 9781568812359

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 :
Title page……Page 1
Date-line……Page 2
Contents……Page 3
Epigraph……Page 6
Preface……Page 7
1.1 Definition……Page 11
1.2 Complexity and Construction……Page 12
1.3 Height Field Visualization……Page 14
1.4 Isosurface Generation……Page 18
1.6 3D Octree……Page 20
1.7 5D Octree……Page 23
2 Orthogonal Windowing and Stabbing Queries……Page 27
2.1 Interval Trees……Page 28
2.2 Segment Trees……Page 32
2.3 Multi-Level Segment Trees……Page 38
2.4 Kd-Trees……Page 43
2.5 Range Trees……Page 47
2.6 The (Axis-Parallel Box/Axis-Parallel Box) Windowing Problem……Page 51
2.7 Texture Synthesis……Page 55
2.8 Shape Matching……Page 58
3 BSP Trees……Page 61
3.1 Rendering without a Z-Buffer……Page 63
3.2 Representing Objects with BSPs……Page 64
3.3 Boolean Operations……Page 65
3.4 Construction Heuristics……Page 69
4 Bounding Volume Hierarchies……Page 75
4.1 Construction of BVHs……Page 79
4.2 Updating for Morphing Objects……Page 86
4.3 Collision Detection……Page 88
5 Distance Fields……Page 95
5.1 Computation and Representation of DFs……Page 97
5.2 Applications of DFs……Page 101
6 Voronoi Diagrams……Page 105
6.1 Definitions and Properties……Page 106
6.2 Computation……Page 111
6.3 Generalization of the Voronoi Diagram……Page 120
6.4 Applications of the Voronoi Diagram……Page 132
6.5 Voronoi Diagrams in Computer Graphics……Page 143
7 Geometric Proximity Graphs……Page 157
7.1 A Small Collection of Proximity Graphs……Page 158
7.2 Classification……Page 168
7.3 Surfaces Defined by Point Clouds……Page 174
7.4 Intersection Detection between Point Clouds……Page 180
8 Kinetic Data Structures……Page 191
8.1 General Terminology……Page 192
8.2 Static Segment Tree……Page 194
8.3 Kinetic Segment Tree……Page 195
8.4 Kinetic BSP in the Plane……Page 197
9 Degeneracy and Robustness……Page 205
9.1 Examples of Instability in Geometric Algorithms……Page 207
9.2 Formal Definition of Robustness and Stability……Page 214
9.3 Geometric Computing and Arithmetic……Page 216
9.4 Robust Expressions and Predicates……Page 254
9.5 Degeneracy……Page 270
9.6 Imprecise Arithmetic Approach……Page 283
9.7 Practical Recommendations and Existing Packages……Page 290
10 Dynamization of Geometric Data Structures……Page 297
10.1 Example of Dynamization……Page 299
10.2 Model of the Dynamization……Page 306
10.3 Amortized Insert and Delete……Page 309
10.4 Dynamization for Worst-Case Performance……Page 318
10.5 Application to Search Query Data Structures……Page 322
Bibliography……Page 325
Index……Page 345