计算机图形学论文 | 多边形中的点可见性快速算法

🦌🦌🦌读论文

🐨🐨摘要

针对点的可见性计算这一计算几何中的基础问题，提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法。以与Voronoi骨架路径对应的Voronoi通道概念，以及相应的局部最短路径概念为基础，按照深度优先策略对Voronoi图进行遍历，在计算Voronoi骨架路径的同时计算局部最短路径，并基于局部最短路径计算所遍历的多边形边的可见部分。该算法可以处理“带洞”多边形，而且只对多边形进行局部访问：对于“带洞”多边形，由于该算法的数据结构比较简单、剖分空间合理且易于实现，因此仅需O(n)空间和O(n log n)预处理时间，最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例，结果表明文中算法是实际可行，且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系。

🐨🐨相关工作

🐼点的可见性计算

对于点可见多边形计算问题，计算几何领域有很多相关的工作。点的可见性计算是最基础的问题，其典型应用包括艺术画廊中的警卫间问题、机械模型浇注、无线传感网络中的覆盖问题等。在计算机图形学、计算机游戏和虚拟现实等领域，其作为实时绘制中的一种关键技术，根据视点的位置计算可见区域，并将可见区域中的对象加入图形绘制流水线，提高绘制效率。

🐼简单多边形的可见性算法

对于简单多边形，文献[16]提出了一种基于三角化的点的可见多边形算法，它首先对简单多边形进行三角化，并基于三角化的结果构造查询点的最短路径树，然后基于该最短路径树计算多边形的每条边相对于查询点的可见部分，最后得到点的可见多边形，算法时间复杂度为O(n)。

🐼“带洞”多边形的可见性算法

近年来，又出现了一些基于可见区域分割或可见图计算“带洞”多边形中点的可见多边形的算法。这些算法的数据结构一般比较复杂且构造方法较困难，消耗较多的预处理时间和空间。

🐨🐨相关概念

🐼多边形Voronoi图

一种将平面划分为多个区域的方式，其中每个区域对应于一个特定的点集合（称为“种子”或“站点”）。在Voronoi图中，平面上的每一点都被分配到离它最近的种子所在的区域。

- 每个Voronoi单元（区域）包含所有距离该种子点最近的点。
- Voronoi边界是种子点之间的垂直平分线。

简单多边形的Voronoi图是一棵树，其叶节点是多边形的顶点；“带洞”多边形的Voronoi图是一个图，其中度数为1的节点为多边形的顶点。

🐼简单多边形vs带洞多边形

简单：只有一条边界的多边形；

带洞：多条边界，外边界顺时针，内边界逆时针

🐼站点o

多边形中的凹顶点或边

🐼站点的voronoi区域VR

多边形P中到o的距离比到其他任意站点距离都近的点的集合

🐼多边形P的voronoi图VD

P中所有站点的VR的并集

🐼voronoi的骨架路径VSP(q,pi)

多边形P中的一个点q到P的一个顶点p的Voronoi骨架路径(Voronoi Skeleton Path, VSP)是一条由系列Voronoi边首尾依次连接而成的路径，用VSP(q, p)表示，如图中粗虚线所示。

🐼边的关联VR

如果边e被两个VR（p1、p2）所共有，则这俩VR就是边e的关联VR，p1和p2是e的关联边；设点a为e的起点，b为e的终点，那么定义有向边ab，若p1在ab左侧，则称p1为ab的左侧关联边，否则是右侧关联边

🐼VSP对应的voronoi通道C

骨架路径的每条边所关联的两边的voronoi区域形成的通道，如上图阴影区域所示。

🐼局部最短路径SP

将VSP看作绳子，将其用力拉紧（变成直线），可以得到在该通道中的一条最短路径，称之为局部最短路径，如上图中拉紧后的虚线所示。

在带洞多边形中，q到pi存在多个voronoi通道，因此存在多个局部最短路径。

🐨🐨算法描述

🐼任意两点间的最短路径算法基本思想

在简单多边形中任意两点间只存在一条voronoi骨架路径，最短路径上的点能够通过顺序遍历其voronoi骨架路径关联的多边形顶点求得。

🐼确定最短路径的算法步骤

1. 确定两点所在的voronoi区域
2. 确定voronoi骨架路径
3. 顺序遍历voronoi骨架路径确定最短路径

🐼算法概述

