Thanks for the info. With backtracking I actually meant the computation of the exact collision time, and let (part of the simulation) only go that far, so it's not really "back tracking" in the physics engine; does that correspond to your 2nd proposal. I just got this from a physics bookhttp://www.amazon.com/Dynamic-Simulations-Multibody-Systems-Coutinho/dp/0387...that implements it that way (at least that why I got from reading it diagonally, the books contains a lot of advanced math...) But do you mean that with your proposed methods the simulation will advance a full "time step" anyway, so the time interval does not need to broken up into smaller ones, where each sub-interval ends with a collision event? I wander how this could work since most of the time in a game when a collision happens, the game logic decides what forces to apply next, so the simulation can't really advance a full time step anyway (although that could be hacked I guess). Converting the game logic into differential equations with constraints seems very hard. However, I must admit I haven't used any modern physics engines the last 5 years or so... But it's interesting to hear from people that did. On Fri, Mar 6, 2009 at 11:59 AM, jean-christophe mincke < jeanchristophe.mincke@gmail.com> wrote:

Hello Peter,

The backtraking in time to solve the collision problem you mentionned is not, in my opinion, efficient.

From a previous life as an aerospace engineer, I remember that two other solutions exist to handle contact or collision constraints, at least if 2nd order diff. equations are used to describe the motion of a solid with mass.

In any case, you have to use a 'serious' variable time step integration algorithm (I.E Runge-Kutta).

1. The naive one: introduce a (virtual) spring between every 2 objets that may collide. When these objets get closer, the spring is compressed and tries to push them back. If the mass/velocity are high, that leads to a stiff system and the time steps may become very small. However, this solution does not require any modification of the equations of motion.

2. The serious one: modify or augment the equations of motion so that the collision constraints are implicitly taken into account. If I remember well, the magical trick is to use langrangian multipliers. The difficult here (especially in the context of aFRP) is to derive the new equations.

Hope it helps

Regards

Jean-Christophe Mincke

2009/3/6 Peter Verswyvelen

...

Regarding hpysics, did anybody did some experiments with this? The blog seems to be inactive since december 2008; has development ceased?

Do alternatives exist? Maybe good wrappers (hopefully pure...) around existing engines?

Integrating hpysics with Grapefruit might be a good topic for the Hackaton, trying to make a simple game (e.g. Pong or Breakout) without using recursive signal functions, but with correct collision response and better-than-Euler integration, all handled by the physics engine. Other FRP engines could be tried, but Grapefruit hacking is already a topic on the Hackaton, so it would combine efforts.

It feels as if none of the current FRP engines can handle physics correctly, since a typical physics implementations requires "time backtracking", in the sense that when you want to advance the current simulation time by a timestep, collision events can happen during that time interval, and hence the FRP engine can only advance time until the earliest collision event. So to do physics *with* an FRP engine, the implementation and maybe even semantics of the FRP system might need to be changed. *Using* a physics engine as a blackbox inside an FRP system might make more sense.

Thanks to Wolfgang Jeltsch and Christopher Lane Hinson for having a discussion with me that lead to this. Interestingly a similar discussion was help by other people in the Reactive mailing list at the same time :-)

Cheers, Peter Verswyvelen

_______________________________________________ Reactive mailing list Reactive@haskell.org http://www.haskell.org/mailman/listinfo/reactive

