（计算数学专业论文）reeb骨架图的扫描提取算法.pdf

大连理工大学硕士学位论文 摘要 随着计算机图形学的迅速发展对三维模型的研究日益深入。骨架作为形状表示的一 种有效形式在三维模型的各个领域中被广泛采用。b l u m 于1 9 6 7 年给出了骨架的最初定 义：骨架( 中轴) 是模型内部各个最大内切球中心的集合。骨架有一个g r a s s f i r e 的模型定 义，从模型表面开始点火，各个方向上的火的相遇点所构成的集合。因为模型的骨架很 好的保留了模型的拓扑连接性及其形态，所以经常被用于碰撞检测、三维动画、模型渲 染、模型表面重建、模型检索等应用中，也有研究人员采用骨架为模型的分解做矫正。 不同的应用，对于骨架应该保存的信息要求不完全相同，故而抽取思路也不完全相同。 在计算机辅助领域，r e e b 图常用来分析模型的等值面，s h i n a g a y a 等基于此原理分 析了牙齿模型在咀嚼过程中曲面的融合情形。r e e b 图还用来检索基于拓扑性相同的几 何模型。作为用户的交互性工具，r e e b 图用来选择模型的等值面。更多关于r e e b 图在 几何模型和可视化领域的应用可以参考a t f o m e n k o 等人所著的t o p o l o g i c a l m e t h o d sf o rv i s u a l i z a t i o n 。 最早提出使用r e e b 图来描述基于三角网格表示的二维流形骨架图是y s h i n a g a w a 等人，算法的时间复杂度为o ( n 2 ) ，n 为所有三角形中的边数。m h i l a g a 等人对该算法做了进一步改进，h c a r r 提出了时间复杂度为o ( n l o g 胛) 的算法，v p a s c u c c i 对三维流形的情形做了进一步分析，k r e ec o l e m c l a u g h l i n 分析了二维流形 情况下，r e e b 骨架图中鞍点的处理情形。 借助m o r s e 函数我们来实现二维流形的等值面，在每个水平集上分析l o o p s 的生成、 合并、消失。以及每个水平集上l o o p s 拓扑关系的处理和有用信息的提取。分析其相邻 水平集上l o o p s 的连通性，进一步叙述如何提取r e e b 图。 二维流形在m o r s e 函数映射下生成等值面，v z ，r ，对应一个水平集z ；，对每个水 平集上的l o o p s 作r e e b 结构图提取，最后将相邻水平集上的r e e b 结构图连接起来便得到 该流形的r e e b 图。 r e e b 图能较好的描述三维模型的拓扑结构形状，具有广泛的应用前景，可用于骨架 提取等本文给出了基于三角网格表示的离散曲面r e e b 图的扫描提取算法，详细分析了 算法流程，鞍点的处理，重点剖析了等高线树的变化规律。 关键词：r e e b 图；扫描算法；水平集；等高线树 r e e b 骨架图的扫描提取算法 r e e bg r a p h ss w e e p a l g o r i t h m a b s t r a c t r e e bg r a p h b a s e dm o d e l i n ga l l o wt h eb s e r sp r e c i s e l ya n di n t u i t i v e l yc o n t r o lt h em o r p h b e c a u s et h et o p o l o g i c a li n f o r m a t i o no ft h eo b j e c t s ，r 印r e s e n t e db yt h es t r u c t u r e so ft h er e e b 伊a p l l s ，i se x p l i c i ta n de a s yt ou n d e r s t a n d m o r e o v e r , t h ec o n t o u r so ft h er e e bg r a p h sa l s o r e p r e s e n t st h eg e o m e t r i c a li n f o r m a t i o no ft h eo b j e c t s s p e c i f i c a l l y ，w es t u d yr e e bg r a p h s ，w h i c he x p r e s st h ec o n n e c t i v i t yo fl e v e ls e t s t h e s e g r a p h sh a v e b e e nu s e di nt h ep a s tt oc o n s t r u c td a t as t r u c t u r e sa n du s e r - i n t e r f a c e sf o rm o d e l i n g a n dv i s u a l i z a t i o na p p l i c a t i o n s i nc o m p u t e r - a i d e dg e o m e t r i cd e s i g n , r e e bg r a p h sh a v eb e e n u s e dt od e s c r i b es u r f a c ee m b e d d i n g su pt oi s o t o p y a p p l i c a t i o n so ft h i si d e ai n c l u d et h e e v o l u t i o no ft e e t hc o n t a c ti n t e r f a c e si nt h ec h e w i n gp r o c e s s m u l t i - r e s o l u t i o nv e r s i o n so ft h e r e e bg r a p hh a v el e a dt od a t a - b a s es e a r c hm e t h o d sf o rt o p o l o g i c a l l ys i m i l a rg e o m e t r i cm o d e l s i nt h ei n t e r a c t i v ee x p l o r a t i o no fs c i e n t i f i cd a t a , r e e bg r a p h sa l eu s e dt oe f f i c i e n t l yc o m p m e l e v e ls e t s r e e bg r a p h sc a l la l s of u n c t i o na sau s e r - i n t e r f a c et o o la i d i n gt h es e l e c t i o no f m e a n i n g f u ll e v e ls e t s am o r ee x t e n s i v ed i s c u s s i o no fr e e b 莎a p h sa n dt h e i rv a r i a t i o n si n g e o m e t r i cm o d e l i n ga n dv i s u a l i z a t i o na p p l i c a t i o n sc a t lb ef o u n di nt o p o l o g i c a lm e t h o d sf o r v i s u a l i z a t i o n ，a t f o m e n k o y s h i n a g a w af i r s tu s er e e bg r a p h st od e s c r i b et h et h r e e - d i m e n s i o n a lm o d e l ， m h l a g aa n dh c a r rd e v e l o p e dt h ea l g o r i t h mf r o m o ( n 令t oo ( n l o g 甩) t i m e c o m p l e x i t y , nr e p r e s e n t a t i v et h en u m b e ro ft r i a n g l ee d g e s k r e ec o l e - m c l a u g h l i nd i s c u s st h e s i t u a t i o no ft w o d i m e n s i o n a lm a n i f o l ds a d d l ep o i n t w ea r ei n t e r e s t e di nt h et o p o l o g yo fs m o o t hf u n c t i o n sa sam e a l l st oa n a l y z ea n d v i s u a l i z ei n t r i n s i cp r o p e r t i e so fg e o m e t r i cm o d e l sa n ds c i e n t i f i cd a t a h e r e ，w eg i v ea n a l g o r i t h mt h a tc o n s t r u c t st h er e e bg r a p h si nd e t a i l s w ef o c u so nl o o p si nr e e bg r a p h sa n d s t u d yw h e n 也e yo c c u ra n dh o wt h e yc a nb ec o n s t r u c t e d ，w h e nt h es a d d l ep o i n to c c u ra n d d i s a p p e a r k e yw o r d s ：r e e bg r a p h s ；s w e e pa l g o r i t h m ；l e v e ls e t s ；c o n t o u r s n 一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：日期： 型翌隆臣二p 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 导师签名： 2 竺盘年上月上日 大连理工大学硕士学位论文 己i吉 jj 目 对三维模型骨架的研究由来已久，出现过很多方法，有的是源于对二维图像的扩展， 有的是针对三维模型提出的，大体上来说，有如下几类： ( 1 ) 基于拓扑细化技术。该类算法主要应用于采用体表示的模型上，通过不断地进行 不改变模型拓扑特性的体元素的削减来实现骨架抽取，因为模型的体表示数据量巨 大，所以整个过程比较耗时。g o n g 2 j 等人提出过一种并行细化算法，通过先定义模型 的简单顶点、删除谓词和两个细化元操作，在抽取算法中不断迭代两个元操作进行 模型细化； ( 2 ) 基于距离矩阵。它一般的计算对象要求也必须是体表示的模型，通过计算每个 体元素的距离来求取模型的脊点。s u n d a r n 等人提出过基于该思想的一个算法思 路，通过计算每个体元素到边界的最小距离来得到骨架点，s u n d a r 采用该算法创建 了一个模型检索系统： ( 3 ) v o r o n o i 图引入到三维骨架抽取。d e y 4 等人提出过一种利用v o r o n o i 图直接近 似中轴的算法。因为对三维模型而言只有部分v o r o n o i 顶点能够汇聚成骨架，所以 他通过定义角度和比例这两个与大小、比重都无关的筛选标准来实现它的中轴近似 算法，并证明该方法能够保证收敛； ( 4 ) 基于r e e b 图思想。该类算法首先在模型上定义一个连续函数，计算每个模型顶 点聚合成一个顶点，得到模型的骨架，其中著名的有h i l a g a 5 j 等人提出的m r g ， h i l a g a 定义的连续函数为顶点到整个模型表面所有顶点的最短距离与面积之积的 和。 ( 5 ) 基于模型分解。l i e n l 6j 等人观察到对于保存模型连接性的分解过程就是一个骨 架抽取的过程，所以提出了基于模型近似凸面体分解的骨架抽取算法，通过计算模 型表面的桥识别模型表面的凹地，计算每个顶点的凹陷性，并对模型按照凹陷性进 行分解，不断迭代该过程创建骨架。 ( 6 ) 其他类。m a 7 j 等人提出过基于可见互斥力的骨架抽取算法，它应用了物理学上 的互斥力的概念来计算模型上的平衡点，最终得到模型的骨架。 本文主要论述了基于r e e b 图思想的骨架抽取算法及其应用。 r e e b 骨架图的扫描提取算法 1 模型预处理 随着计算机图形学的迅速发展，对三维模型的研究日益深入。骨架作为形状表示的 一种有效形式在三维模型的各个研究领域中被广泛采用。b l u m t l 】1 9 6 7 年给出了骨架的 最初定义：骨架( 中轴) 是模型内部各个最大内切球中心的集合它还有一个g r a s s f i r e 的模 拟定义，从模型表面开始点火，各个方向上的火的相遇点所构成的集合因为模型的骨架很 好的保留了模型的拓扑连接性及其形态，所以经常被用于碰撞检测、三维动画、模型渲 染、模型表面重建、模型检索等应用中，也有研究人员采用骨架为模型的分解做矫正。 对于不同的应用，骨架应该保存的信息要求不完全相同，故而抽取思路也不完全相同。 一般采用r e e b 图进行骨架抽取的思路，都将计算对象放在模型的顶点上，而后根 据顶点的函数值计算其所在面片落入的各个函数值区间，进行骨架创建。黄坤武【2 】等人 提出针对面片的r e e b 图骨架抽取算法，用于三维检索的特征描述符。模型的面片和骨 架之间存在着某种映射，并从寻找这种映射出发，提出了一种针对模型面片进行直接骨 架抽取的算法框架。首先定义模型面片之间的距离计算方法，创建模型的对偶图，然后 在该对偶图上应用r e e b 图的计算思想，在对偶顶点上定义一个连续函数并计算每个顶 点的函数值，最终根据计算得到的函数值以及顶点对应的面片之间的邻接关系创建模型 的骨架。 1 1 网格细分 算法建立在对模型面片的计算基础之上，所以面片的规则性非常重要。模型预处理 的目标就是使得其面片都比较规则，即所有面片都近似等边三角形。考虑两种不同的预 处理方法，第一种是边切分，将长度大于用户指定阈值的边进行不断切分；第二种是自 适应的网格细分技术，将满足一定条件的面片进行细分，不满足条件的进行保留。 如图下图所示，其处理过程就是不断地寻找大于阈值的边进行切分。注意，切分时 新添加的边可能必须进行再次切分。 大连理工大学硕士学位论文 a 。岛e b 图1 1 1 边切分 f i g 1 1 1s u b d i v i d ee d g e b 如下图a 所示，若面片a b c 包含两条边1 4 b i ，1 4 c i 均大于阈值( 也可能只有一条边 大于阈值) ，b 图为细分后的结果。 ( a ) 细分前( b ) 细分后 图1 1 2 面片细分 f i g 1 1 2s u b d i v i d e 吼l 出c e 处理方法为：计算面片_ 鼻l b c 上边顶点h ，g ，i 的坐标，而后添加三个顶点，删除 面片a b c ，添加面片a g h ，h i c ，h g i ，g b i ，递归的修改相应的相邻面片的信息。以 h 点为例，该边顶点的计算方法为： 万：! 匕鳌丘竖 爿 8 k 的坐标是通过与该边相邻的两个面片的四个顶点进行加权计算的，所以它将可 能不落在边a c 上，这样细分后的面片将更加的平滑。由于采用了自适应的策略，所以 面片b d c 边长都小于一个阈值不需细分但因相邻面片被细分故被切分成了b d i ，i d c 。 根据l o o p 细分的策略，它可以无限的循环细分下去，只是必须考虑到细分后的时间复 杂度。对于不同的模型，因为创建的分辨率不一样，所以细分的次数是不一致的，必须 在实际应用中加以控制。另外必须注意的是添加面片时顶点的顺序必须保持与原来面片 的顶点顺序一致。另外，本文算法并没有如l o o p 细分中一样重新计算、的 新坐标，是考虑到可能会剧烈修改原有模型的表面特性。 r e e b 骨架图的扫描提取算法 采用细分技术处理的模型，面片比较均匀，虽然模型中可能还包含有大于阈值的边 存在，但已经比较均匀。主要是因为： ( 1 ) 模型的因素，模型局部网格不够均匀，比较多的面片不够规则； ( 2 ) 细分是并非简单的取现有平面上的顶点，而是进行了新顶点的拟合，改变原有 的面片法向矢量； ( 3 ) 细分引入的边都比较均匀，创建的面片就均匀； 所以当模型的某个区域包含较大数量不够均匀的面片时，采用曲面细分进行预处理 的效果要略好于边的切分，但是如果模型本身已经比较规则，只有少量面片不规则时， 那么采用边切分进行模型预处理将可能有着比面片细分更好的计算效率和效果。 一4 一 大连理工大学硕士学位论文 1 2 l o o p 细分 细分算法的最大优点是它能够从任意的初始网格出发产生光滑的曲面。目前的细分 格式大体上分为两类：逼近型和插值型。逼近技术是一种收缩方法，不能对曲面进行有 效的控制，而对曲面进行有效的控制是曲面设计与特征动画的关键问题。相比较而言， 插值技术保持初始网格顶点不变。但曲面的光顺性很难控制。通过引进物理模型对逼近 型细分曲面的控制顶点进行控制，调节物理模型中的不同参数，可以获得不同的细分曲 面，增强细分算法的生命力。 细分曲面( s u b d i v i s i o ns u r f a c e ) 是一个网格序列的极限，网格序列则是通过采用一 组规则( 一般是加权平均) 在给定初始网格中插入新顶点并不断重复此过程而获得的。 从1 9 7 8 年c a t m u l l 和c l a r k 提出的基于双三次b 一样条曲面的c a t m u l l c l a r k f 8 】细分模式 以及d o o 和s a b i n 提出的基于双二次b 一样条曲面的d o o s a b i n t 9 】细分格式以来，大量 的细分模式及其改进涌现出来，同时，细分曲面造型方法的应用也得到了广泛的推广。 细分算法大体上可分为三类：一类是通过修改细分规则来控制细分曲面的形状；通 过标记不同种类的控制顶点，然后对标记的控制顶点采用不同的细分规则，可以使细分 曲面保留棱角、折痕等几何特征。结合逼近、插值的思想来构造细分规则，使得细分曲 面能够保留一定的形状，并且具有一定的光滑性。有文献提出半静态回插细分方法，可 以在不改变控制顶点的情况下，构造出从逼近到插值控制顶点的一系列曲线曲面。把传 统的均匀细分格式推广到非均匀细分格式，为使用者提供了一种能够控制曲面特征的方 法。修改细分规则来使细分曲面的边界或者内部满足法矢约束，极大的提高了对曲面的 控制能力：另一类使通过对初始网格进行处理，然后施加标准的细分规则，使细分曲面 基本上能保持初始的形状并具有一定的光滑性。也可以对初始网格施加新的剖分，然后 对剖分后的网格进行标准的细分，达到保形的目的；第三类是通过直接操纵极限曲面来 控制细分曲面。把细分曲面嵌入到基于物理模型的框架中，通过对细分曲面施加力的影 响来控制极限曲面，提供直接操纵细分曲面的交互式工具。 1 2 1l o o p 细分曲面 l o o p 细分模式是由1 9 7 8 年u t a h 大学的l o o p 在硕士论文中提出一种基于c2 四次 三角形b 一样条的细分模式，l o o p 细分模式生成的曲面是箱式样条曲面的推广。 5 r e e b 骨架图的扫描提取算法 l o o p 细分模式式基于三角形网格的逼近细分格式，我们把初始网格中的内部价为 6 ，以及边界价为4 的顶点称为正则点，否则称为奇异点。每次细分在每条边插入一个 新顶点，则每边一分为二，每个三角形一分为四。我们称那些插入的新顶点为：e 一顶 点，而原来的顶点称为：v 一顶点。每次细分不但要计算e 一顶点，而且要修改v 一顶 点。顶点的计算如下： ( 1 ) 内部e - 顶点：设内部边的两个顶点为v o ，k ，共享此边的两个三角形面为v o ， v l ，和v o ，k ，屹，则e 一顶点为 = v o + k ) + 吉( 圪+ ) ( 2 ) 边界e 一顶点：设边界边的两个顶点为v o ，k ，则e 一顶点为 = ( + k ) ( 3 ) 内部v 一顶点：若内部顶点v 的边邻点为v o ，k ，圪，其中1 3 = l v i 。，则 相应的v 一顶点为： k = ( 1 - n p ) v + ，形 即顶点本身与其所有相邻顶点的加权和，它本身的权值为1 一刀，而邻点权值为 = i 1 ( 甚5 一虿3 + 百1c 。s 2 甩, b 2 ) ( 4 ) 边界v 一顶点：若和顶点v 相连的两条边界边的顶点为v o ，k ，则v 一顶点为 k = 吾+ 三矿+ 吉k 端点 3 8 1 8 1 8 ( a ) 内部e 顶点 3 8 p 8 ( b ) 内部v 顶点 _ - 卜- 一 1 2 1 2 = = 儿 1 1 8 3 41 8 图1 2 1 模板 一6 1 8 ( d ) 边界v 顶点( e ) 带边界 大连理工大学硕士学位论文 r l g l 厶ll e m p z a e s l o o p 细分模式生成箱式样条，在正则点处是c 2 连续的，而在奇异点处是c 1 连续的。 对于开网格，边界e 一顶点采用上图d 的模板计算。为使曲面在边界处光滑，需要修改 以边界点为端点的内部边e 一顶点模板的权值，如上图e 所示，其中乃= i 1 ，y ：= 互1 或 ：! 一! c o s 旦，托：! + ! c o s 旦，n 为边界点的邻边数。另外，满足 乃5 i 一一4c o s i j 托2 孑+ 一4c o s n - 1 n 为边夼启、酮邻迈致。力罗卜 7 两疋 扣c o s 争 4 时，2 s m 告( 以) + ( 2 哪刍_ 2 ) ；s i n k刀一l，2 一l_ 7 r e e b 骨架图的扫描提取算法 1 3 简化的动态模型 1 3 i 动态方程 利用离散弹簧粒子模型来建立拉格朗日动态方程。对于给定网格的控制顶点的移动 可用下列方程【1 0 1 1 】来描述： m 一+ 月，z + g ，= f ，( f = 0 ，1 ，) 其中鼍( x ，y ，z ) 为输入网格的控制顶点的三维坐标，x ，x 分别为置对t 的二阶、一 阶导数。肘。代表质量，r ，代表阻尼系数，g 为和墨相邻的顶点通过弹簧作用的合内力， f 为施加于顶点x i 的外力。 为了简化该动态模型，在这里取m ，- - 0 ，r i = l ，( i = 1 ，n ) 则方程可简化为 置= 只一g j ，( 江1 ，) 运用e u l e r 法解该方程可得： x h 出= ( f g j ) 出- i - x t ( 汪1 ，) 其中出为时间间隔。 1 3 2 内力、外力的定义及计算 施加于定点x ，的内力可用它和它相邻的，用弹簧连接的顶点x j 来表示为 1 0 , 1 2 瓯2 衙q 其中c ，为弹簧的倔强序数，= 忙。卜乃表示弹簧的形变长度，r ，= x ，一，l i i i 是 向量长度算子，屯为弹簧的自然长度，施加于顶点x 。的合力可表示为： k s i = s j k 为顶点x 的价。 大连理工大学硕士学位论文 1 4l o o p 细分曲面控制算法描述 算法的基本思想：从网格m 佃到网格m t 州可以划分为两步操作：第一步称为网格 加细，通过网格加细可以得到网格m ( 肿1 中所有顶点的连接信息，但不确定顶点的具体 位置；第二步操作为顶点放置，计算顶点的实际位置。从第二步出发，把l o o p 细分规 则同物理模型结合起来计算新顶点的位置。 1 4 1 算法流程 ( 1 ) 首先对给定的初始网格按上一节介绍的l o o p 细分规则进行一次细分，判断网格 是否为开网格。 ( 2 ) 对l o o p 细分一次之后的控制网格顶点采用物理模型来计算细分一次后最终的顶 点位置，具体算法如下： 对每个顶点，考虑其邻域，在其邻域中计算顶点x ，和顶点彳相邻边的长度 月u = i x 。一x i ( = o ，1 ，m ) ，m 为在x ，的邻域中和x 。相邻的顶点的个数。 计算每个顶点的单位法矢。由于输入的数据是三角形网格，是一种离散结构， 我们利用和顶点x ，相邻的面的单位法矢“，j = ( o ，1 ，聊) 的和作为该顶点的法矢。 对每个顶点x j f ( f 为形变区域的内点集合) ，令x ，在t 时刻的坐标为形， 计算顶点x ，的内力g ，外力e = h i ；计算新点位置“。 对新产生的顶点进行光滑处理。 为了网格的光滑性，在移动中保留正则点的分布是重要的。采用l a p l a c i a n 光滑算子去除顶点的非正则性。 把新产生的顶点按l o o p 细分的连接原则进行连接。 ( 3 ) 对新网格进行l o o p 细分，重复( 1 ) 、( 2 ) 两步，直到得到光滑的细分曲面。 1 4 2 约束条件 利用约束条件控制网格形状，根据应用的需要可以考虑各种约束条件。 ( 1 ) 顶点位置约束：在网格顶点移动过程中固定某些顶点的位置不变。 9 r e e b 骨架图的扫描提取算法 c 点害烈 这里( x ，y ，z ) 为顶点v 的坐标，n 为顶点v 的一邻域d 的顶点数，( x ，y j ，z j ) ， ( x ky 。，乙) ，1 歹，k 抑，为d 中任意两个顶点。对网格点进行操作，计算各层网 1 4 3 参数设定 ( 1 ) 令在顶点移动中，施加于各顶点最大内力为g m 。，为了使顶点沿着合力方向移 动应保证外力删大于内力，即g h ，栅 删。另一方面，为了使顶点平滑的移动， 对于时间步长的每次迭代，设定顶点的最大移动位移d 耐，当内力为0 时： k 刚垒争。这里d 一= m a x l i x h & - x 。0 为最大位移，最大内力g 而咖，由弹簧原长 乃来确定。 ( 2 ) 在参数c 一乙、a t 、五中，时间步长址对于顶点的控制起着主导作用，a t 【o ，1 】 时，会取得比较理想的细分曲面。参数f 一，一五根据出的取值，具有微调细分曲面的 作用，可拉伸、收缩细分曲面。 1 5小结 本章介绍了模型的预处理，使用l o o p 网格细分算法，来保证模型网格的均匀性。 为下一步模型的骨架提取做准备。 大连理工大学硕士学位论文 2 等高线 等高线在地图中常用来描述地貌形态，在等高线地图上，所有的地形信息都正交的 投影在水平面上。本章介绍等高线的相关知识，在r e e b 扫描提取骨架算法中，在每一 个水平集上就是对等高线的处理。 2 1 等高线空间关系的类型 等高线空间关系在计算机中表达之前，首先要对其描述，即将等高线空间关系加以 分类。 一般认为，二维平面上的要素之间存在3 种空间关系，即拓扑关系、顺序关系和度 量关系。比较而言，拓扑关系在等高线关系中应用最广泛，按照c l e m e n t i n e 的最小拓 扑关系集理论，将等高线视为线目标，则等高线拓扑关系只有一种一一相离关系；若将 等高线视为面对象，则等高线拓扑关系分为两种一一包含和相离关系，相邻关系可以看 作是一种邻近关系。 根据等高线的拓扑性质和高程属性，可将等高线空间关系分为四类。 1 ) 包含关系 若一条等高线位于另一条等高线所形成的区域内，则称后者包含前者； 2 ) 并列关系 若两条等高线高程相等，则称二者为并列关系； 3 ) 第一类并列关系 若两条等高线为并列关系，且被同一条直接邻近的等高线所包含，则称二者为第一 类并列关系； 4 ) 第二类并列关系 若两条等高线为并列关系，但未被同一条直接邻近的等高线所包含，则称二者为第 二类并列关系； 2 2 等值点位的寻找 为了计算等值点在网格边上的位置，首先要确定等值线与网格边相交的条件。设等 值线的值为z 。，显然，只有z 。处于相邻网格点值之间，该边上才有等值点。判断条件 为： r e e b 骨架图的扫描提取算法 ( z 。z 。) ( z b z 。) 0 和( z 。- z 。) ( z 。一z 。) = 0 。 前者说明该边上没有等值 点，后者说明等值点穿过其中一个端点，这时可将该端点的点值加上一个微量，防止等 值点追踪时出现二义性。 等值点的位置均用线性内插值得，即 x c = x 。+ 二_ _ = 生( 一x 。) y，=y。+三a一yo)yy(ybyf2 口+ l 生 一 2 b z 口 为了便于等值点得追踪，选择有效得点位记录方式是重要得。在规则网格中，每个 网眼均用左下角点得行列号表示，这样可设计等值点。在三角网格中，要设置两个二维 数组x b ( i ，j ) 、y b 0 ，j ) 来存放等值点。i = 1 ，2 ，3 表示三角形的三条边；j = 1 , 2 ，3 ，k ，表示 三角形的号数。如果边棱上无等值点则赋于零。 2 3 等值点的追踪 等值点的追踪就是将同一支等值线上的点有序地连接起来，具有z ，值的等值点可能 组成一条或几条等值线。无论哪种等值线，都必须找出起始等值点，称之为线头。闭曲 线的起始点一定位于制图区域内部，即内部的任一等值点均可作为等值线的起点和终 点；开曲线一定是开始于制图区域的边界而又终止于边界，所以它的起始等值点和终止 等值点一定位于边界上。这是建立等值点追踪方案的基本出发点。 不同的网格其追踪方式不相同。对于规则网格来说，由于等值点位于网格边上，所 以等值线通过相邻网格的走向只有四种可能：自上而下、自左至右、自下而上、自右至 左，为了确定曲线进入的边是上下边，还是左右边，可分别建立一些判断条件。设曲线 进入该边之前与某边棱的交点为a ，与该边棱的交点为口，则依次下p t j n 序判断： 如果f 。 f 一则自下而上追踪； 如果j ，。，则自左至右追踪；a 大连理工大学硕士学位论文 如果i n t ( x 。) x 。，则自上而下追踪； 不满足上述三个条件，一定是自右至左追踪。 综上所述，追踪等值点是在任意两个相邻网格进行的，而建立追踪方案的前提条件 是要知道a ，和a ，点的位置。对于开曲线，可把在制图区域边界上寻找的等值点作为第2 点，根据其实际情况假定一点作为a ，点，并使其满足上面条件之一开始追踪第3 点，然 后把找到的第3 点作为第2 点，原来的第2 点作为第1 点，再追踪新的第3 点，直至终 点。每追踪一点都要从原始数据场中将此等值点抹掉，以免重复。当网格边界上无任何 等值点时说明这些等值点可能形成的开曲线已跟踪完，此时再在内部寻找闭曲线的线 头，找到以后按开曲线方法建立追踪方案，只不过在抹去原始数据点时开始不能将第1 点抹去，否则曲线不能闭合。 规则格网法中，当两条具有相同值的等值线落在同一方格内( 即某一网格四条边棱 上都有某一值的等值点) 时会引起不确定性，其连接方式有三种可能，如果碰到这种情 况，只要在算法中避免第三种情况出现。 三角网中的等值点追踪算法与规则网格法不同，这是因为内插等值点是以三角形为 单位的，这就使相邻三角形公共边上的同一等值点计算过两次。如果等值点不是边界点， 则这些点即是第一个三角形的出口点，又是下一个三角形的入口点。如果等值点位于边 界上，它们只能是入口点或者出口点。因此，在确定了某条等值线的起点后，就不难建 立起追踪的算法。由于确定一个等值点是否是边界点，计算较麻烦，所以不必在追踪前 就区分是闭曲线还是开曲线，而是经跟踪后确定。算法是，首先按三角形序号的顺序去 搜索，当在某序号三角形中找到一个等值点后将其坐标记录在另外两个变量中并从原始 数据场中抹去，然后，把这一点作为等值线在这个三角形内的入口点，那么该三角形必 然存在的另一个等值点就是这个三角形的出口点。利用坐标比较可在另一个三角形边上 找到与此坐标相同的一个等值点，它便是该等值线在新三角形内的入口点，再利用坐标 比较，如果相同就是闭曲线，否则就是开曲线。若是开曲线，则将已跟踪的等值点坐标 倒排序，利用已记录的起始点作为出口点继续搜索，直到发现另一个线头。要注意的是， 在追踪时应追踪一点记录一点，并累计计数，追踪过的点都要从原始的等值点数据场中 抹去，以免重复追踪。 r e e b 骨架图的扫描提取算法 2 4 基于扫描线的等高线树生成法 等高线树在地图的产生、地形分析等应用中具有较重要的应用。对于产生等高线树， 提出了一种基于扫描线的方法，该方法把扫描线和等高线之间的交点对解释为区域，利 用区域之间的包含关系对应等高线之间的包含关系，以这种方式来确定父等高线与子等 高线之间的“一对多直接包含关系。与其他方法相比，该方法较容易理解与实现，且 执行速度较快。 等高线树被用于反映等高线之间的拓扑关系及相对高差等信息，在各种地形地貌 ( 山顶、山谷) 的识别，高程的自动标定和检验等过程中，均需要以等高线树为基础进行 判别。等高线树生成的关键点是如何判断等高线之间的包含关系，现有的方法有几何计 算生成法、区域扩张生成法和基于v o r o n o i 内邻近的等高线树生成法。基于扫描线的生 成法不需要等高线的高程值，即可产生等高线树。 2 4 1 相关研究 几何计算法的核心是在根据高程将等高线分层的基础上，利用几何算法直接识别等 高线包含关系。首先根据高程值将等高线归入不同的层，然后识别等高线直接包含关系。 执行过程如下图所示，使用这种方法时，当等高线高程未知或错误时无法进行；其次， 确定包含关系需在相邻高程对之间一一进行，当等高线数量较多或复杂时，该方法效率 较低。 努谚 疆 蜉 姒 酶霉妻 大连理工大学硕士学位论文 图2 4 1 1 几何计算法生成等高线树 f i g 2 4 1 1g e o m e t r yc o m p u t i n g 区域扩张法的基本思路是将等高线图象进行扩张，如果扩张边界相交，则说明两条 等高线邻近。将公共边界的长度作为邻近关系的权重，这些权重值最大的等高线被视为 具有直接包含关系。由于应用邻近关系的权重判别包含关系存在理论缺陷，实际应用中 会产生一些错误的判断；此外，通过该方法识别包含关系的效率较低。 图2 4 1 2 区域扩张法 v o r o n o i 内邻近生成法 1 3 , 1 4 1 分为三个步骤： ( 1 ) 生成等高线的v o r o n o i 图； ( 2 ) 识别等高线基于v o r o n o i 图的一阶邻近关系； ( 3 ) 从地形图上最外围等高线开始，逐个识别每条等高线的全部子等高线，作为树的 各个结点。这种方法不需高程值即可获得等高线树，但要对每条等高线图求其 v o r o n o i 区域，如下图所示，该操作较费时；然后依据v o r o n o i 图的阶邻近关系确 定等高线之间的包含关系，所以说这种方法的效率较低。 图2 4 1 3v o r o n o i 内邻近生成法 r e e b 骨架图的扫描提取算法 2 4 2 等高线树生成方法 等高线满足两个性质：一个是等高线不能相互交叉：二是等高线自我闭合或边界闭 合，边界闭合作为自我闭合的一种特例进行处理。因为等高线不相交且闭合，所以其具 备一种性质，当用扫描线( 一条较长的竖线) 与图形中等高线执行相交检查时，内层等高 线与扫描线的交点位于交点序列的内部，外层等高线与扫描线的交点位于交点序列的外 部，如下图所示，扫描线3 与等高线图的交点序列( 从下到上) 为：等高线1 点、等高线 2 点、等高线3 点( 此处看作两点) 、等高线2 点、等高线1 点，这种对称性质，借助辅 助堆栈即可解释等高线之间的包含关系。 事 等 等 等 h 、 、 ；|。 i ： - 一一 ， 、 、 彭 矿 u 。 i 一_ 。、 絮遵 f，。c 、 ； 卜- 眨 、 孑 。、，l l 一 卜 、 、 | 舅 、 父 。 睾：l 徜乡笼：l234 567 g91 01l1 2 图2 4 2 1 扫描线生成法 f i g 2 4 2 1s w e e pa l g o r i t h m 初始时，顺序读入各条等高线，计算每条等高线的最左下点和最右上点，把这两点 放入一个事件队列中，该队列依据x 坐标从左到右有序排列，并计算图廓的最小和最大 y 坐标，作为扫描线两端点的y 坐标。事件队列中每条等高线的两个点实际指示等高线 的活动区间，循环遍历事件队列。执行中，( 1 ) 对于事件队列中的一个点，判断其所属的 等高线和属于等高线两点中的哪个点，若为最左下点，该等高线位置为活动状态；若为 最右上点，该等高线置为非活动状态；依据该点x 坐标设置扫描线两端点的x 坐标。( 2 ) 检查扫描线与处于非终止状态等高线的交点，有序存入结果集。( 3 ) 借助辅助堆栈解释结 果集中交点序列，保存结果，置非活动状态等高线为终止状态。下面给出其算法： v o i dc o n t o u r t o p o ( c o n a r r a yc o n t o u r s ，i n tn ) c o n t o u r s 表示等高线数组，n 表示等高线个数 f o r ( i n ti = 1t on ) 大连理工大学硕士学位论文 对于每条等高线，求其最左下点和最右上点，结果插入事件队列； 更新扫描线上下两点的y 坐标； 事件队列中点从左到右有序排列： w h i l e ( 事件队列非空) 弹出事件队列中首点赋点e ，依据e 的x 坐标设置扫描线的x 坐标；初始化结果集和辅助堆栈； i f ( e 为等高线的最左下点) 设置e 所指等高线为活动状态； e l s e 设置e 所指等高线为非活动状态； 检查扫描线与处于非终止状态等高线的交点，有序存入结果集： 借助辅助堆栈解释结果集中交点序列，保存结果： 置非活动状态等高线为终止状态； ) 2 4 3 特殊情况的处理 由以上可知，扫描线与等高线的交点，实际上成对表示其所跨越的区域，交点必须 为偶数，计算结果直接影响其后的等高线树。在实际计算扫描线与等高线的交点时，需 要注意下列情况：。 ( 1 ) 扫描线与线段的端点相交 分为两种情况，如图3 2 的点a 和点b 所示。 当检查扫描线1 与等高线1 的相交情况时，其与等高线1 的两条线段相交于端点a ， 其两条线段均位于扫描线的一侧，结果输出为两个交点a a ，即其跨越区域为a a ，区 间宽度为0 。 当检查扫描线7 与等高线3 的相交情况时，其与等高线3 的两条线段相交于端点b ， 其两条线段位于扫描线的两侧，表明扫描线在此处穿过等高线3 ，结果输出为一个交点 b 。其与下边的端点c 成对，跨越区域为c b 。 ( 2 ) 扫描线与垂直线段相交 分为两种情况，如图3 2 的垂直线段d e 和g h 所示。 当检查扫描线8 与等高线l 的相交情况时，其与垂直线段d e 重合，且与垂直线段 相连的两条线段位于扫描线8 的两侧。此时依据等高线与扫描线的相交情况，选择输出 1 7 r e e b 骨架图的扫描提取算法 e e d 或e d d 。图3 2 中，选择e e d ，扫描线8 和等高线1 的相交形成两个区域f e 和 e d 。 当检查扫描线1 2 与等高线l 的相交情况时，其与垂直线段g h 重合，与垂直线段 相连的两条线段位于扫描线1 2 的一侧，选择输出g h ，其跨越区域为g h 。 ( 3 ) 边界闭合等高线 对于边界闭合等高线，由于此类等高线的两端点位于图廓边上，不闭合，所以应通 过添加点线的方法使其闭合。此类等高线把整个图形分为两个区域，应用多边形面积计 算方法，分别计算两个区域的面积，选择面积较小的区域来添加点线。图形边界通过添 加点线闭合后，使用扫描线方法处理时，导致扫描过程中会产生重复的点，需要在结果 集q 和辅助堆栈s 中对加标记的等高线作特殊处理，才可以确定其包含树。 2 5小结 本章首先介绍了等高线及其提取，然后介绍了等高线树，对于等高线包含树的建立， 扫描算法提出了一种方法，依据扫描线与等高线的交点来确定其区域，进而确定其包含 关系；一般扫描线方法中是每条线段提供两个事件点，扫描算法是每个闭合等高线多边 形提供两个事件点，即多边形区域的最左下点和最右上点，以加快扫描线方法的执行。 由于扫描算法在执行过程中不需要等高线的高度，且执行速度较快，所以在模型的骨架 提取等众多领域具有较强的应用价值。 大连理 大学碗七学位论文 3 r e e b 骨架图的扫描提取算法 31 引论 在计算机辅助领域，r e d o 图常用束分析模型的等值面 1 ”，s h i n a g a y a 等“基于此原 理分析了牙齿模型在咀嚼过程中曲面的融合情形。r e e b 图还用来检索基于拓扑性相同 的几何模型m 】。作为用户的交互性工具，r e e b 图用来选择模型的等值面【8 i 。更多关于 r e e b 图在几何模型和可视化领域的应用可以参考【l ”。 最早使用r e e b 图来描述基于三角网格表示的二维流形骨