ITR: Making 3D Visibility Practical

在许多研究领域和应用中，关于三维可见性的有效推理是一个具有挑战性的问题，包括计算机图形学（辐射、虚拟现实漫游）、机器人（基于传感器的导航、视觉监控）、计算机视觉（识别、模型构建）、建筑、城市规划和计算生物学中的可视化。可见性问题在这些领域已经被考虑了四十年，然而，大多数早期的工作都集中在从单个视点计算可见性，而现代技术需要更多的全局可见性信息。全局可见性描述了物体之间比点更复杂的可见性关系：从空间体积区域的可见性，相对于扩展光源的本影和半影的限制，物体对之间的相互可见性，以及可见性结构变化的轨迹。尽管通过引入可见性空间分区和可见性复合体，在理解可见性方面取得了很大的进展，但到目前为止，它们对应用程序的影响很小。这是由于以下几个原因：1)最坏情况下的理论复杂性界限令人沮丧2)有许多必须处理的退化情况，使得很难实现健壮的实现3)可见性的等价导致四维细胞分解，这很难可视化4)细胞可能非常复杂（有些包括孔）。这项工作将通过在两个并行的、集成的轨道上处理问题，使三维可见性计算成为现实。其中一个涉及几个关键问题的调查，这些问题将使3D可见性算法在应用中更具吸引力和实用性：1)执行实际的复杂性分析，捕捉应用程序中典型使用的模型的预期性能，而不是从不常见的病理病例中得出的理论最坏情况2)而不是采取一般的“预计算并返回一切”方法，我们希望预计算的数量，存储在数据结构中的信息，3)通过基于关键事件和莫尔斯理论的分解算法的发展，将促进通过可见射线空间的遍历。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.