Pixel Based Collision Shapes ?

[slembcke]

Woah, busy topic!

http://www.youtube.com/watch?v=Oecv7Cg9lCc

You are in fact not crazy. What you want is signed distance functions. Physics2D.net has them. He has code for transforming bitmaps into polylines, and then creating a signed distance function out of that. There are a couple downsides to SDFs, but in general they work very well in 2D. They can represent complex convex shapes and their performance scales to highly detailed polygons better than my SAT based primitives.

I've been thinking about adding SDFs to Chipmunk. The reason I haven't added them is because I haven't foreseen the need for them in my own projects. Not that I'm selfish, but due to finite amounts of time, that's what drives a lot of Chipmunk's features.

That being said, Chipmunk's collision detection was meant to be extensible. Implementing SDFs probably wouldn't be that hard, especially if you used the Physics2D.net code as a reference. Heck, he might even help you, as he's helped others implement SDFs in their engines.

Using circles as an example (cpShape.c/h and cpCollision.c) it shouldn't be too hard to figure out how to implement a new collision type. Basically, you just need constructors/destructors, a function that updates the shape based on the position of the body it's connected to, and functions for colliding with other primitives. In the case of SDFs, I could see it being good enough to just provide collisions with other SDFs and maybe line segments. If it works out well, I could even integrate it into trunk Chipmunk. Win-Win scenario.

[theanzelm]

That sounds interesting,

I'll look that I'll get into this stuff a bit more and try it out and let's see.

Would be really cool if I could particioate to chipmunk in this way. ^^

What does a function for colliding with the other primitives need?

Collision point, normal, and penetration depth?

[slembcke]

Collision point, normal, and penetration depth?

Yes. To clarify though, a list of collision points their normals and penetration depths.

[theanzelm]

Could you please explain me a bit what SDFs are?

I found some stuff in the internet, and from what i know now,
they are polygons, where the edges aren't defined by a specific position, but by their relative distances?

What are the advantages in contrast to the type of polygons you use?

[citrys]

I started to program it in Ruby with a self-made Ruby-sdl extension.
I got something running what behaved physically not too bad.

The main problem was performance.
If I had more than 5 little objects at once,
The fps got below 10 ^^

Certainly Ruby as an interpreted language is not the right thing.

Were you using SDL rotozooming every frame to redraw all of your objects?

From what I could tell, I ran into the situation that my app was creating and destroying SDL surfaces through per-frame rotozooming faster than Ruby's garbage collector could keep up. My memory usage was ballooning to hundreds of megabytes for a scene with 5 rectangles bouncing around. One of the Rubygame maintainers suggested that I switch to OpenGL sprites to solve that problem. I haven't switched implementations yet, but that problem may reveal itself to other Ruby SDL programmers.

[theanzelm]

that was not the problem, i prerotated the surfaces (without physics i had 60 fps),
but what I need is a description of what SDFs are in detail.

Would be nice

[theanzelm]

Finally I found something!

http://www.cs.unc.edu/~geom/PIVOT/Voronoi_Collide.pdf

I think this is exactly what we need.

I'll probably fight me throught this tomorrow.

[slembcke]

Well, that's not far off from what you would want to do. (I only skimmed it) Basically a signed distance function is a function that returns the distance to the closest feature of a shape for a given point. Points inside the shape have positive values, points outside the shape have negative value, and points on the shape's edge have a value of 0.

You can use this function to create a signed distance field (SDF). A SDF is basically a bitmap of the function. You generate a 2D array of values sort of like a height-map. To use the SDF for collisions when colliding two objects, you sample the vertexes of one shape in the SDF of the other (and vise versa). If the vertex has a positive distance, it's colliding. Generating the collision points from this is pretty straight forward, you already know the location, and penetration distance, calculating the normal can be done from the SDF or pre-calculated.

Creating an SDF from a polygon outline would be pretty easy if you didn't care about performance. For every point, find the closest point on each segment and find the closest one. Creating a poly outline out of a bitmap image to begin with is more difficult however. How much do you trace the contour originally, how do you simplify that, how much do you need to subdivide, etc.

Unless you are really want to do fancy deformable objects, I wouldn't bother with the hardware accelerated part. The GPU could generate an SDF pretty quickly, but I wouldn't bother with collision checking. Unless you could queue up all of the collisions at once, the communication costs would probably cost you far more than you would gain. ... and it would be complicated.

[theanzelm]

Thanks alot, things are now getting really clear.

with distance from a point to the shortest feature of the shape you mean
a line, wich perpendicular to the nearest line segment of the polygon, and which wents through the point?

[slembcke]

Not exactly. The closest point on a line segment could be along the line or one of the endpoints. So not just the perpendicular distance.