Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Let's say we have a 2D image black on white that shows a closed geometric shape.

Is there any (not naive brute force) algorithm that approximates that shape as closely as possible with n triangles? If you want a formal definition:

Approximate the shape with a polygon that when rendered into a new 2D image will match the largest number of pixels possible with the original image.

share|improve this question
    
Have you tried link? –  AranHase Oct 21 '12 at 21:41
    
@AranHase This is good for my other question. Here I get a raster as input. –  Arthur Wulf White Oct 22 '12 at 20:41
    
possible duplicate of Algorithm for approximating sihlouette image as polygon –  Byte56 Oct 24 '12 at 17:22
add comment

1 Answer

up vote 3 down vote accepted

I think you'll need to do it in two or three steps:

For converting a raster image to polygons you can use pre-existing software like http://en.wikipedia.org/wiki/Potrace

Optimizing the result from that to get the best possible result with a specific number of polygons I believe is much harder. However efficiently optimizing an existing mesh down to a lower poly count isn't too difficult if you don't care about the result being optimal. For example http://research.microsoft.com/en-us/um/people/hoppe/proj/meshopt/ describes one algorithm to optimize a 3D mesh, based on a parameter saying how much to optimize it.

Once you have that optimized mesh you could apply a hill climbing algorithm to the vertex positions to try to further improve the fit.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.