[Haskell-cafe] Re: [reactive] FRP + physics / status of hpysics

[jean-christophe mincke]

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 at 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
>
> 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.
>
> 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 <bugfact at gmail.com>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 book<http://www.amazon.com/Dynamic-Simulations-Multibody-Systems-Coutinho/dp/038795192X>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 at 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 <bugfact at gmail.com>
>>>
>>>> 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 at haskell.org
>>>> http://www.haskell.org/mailman/listinfo/reactive
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090306/7e5c36d9/attachment.htm