实时碰撞检测技术研究.
均匀剖分、BSP树、k-d树和八叉树(Octree)等 [Samet 1989][Naylor 1990][Bourma 1991]
层次包围体树法(hierarchical bounding volume trees)
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法
采用空间结构的碰撞检测算法
博士学位论文答辨
实时碰撞检测技术研究
答辨人 范昭炜 指导教师 高曙明 研究员
万华根 副研究员
浙江大学CAD&CG国家重点实验室 浙江大学计算机科学与技术学院 二〇〇三年十一月二十六日
主要内容
绪论 基于图象的快速碰撞检测算法 基于流的实时碰撞检测算法 并行碰撞检测算法 总结与展望
第一部分 绪论
层次包围体树法,包围体类型的不同来加以区分
层次包围球树[Hubbard 1993][Hubbard 1995][Palmer 1995][O’Sullivan 1999]、
AABB层次树(Aligned Axis Bounding Box)[Zachmann 1997][Bergen 1997][Larsson 2001]、
研究背景和研究意义
碰撞检测问题
是机器人、动画仿真、虚拟现实等领域不可回避的 问题之一
基本任务
确定两个或多个物体彼此之间是否发生接触或穿透。
起源
早期在机器人路径规划、自动装配规划等领域中, 为检测机器人与场景中的物体或零件与零件之间是 否发生碰撞,产生了一系列碰撞检测算法。
研究背景和研究意义
OBB层次树(Oriented Bounding Box)[Gottschalk 1996] k-dop层次树(Discrete Orientation Polytope)
[Klosowski 1998][Zachmann 1998] QuOSPO 层次树(Quantized Orientation Slabs with
连续碰撞检测算法
连续的时间间隔内进行碰撞检测 计算速度还太慢 [Cameron 1990][Canny 1986][Redon
2001][Redon 2002a]
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法 基于图象空间的碰撞检测算法
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法
采用一般表示模型的碰撞检测算法
采用空间结构的碰撞检测算法
基于空间域的碰撞检测算法分类
ห้องสมุดไป่ตู้
基于物体空间的碰撞检测算法
采用一般表示模型的碰撞检测算法 多边形表示模型
多边形集合,结构化表示模型
非多边形表示模型
CSG表示模型,隐函数曲面,参数曲面,体表示模型
多边形表 示模型
几何模型
非多边形 表示模型
Primary Orientations) [He 1999] 凸块层次树[Ehmann 2001] 混合层次包围体树[Wan 2001]等等
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法
采用空间结构的碰撞检测算法
层次包围体树法,包围体类型的不同来加以区分
(a) 包围球 (b) AABB包围盒 (c)OBB包围盒 (d) 6-dop包围体 (e)凸包包围体 包围体二维示意图
基于物体空间的碰撞检测算法
采用一般表示模型的碰撞检测算法
面向CSG表示模型
[Zeiller 1993][Su 1996][Poutain 2001]
面向隐函数曲面表示
[Farouki 1989][Miller 1991][Shene 1991]
面向参数曲面表示
非均匀有理B样条曲线(NURBS) [Turnbull 1998]
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法 基于图象空间的碰撞检测算法
利用图形硬件 对物体的二维图象采样 相应的深度信息
基于空间域的碰撞检测算法分类
静止状态下进行碰撞检测 [Dobkin 1985][Agarwal 1991][Chazelle
1989]
离散碰撞检测算法
在每一时间的离散点上进行碰撞检测 是研究的重点和热点 [Lin 1998][Jiménez
2001]
基于时间域的碰撞检测算法分类
离散碰撞检测算法
存在问题
存在刺穿现象 遗漏应该发生的碰撞
多边形 集合
结构化表 示模型
CSG 表 示模型
隐函数 曲面
参数曲 面
体表示 模型
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法
采用一般表示模型的碰撞检测算法
面向多边形表示模型的碰撞检测算法
[Hubbard 1995][Gottschalk 1996] [Klosowski 1998][Zachmann 1998]
目前研究的意义
虚拟场景中的物体模型越来越复杂 在仿真中对实时性和真实性的要求越来越高 现有的碰撞检测算法无法满足要求
碰撞检测算法分类
从两个角度对碰撞检测算法进行分类
从时间域的角度来分 从空间域的角度来分
基于时间域的碰撞检测算法分类
分为静态、离散和连续的碰撞检测算法 静态碰撞检测算法
1998], [Ehmann 2000], [Ehmann 2001]
基于单纯形(Simplex)的碰撞检测算法
Gilbert、Johnson和Keerthi [Gilbert 1988][Gilbert 1990]提出的GJK算法
[Cameron 1997][Bergen 1999]
基于空间域的碰撞检测算法分类
面向凸体的碰撞检测算法
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法
面向凸体的碰撞检测算法
基于特征的碰撞检测算法
Lin-Canny的“最邻近特征算法”[Lin 1991, Lin1993] [Lin 1995], [Cohen 1995], [Chung 1996], [Mirtich
体表示模型
主要用于虚拟手术中可变形物体的碰撞检测 [Heidelb 2003][Boyles1999][魏迎梅 2001]
基于空间域的碰撞检测算法分类
基于物体空间的碰撞检测算法
采用一般表示模型的碰撞检测算法 采用空间结构的碰撞检测算法
空间剖分法(space decomposition)