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]

[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]

[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:


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