NICO | GALOPPO

• Publications
• Classes
• Photos
• Journal
• Resume
• Contact

Purpose of the project

The purpose of this project is to investigate novel methods for simulation of rigid bodies that integrate well with stacking situations. This work focuses on impulse-based simulation techniques with physical interactions such as collision, contact and friction in relatively complex scenes: large number of stacked objects, sliding objects, highly dynamical scenes with non-convex bodies. We want the work to be applicable to real-time applications such as games, therefore we allow some small approximations in the algorithm. Nevertheless, this report will show that we have succeeded in keeping the algorithm as physically correct as possible.

As a teaser, here's a video that shows some of the results in a 'domino-like' scene on a slanted plane. Notice how the large friction constant makes the two first domino blocks stick together when they fall back near the end of the video. All this is in real time. Click the image or link underneath to see the video.

Dominoes on a slanted plane: Slanted Domino (.avi)

Background

Many authors [Baraff01, Mirtich] have built dynamic models that simulate rigid bodies quite efficiently when in ballistic and colliding phase, either using a force-based or an impulse-based approach. Nevertheless, these authors also argue that the simulation is more problematic in the resting case, often shown in the case where objects at rest start sinking into the ground. Many authors use ad hoc threshold velocities in an attempt to prune these cases out of the collision modeling algorithm and instead treat them with a contact model. They either have to solve a complicated quadratic system [Baraff01], or introduce artificial microcollisions [Mirtich] to prevent the bodies from interpenetrating. This causes some unwanted effects, such as blocks vibrating on a plane, or a block sliding down from a slanted plane, where it should sit still because of the friction force. Recently, Guendelmann, Bridson & Fedkiw [Guendelmann], have come up with an elegant, more uniform algorithm, claiming to resolve some of the issues discussed above without the need for ad hoc threshold velocities. The main contribution of the approach is a new, fixed time-stepping scheme that separates collision detection and resolution from contact resolution. They use a dual geometric representation. Aside from the traditional mesh representation, they also keep an object space signed distance function for collision detection. The collision detection algorithm is a sample-based technique: inside-outside tests are performed on the vertices of the triangular mesh, using the stored signed distance function. Although they claim that this is sufficient for well resolved meshes, and although they improve the approach by flagging edges that intersect the zero contour, many collisions can still be missed for fast moving objects.

Approach and techniques used

The classic simulation step looks like this:

Instead, our algorithm uses a novel fixed-time integration scheme, where we allow for penetration between bodies inside a simulation step. A simple Euler integration scheme with time step 0.01s has shown to be sufficiently robust for all our tests. Our algorithm splits the collision and resting contact phases, where only the velocities are updated between both:

The key to the algorithm is that contact modeling occurs directly after the velocity is updated with gravity. If instead either the collision step or a position update were to follow the velocity update, objects at rest will either incorrectly elastically bounce or move through the floor, respectively. On the other hand, contact processing is the correct algorithm to apply after the velocity update since it resolves forces, and the velocity update is where the forces are included in the dynamics.

Novelty of the algorithm: better collision detection, more physically based contact forces and non-convex objects

The main contribution of my work was to integrate this new time integration scheme into a novel collision detection framework and a more physically sound contact force resolution model. As an extra benefit, I was also able to handle non-convex objects, as described in the following section. To end with, we also came up with some simple solutions to improve the overall efficiency of the algorithm.

First results

After the first implementation of this time stepping scheme, the results were promising: for a limited number of objects, the algorithm is really stable. Objects at rest, and stacks of a few objects remain static without sinking into the ground and without slowing down simulation, because of the fixed-time stepping. This is a good improvement over the bisection method, where many close-by objects drastically increase the simulation time.

Nevertheless, as the number of objects increases, I had to decrease the time step size to numbers as low as 0.0001 in order to guarantee non-penetration. We were using SWIFT for collision detection, but SWIFT was conceived for closest-feature determination, and hence not suited for deep penetration detection. We simply cannot rely on the returned closest feature information if we can't guarantee non-penetration beforehand.

