1

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?

Nick Udell
  • 2,420
  • 5
  • 44
  • 83
  • similar: http://stackoverflow.com/questions/9084189/draw-a-sphere-using-3d-pixels-voxels http://stackoverflow.com/questions/564492/recommend-some-bresenhams-like-algorithm-of-sphere-mapping-in-2d – AakashM Mar 13 '12 at 13:38
  • Ah thanks for finding this. I did come across the first link myself, but assumed they were looking for a filled sphere as the responses only covered the brute force method I outlined above (or a span method which is unhelpful for me unless I can calculate the exact span of a voxel transition in angular change. – Nick Udell Mar 13 '12 at 14:31

1 Answers1

2

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.

Nick Udell
  • 2,420
  • 5
  • 44
  • 83
  • Looks good in principle (haven't tried it myself). It's interesting that googling 'sphere rasterize' **doesn't** turn up anything of interest... part of me feels sure that the *techniques* used in Bresenham's Line + Circle must be extendable to a surface, but I can't find anyone who's done it! – AakashM Mar 13 '12 at 16:33
  • 1
    I think this would work very well if the circle algorithm were extended to include either an initial error or fractional radius. I think you'll end up with an issue where near the equator of a sphere it rasters to a cylinder, as you draw the same circle several times, where in reality, through the arc should vary slightly even if the x=0 or y=0 points would stay the same. I think as you follow the first circle (for radius), using the accumulated error from each point as an input to the second circle would solve the issue. – rjp Dec 04 '13 at 18:31