Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (107)
games submitted by our members
Games in WIP (536)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Vectorization of image in Java (triangles on top of image)  (Read 5619 times)
0 Members and 1 Guest are viewing this topic.
Offline M2009

Junior Member





« Posted 2009-06-22 20:31:44 »

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.



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

1  
2  
3  
4  
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.)

Offline thijs

Junior Member




Lava games rock!


« Reply #1 - Posted 2009-06-30 09:14:17 »

You should lookup the marching squares algorithm:
http://en.wikipedia.org/wiki/Marching_squares

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

<a href="http://www.dzzd.net">3DzzD!</a>
<a href="http://www.arcazoid.com">Arcazoid!</a>
Offline M2009

Junior Member





« Reply #2 - Posted 2009-07-08 03:46:07 »

You should lookup the marching squares algorithm:
http://en.wikipedia.org/wiki/Marching_squares

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

Hey thijs, thanks a lot for your reply! I'm glad this thread got one. Smiley 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:

1  
2  
3  
4  
5  
6  
00000
00000
00110
00110
00010
00000


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:

1  
2  
3  
4  
5  
00000
01110
01010
01110
00000


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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline thijs

Junior Member




Lava games rock!


« Reply #3 - Posted 2009-07-08 12:45:22 »

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

<a href="http://www.dzzd.net">3DzzD!</a>
<a href="http://www.arcazoid.com">Arcazoid!</a>
Offline M2009

Junior Member





« Reply #4 - Posted 2009-07-20 01:36:42 »

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:

1  
2  
3  
4  
5  
00100
01110
11111
01110
00100


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:

1  
2  
3  
4  
5  
  1
 X X
1   1
 X X
  1


Thank you again!

Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #5 - Posted 2009-07-20 08:55:54 »

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.
Offline mh114

Junior Member





« Reply #6 - Posted 2009-07-20 09:01:05 »

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:

1  
2  
3  
4  
5  
  1
 X X
1   1
 X X
  1
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. Smiley

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

Offline thijs

Junior Member




Lava games rock!


« Reply #7 - Posted 2009-07-20 11:01:54 »

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

<a href="http://www.dzzd.net">3DzzD!</a>
<a href="http://www.arcazoid.com">Arcazoid!</a>
Offline M2009

Junior Member





« Reply #8 - Posted 2009-07-21 00:05:55 »

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?

Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #9 - Posted 2009-07-21 10:59:00 »

Although I'm not sure what bleb meant with "threshold distance"?

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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline ryanm

Senior Member


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #10 - Posted 2009-08-25 18:11:20 »

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.

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:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
/**
 * 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;
}
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Riven (18 views)
2014-07-29 18:09:19

Riven (13 views)
2014-07-29 18:08:52

Dwinin (12 views)
2014-07-29 10:59:34

E.R. Fleming (31 views)
2014-07-29 03:07:13

E.R. Fleming (12 views)
2014-07-29 03:06:25

pw (42 views)
2014-07-24 01:59:36

Riven (41 views)
2014-07-23 21:16:32

Riven (28 views)
2014-07-23 21:07:15

Riven (29 views)
2014-07-23 20:56:16

ctomni231 (60 views)
2014-07-18 06:55:21
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!