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. |
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 |
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
_______________________________________________ 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. |
Free forum by Nabble | Edit this page |