Generate a vector outline from an image?

[clofresh]

Hey,

Does anyone have a good tool to generate a vector outline from an image's alpha channel? Either in lua, or maybe a standalone tool or gimp plugin.

I wanna create collision polygons around transparent pngs that HC can use for collision shapes, so the outline doesn't have to be super accurate, but should be tighter than a rectangle or circle.

[ivan]

In terms of the tools, there are "potrace" and "autotrace"
(both are used via the command line and are used by 3rd party applications like Inkscape/fontforge)
potrace can generate .geojson which is very easy to parse in Lua.
The output is sometimes large so you have to tweak the settings.
In terms of Lua techniques, you have the "marching squares algorithm"
which is fairly easy to understand and implement, but it's hard to make it robust.
After running marching squares on an image, you have to adjust the output so that it looks smooth.

I have to end the post by saying that iso/contour tracing is not an easy problem.
Sure, you can put something together, but it's way too complicated to tackle the problem on your own.
Good luck!

[pgimeno]

Inkscape has a built-in trace tool.

With Gimp, you can save the alpha by copying it to a layer mask (Layer > Mask > Add Layer Mask > Layer's Alpha Channel), then Select All (Ctrl+A), Copy (Ctrl+C), Paste as New (Ctrl+Shift+V). Export it and load it into Inkscape.

Once in Inkscape, use Path > Trace Bitmap.

The problem is now to load it into Lua

[ivan]

Inkscape has a built-in trace tool.

and it's called "potrace"

[clofresh]

Thanks for the tips! I figured it would be an algorithmically complex problem. I tried pgimeno's method and it seemed to generate too complex of a vector, so I started googling around for the tools and terms you mentioned, and realized that what I want is a convex hull. That led me to opencv's example convex hull finder:

hull.png (107.36 KiB) Viewed 8863 times

Looks like a pretty good approximation for a collision shape. Now to figure out how to export the data!

[ivan]

Tracing tools are great if you are doing graphics.
The output will often contain Bezier curves unless you find a good output format (as I mentioned potrace with geojson is great in my experience).

As for collisions, then you'll get a better approximation using a combination of circles and rects.
Like for example, the ship in your picture could become a circle with a rectangle on top (doesn't matter if they overlap).
On the other hand, convex hull won't work too well for concave shapes like a cross ("X") or the letter "H".
Good luck!

[Alexar]

Code: Select all

function math.convexHull(verts)
	local v={}
	local rt={}
	local lastK=0
	local lastX=0
	local lastY=0
	local lastRad=0
	local v_c=#verts/2
	for i=1,v_c do
		v[i]={}
		v[i].x=verts[i*2-2]
		v[i].y=verts[i*2-1]
	end
	local maxY=-1/0
	local oK=0
	for k,v in pairs(v) do
		if v.y>maxY then
			maxY=v.y
			oK=k
		end	
	end
	lastK=oK
	lastX=v[lastK].x
	lastY=v[lastK].y
	table.insert(rt,v[lastK].x)
	table.insert(rt,v[lastK].y)
	local i=0
	while i<100 do
		i=i+1
		local minRad=2*math.pi
		local minK=0
		for k,v in pairs(v) do
			local rad=math.getRot(lastX,lastY,v.x,v.y,true)
			if rad and rad>lastRad then
				if rad<minRad then
					minRad=rad
					minK=k
				end
			end
		end
		if minK==maxK or minK==0 then return rt end
		lastK=minK
		lastRad=minRad
		lastX=v[lastK].x
		lastY=v[lastK].y
		table.insert(rt,v[lastK].x)
		table.insert(rt,v[lastK].y)
	end

end

here is my code snippet that I converted for the one in language C. hope it can help you.

[davisdude]

This may be a little easier to read, being broken up into multiple functions

Code: Select all

-- p0 = { x, y }
local function orientation( p0, p1, p2 )
    return ( ( p1[1] - p0[1] ) * ( p2[2] - p0[2] ) - ( p2[1] - p0[1] ) * ( p1[2] - p0[2] ) )
end

-- Points need to be sorted by x for this to work
local function hull( points )
    local stack = { points[1], points[2] }
    for i = 3, #points do
        while #stack >= 2 and orientation( points[i], stack[#stack], stack[#stack - 1] ) <= 0 do
            table.remove( stack, #stack )
        end
        table.insert( stack, points[i] )
    end
    return stack
end

local function sortByX( points )
    table.sort( points, function( p1, p2 )
        return p1[1] < p2[1]
    end )
end

local function reverse( points )
    local new = {}
    for i = #points, 1, -1 do
        table.insert( new, points[i] )
    end
    return new
end

function convexHull( points )
    -- Using the "monotone chain" algorithm
    -- Copy table to prevent modification
    local points = { unpack( points ) }
    sortByX( points )
    local upper = hull( points )
    local lower = hull( reverse( points ) )

    -- Exclude first and last points of lower, as they're duplicates
    table.remove( points, 1 )
    table.remove( points, #points )
    for i = 1, #lower do
        table.insert( upper, lower[i] )
    end
    return upper
end

[gcmartijn]

I know this is a old topic, but it is I guess the correct place to ask this question.
I don't want a concave hull but the exact simplified outline (contour) from a transparent png file.

After many road's taken, I did post my full question here:
https://stackoverflow.com/questions/640 ... rect-edges

And thought maybe love2d can output this for me?
After all I'm going to use the polygon inside love2d.