Monte carlo approximation of form factors with error bounded a priori

The exchange of radiant energy (e.g., visible light, infrared radiation) in simple macroscopic physical models is sometimes approximated by the solution of a system of linear equations (energy transport equations). A variable in such a system represents the total energy emitted by a discrete surface element. The coefficients of these equations depend on the form factors between pairs of surface elements. A form factor is the fraction of energy leaving a surface element which directly reaches another surface element. Form factors depend only on the geometry of the physical model. Determining good approximations of form factors is the most time-consuming step in these methods, when the geometry of the model is complex due to occlusions. In this paper, we introduce a new characterization of form factors based on concepts from integral geometry. Using this characterization, we develop a new and asymptotically efficient Monte Carlo method for the simultaneous approximation of all form factors in an occluded polyhedral environment. The approximation error is bounded without recourse to special hypothesis. This algorithm is, for typical scenes, one order of magnitude faster than methods based on the hemisphere paradigm or on Monte Carlo ray-shooting. Let A be any set of convex nonintersecting polygons in R ³ with a total of n edges and vertices. Let ε be the error parameter and let δ be the confidence parameter. We compute an approximation of each nonzero form factor such that with probability at least 1-δ the absolute approximation error is less than ε. The expected running time of the algorithm is , where K is the expected number of regular intersections for a random projection of A. The number of regular intersections can range from 0 to quadratic in n, but for typical applications it is much smaller than quadratic. The expectation is with respect to the random choices of the algorithm and the result holds for any input. Received March 17, 1995, and in revised form April 10, 1996.