面向虚拟装配的碰撞检测技术研究

面向虚拟装配的碰撞检测技术研究

谢󰀁健,闫󰀁静,焦光明,左敦稳,周华林,杨发春(1.南京航空航天大学机电学院,江苏南京󰀁210016)(2.南京晨光集团有限责任公司,江苏南京󰀁210006)

摘要:碰撞检测是虚拟装配过程中的重要环节,其执行效率直接影响到装配仿真的真实感,现从3个层次对此问题展开了论述:通过扫描剪枝与装配关系相结合的方法得到包围盒相交的零件对;利用时空连续性减少包围盒的相交次数,加快了两零件之间的检测;提出了由于模型的近似表达而造成的虚假碰撞的排除方法。

关键词:碰撞检测;虚拟装配;时空连续性

中图分类号:TP391.9󰀁󰀁󰀁文献标识码:A󰀁󰀁󰀁文章编号:1672-1616(2008)21-0029-04󰀁󰀁在三维计算机图形学中,面片造型是一种用许多相连的多边形面片来表达模型表面的造型方法。虽然精度较低,但由于其简单、通用性好,且得到大部分硬件加速渲染支持,因而是一种很常用的模型表达方式。基于虚拟现实的虚拟装配环境要求实时动态显示,一般使用面片模型。

在装配仿真过程中,模型之间在空间上不应有交集(即干涉),碰撞检测最基本的目的就是要适时地找出是否有面片相交,然后阻止干涉的发生。这通常是一个非常耗时的环节,直接影响到仿真的真实感。

事实上,碰撞检测在计算机仿真领域有着广泛的应用。对于面片模型,层次包围盒法是一种常用的检测方法。它首先为模型建立包围盒树,然后双向遍历进行包围盒的相交检测,以减少后续的面片相交检测数目,从而达到减少检测时间的目的。典型的包围盒有AABB(axis-alignedboundingbox)、OBB(orientedboundingbox)、sphere和k-DOP(k-directiondiscreteorientationpoly󰀁tope)[4]等,由于各种包围盒有各自的优缺点,所以也有多种混合使用的[5]。本文讨论的就是基于包围盒的碰撞检测方法。

[1]

[2]

[3]

1

1

2

1

2

2

但其形状复杂,面片数量巨大,检测精度要求高,因此同样对系统的碰撞检测效率提出了很高的要求。另外,同一个装配体内的零件之间非常靠近,若进行检测会非常耗时,而对于占很大比重的刚性体来说,由于相对位置固定,它们之间是根本不会发生干涉的。再者,面片化的表达方式使得曲面的表达不再精确,当2个具有相同公称尺寸的曲面(最典型的是轴孔)配合时,便会产生虚假的干涉,妨碍了装配的顺利进行。针对以上问题,本文提出了面向虚拟装配的碰撞检测方法。

2󰀁碰撞检测的基本步骤

虚拟现实系统是通过不断刷新画面来实现动画效果的,每个画面为一帧。每帧中系统根据传感器的输入调整运动物体的位姿,然后对这一特定的场景进行碰撞检测,随后根据检测结果触发对应的响应。为了减少检测时间并保证特定装配环节的顺利进行,本文将整个碰撞检测过程依次分为3部分:筛选出可能发生干涉的零件对、每对零件的面片级检测和排除精确模型面片化导致的装配时的虚假碰撞。

2.1󰀁可能碰撞零件对的选取

由于只有2个零件的包围盒相交才有必要进行进一步的检测,因此碰撞检测的第一步就是要找出所有这些零件对。工业级的装配场景有时含有成千上万的零件,若直接对每2个零件之间进行包围盒检测,则无法满足实时性要求。针对这一问

1󰀁虚拟装配中的碰撞检测

虚拟装配中的碰撞检测有其特殊性。首先,物体运动的速度和面片数目是影响检测速度的两大因素,虽然虚拟装配环境中模型的运动速度较慢,

收入日期:2008-08-05

作者简介:谢󰀁健(1983-),男,江苏无锡人,南京航空航天大学硕士研究生,主要研究方向为虚拟装配。302008年11月󰀁中国制造业信息化󰀁第37卷󰀁第21期

