Hpysics blog

LambdaCube accepted to JSSP

2009-05-12T20:08:00.002+03:00

LambdaCube render engine by Csaba Hruska is accepted as Jane Street Summer Project this year. Congratulations, Csaba!

Hpysics + GrapeFruit (and hackathon)

2009-04-03T00:37:00.003+03:00

The 5^th Haskell Hackathon will be the place where Hpysics will meet Grapefruit — a library for Functional Reactive Programming with a focus on user interfaces. It means that one of our goal on Hac5 is integrating Grapefruit with Hpysics.

Tonight we held an IRC meeting where this and other goals of Grapefruit were discussed. The main points (regarding Hpysics) are:

There are people interested in Hpysics (and particularly in Hpysics+Grapefruit)
There should be no problems to integrate Hpysics with Grapefruit. However, in the new version of Grapefruit there are no means of visualization yet. We'll need to tackle this at Hackathon, too.

Recent activity

2009-03-27T00:07:00.004+03:00

For now, I rewrote Hpysics to use plain lists instead of parallel arrays. I will investigate DPH applicability a bit later, when I fix some other things.

Also, there's now an issue tracker for Hpysics.

DPH docs and project status

2008-12-02T19:10:00.003+03:00

DPH devs finally updated the documentation on using Data Parallel Haskell!

To talk about Hpysics, as I've figured out the code was not properly vectorised, and this is probably the main reason of bad performance. Working on it.

The Monad Reader, SoC special

2008-11-20T10:41:00.002+03:00

The Monad.Reader Issue 12 is now out. It contains my article on physics engine implementation as well as articles from other SoCers, Max Bolingbroke and Neil Mitchell, and wonderful poetry by Wouter Swierstra, the editor.

Thanks to Thomas Schilling and Roman Leshchinskiy for help with the article.

Status report: week 11-12

2008-08-12T15:35:00.004+03:00

As I wrote before, I added complete support for polyhedra and fixed collision handler.

Also, I made a little optimization to collision detector: bounding spheres. The idea is that testing spheres for collision is faster than testing polyhedra. Also, if we consider sphere with center in body's center of mass, it's rotationally invariant.

Then I spent some time trying to compile head GHC and DPH. My (not so pleasant) experience is described here.

When I succeeded, I wrote simple benchmark to evaluate gains from using bounding volumes. Result was disappointing -- simple 2-step simulation with 10 bodies took 9 seconds and almost 1Gb of memory to complete. After consulting with my mentors we concluded that vectoriser is not ready yet (delay is due to issues with GHC build system) and that I should postpone benchmarks for a while.

So, my plans for nearest future is to implement static bodies and BSP trees (I already started the latter). Until 21 of August I will be teaching at summer math. school, and then I will continue the work.

Also, I'll be writing SoC report for the Monad Reader soon. If you'd like some particular issue to be explained or highlighted there, feel free to tell me!

Physics and polyhedra

2008-08-06T08:55:00.008+03:00

Thanks to my fellow physicist, Oleg Matveychuk, I've done with the collision handler bug I said in the last status report. That was indeed a mistake in the paper (Collision Detection and Response for Computer Animation).

One of the collision equation in that paper looks like

Here, is linear and is angular velocity of each of two bodies, is the vector pointing from center of mass to collision point, and is normal to collision plane. The expression in parens, let's call it , is relative velocity of collision points of two bodies. So, Moore and Wilhelms propose to set to 0.

It appears that this corresponds to completely unelastic collision (with restitution coefficient equal to 0), and that's why it doesn't look too realistic.

If we have coefficient of restitution , then proper equation is , where is taken after collision and before.

