Has anyone implemented an elegant, efficient, and stable physics engine lately? I have just gotten one up and running including: velocity, acceleration, friction (static and kinetic), viscosity, bouyancy, and inelastic collisions! It was working quite well, but I noticed a few glitches here and there. Well, fifteen hacked up patches and a week later I can''t even let it run for more then a few seconds without coming across an error! The real problem seems to be the collision detection routines. So I guess my question is this... Has anyone got a well layed out collision detection routine I can look at?

It may not be only your CD method. If you are actually detecting the collisions, then they basically act as forcing functions for the dynamics of your system, and you will get numerical problems if you don''t use a consistent, stable integration scheme----regardless of whether your CD is good or bad.

How are you doing the time integration? What type of integration scheme are you using? Explicit Euler? Runge Kutta?




Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

sure

I don''t know what the name of the method of time integration I''m doing is. It''s the only way I know of doing it. Essentialy I calculate the displacement over the given time period and check for collisions along that path.

I calculate the displacement explicitly using traditional newtonian mechanics (i.e. f = ma, v = at, s = vt + 0.5at^2, ...etc.). Then I treat that displacement as a direct vector of travel (of course this is mildly inaccurate when under acceleration, but I doubt the user will notice the difference...).

Example->

do_physics(Object *obj, float time)
{
Vector f, a, d;
Collision *col;

f = get_total_force(obj);
a = get_total_accel(obj, f);
d = get_total_disp(obj, a, time);

col = check_collisions(obj, d);

if(col == NULL)
{
displace(obj, d, 1.0);
accel(obj, a, time);
}
else
{
displace(obj, d, col->fraction);
accel(obj, a, col->fraction * time);
rebound(obj, col);

time -= col->fraction * time;

do_physics(obj, time);
}
}

Does that answer your question?

Well, a little research has shown that I am more or les using the Euler method. I did find a few rough spots in my CD routines, and fixing those seems to have gotten my simulator off it''s knees

Thanks for bringing up the time integration matter though grhodes_at_work. I think Euler may be adequate for my needs, but I''m keeping RK in mind.

Anyway, I''d still be interested in seeing somebody else''s code if anyone has some available for comparison?

quote: Original post by Novalis
I calculate the displacement explicitly using traditional newtonian mechanics (i.e. f = ma, v = at, s = vt + 0.5at^2, ...etc.). Then I treat that displacement as a direct vector of travel (of course this is mildly inaccurate when under acceleration, but I doubt the user will notice the difference...).

For projectile motion, you approach is basically *exact*, as long as you use the correct t. The only flaw is that you don''t have a initial displacement in the equation for s. And you don''t have an initial velocity in the equation for v. I would use instead, v = at + v_initial and s = vt + 0.5at^2 + s_initial. You do have velocity as a linear function in time and displacement as a parabolic function in time which are exact for simple projectile motion. If you use *these* equations correctly, then there won''t be any error at all, and the trick *does* become one of collision detection.

The trick in using these exact equations correctly is what value of t do you use. Turns out, t will be different for every object, once you start having collisions. You sort of have to restart the equations for those objects participating in a collision, using a new value for v_initial and s_initial after the collision, and for the objects that collide, t restarts at zero. Otherwise, you''re going to be pluggin the wrong value of t in there. (You could just restart with new values of t, v_initial, and s_initial for *every* object after each collision, to keep implementation simpler.) This doesn''t help with detecting collisions of course.

quote: Original post by Novalis
Well, a little research has shown that I am more or les using the Euler method. I did find a few rough spots in my CD routines, and fixing those seems to have gotten my simulator off it''s knees

Are you certain? This contradicts your post above, which indicated you were using the *exact* projectile motion equations---but possibly using them wrong.

quote: Original post by Novalis
Thanks for bringing up the time integration matter though grhodes_at_work. I think Euler may be adequate for my needs, but I''m keeping RK in mind.

Again, if you''re using the exact equations then you are in fact *not* using Euler integration. But....

