虚拟环境路径规划.docx

摘要处理虚拟环境中应用程序的一个中心问题是为虚拟角色规划无碰撞的路径由于环境和虚拟 角色越来越真实，虚拟角色的路径需要使人视觉上信服，这意味着路径是短的、平滑的、和 环境中的障碍物有一定的间隙并且能避开其他虚拟角色同时满足这些标准和实现实时性被 征明时困难的我们介绍一个新的数据结构即：显示的坐标地图，它允许创建最短路径，这个路径有有最大 的间隙和障碍物，或任何两条路径之间除了高效，对应的算法也是出奇的简单，通过把数 据结构和算法融入引导路径（IRM），我们表示：令人视觉信服的短路径可以被实时的获取1引言在处理虚拟角色应用上的一个主要挑战之一是规划虚拟角色的路径传统的算法设计 是计算虚拟角色的开始位置到目标位置与其他角色和障碍物没有碰撞虽然这个算法成功的 运用在这些领域，如移动机器人，操作规划，人类机器人规划[1] -3]，然而当期的虚拟环境 如游戏和人群模拟，对这个算法提出了新的挑战那就是，视觉令人信服的短路径并穿越不 断变化的环境需要同时和实时的规划因此，每秒的cpu时间只有毫秒的一小部分用来计算 令人视觉信服的虚拟角色的段路径，即路径是平滑的，短的，与障碍物有一些间隙，并且可 以避开其他角色。

