MathEngine Karma is a physics and collision detection software package. Software libraries are provided that contain routines that users can call on to quickly and easily add physical behaviour to their 2D or 3D environment. While the Karma product is suitable for a wide range of applications users should note that it is targeted at the games and entertainment markets. This userguide provides a background to the subject and introduces the Karma package, before going on to explain in detail how Karma can be used and integrated into a project. Karma is aimed at developers of real-time entertainment simulation software who are familiar with the C programming language and have a basic knowledge of maths. Experience with Microsoft Visual C++ is an asset. The source that is provided is in C. Karma uses a C API.

In broad terms Karma consists of collision detection and dynamic simulation modules that may be used alone or together. The Karma Bridge (Mst Library) provides an API that simplifies the interoperation of Karma Dynamics (Mdt Library) and Karma Collision (Mcd Library). A basic cross platform renderer that wraps the DirectX and OpenGL graphics libraries is provided. While this allows users to build 3D applications with simple scenes, it is intended that users will integrate Karma with their own rendering solution.

Karma is available for:

• Win32 built in single precision against the Microsoft LIBC, LIBCMT or MSVCRT libraries.
• the Sony PlayStation®2 games console.
• the Xbox games console.
• Win32 double precision and Linux versions on request.

Information about each library function is provided in the html online documentation that can be found by following the ‘Demos and Manuals’ hyperlink in the index.html file in the metoolkit directory.

The origins of physical simulation, and how it has developed from the early days of electronic games through to the recent introduction of what have become known as Physics Engines, are discussed in chapter 1.

Chapter 2 introduces MathEngine’s Karma product – a physics engine – and outlines what it can be used for, and how it works. The internal data structures are discussed, along with the data flow during a game. An example of two spheres colliding is used to demonstrate this.

Chapter 3 presents Karma Dynamics, including discussions on the units, scale, coordinate system and reference frames used. The dynamics library functions are discussed and demonstrated with explanations of relevant physical behavior and the provision of user examples – from basic user functionality through to more advanced usage of Karma’s libraries. World properties, bodies, constraints and forces are introduced.

In chapter 4 an overview of collision detection is given, with an explanation of how the three main parts of Karma, namely Karma Dynamics, Karma Collision and the Karma Simulation Toolkit, work together. The distinction between collision primitives, aggregates, and static models is made and examples of their implementation provided. Determination of object intersection in a game environment is demonstrated, along with line of sight tests to determine any objects that lie on a line joining two points in 3D space. Change blocks are introduced and the user is told how, and (importantly) when, to update collision model information.

Chapter 5 discusses the simulation toolkit or bridge, which can be used at the high level to control Karma dynamics and collision.

Chapter 6 provides valuable developer information that summarizes the main do’s and don’ts when using Karma. A number of important points are listed and later discussed. These will help when building simulations using Karma. Following this is a section that contains, in part, answers to questions that have been asked by developers using Karma.

The internal performance of Karma is discussed in Chapter 7, with specific information on x86 and PlayStation®2 performance provided for game relevant scenarios. Recent computational methods that are used in physical simulation are introduced – Mirtich’ method, Penalty Methods and LCP-type methods. The improvements made by platform specific optimization is demonstrated and the improvements in speed through identifying platform specfic internal ’hotspots’ in the software discussed.

Finally the eighth chapter comprises a user tutorial that takes a user through the steps required to build a Karma simulation of a character riding a quadbike over a static terrrain.

The appendices provide:

• default values of Karma properties
• a basic discussion of the Karma viewer
• an explanation of how Karma manages its memory, with example game scenarios provided to demonstrate memory allocation
• a constraint reference specification

A glossary of terms and a bibliography form the last two sections.

Typographical Conventions

Bold Face:

• User Interface element names (except for the standard OK and Cancel buttons)
• Commands
• Document and book titles

Courier:

• Program code
• Directory and file names

Italics:

• Cross-references
• Introduction of a new word or a new concept

About MathEngine

