Oberseminar

Wintersemester 2019/2020

Jannik Castenow

October 16, 2019, 14:00 pm, F1.110

Stretching a Communication Chain of Oblivious Mobile Robots — The Continuous Case

In the talk, we consider the problem of arranging a communication of n robots on a straight line of length n-1. The robots have a limited viewing range of 1, do not agree on a coordinate system or compass and are oblivious. In contrast to previous talks about this problem, we consider the continuous time model in which robots can continuously observe their environment and can immediately adjust their own trajectory based on their observations. We introduce the Max-Move-On-Bisector strategy, analyze its behavior in one-dimensional configurations and give insights about the current state of research about two-dimensional configurations.

Sascha Brandt

October 09, 2019, 14:00 pm, F1.110

Visibility-Aware Progressive Farthest Point Sampling on the GPU

In this talk, I present the first algorithm for progressive sampling of 3D surfaces with blue noise characteristics that runs entirely on the GPU. The performance of the algorithm is comparable to state-of-the-art GPU Poisson-disk sampling methods, while additionally producing ordered sequences of samples where every prefix exhibits good blue noise properties.

The basic idea is, to reduce the 3D sampling domain to a set of 2.5D images which we sample in parallel utilizing the rasterization hardware of current GPUs. This allows for simple visibility-aware sampling that only captures the surface as seen from outside the sampled object, which is especially useful for point-based level-of-detail rendering methods. However, the method can be easily extended for sampling the entire surface without changing the basic algorithm. I provide a statistical analysis of our algorithm and show that it produces good blue noise characteristics for every prefix of the resulting sample sequence and analyze the performance of the method compared to related state-of-the-art sampling methods.

 

Sommersemester 2019

Michael Braun

October 02, 2019, 14:00 pm, F1.544

Local Gathering of Mobile Robots in Three Dimensions

In the future, large groups of inexpensive robots might be used to collectively perform a variety of tasks. In order to facilitate this, there has been a considerable interest in the investigation of related algorithmic and complexity problems.

One particular problem that has been studied is robot-gathering in which all robots have to meet at some (non-specified) point in a Euclidean space, starting from an arbitrary configuration. Furthermore, it is typically assumed that the robots only have a limited vision range, share no information and have to act in a distributed fashion.

In this setting and under a synchronous, discrete time model, Ando et al. presented an algorithm called Go-to-the-Center, that solves this problem. Degener et al. could then show that this takes \theta(n^2) rounds. Under a continuous time model, Podlipyan described the class of contracting algorithms, for which he could show a gathering time of O(nd), where d is the initial diameter of the configuration. Kempkes et al. could show that a member of this class known as Move-on-Bisector can solve gathering in time O(n) in the continuous time setting.

However, all of these results have so far only been established in the two-dimensional Euclidean space. The goal of my master's thesis is therefore to attempt to find generalizations of these results for three or even higher dimensions.

(Introductory presentation Master's thesis)

 

Project group DragRace

September 30, 2019, 2:00 pm, F1.110

Dynamic Rendering And Generation of Real-time Adaptive Complex Environments

In this presentation we will give an overview over the work of the DRAGRACE project group. We have created a 3D-environment generator capable of dynamically generating randomized landscapes during runtime in virtually arbitrary size featuring among other things cities, different vegetation and various terrain types. The generator has a server component enabling multiple users to explore these landscapes at the same time. Our work has been implemented using the PADrend platforms to provide easily extendable rendering functions.

(Final presentation)

 
Ansgar Mährlein

August 14, 2019, 2:00 pm, F1.110

Performance Optimization for FlightSimulation through CullingAlgorithms

In the final presentation of my master thesis, i will present occlusion culling algorithms for flight simulation. Scenes encountered in flight simulators are usually quite flat with a viewpoint high above the scene. However, when simulating low enough flight in alpine regions, the undulating terrain can provide a high level occlusion. Additionally, the three-dimensional cockpit model of some simulators can also occlude large parts of the scenery. I will present two algorithms that take advantage of the occlusion in the two aforementioned cases, and show that performance gains of up to 400% are attainable in flight simulation use cases in mountainous regions.

(Final presentation Master's thesis)

 

Sören Möllers

May 08, 2019, 14:15, F1.110

Effiziente prozedurale Generierung von Flüssen und Seen mithilfe lokaler Simulation von Erosion

Prozedural Generierung virtueller Landschaften ist für viele Computerspiele und Simulationen essentieller Bestandteil. Oft werden Erosionsprozesse von Wasser simuliert, die Flüsse und Seen produzieren und die Landschaft natürlicher wirken lassen. Diese Methoden bauen auf regulären Gittern als Repräsentation der Landschaft auf und führen unnötige Berechnungen aus auch in Bereichen, die nicht von Erosion betroffen sind. Um diese aufwändigen Simulationen zu beschleunigen, wird eine Methode vorgeschlagen, die die Simulationsgitter in einer hierarchischen Datenstruktur, genauer einer Art von Quadtree, speichert und so die Simulation auf Bereiche starker Erosion beschränkt. Dabei passt sich der Algorithmus adaptiv der Verteilung von Wasser an und erhöht in entsprechenden Regionen die Auflösung der Landschaft. Die Evaluation zeigt, dass eine solche adaptive Datenstruktur die Perfomance in einigen Situationen tatsächlich verbessern kann ohne die Simulationsqualität merklich zu mindern.

 

Simon Pukrop

May 08, 2019, 14:45, F1.110

Scheduling Algorithms for Multi-Operation Jobs with Setups on a Single Machine

In this final presentation of my master thesis, we will have a look at a realistic, but not much researched, scheduling setting. In the problem class we consider composed jobs represented by a set of operations, which themselves are ordered into different families. When scheduling operations of different families back to back one induces additional costs in the form of a setup time. We describe the quality of a schedule by its total completion time. I will present and explain our new (and first known) approach that yields polynomial time constant factor approximations for this NP-hard problem.