Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


Converting a bitmap image to a meshed approximation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 JohnnyLightwave   Members   -  Reputation: 146

Like
0Likes
Like

Posted 10 May 2012 - 01:30 PM

Hi all,

I've been googling this for a time, but I can't find anything useful. I'm a little afraid nobody's ever even done it, but that seems impossible. It's like Rule 34 for programming.

I want to take a source image, and turn it into as bunch of triangles for rendering as an approximation. The use for this is to allow the user to draw shapes in an editor, and then the shape is saved as triangles for later rendering with a texture. In perfect-world I'd save the bitmap image itself, but I'm looking at mobile device amounts of memory.

So, too illustrate:

Input: http://i.imgur.com/qqT6l.jpg

Desired output: http://i.imgur.com/rHqDp.jpg

UV's not needed, since those would be computer by me depending on in-program settings.

Anyone ever seen an algo like this, or have any tips on implementing?

Thanks!

Sponsor:

#2 FLeBlanc   Crossbones+   -  Reputation: 3125

Like
1Likes
Like

Posted 10 May 2012 - 02:26 PM

You can google for things like "raster to vector algorithm", etc... It's a fairly complex little bit of image processing, with a number of different solutions of varying quality.

One possible solution is to construct a quad-tree from the image and iteratively subdivide it, stopping subdivision when a given square is either fully "green" (ie, fully inside the shape) or fully "black" (ie, fully outside the shape). It wouldn't construct the neat little triangle strips from your illustration, but rather a varying soup of polygons of different sizes all willy-nilly in the mix, ranging from larger squares well in the center of the green region, to lots of tiny little squares defining the edges.

Other methods include running an edge detection algorithm to detect "edges", or groups of pixels that can be inferred to form an edge. Edge detection is a fuzzy science, greatly affected by the contrast within the image; your sample of green on black would be a relatively easy case. A quick google turned up this page, which describes an algorithm wherein you iterate the image and for each pixel that is "turned on" (ie green in your example) you would construct tiny little vectors describing the tiny little box surrounding the pixel. Then you would iterate all the generated vectors and merge the "identical ones"; ie, the common edges between boxes. You would eliminate vectors that were not edges, ie that divided pixels of the same color. Then another pass would merge vectors that are co-linear into single long vectors. The result would be a set of vectors that run only horizontally or vertically, so you could run some sort of mesh relaxation or smoothing algorithm if you desired, to eliminate the stair-stepping that would be produced.

A variant of that scheme would follow along the idea of the "marching cubes" algorithm, (or, rather, "marching squares" since we are operating in 2D space). The image space would be partitioned into a fine grid, where the vertices of the grid would fall on pixel centers. Thus, each box would be defined by the values of pixel at the corner. Then each box would be analyzed, and a set of vectors would be generated to represent the edge pattern of the box. If all the pixels forming a box are the same color, no edges would be generated. Otherwise, edge vectors would be formed according to the edge pattern encompassed by the box. These vectors wouldn't necessarily lie on the horizontal and vertical axes, so the stair-stepping as in the previous algorithm wouldn't be as bad.

In this case, after the vectors were found that enclose the regions of your image, then you need to tessellate the regions into faces. You could convert the edge vectors to a closed spline curve and tessellate the surface. You could reference this article from GPU Gems 3 about rendering vector art on the GPU. Again, this is a fairly complex field.

#3 taby   Members   -  Reputation: 336

Like
2Likes
Like

Posted 10 May 2012 - 07:34 PM

I know that you're looking for something a little different than Marching Squares, but you could just run the triangles through a simple decimation algorithm to combine adjacent filled squares into a single larger square/rectangle, etc. Anyway...

I went the Marching Squares route once. Attached is output generated from your input image. Also attached is a 32x32 input image of a cat and the output that was generated from it. I drew the interior triangle edges for this tiny cat output just to show you how many triangles are created -- to compare, a 640x480 image generates an obscene amount of triangles. For fun, I also attached the large version of the cat and the associated output.

I've attached the source, including a small GLUT visualization to show what it's doing. There are a few minor things left to do on the source:
- Still needs code to combine all vertices into a single array (right now the vertices are stored in each of their respective triangles), then write vertices and triangles to .obj file.
- Although the code does generate triangles along the boundary of the image, it does not generate the extra edge line segments along the boundary of the image. Look at the output that I generated from your sample image. See how there are no extra edge line segments along the boundary at the top and bottom? You can work around this by simply ensuring that the input image has a 1 pixel wide/tall black border.

The code compiles in MSVC++ (should port to gcc rather easily though... it's all C++) and requires GLUT (a free library) for drawing the generated triangles and extra edge line segments. The syntax for the commandline is

"program.exe image_name.tga 1 0.5"

where the third parameter '1' makes the grid 1 metre x 1 metre, and the fourth parameter '0.5' is the isovalue that indicates that the triangles should cover anything as light as or lighter than the RGB value 127,127,127.

I've included a few grayscale TGA images to demonstrate. The commands would be:
"program.exe tabby.tga 1 0.5"
"program.exe tabby_blur.tga 1 0.5"
"program.exe tabby_noise.tga 1 0.5"

I don't think the TGA files necessarily have to be grayscale, but do note that the code converts all colour pixels to a grayscale value, since the Marching Squares algorithm is essentially "monochromatic".

If you try to feed the code a non-square/non-power-of-two TGA file, it'll complain, but that's only due to non-fatal graphical glitches that I ran into with the rendering portion of the code (which I assume you don't need). The triangle generation code should be able to handle non-square/non-power-of-two TGA files just fine.

The code is not as complex as it might first appear. I may be around to answer questions if you have any. Very serious cat approves of your very serious project. ;) I originally snagged the image from http://www.iacuc.ari...cats/index.html (The University of Arizona Institutional Animal Care and Use Committee) but it doesn't seem to be there anymore.

Attached Thumbnails

  • tabby_tris.jpg
  • tabby_tiny.jpg
  • qqT6l_output.jpg
  • tabby.jpg
  • tabby_bigtris.jpg

Attached Files


Edited by taby, 10 May 2012 - 09:21 PM.


#4 JohnnyLightwave   Members   -  Reputation: 146

Like
1Likes
Like

Posted 11 May 2012 - 10:20 AM

Taby, you might be a God Among Men.

I will look this over this weekend and see if I can make use of it. Needless to say, if I can make it do what I need, you will go on the credit's list for my project!

If think after incorporating your project, I can reduce the triangles myself and come up with an acceptable solution.

Stay tuned!

Edited by JohnnyLightwave, 11 May 2012 - 10:22 AM.


#5 taby   Members   -  Reputation: 336

Like
1Likes
Like

Posted 11 May 2012 - 02:57 PM

I will look this over this weekend and see if I can make use of it. Needless to say, if I can make it do what I need, you will go on the credit's list for my project!

If think after incorporating your project, I can reduce the triangles myself and come up with an acceptable solution.

Stay tuned!


If it works out, there is no need to credit me. I put the code in the public domain. Just go pet a cat nicely if you must do something in return. I do sincerely hope that the code helps. Best of luck.

Edited by taby, 11 May 2012 - 03:07 PM.


#6 jameszhao00   Members   -  Reputation: 271

Like
1Likes
Like

Posted 11 May 2012 - 08:32 PM

One way is to have a high resolution mesh with vertex colors, and then run it through http://research.micr...le/hoppe/pm.pdf

Look on the 2nd to last page. They give an example image (the baboon).

Edited by jameszhao00, 11 May 2012 - 08:33 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS