1、实时碰撞检测技术研究 答辨人答辨人 范昭炜范昭炜 指导教师指导教师 高曙明高曙明 研究员研究员 万华根万华根 副研究员副研究员博士学位论文答辨博士学位论文答辨浙江大学浙江大学CAD&CG国家重点实验室国家重点实验室浙江大学计算机科学与技术学院浙江大学计算机科学与技术学院二二三年十一月二十六日三年十一月二十六日主要内容l绪论绪论l基于图象的快速碰撞检测算法基于图象的快速碰撞检测算法l基于流的实时碰撞检测算法基于流的实时碰撞检测算法l并行碰撞检测算法并行碰撞检测算法l总结与展望总结与展望第一部分 绪论研究背景和研究意义 l碰撞检测问题碰撞检测问题l是机器人、动画仿真、虚拟现实等领域不可回避的是机器
2、人、动画仿真、虚拟现实等领域不可回避的问题之一问题之一l基本任务基本任务l确定两个或多个物体彼此之间是否发生接触或穿透。确定两个或多个物体彼此之间是否发生接触或穿透。l起源起源l早期在机器人路径规划、自动装配规划等领域中，早期在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中的物体或零件与零件之间是为检测机器人与场景中的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算法。否发生碰撞，产生了一系列碰撞检测算法。研究背景和研究意义l目前研究的意义目前研究的意义l虚拟场景中的物体模型越来越复杂虚拟场景中的物体模型越来越复杂 l在仿真中对实时性和真实性的要求越来越高在仿真中对实时性和
3、真实性的要求越来越高l现有的碰撞检测算法无法满足要求现有的碰撞检测算法无法满足要求碰撞检测算法分类 l从两个角度对碰撞检测算法进行分类从两个角度对碰撞检测算法进行分类 l从时间域的角度来分从时间域的角度来分l从空间域的角度来分从空间域的角度来分 基于时间域的碰撞检测算法分类 l分为静态、离散和连续的碰撞检测算法分为静态、离散和连续的碰撞检测算法l静态碰撞检测算法静态碰撞检测算法l静止状态下进行碰撞检测静止状态下进行碰撞检测lDobkin 1985Agarwal 1991Chazelle 1989 l离散碰撞检测算法离散碰撞检测算法l在每一时间的离散点上进行碰撞检测在每一时间的离散点上进行碰撞检
4、测l是研究的重点和热点是研究的重点和热点 Lin 1998Jimnez 2001 基于时间域的碰撞检测算法分类l离散碰撞检测算法离散碰撞检测算法l存在问题存在问题l存在刺穿现象存在刺穿现象 l遗漏应该发生的碰撞遗漏应该发生的碰撞 l连续碰撞检测算法连续碰撞检测算法l连续的时间间隔内进行碰撞检测连续的时间间隔内进行碰撞检测l计算速度还太慢计算速度还太慢 lCameron 1990Canny 1986Redon 2001Redon 2002a基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l基于图象空间的碰撞检测算法基于图象空间的碰撞检测算法基于空间域的碰撞检测算
5、法分类 l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l采用一般表示模型的碰撞检测算法采用一般表示模型的碰撞检测算法 l采用空间结构的碰撞检测算法采用空间结构的碰撞检测算法 基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l采用一般表示模型的碰撞检测算法采用一般表示模型的碰撞检测算法l多边形表示模型多边形表示模型l多边形集合，结构化表示模型多边形集合，结构化表示模型l非多边形表示模型非多边形表示模型lCSG表示模型，隐函数曲面，参数曲面，体表示模型表示模型，隐函数曲面，参数曲面，体表示模型 多边形表示模型 非多边形表示模型 结构化表示模型 多边形集合
6、CSG 表示模型 隐函数曲面 参数曲面 几何模型 体表示模型 基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l采用一般表示模型的碰撞检测算法采用一般表示模型的碰撞检测算法l面向多边形表示模型的碰撞检测算法面向多边形表示模型的碰撞检测算法lHubbard 1995Gottschalk 1996 Klosowski 1998Zachmann 1998 l面向凸体的碰撞检测算法面向凸体的碰撞检测算法基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l面向凸体的碰撞检测算法面向凸体的碰撞检测算法l基于特征的碰撞检测算法基于特征的碰撞检
7、测算法lLin-Canny的的“最邻近特征算法最邻近特征算法”Lin 1991,Lin1993 lLin 1995,Cohen 1995,Chung 1996,Mirtich 1998,Ehmann 2000,Ehmann 2001 l基于单纯形（基于单纯形（Simplex）的碰撞检测算法）的碰撞检测算法 lGilbert、Johnson和和Keerthi Gilbert 1988Gilbert 1990提出的提出的GJK算法算法 lCameron 1997Bergen 1999 基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l采用一般表示模型的碰撞检测算法
8、采用一般表示模型的碰撞检测算法l面向面向CSG表示模型表示模型lZeiller 1993Su 1996Poutain 2001 l面向隐函数曲面表示面向隐函数曲面表示lFarouki 1989Miller 1991Shene 1991 l面向参数曲面表示面向参数曲面表示l非均匀有理非均匀有理B样条曲线（样条曲线（NURBS）lTurnbull 1998 l体表示模型体表示模型 l主要用于虚拟手术中可变形物体的碰撞检测主要用于虚拟手术中可变形物体的碰撞检测lHeidelb 2003Boyles1999魏迎梅魏迎梅 2001 基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰
9、撞检测算法l采用一般表示模型的碰撞检测算法采用一般表示模型的碰撞检测算法l采用空间结构的碰撞检测算法采用空间结构的碰撞检测算法l空间剖分法（空间剖分法（space decomposition）l均匀剖分、均匀剖分、BSP树、树、k-d树和八叉树（树和八叉树（Octree）等）等Samet 1989Naylor 1990Bourma 1991 l层次包围体树法（层次包围体树法（hierarchical bounding volume trees）基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l采用空间结构的碰撞检测算法采用空间结构的碰撞检测算法l层次包围体树法
10、，包围体类型的不同来加以区分层次包围体树法，包围体类型的不同来加以区分l层次包围球树层次包围球树Hubbard 1993Hubbard 1995Palmer 1995OSullivan 1999、lAABB层次树（层次树（Aligned Axis Bounding Box）Zachmann 1997Bergen 1997Larsson 2001、lOBB层次树（层次树（Oriented Bounding Box）Gottschalk 1996lk-dop层次树（层次树（Discrete Orientation Polytope）Klosowski 1998Zachmann 1998 lQuOS
11、PO 层次树层次树(Quantized Orientation Slabs with Primary Orientations)He 1999 l凸块层次树凸块层次树Ehmann 2001 l混合层次包围体树混合层次包围体树Wan 2001等等等等 基于空间域的碰撞检测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l采用空间结构的碰撞检测算法采用空间结构的碰撞检测算法l层次包围体树法，包围体类型的不同来加以区分层次包围体树法，包围体类型的不同来加以区分(a)包围球 (b)AABB包围盒 (c)OBB包围盒 (d)6-dop包围体(e)凸包包围体包围体二维示意图基于空间域的碰撞检
12、测算法分类l基于物体空间的碰撞检测算法基于物体空间的碰撞检测算法l基于图象空间的碰撞检测算法基于图象空间的碰撞检测算法l利用图形硬件利用图形硬件 l对物体的二维图象采样对物体的二维图象采样l相应的深度信息相应的深度信息基于空间域的碰撞检测算法分类l基于图象空间的碰撞检测算法基于图象空间的碰撞检测算法lShinya等等Shinya 1991和和Rossignac等等Rossignac 1992 lMyszkowski等等Myszkow 1995lBaciu等等Baciu 1997Baciu 1999 lHoff等等Hoff 2001，Kim等等Kim 2002，Lombardo 1999，Vas
13、silev 2001，Heidelb 2003，Govindar 2003 l基于可编程图形硬件基于可编程图形硬件.碰撞检测算法框架 l归纳出一个统一的碰撞检测算法框架 碰撞检测算法的一般框架l初步检测阶段初步检测阶段 l空间剖分法空间剖分法l基于插入排序的基于插入排序的“掠扫和裁剪掠扫和裁剪”法法(Cohen 1995)碰撞检测算法的一般框架l详细检测阶段详细检测阶段 l逐步求精层逐步求精层 l空间层次剖分技术和层次包围体树技术空间层次剖分技术和层次包围体树技术 l精确求交层精确求交层 l主要处理多边形面片或基本体素之间的精确相交主要处理多边形面片或基本体素之间的精确相交检测检测目前存在的问
14、题 l处理大规模复杂场景的能力不足处理大规模复杂场景的能力不足 l处理非凸物体的能力不足处理非凸物体的能力不足 l基于图象的碰撞检测算法的精度不高基于图象的碰撞检测算法的精度不高 l面向特定应用领域的高效碰撞检测算法缺面向特定应用领域的高效碰撞检测算法缺乏乏 l离散碰撞检测算法的刺穿和遗漏问题离散碰撞检测算法的刺穿和遗漏问题本文研究目标l提高碰撞检测算法的效率以达到实时性要提高碰撞检测算法的效率以达到实时性要求求l突破基于图象算法在适用面和检测精度上突破基于图象算法在适用面和检测精度上的局限性的局限性本文研究内容l从三个角度出发，设计、实现并验证了一从三个角度出发，设计、实现并验证了一组新的碰
15、撞检测算法组新的碰撞检测算法l从利用从利用图形硬件图形硬件辅助通用计算的角度出发，辅助通用计算的角度出发，研究并提出一种新的基于图象空间的快速碰研究并提出一种新的基于图象空间的快速碰撞检测算法撞检测算法 l从利用从利用可编程图形硬件可编程图形硬件高并行性的角度出发，高并行性的角度出发，提高基于图象的碰撞检测算法的速度与精确提高基于图象的碰撞检测算法的速度与精确性性 l从利用从利用多处理机多处理机并行计算能力的角度出发，并行计算能力的角度出发，提出一种并行的快速碰撞检测算法提出一种并行的快速碰撞检测算法 第二部分 基于图象的快速碰撞检测算法本章研究意义l多数基于图象的碰撞检测算法优缺点多数基于图
16、象的碰撞检测算法优缺点l有效利用图形硬件绘制加速功能，减轻有效利用图形硬件绘制加速功能，减轻CPU计算负荷，提高碰撞检测效率计算负荷，提高碰撞检测效率 l存在的问题存在的问题l仅能在凸体间进行碰撞检测，仅能在凸体间进行碰撞检测，l绘制过程往往直接针对物体进行，缺乏必要的优绘制过程往往直接针对物体进行，缺乏必要的优化手段，化手段，l性能不够理想性能不够理想 本章研究意义l算法设计目的算法设计目的l继承一般基于图象的碰撞检测算法优点继承一般基于图象的碰撞检测算法优点l突破局限性突破局限性l能够在保证效率的前提下处理任意形状多面体之能够在保证效率的前提下处理任意形状多面体之间的碰撞检测问题间的碰撞检
17、测问题l算法采用的主要技术算法采用的主要技术l基于表面的凸分解基于表面的凸分解l三角形带压缩编码技术三角形带压缩编码技术lOBB包围盒技术包围盒技术 算法概述算法预处理阶段 l表面凸分解表面凸分解l组织层次凸块二叉树；组织层次凸块二叉树；l为凸块构建为凸块构建OBB包围盒；包围盒；l对凸块进行三角形带压缩编码。对凸块进行三角形带压缩编码。算法预处理阶段l基于表面的凸分解基于表面的凸分解l目的，使算法可处理任意形状的物体目的，使算法可处理任意形状的物体l非凸物体的表面分解成一些凸面片的集合非凸物体的表面分解成一些凸面片的集合(a)凸片 (b)相应的凸块算法预处理阶段l表面凸分解的结果示例表面凸分
18、解的结果示例算法预处理阶段l建构层次二叉树建构层次二叉树l自顶向下的方法将凸块集（或称为凸块列表）自顶向下的方法将凸块集（或称为凸块列表）组织成层次二叉树结构组织成层次二叉树结构 l求所有凸块的凸包，作为树的根节点求所有凸块的凸包，作为树的根节点l凸块列表按空间位置剖分凸块列表按空间位置剖分l递归过程，建构层次树递归过程，建构层次树算法预处理阶段l建构凸块的建构凸块的OBB包围盒包围盒l凸块所有顶点的坐标向量的协方差矩阵计算凸块所有顶点的坐标向量的协方差矩阵计算niikijikijikijjkrrqqppnC0)(31niiiirqpn0)(313,1kj算法预处理阶段l表面凸分解表面凸分解l
19、组织层次二叉树组织层次二叉树l为凸块构建为凸块构建OBB包围盒包围盒l对凸块进行三角形带压缩编码对凸块进行三角形带压缩编码算法预处理阶段l凸块的三角形带压缩编码凸块的三角形带压缩编码l在基于图象的碰撞检测算法中，两物体间进在基于图象的碰撞检测算法中，两物体间进行一次碰撞检测往往需要对物体进行多次绘行一次碰撞检测往往需要对物体进行多次绘制制 l提高绘制速度提高绘制速度 l三角形带不改变物体的几何结构三角形带不改变物体的几何结构算法预处理阶段l凸块的三角形带凸块的三角形带压缩编码压缩编码l利用三角形网利用三角形网格模型的连通格模型的连通性对生成的三性对生成的三角形带进行编角形带进行编码压缩码压缩
20、深黑色的折线指示出三角形带碰撞检测核心算法 l遍历物体对的层次凸块二叉树遍历物体对的层次凸块二叉树l递归遍历，广度优先（递归遍历，广度优先（BFS）l检测凸块检测凸块OBB包围盒是否相交包围盒是否相交l采用基于图象的方法检测凸块之间的相交采用基于图象的方法检测凸块之间的相交情况情况碰撞检测核心算法l凸块之间的相交检测凸块之间的相交检测l通过图形硬件的绘制过程实现通过图形硬件的绘制过程实现l视域参数设置视域参数设置l视口（视口（viewport）的大小决定了绘制的速度）的大小决定了绘制的速度l直接利用直接利用OBB的相交结果来快速地设定尽可能小的相交结果来快速地设定尽可能小的视口的视口碰撞检测核
21、心算法l利用利用OBB的相交结果来设定尽可能小的视口的相交结果来设定尽可能小的视口l凸块凸块OBB包围盒的相交检测方法包围盒的相交检测方法l分离轴定理分离轴定理，15个分离轴个分离轴 A B A DS SAD B SA 碰撞检测核心算法l利用利用OBB的相交结果来设定尽可能小的视口的相交结果来设定尽可能小的视口l视域参数设置视域参数设置碰撞检测核心算法l凸块之间的基于图象的相交检测过程凸块之间的基于图象的相交检测过程l判断凸块在视域中平行透视投影的图象是否判断凸块在视域中平行透视投影的图象是否相交相交l多遍绘制，并利用深度信息进行深度测试多遍绘制，并利用深度信息进行深度测试l利用模板缓存保存相
22、交结果利用模板缓存保存相交结果l读取模板缓存值获取相交结果读取模板缓存值获取相交结果碰撞检测核心算法l凸块之间的相凸块之间的相交检测过程交检测过程l模板缓存与物模板缓存与物体相交关系的体相交关系的对应图对应图 模板缓存值 Zmin Zmax 情况 0 情况 1 情况 2 情况 3 情况 4 情况 5 情况 6 情况 7 Amin Amax Bmin Bmax Amin Amax Bmax Bmin Amin Amax Bmax Amin Bmin Amax Bmax Bmin Amin Amax Bmax Amin Bmin Amax Amin Bmax Bmin Amax 3 3 3 2 2
23、 1 10 视线方向 实验结果130多个物体 18,217个三角面片实验结果实验结果小结 l创新点创新点l提出了一种可处理任意形状物体间碰撞检测提出了一种可处理任意形状物体间碰撞检测问题的基于图象的快速碰撞检测算法问题的基于图象的快速碰撞检测算法l结合了图形硬件绘制性能，三角形带绘制加结合了图形硬件绘制性能，三角形带绘制加速技术和速技术和OBB包围盒的简化优势来提高复杂包围盒的简化优势来提高复杂物体间碰撞检测的速度物体间碰撞检测的速度第三部分 基于流的实时碰撞检测算法本章研究意义l基于图象的碰撞检测算法（采用一般图形基于图象的碰撞检测算法（采用一般图形硬件）普遍存在的问题硬件）普遍存在的问题l
24、硬件绘制的图象本身固有的离散性会带来的硬件绘制的图象本身固有的离散性会带来的误差，在精确性和准确性方面有欠缺误差，在精确性和准确性方面有欠缺l新的契机新的契机l高性能可编程高性能可编程GPU 的出现的出现l图形绘制流水线的变革图形绘制流水线的变革l浮点缓存技术浮点缓存技术本章主要内容l流计算模式流计算模式 l基于流的碰撞检测基本算法基于流的碰撞检测基本算法l优化的基于流的碰撞检测算法优化的基于流的碰撞检测算法 l本章小结本章小结 流计算模式 流处理器 输出数据流 输入数据流 .l易于并行化易于并行化l能够有效利用高带宽能够有效利用高带宽l消除潜在的内存重用危险消除潜在的内存重用危险流计算模式l
25、可编程图形流水线可编程图形流水线l可编程顶点处理器（可编程顶点处理器（vertex shader）l可编程片断处理器或象素处理器（可编程片断处理器或象素处理器（fragment shader or pixel shader）几何基本体素 顶点几何变化与光照计算 光栅化和插值 帧缓存 剔除与裁剪 光栅操作 纹理拾取与应用 颜色求和与雾的计算 可编程的顶可编程的顶点处理器点处理器可编程的片可编程的片断处理器断处理器基于流的碰撞检测基本算法 l主要思想主要思想l将碰撞检测计算映射为流计算模式将碰撞检测计算映射为流计算模式 l采用检查一物体的所有边与另一物体的所有三角形是采用检查一物体的所有边与另一物
26、体的所有三角形是否有交的方法来确定它们是否发生碰撞否有交的方法来确定它们是否发生碰撞 l碰撞检测问题转化为碰撞检测问题转化为边的数据流边的数据流与与一组三角形集合一组三角形集合的的相交检测相交检测AB基于流的碰撞检测基本算法l算法步骤算法步骤l边纹理生成边纹理生成l边与三角形求交边与三角形求交l求交结果获取求交结果获取l各步骤之间通过存储在纹理和帧缓存中的数据各步骤之间通过存储在纹理和帧缓存中的数据流联系在一起流联系在一起 基于流的碰撞检测基本算法l生成物体的边纹理生成物体的边纹理l起始点纹理起始点纹理（r，g，b）存放边起始点的位置向）存放边起始点的位置向量量）l方向长度纹理方向长度纹理（r
27、，g，b）存放边的方向矢量，）存放边的方向矢量，a 存放边的长度存放边的长度l边纹理大小由边的总数所决定边纹理大小由边的总数所决定l采用采用NV_RECTANGLE_TEXTURE的技术的技术l采用浮点缓存技术采用浮点缓存技术1enhw基于流的碰撞检测基本算法l边纹理的例子球的模型：共396条边象素对应于一条边边纹理:大小20 x20 象素对应于一条边未被使用的象素基于流的碰撞检测基本算法l边与三角形求交边与三角形求交l如何表示三角形的数据？如何表示三角形的数据？l如何用可编程如何用可编程GPU自定义的片断绘制程序实自定义的片断绘制程序实现边与三角形求交？现边与三角形求交？l如何从如何从GPU
28、中获取相交的结果？中获取相交的结果？基于流的碰撞检测基本算法 边纹理图 矩形(0,h)(0,0)(w,h)(w,0)矩形顶点属性:(v1-TEXCOORD1)(v2-TEXCOORD2)(v3-TEXCOORD3)(n-TEXCOORD4)TEXCOORD0 l边与三角形求交边与三角形求交l数据流输入数据流输入 l三角形的数据被存放在矩形顶点属性的纹理坐标中三角形的数据被存放在矩形顶点属性的纹理坐标中基于流的碰撞检测基本算法(0,0)(w,0)(0,h)(w,h)V1,V2,V3,N(三角形数据)光栅化基于流的碰撞检测基本算法l边与三角形求交边与三角形求交(0,0)(w,0)(0,h)(w,h
29、)边纹理 三角形数据纹理映射纹理映射片断绘制程序片断绘制程序由由Nvidia 的的Cg（C for graphics)程序实现程序实现返回交点的返回交点的t参数为当前深度值参数为当前深度值基于流的碰撞检测基本算法l边与三角形求交边与三角形求交l获取检测结果获取检测结果 l深度测试深度测试lt 边长度边长度lNVIDIA的硬件遮挡查询技术的硬件遮挡查询技术（NV_Occlusion_query)优化的基于流的碰撞检测算法 l基于流的碰撞检测基本算法的时间复杂度基于流的碰撞检测基本算法的时间复杂度 l边的个数边的个数 l三角形个数三角形个数 l两种优化方法两种优化方法 l层次树优化法层次树优化法
30、l子纹理优化法子纹理优化法 l减少每次求交检测中所涉及的边的个数减少每次求交检测中所涉及的边的个数 优化的基于流的碰撞检测算法l层次树优化法层次树优化法l尽量减少输入待检尽量减少输入待检测的三角形个数测的三角形个数 l边与包围盒求交检边与包围盒求交检测由测由PGPU的片断的片断绘制程序实现绘制程序实现 AB优化的基于流的碰撞检测算法l子纹理优化法子纹理优化法 l减少每次求交减少每次求交检测中所涉及检测中所涉及的边的个数的边的个数l依据相交的边依据相交的边重新构建新的重新构建新的边子纹理边子纹理 AB优化的基于流的碰撞检测算法 输入两物体:A and B 深度比较，得出所有与 OBB 相交边的集
31、合(E)创建与 A 的边纹理相同大小的视口，并设定视域参数 把 CO 的两个子节点放入递归堆栈（S）中 PGPU CPU 预处理创建 A，B 的边纹理和 OBB 树 首先处理 A 的边表与 B 的 OBB 树(A,B)之间的相交检测 通过一次纹理映射将边的长度写入深度缓存 绘制 Q，用片断绘制程序计算 A 的边与当前OBB 的相交检测 CO 是否 T 的叶子节点？设定 B 的 OBB 树(T)的根节点(R)为当前的 OBB（CO）执行基本算法中的边与三角形相交检测 否 是否相交？否 是 返回相交 交换 A 与 B的角色 重新创建边子纹理，并调整视口大小 E 为空？是 设定一个与视口同 大 小
32、的 矩 形（Q），其四个顶点属性均保存了CO 的参数 CO=R？从 S 中取出 一 个 元素作为 CO 返回不相交 是 否 S=？否(B,A)是 否 已处理？否 是 否 是 是 l优化的基优化的基于流的碰于流的碰撞检测算撞检测算法流程法流程 实验结果21,292个三角面片 18,217个三角面片实验结果40,419个三角面片 18,378个三角面片实验结果实验结果场景SCD0SCD1SCD2RECODERAPID1tcd 6627.547.623.029.31.0Speedup1139.2288.2226.26627.52tcd 2256.053.240.4Na1.9Speedup142.45
33、5.8Na1187.43tcd 15587.458.724.1Na161.6Speedup1265.5646.8Na96.54tcd9593.672.326.1Na10.2Speedup1132.7367.6Na940.5SCD0:基于流的碰撞检测基本算法；SCD1:采用了OBB树的基于流碰撞检测算法；SCD2:优化的基于流碰撞检测算法；RECODE:Baciu 1999中提出的算法；RAPID:Gottschalk 1996中提出的算法；tcd:平均碰撞检测时间(ms)；Speedup：各种方法相对SCD0的加速比。实验结果实验结果随场景复杂度变化的算法性能曲线本章小结 l可编程可编程GPU
34、上实现实时碰撞检测算法上实现实时碰撞检测算法l提出了两种有效的优化方法提出了两种有效的优化方法l算法特点算法特点l高效率高效率 l利用高性能的利用高性能的GPUl精确性精确性 l利用浮点缓存利用浮点缓存l通用性通用性 l可处理任意多边形网格物体可处理任意多边形网格物体l前景广阔前景广阔 lGPU的性能增长快于的性能增长快于CPU的性能增长的性能增长第四部分 并行碰撞检测算法本章研究意义及主要内容l研究意义研究意义l利用多处理机并行计算来加快碰撞检测过程利用多处理机并行计算来加快碰撞检测过程l主要内容主要内容l简单并行碰撞检测算法简单并行碰撞检测算法 l基于边包围体遍历策略的并行碰撞检测算法基于
35、边包围体遍历策略的并行碰撞检测算法l算法实现与实验结果算法实现与实验结果 l小结小结 简单并行碰撞检测算法 l建构平衡包围盒树建构平衡包围盒树 l简单串行碰撞检测算法简单串行碰撞检测算法 l简单并行碰撞检测算法简单并行碰撞检测算法 简单并行碰撞检测算法l建构平衡包围盒树建构平衡包围盒树l树的各节点的大小是否大致相当会直接影响并行算法的加速树的各节点的大小是否大致相当会直接影响并行算法的加速比比l平衡包围盒树保证兄弟节点的包围盒中包围的三角面片大致平衡包围盒树保证兄弟节点的包围盒中包围的三角面片大致相当相当 1568 896 840 509 457 479 423 256 285 261 228
36、 243 268 210 243 简单并行碰撞检测算法l简单串行碰撞检测算简单串行碰撞检测算法法l同时遍历两物体的层同时遍历两物体的层次树次树l简单并行碰撞检测算简单并行碰撞检测算法法l将一个层次上的各个将一个层次上的各个子任务进行并行处理子任务进行并行处理l并行算法粒度小，并并行算法粒度小，并行加速比不高行加速比不高 BVA,10(a)A的层次二叉树(b)B的层次二叉树 BVA,11 BVB,00 BVB,10 BVB,11 BVA,00 BVB,00 BVA,10 BVB,10 BVA,11 BVB,10 BVA,10 BVB,11 BVA,11 BVB,11(c)A与B的一个遍历任务树
37、BVA,00 基于边包围体遍历策略的并行碰撞检测算法l为提高并行的粒度为提高并行的粒度l基于边包围体遍历策略基于边包围体遍历策略l 一物体的所有边与另一物体之间通过遍历其一物体的所有边与另一物体之间通过遍历其层次包围体树来进行求交检测层次包围体树来进行求交检测l算法所采用的遍历策略称为算法所采用的遍历策略称为“边包围体遍历边包围体遍历策略策略”基于边包围体遍历策略的并行碰撞检测算法l采用采用“边包围体遍历策略边包围体遍历策略”遍历生成的层次任务树遍历生成的层次任务树l子任务个数减少子任务个数减少l每个任务节点的计算量增加每个任务节点的计算量增加l并行的粒度加大并行的粒度加大l并行处理任务树每一
38、层上的子任务并行处理任务树每一层上的子任务 ESA ESA ESA ESA ESA ESA ESA BVB,00 BVB,10 BVB,11 BVB,20 BVB,20 BVB,21 BVB,21 物体A边的集合算法实现 l采用多线程技术采用多线程技术l(1)提高应用程序响应；提高应用程序响应；(2)更加有效地使用更加有效地使用多多CPU系统；系统；(3)改善程序结构；改善程序结构；(4)占用更占用更少的系统资源；少的系统资源；(5)改善性能改善性能 l在多处理机上实现在多处理机上实现lSGI ONYX2工作站（工作站（4个个R10000处理器）处理器）实验结果28,853个18,378个 1
39、0,131个三角面片实验结果 场景SSCDSPCDESCDEPCD1tcd246.9109.4231.289.3Speedup12.2612.592tcd3652.11443.8349.1125.9Speedup12.5312.773tcd14832.77225.9581.7222.4Speedup12.0512.66SSCD:简单串行碰撞检测算法；简单串行碰撞检测算法；SPCD:简单的并行碰撞检测算法；简单的并行碰撞检测算法；ESCD:基于基于边包围体遍历策略的串行碰撞检测算法；边包围体遍历策略的串行碰撞检测算法；EPCD:基于边包围体遍历策略的并行基于边包围体遍历策略的并行碰撞检测算法；碰
40、撞检测算法；tcd:平均碰撞检测时间平均碰撞检测时间(ms)；Speedup：并行算法相对其相应串行：并行算法相对其相应串行算法的加速比。算法的加速比。本章小结 l算法主要特点算法主要特点l利用并行思想利用并行思想l提出了一种边包围体的遍历策略提出了一种边包围体的遍历策略l加大了并行算法的粒度，提高并行加速比，改善加大了并行算法的粒度，提高并行加速比，改善了并行碰撞检测算法的效率了并行碰撞检测算法的效率l采用多线程技术实现，具有一定的通用性采用多线程技术实现，具有一定的通用性l适用于对动态、复杂的场景进行实时碰撞检适用于对动态、复杂的场景进行实时碰撞检测测第五部分 总结与展望总结l本文着重探讨
41、了如何利用图形硬件的高计算性本文着重探讨了如何利用图形硬件的高计算性能、可编程性及多处理机的并行计算能力来有能、可编程性及多处理机的并行计算能力来有效提高碰撞检测算法的效率。效提高碰撞检测算法的效率。l提出了一种基于流的、精确快速的碰撞检测算法。提出了一种基于流的、精确快速的碰撞检测算法。l突破了一般基于图形硬件的碰撞检测算法在检测精突破了一般基于图形硬件的碰撞检测算法在检测精度上的局限性。度上的局限性。l提出了一种新的基于图象的快速碰撞检测算法。提出了一种新的基于图象的快速碰撞检测算法。l提出了一种并行的快速碰撞检测算法。提出了一种并行的快速碰撞检测算法。l实现了以上算法，进行了相应的测试，给出了比较实现了以上算法，进行了相应的测试，给出了比较结果。结果。今后工作展望 l通过合理平衡通过合理平衡CPU和和GPU的计算负载，的计算负载，优化基于图象碰撞检测算法的性能优化基于图象碰撞检测算法的性能l进一步提高基于流的碰撞检测算法的效率进一步提高基于流的碰撞检测算法的效率l改进基于流的碰撞检测算法，使其能够有改进基于流的碰撞检测算法，使其能够有效地处理可变形物体效地处理可变形物体 谢 谢！
