2d mesh building algorythim

[NoreoAlles]

Hey, does anyone got a algorythim that i can use freely, wich builds polygonal meshes made of squares from a map like this:

Code: Select all

map = {

{0,1,1,1,0},
{1,1,0,1,1},
{1,1,1,1,1}

}

It should connect all the 1s to one big mesh and if there are unconnected 1s they should make a new mesh.

[pgimeno]

You can use a flood fill algorithm to separate the meshes. A spritebatch is pretty much like a mesh; you can use that - unless you want mesh-specific features like custom vertex attributes or anything.

[NoreoAlles]

You can use a flood fill algorithm to separate the meshes. A spritebatch is pretty much like a mesh; you can use that - unless you want mesh-specific features like custom vertex attributes or anything.

I do got a spritebatch, i just need a way to make a box2d mesh out of that shape, im soryy if i didnt get that point accross, i am not so good at english.

[darkfrei]

Hey, does anyone got a algorythim that i can use freely, wich builds polygonal meshes made of squares from a map like this:

Code: Select all

map = {

{0,1,1,1,0},
{1,1,0,1,1},
{1,1,1,1,1}

}

It should connect all the 1s to one big mesh and if there are unconnected 1s they should make a new mesh.

The solution is a outline line of this given tiles
So every tile can have two lines: the horizontal one and the vertical one.
Iterate every tile and create the line for given tile and for tiles that are right or lower as the given tile; delete this flag by repeating as:

Code: Select all

for y = minY, maxY do
	for x = minX, maxX do
		-- this tile
		cellsMap[y][x].v = not cellsMap[y][x].v
		cellsMap[y][x].h = not cellsMap[y][x].h
		-- right tile border
		cellsMap[y][x+1].v = not cellsMap[y][x+1].v
		-- bottom tile border
		cellsMap[y+1][x].h = not cellsMap[y+1][x].h

So the map

Code: Select all

map = {
{0,0,0,0,0},
{0,1,1,0,0},
{0,0,0,1,0},
{0,0,0,0,0},
}

borders-64.png (3.51 KiB) Viewed 1361 times

has lines by positions:

Code: Select all

{x=2, y=2, v=true, h=true},
{x=3, y=2, v=false, h=true},
{x=4, y=2, v=true, h=false},
{x=2, y=3, v=true, h=true},
{x=3, y=3, v=false, h=true},
{x=4, y=3, v=false, h=true},
{x=5, y=3, v=true, h=false},
{x=4, y=4, v=false, h=true},

And then you can convert this outline lines to one or two polygons.

[pgimeno]

I do got a spritebatch, i just need a way to make a box2d mesh out of that shape, im soryy if i didnt get that point accross, i am not so good at english.

Hm, Box2D mesh?

Box2D can only handle convex shapes, which for tile-based shapes means rectangles. If you have something more complex, you need to make a body with multiple fixtures, each with a shape. For simplicity, you could have square shapes with the positions in the grid and add as many fixtures as there are squares belonging to each block; I don't know if that would behave sanely though.

[NoreoAlles]

I do got a spritebatch, i just need a way to make a box2d mesh out of that shape, im soryy if i didnt get that point accross, i am not so good at english.

Hm, Box2D mesh?

Box2D can only handle convex shapes, which for tile-based shapes means rectangles. If you have something more complex, you need to make a body with multiple fixtures, each with a shape. For simplicity, you could have square shapes with the positions in the grid and add as many fixtures as there are squares belonging to each block; I don't know if that would behave sanely though.

I did that with a body, shape and fixture for each individual block, wich made me get caught on the edges of blocks, but i didnt think just using one big body.

[pgimeno]

Joints are elastic, while bodies with multiple fixtures/shapes are rigid. Still, depending on what you mean by "get caught on the edges of blocks", you may still have trouble if you do it that way.

If that causes problems, the next step would be to find the contour and decompose it into convex shapes. Ideally, a proper convex polygon decomposition algorithm should be used to create the shapes, so that there are as few as possible. I haven't found any convex polygon decomposition library in Lua, though. Maybe you can get away with triangulating the shape with love.math.triangulate, because triangles are convex, but that decomposition generates many more polygons than necessary, so it's not exactly ideal.