基于工程图纸的三维形体重建技术

基于工程图纸的三维形体重建技术

1多三维形体重建算法基于工程图纸的三维重建技术是计算机设计和计算机绘图的一个重要研究领域。国内外研究人员先后提出了几种重建算法。idesaw首先提供了三维重建方法的数学推理模型。该方法仅研究了非常有限的3d重建算法，但它提出的自函数法已成为许多3d重建算法的基础。marrowsky和wesley提出了一种适合任何多面体的重建算法。该算法可以生成符合输入三个场景的多个解决方案，以适应3d图像。gu部分解决了平面体和柱面体重建的问题，并将柱面体轴的自由度延长到与特定坐标平面平行的平面上。yan提出了适合平面体重建的算法。该算法使用决策树技术加速了三维边缘的生成速度。阴影利用每个图像中的二维信息和重建过程中产生的三维信息之间的关系，减少检测和评估的数量，在一定程度上提高了算法的操作效率。以前的重建算法由于反复执行投影匹配操作和复杂的几何运算,需要较长的处理时间.本文工作的主要目的是减少重建过程的处理时间.在重建过程中,我们利用几何基元之间的几何性质和拓扑关系,减少了投影匹配的次数,避免了复杂的几何运算.在决策求解过程中,我们根据Moebius规则和工程图的性质,省去了候选块生成这一步骤,简化了传统的决策求解.2概念和结论1.定义12.定义2定义3(1)环L内没有与其共边的其它环;(2)环L的方向与有界面F的法向满足右手螺旋定则.定义4维点与二维点性质1(空间点的投影特性).设空间点P(x,y,z)在主视图投影面上的投影为(xf,zf),在俯视图投影面上的投影为(xt,yt),在侧视图投影面上的投影为(ys,zs),则有:xf=xt=x,yt=ys=y,zf=zs=z.性质2(对应原理).若主视图、俯视图、侧视图3个视图中的二维点(xf,zf),(xt,yt)和(ys,zs)满足那么它们对应于三维空间中的唯一点(xf,yt,zs).3维形体算法本节主要讨论基于三视图的平面体的重建算法,与传统的自底向上的重建算法相比较,该算法省去了候选块的生成这一步骤.在重建过程中,我们首先根据对应原理,从三视图生成形体的三维顶点和三维边,初步构造出形体的线框模型.然后利用线框模型生成形体的面环,最后根据Moebius规则和投影性质进行决策求解,获得最终的三维形体.算法的主要步骤为:检查整理输入数据;生成三维候选顶点;生成候选边;生成切割点;构造面环;决策求解.在形体重建过程中,所产生的顶点、边、面等未必都是最终形体的成分,有的可能是非法的,在重建过程中将被消除.为此,我们把这个过程中的顶点、边和面称为候选顶点、候选边和候选面,分别记为C＿Vertex,C＿Edge和C＿Face.3.1建立阶段及其数据的选取过程本算法的输入数据是屏幕坐标系下的三视图.为了获得重建算法所需的数据,首先需要找出3个视图的公共原点,然后分离3个视图.对于每一个视图,我们建立相应的二维顶点表CnodeList和二维边表CsegmentList,并检查输入数据的合法性.3.2共享轴接合点的构成为了生成所有的三维候选顶点,我们首先从两个不同视图的二维顶点表中各取一点,如果两点在共享轴上的坐标值相等,那么继续在第3个视图的二维顶点表中查找与上述两点除相同坐标值之外的其它两个坐标值完全相同的顶点.如果第3个视图的二维顶点表中存在这样的二维点,那么这3个二维顶点生成了一个C＿Vertex.3.3假设假设不成立为了降低处理时间,我们利用二维点、边和三维点、边之间的几何关系和生成规则,来减少投影匹配的次数.性质3.垂直于某投影平面的直线段在该投影面上的投影是二重点(二维顶点).性质4.设e是由两个C＿Vertex构成的线段,如果e仅在一个视图中的投影包含在二维视图的边表中,则e不是一条C＿Edge.证明.假设命题不成立,则出现下面两种情况.1)e仅在一个视图中的投影为二维边,在其它两个视图中的投影为二维顶点;2)e在3个视图中的投影均为二维顶点.以1)为例证明.由性质3可知仅当某条线段垂直于某一个投影平面时,它在该平面上的投影为二维顶点.为了满足条件1),e应该同时垂直于两个投影平面.然而,一条直线段不可能同时垂直于两个非平行平面,出现矛盾.同理可证假设2)也不成立.因而一条属于三维形体的边至少在两个投影平面的投影为二维边.证毕.新的三维边生成方法主要是利用上述性质来加快C＿Edge的生成.为了充分利用上述性质,我们采用如图2所示的数据结构.新三维候选边的生成方法为:对于每一视图的二维边,从二维边两个端点的C＿Vertex表中各取一点,连接这两点形成的三维边为e,将e投影到另外两个视图中进行匹配判断.在匹配过程中,利用图2的数据结构,我们仅需查找与该三维边某一端点的投影点相关联的二维边,减少了匹配判断次数,降低了运行时间.我们将在第4节分析算法的效率.3.4切割点的生成在第3.2节,我们给出了一般顶点的生成方法,然而形体中可能存在切割点(如图3中的点P),不能通过前述方法生成.为了得到合法的线框图,我们在线框模型中引入切割点.由切割点的定义和投影的性质可知,切割点至少在一个视图中的投影为两条非共线二维边的交点,并且这一交点不是该视图中二维边的端点,而是二维边的内点.按照惯例,这类二维点是不出现在二维视图中的.然而为了能够生成相应的线框图,我们需要求出该二维点及与其相关联的二维边.利用这一性质,在三视图的预处理中,对两个非共线的二维边求交获得此二维点的同时,我们将这样的二维顶点放入到一个临时的二维点表中,并记录与其相关联的两条二维边.此处我们仅检测这些二维顶点,由通过该二维顶点的两条二维边找到其生成的三维边,对两个三维边进行求交获取切割点.3.5以vivi,vi为起点的环本节将讨论从线框模型中提取表面信息的算法.目前常用的表面信息自动识别方法为几何方法.该方法的基本思想是:根据相邻两条边的类型来确定一个三维面及其方程,然后应用深度优先方法搜索该面中的所有边,生成所有可能的面环,最后应用一定的准则删除非极小环.由上面的讨论可知,几何方法的几何运算复杂,需要较多的存储空间和较长的处理时间.针对这一不足,我们提出了左邻边序列法,这一方法仅需生成构造形体的面所需要的环,避免了非极小环的生成,节省了算法的处理时间和存储空间.算法主要包含6步:1.选择未处理过的凸顶点vi作为跟踪起点;2.选择未组合过的共点于vi且不共线的边对el(vl,vi),em(vi,vm),假设由这两条边所组成的面F的法向为n=(vi-vl)×(vm-vi),找出属于该面的所有边E(F),确定该平面顶点和边的连接关系.对于度大于2的顶点,求出该顶点的左邻边序列;3.从E(F)中选择一条未被引用过的边ei(vi,vj)作为初始边;4.根据已知条件,选择一遍历方向,假设vi→vj是目前的遍历方向;5.如果vj的度为2,则将与该点相关联的另外一条边加入到环中,否则根据该点的左邻边序列确定环中的下一条边,假设这条边为el(vj,vl);6.若vl=vi,生成环并返回到步骤2,否则令vj=vl,转步骤4;注:在寻找一个面的所有边时,我们仅检测与该面上已知顶点相关联的边,并且属于该面的共点边对均认为已经组合过,不再用于求解新的面方程,这样就减少了面及面环生成过程的判断次数.另外,确定左邻边序列时,我们并不求出两边的夹角,而通过下述方法来简化计算.设共点于vi的边为e1,e2,…,ek,将e1作为x轴,将该平面的法向量看作是z轴,那么y=z×x.设《n》x,《n》y为x轴和y轴的单位向量,e1和ei夹角的正、余弦为:通过比较cosθi和sinθi(i=2,…,k),可以确定相应夹角的大小关系,进而可以求出该点的左邻边序列.这样就避免了反余弦求角计算,降低了运算复杂度.3.6结果显著性处理从前面的讨论可知,三维形体的点和边是重建过程中生成的三维线框模型的子集.即,三维线框模型中可能包含假元.因而重建的关键技术是检测并删除线框模型中的假元.Wesley和Markowsky首先给出与候选块(Candidateblock)有关的决策求解方法,目前许多B-rep重建使用这种方法.该方法生成许多临时候选块,然后组合这些候选块,构造所有可能的形体,并检查每个合法形体的三视图是否与输入数据完全匹配.然而,算法中临时生成的某些候选块可能会相交,在其边界上产生非法的交线.为了避免两个候选块之间存在非法交线,传统方法引入了原三维形体中并不存在的临时的“切割边”.切割边将刚生成的候选面分割成较小的候选面.然后交替引用每一面,组合出所有的候选块.从上面的讨论可知,传统决策求解方法不仅搜索复杂度是指数级的,而且切割边的引入也是十分费时和浪费存储空间的,特别是当形体中包含曲面时为了避免这种穷举搜索策略和切割边的引入我们给出与面有关的决策求解方法.该方法利用一些决策规则搜索求解最终的三维形体.本节使用的决策规则主要是基于Moebius规则和工程图的性质.我们首先介绍组成形体的边应满足的两个条件.(1)局部条件(Moebius规则):2-流形体中的每一条边属于两个面,三维边在每个面中的方向不同,即属于两个面的边在两个面环中的方向相反;(2)全局条件:组成形体的任意两个面除了构成它们的边之外,不能再有任何交线.决策求解算法的基本思想是根据形体的局部条件和全局条件删除线框模型中的非流形边,并使生成的形体满足输入的三视图.为了确保生成的三维形体与输入的视图匹配,我们采取下述方法.对于二维视图中的每一条二维边si,我们计算出该二维边所对应的三维边总数ni.在构造三维形体的过程中,我们可能会删去线框模型中的一部分边,这时二维视图中一部分二维边的ni值将会减少.决策方法的目标是在保证每一个ni为正数的前提下,生成有效的三维形体.图4给出决策求解方法中所用的数据结构.下面给出决策求解算法.1.在生成的线框模型中寻找非流形边,设为ei.2.在与ei相关联的面中选出任意两个未组合的面,设这两个面为合法面,将两个面的所有边均标识为TRUE,删除与ei相关联的其它面,并检查删除边所对应二维边的ni值是否为0,若为0,返回2,否则转3;3.检查线框模型中是否存在仅与一个面相关联的边,若不存在,转向5,否则,转向4;4.删除该面和该边,检查删除边所对应二维边的ni值是否为0,若为0,返回2,否则转5;5.检测是否存在与现有合法面相交于内部的面,若存在,则该面为非法面,删除该面,转向3,若不存在,转向6;6.对于线框模型中投影线为虚线的边,检测是否有面遮挡它,若有,转向7,否则,转向2;7.检测是否所有边的表示均为TRUE,若是,生成形体,否则转向1.基于以上算法步骤,我们使用VisualC++实现了一个原型实验系统,图5给出了应用新方法进行重建的机械零件.4算法运行时间的比较本节详细分析了重建主要阶段的算法复杂性,并以实际物体为例,比较了本文所提出的算法与传统的以Gujar和Shin为代表的重建方法的运行效率.图6、图7给出了应用本文的算法进行重建的例子,实验结果表明,与传统算法相比较,该算法在保持存储空间不变的情况下,运行速度提高了10倍左右.(1)候选边生成阶段的算法效率分析:传统的三维边的生成方法为:在生成的C＿Vertex表中任取两点,为了检测这两点的连线是否为一条C＿Edge,需要将这条新生成的C＿Edge重新投影到三视图中,并与三视图的二维点表和边表进行匹配.如果该线段的投影包含在3个视图的二维点表或边表中,则该边是一条C＿Edge.该方法再投影的次数为n(n-1)/2,其中n=card(C＿Vertexs).每一C＿Edge的匹配时间复杂度为O(m),m为三视图中二维线段与顶点之和.对于复杂的形体,这一过程势必导致处理时间的迅速增加.而新算法的再投影次数为msn-2.ms为二维边数,n-是每一个二维点所生成的C＿Vertex平均数,且n-满足1≤n-≤3n,即msn-2<<n2.每一C＿Edge的匹配时间复杂度为O(1).表1给出了候选边生成过程的运行时间的比较,由表1可知,本文所提出的算法显著减少了处理时间(2)切割点生成阶段的算法效率分析:传统的方法从生成的三维候选边表中任取两条边,通过求交获取切割点,因而传统切割点生成方法的求交次数为ne(ne-1)/2,其中ne为C＿Edge总数.我们方法的求交次数为nsne2,其中ns是度≥4的二维顶点数,ne是投影通过这些二维顶点的C＿Edge平均数.由于2nsne<ne,ne<<ne,所以nsns2<<ne2.(3)面及面环生成阶段的算法效率分析:表3给出了提取表面信息阶段算法运行时间的比较,由表3可知本文所提出的方法需要较少的处理时间.(4)决策求解阶段的算法效率分析:表4给出了决策求解阶段运行时间的比较,表4表明本文所提出的方法需要较少的处理时间,这是因为我们的方法省去了候选块的生成这一步骤,避免传统穷举搜索策略和切割边的引入,从而降低了运行时间.上面列出了重建主要阶段的算法运行时间,加上其它一些必要处理过程的运行时间,我们给出了整个重建过程的处理时间比较(见表5),实验结果表明我们的重建算法提高