也多与世界坐标方向相近,加之装配过程较少有大角度的姿态变化,所以模型在整个装配过程中基本保持包围盒体积较小的状态,相交的数目比使用固定尺寸包围盒时少很多。其次,充分利用AABB的几何特点,其更新的计算量仅相当于2个点的完整变换。如果只作平移,则只需一个点(包围盒中点)的完整变换,与固定尺寸立方体相同。

题,可使用扫描剪枝(sweepandprune)方法[6,7]。这是一种降维法,其原理基于以下事实:若2个AABB在3个坐标轴方向的投影均相交,则它们相交,反之亦成立。其中,模型的AABB为包含该模型且各面始终保持与给定坐标轴方向平行的最小正六面体,扫描剪枝法中给定坐标系指世界坐标系。将场景中的每个物体的轴向包围盒分别投影至3个坐标轴方向,就形成了与物体个数相同的3组区间。图1为二维情况下3个零件的AABB(图1中实线框)在X,Y2个坐标轴的投影区间,以[bnen]表示。将3个方向投影都相交的一对包围盒所对应的一对零件保存于零件对链表,作为下续检测的输入。扫描剪枝方法的优势就在于利用了虚拟场景的时空连续性:由于每一帧所耗费的时间很短,所以前后两帧各物体之间的空间关系只会产生很小的变化。当物体前后两帧的位姿发生变化时,其对应的投影区间长度及位置也发生相应的变化,变化过程中投影区间会相交与相离,我们只需关注这一区域的变化,而无需进行所有包围盒的相交检测。

图2󰀁3种AABB(二维)

每个装配体内部零件之间的碰撞检测可通过以下方式避免:为每个零件设定一个装配标识以指明所属装配体,当一个新的零件或子装配被加入另一个装配体时,新加入部分的所有零件的装配标识都被改写;当拆卸时,拆除部分的所有零件的装配标识都被改写。再考虑到一次装配操作一般只有一个零件或装配体处于运动状态,因此只需检测该运动物体与静止物体之间的碰撞。由此需要进入面片级检测的每2个零件满足条件:在零件对链表中,其中有且仅有一个零件的装配标识为活动装配体标识。除了通过设置装配标识来辨别零件所属的装配体外,还可以用更直接的方法,就是利用装配体本身的树结构。此时的AABB属于装配体或未装配的零件,检测到包围盒相交后需对这2个装

图1󰀁扫描剪枝算法示意图(二维)

配体树进行双向遍历检测,才能得到包围盒相交的零件对。这样做的优点是很自然地避免了同一装配体内零件间的检测;缺点是每次检测需要对两棵树重新遍历,降低了时空连续性的利用率,且该阶段的检测效率会受到树结构的影响。

模型位姿变化后需要更新包围盒。严格意义上AABB的更新需重新遍历模型的所有面片的顶点,当面片较多时比较耗时,不适用于大规模动态场景,如图2(a)所示。对于装配仿真,可使用2种简化包围盒。一种是固定尺寸立方体(图2(b)实线框),使得模型处于任意姿态时都能完全包裹。当大部分零件及装配体形状接近立方体或球体时,因简化引起的包围盒体积增量很小,同时仅需更新一个点(包围盒中心)的坐标就能实现包围盒的更新。另一种简化方式的包围盒是根据模型局部坐标下的AABB(图2(c)虚线框)求得的(图2(c)实线框),尽管其更新时间较图2(b)长,但对于零件多为长条和扁平状的装配场景,会是更好的选择。首先,因为CAD系统中沿轴向的建模方式使得模型在该姿态的AABB较紧密,模型最终的安装姿态2.2󰀁零件对的碰撞检测

此阶段进行每2个零件之间的检测,由于该检测需要精确到面片,所以计算量大,比较耗时。直接进行模型之间的面片两两相交检测效率太低,通常无法满足实际使用要求。如前所述,每个模型都对应于一棵层次包围盒树,而碰撞检测的过程首先是两棵树的双向遍历检测过程。若把每2个进行检测的包围盒作为一个节点,则整个双向遍历过程便又产生一棵碰撞检测树(如图3所示)。当层次包围盒树和双向遍历策略都确定,碰撞检测树也就确定了。于是,碰撞检测的过程可以看作碰撞检测󰀂现代设计与先进制造技术󰀂󰀁󰀁谢󰀁健󰀁闫󰀁静󰀁焦光明等󰀁面向虚拟装配的碰撞检测技 31树的前序遍历过程。在场景层,文献[8]通过记录上一时间点活动对象在环境对象树中的遍历结果作为当前时间点遍历起点来提高算法效率。由于同样是树的遍历,所以可以把这一方法拓展到面片层。

