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

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