OK I'll rephrase the question.
Who has experience in using matrix operations to solve non-trivial simultaneous equations?
Posted on 2009-01-02 11:21:17 by Homer
Why not scaling the vectors according to the velocities they represent and then just add them all together?
Posted on 2009-01-02 14:14:36 by ti_mo_n
For multiple simultaneous contacts apon a single body, we can't simply add the vectors, or average them, or calculate them individually and add the resultant motions, or average them.
We can't do this because these events are codependant - they are not independant because although they are applied at different points, the application of these forces affects the other contacts through the center of mass via the inertia tensor.
We really need to solve this as a simultaneous equation, which can be expressed as matrix alegbra, although that is not absolutely necessary it is certainly computer-friendly and handles the general case well.

Sure there are some cases where we can apply an average impulse to a mean point of contact - we can do it if there is an edge / face collision involving only two bodies.
But if a body collides with more than one other body (say, it hits two walls in a corner), or if there are MORE than two points of contact (police car lands on its roof) then we can't cheat.

We need to find (for each simultaneous contact) a linear impulsive force which satisfies an entire set of constraints - those of the local collision event, and those of all the other simultaneous contacts.

Posted on 2009-01-02 19:44:41 by Homer

OK I'll rephrase the question.
Who has experience in using matrix operations to solve non-trivial simultaneous equations?

Are we supposed to use Gaussian elimination to solve such a problem? http://en.wikipedia.org/wiki/Gaussian_elimination I have C code for it...
Posted on 2009-01-02 23:29:04 by roticv
That will work for a collision with just two points of contact, since (without proof) we are working with matrices that ALWAYS have a clean inverse... however it won't work for three or more contacts.
Same for Jacobian rotation (another way to row-reduce a matrix).

Perhaps I'd be better off either describing the simultaneous equations I am talking about in matrix form so you can see the problems for yourself, and maybe posting some simple sketches that show why summed / averaged vectors don't provide an accurate solution.

Perhaps accuracy isn't even that important, since I am game-oriented in terms of my aspirations... perhaps I should just settle for 'visibly plausable' rather than 'physically accurate' - but if I do, I will never be able to create 'stacking' simulations - if I accept that I don't need stacking, I can forget this whole problem.... although stacking certainly seems like a reasonable expectation, even for lowly game simulation.

As things stand, I don't even distinguish between Resting and Colliding contacts - although I understand that this is the currently preferred model.

Posted on 2009-01-03 04:28:12 by Homer
OK - this post will make a few assumptions, and shed a little light on my current thoughts.
Let's assume that there are more than two contacts, and that those contacts are striking a body 'off-center'.

We need to think about the linear and angular characteristics of our body as being completely separated.

The impulses we will apply to the body are equal and opposide to the impact forces, which are linear.
These impulses are applied at / to the points of contact.

Linear impulses applied to an arbitrary contact point can be further split into their effects apon the center of mass (linear and angular).

Speaking of the linear, a linear force applied ANYWHERE on the body DIRECTLY affects the center of mass - we can say that ALL of the linear force is applied "linearly" at the center of mass - the whole body is affected linearly.

But a linear force applied OFF CENTER OF MASS causes angular effects.
It causes a TORQUE, which causes change in angular momentum, which causes change in angular velocity, which causes change in orientation.

We can and should treat the linear and angular components separately.

LINEAR: We can always use the AVERAGE of the input forces, since they are always all applied to the center of mass.

ANGULAR: We can always use the SUM of the input forces, since they always tend toward the Origin of the Body (else there is no collision) and thus at opposing extremes, cancel each other out.

I think this will create plausible results in all cases - not physically accurate, but visibly plausible.
I will attempt to sketch some examples to prove this before I code it.

If I am right, I am a very! happy man, because I outsmarted those nasty mathematicians using intuition alone.
Posted on 2009-01-03 06:14:21 by Homer
OK, here's some visual examples of some multipoint collisions. They're only 2D, and they're relatively simplistic examples, but I think they're useless nonetheless.