变化情况保持不变m下移一层m上移一层

所以很少出现以上情况。若只进行向下更新,虽然边界下移或保持不变时均能减少(n-1)次,但边界链表只会增长,当物体远离时的其计算量与最接近时相同。

表1󰀁2种节点遍历方法比较

边界遍历次数(至多)3n/23m+3(n-m)/2m/4+3n/2

完整遍历次数

2n-12n-1+2m2n-1-m

减少次数(至少)n/2-1(m+n)/2-1

5m/4-n/2-1图3󰀁碰撞检测数、检测边界及终止节点

以下讨论最常用的二叉树结构。当2个物体的层次包围盒树为二叉树时,碰撞检测树也为二叉树。由于每个分支向下遍历过程中遇到包围盒不相交或叶节点会终止,所以每次检测都会将树分成已遍历和未遍历两部分,于是形成一道边界(图3中的虚线),当两物体远离时,此边界向上移,靠近则向下移。由于时空连续,前后两次检测形成的边界位置仅有少量变化,没必要每次都从根节点开始检测,所以设想把上一次的终止节点(图3中灰色节点)保存到链表,作为下一次检测的起始位置。检测的同时需要更新边界,策略为:顺序访问边界链表中的每个节点,遇到相交节点,则按双向遍历规则向下递归更新(如果叶节点相交就进行面片的相交检测);当遇到相邻的2个不相交节点,且它们有共同的不相交的父节点,则父节点取代它们存入链表,即向上更新,然后往回遍历;当与链表中前一个节点(已更新)有相同且不相交的父节点时,则向上更新,然后继续往回,直至更新完毕,接着继续顺序遍历。令某一时刻边界之上的一层终止节点数为n,若下一时刻其中的m个节点位置发生变化,则从边界开始遍历和从根节点开始遍历2种方法的比较见表1。

对于移动多层的情况可考虑为单层情况的叠加。从表1中可以看出,当m>2n/5时,边界遍历有可能更耗时。不过,由于在虚拟装配环境中时空连续性较强,前后2个时刻边界变动比例很小,图4󰀁2个测试场景

󰀁󰀁如图4所示,我们分别从外部和内部这2种碰撞情形进行了测试:任意选取3组位姿,使其中一

个零件与另一个靠近,直至发生碰撞,然后按原轨迹返回。每次往返过程中边界遍历方式与完整遍历方式相比速度平均提升量见表2。从表2中可以看出,OBB并未通过此方法得到速度的提升,而对于AABB则能减少约30%的检测时间。该方法不适用于OBB的原因主要有2个:第一,由于OBB的祖先包围盒不能够完全包含子孙包围盒,因此当祖先包围盒事实上不相交时,子孙包围盒却可能检测出相交而无法及时向上更新,导致包围盒相交检测数目增加,这集中体现在返回阶段;第二,由于边界法并不从根节点重新遍历,因此OBB的姿态只能记录在模型局部坐标下的描述值,在相同条件下,相比于使用在父包围盒坐标中的描述方式,相交检测效率有所降低。

表2󰀁边界遍历较完整遍历速度提升比例

包围盒OBBAABB

a

b

6%34%

8%-13%-7%-5%-4%29%

26%

28%

27%

26%

󰀁󰀁测试表明,若以OBB姿态局部坐标描述方式的完整遍历检测时间作为参考,使用边界遍历时零件靠近阶段(此时第一点中提到的影响很小)同样能得到与AABB时相当的速度提升量。AABB的结构决定了没有包围盒的包含问题,因而没有更新

322008年11月󰀁中国制造业信息化󰀁第37卷󰀁第21期

c1为倒角外圆周的理论形状,c2的直径对应孔与销的直径。如果倒角宽度太窄或模型面片化的精度太低,柱销面D可能与活塞端面C发生干涉,而这本应当也在排除范围内。考虑到设计结构的多样性,对类似问题还未找到统一的解决方法。不过国家标准[9]对于倒角尺寸的推荐值中倒角宽度与直径之比均不小于1.5%,由此可算出当一个柱面被划分成13份以上便不会出现问题,这样的分割精度在实际应用中是基本满足的。对于极端情况可屏蔽干涉,仅依靠约束完成装配。

