Tuesday, July 22, 2008

Status report: week 7-8

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

Tuesday, July 8, 2008

Double buffering & demo

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.

QuickCheck puzzle: the answer

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

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.

Wednesday, July 2, 2008

V-Clip seems to work!

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!