[Haskell-cafe] Collision Detection

[Sergiu Ivanov]

Dear Yotam,

Disclaimer first: I'm not a specialist in numeric simulations nor in
computer algebra systems, nor in physical simulations, although I've
done some simple contributions to these domains in the past.

Thus quoth  Yotam Ohad  at 08:17 on Sat, Jul 08 2017:
>
> I am thinking about writing a small physics engine with collision detection
> and I wanted to go over my ideas with you to help me refine them.

That's cool!

> I want to express objects as a group of inequalities and their domain. For
> example, a sphere would be only one inequality: x^2+y^2+z^2 -1 <= 0 on the
> whole domain. That way, to check a collision between two objects, one needs
> to check if at least one pair of inequalities with overlapping domains has
> a solution. I am unsure about how to express the inequalities in a way that
> could still allow me to compare between two of them.

The problem you are stating looks like that of representing and solving
a system of non-linear polynomial equations.  Haskell's ecosystem has
some numerical solvers which you may want to use [0].  If you want exact
(symbolic) solutions, however, that's what computer algebra systems
(like SymPy [1]) are good at, but it looks like Haskell has no recent
actively maintained libraries for that [2].

In general, representing systems of polynomial equations/inequalities is
done using collections of polynomials, which are collections of
monomials, which are essentially dictionaries (vectors) assigning the
power and the coefficient to each variable.  For example:

 2x^2 3y - 5z^3 2x --> [ {x: (2,2), y: (3,1), z: (0,0) }
                       , {x: (2,1), y: (0,0), z: (5,3) } ]

(I denote multiplication by juxtaposition (omitting *)).

Finding the roots of such a polynomial is often non-trivial business.

> To add forces in, I think I can express them by adding a time dimension to
> the inequalities. For example, a constant force in the x-dimension on the
> previous sphere could be represented as (C+dx/dt*t+0.5*a*t^2)^2+y^2+z^2 <=
> 0.

Given that the equation of a sphere is

  (x-x0)^2 + (y-y0)^2 + (z-z0)^2 = r^2

and that you seem to be trying to express the movement of its centre
(x0,y0,z0) along the x axis, I suppose that you meant to write something
like

  (x-x0(t))^2 + y^2 + z^2 - r^2 <= 0

where x0(t) = x0 + v t + a t^2/2.

> But then I am not sure about how to treat non-integrable forces.

You probably don't want to go that complicated for a lot of real-world
applications.  (Especially if you are doing numerical resolution.)

> Another approach is to calculate the displacement of the object after
> each time interval.

I'm not sure how that differs from what you wrote previously.

> I don't like this approach as I want to integrate it with FRP in the
> end, and FRP continues time is something I would like to preserve.

Good news: If you are able to compute the time delta between two events,
you can plug it into your equations to compute the new position.

Very bad news: Usually when your time step gets too big, the simulations
(at least for Newtonian mechanics) stop working.  That's because the
equations like x = v t + a^t/2 give you velocity _at a given moment of
time_, and if this velocity varies quickly, you are likely to miss
important events.

Now, you may also have something different in mind.

> After I'll have everything above sorted, the next things would be to run
> simulations. I think at the start I'll check every pair of objects and try
> to calculate whether or not the will collide in the future.

That's a reasonable naive solution that will probably not scale well
with the number of objects.

I hear people use "proximity volumes" (they use different words which I
cannot remember right away): each object is assigned a sphere which
contains it completely, and then some space.  Now, you only test
collisions with the objects in your proximity volume, to save time.

> I'll save all the results in ascending time order. and every
> iteration, update the movement after the closest collision and update
> the collision pair order.

I'm not sure why you want to do this.

--
Sergiu

[0] https://wiki.haskell.org/Applications_and_libraries/Mathematics

[1] http://www.sympy.org/en/index.html

[2] https://wiki.haskell.org/Applications_and_libraries/Mathematics#Computer_Algebra
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170709/25a9f9fd/attachment.sig>