资源描述：
《利用法向矢量计算三维物体间的距离》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第20卷第6期Vol.20,No.6机器人ROBOT1998年11月Nov.,1998a利用法向矢量计算三维物体间的距离谭光宇袁哲俊姚英学(哈尔滨工业大学机电学院哈尔滨150001)摘要机器人路径规划和装配路径规划都要计算空间两个物体之间的距离,实时仿真系统则要求算法既简便、快速,又能够支持规划算法.本文提出了基于B-Rep的计算三维物体间距离的方法,即利用物体的表面法向矢量直接计算三维物体间的定向距离.该方法达到了上述系统对物体间距离的检测要求.关键词定向距离,法向矢量,碰撞检验,路径规划,仿真1引言实时路径规划或检
2、测一个已规划好的路径是否为无碰路径,都要快速地计算空间物体之间的距离.长期以来,人们通过各种尝试计算三维运动物体间的距离,其中多数是基于B-Rep[1～5][6]和CSG模型的,也有基于层次模型的.层次模型是一种近似的表达方法,其优点是可表达任何复杂的形体,如果提高检测精度,则需要增加划分级别,这将引起存储量的急剧增加.而基于B-rep模型的算法,当形体造型复杂时,被测要素增加,则算法效率不高.除此之外,这些算法还存在以下不足:(1)计算量问题,应用迭代过程求解最小距离,在某些情况下则可能出[2,3]现无穷迭代、算法收
3、敛太慢或穷举搜索;(2)实体的凸凹性限制,一般难以处理复杂物体,因[4,5]而往往将物体限制为凸多面体.鉴于B-rep表示的重要性,本文提出了基于B-rep表示的算法,称为法向矢量法.本算法的最初想法来自于对穴居类动物的观察,在黑暗的洞穴里,它们主要靠胡须测量洞穴的大小和障碍物,产生身体与环境物体的距离感,以便确定它的身体能否通过,这一过程就是路径规划过程或无碰路径的碰撞检验过程.仿效这一过程,提出了利用法向矢量计算空间物体之间的距离.本算法直接从B-rep数据结构中获取所需的数据,不需要模型的进一步转换或迭代计算,只
4、利用物体表面法向矢量计算两个物体表面之间法向矢量方向的距离(定向距离),即用法向矢量同另一个物体的面求交,获得该法向矢量的残余长度.然后,通过这个定向距离,还可以解决两个运动物体之间的碰撞和干涉距离的计算等问题,并支持装配路径的实时生成.下面,分别介绍物体表面法向矢量的生成、法矢残余长度分类和法矢插值算法及其应用.2表面法向矢量的生成给物体加上"胡须",就是在物体表面上生成法向矢量(简称法矢).实体类型不同,其上法矢的生成方法也不相同,对于平面实体,直接从B-rep结构数据中读取面表中的平面方程系数[4]normal,
5、可以得到该平面的单位法向矢量,然后,将法矢平移到该面的各个顶点上,对于多面体而言,其所有角点上均分布有交于该顶点的各个面的法矢,如图1(a)所示.a1998-03-13收稿456机器人1998年11月而曲面实体法矢的分布方法则各不相同,取决于曲面的类型.二次曲面,如球、柱、圆锥等,法矢从中心点或轴线出发均匀分布,如图1(b)所示为圆柱体的法矢分布方法;雕塑曲面则将法矢加到控制顶点上或曲面离散后的网格点上.(a)平面实体(b)曲面实体(圆柱)图1实体表面法矢分布3法矢与实体求交3.1实体配对当样本空间内的物体超过两个时,
6、要进行配对,建立实体对.然后,选择一个实体对进行距离计算.首先,在一个物体(称为主测体)上加法矢,用其各法矢与另一物体(称为被测体)的各面求交,如果交点有效,再计算法矢的残余长度.然后,主被测体对调,再进行上面的计算.为了防止漏检,轮流将法矢加到两个物体上,当环境不复杂时可以只加到一个运动物体上即可,从而节约一定的计算量.3.2法矢求交经过在物体表面上加上法矢,就将计算两个物体之间的距离问题转化为一个物体上的各个法向矢量与另一个物体的各面是否有交点的问题.如交点存在,再计算法矢的残余长度,否[7]则,转到下一个法矢的计
7、算,直至全部计算结束.关于矢量与平面求交可参见几何造型学的有关内容,这里不再赘述.3.3粗判准则为提高算法的效率,通过粗判准则,过滤掉实际上不需要计算的被测表面,以减少被测要yo素.计算法矢R与n被测面法矢的点积,以确定法矢与被测面的位置.二矢量的内积>0yoRn=0<0如图2所示,阴影线表示被测面的内侧,B-rep表示的面法矢总是指向实体的外侧.当yoRn>0时,表明法矢从物体内部或背向穿过被测表面.显然,在此之前,法矢已经穿过物图2法矢量与平面法矢的夹角体的另外表面,或从体外经过,故排除该面;y当Rno=0时,法矢
8、与面法矢垂直,可分为3种情况.第一种情况是法矢在表面的外侧经过,这种情况凸多面体则法矢不会与物体相交,而凹多面体则可能与另外的表面相交;第二、三种情况是法矢在表面上或从物体的内部穿过而与第20卷第6期谭光宇等:利用法向矢量计算三维物体间的距离457该表面的邻面相交.以上3种情况都不需计算,从而排除法矢与该表面的相交计算.当yRo<
