The error images in my previous post are the relative error of the lightcuts image w.r.t. the reference image (i.e. abs(lightcuts - reference) / reference). This error differs from the error bound used in the lightcuts algorithm because the reference solution is obviously not available during the lightcut calculations. The lightcuts algorithm uses an upper bound on the total illumination (further referred to as
maximum total illumination or
mti) to determine whether the maximum error for a particular cluster is acceptable (i.e. it is smaller then some percentage of the mti). So the lightcuts algorithm gives no real guarantee w.r.t. the real relative error. Such a guarantee would require using a
minimum total illumination which is a lot harder then a maximum because a decent lower bound on the visibility term is necessary.
During cut refinement the estimate of the mti is also improved using the bounds computed for the refined clusters. This means that not only the error bounds on the individual clusters drops, but also the mti and thus the maximum allowed error.
In pseudo-code the lightcut algorithm is something like this:
rootUpperBound = calc. upper bound root cluster
mti = rootUpperBound
root.maxerr = rootUpperBound
cut = [root]
while(largest cluster error in cut > some% of mti) {
cluster = remove cluster from cut with largest error
left = cluster.leftchild
right = cluster.rightchild
leftUpperBound = calc. upper bound left cluster
rightUpperBound = calc. upper bound right cluster
if(left is leaf)
left.maxerr = 0;
else
left.maxerr = leftUpperBound
if(right is leaf)
right.maxerr = 0
else
right.maxerr = rightUpperBound
mti -= cluster.maxerr
mti += leftUpperBound + rightUpperBound
cut = [cut left right]
}
The lowering of the mti can result in some unexpected effects like a reduction in cut size for occluded pixels if the number of lights increases. This is caused by a cascade effect if too few light sources are used at these occluded pixels. At some point during cut refinement a leaf node is reached. Because the point is occluded, the mti will be significantly reduced (the previous node still had a non-zero upper bound). This results in more nodes that need to be refined which again results in new leaf nodes.
The use of the mti instead of the reference image in the calculation of the maximum acceptable error also explains the large relative errors in shadow boundaries as visible in the error images of my previous post. In the highly occluded regions the mti is significantly higher then the real illumination due to the poor visibility bound (i.e. everything is visible), so the lightcuts algorithm will allow too large errors.
