> For objects that fill a reasonably high percentage of the bounding box 
> (such as a sphere) it wouldn't be a big problem unless you really care 
> about high accuracy. For other objects though, such as, say, a cylinder 
> from <-1,-1,-1> to <1,1,1> with radius 0.01, testing all points (with some 
> proximity) within the bounding box is extremely inefficient. However, 
> pre-testing with trace lines within the bounding box parallel with one or 
> more axes could be used to weed out by far the most points beforehand, and 
> this would only be O(n^2).

It just occured to me that the object can be rotated and the bounding
box tested for minimum volume to reduce the bounding volume on long
narrow objects, it wouldn't do much for spikey things though.

>Come to think of it, the tracing could be used iteratively to do the volume 
>calculation in the first place. This would work in all cases and would only 
>be O(n^2*m) where m represents the complexity of the object.

So, if you start with a grid and trace across, measuring the surface 
locations
with the trace to determine the distance of the line that is inside the 
object
at each grid point and then average all the distances, then the average
divided by the depth of the bounding box should be the percentage of the
bounding volume that represents the object volume? Sort of like sticking
a bunch of long pins into it and measuring how much is inside? Wouldn't
some objects still squeeze thru the grid?

Post a reply to this message