本节首先讨论多边形内计算一条边相对于给定查询点的可见部分的计算算法。充分性，由引理1知，SP(q, p)上的点为VSP(q, p)所关联的凹顶点，如果只用VSP(q, p)的左侧关联凹顶点计算SP(q, p)，则SP(q, p)为VSP(q, p)的左侧关联凹顶点的凸多边形链L_CP。

🐼引理与定理

引理1和引理2为算法提供了理论基础，定理1给出了边的可见部分的计算方法，定理2给出了沿VD(P)进行深度遍历的终止条件。

🐼算法步骤

算法1详细描述了计算点的可见多边形的过程，包括判断q所在的Voronoi区域、计算VSP和SP、计算对于q的可见部分等步骤。

🐼存在可见部分

q到pi的局部最短路径SP是一条在P内的多边形链且在qpi的右侧；且q到pi+1的局部最短路径SP也是一条在P内的凸多边形链且在qpi+1的左侧

🐼定理1

对于一个多边形P及其内部一点q，在q到P的边pipi+1的一个voronoi通道中，有两个SP，pipi+1相对于q存在可见部分，当且仅当ql1在qr1的左侧；且当前voronoi通道中pipi+1相对于q的可见部分可通过计算射线ql1和qr1与pipi+1的交点得到。

由图所示，qp3在qp6左侧，根据定理，p4p5相对于q存在可见部分。通过计算射线qp3、qp6与p4p5的交点可以计算出p4p5相对于q的可见部分qlqr。射线ql1和qr1直接的区域成锥体状，称为可见锥体VC

🐼停止条件

1：如图所示，当遍历到q2和q3时都没必要再深度搜索圈出的两个区域了，因为它们后边的voronoi边关联的多边形的边肯定相对于q不可见

2：带动多边形如果不设终止条件会陷入死循环。当遍历到某个voronoi顶点（如q1、q2和q3）后，后面的voronoi边对应的边都相对于q不可见，所以可以停止该方向的遍历了。

🐼终止条件设置算法

🐨🐨计算VSP和SP

🐼初始VSP和SP的计算

算法1的Step1首先确定给定点q所在的Voronoi区域VR(o)，算法1的Step2用于计算初始的Voronoi最短路径和SP。

确定Voronoi骨架路径的过程通常包括以下几个步骤：

1. 构造Voronoi图：首先，需要为给定的多边形构造Voronoi图。这个图表达了多边形内部每个点到最近站点（多边形的顶点或边）的距离。

2. 确定Voronoi区域：对于给定的查询点q，确定其所在的Voronoi区域。这个区域表示所有比到任何其他站点更接近查询点q的点的集合。

3. 计算Voronoi骨架路径：通过深度优先搜索Voronoi图，计算从查询点q到多边形顶点的Voronoi骨架路径。这个路径是由连接查询点q和多边形顶点的Voronoi边组成的。

4. 更新VSP：在DFS过程中，每当访问到一个新的Voronoi顶点时，根据需要更新当前的VSP。这涉及到添加或删除Voronoi边，以反映从查询点到当前顶点的路径。

5.计算SP：在Voronoi通道内，SP(q, p)可以通过连接VSP(q, p)上的点和多边形顶点p来计算。这通常涉及到找到VSP(q, p)上与多边形顶点p最近的点。

6.局部最短路径更新：在DFS过程中，随着VSP的更新，相应的SP也需要更新。这涉及到在VSP上添加或删除点，以确保SP始终保持为局部最短路径。

7. 确定可见性：通过分析Voronoi骨架路径和局部最短路径，确定多边形边相对于查询点的可见部分。

🐶深度优先搜索（DFS）

• 访问和标记：从q开始，访问与其直接相连的Voronoi边，并标记这些边为已访问。
• 递归遍历：对于每条已访问的Voronoi边，找到与之相邻的未访问的Voronoi区域，并递归地访问这些区域。这通常涉及到移动到相邻Voronoi区域的顶点或边，并继续探索。
• 回溯：当一个区域的所有相邻区域都被访问后，回溯到上一个顶点，并继续探索其他未访问的区域。

🐼后续VSP和SP的计算

在已计算的VSP(q, p+1)和SP(q, p+1)的基础上，考虑如何快速确定下条边对应的2条VSP和SP，这取决于TC(q-)的值。