Another thing I've done is support of generic polyhedra. For example, now we can experiment not just with cubes, but with parallelepipeds or tetrahedra. And in future this will help us to handle arbitrary shapes by approximating them with polyhedra, using point repulsion algorithm which I'm going to implement (it's also needed for semi-adjusting BSP trees).

Status report: week 9-10

2008-08-02T21:46:00.003+03:00

I'm back from IMC at Bulgaria with second prize, and ready to work!

While I was away I thought about generic convex polyhedra and actually started implementing them. I hope to finish that in a few days. This not only makes engine practically more useful but also makes some computations more cheap and robust.

Also I discovered some problem with my last collision handler. It conforms to one paper, and now I doubt that paper is correct. I'll consult local physicists in the nearest time.

Finally, I read several papers on broad-phase collision detection. The one I liked most is Broad-Phase Collision Detection Using Semi-Adjusting BSP-trees. So I'll start implementing it as soon as possible.

Status report: week 7-8

2008-07-22T20:32:00.002+03:00

Last week I've implemented full handling of rigid bodies collision. When two bodies collide, not just they velocities, but also their angular velocities are modified, as it is in real world.

Now, supposing engine is correct (it needs more testing, though), need to make it fast (after all, this is what Data Parallel Haskell is about).

One of the obvious optimization is to perform broad-phase collision detection, that is, to filter out pairs of bodies which certainly cannot collide and run collision detection algorithm (which is then called narrow-phase) on the pair of bodies left.

So, I'll need to study the subject and choose algorithm which is best suitable for nested data parallelism. And there will be good chance for that — I'm leaving to participate in IMC.

I've printed four papers describing broad-phase collision detection and will study them while I'm away (well, maybe I'll even find time to code something).

Double buffering & demo

2008-07-08T14:34:00.004+03:00

With help and patches from kpierre and excid, Hpysics' visulization code now performs double buffering, which makes it much more pleasant for eyes. Also this allowed me to record a demo.

Ogg Theora version [2.1M]
YouTube version (but their player doesn't go well on this video for some reason)

QuickCheck puzzle: the answer

2008-07-08T12:56:00.004+03:00

Some time ago I mentioned a problem I've run into with QuickCheck: the following code, intended for generation of non-zero random vectors, does not terminate:

nonzero :: Gen Vec
nonzero = do
  v <- arbitrary
  if norm v > 0 then return v else nonzero

Now it's time to give the answer to this puzzle, which was found by Dmitry Astapov (ADEpt). Test data generators have an implicit size parameter, which is passed down in monadic computation. So if we got zero size, we will always get zero vectors -- "arbitrary" vectors with components from interval [0;0]. So, solution may look like

nonzero = do
  v <- arbitrary
  if norm v > 0 then return v else resize 1 nonzero

Status report: week 6

2008-07-08T01:40:00.004+03:00

Well, it was too optimistic to think that V-Clip is working properly. Number of bugs, errors and just stupid mistakes was sufficient to keep me busy till now. (Although they were not only related to my V-Clip implementation, but to simulation algorithm too, and also I found -- and fixed in my implementation -- an error in V-Clip paper itself -- I'll probably write about this later.) But I have good news :)

{- Here a demo video supposed to be, but unfortunately I can't get it of acceptable quality, so you're encouraged to build and run vis.hs. -}

As you can see, V-Clip isn't only consuming CPU time, but really detects collisions. Although this demo might seem physically realistic, it isn't -- only linear, but not angular velocities are updated during collisions. This is what I'm going to do this week.

Aside from fixing bugs, I also improved simulation code -- now it guarantees that during collision opposite impulses are applied to bodies, and also makes twice as little collision checks.

V-Clip seems to work!

2008-07-02T01:15:00.002+03:00

Finally, I've got V-Clip working. At least now (after one bugfix) it always terminates -- quite encouraging for such algorithm!

*Properties> quickCheck prop_VClipTerminates 
OK, passed 100 tests.
32% Done, ("Edge","Edge").
14% Done, ("Edge","Vertex").
11% Done, ("Vertex","Edge").
10% Done, ("Face","Vertex").
8% Penetration, ("Face","Vertex").
8% Done, ("Vertex","Face").
7% Done, ("Vertex","Vertex").
5% Penetration, ("Vertex","Face").
3% Penetration, ("Face","Edge").
2% Penetration, ("Edge","Face").

The next step in testing will be visualizing cubes collisions -- and I'm still moving towards rotation!

Status report: week 5

2008-06-28T19:16:00.006+03:00

This week I was implementing Mirtich's V-Clip algorithm for collision detection.

Also I found several bugs in my functions, which took some time to fix. To check the code I used QuickCheck properties. I expect to finish V-Clip during the first half of the following week, if everthing goes fine.

I also found time to cabalize and haddockize Hpysics. Note that you need haddock 2 to build docs, because earlier versions don't like parallel arrays syntax.

Also, there was an interesting challenge with QuickCheck. To test some things I need to generate non-zero vectors. I tried the following:

nonzero :: Gen Vec
nonzero = do
  v <- arbitrary
  if norm v > 0 then return v else nonzero

(i.e. if we got zero vector, just generate another one until we get what we want), but for some reason this code doesn't terminate. To understand why, I probably should learn more about how QuickCheck's rng works, but I won't complain if someone explains this effect :)

V-Clip algorithm (status update)

2008-06-25T00:17:00.002+03:00

Finally, I've found an algorithm which should be relatively easy to implement. It is Mirtich's V-Clip algorithm described in this paper.

It is similar to Lin-Canny algorithm (they both are based on Voronoi regions and even uses the same theorem), but advantage of V-Clip is that it avoids finding the closest points of two features (that was the problem I could not resolve last week).

So, I'm going to dive deeply in the paper and try to implement that algorithm.

Status report: week 4

2008-06-20T17:40:00.003+03:00

This week went not so good as I was planning.

I wanted to implement simple ad-hoc cubic collision geometry to test collisions with rotation. So I started with calculating closest features of two polyhedra (this would also be useful for Lin-Canny algorithm), but when it came to faces it became too cumbersome (and this part isn't very extensible, because it deals specifically with squares, not generic polygons).

So, I decided to spend some time reading papers on this topic and looking for acceptable solution.

If I won't find anything better, I'll end up implementing Lin-Canny algorithm (I don't want to do this atm, because it's not very simple and requires some reorganizing of simulation process). As always, suggestions are welcome!

Status report: week 3

2008-06-13T17:11:00.002+03:00

This week I devoted to rotation. To test it I added cubic shape.

I use quaternions to represent orientation of body in space (see Quaternions and spatial rotation).

To integrate orientation of body over time, numerical methods of solving differential equations are used. Currently I use Euler method, but it can be easily replaced by any other, see Hpysics.ODE. Differential equation itself is produced by Hpysics.Simulation.rotationDE.

Finally, I added rotation visualization, so if you compile vis.hs, you can watch falling rotating cube.

Next, I need to handle collisions properly with respect to rotation. So, I'll need to implement collision detection for cubic shape, and when bodies collide, angular momentum should be added in addition to linear.

I also think about documentation, which should be added at some point. On the one hand, haddock is convenient with its hyperlinks. On the other, literate haskell is interesting alternative. It can be less formal and more descriptive then haddock.

Status report: week 2

2008-06-07T21:12:00.001+03:00

During this week I dived into OpenGL and finished with a simple visualization. It isn't very fancy, but at least now I can say engine produces some physically plausible results.

Another achievements include rewriting vectors as data types and writing few unit tests.

The next thing I'm going to do is to add some 3d physics, namely, friction, restitution and rotation.

Status report: week 1

2008-05-29T12:07:00.000+03:00

So far, I have physics engine which:

Handles static and dynamic bodies
Deals with spheres and planes
Detects collisions and treats them as completely elastic and frictionless

These are global TODOs:

Rotation. I deliberately chose such shapes that aren't sensitive to rotation, but this need to be done anyway. As I see, only two things are needed: to respect angular velocity during integration and to apply torque during collision.
More shapes are needed to test rotation. It will be good to implement generic polyhedra.
Friction and restitution. There are problems with these, because coefficients of friction and restitution depends on two bodies (i.e. you cannot directly derive them from the properties of separate bodies). I'll need to investigate how this is implemented in other PEs.
Some code is currently suboptimal (e.g. some calculations are duplicated)

Plans for the next week:

Visualization. It's the best method of testing that I see.
Restitution and friction
Types. Currently I use lists for vectors, but as Manuel Chakravarty pointed out, this prevents compiler optimizations, so it's better to use explicit datatypes. Shouldn't be much of work.

The first day

2008-05-26T20:15:00.000+03:00

Today my coding period has started.

Some initial code is darcs-pushed to http://code.haskell.org/hpysics. Now I want my mentors to look at the data structures I've defined and tell me if some of they won't play nicely with NDP.

Then, my nearest plans are to get basic collision handling working. Also, though I planned visualization for the late June, I probably will do it earlier -- it's very tempting to see your physics engine produces plausible results.

Literature

2008-05-23T15:50:00.000+03:00

This book will be my bible during this summer: This is printed Brian Mirtich's thesis about rigid body simulations.

Wiki page

2008-05-13T20:34:00.000+03:00

I've started a wiki page for hpysics. It summarizes what I've learnt about existing physics engines.

The Name

2008-04-26T16:08:00.000+03:00

Most of the SoC projects deal with existing projects. However, I'm going to create the new one. And every project needs some name.

So for now I'll pick up the codename hpysics — it's "physics" with two first letters swapped. The first "h" indicates that engine is written in Haskell (this is a convention which lots of Haskell projects use).

Maybe I'll change the name at some point, so if you have some suggestions, please share them!

Learning

2008-04-25T00:57:00.000+03:00

There are lots to learn about physical simulations before the coding itself starts. There is a great collection of links on reddit on the topic. Currently I'm attracted with MIT video lectures on Classical Mechanics (to refresh the knowledge got in school) and with these lecture notes which contains quite good list of links to apropriate papers.

Intro

2008-04-22T08:17:00.000+03:00

Hi all!

My name is Roman Cheplyaka and my proposal Data parallel physics engine was accepted for Google Summer of Code 2008. My mentors are Manuel M T Chakravarty and Roman Leshchinskiy.

In this blog I'll write about everything interesting I'll learn during this project, and also about my achievements and problems.

Please feel free to annoy me with your suggestions, advices or comments of any kind :)