Founded in Oxford, UK in 1997, MathEngine provides physical simulation software that gives developers the ability to add physical behavior to applications for use in the games and entertainment markets.

Introduction

This chapter provides a background to physical simulation, from a historical perspective right up to the techniques currently employed on modern day computing systems. From the empirical physical laws first formulated hundreds of years ago, to the present techniques that are based on these straightforward laws and employed in software such as the Karma package supplied by MathEngine, physical simulation is finding its way into a diverse range of applications.

Historical Background

It is convenient to begin during the seventeenth century when Isaac Newton stated his three empirical physical laws describing the dynamical response of an object under the application of an external force. We are all introduced to these laws in secondary school, and they form the basis of the deterministic physical simulation methods that are employed today. Newtonian rigid body dynamics (RBD) has been around for a long time, and the mathematics describing such systems in the public domain. However, it is only in comparatively recent years that extensive investigation, modelling and research into simulation has been made possible by the advent of automatic calculating machines with the ability to perform the necessary calculations. The current status of this technology is such that mathematical models that describe the time evolution of physical systems of rigid bodies can be implemented on low end PCs and games consoles targeted at the home computer market.

RBD describes the behavior of a system whose elements are considered to be rigid. Rigid bodies have infinite hardness and do not deform. Even though this restriction simplifies the mathematics used to describe such systems, analytical solutions exist only for very simple systems, and thus we must turn to numerical methods. Multi-body systems are also subject to the so-called butterfly effect, in which very small changes or inaccuracies in initial configurations can build up over time into large deviations, producing widely varying behavior. For example, when breaking in a game of snooker or pool, no matter how carefully you set the game up, the slight errors in the position of the balls build up to the macroscopic level, resulting in a unique break every time.

In physical computer simulations, the inherent uncertainties in initial configuration and the limits imposed by the calculating machine mean that systems cannot be modelled exactly, only a possible evolution path predicted. MathEngine’s Karma software utilises predictive methods to find such a path.

Application to entertainment

Since the early days of TV and computer games the entertainment software market has been striving to provide better entertainment solutions. Within the home user budget, increasingly more powerful computers systems are becoming available, and in turn better gaming experiences.

While the improvements in graphics over the last decade are very apparent, the solutions available to improve realism are not so well known. A potential revolution may be in the making in the area of ‘game/virtual world’ response and realism. While things have been slow to take off – mainly because of the changes this will bring about in gaming methodology – the coming years will bring a new genre of coding tools to the hands of the games programmer in the form of methods to add physical behavior to an environment. These new tools have led to the coining of the phrase ‘Physics Engine’.

Physics Engines

To explain the potential of physics engines, we need to consider the current solution to handling object behavior in a simulated game environment. This falls into two categories, namely scripted behavior (animation), and bespoke solutions:

Scripted behavior is a predefined sequence of events used to define the path through time of a game object. For example, consider a racing car rounding a bend. The way the car behaves is determined by certain properties when it comes into the bend. A scripted solution chooses a sequence from a library of prerecorded sequences, the chosen sequence depending on the approach parameters of the car to the bend.

A bespoke solution looks at the specific problem and solves it by applying the appropriate mathematical equations to work out what a body should do. For example if a car is being driven over a terrain with the accelerator down and the accelerator pedal is released, friction between the wheels and the ground, and frictional drag caused by air resistance, are the cause of two forces that act to slow the car down. The drag force could be coded with an equation that decreases the wind resistance drag force as the car slows down.

The paradigm shift with a physics engine is that the engine implements a general mathematical model of real-world objects and their interactions. The application configures the model and defines the objects within it, and the physics engine evolves the positions and velocities of the objects over time in response to inputs from the application. So in the example above, the application would define a model for the terrain, and a model of the car, including such things as its wheels, its suspension and steering mechanisms. To simulate wind resistance on the car, the application would use an API function, perhaps of the form SetDrag(car, drag value). Similarly, for a car rounding a corner, the properties of friction, velocity, drag, mass and mass distribution could be entered into the physics engine and the cars natural behavior calculated according to physical laws that act in the real world. This option can be used on its own or combined with some other solution. You can move from your scripted scene to a physics engine and back if you want to use physics to provide a more realistic approach to a certain situation.

