Rigid Bodies
class Vertex {
constructor(world, body, x, y) {
this.position = new Phaser.Math.Vector2(x,y);
this.oldPosition = new Phaser.Math.Vector2(x,y);
this.acceleration = new Phaser.Math.Vector2();
this.parent = body;
}
}
class Edge {
constructor( world, body, pV1, pV2, pBoundary) {
this.v1 = pV1;
this.v2 = pV2;
this.length = Math.hypot(pV2.position.x - pV1.position.x, pV2.position.y - pV1.position.y); //Calculate the original length
this.parent = body;
this.boundary = pBoundary;
}
};
Now we have a working physics code that will calculate the trajectories of arbitrary points just fine. But points alone are not very useful, except when you're programming a particle simulation. Since that's normally not the case if you're into game programming, we have to extend the points in some way so we can simulate rigid body behaviour as well. If we look at rigid bodies in nature, we see that they are actually a huge amount of points (=atoms) held together by various forces.
We could of course try and create thousands of particles and connect them in some way to approximate the behaviour of rigid bodies, which would work indeed. However, that would cause a huge amount of calculations to be done for e.g. a single cube, let alone a whole game filled with physics bodies, so this isn't really an optimal solution. Luckily, it shows to be sufficient only to model the vertices of a body. If we were to simulate a box, we would simply create the four vertices that make up the shape of a box, connect them somehow and we're done.
The problem left to compute is now only that of the connections. If we again imagine a box and the four vertices, it should become clear that the distance of a vertex to another should always remain constant. If the distance between two vertices changes, this always means that the shape of the body gets deformed, and we don't want that - who would like to have a crate in his game that collapses once you stand on it? Therefore, we have to find a way to keep the distance between two vertices at a constant value.
If we had the same problem in reality, the solution would be simple - just insert some kind of pole in-between and the vertices won't approach each other anymore. We will do the exact same thing in our program; create a new class that represents an 'imaginary pole'. It connects two vertices and keeps those vertices at a constant distance. The algorithm to update these 'poles' is called once the Verlet is calculated. The algorithm itself is actually quite simple. First of all, we have to calculate the vector between the two vertices that are connected by the pole. The current distance between the two vertices is simply the length of that vector. Once we have the current length, the difference of the original length of the pole should be calculated. We can now use the difference to push the vertices to a position where the distance constraint is satisfied.
That's it - if we created a few points and connected them with our newly created edge struct, the resulting body would show very nice rigid body-behaviour, including rotational effects when it hits the floor. But why does that work? The code isn't much different from before, we only added a few lines to satisfy the distance constraint and suddenly we have rigid bodies. The reason behind this lies within our integration method. If we recall that the Verlet integration doesn't work with velocity but rather with the difference between the current position and the position before the last integration step, it should become clear that the speed of the point will change if we change its position. Therefore, since we change its position in the UpdateEdges method, its velocity will also change. The overall change in velocity looks exactly like we would expect it from a vertex of a rigid body; it is not totally correct, but good enough for games.
The only way to get rid of this problem is to execute the edge correction method more than just once per frame. The more this method is called, the more perfect the situation gets approximated, where all vertices have the right distance to each other. This gives game programmers a scalable physics algorithm - the more time is left at the end of the main loop, the more iterations can be used for the distance correction (and the collision response that will be introduced later). Vice-versa, if the main loop takes more time to execute, the iterations used for physics can be reduced so the game runs at a more or less constant frame rate.
class Polygon extends PhysicsBody {
constructor(world, x, y) {
super(world, x, y);
this.edges = [];
}
addJoint(e) {
this.edges.push(e);
this.world.addJoint(e);
}
assignParent(body) {
for (let v of this.vertices) {
v.parent = body;
}
for (let e of this.edges) {
e.parent = body;
}
}
projectVertices(axis) {
let v = 0;
// get the first point
const p = this.vertices[0].pos;
// project the point onto the vector
let min = p.dot(axis);
let max = min;
// loop over the rest of the vertices
for (let i = 0; i < this.vertices.length; i++ ) {
// get the next point
const p = this.vertices[i].pos;
// project onto the axis
v = p.dot(axis)
min = Math.min( v, min );
max = Math.max( v, max );
}
return new Interval(min, max);
}
computeAABB() {
var minX = this.vertices[0].pos.x;
var minY = this.vertices[0].pos.y;
var maxX = this.vertices[0].pos.x;
var maxY = this.vertices[0].pos.y;
for (let i = 1; i < this.vertices.length; i++) {
minX = Math.min( minX, this.vertices[ i ].pos.x );
minY = Math.min( minY, this.vertices[ i ].pos.y );
maxX = Math.max( maxX, this.vertices[ i ].pos.x );
maxY = Math.max( maxY, this.vertices[ i ].pos.y );
}
this.aabb.minX = minX;
this.aabb.minY = minY;
this.aabb.maxX = maxX;
this.aabb.maxY = maxY;
}
}
Apart from detecting whether or not the two bodies collide, the collision detection should also provide certain information about the collision. We also have to calculate a so-called collision vector that is big enough to push the two bodies apart so they don't collide anymore, but touch each other. There are of course arbitrarily much vectors that could accomplish this, but for our physics to look right we have to find the smallest of those vectors. The vector we're looking for has the pleasant property that it's always parallel to one of the lines we projected to, which means that we only have to check each edge and calculate the length of the vector needed to push the two bodies apart. Figuring out the length isn't really a hard thing to do, if we take a look at figure 8.
Once we have this, we'd be already able to write a very simple collision response. Since the collision vector we calculated pushes the two bodies apart so they don't collide anymore, we could just move all vertices of both bodies back by half the vector and we'd be done. This would work, since interpenetrations are resolved, but it wouldn't look right. The bodies would simply glide off each other, meaning they don't start to spin like a real object when hit.
The problem is that a body in our approach only spins if the velocities of its vertices differ. In the same manner, a body only changes its rotational velocity if its vertices experience different acceleration. Acceleration is change in velocity, and in Verlet integration change in velocity is equal to change in position. Therefore, if we move the two bodies back by the collision vector, we change the velocity of all vertices of both bodies by the same amount, which means that there is no change in the rotational velocity. For this reason, we need to write a better collision response.
This is where the advantage of our approach kicks in! In a rigid body system, we would have to use complicated formulas to calculate the momentum and then treat the linear and angular case separately. In our system, the whole thing is much easier - we just have to move the edge and the vertex participating in the collision backwards so they don't intersect, but touch each other. Since both the edge and the vertex are connected to the rest of their respective body, the position (and therefore the velocity) of the other vertices will change immediately to fulfil the length constraint. Both bodies will start spinning self-actingly. The whole collision response reduces to identifying the edge and the vertex that participate in the collision and separating them from each other; everything else will be done automatically by the edge correction step.
Identifying the collision edge and vertex is not that hard. The collision vertex is the vertex that lies closest to the other body. Therefore, we simply have to create a line whose normal vector is the collision normal (its starting point doesn't really matter). We then measure the distance of each vertex of the first body from the line using the line equation in vector geometry, which is
(The angle between the same vectors is equal to 0º, and hence their dot product is equal to 1. And the angle between two perpendicular vectors is 90º, and their dot product is equal to 0.)
where N is the normal vector, R[sub]0[/sub] the origin of the line, R the point to be tested and d the distance of the point from the line. The set of all points that form a line are given by d = 0 (all points that have zero distance from the line), just as a side note. Once we have the distance of each vertex from the line, we choose the one with the lowest distance - that's the collision vertex we were looking for. Please note that d can also be negative. A line separates a two dimensional space in two halves; if the point R lies in the half the line normal points into, the distance will be positive, but if it lies on the other side, the distance will be negative. Therefore, it is important in which direction the collision normal points (in the implementation presented below, it's always made sure that the collision normal points at the body containing the collision vertex).
The collision edge is even easier to find. Remember when we projected the bodies on the perpendicular of an edge to find the smallest collision vector? The collision edge is simply the edge that resulted in the smallest vector.
class SAT {
static detect( b1, b2 , manifold) {
let axis = new Vec2(); // hold the projection axis
manifold.depth = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < b1.edges.length; i++ ) {
const e = b1.edges[i];
if (!e.boundary) continue;
// Calculate the normal of each face and normalize it
axis.set(e.v1.pos.y - e.v2.pos.y, e.v2.pos.x - e.v1.pos.x).normalize();
const interval1 = b1.projectVertices( axis );
const interval2 = b2.projectVertices( axis );
const o = interval1.getOverlap(interval2);
if (o < 0) return false;
if (o < manifold.depth ) {
manifold.depth = o;
manifold.normal.copy(axis);
manifold.e = e; //Store the edge, as it is the collision edge
}
}
// now do the same against the face normals of b2
for (let i = 0; i < b2.edges.length; i++ ) {
const e = b2.edges[i];
if (!e.boundary) continue;
axis.set(e.v1.pos.y - e.v2.pos.y, e.v2.pos.x - e.v1.pos.x).normalize();
const interval1 = b1.projectVertices( axis );
const interval2 = b2.projectVertices( axis );
const o = interval1.getOverlap(interval2);
if (o < 0) return false;
if (o < manifold.depth ) {
manifold.depth = o;
manifold.normal.copy(axis);
manifold.e = e; //Store the edge, as it is the collision edge
}
}
// Ensure that the body containing the collision edge is B2 and the one conatining the collision vertex is B1
if (manifold.e.parent !== b2) {
var temp = b2;
b2 = b1;
b1 = temp;
}
//This is needed to make sure that the collision normal is pointing at B1
var cToc = new Vec2(b1.center.x - b2.center.x, b1.center.y - b2.center.y)
if (cToc.dot(manifold.normal) < 0) {
manifold.normal.negate();
}
var smallestD = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < b1.vertices.length; i++) {
// Measure the distance of the vertex from the line using the line equation
var xx = b1.vertices[i].pos.x - b2.center.x;
var yy = b1.vertices[i].pos.y - b2.center.y;
var distance = manifold.normal.x * xx + manifold.normal.y * yy;
if (distance < smallestD) {
smallestD = distance;
manifold.v = b1.vertices[i];
}
}
// return true
return true;
}
}
Collision Response
As explained above, we just have to push the collision vertex and the collision edge apart by the collision vector and we're done. This is trivial for the collision vertex. Since we already ensured that the collision normal points at the first body which contains the collision vertex, we just have to add half of the collision vector to the position of the vertex:
For the edge case, this will become a bit more complicated. The edge consists of two vertices that will move differently, depending on where the collision vertex lies. The closer it lies to the one end of the edge, the more this end will move and vice-versa. This means that we first have to calculate where on the edge the collision vertex lies. This is done using the following equation:
That's it.
class Contact {
static solve(manifold) {
var e1 = manifold.e.v1;
var e2 = manifold.e.v2;
var collisionVector = new Vec2(manifold.normal.x * manifold.depth, manifold.normal.y * manifold.depth)
var t;
if (Math.abs( e1.pos.x - e2.pos.x ) > Math.abs( e1.pos.y - e2.pos.y ) ) {
t = ( manifold.v.pos.x - collisionVector.x - e1.pos.x )/( e2.pos.x - e1.pos.x );
}
else {
t = ( manifold.v.pos.y - collisionVector.y - e1.pos.y )/( e2.pos.y - e1.pos.y );
}
var lambda = 1.0 / ( t*t + ( 1 - t )*( 1 - t ) );
var edgeMass = t * e2.parent.mass + ( 1 - t ) * e1.parent.mass;
var invCollisionMass = 1.0 / ( edgeMass + manifold.v.parent.mass );
var ratio1 = manifold.v.parent.mass * invCollisionMass;
var ratio2 = edgeMass * invCollisionMass;
e1.pos.x -= collisionVector.x * (( 1 - t )* ratio1*lambda);
e1.pos.y -= collisionVector.y * (( 1 - t )* ratio1*lambda);
e2.pos.x -= collisionVector.x * ( t * ratio1*lambda);
e2.pos.y -= collisionVector.y * ( t * ratio1*lambda);
manifold.v.pos.x += collisionVector.x * ratio2;
manifold.v.pos.y += collisionVector.y * ratio2;
}
}
Main Simluation Class
class Physics {
constructor(scene, width, height, GravitationX, GravitationY, pIterations) {
this.scene = scene;
this.screenWidth = width;
this.screenHeight = height;
this.bodies = [];
this.bodyCount = 0;
this.vertices = [];
this.vertexCount = 0;
this.edgeCount = 0;
this.edges = [];
this.gravity = new Phaser.Math.Vector2(GravitationX, GravitationY);
this.iterations = pIterations;
this.MAX_BODIES = 256; //Maximum body/vertex/edgecount the physics simulation can handle
this.MAX_VERTICES = 1024;
this.MAX_EDGES = 1024;
this.MAX_BODY_VERTICES = 10; //Maximum body/edge count a body can contain
this.MAX_BODY_EDGES = 10;
this.axis = new Phaser.Math.Vector2()
this.collisionInfo = new CollisionInfo();
}
update(dt) {
this.updateForces(dt);
this.updateVerlet(dt);
this.iterateCollisions();
}
render() { // pass the graphics object
this.graphics.clear();
this.graphics.lineStyle(1,'0xff0000')
for (let i = 0; i < this.edgeCount; i++ ) {
this.graphics.lineBetween(this.edges[ i ].v1.position.x, this.edges[ i ].v1.position.y, this.edges[ i ].v2.position.x, this.edges[ i ].v2.position.y );
}
this.graphics.fillStyle('0xffffff');
for (let i = 0; i < this.vertexCount; i++ ) {
this.graphics.fillCircle(this.vertices[ i ].position.x, this.vertices[ i ].position.y, 4);
}
}
/**
* Adds new elements to the simulation
* @param Body
*/
addBody(Body) {
this.bodies.push(Body);
this.bodyCount++;
}
addEdge(E) {
this.edges.push(E);
this.edgeCount++;
}
addVertex(V) {
this.vertices.push(V);
this.vertexCount ++;
}
findVertex( X, Y ) {
var nearestVertex = null;
var minDistance = 1000;
var coords = new Phaser.Math.Vector2(X, Y);
for (let i = 0; i < this.vertexCount; i++ ) {
var distance = Math.hypot(this.vertices[ i ].position.x - coords.x, this.vertices[ i ].position.y - coords.y);
if (distance < minDistance ) {
nearestVertex = this.vertices[ i ];
minDistance = distance;
}
}
return nearestVertex;
}
updateForces(dt) {
for (let I=0; I<this.vertexCount; I++ ) {
this.vertices[ I ].acceleration = this.gravity;
}
}
updateVerlet(dt) {
var tempX;
var tempY;
for (let i = 0; i < this.vertexCount; i++) {
let v = this.vertices[i];
tempX = v.position.x;
tempY = v.position.y;
v.position.x += v.position.x - v.oldPosition.x + v.acceleration.x * dt;
v.position.y += v.position.y - v.oldPosition.y + v.acceleration.y * dt;
v.oldPosition.x = tempX;
v.oldPosition.y = tempY;
}
}
updateEdges() {
for (let i = 0; i < this.edgeCount; i++) {
var e = this.edges[ i ];
// Calculate the vector between the two vertices
let v1v2x = e.v2.position.x - e.v1.position.x;
let v1v2y = e.v2.position.y - e.v1.position.y;
let v1v2Length = Math.hypot(v1v2x, v1v2y); //Calculate the current distance
let diff = v1v2Length - e.length; //Calculate the difference from the original length
// Normalise
var len = 1.0/Math.hypot(v1v2x, v1v2y);
v1v2x *= len;
v1v2y *= len;
// Push both vertices apart by half of the difference respectively so the distance between them equals the original length
e.v1.position.x += v1v2x diff 0.5;
e.v1.position.y += v1v2y diff 0.5;
e.v2.position.x -= v1v2x diff 0.5;
e.v2.position.y -= v1v2y diff 0.5;
}
}
iterateCollisions() {
for (let i = 0; i < this.iterations; i++ ) { //Repeat this a few times to give more exact results
//A small 'hack' that keeps the vertices inside the screen. You could of course implement static objects and create
//four to serve as screen boundaries, but the max/min method is faster
for (let t = 0; t < this.vertexCount; t++ ) {
var pos = this.vertices[ t ].position;
pos.x = Math.max( Math.min( pos.x, this.screenWidth ), 0.0 );
pos.y = Math.max( Math.min( pos.y, this.screenHeight ), 0.0 );
}
this.updateEdges(); //Edge correction step
for (let j = 0; j < this.bodyCount; j++) {
this.bodies[j].calculateCenter(); //Recalculate the center
}
for (let b1 = 0; b1 < this.bodyCount; b1++) { //Iterate trough all bodies
for (let b2 = 0; b2 < this.bodyCount; b2++) {
if (b1 != b2) {
if (this.bodiesOverlap(this.bodies[b1], this.bodies[b2])) { //Test the bounding boxes
if (this.detectCollision(this.bodies[b1], this.bodies[b2])) { //If there is a collision, respond to it
this.processCollision();
}
}
}
}
} // for loop iterating through all the bodies for intra-body collision
} // for loop this.iterations
} // end of iterateCollision method
detectCollision( b1, b2 ) {
var minDistance = 10000.0; //Initialize the length of the collision vector to a relatively large value
for (let i = 0; i < b1.edgeCount + b2.edgeCount; i++ ) { //Just a fancy way of iterating through all of the edges of both bodies at once
var e;
if (i < b1.edgeCount) {
e = b1.edges[i];
}
else {
e = b2.edges[i - b1.edgeCount];
}
//This will skip edges that lie totally inside the bodies, as they don't matter.
//The boundary flag has to be set manually and defaults to true
if (e.boundary == false) {
continue;
}
// Calculate the perpendicular to this edge and normalize it
this.axis.x = e.v1.position.y - e.v2.position.y;
this.axis.y = e.v2.position.x - e.v1.position.x;
// Normalise
var len = 1.0/ Math.hypot(this.axis.x, this.axis.y);
this.axis.x *= len;
this.axis.y *= len;
// Project both bodies onto the perpendicular
var dataA = b1.ProjectToAxis( this.axis );
var dataB = b2.ProjectToAxis( this.axis );
var distance = this.IntervalDistance( dataA.min, dataA.max, dataB.min, dataB.max ); //Calculate the distance between the two intervals
// If the intervals don't overlap, return, since there is no collision
if (distance > 0.0) {
return false;
}
else if (Math.abs(distance) < minDistance ) {
minDistance = Math.abs(distance);
// Save collision information for later
this.collisionInfo.normal.x = this.axis.x;
this.collisionInfo.normal.y = this.axis.y;
this.collisionInfo.e = e; //Store the edge, as it is the collision edge
}
}
this.collisionInfo.depth = minDistance;
if (this.collisionInfo.e.parent != b2) { //Ensure that the body containing the collision edge lies in B2 and the one conatining the collision vertex in B1
var temp = b2;
b2 = b1;
b1 = temp;
}
// int Sign = SGN( CollisionInfo.Normal.multiplyVal( B1.Center.minus(B2.Center) ) ); //This is needed to make sure that the collision normal is pointing at B1
var mult = this.collisionInfo.normal.x xx + this.collisionInfo.normal.y yy;
// Remember that the line equation is N*( R - R0 ). We choose B2->Center as R0; the normal N is given by the collision normal
if (mult < 0) {
// Revert the collision normal if it points away from B1
this.collisionInfo.normal.x = 0-this.collisionInfo.normal.x;
this.collisionInfo.normal.y = 0-this.collisionInfo.normal.y;
}
var smallestD = 10000.0; //Initialize the smallest distance to a large value
for (let i=0; i<b1.vertexCount; i++) {
// Measure the distance of the vertex from the line using the line equation
// float Distance = CollisionInfo.Normal.multiplyVal( B1.Vertices[I].Position.minus(B2.Center) );
var xx = b1.vertices[i].position.x - b2.center.x;
var yy = b1.vertices[i].position.y - b2.center.y;
var distance = this.collisionInfo.normal.x xx + this.collisionInfo.normal.y yy;
if (distance < smallestD) { //If the measured distance is smaller than the smallest distance reported so far, set the smallest distance and the collision vertex
smallestD = distance;
this.collisionInfo.v = b1.vertices[i];
}
}
return true; //There is no separating axis. Report a collision!
}
processCollision() {
var e1 = this.collisionInfo.e.v1;
var e2 =this.collisionInfo.e.v2;
var collisionVectorX = this.collisionInfo.normal.x * this.collisionInfo.depth;
var collisionVectorY = this.collisionInfo.normal.y * this.collisionInfo.depth;
var t;
if (Math.abs( e1.position.x - e2.position.x ) > Math.abs( e1.position.y - e2.position.y ) ) {
t = ( this.collisionInfo.v.position.x - collisionVectorX - e1.position.x )/( e2.position.x - e1.position.x );
}
else {
t = ( this.collisionInfo.v.position.y - collisionVectorY - e1.position.y )/( e2.position.y - e1.position.y );
}
var lambda = 1.0/( t*t + ( 1 - t )*( 1 - t ) );
var edgeMass = t*e2.parent.mass + ( 1 - t )*e1.parent.mass; //Calculate the mass at the intersection point
var invCollisionMass = 1.0/( edgeMass + this.collisionInfo.v.parent.mass );
var ratio1 = this.collisionInfo.v.parent.mass*invCollisionMass;
var ratio2 = edgeMass*invCollisionMass;
e1.position.x -= collisionVectorX (( 1 - t )ratio1*lambda);
e1.position.y -= collisionVectorY (( 1 - t )ratio1*lambda);
e2.position.x -= collisionVectorX ( t ratio1*lambda);
e2.position.y -= collisionVectorY ( t ratio1*lambda);
this.collisionInfo.v.position.x += collisionVectorX * ratio2;
this.collisionInfo.v.position.y += collisionVectorY * ratio2;
}
IntervalDistance( minA, maxA, minB, maxB) {
if (minA < minB) {
return minB - maxA;
}
else {
return minA - maxB;
}
}
/**
* Used for optimization to test if the bounding boxes of two bodies overlap.
* @param B1
* @param B2
* @return
*/
bodiesOverlap( B1, B2 ) {
return ( B1.minX <= B2.maxX ) && ( B1.minY <= B2.maxY ) && ( B1.maxX >= B2.minX ) && ( B2.maxY >= B1.minY );
}
}
BOOT
class Game extends Phaser.Scene {
constructor() {
super({key: "Game"});
}
create() {
this.world = new Physics(this, SCREEN_WIDTH, SCREEN_HEIGHT, 0.0, 1, 15 );
for (let X = 20; X < SCREEN_WIDTH; X += 100 ) {
for( let Y = 50; Y < SCREEN_HEIGHT - 50; Y += 100 ) {
const box = new PhysicsBody(this.world, 1).createBox( this.world, X, Y, 50, 50 ); //Create a few boxes
}
}
for( let X = 50; X < SCREEN_WIDTH - 50; X += 130 ) {
const tri = new PhysicsBody(this.world, 1).createTriangle( this.world, X, 0, 100, 45); //Create a few triangles. Only boxes would get boring, right?
}
}
update(t, dt) {
this.world.update(dt*0.001);
this.world.render();
}
}
CODEPEN
Useful References
This is most commonly referred to
BELOW IS A complete demo using C.
TEARBLE CLOTH
https://carmencincotti.com/2022-08-01/the-pbd-simulation-loop/ (quite indepth)
https://zalo.github.io/blog/constraints/ lots of examples on solving constraints using projection
Comentários