I've been working on a physics component (for and with ObjAsm32/DX9) for some time now.
Its a 3D multibody simulator which so far supports springs, gravity and the usual stuff.
The integrator is currently just a Euler integrator, being driven in fixed timesteps of 0.100 seconds and synchronized to realtime via a 'time accumulator'... the only way that the integrator differs from the gamut of other simulators is the way it behaves when a collision is detected - the simulation is wound forward to the exact moment of collision, and the unused portion of the frametime is returned to the Time Accumulator pending the next update.
In terms of geometry, supported so far are only Spheres and Oriented Boxes, however complex meshes can be driven via the transform of a rigid body.
So.. we can take any old mesh object, and wrap it in a box, or a sphere.

The collision hulls are (barely) hierarchical in nature... all Boxes naturally have a Sphere, and so collision detection begins with spheres, regardless of the actual geometry of the bodies.
I have mentioned in another post why I like sphere tests, but I'll briefly say it again: sphere tests are slightly modified point tests, and theyre very cheap... to determine if two 3D spheres are intersecting at a given instant in time, we measure the distance between their origins, if that distance is less than the sum of the sphere radii, then theyre intersecting.

Collision tests generally fall into two categories, sometimes called 'macro and micro', or 'coarse and fine', or 'swept and instantaneous'.
Instantaneous tests are cheaper, but theres a drawback, particularly noticeable when bodies have high velocity (ie are moving quickly)... since their position is updated by relatively large amounts each frame, theres a chance of us 'missing' collisions (our collision detector simply does not see them occur) and so fast-moving objects can go right through walls, and each other, which obviously isn't correct.
The solution to this problem is to use a Swept test.
Swept tests are able to check for intersection of the bodies all the way along their respective paths of travel, they can tell us not only if there will be a collision, but when and where it will occur.
By predicting collisions slightly into the future in this way, the problem of high velocity collision detection is solved, at least for spheres.
But in my current demo, my objects are not spheres, they are boxes, and they are able to rotate freely.

Since thats true, we know that when the Spheres around our boxes first touch, then the Boxes are certainly NOT Penetrating - theyre probably Clear of one another, and theres a small chance they are Colliding (touching at the corners).
My sphere-sweep test returns TWO collision times : the time when the spheres would begin to touch, and the time when the spheres would begin to separate (had they passed through one another).
I know that my 'actual' collision time, no matter what geometry my bodies are, is somewhere between these two times.
Now I have narrowed down the actual collision time to quite a small window of time and I still haven't bothered to look at what actual geometry they use :)
At this point I begin to do that, I have case-code for the 'actual' geometry type of my bodies.
So, I have a method which, given the start and end of the search window, will find the exact moment of collision of the two bodies with specific geometry, and return that time.
This method uses a binary search which involves integrating the two offending bodies to various test times while shrinking the search window.
Note that the search is restricted to manipulation of two of N bodies, THIS is different to many other simulators and offers a big speedup.
Anyway, having found and returned the exact time the boxes will collide in the current frame, the entire simulation is wound forward to that time, and the collision between those two bodies is resolved, leaving the system in a fit state to continue integrating happily forwards.

So - we have the Sweep phase, where we sweep-test the boundingspheres of all unique pairings of rigid bodies, whose job is to tell us the earliest collision of two bodies.
Then we have the binary search for exact collision of two moving and rotating bodies of arbitrary geometry.
Then we glitch the system forwards to the collision time, ready to resolve the collision.

The collision resolving scheme is able to handle multiple simultaneous point collisions between two bodies, which it currently does by calculating the due impulse for each point collision, calculating the change in velocity (linear and angular) due to each impulse, summing these deltas, and then applying the averages of those sums to the bodies.
I'm not at all sure that efficient or even correct but the results are plausible, and look far more correct than simulators which just solve the first collision they see and move on... when you drop a box flat onto a plane, it should bounce straight up with no rotation, but in those simulators, the box will bounce away at an angle, and with some spin.

Well, that pretty much covers the mysterious inner workings of my simulator, I'd love to hear your comments and suggestions.