To use a physics toolkit effectively requires the understanding of concepts such as drag, and the learning of new skills such as knowing how best to join one body to another. But the underlying mathematical functions are already there to use, which can save time prototyping and building a project. Game physics programmers will have a new set of tools at their disposal that will provide fast, stable implementations of foundational algorithms, allowing them to focus on advanced modeling techniques and game-specific features, and therefore to implement better physical behavior within their available budget. Physics providers are working to improve the speed, stability and accuracy, through improved mathematical methods, optimized code and more accurate physical modelling. This would usually be beyond the resources of a single games project.

A physics engine that solves mathematical systems of rigid articulated objects with frictional contacts can realistically simulate

• car games with obstacles
• large mechanical systems
• robots, humans and creatures
• fighting games with a large number of contacts and occasional jointed systems

Another important point to note about physics engines is that while the term ‘more realism’ is often used when discussing the addition of physics to games, this does not restrict development to natural behavior. A physics simulator can alter the real world behavior to give ‘cartoon physics’ by implementing other physical laws. Gravity can be high or low, and be made to act up or down. Cars can be light or heavy and the mass properties altered to give the required response.

Usage

Let’s take a look at what may or may not be needed by the game developer who is just about to start work on the next game, and is considering a third party physics solution. What should a developer be considering when deciding on whether or not to invest in a physics engine? It should be noted that a physics engine might not always be the most appropriate approach. This may be the case when the amount of physics required is minimal, or the expertise exists in-house to implement a solution.

The goal of any rigid body physics engine is to calculate the motion of a collection of objects giving the impression that the objects have real world properties such as mass, and respond to real world events and conditions, such as collisions and forces. The calculated motion should also obey a number of constraints. For example, objects should not be allowed to pass through each other or the world, and when objects touch they should experience friction. Objects that are part of articulated structures, such as humans and vehicles, should move in a way that respects the joints between them.

How might one proceed? The specification requires that game objects behave realistically, and research leads to some relatively new software solutions on offer, namely physics engines. Why choose to license one of these in favor of an in-house solution? Let’s look at what needs to be considered for an in-house solution.

There are several algorithms available, but will they fulfil the specification? Featherstone’s algorithm is fast and can be used for chain-like structures, but problems are encountered when there are contacts or if the chain needs to be broken to add another object. Mirtich type methods, where one constraint at a time is satisfied are difficult to make stable, and objects suffer from jitter.

If you need to

• add and remove objects
• simulate complex articulated objects – such as chains, or structures with branches and loops
• simulate friction
• limit joint movement
• simulate motors
• handle contacts

a more general approach such as a Lagrange Multiplier method is needed. MathEngine’s Karma software
uses such a method.

A model using such a general approach which is fast and stable, deals with stiff forces without numerical instability, and has a reasonable friction model, requires some fairly complicated mathematics that must then be carefully and efficiently implemented. Given the stringent real time gaming requirements on current low end platforms, the algorithm may well need simplifying, may not provide the complete solution, and need a lot of optimization. A collision detection system is also required to produce good predictive behavior.

There are numerous papers in the public domain† that discuss the problems that need to be addressed, and provide solutions in some of the areas. However, the time available to the game developer to build and optimize this basic functionality may be limited. Physics Engines provide a solution: the basic problems that a game physics programmer would need to overcome have been solved, allowing the programmer to build a solution more quickly and concentrate on adding further, better physics and features to improve playability.

Whether you decide to go it alone or buy a package to make it easier for you, physics engines are here to stay. Current games processors are fast enough to satisfy many of the requirements of game physics, and future improvements will lead to ever better real-time simulation.

The Structure of Karma

Overview

