Here is my situation: I have a rigid body with finite mass in contact with N surfaces with infinite mass. I want to apply a force f to the rigid body. This force is divided among the N surfaces: for each surface s[sub]i[/sub], a certain proportion of this force will be applied, w[sub]i[/sub]*f, where the sum of all the w[sub]i[/sub]s is at most 1. The resulting force pushing back from each surface is -w[sub]i[/sub]*f·n[sub]i[/sub], i.e. the normal component of the force applied to surface.

How do I compute the weights w[sub]i[/sub] for each surface? I attached an example image.

That depends on the type of update you are using to run your physics simulation.
There are methods for determining the final force acting on an object accounting for multiple simultaneous contacts. The most popular approach is the “linear complimentary problem” which involves building a Jacobian matrix. Because I feel there are better solutions, I leave you with these key words and let you do your own Google’ing.


There are otherwise 2 common physics-cycle implementations.
#1:
Generate a list of contacts and sort them by time. Handle the smallest time first and update the simulation by that amount, then repeat until you have eventually updated the simulation by the full requested time-step.
This is very accurate and implicitly gets you the correct result. There is nothing special you need to do to handle any number of simultaneous contacts on any given object.
Using your example, at t=0 there are 2 contacts. After sorting, either of them could be handled first, so let’s just assume n1 is handled first.
The force vector f will be changed to reflect off the n1 plane, so that it now points (let’s say) about 140°.
The simulation is updated by t=0, and since no time has passed you don’t have to rebuild any contacts, just move on to the next one which would be n2.
The force vector has changed, so it is not hitting n2 as shown in your picture but at about 140° (screen space). Once again it is reflected off n2 and the new force vector is applied.
The simulation again steps forward by 0 (so just move on to the next contact instead of generating a whole new list and re-sorting it), etc.

The con to this method is performance. If your goal is to step 30 milliseconds into the simulation, you may incur several mini-steps inside the simulation and regenerating contact lists, keeping only the lowest ones, etc. in order to reach the end of the 30-millisecond simulation.


#2:
The most common and fastest approach is to simply allow there to be error.
Generate contacts for a whole simulation time-steps and sort by interpenetration depth. In this case n2 would be handled first.
Each time you resolve a collision, once again you are just updating the force acting upon the body, but instead of advancing the simulation you just update other contacts that involve that body. This is fairly quick.
Then you continue handling contacts in the already-sorted order and re-updating only the ones that could have been affected by the current contact resolve.
Finally, you advance the simulation.

In your example, there would be no error—it would just handle n2, update n1’s contact information, handle n1, and then the ball would be bouncing away from both of them correctly.
But objects that are bouncing inside tightly-closed areas will end up with some interpenetration at the end of the simulation.
The routine sorts by penetration depth, so these will be resolved first-thing next frame and no one will notice it ever happened.
This makes this the preferred method of driving a real-time physics simulation.


L. Spiro

Thanks for the reply. I'm currently doing something similar to what you describe in #1 - continuous collision detection, where I start with t = 0, solve for the first contact, step to that point, add to t, adjust velocity, and keep doing this until t = 1.

The issue is in the "adjust velocity" step. Usually, when coming in contact with a new surface, the velocity should be adjusted by subtracting n*(n.v) from the current velocity - that is, you remove the component of the velocity which is parallel to the normal of the surface you just came in contact with. However, if you're actually in contact with several surfaces, it's more complicated. Consider the following case, as illustrated in the attached image: your character is walking along surface A, and then comes in contact with a sloped ceiling, surface B. The desired reaction in this case is that the initial velocity vector, v1, is projected along the line formed by where the the two surfaces meet - i.e. the cross product of their normal vectors - and the velocity after the intersection is v2. However, if when processing contacts you only take a single contact into account, the following happens:

1) The object is moving along surface A
2) The object hits surface B, and the component of the velocity which is parallel to surface B's normal is removed. This causes the object's new velocity to be slightly downward.
3) IMMEDIATELY after this ("0 time later"), an intersection with surface A is detected. The component of the velocity which is parallel to surface A's normal is removed, and the object's new velocity is, again, pointing into surface B.
4) IMMEDIATELY after this ("0 time later"), an intersection with surface B is detected...
... And the process keeps repeating until you reach an iteration cap. Essentially, there are two contacts, and they each alter the object's velocity so that it's going into the other object, and so no progress is ever made.

In my initial post, what I was trying to get at was a general solution to this. You first build a list of all surfaces that the object is in contact with. Then, you compute the amount of force that would be applied to each surface when attempting to move the object by it's current velocity. Finally, you cause each surface to push back with a force equal to that which was exerted on it. This would result in the true final altered velocity of the object.

However, now I realize that there are really 3 cases to deal with:
1) The object is only in contact with one surface, e.g. walking up a hill. In this case, you simply remove the velocity projected onto the normal.
2) The object is in contact with two surfaces, e.g. the example image. In this case, if the velocity direction is toward the "crease" created by the two surfaces, you project the velocity onto the vector onto the cross product of the two normals, and take that as your new velocity; otherwise, you revert to case 1, using the plane which the velocity vector points most toward.
3) The object is "pinned" by 3 or more points of contact (e.g. attempting to walk into a sharp corner). In this case, the object won't be able to move at all, so just set the new velocity to 0 and end the timestep.

If you have just one contact point, it's always case 1. If you have 2 contact points, it could be case 1 or case 2, depending on where the velocity vector is pointed, but it's not too hard to tell. However, case 3 seems trickier. If you have N contact points, any of these cases could be produced. Consider the case where you're standing in a corner, contacting two walls and the floor. If you walk directly OUT of the corner, it's case 1: you're only "pushing" against one contact point, the floor. If you walk OUT of the corner against one of the walls, it's case 2: you're walking away from one of the walls, but pushing against the floor and one other wall. If you're walking INTO the corner, it's case 3: you're being "pinned" by all 3 surfaces.

Any ideas on how to robustly distinguish between these cases?

So are you aiming for a sophisticated physic simulation or do you just want to keep the player from penetrating the world ( like in a classical FPS game, e.g. Quake 3)?

Not looking for anything sophisticated, just keeping the player from falling through the world. Though after this phase of the update, I will have to do some discrete solving to push overlapping entities apart (everything is capsules or spheres though).

Frankly you are on the right path, although what you call “overlapping” I call “interpenetrating”.
No physics simulation is really complete without the ability to resolve interpenetrating objects, and the solution for your current situation will rely on it.

From your reply and proposed example, the only solution of which I can think is to either use the linear complimentary problem or to use #1 with interpenetration resolving.

I have used both #2 and #1 and #1 has been the most useful so far. Yes sometimes things go where they should not, but within a single frame no one ever really notices that, and I have even encountered your proposed problem without encountering any noticeable problems. If you are going for a super-detailed simulation, #1 may not be suitable, but in everything I have done and Pilotwings has done it has been very suitable.


L. Spiro