Collision detection with penetration information

Because of the previous discusssion, we need a new way to deal with collisions. As opposed to Guendelmann's distance field approach, our idea is to use the deepest point of penetration between a pair of objects to calculate proper response. This is also plausible for simulations with a larger number of objects, as we only have to resolve one pair of colliding points for every pair of objects. The collision resolution phase will then make sure that the objects are properly separated before going into contact resolution. Thus, I changed the collision detection to DEEP [DEEP]. The returned pair of deepest penetration points is used to resolve the collisions, using Poisson’s hypothesis (u'_rel = -ε u_rel). This approach turned out to be rather successful, allowing for fixed time steps of 0.01s, regardless of the packing of the scene. This is important, because one of the major drawbacks of the bisection scheme is the simulation slowdown when alot of objects are close to each other.

Although I can't directly compare the performance of my approach to Guendelmann's, because there is no implementation of his collision detection available, I believe this approach will be faster, as we only have to compute the response of one collision/contact per pair of objects. On the other hand, it is unsure how both algorithms compare in terms of convergence. Nevertheless, I am confident that the convergence of our algorithm is in the same range, as we have a better approximation of the deepest point of penetration than Guendelmann's sample based collision detection. This approach gives good convergence, because calculating the impulse response in this deepest point of penetration usually separates the objects well.

One of the drawbacks of Mirtich's contact resolution model, is its instability for resting objects if no counteracting microcollisions are applied. Our algorithm shows that the Mirtich's model can be applied to the new time integration scheme without microcollisions, and still have a stable result. This is explained in the next section.

The video below illustrates the stability of the algorithm with DEEP collision detection and Mirtich contact response in place. The scene consists of 60 stacked objects, with a fixed time step of 0.01s. The average time spent in the simulation loop for this scene was 38.3ms, which results in a framerate of 26 FPS.

60 stacked objects: Stacking scene (.avi)

One drawback of using the (original) DEEP code though, is that it does not directly handle non-convex objects, whereas Guendelmann's approach does. I was able to overcome this limitation and handle non-convex objects, as is described further down in this report.

Physically based contact force response and friction

The next step was to include an appropriate friction model. Guendelmann's paper mentions the use of Moore's model [M&W]. I implemented this model, but it doesn't account for rolling or sliding friction. Therefore, I integrated Mirtich's contact response and friction model. The algorithm takes a more physically-based approach to contact resolution. Compared to Moore's model, we observe more realistic and convincing dynamic behaviour. Moreover, we've seen less problems with bouncing objects that would be caused by the introduced microcollisions, because of the novel time-stepping scheme. Indeed, for resting objects, elastic bounce is far less probable to happen. The next video shows a nice result of Mirtich's friction model where the ball is clearly spinning (we render the object-oriented bounding box to show the effect)

Mirtich friction at work: Spinning ball (.avi)

In the table below, we show that although Moore's model is slightly cheaper in computational complexity (avg. time per contact resolution), it is clearly convergences slower in our algorithm, as can be seen from the number of contacts that remain unresolved in each simulation step.

Improving efficiency and convergence of the algorithm

A classic way to resolve multiple collisions is to solve some kind of system of constraints, either on the contact forces [Baraff94] or directly on the impulses[Kawachi]. In our algorithm, we do not do this, but we process them sequentially instead. That is why it is important to find an appropriate ordering to speed up the convergence of collision resolution.

An interesting parameter when dealing with a large number of collisions/contacts in scenes with many objects, is the order in which we resolve the contact point pairs. This is true both for the case of high dynamic scenes and for stacking situations. This is explained in the following figure. In the stacking example, we want to process the objects from the bottom up: the main force in most simulations is gravity, pulling objects down. It can be beneficial to resolve collisions for the bodies on the bottom first, such that we need less iterations to come to a state of non-penetration between all pairs. In the dynamic case, the axis of translation is a good sorting direction to consider.

Figure 1: Axes of acceleration and velocity

