In the last day or so I've thrown together a rigid body dynamics library, and I would be very grateful if some others could try my first test program to see (a) if it works at all; and (b) if it works flawlessly on their machines?

Screenshot:
{"name":"RigidBodies.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/7\/574106eb320d7e68f8d6124cad6c88a0.png","w":640,"h":502,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/7\/574106eb320d7e68f8d6124cad6c88a0"}

Download links:
Windows
Mac

Use cursor keys to move about. It uses my usual game framework so other keys of note are:
Alt+enter — enter/exit full screen mode
H — toggle high resolution display while in full screen mode
M — toggle multisampling
ESC — quit

The window can be freely resized.

It's OpenGL based and shouldn't use much CPU. It uses about 5% on my machine.

Works really great!. add more objects so we can play more .

Windows version works beautifully here. Nice work.

I'd love to try it on my Linux Core2Quad. I can test in a VM in windows if you like, but I'd like to try linux.

Hmmm. I don't know if it's really ready for a stress test yet. I have several mechanisms for reducing the number of tests that are actively done, but mostly obvious stuff. I've written and put most of this together in the last 24 hours or so, so I need to go away and think about it more, or else read some articles.

Technical details, because I know everyone loves them:

All shapes are convex polygons. A minimum bounding circle is calculated¹. Collisions are tested first as a bounding circle test, then a full blown Minkowski sum². Convex shapes know their position and orientation.

Rigid bodies contain a convex shape, along with velocities. They can react to collisions by adjusting position and velocity as necessary. They also have a simple Euler integrator for progressing state.

A rigid body collection hold a whole bunch of rigid bodies. It uses a sweep test³ based on the bounding circles to limit collision tests, and otherwise ensures all collisions are handled.

Total length of physics code is about 850 lines, including headers. I'd release it as a library if Chipmunk didn't already do everything I do plus more, and better. Mine is less than 10% the size of that, but only because I've specialised myself to polygons, with no joints.

¹ yes, the genuine minimum bounding circle, not an approximation. Uses the "for each pair of points in the shape, add a potential circle that is centred between them and just touches them", "for each triplet of points in the shape, add their circumcircle as a postential", "remove all potential circles that don't cover everything", "pick smallest of remaining circles" algorithm.

² the shapes are all convex, and their points all wind the same way, so this is easy. It can be as simple as a merge sort on edges, according to their angle with a fixed line (e.g. the horizontal), but right now I spend a little too much time figuring out how far outwards to push the edges so my code isn't quite optimal.

³ i.e. work out a minimum and a maximum x for all objects. Put them in a list and sort it by min x. Run through list and test each item with everything further down the list that has a min x less than this objects max x. Keep the list from frame to frame, use insertion sort to resort it because insertion sort is very cheap on lists that are already nearly sorted.

EDIT: Give me a minute and I'll package up the source, though it contains a whole load of 'junk' because I've just built it on top of my normal game framework.

EDIT2: source code & my own documentation of all the physics functions are attached. You'll need SDL, SDL_image and SDL_mixer (the latter two because of all the other stuff included in my game framework). I've just included the documentation for the curious, it's not quite complete, but probably would be if I added: all angles are in radians, points must currently be added to convex shapes in anti-clockwise order (if you think of the axes set up as on graph paper, not in the normal computer screen way).

Yep, very nice. Next thing I'd like to see is how your lib handles stacking objects. That's always a tough one to get right from what I've seen.

I expect it would explode and cry! I haven't thought even slightly about the problem, as I am mostly putting it together for an overhead style game, where there is no meaningful concept of stacking.

EDIT: due to the fact that I've just posted to this thread twice in quick succession, I just feel the need to underline that I've attached source to my previous post, for Thomas Fjellstrom and any other Linux-types.

Worked fine on Vista. Your screenshot showed white objects but in the demo everything was red. Is that a wierd bug?

Yes it is. But it's probably because, as I've just noticed, I have one too many glEnd()s. So it isn't strictly speaking valid OpenGL. Not that it matters too much, because I don't really intend to use that drawing function — it's just temporarily there as a test that data is going into that class and being organised correctly.

The loose one is at the bottom of EBGFConvexShape.cpp in the function "void CConvexShape:: Draw()", in the middle of some commented stuff, if that causes any similar Linux issues.

EDIT: aha! I managed to break the program myself! My attempt to push on to a valid state when possible doesn't seem ideally suited to the situation where the two objects of infinite mass (the two rotating things — they have infinite mass so that they won't move around in the linear sense, it's a poor man's joint) are constrained by an object of finite mass inbetween. Which is extremely hard to set up.

Better get back to it...

EDIT2: Okay, that was easier to fix than I thought. Oh well, I won't turn this thread into a development blog by posting every little change. I'll go away and think a bit more about everything.

Thanks for the help, everyone!

EDIT3: Oh, I should tell you all this: the program will leave a configuration file either in %HOME% on UNIX and OS X, in %APPDATA% under Windows 2000, XP and Vista, and any other with that environment variable set, and with the executable otherwise (which usually means in Windows 95/98). It'll be called either ".Destruction Derby.cfg" (UNIX/OS X) or "Destruction Derby.cfg" (Windows) and is a shocking 13 bytes long, storing your desired screen resolution/etc.