Why am I doing this? Why not just use an existing engine?
This is a wide open field and still the subject of much active research, and well, lets face it, playing with 3D physics stuff is FUN :D
I believe that most physics engines trot out the same algorithms in the same order and produce code that benchmarks similarly as a result... I don't think it would take much of a leap in paradigm to put most of them to shame.
The number one reason that some of these products receive commercial attention at all is simply because they are proven in the marketplace, and the cost of a license is a small fraction of the cost of developing an in-house solution.
Since I am not constrained by the leather straps of commercial reality (I don't stand to make a single cent of profit), I'm able to develop projects like this at my leisure, and without being forced to make compromises in order to meet some unrealistic deadline.

If you'd like to help develop this code (with the understanding that it will become a part of the OA32 library, and essentially open-sourced) I'd also love to hear from you.
Posted on 2008-05-12 04:56:22 by Homer
I've just added a new test to the collision detection scheme...
At the start of the Sphere/Sphere sweep test, I now calculate the Closing Velocity between the two spheres (not to be confused with the Relative Velocity, which is a vector).
The sign of the Closing Velocity tells me whether the Spheres are approaching or separating.
If they're separating, I let them continue without further checking, EVEN IF THE BODIES ARE CURRENTLY PENETRATING.
If they're moving apart, and they're penetrating, letting them go will only improve the situation, without the need to apply any heavy-handed "penetration correction' impulses (something I've tried to avoid).
But more importantly, if they're moving apart, and they're clear, we know that collision is not possible, so we can exit the sweep test for this pair of bodies early.
So, we don't even need to perform the Sphere Sweep itself unless we know the Spheres are generally moving toward one another !!!
In hindsight, it is obvious that this test should be the first test we perform, I'm just sorry it took me so long to realize it, and I'm suprised that it is not mentioned more frequently in general literature, but I guess that this is just an example of what I'm talking about - the algorithms are out there, they just need to be strung together in optimal order.

Posted on 2008-05-12 09:29:51 by Homer
Errata: I stated that my Sphere Sweep test returned two Time values: the time that the spheres first touched, and the time that they first separated. Then I said I searched between these times for the moment of collision.
This is not quite accurate.

As stated, my search for the perfect collision time takes two input times, however it returns two output times, since we cannot be assured of finding a 'perfect time' due to numerical accuracy.
The two time values returned represent the most advanced time that the Bodies were still found to be Clear, and the least advanced time that  the Bodies were found to still be Penetrating.
The maximum difference between these two times is an Epsilon value of 0.0001 seconds, and the 'perfect' time is somewhere between the two returned values.

I am currently winding the simulation to the lower of the two returned values, where the Bodies are expected to be in a legal and Clear configuration, because I know that if I was to advance all the way to the higher returned time I would have Penetration to deal with.
Now I find the closest Plane on body A to body B, and then test the points of body B against it, noting which points crossed the test plane. This planar test has an error threshold, which allows points just slightly outside the plane to count as being coplanar...
The points found to be coplanar are treated to a final test to determine whether they are indeed within the volume of the test box...
Points that are Clear are ignored.
Points that are Penetrating cause an int3, this is quite alarming, this state should not be possible, since we integrated the system to the LAST DISCOVERED 'CLEAR' TIME !!!!
Points that are Colliding (coplanar) within the threshold are sent to the collision resolver.
Having tested all the points of body B against body A, I perform the entire test again with the Bodies switched about, testing body A's points against body B's closest plane.
This sounds exhaustive, and it is, but it ensures that all of the correct points (and none of the wrong ones) will end up producing a collision response...They call all these point collisions 'microcollisions'.
Having all these little impulses acting at once gives us much more realistic behaviour during collisions, at the cost of a little extra processing.
I intend to fake the physics for a lot of non-critical stuff in my game engine, and I don't plan on simulating zillions of objects with a single simulator, so I think can afford to have the extra accuracy.
In regards to large numbers of bodies, I intend to associate an instance of my simulator with each partioned chunk of my game world, connected via portals.
The mini-simulators will be able to pass objects between them via the portals.
In this way, spatial partitioning is applied to the simulator.
Individual simulator instances can be put to sleep when inactive.
As long as we don't have too many bodies in one partition of our worldspace, we have avoided the problem of the cost of the sweep growing exponentially with respect to the number of bodies being simulated in the entire game.. that is to say, we can afford to correctly simulate bodies that are not necessarily near the player, and do it in realtime, whereas we might be tempted to cull the simulation by visibility otherwise in order to meet our framerate quota.

Posted on 2008-05-12 11:38:49 by Homer
I couldn't sleep last night, thoughts kept running through my mind.
One of them was in regards to my 'search for perfect collision time'.
It occurred to me that although my current code guarantees that I find the upper and lower bounds of the collision time accurate to one ten thousandth of a second (0.0001), since I have not (and indeed cannot) calculate the EXACT time (due to numerical precision), I can not calculate the EXACT point(s) of collision on both bodies !!!
The reason for this is Velocity.
When the velocity is small, the change in position per frame (displacement) is also small.
At high velocity, even a very small amount of time can produce a large displacement.
I am currently between zero and one ten thousandth of a second away from the EXACT collision time, so my two bodies are displaced by one ten thousandth of their total change in velocity for this frame.

I said I can't predict the exact time of collision, because of numerical precision.
But the collision time is not what we REALLY want, is it?
WHY are we obtaining the collision time?
We want it so we can place our objects at the time of collision, so then we can find our microcollisions, right?

Well, even if we can't find the exact collision time, can we find the exact positions of the bodies at the moment of collision ?

Lets think about this: right now, we're about to put the bodies at two specific locations , at a time just before collision occurred.
Also, we've already missed an opportunity to note which point(s) penetrate, since we've been staring at these points over a number of integration positions during our Search.
Finally, we know the velocities of the bodies... we even know how much it changed (acceleration) during the frame.
If we treat the Velocities to a binary division, we can estimate exact collisions to several more orders of accuracy than we currently can...
Hey, this is a stream of consciousness here, but here's an idea... if we were to double the velocity, and half the time, we would get to the same position, yes?
Lets half our velocity, and double the size of our remaining search window, until we run low on velocity.
Now that we have rescued our search window size from the clutches of numerical oblivion and also gotten rid of that nasty Velocity, we can consume the remaining search window size by running through a few bonus iterations of our Search.
Of course, we're going to have to preserve the Source states of our pair of bodies during this second round of Search iterations, because we're only doing it to more accurately estimate the exact configurations of the bodies at the exact collision time.
We can pilfer the configurations for the positions of the offending Points and restore the Source configs of the pair of bodies before leaving the Search method.
Perhaps the 'search' method could be able to handle resolving of collisions and never need to return a result , making the second round of collision testing unnecessary...
Anyway, once we return, the simulation will be wound to the slightly-incorrect pre-collision time, so we shouldn't resolve the collisions until we return.
We're now resolving the collisions at the exact collision points, but possibly a fragment of a second earlier than we should have.
For me, this is preferable to processing collisions that haven't happened yet, and in the wrong place. The reason is this: each of our point-collisions is actually two points coming together at the collision moment - theres a place on EACH body that is meeting at a collision point, and at the moment of impact, these points coincide.
I wish to observe this constraint, I wish that the worldspace collision point, the collision point on body A, and the collision point on body B all coincide when I resolve the collision.
I would rather hand my collision resolver accurate positions, and suffer a tiny time-glitch (for those two bodies only) than be perfectly timely and perfectly wrong.

I guess this post isnt very well thought out at all, its just junk on my brain really.
Anyone out there got any ideas?
I don't care if they're crappy, I'd still love to hear them.

Posted on 2008-05-13 00:09:25 by Homer
I have two tiny ideas, that might help in optimization:
1) before doing expensive swept-sphere tests, simply do an instantenous sphere-sphere hittest, but each object's sphere radius is increased by the length of its velocity-vector.
2) find collision-times by using the approach ADCs ICs use (by bit-toggling, comparison). So, 32-bit a FP value will take no more than 32 steps to be found. This needs the comparison/test to be made into a linear function/thing, though.

