近邻我想建网站

中国机械工程第14卷第9期2003年5月上半月文章编号:1004—132x(2003)09—0756—04基于二维Delaunay近邻的空间散乱数据曲面重建算法单东日柯映林摘要:给出了一种新的散乱数据曲面重建算法.
算法基于曲面的局平特,}生,通过二维Delaunay三角剖分到三维空间的映射,快速查找空间任意点的Delaunay近邻,然后根据散乱数据重建三角网格中顶,占'互为Delaunay近邻的原理,进行曲面拓扑重建.
应用新的求解矗一近邻和二维Delaunay近邻的算法,提高了曲面重建的算法效率.
实验表明,该算法高效、稳定,对不均匀数据有较好的适用性.
关键词:曲面重建;散乱数据点;二维流形;三角剖分中图分类号:TP391文献标识码:A随着深度摄像、激光测距、CT、MRI等三维测量和信息获取技术的发展,包含被测物体更多细节的散乱数据的获取成为可能.
基于散乱数据的三维重建在反求工程、科学计算可视化等众多领域中具有重要的研究意义和实用价值.
一些学者对基于散乱数据的曲面重建进行了研究u].
1相关概念lD一密度样本如果以曲面上任意一点为球心,半径为lD的球面内至少包含一个曲面上的样点,则称此样点集为该曲面的一个lD一密度样本.
k一近邻散乱点集P中与某一点p,的直线距离最短的k个测点,称为点p,的k一近邻,记为N(p,),k一近邻中的每个点称为p,的邻近点[3].
二维Delaunay三角剖分一个三角形集合T一{Tli一1,2,…,N},若满足以下条件:①7的顶点集为P;②7'的并集为P的凸包;③7'中任两个三角形的交集或为空集、或为P中的点、或为以P中两点为端点的一条边;④T中每个三角形外接圆的内部不包含其它的点[4,s2,则称7'为平面上不共线有限点集P的Delaunay三角剖分.
二维Delaunay近邻二维Delaunay三角剖分中,与点p,共边的顶点,称为的二维收稿日期:2001—12—31基金项目:国家863高技术研究发展计划资助项目(863—511—942一O18);高等学校博士学科点专项科研基金资助项目(98033532)·756·Delaunay近邻.
2算法描述单东El博士研究生2.
1计算矗一近邻为建立散乱点的拓扑邻接关系和估算切平面,需首先计算每个测点的邻近点.
为此,我们设计了计算矗一近邻的快速算法,算法步骤如下:(1)用快速排序算法对散乱点按坐标zxy词典顺序排序.
首先按坐标z由小到大排序,如果z相等,则按z排序,如果z也相等,则按Y排序.
(2)查找以点p,为中心,2P为边长的立方体包围盒内的点,可根据采样密度适当选取.
(3)如果包围盒内的点数小于是,则令e一2e,重复(2).
否则,查找并记录离点p,最近的k个点.
(4)重复(2)、(3),遍历散乱点集中的所有点.
2.
2估算法矢通过点p的k一近邻拟合最小二乘平面来估算法矢的主要方法有正则方程法(themethodofnormalequations,MNE)、奇异值分解法(singularvaluedecomposition,SVD)和特征向量估计法(eigenvectorestimation,EVE).
由于MNE和SVD在曲面过原点时产生零解,我们采用EVE方法,即min:[(p—p)·,l]pC--N(RI)对称的半正定3*3矩阵M为M=[(p一)·(p一)],∈N9)容易证明,把最小的特征值对应的特征向量单位化,即为曲面在点p的法矢厅.
由于只需计2http://www.
paper.
edu.
cn基于二维Delaunay近邻的空间散乱数据曲面重建算法——单东日柯映林算最小特征值对应的特征向量,所以我们采用逆迭代法求解.
2.
3计算Delaunay近邻按照拓扑学的定义,曲面即是二维流形.
直观地说,曲面的整体形状可以很复杂,但其局部却是平坦的,即每一点的近旁都有一块区域同胚于平面,这就是曲面的局平特性.
因此,在曲面上任意点P处必存在一微小邻域』\,,』\,内的点与其在点P切平面内的投影存在一对一的映射关系j.
基于上述理论,我们建立平面坐标系:投影点P,的足一近邻至7P(丁P为过点P,法矢为,l的平面,即曲面在点P的切平面),以点P为原点,足一近邻的投影点中离P最近的投影点(记为Nearest—Prj)与P连线所在直线为轴,在平面P内建立二维平面直角坐标系x0y.
建立二维坐标系后,点P的邻近点就与其在丁P的投影点(记为SetProj)建立了一对一的映射关系(z,,2)(X,Y).
在切平面丁P,内,从P邻近点的投影点中查找P,的二维Delaunay近邻,然后映射到三维空间,与P,的二维Delaunay近邻相对应的P的邻近点称为:::::r:De田launa—y莲近邻,见图1.
因P为—————旦—-一/x0y的坐标原点,图l二维Delaunay近邻及所以只需从Set其到三维空间的映射Proj中查找坐标原点的Delaunay近邻.
对二维点集的Delaunay三角剖分丁,有如下基本定理:定理1如果点P∈S、P∈S,P是关于P的最近邻近点,则线段PP是7s的一条边.
定理2如果P∈S、P∈S、P.
∈S,P是关于P的最近邻近点,Ps是相对边P.
P张角最大的样点之一,则三角形/hpPP.
是7的一个三角形.
定理3如果Pl∈S、P2∈S、P3∈S、P∈S,三角形/hpPP.
是,,s一个三角形,点P位于三角形/hpPzP.
关于边PP的外侧且对边PP的张角最大的样点之一,则三角形/hpPP是r,的一个三角形.
根据上述定理,我们设计查找点P(即X0y的原点)的二维Delaunay近邻的算法如下:(1)令P1:NearestPrj,flag一0.
记录Nearest—Prj.
(2)从Set.
Proj中找出对边Op.
张角最大的点P得/NOPP,记录Pz并令P=P2.
(3)检查/NOP.
P关于边OP的外侧是否有SetProj中的点,如果有,从中找出对边OPz张角最大的点P.
得/NOPP.
,记录P.
并转(4),如果OP的外侧没有点,则令flag—flag+1,转(5).
(4)如果P.
=P.
,则转(6),否则,令P一Pz,P2=P3,转(3).
(5)如果flag一2,转(6),否则,令P.
=P,P一Nearest—Prj,转(3).
(6)结束.
由于余弦在[O,兀]上是严格单调递减函数,因此计算最大张角只需计算夹角最小余弦值.
由于局部平面坐标系的原点取在P,因此判断SetProj中任意点P.
是否位于三角形OPP.
关于边OP.
的外侧只需计算下式的正负:IsotherSide一(pyp1一YP2X】)(Xp2yp一YP2Xp3)2.
4三角化拓扑重建作为曲面重建的第一步,其任务是重建各样点之间的拓扑关系,重建结果为一张与原曲面拓扑等价的三角形网格.
在计算完所有测点的空间Delaunay近邻后,可根据定理4计算出由空间散乱点组成的所有三角形.
定理4当且仅当点P、P、P.
的空间Delaunay近邻分别含有{P2,P3)、{P.
,P3)和{P.
,P}时,点P、P和p.
构成一三角形.
2.
5调整法矢一致调整法矢一致是指把整体三角网格中的所有三角形的法矢指向曲面同侧,其在拓扑重建与几何重建中具有重要作用.
为调整三角形法矢一致,我们首先调整测量点的法矢一致.
设测点P∈S,P,∈S是曲面上距离很近的两点,则相应法矢的点积,l·,l≈1,否则,,l或,l,应当被反向.
基于此基本原理,调整测量点法矢一致的主要步骤如下:以每个测点为顶点,每两个Delaunay近邻之间连一条边并将边的权值赋为1一·,l,I,形成一个赋权无向图,亦称Riemannian图.
采用Prim算法生成Riemannian图的最小生成树(EMST)[川,按深度优先遍历EMST,调整法矢指向曲面同侧.
测量点法矢调整一致后,计算三角形三顶点法矢的平均值,l,并调整三角形的法矢Ⅳ与其一致.
如果,l·N<0,则将Ⅳ反向.
三角形/hpPP.
的法向可表示为jv一(P2一p1)*(p3一p1)/II(p2一p1)*(p3一p1)由上式可知,改变三角形/XpPP.
的法向,只需交换三角形中某两个顶点的存储顺序.
2.
6拓扑重建·757·中国机械工程第14卷第9期2003年5月上半月为重建一张整体光顺的三角曲面,必须建立点边、三角形之间的拓扑关系.
即在点的数据结构中记录其所在的边、三角形;边的数据结构中记录边的起点、终点,左、右三角形;三角形的数据结构中按顺序记录三角形的三个顶点,三条边及与三个顶点相对应的三个三角形.
在完成测量点的空间Delaunay近邻计算和调整法矢一致后,三角网格的拓扑关系容易建立.
几何重建从拓扑重建获得的三角网格出发,重建光滑的曲面以近似地再现原曲面L8J.
3算法分析3.
1k一近邻本文算法将邻近点个数走作为输入参数,是的选取关系到算法效率和重建效果.
由于Delaunay近邻包含在测点的k一近邻之中,如果k取的过小,可能导致查找不到测点的全部Delaunay近邻,从而形成孔洞或有些测量点不参与三角化;走取的过大,会降低算法效率,但一般不影响重建效果.
由于二维Delaunay近邻的数学期望值为6[6],在实践中,对均匀分布的数据点集k取10~20,一般都能获得较好效果.
.
3.
2算法效率笔者在散乱数据的曲面重建算法中,应用一新的计算k一近邻的算法,计算任一点的k一近邻只需计算其到立方体包围盒内的点的距离,提高了算法效率.
据文献E53介绍,采用传统算法计算4102个点的12一近邻需要26min,而应用本文算法计算图2所示型号工装测量数据的(15476个点)的15一近邻仅需数秒.
另外,在计算Delaunay近邻时,我们建立了一特殊的平面直角坐标系,使得计算效率大大提高.
3.
3P一密度样本P一密度样本实际上定义了一均匀密度样本,但实际应用中由于测量数据具有一定的不均匀性,一般不能满足此要求.
本文算法对数据分布的不均匀性具有一定的适应性,只是当数据分布不均匀时,k应取的较大,对算法效率有一定的影响.
3.
4孔洞处理由于数据分布的不均匀性,容易造成重建三角网格包含孔洞.
根据拓扑关系容易识别三角网格的内、外边界,如果想封闭三角网格的孔洞,只需对孔洞的边界多边形进行三角化.
空间多边形三角化算法见文献[-83.
3.
5叶片数据·758·Eh于本文算法需从散乱点的邻近点查找其Delaunay近邻,而如果散乱数据采集于非常薄的叶片,则算法不能自动分离叶片上下表面数据点,从而导致拓扑关系错误,以及许多点不能参与拓扑重建,这也是局部重建算法的共同缺点.
4应用实例本文算法已用C++语言在浙江大学自主版权反求软件Re--Soft中实现.
我们已用多个例子进行测试(图2中左侧为散乱数据点,右侧为三角网格渲染效果图.
其中,型号工装测量数据用三坐标测量机采集获得,水龙头数据为反求软件Sur—facer的实例通过*.
igs文件输出获得),测试结果见表1.
实验结果表明本文算法高效、稳定.
表1测试结果CPU时间实例点数k三角形数(s)型号工装15476153094963水龙头246211249283196(a)型号工装(b)水龙头图2测量数据与三角网络模型5结论本文提出了一快速、可靠的散乱数据曲面重建算法.
算法适用于任意拓扑的几何外形,不需事先给出测点法矢、曲面边界等附加信息.
重建三角网格符合Delaunay原则,可广泛应用于工程数据可视化及反求工程等领域.
参考文献:[1]GUOB,MenonJ,wiIIetteB.
SurfaceReconstruc—tionUsingAlphaShapes.
ComputerGraphicsfo—rum,1997,16(4):177~19O[2]GopiM,KrishnanS,SilvaCT.
SurfaceRecon—structionBasedonLowerDimensionaILocalizedDelaunayTrianguIation.
EUR0GRAPHICS,2000,】9(3):467~478协同集成设计环境的计算机辅助工具的协同用户界面研究——何发智王少梅孙国正等文章编号:1004一I32x(2003)09—0759—04协同集成设计环境的计算机辅助工具的协同用户界面研究何发智王少梅孙国正高曙明摘要:以一个协同集成设计环境的计算机辅助工具为背景,对协同用户界面进行探讨.
按照以群体为中心的协同用户界面的设计思想,提出了一种基于Agent的协同用户界面模型,把通讯和协作支持等并行处理的概念和方法引入到现有结构化模型之中.
对比传统CAD交互结构,构造了一种支持上述用户界面模型的软件Agent结构.
关键词:协同用户界面;协同设计;计算机辅助设计;Agent;群体感知中图分类号:TP391文献标识码:A设计活动不仅具备创造性和智能性,而且具备群体性和协作性.
人们已经开始采用计算机网络技术来支持群体设计活动,但是工作界面仍然停留在个体工作的层次上[1].
协同集成设计环境的计算机辅助工具(computer—aidedtoolsforcollaborativeintegrateddesignenvironments,CATCIDE)是一种典型的分布式、多用户协同工作系统,用于支持密切、并行的设计工作.
国内相关研究主要是针对协同编著系统的[2].
本文以CoCADToolAgent——一个CATCIDE为实例和背景,对协同用户界面进行研究.
1以群体为中心的协同界面设计思想现有协同工作系统的两类基本协作框架均存在不足引.
CoCADToolAgent是一种半透明半明确的协作框架,在没有源代码的情况下利用该工具成功地将传统单用户CAD系统转换成为网络环境下支持群体协同工作的CAD系统.
我们在收稿日期:2OO1一O7一O2基金项目:国家自然科学基金资助项目(60273057);国家863高技术研究发展计划资助项目(2002AA41131O)一何发智副教授CoCADToolAgent的研究中,提出了一种以群体为中心的界面设计思想,为协作者提供如下特色功能:①一些分布式CAD系统虽然支持多个用户对异地或共享资源的交互,但用户界面本质上仍然是人机界面,因为每个用户在与机器交互时感觉不到其他用户的存在.
而CoCADToolAgent界面以群体为中心,在低层原语中加入用户信息,使协作者在操作时能明显地感觉到其他用户的存在.
②传统界面只支持对设计对象的各种处理功能,而CoCADToolAgent界面提供了各种关于群体的操作功能.
例如,传统界面提供了对图形对象的查询功能,而协同用户界面则可以根据协作者名字来查询该用户所创建、修改的对象,以便于了解群体组织结构、群体的设计历史、群体的活动特.
征等.
③传统界面仅支持单个用户独立地对图形对象进行创建、修改、删除等建模活动,而Co—CADToolAgent界面支持多个用户的协同建模活动,通过一个任务向导来帮助传统CAD用户从独立工作方式过渡到协同工作环境中来,提供三种协作模式和相应的并发控制来支持典型设计过程中的协同工作活动.
④传统界面所提供的人机交互感知技术有文本光标、图形指针、夹点显示、[33周儒荣,张丽艳.
海量散乱点的曲面重建算法研究.
软件学报,2001,12(2):249~255[4]李立新.
散乱点集曲面重建的理论、方法及应用研究:[博士学位论文].
杭州:浙江大学,2001[53周培德.
计算几何.
北京:清华大学出版社,2000[6]陈省身,陈维桓.
微分几何讲义.
北京:北京大学出版社,1999[7]WilliamF,WilliamT著.
数据结构.
刘卫东,沈官林译.
北京:清华大学出版社,1998[8]李江雄.
复杂曲面反求工程CAD建模技术研究:[博士学位论文].
杭州:浙江大学,1998(编辑马尧发)作者简介:单东日,男,1973年生.
浙江大学(杭州市310027)机械与能源工程学院助教、博士研究生.
主要研究方向为反求工程、计算机图形学、CAD/CAM.
发表论文3篇.
柯映林,男,1963年生.
浙江大学机械与能源工程学院教授、博士研究生导师.
·759·誊