....Your statement is a bit naive (but not at all uncommon). I can advise on this matter because of my background and experience. I have some expertise in numerical simulation and integration. I have a M.S. degree in aerospace engineering and have completed most of a Ph.D., where I''m focusing on real-time fluid dynamics simulations using numerical methods. I also have a strong background in mechanics and vibration simulation. I can tell you this. The Euler method may be easy, but is generally unstable and a poor choice. It *only* works reasonably when there are no springs (or other causes of oscillations) in the system. Now, you don''t have any springs in your system (it seems) so Euler may work OK for you and that''s fine. But if you have *lots* of collisions----such that objects bounce back and forth in an oscillatory (repetitive) fashion then Euler may blow up on you. Essentially, periodic collisions can exite the oscillatory instability of the Euler method. RK is better, but it too is not universally stable. But for your type of simulation it should be just fine. (RK will fail if you have articulating rigid bodies and are using very stiff springs to enforce joint constraints.)

Oh well, hope I''ve given you just a little more more helpful information. Good luck!




Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Whew...

I can see I''ll have to be precise when talking to you! I was keeping things simple for the sake of less typing

First off, the equation for s doesn''t need an initial s, that would be an equation for absolute position, not relative displacement.

Secondly, my bad. I should have stated my velocity equation as dv = at, which of course leads to vf = v0 + at, but worry not, that is how it is applied.

As for dt, as you indicated I use fractional dt when a collision is detected.

Now your next point shows me where our perspectives diverge... I think it is my fault. I am not calculating the *absolute* displacement and velocity explicitly, I am calculating the *relative* displacement and velocity (ie ds and dv) per time period dt. I spent last night studying Euler, RK, Bulirsch-Stoer, and the rest and I assure you I''m using Euler right now.

I''m not sure I''d go so far as to call myself naive for implementing Euler first though... Let''s go with optimistic
As it is, I do have "springs" in my system. Well, drag and friction are oscillatory forces at any rate... However, I have implented a bit of a fail-safe mechanism to prevent overshoot. I''m still massaging the whole thing right now, so I''ll just describe it in brief rather then use pseudo-code... Basically when calculating ds I manage acceleration due to what I''ll term "external forces" and acceleration due to friction and drag seperately. First I look at the "requested" time interval. Then I check to see if the dv reaches zero during that time. If it does, I calculate ds up to that point, then I recalculate the friction and drag forces and calculate ds for the remaining time interval. I''m not sure if I was clear or not... As soon as I''ve polished it off, I''ll post it. I would be very interested to hear your criticism of the whole system.

Thanks for the feedback!

OK, how about some comments on the following code...

void phys_update(struct S_BSP *bsp, struct S_PHYSATTRIB *obj, float time){	VECTOR				ds, dv, nodisp = {0.0f, 0.0f, 0.0f};	PHYSCOLLISION		*col;	SCALAR				dt;/* This is a speed hack and can be ignored	VECTOR				f_total, accel;	phys_get_force(obj, f_total);	VScale(f_total, 1.0f / obj->mass, accel);	phys_get_disp(obj, f_total, accel, time, ds);*/	for(col=ll_head(&obj->collisions); col!=NULL; col=ll_next(&obj->collisions))	{		if(!sphere_isects_face(bsp, col->face, obj->origin, obj->radius, ds))		{			ll_del(&obj->collisions, col);			free(col);		}	}	while(time > 0.0)	{		dt = phys_get_step(obj, time, dv, ds);		col = sphere_isects_bsp(bsp, 0, obj->origin, obj->radius, ds, VLen(ds)+obj->radius);		if(col == NULL)		{			VAdd(obj->origin, ds, obj->origin);			VAdd(obj->velocity, dv, obj->velocity);			break;		}		else if(col->dist < 0.0)		{			VScale(col->plane.normal, 0 - col->dist, ds);			VAdd(obj->origin, ds, obj->origin);			free(col);		}		else		{			VScale(ds, col->dist, ds);			VAdd(obj->origin, ds, obj->origin);			VScale(dv, col->dist, dv);			VAdd(obj->velocity, dv, obj->velocity);			time -= col->dist * dt;			if(phys_rebound(obj, &col->plane, 1.0f) == 0.0)			{				ll_add(&obj->collisions, col);			}			else			{				free(col);				ll_free(&obj->collisions);			}		}	}}

