《图像的快速碰撞检测算法》由会员分享，可在线阅读，更多相关《图像的快速碰撞检测算法（28页珍藏版）》请在金锄头文库上搜索。
1、基于图像的快速碰撞检测算法,范昭炜 万华根 高曙明浙江大学CAD&CG国家重点实验室Chinagraph2002, Beijing September 26, 2002,概要,背景 相关工作 基于图像的碰撞检测算法 算法实现与实验结果 结论,背景,碰撞检测的重要性待解决的问题 实时性 大规模场景 本文的研究目标 提高碰撞检测算法效率 面向大规模场景,计算机 动画,虚拟现实,物理仿真,计算机 图形学,其他相关 领域,碰撞检测,相关工作,碰撞检测算法分类 基于物体空间 基于图像空间,相关工作,基于物体空间的碰撞检测 处理凸体 M.Lin, et al(UNC) I-COLLIDE， SWIFT K
2、, Chung and W. Wang Q-COLLIDE Mirtich VCLIP 可处理非凸物体 Gottschalk, M. Lin, et al RAPID V-COLLIDE T. Klosowski, et al QUICKCD S. Cameron SOLID,相关工作,基于图像空间的碰撞检测,Shinya and Forque, 1991,Rossignac, Siggraph92,Myszkowski, 1995,Baciu(RECODE), 1999,基于图像的碰撞检测算法,输入物体模型,建构节点为凸体的层次二叉树,对层次树节点进行三角形带压缩编码,进行表面凸分解得到一系
3、列凸面片,遍历物体对的层次二叉树,在层次树的节点对之间进行基于图像空间的碰撞检测,利用掠扫和删减技术快速找到可能发生碰撞的物体对,碰撞检测阶段,判断并返回检测结果,预处理阶段,算法整体框架,基于表面的凸分解,目的 把非凸物体的表面分解成一些凸面片的集合 方法 基于共轭图的搜索方法 选定种子面 遍历共轭图 三个判别准则,基于表面的凸分解,三个判别准则 准则1：遍历经过的边不能是凹边； 准则2：在当前处理面的远顶点（即除邻边的两顶点之外的顶点）处不能看到当前凸片中任一面的外表面； 准则3：当增加当前面后，所形成的新凸块不能与任何非原凸片上的面相交。,基于表面的凸分解,一个简单的表面凸分解实例,基于
4、图像的碰撞检测算法,输入物体模型,建构节点为凸体的层次二叉树,对层次树节点进行三角形带压缩编码,进行表面凸分解得到一系列凸面片,遍历物体对的层次二叉树,在层次树的节点对之间进行基于图像空间的碰撞检测,利用掠扫和删减技术快速找到可能发生碰撞的物体对,碰撞检测阶段,判断并返回检测结果,预处理阶段,算法整体框架,凸块层次二叉树的建构,对象 一组凸块的集合 建构策略 自顶向下 自底向上 凸块集的划分,凸块层次二叉树的建构,用质点代表凸块的位置,求所有质点凸包的协方差矩阵,特征向量提取求出最大伸展方向,设置该方向为剖分轴,所有质点在剖分轴上的垂直投影排序,将有序数值列表按一定方法划分为两组,凸块集的划分
5、过程,基于图像的碰撞检测算法,输入物体模型,建构节点为凸体的层次二叉树,对层次树节点进行三角形带压缩编码,进行表面凸分解得到一系列凸面片,遍历物体对的层次二叉树,在层次树的节点对之间进行基于图像空间的碰撞检测,利用掠扫和删减技术快速找到可能发生碰撞的物体对,碰撞检测阶段,判断并返回检测结果,预处理阶段,算法整体框架,凸块的三角形带压缩编码,目的 优化三角形带，加快绘制过程 方法 借鉴 Isenburg, 2000 三角形带压缩编码的思想 实现 预处理阶段 三角形带压缩编码 碰撞检测阶段 对三角形带进行解码绘制，提高绘制速度，进而加速基于图像的碰撞检测过程中的物体绘制,基于图像的碰撞检测算法,输
6、入物体模型,建构节点为凸体的层次二叉树,对层次树节点进行三角形带压缩编码,进行表面凸分解得到一系列凸面片,遍历物体对的层次二叉树,在层次树的节点对之间进行基于图像空间的碰撞检测,利用掠扫和删减技术快速找到可能发生碰撞的物体对,碰撞检测阶段,判断并返回检测结果,预处理阶段,基于图像的碰撞检测算法,核心算法思路 凸体之间进行检测 将三维物体的碰撞检测问题降维到二维图像空间，并最终简化到深度方向上的一维区间进行重叠检测 一维区间重叠与模板缓存,基于图像的碰撞检测算法,核心算法流程,输入凸体A 和凸体B,求出A，B在投影面上的 最小重叠区域(MOR)； 禁止写帧缓存；,清深度缓存与 模板缓存,调用my
7、Render SetStencilByZ(A)；,调用myRender TestStencilByZ(B);,SecondRender = false; for(MOR上所有象素点) if(模板缓存值为2)return(true); /发现碰撞 if(模板缓存值为3)SecondRender true; ,return false; /没有碰撞发生,for(MOR上所有象素点) if(模板缓存值为 2) return(true); /发现碰撞 / end for,SecondRender ?= false,清深度缓存与 模板缓存,调用myRender SetStencilByZ(B)；,调用m
8、yRender TestStencilByZ(A);,true,false,核心算法流程,输入凸体A 和凸体B,求出A，B在投影面上的 最小重叠区域(MOR)； 禁止写帧缓存；,清深度缓存与 模板缓存,调用myRender SetStencilByZ(A)；,调用myRender TestStencilByZ(B);,SecondRender = false; for(MOR上所有象素点) if(模板缓存值为2)return(true); /发现碰撞 if(模板缓存值为3)SecondRender true; ,return false; /没有碰撞发生,for(MOR上所有象素点) if(模
9、板缓存值为 2) return(true); /发现碰撞 / end for,SecondRender ?= false,清深度缓存与 模板缓存,调用myRender SetStencilByZ(B)；,调用myRender TestStencilByZ(A);,true,false,myRenderSetStencilByZ(X) 剔除物体X的正面； 用模板测试操作给模板缓存置1； 允许写深度缓存； 三角形带解码绘制X； ,核心算法流程,输入凸体A 和凸体B,求出A，B在投影面上的 最小重叠区域(MOR)； 禁止写帧缓存；,清深度缓存与 模板缓存,调用myRender SetStencilB
10、yZ(A)；,调用myRender TestStencilByZ(B);,SecondRender = false; for(MOR上所有象素点) if(模板缓存值为2)return(true); /发现碰撞 if(模板缓存值为3)SecondRender true; ,return false; /没有碰撞发生,for(MOR上所有象素点) if(模板缓存值为 2) return(true); /发现碰撞 / end for,SecondRender ?= false,清深度缓存与 模板缓存,调用myRender SetStencilByZ(B)；,调用myRender TestStenci
11、lByZ(A);,true,false,myRenderTestStencilByZ(X) 用模板测试只处理值为1的象素点； 深度测试是否满足条件Z(X)=Zmax； 上面两个测试通过，则模板缓存值加1； 禁止写深度缓存； 三角形带解码绘制X； /正面和背面 ,算法实现与实验结果,SGI ONYX2(195 MHz R10000 MIPS)工作站 Infinite Reality(IR2e) 图形卡 OpenGL/GLUT/C+ 两类场景 多物体场景 一对物体的场景 算法稳定性 碰撞检测时间的变化率：,两个测试场景,测试场景一的实验结果,实验结果,测试场景二的实验结果,实验结果,本算法在测试场
12、景二中的 碰撞检测时间变化率,RAPID算法在场景二中的碰撞检测时间变化率,结论算法特色,通用性 可处理任意形状的物体；,高效率 通过建构结点为凸体的层次二叉树以及采用基于三角形带的绘制加速技术，有效提高了算法的效率；,平稳性 继承了基于图像碰撞检测算法的优点，对同一复杂度的场景而言，碰撞检测时间变化不大，具有较高的平稳性，有利于预测碰撞检测过程；,可发展性 由于充分利用了图形硬件，解放了CPU，相信随着图形硬件的高速发展，算法将有更好的发展前景。,结论,今后的工作 利用硬件加速，只要几何裁剪无需光栅绘制 将层次背面剔除技术应用到碰撞检测算法中 自适应系统框架，能自动最优化平衡CPU和GPU的负载 利用多图形通道多CPU提高效率,谢谢！,
