Collision Detection

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Collision Detection

Yotam Ohad
Dear Cafe,
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.

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.

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. But then I am not sure about how to treat non-integrable forces. Another approach is to calculate the displacement of the object after each time interval. 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.

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. 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.

Thanks,
Yotam

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Collision Detection

Sergiu Ivanov-2
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

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

signature.asc (497 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Collision Detection

William Yager
In reply to this post by Yotam Ohad
Take a look at the (WIP) course notes from Etienne Vouga's physical simulation class (shared with permission). I recommend these very strongly to anyone interested in macro-scale physical simulation. Its relatively rigorous approach to algebraic object types should also appeal to haskellers. 


Chapter 10 discusses practical efficient collision techniques. 

--Will

On Jul 8, 2017, at 3:17 PM, Yotam Ohad <[hidden email]> wrote:

Dear Cafe,
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.

...
Thanks,
Yotam
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Loading...