Vectorization of image in Java (triangles on top of image)

M2009 · June 22, 2009, 6:31pm

Alright, time to kick it up a notch. I’ve been thinking lately:

Say you have a 2D game seen from the side and the map is build using polygons. So when you build the map you need to place each polygon manually.

Imagine if there was a way to automate this - instead of building a map you draw a picture of how you want the map to look and then let the application build the map for you by filling what you have drawn with triangles (polygons).

Here’s a small example, the image drawn will be in black and white (black = air, white = ground). The yellow lines are the polygons that the application has calculated to fill the white space.

http://www.java-gaming.org/index.php?action=dlattach;topic=20699.0;attach=1426

Here’s how I would like the code to look:

VectorizationTool vt = new VectorizationTool(Color.WHITE);
ArrayList<Polygon> ground = vt.process(<image object>);
vt.setColor(Color.RED);
ArrayList<Polygon> lava = vt.process(<image object>);

There we have it, would be very simple to use. We create an instance of the tool where we say that the color white is the ground, then we process the image and get the polygons representing the ground in our map. All other colors that arent pure white will be ignored. Then we just switch which color to process and use the same image to get the polygons that should represent a “lava” type of ground. The “Polygon” object can simply be the polygon’s three corners’ X/Y coordinates measured in pixels. (0,0) would be at the top left corner of the image that is processed.

Now my question to you fellows is as follows: How would one go about implementing this thing? Is there already available source to look at, or maybe even something like this already exists in Java and is ready to use?

I’ve been searching the net for this a bit but come up short. There are many algorithms out there, but I’m not sure which one I want that does what I want it to do or which one that is most effective. Hopefully there are people on this forum that knows this better than I do, I’m not at all good at math so I bet there are plenty of people here that can advise me.

(In case this thread will become a success I will now write down some key words to help others to find this topic more easily by search in the future: trace bitmap to vector, Raster-to-Vector Algorithm, Vectorization, convert bitmap to polygons, convert image to polygons, image edges java, fill image with polygon java, polygon mask java, poly2mask java. Some of these “keywords” might make no sense but they are part of what I searched for in order to finally decide on the thread’s subject.)

thijs · June 30, 2009, 7:14am

You should lookup the marching squares algorithm:

It does exactly what you want, and the wiki entry links to a Java implementation.

M2009 · July 8, 2009, 1:46am

Hey thijs, thanks a lot for your reply! I’m glad this thread got one. That algorithm will be very useful, awesome that there already is a Java implementation of it too.

But it doesn’t do exactly what I want. What I get from that algorithm is the path through a object’s outline, from an origin and back to the origin. From this:

This would be returned: S, S, E, S, E, N, N, N, W, W.

That is the path around the ones representing the object in the code above. It can be parsed in order to take out the coordinates of every corner (every change in direction), and then the results of that can be parsed to remove unnecessary coordinates that follows the same direction (for diagonal lines). Then I would have the coordinates of the outlines of one object in the image.

However I figure this can’t discover many objects in one image. And it also won’t detect holes inside a object, like so for example:

And mainly, it won’t divide the object into triangles (like in my example picture). That’s the biggest problem. I guess some, if not all, of these things can be implemented somehow using the algorithm in some clever way, but I can’t figure that out myself.

Edit: Forgot to close a code tag.

thijs · July 8, 2009, 10:45am

About the multiple image issue:
Can’t you split them in a seperate images? You can identify an mask color for transparant pixels (fx black) in the image, which you can use as empty space for the marching squares algorithm or “cut” out seperate images from your map.

About the holes:
You could repeat the process for the marching squares from within the first transparant pixel you find within the bounds of the already vectorized outline in the image. That will give the vector outline for the hole.

About the triangles:
Once you have created the concave polygon for your image you can use a tesselator to split the concave polygon into triangles which the gpu can render. JOGL has a nice tesselator in the glu package, if you dont want to stick to jogl, there are plenty of others around. But be aware that the quality of these tesselators can vary a great deal, some cant deal with concave polys, other cant handle holes in polys etcetc. I know the opengl version is very robust and I believe Slick also has a good one for tesselating SVG shapes.

Good luck!

Thijs

M2009 · July 19, 2009, 11:36pm

Sorry for the late reply, haven’t read for a while.

Thanks for your thoughts, the JOGL tesselator sounds great! Did a search and came up with a few links which I’ll post now in case someone else needs them:
http://www.songho.ca/opengl/gl_tessellation.html
http://glprogramming.com/red/chapter11.html

Also found this which might be useful:
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
It’s for finding if a point is inside a polygon, not exactly related to this thread maybe but I’ll post it anyway since it may come in handy sometime.

Your suggestions are great. However I’ve been thinking that to solve the first “multiple image” issue maybe I can just remove the pixels of a found polygon from the original image before I look for another polygon?

Since you seem to know stuff I thought I’d ask if you also have a colution for removing unnecessary points from a polygon? Imagine this example:

