实时碰撞检测技术研究

实时碰撞检测技术研究答辨人范昭炜指导教师高曙明研究员万华根副研究员博士学位论文答辨浙江大学CAD&CG国家重点实验室浙江大学计算机科学与技术学院二〇〇三年十一月二十六日主要内容绪论基于图象的快速碰撞检测算法基于流的实时碰撞检测算法并行碰撞检测算法总结与展望第一部分绪论研究背景和研究意义碰撞检测问题是机器人、动画仿真、虚拟现实等领域不可回避的问题之一基本任务确定两个或多个物体彼此之间是否发生接触或穿透。起源早期在机器人路径规划、自动装配规划等领域中，为检测机器人与场景中的物体或零件与零件之间是否发生碰撞，产生了一系列碰撞检测算法。研究背景和研究意义目前研究的意义虚拟场景中的物体模型越来越复杂在仿真中对实时性和真实性的要求越来越高现有的碰撞检测算法无法满足要求碰撞检测算法分类从两个角度对碰撞检测算法进行分类从时间域的角度来分从空间域的角度来分基于时间域的碰撞检测算法分类分为静态、离散和连续的碰撞检测算法静态碰撞检测算法静止状态下进行碰撞检测[Dobkin1985][Agarwal1991][Chazelle1989]离散碰撞检测算法在每一时间的离散点上进行碰撞检测是研究的重点和热点[Lin1998][Jiménez2001]基于时间域的碰撞检测算法分类离散碰撞检测算法存在问题存在刺穿现象遗漏应该发生的碰撞连续碰撞检测算法连续的时间间隔内进行碰撞检测计算速度还太慢[Cameron1990][Canny1986][Redon2001][Redon2002a]基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于图象空间的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法采用空间结构的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法多边形表示模型多边形集合，结构化表示模型非多边形表示模型CSG表示模型，隐函数曲面，参数曲面，体表示模型多边形表示模型非多边形表示模型结构化表示模型多边形集合CSG表示模型隐函数曲面参数曲面几何模型体表示模型基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法面向多边形表示模型的碰撞检测算法[Hubbard1995][Gottschalk1996][Klosowski1998][Zachmann1998]面向凸体的碰撞检测算法基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法面向凸体的碰撞检测算法基于特征的碰撞检测算法Lin-Canny的“最邻近特征算法”[Lin1991,Lin1993][Lin1995],[Cohen1995],[Chung1996],[Mirtich1998],[Ehmann2000],[Ehmann2001]基于单纯形（Simplex）的碰撞检测算法Gilbert、Johnson和Keerthi[Gilbert1988][Gilbert1990]提出的GJK算法[Cameron1997][Bergen1999]基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法面向CSG表示模型[Zeiller1993][Su1996][Poutain2001]面向隐函数曲面表示[Farouki1989][Miller1991][Shene1991]面向参数曲面表示非均匀有理B样条曲线（NURBS）[Turnbull1998]体表示模型主要用于虚拟手术中可变形物体的碰撞检测[Heidelb2003][Boyles1999][魏迎梅2001]基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用一般表示模型的碰撞检测算法采用空间结构的碰撞检测算法空间剖分法（spacedecomposition）均匀剖分、BSP树、k-d树和八叉树（Octree）等[Samet1989][Naylor1990][Bourma1991]层次包围体树法（hierarchicalboundingvolumetrees）基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用空间结构的碰撞检测算法层次包围体树法，包围体类型的不同来加以区分层次包围球树[Hubbard1993][Hubbard1995][Palmer1995][O’Sullivan1999]、AABB层次树（AlignedAxisBoundingBox）[Zachmann1997][Bergen1997][Larsson2001]、OBB层次树（OrientedBoundingBox）[Gottschalk1996]k-dop层次树（DiscreteOrientationPolytope）[Klosowski1998][Zachmann1998]QuOSPO层次树(QuantizedOrientationSlabswithPrimaryOrientations)[He1999]凸块层次树[Ehmann2001]混合层次包围体树[Wan2001]等等基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法采用空间结构的碰撞检测算法层次包围体树法，包围体类型的不同来加以区分(a)包围球(b)AABB包围盒(c)OBB包围盒(d)6-dop包围体(e)凸包包围体包围体二维示意图基于空间域的碰撞检测算法分类基于物体空间的碰撞检测算法基于图象空间的碰撞检测算法利用图形硬件对物体的二维图象采样相应的深度信息基于空间域的碰撞检测算法分类基于图象空间的碰撞检测算法Shinya等[Shinya1991]和Rossignac等[Rossignac1992]Myszkowski等[Myszkow1995]Baciu等[Baciu1997][Baciu1999]Hoff等[Hoff2001]，Kim等[Kim2002]，[Lombardo1999]，[Vassilev2001]，[Heidelb2003]，[Govindar2003]基于可编程图形硬件….碰撞检测算法框架详细检测阶段初步检测阶段逐步求精层精确求交层归纳出一个统一的碰撞检测算法框架碰撞检测算法的一般框架初步检测阶段空间剖分法基于插入排序的“掠扫和裁剪”法([Cohen1995])碰撞检测算法的一般框架详细检测阶段逐步求精层空间层次剖分技术和层次包围体树技术精确求交层主要处理多边形面片或基本体素之间的精确相交检测目前存在的问题处理大规模复杂场景的能力不足处理非凸物体的能力不足基于图象的碰撞检测算法的精度不高面向特定应用领域的高效碰撞检测算法缺乏离散碰撞检测算法的刺穿和遗漏问题本文研究目标提高碰撞检测算法的效率以达到实时性要求突破基于图象算法在适用面和检测精度上的局限性本文研究内容从三个角度出发，设计、实现并验证了一组新的碰撞检测算法从利用图形硬件辅助通用计算的角度出发，研究并提出一种新的基于图象空间的快速碰撞检测算法从利用可编程图形硬件高并行性的角度出发，提高基于图象的碰撞检测算法的速度与精确性从利用多处理机并行计算能力的角度出发，提出一种并行的快速碰撞检测算法第二部分基于图象的快速碰撞检测算法本章研究意义多数基于图象的碰撞检测算法优缺点有效利用图形硬件绘制加速功能，减轻CPU计算负荷，提高碰撞检测效率存在的问题仅能在凸体间进行碰撞检测，绘制过程往往直接针对物体进行，缺乏必要的优化手段，性能不够理想本章研究意义算法设计目的继承一般基于图象的碰撞检测算法优点突破局限性能够在保证效率的前提下处理任意形状多面体之间的碰撞检测问题算法采用的主要技术基于表面的凸分解三角形带压缩编码技术OBB包围盒技术算法概述预处理阶段物体模型输入建构层次凸块二叉树对每个凸块进行三角形带的压缩遍历物体对的两个层次凸块树碰撞检测运行阶段碰撞检测结果获取和返回在凸块节点间进行图象空间的碰撞检测检测凸块OBB包围盒之间是否相交，并由检测结果设置视域参数为层次树中每个凸块节点生成OBB包围盒表面凸分解得到凸片集合，由凸片集生成凸块集合算法预处理阶段表面凸分解组织层次凸块二叉树；为凸块构建OBB包围盒；对凸块进行三角形带压缩编码。算法预处理阶段基于表面的凸分解目的，使算法可处理任意形状的物体非凸物体的表面分解成一些凸面片的集合(a)凸片(b)相应的凸块算法预处理阶段表面凸分解的结果示例算法预处理阶段建构层次二叉树自顶向下的方法将凸块集（或称为凸块列表）组织成层次二叉树结构求所有凸块的凸包，作为树的根节点凸块列表按空间位置剖分递归过程，建构层次树算法预处理阶段建构凸块的OBB包围盒凸块所有顶点的坐标向量的协方差矩阵计算niikijikijikijjkrrqqppnC0)(31niiiirqpn0)(313,1kj算法预处理阶段表面凸分解组织层次二叉树为凸块构建OBB包围盒对凸块进行三角形带压缩编码算法预处理阶段凸块的三角形带压缩编码在基于图象的碰撞检测算法中，两物体间进行一次碰撞检测往往需要对物体进行多次绘制提高绘制速度三角形带不改变物体的几何结构算法预处理阶段凸块的三角形带压缩编码利用三角形网格模型的连通性对生成的三角形带进行编码压缩深黑色的折线指示出三角形带碰撞检测核心算法遍历物体对的层次凸块二叉树递归遍历，广度优先（BFS）检测凸块OBB包围盒是否相交采用基于图象的方法检测凸块之间的相交情况碰撞检测核心算法凸块之间的相交检测通过图形硬件的绘制过程实现视域参数设置视口（viewport）的大小决定了绘制的速度直接利用OBB的相交结果来快速地设定尽可能小的视口碰撞检测核心算法利用OBB的相交结果来设定尽可能小的视口凸块OBB包围盒的相交检测方法分离轴定理，15个分离轴ABADSSADBSA碰撞检测核心算法AB视口φA2φA1a2(0,0,0)相机位置(C1,C2,-∞)xyDa1利用OBB的相交结果来设定尽可能小的视口视域参数设置碰撞检测核心算法凸块之间的基于图象的相交检测过程判断凸块在视域中平行透视投影的图象是否相交多遍绘制，并利用深度信息进行深度测试利用模板缓存保存相交结果读取模板缓存值获取相交结果碰撞检测核心算法凸块之间的相交检测过程模板缓存与物体相交关系的对应图模板缓存值ZminZmax情况0情况1情况2情况3情况4情况5情况6情况7AminAmaxBminBmaxAminAmaxBmaxBminAminAmaxBmaxAminBminAmaxBmaxBminAminAmaxBmaxAminBminAmaxAminBmaxBminAmax333221130视线方向实验结果130多个物体18,217个三角面片实验结果0204060801001202500500075001000012500150002000025000三角面片总数(个)平均碰撞检测时间(ms)RAPIDRECODEIBCDIBCD(nostrips)05101520253035404525005000750010000150001750020000三角面片总数(个)平均碰撞检测时间(ms)RAPIDRECODEIBCDIBCD(nostrips)实验结果-100%-75%-50%-25%0%25%50%75%100%50100150200250300350400450500碰撞检测的步数碰撞检测时间的变化率IBCDRAPID小结创新点提出了一种可处理任意形状物体间碰撞检测问题的基于图象的快速碰撞检测算法结合了图形硬件绘制性能，三角形带绘制加速技术和OBB包围盒的简化优势来提高复杂物体间碰撞检测的速度第三部分基于流的实时碰撞检测算法本章研究意义基于图象的碰撞检测算法（采用一般图形硬件）普遍存在的问题硬件绘制的图象本