实时碰撞检测技术研究概要课件

实时碰撞检测技术研究

答辨人 范昭炜指导教师高曙明研究员 万华根副研究员博士学位论文答辨浙江大学CAD&CG国家重点实验室浙江大学计算机科学与技术学院二〇〇三年十一月二十六日实时碰撞检测技术研究 答辨人 范昭炜博士学位论文答1主要内容绪论基于图象的快速碰撞检测算法基于流的实时碰撞检测算法并行碰撞检测算法总结与展望主要内容绪论2第一部分 绪论第一部分 绪论3研究背景和研究意义碰撞检测问题是机器人、动画仿真、虚拟现实等领域不可回避的问题之一基本任务确定两个或多个物体彼此之间是否发生接触或穿透。起源 早期在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算法。研究背景和研究意义碰撞检测问题4研究背景和研究意义目前研究的意义虚拟场景中的物体模型越来越复杂在仿真中对实时性和真实性的要求越来越高现有的碰撞检测算法无法满足要求研究背景和研究意义目前研究的意义5碰撞检测算法分类从两个角度对碰撞检测算法进行分类从时间域的角度来分从空间域的角度来分碰撞检测算法分类从两个角度对碰撞检测算法进行分类6基于时间域的碰撞检测算法分类分为静态、离散和连续的碰撞检测算法静态碰撞检测算法 静止状态下进行碰撞检测[Dobkin1985][Agarwal1991][Chazelle1989]离散碰撞检测算法在每一时间的离散点上进行碰撞检测是研究的重点和热点[Lin1998][Jiménez2001]基于时间域的碰撞检测算法分类分为静态、离散和连续的碰撞检测7基于时间域的碰撞检测算法分类离散碰撞检测算法存在问题存在刺穿现象遗漏应该发生的碰撞连续碰撞检测算法连续的时间间隔内进行碰撞检测计算速度还太慢[Cameron1990][Canny1986][Redon2001][Redon2002a]基于时间域的碰撞检测算法分类离散碰撞检测算法8基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于图象空间的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法9基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法采用空间结构的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法10基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法多边形表示模型多边形集合，结构化表示模型非多边形表示模型CSG表示模型，隐函数曲面，参数曲面，体表示模型基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法11基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法面向多边形表示模型的碰撞检测算法[Hubbard1995][Gottschalk1996][Klosowski1998][Zachmann1998]面向凸体的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法12基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法面向凸体的碰撞检测算法基于特征的碰撞检测算法Lin-Canny的“最邻近特征算法”[Lin1991,Lin1993][Lin1995],[Cohen1995],[Chung1996],[Mirtich1998],[Ehmann2000],[Ehmann2001]基于单纯形（Simplex）的碰撞检测算法Gilbert、Johnson和Keerthi[Gilbert1988][Gilbert1990]提出的GJK算法[Cameron1997][Bergen1999]

基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法13基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法面向CSG表示模型[Zeiller1993][Su1996][Poutain2001]面向隐函数曲面表示[Farouki1989][Miller1991][Shene1991]面向参数曲面表示非均匀有理B样条曲线（NURBS）[Turnbull1998]体表示模型主要用于虚拟手术中可变形物体的碰撞检测[Heidelb2003][Boyles1999][魏迎梅2001]

基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法14基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法采用空间结构的碰撞检测算法空间剖分法（spacedecomposition）均匀剖分、BSP树、k-d树和八叉树（Octree）等[Samet1989][Naylor1990][Bourma1991]层次包围体树法（hierarchicalboundingvolumetrees）基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法15基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用空间结构的碰撞检测算法层次包围体树法，包围体类型的不同来加以区分层次包围球树[Hubbard1993][Hubbard1995][Palmer1995][O’Sullivan1999]、AABB层次树（AlignedAxisBoundingBox）[Zachmann1997][Bergen1997][Larsson2001]、OBB层次树（OrientedBoundingBox）[Gottschalk1996]k-dop层次树（DiscreteOrientationPolytope）[Klosowski1998][Zachmann1998]

QuOSPO层次树(QuantizedOrientationSlabswithPrimaryOrientations)[He1999]

凸块层次树[Ehmann2001]

混合层次包围体树[Wan2001]等等