Example 1:
A box has fallen flat, and on to flat ground.
The red circles indicate two points of impact, and the red arrows indicate the impulses which result from the collision forces.
The green circle indicates the center of mass, and the green arrow indicates the total impulse applied to the center of mass. As we can see, it is an AVERAGE of the two input impulses... if we SUMMED them, the green arrow would be twice as long as the red ones, and we'd have too much collision response. It's pretty clear that there is NO ROTATION resulting from these two collisions - actually there is, but it cancels out perfectly... this proves that the impulse torques SHOULD BE SUMMED... why dont we average them too? lets see another example.

Example 2:
A box has fallen flat, and into a Valley (ie a  vee)
This time we have some (thin) purple arrows which show the (angular) Torque forces, which are applied on a radius from the center of mass (the radii are shown as thick purple lines).
Now we can see more clearly that these angular forces are cancelling out when we add them together.
But we still can't see why we can't average them.. so one more example.

Example 3:
The box is in 'mid air', not touching the ground.
We're applying two forces at two diagonally opposite corners, and in different directions.
The linear forces cancel each other out.
But the angular forces MUST BE SUMMED... if they were averaged, we'd have HALF the angular force that we would expect, it would be as if only one of the impacts occurred.
Intuition tells us that we should expect the box to rotate TWICE as much with both contacts affecting the box.
And it also tells us that we expect the linear result of the impact to be Zero.

So in summary - if we Average the linear forces, and Sum the angular forces, we should get realistic outcomes in all cases.

What do YOU think? Do you agree? No? Why?

Posted on 2009-01-04 21:26:58 by Homer
I've implemented the few small changes necessary to deal with the proposed solution to the problem of multiple contact as described above.

However while doing so, I noticed a rather big problem in my collision response.
I'm not fixing up the angular velocity after a collision occurs !!!

Let's look closely at the series of equations that I use to INTEGRATE a body forwards in time..
Here we can see how I am extracting a new AngularVelocity from the change in orientation due to the old AngularVelocity..

1: NewAngularMomentum = OldAngularMomentum + (Torque * Time)
2: NewOrientation = OldOrientation + (Star(Old AngularVelocity) * Time)
3: (orthonormalize the NewOrientation)
4: invWorldInertiaTensor = NewOrientation * invBodyInertiaTensor * Transpose (OldOrientation)
5: New AngularVelocity = invWorldInertiaTensor * NewAngularMomentum

Please note that for collision response, we don't need to alter the orientation, since the collision is assumed to have occured 'instantly' (no time has passed).. orientation will change during the NEXT call of the Integrate function (ie, as the body bounces away from the collision)... but for that to happen correctly, we need to already know the post-collision angular velocity.

We already know the new angular momentum.
Can we rearrange these equations to give us a new angular velocity?
Is it actually necessary?

My guess : since no time has passed, the invWorldInertiaTensor has not changed... it should be perfectly legal to just use Step 5 and update our new angular velocity from the new angular momentum and the invWorldInertiaTensor which we already calculated in the Integrate function.

I would like to hear your opinion!
Posted on 2009-01-05 00:03:26 by Homer
Disappointed that nobody has an opinion on this.
Anyway, I won't know if this works until I have implemented 'higher order' polygons than Sphere (which means ANY other polytope, eg Box)... I suspect I might have to INVERT the already-inverted worldspace inertia tensor.

Speaking of high-order polygons, I am currently inclined to implement a general purpose 3D mesh class as my next step, rather than implement other Plutonic polytopes (cone, cylinder etc) which are not 'triangle-friendly'.

Last time, I tried to implement a hierarchy of polytopes based on their complexity, I still feel that was the right path, however I am impatient... I want to describe the WORLD, or at least chunks of it, as just another physics body I can collide with.

On another topic, I had a thought last night about Networked physics.
Typically, the physics is performed on both the server and the clients (but only the server does collision handling), and the server sends all the clients information whenever a physical body diverts from its current trajectory (ie due to a collision, or for player models, due to actions of the player).
In most 3D multiplayer games, players don't typically move in straight lines for long periods, and from the Client perspective, why the hell do we care about the physical state of something that is not visible?
It seems worthy to try sending only the combined world transform of currently-visible objects to each Client.
This means two things: firstly, the Client doesn't need a physics engine AT ALL ... and secondly, the Client does not have to perform ANY visibility checks - it simply draws what it is told to draw.
This places a little more cpu load on the Server, but I suspect it will actually REDUCE network bandwidth considerably in a massively-multiplayer scenario, while freeing up valuable clientside cpu time for even more eyecandy!

