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.
Answer
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.
No comments:
Post a Comment