Zumbs' Blog

The truth may be out there, but lies are inside your head

Education

This page contains a subset of projects I worked on at university, including my Masters and Bachelors thesis. Use the links below to jump directly to the projects in question.

  1. Masters Thesis: A Parallel Gauss-Seidel Method for Computing Contact Forces
  2. Bachelors Thesis: Suffikstræer og deres anvendelser
  3. Publications
  4. Projects

 

Masters Thesis: A Parallel Gauss-Seidel Method for Computing Contact Forces

Download
Supervisor: Kenny Erleben

Picture an empty mug of coffee at rest on a table. In the real world, the mug would not fall through the table. If one side of the table were elevated to a certain height, the mug would start to slide off the table. The problem of computing how two or more bodies in contact affect each other is called the contact problem, which is the subject of this thesis.

Solving the contact problem is an important bottleneck when running large simulations of multiple rigid bodies. Many traditional methods of solving the contact problem, such as the projected Gauss–Seidel method, are inherently sequential. However, with modern hardware advances, improvements in raw computing power have been realized by adding multiple cores to the processing units.

This poses a challenge. Can sequential algorithms be rephrased in a concurrent setting? Or are simpler, but embarrassingly parallel methods better suited? These are some of the questions this thesis aims to address.

Commonly used techniques for parallelizing a sequential algorithm start by expressing the internal dependencies of the problem in a convenient structure. The dependencies of the contact problem can be expressed by a contact graph, where each body is a node and each contact is an edge.

Applying an edge-coloring scheme to the contact graph can detect the internal dependencies of a given scene. The contacts in each color are independent of all contacts in that color, and can be solved in an embarrassingly parallel manner. This raises a number of questions. Which coloring scheme yields the best parallel performance? What sort of problems can a coloring scheme cause? Will the quality of the solution deteriorate when more cores are added? And how does it scale?

A number of parallel physics solvers based on the proximal map formulation of the contact problem have been implemented, analyzed and benchmarked. The solvers utilize Jacobi and Gauss–Seidel based ?xed point schemes.

The conclusions are that minimizing the number of colors maximize parallel performance of the Gauss–Seidel schemes, as the need for communication between cores is reduced. An even distribution of colors improves performance, as it makes load balancing easier with lower overhead. This method does not cause a deterioration of the quality of the sequential solver when more cores are added.

A highly unbalanced coloring can be addressed by merging colors with few contacts into a larger color, and apply a naive parallelization scheme to this color. This can, however, cause some deterioration of the quality of the solution.

Benchmarks suggest that the simpler Jacobi-based methods may produce the same results as Gauss–Seidel-based methods, but faster as the number of cores is increased. Note that there are a number of optimizations that can improve the performance of the Gauss–Seidel-based schemes considerably, and may change this result. This could be a topic for future work.

 

Bachelors Thesis: Suffikstræer og deres anvendelser

Download
Co-authors: Troels Larsen and Kim Olsen
Supervisors: Martin Zachariasen and Benny Kjær Nielsen

A suffix tree representing the string "kakao"

A suffix tree representing the string "kakao".

The thesis is in Danish, but there is a short introduction to the subject on wikipedia.

Et suffikstræ er et træ, der er bygget over en tekststreng, således at alle delstrenge af tekststrengen kan findes i træet i tid proportional med længden af delstrengen. Endvidere er det muligt at finde alle de steder i tekststrengen, hvor delstrengen optræder i tid proportional med længden af delstrengen og antallet af steder, hvor delstrengen optræder.

Første del af rapporten udvikler et teoretisk fundament til beskrivelse af suffikstræer og beskriver lineærtidsalgoritmer til konstruktion af suffikstræer. I denne del af rapporten vil Gusfield [GUS1999] og Smyth [SMY2003] blive brugt i et betydeligt omfang til referencer og generel vejledning. Der vil blive lagt vægt på Ukkonens algoritme [UKK1995], da denne kører i lineær tid, er on-line og anses for at være den simpleste lineærtidsalgoritme. Første afsnit vil blive afsluttet med et overblik over forskning i suffikstræer, siden Ukkonen fremlagde sin algoritme.

I anden del af rapporten designes en implementering af Ukkonens algoritme, og der vil blive udført en analyse og afprøvning af implementeringen. Vi vil koncentrere os, om hvorvidt køretiden og pladsforbruget af implementeringen stemmer overens med teorien.

 

Publications

Heuristic Convergence Rate Improvements of the Projected Gauss–Seidel Method for Frictional Contact Problems.