Sorry, my message was inadvertently sent - hit the wrong key - a gmail feature Peter, Backtracking: yes it is the computation of the exact collision time. I gave 2 solutions that can be used in multi-body dynamics, in general (that is, with 2nd order derivatives). I am not a game writing specialist but, if I understand you, I would say that, in a game, we have 1st order diff equations of the form x(T) = integrate(speed(x(t), t), T0, T) or on a diff form : dx/dt = f( x(t), t) where speed depends, without any lost of generality, on t and x(t). In case of a collision, that is when x(t) = Collision_position (i.e a ball boucing against a fixed wall), the speed may change discontinuously (i.e. speed = -speed). It will happen at an unknown time Tc. It is possible to find Tc, accurately, by solving the equation (i.e Newton Raphson or another root finding method). x(Tc) = Collision_position where x(Tc) = integrate(speed'(x(t), t), T0, Tc) where speed' is the speed as if there were no obstacle. So I would say that the main algorithm to solve such a problem is: 1.Suppose that S(t) is the description (equations) of your system with t >= some initial t0. This system will behave continuously (that is, all its state variables will be continuous) between t0 and t1. In your example t1 is the exact moment of the collision. 2. With a combination of a integration/root finding algorithm, find t1 - you get all the state variables for free because to find t1, we need to integrate the system. 3 Change S(t) to S'(t) where t >= t1. S'(t) is a description of the system that takes into account the effect of the collision. 4 Continue with first step. Rem: If an accurate root finding algorithm is too costly, another solution is: knowing S(t) at some tn, compute S(t) at tn+1 without paying attention to any collision. Than use S(tn+1) to check whether a collision took place. If no collision: continue and compute S(tn+2) etc. If collision: Assume that the system is linear between tn and tn+1 and then solve the linear equation: x(tc) = x(tn) + (x(tn+1) - x(tn))/(tn+1 - tn) * tc = Collision_position Once tc is known, replace your system as explained above with S'(t) , t>= tc The condition here is that [tn, tn+1] must be choosen small enough in order that the assumption if linearity holds. Regards Jean-Christophe Mincke On Fri, Mar 6, 2009 at 2:26 PM, jean-christophe mincke < jeanchristophe.mincke@gmail.com> wrote:

Peter,

Backtracking: yes it is the computation of the exact collision time.

I gave 2 solutions that can be used in multi-body dynamics, in general (that is, with 2nd order derivatives). I am not a game writing specialist but, if I understand you, I would say that, in a game, we have 1st order diff equations of the form

x(T) = integrate(speed(x(t), t), T0, T) or on a diff form : dx/dt = f( x(t), t)

where speed depends, without any lost of generality, on t and x(t).

In case of a collision, that is when x(t) = Collision_position (i.e a ball boucing against a fixed wall), the speed may change discontinuously (i.e. speed = - speed). It will happen at an unknown time Tc. It is possible to find Tc, accurately, by solving the equation (i.e Newton Raphson or another root finding method).

x(Tc) = Collision_position where x(Tc) = integrate(speed'(x(t), t), T0, Tc) where speed' is the speed as if there were no obstacle.

So I would say that the main algorithm to solve such a problem is

...

= some initial t0. This system will behave continuously (that is, all its state variables will be continuous) between t0 and t1. In your example t1 is

1.Suppose that S(t) is the description (equations) of your system with t the exact moment of the collision.

2. With a combination of a integration/root finding algorithm, find t1 - you get all the state variables for free because to find t1, we need to integrate the system.

3 Change S(t) to S'(t) where t >= t1. S'(t) is a description of the system that takes into account the effect of the collision.

Continue with first step.

Rem: If a accurate root finding algorithm is too costly, another solution is, knowing S(t) at some tn, compute S(t) at tn+1 without paying attention to any collision. Than using S(tn) to check whether a collision took place.

If no collision: continue and compute S(tn+2) etc. If collision: Assume that the system is linear between tn and tn+1 and then solve the linear equation:

On Fri, Mar 6, 2009 at 1:01 PM, Peter Verswyvelen wrote:

...

Thanks for the info. With backtracking I actually meant the computation of the exact collision time, and let (part of the simulation) only go that far, so it's not really "back tracking" in the physics engine; does that correspond to your 2nd proposal. I just got this from a physics bookhttp://www.amazon.com/Dynamic-Simulations-Multibody-Systems-Coutinho/dp/0387...that implements it that way (at least that why I got from reading it diagonally, the books contains a lot of advanced math...) But do you mean that with your proposed methods the simulation will advance a full "time step" anyway, so the time interval does not need to broken up into smaller ones, where each sub-interval ends with a collision event? I wander how this could work since most of the time in a game when a collision happens, the game logic decides what forces to apply next, so the simulation can't really advance a full time step anyway (although that could be hacked I guess). Converting the game logic into differential equations with constraints seems very hard.

However, I must admit I haven't used any modern physics engines the last 5 years or so... But it's interesting to hear from people that did.

On Fri, Mar 6, 2009 at 11:59 AM, jean-christophe mincke < jeanchristophe.mincke@gmail.com> wrote:

...

Hello Peter,

The backtraking in time to solve the collision problem you mentionned is not, in my opinion, efficient.

From a previous life as an aerospace engineer, I remember that two other solutions exist to handle contact or collision constraints, at least if 2nd order diff. equations are used to describe the motion of a solid with mass.

In any case, you have to use a 'serious' variable time step integration algorithm (I.E Runge-Kutta).

1. The naive one: introduce a (virtual) spring between every 2 objets that may collide. When these objets get closer, the spring is compressed and tries to push them back. If the mass/velocity are high, that leads to a stiff system and the time steps may become very small. However, this solution does not require any modification of the equations of motion.

2. The serious one: modify or augment the equations of motion so that the collision constraints are implicitly taken into account. If I remember well, the magical trick is to use langrangian multipliers. The difficult here (especially in the context of aFRP) is to derive the new equations.

Hope it helps

Regards

Jean-Christophe Mincke

2009/3/6 Peter Verswyvelen

...

Regarding hpysics, did anybody did some experiments with this? The blog seems to be inactive since december 2008; has development ceased?

Do alternatives exist? Maybe good wrappers (hopefully pure...) around existing engines?

Integrating hpysics with Grapefruit might be a good topic for the Hackaton, trying to make a simple game (e.g. Pong or Breakout) without using recursive signal functions, but with correct collision response and better-than-Euler integration, all handled by the physics engine. Other FRP engines could be tried, but Grapefruit hacking is already a topic on the Hackaton, so it would combine efforts.

It feels as if none of the current FRP engines can handle physics correctly, since a typical physics implementations requires "time backtracking", in the sense that when you want to advance the current simulation time by a timestep, collision events can happen during that time interval, and hence the FRP engine can only advance time until the earliest collision event. So to do physics *with* an FRP engine, the implementation and maybe even semantics of the FRP system might need to be changed. *Using* a physics engine as a blackbox inside an FRP system might make more sense.

Thanks to Wolfgang Jeltsch and Christopher Lane Hinson for having a discussion with me that lead to this. Interestingly a similar discussion was help by other people in the Reactive mailing list at the same time :-)

Cheers, Peter Verswyvelen

_______________________________________________ Reactive mailing list Reactive@haskell.org http://www.haskell.org/mailman/listinfo/reactive

* Peter Verswyvelen [2009-03-07 18:34:10+0100]

On Fri, Mar 6, 2009 at 10:39 PM, Roman Cheplyaka wrote:

...

...

The blog seems to be inactive since december 2008; has development ceased?

Sort of. One reason is that DPH does not seem to be ready for hpysics yet, another one is that I don't see any potential users around (read: I just need a kick in the ass).

Is it a performance issue?

Yes. As Roman Leshchinskiy explained it's because parallel arrays are not fused properly yet. But it's quite trivial to modify Hpysics to use ordinary lists or arrays, and I think it'll give reasonable performance.

...

...

Integrating hpysics with Grapefruit might be a good topic for the Hackaton, trying to make a simple game (e.g. Pong or Breakout) without using recursive signal functions, but with correct collision response and better-than-Euler integration, all handled by the physics engine. Other FRP engines could be tried, but Grapefruit hacking is already a topic on the Hackaton, so it would combine efforts.

Yes, I'm actively pondering Hpysics+Grapefruit (it's the primary reason of my interest in Grapefruit). But first of all we need to get graphics support into Grapefruit.

