Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!wuarchive!uunet!cbmvax!chrisg
From: chrisg@cbmvax.commodore.com (Chris Green)
Newsgroups: comp.graphics
Subject: Re: intersecting planes and spheres
Message-ID: <21952@cbmvax.commodore.com>
Date: 28 May 91 14:44:23 GMT
References: <28400a5b.b93@petunia.CalPoly.EDU>
Reply-To: chrisg@cbmvax.commodore.com (Chris Green)
Organization: Commodore, West Chester, PA
Lines: 34

In article <28400a5b.b93@petunia.CalPoly.EDU> rkaye@polyslo.CalPoly.EDU (Depeche) writes:
>
>I am looking for a similar algorithm, which intersects ellipsoids,
>and voxels. (not square boxes) Does anybody have a list of references 
>for algorithms like this one?
>

	You can do this very efficiently using interval arithmetic. Plug the intervals
for XY and Z of your voxels into the quadratic equation of your ellipsoid. If
the resulting interval contains zero, then it is extremely likely (though not
absolutely certain) that that voxel contains part of the ellipsoid.

	Interval arithmetic is mathematical operations on intervals, which are min/max
pairs of numbers. if [a,b] is an interval with a<=b, and likewise for c,d, then:

[a,b]+[c,d] = [a+c,b+d]
const*[a,b]= [const*a,const*b] or the reverse if const is <0.

[a,b]^2 = 
	if a<0 then
		if b<0 then
			[b^2,a^2]
		else [0.0, max(-a,b)^2
	else [a^2.b^2]


	Those operations should be the only ones you need for ellipsoids versus boxes.
-- 
*-------------------------------------------*---------------------------*
|Chris Green - Graphics Software Engineer   - chrisg@commodore.COM      f
|                  Commodore-Amiga          - uunet!cbmvax!chrisg       n
|My opinions are my own, and do not         - killyouridolssonicdeath   o
|necessarily represent those of my employer.- itstheendoftheworld       r
*-------------------------------------------*---------------------------d