Monday, April 25, 2016

rendering - Is there any heuristic to polygonize a closed 2D raster shape with n triangles?


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

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...