News

Jun 17, 2017: Haptic and hand tracking demos at the Open Campus 2017.

Feb-Apr 2017: David Vilela (Mechanical Engineering Laboratory, University of Coruna, Spain) visited our lab. He is working on benchmarks to compare different intersection calculation methods in collisions, and also different force models.

Feb 2017: G. Zachmann and J. Teuber visited the Mahidol University in Bangkok, Thailand as part of a delegation from the University of Bremen. The goal of the visit was to foster the cooperation between the two universities and lay ground-work for future colaborations.

Jun 2016: Radio Bremen visited our lab to film the works of the Creative Unit "Intra-Operative Information" for a news magazine on the local TV station. Click here for the film at Radio Bremen. And Click here for the same film on our Website.

May 16, 2016: Patrick Lange was honored with the SIGSIM Best PhD Award at the ACM SIGSIM PADS Conference 2016.

Jun 19-21, 2015: G. Zachmann gives invited talk at the DAAD-Stipendiatentreffen in Bremen, Germany.

Jun 2015: Haptic and hand tracking demos at the Open Campus 2015.

Dec 08-10, 2014: ICAT-EGVE 2014 and EuroVR 2014 conferences at the University of Bremen organized by G. Zachmann.

Sep 25-26, 2014: GI VR/AR 2014 conference at the University of Bremen organized by G. Zachmann.

Sep 24-25, 2014: VRIPHYS 2014 conference at the University of Bremen organized by G. Zachmann .

Feb 4, 2014: G. Zachmann gives invited talk on Interaction Metaphors for Collaborative 3D Environments at Learntec.

Jan 2014: G. Zachmann got invited to be a Member of the Review Panel in the Human Brain Project for the Competitive Call for additional project partners

Nov 2013: Invited Talk at the "Cheffrühstück 2013"

Oct 2013: Dissertation of Rene Weller published in the Springer Series on Touch and Haptic Systems.

Jun 2013: G. Zachmann participated in the Dagstuhl Seminar Virtual Realities (13241)

Jun 2013: Haptic and hand tracking demos at the Open Campus 2013.

Jun 2013: Invited talk at Symposium für Virtualität und Interaktion 2013 in Heidelberg by Rene Weller.

Apr 2013: Rene Weller was honored with the EuroHaptics Ph.D Award at the IEEE World Haptics Conference 2013.

Jan 2013: Talk at the graduation ceremony of the University of Bremen by Rene Weller.

Oct 2012: Invited Talk by G. Zachmann at the DLR VROOS Workshop Servicing im Weltraum -- Interaktive VR-Technologien zum On-Orbit Servicing in Oberpfaffenhofen, Munich, Germany.

Oct 2012: Daniel Mohr earned his doctorate in the field of vision-based pose estimation.

Sept 2012: G. Zachmann: Keynote Talk at ICEC 2012, 11th International Conference on Entertainment Computing.

Sep 2012: "Best Paper Award" at GI VR/AR Workshop in Düsseldorf.

Sep 2012: Rene Weller earned his doctorate in the field of collision detection.

Aug 2012: GI-VRAR-Calendar 2013 is available!

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