基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法16基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用空间结构的碰撞检测算法层次包围体树法，包围体类型的不同来加以区分(a)包围球(b)AABB包围盒(c)OBB包围盒(d)6-dop包围体(e)凸包包围体包围体二维示意图基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法(a)17基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于图象空间的碰撞检测算法利用图形硬件对物体的二维图象采样相应的深度信息基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法18基于空间域的碰撞检测算法分类基于图象空间的碰撞检测算法Shinya等[Shinya1991]和Rossignac等[Rossignac1992]Myszkowski等[Myszkow1995]Baciu等[Baciu1997][Baciu1999]Hoff等[Hoff2001]，Kim等[Kim2002]，[Lombardo1999]，[Vassilev2001]，[Heidelb2003]，[Govindar2003]基于可编程图形硬件….基于空间域的碰撞检测算法分类基于图象空间的碰撞检测算法19碰撞检测算法框架归纳出一个统一的碰撞检测算法框架碰撞检测算法框架归纳出一个统一的碰撞检测算法框架20碰撞检测算法的一般框架初步检测阶段空间剖分法基于插入排序的“掠扫和裁剪”法([Cohen1995])

碰撞检测算法的一般框架初步检测阶段21碰撞检测算法的一般框架详细检测阶段逐步求精层空间层次剖分技术和层次包围体树技术精确求交层主要处理多边形面片或基本体素之间的精确相交检测碰撞检测算法的一般框架详细检测阶段22目前存在的问题处理大规模复杂场景的能力不足处理非凸物体的能力不足基于图象的碰撞检测算法的精度不高面向特定应用领域的高效碰撞检测算法缺乏离散碰撞检测算法的刺穿和遗漏问题目前存在的问题处理大规模复杂场景的能力不足23本文研究目标提高碰撞检测算法的效率以达到实时性要求突破基于图象算法在适用面和检测精度上的局限性本文研究目标提高碰撞检测算法的效率以达到实时性要求24本文研究内容从三个角度出发，设计、实现并验证了一组新的碰撞检测算法从利用图形硬件辅助通用计算的角度出发，研究并提出一种新的基于图象空间的快速碰撞检测算法从利用可编程图形硬件高并行性的角度出发，提高基于图象的碰撞检测算法的速度与精确性从利用多处理机并行计算能力的角度出发，提出一种并行的快速碰撞检测算法

本文研究内容从三个角度出发，设计、实现并验证了一组新的碰撞检25第二部分 基于图象的

快速碰撞检测算法第二部分 基于图象的

快速碰撞检测算法26本章研究意义多数基于图象的碰撞检测算法优缺点有效利用图形硬件绘制加速功能，减轻CPU计算负荷，提高碰撞检测效率存在的问题仅能在凸体间进行碰撞检测，绘制过程往往直接针对物体进行，缺乏必要的优化手段，性能不够理想

本章研究意义多数基于图象的碰撞检测算法优缺点27本章研究意义算法设计目的继承一般基于图象的碰撞检测算法优点突破局限性能够在保证效率的前提下处理任意形状多面体之间的碰撞检测问题算法采用的主要技术基于表面的凸分解三角形带压缩编码技术OBB包围盒技术

本章研究意义算法设计目的28算法概述算法概述29算法预处理阶段表面凸分解组织层次凸块二叉树；为凸块构建OBB包围盒；对凸块进行三角形带压缩编码。算法预处理阶段表面凸分解30算法预处理阶段基于表面的凸分解目的，使算法可处理任意形状的物体非凸物体的表面分解成一些凸面片的集合

(a)凸片 (b)相应的凸块算法预处理阶段基于表面的凸分解

(a)凸片 31算法预处理阶段表面凸分解的结果示例算法预处理阶段表面凸分解的结果示例32算法预处理阶段建构层次二叉树自顶向下的方法将凸块集（或称为凸块列表）组织成层次二叉树结构求所有凸块的凸包，作为树的根节点凸块列表按空间位置剖分递归过程，建构层次树算法预处理阶段建构层次二叉树33算法预处理阶段建构凸块的OBB包围盒凸块所有顶点的坐标向量的协方差矩阵计算算法预处理阶段建构凸块的OBB包围盒34算法预处理阶段表面凸分解组织层次二叉树为凸块构建OBB包围盒对凸块进行三角形带压缩编码算法预处理阶段表面凸分解35算法预处理阶段凸块的三角形带压缩编码在基于图象的碰撞检测算法中，两物体间进行一次碰撞检测往往需要对物体进行多次绘制提高绘制速度三角形带不改变物体的几何结构算法预处理阶段凸块的三角形带压缩编码36算法预处理阶段凸块的三角形带压缩编码利用三角形网格模型的连通性对生成的三角形带进行编码压缩

