Physics - how are they done current and nextgen

[Npl]

Yesterday I thought alot about Cell and how it should aid physics, I just realised that I cant figure out a way to actually do physics without either being accurate to death (and therefore potentially killing even nextgen Consoles) or having alot of possible "Ooops"-Situations. Im wondering how its done in current games and what approach next-gen Games are taking, anyway this are the algorithms I could come up with:

1) The easiest approach:
Compute movement of each Object without caring for collisions. Then check any combination of 2 Objects (translated with their already computed movement) for collision, calculate position and 'refraction' angle at the time of collision. Adjust both objects so they represent their final speed and direction after the collision. Pick next 2 Objects.
Pros: Complexity is n!/2 (ignoring complexity of Objects); Can use -atleast partially- 'Streaming'
Dodgy Situations:
*) Fast moving Objects could "jump" over Collisions
*) Outcome is dependand of ordering of Pairings, suppose a marble is shot onto 2 others, hitting both, but not at once. Would need some kind of depth-ordering to fix this, which would need random access.
*) Similar to last Point, but suppose 2 Marbles (a,b) are moving. The Marble a would hit both b and c, but b could still hit something on its way to collision point, if b`s Path would be corrected before looking at a, a might not collide with b at all.

2) An more exact approach:
Compute a movement-hull of each Object without caring for collisions. Test every pairing of 2 hulls for collision, if colliding adjust movement of both correctly, recalculate hulls. take next 2 hulls
Pros: Fixes fat moving objects, Can still -atleast partially- 'Streaming'
Cons: More intense than the easy approach, especially since hulls could get quite complex (nonlinear movement or irregular shaped objects)
Dodgy Situations:
*) Outcome is dependand of ordering of Pairings - see easy approach

3) Deadly exact approach:
Compute a movement-hull of each Object without caring for collisions, create a list of Object-Pairings. Test every pairing of 2 hulls for collision, if colliding store the Pairing in the list, sorted by collision-time. take next 2 hulls
For each Pairing (a,b) in the list do:
adjust movement of both correctly, recalculate hulls, remove all Pairings in the list which contain either a or b, then test all Pairings (a,n) and (b,n) for Collision, store coliding Pairings in the list, sorted by collision-time.
Pros: Fixes all Dodgy Situations - should be VERY accurate
Cons: Complexity can (and will) explode. heavy Random Access.


Sorry for the longish post and my limited english, but Im really curious how this is being dealt with.

 

[London Geezer]

All i want is for fighting games where the main attractors (the 2 characters, which are the things we are looking at constantly in the game) don't go through each other. Either their hair or clothes or whatever else.
2 characters in relatively limited environments is nothing, and these irritating problems should be solvable in those conditions.

 

[Npl]

All i want is for fighting games where the main attractors (the 2 characters, which are the things we are looking at constantly in the game) don't go through each other. Either their hair or clothes or whatever else.
2 characters in relatively limited environments is nothing, and these irritating problems should be solvable in those conditions.

Thanks, now i`ve to think about how connected stuff like cloths could be done too . *Brain melts*

 

[ERP]

1 is the closest.

Havok 3.0 does something like 2 but allows interpenetration.

But your making it more complex than it needs to be.

The brute force solution is as follows

1. Integrate motion over time (realtively cheap unless there are a lot of constraints)

2. Determine collision (overlapping objects) if there is any search for the point in time just before collision took place (expensive)

3. Apply impulses to the touching bodies and try and advance time again -- goto 2


The secret to a fast solution to this is three fold, since in most interesting cases only a small portion of your objects are in contact you have to compute the minimum subset of the bodies to backup for step 2, you pick an epsilon for your search that is as large as you can get away with, You deal properly with sliding contact constraints (if you don't, any surface contact will kill your simulation).

The other alternative is to allow bodies to slightly interpenetrate and then push them apart. This has it's own set of issues, but it is the way that Havok 3.0 works. They use volume sweeps and I would assume estimate time of impact.

 

[Npl]

But your making it more complex than it needs to be.

I was aware of that ,and thats why I wanted someone to tell me the compromise common solution have.

1. Integrate motion over time (realtively cheap unless there are a lot of constraints)

2. Determine collision (overlapping objects) if there is any search for the point in time just before collision took place (expensive)

3. Apply impulses to the touching bodies and try and advance time again -- goto 2

This is actually what I figured with approach 1 together with what I called "depth-ordering" (I figure you meant the first collision in you Point 2).
This still has the issue that collisions could go by undetected if the speed is high enough to jump entirely over the colliding object.

The secret to a fast solution to this is three fold, since in most interesting cases only a small portion of your objects are in contact you have to compute the minimum subset of the bodies to backup for step 2, you pick an epsilon for your search that is as large as you can get away with, You deal properly with sliding contact constraints (if you don't, any surface contact will kill your simulation).

The other alternative is to allow bodies to slightly interpenetrate and then push them apart. This has it's own set of issues, but it is the way that Havok 3.0 works. They use volume sweeps and I would assume estimate time of impact.

Do you have links to implementation details of Havok?

So I guess it will come down to a set of different algorithms, based on the kind of movement and object, eg fast-moving object like bullets, world-geometry, sliding contact, whatever else.
The more I think of it the more im certain the SPUs will only be used for some kind of RPC. Figure out the rough Details on the PPU, push the grunt work on one of the SPE`s, put PPE-Thread to sleep until SPE is done.

 

[ERP]

Bullets are usually resolved as ray-casts or similar, I don't know of any game that puts bullets into the physics simulation.


Yes almost all available physics simulations can have complete pass through if the objects are moving fast enough. The general solution if this is an issue is to decrease the size of the timestep.

Havok 3.0 uses volume sweeps to resolve this issue.

 

[Jawed]

Operation Flashpoint simulates wind shear and drop for all projectiles.

It's kinda funny when bullets start dinging into the ground around you when the battle is going on a mile down the road...

Jawed

 

[Fafalada]

Yes almost all available physics simulations can have complete pass through if the objects are moving fast enough. The general solution if this is an issue is to decrease the size of the timestep.

At one point in time our implementation used an adaptive step (it would compute multiple iterations of smaller time step for fast moving objects) but as it turns out on average that was just using up extra resources with no real benefit.

 

[ShootMyMonkey]

Sweep tests and bounding volume hierarchies (to limit created pairings) are already possible on current-gen.

The thing that's going to make physics hard on next-gen is parallelizing the whole darn thing. You can parallelize individual collision tests, but actually solving the constraints and computing response is a whole other matter.