We do a fixed number of collision/contact iterations (in phase 1 and 2 of algorithm 1), using the priority ordering from algorithm 2. We have seen some convergence improvement by utilizing this algorithm, indicated in the table below. In the table below, I evaluate the benefit of the ordering. We compare the average number of remaining unresolved contact pairs after 30 collision/contact iterations each in a stacking scene with 60 objects.

A step further: non-convex objects

DEEP wasn't really designed to handle non-convex objects. There is a good explanation for this: there is no clear definition for penetration depth for non-convex objects in the first place. The problem is therefore not with the DEEP algorithm by itself, but rather with the concept of using penetration depth as a means of contact information. When two non-convex objects penetrate they might be sticking out at two opposite sides, making the concept of penetration depth ambiguous.

Nevertheless, there is a way to make DEEP work with non-convex objects. DEEP was built from SWIFT++, which is able to handle non-convex objects by decomposing them into convex pieces. After decomposition, the convex pieces have real and virtual faces. Virtual faces are the faces that were created to form the convex pieces, but that are not part of the original non-convex geometry. To make DEEP work with non-convex objects, we have modified the code, such that only penetration depths between real faces are returned.

The video's below show some non-convex examples. These run at real-time. There is virtually no overhead for adding non-convex geometry to the scenes, these examples easily run at 180 FPS on my 1.5 Ghz Centrino Laptop.

Cup and torus (.avi)	Sliding torus (.avi)

2 torii (.avi)

Advantages and innovations of our algorithm

As a recap, I summarize what I believe are the major advantages and innovations in this algorithm:

• Stable, simulation step size can be kept at 0.01s without any problems.
• Simulation time is only proportional to complexity of the scene, not to number of resting objects.
• Good convergence by usage of deepest point of penetration, calculating the impulse response in this point usually separates the objects well.
• We can use Mirtich's physically realistic contact force model, but avoid one of its major drawbacks, the bouncing of resting objects, without introducing artificial microcollisions.
• Handling of non-convex objects in DEEP.

Overall, I feel we have succeeded in designing a simulation algorithm for relatively complex scenes with non-convex objects, while sufficiently stable, physically sound and efficient for real-time applications such as games.

Limitations and further work

• Although we were able to extend DEEP to deal with non-convex objects, it doesn't handle sharp features very well. This is not a problem of the algorithm by itself, but of the concept of using point of deepest penetration as the point of contact.
• Compared to Mirtich's original work, resting objects are much more stable in our approach, but there might still be a slight vibration in our algorithm. Consider the setup in the following figure. In the contact resolution phase, we apply an impulse which exactly counterreacts gravity. This impulse causes the box to rotate and penetrate on the other side. In the next collision resolution iteration, this slight penetration causes the object to have a slight elastic bounce. In order to solve this, we could extend DEEP to return multiple points of penetration, within some distance ε of the point of deepest penetration.

Figure 2: Penetration just before elastic bounce

Code

The simulator was codenamed pulsk, it's available right here (tracking the latest version with git): pulsk zip file.

The zip file includes a win32 binary and source code. To compile the source, you will need to install the G3D library for some graphics routines. Pulsk compilation has only been tested under MSVC7.1, so your mileage may vary. If you have questions regarding code, compilation or algorithms used, you can always mail me.

A short usermanual for the program:

  pulsk.exe <scenefilename.scn>

    Start up the rigid body simulator, loading up the scene
    description in <scenefilename.scn>.

  Scenefile description: the .scn files are composed out of a 
        set of parameter groups:

    [primitive] {
        [parameter] = value
    }

    "primitives" include:

        world           world description (gravity, drag, shadows)
        camera          camera description (lookat, base)

        box,
        sphere,
        ifs,
        tri             objects description, initial configuration:
                            name, filename, base, normal, color,
                            scale, density, elasticity, friction,
                            velocity, replication

    "value" can be either scalar, vectorial '(x, y, z)', true/false, 
    hex RGB color value (0xRRGGBB), 4-tuple in case of a replication
    statement (xstep, ystep, zstep, n), "random" for random color 

Acknowledgements

© Copyright 2005 Nico Galoppo. Hosted by dreamhost.