-
Notifications
You must be signed in to change notification settings - Fork 2
Physics Engine
!(UML Here)[]
General description of object interactions:
- Physics engine helps manage physics worlds
- Physics worlds contain and manage all of the data belonging to their world
- A collision body represents a game object - a collection of box and sphere colliders. Has an absolute position and rotation that should match that of the object in the game world.
- Box/Sphere colliders represent a part or whole of a collision body
- Positioned relative to their parent collision body
Our collision detection operates in two "phases"; a broad phase and a narrow phase. This allows for cheap but inaccurate collision detection over all objects, and then more computationally expensive but accurate collision detection for objects likely to be colliding.
Broad phase collision detection compares the axis-aligned bounding boxes of all objects in the physics world against each other. If any vertex of one AABB is contained within the bounds of or shares a position with another AABB, then the two AABB's must be colliding.
This is implemented as follows;
TODO: MOVE TO APPENDIX
bool testAABBCollision(CollisionBody *a, CollisionBody *b){
assert(a != NULL && b != NULL);
// the min and max points of each CollisionBody, which will be used to determine if the two AABB's of the CollisionBodies are intersecting (colliding)
float x1min, x1max, y1min, y1max, z1min, z1max, x2min, x2max, y2min, y2max, z2min, z2max;
// determine which coordinate is larger than the other, for each coordinate pair of each CollisionBody
minMax(a->AABBx1, a->AABBx2, &x1min, &x1max);
minMax(a->AABBy1, a->AABBy2, &y1min, &y1max);
minMax(a->AABBz1, a->AABBz2, &z1min, &z1max);
minMax(b->AABBx1, b->AABBx2, &x2min, &x2max);
minMax(b->AABBy1, b->AABBy2, &y2min, &y2max);
minMax(b->AABBz1, b->AABBz2, &z2min, &z2max);
return (x1min <= x2max && x1max >= x2min) &&
(y1min <= y2max && y1max >= y2min) &&
(z1min <= z2max && z1max >= z2min);
}
Narrow phase collision detection compares both axis-aligned bounding boxes and sphere colliders
Overall narrow phase implementation:
bool testNarrowPhaseCollision(CollisionBody* a, CollisionBody* b, PVec3* fn, float* pen){
assert(a != NULL && b != NULL);
// compare all box colliders with each other
for(size_t i = 0; i < a->numOfBoxColliders; ++i){
for(size_t j = 0; j < b->numOfBoxColliders; ++j){
if(testBoxColliderCollision(a->BoxColliders[i], b->BoxColliders[j], fn, pen)){
return true;
}
}
}
// compare all sphere colliders with each other
for(size_t i = 0; i < a->numOfSphereColliders; ++i){
for(size_t j = 0; j < b->numOfSphereColliders; ++j){
if(testSphereColliderCollision(a->SphereColliders[i], b->SphereColliders[j], fn, pen)){
return true;
}
}
}
// compare boxes of a with spheres of b
for(size_t i = 0; i < a->numOfBoxColliders; ++i){
for(size_t j = 0; j < b->numOfSphereColliders; ++j){
if(testBoxSphereCollision(a->BoxColliders[i], b->SphereColliders[j], fn, pen)){
return true;
}
}
}
// compare spheres of a with boxes of b
for(size_t i = 0; i < a->numOfSphereColliders; ++i){
for(size_t j = 0; j < b->numOfBoxColliders; ++j){
if(testBoxSphereCollision(b->BoxColliders[j], a->SphereColliders[i], fn, pen)){
return true;
}
}
}
return false;
}
Similar to broad phase, determines if two AABBs are colliding. If they are, determine the collision normal and how far the objects are penetrating into each other.
Collision normal is determined by determining the axis of least overlap, and then the collision normal must be along that axis.
bool testBoxColliderCollision(BoxCollider *a, BoxCollider *b, PVec3* fn, float* pen){
assert(a != NULL && b != NULL);
// alg from https://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-the-basics-and-impulse-resolution--gamedev-6331
PVec3 cenA = getAABBCenter(a);
PVec3 cenB = getAABBCenter(b);
PVec3 n = subtractPVec3(&cenB, &cenA);
// calculate half-extents along x for each object
float a_extent = (a->AABBx2 - a->AABBx1) / 2;
float b_extent = (b->AABBx2 - b->AABBx1) / 2;
// calculate x overlap
float x_overlap = a_extent + b_extent - fabsf(n.data[0]);
// SAT test on X axis
if(x_overlap > 0){
// calculate half-extents along y for each object
a_extent = (a->AABBy2 - a->AABBy1) / 2;
b_extent = (b->AABBy2 - b->AABBy1) / 2;
// calculate y overlap
float y_overlap = a_extent + b_extent - fabsf(n.data[1]);
if(y_overlap > 0){
// calculate half-extents along z for each object
a_extent = (a->AABBz2 - a->AABBz1) / 2;
b_extent = (b->AABBz2 - b->AABBz1) / 2;
// calculate z overlap
float z_overlap = a_extent + b_extent - fabsf(n.data[2]);
if(z_overlap > 0){
// determine axis of most pen
float min = getMin(x_overlap, getMin(y_overlap, z_overlap));
if(min == x_overlap){
if(n.data[0] < 0){
fn->data[0] = -1;
fn->data[1] = 0;
fn->data[2] = 0;
}
else{
fn->data[0] = 1;
fn->data[1] = 0;
fn->data[2] = 0;
}
*pen = x_overlap;
}
else if (min == y_overlap){
if(n.data[1] < 0){
fn->data[0] = 0;
fn->data[1] = -1;
fn->data[2] = 0;
}
else{
fn->data[0] = 0;
fn->data[1] = 1;
fn->data[2] = 0;
}
*pen = y_overlap;
}
else{
if(n.data[2] < 0){
fn->data[0] = 0;
fn->data[1] = 0;
fn->data[2] = -1;
}
else{
fn->data[0] = 0;
fn->data[1] = 0;
fn->data[2] = 1;
}
*pen = z_overlap;
}
return true;
}
}
}
return false;
}
Determines if a box collider is colliding with a sphere collider. This is done by determining the minimum distance between the sphere collider and box collider, and if this distance is less than the radius of the sphere collider then the colliders must be colliding.
bool testBoxSphereCollision(BoxCollider *a, SphereCollider *b, PVec3* fn, float* pen){
float x = getMax(a->AABBx1, getMin(b->xPostRot, a->AABBx2));
float y = getMax(a->AABBy1, getMin(b->yPostRot, a->AABBy2));
float z = getMax(a->AABBz1, getMin(b->zPostRot, a->AABBz2));
float distance_between = sqrtf(powf(x - b->xPostRot, 2) +
powf(y - b->yPostRot, 2) +
powf(z - b->zPostRot, 2));
if (distance_between < b->radius) {
determineCollisionNormalBoxToSphere(a, b, fn, pen);
return true;
} else {
return false;
}
}
Determines if two spheres are colliding. This is done by getting the distance from the center of each sphere, and if the distance is less than or equal to the sum of radii then the spheres must be colliding.
bool testSphereColliderCollision(SphereCollider *a, SphereCollider *b, PVec3* fn, float* pen){
assert(a != NULL && b != NULL);
// separated for clarity
if(a->xPostRot + a->radius >= b->xPostRot - b->radius && // a within b
a->xPostRot - a->radius <= b->xPostRot + b->radius) {
if(a->yPostRot + a->radius >= b->yPostRot - b->radius &&
a->yPostRot - a->radius <= b->yPostRot + b->radius){
if(a->zPostRot + a->radius >= b->zPostRot - b->radius &&
a->zPostRot - a->radius <= b->zPostRot + b->radius){
Matrix41 cenA;
cenA.elem[0] = a->xPostRot;
cenA.elem[1] = a->yPostRot;
cenA.elem[2] = a->zPostRot;
Matrix41 cenB;
cenB.elem[0] = b->xPostRot;
cenB.elem[1] = b->yPostRot;
cenB.elem[2] = b->zPostRot;
*pen = a->radius + b->radius - distance(cenB, cenA);
fn->data[0] = cenB.elem[0] - cenA.elem[0];
fn->data[1] = cenB.elem[1] - cenA.elem[1];
fn->data[2] = cenB.elem[2] - cenA.elem[2];
return true;
}
}
}
return false;
}
For every collision, resolve the collision.
void collisionResolution(Collision* collisionArray, size_t numOfCollisions) {
if (collisionArray == NULL || numOfCollisions == 0) {
return;
}
for (size_t i = 0; i < numOfCollisions; ++i) {
resolveCollision(&collisionArray[i]);
}
}
void resolveCollision( Collision* collision )
{
if (collision->body1->mass + collision->body2->mass == 0.0f) {
return;
}
float inv_massA = 0.0f;
float inv_massB = 0.0f;
if (collision->body1->mass > 0.0f) {
inv_massA = (1 / collision->body1->mass);
}
if (collision->body2->mass > 0.0f) {
inv_massB = (1 / collision->body2->mass);
}
// Calculate relative velocity
PVec3 rv = subtractPVec3(&collision->body2->velocity, &collision->body1->velocity);
// Calculate relative velocity in terms of the normal direction
float velAlongNormal = dotProductPVec3(&rv, &collision->normal);
// Do not resolve if velocities are separating
if(velAlongNormal > 0) {
return;
}
// Calculate restitution
float e = fminf( collision->body1->restitution, collision->body2->restitution);
// Calculate impulse scalar
float j = (-1.0f *(1.0f + e)) * velAlongNormal;
float invMassSum = inv_massA + inv_massB; /*+ Sqr( raCrossN ) * A->iI + Sqr( rbCrossN ) * B->iI;*/
//j /= 1 / collision->body1->mass + 1 / collision->body2->mass;
j /= invMassSum;
// Apply impulse
PVec3 impulse = PVec3MultiplyScalar(&collision->normal, j);
//TODO: Static objects will most likely need to be accounted for here.
PVec3 aDiff = PVec3MultiplyScalar(&impulse, inv_massA);
collision->body1->velocity = subtractPVec3(&collision->body1->velocity , &aDiff);
PVec3 bDiff = PVec3MultiplyScalar(&impulse, inv_massB);
collision->body2->velocity = addPVec3(&collision->body2->velocity , &bDiff);
positionalCorrection(collision, inv_massA, inv_massB);
}
TODO:
- How to add object to physics world
- How to create collision body
- How to transform collision body
- How to create collider
- How to transform collider
- How to remove object from physics world
- How to update game state from Physics Engine
Since its an external lib, maybe also provide instructions on preconditions for the Physics Engine to work (eg. at least one PhysicsWorld exists)
Before every draw call, the following maintenance to the Physics World is recommended:
- Update object positions in the physics world if they have been "manually" moved
-
PhysicsEngine_updateWorld()
, passing in the current delta time.
The PhysicsEngine
aims to be an overall manager and container of all physics objects and their processes. The PhysicsEngine
allows the client to create and free both itself and numerous PhysicsWorld
's contained within as the client requests.
It also is home to the PhysicsEngine_updateWorld()
function, which initiates processing of all the objects in the given PhysicsWorld
to resolve current accelerations (typically gravity), update current object positions based on their instantaneous velocity, and detect and resolve any resulting collisions.