Also, after the broad-phase, we have the count of objects/tests we'll have to do in the narrow-phase. If that count is too high, maybe it'll be a good thing to use simpler/faster algorithms for the narrow-phase.
Posted on 2008-05-13 12:09:34 by Ultrano
Heya Ultrano :)
Thanks for replying, I'm happy to see you're taking an interest.
I presume that the only reason that this thread has received over 100 views on its first day is that there's simply nothing else going on around here lately... I further presume that everyone is just busy like me, and not ready to announce their work... anyway, here's my two cents worth:

#1 - The swept sphere test is not expensive (well, its relatively cheap, its a modified version of the instantaneous sphere test), and indeed it incorporates a test for instantaneous intersection at the start of the frame, and incorporates the velocities to test for collision all the way along the travel paths, which is what you're trying to achieve by expanding the spheres via their velocities - its just tonnes more accurate than testing with expanded spheres, and can tell me not just IF, but WHERE and WHEN.
But to be completely fair, I had exactly the same idea as you before I found this algo.

This link leads to a page that explains the sphere-sphere sweep algorithm in detail:

#2 - The problem with the approach that ADCs use is the same problem I have : they are not numerically accurate, they are STEPPED (insert fond memories of building R2R ladders using discrete components HERE). My problem is not finding the collision time - the search I've implemented is actually a kind of binary search, and very fast and efficient, given that it handles rotating bodies of arbitrary geometry.
No, the problem is that I run out of numerical precision.
I can, as stated, find the collision moment accurate to 0.0001 seconds and I can do that in about 12 iterations of my search algo, no matter what geometry the bodies are, no matter what speed they are moving AND ROTATING at , in 3D space.
But this still leaves me with a potential error of between 0 and 0.0001 seconds.
If we then take into account the Closing Velocity of the two bodies, and multiply that by our presumed collision time, the Bodies will be very close to being in the correct positions for collision, but they wont be EXACTLY in position.
Observe that the point of collision on each body coincide in worldspace at the time the collision occurs - if we have not positioned our bodies correctly, those points will not coincide... and if they dont coincide, then we cannot accurately resolve the collision, we'll be handing the collision resolver bodyspace locations which are slightly wrong.
I'd rather produce nice collision responses and have two offending bodies glitch slightly in Time than have all my bodies perfectly time-synchronized but producing incorrect collision responses.
So the problem I am really trying to solve is NOT  "find the exact collision time" (because theres no such thing as exact due to numerical precision), the REAL problem I wish to solve is "find the configurations of the offending bodies at the collision time".
Since this involves multiplying the Velocity by the collision time to find the displacement of each body, any error in the calculated time is multiplied too, producing positional error.
Perhaps I should simply turn my attention to this positional error, possibly applying it as a threshold during fine collision testing.

