3D碰撞检测

第13章求交测试方法金小刚Email:[e-mail]浙江大学CAD&CG国家重点实验室紫金港校区信息与控制大楼506图形学中经常需要进行求交测试…„用鼠标单击屏幕上的物体进行物体拾取„判断两个物体是否相碰撞„光线跟踪绘制中光线与物体的求交„。。。„一般来说，求交测试属于图形流水线中的应用层。OpenGL提供的拾取方法„将所有的物体绘制到一个比较小的拾取窗口，所有覆盖在该窗口上的物体都会返回一个表，同时附有每个物体的最大和最小z深度值。„优点：不仅可以拾取面，而且可以拾取线和点。求交测试vsOpenGL提供的拾取„但求交测试具有一些OpenGL拾取方法不具有的优点。„CaseStudy：判断一条光线是否穿过一个三角形？„OpenGL拾取：首先需要用拾取窗口对该三角形进行裁剪，再判断是否选中该三角形。„求交测试：直接进行光线与三角形之间的求交测试要比OpenGL快得多，而且可以计算出交点位置、法向、纹理坐标等数据。独立于具体的API。视域四棱锥裁剪(ViewFrustumCulling)„是一种将视域四棱锥外的物体进行快速剔除的方法。„用于判断一个包围盒„是否完全在视域四棱锥内„是否完全在视域四棱锥外„部分在在视域四棱锥内基于层次包围盒的拾取方法„拾取问题可以采用层次包围盒来解决。„首先，计算出视点到用户拾取象素位置之间的光线。„然后，用递归方法测试这条光线是否与场景图中的包围盒相交。如果光线与某个包围盒无交，则可以忽略该包围盒所在的子树。否则，继续对该包围盒的子包围盒进行上述测试，直到包含几何体的叶子节点。„最后，将光线与叶子节点包含的所有图元进行求交测试。碰撞检测算法中的图元„碰撞检测算法通常建立在层次结构上，涉及判断两个图元是否发生碰撞。„图元类型：„三角形„球体„轴对齐包围盒(Axis-AlignedBoundingBox，AABB)„有向包围盒(OrientedBoundingBox,OBB)„离散有向多面体(DiscreteOrientedPolytope，k-DOP)求交测试结果„A与B是否相交„A完全在B内（或者B完全在A内）„A与B完全分离„A与B相交„相交信息„精确的相交位置„与相交位置点的距离„交点处的法向、纹理坐标等信息硬件加速拾取方法„Hanrahan和Haeberli提出的拾取方法„将每个多边形用一种唯一的颜色作为标识，然后把整个场景以没有光照的方式绘制到缓冲器。„形成的图象以离屏的方式进行存贮。当用户点击到一个象素时，通过颜色标识就可以很快地确定相应的多边形。„缺点：必须用一个单独的通道来绘制整个场景硬件加速拾取方法„借助颜色缓冲器找到点在三角形中的相对位置„把三角形三个顶点的颜色分别设为红(255,0,0)、绿(0,255,0)、篮(0,0,255)，用GouraudShading绘制每个三角形。„假设拾取的颜色象素为(23,192,40)，则红色顶点贡献了23/255，绿色顶点贡献了192/255，篮色顶点贡献了40/255（实际上这些值就是拾取点相对于三角形的面积坐标）。利用这些信息可以找到拾取点在三角形中的真实位置及(u,v)坐标。„类似，通过把三角形顶点法向的每个分量从[-1,1]变换到[0,1]，可把顶点法向变换为RGB颜色，利用GouraudShading绘制后，就可以从颜色缓冲器中读出任意点的法向。定义和工具一条射线及其参数：r(t)=o+td，其中o为原点，d是射线方向(归一化为单位矢量)，t为参数„射线及其参数表面的定义„隐式表面„例子:中心在原点,半径为r的球„显式表面„三角形▲v0v1v2表示为显示形式02222=−++rpppzyx210)1(),(vvvtvuvuvu++−−=0),,()(==zyxpppffPAABB包围盒的定义„轴对齐包围盒(Axis-AlignedBoundingBox,AABB)„是一个表面法向与坐标轴方向一致的长方体。„可以用两个顶点amin和amax来表示物体A的AABB，其中aiminaimax,i∈{x,y,z}OBB包围盒的定义„有向包围盒(OrientedBoundingBox,OBB)„是一个表面法向两两垂直的长方体。是一个可以任意旋转的AABB„可以用它的中心点bc、三个归一化向量bu、bv、bw以及半边长huB、hvB、hwB来描述。离散有向多面体k-DOP的定义„由k/2(k是偶数)个归一化法向ni来定义(1≤i≤k/2)，每个ni有两个相关标量值dimin和dimax，其中dimindimax。每个三元组(ni,dimin,dimax)描述一个平板层Si，表示两个平面之间的空间。这两个平面是ni.x+dimin=0和ni.x+dimax=0。所有平板层的交集为k-DOP的实际空间。一个茶杯的二维8-DOP示例，包括所有法向和零号平板。分离轴定理(SeparatingAxisTheorem,SAT)„对于任意两个互相分离的凸多面体A和B来说，存在一条分离轴，其中这两个多面体在这条轴上具有一定间隔而且在轴上的投影也是互相分开的。这条轴正交于下列其一(也就是由一个平面分开，该平面平行于下列其中一个平面)：„A的一个面„B的一个面„多面体的一条边分离平面分离轴AB注：这里指的广义上的凸多面体(包括线段和三角形等)„相交测试的优化方法„排除检测：通过在早期进行一些简单的计算来判断射线或物体是否与其它物体完全分开„投影：将三维物体投影到最优的一个正交平面上(xy,xz或yz)，然后在二维平面上进行处理。„ɛ问题„由于计算精度问题，相交测试常常会用到非常小的数字，用ɛ来表示。„选择ɛ的值：具体问题具体分析。包围盒的创建„给定一组物体，选择合适的包围盒非常重要，因为可以将相交测试的代价最小化。„任意一条射线与凸体相交的概率与该物体的表面积大小成正比。因为排除过程通常比直接计算射线与物体的交点要快，所以将表面积最小化可以有效提高相交算法的效率。„在碰撞检测算法中，最好将包围体的体积最小化。AABB与k-DOP的创建„AABB的创建„沿每条轴线方向分别取给定多边形组中顶点的最大值和最小值，就可得到AABB。„k-DOP的创建„将顶点投影到k-DOP的每条法线方向ni上，然后将投影的极大值和极小值分别保存在dimin和dimax中，这两个值定义了该方向上最紧密的平板层。所有这些值共同定义了一个最小的k-DOP。包围球体的创建„算法很多，取决于速度和质量之间的折中。„恒时单遍算法(ConstantTimeSinglePass)„先为多边形组构建一个AABB，然后用该AABB的中心和对角线来构造球体包围体。„改进：从AABB的中心出发，将它作为球体包围盒的中心，然后再次遍历所有的顶点，找到距离最远的顶点，最后将最远距离最为球的新半径。„Ritter的近似最优包围盒方法：先找到x、y、z轴线上最远和最近的顶点，然后从这三组顶点中找出距离最大的一组顶点，取这组的中心为球心，取它们之间距离的一半为半径。然后，遍历其它顶点，计算顶点到球心之间的距离d，如果这个顶点在球体半径r以外，则将球心朝着这个顶点方向移动(d-r)/2，同时将半径大小修正为(d＋r)/2。重复上述过程，直到把不在这个球体内的顶点和旧的球体全部包含在新的球体内。包围球体的创建„Welzl的方法：找到一组定义球体的支撑点，当发现一个顶点在当前球体的外面时，将这个顶点位置添加到支撑点集合中（同时删除旧的支撑点），计算新的球体。再次遍历随机分布的顶点列表，直到球体包含所有的顶点。该算法的复杂度对于一组随机分布的顶点来说是线性的，并能保证生成一个最优的包围球体。OBB的创建„Gottschalk方法：„思想：首先从物体的凸包计算出一个方向，然后找到紧密贴合物体的OBB。„凸包计算方法：QuickHull方法。计算复杂度为O(nlogn)。„方向计算方法：计算凸包的协方差矩阵，求其特征向量并将其归一化就是所球包围盒的方向向量。„OBB的中心和半边长计算方法：将凸包上的点投影到方向向量上，并求每个方向上的最大值和最小值。每个方向最大值和最小值的平均值决定了该方向的中心，最大值减去最小值的一半为该方向的半边长。OBB的创建„Eberly的方法：„原理：利用最小化技术来计算体积最小的OBB。是一种迭代方法，其收敛速度取决于长方体的初始估计。„优点：不需要凸包计算。„设已经有一个估计的长方体，三条轴线分别为au,av,aw,将所有点在这三条轴线上进行投影，可以找出au方向上的最小值kumin和最大值kumax。同样可以找出kvmin和kvmax、kwmin和kwmax。利用这些值计算长方体的中心：长方体的半边长可表示为:hl=(kumin+kumax)/2,l∈{u,v,w}。再迭代。„初始长方体的计算：对所有可能的方向进行采样，选择长方体最小的一组轴线最为迭代计算的初始值。=求交测试的重要规则„这些规则可以使得相交测试更快速、稳定、精确。„尽可能利用简单的比较和计算来排除或确认各种相交类型，从而避免进一步的计算。„尽可能充分利用上次的测试结果。„如果使用了多种排除或确认测试，试着改变它们之间的内部顺序，这有可能产生一个更有效的测试结果。„尽量搁置开销量大的计算，如三角函数、平方根、除法等。„降低维数。（如把三维降为二维、二维降为一维）。„尽量找出在相交测试之前可预先完成的计算。„当相交测试比较复杂时，尽量先利用物体的包围球进行初步排除。„上机实践进行计时比较，计时要采用真实的数据和测试环境。„尽量使程序具有比较好的鲁棒性。能处理各种特殊情况，对浮点精度误差不敏感。射线/球体相交测试„数学方法„把射线的参数方程代入球体的隐式方程，得到一个一元二次方程，利用方程的判别式进行无根判别和根的计算。没有交点两个交点一个交点射线/球体相交测试„优化方法„不需要对射线原点o后的相交进行计算。„计算射线原点o到球体中心的向量l=c-o，其平方长度为l2＝l.l。如果l2r2，则说明射线原点位于球体内部（见上图右），从而可以肯定这条射线肯定与球体相交。如果只需知道它们之间是否会相交，则结束，否则继续。„计算l在射线方向的投影：s=l.d。如果s0而且射线原点位于球体之外，则球体位于射线原点的后面，没有交点。(见上图中)„利用勾股定理计算球心与投影点之间的平方距离：m2=l2-s2。如果m2r2,则射线与球体无交，否则肯定有交点。射线/长方体相交测试„平板层相交法„可以处理AABB、OBB、K-DOP等情况„Woo算法„只能处理AABB。但在某些体系结构下可以计算得更快一些。„线段/长方体重叠检测法„基于分离轴定理，只能处理线段与AABB之间的相交问题。平板层相交法„将长方体看成3个平板层。计算射线与平板层的交点。对于每个平板层，存在一个最小的t值和最大的t值，分别记做timin和timax，i∈{u,v,w}，计算tmin＝max(tumin,tvmin,twmin)tmax＝min(tumax,tvmax,twmax)然后就可以进行巧妙测试：如果timin≤timax，射线与长方体相交，否则不相交。平板层(Slab)为两个相互平行的平面。二维情形相交不相交Woo算法„针对射线与AABB之间的相交检测，Woo提出了一些巧妙的优化方法。„基本思想：在组成AABB的6个平面中选出3个候选平面。对于每一对互相平行的平面来说，忽略其背向平面而不作进一步考虑。计算射线与候选平面的相交距离(t值)，其中的最大值就可能对应一个相交情形。如果找到潜在的相交情形(相交点位于AABB的相应面上)，再计算出实际的相交点。候选平面的方向朝前，用粗线条表示，与射线之间的交点用灰色表示。由于左边的相交点距离射线原点最远，因此将该点作为潜在相交点。线段/长方体重叠检测„利用分离轴定理判断一条线段是否与一个AABB彼此重叠。„线段与射线不同，其长度是有限的，设线段由一个中点c和一个半向量w定义。对线段和AABB进行平