Error and complexity of random walk Monte Carlo radiosity

摘要

The author studies the error and complexity of the discrete randomnwalk Monte Carlo technique for radiosity, using both the shooting andngathering methods. The author shows that the shooting method exhibits anlower complexity than the gathering one, and under some constraints, itnhas a linear complexity. This is an improvement over a previous resultnthat pointed to an O(n log n) complexity. The author gives and comparesnthree unbiased estimators for each method, and obtains closed forms andnbounds for their variances. The author also bounds the expected value ofnthe mean square error (MSE). Some of the results obtained are also shownnto be valid for the nondiscrete gathering case. The author also givesnbounds for the variances and MSE for the infinite path lengthnestimators; these bounds might be useful in the study of biasednestimators resulting from cutting off the infinite path