#3 - my broad-phase detector (the n-body swept sphere test) returns information about the pair of bodies whose spheres will collide FIRST in the current frame : which pair of bodies, and when.
My narrow-phase detector is handed this information, which it then uses to search for the exact collision time and the set of simultaneous collision points involved.
So my narrow-phase stuff is all just working with one pair of bodies, and the binary timesearch algo is amongst that code, so I am only performing test integrations with one pair of bodies, independent to the rest of the simulation.
The entire simulation is wound to the collision time, the set of collisions is resolved for the offending bodypair, and the entire simulator is now in a fit state, but it has not reached the end of the timestep, so we return the unused time to the simulator's 'time accumulator', where it will be spent in the next timestep.
Excluding the binary timesearch, the cost of narrow-phase testing is thus linear for a given pair of geometries.
The most complex pair of geometries I currently handle is Box/Box.
I consider a Box as a cloud of points and planes, so the code can be adapted for arbitrary hulls, but I really don't see any value in simulating complex meshes - collision testing against them perhaps, but we'd associate a proxy hull with a mesh to accelerate its physics.
That's what I'm currently doing.
In my current democode, for testing purposes, I have m$'s tiger.x mesh surrounded by a box surrounded by a sphere, and I make two instances, and bash them into each other.
The BOX is the physical proxy, but Boxes always have a Sphere in my system.
When I want to draw a tiger, I use the translation and rotation of its proxy hull.
So anyway, its the BOX that is the thing that has Mass and Velocity and such, the Tiger is just sharing its transform.
Posted on 2008-05-14 01:36:04 by Homer
Now that I've talked about my current code and current ideas and such, perhaps it would be good to look closely at the way I'm resolving collisions.

We have a pair of bodies which are positioned at the moment of impact, and which are hell-bent on penetrating each other unless we do something about it.
We're sure that they are touching in one or more places (not penetrating yet).
Each place where they touch is a COLLISION.
It might be just one place, or it might be a few places.
My system will detect them all, solving each separately, then applying an averaged response.
But I'm jumping the gun.
Let's look at the example of two Boxes...

I've said before that I consider a Box to be a cloud of Points and Planes.
In fact, my Boxes contain an array of eight Points, and six Planes, describing the Box with no rotation and positioned at world zero... ie, this is a BodySpace declaration of the geometry.
I never screw with the data in these arrays, they are kept intact at all times.
Whenever I integrate a Body into a new configuration (adjust its physics variables), I transform the array of BodySpace points into WorldSpace, giving me an oriented and positioned set of eight vertices in worldspace coords. And when I wish to perform collision testing, I transform those worldspace vertices into the BodySpace of my test body, so I am able to test the points against the UNROTATED PLANES on my test body.
Thus, my narrow-phase collision detection tests are usually performed in the Space of some specific body.
So... at the cost of one extra transform per point, I'm able to perform reasonably cheap tests and avoid transforming some other dynamic data (the planes in this example).
For the record, my demo code does not actually use the planes at all, they are redundant, but it still performs point tests in body space.
Anyway, back on track, we're able to identify WHICH POINTS ARE TOUCHING.
Let's now treat ONE of these collisions, and check out how I resolved it...

When a Collision occurs in my system, its always due to an aggressor Point of body A colliding with one of the faces of body B (noting that faces are always planar - theyre flat).
Some physics engines solve collisions in 'collision space'.
This is not desirable, it requires extra transformations for no good reason.
I solve my collisions in WorldSpace, relative to the point of impact.
I calculate an Impulse due to the collision, and then I apply that Impulse at the point of collision to both bodies, scaled by their mass-relationship.
The application of this impulse will produce a change in linear velocity, and usually, also a change in angular velocity.
I note these delta values per body, but I don't apply them... there might be several simultaneous collision points, I loop through all of them, summing the deltas, not applying them.
Now that I've run out of test points, I average the sum of the delta values, and apply the average.
This probably sounds a little expensive, and might seem like I'm applying the average of the impulses to the bodies, but in fact, I am applying the average of the EFFECT of the impulses on each body.
The result of doing this is that we get more realistic behaviour from the simulator.
For example, if we drop a box flat onto a flat plane such that two flat planes meet and we have four collision points, the box should bounce back up without any spin - it should not rotate.
If we resolve the four collisions as suggested, each will produce a rotation, but they will cancel out, and give us the correct result !!! More samples equals more quality, so long as we're dealing with reasonable numbers of points... This system might sound rather naiive, however consider that it naiively is solving point/face, point/edge, edge/face, edge/edge and face/face collisions, all within the same optimized loop and without apparent effort or extra cost.

Would you do it this way?
What would you do differently?

Posted on 2008-05-15 01:46:39 by Homer
I've added some code to allow individual bodies to be put to sleep...
If a body is not moving and/or rotating, we don't need to Integrate it, and it can never act as an Aggressor or 'cause' any collisions... so when a body's energy becomes very low, I'll make it go to sleep.
The body is woken once more if it is involved in a collision.
Later I intend to extend this theme to allow me to put the entire simulator to sleep - because I intend to create several instances of the simulator at once, each representing a region of space, each looking after a chunk of my world.
Anyway, as usual, the cheapest operation we can perform is the one we DONT perform, so this represents a nice speedup, especially as the number of bodies increases.

Oops.. Sleeping bodies are not affected by Gravity :D I'll have to be more careful about putting Bodies to sleep !!!
I guess my next move will be to go back to testing with a single body and some fixed world bounding planes and start to implement 'resting contact'.

