ITR: Making 3D Visibility Practical

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