Geometric Data Structures and Algorithms for Computer Graphics  SS 15
Where should you place a new cell phone transmitter in a city such that its coverage area does not overlap with other, existing cell phone transmitters? How should you connect the nodes of a height field such that you obtain a plausible 3D terrain? How can you compress images very easily and still get a decent compression rate? (JPEG achieves very good compression rates, but it also is very complex.)
In recent years, methods from computational geometry have been widely adopted by the computer graphics community yielding elegant and efficient algorithms. This course aims at endowing practitioners in the computer graphics field with a working knowledge of a wide range of geometric data structures from computational geometry. It will enable readers to recognize geometric problems and select the most suitable data structure when developing computer graphics algorithms.
The course will focus on geometric algorithms and data structures that have proven to be versatile, efficient, fundamental, and easy to implement. Thus students will benefit immediately from this course, if they are interested in areas such as computer graphics, computer vision, computational geometry, spatial databases, visualization, simulation, and many others.
Our goal is to familiarize practitioners and researchers in computer graphics with some very versatile and ubiquitous geometric data structures, enable them to readily recognize geometric problems during their work, modify the algorithms to their needs, and hopefully make them curious about further powerful treasures to be discovered in the area of computational geometry.
There are no formal prerequisites for this course; it is selfcontained. It does not require knowledge of mathematics beyond high school algebra, but it does assume that students are comfortable with rigorous thinking, and not intimidated by formal proofs. Also, my computer graphics courses are not mandatory, but they might help you better appreciate the techniques you will learn in this course. If you have attended my Computer Graphics course in the bachelor program (CG1), then your feelings towards the chapter on triangulation can serve as an indicator whether or not this course will be interesting and rewarding to you.
This course is for you, if you want to acquire ...
 Knowledge and mastering of some of the geometric data structures that are very important for many methods in computer graphics (and other areas).
 Indepth insights into the reasons why algorithms become very efficient by using these data structures.
 Knowledge of some applications of these data structures in computer graphics.
 Some skills in proving the correctness and complexity analysis of geometric algorithms.
Some of the envisioned topics (these might change a little during the semester):
 Quadtrees / octrees, texture compression, isosurfaces, terrain visualization.
 Kdtrees, texture synthesis, point cloud surfaces,
 BSP trees, boolean operations on solids,
 Bounding volume hierarchies.
 Kinetic data structures, collision detection.
 Convex hulls.
 Voronoi and Delaunay diagrams, facility location problems, approximation to the TSP.
 Rangetrees and prioritysearch trees, range queries on the grid.
Note: the exact combination of topics will be modified a little bit each time.
This course is at the intersection of computational geometry and computer graphics. Therefore, we will not assign practical, but only (easy) theoretical exercises.
Topics
The following table contains the topics presented in class.
Week  Topics  Exercises 

1.  Quadtrees: navigation in quadtrees, balanced quadtrees  
2. 
Meshing with quadtrees for integer polylines,
meshing for arbitrary polygons. Closest points problem. 

3. 
Variants of quadtrees/octrees and generalizations,
Implementation of quadtrees (Morton codes etc.),
image compression using quadtrees,
Isosurfaces: definition, marching cubes, acceleration using octrees, 

4.  Exkurs: Kompetitive Strategien (am Beispiel "Suche nach einer Tür in der Wand"), Suchtiefenverdopplung, lineare Rekursion  
5.  Isosurfaces over timevarying scalar fields using the span space, Pointinpolygon test using octrees, Nearest neighbor search with octrees, accelerating ray casting with octrees,  
6. 
KdTrees: definition, construction, complexity of the construction, variants of kdtrees,
Nearestneighbor (NN) search using kdtrees. Curse of dimensionality 

7.  Approximate nearest neighbor (ANN) search: algorithm, correctness, running time; proof for the number of visited nodes in the ANN algorithm (by establishing the Hypercube Stabbing Lemma and the Packing Lemma for LongestSide KdTrees).  
8.  Applications of NN search: texture synthesis, statistical shape matching, surfaces over point clouds  
9.  BSPTrees: definition, examples, construction algorithm, complexity of BSPs (expected size and construction running time), BSPs over convex polyhedra, applications of BSPs (ray shooting, point location in closed polyhedra, hidden surface elimination)  
9.  BSPtrees: Boolean operations on solids using the BSP representation  
10. 
Kinetic data structures:
general algorithmic technique, tournament tree (kinetic heap),
(static) segment tree (for stabbing queries),
kinetic segment tree; Bounding volume hierarchies 1: definition of BVHs, tightness metrics for BVs. 

12. 
Bounding volume hierarchies: construction using insertion strategy (= SalmonGoldsmith),
surface area heuristic (SAH), topdown construction, construction in configurationspace
using kdtrees, efficiency of bounding boxes as BVs for neighbor filtering (broad phase),
computation of OBBs, application of kDOPs for raytracing,
different kinds of BVs, collision detection using BVHs.
Convex hulls 1: definition, CH over sets of points, Graham's scan. 

13. 
Convex hulls 2: lower bound on complexity, more properties,
geometric robustness and stability, applications. Voronoi diagrams: definition and basic properties, the lemma of the expanding circle, complexity of the VD. 

14. 
Voronoi diagrams 2:
relationship between Voronoi diagrams and the convex hull,
complexity of VD's,
generalizations of VD's (higherorder sites, power diagram,
additive weights, etc.). Applications of VD's: river mile coord system, clustering, molecular dynamics. Delaunay triangulations: definition, relationship with VD's, Thales theorem and edge flips, theorem on the maximal minimal angle of DT's, construction of 2D Delaunay triangulations. 
Hier finden Sie die Folien, die während der Vorlesung zu Illustrationszwecken gezeigt wurden.
Literature
 Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications; Springer
 Franco P. Preparata, Michael Ian Shamos: Computational Geometry: An Introduction; Springer
 Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen; Springer
 Joseph O'Rourke: Computational Geometry in C. Cambridge University Press
 G. Zachmann & E. Langetepe: Geometric Data Structures for Computer Graphics CRC Press, 2006, ISBN: 9781568812359 (in the past AK Peters)
 Satyan L. Devadoss, Joseph O'Rourke: Discrete and Computational Geometry. Princeton University Press. (Kapitel 1 zum Thema Triangulation)
Links and OnlineLiterature
 Marching Cubes Demo
 Isosurface extraction where users can define the implicit function by themselves (metaballs rendering)
 Here you can find Python code and the results of some experiments of approximate nearestneighbor search in ddimensional spaces by kdtrees.
 Introduction to Kinetic Data Structures by Leonidas Guibas (Source: Handbook of Data Structures and Applications")
Gabriel Zachmann
Last modified: Mon Aug 29 16:37:40 CEST 2016