Computational and Algorithmic Representations of Geometric Objects - CARGO: The Geometry of Optical Paths: Intrinsic Properties, Complexity of Approximation, and Applications

詹姆斯·R·阿沃最熟悉的几何光学原理认为，照射在理想镜子上的光线将以这样一种方式出现，即反射角等于入射角。因此，光子(或台球，用另一个常见的比喻)的轨迹完全由它的初始条件和随后遇到的镜子的几何形状决定。这种轨迹的几何在许多领域都很有兴趣，包括平面几何、计算几何和计算机图形学，然而它们在属于几何光学范围内的所有光路的类别中包括一个极小的子集(零度量值的集合)。特别是，由非镜面反射产生的光路构成了一个大得多的类别。此外，它们对图像合成的重要性要大得多，因为它们是由物理上可实现的反射模型产生的。然而，到目前为止，非镜面反射路径作为有趣的几何问题的来源在很大程度上被忽视了。因此，这项研究的主要目的是对非镜面光路的基本几何性质展开初步的研究，既在传统的组合意义上，如寻找连接两点的最佳路径，在连续意义上，如S寻找极值路径，或计算连接两个区域的所有k段路径的度量。第二个目标是探索与概率方法的联系，如标准蒙特卡罗能见度技术和大都会光传输，这可能是这项工作的第一个直接受益者。这项工作有望通过识别光路本身作为有趣的几何实体，并揭示它们在密度、测量和计算复杂性方面的一些基本性质，主要为图像合成的数学基础做出贡献。此外，预计这种新的视角最终将有助于研究真实感图像合成的准确性和计算复杂性，目前对此知之甚少。虽然这里研究的问题总是与计算几何中直接和间接照明问题的前人工作有许多共同之处，但所采取的方法将具有明显更连续的风格，大量借鉴了测度论、微分几何和几何概率等领域的知识。最后，预计这项工作将通过建立基本工具和与其他学科的联系，作为对计算机图形学计算复杂性的长期研究的一个部分。

DMS-0138440James R. ArvoThe most familiar principle of geometrical optics asserts that a ray of light impinging on an ideal mirror will emerge in such a way that the angle of reflection equals the angle of incidence. The trajectory of a photon (or a billiard ball, using another common metaphor), is thus completely determined by its initial conditions and the geometry of the mirrors it subsequently encounters. The geometry of such trajectories has been of interest in numerous fields, including plane geometry, computational geometry, and computer graphics, yet they comprise a vanishingly small subset (a set of measure zero) within the class of all optical paths that fall within the purview of geometrical optics. In particular, optical paths resulting from non-specular reflections constitute a vastly larger class. Moreover, they are of far greater importance to image synthesis as they result from physically realizable models of reflection. Nonetheless, non-specular paths have thus far been largely overlooked as a source of interesting geometrical problems. The main objective of this research is therefore to launch aninitial investigation into the basic geometrical properties of non-specular optical paths, both in the traditional combinatorial sense, such as finding a optimal paths connecting two points, and in the continuous sense, such s finding extremal paths, or computing the measure of all k-segment paths connecting two regions. A secondary objective is to explore connections with probabilistic methods, such as standard Monte Carlo visibility techniques and Metropolis light transport, which will likely be the first direct beneficiaries of this work.This work is expected to contribute primarily to themathematical foundations of image synthesis by identifyingoptical paths as interesting geometrical entities in themselves, and by exposing some of their fundamental properties in terms of density, measure, and computational complexity. Moreover, it is expected that this new perspective will ultimately be instrumental in studying the accuracy and computational complexity of realistic image synthesis in general, about which very little is known currently. While the problems investigated here will invariably have much in common with previous work ondirect and indirect illumination problems in computationalgeometry, the approaches taken will have a distinctly morecontinuous flavor, drawing heavily from fields such as measure theory, differential geometry, and geometric probability. Finally, it is expected that this work will serve as a segue into a longer-term investigation of computational complexity in computer graphics by establishing basic tools and connections with other disciplines.