Hi, I''ve been trying to think of solutions to my problem for several days now, and feel that it is time to ask for some assistance. You see, I have a (basic - for now) physics engine in place, which allows me to apply velocity, acceleration, etc. Now, the physics engine steps every frame, which makes it impossible to have the intersection of 2 objects to be the same on every machine... which means that I have to find exactly when those 2 objects collided. This, I have discovered, is no easy task. Does anyone know how I can find the exact time of intersection for 2 dynamic object?

By setting up some equations for the position of the objects, then solving them you can, but these equations will become extremely complicated very quickly. For linear movement with bounding spheres it''s manageable, but once it gets beyond that then it gets tricky. There may be another method which will be far nicer, either you could run the physics at a fixed number per second. So it you have a very high fps, you miss out an iteration, or with a low fps you repeat(although this will make your fps even lower). That way it wont matter. But I''m not sure I see why you would want such accuracy.

generally you solve these problems by just correcting once there has been a collision. so if in frame 1 the objects dont intersect, but in frame 2 they will, instead of trying to figure out exactly when they intersected you just move them so they are only just touching and then apply appropriate contact forces.

for most applications this is enough, because with interactive frame rates and sensible object velocities, they will never overlap so much as to cause problems. also with collision geometry generally being much lower resolution, any innaccuracies are generally not resolvable to the user anyway.

of course if you''re doing something a bit more critical, like engineering software instead of a game, you should probably solve for the intersection rigorously.

Well I have not yet determined the applications of my engine... but I''d liek to make it as acurate as possible. Unless, of course, if the only possible fix is really impractical.

------------------------------
There are 10 types of people in this world, those who know binary, and those who don''t.

The first step is as someone said, make things in your game happen depending on (real)time, not on frame rate. So for instance, instead of having a moving object get x+=4 each frame when something is moving, you would be able to say
x+=.2*timePassed. This way, even when you are getting 2 FPS objects will still move with the same speeds. This will fix the 'different events on different machines' problem, well mostly. You still have the problem of collisions that happen between time steps.

When you find that something has collided, step the time backwards (for just those two objects) by a half step. Then see if they are still collided. If so, step it back 1/4 step. If not, step it forward 1/4 step. And you can keep repeating this until you get the resolution you want.

You can already see that your time resolution is 4x greater with just two steps, and would be 8x greater with 3. For speeding this up, you can take advantage of the fact that once you do it the first time, you pretty much know which part of the objects collided, and you may not have to recalculate the entire collision detection routine.

Anyway this method won't get you 100% accuracy, but it will greatly improve the version of events from machine to machine.

[edited by - aargyle on April 27, 2003 7:52:51 PM]

Well I am already running my physics engine in real time (using an elapsed time variable), so don''t worry about that. Also, there is no need to step back and forward 1/4 steps or anything like that, because I could throw in a simple formula to find the time... Only problem is that some machines could completely miss the collision (eg. frame a shows the 2 objects before collision, and frame b shows it after the collision)
This idea, however, is so far better than my idea of making a heirachy of all the objects both before and after the physics engine step, and comparing every object in the scene. This would be both difficult to engineer, and very expensive computationally.
Do you have any suggestions as to how I could make sure a collision isn''t missed using your method, or some way I could speed up mine?

Thanks for all the help.

------------------------------
There are 10 types of people in this world, those who know binary, and those who don''t.

Resurfacing

------------------------------
There are 10 types of people in this world, those who know binary, and those who don''t.

hmmm... It''s probably better to force some sort of synchronisation between the machines (I take it you refer as ''machines'' as different computers on a distributed network). Typically, you''d have a server doing all the physics stuff, and sending the complete physics state to all the client machines. The client machines do not process the physics update, they merely receive messages from the server telling them the orientation and position of the objects in the world at a particular time. If you have a slow network, you can allow the clients to run the physics update, while still receiving the object positions and orientations from the server, all they do then is interpolate what physics state they found to what the server found, the amount of interpolation would depend on the lag.

If you don''t synchronise the machines, they will diverge, quite rapidly. Their timing might not be the same, the floating point operations could return different results (different CPUs), one could lag, and if you use real time physics, it won''t solve everything. A ball having a trajectory at 60 fps will not have the same trajectory at 30 fps, if you have collisions, ect... You have to use a discreet time step, no matter what, if you want a complete rigid body dynamics system.

use a method of stepping that using a delta time. ever frame you check for penetrations. if you find one u divide your delta time by two and see if the objects collide at that time. you do this until u find the exact point in time they collide or until the amount they interpenetrate is within tolerable limits.

"We are what we repeatedly do. Excellence, then, is not an act, but a habit." - Aristotle

I think hes talking about a simple miss on two different speed machines. Like, on the first one at 85 FPS the collision is detected, but on a different computer at 25 FPS the objects appear on the other side of each other without ever colliding.

What you need to do is not test the objects bounding boxes, but test a bounding box that includes the objects entire path from one frame to the next. So, say you had a box moving forward, you would test it as a really long box that starts where the object started and stops where the object ended up.