Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / multimedia / OpenGL

Bouncing Balls in OSG

4.50/5 (4 votes)
29 Aug 2008CPOL4 min read 3   835  
Simulation in OSG using discrete events, a Ternary Heap and Interpolation

Contents

Introduction

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.

MixedOSG.gif

Motivation

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.

Overview

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.

Building

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.

OSG Scene

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).

Priority Queue

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.

Ternary Heap

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.)

C++
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.

Continuous Motion and Interpolation

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.

C++
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:

C++
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;
} 

Changes (Events)

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:

C++
double s2 = s * s; // dot product
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 )
{
// Collision occurs at time t
ChangeTime( t );
Enable( true );
}
else
{
// Collision occurred in the past
Enable( false );
}
}
else
{
// Collision does not occur
Enable( false );
} 

Revision History

  • 29th August, 2008: Original article

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)