mblum%asylum.utah.edu@cs.utah.edu (Michael Blum) (05/24/91)
HI! I'm trying to figure out how to find whether a sphere intersects a plane. Actually, I need to know whether a sphere intersects a cube, and if so which side of the cube. I imagine this is a simple extension to the general intersection problem, but I'm not exactly sure how to approach the problem. Any ideas? please e-mail at mblum@asylum.utah.edu Thanks! -Mike Blum
3ksnn64@cidmac.ecn.purdue.edu (Joe Cychosz) (05/25/91)
In article <1991May23.205708.9746@hellgate.utah.edu> mblum%asylum.utah.edu@cs.utah.edu (Michael Blum) writes: >HI! > >I'm trying to figure out how to find whether a sphere intersects a plane. >Actually, I need to know whether a sphere intersects a cube, and >if so which side of the cube. I imagine this is a simple extension >to the general intersection problem, but I'm not exactly sure >how to approach the problem. Any ideas? please e-mail at >mblum@asylum.utah.edu > 1. Compute the perpendicular distance the center of the sphere is from the plane. 2. The dot product of the plane normal with the vector formed by the the line from the plane through the center of the sphere tells you what side of the plane the sphere is on. The dot product should be 1 or -1. 3. If the perpendicular distance is less than the radius, the sphere intersects the plane. 4. For the cube case you can treat the plane pairs together and the distance to the second plane = the distance between the planes - dot product (step 2) * distance (step 1). 5. Count the number of cases where the sphere is between the plane pairs or intersects one of the planes. If the answer is 3, the sphere is within or intersects the cube. Assumption: the normal of the 6 planes all point outward of the cube.
3ksnn64@cidmac.ecn.purdue.edu (Joe Cychosz) (05/25/91)
In article <1991May24.180454.10744@noose.ecn.purdue.edu> 3ksnn64@cidmac.ecn.purdue.edu (Joe Cychosz) writes: >In article <1991May23.205708.9746@hellgate.utah.edu> mblum%asylum.utah.edu@cs.utah.edu (Michael Blum) writes: >>HI! >> >>I'm trying to figure out how to find whether a sphere intersects a plane. >>Actually, I need to know whether a sphere intersects a cube, and >>if so which side of the cube. I imagine this is a simple extension >>to the general intersection problem, but I'm not exactly sure >>how to approach the problem. Any ideas? please e-mail at >>mblum@asylum.utah.edu >> > >1. Compute the perpendicular distance the center of the sphere is from the > plane. > >2. The dot product of the plane normal with the vector formed by the the > line from the plane through the center of the sphere tells you what > side of the plane the sphere is on. The dot product should be 1 or -1. > >3. If the perpendicular distance is less than the radius, the sphere > intersects the plane. > >4. For the cube case you can treat the plane pairs together and the > distance to the second plane = the distance between the planes - > dot product (step 2) * distance (step 1). > >5. Count the number of cases where the sphere is between the plane pairs > or intersects one of the planes. If the answer is 3, the sphere is > within or intersects the cube. Assumption: the normal of the 6 planes > all point outward of the cube. As has been pointed out to me. It is possible for a sphere to intersect the plane pairs and still not intersect the cube. At the moment I do not have a correction for the algorithm. A sphere may be "between" all three plane pairs and still not intersect the cube. As an example consider the cube defined by 0<= x <= 1; 0 <= y <= 1; 0 <= z <= 1 and the sphere centred at (-2, -2, 0) and passing through (-1, .5, 0).
jk87377@cc.tut.fi (Juhana Kouhia) (05/26/91)
In article <1991May23.205708.9746@hellgate.utah.edu> mblum%asylum.utah.edu@cs.utah.edu (Michael Blum) writes: > >Actually, I need to know whether a sphere intersects a cube, and >if so which side of the cube. (I will e-mail this to you as you requested...) If I understand your problem right, you should look for the paper Eric Haines and John Wallace Shaft Culling for Efficient Ray-Traced Radiosity May 1991 Presented in Second Eurographics Workshop on Rendering, Barcelona See section Shaft Cull Testing, and sphere/box test. Paper is in nic.funet.fi, pub/graphics/papers^2/hain91.ps.Z; and hopefully soon in weedeater.math.yale.edu; pub/Papers (Mr. Kolb is in Europe now and are not available). Juhana Kouhia PS. What is the definition for the "computer graphics professional"?
rkaye@polyslo.CalPoly.EDU (Depeche) (05/27/91)
In article <1991May23.205708.9746@hellgate.utah.edu> mblum%asylum.utah.edu@cs.utah.edu (Michael Blum) writes: > >Actually, I need to know whether a sphere intersects a cube, and >if so which side of the cube. I have been following this thread for a few days now, wishing somebody would bring up what I am looking for, but so such luck. :-) 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? -R.k. polyslo.calpoly.edu!petunia!dega!depeche rkaye@polyslo.calpoly.edu
chrisg@cbmvax.commodore.com (Chris Green) (05/28/91)
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
glassner@parc.xerox.com (Andrew Glassner) (05/29/91)
A previous poster writes: >Actually, I need to know whether a sphere intersects a cube, and >if so which side of the cube. A solution is presented in "A Simple Method for Box-Sphere Intersection Testing," by Jim Arvo, in the book "Graphics Gems," published by Academic Press (pp. 335-339). C source code for the technique is also given in the book (pp. 730-732) - the code is available via anonymous ftp from weedeater.math.yale.edu. Minor changes will tell you which side of the cube is intersected. Jim also describes how to generalize the method to ellipsoids and arbitrary rectangular boxes (not just cubes). It's fast, elegant, correct, and simple - this is the technique I use in my ray tracer. -Andrew Glassner (glassner@xerox.com)
erich@eye.com (Eric Haines) (05/29/91)
In article <glassner.675494763@overture> glassner@parc.xerox.com (Andrew Glassner) writes: >A previous poster writes: >>Actually, I need to know whether a sphere intersects a cube, and >>if so which side of the cube. > >A solution is presented in "A Simple Method for Box-Sphere >Intersection Testing," by Jim Arvo, in the book "Graphics Gems," >published by Academic Press (pp. 335-339). Wow! Withdraw, delete, cancel my incredibly long-winded, lousy answer to this question - Andrew's absolutely correct, Jim's method is elegant and faster than fast. Amazing what a shift in perspective can do! Summary: check X,Y, and Z coordinates separately; if the sphere's center for an axis is inside the box, ignore it, otherwise sum the distance squared from the closer box end. If this sum is less than or equal to the sphere's radius squared, the sphere intersects the box! Whack me with a Zen Master's stick! Mu! Much enlightened, Eric