[b]Overview[/b]:
So this is a physics engine that I'm developing as a graduate project. It must also be hardware accelerated to run on the GPU with OpenCL. After its completion, I have to write a paper to submit to academia for publishing. You can think of the project as a PhysX-2D, except that it's OpenCL-based to run on both ATI AND Nvidia cards (or any other OpenCL-capable coprocessor), whereas PhysX is only hardware accelerated on NVidia cards.
The library is written in ANSI C (not ++), and only has a dependency on LibGyro2.0 (which is being codeveloped with it and also written in C). All algorithms/code that will be implemented as OpenCL kernels on OpenCL-capable platforms will also be implemented in software (on the CPU) for platforms without OpenCL. Thanks to the SIMD (single instruction multiple data) manner in which I've been writing the engine, it will also allow for hardware acceleration using regular SIMD instructions (with a bit of fuck-ugly assembly) on capable platforms such as SSE instructions on Intel/AMD cards, matrix/vector operations on the Dreamcast's CPU, and the vector coprocessor on the PSP.
For now, I'm implementing everything in straight C. Once this is complete, I'll begin moving functions over to the GPU as OpenCL kernels. Finally, we can worry about hardware-specific SIMD optimizations later.
[b]Structure[/b]
The main functionality of the engine is split into three discrete pieces all handled by separate subystems. All data required for each is stored in a static, contiguous region of memory as an array. For the software-based approach, we loop through these arrays and perform each operation on them (collision detection, integration, resolution). For the OpenCL-based approach, each operation will be a "Kernel" with dozens of instances executing in parallel on each shader processor of the GPU. For example, there may be 50 kernels executing on the GPU, all testing for collision independently in parallel between different sets of rigid bodies in the scene.
[b]Collidables and Collision Detection[/b]
The first type of entity supported is the Collidable, and the first task in the pipeline is collision detection. Currently, the engine only supports quads (that makes it easier for me to implement for a grade, I can get risky/creative after I graduate). Collision detection is implemented with an optimized separating axis theorem algorithm that can be expanded upon to work for any convex polygon. When a collision is detected, depending on the type of collision (rigid body, terrain, particle, etc), the collision detector creates a contact for the bodies. Bodies that aren't rigid (such as particles) don't require certain data such as the point of contact, so that is skipped.
[b]Particles and Mass Aggregate Physics[/b]
Currently, I have completed mass aggregate-based physics. This is basically a full physics engine MINUS rotational components of objects (moment of inertia, rotational velocity, torque, point of contact). It fully supports and resolves collisions between two oriented rectangles with varying mass, coefficients of restitution, and force applications.
[b]Force Application[/b]
LibKineticGyro supports arbitrary force application by registering "force applicator" function pointers where you can implement custom logic to apply forces to a list of bodies each frame. For example, I'm able to register an "ApplyGravityForce()" function to the engine and simulate gravity each frame. Notice that the particles all fall.
[b]Interpenetration Resolution[/b]
The contact resolution process is two-fold. The first step is interpenetration resolution to separate two overlapping bodies. The second step is velocity resolution to adjust the resultant velocities of two bodies after a contact. Interpenetration resolution is best seen in action when a player collides with a wall (the wall has infinite mass, so it doesn't take any velocity from the player), and the player is pushed back out of the wall (so it looks like the wall stopped him). The second example is a player pushing objects around a puzzle. The player collides with the body, then the body is separated (based on its mass) and "pushed" away from the player.
The interpenetration algorithm is implemented by taking both the contact normal and penetration depth from the collision detector, then moving each body backwards along the normal in proportion to their masses.
void gyroContactResolveLinearInterpenetration(const GYuint32 index, gyroVector2 posDelta[]) { gyroContact *con = &_conPool[index]; float totalInverseMass, invMass1, invMass2; gyroVector2 totalDisplacement; char secondBody = !((con->_type == GYRO_CONTACT_COLLIDABLE_TERRAIN) || (con->_type == GYRO_CONTACT_PARTICLE_TERRAIN) || (con->_type == GYRO_CONTACT_RIGID_BODY_TERRAIN)); if(con->_depth <= 0) return; //UHM WHAT!? posDelta[0] = _colPool[con->_colIndex[0]].instMat.pos; if(secondBody) posDelta[1] = _colPool[con->_colIndex[1]].instMat.pos; totalInverseMass = invMass1 = _attribPool[_partPool[_colPool[con->_colIndex[0]].partIndex]._attribIndex]._inverseMass; if(secondBody) totalInverseMass += _attribPool[_partPool[_colPool[con->_colIndex[1]].partIndex]._attribIndex]._inverseMass; if(totalInverseMass <= 0) return; //gyroVector2AddScaled(&totalDisplacement, &con->_normal, (-con->_depth / totalInverseMass)); totalDisplacement.x = con->_normal.x * (-con->_depth / totalInverseMass); totalDisplacement.y = con->_normal.y * (-con->_depth / totalInverseMass); gyroVector2AddScaled(&_colPool[con->_colIndex[0]].instMat.pos, &totalDisplacement, -invMass1); gyroVector2Sub(&posDelta[0], &_colPool[con->_colIndex[0]].instMat.pos, &posDelta[0]); if(!secondBody) return; printf("ABOUT TO APPLICATE 2...nt1 - %ft2 - %fn", invMass1, totalInverseMass); gyroVector2AddScaled(&_colPool[con->_colIndex[1]].instMat.pos, &totalDisplacement, _attribPool[_partPool[_colPool[con->_colIndex[1]].partIndex]._attribIndex]._inverseMass); gyroVector2Sub(&posDelta[1], &_colPool[con->_colIndex[1]].instMat.pos, &posDelta[1]); }
[b]Velocity Resolution[/b]
Velocity resolution is implemented using a few things: 1) the rate at which the two objects are "separating" relative to the direction of the contact normal and 2) the coefficients of restitution for the two bodies (0 being a completely inelastic collision, where the two objects stick and move together, 1 being completely pong-style bouncy) and 3) the masses of each object. The "impulse" (instantaneous change in velocity) to be applied to each body is in the direction of the contact normal and in proportion to the two objects' speed and mass (in accordance with the law of conservation of momentum).
void gyroContactResolveLinearVelocity(const GYuint32 index, gyroVector2 velDelta[], const float deltaTime) { gyroContact *con = &_conPool[index]; float totalInverseMass; float newSepVelocity, deltaVelocity; gyroVector2 totalImpulse; float impulseMag; //Contact is either separating or stationary if(con->_separatingVelocity > 0) return; //maybe need an epsilaaaawn! totalInverseMass = _attribPool[_partPool[_colPool[con->_colIndex[0]].partIndex]._attribIndex]._inverseMass; totalInverseMass += _attribPool[_partPool[_colPool[con->_colIndex[1]].partIndex]._attribIndex]._inverseMass; if(totalInverseMass <= 0) return; velDelta[0] = _partPool[_colPool[_conPool[index]._colIndex[0]].partIndex]._velocity; velDelta[1] = _partPool[_colPool[_conPool[index]._colIndex[1]].partIndex]._velocity; newSepVelocity = -con->_separatingVelocity * con->_coeffOfRestitution; deltaVelocity = newSepVelocity - con->_separatingVelocity; impulseMag = deltaVelocity / totalInverseMass; totalImpulse.x = con->_normal.x * impulseMag; totalImpulse.y = con->_normal.y * impulseMag; gyroVector2AddScaled(&_partPool[_colPool[_conPool[index]._colIndex[0]].partIndex]._velocity, &totalImpulse, _attribPool[_partPool[_colPool[con->_colIndex[0]].partIndex]._attribIndex]._inverseMass); gyroVector2AddScaled(&_partPool[_colPool[_conPool[index]._colIndex[1]].partIndex]._velocity, &totalImpulse, -_attribPool[_partPool[_colPool[con->_colIndex[1]].partIndex]._attribIndex]._inverseMass); gyroVector2Sub(&velDelta[0], &_partPool[_colPool[_conPool[index]._colIndex[0]].partIndex]._velocity, &velDelta[0]); gyroVector2Sub(&velDelta[1], &_partPool[_colPool[_conPool[index]._colIndex[1]].partIndex]._velocity, &velDelta[1]); printf("TotalInvMass - %f, sepVel - %f, newSep - %f, deltaVel - %fn", totalInverseMass, con->_separatingVelocity, newSepVelocity, deltaVelocity); printf("impulseMag - %f, totalImp - <%f, %f>n", impulseMag, totalImpulse.x, totalImpulse.y); }
The code may look a little ugly with all of the arrays indexing into arrays indexing into arrays. I haven't done any caching optimization yet, and as I said, that's due to the SIMD structure. It also probably looks ugly, because it's straight C. The vector operations are all implemented in LibGyro2.0's math API.
[b]Integrating with ES[/b]
So how does this fit into the big picture? Very fucking nicely. Glad you asked. :)
To this day, the new engine still has never implemented any sort of entity versus terrain collision detection. This is for a few different reasons. 1) we had always planned on having some form of rigid body physics engine (which we now have), and 2) because the task of efficiently checking for collision between OBBs and any kind of tile was something we had a lot of trouble figuring out. Fortunately, I think we've come up with a really kickass algorithm (based on preexisting clipping algorithms that are used in graphics).
As soon as this engine is complete, I plan to be integrating it with the main engine. This will give us efficient collision detection between any kind of body, allow us to interact with obstacles and objects within a level, and allow us to finally collide with the environment. Marcel and I plan to be implementing some sort of "collision tool" in the toolkit that will allow level designers to lay vertices to define their own "collidable" regions when editing tiles and characters.
I'll be keeping you guys updated on this front. I'm hopefully going to be concluding at least the first phase of this engine in two weeks (and graduating). Looking forward to jumping immediately back into the Toolkit afterwards. Back the fuck to work on rotations for me!
