Hi all...

[Reposted from mistaken thread in povray.programming]

What is the best method in POV-Ray for finding the
volume of a simple convex (that is, no hollows or cavities)
object that is the intersection of two other objects?

One way might be to iteratively intersect this object
with a series of long thin boxes incremented
along (for example) the xy plane, and use the Extents macro
in shapes.inc to get the length of the box. Summing these
box volumes would return a total volume slightly larger
than the real volume.

Another way might be to use the Isect macro to get
the intersection points at each corner of each "box"
and calculate the volume of the resulting polyhedron.

Is there an easier way to do this?

Regards,
Chris


-- 
||||| www.kinata.net web design and hosting

Post a reply to this message

Wasn't it Chris Kinata who wrote:
>Hi all...
>
>[Reposted from mistaken thread in povray.programming]
>
>What is the best method in POV-Ray for finding the
>volume of a simple convex (that is, no hollows or cavities)
>object that is the intersection of two other objects?
>
>One way might be to iteratively intersect this object
>with a series of long thin boxes incremented
>along (for example) the xy plane, and use the Extents macro
>in shapes.inc to get the length of the box. Summing these
>box volumes would return a total volume slightly larger
>than the real volume.

The Extents macro won't help. It will return the full length of the box
rather than just the portion that intersects the target object. 

I'd suggest using trace() in the same sort of way. Use trace to find the
two points where the midline of the long thin box intersects the surface
and multiply the distance between them by the cross section area of the
(now imaginary) box.

Here's a quick test with a sphere. I've used a sphere because I know
what the actual result should be. 

#declare THING = sphere {0,1}

#debug concat("Actual volume = ", str(4/3 * pi,-1,-1), "\n")

#declare Step = 0.01;
#declare Area = Step*Step;

#declare Vol = 0;

#declare X=-1;
#while (X<1) 
  #declare Y=-1;
  #while (Y<1)
    #declare P1 = trace(THING, <X,Y,1000>, -z);
    #declare P2 = trace(THING, <X,Y,-1000>, z);
    #declare Vol = Vol + (P1.z - P2.z)*Area;
    #declare Y = Y + Step;
  #end
  #declare X = X + Step;
#end

#debug concat("Calculated volume = ", str(Vol,-1,-1), "\n")

Shooting 10000 pairs of rays gives four figure accuracy.
     

-- 
Mike Williams
Gentleman of Leisure

Post a reply to this message

Hi Mike,

Thanks, really cool...

So in your code, we're:

-- Scanning over the xy plane, shooting rays parallel
to the z-axis, down from above and up from below.

-- If the z-values of the intersection points returned
are equal, the object has no thickness at that xy coordinate.
If they're both 0, there was no intersection, or the object
coincides with the xy plane at that point.

I can use this to code a macro that takes an object and a
step increment, and then uses its extents to find what part
of the xy plane to scan, and returns the estimated volume.

Maybe at some point I could add code that sort of recursively
continues a scan ray through the object, testing whether a
given surface-to-surface vector is inside or outside. This would
permit estimating the volume of concave objects.

Regards,
Chris

> Here's a quick test with a sphere. I've used a sphere because I know
> what the actual result should be.
>
> #declare THING = sphere {0,1}
>
> #debug concat("Actual volume = ", str(4/3 * pi,-1,-1), "\n")
>
> #declare Step = 0.01;
> #declare Area = Step*Step;
>
> #declare Vol = 0;
>
> #declare X=-1;
> #while (X<1)
>  #declare Y=-1;
>  #while (Y<1)
>    #declare P1 = trace(THING, <X,Y,1000>, -z);
>    #declare P2 = trace(THING, <X,Y,-1000>, z);
>    #declare Vol = Vol + (P1.z - P2.z)*Area;
>    #declare Y = Y + Step;
>  #end
>  #declare X = X + Step;
> #end
>
> #debug concat("Calculated volume = ", str(Vol,-1,-1), "\n")
>
> Shooting 10000 pairs of rays gives four figure accuracy.
>
>
> -- 
> Mike Williams
> Gentleman of Leisure

Post a reply to this message

Mike, I'm wondering how this works for anything other than a sphere of 0,1 ,
and I'm trying to figure out how the trace function doesn't flake out when
you "miss" the object completely.

Consider:
http://news.povray.org/povray.text.scene-files/thread/%3C39bc2947%40news.povray.org%3E/?ttop=203039&toff=300



--
Greg M. Johnson

Post a reply to this message

Just a suggestion: adaptive integration. Recursively subdivide the object
into octants, comparing the volume calculated from each subdivision with
the previous stage, and stopping subdivision when the difference in
calculated volumes drops below a certain level.

I've used this technique succesfully in 2D, I don't see any reason for it
not to work in 3D. Adaptive integration is most efficient when each stage
can reuse the results from the previous stage.

Post a reply to this message

Wasn't it gregjohn who wrote:
>Mike, I'm wondering how this works for anything other than a sphere of 0,1 ,

It works for any convex object that fits inside the unit sphere.
For objects that don't fit into the unit sphere you could use min_extent
and max_extent of the object.

>and I'm trying to figure out how the trace function doesn't flake out when
>you "miss" the object completely.

When it misses, trace() returns P1 = <0,0,0>and P2 = <0,0,0>, so 
(P1.z - P2.z)*Area is zero, and that line adds nothing to the volume.

I could have got trace() to return a normal and checked that in the
documented manner to determine if trace() had missed, but it's probably
more efficient to just add the zero.

(It might possibly be more efficient to check to see if the trace() in
one direction hits, and only perform the second trace() if the first one
succeeds, but I was writing it in the middle of the night and couldn't
be bothered with such fine points.)

>Consider:
>http://news.povray.org/povray.text.scene-files/thread/%3C39bc2947%40news.povray.
>org%3E/?ttop=203039&toff=300

I guess that approach might work for concave objects too.

-- 
Mike Williams
Gentleman of Leisure

Post a reply to this message

Will scanning the object (in X, Y and Z) with the inside() function do what
you want? I've used that approach to compute the centre of mass for things,
I don't think it's much different. You can easily modify it to do the
adaptive subdivision thing as well.

Post a reply to this message

> What is the best method in POV-Ray for finding the
> volume of a simple convex (that is, no hollows or cavities)
> object that is the intersection of two other objects?


Out of curiosity, why?

People ask this question a lot, but I've never found it necessary myself.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

I've been interested in using a method like this for collision detection of
oddly-shaped objects...you know, find the volume of the intersection of the
two objects...if it's not zero, then they've collided.  There's probably a
more mathematically correct way of doing it, but often it turns out I can't
be bothered to figure out the necessary maths for doing it "right" when an
approximation will work almost as well...

Cheers,
Joe

Post a reply to this message

"Slime" wrote
> Out of curiosity, why?

In this specific instance, my sailboat was destroyed a couple
of months ago, and I've salvaged its lead-filled keel. Getting
it weighed (~1500lbs) has proved problematic, but I've taken
measurements, can model its shape, and wanted to estimate
its weight using the density of lead.

A longer-term "why" is that I'm interested in modeling objects
and then create them physically. Rather than develop mathematical
models independently of POV-Ray (say in Excel), wanted a
general approach for estimating volume of complex shapes.

For example, I want to design a series of cascading bowl-shapes
for a water feature in a garden, define shapes, sizes, thicknesses,
etc., and then cast them in concrete. It would be cool to get
a readout of volume of concrete needed and the resulting cast
weight.

--Chris

Post a reply to this message