Interesting challenge: Volume of intersection

i think he mean some part of cube is inside sphere.

Teh solution for arbitrary mesh:

You know how to compute volume of object using volumes of piramids? (for 2d analog, Riemann sum you mentioned, but in polar coordinates) Then you need to do the same but compute only volume that is inside sphere.

Then do it - split cube faces into triangles, use center of sphere as center for piramids and for piramid with one vertex at center it's not hard to find part of volume of piramid that is inside sphere. (sure i can derive formule) . It's not an approximation, you don't need to tesselate.

Probably problem is as simplified as possible.

Not sure but i'll try:

1. Find the points of intersection between the cube and the sphere.
2. Construct pyramids starting from the center of the sphere and using the triangles in the triangle fan determined by the penetrating point and each two consecutive intersection points as the base.
3. Sum up the volumes of these pyramids (if you know a way to, otherwise i'd have to think about this).
4. Subtract the sum from the volume of the sphere and you get the common volume between the cube and the sphere.
EDIT 2: actually subtract the sum and the volume of the unaffected sphere (whose surface is the intersection's hull), not sure how to do this.


edit: man, beaten to it by 2 minutes :)

ok, to calculate the volume of an arbitrary pyramid:

1. find the lengths of the segments of the base
2. Use heron's formula to find the area: sqrt(p*(p-a)*(p-b)*(p-c)) where p = 0.5(a + b + c) and a, b, c are the sides of the triangle
3. Calculate the surface normal of the base plane.
4. Calculate the distance between the apex (in your case the center of the sphere) to the base plane (project it onto the plane)
5. calcualte the volume using this distance and the area of the base

[Edited by - Ilici on October 21, 2004 4:34:45 AM]

Quote:

Original post by Ilici Not sure but i'll try: 1. Find the points of intersection between the cube and the sphere. 2. Construct pyramids starting from the center of the sphere and using the triangles in the triangle fan determined by the penetrating point and each two consecutive intersection points as the base. 3. Sum up the volumes of these pyramids (if you know a way to, otherwise i'd have to think about this). 4. Subtract the sum from the volume of the sphere and you get the common volume between the cube and the sphere. edit: man, beaten to it by 2 minutes :) ok, to calculate the volume of an arbitrary pyramid: 1. find the lengths of the segments of the base 2. Use heron's formula to find the area: sqrt(p*(p-a)*(p-b)*(p-c)) where p = 0.5(a + b + c) and a, b, c are the sides of the triangle 3. Calculate the surface normal of the base plane. 4. Calculate the distance between the apex (in your case the center of the sphere) to the base plane (project it onto the plane) 5. calcualte the volume using this distance and the area of the base

our ideas is different and i don't sure how your idea will work -
as i imagine you'll get [volume of sphere] - [volume of piramids] , and if cube only touch sphere, you'll get [volume of sphere]-[something small] as result...
Also lines of intersection with sphere isn't straight, so you need to compute not piramidal volume but something different.

another thing, i'm not very sure, but to compute piramid volume with points abcd, you simply need something like (1/6)*(A-B)x(A-C).(A-D)
where x is cross product and . is dot product.
edit: my piramid volume formule seems to be correct.

Ok i think you're right as my algo works only for a single point of the cube penetrating the sphere, but i think it could work for line intersections with some modifications for the pyramid construction.

Quote:

Original post by Ilici Ok i think you're right as my algo works only for a single point of the cube penetrating the sphere.

also note that you may have situation where no point penetrates sphere , but 'em may be intersected anyway.

Quote:

Original post by Dmytry Quote: Original post by Ilici Ok i think you're right as my algo works only for a single point of the cube penetrating the sphere. also note that you may have situation where no point penetrates sphere , but 'em may be intersected anyway.

If the cube is just tangent, there will be a single point of intersection so we can ignore the case.

Also, i check out EDIT2 in my OP, i made a mistake there.

Quote:

Original post by Ilici Quote: Original post by Dmytry Quote: Original post by Ilici Ok i think you're right as my algo works only for a single point of the cube penetrating the sphere. also note that you may have situation where no point penetrates sphere , but 'em may be intersected anyway. If the cube is just tangent, there will be a single point of intersection so we can ignore the case. Also, i check out EDIT2 in my OP, i made a mistake there.

ops, i meant to say, "no vertice penetrates sphere"...