Posted on 2008-05-15 21:44:17 by Homer
Basically, I need to devise some categories for general collisions.
The 'normal' sort of collision, we'll call a Collision (no confusion here).
But theres at least two more kinds of collision, and they are due to friction.
'Rolling Friction' can cause 'Rolling Contact'.
And 'Static Friction' can cause 'Static Contact.
Only the last kind can put a Body to sleep.
At the moment, friction is implemented as simply a Dampening scalar.
This is not enough.
We need to model friction better than this, so we can create rolling and sliding behaviours, particularly for round shapes but also generally. We actually don't need to describe two new kinds of contact, what we need is to handle friction properly when resolving collisions.
And we still need to recognize when a Body is effectively at equilibrium (low energy) so we can put it to sleep, but we should be looking at the current Forces due to internal and external energies rather than velocities and such, so that gravity and static contact is taken into account automatically.

Posted on 2008-05-18 06:02:41 by Homer
I've half-corrected the problem of Sleeping bodies not being affected by Gravity - it was how I was deciding that a body has 'low energy' - I was checking velocities, when I should have been checking the FORCES (linear and angular).
My 'ComputeForces' method is responsible for calculating the INTERNAL force and torque which are due to velocity (linear and angular), and also account for any EXTERNAL forces due to Gravity, Springs, Rockets, Punches, Grenades, or whatever.
I should check for low energy after a collision is resolved.
This would allow bodies to fall (or be pulled by springs) into a colliding, AND low-energy state.

I'm pretty much completely dissatisfied with my existing collision processing.
By the time the earliest set of collisions in the current timeframe between two bodies is detected and resolved, the detection loop has terminated.
What if a body is involved in collisions with multiple bodies, and its simultaneous?
My existing code will detect the second collision, but by then, the first collision has been resolved, and the velocities have changed, so the second collision will be resolved incorrectly, and the overall simulation will be wrong.
Also, since my existing code begins the detection loop from the start, it will probably loop uselessly through a bunch of non-colliding bodies before it finds something to chew on, when it should have picked up where it left off at the most recent offending pair.
To fix that, the counters for that loop should be stored as class variables of the simulator instance, rather than as stack locals of some specific procedure.

Posted on 2008-05-19 20:31:48 by Homer
As I said, I'm not a happy camper, my so-called microcollision engine is not able to handle multiple bodies colliding at once? I'm making some big changes, pushing much of the collision detection code further back into the engine, and out of the Simulate method.
I'll be doing something like this:
Make a list of potential collisions, and as I do so, toss out any 'older' ones, leaving a list of potential collisions at time X.
Now advance the simulation to time X and process all of those collisions.
Now we can return to the Simulate method, and toggle the simulator's 'configuration index'.

I like this solution, my code is object oriented, so pushing code deeper into the engine is actually desirable as it more cleanly partitions the engine's functionality - at the cost of a few cycles of call overhead, we eliminate a lot of repetition of binary code snippets, and our sourcecode looks more tidy as a bonus.
The solution only requires that one big chunk of Simulate() is moved into CheckCollisions(), there's no need to add anything, or track those counters as I suggested previously.

Posted on 2008-05-19 23:20:34 by Homer
Hey Homer!

I'm an undergraduate student n am mid way through my course. I'm completely new to assembly programming as i've mentioned in the post you replied to. Though i came here looking to dig into assembly programming to expand my horizons my true interests lie in 3D n Physics engine development. But in reality i've never actually initiated work in that field. I'm a bit lazy i admit but never the less i have a good understanding of physics and i've always wondered how they are implemented in an engine. Reading your posts has helped me fill this gap to some extent and i'm more than excited to aid you in this in anyway i can. :D
    As far as my opinion on your methods goes, i like your sphere sweep, and your collision resolving algos though i feel your hesitation to "put objects to sleep" is not justified. See you can comfortably put an object to sleep(ofcourse when its in a state of low energy) until you find out in the instance of the sweep of the aggressor the "sleeping" object in question is about to participate in the oncoming collision(this is the time you wake it up). Until then the forces acting on this object (gravity,friction..) produce no visible effects though they are constantly acting on it.
Posted on 2008-05-20 06:59:52 by SNce
I'll begin to post my sourcecode soon, but right now I'm making fast and furious changes to it, so I'll wait until I'm a little more ok with it, and save everyone reading this a lot of pain.

The collision detection has changed a lot, for example.
I'm now collecting a list of 'potential collisions' in a loop that relies on Sphere/Sphere and Sphere/Plane sweep tests, as well as determining the earliest collision time X.
This gives me a short list of body pairs whose spheres all collide with something at time X.
Now thats in place, I need to perform fine collision checking on that list, which is where I'm at right now. I had avoided using any kind of lists previously, but thats the only way I can see of dealing with arbitrary multiple simultaneous collisions and yielding accurate results.

In some ways the algo I'm using hasn't changed a lot - but the code implementation has changed considerably, and for the better. What I have set in place now more closely resembles a series of filters which becomes more and more fine.
It's a multi-pass culling scheme, nothing more, nothing less.
And that's exactly what I think will give me the best results, and where I think I should be going with this.... for large numbers of bodies, other authors will suggest using some kind of 'bounding volume tree' which must be maintained as bodies move about... I think partitioning the simulator is a better solution since I don't expect huge numbers of bodies in one place.

