Summary
A simple physics engine developed for IET masters.This essentially an implementation of the basic physics pipeline with: particle system physics, rigid body motion, narrow and broad phase rigid body
collision detection and rigid body contact modeling and collision response. This was implemented in C# using the XNA libraries.
Particle System
This system was based on the Siggraph2001 course notes by Baraff, Witkinand and Kass [Baraff et al. 2001],, and implements a collection of particles in a realistic physical scene. These particles have forces applied to them (spring, gravity, viscous drag), also have plane collision handling and include Euler and midpoint integration.
The system is divided into several classes, with the overall physics of the simulation managed by the particle system class. The particles themselves are instances of the particle class which stores the particle in question's position, velocity, force and mass. The various forces are derived from an abstract force class, and contain a method for setting the required force to be the force stored in each particle instant. Gravity is the simplest of these, applying a force of -9.8 to the y axis of the particle times the particles mass. Viscous drag simply reduced the force of a particle based on its velocity, and the spring force is the basic damped spring formula as laid out by Baraff, Witkinand and Kass [Baraff et al. 2001],.
The particle system class initializes the required number of particles in random positions with random velocities within a predefined box. This box is in fact a collection of planes which are managed by the Plane class. When initializing these planes, all of the normals are checked to ensure that they are not facing the wrong way, which will cause problems later in the program when particle plane collision detection is used. The Particle System will also set up the required forces for this particular simulation. On each update of the system, all of the individual particle forces are cleared and then the forces are reapplied (based on the current particles positions, velocities, etc). The particles are then integrated in order to discover their new position and velocity values. The system can be set to do either Euler or midpoint integration for comparison reasons. Which ever method is used, collision detection is applied afterwards. This is done by checking whether each particle is colliding with the plane and if it is reversing its velocity, reducing it by some elasticity values(in this case .6), i.e. with a elasticity of 1 the particle would bounce forever. Backtracking is used to ensure that particles do not penetrate the plane. All of the visualization of the physics is handled in the main game class, using point lists for the particles and line list to display the box of planes they are contained inside.
Rigid Body Unconstrained Motion
This lab involved representing the data required for a rigid body and setting up unconstrained motion for this body. The data structure for this rigid body is stored in a separate class containing all the variables detailed by [Baraff et al. 2001],. The inertial tensor for the rigid body is set using the formula for a cube as in the rest of this simulation cubes are the rigid bodies used, however the program infrastructure is built in order to add the formulas for other rigid body models if so required. The orientation of the body is stored as quaternions, normalized and then converted into a matrix.
The class has method to apply torque (with calculations done based on the objects center of mass) as well as a method to apply a linear force. The update method calculates the inverse of the inertial tensor and multiplies it by the torque, this gives the rotational velocity which is applied based on time the rotation (a quaternion) to the orientation. The orientation is then converted into a matrix (which will be needed for drawing). The position of the object is recalculated based on the linear momentum divided by mass. Again all of the drawing is handled in the main game class, with a 3d cube model loaded in to represent the rigid body cube.
Collision Detection:broad and narrow phase
Collision response for the system is handled in two phases, broad and narrow. The broad phase collision detection was handled by encasing the object in an axis aligned bounding box. This was created by scanning through the object mesh and determining the max and min points for the object. Axis aligned bounding box was chosen due to its low amount of storage needs( only 6 points, the min and max of the three axis), its ease in updating(simply translate these points by the model world coordinates) and, most importantly, it's ability to be used in the sweep and prune method. This method was deemed to be an efficient and easy to implement broad phase detection algorithm. Lists where created for each axis, feeding in the min and max point as well as storing which box these points belong to. This list is kept ordered according to the point position value, which is done manually, scanning through the linked list until a position is found with a lower value and the new element is placed before this on in the list. These lists(one for each axis) are then scanned through searching for overlapping boxes, if more than one bounding box is active at the same time on a list they are overlapping. Overlapping boxes have their index number stored in an hash table of overlapping pairs for the particular axis (overlapping pairs is a private class which stores the index for pairs of elements). Once all of the lists have been traversed the overlapping pairs are compared, this is the reason for using a hash table as store, as it allows elements in the lists to be quickly checked against the elements of another list. If all three axis contain the same colliding pair then a collision has occurred and the overlapping pair is added to a linked list of collisions which have occurred in the system.
The narrow phase collision detection uses veronoi regions. The regions for the cube are implemented as the 2d veronoi calculations for each of the polygons which make up the surface of the cube. The veritces for the cube are stored in an array of 3d vectors, thus the index for each point which makes up these triangles must be manually fed into a general function for finding the veronoi regions. This function finds the closest point on a polygon to the point fed into the function (the goal point). This is returned to the main searching function which compares the distances of the of closest point of each of the polygons and the goal point and determines the closest point on the cube overall. As mentioned here, using the veronoi regions to find a closest point, requires a point to be aiming for, with two colliding objects this is a problem. Thus based on Lin-Canny, the narrow phase collision detection scans through the features for one of the colliding objects while comparing this with the veronoi regions of the other, keeping track of which set had the smallest distance. This improves accuracy and efficiency rather than just scanning though all of the features for each object. This is done for each of the colliding pairs found in the broad phase detection, with the linked list of the colliding pairs updated with the exact location of their collision. Collision with planes is simple and is dealt with using the same formula used in the particle simulation.
Collision Response
Collision response is based around [Baraff et al. 2001]'s pseudo code for impulse response magnitude. This introduces response for colliding objects based on the colliding points calculated previously, causing a change in linear and angular momentum for the objects in question. This system implements detection and response for collisions both with planes and with other objects in the simulation. Objects colliding with each other are stored in the linked list mentioned earlier and thus this list is scanned through, applying the according response for the colliding objects. The objects also require a response to ensure the objects do not sink into each other. This is applied based on how far the objects have sunk into each other(ie a spring force). This is also similarly applied with the collision response calculations for the plane. the plane response is again done using the [Baraff et al. 2001] formula, making the necessary changes for dealing with a stationary object. The plane is also given a much high epsilon that object collisions, this is to ensure that the objects remain inside the bounds of the plane in questions, ie collisions with other objects do not cause them to penetrate the plane.
References
[Baraff et al. 2001] BARAFF, D., WITKIN, A., AND KASS, M. 2001. Physically based modeling. Siggraph.