Posted on 2009-01-06 00:05:57 by Homer
Homer, I think your solution for the 1st example isn't quite right. I think the points of impact is throughout all the points in contact with the ground. Yeah for your last example it should be rotating.

Haha you need a physics major. I'm only a mathematics major.  ;)
Posted on 2009-01-08 09:00:46 by roticv
Victor, I agree with that.. #1 is really a 'contact region' problem - however, my understanding is that this has no bearing on impact forces, its only related to the application of friction and restitution which slightly changes the contact resolution - ie theres more friction because theres more surface area in contact, but if we disregard this, the collision can be resolved by using the bounding points. The difference is tiny for a 'head-on' collision, but gets larger if the object is sliding... basically, I'm not interested in simulating physics with absolute accuracy, I'm more interested in producing realistic (plausible) outcomes with as few cycles as possible.
Still, if any physics majors happen to read this thread, I'd love to hear from them :)

Posted on 2009-01-08 09:21:28 by Homer
Networked physics: I've decided that Clients should all run a simulator.
Client will inform Server if/when the user presses a 'player control'.
Server will broadcast this to all other Clients WHO CAN SEE THAT PLAYER.

From the client point of view, if another player is on your screen, you're getting sent data about which keys/controls they are pressing... and when another player becomes visible for the first time, or they collide with something, you're getting sent the full physics state as well.

So we only get sent data about the physical state of on-screen players when they first breach the view frustum, or they bounced off something and their trajectory changed.

This way we further minimize the amount of data being sent by the server to the clients, and take more advantage of dead-reckoning on the client side.

Posted on 2009-01-09 09:30:09 by Homer
Today I decided to add support for CollisionTriangle.
Because I'm such a nice guy, I've given code for the most primitive triangle-based collision method.. it tests if a given 3D point (assumed to be on the triangle's plane) is inside the Triangle, or outside of it.. I've called it CollisionTriangle.versus_Point :) We'd expect to call a preliminary method to test for intersection of (eg) a Ray and a Plane, and then pass the intersection point to this method to see if we actually hit the triangle.
There's an update of the CollisionBody.inc file attached below.

The inheritance hierarchy for collidable stuff now looks like this:

CollisionShape
--CollisionPlane
----CollisionTriangle
--CollisionBody
----CollisionSphere

As we derive more complex entities, we will add them to this tree, taking full advantage of the power of Object Oriented Programming in the way it was intended to be used (rather than merely for the sake of it).

Soon we'll need to depart from this clean tree somewhat, as we'll be deriving shapes which are based apon other shapes... for example, a 3D cube will be composed of triangles and planes.

When we get to that stage, I'll probably improve the way I am storing the points (vertices) of the primitives (most likely I'll index a global array rather than keep duplicate points everywhere).

Posted on 2009-01-10 01:24:43 by Homer
I see that this thread is still popular, so I will continue with my public posts.
It should be clear by now that the class which performs all the physics stuff is separate from the class(es) which performs the collision detections.

Our main physics body class works for ANY SHAPE... it does not care, with the exception of the Inertia Tensor...
But the collision detection depends on the shape of the body.
Posted on 2009-01-11 07:58:30 by Homer
Today saw the introduction of two new classes.

CollisionPolygon derives from CollisionBody, it is a baseclass for arbitrary 3D polygons.
CollisionBox derives from CollisionBody, it describes a 3D Box-shaped collision hull.

I will be removing the CollisionTriangle class... since CollisionPolygon stores a list of collision primitives (points, edges, planes, triangles) which have been defined as simple structs.
Its functionality will be absorbed by the CollisionPolygon class in the immediate future.

Also, I will be removing the fields and methods of CollisionBody which deal with the physical State of a Body, and moving them into a new class called PhysicalEntity: CollisionBody and its relatives will describe a Reference geometrical entity, while PhysicalEntity will describe a LIVING INSTANCE of a CollisionBody, and that's where the State information really belongs.