延迟;又由于同一棵包围盒树中包围盒姿态一致,因而不存在姿态描述的多样性。k-DOP与AABB有相同的特点,由此推测此法亦较为适用。Sphere也可能出现祖先包围盒不能完全包含子孙包围盒的情况,不过由于没有姿态信息,所以没有以何种方式描述的问题。

边界法需占用更多的内存,这对于以存储空间为优化目标的场合并不合适,而且由于依赖于时空连续性,当物体快速运动时无法体现出优势。

2.3󰀁虚假干涉的排除

不同于CAD系统的参数化表达方式,虚拟装配环境中的面片化表达使得孔的形状变为多边形,面积缩小,导致装配时会产生原本不存在的干涉。屏蔽碰撞检测而仅依靠约束关系当然能完成装配,但当模型形状较复杂时就可能因此发现不了设计上的错误。因此,这个阶段的任务是检测出真实干涉的同时排除这些多余的干涉。下面以最典型的轴孔类装配为例说明。

基本策略:(1)通过对在同一个面(此处所指的面与CAD系统中的一致,导出的VRML文件记录了此信息)内的面片设置相同的标识,确定每个面片的归属。(2)当一对轴孔配合被识别而进入约束状态后,干涉排除阶段开始。(3)当碰撞检测进行到2个面片时,即可通过其标识判断是否在排除范围内,以决定是否需要检测。问题的关键在于,这些面包括哪些以及如何找出。观察后发现,它们是轴面和孔面及其分别对应的!凹∀面。对于孔,!凹∀面指与其相连,且其所有点不被孔所在柱面所围空间包含的面;对于轴面则指与其相连,且所有点不被轴面所在柱面所围空间包含的面(如果为锥面配合,!凹∀面就应根据锥面来判断),当2个面片分别属于这2组时即需排除。需注意的是,当!凹∀面与孔或轴面的相交线平行于孔或轴的中心线时(锥面时则为共面),该面的检测不应该被排除(如键槽的侧面),因为此类面并未引入虚假的干涉。利用从CAD系统中提取的一对轴孔的几何及装配约束信息,结合以上分析的几何关系即可找出所有应该排除的面。这种干涉排除方法基于一个前提:非配合面不因面片化而引入虚假干涉。

以上方法在某些情况下可能不适用。图5(a)为一个柱销插入活塞孔的情形。按照上述方法,活塞的!凹∀面在图中可见的为A和倒角B(另外2个不可见的分布于对称位置)。图5(b)示意了沿轴向的视图,并进行了简化,整个圆周仅被分为6份,图5󰀁圆柱销与活塞的装配

3󰀁结束语

结合虚拟装配环境的特点,本文把整个碰撞检测过程分为3个部分。在装配场景层,使用扫描剪枝和装配树结构尽早地避免了不必要的相交检测;在面片层,利用时空连续性实现了零件对的快速检测;依据面的邻接关系排除了大部分的虚假干涉。通过3个层次的有机结合,已基本实现虚拟装配环境的实时碰撞干涉检测。不过,文中涉及的主要是刚性体,线缆等柔性零部件的检测还有待于进一步的研究。参考文献:

[1]󰀁VanderbergenG.Efficientcollisiondetectionofcomplexde󰀁

formablemodelsusingAABBtrees[J].JournalofGraphicTools,1997,2(4):1-13.

[2]󰀁GottschalkS,LinMC,ManochaD.OBB-Tree:AHierarchi󰀁

calStructureforRapidInterferenceDetection[A].Siggraph96:23rdInternationalAcmConferenceonComputerGraphics&InteractiveTechniques[C],NewYork:AssociationforComputingMachinery,1996:171-180.

[3]󰀁HubbardPM.CollisiondetectionforinteractivegraphicsAppli󰀁

cations[J].IEEETransactiononVisualizationandComputerGraphics,1995,1(3):218-230.

(下转第36页)

362008年11月󰀁中国制造业信息化󰀁第37卷󰀁第21期

算机床误差、实现误差补偿和修正控制指令提供理论依据,并具有广泛的应用前景。参考文献:

[1]󰀁粟时平.基于空间误差模型的加工中心几何误差辨识方法

[J].机械工程学报,2002,38(7):121-125.

[2]󰀁刘丽冰,乔小林,刘又午.多轴数控机床误差建模研究[J].

河北工业大学学报,2000(3):2-6.

