Thread: [Algorithms] Volume of intersection of sphere and AABB
Brought to you by:
vexxed72
From: John M. <jo...@jo...> - 2008-12-05 22:30:47
|
Hi, I'm wondering if anyone has an idea of how to compute the volume of the intersection of a sphere (center, radius) and an AABB(max,min) ? The idea being if the sphere is completely inside the AABB that the volume returned would be that of the sphere and as the sphere moves out of the AABB the volume drops to zero. I've googled but haven't been able to find anything. Thanks, -- John McCutchan <jo...@jo...> |
From: Gregory J. <gj...@da...> - 2008-12-05 23:09:16
|
> > I'm wondering if anyone has an idea of how to compute the volume of > the intersection of a sphere (center, radius) and an AABB(max,min) ? > > The idea being if the sphere is completely inside the AABB that the > volume returned would be that of the sphere and as the sphere moves > out of the AABB the volume drops to zero. > > I've googled but haven't been able to find anything. > I think you are looking for Constructive Solid Geometry algorithms? Greg |
From: John M. <jo...@jo...> - 2008-12-05 23:23:12
|
On Fri, Dec 5, 2008 at 2:41 PM, Gregory Junker <gj...@da...> wrote: >> >> I'm wondering if anyone has an idea of how to compute the volume of >> the intersection of a sphere (center, radius) and an AABB(max,min) ? >> >> The idea being if the sphere is completely inside the AABB that the >> volume returned would be that of the sphere and as the sphere moves >> out of the AABB the volume drops to zero. >> >> I've googled but haven't been able to find anything. >> > > I think you are looking for Constructive Solid Geometry algorithms? Am I? I don't want the geometry, I'm looking for the scalar measurement of the volume of space contained in the geometry. -- John McCutchan <jo...@jo...> |
From: Gregory J. <gj...@da...> - 2008-12-05 23:41:33
|
> On Fri, Dec 5, 2008 at 2:41 PM, Gregory Junker > <gj...@da...> wrote: > >> > >> I'm wondering if anyone has an idea of how to compute the volume of > >> the intersection of a sphere (center, radius) and an > AABB(max,min) ? > >> > >> The idea being if the sphere is completely inside the AABB that the > >> volume returned would be that of the sphere and as the sphere moves > >> out of the AABB the volume drops to zero. > >> > >> I've googled but haven't been able to find anything. > >> > > > > I think you are looking for Constructive Solid Geometry algorithms? > > Am I? I don't want the geometry, I'm looking for the scalar > measurement of the volume of space contained in the geometry. > CSG is all about intersections of objects in 3D space. Once you have completed the boolean operation on your shapes, then you have something with which you can compute a volume. Given that the relative positions of your two objects can be completely arbitrary, there is no analytical solution of which I am aware. Is the sphere intersecting one face? Two? Three? All 6? I have to say, this isn't something you likely are going to want to do every frame. Is there a higher-level goal you are trying to achieve? Perhaps there is a different solution that serves your needs. Greg |
From: Darren G. <dg...@ke...> - 2008-12-05 23:59:04
|
The first thing that comes to mind is to start with 'the integral of circular slabs' approach. That will get you an easy volume by integrating across a box axis instead of the entire sphere. Modifying the slab (circle) area equation similarly so that each circle is bounded by the four remaining edges should get you the rest of the way. (Haven't tried this so I can't say it won't be ugly, but it does help that the edges are mutually orthogonal so their equations become constant values.) It also seems like this would be a fairly common csg problem.. and approximating the initial sphere with a convex polytope and clipping that against the planes of the box is another option in that field. Regards, Darren At 02:00 PM 12/5/2008, John McCutchan wrote: >Hi, > >I'm wondering if anyone has an idea of how to compute the volume of >the intersection of a sphere (center, radius) and an AABB(max,min) ? > >The idea being if the sphere is completely inside the AABB that the >volume returned would be that of the sphere and as the sphere moves >out of the AABB the volume drops to zero. > >I've googled but haven't been able to find anything. > >Thanks, >-- >John McCutchan <jo...@jo...> > >------------------------------------------------------------------------------ >SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada. >The future of the web can't happen without you. Join us at MIX09 to help >pave the way to the Next Web now. Learn more and register at >http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ >_______________________________________________ >GDAlgorithms-list mailing list >GDA...@li... >https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >Archives: >http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > >-- >No virus found in this incoming message. >Checked by AVG. >Version: 7.5.552 / Virus Database: 270.9.14/1832 - Release Date: >12/5/2008 9:57 AM |
From: Jon W. <jw...@gm...> - 2008-12-06 00:25:18
|
Oh, and I forgot to mention: one way to classify which of the cases you're dealing with is to check whether each vertex of the box is inside or outside the sphere. The sphere intersects the sides where at least one vertex is inside the sphere (I think a side that's fully inside still should be treated as a cutting plane). Sincerely, jw John McCutchan wrote: > Hi, > > I'm wondering if anyone has an idea of how to compute the volume of > the intersection of a sphere (center, radius) and an AABB(max,min) ? > > The idea being if the sphere is completely inside the AABB that the > volume returned would be that of the sphere and as the sphere moves > out of the AABB the volume drops to zero. > > I've googled but haven't been able to find anything. > > Thanks, > |
From: Osman, B. <BO...@vv...> - 2008-12-06 16:52:32
|
But that doesn't catch all cases, does it? What about when the sphere penetrates one side of the box, but with a shallow enough penetration that it never reaches any of the corners. The trivial version of this is when the sphere's radius is much smaller than the sides of the box, and the sphere centered on one side of the box. I can't imagine solving this from scratch ... I'd certainly seek out the existing CSG methods, and work from there. -Brian -----Original Message----- From: Jon Watte [mailto:jw...@gm...] Sent: Friday, December 05, 2008 7:25 PM To: Game Development Algorithms Subject: Re: [Algorithms] Volume of intersection of sphere and AABB Oh, and I forgot to mention: one way to classify which of the cases you're dealing with is to check whether each vertex of the box is inside or outside the sphere. The sphere intersects the sides where at least one vertex is inside the sphere (I think a side that's fully inside still should be treated as a cutting plane). Sincerely, jw John McCutchan wrote: > Hi, > > I'm wondering if anyone has an idea of how to compute the volume of > the intersection of a sphere (center, radius) and an AABB(max,min) ? > > The idea being if the sphere is completely inside the AABB that the > volume returned would be that of the sphere and as the sphere moves > out of the AABB the volume drops to zero. > > I've googled but haven't been able to find anything. > > Thanks, > ------------------------------------------------------------------------ ------ SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada. The future of the web can't happen without you. Join us at MIX09 to help pave the way to the Next Web now. Learn more and register at http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix. com/ _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis t |
From: David D. <dyn...@cs...> - 2008-12-06 19:55:27
|
Just a thought - is the volume removed from a sphere by a cutting plane proportional to the distance from the origin of the sphere to the plane? That probably wouldn't work for the sphere intersecting more than one side though. Osman, Brian wrote: > But that doesn't catch all cases, does it? What about when the sphere > penetrates one side of the box, but with a shallow enough penetration > that it never reaches any of the corners. The trivial version of this is > when the sphere's radius is much smaller than the sides of the box, and > the sphere centered on one side of the box. > > I can't imagine solving this from scratch ... I'd certainly seek out the > existing CSG methods, and work from there. > > -Brian > > > -----Original Message----- > From: Jon Watte [mailto:jw...@gm...] > Sent: Friday, December 05, 2008 7:25 PM > To: Game Development Algorithms > Subject: Re: [Algorithms] Volume of intersection of sphere and AABB > > > Oh, and I forgot to mention: one way to classify which of the cases > you're dealing with is to check whether each vertex of the box is inside > > or outside the sphere. The sphere intersects the sides where at least > one vertex is inside the sphere (I think a side that's fully inside > still should be treated as a cutting plane). > > Sincerely, > > jw > > > John McCutchan wrote: >> Hi, >> >> I'm wondering if anyone has an idea of how to compute the volume of >> the intersection of a sphere (center, radius) and an AABB(max,min) ? >> >> The idea being if the sphere is completely inside the AABB that the >> volume returned would be that of the sphere and as the sphere moves >> out of the AABB the volume drops to zero. >> >> I've googled but haven't been able to find anything. >> >> Thanks, >> > > > ------------------------------------------------------------------------ > ------ > SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, > Nevada. > The future of the web can't happen without you. Join us at MIX09 to > help > pave the way to the Next Web now. Learn more and register at > http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix. > com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-lis > t > > ------------------------------------------------------------------------------ > SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada. > The future of the web can't happen without you. Join us at MIX09 to help > pave the way to the Next Web now. Learn more and register at > http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
From: Ben Sunshine-H. <sn...@gm...> - 2008-12-06 20:49:47
|
On Fri, Dec 5, 2008 at 5:00 PM, John McCutchan <jo...@jo...> wrote: > Hi, > > I'm wondering if anyone has an idea of how to compute the volume of > the intersection of a sphere (center, radius) and an AABB(max,min) ? Doesn't sound like too difficult of a problem. The candidate points, the extrema of which form the resultant AABB, will come from the extrema of the intersections of the sphere with each face of the original AABB, and the extrema of the sphere itself (the six intersection points of the sphere and the faces of its own AABB) which are inside the original AABB. Determine which planes on the original AABB intersect the sphere, find the extrema of any intersection between the corresponding faces and the sphere, and union the results, plus the aforementioned sphere extrema, into an AABB. Ben |
From: Willem H. de B. <wi...@wh...> - 2008-12-07 13:24:49
|
Do you need an accurate answer? If accuracy is something you wouldn't mind say compute over several frames, then you could use a simple Monte Carlo-like scheme. (Though I think the number of sample points required is low enough to be able to compute the volume in real-time) One could proceed by generating random points inside the union of the AABB and the sphere, the total volume, V, of which is easy to calculate ofcourse. Then only keep those points that lie within the intersection of the AABB and the sphere and keep track of the ratio of points within to the total number of points generated, call this r_n. Then after a suitable number of points generated, the volume is roughly r_n * V. The trouble with finding an analytic description of the volume is that the domain of integration (i.e. the intersection of AABB and sphere) is usually difficult to parametrise. In such cases MC-like schemes work very well. Cheers, Willem ----- Original Message ----- From: "John McCutchan" <jo...@jo...> To: "Game Development Algorithms" <gda...@li...> Sent: Friday, December 05, 2008 10:00 PM Subject: [Algorithms] Volume of intersection of sphere and AABB > Hi, > > I'm wondering if anyone has an idea of how to compute the volume of > the intersection of a sphere (center, radius) and an AABB(max,min) ? > > The idea being if the sphere is completely inside the AABB that the > volume returned would be that of the sphere and as the sphere moves > out of the AABB the volume drops to zero. > > I've googled but haven't been able to find anything. > > Thanks, > -- > John McCutchan <jo...@jo...> > > ------------------------------------------------------------------------------ > SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, > Nevada. > The future of the web can't happen without you. Join us at MIX09 to help > pave the way to the Next Web now. Learn more and register at > http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
From: John M. <jo...@jo...> - 2008-12-07 16:30:45
|
Thanks everyone for your suggestions and interesting conversation. The reason I asked was that I'm trying to determine how much volume of an object (discretized into spheres) is submerged under a height field (discretized into AABBs) and need to do this many times per frame. I think I've figured out a cheap solution that should give reasonable results (never count a submerged sphere twice.) Thanks, John On Sun, Dec 7, 2008 at 5:24 AM, Willem H. de Boer <wi...@wh...> wrote: > Do you need an accurate answer? If accuracy is something > you wouldn't mind say compute over several frames, then > you could use a simple Monte Carlo-like scheme. (Though > I think the number of sample points required is low enough > to be able to compute the volume in real-time) > > One could proceed by generating random points inside > the union of the AABB and the sphere, the total volume, > V, of which is easy to calculate ofcourse. > > Then only keep those points that lie within the intersection > of the AABB and the sphere and keep track of the ratio of > points within to the total number of points generated, call > this r_n. > > Then after a suitable number of points generated, the volume is > roughly r_n * V. > > The trouble with finding an analytic description of the volume > is that the domain of integration (i.e. the intersection of AABB > and sphere) is usually difficult to parametrise. In such cases > MC-like schemes work very well. > > Cheers, > Willem > > ----- Original Message ----- > From: "John McCutchan" <jo...@jo...> > To: "Game Development Algorithms" <gda...@li...> > Sent: Friday, December 05, 2008 10:00 PM > Subject: [Algorithms] Volume of intersection of sphere and AABB > > >> Hi, >> >> I'm wondering if anyone has an idea of how to compute the volume of >> the intersection of a sphere (center, radius) and an AABB(max,min) ? >> >> The idea being if the sphere is completely inside the AABB that the >> volume returned would be that of the sphere and as the sphere moves >> out of the AABB the volume drops to zero. >> >> I've googled but haven't been able to find anything. >> >> Thanks, >> -- >> John McCutchan <jo...@jo...> >> >> ------------------------------------------------------------------------------ >> SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, >> Nevada. >> The future of the web can't happen without you. Join us at MIX09 to help >> pave the way to the Next Web now. Learn more and register at >> http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> > > > ------------------------------------------------------------------------------ > SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada. > The future of the web can't happen without you. Join us at MIX09 to help > pave the way to the Next Web now. Learn more and register at > http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > -- John McCutchan <jo...@jo...> |
From: Jason H. <jas...@di...> - 2008-12-11 17:25:56
|
Ah. If you can tolerate a little error, you could make your object into a hierarchy of spheres rather than just a single level. If a sphere is completely above, it's above. If it's below, it's below. If it's split, traverse to the next level of the hierarchy and check again. The good thing about spheres is you can more or less use any orientation for them because you want them to fill space. So, there's only a need to generate the initial layer of spheres, then translate and scale some fixed pattern of sub-spheres inside the one you're currently testing. Best of luck, JH John McCutchan wrote: > Thanks everyone for your suggestions and interesting conversation. The > reason I asked was that I'm trying to determine how much volume of an > object (discretized into spheres) is submerged under a height field > (discretized into AABBs) and need to do this many times per frame. I > think I've figured out a cheap solution that should give reasonable > results (never count a submerged sphere twice.) > > Thanks, > John > > On Sun, Dec 7, 2008 at 5:24 AM, Willem H. de Boer <wi...@wh...> wrote: > >> Do you need an accurate answer? If accuracy is something >> you wouldn't mind say compute over several frames, then >> you could use a simple Monte Carlo-like scheme. (Though >> I think the number of sample points required is low enough >> to be able to compute the volume in real-time) >> >> One could proceed by generating random points inside >> the union of the AABB and the sphere, the total volume, >> V, of which is easy to calculate ofcourse. >> >> Then only keep those points that lie within the intersection >> of the AABB and the sphere and keep track of the ratio of >> points within to the total number of points generated, call >> this r_n. >> >> Then after a suitable number of points generated, the volume is >> roughly r_n * V. >> >> The trouble with finding an analytic description of the volume >> is that the domain of integration (i.e. the intersection of AABB >> and sphere) is usually difficult to parametrise. In such cases >> MC-like schemes work very well. >> >> Cheers, >> Willem >> >> ----- Original Message ----- >> From: "John McCutchan" <jo...@jo...> >> To: "Game Development Algorithms" <gda...@li...> >> Sent: Friday, December 05, 2008 10:00 PM >> Subject: [Algorithms] Volume of intersection of sphere and AABB >> >> >> >>> Hi, >>> >>> I'm wondering if anyone has an idea of how to compute the volume of >>> the intersection of a sphere (center, radius) and an AABB(max,min) ? >>> >>> The idea being if the sphere is completely inside the AABB that the >>> volume returned would be that of the sphere and as the sphere moves >>> out of the AABB the volume drops to zero. >>> >>> I've googled but haven't been able to find anything. >>> >>> Thanks, >>> -- >>> John McCutchan <jo...@jo...> >>> >>> ------------------------------------------------------------------------------ >>> SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, >>> Nevada. >>> The future of the web can't happen without you. Join us at MIX09 to help >>> pave the way to the Next Web now. Learn more and register at >>> http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ >>> _______________________________________________ >>> GDAlgorithms-list mailing list >>> GDA...@li... >>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >>> Archives: >>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >>> >>> >> ------------------------------------------------------------------------------ >> SF.Net email is Sponsored by MIX09, March 18-20, 2009 in Las Vegas, Nevada. >> The future of the web can't happen without you. Join us at MIX09 to help >> pave the way to the Next Web now. Learn more and register at >> http://ad.doubleclick.net/clk;208669438;13503038;i?http://2009.visitmix.com/ >> _______________________________________________ >> GDAlgorithms-list mailing list >> GDA...@li... >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list >> Archives: >> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list >> >> > > > > |
From: Jon W. <jw...@gm...> - 2008-12-08 20:30:34
|
Yes, I agree, you also have to test for sphere/face penetration cases separately. The corner vertex test is useful when the center of the sphere is outside the union of the slabs that define the box. Sincerely, jw Osman, Brian wrote: > But that doesn't catch all cases, does it? What about when the sphere > penetrates one side of the box, but with a shallow enough penetration > that it never reaches any of the corners. The trivial version of this is > when the sphere's radius is much smaller than the sides of the box, and > the sphere centered on one side of the box. > > I can't imagine solving this from scratch ... I'd certainly seek out the > existing CSG methods, and work from there. > > -Brian > > > -----Original Message----- > From: Jon Watte [mailto:jw...@gm...] > Sent: Friday, December 05, 2008 7:25 PM > To: Game Development Algorithms > Subject: Re: [Algorithms] Volume of intersection of sphere and AABB > > > Oh, and I forgot to mention: one way to classify which of the cases > you're dealing with is to check whether each vertex of the box is inside > > or outside the sphere. The sphere intersects the sides where at least > one vertex is inside the sphere (I think a side that's fully inside > still should be treated as a cutting plane). > > Sincerely, > > jw > |