It is convenient in simulation to represent a virtual world object as three separate parts, namely the dynamic body, collision frame and rendered object. These can be manipulated individually, but are more likely to be linked by using the same position and orientation information for each. The dynamic body has no knowledge of its extent save for the mass distribution of the extended shape. The collision properties of an object determine its extent in 3D space and are used to determine whether this object collides with another. An object is in collision with another object when it is not the only object to occupy a particular volume in the 3D space in which it exists. The rendered object is a visual display of what is going on in the virtual world. A physics simulation with collision detection can evolve without any graphical display. However it is often convenient for the user to render the scene to observe the behavior.

Karma Simulation

At a basic level, the Karma simulation process can be described in three steps:

1. The user describes at the API level a closed system at time instant t.
2. An internal mathematical representation of the system is built by the software.
3. The system is evolved, with account taken of any new objects entering the system or additional forces arising, at a future time t’.

Step 1.

This involves defining:

• the objects that make up the system. Physical properties such as mass, position and velocity are specified.
• any constraints (joints or contacts) on the system.
  These are contact forces arising from two bodies interacting.
• world properties such as any fields that all objects in that world will interact with, for example a gravitational force field.
  Force fields are non-contact forces that act on objects without physically contacting them.

Constraints are of two types:

• Equality constraints. A particular restriction on a body, or a pair of bodies is imposed. For example, you could say that specified points on two objects must remain coincident, yet the bodies can rotate freely around one another. This constraint is a Ball and Socket joint, and the application programmer would specify it as such.
• Inequality constraints. As an example consider that the user has specified body fifteen in a twenty body simulation as being a solid sphere of radius ten meters. No other object can penetrate the surface of body fifteen, or occupy the same space. Mathematically this is conveniently expressed as an inequality constraint.

To maintain constraints, the system must be continually checked as it is dynamically evolved to see if any objects are colliding. The user would create collision models to describe the shapes of the bodies in the world, that the collision detection system would then use.

Contact properties such as the type and parameters of the friction model can be specified, to govern how colliding bodies behave.

Step 2.

A matrix equation is built to represent the way forces and constraints act on each body. This is used to compute the forces on each body required to maintain the constraints.

Step 3.

An integrator is used to move the system forward in time by some user specified increment, ∆t. The requirements of this process are that:

• the system be evolved at a certain speed e.g. real time.
• the system remain stable.
• evolution is accurate from the perspective of the user.

These requirements are interdependent. For example, reducing ∆t usually increases accuracy and may improve stability, with an associated increase in the time required for simulation.

The Karma Pipeline

The execution of Karma within a particular frame can be viewed as a pipeline, with each stage producing information which is used by the next. Typically the pipeline stages execute in each frame as shown in the following diagram, with rendering and user interaction being performed between runs of the pipeline.

[Illustration]

Farfield Collision Detection

The function of the farfield is to detect those pairs of objects which are nearby. In Karma, pairs of objects are considered to be nearby if their axis-aligned bounding boxes (AABBs) overlap.

Nearfield Tests

When the pairs of objects that might be in collision have been identified, it is the job of the nearfield tests to determine whether the objects actually do overlap. Karma dynamics is designed to respond to collisions by applying forces at a finite number of points, called contacts. Each contact is specified by a position, a normal and a penetration depth. If the objects intersect, the nearfield test chooses a set of contact points that best represent the intersection..

[Illustration]

Karma’s nearfield algorithms allow arbitrary sets of triangles to be used for non-dynamic objects such as the terrain. Dynamic objects are typically represented by:

• sphere, box, cylinder or sphyl primitives.
• a collection, or aggregate of these primitives.
• arbitrary convex meshes.

Partitioning and Freezing

Physical simulation becomes more computationally expensive as the number of interacting objects increases. If there are ten objects in a world that are all mutually constrained, the scene is more difficult to simulate than when there are ten uncoupled objects because of all the interactions among the linked structures. Karma separates the world into groups of objects that interact among themselves, but not with objects in other groups and treats each group separately.