I was actually trying furiously to create that situation, but it was too hard.

Works flawlessly here. Uses less than 1% CPU, as well (1.8GHz Sempron, Geforce 6200A [256bit, 256Mb, 450/630 core/memory]). I was able to stop both rotating blocks by pushing against the larger one, though. I suppose that since I was using it as leverage, it's possible that is correct, however I would expect that both of the blocks combined should be able to push the player object away.

What do you plan on doing with this library? Will it be personal use, or publicly available? Will you show source? How will concave polygons behave?

No, I think that's right. Though I'll look into it, as I'm not 100% confident.

Oh, I have a few ideas for bits and pieces. I'm not really certain though. Mostly I'm just messing around. I usually enter ChristmasHack, maybe I'll keep it aside and see if I can use it then.

I always publish full source for my projects, as much so that I won't lose it as anything else. My members.allegro.cc site has almost everything I've ever worked on. The source code for this (minus my fix just now) is attached to a post up above.

I've no intention of handling them for the time being, as I'm not really familiar with the associated algorithms. I could put something together easily enough, but it'd be extremely inefficient. I will read up on Minkowski sums of non-convex polygons just in case it's easier than I think, but I'm happy enough with convex shapes.

Let me know how that goes. Although, I had a simple idea for handling concave polygons. You could just triangulate concave polygons and use whatever collision detection you are using now. Maybe that means you'll have more polygons to check collision against, but it should also be much simpler math and could possibly be faster. Perhaps I should also look at Minkowski sums, as I don't know much about them, and will probably be needing them for a project I'm working on myself.

Also, this looks promising.

By holding the left object, I managed to block both left and right objects for a few seconds. By the time I was sent backward into space, the right object was very slightly overlapping the left one.
http://www.allegro.cc/files/attachment/593099

where's the linux version???

Thomas attached the source to one of his earlier posts.

I totally missed that must have been an edit...

edit: DANGER! DANGER! Danger, Will Robinson, Exploding Zip Ahead!

edit2:

Heres what I did to build:

moose@natasha:~/build/THartePhysics/src$ find . -iname "*.cpp" | xargs gcc -W -Wall -ggdb3 -I/usr/include/SDL/ -c

Heres the warnings from that:

Heres the linking stage:
g++ *.o -o game -lSDL -lSDL_image -lSDL_mixer -lGL -lGLU

And heres what happens when I run it:

moose@natasha:~/build/THartePhysics/src$ ./game
Unable to open graphics mode!

The problem is that my current implementation needs to know complete separation vectors for every object. Which would mean decomposing both polygons into convex polygons (which could be done ahead of time, as they're rigid), then I'd need to compare every polygon of one shape against every poylgon of the other, then do a combine operation on all of them. Though that may just be because I'm being so picky about my collision stuff.

This is the combination of a limitation in my implementation and a bug that affects that limitation. Using Minkowski sums makes it extremely easy to figure out how objects should be moved so that they stop overlapping, but doesn't help at all with figuring out how objects could be rotated so that they stop overlapping. However, from a level design viewpoint it's really very inconvenient not to be able to place static objects.

Anyway, that's the limitation that should cause the two objects to interpenetrate a very small amount, then stick correctly.

The bug is that I have my ordering for applying forces and fixing for penetrations/contacts all messed up. That shouldn't be a tough fix.

Oh, yeah, I zipped it on OS X, which means it should have lots of useless .DS_STORE files in it (including at the root). Sorry about that! It's part of how OS X uses .zip files to store information that is in the Mac filing system but not storable in .zip files otherwise. I wonder what Sun do with ZFS.

Well that's peculiar. And I assume that plenty of other OpenGL applications, etc, work fine - i.e. I should definitely start checking my code?

I tried this yesterday, turns out not brilliantly. But I think I can fix that. The main problem at the minute is that I reduce every single collision to one contact point, but if boxes (or whatever) are sitting on top of each other then they should rightly have a contact patch. Luckily it isn't much harder to figure out a patch than a point from the way I have things set up. Sitting here (at work) now, I think it shouldn't be much harder than checking the Minkowski sum for adjacent parallel sides. And you should end up with one point on each shape (provided neither has any parallel sides in its original geometry, but I can just remove those in advance).

I also need a better way to aggregate things that need rechecking when I'm doing the final step of my world progression loop, as at the minute if anything is forcibly moved, everything is checked again. Which is stupid. Should just be a matter of keeping some handy flags.

Oh, I'm always doing that. I think perhaps I'm simple.

Anyway, thanks again to everyone for their comments!

Well GL does work here.

moose@natasha:~$ glxgears
82651 frames in 5.0 seconds = 16530.121 FPS
82455 frames in 5.0 seconds = 16490.940 FPS
83406 frames in 5.0 seconds = 16681.103 FPS
83781 frames in 5.0 seconds = 16756.157 FPS

Must be my code then! I'll look into it.