PhysicalEntity will not derive from any existing class: it will be 'friendly' with the Collision classes, and will use a pointer field to identify which (previously-created) collision geometry best describes it.

Finally, I will be writing a PhysicalMeshEntity class which derives from PhysicalEntity, and those will represent the Living Instances of a D3D_Mesh object.

It's nice when you find a good design pattern, everything falls into place, even if it took a while to find the right path.

Posted on 2009-01-12 08:59:27 by Homer
I made a mistake in my last post.
CollisionBox derives from CollisionPolygon.

It should be obvious?
Posted on 2009-01-13 02:48:19 by Homer
I've done a fair bit of work to split the CollisionBody class, mostly to improve the use of memory when the number of physical entities is high (yes, I am optimistic).

CollisionBody now represents the BodySpace geometry and mass attributes of a physical body, but does not describe anything about its physical State (ie, there is no Position, there is no Orientation, there is no Velocity).

A new class called CollisionBodyInstance contains the physical State information, as well as a pointer to a CollisionBody (and thus any number of instances can share the same reference object).

I've decided to store all instances in one collection (in the Simulator), in order to keep the code loops as unrolled as possible, and in order to reduce cache misses during broad-phase collision testing.

We now have two object trees that look like this:

-CollisionShape
----CollisionPlane
--------CollisionTriangle
----CollisionBody

-CollisionBodyInstance
----CollisionPolygon
--------CollisionBox

...and you can draw a nice pointy arrow from CollisionBodyInstance to CollisionBody.

I'm fairly unhappy with the naming convention now, but CollisionPolygonInstance is rather long to type :P

I think I can safely merge the code from the CollisionPlane and CollisionTriangle classes into CollisionPolygon, and get rid of CollisionShape completely, leaving me with only CollisionBody in the upper object tree.
That will mean that all the point/plane styled collisions will be handled by CollisionPolygon, which makes sense to me.
I will leave the lower object tree alone, as I intend to add 'implicit' geometries later (ellipses, cones, cylinders etc).

Guess I'll post another update soon :)
Posted on 2009-01-18 23:27:03 by Homer
I've finished moving code from one class to another (for now).

We now have:
Collision Primitive structs (Point, Edge, Plane).
CollisionBody (reference object), and its derived D3D_CollisionMesh.
CollisionBodyInstance, and its derived classes (CollisionBox,CollisionPolygon,D3D_PhysicalEntity).

The simulator operates apon INSTANCE objects, but is aware of REFERENCE objects.
For now, the ref objects are stored outside the simulator (ie, in the application).

Any questions? I'm ok to answer any and all relevant questions at this time.
Posted on 2009-01-19 03:18:48 by Homer
I haven't done a lot of coding in the past few days, but today I did add a new attribute (switch) to the CollisionBodyInstance class which allows us to defy the laws of physics for a body instance which is 'static' - no forces (gravity, collisions) will ever affect it, it will not rotate or move, it is a static part of the physical world (this could be thought of as the equivalent a zero dof constraint). This means that much of the game world can be constructed from physical mesh instances (ie using a custom level editing tool and/or scripts) rather than laboriously constructed from unique surfaces in a 3D modeling application.
Of course, you'll still need to create the reference meshes in a 3D modeling app... but having done so, you can import them into the game and create as many instances as you like, rotating and positioning each instance to suit yourself, while arbitrarily declaring instances as being static or dynamic.
This being the case, it might be cool if we can disable (collision detection and rendering for) given faces of a given instance, knowing that these faces will always be occluded.... but I'll leave such optimizing until I have a rough "in-game" level editor.

Posted on 2009-01-22 00:12:37 by Homer
Today I made a few small but interesting changes.
CollisionBodyInstance.Integrate is now a Dynamic method.
It is redefined in the derived CollisionPolygon class, where extra code has been added which transforms the bounding points from bodyspace to worldspace.

Now, whenever the Integrate method is called, the WorldSpace bounding points are recomputed automagically :)
This is incredibly important for the 'narrow' (aka 'discrete') collision testing.

In my next post, I'll begin to discuss collision tests for 3D convex polygons other than the Sphere.