Pixel Based Collision Shapes ?

[theanzelm]

Hi!

I'm 14, from Germany and you will probably call me insane:

I'm planning and programming a 2d game engine mainly based on SDL.

I wanted to implement my own pixel-perfect physics engine.
Pixel Perfect means in this case, that the physical object's shape is defined by how their sprite looks.
The advatage of this is, that you don't have to think about a shape of something, you just design it
in Photoshop or Gimp, you have an image, and the non-transparent pixels also are the physical shape of the object.
Also it is more accurate than any shape approximation like boxes or circles.

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.

So I started all over in C++.

I'm very impressed by Chipmunk Physics, because of its high performance and stability.

Now I had the Idea of just adding a new type of collision shape to the engine,
a pixel-based one.

Then you could use either polygon shapes, or pixel-based shapes together,
what would, in my eyes, be a perfect balance between performance, accuracy and simplicity.

What do you think of this Idea? Would it be hard to implement?
Any suggestions?

If you don't say its a completely insane and dumb idea I will try it and see.

Thanks for any tips and sorry for my English.

Anselm

[X-0ut]

Find the contours of the alpha channel. Plot points. Sort them into an order like CW or CCW. Form segments between each point. Use a threshold so that only a new segment is formed
based on some angle. Remove colinear segments.
Next triangulate the remaining segment points - EAR is good for this.
Break it down into multiple convex shapes.
All done

[theanzelm]

This is a good idea.

Do you think a algorithm converting the pixels to polygons is fast enough to be able to change the shape in realtime?
I definetly need that.

[Pipo]

Hi, I'm 14, from France, and you're not insane (or I'm insane too )

No, a such alogrithm isn't fast enough.

For more performance, you should create, for each sprite, a mask containing the image's collision pixels. Thus, the algorithm will have fewer pixels to process. You will also be able to use different colors in the mask, with different attributes (exemple: red for "offensive" pixels, green for "defensive" pixels and blue for normal collision pixels.

I did a such algorithm one or two months ago in ruby, I can give you the source code with explanations, if you want it
I haven't done any performance test, but it is optimized for occasional contacts. Use Chipmunk physic engine for persistent contacts(like between an object and the floor).

[theanzelm]

Good to know you're insane too ^^

It's the question,
collision masks are slower for collision detection,
but easier and faster to change in runtime.

Polygons are faster for collision detection,
but its slower, when you change the sprite,
to recalculate it's polygons.

BTW in chipmunk only convex polygons are possible?
That wouldn't be so good.

In my old engine I did the stuff with the collision detection( what means, comparing pixels ) within my C extension.
Are you really doing it in pure ruby? I don't think this is fast enough.

But thanks for the offer!

[Pipo]

In my old engine I did the stuff with the collision detection( what means, comparing pixels ) within my C extension.
Are you really doing it in pure ruby? I don't think this is fast enough.

The algorithm I started is optimized for occasional collisions. For persistent contacts, like an object on the floor, or for two objects imbricated, chipmunk is much faster. For ocasional contacts and dynamic shape with pixel-based collision detection, I think my algorithm is fast enough. Actually, it uses thes bounds of the mask as a bounding box, and if two bounding boxes are intersecting, the algorithm uses the pixel-perfect collision detection. If you use this in your C algorithm, it will be much faster

EDIT: I just did a performance test. 100 tests are done quasi-instantaneously if the two objects are not colliding, and in some 0,1 seconds if they are.
If it's not fast enough(my code is'nt really finished), I think you can optimize your C extension, with a mask system and a bounding box system

[theanzelm]

In the specific game I'm planning I need a lot of persistent contacts (tons of tiny objects stacking and building a wall).

For this I will use the standart shape types, but for the ground I think I'll use a mask, because it shuld be destroyable.


Thats exacty what my C Algorithm was doing.
First check the bounding boxes for overlap,
then in the overlapping area check for non-transparent pixels in both sprites.

With 5 Objects and sub-timesteps it starts to get slow.
With less timesteps I would get tunneling (especially for fast rotations).


Or is it easy to change the polygons (or line segments, because its static and they can be concav) of the ground at runtime, for example, when it gets hit by something.

[Pipo]

then in the overlapping area check for non-transparent pixels in both sprites.

Mmmh... In your algorithm, how do you "check for non-transparent pixels"? Maybe this is the problem. If you are using a method to get the transparency of each pixel at runtime, it will be very slow. You should store all the collision pixels of each sprite in an Array(if the sprite is animated, you have to do this with all the frames), and then use these arrays for collision detection. It will be much faster!

[Blue Prawn]

Hi,
I don't know if it would help you to look at other similar projects,
maybe you know these yet, but in case not, here are some:
http://www.allegro.cc/resource/Libraries/Graphics/pmask
http://www.allegro.cc/resource/Libraries/Graphics/ppcol
it seems that the first one works with SDL too
regards

[theanzelm]

No that's not really what I need, it wouldn't be a problem for me to program this mask collision detection.

But do you know where i can find such an algorithm to calculate polygons from pixels,
or do you have any tips about it?

Thanks guys