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

几何对象的计算和算法表示 - CARGO：光路几何：内在属性、近似的复杂性和应用

• 批准号: 0353203
• 负责人: James Arvo
• 金额: $ 9.68万
• 依托单位: University of California-Irvine
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-02-10 至 2004-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0353203&HistoricalAwards=false
• 关键词: Computational; Algorithmic; Representations; Geometric; Objects

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.

DMS-0138440James R.最熟悉的几何光学原理认为，一束光照射在理想的镜子上，反射角等于入射角。 因此，光子（或台球，使用另一种常见的比喻）的轨迹完全由其初始条件和随后遇到的镜子的几何形状决定。 这种轨迹的几何形状在许多领域都很受关注，包括平面几何、计算几何和计算机图形学，但它们在属于几何光学范围内的所有光路的类别中包括一个极小的子集（一组测量零点）。 特别地，由非镜面反射产生的光路构成了大得多的类别。此外，它们对图像合成的重要性要大得多，因为它们来自物理上可实现的反射模型。 尽管如此，非镜面路径迄今为止在很大程度上被忽视为有趣的几何问题的来源。因此，本研究的主要目标是对非镜面光路的基本几何性质进行初步研究，无论是在传统的组合意义上，如找到连接两点的最佳路径，还是在连续意义上，如找到极值路径，或计算连接两个区域的所有k段路径的度量。 第二个目标是探索与概率方法的联系，如标准蒙特卡罗可见度技术和大都会光传输，这将可能是这项工作的第一个直接受益者。这项工作预计将主要有助于图像合成的数学基础，通过识别光路本身作为有趣的几何实体，并通过揭示它们的一些基本性质的密度，测量和计算复杂度。 此外，预计这种新的视角最终将有助于研究逼真图像合成的准确性和计算复杂性，目前对此知之甚少。 虽然这里调查的问题将总是有很多共同点与以前的工作ondirect和间接illumination问题在computationalgeometry，所采取的方法将有一个明显的morcontinuous风味，绘制大量的领域，如测量理论，微分几何，几何概率。最后，预计这项工作将作为一个segue到计算机图形学的计算复杂性的长期调查，建立基本的工具和连接与其他学科。