Rune wrote:
> 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).

...in most common cases that is. It won't work for, say, a sphere with a 
slightly smaller sphere carved out of it.

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.

Rune
-- 
http://runevision.com

Post a reply to this message