Draw a sphere using 3D pixels (voxels)

Question

Can you suggest an algorithm that can draw a sphere in 3D space using only the basic plot(x,y,z) primitive (which would draw a single voxel)?

I was hoping for something similar to Bresenham's circle algorithm, but for 3D instead of 2D.

FYI, I'm working on a hardware project that is a low-res 3D display using a 3-dimensional matrix of LEDs, so I need to actually draw a sphere, not just a 2D projection (i.e. circle).

The project is very similar to this:

... or see it in action here.

One possibility I have in mind is this:

• calculate the Y coordinates of the poles (given the radius) (for a sphere centered in the origin, these would be -r and +r)
• slice the sphere: for each horizontal plane p_i between these coordinates, calculate the radius of the circle obtained by intersecting said plane with the sphere => r_i.
• draw the actual circle of radius r_i on plane p_i using Bresenham's algorithm.

FWIW, I'm using a .NET micro-framework microprocessor, so programming is C#, but I don't need answers to be in C#.

Answer 1

The simple, brute force method is to loop over every voxel in the grid and calculate its distance from the sphere center. Then color the voxel if its distance is less than the sphere radius. You can save a lot of instructions by eliminating the square root and comparing the dot product to the radius squared.

Pretty far from optimal, sure. But on an 8x8x8 grid as shown, you'll need to do this operation 512 times per sphere. If the sphere center is on the grid, and its radius is an integer, you only need integer math. The dot product is 3 multiplies and 2 adds. Multiplies are slow; let's say they take 4 instructions each. Plus you need a comparison. Add in the loads and stores, let's say it costs 20 instructions per voxel. That's 10240 instructions per sphere.

An Arduino running at 16 MHz could push 1562 spheres per second. Unless you're doing tons of other math and I/O, this algorithm should be good enough.