Each group is then examined to determine whether or not the accelerations and velocities of the objects in the group, and the forces acting on them, are all small enough that simulation will produce no perceptible change. If this is the case, all the objects in the partition are deactivated: dynamics bodies are disabled, and their associated collision models are frozen.

BCL

BCL converts Karma’s high-level constraint representation, formulated in terms, for example, of hinge axes
and joint positions, to a set of matrices and vectors that depend on the parameters of the constraints and the
positions and velocities of the bodies they constrain.

Kea

Karma uses a Lagrange multiplier method to model jointed systems and contacts. In such a model, the effect of constraints is modeled by forces that act to maintain the constraint. In order to calculate these forces, a type of matrix problem called a linear complementarity problem (LCP) is solved. Karma’s LCP solver is called Kea. Kea calculates forces which when applied, satisfy the constraints at the end of the time-step.

The word complementarity refers to the fact that related quantities can be required to satisfy a complementarity condition: that both are non-negative, and at least one is zero. For example, the complementarity condition for a typical contact specifies that the separation velocity and the force which maintains non-penetration both have a non-negative component in the direction of the contact normal, and at least one of them is zero. This means that at the end of the time-step either the contact will be separating and no force is being applied to enforce non-penetration, or there will be a contact force that prevents the bodies penetrating and the velocity of the objects towards each other will be zero at the contact point.

Euler Integrator

Because the forces calculated by Kea satisfy the constraints at the end of the time-step, Karma can use an Euler method to integrate the constraint forces. This provides the guaranteed stability offered by implicit methods, while taking exactly the same number of operations as an explicit Euler method. This makes Kea naturally stable, and capable of stably simulating stacks and piles of arbitrary objects without the need for user tuning or damping. External forces, such as gravity, are explicitly integrated.

Karma Data Structures

Although Karma has many datatypes, to understand the basic implementation of the pipeline it is necessary to describe just a few and outline the relationships between them. McdModels and McdModelPairs, and MdtBodys and MdtContactGroups are small datatypes, that may be created and destroyed frequently during gameplay. The MdtWorld, McdSpace, and MstBridge are large datatypes that there would usually only be one of. Naturally these would be created and destroyed infrequently, perhaps when starting or ending a game level.

McdModels and MdtBodys

[Illustration]

An McdModel is the top-level collision data structure containing geometric information about the extent of an object. It corresponds fairly closely to an MdtBody, which is the data structure containing the physical properties of an object, such as its mass, position, and velocity. A model may or may not have an associated body: it may represent a fixed piece of the world for which dynamic simulation is neither desirable nor necessary.

Typically there are many more objects in a Karma simulation than are being actively processed during a given time-step. The most important optimization is that when objects are not moving they have the minimum affect upon performance, which requires that they be culled from the pipeline as early as possible. This is accomplished by freezing collision models and disabling dynamics bodies that are at rest, where:

• Freezing a model informs collision that the model’s transformation matrix will not change. A frozen model will not have its AABB updated automatically by the farfield, nor will it be tested for collision against any other frozen models.
• Disabling a body instructs Karma not to include it in dynamic simulation.

If a model is frozen but has a body that is enabled, the body will be simulated, but contacts against frozen models (such as the world) will not be generated. So the body will typically fall though the world. If a body is disabled but its model is not frozen, fresh contacts will be generated for it every frame even though it is not moving. This will result in correct behavior, but with a loss of performance.

McdModelPairs and MdtContactGroups

[Illustration]

A McdModelPair is a collision data structure that corresponds to a pair of models that have been detected by the farfield to be sufficiently close that they may be intersecting. McdModelPairs are created as soon as the axis-aligned bounding boxes (AABBs) of two models overlap, and thus the models possibly, but not necessarily, intersect. They persist until the AABBs cease to overlap.

If the models in an McdModelPair do intersect, the McdModelPair will have an associated MdtContactGroup. A MdtContactGroup is a dynamics data structure that contains a list of dynamics contacts together with dynamics information about the intersection that may be useful on subsequent frames. By contrast with McdModelPairs, MdtContactGroups are created only when the models in a McdModelPair do actually intersect. They are destroyed when the McdModelPair is destroyed. Like joints, MdtContactGroups are a type of constraint.