This will generate four points too much, these points aren’t needed since if they were removed the polygon would look the same. The polygon have four corners, would be nice to have four points then instead of eight. Do you have any suggestion as to how unnecessary points can be detected? To be clear I have marked the points that are not needed with “X” here:

Thank you again!

bleb · July 20, 2009, 6:55am

Loop around the vertices of your polygon and examine every adjacent triple A-B-C. If B lies within some threshold distance of the line segment AC, then it can be removed. Keep looping around the vertices until no more vertices are being removed.

mh114 · July 20, 2009, 7:01am

[quote=“M2009,post:5,topic:33748”]
You could check the slope / angle of the line between point N and point N+1, and compare it to the line between point N+1 and point N+2 (or N to N+2). If it’s equal within certain margin, point N+1 can be eliminated. I’m sure there are better approaches, and I’m not sure if this approach even works for all shapes, but it’s worth trying. Unless other people come up with a better solutions, that is.

EDIT: bleb posted while I was writing this. Checking distance would work too, yes.

thijs · July 20, 2009, 9:01am

Additionally, you could have a look at http://www.vividsolutions.com/jts/JTSHome.htm

It implements many polygon operations (including the ones you asked about like simplifying polygons), its open-source so you could take a peek how they tackled it…

M2009 · July 20, 2009, 10:05pm

Wow that was answered quickly. Thanks guys, lots of good information.

Although I’m not sure what bleb meant with “threshold distance”?

I think you mh114 meant that I should check if the direction from A towards B is the same as the direction from B towards C, then I can remove B. I think it’s pretty math-heavy and requires stuff like Math.sin to be used, but it will work.

About your link thijs, I’m sure there could be lots of useful information on that site, however finding it seems to be a quest on its own. I will save the URL, but I wonder if it won’t be faster to do a search on the net instead of looking at the source of that project when I want to find out an algorithm. Is there anything in particular you think is good or useful in the JTS Topology Suite?

bleb · July 21, 2009, 8:59am

In a perfect world you could use 0 as the threshold, and collinear points would be culled and everything would be rosy.
However, floating-point imprecisions and the like will conspire to give you very small but decidedly non-zero values when you measure the distance between AC and B, even if they should be perfectly collinear. And so you must also use some small but non-zero value to compare against when deciding to cull or not.

It also gives you a handy way to vary the quality of the output polygons: small values will better match up with the input image but result in many vertices, larger values will give poorer quality but fewer output vertices.

bleb · August 25, 2009, 4:11pm

I’ve since had cause to actually implement this, and it fails miserably, especially with curves. :persecutioncomplex:
Turns out, you actually want to look for runs of adjacent vertices that can be approximated as a straight line -according to your threshold distance- and remove the extraneous vertices all at once.
Like so:

/**
 * Reduces the vertex count of a simple shape
 * 
 * @param input
 *           The shape to decimate
 * @param minFeature
 *           The minimum distance a vertex must be from the line
 *           segment between it's two neighbours in order to avoid
 *           decimation
 * @return The simpler shape
 */
public static Shape decimate( Shape input, float minFeature )
{
	PathIterator pi = input.getPathIterator( null, minFeature );

	float[] coords = new float[ 6 ];

	// build vertex list
	ArrayList<Point2f> verts = new ArrayList<Point2f>();
	while( !pi.isDone() )
	{
		int type = pi.currentSegment( coords );
		switch( type )
		{
			case PathIterator.SEG_MOVETO:
			case PathIterator.SEG_LINETO:
				verts.add( new Point2f( coords[ 0 ], coords[ 1 ] ) );
				break;
			case PathIterator.SEG_CLOSE:
				break;
			default:
				assert false;
		}
		pi.next();
	}

	for( int i = 1; i < verts.size() - 1; i++ )
	{
		int base = i - 1;
		int test = i;

		// find a run of adjacent verts that can be approximated with
		// a straight line
		while( test < verts.size() && testPoints( verts, base, test, minFeature ) )
		{
			test++;
		}

		// remove the unnecessary points
		verts.subList( base + 1, test - 2 ).clear();
	}

	// build the output shape
	GeneralPath gp = new GeneralPath();
	Point2f p = verts.get( 0 );
	gp.moveTo( p.x, p.y );
	for( int i = 0; i < verts.size(); i++ )
	{
		p = verts.get( i );
		gp.lineTo( p.x, p.y );
	}
	gp.closePath();

	return gp;
}

private static boolean testPoints( ArrayList<Point2f> verts, int base, int test, float limit )
{
	Point2f bp = verts.get( base % verts.size() );
	Point2f tp = verts.get( test % verts.size() );

	// test all vertices between base and test to see if they lie
	// outwith the threshold distance to the line between base and
	// test
	for( int i = base + 1; i < test - 1; i++ )
	{
		Point2f ip = verts.get( i );

		float d = LineUtils.closestPointOnLine( ip, bp, tp ).distance( ip );
		if( d > limit )
		{
			return false;
		}
	}

	return true;
}