[3]󰀁范晋伟,闰邵泽,关佳亮,等.数控机床通用几何误差补偿关

键技术的研究[J].航空精密制造技术,2005(5):19-22.[4]󰀁郭󰀁辰,杨󰀁林,李庆勇.基于多体系统理论的数控机床误差

建模[J].机械设计与制造,2005(3):123-125.

[5]󰀁粟时平,李圣怡.五轴数控机床综合空间误差的多体系统运

动学建模[J].组合机床与自动化加工技术,2003(5):15-18.

T01,s󰀁T01,sT12,p󰀁T12,pT12,s󰀁T12,sT23,p󰀁T23,p󰀂T23,s󰀁T23,sT34,p󰀁T34,pT34,s󰀁T34,s)-󰀁T67,pT67,s󰀁T67,spt

1

T05,p󰀂(13)

󰀁T05,pT05,s󰀁T05,sT56,p󰀁T56,pT56,s󰀁T56,sT67,p󰀂

4󰀁结束语

基于多体系统理论,结合数控机床各部件间的

运动形式,采用低序体阵列描述复杂机械系统,建立了通用的数控机床运动模型,规范了的数控机床误差的建模方法,该方法具有通用性强、灵活性高和实用性强的特点,非常适合用计算机来实现空间误差的自动建模。此外,该机床误差补偿的数学模型,不受机床结构和运动复杂程度的,可为计

ResearchontheUniversalCompensateModelingofVolumetricErrors

forCNCMachineTools

TANGXiao,LIUZhuang

(NanjingUniversityofAeronautics&Astronautics,JiangsuNanjing,210016,China)

Abstract:Basedonthetheoryofmulti-bodysystemandcombinedwiththemovementformofCNCmachinetoolcomponents,itderivesauniversalmodelofvolumetricerrors,presentsanormativeandgeneralmodelingmethodforCNCmachinetoolserror.Theapplicationwithanexampleshowstheconstructionofvolumetricerrorsmodelof5-axismillingmachine.

Keywords:Multi-bodySystem;CNCMachineTools;VolumetricError;Modeling

(上接第32页)

[4]󰀁KlosowskiJT,HeldM,MitchellJSB,etal.Efficientcollision

detectionusingboundingvolumehierarchiesofk-DOPs[J].IEEETransactionsonVisualizationandComputerGraphics,1998,4(1):21-36.

[5]󰀁FigueiredoM.AdjustableApproachforCollisionDetectionin

VirtualPrototypeEnvironments[A].SarfrazM.GeometricModelingandImaging:Gmai2007[C].Piscataway:IEEEComputerSocietyPress,2007:44-47.

[6]󰀁CohenJD,LinMC,ManochaD.I-COLLIDE:AnInteractive

andExactCollisionDetectionSystemforLarge-ScaleEnviron󰀁ments[A].ZydaMJ.SymposiumonInteractive3DGraphics[C].NewYork:AssociationforComputingMachinery,1995:1-196.

[7]󰀁ComingDS,StaadtOG.Kineticsweepandpruneformulti-bodycontinuousmotion[J].Computers&Graphics,2006,30(3):439-449.

[8]󰀁魏迎梅.虚拟环境中碰撞检测问题的研究[D].长沙:国防科

学技术大学,2000.

[9]󰀁GB/6043.4-1986,零件倒圆与倒角[S].

ResearchontheCollisionDetectionforVirtualAssembly

XIEJian1,YANJing1,JIAOGuang-ming2,ZUODun-wen1,ZHOUHua-lin2,YANGFa-chun2

(1.NanjingUniversityofAeronauticsandAstronautics,JiangsuNanjing,210016,China)

(2.NanjingChenguangGroupLtd.Co.,JiangsuNanjing,210006,China)

Abstract:Collisiondetectionisoneofthemostimportantcomponentsinvirtualassemblysystemanditseri󰀁ouslyaffectsrealisticfeelingduringthesimulation.Itpresentsthemodeltoselectthepairsofpartswhoseboundingboxesoverlapusingakindoftechniquecalled∀sweepandprune∀combinedwithassemblytreestructure,describestheprocesstoreducebox-boxtestsbydevelopingtemporalandspacecoherence,propos󰀁esamethodtoeliminatetheintersectionsintroducedbyproximityofthepolygonalrepresentation.Keywords:CollisionDetection;VirtualAssembly;TemporalandSpaceCoherence