## Efficiently rasterize ellipsoid?

### Efficiently rasterize ellipsoid?

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.

At the moment I have some pretty horrible code that evaluates whether
the voxels in the containing volume intersect the surface or not.  It
works, but I'd rather use something a bit more efficient!

Any ideas?

TIA

Rob.

### Efficiently rasterize ellipsoid?

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
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

### Efficiently rasterize ellipsoid?

PS

Quote:> Hi

> 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.

I should have mentioned the important bit -- avoid floating point.  Store D
as a rational number, and don't do the division if you don't have to.

That is, unless floating point turns out to be more efficient, which it
might do on a P4.

Regards
David Turner

I am trying to draw normalised ellipsoids in opengl ..

The method I have used is to render a 1*1*1 sphere using glut ,
normalised it then used glScale?() to extrude it in various
dimensions..  Is this a good method ??

How do I render a hemisphere / hemi-ellipsoid in glut.

Any help or comments are greatly appreciated