Posted on 2008-05-20 09:42:53 by Homer
I'm reasonably happy with the changes I've made to the collision detection.
It involved a complete rewrite of the main loop, which I'll describe in pseudocode below.
The coarse and fine tests are both incorporated in the main loop, so only one pass is needed.
The collision time found by this loop is the time that the arbitrary geometries collide, NOT the time when their bounding spheres do, ie, the result is FINE.

0. Create a temporary collection to hold collision data
1. For X = 0 to #Bodies
2. BodyA = Bodies
3. Perform sweep test of A's sphere against the set of World Bounding Planes
Will the sphere will touch a plane during the current frame?
4. NO - goto 9
5. YES - Perform Binary Search for exact collision of geometry of A with a specific Plane
Is this the earliest 'exact' collision time we've found?
6. MORE - goto 9
7. LESS - Note the time, flush the temp collection, and goto 8
8. SAME - Shove the Body and Plane into our temp collection
8. For Y = X+1 to #Bodies
9. BodyB = Bodies
10. Perform sweep test of A's sphere against B's sphere
Will the spheres collide during the current frame?
11. NO - goto 16
12. YES - Perform Binary Search for exact collision of geometry of A with B
Is this the earliest 'exact' collision time we've found?
13. MORE - goto 16
14. LESS - Note the time, flush the temp collection, and goto 15
15. SAME - Shove the two Bodies into our temp collection
16. Next Y
17. Next X

At this point, we have found the exact time that the earliest collision occurs, and we've made a list of all the pairs of bodies which collide at that time (since there may be more than two bodies all simultaneously colliding, such as in a game of pool).
Now we rattle through that list, and resolve the collision for each pair of bodies.
I'll show you the pseudocode for that in my next post, I'd like to hear your comments regarding the above pseudocode before I continue.

Posted on 2008-05-22 01:46:11 by Homer
Nothing to say? Either I'm doing a great job with this thread, or a lousy one :)

Today I'm going to talk about how I resolve collisions.
In my simulator, I currently treat two kinds of collision, but the solution is really the same as you'll see.
The first kind of collision is where a Point on the boundary of Body A has collided with one of the Faces of Body B.
The second kind is where a Point on the boundary of Body A has collided with a World Bounding Plane.

In order to resolve a collision, we will be calculating an IMPULSE.
And in order to do that, we need a Collision Normal, and a Collision Point.
For the second type of collision, the Normal is simply that of the Plane.
But for the first type, the collision normal must be calculated from the state of the two bodies.
So I'm going to pretend we have a Normal and a Point, and forget about what Kind of collision it is - the goal is to get our hands on an Impulse.

Impulses are a lot like forces, except that forces change momentum gradually over time, whereas impulses act 'instantly' - we can say that impulse = the time-integral of force.
Impulses are related to force in that they cause a change in momentum, but time is not part of the equation.

We can calculate the world-relative velocity as experienced at the collision point.
This is partly based on the linear velocity of the Body's center of mass, and partly on the angular velocity of the Body. We want the post-collision velocity of the POINT to be the negative of the that velocity..
When the collision occurs, the Body will impart force against the collision surface.... it will hit it hard because it has some mass.
The collision response involves how much energy is returned to the Body after the collision.
This energy is our Impulse, and its direction is related to the Closing velocity and the Collision Normal.... if we ignore anything you may know that I am YET to mention about interaction of bodies during collisions, we can think of the impulse as being a slapping, instantaneous kind of force that is equal and opposite to the slapping, instantaneous force of the collision itself.
The minimum stuff we need is the collision surface's normal, and the closing velocity at the Point.
We calculate the force of the collision at the collisionpoint, reverse its sign, and we have our impulse.
Now guess where we have to apply our impulse?
Yes, the impulse needs to be applied at the collisionpoint.
Now we're sick of working with respect to the collisionpoint, we want to relate this stuff back to our Body...Usually, we're applying this force off-center with respect to the Body, which means that we'll get some 'spin' as well as simply linear movement... it will want to rotate.
We calculate the force and torque that this applied force caused to our Body's center of mass.
This is our collision response force and torque, as applied at the center of mass.
This pair of values is only valid for one Body.
If theres another Body involved in the collision, we need to flip the sign of our impulse, and apply it to the other body, repeating much (but not all) of the above process.
Thats what I meant when I said the solution is the same... for two bodies, we just flip the direction of our impulse and apply it to the second body, easy.
Remember, equal and opposite.
In fact for two bodies its 'slightly' more complex, because the mass ratio of the bodies should be taken into account, weighting the response energy for each body by the other body's mass.
This will make a heavy body impart much force on a small body and vice versa, which is physically correct.

Now, what we do with the collision response force and torque is up for debate...
How, and when, do we apply the response?
Bear in mind that we probably have several points colliding at once, and we don't want to apply ALL of the response energy to each point, or we'll get too much impulse overall.
I currently count the point-collisions per body and then wait until the next timestep to apply the response (from the previous timestep) in ComputeForces where the response is simply added to the 'internal' force and torque values.

