基于规则的曲面体三维重建.docx
《基于规则的曲面体三维重建.docx》由会员分享,可在线阅读,更多相关《基于规则的曲面体三维重建.docx(18页珍藏版)》请在冰点文库上搜索。
基于规则的曲面体三维重建
第10卷第6期计算机集成制造系统
Vol.10No.6
2004年6月ComputerIntegratedManufacturingSy
stemsJun.2004
文章编号:
1006-5911(200406-0714-07
基于规则的曲面体三维重建
张爱军,薛勇
收稿日期:
2003-04-10;修订日期:
2003-12-19。
作者简介:
张爱军(1969-
男,河北唐山人,中国科学院遥感应用研究所博士后,主要从事三维重建、空间信息可视化等研究。
E-mail:
aj.zhang
@263.net。
(中国科学院遥感应用研究所开放实验室,北京100101
摘要:
为了加快曲面体的三维重建速度,提出一种利用面判定重建策略来构造目标形体的重建算法。
在面判定重建策略中,提出了“面序列”和“确定性面序列”两个概念。
在重建过程中,首先根据2-流形体(2-mani-folds的性质和莫比乌斯法则(Mobiusrule以及正投影规律,提取出一些基本的判定规则;然后根据这些判定规则,从由三视图恢复和提取的所有空间候选面中确认面序列及确定性面序列,并将面序列作为拓扑同构面片;最后利用判定规则对候选面片进行组合判定,将符合条件的面片和面序列装配成实体。
该方法减少了候选面片的组合判定次数,提高了重建效率。
关键词:
三维重建;线框模型;实体模型;面序列;确定性面序列中图分类号:
TP391.41文献标识码:
A
0引言
工程图(特别是三视图曾广泛应用于工程设计中。
如何利用传统的工程图重建三维形体,是计算机图形学和计算机辅助设计领域的一个重要研究课题,受到国内外的普遍重视,到目前已有许多富有成
效的成果[1~11
]。
目前,由工程图重建三维形体基本分为两类方
法,一是构造实体几何(CSG法[1~4?
@
二是边界表示(B#rep
法[5~10]。
CSG方法的基本思想是将复杂的三维形体分解成预定义的一些体素的组合,并将所有预定义的体素的三维特征及其三视图投影特征描述定义成一系列的模式,构成描述体素的模型。
CSG方法对于简单的视图信息比较有效,但是当视图信息比较复杂时,则很难构造出相应的体素。
B#rep方法是一种几何元素分层重建方法,
即依据视图图形的几何元素(点、线等的投影对应关系和求解规则,通过对视图二维几何和拓扑信息的分层解释逐步恢复三维信息(点、棱边、面等。
这是目前应
用较多的一种重建方法。
最后利用实体表面流形的性质,通过对已恢复的各个候选面片依次进行组合
判定,
将符合要求的面片组装成实体模型[5~10]
。
这种方法在构造实体模型时需对各个面片依次进行组合判定,因而费时。
针对B#rep方法存在的缺陷,本文提出一种基于规则的面判定重建策略,通过引入判定规则,来加快重建速度,提高重建效率。
1构造曲面体线框模型
根据各视图中的二维点、线信息的投影对应关系,
恢复空间的顶点和边,将空间顶点和边对应连接,构造出线框模型[5~10]
。
线框模型中的顶点和边
分别称为候选顶点和候选边。
1.1由线框模型提取表面信息
首先从线框模型中提取出所有可能的表面,这些表面包含了实体的各个面片。
在线框模型中,空间边的类型为直线和平面二次曲线(圆锥曲线,可根据线框模型中相交于一点的两条非共线边来构造
第6期张爱军等:
基于规则的曲面体三维重建
表面,这两条边的类型和位置关系通常决定了其所在曲面的类型和特征[10]。
例如两条不共线的直线边可以决定一个平面,一条直线边和一条二次曲线边相交或两条二次曲线边相交可以决定一个平面或一个二次曲面。
确定空间表面后,采用最大转角法(MaximumTurningAngle,MTA构建各表面上的基环[9]。
1.2确定候选面片
首先确定每个表面上各基环之间的位置关系,即包含或分离。
在包含关系中,如果环1被环2直接包含,则称环1是环2的子环,环2是环1的父环。
根据基环间的包含关系,每个当前基环和其所有子环之间构成一个面片。
其中,当前基环为面片的外环,其所有子环为内环。
不含子环的基环单独构成一面片。
如果当前基环被2n+1(n00个基环所包含,则通常将该基环和其子环之间构成的面片视作整个表面上的孔。
此时,可将所有面片和孔都视作重建过程中的候选面片。
2基于规则的2"流形体的面判定求解从线框模型恢复、提取的各候选面片不一定都是重建目标形体的实有面,那些确实属于目标形体上的候选面片称为真面,而其他的候选面片称为假面。
所谓基于规则的面判定求解,就是根据2#流形体(2#manifolds的定义和性质、莫比乌斯法则(Mobiusrule以及投影信息的特征(如深度信息[5~9]对各候选面片进行判断、组合和搜索,作“去伪存真”处理,最后将符合判定规则的面片进行组合,从而构成目标形体。
为进一步提高面组合判定的处理效率,本文提出了“面序列”和“确定性面序列”两个概念,通过提取候选面片中的面序列以及确认确定性面序列来加快面组合判定的处理过程。
定义1流形边(非流形边。
在B-rep实体模型中,若一条边仅与两个不共面的面片相关联,则称该边为流形边;否则,称之为非流形边。
定义2面序列。
在由线框模型提取的所有候选面片中,依次以流形边连接在一起的一簇面片构成一个面序列。
定义3确定性面序列。
若视图中的某些投影线段唯一对应于一个面序列,则该面序列是一个确定性面序列。
2.1面判定求解的规则
这里提取出一系列判定面片状态的规则:
规则12#流形体中的每条边只能有两个面与之相关联。
规则22#流形体中的任意两个面只能相交于面的边线。
规则3当形体中两个或多个面内部相交时,至多有一个面为真。
规则4若与一条边相关联的面仅有两个,则这两个面同为真或同为假。
规则5若一条边为真且与之相关联的面仅有两个,则这两个面亦为真。
规则6若一条边仅与一个面相关联,则该边和面同为假。
规则7与空间切线边相关联的面中必有两面为真。
规则8对于视图上的任一条线段,必有至少一条空间边与之相对应。
规则9若一条边在某方向上的投影为虚线,则在该投影方向上必有至少一个面位于它的前方;否则,该空间边为假边。
规则10若一条边在某方向上的投影为实线,则在该投影方向上位于它前方的任何面必为假面。
规则11空间面共面邻接,若共享边在某方向上的投影为虚线,则这两个面同为真或同为假。
规则12空间面共面邻接,且共享边在某方向上的投影为实线,若在该投影方向上无其他遮挡面,则这两个面中必有一面为假面。
规则13若一条边仅与两真面相关联且两面共面,则该边为假边。
规则1~6是根据空间形体的基本特征得到的,满足2#流形体的几何及拓扑特性,符合莫比乌斯法则,保证目标形体是拓扑有效的;规则7~13反映了制图原理和投影规则,保证目标形体的正投影与原三视图一致。
2.2提取面序列
由规则1~7可知,对于线框模型中的任意一条边,若仅有两个不共面的面片相交于此,那么这两个面片和该边应具有相同的状态特征,即在组合判定过程中同为真或假。
由此可推知,在所有候选面片中,相互间以流形边相连接的非共面面片的状态特征是一致的,因而这些面片就构成了一个面序列。
面序列在面组合判定过程中可作为一个单独的处理517
计算机集成制造系统
第10卷
对象。
从这个意义上讲,一个面序列拓扑同构于一个面片。
一个面序列的各面片之间以流形边相连,而其中各面片的非流形边构成了该面序列的边界,即成为拓扑同构面片的各边。
将面序列表示为三元组形式:
SF=(Fs,Es,En,其中,Fs为构成面序列SF的面片集;Es为面序
列中连接各面片的流形边集;En为面序列中的非流形边集,称非流形边为面序列的边界。
采用“以边定面”的面扩展处理方法来提取候选面片中的面序列,步骤如下:
(1将各候选面片和候选边中的各流形边标志为unexamined。
(2设置当前面序列中Fs=],流形边集Es=],非流形边集En=]。
(3若候选边中的各流形边均标志为exam-ined,则结束;否则,任选一标志为unexamined的流形边ei,提取与其相关联的两面片fi和fj,令FsQfi,FsQfj,EsQei,并将ei,fi和fj标志为e
xam-ined;(4判断面片集Fs中的各流形边,
若均标志为examined,则将Fs中的非流形边存入En,
当前面序列提取完毕,转到(2;否则,对面片集Fs中标志为unexamined的各流形边递归地进行如下判断处理:
%若与当前流形边ek相关联的两面片均标志为ex-amined,则将该边标志为examined,令EsQek;
&若Fs中仅存在一个与当前流形边ek相关联的面片且标志为examined,则从候选面片中提取另一关联面片fk,将边ek和fk标志为examined,并令FsQfk,EsQek。
提取面序列如图1所示,由图1a中的三视图生成图1b的形体线框模型,候选边集为{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,e18},提取面信息后得到候选面片{f1,f2,f3,f4,f5,f6,f7,f8,f9,f10}(如图1c~e。
其中的流形边有{e4,
e5,e6,e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,e18}
非流形边为{e1,e2,e3}。
令Ecs表示当前面片集Fs中面片的所有流形边的集合(包括标志为examined和unexamined的边,Eunexamined表示标志为unexam-ined的候选流形边集,Funexamined表示标志为unexam-ined的候选面片集。
(1首先将各候选面片和流形边标志为unex-amined
有Funexamined={f1,f2,f3,f4,f5,f6,f7,f8,f9,
},
e17,e18}。
从Ecs中任选一标志为unexamined的边,如e9,
提取另一关联面片f5,将e
9
和f
5
标志为examined。
由于f4和f
5
均标志为examined,则其相交边e17也
标志为examined,所以有
Fs={f1,f4,f5,f6}examined,
Es={e7,e8,e9,e15,e17}examined,
Ecs={{e7,e8,e9,e15,e17}examined,{e10,e11,e13,e14,e16,e18}unexamined},
Funexamined={f2,f3,f7,f8,f9,f10},
Eunexamined={e4,e5,e6,e10,e11,e12,e13,e14,e16,e18}。
从E
cs
中任选一标志为unexamined的边,如e10,提取另一关联面片f3,将e10和f3标志为exam-ined。
由于f1,f3和f5均标志为examined,则其相
交边e11和e
13
也标志为examined,所以有
Fs={f1,f3,f4,f5,f6}examined,
Es={e7,e8,e9,e10,e11,e13,e15,e17}examined,Ecs={{e7,e8,e9,e10,e11,e13,e15,e17}examined,{e12,e14,e16,e18}unexamined},
Funexamined={f2,f7,f8,f9,f10},
Eunexamined={e4,e5,e6,e12,e14,e16,e18}。
从E
cs
中,任选一标志为unexamined的边,如e12,提取另一关联面片f2,将e12和f2标志为exam-ined。
由于f1,f2,f4和f5均标志为examined,则其
相交边e14,e
16
和f
18
也标志为examined,所以有
Fs={f1,f2,f3,f4,f5,f6}examined,
Es={e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,e18}examined,
Ecs={{e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,e18}examined,{}unexamined},
Funexamined={f7,f8,f9,f10},
Eunexamined={e4,e5,e6}。
至此,Fs中f
1
f
2
f
3
f
4
f
5
和f
6
的各流形边均
标志为examined,因而得到一个面序列SF1,SF1=
(Fs,E
s
E
n
其中,
Fs={f1,f2,f3,f4,f5,f6},
Es={e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,
e18},
En={e1,e2,e3}。
由于E
unexamined
不为空,按上述方法继续提取面
序列,得到另一个面序列SF2,S
F2=
(F
s
E
s
En
其
中,Fs={f
7
f
8
f
9
},E
s=
{e
4
e
5
e
6
},E
n=
{e
1
e
2
e3}。
提取面序列后,最后剩下一个候选面片f10
。
由
于面序列S
F1
和S
F2
分别拓扑同构于一个单独的面
片,所以在后面的重建过程中,只需对S
F1
S
F2
和f10进行组合判定处理。
2.3检验确定性面序列
若一个面序列是最终构成目标形体的一个必需的面组合,则可将其视为确定性面序列。
通常,判断一个面序列是否为确定性面序列是困难的,但是根据规则8,如果某面序列被删除后导致投影信息不一致,则说明该面序列是不能被删除的,它应是一个确定性面序列。
因而,为了检验一个面序列是否为确定性面序列,需要对其进行投影匹配。
首先,为每个视图中的各投影线段设置一个投影计数器,记录该投影线段所对应的空间边的数目[6];然后,检测若将被检验的面序列删除,其中是否存在至少一条流形边使得在某个视图中对应的投影线段的投影计数器的值变为零。
若存在,则该面序列为确定性面序列,即它所包含的各面片及流形边必然属于目标形体上的实有元素,不能被删除,状态为“真”。
否则,说明该面序列中的面片和流形边是不确定元素。
2.4面判定、提取与组合
根据2-流形体的基本性质,面判定求解的过程实际上是消除非流形边的过程,因而面组合判定的切入点是面片中的非流形边,并且面组合判定首先从确定性面序列开始,即初选的非流形边应是确定性面序列的边界。
若候选面片中不存在确定性面序列,则任选一非流形边,把在非流形边上初选的面片称为当前扩展基面,其他关联于该边的面片称为候选扩展面,从候选扩展面中选定的与当前扩展基面进行组合的面片称为当前扩展面。
在进行面组合判定的过程中,每选择一个候选扩展面作为当前扩展面,都要应用前述规则1~13检验当前面组合的合法性,从而确定当前扩展面的状态(真or假。
判定过程如下:
(1令U为候选面片集,将U中各非流形边标志为unexamined,若U中含有确定性面序列,则将其各面片标志为True。
(2检测U中的各非流形边,若都标志为exam-ined,则结束。
否则,若U中含有确定性面序列,则选择其一条标志为unexamined的边界边e,并令该
面序列作为当前扩展基面f
。
若无确定性面序列,则选择一标志为unexamined的非流形边e,并从与
其相关联的面片中任选一面作为当前扩展基面f0。
(3在相交于非流形边e的候选扩展面中选择
一个未曾与f0组合过的面片作为当前扩展面f1,与
f0组合。
考虑下面几种情况:
%若f0为确定性面序列,且与候选扩展面都已组合过,则将非流形边e标志为examined,转(2;&若f
为确定性面序列,且其候选扩展面中存在一确定性面序列,则令该确定
性面序列为f
1
并将非流形边e标志为examined;’若f0为确定性面序列,且其候选扩展面为一般候
选面片,则任选一未曾与f0组合过的面片为f1;(
若f
为一般候选面片,其候选扩展面中存在一确定性面序列,且二者未曾组合过,则令该确定性面序列
为f1;若f
为一般候选面片,且其候选扩展面中
存在一对未曾组合过的确定性面序列,则转(2;2若f
为一般候选面片,且与其他候选扩展面都组合过,则转(2;3若当前非流形边e所关联的各面片之间均组合过,则将该非流形边标志为examined,转(2。
(4删除与当前非流形边e相关联的其他面片,并应用规则1~13对当前的面组合进行判断:
%检验被删除面片所对应的视图投影线段的投影计数器的值是否变为0,若为0,则转(3,否则,继续;&检测当前面组合中是否存在悬面,若存在,则将其删除并转%,否则,继续;’检测当前面组合中是否存在与现有合法面相交于内部的面片,若存在,则将其删除