Geometric Data Structures for Computer GraphicsData 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. |
Contents
Preface | xi |
x | 21 |
Orthogonal Windowing and Stabbing Queries | 30 |
Copyright | |
14 other sections not shown
Other editions - View all
Geometric Data Structures for Computer Graphics Elmar Langetepe,Gabriel Zachmann No preview available - 2019 |
Geometric Data Structures for Computer Graphics Elmar Langetepe,Gabriel Zachmann No preview available - 2006 |
Common terms and phrases
Additionally algorithm approximation assume binary decomposition BSP tree Burnikel cells CGAL circumcenter collision detection Computational Geometry Computer Graphics construction convex hull corresponding data structure DCEL defined definition Delaunay triangulation delete denote distance field dynamic edge flip efficient endpoints Equation evaluation exact example Figure floating-point arithmetic floating-point number function Geom geometric algorithm given Guibas IEEE implemented input integer interpolation search intersection interval kd-tree Klein Lemma line segments mod q neighbor node O(log O(n log objects octree orientation test Overmars p₁ perturbation plane point cloud polygons precision predicates problem Proc proximity graph quadtree recursive relative error representation represents robust scheme search tree Section segment tree set of points Shewchuk SIGGRAPH simple space sphere split stabbing query static surface tetrahedra Theorem training set triangle TwoSum V₁ VD(S vector vertex vertices Voronoi diagram WeakDelete operation x-coordinates Zachmann