There is one final complication to consider.
The Bodies are (probably) not EXACTLY positioned correctly for collision resolution.
There is a small error tolerance in the positive (separation) direction.
This small error will result in a discrepancy in the impulse that we calculate.
The solution is to rely on the (negative of the) pre-collision velocity of the Point - we want to scale the post-collision stuff to equal that, so we just need to figure out a scaling value that will get us from the (value) we have to the (value) we want it to be after the collision.
This ensures that our Bodies end up with the correct velocity, and bounce off happily into the wild blue yonder.
I am yet to actually implement the solution of 'the final complication'..

So how am I doing? You guys actually getting anything out of my rant?
Wanna see more math? Got questions? etc
Posted on 2008-05-23 04:02:05 by Homer
I've implemented that final bit of code to Scale the impulse magnitude.
I take the impulse and calculate the change to linear velocity due to that impulse.
Then I divide that change in velocity by abs(ClosingVelocity) since thats the velocity that I actually wanted to see. This gives me a scaling value, which I then apply to the Impulse.
Finally, I once more calculate the change to linear velocity due to the impulse, and this time I also do that for angular momentum as well, since now I'm working with the correct magnitude of force.
Doing this makes sure that our post-collision states are correct, even if we provide slightly incorrect collision data.... if we don't do it, we'll gain or lose energy each time we collide, completely unrealistic and unwanted behavior.

I'm no longer simply calculating delta values to add to the simulator, I'm now calculating the PRECISE post-collision values, and directly replacing the state values.
OK not directly, since I still accumulate and average, but now I'm accumulating and averaging Final State Values, not Delta values.
I know what output state I want for linear velocity, which allows me to forcefully scale the output to eliminate all sources of error.... or does it? :P
Oh, and in regards to my Averaging of the Point responses per Body, I've found one paper which does use this approach, so I feel a little vindicated, since this was something I thought of all by myself :)

In my current demo I am dropping a box with no rotation, and letting it fall under gravity "and no other forces" until it slams into the floor plane, where I detect four point-collisions.
Here's some debug spew showing the results of one Point/Plane collision, which clearly show that this is required, and that this solution works. Note that these are 3D (x,y,z) vectors:

edx -> [ 0.000000000000E+0000, -4.467054748535E+0001,  0.000000000000E+0000], Velocity at CollisionPoint
edx -> [ 0.000000000000E+0000,  2.634777526855E+0002,  0.000000000000E+0000], COLLISION IMPULSE
edx -> [ 0.000000000000E+0000,  5.105207824707E+0001,  0.000000000000E+0000], DeltaVelocity
edx -> [ 0.000000000000E+0000,  2.305429229736E+0002,  0.000000000000E+0000], RESCALED COLLISION IMPULSE
edx -> [ 0.000000000000E+0000,  4.467054748535E+0001,  0.000000000000E+0000], RESCALED DeltaVelocity

There's one special case in the collision detection that I am yet to completely handle, but otherwise I am seeing STABLE RESULTS !!!! :D :D :D :D :D
If I enable Damping that is.. otherwise, I am getting just a smidge too much response energy...
Without Damping, I get a collision velocity of 4.46 on the first bounce, and 4.56 on the second bounce, and it will grow, we'll start bouncing off the roof, then directly between the roof and floor, eventually the simulator will explode.
With Damping, I get 4.41 and 4.409, and it seems to be almost perfectly numerically stable, and repeatable, with the exception of that special case I mentioned.

The special case is where I detect that a Body's Sphere is penetrating a World Bounding Plane at the START of the TimeStep.
Its not necessarily a problem since the actual geometries may not be overlapping at that time.
Thats all I need to add and I think I'll be about ready to start posting code here and hopefully you guys can help test and harden and improve this thing further  8)

Posted on 2008-05-24 05:38:31 by Homer
This recent change to Scale collision response impulses has a problem.
It completely disregards our 'coefficient of restitution' (E).
We end up with a result that always has E=1.0, a "perfectly elastic collision".

What am I talking about?

The value E is used to describe how objects react when they collide - its a measure of how 'bouncy' they are. A value of 1.0 means it is 'perfectly bouncy', so that no energy is lost during the collision. Think of a rubber 'super-ball'. A value of 0.0 would indicate something like a lump of wet clay, it will not bounce at all, will it?

I shall now some pseudocode which sheds some light on the actual math being used to calculate the collision impulse for a point on a body and a fixed Plane. This is the original, without the rescaling stuff.
Lets take a look at it:

1. vR = vCollisionPoint - Body.CMPosition
2. vVelocity = Body.CMVelocity + CrossProduct(Body.AngularVelocity,vR)
3. fClosingVelocity = vVelocity Dot vCollisionNormal
4. IF fClosingVelocity is POSITIVE (bit 31 is clear) then RET
5. fImpulseNumerator = -(1 + Body.CoefficientOfRestitution) * fClosingVelocity
6. fImpulseDenominator = Body.OneOverMass + DotProduct(CrossProduct(Body.InverseWorldInertiaTensor * CrossProduct(vR,vCollisionNormal),vR),vCollisionNormal) 
7. vImpulse = (fImpulseNumerator/fImpulseDenominator) * vCollisionNormal
8. vDeltaVelocity = vImpulse * Body.OneOverMass
9. vDeltaAngMomentum = vImpulse