🐨🐨算法分析与实例

🐼算法效率

本文算法在预处理阶段需要构造多边形的Voronoi图，一旦构造完成，其可用于任意点的可见多边形查询。对于简单多边形，其Voronoi图可在O(n)时间内构造出来，对于“带洞”多边形的Voronoi图的构造，则需要O(n log n)时间。

🐼算法实例

给出了算法在虚拟博物馆中的应用实例，展示了算法的实际效果。

🦌🦌🦌做笔记

🐕🐕该文章的研究目的

🐈研究背景

本文针对点的可见性计算问题，提出了一种基于多边形Voronoi图的点可见性算法。该算法支持任意查询点的可见多边形快速计算，对于“带洞”多边形也适用，并且只对多边形进行局部访问。

🐈研究目标

旨在提高多边形中点可见性计算的效率，特别是在三维室内虚拟场景设计与漫游系统中的应用。

🐕🐕该文章的研究方法

🐈Voronoi图的应用

文章提出了Voronoi通道和局部最短路径的概念，通过深度优先策略对Voronoi图进行遍历，在计算Voronoi骨架路径的同时计算局部最短路径，并基于局部最短路径计算所遍历的多边形边的可见部分。

🐈算法实现

算法基于Voronoi图的几何特性，通过深度优先搜索遍历Voronoi图，计算Voronoi骨架路径和局部最短路径，从而确定点的可见多边形。

🐕🐕该文章的研究内容

🐈相关概念

定义了多边形Voronoi图中的Voronoi通道和局部最短路径，并提出了计算这些路径的算法。

🐈算法描述

详细描述了算法的步骤，包括如何确定点所在的Voronoi区域，计算Voronoi骨架路径和局部最短路径，以及如何基于这些路径计算点的可见多边形。

🐈算法分析

分析了算法的时间复杂度和空间复杂度，并讨论了算法在“带洞”多边形中的应用。

🐕🐕该文章的创新点

• 提出了Voronoi通道和局部最短路径的概念，为点的可见性计算提供了新的视角。
• 算法可以处理“带洞”多边形，并且只对多边形进行局部访问，提高了计算效率。
• 算法的数据结构简单、空间合理且易于实现，预处理时间复杂度为O(n log n)，空间复杂度为O(n)。

🐕🐕该文章给我们的启发

• Voronoi图可以作为解决可见性计算问题的有效工具，特别是在复杂场景中。
• 通过局部访问和深度优先搜索策略，可以显著提高算法的效率。
• 算法的简单性和实用性使其适用于实际的三维虚拟场景设计与漫游系统。

🦌🦌🦌反思

🐨🐨从中学到了什么

🐼1. Voronoi图在可见性计算中的应用

- 学会了如何利用Voronoi图来解决多边形中的点可见性问题，特别是在复杂或“带洞”的多边形中。

🐼2. 深度优先搜索（DFS）的策略

- 了解了如何通过深度优先搜索策略在Voronoi图中遍历，以计算Voronoi骨架路径和局部最短路径。

🐼3. 算法的时间和空间复杂度

- 掌握了评估算法效率的方法，特别是如何分析算法的时间和空间复杂度，并理解了近似线性算法和近似输出敏感算法的概念。

🐼4. 算法的实际应用

- 认识到了这种算法在三维虚拟场景设计与漫游系统中的应用价值，特别是在提高渲染效率和优化用户体验方面。

🐼5. 计算几何中的基本概念

- 学习了Voronoi图、Voronoi骨架路径、Voronoi通道和局部最短路径等计算几何中的基本概念，并理解了它们在算法中的作用。

🐨🐨有什么问题

🐼1. 算法的扩展性

- 该算法是否可以扩展到非多边形（如曲线边界）的几何形状，以及如何适应更复杂的三维场景？

🐼2. 算法的优化

- 在大规模数据集或高密度点集中，算法的性能如何？是否存在进一步优化空间，以提高算法的效率？

🐼3. 算法的鲁棒性

- 算法对于噪声数据或不精确的输入有多鲁棒？如何处理输入数据的误差？

🐼4. 实际应用中的挑战

- 在实际的三维虚拟场景中，算法如何处理动态变化的场景，例如移动的物体或变化的视角？

🐼5. 算法的并行化

- 考虑到现代计算硬件的发展，该算法是否可以并行化以利用多核处理器的优势？