Since the MdtContactGroup is created from the McdModelPair, generally the order of bodies within it is inherited from the order of models within the McdModelPair, so the above diagram is representative. However, it is possible for a collision model not to have a corresponding dynamics body, if for example it represents an immovable part of the world geometry. In this case, the dynamics body is always body1 in the MdtContactGroup, and the body2 is set to NULL. Hence body1 will be pointed to by whichever of model1 and model2 corresponds to the dynamic body.

MdtWorld, McdSpace, and MstBridge

The MdtWorld is a dynamics data structure that contains all of the dynamics bodies and MdtContactGroups, along with other entities such as joints, and general data pertaining to dynamics, such as the gravitational force and threshold values for freezing partitions.

The McdSpace contains the McdModels and McdModelPairs. Its primary function is to detect which pairs of models have overlapping AABBs, and produce a McdModelPair for each. As a secondary function, in order to permit the allocation and deallocation of resources associated with colliding pairs, the space implements a simple protocol for their creation and destruction. Each McdModelPair in the space is in a state that is one of Hello, Goodbye, and Staying.

• Hello McdModelPairs correspond to pairs of models whose AABBs overlap at the current time-step, but did not overlap at the previous time-step.
• Staying McdModelPairs correspond to pairs of models whose AABBs overlap at the current and previous time-steps.
• Goodbye McdModelPairs correspond to pairs of models whose AABBs overlapped on the previous time-step but not on the current time-step.

Hello and Goodbye pairs are sometimes referred to as transitional pairs, for obvious reasons.

The API function that calculates the set of McdModelPairs on the current time-step is a function on the space.

The MstBridge contains a material table, which is a table that enables contacts found by nearfield tests to be augmented with dynamics contact properties such as restitution and friction parameters.

Implementation of the Pipeline

[Illustration]

McdSpaceUpdateAll

The Collision farfield is implemented as an axis-aligned sort. It keeps track of the number of axes on which pairs of models overlap, and when this reaches the number of axes on which sorting is taking place, a McdModelPair is generated. McdSpaceUpdateAll performs this sorting operation. In order to do this, it invokes on each model that is not frozen a function to update the model’s transformation matrix, and compute its AABB. The transformation matrix and AABB are then cached in the model for later use.

McdSpaceGetPairs

This function reads a fixed number of McdModelPairs from the collision farfield into a container, called a McdModelPairContainer. Typically the functions McdSpaceGetPairs, MstSpaceHandleTransitions, and MstSpaceHandleCollisions are executed repeatedly until the set of McdModelPairs in the farfield has been exhausted.

MstSpaceHandleTransitions

This routine handles the processing for each model pair in a container that is in the Hello or Goodbye state.

• For Hello pairs Karma orders the models within the pair, because nearfield tests are only implemented “one way round”, that is, there is a box-sphere test but no sphere-box test. Then it determines the intersection function according to the geometry types of the two models, and caches it in the model pair.
• The only special processing performed by Karma for a Goodbye pair is to destroy an associated MdtContactGroup if one exists.

MstSpaceHandleCollisions

This function calls a nearfield test for every Hello or Staying model pair in a container where at least one of the models is not frozen. Some of the pairs may represent two moving objects colliding, but others may represent the collision of a moving object with a mesh of terrain triangles. In the latter case, a callback is executed from each nearfield test to interrogate the game’s terrain format and determine the set of triangles that intersect the bounding sphere of the moving object.

The primitive-primitive intersection algorithms are fairly standard and the convex-convex intersection algorithm used is the Gilbert, Johnson, and Keerthi (GJK) algorithm – please refer to the bibliography. In both cases proprietary enhancements have been made to calculate penetration depth and ensure that good contact sets are made.

