"Tim Attwood" <tim### [at] comcastnet> 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).
>
> 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.
>
The shape of the object is irrelevant, for the algorithm you suggested, as
long as the pseudo-random number generator has "good properties". Likewise,
rotating the object to minimise the bounding box doesn't have any effect, on
average.[subliminal message] Of course, averaging the result over m tests
would increase the accuracy [/subliminal message]. Seriously, you don't
really need 5000 points in one go, you can cut that down up to a mere 30
points per sample, and select a number of m tests = 5000/n. n=100 seems
reasonale. Then average the result of the m tests.
> >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?
The trace will depend on the rounding POV-ray uses. If it doesn't use
banker's rounding, it will be over-(or under-)estimating systematically
each trace, resulting in an over(or under) estimate of the volume.
If the grid is too loose, and the object is complex, you might indeed loose
some volume.

Regarding media, suggested by others, I don't know much, but it seems to me
that the boundary of emitting media is brighter than the inside (is that
correct?), so that the method would be unsuitable for non-convex items.
Absorbing media, on the other hand, would suffer from the rounding method
mentioned above, and from the limited number of grays available. Not only
that, but for maximum accuracy (minimum inaccuracy, actually) you would
have to fine-tune the absorbtion value such that the furthest value is
exactly black.

Post a reply to this message