News

Oct, 2017: EUROVR association is co-financing an important initiative: the VR Tour. Organized by Laval Virtual, the tour is scheduled to visit the various actors operating in the fields of Virtual and Augmented Reality in all Europe.

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: PhD thesis 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!

Computational Geometry - SS 17

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 in various fields of practical computer science, yielding elegant and efficient algorithms. This course aims at endowing practitioners with a working knowledge of a wide range of algorithms, methods, and tools from computational geometry. It will enable attendees to recognize geometric problems in their respective field of work and select the most suitable data structure. In the ourse, I will show this with a number of examples, which are mostly situated in the area of visual computing.

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, robotics, machine learning, spatial databases, visualization, simulation, and many others.

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 that they not intimidated by formal proofs. If you have attended my Computer Graphics course in the Bachelor's 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 a lot of areas of practical computer science (see above).
  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 visual computing.
  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 practical computer science. Therefore, we will not assign practical, but only (easy) theoretical exercises.

News


Topics

The following table contains the topics presented in class.

Week Topics Assignments
1. Quadtrees: definition, complexity of quadtrees over points, navigation in quadtrees, balanced quadtrees, complexity of balancing operation, meshing for integer polylines using quadtrees,
2. Quadtrees 2: Closest points problem, meshing for arbitrary polylines, variants of quadtrees/octrees and generalizations, storage and implemenation, space-filling curves, Morton codes, Assignment 1
3. Applications of quadtrees: reconstruction of 3D objects from image sequences, summed area tables, image compression, texture compression using BTC, CCC, and S3TC,
4. Isosurfaces: definition, marching cubes, acceleration using octrees, solving stabbing queries using the span space, isosurfaces over time-varying scalar fields, Assignment 2
5. Kd-Trees: definition, construction, complexity of the construction, variants of kd-trees, Nearest-neighbor (NN) search using kd-trees, k-NN classification.
four-dimensional geometric thinking, curse of dimensionality.
6. Approximate nearest neighbor (ANN) search: algorithm, correctness, running time; "best" ANN algorithms (randomized kd-tree, PCA-RKD, RKD forest), experimental results; applications: texture synthesis, implicit surfaces over point clouds using weighted moving least squares, iterative closest points (ICP) Assignment 3
7. BSP-Trees: definition, examples, construction algorithm, complexity of BSPs (expected size and construction running time), simple applications of BSPs (ray shooting, hidden surface elimination)
9. Construction of good BSPs using heuristics: cost function, case of known query distributions, deferred and self-organizing BSP trees.
BSPs representing polyhedra, Boolean operations (CSG operations) on solids using the BSP representation
10. Bounding volume hierarchies: definition of BVHs, tightness metrics for BVs, 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.
12. Convex hulls: definition, constructive proof for CH over sets of points, lower bound on complexity, more properties, convex combination, Euler's equation and application to polyhedra, construction of the CH in 3D with Clarkson-Shor's algorithm, application: convex collision detection (separating planes algorithm).
13. Voronoi diagrams: definition and basic properties, the lemma of the expanding circle, complexity of the VD. relationship between Voronoi diagrams and the convex hull, generalizations of VD's (higher-order sites, power diagram, additive weights, etc.), applications of VD's: bioinformatics.
Delaunay triangulations: definition of triangulations, defintion of DT's as dual of the Voronoi diagram, simple properties, theorem on the maximal minimal angle of DT's, minimum spanning tree as subgraph of the DT, nearest-neighbor graph as subgraph of the DT.

Here are the slides I showed during the lecture to illustrate the practical applications of the computational geometry concepts (and sometimes to explain a topic that can be better explained using slides). Note that not all of the slides were covered in class (you remember, I hope, which ones were covered :-) ).

Literature

Links and Online-Literature

Gabriel Zachmann
Last modified: Wed Jul 05 11:50:38 CEST 2017