Draw a sphere surface in voxels efficiently?

Question

I have a large 3D grid (with minimum grid box size of 1x1x1 for simplicity) and want to draw only the surface of a large number of spheres with variable radius in this grid. However I want to eliminate the typical rasterization problems of holes and mounds.

I also don't want to do a brute force approach (find all pixels within radius of sphere centre, remove non-boundary pixels) as I'll be creating millions of these spheres, and some of them could have very high radii. The Bresenham algorithm for circles is similar to what I want, but I'm wondering how I could adapt this to the sphere shape.

Anybody out there able to help?

Answer 1

Ok I think I have it worked out. Not sure if this is the most efficient version though.

Essentially a sphere's surface is made up of an infinite set of circles with radius r that increases and then decreases as you move through the axis perpendicular to the plane intersecting that circle. The increase and decrease of the radius can be described using a semicircle.

In a discrete space we can then model the sphere's surface in an efficient manner by drawing a set of circles using the Bresenham algorithm where the radius is calculated using an additional bresenham circle, whose radius is that of the spheres. This radius is envisioned as being sticking "up" from the circle, in the third dimension.

The other circles build up around it as if the primary circle is a frame for construction.

I'm not entirely sure if that was all that easy to understand, so hopefully the algorithm might shed a bit more light:

public static void bresenhamSphere(Vector3 centre, int radius)
    {
        List<Vector3> points = new List<Vector3>();
        foreach (Point coord in bresenhemCircle(new Point(0,0), radius)) //get the set of points for an initial bresenham circle centred at the origin (we'll add the coordinates later)
        {
            int z = coord.Y; //I think you should be able to pick which coord matches to Z and which matches to radius arbitrarily, but this was more intuitive
            int r = coord.X; //the radius for the new circles
            foreach(Point point in bresenhemCircle(new Point((int)(centre.X),(int)(centre.Y)), r)) //get the circle spans around the original circle, this will make the surface of the sphere - this time create them at the x and y coordinates of the centre point supplied in the parameters
            {
                points.Add(new Vector3(point.X, point.Y, (int)(centre.Z) + z)); //convert the 2D results into 3D points by adding in the z value and add to the list.
            }
        }
    }

Where BresenhamCircle(centre, radius) returns the coordinates of all pixels on the circumference of the circle formed of the centre and radius provided.

Where BresenhamSemiCircle(centre, radius) returns the coordinates of all pixels on the circumference of the semicircle formed of the centre and radius provided.

One additional enhancement would be to not add in the initial points on the new circles as we already have these from the original circle run, but I'm not sure how much of a bonus there is in that.