In order to fix the incorrect impulse, I added this:

9. fScalar = abs(fClosingVelocity) / SQRT(DotProduct(vDeltaVelocity,vDeltaVelocity))
10. vImpulse = vImpulse * fScalar
11. vDeltaVelocity = vImpulse * Body.OneOverMass (yes, AGAIN)
12. vDeltaAngMomentum = vImpulse

And the problem with THAT?
Now our delta velocity has been 'SHAPED' to be exactly what we wanted, right?
If E=1.0 then yeah its fine - but for any other value of E, we need a smaller output value.
So what I did to solve this is move E right out of the original equation until we've got our fScalar value:

5. fImpulseNumerator = -2 * fClosingVelocity
6. fImpulseDenominator = Body.OneOverMass + DotProduct(CrossProduct(Body.InverseWorldInertiaTensor * CrossProduct(vR,vCollisionNormal),vR),vCollisionNormal) 
7. vImpulse = (fImpulseNumerator/fImpulseDenominator) * vCollisionNormal
8. vDeltaVelocity = vImpulse * Body.OneOverMass
9. fScalar = abs(fClosingVelocity) / SQRT(DotProduct(vDeltaVelocity,vDeltaVelocity))
10. vImpulse = vImpulse * fScalar * Body.CoefficientOfRestitution
11. vDeltaVelocity = vImpulse * Body.OneOverMass (yes, AGAIN)
12. vDeltaAngMomentum = vImpulse


Oh yeah footnote : I tried getting rid of the SQRT in the above code, but doing so yielded too much error in the output.. collisions dont happen often in a simulation so I'll just wear it.
Posted on 2008-05-24 20:18:21 by Homer
I've added code to handle the special case of a sphere penetrating a world bounding plane at the START of the timestep.
I test for instantaneous intersection of the Body geometry and the plane.. if none is found, I handle it almost as usual - I hand execution to the binary search as usual, but I use a much-reduced search window since I know that the collision is near the start of the timestep, this eliminates a few iterations from the search.
But if I find that the geometry of the Body penetrates the plane at the start of the timestep, I have an int 3 breakpoint.

The int 3 is never being triggered - the simulation is stable and smooth until I get bored.

Also, I switched the Gravity axis to check all six of the world bounding planes are behaving themselves, and they are.

Happy days :)
Posted on 2008-05-24 22:21:11 by Homer
I found that my solution has problems when angular velocity is a large proportion of the closing velocity.... we get too much collision response energy, uh oh.

So I started examining some of the more high-tech solutions for resolving simultaneous multi-point collisions, including a scary thing called a Jacobian.
Amongst the various papers I read, one of them mentioned something that caught my eye.
It said "collision point or region".

Collision Region.
Perhaps I could use a single point to resolve a multi-point collision after all...
We can consider all the points involved in a collision between two Bodies as a single-point collision to be resolved, and for each such inter-body collision, directly add the resulting changes in velocities per body. Should work... agree, or not?

Posted on 2008-06-01 03:34:37 by Homer
Its time to talk about Friction.
Think you know what friction is? Try defining it :)

Actually, that's not a fair question because there are TWO kinds of friction.

Static friction acts on Bodies which are AT REST.
It can be defined as a force which resists motion tangent to a contact surface.
Think of a Body in resting contact with a flat floor plane. If you try to push the Body sideways, static friction will fight you... the more you push, the more static friction will push back, CANCELLING your efforts to get the Body moving. If you increase your efforts and push harder, at some point you will OVERCOME Static Friction, and the Body will begin to move.
Static friction does not affect a Moving body, so it will no longer play a part.

Dynamic Friction acts on Bodies which are MOVING.
It can ALSO be defined as a force which resists motion tangent to a contact surface.
The effect it has on the Body is to eat away at any momentum that is tangent (parallel to) the surface... it slows our Body down, taking away its energy and its velocity over time.
Eventually, it will cause our Body to come to Rest, and Static friction will become relevant once more.

We'll explore the implementation of a collision resolver which employs friction over the next few days. But before we do, lets talk about the properties of a physical Material.

In the Really Real World, everything is made up of some kind of material.
The tyres on your car are made of Rubber.
The car itself is made of Metal.
The tree we're about to hit is made of Wood.

When two Bodies collide and/or slide against one another, the friction between them depends very much apon the interaction of a pair of Materials.
Wet ice applied to wet ice will obviously have very low friction - and dry rubber against dry concrete will obviously have much higher friction - yes?

The problem is that different pairs of Materials will have very different friction coefficients.
Tables of friction coefficients CAN be found on the web... but will generally be INCOMPLETE and you will need to find the missing values by pure experimentation.

So we create a table containing friction coefficients for various pairs of materials... during collision resolving, we look up the appropriate cell in this table based on the material composition of the Bodies involved in the collision :)

Theres a lot more to this Friction stuff that I haven't mentioned, such as Rolling Friction...
Posted on 2008-06-02 22:17:23 by Homer