路径应该是短的，因为他需要最少的时间来遍历然而，这个路径不应该 是最短的，因为这样的路径可能触碰到障碍物当虚拟角色运动的时候可能导致与环境发生 碰撞因此，最短的路径要求与障碍物有一定的最低的间距当前的规划者不能同时满足这 些标准，因为当在一个大的环境中运行时这太慢了或者要耗掉很多内存在1968年推出的A*算法是第一规划之一，因为它的简单性和能在由自由单元的网格覆 盖的环境中找到最短路径受到欢迎然而生成的路径与障碍 口" 小、"丫通过时必须谨慎小心类似A*法, Potential 的势场的逐步递减产生然而 相当费时的，的方法（r快没有陷入局部是那么自然，所以勺路径可以通平滑E 势场，这样的计:于位图它可能降低实时性based），如可〈最小，通常确保发现存在的物有很小的间隙，并且看起来不 Field法能避免障碍此外，[2],快速搜基图法（「RM）[8],代表环境中自由空间的位图「因为，当一个路径从这个途中它可以计算[7创建了部最小、的和概率路径 -个 性索随机树法（路径在这是取时，可以实现离线和实时(g) Left/right closest (h) Explicit Corridor (i) Shortest minimum points of a corridor ④ . ok/s y ok/s £ ith此外这可以应用到自由度不同的问题中，然而，它缺乏灵活性，因为他只能得到一个固定的 路径从空间从图中。

此外这个路径也是不平稳的，尽管有优化算法，他对实时性来说依然是 很慢的［10］另外一个方法是用VOronoi图，它可以获取一个和障碍物有最多间距的路径［11］, ［12］ 与此相反，引用并找到移动物体的最短路径最近，坐标内的路径规划被引入［15］ -17］，坐标被定为一系列的空盘因为这些盘的连接构 成了一个二维空间，所以坐标促进为虚拟角色建立一个平滑无碰撞的路径，同时避免和其他 角色碰撞这种灵活性很难在一维图空间中实现，除了这个理想的灵活性，坐标也允许用来 创建许多实时的路径，因为他可以通过离线的计算获得数据结构然而，它不支持创建最短 路径，和最小的间距路径Visibility-VOronoi混合可以创建这样的路径，这样一种数据结构 允许在可视图（创建最短路径）和V）ronoi图（创建最大间隙的路径）之间插值这种方法 的算法是准确的，并且可以产生令人信服的短路径此外，全局的最短路径也是可以计算的， 但是需要二次存储算法也是复杂的，实施也是很慢的我们还提出了一种具有线性复杂度的数据结构，它可能找不到全局路径这种结够即显 示坐标地图，它允许我们用新的，最简单的方法计算出在坐标内具有最小间隙的最短路径。

把这个算法和指引路径法（irm）结合在一起［19］,在几毫秒内我们可以获得灵活的具有最小 间隙的最短路径因此这个算法可以用在具有很多虚拟角色交互式环境中本文的结构如下：在第二部分我们介绍显示坐标地图，并展示怎样用图形硬件有效的构建一 种这样的数据结构然后，在第三，四部分，我们给出在坐标内计算最短路径和与障碍物有 最小间隙的路径的算法虽然，现在产生的路径是短的且安全，但是他是刚性的，因为虚拟 角色的运动被限制在这个路径中在第五部分我们介绍允许虚拟角色偏离坐标，以至于可以 避免其他虚拟角色并增加路径的平滑性接下来我们在第六部分进行实验，在第七部分得出 结论产生令人视觉信服的短路径如图1描述，可以进行实时的计算2显示坐标地图我们的目标是构建一个高效的数据结构，它占用小的存储空间，可以快速获得与障碍物 之间具有最小的间距的最短路径因为现在的虚拟环境是巨大的，我们希望一个站内存小的 数据结构，即在所有障碍物的大量顶点中一个线性结构由于这个结构在很短的时间内被大 量的虚拟角色查询，所有一个路径需要高效的计算我们提出的数据结构，即显示坐标地图， 满足这些要求定义1：显示坐标地图是一个广义的V）ronoi图G=（VE）,V和E分别是V）ronoi图的边 和顶点，这些边标记着到障碍物最近的点。

虽然图中包含一维曲线，但它的注释中明确定义了环境中自由空间的二维设定，我们将介绍 用这个设定可以规划所需的路径在我们说明怎么标注这个边（B）和怎样构建这个设定（c）之前，我们讨论如何用图形硬 件有效的计算出一个广义V）ronoi图A 广义V^ronoi图发生在虚拟环境中自由空间的路径规划，即可行走的2维空间自由空间定义为这个空间不 被环境中的痕迹占有，这些痕迹是凸起的障碍物的集合，包含点、线和凸多边形，所有在平 面上的可行走的空间可由广义V）ronoi图（GVD）简洁的表示它是一个自由空间分解成许多 区域，以致区域R（p）中所有的点p到某一障碍物比到环境中其他任何障碍物近［20］这个区 域被称为V）ronoi区域Wronoi区域的边界构成了 GVD的基本图图中的每一个顶点位于 非凸角处，或者在这个位置有三个或更多个图中的边相交每条边连接两个顶点并且是两个 V^ronoi区域的边界利用图形硬件可以有效的计算出GVD可以计算出每一个障碍物的3维网格的距离 每一个网格在图形卡上图上不同的颜色这些网格的平行投影得出了 GVD从图形卡的框 架缓冲区中可以检索出图，可以从z-缓冲中找到间距值，参考图2(a-c)。

我们要求所有的边缘凸凹有致，这保证边运行到凹的边缘，因此完全代表路径规划的目的性 [21]这个要求不能限制我们因为非凸障碍物可以被分解成凸多边形，如三角形[22]，或最 佳分解[23], [24]通常，两个不同的凸障碍物形成一个边，边上的点是在边界被框架缓冲区以不同的颜 色划分通过每一种障碍物连接一个颜色，我们知道每一个点最近的两个障碍物这些对我 们分析是非常有用的一般情况下，一组障碍物形成部分障碍物的凸链，形成边在我们的 分析中，我们处理凸链作为一个单独的障碍物，涂上单一的颜色因此不失一般性，我们假 设，边连接两个VOronoi区域的边界In[20],我们取样GVD的边，把取样结过称为坐标图如图2(d)给出了一个这样的例子 对每个样本点，空圆盘的最大半径是指定的因此，连续的相邻的圆被称为坐标看图.2(e) 尽管这个坐标用来规划最短路径，但他不能找到具有最小间距的路径，因为他没有提供一个 明确的边界描述；另一个缺点是，取样点没有覆盖整个自由空间此外他的内存空间不是线 性的通过指定一些样本左边和右边最近的点，我们可以得到边界的明确描述如图2(f-h)所示 如我们所见，他们可以高效的计算出一个具有最小间隙的路径。

请参看图2(i)B注释一个VOronoi边(a) Triangulation (b) Shortest path在在这个边一组点和虽然我们可 一个[坐标图的边，一个边包含 形成边 ’界，但要接近现实边算导最近的.含V)rinoi边并连接V^rmoi顶点的边边是距离两个障碍距离相等的点，畦B2表示曲线段如果部分在■障碍物的右汁性时间，这可能会影更多的边是有连续的曲线形成，如2,』2)表示相关的最近的左实时计算线段和抛物线.边和右边点曲线是一个物的左边，线段连接r1 r2障碍物同样的，我们于效率的原因用最少的曲线描述边是重要牛 因此，我们必须找到曲线必须开始和结束的置这样的位置被称作为边的事件点用BronoB1和线的两个l1= l2 A、端点，(l1 ,r)和r1 = r2 ,或者如口果线段和障碍物不相交，他划开接血，l2部分在障碍边，注意，如物线弧形如果l1! = l2 A r1 =[t]参数化边，0 < t；让l[t] r[t]分别表示相关的最近的左边和右边的点此外,让n1[t]和n2[t]分别表示有向量B[t]- l[t] andB[t] -r[t]lcorridor ancc path in a shrunk corridor形成的左右法向量。

