Module Name: Sphere
Data members: vector sphere_center, float radius, vector velocity, matrix transformations
Functions: constructor
destructor
set sphere_center
set radius
set velocity
get sphere_cneter
get radius
get velocity
sphere sphere intersection
sphere box intersection
Algorithms for each:
bool sphere_sphere_intersection (sphere s) {
vector distance = this.center - s.center;
float d_sqr = squared(distance . magnitude)
if(d_sqr > squared(this.radius + s.radius)
return no intersection;
else
return intersection;
}
bool sphere_box_intersection (box b) {
float distance = 0;
if(this.center.x < box.min.x) {
d += squared(this.center.x - box.min.x);
} else(this.center.x > ) {
d += squared(this.center.x - box.max.x);
}
if(this.center.z < box.min.z) {
d += squared(this.center.z - box.min.z);
} else(this.center.z > ) {
d += squared(this.center.z - box.max.z);
}
if(this.center.y < box.min.y) {
d += squared(this.center.y - box.min.y);
} else(this.center.y > ) {
d += squared(this.center.y - box.max.y);
}
if(d > squared(this.radius))
return no intersection;
else
return interesection;
}
Module Name: box
Data members: vector box_center, vector dimensions, vector velocity, matrix transformations, vector min, vector max
Functions: set box_center
set width
set height
set depth
set velocity
set min
set max
get box_center
get width
get height
get depth
get velocity
get min
get max
box box intersection
box sphere intersection
Algorithms for each:
bool box_box_intersection (box b) {
for each coordinate {
if (this.min > b.max or b.min > this.max) {
return intersection;
}
else
return no intersection;
}
}
bool box_sphere_intersection (sphere s) {
float distance = 0;
if(s.center.x < this.min.x) {
d += squared(s.center.x - this.min.x);
} else(this.center.x > ) {
d += squared(s.center.x - this.max.x);
}
if(x.center.z < this.min.z) {
d += squared(s.center.z - this.min.z);
} else(this.center.z > ) {
d += squared(s.center.z - this.max.z);
}
if(x.center.y < this.min.y) {
d += squared(x.center.y - this.min.y);
} else(this.center.y > ) {
d += squared(s.center.y - this.max.y);
}
if(d > squared(s.radius))
return no intersection;
else
return interesection;
}
#pragma once
#ifndef _VEC3F_H_
#define _VEC3f_H_
class Vec3f
{
public:
//Constructors
Vec3f(); //defualt
Vec3f( const Vec3f& v2 ); //Copy
Vec3f ( float x2, float y2, float z2 ); //3D Component wise
//Vec3f ( float x, float y, float z, float w );//3D + homogoneous
//Methods
float dot( const Vec3f& v2 )const; //dot product
Vec3f cross( const Vec3f& v2 ) const; //cross product
float GetMag (); //return magnitude
void normalize (); //normalization
void negate(); //mutltiplies vector by -1
//Operators
friend Vec3f operator + ( Vec3f v1, Vec3f v2 ); //Vector Addition
friend Vec3f operator - ( Vec3f v1, Vec3f v2 ); //Vector Subtraction
friend Vec3f operator * ( float S, Vec3f v1 ); //scalar multiplication
friend Vec3f operator * ( Vec3f v1, float S ); //scalar multiplication
friend Vec3f operator / ( Vec3f v1, float S ); //scalar ,"division", multiplication
friend Vec3f operator / ( float S, Vec3f v1 ); //scalar ,"division", multiplication
float operator [] ( int index );
Vec3f& operator = ( Vec3f& v2 ); //Set equal to
bool operator == ( const Vec3f& v2 ); //Logical equal to
bool operator != ( const Vec3f& v2 );//Logical not equal to
//Class variables
float x;
float y;
float z;
};
#endif
#include "Vec3f.h"
#include "math.h"
//Constructors
Vec3f::Vec3f () //defualt
{
x = 0.0;
y = 0.0;
z = 0.0;
}
Vec3f::Vec3f(float x2, float y2, float z2) // Component Wise
{
x = x2;
y = y2;
z = z2;
}
Vec3f::Vec3f(const Vec3f& v2 ) // Component Wise
{
x = v2.x;
y = v2.y;
z = v2.z;
}
//Methods
float Vec3f::dot(const Vec3f &v2) const //dot product
{
return ((v2.x*x) + (v2.y*y) + (v2.z*z) );
}
Vec3f Vec3f::cross( const Vec3f &v2) const //cross product
{
Vec3f v3;
v3.x = ((y*v2.z) - (v2.y*z));
v3.y = ((z*v2.x) - (x*v2.z));
v3.z = ((x*v2.y) - (y*v2.x));
return v3;
}
float Vec3f::GetMag()
{
return (sqrt(x*x + y*y + z*z));
}
void Vec3f::normalize()
{
float mag = Vec3f::GetMag();
x = x/mag;
y = y/mag;
z = z/mag;
}
void Vec3f::negate()
{
x = -x;
y = -y;
z = -z;
}
float Vec3f::operator []( int index )
{
if ( index < 3 && index > -1 )
{
if ( index == 0 ) return x;
if ( index == 1 ) return y;
if ( index == 2 ) return z;
}
}
Vec3f& Vec3f::operator =( Vec3f& v2)
{
//Vec3f ans( v2.x, v2.y, v2.z);
x = v2.x;
y = v2.y;
z = v2.z;
return *this;
}
bool Vec3f::operator ==( const Vec3f &v2)
{
return ( (x == v2.x) && (y == v2.y) && (z == v2.z));
}
bool Vec3f::operator !=( const Vec3f &v2)
{
return !( (x == v2.x) && (y == v2.y) && (z == v2.z));
}
Vec3f operator - (Vec3f v1, Vec3f v2)
{
return (Vec3f(v1.x - v2.x, v1.y - v2.y, v1.z - v2.z));
}
Vec3f operator + (Vec3f v1, Vec3f v2)
{
return (Vec3f(v1.x + v2.x, v1.y + v2.y, v1.z + v2.z));
}
Vec3f operator * ( float S, Vec3f v1 )
{
return (Vec3f(v1.x*S, v1.y*S, v1.z*S));
}
Vec3f operator * ( Vec3f v1, float S )
{
return (Vec3f(v1.x*S, v1.y*S, v1.z*S));
}
Vec3f operator / ( Vec3f v1, float S )
{
if ( ( S > 0 ) || ( S < 0 ) )
{
return (Vec3f(v1.x/S, v1.y/S, v1.z/S));
}
else
{
return (Vec3f(v1.x, v1.y, v1.z));
}
}
Vec3f operator / ( float S, Vec3f v1 )
{
if ( ( S > 0 ) || ( S < 0 ) )
{
return (Vec3f(v1.x/S, v1.y/S, v1.z/S));
}
else
{
return (Vec3f(v1.x, v1.y, v1.z));
}
}
#pragma once
#ifndef _MAT3F_H_
#define _MAT3F_H_
#include "Vec3f.h"
class Mat3f
{
public:
//Constructors
Mat3f(); //defualt
Mat3f( const Mat3f& mat); //Copy constructor
Mat3f( float r0c0, float r0c1, float r0c2, float r0c3,
float r1c0, float r1c1, float r1c2, float r1c3,
float r2c0, float r2c1, float r2c2, float r2c3,
float r3c0, float r3c1, float r3c2, float r3c3 ); //Component Wise
//Operators
friend Mat3f operator + ( Mat3f m1, Mat3f m2 ); //Vector Addition
friend Mat3f operator - ( Mat3f m1, Mat3f m2 ); //Vector Subtraction
friend Mat3f operator * ( float S, Mat3f m1 ); //scalar multiplication
friend Mat3f operator * ( Mat3f m1, float S ); //scalar multiplication
friend Mat3f operator * ( Mat3f m1, Mat3f m2 ); //matrix multiplication
friend Vec3f operator * ( Mat3f m1, Vec3f v1 ); //vector multiplication
void QuatRotate( float angle, Vec3f axis ); //Quaternion based rotation matrix
void Identity (); //set matrix to identity matrix
Mat3f& operator = ( Mat3f& m2 ); //Set equal to
//data members
float m[4][4];
};
#endif
#include "Mat3f.h"
#include "math.h"
Mat3f::Mat3f () //default
{
m[0][0] = 1.0; m[0][1] = 0.0; m[0][2] = 0.0; m[0][3] = 0.0;
m[1][0] = 0.0; m[1][1] = 1.0; m[1][2] = 0.0; m[1][3] = 0.0;
m[2][0] = 0.0; m[2][1] = 0.0; m[2][2] = 1.0; m[2][3] = 0.0;
m[3][0] = 0.0; m[3][1] = 0.0; m[3][2] = 0.0; m[3][3] = 1.0;
}
Mat3f::Mat3f ( const Mat3f& mat ) //default
{
m[0][0] = mat.m[0][0]; m[0][1] = mat.m[0][1]; m[0][2] = mat.m[0][2]; m[0][3] = mat.m[0][3];
m[1][0] = mat.m[1][0]; m[1][1] = mat.m[1][1]; m[1][2] = mat.m[1][2]; m[1][3] = mat.m[1][3];
m[2][0] = mat.m[2][0]; m[2][1] = mat.m[2][1]; m[2][2] = mat.m[2][2]; m[2][3] = mat.m[2][3];
m[3][0] = mat.m[3][0]; m[3][1] = mat.m[3][1]; m[3][2] = mat.m[3][2]; m[3][3] = mat.m[3][3];
}
Mat3f::Mat3f ( float r0c0, float r0c1, float r0c2, float r0c3,
float r1c0, float r1c1, float r1c2, float r1c3,
float r2c0, float r2c1, float r2c2, float r2c3,
float r3c0, float r3c1, float r3c2, float r3c3 )
{
m[0][0] = r0c0; m[0][1] = r0c1; m[0][2] = r0c2; m[0][3] = r0c3;
m[1][0] = r1c0; m[1][1] = r1c1; m[1][2] = r1c2; m[1][3] = r1c3;
m[2][0] = r2c0; m[2][1] = r2c1; m[2][2] = r2c2; m[2][3] = r2c3;
m[3][0] = r3c0; m[3][1] = r3c1; m[3][2] = r3c2; m[3][3] = r3c3;
}
Mat3f operator * ( float S, Mat3f m1 )
{
return (Mat3f( m1.m[0][0] = S*m1.m[0][0], m1.m[0][1] = S*m1.m[0][1], m1.m[0][2] = S*m1.m[0][2], m1.m[0][3] = S*m1.m[0][3],
m1.m[1][0] = S*m1.m[1][0], m1.m[1][1] = S*m1.m[1][1], m1.m[1][2] = S*m1.m[1][2], m1.m[1][3] = S*m1.m[1][3],
m1.m[2][0] = S*m1.m[2][0], m1.m[2][1] = S*m1.m[2][1], m1.m[2][2] = S*m1.m[2][2], m1.m[2][3] = S*m1.m[2][3],
m1.m[3][0] = S*m1.m[3][0], m1.m[3][1] = S*m1.m[3][1], m1.m[3][2] = S*m1.m[3][2], m1.m[3][3] = S*m1.m[3][3] ));
}
Mat3f operator * ( Mat3f m1, float S )
{
return (Mat3f( m1.m[0][0] = S*m1.m[0][0], m1.m[0][1] = S*m1.m[0][1], m1.m[0][2] = S*m1.m[0][2], m1.m[0][3] = S*m1.m[0][3],
m1.m[1][0] = S*m1.m[1][0], m1.m[1][1] = S*m1.m[1][1], m1.m[1][2] = S*m1.m[1][2], m1.m[1][3] = S*m1.m[1][3],
m1.m[2][0] = S*m1.m[2][0], m1.m[2][1] = S*m1.m[2][1], m1.m[2][2] = S*m1.m[2][2], m1.m[2][3] = S*m1.m[2][3],
m1.m[3][0] = S*m1.m[3][0], m1.m[3][1] = S*m1.m[3][1], m1.m[3][2] = S*m1.m[3][2], m1.m[3][3] = S*m1.m[3][3] ));
}
Mat3f operator + ( Mat3f m1, Mat3f m2 )
{
return (Mat3f ( m1.m[0][0] + m2.m[0][0], m1.m[0][1] + m2.m[0][1], m1.m[0][2] + m2.m[0][2], m1.m[0][3] + m2.m[0][3],
m1.m[1][0] + m2.m[1][0], m1.m[1][1] + m2.m[1][1], m1.m[1][2] + m2.m[1][2], m1.m[1][3] + m2.m[0][3],
m1.m[2][0] + m2.m[2][0], m1.m[2][1] + m2.m[2][1], m1.m[2][2] + m2.m[2][2], m1.m[2][3] + m2.m[0][3],
m1.m[3][0] + m2.m[3][0], m1.m[3][1] + m2.m[3][1], m1.m[3][2] + m2.m[3][2], m1.m[3][3] + m2.m[0][3] ) );
}
Mat3f operator - ( Mat3f m1, Mat3f m2 )
{
return (Mat3f ( m1.m[0][0] - m2.m[0][0], m1.m[0][1] - m2.m[0][1], m1.m[0][2] - m2.m[0][2], m1.m[0][3] - m2.m[0][3],
m1.m[1][0] - m2.m[1][0], m1.m[1][1] - m2.m[1][1], m1.m[1][2] - m2.m[1][2], m1.m[1][3] - m2.m[0][3],
m1.m[2][0] - m2.m[2][0], m1.m[2][1] - m2.m[2][1], m1.m[2][2] - m2.m[2][2], m1.m[2][3] - m2.m[0][3],
m1.m[3][0] - m2.m[3][0], m1.m[3][1] - m2.m[3][1], m1.m[3][2] - m2.m[3][2], m1.m[3][3] - m2.m[0][3] ) );
}
Mat3f operator * ( Mat3f m1, Mat3f m2 )
{
float mat[4][4];
for ( int i = 0; i < 4; i ++ )
{
for ( int j = 0; j < 4; j++ )
{
mat[j][i] = m1.m[0][j]*m2.m[i][0] + m1.m[1][j]*m2.m[i][1] + m1.m[2][j]*m2.m[i][2] + m1.m[3][j]*m2.m[i][3];
}
}
return (Mat3f ( mat[0][0], mat[0][1], mat[0][2], mat[0][3],
mat[1][0], mat[1][1], mat[1][2], mat[1][3],
mat[2][0], mat[2][1], mat[2][2], mat[2][3],
mat[3][0], mat[3][1], mat[3][2], mat[3][3] ) );
}
Vec3f operator * ( Mat3f m1, Vec3f v1 )
{
return ( Vec3f( (m1.m[0][0]*v1.x + m1.m[0][1]*v1.y + m1.m[0][2]*v1.z + m1.m[0][3]),
(m1.m[1][0]*v1.x + m1.m[1][1]*v1.y + m1.m[1][2]*v1.z + m1.m[1][3]),
(m1.m[2][0]*v1.x + m1.m[2][1]*v1.y + m1.m[2][2]*v1.z + m1.m[2][3]) )
);
}
Mat3f& Mat3f::operator = ( Mat3f& m2 )
{
m[0][0] = m2.m[0][0]; m[0][1] = m2.m[0][1]; m[0][2] = m2.m[0][2]; m[0][3] = m2.m[0][3];
m[1][0] = m2.m[1][0]; m[1][1] = m2.m[1][1]; m[1][2] = m2.m[1][2]; m[1][3] = m2.m[1][3];
m[2][0] = m2.m[2][0]; m[2][1] = m2.m[2][1]; m[2][2] = m2.m[2][2]; m[2][3] = m2.m[2][3];
m[3][0] = m2.m[3][0]; m[3][1] = m2.m[3][1]; m[3][2] = m2.m[3][2]; m[3][3] = m2.m[3][3];
return *this;
}
void Mat3f::QuatRotate( float angle, Vec3f axis )
{
float t = sin ( angle / 2.0f), s = cos ( angle / 2.0f);
float x = axis.x*t, y = axis.y*t, z = axis.z*t, w = s;
m[0][0] = 1.0f - 2.0f*y*y - 2.0f*z*z;
m[0][1] = 2.0f*x*y - 2.0f*w*z;
m[0][2] = 2.0f*x*z + 2.0f*w*y;
m[1][0] = 2.0f*x*y + 2*w*z;
m[1][1] = 1.0f - 2.0f*x*x - 2.0f*z*z;
m[1][2] = 2.0f*y*z - 2.0f*w*x;
m[2][0] = 2.0f*x*z - 2.0f*w*y;
m[2][1] = 2.0f*y*z + 2.0f*w*x;
m[2][2] = 1.0f - 2.0f*x*x - 2.0f*y*y;
}
void Mat3f::Identity()
{
m[0][0] = 1.0; m[0][1] = 0.0; m[0][2] = 0.0; m[0][3] = 0.0;
m[1][0] = 0.0; m[1][1] = 1.0; m[1][2] = 0.0; m[1][3] = 0.0;
m[2][0] = 0.0; m[2][1] = 0.0; m[2][2] = 1.0; m[2][3] = 0.0;
m[3][0] = 0.0; m[3][1] = 0.0; m[3][2] = 0.0; m[3][3] = 1.0;
}
Procedural Elements Explained!: Collision Detection and Response, an Overview
By Eric Stegemoller
Introduction:
My purpose for writing this overview is to begin an explanation of how we are going about handling the technical aspects of simulating the many physical effects that cannot be produced by standard key frame animating in Maya. This overview is also meant to be a point of organizing the research, plans and elements that we have already developed thus far. My final purpose is to establish the mathematics, physics and algorithms as they pertain to our systems. Finally I would like to say that what is established here is not set in stone as many problems and solutions will not be apparent to us until the code has been fully tested. (I also may very well write down some things that may be plainly incorrect due to my own inexperience/ignorance in some of the subject matter.)
The Situation:
When wanting to detect collisions between two complex objects such as humanoid characters, such as we have in our animation project, it is imperative that the geometry used in testing for collisions be simplified as much as possible. This makes the algorithms less complicated and the number of calculations fewer. This can come at a cost of physical accuracy and as such we must take care to be aware of the degree of accuracy that is requisite of each situation we apply our detection systems to. Our project calls for the presence of large crowds of characters engaging in a battle scene. As such we will have many, many calls to test for collisions between characters that will be roving about a very chaotic environment filled with other moving objects/characters.
In the most physically accurate view of the problem we would be testing each complex mesh of our characters against one another whether that is by tessellation the mesh and testing the many, possibly thousands of triangles composing the meshes or some other such system of division. If our characters were composed of even a few hundred such triangles then you can imagine how quickly the render time would increase. Fortunately for us we can simplify our situation by looking at; the physicality of our character models, what situations they’ll be put in, and how best we can simplify this in terms of math and physics.
Our Models:
As can be seen we had the foresight to construct our character models from fairly basic geometric shapes making our job of procedural processing character motion much easier. Essentially it is a lot cleaner physics and math to simulate a box’s or sphere’s motion than that of some lumpy organic critter. This gives us a tremendous advantage as if we wanted to generate a simple geometric representation of say our square guy’s head we could merely bound it with a box with little loss in representation. Which makes the most important point; in order to easily represent a character mathematically we must choose simple geometry to fit around their bodies as a whole or in parts such that there is a “close fit” to the model. As can be seen in the examples below there occurs the problem of what I call “white space” or void space. (INSERT MODEL PICS) White space is the unfilled areas between the actual model of the character and the shapes we use to approximate it. This can present a myriad of problems as a white space area would intersect another object before the actual model itself. So here there is already an apparent loss in accuracy. Along with the white space problem is the issues of contiguous surfaces vs. polygonal surfaces i.e. spheres vs. boxes. In the case of our circle/rock guy he is composed of spherical objects so if say his head were to be approximated by a box or some sort of polygon there exists an issue of the fact that his representation has corners were as his head does not. This would cause evident problems in a physical simulation of his head, as we all know cubes just don’t roll as easily as spheres. So when selecting our representative geometry we once again come back to the question of: How accurate do we need it to be? The answer to this lies in looking at what physical situations we want to simulate and what we want to get from them.
The Situations:
When looking over our plans for our shots (listed else where, include link?) it is evident that we will need to simulate the following physical situations:
1.Soldiers bumping into Soldiers
2.Soldiers bumping into Objects
3.Projectiles hitting Soldiers
4.Dead soldiers Collapsing/Being moved by some external force
The first is just soldiers wishing to avoid passing through each other as they seek out enemy combatants. Soldiers and object collisions will consists of soldiers wanting to avoid the catapults, dead bodies, catapult shot or anything else that litters the battle field.
Projectiles hitting soldiers is pretty self explanatory; we just want to know when someone takes a trident or boulder to the head so we can kill’em. The fourth will be better expounded upon in our explanation of the Rag-Doll Physics System but it relies upon collision detection and processing to carry this out.
What follows from here in the subsequent sections is a breakdown of each section above and how we are going to go about solving these problems with consideration to the accuracy we need and how we will achieve this with our geometric approximation and methods of physics simulation.
Case 1: Soldiers bumping into Soldiers
A soldier bumping into soldiers is perhaps the simplest of our cases this is due the fact that Tim and Kevin will have a system that is a mixture of flocking, behavior and crowd control that will bring some order to the chaos mainly through controlling the movements of the soldiers as well as their actions. From my understanding of their system collision detection and response will occur when the soldiers come out from their controlled rank and file marching behavior and engage in battle under their own local behavior control. Essentially what is needed is that each soldier maintains a certain amount of “personal space” as they move about the battle seeking the enemy so as not to run through their comrades, already engaged enemies or other obstacles. In order to create this effect each soldier will have a sphere attached to them to represent this personal bubble. When two soldiers get too close to one another their two spheres touch which will trigger them to adjust their course to avoid one another. The computation for sphere-sphere collision is simple enough, when the distance between two objects D, and the radius of two spheres R1 and R2 is such that: D = R1+R2 , then a collision is present. This is illustrated below in the animation. (INSERT ANIMATION) So in this way we avoid true physical collision between two soldiers and avoid a computation of having to process the physical results of two soldiers truly bumping into one another. (Technical Note: We have decided to effectively project our sphere onto the ground plane which is totally flat at the battle plain which avoids issues of having to deal with the roundness of the sphere, so it is like the soldier actually surrounded by a column/cylinder.)
Case 2: Soldiers bumping into Objects
This case is our other fairly easy case as it is another case of avoidance. The only way in which it differs from Case 1 is that for some objects, such as the catapults, we will use boxes to bound them because boxes solve the white space issue better for such objects (we also want our soldiers to avoid the catapults but pass somewhat close). Other than things like the catapults (which sometimes move) the other objects to avoid will be stationary such as spent catapult shot or tridents.
Case 3: Projectiles hitting Soldiers
This case is our first case which will require an actual calculated physics response. For our project projectiles will come in the form of: tridents (Yeah tridents!) and catapult shot (boulders). After determining a boulder or trident has struck a soldier (using the bounding boxes of the Rag-Doll system to test against for collisions, more on that later) we will tag the soldier as being dead and then calculate the impact force and feed this to the Rag-Doll system to effect his motion appropriately, in addition to this we will determine effect on the projectile’s motion. Also we will test for collision with the ground plane and affect the projectile’s motion accordingly (bouncing, rolling or stopping etc.). With regards to the soldiers much of this depends on the Rag-Doll system which is a whole section of explanation in and of itself. Concerning the bounding geometry of the tridents and boulders they too will be close fitting spheres for the boulders and a closefitting box or two for the trident. (SEE PIC)
TECHNICAL NOTE: Since these types of collisions appear in very specific shots we very well may pair this down further such that we might just feed forces to the Rag-Doll system when a regularly animated boulder strikes near by etc. See the animation below for a better idea of the effect we wish to create. (INSERT ANIMATION)
Case 4: Dead soldiers Collapsing/Being moved by some external force
This case will depend the most heavily upon the Rag-Doll system as it consists of letting procedural elements take total control over the movement and articulation of the figure based upon the mathematics of physical simulation. This covers such situations as our letting a lifeless soldier crumple to the ground, or be flung by a force of impact in a realistic manner based upon forces acting upon him as his various limbs strike the objects around him on his journey from the time of impact till the end of the scene or rest position. The technicalities, mathematics and finally Rag-Doll system of this and the physics behind simulating rigid body collision will be covered in the next section to come.