Hi

Quote:> Hi all,

> I'm trying to find the 'best' way to resterize an ellipsoid (well,

> prolate spheroid) of arbitrary pose into a standard grid of voxels.

Generalise Bresenham's algorithm as follows:

1. Write an implicit definition of the ellipsoid in the form of a

discriminant: D(x) is positive if x is outside the ellipsoid, negative or

zero otherwise.

1.5. Decide if your voxels are centered on integral points, or if the

corners lie on integral points, and if so, how. Be careful about this.

2. Pick a point x in the ellipsoid. Calculate D(x).

3. For each of the twenty six neighbours x' of x, use the partial

derivatives of D to calculate D(x') quickly.

4. Repeat recursively until there are no more points to be filled.

The tricky part lies in how you do the recursion. Drawing a line (or a

circle) is relatively simple because these are one-dimensional objects. You

have a multidimensional space to enumerate. Pick a suitable one-to-one map

:o).

Regards

David Turner