图像的快速碰撞检测算法.ppt

《图像的快速碰撞检测算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于图像的快速碰撞检测算法范昭炜万华根高曙明浙江大学CAD&CG国家重点实验室Chinagraph’2002,BeijingSeptember26,2002概要背景相关工作基于图像的碰撞检测算法算法实现与实验结果结论背景碰撞检测的重要性待解决的问题实时性大规模场景本文的研究目标提高碰撞检测算法效率面向大规模场景计算机动画虚拟现实物理仿真计算机图形学其他相关领域碰撞检测相关工作碰撞检测算法分类基于物体空间基于图像空间相关工作基于物体空间的碰撞检测处理凸体M.Lin,etal(UNC)I-COLLIDE，SWIF

2、TK,ChungandW.WangQ-COLLIDEMirtichVCLIP可处理非凸物体Gottschalk,M.Lin,etalRAPIDV-COLLIDET.Klosowski,etalQUICKCDS.CameronSOLID相关工作基于图像空间的碰撞检测ShinyaandForque,1991Rossignac,Siggraph’92Myszkowski,1995Baciu(RECODE),1999…基于图像的碰撞检测算法输入物体模型建构节点为凸体的层次二叉树对层次树节点进行三角形带压缩编码进行表面

3、凸分解得到一系列凸面片遍历物体对的层次二叉树在层次树的节点对之间进行基于图像空间的碰撞检测利用掠扫和删减技术快速找到可能发生碰撞的物体对碰撞检测阶段判断并返回检测结果预处理阶段算法整体框架基于表面的凸分解目的把非凸物体的表面分解成一些凸面片的集合方法基于共轭图的搜索方法选定种子面遍历共轭图三个判别准则基于表面的凸分解三个判别准则准则1：遍历经过的边不能是凹边；准则2：在当前处理面的远顶点（即除邻边的两顶点之外的顶点）处不能看到当前凸片中任一面的外表面；准则3：当增加当前面后，所形成的新凸块不能与任何非原凸片上

4、的面相交。基于表面的凸分解一个简单的表面凸分解实例基于图像的碰撞检测算法输入物体模型建构节点为凸体的层次二叉树对层次树节点进行三角形带压缩编码进行表面凸分解得到一系列凸面片遍历物体对的层次二叉树在层次树的节点对之间进行基于图像空间的碰撞检测利用掠扫和删减技术快速找到可能发生碰撞的物体对碰撞检测阶段判断并返回检测结果预处理阶段算法整体框架凸块层次二叉树的建构对象一组凸块的集合建构策略自顶向下√自底向上凸块集的划分凸块层次二叉树的建构用质点代表凸块的位置求所有质点凸包的协方差矩阵特征向量提取求出最大伸展方向设置该

5、方向为剖分轴所有质点在剖分轴上的垂直投影排序将有序数值列表按一定方法划分为两组凸块集的划分过程基于图像的碰撞检测算法输入物体模型建构节点为凸体的层次二叉树对层次树节点进行三角形带压缩编码进行表面凸分解得到一系列凸面片遍历物体对的层次二叉树在层次树的节点对之间进行基于图像空间的碰撞检测利用掠扫和删减技术快速找到可能发生碰撞的物体对碰撞检测阶段判断并返回检测结果预处理阶段算法整体框架凸块的三角形带压缩编码目的优化三角形带，加快绘制过程方法借鉴Isenburg,2000三角形带压缩编码的思想实现预处理阶段三角形带压

6、缩编码碰撞检测阶段对三角形带进行解码绘制，提高绘制速度，进而加速基于图像的碰撞检测过程中的物体绘制基于图像的碰撞检测算法输入物体模型建构节点为凸体的层次二叉树对层次树节点进行三角形带压缩编码进行表面凸分解得到一系列凸面片遍历物体对的层次二叉树在层次树的节点对之间进行基于图像空间的碰撞检测利用掠扫和删减技术快速找到可能发生碰撞的物体对碰撞检测阶段判断并返回检测结果预处理阶段基于图像的碰撞检测算法核心算法思路凸体之间进行检测将三维物体的碰撞检测问题降维到二维图像空间，并最终简化到深度方向上的一维区间进行重叠检测一

7、维区间重叠与模板缓存基于图像的碰撞检测算法核心算法流程输入凸体A和凸体B求出A，B在投影面上的最小重叠区域(MOR)；禁止写帧缓存；清深度缓存与模板缓存调用myRender－SetStencilByZ(A)；调用myRender－TestStencilByZ(B);SecondRender=false;for(MOR上所有象素点){if(模板缓存值为2)return(true);//发现碰撞if(模板缓存值为3)SecondRender＝true;}returnfalse;//没有碰撞发生for(MOR上所有

8、象素点){if(模板缓存值为2)return(true);//发现碰撞}//endforSecondRender?=false清深度缓存与模板缓存调用myRender－SetStencilByZ(B)；调用myRender－TestStencilByZ(A);truefalse核心算法流程输入凸体A和凸体B求出A，B在投影面上的最小重叠区域(MOR)；禁止写帧缓存；清深度缓存与模板缓存调用myRen