Co-authors: Sarah Niebe and Kenny Erleben
Download at the WSCG 2010 homepage (please scroll down to FULL Papers proceedings)

In interactive physical simulation, contact forces are applied to prevent rigid bodies from penetrating and control slipping between bodies. Accurate contact force determination is a computationally hard problem. Thus, in practice one trades accuracy for performance. The result is visual artifacts such as viscous or damped contact response. In this paper, we present heuristics for improving performance for solving contact force problems in interactive rigid body simulation. We formulate the contact force problem as a nonlinear complementarity problem, and discretize the problem using a splitting method and a minimum map reformulation. The resulting model is called the Projected Gauss–Seidel method. Quantitative research results are presented and can be used as a taxonomy for selecting a suitable heuristic when using the Projected Gauss–Seidel method.

 

Projects

Visualization of Parametric Surfaces

Download
Co-authors: Dirk Hasselbalch and Michael Niedhardt
Course: Introduction to Computer Graphics

Teapot

A teapot rendered by our program.

Computer graphics is widely used, and seems to grow in importance. The present report attempts to analyse the central aspects of 3D visualisation, to find good design solutions and to create code that might possibly be of use to us later, but as such it contains nothing new. The main areas of interest have been scan conversion of triangles, how to handle surfaces in 3D, the projection of 3D objects onto 2D planes and how to apply light and shading to objects. We have been able to create all the required visualisations: The general parametric surface and the 2 objects defined by Bezier patches. We think that illumination and shading has been done with a certain success, at least based on visual inspection. There are minor errors in the final images that we would have preferred to remove, but time has not allowed us to do that.

 

Associative Containers with Strong Guarantees

Download
Co-author: Lars Skovlund
Course: Generic Programming and Library Development
In this assignment, the task is to write an associative container along with the associated data structure. We are given a list of possible data structures and a number of conflicting requirements for the finished product. Our job is to make the hard choices regarding these requirements and end up with a subset that we would like to focus on. Several of the requirements are absolute; they are given by the C++ standard and must be met. Others depend on the choice of data structures and are mutually exclusive.

A datastructure called Deterministic Skip List has been implemented to be used in associative containers, such as sets and maps. Functionality to insert and erase using iterators have not been implemented.

 

The Corn Hungry Martians

Download
Course: Game Animation

Dawn

The rising Sun as rendered by our game engine.

A game engine is one of the central building blocks of a computer game. It supplies game content developers with an interface that can steamline the path from ideas to the computer screen. The subject of this paper is the construction and implementation of a light weighted game engine. The overall design could use a little extra work, and should be expanded to support world building separate from the code. The most glaring problem of the engine is that it seems to “freeze” when new cells are generated.

During development it became clear that building a game engine that can render a realistic scene is not done by doing using (or even approximating) scientific principles, but by finding a hack that makes the scene look real, as the “correct” calculations are still beyond the computational ability of current hardware.

The game engine were build using Open Tissue and a project framework developed by Kenny Erleben, Knud Henriksen and Lars Schjøth. The report will not document the project framework, so the reader is assumed to be familiar with it. The game engine was build in collaboration with Dirk Hasselbalch, Stefan Lemvig Glimberg and Toke Mundt Stensgaard Nielsen, and is not supplied.

 

Using Splitting Methods in Multibody Dynamics Animation

Download
Supervisor: Kenny ErlebenAn unstable stack of boxes

Simulation of the movement of multiple rigid bodies are used in a number of fields, ranging from engineering to computer games. One challenging problem is to handle contact between bodies in a robust fashion at interactive speeds. In this project, the Newton-Euler equations are derived for multiple rigid bodies and rephrased as a non-linear complementary problem. This problem can be reduced to solving the matrix equation Ax + b = 0 for x. An iterative method to compute an approximate solution can be found by splitting A into a sum of matrices. Methods for improving the convergence of such a method has been considered and tested. Neither of the investigated methods proved to be significantly better than the others.

 

Projected Gauss-Seidel order from Physical and Geometric Properties

Download
Supervisor: Kenny ErlebenA spiral of domino pieces

This project investigates how the physical and geometrical properties of a multibody system can be used to improve quality and speed of computing contact forces. The problem of computing contact forces can be formulated as a nonlinear complementary problem, which can be solved using the iterative matrix solver projected Gauss-Seidel. Using a staggered approach, where the method switched between solving for normal and frictional impulses, showed an improved rate of convergence, if a greedy approach to switching were utilized. If the problem were split into two coupled subproblems, the time usage per iteration were significantly reduced.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: