|
|
 |
|
Studienarbeit / Bachelor thesis
Rigid body dynamics: Hierarchical Hash Grids
Supervision:
Background:
The pe rigid body physics engine is a C++ framework for the physically
correct simulation of rigid bodies of arbitrary shape.
During each time step, the collisions between the simulated rigid bodies have to be treated.
The first step in the collision handling pipeline is the detection of contact points between
all rigid bodies. Since the calculation of contact points between rigid bodies of arbitrary
shape is a computationally expensive procedure, a common goal is to reduce the necessary work
as much as possible. One basic idea is to introduce so called bounding volumes that offer
very fast rejection tests: if two bounding volumes overlap, then the two contained rigid bodies
potentially collide and have to be further processed, otherwise the pair can be immediately
neglected. However, although bounding volumes introduce an enormous performance improvement,
it is still necessary to handle every possible pair of rigid bodies, a task that has a complexity
of O(N²). Therefore in addition to bounding volumes, some other algorithms are introduced
to reduce the number of necessary tests to a minimum. One of these algorithms are hash grids
and their extension hierarchical hash grids.
The task of this thesis is the extension of the pe physics engine with hierarchical hash grids
to improve the performance of the collision detection process. The task involves the development
and implementation of an efficient data structure for the hierarchical hash grids and the
development of suitable test cases to prove both the correctness and the efficiency of the
implementation. In order to make the development of this new feature easier, the pe
framework already offers a suitable interface to plug in the new collision detection algorithm in
an effortless way.
Tasks:
- Development and implementation of the hierarchical hash grids collision detection
algorithm and integration into the pe framework
- Performance and memory requirement evaluation of the C++ implementation
- Development of suitable test scenarios to prove the correctness and efficiency of the
implementation
- Development of demonstration examples
Recommended knowledge:
Status:
Reserved
|
|
|
|
