我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:彩63彩票 > 多面体裁剪 >

碰撞检测理论与技术分析

归档日期:04-23       文本归类:多面体裁剪      文章编辑:爱尚语录

  (西北工业大学电子信息学院西安虚拟现实工程技术研究中心西安710072) (信息产业部第54所石家庄050081) 内容摘要:碰撞检测是虚拟物体之间交互作用的基础,是虚拟现实、计算机动画中的基本问 题.由于研究对象具有不同的性质特点,碰撞检测所采用的技术方法差异很大。本文从面模 型(包括刚性表面及柔性表面)和体模型几个方面综合归纳了各类研究中的典型算法和最新 研究成果。对最常见的刚性表面碰撞检测.按照参数表面和非参数表面两类模型.从精确的 碰撞检测算法、包围体技术到空间分解技术进行了详细的讨论。柔性表面模型和体模型的建 模及碰撞捡测技术是近+余年来发展起来的新兴研究热点.文中对它们的最新研究成果和典 型碰撞检测算法进行了总结。 关键词:碰撞检测包围体刚性表面模型柔性表面物体模型体模型 AnaIyses forthe Theory CoIIisionDetectionMill Q—chongyangHa0‘Ming’卸Ton—xibin Ga02 xianyongzhan91YbIlgiiall Huai (Elemnics&Infbrrn撕0ncouege of咄wcstem P0帆cchnicalUIliVers咄X.柚Tech.如ch. c朗terof咖aI ReaI吼710072xi,an) 邻4t}1ins石tute,M_mis乜y ofI心珊atl0Elal IIldu嘟‘050081sh玎iazll咖g) Abst晴ct:coIIisiondeIectionis廿leb船tc problem ofvi巾】al real崎as wellas computer枷mation, andme detec吐on印prches VeIydi】髓re址This p印erpres如15syst。micafl柚,ses f打lhe 血cory impl哪enttecluliqu瞄of collision d咖嘶0n.Th州gh synt}1etIcalind删0naIld exac石on of帅icalalgorntIrns,tlleme嘶and钯chn岣ues arediscussed accordir培t0 thethree kindsof objects:ri舀d su血ces,nexibles叫.aceswelI鹤volumetric objec拓,如d ttIc bounding Volume techniqu豁are a|sDdi5cussed th删ghly The paperprovjdcs a出eoreticalbasisforlhe smdy ofcomsion岫ec廿on. Key words:Collision de把c石on,Bounding voIl蛐e'Rjgid sum圮髂,FIc蚶blesum啪s, 、,01眦c证c obj哟 一219— 碰撞检测是虚拟现实中动态物体与静态物体之问或动态物体与动态物体之间交互作用 的基础,是虚拟现实、计算机动画中的一个基本问题。将模型间的这些碰撞准确地检测出来, 并进行正确的响应,对虚拟环境的逼真性有着至关重要的影响。 1.碰撞分类 所谓“碰撞”是指,两个以上的物体发生接触或冲突,即某时刻多个物体占有同样的空 间位置。人们对于碰撞检测已经从不同的方面进行了广泛的研究,由于研究客体牲质的不同. 所采用的方法也大相径庭.从总体上说,碰撞揎渊所研究的对象可分为二大类:基于表面建 模的物体(Sllf雠e_basedo埒ect)一面模型,及体视化对象(、锐mgh{cobjen)—体模型。 面模型是传统的面图形学研究的对象。根据这类模型的柔韧性和形变特性.碰撞问题可 归纳为两类:刚性表面(1tig试柏ce)碰撞和柔性表面(Fl嘲ble翮由)碰撞。柔性表面 碰撞是指有布织物一类的柔软而有弹性的物体参与的碰撞.这类物体发生碰撞后其外表形状 必然会发生较大的变化。刚性表面碰撞又可分为二类,一种是由体素构造法(con曲m甜vesolid geon}e灯y,csG)或多边形网格生成的非参数曲面模型,另一类是由参数曲面生成的模型。 这两类物体从宏观上讲,不会因为碰撞引起形变,但参数曲面模型有时会由于其自身固有属 性的原因,随时间发生形状的改变. 体模型是体图形学研究的类型。相对于面模型而言,体模型是一种新的三维模型描述方 式,目前这方面的研究还大量集中在建模方法上,有关体模型的碰撞问题仅有少量研究。 综上所述,根据碰撞的不同类型,碰撞检测理论及技术分类如图i所示。下面分别从刚 性表面、柔性表面和体模型三个方面分别讨论碰撞检测问题.综合归纳各类研究中的典型算 法和最新研究成果,对碰撞检测的理论及技术进行系统的分析和讨论. 图l碰擅检测理论及技术分类 2.刚性表面碰撞检测 2.1非参数表面模型碰撞检测技术 (1)基本碰撞检测方法 基本的碰撞检测方法通过跟踪每对物体的位置关系来实现。从距离方面考虑,需要求出 一对物体间的距离函数.当两个物体远离时,函数返回两个物体最近点间的距离;当两个物 一220_~ 体发生接触时,返回零值。这个函数通常依赖于两个物体的位置和形状.对复杂一些的物体, 距离函数一般比较难求,因此用易于计算距离的简单边界近似代替物体的精确边界,可以大 大提高距离计算的效率. 在此基础上的改进方法,是速度一距离边界条件法(vekily_dignmbound me山od)【“。 用构成物体点集中的最大速度和最小距离确定某个碰撞发生的最早时间kb,在这个时间之 前钧体不会发生碰撞.这时可吐确定一个适当的时间间隔t,当时问超过l_后, t逐渐减 小,直到两个物体之问的距离小于一个规定的阚值为止,此时认为两个物体发生了碰撞.如 果需要,可I;I进~步进行精确的碰撞检测. (2)凸面体的精确碰撞判断 由于凹面体总可以分解成多个凸面体的集合,所以不妨假设两个多面体都是凸面体。将 二雏的cym.Bock裁剪算法推广到三维情况,即为凸面体精确碰撞检测算{去闭.基本思想是 检测构成一个多面体的所有点是否在其它多面体内部.利用这个算法对组成两个物体的所有 多面体对进行测试,即可检测到碰撞.对于n个多面体、每个多面体有m个顶点的情况,算 法的时间复杂度为D(fn产)。 此外对光掘图形设备,当有图形硬件机翻(如光线投射引擎,R丑ystingetI啦)支持 标准功能函数的计算时,还可以用基于深度缓存(二bu日妇)或光线跟踪(R町蛔cing)的方 法进行碰撞检测Ijl.这类方法在高级图形工作站上很容易实现。 (3)非参数曲面模型包围体技术 任何碰撞检据系统的设计都要涉及到两个基本问题.即效率和准确性。如果在碰撞检测 时.将两个模型的所有特征都进行比较,计算开销非常大,通常都采用各种技巧,尽可能地 避免这类计算,从而达到对算法加速的目的。加快碰撞检测的主要策略是利用开销不大的检 测,去尽可能地捧除那些没有发生碰撞的情况,如采用包围体的方法。 典型的包围体(Bound崦vo|me)有包围盒(Bodingb%)和包围球(Boundjngsphefe) 两种.它们是包围虚拟物体的最小长方体或外接球。包围盒又有不同的形式,如轴平行包围 盒(AxiS-ali掣Ied洲iIlgbox,AABB)、有向包围盒(Orien々ed’boundhlgb0)('oBB)等。轴 平行包围盒的各个面分别与坐标系的各个轴平行,而有向包围盒的轴向根据模型的形状而 定,可以在三维空问中的任何方向上。 包围体仅仅是物体边界的一个简单粗略的表示,当两个物体的包围体相交时,并不能确 定两个物体一定发生了碰撞.这时还需要进行进一步的精确检铡。尽管如此,由于利用包围 体进行碰撞检测可以快速有效地判断出两个物体不相交的情况,排除了大量不必要的精确检 测计算,因此大大加快了碰撞检测的速度。 在这几种包围体中,轴平行包围盒和包围球在检测重叠的存在性方面非常高效.但是这 两类包围体不能紧贴地包围一些细长的或任意方向的多边形.有向包围盒可以以最好的紧包 围形式包围所有类型的模型,但是它们之间重叠检铡的计算开销相对较大,速度比上述两种 包围体慢得多.因此.通常在选择时需要权衡。 (41空间分解技术 当两个物体距离较远时,包围体的“排斥检测”效率根高,一旦两个物体靠近后,耳前 较好的方法是采用基于细分的空间分解技术解决碰撞检测问题【4】。空间分解技术广泛采用分 级的层次数据结构(Hierarchjcaldata蜘nlre),分级碰撞检涌的实质是构造一个包围体树, 用来尽可能紧地包围原始物体。这样从树的最高级开始.用递归算法进行碰撞检测,只有在 当前级检测到两个包围体相交时,算法才进行到更低一级的层次上。所以通过排除那些不可 能接触的区域,大量的计算时间就可毗节省下来。 但是当两个物体有多个接触区时.算法仍要对数量巨大的包围体进行检测。在这种情况 下,计算开销增大,而且需要更多的存贮空问,性能也随之大幅度降低.成为仿真模拟中的 一个主要瓶颈。 2.2参数表面模型碰撞检测技术 在参数表面模型的碰撞检测问题中,参数模型为静态的情况有少量研究,以时闻为函数 进行运动或变形的参数表面的碰撞检测于1990年由Brian von H首次提出口】。 (1)基本碰撞检测方法 参数表面可以看作是三个参数变量的向量函数瓜叶,吁,f)和甙崦,唯,,).其中蜥和vJ是张成 血面的参数变量,f为时间,碰撞检澜即是找出最早接触时间k。。当满足 ll,恤r,Vr,,。。J—gk,Vg,fM州<, 时,称为发生了y一碰撞。这个方程给出的是一个复杂的、非线性、五维的基本检测方法。当,值较大时,可以进行粗糙近似的碰撞检测,报快得出结论。当,减小时,计算量增加,速 度减慢。在此基础上,利用包围体技术可以大大提高碰撞检测的速度。 r2)基于Llpsch池条件的包围球 给定一个连续的参数表面贝H),在,值域的某个区域R内,存在一个有界常数上.满足 公式(2)即为LipschI乜条件,它暗示了函数瓜)是否存在有界的偏导数上。对于一些不可微的曲面,也有求Lipsch.乜值三的方法。Lipschi乜条件可以保证生成完全包围参数曲面的包围体 集。在碰撞测问题中,一个移动变化的参数曲面氕),鼍%v’玎是时间的函数,这时对参数 曲面的变化速度和其他参数导数而言,三是一个上界值。 当用Li口Sclli乜方程构造包围球时,模型空间中的包围球半径r由参数空间中区域的尺寸 大小和函数的Llpschi乜值确定,即由r£(一一f)确定,其中工满足 根据参数空间中区域的层次划分,包围球也可构成层次结构。每个参数子区域都有自己的包围球,随着细分的进行.包围球越来越小。 (31Jacobiall包围盒 L岫schi乜球做为包围件,有较多的冗余。对参数函数利用Lips凼乜条件的J0bi型矩 阵,可以生成参数函数的包围盒。这种包围盒比用标准的LipscIIi乜条件生成的包围球有更好 的紧包围效果,可咀减小包围体的尺寸,相应地就减少了碰撞检测计算的平均次数,提高了 算祛效率。 假设某个参数子区域R:m“啦,vlv,“f如,R中心点的参数坐标为 %鼍酶.嵋.,模型空问的坐标为巾U屯拙.磊)‘,则可以生成一个与x,y,z轴平行的矩形 体,将此矩形体定义为包围盒,各方向上的半径定义为: 缸{M。幽jrM。抽+Mt出其中jlf为比倒矩阵: 这个矩阵包括了向量函数,所有分量的参数导数的上界值。这是运动的参数曲面之间计算碰撞的一个根有效的包围盒,与方程(2)相比通常会产生更好的紧包围效果。 3.柔性表面的碰撞检测 柔软性物体的运动是带有变形现象的复杂运动,受许多弯曲和碰撞控制,典型代表就是 布类织物.这类模型的碰撞检测主要用来阻止织物穿入与其接触的对象和阻止其不同部分发 生自碰撞。通常用安捧在矩形栅格上的三维空间点表示织物的二维拓扑网状结构。 目前已有的布类仿真算法,按照其内部能量的定义方式可分为两大类。一类以变形模型 为基础,采用弹性理论构造一些微分方程,其中能量函数以连续的形式导出16】。另一类通过 真实布类织物的材料特性构成能量函数,以势能函数的形式对经纬线之间的相互关系提出约 束条件.动画过程中通过减小这些能量函数来模拟布飘落和弯曲起皱的行为”】. 3.1光线线段检测法 首先将布织物模型中.每个结点在一个时间片内的起始位置和最终位置构成的线段定义 为光线线段(Ray唧ent).然后用光线跟踪中的交叉判断方法确定光线线段是否与其它物 体相交.如果某个结点在一个时间片内的光线线段与物体的任何几何面相交,这个时间片内 就可能发生碰撞。由于线段是结点实际所走曲线路径的近似表示.为了精确地确定发生碰撞 的交叉点。需要进行进一步的迭代。迭代过程中通过计算结点从光线线段的起始点运动到与 几何面的交叉点所需的时问,将对问步长逐渐减小.直到发现一十刚好落在光线线段端点上 的交点为止。此时发现一个精确的碰撞点,否则即可确定没有碰撞发生。 一223~ 如一甜如一m如一甜 这个方法可以用来计算布类模型与静止刚性障碍物之间的碰撞情况。3.2几何碰撞检测法 描述布类织物的基本形式是规则的栅格结点。很多情况下,用这些栅格结点再组成三角 形网格,以三角形网格的形式定义布类对象,此时碰撞就归结为两个三角形片的碰撞,碰撞 方式包括顶点,三角形型和边/边型两种基本碰撞形式18l,如图2所示。 图2两种基本碰撞形式(1)顶点,三角形型碰撞:指一个三角形的顶点与 另一个三角形发生接触,如图2(a)所示。在f时刻P点是否与三角形相碰.可以通过下式进行判定。 如果发生碰撞则满足: (2)边,边型碰撞:某三角形的一个边与另一个三角形的边发生接触。如图2(”所示。在f时刻如果两个边发生了碰撞.则下式成立: 这种方法需要对每个顶点,三角形对和每个边,垃对求解一个三次多项式方程。如果布类模型有n个结点,障碍物由m个三角形组成,那么需要0(1II】吣的时间来检测与障碍物的碰撞, 还需要0伽21的时间来检测布织物各部分之间的自碰撞。 几乎所有布类和静止非变形障碍物之间的碰撞,都可以通过检测顶点/三角形碰撞发现。 此外还有两种特殊情况,即两个三角形片形成锐角片对(Sharppatchpajr)或钝角片对的状 态。对于锐角片对必须进行一定处理,然后用边,边型碰撞检测方法判定。出现钝角片对时. 可以用薄的包围层围绕静态刚性物体表面的方式进行处理,以避免轻微穿入的发生。 为了加快布模型的碰撞检测,利用柔性模型发生碰撞的区域可以扩展蔓延的特点,根据 某些曲率准则,即可忽略掉大面积规则区域的布,布自碰撞检测,从而加快计算速度。 4.体模型的碰撞检测 体数据是对某种物理场或实际物体的离散采样。典型的体(Vbl岫e)是一个三维的、由 体的基本单元———体素(xeI)构成的立方体矩阵。每个体素在离散的栅元位置上定义一组 标量属性,插值函数用来定义栅元间的空间位置上标量的值.以便为每个属性产生一个连续 的标量场。由于体模型建模的基础是体栅元,而体栅元是以离散方式定义的.因此体模型之 间的碰撞检测与面模型之间的碰撞检测完全不同。 4.1简单的体对象碰撞检测法 Gibson于1995年提出了关于体模型之间碰撞检测的第一个算法,算法中采用了多个体. 一个体表示一个物体。首先根据整个虚拟空间体积的大小构造一个位置映射图(occupancey ma口),映射图的每个单元包含~个空指针或一个体素的地址指针。当某个对象体素的地址指 针被写入映射图的某个单元,而这一单元已经被另一对象体素的地址指针占据时,算法认为 检测到一次碰撞。这个方法实质上等价于将体素的坐标值变换到其它体的坐标系中,来完成 ~224— 碰撞检测。假如体的分辨率为o(N3),则这种方法的时间复杂度为D(N3)。如果体的分辨很大, 则碰撞检测的时间就会急速增加。算法速度较慢。 Avila等人于1996年提出了一个体视化中的触觉交互作用(Ha州cifIIcrw60n)模型【”。 同样是利用位置映射图,从局部的密度、梯度等体属性中产生一个触觉力反馈,研究的重点 是基于点的虚拟设备和体模型的交互作用和快速绘制。 4.2基于概率模型的碰擅检测算法 算法基于这样一个思想:首先,由于通常的“碰撞”概念只适用于有良好表面定义的实 体模型,所以体模型的碰撞需要重新定义。另一方面,体描述法包含了物体内部结构等更多 的信息,因此应该提出一个关于体结构对象之间相互作用的更详细的描述。在这一思想指导 下,】997年出现了黄于体模型碰撞描述的概率模型110l。 (1)基于概率模型的碰撞概念 从理论上讲,由于离散描述的限制,体模型没有一个定义完好的表面.描述任何相互作 用的精确程度完全决取子体分辩率。因此自然地可以认为,体模型之间的相互作用不是一个 碰或未碰的二值过程,相反地可以用一个非确定性的过程来描述它。由此对每个空间点给出 碰撞“概率”,用来表示不同成分物体之问的相互作用特性。 这里虽然引用了面模型中的。碰撞”和“碰撞检测”术语,但是研究的重点是交叉区域 中表现出的不同交互作用属性。侧如对于面模型.当一个小球从空中落向地面时,碰撞检测 可以报告“是否、何时、在哪”小球碰到了地面。当射线束照射由CT采样数据集构造的体 对象—cT-头时,可以用体碰撞的概率模型报告出光束当前接触区的材料特性,如骨骼、软 组织或两者兼而有之等。 (2)碰撞的概率模型 在这个模型中,体中的每个点被赋予【0,l】间的一个值,这个值从概念上可以理解成: 存在一个通过该点的“表面”的概率。这个“表面”不需要任何几何或物理上的含义.是一 个抽象的概念,用于描述物体的所有属性。面经过点的概率是一个与体素有关的值,如密度、 硬度或吸引/排斥系数等。 对每个物体建立这样一个概率模型后.某点上两个物体的碰撞概率定义为:两个物体在 该点的面相交的概率。根据概率论理论,“碰撞概率”等于两个物体上各自通过该点的表面 的存在概率之积。此外,由于面存在概率可以是物体任何属性的抽象,因此也可以有其它碰 撞概率的计算方法,如加法等。概率模型的实质是首先定义一个从物体属性到面存在概率的 映射图.然后再定义一个从不同物体的面存在概率到碰撞概率的映射图.由这两个过程完成 碰撞检测任务。这个算法吸收了体描述法的一个突出优点——具有支持由不同内部成分构成 的复杂模型的能力。 5总结 碰撞检测是虚拟物体之间交互作用的基础.是虚拟现实、计算机动画中的基本问题。由 }研究对象具有不同的性质特点.碰撞检测所采用的技术方法差异很大。本章根据研究客体 一225— 的不同,将碰撞检测理论和技术划分为三大类:刚性表面的碰撞检测、柔性表面的碰撞检涌 以及体模型的碰撞检铡。综合归纳了各类研究中的典型算法和最新研究成果.进行了系统的 分析和讨论。 刖性表面碰撞是现实世界中存在最多的一种形式,文章按照参数和非参数两类刚性表面 模型,对待确的碰撞检测算法、各类包围体技术以及基于分级树型层次结构的空间分解技术 进行了详细的讨论。柔性表面模型和体模型的建模方法和碰撞检测技术是近十余年来发展起 来的新兴研究热点.文中对它们的最新研究成果和典型碰撞检测算法进行了总结. 参考文献 皿kcuIly如dK.G.K蛐pf.A儿磷detc删蚰咄r0删珊bascd如删1)r鼬ddis妯ceb0岫ds.Pro训iflgs 0f删阻Intc删村alc0砌黼锄删cs蛆dA珊咖甜叩, 】986, pp.106和1069. M删heMM00andJamwimclms.(bn商帆de蜊如andrespome fw complner 咖I炯。GfaphIcs-v01.23,.4- 1988,p啦89五粥. 酬My毫吐。螨ld甜以.Fastc0慨id鲫砌锄be咖蜘啪pl麟Iidsming删i吲西llg印IpIIihafdwafc.11leviSualCotnl砌cer(1995)11.497h511. S.G删甑|haIk“a,.oBBme:ahi%|Ic蚵caI蛐I眦um细唧id砷6erfbnce det。cton.Proc. SIGGRAPH’96,pp.17弘173. Bri卸、bnHe舢 Ge删me矾ccoll.siom蠡t.皿e-d印endem sI】时缸es.CompIIIerGraphjcs,v01.24,No.4,1990,坤.39—48.6.De眦州Te脚pouIos“口f..E埘砌Iy de向吼曲Ie models.咖uterG哪ics,1987. J.2I-N0.4,pp.20”14. D撕dE.Brcenef以.Aphysjy‘basedpanicIc madelofwaV锄cloth.n把visIl_al complIc盯 (19912)8:264^丑77. J朋.DLiu盯df.C011ision卯Oid蚰ce.mcIalh蛆.蛐嘶蛐.1'tIe visual ComDuter (1996)12:234~243. 9.砌cardoS.Av订a柚d“sa M.Sobic删s-d.Ahap缸int啪c曲n me血0d如rvol哪e visualiz撕on.Proc.Vi鲫ali豫曲n,96,即.197也04. 10. 伽ng Heand A弛m劬锄.coIIisidete‘:tion缸‘v01岫etric 0bjects.PToc. visu出i益虹On’97.pp.27—34. 个人信息: 西安市西北工业大学.博士生,讲师.西安市西北工业大学电子信息学院电子工程系 710072 (029)8495899(o) (029)8491772(H) 一226—

本文链接:http://ashtonstewart.net/duomianticaijian/9.html

上一篇:没有了

下一篇:模型设计与制作课程总结