英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
使用GPU着色器计算最短路径图
Carlo Camporesi Marcelo Kallmann
加州大学默塞德分校 加州大学默塞德分校
摘要：
我们在本文中提出了一种新的基于GPU的，用于从多边形主体中的源点计算最短路径图（SPMs）的方法。 我们的方法式充分利用GPU多边形栅格化和着色器编程。在帧缓冲区中对SPM进行编码之后，全局最短路径的计算时间与路径中顶点的数量相对成比例，用常量时间单位来作为长度查询标准。我们已经在多种环境中评估了我们的方法，并且我们的结果显示出与以前的方法相比显着的速度提升。
关键词：
路径规划 、最短路径、最短路径展示图
引言：
欧几里得的最短路径障碍物的计算是一个经典问题，在很多领域都有应用。最短路径图（SPM）[Lee and Preparata 1984; Mitchell 1993]是一个结构体，它可以就一个给定的源点而言有效地捕获多边形域中所有最短路径。虽然SPM在计算几何中是众所周知的，但它们在计算机图形学的其他领域仍然鲜为人知，并且它们在实际应用中的使用尚未得到很多探索。造成这种情况的原因之一是计算SPM的高效方法并不直观，所以可以开发出替代性的基于GPU（图形处理器）的方法。我们在本文中介绍了一种基于GPU着色器编程技术的SPM计算新方法。我们的实验表明我们的方法比以前报道的结果快得多。我们的方法首先依靠标准CPU算法计算障碍集的最短路径树，然后应用提议的着色器以任意分辨率对帧缓冲区中的SPM进行编码。最后一步完全是通过GPU操作来完成的。参见图1中的例子。给定n个顶点的多边形环境，我们的离散（基于像素的）SPM表示就能够计算从源点到O（k）中环境中任何可到达点的最短路径，其中k是数字在路径上转弯;并在不变的时间内计算最短路径长度查询。相反，用于计算SPM的连续方法将分别在O（log（n） k）和O（log（n））时间回答这些查询
图1：结果示例。 左边：从源点生成的示例SPM，标记有一个小的黄色十字。 SPM中的每个区域都有一个生成器，这使得重建最短路径非常有效。 红色路径是通向任意目标点的最短路径。 右图：从源头上扩大测地线填充。从蓝色到深红色的颜色表示距离源点的距离，从近到远。
2、相关工作
最常见的解决欧几里得最短路径问题的方法是首先建立可见性图[Nilsson 1969; De Berget al。 2008]的环境，然后在图上运行标准图搜索算法。然而，可见性图是O（n2）个节点的图，其中n是环境中的顶点总数[Welzl 1985; Storer和Reif 1994; Overmars和Welzl1988];此外，对于每个给出的最短路径查询，都需要一个新的图进行搜索。
有效的解决问题的方法是基于连续的Dijkstra迪杰斯特拉范例[Lee and Preparata 1984]，它模拟连续波前的传播，保持与源点等长。当应用于整个环境时，结果是最短路径图（SPM），它能够有效地对源点进行最短路径查询。有效的算法可用于构建SPM [Mitchell 1993; Hershbergerand Suri 1997];然而，它们涉及的技术和数据结构不切合实际。
连续方法的一种替代方法是，基于GPU的分布式并行化已经开发出了基于像素的离散方法。与我们的方法一样，Wynters [2013]首先计算环境的可见性图和最短路径树（SPT），然后构建SPM。SPM生成技术并不依赖像我们的方法那样使用着色器进行光栅化，而是基于最接近的SPT点的蛮力并行化的每像素确定，导致SPM区域中像素空间的细分。使用我们提出的方法获得的结果在类似的报告条件下显示出大约20倍的显着加速[Wynters 2013]。
我们达到了以前在前期工作中未曾见过的复杂性和细节水平。
关于之前着色器编程技术，我们的工作主要依靠阴影卷的使用[Eisemannet al。 2009年]。实时渲染硬阴影的算法大致可分为三类：阴影映射[Williams1978; Lauritzen等人2011; Lloyd等人2008]，没有别名的shadowmaps [艾拉和莱恩2004年; Johnson等人2005; Sintorn et al。2011]和影子卷[Fuchs et al。 1985; Heidmann 1991]。我们的工作依赖于影子体积的产生以及z-fail方法的变化[Carmack 2000; Bilodeau和Songy1999; Everitt和Kilgard 2002]。这种方法比使用阴影图的方法要慢，这是由于较高的透支率以及近距离和远距离的几何裁剪需求[Laine 2005];但它不会受到（相当严重）分辨率混叠现象的影响，并且不依赖于相机，从而允许在每个场景方向上生成阴影。
- 方法
我们的整体方法由三个主要步骤组成：环境预计算，可见性图和SPT计算以及SPM生成和查询，如算法1中总结的。另见图2。
每个输入多边形障碍物由一个唯一的ID（pid）来标识。我们假设障碍物是不相交的，由顶点顺时针顺序表示，并且它们至少有3个顶点。
图2：根据可见性图计算SPT后确定每个顶点的可见区域（中心），并按照SPT排序构成可见区域以形成SPM（右）。
3.1环境预计算
我们算法的第一步是生成沿z轴的输入多边形的拉伸体积环境的轴，它是多边形域平面的正交轴。见图3.挤压多边形表示为三角形网格，并用三角形邻接信息增强[Shreiner et al。 2013]，以便能够通过几何着色器从任何视点生成阴影体.
3.2可见性图形
我们生成的可见性图形遵循标准方法来连接彼此可见的所有顶点对，优化只包括边缘连接两个凸顶点。我们的实现通过从每个顶点向外遍历环境的三角剖分来确定可见顶点。该方法需要O（n3）时间，但实际上它会有效地剔除环境中的不可见区域。我们的可见性图的每个节点都存储一个列表，其中包含所有可见障碍物的专属编码。
3.3 SPM生成
每当给定一个新源点时，该点首先连接到其可见性图的可见节点的边。然后执行从新插入的源节点开始的详尽的Dijkstra扩展，并且生成的扩展树是多边形环境的SPT。 SPT的每个节点将对应一个特定的障碍顶点。参见图2左。
在SPT构建过程中，如果连接到顶点的边缘从其SPT父顶点都可见（部分或全部），或者其中一个顶点完全被遮挡，则标记每个顶点以标识。从SPT中移除与可见边缘相邻的SPT节点，因为他们不会成为SPM会议的发起人[Mitchell 1993]。其余节点将是生成器，并为其分配唯一的颜色专属编码。生成器节点按照每个节点到源点的欧几里得测地距离排序，列表中我们的方法。
我们获得SPM的方法受GPU渲染锥的表示方法的启发，作为一种表示到边界距离的方法，最初提出用于计算广义Voronoi dia-grams [Hoff 等人。 1999年]。在我们的SPM案例中，我们使用剪切的3D conesto表示来自SPT发生器顶点的波前扩展。每个锥体的高度等于其半径。在源点情况下，锥体不需要被裁剪。当锥形从正交视点呈现时，生成的深度缓冲区将包含到发生器点的距离。
根据从发生器到源点的测地距离，沿着Z轴以不同高度放置不同的高度。参见图3-b。使用这些设置，如果呈现两个交叉锥体（具有不同的颜色ID），则对于每个Z缓冲区像素，Z缓冲区深度测试将仅维持与相机视角最接近的锥形度的深度值。 Z缓冲区中的每个值仍然与生成锥体的几何体相关联，以便可以在渲染步骤中将锥体的颜色分配给帧缓冲区中的特定像素。生成的最终图像由颜色区域组成，其中每个像素的颜色都是直接访问其最近的SPT生成器节点的ID，并且Z缓冲区中的深度值对于每个像素都包含到SPM源点的测地距离。
一个重要的观察结果是，仅仅在其顶点发生器顶点处将锥体放置在正确的高度是不够的，因为它可能与放置在环境中的无关锥体相交，导致错误的结果。为了解决这个问题，我们必须确保锥体传播不会影响锥体发生器顶点不可见的区域。这个过程可以通过生成每个顶点的圆锥体进行修饰，但是每个顶点需要计算每个顶点的特定形状的CPU计算，这些计算必须被计算并传递给每个新的以SPM源头的图形硬件。
图3：锥体放置和障碍物挤压。
- 锥体呈现平坦的阴影，并投射到障碍平面; redrectangle是障碍。
- 夹角锥和挤压障碍物的透视图。锥体被削减的可见性区域。灰色的飞机是障碍飞机。
- 没有障碍物平面的透视图。
- 剪切后的剖视图显示挤压多边形的内部部分。灰色方框显示裁剪量。
我们的方法利用了点光线传播和阴影的概念。我们认为每个SPT节点都是一个全向光源，我们直接在GPU阴影体积中生成，这将用于在每个锥体渲染过程中识别锥体的哪些特定部分应该用于渲染，因此仅用于更新相关颜色和深度缓冲区值。我们使用了z-fail阴影体积算法的优化版本在场景中生成阴影区域以用于锥切。图2中心举例说明了由影子体积算法生成的可见区域，并应用于源点的圆锥体。图3显示了由我们的方法放置和裁剪的多个锥体产生的SPM的多个视图。
这种方法依赖于顺序更新缓冲区，并且在我们的设置中需要锥体渲染遵循与SPM源的排序测地距离的严格顺序。已分类的顶点列表是在SPT计算步骤中创建的。最远的锥必须先渲染。
锥体渲染已完成两次渲染的。第一次将模板缓冲区与每个光源（一个SPT生成器顶点）产生的阴影体积信息相对多边形障碍物挤压几何体进行更新。这个阶段也是优化的，用3.1节中定义的pid预先剔除遮挡的多边形。第二遍包含实际渲染的几何图形和启用的模板操作。只有在场景中阴影体积不存在的情况下，锥体才被渲染。整体方法在算法2中详细描述。
我们使用两个着色器程序。第一个着色器技术（科技平板）只是使用指定的颜色机智渲染锥体来自几何体的任何阴影信息。第二个shader程序（tech Shad）负责计算投影环境几何轮廓的阴影体积为无限（投影点是SPT生成器节点或SPM源点）。该着色器是最常见的轮廓生成算法的修改版本。
该算法提出了一种通用方法，可以使用具有相邻信息的几何图形从任何角度创建阴影。我们还从正交相机的角度开发了一个专用版本，仅使用通用几何测量（无邻接信息）。为了将顶点投影估计为无穷大，着色器使用一个简单的解决方案，使用非常接近0的值作为由光源和顶点定义的归一化方向的均匀分量。 [Everitt和Kilgard 2002]也可以使用另一种不依赖于某种技术的方法
以下四个附加考虑事项需要考虑在内，如下所示。
图形卡片数字精度：通常着色器的光源位置通常是一个SPT节点（因此恰好在一个polygonvertex中），并且由于精度错误，图形卡可能会错误地将其视为在多边形内，并且在这种情况下可能会生成不正确的结果。我们避免了这个问题，将光源沿障碍物外侧的两个相邻边缘之间的平分线矢量稍微放置到顶点。
- 缓冲精度：所提出的算法依赖于深度缓冲精度，其直接取决于z N ear和z F ar的值。为了充分利用深度缓冲区精度，根据算法所需的最大深度维度，自动计算z F ar值。考虑到摄像机的视角，我们也适当地设置了z N ear值，以便在为了调试目的而从通用视点渲染场景时正确地渲染整个场景。
Fighting（ Z-fighting主要是指当两个面共面时，二者的深度值一样，深度缓冲就不能清楚的将它们两者分离开来，位于后面的图元上的一些像素就会被渲染到前面的图元上，最终导致图象在帧与帧之间产生微弱的闪光）
由于每个锥形网格具有相同的斜率，并且儿童扩展的放置位置是恰好在父母的边缘，属于不同锥体但具有父子关系的多边形可能会产生z-fighting 行为。为了避免这个问题，我们给孩子的锥体高度增加了一个微小的差距。这样可以使修剪后的锥形网格总是呈现在父母的剪切锥形网格下方。此值也是自适应计算的，因为它取决于深度缓冲区的精度。
滤网分辨率：对于正确的结果，需要适当地设置一个网格的分辨率。自适应分辨率对于优化结果也是有用的[Hoff et al。 1999]
- 结果
我们在Open GL 3.3或更高版本中实现了我们的着色器，并且在CPU部分使用了C 。我们的性能评估采用了Ge Force 570 GTX GPU和单核Intel i7-2600K CPU at 3.40 GHz。对于帧缓冲区对象渲染通道，我们使用了一个32位RGBA渲染目标（用于存储颜色）和一个24位深度和8位模板渲染目标（分别用于存储深度和模板信息）。渲染目标（FBO，深度和模板缓冲区）的测试分辨率设置为512x512，1024x1024和2048x2048像素。我们还将圆锥的分辨率改变为每个圆锥512个，1024个，1598个，2048个，4196个三角形。我们评估了7个具有不同数量的方形圆锥体的地图，并使用中心点作为SPM源。我们已经考虑了具有复杂障碍的通用环境（图8）。图5显示了这些图和它们的SPM。表1总结了统计数据。（有关其他结果，请参阅随附的视频，网址为http://graphics.ucmerced.edu/publications.html.)
表1：评估环境。输入多边形集合中的顶点数量为n，nf代表多边形障碍物中所有挤出体积的三角形数量。 Timetpr是环境预计算时间，其中包括可见性图的计算。列tspt显示在每个给定环境中生成SPT所
全文共6399字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16346]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