A few explanations...
When col->dist < 0 that means the obj actualy intersected something else and needs to be "backed" out of it before it can move.

The "collisions" linked list holds a list of all the planes that the object is currently "sliding" along.

When phys_rebound() returns 0 it means that the object didn't have a high enough incident (terminology?) speed to rebound away from the plane so it begins sliding along it.

phys_get_step() is the integrator. It returns the actual amount of time covered by the step it calculated (this was done to include that hack I mentioned before about correctly calculating oscillatory forces).

I think the rest is pretty self-explanatory.

So aside from any general criticism... I'd also like to hear some thoughts on what seems to be my last problem (cha, as if...). Sometimes when an object collides with a polygon with a very low normal velocity, but a very high tangential velocity, it gets "stuck". What happens is sphere_isects_bsp() returns a very small dist (like 1.0E-6). This small a number basically equals zero for the purposes of floating point math, so the object doesn't step forward at all. The next phase of the problem is that phys_rebound() doesn't really manage to get the objects velocity away from the polygon because the incident velocity is so low (again on the order of 1.0E-6 as an example). So the object never moves forward, and it never rebounds away from the polygon it hit. Thoughts?

Edited by - novalis on November 10, 2000 12:47:44 PM

Wow - a physics engine with quadratic position accuracy, collisions, friction, viscosity and buoancy! What game are you making with this?

With my engine, positions are stored in integers and velocities in floats. I didn''t use floats for position because I was afraid of rounding errors. Although my shapes are defined mathematically, every point is either in or out and my collision detection will calculate exactly which step takes you over the line. Resolving collisions in this system took a lot of work, although if I''d worked out my current (not too complicated) solution earlier I would have saved a few months. But in my system of discrete time units, an object resting on the ground is actually the object colliding with the ground at "speed g" every time through the main loop, and these requent litle collisions to the work of friction as well.

It looks here like you are using all floats and calculating everything mathematically. What sort of shape structure are you using?

Having worked for a long time to make the system I use, I''m always proffering hints to other people on the topic, but you''ve gone further than I, and further than most, and using gradual amounts of time (it seems), which I thought would not work in the context of a game.

If I''d known how long it was going to take me, I would have stuck with tile-based land and no other collisions where overlap must be prevented.

Well AndyMan, the shape structure I''m currently using is simple bounding spheres. I believe that it will provide sufficient accuracy for my game (for simplicities sake we''ll call it an RTS), but have kept in mind that in the long run I may have to use the bounding sphere as only a preliminary collision detection, and use the actual model BSPs to make the final determination.

I suppose I could be wrong, but I don''t believe that my work has in any way exceeded the typical physics engine these days. It is a bit more than is required for my game, but I majored in physics in college and can''t help myself The application of the various physical laws is trivial in comparison to the problems of time integration and accurate collision detection.

As for "gradual time increments", I''m not sure it would be possible to make a modern game without them! Considering the issues of varying processor speeds, and network latency to name just a few, a fixed time interval seems unlikely...

Sounds like what I''m doing. I''m using Genesis3D''s BSP and actor collision routines to do CD. I''m also applying gravity, fluid resistance, buoyancy, and friction. I have conserved-momentum collisions between the actors, too; inelastic collisions work well, and elastic collisions also work, but I''m not sure that energy is being conserved correctly. When I complete the code, inter-object friction should be working well, allowing objects to slide around realistically on other objects. I''m also using time minimization to accurately find the true collision point, because the motion of an object is curved, and collision planes are flat. When I do get it all done, im gonna put the code up on my website as part of my game wrapper.

I have fairly good results. It''s awesome watching objects fall through the air, then into the water and slow down, drifting slowly to the bottom.

anthalaris.8k.com