Each model has an associated material property, and if two models are colliding, the two materials are used to index into the material table to determine the dynamics parameters for the contact. Dynamics parameters are copied into the contact structure by value so that they may be changed by the application on a percontact basis. The material table also contains callbacks which can be used to parameterize the contact conversion process.

Unless both models in a McdModelPair are frozen, collision contacts (and therefore dynamics contacts) are re-created every frame.

MdtUpdatePartitions

A partition is a set of bodies and constraints that can be simulated without reference to any other bodies and constraints. An alternative definition is that it is a minimal non-empty set of bodies and constraints such that if a body in the partition shares a constraint with another body, that body and constraint are also in the partition. Partitions are generated by iterating over the set of enabled bodies that are not yet in a partition, and adding new bodies by performing a breadth first search of constraints. If a disabled body is found connected by a constraint to an enabled body, it is automatically enabled. Enabling the body causes a routine to be invoked in the bridge to unfreeze the corresponding collision model.

It is possible to set a threshold on the number and complexity of a partition, in order to trade simulation fidelity for speed. If such a threshold is set, the partition may be automatically simplified at this point in order to bring it down to the required size.

MdtAutoDisable

Karma examines each partition after it has been generated to see if the velocities of objects are sufficiently small that simulation will produce no perceptible change, and if so, disables all the bodies. Disabling a body causes a routine to be invoked in the bridge which freezes the corresponding collision model.

MdtPack

MdtPack iterates over the set of partitions, calling the appropriate routine in BCL for each constraint in the partition. The BCL routine computes the matrix of partial derivatives for the constraint, as well as upper and lower bounds for constraints such as force-limited motors, friction limits on contacts, and movement limits on joints.

MdtKeaSolve

Kea, Karma’s LCP solver, contains the highly optimized per-platform implementations of the matrix and vector routine required to solve an LCP.

Kea’s constraint formulation is based upon a semi-implicit time-stepping method. Its friction model and degeneracy protection produce symmetric positive definite LCPs that are guaranteed to have a solution. It uses an iterative procedure to generate successive candidates that should be closer approximations to the correct solution, and usually finds the correct solution in a small number of iterations.

However, there is no general procedure for efficiently solving sets of inequality and complementarity constraints: in the worst theoretical case, finding the correct solution requires time exponential in the number of inequality constraints. Physical simulations do not give rise to such pathological LCPs, but it is important nonetheless to have the option to trade simulation fidelity for speed. There are two possible mechanisms that a Karma application can use to accomplish this:

• relax the constraint conditions, so that a generated solution is more likely to satisfy the constraints.
• limit the maximum number of iterations.

Either of these mechanisms will result in a loss of fidelity in the simulation. But they offer the option of reducing the execution time spent in Kea, based on the degree of constraint violations and other nonphysical artifacts that the application can tolerate.

MdtKeaIntegrate

MdtKeaIntegrate invokes Karma’s Euler integrator to evolve the positions and velocities of bodies using the forces calculated in MdtKeaSolve.

MdtUnpackForces

Sometimes it is useful to be able to access the constraint forces computed by Kea, for example when using a friction model that takes as input the normal force at the previous time-step. MdtUnpackForces extracts the constraint forces for each constraint from Kea’s internal data representation, and writes them into the constraint structures.

High Level API

The function MstBridgeUpdateContacts invokes the following functions repeatedly until all pairs in the space have been processed:

• McdSpaceGetPairs
• MstBridgeUpdateTransitions
• MstBridgeUpdateCollisions

The function MdtWorldStep invokes the following functions (some indirectly):

• MdtWorldUpdatePartitions
• MdtAutoDisable
• MdtPack
• MdtKeaSolve
• MdtKeaIntegrate

So the application code to invoke the pipeline can be as simple as

McdSpaceUpdateAll(space);
MstBridgeUpdateContacts(bridge, space, world);
MdtWorldStep(world,stepSize);

If you are using the MstUniverse API, which provide a convenient wrapper around some of the dynamics and collision code, the API function MstUniverseStep invokes exactly this sequence of functions.

Two Spheres Colliding

[to be continued]