1.一种基于空间细分与动态包围盒的连续碰撞检测方法,其特征是按以下步骤:步骤1:构造被用于碰撞检测的虚拟软组织模型与虚拟器械模型;
步骤2:计算检测对象的移动路径所占据的空间,若待检测对象的移动路径共用同一个空间,则执行下一步,否则退出检测;
步骤3:为同一空间内的对象的移动路径构建动态包围盒,并对这些包围盒做相交测试;若相交,则执行下一步,否则退出检测;
步骤4:二分法确定可能发生碰撞的位置,回溯技术将待测对象从实际位置回退至初次碰撞发生位置;
步骤5:为可能发生接触的对象集构建层次包围盒并执行包围盒相交检测;若检测到子节点包围盒相交,则执行下一步,否则退出检测;
步骤6:精确检测步骤5中的子节点所包含的特征是否碰撞;若检测到发生碰撞,则重新计算待测对象的位置;否则待测对象位置不变;
所述的步骤2中,首先,将离散的时间间隔内的物体运动轨迹视为匀速直线运动,并计算运动轨迹所占据的子空间;再利用哈希函数对扫掠体的空间网格进行压缩,使三维的体积空间被映射到一维的哈希值索引;具体过程为:(1)预处理各个子空间的尺寸为D,并将空间各个顶点的位置离散化为(x,y,z);将顶点的坐标除以给定的单元格大小,并四舍五入到下一个整数坐标(i,j,k);其中,i=[x/D],j=[y/D],k=[z/D];接着,三维的顶点整数坐标(i,j,k)被映射到一维的哈希值H索引,哈希值通过哈希函数获取,即:hash(i,j,k)=(i·p1xor j·p2xor k·p3)modN其中,p1,p2,p3代表三个足够大的质数以确保每个索引的哈希值唯一,N是哈希列表的长度;
(2)计算扫掠体的哈希值:首先,计算三角面扫掠体的最大哈希值和最小哈希值,将顶点的最大坐标和最小坐标设为(xmax,ymax,zmax),(xmin,ymin,zmin),并通过最大坐标点和最小坐标点得到扫掠体的子空间最大索引值和最小索引值(imax,jmax,kmax),(imin,jmin,kmin);根据索引值进一步计算最大哈希值和最小哈希值hash(imax,jmax,kmax),hash(imax,jmax,kmax);
并计算出扫掠体的哈希表索引范围:[Hashmin,Hashmax];若不同三角面的扫掠体的索引范围存在交叠,那么这些三角面都被标记为可能发生接触的,并被用于后续检测;
所述的步骤3的具体步骤如下:
(1)选择有向包围盒;
(2)扫掠体包围盒的连续相交检测;由于连续检测的需求,必须确定扫掠体的有向包围盒是否重叠,再利用二分回溯法确定碰撞发生的精确位置;对包围盒进行分离轴测试;分别定义两个包围盒的轴中心,中心距各轴距离分别为a1,a2,a3,Ta,e1,e2,e3和b1,b2,b3,Tb,f1,f2,f3;当两个包围盒到各轴的投影均不重叠时,可以判断包围盒不相交;即满足:轴k可由包围盒的各轴推导而得:
k∈{ai,bj,ai×bj,1≤i≤3,1≤j≤3}
所述的步骤4中,若包围盒在时间间隔内未检测到分离轴则进行细分检测;细分测试进一步细化时间间隔,直到时间间隔的长度满足要求的精度为止,精度的设定与系统的精确性,物体表面厚度和物体移动速度有关;对一段给定的时间步长[0,t]和轨迹γA,γB,确定了最短时间子区间[k·(t/2)^n,(k+1)·(t/2)^n];其中n表示细分程度,k表示细化时间间隔的索引;碰撞发生的时间可近似为k·(t/2)^n;
所述的步骤6中,在经过上述步骤后将筛选出可能发生接触的三角面及接触位置、接触时间;最后,详细检测这些基本图元的接触情况;具体步骤如下:(1)确定两三角面所在平面是否相交;定义ΔB1B2B3各点到ΔA1A2A3所在平面的距离矢量为 其中:如果三个距离矢量的符号相同,则不会发生接触;这是因为 符号相同时表示ΔB1B2B3各点在ΔA1A2A3所在平面同侧,则必不可能接触;类似地,可以判断ΔA1A2A3各点在ΔB1B2B3所在平面的相交情况;
(2)计算两条相交线是否重叠;定义 为ΔB1B2B3与ΔA1A2A3所在平面的相交线;点C坐标为:其中,
上下同乘以
同理,也可以求出交点D,E,F的坐标;又由于 必然共线,要判断相交,只需判断C是否在E,F两侧;即 当判定 与 相交时,即确定ΔB1B2B3与ΔA1A2A3接触。
2.根据权利要求1所述的一种基于空间细分与动态包围盒的连续碰撞检测方法,其特征是,所述的步骤1的建模过程,利用三维建模软件构建待测的虚拟软组织模型与虚拟器械模型;模型均由具有一定厚度的三角面网格构成,在表面三角形网格上进行碰撞检测。