Algorithm to "de-rasterize" a voxel image of a polyhedron

Question

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.

1. Remove the inside of the image if there is one, so we have a 1-pixel thick perimeter
2. Assign an arbitrary "first" pixel as our active pixel, and the first point on our polygon
3. Iterate in one direction around the image, using each pixel as a "test pixel"
4. For each test pixel, keep track of the minimum and maximum angle between the active pixel and our test pixels
5. If the difference between these two angles becomes greater than D*2, create points on the polygon for these two minimum and maximum points
6. Set the active pixel to whichever of the min/max was second (that is, the furthest clockwise)
7. 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.

Answer 1

Note: I am assuming there is only one object (all voxels are connected). If this may not be the case, then you need to start by separating "all voxels" into "one set of voxels per object".

Start by assuming each voxel is a cube with 6 faces. For each face the neighbouring voxel may be empty (the face has to be in the mesh) or present/solid (the face is omitted from the mesh). This is basic hidden surface removal.

Next; merge adjacent faces. For example, for a 3*3*3 cube of voxels the top would be 9 little faces and these little faces can be merged to form 1 large face. You may (if desired) generate textures for each "large face" while doing this or after doing this (where textel colour = corresponding voxel colour).

Next; find "inner bubbles". Choose any face and mark is as belonging to "mesh 1". Then find any faces that share an edge with that face and mark them as belonging to "mesh 1" too. Continue doing this recursively to find all faces that belong to "mesh 1". If there are any faces left over, choose one and mark it as belonging to "mesh 2", and find all other faces that belong to "mesh 2". Do this until there are no faces left over (all faces belong to a mesh). Cast a ray from any far away point (e.g. along the Z axis from "Z = infinity") and see which face it hits first. Whichever mesh this face belongs to is the "exterior mesh". All other meshes are "inner bubbles".

Note 1: If the camera can't be inside any inner bubble, then you can discard the inner bubble meshes. If the camera can be inside an inner bubble, then for each inner bubble mesh you can find its centre point and radius (the furthermost vertex from the centre point), and then only render the inner bubble if the distance from camera to the bubble's centre point is less than the distance from the bubble's centre to its furthermost vertex.

Note 2: I described it like this to make it easier to understand. In practice you'd want to cast the ray first, and use the face it hits first as the first face of "mesh 1". This means that "mesh 1" is always the exterior mesh; and (if the camera can't be within an inner bubble) allows you to discard all faces that aren't part of "mesh 1" without building any inner bubble meshes.

Note 3: You'd also cast that ray in the opposite direction to what I described; starting from a face and finding the last face the ray passes through. This avoids the chance of "ray misses all faces".

Finally, (if desired) smooth the mesh/es by finding the edges between faces and generating new faces such that the surface normal of the new face is the dot product of the surface normals of the old faces. You may do this multiple times (e.g. 90 degree corners become 45 degree "chamfered corners", which become 22.5 degree "triple chamfered corners", and so on) until you're approximating curves with a radius equal to half the width of a voxel.