next »

[st33d]

I'm using a marching squares algorithm to plot out the polygons I'll need to collide with in my engine.

But I'm using separating axis to resolve the collisions - which means the polygons must be convex.

I'd like to reduce my concave block into the least number of concave rectangles.

Before my head explodes, does anyone have any suggestions on how to go about it?

To sweeten the deal, in true st33d style I'll be uploading the solution when we get to one.

[skyy]

Rectangle packing... ahh.. enjoy. It's a proper way to get destroyed. I have worked on this problem on few different projects.

But yeah, check these out:
- http://www.blackpawn.com/texts/lightmaps/default.html (I used a modification of this in one of my projects to do rectangle packing)
- http://grial.iiia.csic.es/~marti/wordpress/wp-content/uploads/2007/03/packing.pdf
- http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing/

Random bibs on it:
- http://en.wikipedia.org/wiki/Bin_packing_problem

But I definitely recommend the first one. It wasn't anything magical but got me started a year ago when I did it for the first time.  

Have fun and hopefully some of those links give some idea on rectangle packing.

[Ivan]

I used that same tutorial (the first one) as well when i was writing lightmapping code for my engine.

[BorisTheBrave]

This is not a packing problem, it is a tessellation problem. The distinction 1) is you must fully partition the enclosing space, waste is not accepted, and 2) The shapes you are "packing" are not so important, and frequently unconstrained.

A wide variety of algorithms exist for arbitrary polygons. The most common ones first triangulate the shape into triangles (which are always convex), and then seeks to build polygons back up, but I have seen some with work with polygons. Most are O(n log n).

If you want something simple, which can make use of the fact you've come from marching squares (which gives only 8 directions of lines, right?) try this: divide up the polygon into vertical strips 1/2 a block, which must be convex. Then attempt to merge adjacent ones. Using a library is of course even simpler.

[raigan]

I'm confused about "concave rectangles".. ?! 

[Zaphos]

I'm using a marching squares algorithm to plot out the polygons I'll need to collide with in my engine.

Is this giving you arbitrary polygons or just an outline of a bunch of tiled squares?  If you're colliding against tiled squares, why not just skip the marching squares+separating axis, and use the tile map directly as your collision data structure?  Or, if you don't want to collide against a tilemap, you could convert the tiles to large rectangles with a simple RLE algorithm (which is not going to be an optimal packing, but is simple and fast and often effective).

[st33d]

If you're colliding against tiled squares, why not just skip the marching squares+separating axis, and use the tile map directly as your collision data structure?

The character is a line. I have to do polygon collision.

The issue here is toe-stubbing. If there's breaks in a surface then that may lead to the line getting buried between two polygons as separating axis tries to shove it to the nearest edge.

Which was why I went down this road, because that's what was happening.

So it's actually a specialised form of packing really - What I actually need are unbroken surfaces.

I'm confused about "concave rectangles".. ?! 

Never seen a convex rectangle? Pah, some programmer you are. 

But yeah, check these out:
- http://www.blackpawn.com/texts/lightmaps/default.html (I used a modification of this in one of my projects to do rectangle packing)
- http://grial.iiia.csic.es/~marti/wordpress/wp-content/uploads/2007/03/packing.pdf
- http://kossovsky.net/index.php/2009/07/cshar-rectangle-packing/

I'll muse over these this morning. Fortunately this is a work problem, so I'm being paid to figure this one out.

[st33d]

Okay, so here's marching squares for you on wonderfl:

http://wonderfl.net/code/f4e0c27903a3992c257da1f40ce300cabdf4db18

You're welcome to fork it and optimise it if you want.

[Zaphos]

If you're colliding against tiled squares, why not just skip the marching squares+separating axis, and use the tile map directly as your collision data structure?

The character is a line. I have to do polygon collision.

Lines can do tilemap collision.  You just 'raster' the line onto the tilemap, using an algorithm that touches all the tiles the line touches.

The issue here is toe-stubbing. If there's breaks in a surface then that may lead to the line getting buried between two polygons as separating axis tries to shove it to the nearest edge.

Which was why I went down this road, because that's what was happening.

Hmm, another solution is to do something smarter when finding the 'nearest edge'?  It sounds like you're saying you have two adjacent rectangles, and you find as your nearest edge the shared edge between the two?  Some extra special-case code should be able to pretty easily recognize when this is happening, and use a different nearby edge in this case ....

So it's actually a specialised form of packing really - What I actually need are unbroken surfaces.

What do you mean exactly by 'unbroken' surfaces?  Unless I'm misunderstanding the term, wouldn't this requirement make convex decomposition impossible?

[st33d]

You're right, I've realised that the squeezing problem is unavoidable.

My guess is that from all the collision tests, the deepest penetration should dictate the winning resolution (and I'm using preventative collision here - there will be no jitter - I will test for the best result).

When I get back to work, I'm going to run a worst case scenario of all tiles as squares and see if it works.

But if it does work, then I have the secondary issue that I could break the whole level down into simple polygons.

My co-worker made Ice Breaker and his convex polygon making routine went along the lines of testing for all intersections. Which works well for a single cut because the cpu jump on one manuvre is not noticable. But of course he's not using just rectangles like I am. And I was considering making these polygons on the fly.

But I'm going to run into the squeezing issue regardless, my coder sense of future projections tells me there will be a situation where it will occur. But having the level cached as simple convex shapes would be nice.