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 self-contained. 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 ...

  1. Knowledge and mastering of some of the geometric data structures that are very important for many methods in computer graphics (and other areas).
  2. In-depth insights into the reasons why algorithms become very efficient by using these data structures.
  3. Knowledge of some applications of these data structures in computer graphics.
  4. 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):

  1. Quadtrees / octrees, texture compression, isosurfaces, terrain visualization.
  2. Kd-trees, texture synthesis, point cloud surfaces,
  3. BSP trees, boolean operations on solids,
  4. Bounding volume hierarchies.
  5. Kinetic data structures, collision detection.
  6. Convex hulls.
  7. Voronoi and Delaunay diagrams, facility location problems, approximation to the TSP.
  8. Range-trees and priority-search 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 Assignment 1
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, 		Assignment 2
4. Exkurs: Kompetitive Strategien (am Beispiel "Suche nach einer Tür in der Wand"), Suchtiefenverdopplung, lineare Rekursion Assignment 3
5. Isosurfaces over time-varying scalar fields using the span space, Point-in-polygon test using octrees, Nearest neighbor search with octrees, accelerating ray casting with octrees,
6. Kd-Trees: definition, construction, complexity of the construction, variants of kd-trees, Nearest-neighbor (NN) search using kd-trees.
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 Longest-Side Kd-Trees). Assignment 4
8. Applications of NN search: texture synthesis, statistical shape matching, surfaces over point clouds
9. BSP-Trees: 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) Assignment 5
9. BSP-trees: 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. 		Assignment 6
12. Bounding volume hierarchies: construction using insertion strategy (= Salmon-Goldsmith), surface area heuristic (SAH), top-down construction, construction in configuration-space using kd-trees, efficiency of bounding boxes as BVs for neighbor filtering (broad phase), computation of OBBs, application of k-DOPs for ray-tracing, 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 (higher-order 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

Links and Online-Literature

Gabriel Zachmann
Last modified: Mon Aug 29 16:37:40 CEST 2016