Efficiently rasterize ellipsoid?

Efficiently rasterize ellipsoid?

Post by R.K. Harl » Fri, 11 Jul 2003 22:51:15



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?

Post by David Turne » Sat, 12 Jul 2003 00:15:57


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?

Post by David Turne » Sat, 12 Jul 2003 00:19:24


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

 
 
 

1. Ellipsoids / "Hemi-Ellipsoids"

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

2. US-CA-S.FRANCISCO - ***kINETIX***EXCEPTIONAL OPPORTUNITIES!!!

3. Capture screen efficiently using DirectX API (95/NT)

4. 16 bit multipart tiff

5. storaging graphics efficiently...

6. ndspy.h constants and structs

7. Need help/suggestions on running PS5 more efficiently

8. Changing video format

9. How to calculate view frustum planes efficiently?

10. Efficiently drawing a Mercator projection

11. Efficiently finding nearest 3D point in a 3D points cloud

12. How to compute contact regions efficiently

13. Travel a bitmap efficiently in C++...