by Marco Pellegrini
We present a new approach to problems in computational physics that uses techniques developed in the field of computational geometry. This line of research is now under way at the Istituto di Matematica Computazionale (IMC-CNR), Pisa.
Modelling of physical continuous phenomena is a complex task. The standard approach can be described as follows. Firstly a description of the physical aspects is produced via a set of differential equations which describe the local behaviour. Secondly the global geometry of the problem is modelled via a meshing. Thirdly, the differential equations are integrated over each single mesh element according to a suitable approximation criterion. The consistency requirements of the whole system are then translated into a system of linear equations which is solved using methods from Computational Linear Algebra.
Traditionally the requirements on the geometric meshing were expressed without specific reference to the original physical problem. For example, it is usually required that a triangulation of a set of points on the plane should have the largest minimum angle. This requirement is satisfied by the Delaunay triangulation, which justifies the extensive research on this topic.
Our research departs from this standard scenario. We believe that geometric aspects should be more tightly coupled with the initial phase of physical modelling. We give two examples where this approach has produced significant progress. The first example is a problem of radiant energy transfer. The second problem is the computation of electrostatic forces.
Radiant Energy Transfer and Form Factors
The exchange of radiant energy (e.g. visible light in Graphics, or infra-red radiation in Heat Transfer Engineering) in simple classical models is approximated by the solution of a system of linear ``energy transport" equations. Each variable in such a system represents the total energy emitted by a discrete surface element, and the coefficients depend on the "form factors" between pairs of surface elements. A form factor is the fraction of energy leaving one element which directly reaches the other. 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.
We have introduced a new geometric characterization of form factors and developed a new asymptotically efficient Monte Carlo method for simultaneously approximating all form factors in an {\em occluded} polyhedral environment. This is the first algorithm for which an asymptotic time bound {\em and} a bound on the absolute approximation error has been proved. For typical scenes, it is an order of magnitude faster than methods based on the popular hemisphere paradigm.
Computation of Electrostatic Forces
We consider the following problem which arises in the computation of electrostatic fields. We are given two disjoint polyhedra in 3-space, endowed with a known charge density, and we want to compute the electrostatic force acting on the two polyhedra. We have introduced a Monte Carlo method that, for a large class of density functions, computes an approximation of the electrostatic force within the desired error bounds. We also give asymptotic bounds on the running time which depend on the input size and the error bound.
This result is obtained using a new interpretation of the electrostatic field, based on integral geometry, which eliminates the singularities present in traditional definitions derived from Coulomb's law. The method uses powerful properties of planar projections and does not require any 3-dimensional meshing.