ITR: Making 3D Visibility Practical

在计算机图形学(光能传递、虚拟现实漫游)、机器人(基于传感器的导航、视觉监视)、计算机视觉(识别、模型构建)、建筑、城市规划和计算生物学中的可视化等许多研究领域和应用中，关于三维可见性的有效推理是一个具有挑战性的问题。可见性问题在这些领域已经被考虑了40年，然而，大多数早期的工作都集中在从单一视点计算可见性，而现代技术需要更多的全局可见性信息。全局可见性描述了比点更复杂的对象之间的可见性关系：空间体积区域的可见性、相对于扩展光源的本影和半影的限制、对象对之间的相互可见性以及可见性结构变化的轨迹。尽管通过引入可见性空间分区和可见性复合体在理解可见性方面取得了很大进展，但到目前为止它们对应用的影响很小。这是由于以下几个原因：1)最坏情况的理论复杂性界限令人沮丧2)有许多退化的情况需要处理，使得健壮的实现变得困难3)可见性的等价性导致四维单元分解，这很难可视化4)单元可能非常复杂(一些包括洞)。这项工作将通过在两个并行的、集成的轨道上处理该问题来使3D可见性计算变得实用。一种涉及对使3D可见性算法在应用中更具吸引力和实用性的几个关键问题的研究：1)执行实际的复杂性分析，其捕捉通常在应用中使用的模型的预期性能，而不是从不常见的病理情况导出的理论上的最坏情况范围2)与采用一般的“预计算并返回一切”方法不同，我们希望预计算量，存储在数据结构中的信息，3)通过基于关键事件和Morse理论的分解算法的开发，将有助于遍历可见性射线空间。4)我们将开发关于演变的阴影空间(不可见点集)的推理技术，这是许多涉及移动视点的问题所必需的。第二条轨道涉及基于健壮的可见性基元的3D可见性库的开发。我们希望通过将这个库免费提供给其他研究人员，对应用程序产生立竿见影的影响。该图书馆将在研究发展过程中作为一个有用的可视化和评估工具，并在工作完成后作为激发其他对3D可见性的兴趣和应用的方式。这一努力，再加上从调查关键可见性问题中获得的理解，预计将对依赖于能见度信息有效处理的各种应用程序产生广泛影响。

Efficient reasoning about three-dimensional visibility is a challenging problem in many research areas and applications, including computer graphics (radiosity, virtual reality walkthroughs), robotics (sensor-based navigation, visual surveillance), computer vision (recognition, model building), architecture, urban planning, and visualization in computational biology. Visibility issues have been considered for four decades in these areas however, most early work has focused on computing visibility from a single viewpoint, while modern techniques require more global visibility information. Global visibility describes the visibility relationships etween objects that are more complex than points: visibility from a volumetric region of space, limits of umbra and penumbra with respect to an extended light source, mutual visibility etween pairs of objects, and loci of structural changes of visibility.Although great strides have een made in understanding visibility through the introduction of visibility space partitions and the visibility complex, they have so far had little impact on applications. This is due to several reasons: 1) worst-case theoretical complexity bounds are discouraging 2) there are many degenerate cases that must be handled, making it difficult to make robust implementations 3) equivalences in visibility lead to a four-dimensional cell decomposition, which is difficult to visualize 4) cells can be extremely complicated (some include holes).This work will make 3D visibility computations practical by approaching the problem in two parallel, integrated tracks. One involves the investigation of several key issues that will make 3D visibility algorithms more attractive and practical in applications: 1) performing practical complexity analysis that captures the expected performance for models that are typically used in applications, as opposed to theoretical worst-case ounds derived from uncommon pathological cases 2) rather than taking a generic "precompute and return everything" approach, we would like the amount of precomputation, information stored in data structures, and extraction algorithms to be nicely tailored to the number of queries and the type of information arises in a particular application 3) traversal through the space of visibility rays will be facilitated through the development of decomposition algorithms based on critical events and Morse theory 4) we will develop techniques for reasoning about the evolving shadow space (set of points not visible), which is required for many problems that involve moving viewpoints.The second track involves the development of a 3D visibility library ased on robust visibility primitives. We expect to make an immediate impact on applications by making this library available for free to other researchers. The library will serve both as a helpful visualization and evaluation tool during the development of the research, and as a way to stimulate other interest and applications of 3D visibility after the work is completed. This effort, combined with the understanding gained from investigating the key visibility issues, is expected to make a broad impact on a wide array of applications that depend on efficient processing of visibility information.