深黑色的折线指示出三角形带算法预处理阶段凸块的三角形带压缩编码深黑色的折线指示出三37碰撞检测核心算法遍历物体对的层次凸块二叉树递归遍历，广度优先（BFS）检测凸块OBB包围盒是否相交采用基于图象的方法检测凸块之间的相交情况碰撞检测核心算法遍历物体对的层次凸块二叉树38碰撞检测核心算法凸块之间的相交检测通过图形硬件的绘制过程实现视域参数设置视口（viewport）的大小决定了绘制的速度直接利用OBB的相交结果来快速地设定尽可能小的视口碰撞检测核心算法凸块之间的相交检测39碰撞检测核心算法利用OBB的相交结果来设定尽可能小的视口凸块OBB包围盒的相交检测方法分离轴定理，15个分离轴碰撞检测核心算法利用OBB的相交结果来设定尽可能小的视口40碰撞检测核心算法利用OBB的相交结果来设定尽可能小的视口视域参数设置碰撞检测核心算法利用OBB的相交结果来设定尽可能小的视口41碰撞检测核心算法凸块之间的基于图象的相交检测过程判断凸块在视域中平行透视投影的图象是否相交多遍绘制，并利用深度信息进行深度测试利用模板缓存保存相交结果读取模板缓存值获取相交结果碰撞检测核心算法凸块之间的基于图象的相交检测过程42碰撞检测核心算法凸块之间的相交检测过程模板缓存与物体相交关系的对应图碰撞检测核心算法凸块之间的相交检测过程43实验结果130多个物体 18,217个三角面片实验结果130多个物体 144实验结果实验结果45实验结果实验结果46小结创新点提出了一种可处理任意形状物体间碰撞检测问题的基于图象的快速碰撞检测算法结合了图形硬件绘制性能，三角形带绘制加速技术和OBB包围盒的简化优势来提高复杂物体间碰撞检测的速度小结创新点47第三部分 基于流的

实时碰撞检测算法 第三部分 基于流的

实时碰撞检测算法 48本章研究意义基于图象的碰撞检测算法（采用一般图形硬件）普遍存在的问题硬件绘制的图象本身固有的离散性会带来的误差，在精确性和准确性方面有欠缺新的契机高性能可编程GPU的出现图形绘制流水线的变革浮点缓存技术本章研究意义基于图象的碰撞检测算法（采用一般图形硬件）普遍存49本章主要内容流计算模式基于流的碰撞检测基本算法优化的基于流的碰撞检测算法本章小结本章主要内容流计算模式50流计算模式易于并行化能够有效利用高带宽消除潜在的内存重用危险流计算模式易于并行化51流计算模式可编程图形流水线可编程顶点处理器（vertexshader）可编程片断处理器或象素处理器（fragmentshaderorpixelshader）

可编程的顶点处理器可编程的片断处理器流计算模式可编程图形流水线可编程的顶点处理器可编程的片断处理52基于流的碰撞检测基本算法主要思想将碰撞检测计算映射为流计算模式采用检查一物体的所有边与另一物体的所有三角形是否有交的方法来确定它们是否发生碰撞碰撞检测问题转化为边的数据流与一组三角形集合的相交检测AB基于流的碰撞检测基本算法主要思想AB53基于流的碰撞检测基本算法算法步骤边纹理生成边与三角形求交求交结果获取各步骤之间通过存储在纹理和帧缓存中的数据流联系在一起

基于流的碰撞检测基本算法算法步骤54基于流的碰撞检测基本算法生成物体的边纹理起始点纹理（（r，g，b）存放边起始点的位置向量

）方向长度纹理（（r，g，b）存放边的方向矢量，a存放边的长度边纹理大小由边的总数所决定采用NV_RECTANGLE_TEXTURE的技术采用浮点缓存技术基于流的碰撞检测基本算法生成物体的边纹理55基于流的碰撞检测基本算法边纹理的例子球的模型：共396条边象素对应于一条边边纹理:大小20x20象素对应于一条边未被使用的象素基于流的碰撞检测基本算法边纹理的例子球的模型：共396条边象56基于流的碰撞检测基本算法边与三角形求交如何表示三角形的数据？

如何用可编程GPU自定义的片断绘制程序实现边与三角形求交？如何从GPU中获取相交的结果？基于流的碰撞检测基本算法边与三角形求交57基于流的碰撞检测基本算法边与三角形求交数据流输入三角形的数据被存放在矩形顶点属性的纹理坐标中基于流的碰撞检测基本算法边与三角形求交58基于流的碰撞检测基本算法(0,0)(w,0)(0,h)(w,h)V1,V2,V3,N(三角形数据)光栅化基于流的碰撞检测基本算法(0,0)59基于流的碰撞检测基本算法边与三角形求交(0,0)(w,0)(0,h)(w,h)

