Re: [Algorithms] Volume of intersection of sphere and AABB

[Willem H. de B. <wi...@wh...>]

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
>