Quote:

Original post by Dmytry ops, i meant to say, "no vertice penetrates sphere"...

In that case, wouldn't the volume be a slice of the sphere (not sure about the word - calot?) - obtained by cutting the sphere with a plane. The volume of the slice is easy to calculate.

Quote:

Original post by Ilici Quote: Original post by Dmytry ops, i meant to say, "no vertice penetrates sphere"... In that case, wouldn't the volume be a slice of the sphere (not sure about the word - calot?) - obtained by cutting the sphere with a plane. The volume of the slice is easy to calculate.

easy,but you have to handle all special cases.Imagine one point penetrates sphere a bit, and also there's almost quarter of that "calot" - what your algo will do?

Also what if edge penetrates the sphere?

I don't know the analytical solution for that kind of stuff, but for a good (or even extremly good) approximation, a standard integration method should do the trick, or some kind of tree-based integration for very good accuracy and speed (like an octree of AABoxes).

Timkin,

I'm assuming, since you haven't a really good solution already, that the radius of the sphere is not so large that you can treat the sphere as a clipping plane, and just find the volume of the cube on one side of the clipping plane. Correct assumption? If it is NOT (and the radius is >>>> cube edge length), and if I understand the problem correctly, the effectively infinite radius sphere ~ clip plane approach could work well, e.g., the solution could be within roundoff error of a true analytic sphere/cube intersection algorithm or within roundoff + truncation error of a discretized solution.

Lets consider the general case when the sphere radius is > cube edge length but not >>>>> cube edge length.

To find the volume of intersection, you're basically wanting to integrate over some arbitrary volume *containing* both the sphere and cube, e.g.:

Volume of intersection=integral[(density)dV]

where dV is a differential element of volume of the containing region and density is either 1 (if the differential element is contained in the sphere and cube) or 0 (if the element is not contained in both).

The volume integral reduces to a surface integral by the Divergence Theorem (as you know), allowing you to integrate only over the boundary surfaces, e.g., the bit of sphere surface on the outside and the bits of cube surface on the inside. If you can find the exact boundaries (which you can in this case---though its tedious), then you could compute a numerically "exact" volume this way.

Now, if all those surfaces were planar, you could easily use Green's Theorem to reduce the surface integrals down to line integrals (as you know). But that darned sphere surface fragment means you don't have planar surfaces. HOWEVER, a mapping should make it possible. Integrate the cube surfaces as line integrals using Green's Theorem. Sure, the boundary edges at the sphere intersection aren't themselves linear, but they are in the plane of the cube faces so Green's Theorem works. And, for the sphere surface, use spherical coordinates to map the sphere surface onto a plane in which the two angular coordinates are the coordinates of planar integration...this should make sense to you, though its going to be tedious and possibly quite annoying to actually do.

For inspiration you can look at Brian Mirtich's paper in which he develops some of this for polyhedra:

Fast and Accurate Computation of Polyhedral Mass Properties

Quote:

Original post by xor Hi i didn't read all the answers so i don't know if the problem was already solved, or if the (possible)solution i'm about the give was already posted. Also i'm no expert in this field, so considering all the above, if i repeat something already said or i give an absolutly wrong answer, please excuse me, just trying to help. =) I sent a message privately to Timkin asking if he could calculate the space of the intersection of a sphere/cube and a plane, and for both he said it was pretty trivial, so based on that assumption i'll sugest a possible solution. This possible solution, doesn't work for, a sphere completely inside a cube, a cube completely inside a sphere, and a sphere or a cube small enought to have more then 4 points of intersection.(Since in the orignal post these cases weren't contemplated i assume it won't be a problem) Possible solution: You have a sphere and a cube intersected. Now visualise just the intersection points with the cube, you get a plane from the intersection points and a cube, you can calculate that area. Now visualise only the sphere and the intersection points, again you get a plane from the intersection points and a sphere, you can also calculate that area. The sum of those areas are the total intersection area. PS - I forget to ask if finding the intersection points was trivial Hope this helps somehow =)

finding intersection points is trivial(line-sphere intersection) but
1:if there's >3 intersection points,them probably don't lie exactly on same plane.
2: even if there's only 3 intersection points, you'll get wrong results, because volume cut by plane must be also cut by cube faces.
but it may be used as approximation, probably.

Quote:

