Although I'd consider myself a math geek as well, I'm not so good when it comes
to statistics, so maybe someone can help me out with this one I need for
radiosity optimizations:

The problem I need to solve is probably quite similar to those famous quality
control jobs, where you produce (or buy) something and need to take samples, to
make sure with a certain confidence that only a certain maximum percentage of
the products fails to meet the specifications.

So in its simplest form, the question would be:

(1) Given an allowed percentage of failure p (say, 10% may be faulty), and a
desired test confidence q (say, I want to be 95% sure that those 10% are met),
how many samples do I need to take (need a formula though, not just values for
this case)?

However, being the miser I am, and each test being very costly, I don't want to
waste a single penny; so when my first samples look like I'll only have 1% of
failures, I get the idea that I might not have to do all these tests, but cut
them short.

(2) Again given allowed percentage of failure p and a confidence q, a number of
samples taken already N, and a number of failures among them M, the question
is: Can I stop testing here, because I (a) can be sure enough I'll have too
many failures and should better optimize my production, (b) can be sure enough
my level of quality is ok, or (c) do I need to continue taking samples before I
decide?

Now things get even more complicated: Let's say that with every failed product,
I can do an analysis of what went wrong, and eliminate that source of error
from my production (unfortunately I don't know by how much the overall quality
will improve by this). What can math tell me about this?


So much for the pure math; in case you're interested, and might have additional
ideas, this is how it relates to POV's radiosity (note that there's an
additional feedback here, that causes the percentage of failure to in fact
decrease as I take samples):

I intend to re-design the pretrace sequence, and throw out the current fixed
start and end resolution. Instead, I want to specify a (user-defined) maximum
allowed percentage of samples to be taken during final render, and have the
pretrace run until that requirement is met with a certain (hard-coded)
confidence. This will be done on a per-tile basis, and tiles proving to be
particularly problematic will be split up even more recursively, to get some
adaptive element.

In order to do this, while I am generating samples during pre-trace I want to
keep an eye on the ratio between the "radiosity queries" (not necessarily equal
to the number of rays shot) triggered, and the new samples gathered (the
"failures") to satisfy these queries (both per tile), and stop work on a tile
as soon as I'm confident enough that the final render will not take
(significantly) more new samples than the user declared as acceptable.

Questions that still bug me here:

- When can I stop work on a single tile because I can be confident that it has
enough samples?

- Is there a smart way to find out "on the fly" how good I am doing "right now"
(instead of just how good I have been doing "so far" since I started, which
will always look worse because I'll have improved since then with every
failure), without having to use designated "measuring intervals"?

- When does it make sense to "drill down" on a certain tile, and effectively
split it up into four? Doing it too soon might have memory requirements go
berserk. (Hm... thinking about it, maybe I should always keep track of the
pretrace quality separately for every quarter even while I'm still pretracing
it as a whole, and drill down as soon as I am happy with one quarter of the
tile but still significantly unhappy with some other.)

- When I "drill down" on a certain tile, is there a way I can re-use information
obtained on the whole combined tile so far? (Then again, maybe the smartest
thing to do when drilling down is to start a brand new measuring interval
anyway.)

Thanks in advance for any helpful or inspiring comments!

Post a reply to this message