边纹理三角形数据纹理映射片断绘制程序由Nvidia的Cg（Cforgraphics)程序实现返回交点的t参数为当前深度值基于流的碰撞检测基本算法边与三角形求交(0,0)60基于流的碰撞检测基本算法边与三角形求交获取检测结果深度测试t<边长度NVIDIA的硬件遮挡查询技术（NV_Occlusion_query)基于流的碰撞检测基本算法边与三角形求交61优化的基于流的碰撞检测算法基于流的碰撞检测基本算法的时间复杂度边的个数三角形个数两种优化方法层次树优化法子纹理优化法减少每次求交检测中所涉及的边的个数优化的基于流的碰撞检测算法基于流的碰撞检测基本算法的时间复62优化的基于流的碰撞检测算法层次树优化法尽量减少输入待检测的三角形个数边与包围盒求交检测由PGPU的片断绘制程序实现

AB优化的基于流的碰撞检测算法层次树优化法AB63优化的基于流的碰撞检测算法子纹理优化法减少每次求交检测中所涉及的边的个数依据相交的边重新构建新的边子纹理

AB优化的基于流的碰撞检测算法子纹理优化法AB64优化的基于流的碰撞检测算法优化的基于流的碰撞检测算法流程

优化的基于流的碰撞检测算法优化的基于流的碰撞检测算法流程65实验结果21,292个三角面片 18,217个三角面片实验结果21,292个三角面片 18,217个三角面片66实验结果40,419个三角面片 18,378个三角面片实验结果40,419个三角面片 18,378个三角面67实验结果实验结果68实验结果场景SCD0SCD1SCD2RECODERAPID1tcd

6627.547.623.029.31.0Speedup1139.2288.2226.26627.52tcd

2256.053.240.4Na1.9Speedup142.455.8Na1187.43tcd

15587.458.724.1Na161.6Speedup1265.5646.8Na96.54tcd9593.672.326.1Na10.2Speedup1132.7367.6Na940.5SCD0:基于流的碰撞检测基本算法；SCD1:采用了OBB树的基于流碰撞检测算法；SCD2:优化的基于流碰撞检测算法；RECODE:[Baciu1999]中提出的算法；RAPID:[Gottschalk1996]中提出的算法；tcd:平均碰撞检测时间(ms)；Speedup：各种方法相对SCD0的加速比。实验结果场景SCD0SCD1SCD2RECODERAPID169实验结果实验结果70实验结果随场景复杂度变化的算法性能曲线实验结果随场景复杂度变化的算法性能曲线71本章小结可编程GPU上实现实时碰撞检测算法提出了两种有效的优化方法算法特点高效率利用高性能的GPU精确性利用浮点缓存通用性可处理任意多边形网格物体前景广阔 GPU的性能增长快于CPU的性能增长本章小结可编程GPU上实现实时碰撞检测算法72第四部分 并行碰撞检测算法第四部分 并行碰撞检测算法73本章研究意义及主要内容研究意义利用多处理机并行计算来加快碰撞检测过程主要内容简单并行碰撞检测算法基于边包围体遍历策略的并行碰撞检测算法算法实现与实验结果

小结本章研究意义及主要内容研究意义74简单并行碰撞检测算法建构平衡包围盒树简单串行碰撞检测算法简单并行碰撞检测算法简单并行碰撞检测算法建构平衡包围盒树75简单并行碰撞检测算法建构平衡包围盒树树的各节点的大小是否大致相当会直接影响并行算法的加速比平衡包围盒树保证兄弟节点的包围盒中包围的三角面片大致相当简单并行碰撞检测算法建构平衡包围盒树76简单并行碰撞检测算法简单串行碰撞检测算法同时遍历两物体的层次树简单并行碰撞检测算法将一个层次上的各个子任务进行并行处理并行算法粒度小，并行加速比不高简单并行碰撞检测算法简单串行碰撞检测算法77基于边包围体遍历策略的并行碰撞检测算法为提高并行的粒度基于边包围体遍历策略一物体的所有边与另一物体之间通过遍历其层次包围体树来进行求交检测算法所采用的遍历策略称为“边包围体遍历策略”基于边包围体遍历策略的并行碰撞检测算法为提高并行的粒度78基于边包围体遍历策略的并行碰撞检测算法采用“边包围体遍历策略”遍历生成的层次任务树子任务个数减少每个任务节点的计算量增加并行的粒度加大并行处理任务树每一层上的子任务物体A边的集合基于边包围体遍历策略的并行碰撞检测算法采用“边包围体遍历策略79算法实现采用多线程技术(1)提高应用程序响应；(2)更加有效地使用多CPU系统；(3)改善程序结构；