Does your proposal re Hackathon indicate that you'd like to join?

Yes, Thomas 'Bob' Davie and I already joined the Hackaton, but the wiki is not yet updated.I see you've joined too, cool

Great! I'll have more free time after March 15, and we can arrange an IRC meeting to discuss this. -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain

* Peter Verswyvelen [2009-03-08 12:00:23+0100]

On Sat, Mar 7, 2009 at 6:49 PM, Roman Cheplyaka wrote:

...

* Peter Verswyvelen [2009-03-07 18:34:10+0100]

...

On Fri, Mar 6, 2009 at 10:39 PM, Roman Cheplyaka wrote:

Is it a performance issue?

Yes. As Roman Leshchinskiy explained it's because parallel arrays are not fused properly yet. But it's quite trivial to modify Hpysics to use ordinary lists or arrays, and I think it'll give reasonable performance.

Personally I would not mind too much about performance initially; I'm very confident that lots of optimizations can be done afterwards - maybe even letting the GPU handle certain tasks.

I wouldn't mind too if it was just 'inefficient'; however, it's practically unusable. <> http://physics-dph.blogspot.com/2008/08/status-report-week-11-12.html -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain

Am Samstag, 7. März 2009 18:49 schrieb Roman Cheplyaka:

Great! I'll have more free time after March 15, and we can arrange an IRC meeting to discuss this.

I’d be happy if you would also invite me to this IRC meeting when it will finally happen. Best wishes, Wolfgang