Contents
This project is a demonstration of a simulation in which objects can change continuously (moving and rotating balls) and instantaneously (collisions). It is for OSG (at least version 2.2) and Visual Studio/Express 2005 or 2008.
Many physical simulations estimate positions of objects by performing calculations at regular intervals of time. This gives great results for a number of simulation engines that use finite element analysis such as ODE. But this can result in a loss of accuracy if the time intervals are too long - for example, objects which should collide, fly through each other instead. I created this project to model a system by calculating the exact time a change occurs - in this example, when a collision occurs. In this way, a simulation can run more quickly without loss of accuracy.
In many sample OSG applications, objects are updated after rendering each frame, resulting in a jerky motion. In this example, the objects are updated with an osg::NodeCallback so that they move smoothly.
The simulation predicts the position and rotation of balls bouncing in a box, rendering their motion with OSG. It predicts when balls collide based on their current trajectory, and processes these collisions. As the simulation moves forward in time, it must check whether any changes should have occurred. If so, it finds the next predicted change, and processes it by updating the velocity of the balls at that time.
To build or run this project, OSG (OpenSceneGraph) must be installed. This is most easily done by downloading pre-built binaries for the relevant version of Visual Studio by following the links here, in which case this project should be built in release mode.
The OSG scene consists of a transparent box (osg::Box, osg::Material) and a number of spheres (osg::Sphere) with a textured surface (osg::Texture2D) which moves and rotates (osg::PositionAttitudeTransform, osg::NodeCallback).
A priority queue is any data structure which allows us to add items, and to remove the item with the highest priority. In this case, the items are the changes due to collision predictions. One change has higher priority than another if it is predicted to occur first. The simulation uses a priority queue to find the next change so that it can give the accurate situation at any time. The STL library contains a priority queue, but we also want to be able to increase or decrease the priority of items when the simulation is updated after a collision.
A heap is a tree in which the parent of each item has a higher priority, and the root item has the highest priority. This is known as the heap property. We can use a heap as a priority queue.
In a ternary heap, each item has 3 children (except possibly the last item, leaving room to add or remove items). The items are stored in an array. This is easy to maintain and it is also easy to find the parent and first child of an item at a particular index in the array. (A ternary heap performs better than a binary heap.)
int Parent(int index)
{
return (index - 1) / 3;
}
int Child(int index)
{
return index * 3 + 1;
}
When the priority of an item in the heap changes, this may break the heap property, but it turns out that we can swap an item with its parent or child until the heap property is restored (shifting up or down), and this allows us to change, add or remove items in the heap.
We can add items to the heap by appending them to the end of the array, then shifting the item up the heap. We can also remove the first item in the array (the root of the heap) by swapping with the last item of the array, removing the last item, and shifting the new root down.
The recommended way to update the position and rotation of objects in OSG is to use an osg::NodeCallback object. This is used to bring the simulation up-to-date for the correct time of the frame being rendered. Then the position and rotation of the ball is updated.
If the position of a ball at time t0 is a vector s0, and its velocity is a constant vector v0, then it is simple to calculate (interpolate) its position at any time t.
s = s0 + (t-t0) * v0
If its rotation at time t0 is represented by a quaternion rot0 and its angular velocity is a0 then we can also rotate the ball. (I have avoided osg::Quat::slerp which interpolates between two quaternions as it is less accurate for our purposes). The rotation quaternion is calculated as follows:
osg::Quat Rotation( double time ) const
{
double angular_speed = a0.length();
if( angular_speed < 1.0e-5 )
return rot0;
double t = time - t0;
double half_angle = 0.5 * t * angular_speed;
double cos_half_angle = cos( half_angle );
double sin_half_angle = sin( half_angle );
double factor = sin_half_angle/angular_speed;
osg::Quat rotation;
rotation.x() = a0.x() * factor;
rotation.y() = a0.y() * factor;
rotation.z() = a0.z() * factor;
rotation.w() = cos_half_angle;
return rot0 * rotation;
}
When a ball collides, the velocity of the ball is changed, so its collision predictions must be recalculated.
Collisions between balls and walls are easy enough to predict and process since the walls are aligned with the x, y, z axes.
I found collisions between two balls easier to work out using vectors. Let v and s be the relative velocity and position between two balls at a time t0. We want to find the time t when the relative position vector has magnitude r (the sum of the ball's radii). Then we can predict the collision as follows:
double s2 = s * s; double v2 = v * v; double sv = s * v; double r = b0->radius + b1->radius;
double r2 = r * r;
double sqr = sv*sv - v2 * (s2 - r2 );
if( sqr > 0.00001 )
{
double t = t0 + ( - sqrt( sqr ) - sv ) / v2;
if( t > time )
{
ChangeTime( t );
Enable( true );
}
else
{
Enable( false );
}
}
else
{
Enable( false );
}
- 29th August, 2008: Original article
