Real-time calculation and visualization of the dynamics of boulder in a changing environment

Study course: Media Computer Science, winter semester 2003/2004
Institute for Software and Multimedia-Technology
Chair of Computer Graphics und Visualization

Tutor: Dipl.-Inf. (FH) Benjamin Neidhold
Professor: Prof. Dr. Siegfried Fuchs (Institute for Artificial Intelligence)

Contents

• Conceptional Formulation
• Introduction
• Rigid-body dynamics
• Collision detection
• Collision response
• Implemention
• Download

Conceptional Formulation

In order to simulate and visualize erosion processes in a given environment it is necessary to include objects placed on an elevation map (e.g. pieces of rocks) in the simulation. For this application the physically correct (resp. approximated) behavior of rocks in a changing environment has to be implemented in the framework of this thesis (impact of gravity, consideration of interactions between single pieces of rocks). The rocks can be approximated with balls in the simulation. An example implemented with OpenGL is to facilitate a graphical representation of the simulation in specific intervals.

Introduction

The implementation of a dynamic simulation of boulder in a changing environment and the required physical, mathematical and algorithmic concepts and ideas are described in this thesis. After a detailed explanation on calculating the movement of boulder using the general rigid-body model as a result of different influences (e.g. applied forces), details about the derivation and the solution of a more appropriate form of the dynamic equation are given.

As this equation illustrates only the unconstraint motion of a rigid-body, the problem of collision detection and handling were analyzed in the further course. Here the main focus lies on efficient methods of collision detection between optional triangle meshes to realize a gradual demonstration of the simulation in real-time, because this depicts the main performance bottleneck of the calculation. With these results it is possible not only to examine effects realized by forces (e. g. gravitational force) but also non-continuous movement changes as they take place on impacts.

For the provision of the surface geometries an exporter for Maya was implemented.

Rigid-body dynamics

The physical model of a rigid-body describes an object as a set of mass points with pair wise fixed distances towards. The position of an object can be characterized by six degrees of freedom in three-dimensional space, three for the position of the centre of mass and three for the orientation.

The aim is to simulate the changing of these six values over time. Here the material properties of the object such as the mass or the inertia tensor as well as the effective forces on the object (and the resultant torques) become important. Using some principles of the classical mechanics these changes can be described by ordinary differential equations.

Numerical methods such as the explicit Euler-, Midpoint- or the fourth order Runge-Kutta-method are used to solve the equations.

Collision detection

The problem of collision detection is primarily made up of two questions:

1. When does the collision occur?
2. Where does the collision occur?

Because the simulation runs in discrete time steps it may happen that an object is in a valid configuration and in the next time step it is in an invalid configuration (objects are penetrating). The reason for this situation is the missed collision handling. This handling should preferably take place in the exact moment of contact.

Furthermore it is important to know the exact points in time on which the contact happens, the orientation of the surface normal at these points and which velocities are existent to calculate an adequate impulse between the objects (a discontinuous change of acceleration).

Because the surfaces of the collision objects are described by so many triangles it is not possible anymore to test the distances between each triangle pair of both collision partners in real-time.

That is why special spatial data structures (so called collision trees) were used which allow an efficient intersection test of the triangles. The basic principle here is the hierarchical insertion of the triangles in a tree of bounding volumes. At first the root node describes a bounding volume around the entire object (all triangles). After that the triangle set is divided into two subsets along the main axis of the bounding volume. So another bounding volume can be put around the two subsets. Hence, these ones form the child of the previous node. The final leaf nodes are created by single triangles.

Two-dimensional example of the creation of a collision tree using OBBs as bounding volumes. The lines in 2D are corresponding to the triangles in three-dimensional space.

Structure of the collision tree

The intersection test (resp. the overlapping test) can be accomplished efficiently by starting with the two root nodes and then traversing the trees recursively. If there is no overlapping on a pair of parent nodes all the child nodes will fail the test instantly.

The choice of an appropriated bounding volume depends on how fast the overlapping test is accomplishable and if there is a good volume approximation. OBBs were used for the implementations which average the best results.

Various bounding volumes (from left to right): AxisAlignedBoundingBox, BoundingSphere, OrientatedBoundingBox

Collision response

After all required information is collected by the collision detection routines the calculation of the collision impulses between both objects can now be done. The collision impulses must be chosen in a way that the negative relative velocities of the contact points are adapted according to the empirical law:

The ? is the collision factor. It can range from zero to one; zero is equivalent of a completely inelastic contact and 1 is equivalent of a full elastic contact. (+ indicates values after the collision, - indicates value before the collision)

More precisely it means applying an appropriate change of the total linear and angular velocities of the objects involved.

Implementation

The programs were developed with C++ and Managed C++ as a .NET-application with Microsoft Visual Studio .NET 2003. The graphical representation and processing was realized with OpenGL. The following shortcuts can be used:

Left: test with friction, right: collision with elevation map

• ALT + left mouse button: Rotate
• ALT + middle mouse button: Move
• ALT + right mouse button: Zoom
• left mouse button: Apply impulse (not in all demos
• space bar: Add a rock (not in all demos)
• picture up/down: Change the elevation map (not in all demos)

• Download

  • Demos (.zip): (2,73 MB)
  • Thesis (.pdf): (1,86 MB)
  • Presentation (.pdf): (3,33 MB)