Generate a vector outline from an image?

General discussion about LÖVE, Lua, game development, puns, and unicorns.
Post Reply
User avatar
clofresh
Citizen
Posts: 87
Joined: Sun Jul 26, 2009 4:21 pm
Contact:

Generate a vector outline from an image?

Post by clofresh » Sat Aug 27, 2016 11:01 pm

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.
----------------------------------------
Sluicer Games

User avatar
ivan
Party member
Posts: 1531
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Generate a vector outline from an image?

Post by ivan » Sun Aug 28, 2016 12:06 am

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!

User avatar
pgimeno
Party member
Posts: 1908
Joined: Sun Oct 18, 2015 2:58 pm
Location: Valencia, ES

Re: Generate a vector outline from an image?

Post by pgimeno » Sun Aug 28, 2016 1:23 am

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

User avatar
ivan
Party member
Posts: 1531
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Generate a vector outline from an image?

Post by ivan » Sun Aug 28, 2016 6:36 am

pgimeno wrote:Inkscape has a built-in trace tool.
and it's called "potrace" :)

User avatar
clofresh
Citizen
Posts: 87
Joined: Sun Jul 26, 2009 4:21 pm
Contact:

Re: Generate a vector outline from an image?

Post by clofresh » Sun Aug 28, 2016 1:47 pm

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
hull.png (107.36 KiB) Viewed 1748 times
Looks like a pretty good approximation for a collision shape. Now to figure out how to export the data!
----------------------------------------
Sluicer Games

User avatar
ivan
Party member
Posts: 1531
Joined: Fri Mar 07, 2008 1:39 pm
Contact:

Re: Generate a vector outline from an image?

Post by ivan » Sun Aug 28, 2016 3:43 pm

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!

User avatar
Alexar
Party member
Posts: 174
Joined: Thu Feb 05, 2015 1:57 am
Location: Chengdu,China

Re: Generate a vector outline from an image?

Post by Alexar » Mon Aug 29, 2016 12:47 am

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
Party member
Posts: 1154
Joined: Sun Apr 28, 2013 3:29 am
Location: North Carolina

Re: Generate a vector outline from an image?

Post by davisdude » Mon Aug 29, 2016 1:23 am

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
GitHub | MLib - Math and shape intersections library | Walt - Animation library | Brady - Camera library with parallax scrolling | Vim-love-docs - Help files and syntax coloring for Vim

Post Reply

Who is online

Users browsing this forum: No registered users and 7 guests