Original post by xor Dmytry: On point 1, you're right, they won't. I never thought of that. Still, in a more complicated way it's still possible to do it, for one shape at a time, group the intersection points in a group of 3, calculate the intersection area, then chose the oposite 3 group, calculate it again, them add the two areas subtracting the intersection. Now do the same for the other shape. Isn't has simple as i thought it would be though. =) On point 2, i'm not sure what you mean, i was aiming at finding the intersection of the area of a perfect sphere with a cube, so there would be no faces in the sphere. If the sphere is to have faces, the calculation will be wrong.

i mean different thing.
Volume you cut from sphere with your plane looks like lens |) shape, with circular border, and it should have non-circular border because cut by cube's faces.
I mean, let's you have 3 points of intersection A,B,C. (only one vertice of cube is inside the sphere)

Volume of intersection looks like piramid with curved bottom, but bottom sides of piramid looks like triangle with slightly curved edges.

And with your method you get bigger volume:
You make a plane that pass the points ABC. Then you cut piece of your sphere with that plane, and piece of cube. Piece of sphere have circular border and looks like lens with flat side. Piece of cube looks like piramid.

When you add up piece of cube to piece of sphere you get shape that looks like piramid staying on flat side of lens with circular border. It can be seen that it's larger than volume of intersection because it contains volume of intersection and some additional volume.

Visualising in 3D it's exactly what i did. In 2D it works as you said. But in 3D :
that curved bottom have 2 slightly curved edges.
And lens-like piece of sphere have completely circular border.
In fact, lens-like piece of sphere contains curved bottom plus some more volume that shouldn't be there.

edit: that is, imagine piramide staying at flat side of lens ,and lens have radius so all piramid base vertices is at border of lens.

You're right.

How can a plane intersection with a sphere output a shape with flat sides like a piramid base. You're right.

I'm going to delete the posts, the 'method' is completely bogus.

Hey, You made method that gives upper and lower bound for volume of intersection in some special case. (lower bound - without sphere slice, upper with), and it may be good. At least if someone will implement algo your method can be used for some testing. So don't delete posts.

Too late =)
You have them on quote though, no harm done.

ok, here we go! :-)

something like this:
(convert sphere into cubespace, so that x,y,z are cube directions)

#1
find the paralell planes of the cube, that devides the sphere least evenly (if sphere is inside, irellevant, if two is equal, pick one...)

#2
divide sphere in the middle with this plane (in imagination, no geometry splitting)

#3
Now you should have 2 3D graphs witch are based on functions, one pointing each way out from your halv sphere plane. with a function like: f(x,y)=z (x,y is splittingplane, z = depth/volum), representing the spheres total volum

#4
Scale the functions x and y, and offset the center, so that the other edges of your cube becomes a (0,0) - (1,1) array....
so that 0,0 is one corner of your cube, watched trough the splitt-plane, and 1,1 is the oppositt corner.
(this is for easy handeling generalisation stuff)
Now the total volum of your two functions should be:
spherevolum = funcvolum * width * height
(depth is the splitt direction, we need to keep this)

#5
integrate both the functions (witch still are equal) to get funcvolum (since the funcvolum is just a full, scaled sphere this could be done fast
funcvolum = spherevolum / cube_width*cube_height*2
for each half)

#6
Now we need to clip each volum two times...
the functions should be something like:
f(x,y) =
sqrt( scaledx - square(x - offsetx)) times
sqrt( scaledy - square(y - offsety))

#7
For each sphere side, calc volum inside plane closest to sphere center from (0,0) to (1,1)...
i know this is possible, but it will not be very fast...
so that volum =
integated f(x,y) from (0,0) to (1,1)
where f(x,y) > cube_plane pointing away from half_sphere top
save as big_volum
if all is inside, you get big_volum = funcvolum
if all is outside, big_volum = 0
next,
integrates f(x,y) from (0,0) to (1,1)
where f(x,y) > cube_plane pointing towards half_sphere top
save as small_volum
if all is inside, you get small_volum = funcvolum
if all is outside, small_volum = 0

(planes here will just be 1 dim variables)

side_volum = big_volum - smal_volum

add the two sides, and you got your func_volum_in_sphere

the integration, should be possible to solve into one general function, witch you can use, cant solve this in my head right now.. anybody?

#8
to get the volum_in_sphere, multiply func_volum_in_sphere with width and height!

tada!