注意，n1[t ]和n2[ t]是左右障碍物的法向量，只有在障碍物的顶点改 变然后事件点使从点集s中分离出来的，例如右边的点 s = {B|t] : = nfi[t\ An?|t t 6t\ 丰 n}i\t\） V （n?|t-况]丰 njt] A m[i t 8t\ = m『）}, where 5 is an infinitesimal-■- ■■ '■ ■ - 1 - ■- ■ ■ ■ . - ■ 5 是无穷小数，相同的方法事件点被增加到左边如果我们考虑边线可以计算集合S首先我们计算每一个障碍物的法向量，我们联接法 向量ni和边ei联接顶点vi和法向量ni和ni+1;事件点和边上的点相关联为了提高效率，我们计算VOronoi边和最近的点集合用图形硬件让p=p1,p2,..pn表示帧缓 冲区描述VOronoi图的边中里像素的坐标因为边是有两个障碍物确定的，通过观察有临近 的点p1=（x1 ,y1 ） and p 2=（x2 ,y 2）确定的局部指向获取左右两个顶点例如相关的方向是向 上的如过y2

现在我们了解了 Voronoi图的边，和它的左边和右边的最近的障碍物，我们可以用简单的线 性代数计算事件点S和他最近的点注意我们没有存储在两个事件点之间边上的中间点， 因为这些曲线是有相关的最近的点确定的GVD的存储复杂是线性于障碍物的顶点数量IVI [22]因为每个障碍物（具有m个顶点） 至少生产两条边，至少有O（m）个事件点ECM的存储复杂度也是线性的，即OIVI.因此， ECM是一个高效率的数据结构可以用在大的环境中尽管图形卡可以有效的计算出一个GVD，但他可能引起一个ECM错误，因为当两个障碍 物被任意的放置时被限制了一个有限的分辨率这样的一个错误导致他自己作为一个边而不 能被识别（当他们之间的距离小于一些像素点的宽度时）然而在实践中，这不是一个问题， 因为我们可以用一个足够高的分辨率如此高的分辨率可以通过几个模块的渲染得到此外， 如果一个边被发现，障碍物的边界就可以精确的描述，尽管他们之间的距离小于一些像素的 距离C显示坐标为。