Rasterizing a polygon in this question consists of creating an array of binary pixels that "represent" the polygon. The reverse of this process is easy to approximate in linear time to the perimeter in pixels. It uses a "detail threshold" D to define how complex the polygon will be. As D decreases, the polygon becomes more detailed.
Keep in mind this is just for polygons and 2D images, not 3D, yet.
- Remove the inside of the image if there is one, so we have a 1-pixel thick perimeter
- Assign an arbitrary "first" pixel as our active pixel, and the first point on our polygon
- Iterate in one direction around the image, using each pixel as a "test pixel"
- For each test pixel, keep track of the minimum and maximum angle between the active pixel and our test pixels
- If the difference between these two angles becomes greater than D*2, create points on the polygon for these two minimum and maximum points
- Set the active pixel to whichever of the min/max was second (that is, the furthest clockwise)
- From now on, iterate around the image and add another vertex whenever |(angle of previous line segment) - (angle between active/test pixel)| > D. The active pixel becomes the most recently added vertex.
This doesn't produce an optimal polygon, but it works. It's the best I could think of, anyway. If you rasterize the result, it would produce something similar to the original image. It could be potentially improved by setting a minimum distance between vertexes.
However, how could an algorithm like this be extended to 3D, where the rasterized "image" is 3D/has volume, and we are producing a polyhedron? I'm at a loss as to how to figure this out.
Thanks in advance for the help.