（模式识别与智能系统专业论文）分支结构的建模和采样.pdf

摘要 摘要 具有分支结构的物体是自然界普遍口j 见的物体之一，由于其几何结构和拓扑结构的复 杂盹，具有分支结构的物体一直是计算机图形学领域研究的热点和难点之一。传统的建模 雨i 可视化方法主要集叶1 在用参数| l 甫和隐式曲面两种，前者沣重快速的全局绘制，忽略了 分支处的细节；后者虽然能很好地表现分支结构的局部细节，到不易快速绘制。 本文针对分支结构建模和可视化进行了伞面的研究，在采埘隐式曲面的方法作为分支 结构建模上具时，提出了对建模的隐式曲阿进行点采样的方法，兼顾考虑了分支结构建模 过程中的局部细节和快速绘制的两方面问题。本文的主要工作和贡献有： 针对分支物体结构复杂、具有一定白相似度的特点，提出了一种基于子结构的点采 样方法。通过将分支系统分解为一系列具有等级的了= 结构，继而简化为基本单枝的 线性组合，降低了系统结构的复杂度。同时，在底层创建了一个基本单枝的采样点 库，通过高层的复制、变换等操作，直接获取整个系统的采样点。该方法通过缩减 底层的直接采样目标，避免了对整个分支结构进行采样而产生的速度慢、参数难蛹 等问题，提高了点采样的速度，同时充分利用已采样的子结构，避免对与其相同或 者相似的结构进行采样的重复工作，从而进一步提到了点采样算法的效率。 利用隐式曲而易融合的特性，对分支区域内的分支粒子提出进行融台操作的方法， 分别对椭圆融合、缩减骨架、超椭圆融合等方法进行了实现和深入的分折比较， 虽后粟取了修正的超椭圆融合方法，通过分辩两骨架相交所形成的不同“凹”、 “凸”区域，分别对分支粒子采取不同的融合方法，使分支粒予最终可以重新移动 到分支之间光滑连接的融合曲面上同时不引起额外的“膨胀”部分。 研究并实现了一个基于子结构的点采样软件，该软件可以根据输入的分支结构的骨 架文件，快速获得融合后的整个分支系统的采样点信息并给予显示。 总的说来，本文在针对一类特定( 基于骨架、具有等级) 的分支结构的建模和点采样工作 中做了一些有益的探索。 关键词：分支结构，隐式建模，点采样，子结构，等级结构 第i 页 英文摘要 a b s t r a c t r a 柚i n e do b j e c t s ，o n ek j n do fu b i q u i t 0 1 1 5o b 】e c t s ，c o m p o s eag r e a tc h a i l e n g e i nc o m p u t e rg r 印h i c sd u et ot h e i rc o m p l e xt o p 0 1 0 9 i c a la n dg e o m e t r i cs t r u c t u r e 8 t a d j t i o n 出m e t b o d sf o rm o d e l l i n ga 朋dv i s u a l i z i n gr a m i 是e do b j e c t sc a nm a i n l yb e d i v i d e di n t ot w ok i n d s o n ei sb a s e do nt h ed a r a m e t r i cs u r f a c e w h i c hf o c u s e so n t h ef a s tg l o b a lm o d e l l i n ga 丑dv i s u a l i z a t i o nw h i l ed o e s n tc a r et o on l u c ho nl o c a l d e t a i l si nr a m m c a t i o mt h eo t h e ri sb a 5 e do nt h ei m d l i c i ts u r f a c e w h i c hs h o w s u n m a t c h e da d v a n t a g e si ng e n e r a t i n gs m o o t hb l e n d i n gs u r f a c ew h i l eh a v ed i 佑c u l t y i r e a l t i m er e n d e r i n g ， t h r o u g hg e n e r a l r e s e a r c hf o rm o d e l l i n ga n dv i s u a l i z i n gr a m m e do b j e c t s b o t h c o n s i d e r i n gt h el o c a ld e t a i l si nr a m i f l c a t i o na n dt h ef a s te l o b a lr e n d e r i n g ，w ea d o p t a ni m p h c i t l ym o d e m n gm e t h o da n dp r o p o s eap o i l l ts a m p l i n ga l g o r i t h m ，t h e m a i nw o r k sa 工l dc o n t r i b u t i o n so ft h i st h e s i sa r el i s 钯da sf b l l o w i n g ： d u et or a m m e do b j e c t sh a i n gc o m p l e xs t r u c t u r e sa n ds e l f 8 i m i l a r i t yi nc e 卜 t a i nd e g r e e ，r ep r o p o s ea8 u b s t r u c l u r e b a s e dp o i n ts a m p l i n gm e t h o d b y r e c u r s i v e l vd i v i d i n gt h e h 1 1s y s t e mh n oas e co f8 u b 8 t r u c t u r e sw i t hc e r t a i n o r d e r sa n df i n a l l vi n t ou 1 el i n e a rc o m b i n a t i o no fb a s i cb r a n e h e s t h e8 t r u c t u r ec o m p l e ) ( i t yh a sb e e nr e d u c e dm e a n w h i l e ，w eb u i mu pas 啪p l i n gp o i n t l i b r a r vf o rb a 8 i cb r a n c l l e 8i nt h el o wl e v e l a n dg e tt h es a m p l i n gp o i n t sf o rt h e f u l ls y s t e mb yc o p y i n g ，t r a n 8 f o r m i n go p e r a t i o n 8i nt h eh i g h1 e v e l s i n c et h i s m e t h o ds h r i n l 【s8 n ds i m p h 丘e st h es a m p l i n gt a r g e ti nl o wl e v e l ，i ts p e e d su p c h es 锄p l i n gp r o c e s sa n ds o l v e st h ep r o b l e mo fc h o o s i n gp a r a m e t e r sw h e n w ed i r e c t l vs a m p l et h ef l l l ls v s t e m a d d i t i o n a l l y t h ea p p l i c a t i o no fs u b s t r u c t u r e sh e l p st oa v o i dt h er e p e t i t i o u sw o r k sf o rm o d e l l i n ea n ds 眦p l i n g t h es a m eo rs i m i l a rs u b s t r u c t u r e s ，s oi tf u r t h e ri m p r o v e st h ee m c l e n c yo f s a m p l i n ga k o r i t h m u t i l i z j n gt h eb l e n d i n gp r o p e r t y0 fi m 甜i c j ts u r f 如，w ep r 印o s et o 印p l ya m e r 西n go p e r a t i o nt ot h o s er a m i f o r mp a r t i c l e sw h i c he o m ef r o md i 黯r e n t s u b s t r u c t u r e 8a n dl o c a t ei nr a m i 矗c a t i o n s w er e s p e c t i v e l yi m p l e m e n tt h e e l l i p t i c - m e r g i n g ，s k e l e t o n r e d u c t i o na n ds u p e r e l l i p t 记m e r g i n go p e r a t i o n s a n dd oad e e pa n a 】y 8 i sa i l dc o 瑚【p a r i s o n ， f i n a l l y ，w es u g g e s tam o d i f i e d s u p e r e l l i p t i cm e r g i n go p e r a t i o n ，w h i c hs e p a r a t et h ed i 脑e n tr e g i o 咀8t h a t t h et w oe o n n e c t e db r a n c h e 8c a 肌s e da i l da p p l i e dd i 丘e r e n tm e r g i n e 叩e r a t i o n s t or a m i f o r mp a r t i c l e sl o c a t i n gi nd i f f e r e n tr e g i o n s a f t e rm e r g i n go p e r a t i o n ， a l lr a m i f o r mp a r t i c l e sh a v em o v e dt ot h es m o o t hb l e n d i n gs u r f a c ea n dn o u n e x p e c t e db u l g ew i l le x i 8 t w ed e v e l o pas o f t w 孤ef o ro u rs u b s t r u c t u 洚b a s e dp o i m8 a m p l i n gm e t h o d a c c o r d i n gt od i f f e r e n tb r a n c h i n gs t r u c t 毗ei n p u t 8 ，w ec 觚a c q u i r ea nt h e s a m p l i n gp o i n t sf o rt h em e r g e ds u r f a c ef a s ta n de m c i e n t l 矿 k e yw b r d s ：r a m i f i e ds t r u c t u r e ，i m p l i c 主t l ym o d e l l i n g ，p o i n ts a m p l i n g ，s u b s t r u c t u r e h i e r a r c h i c a ls 打u c t u r e 第i i 页 插图目录 插图目录 】- 】l 系统：规则与产生的图形示例( 左) ；渲染后的树结构( 右) 1 0 】2 2 1b 1 0 0 m e n t h a l 用样条插值法得到的分支结构：插值前所计算的分支 处的基本轮廓线( 左) ：得到的分支处一系列样条曲线( 中) ； 渲染后的枫树( 右) f 1 6 1 2 、2 基于曲线骨架的距离曲面：骨架( 左) ；等值线( 右) 14 1 2 。3 用s u p e m l l i p t i c 法对两个圆柱体进行融合：融合前两个独市的圆柱 体( 左) ；融合后得到的侧面轮廓线( 右) f 1 4 1 2 4 基于过程建模的分支结构：e v a h t a t i o no ff ( p ) ( 1 e f t ) ；”e n v e l o p e ” c u r v e ( m i d d l e ) ；s h a d e ds u r f a c e ( r i g h t ) 【13 】 ， 2 ，5 基于卷积曲面建模的分支结构：分支结构的骨架( 左) ；渲染后 的分支曲面( 右) 1 5 1 ，、 2 。6 基于b l o b n e e 系统的分支结构建模：分支处连续和非连续的细节 建模( 左) 【4 4 】= 渲染后的整个树干结构( 右) 【4 5 】， 2 7g r e e n l a b 开发的虚拟植物的可视化软件：生成的全景圈( 左) ； 枝干的局部细节( 右) ( 选自腾军自行开发的程序) 2 8 光线追踪法：光线穿透两个融合的球体( 左) ；光线穿透后的切面 ( 右) 2 3 2 9 点绘制技术的渲染通道， 2 r 1 0b l o o m e n t h a l 的基于“种子点”的采样隐式曲面方法：原始“种 子点”( 左) ；“种子点”的移动路径( 中) ；最终的采样点 ( 右) 【1 3 ， ， 2 1 1w i t k i n 的点采样方法：由卜- 至下，我们可以看出粒子通过不断的 移动、分裂最终覆盖整个曲面，并且达到均匀的分布f 2 5 1 3 1 分支建模的几何示意图：具有统一半径的单枝( 左) ；具有变化 半径的单枝( 右) ( 其中各参数的表示意义如公式( 3 4 ) 所示) 3 2 子结构构造示意图。其中p 和j 分别表示子结构的生理年龄和生长 年龄f 5 0 】 ， 3 3 分支系统分解示意图：分支系统的骨架( 上) ；分支系统的分解 ( 下左) ；分解后各级子结构的示例( 下右) 3 4 子结构的连接关系图 、， 35 基于子结构的分支系统的隐式建模流程图， ， 4 _ 1 初始采样点的选取( 红色实线均为骨架，由骨架引出的虚线与包 围盒的相交点为初始采样点) ：基于包围盒的初始点( 左) ；基 于全局包围盒( 红色点画线) 和局部包围盒( 蓝色实线) 的初始 点对比( 中) ；基于“广义圆柱”的初始点( 右) 第v 页 2 7 6 7 8 8 9 9 0 1 2 捣 h 埔 ” 如引沈 插图目录 4 2 基于“广义圆柱”的初始采样点：直线7 目架( 左) ；曲线骨架 ( 右) 4 3 分支系统点采样的流程图，其中每个标号代表个步骤 4 4 基本单枝的采样点库示例：1 5 种单枝类型( 绿色的点表示用点 显示的采样粒子，本章均同) 。 4 5 基于复制、变换操作的分支结构的采样点：分支结构的骨架 ( 左) ；复制、变换操作后得到相应的采样点( 右) “6 分支区域内相互交错的粒子；不同等级的分支采用不同的颜色， 红色代表等级为o 的分支，绿色代表等级为1 的分支，蓝色代表等 级为2 的分支，放大的线框内表示来自不同分支的粒子相互交错 4 7 分支区域的”包围盒“的定义：包围盒的定义( 庀) ；两相交包 围盒的合并( 红线框表示合并后的包围盒) ( 中) ；两相交包围 盒的不合并情况( 蓝色和黄色包围盒所示) ( 右) 4 - 8 包围盒半径的定义：g 表示两骨架的交点，r ，r ，分别为两分支 的半径，r ，r ；分别为两骨架的影响范围 4 9 确定分支区域及分支粒子：定义的包围盒( 绿色球体表示) ( 左) ：在“包围盒”内的分支粒子( 红色粒子表示) ( 右) 4 1 0 两个圆球体的椭圆融合( e l l i p t i cb l e n d ) 4 n 融合曲面在粒子处的梯度：单枝的梯度方向分布( 左) ；分支处 梯度的叠加( 右) 一 垂1 2 融合操作前后分支结构的采样点分布图：融合操作前( 左) ；融 合操作后( 右) ， 4 1 3 分支的影响范围r 的改变对所形成融合曲面的影响示意图 4 1 4 通过骨架的缩减消除“膨胀”部分的示例：原来相交的两骨架 ( 左) ；其中一骨架a 沿原骨架方向缩减如长度( 右) ， 4 - 1 5 改变骨架缩减的长短对所形成的融合曲面的影响( 均为分支的影 响范围r = 3 兄情况) ， 4 1 6 超椭圆融合：改变指数t 对融合曲面的影响( 均为分支的影响范 围r = 3 r 情况) ， 4 1 7 分支粒子处不同骨架所成梯度的夹角 4 _ 1 8 采样不同融合方法得到的分支结构采样点对比图：合并操作 ( 左) ；超椭圆融合( 中) ；修正后的超椭圆融合( 右) ( 采用 棕色的小圆片绘制) ， 4 】9 分支系统的最终采样点图( 采用棕色的小圆片绘制) ， 5 1 算法实现各部分的关系图：绿色的虚线框表示底层部分，红色的 虚线框表示上层部分，黄色部分表示基本的采样点库，灰色的部 分分别表示底层和上层的算法部分 ， 5 2 基本点采样软件界面， 5 3 分支系统点采样软件界面 5 4 子结构类的定义形式 5 5 基本点采样算法中粒子结构的定义 第v i 页 2 8 3 1 3 3 3 4 4 4 4 5 4 7 4 7 4 8 5 u 5 l 盯 盯 如甜 龅 船 鸲议 插图目录 5 6 系统点采样算法中粒子结构的定义 ， 5 7 粒子系统中的数据结构表示图：其中c s “b i 表示对子结构的记 录，p n r c f e i 表示对采样粒子的记录 ， 5 8 皋本单枝点采样的步骤：单枝的初始点( 左) ：基本点采样算 法分别进行不同迭代次数的效果图：迭代次数= 1 1 ( 左二) ；迭 代次数= 2 5 ( 有二) ；迭代次数= 4 5 ( 右一) 5 ，9 具有不同采样点密度的单枝的采样：采样点密度逐渐增大( 左一 右)， 5 1 0 具有不同采样点密度的分支结构的采样：采样点密度逐渐增大 ( 左一右) ，n 表示采样点的个数 5 n 具有不同采样点密度的单个圆球的采样：采样点密度逐渐增大 ( 左一右) ， 5 ，1 2 模拟b l i n 的原子模型采样：融合参数b 逐渐增大( 七一下) ( 左 边采用点来绘制，右边采用小圆片来绘制) 5 。1 3 基于6 个圆球的融合模型采样：骨架信息( 左) ；采样点信息 ( 中) ；渲染后的结果( 右) 5 1 4 基本单枝的采样粒子库：包含l 一1 0 种的基本单枝的采样、 5 1 5 基于基本单枝库的不同分支结构的采样结果( 左边采用点来绘制， 右边采用小圆片来绘制) ， 第v i i 页 5 1 5 2 鸵 船 弱 矾 的 弱弱 表格目录 2 一l 点采样算法的分类 表格目录 5 1 基本单枝的骨架输入文件 5 2 分支结构的骨架输入文件 5 3 基本单枝的采样点库输入文件 第v n i 页 1 2 4 8 4 0 4 9 独创性声明 本人声明所递交的论文是我个人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果。与我一同工作的同志对本研究所做的任何贡献 均己在论文中作了明确地说明并表示了谢意。 签名：翌趱日期： 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用 学位论文的规定，即：中国科学院自动化研究所有权保留送 交论文的复印件，允许论文被查阅和借阅；可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 签名：望盘超导师签名：重佥堡墨鱼日期： 分支结构的建模和采样 第一章绪论 1 1 分支结构可视化研究的意义 随着计算机硬件和软件的迅速发展，自然景物和自然现象的模拟和绘制越 来越受到人们的关注，并被广泛的应用于3 d 游戏、虚拟现实、计算机动画、计 算机辅助设计及计算机教学等领域：具有分支结构的物体是自然界最常见的物 体之一，许多动植物的枝干，如树、珊瑚、海星、动物的血管系统等，都具有 树状的分支结构。南于其几何结构和拓扑结构的复杂性，如何快速、逼真地模 拟和绘制具有分支结构的物体一直是计算机图形领域的热点和难点之一。 1 2 分支结构建模及可视化研究的概况及存在的问题 最早在计算机上模拟和可视化分支结构可以追溯到1 9 6 7 年c o h e n ( 1 】通过定 义平面上的密度场产生类似树结构的分支图形。般的说，分支结构的建模可 分为两类：一类是基于形态发生模型的全局建模，侧重于模拟生成整个分支结 构的骨架、分支结构的各个组成部分在空间的位置、朝向及相关几何参数。这 类建模方法已经被广泛地应用于虚拟植物的生长模拟研究中。l l n d e n m a y e r 提出 的后来被称之为。系统的模型f 4 1 ，通过迭代产生重写的字符串，由每个字符串 的含义可以得到相应植物分支的拓扑结构。而后p r u s i n k i e 丽c z 【5 】等人提出了龟 行几何( n n kg e o m e t r y ) 理论，通过“龟图”将字符串解释为一系列几何绘图 指令，从而可以应用计算机图形学的方法研究l 一系统。之后，许多学者对l 一系 统进行了进一步深入的研究，并相继提出开放式l - 系统、随机l 一系统【8 j 、参 数l 一系统f 6 1 、时变l 一系统【7 】以及微分l 系统 9 】等，从而使l 系统可以更好的 模拟和体现植物分支结构中的随机性及多样性。另外，d er ，e 曲e 提出了基于有 限自动机的虚拟植物建模方法。此模型结合了自动机理论和马尔可夫链理论来 描述植物生长，著名的虚拟植物生长软件a m a p 便是在这基础上建立起来的， 它可咀通过对参数进行模拟，建立三维结构，从而再现植物的生长过程。在 此基础上，赵星等又提出了基于双尺度自动机模型【2 9 】，并用它来模拟花序结 第l 页 筘一章绪论 一+ 一i 岳 一垆率y 举 图1 1l 系统： i ! l l l j l i | 与j 生旧图形乐例( 左) ：渲染肪的树结构( 也) | 】( ) 构【3 0 ，之后由中科院自动化所中法实验室( l l a m a ) 和法国科研人员共同开发 了g r e e n l a b 虚拟植物模型3 1 1 口 另一类方法是已知分支结构的骨架，利片j 计算机图形学的技术，逼真地模 拟分支处局部细节的局部建模，这类方法侧重于视觉效果上的真实感。当我们 仔细地、近距离地观察具有分支结构的物体时，不难发现，大多数物体都具有 这样的特性一在分支处，不同枝干之间的连接都是光滑地、连续地。许多学者 已对分支结构的局部建模进行了研究，主要的方法足利用模型产生的或者已知 的分支结构的骨架，进行进一步的基于参数曲面或是基于隐式曲面的建模，从 而得到分支处光滑连接的曲面。但是无论用参数曲面或是隐式曲面，对局部分 支处建模都具有一定的困难。用参数曲面来拟合分支处的连接曲面时，需要计 算大量参数或是解非线- 陛方程组，尤其当分支结构复杂、分支繁多的时候，需 要大量的内存和计算时间；用隐式曲面拟台分支处的连接曲面时，虽然隐式曲 面易于融合操作，便于产生光滑的连接曲面，但是隐式曲面的挟速绘制存在着 一定的困度，尤其当隐式曲面造型比较复杂的时候，精确的绘制需要大量的时 间。对分支结构局部建模的相关工作将在下一章进行详细的介绍。 此外，一些学者还采用基于视觉重建的方法对分支结构( 尤其是植 物的分支结构) 进行建模。s 妇9 1 l c h i 等f 3 3 1 采用了通过正交的反投影重建 了3 d 的v o l u m e ，通过对局部区域内v o x e l 值的判断来生成树的枝干部分，并模拟 了植物的运动状态。s h l y a k h t e r 等f 3 2 】通过反向投影的方法重建了3 d 树的外壳， 并通过寻找中轴线的方法确定树的大概骨架，然后采用l 系统的方法生成其他的 细节。该方法只针对于某些特殊形态的树，对于那些分支多或无叶子的树，则 很容易造成形态误差较大，真实性大大降低。 关于分支结构的绘制，最简单的方法就是利用三维的圆柱体直接替代每个 第2 页 分支结构的建模和采样 分支，这种方法对于快速的绘制具有人最分支的物体是很有效的。但是当我们近 距离观察的时候，就会发现所给制曲面分支处的不连续性，从而造成视觉上的 瑕疵，影响了绘制的真实感。s n i i _ l 3 4 1 利用图元( 印出a 1 ) 的疗法产生草- ：幸! = 植 物和树木的图像。r e e v e s 【3 5 1 利用结构化的粒予系统来绘制植物和植物群落， 该方法虽然产生了逼真的祝话效果，但是不适用于单株植物，需要绘制者的经 验和大量干预，对于生成的粒子的形态也难以直接择制。o p p e l l h e i m e r 等f 3 6 1 用 分形的疗法柬模拟具有自相似性的植物( 女蕨类植物) ，通过一定程度上 随机的凋整挣制参数来反映真实植物所具有的多样性和随机性，取得了较 好的效果，但是该分形的方法只引对具有高度相似性的植物会产生很好的 效果，对于植物个体之间、同一植物内部1 ；通部分之间的差异却很难表现出 来。g r 。c n 3 7 1 通过体元空间的自动机模拟植物的随机生长，使用体绘制的 西法来模拟蔓生植物沿屋生长的现象，该方法需要多次绘制才能完成渲染过 程。v i e r - n m 【3 8 1 用分枝矩阵的方法产生随机的树结构，并直接通过矩阵控制植 物分支的最终形态。l i n t ”n a l l i l 等1 3 9 1 开发了基于圈符的交瓦式植物可视化图 形软件，使得用户可以通过不同的器官选择构造自己定义的虚拟植物，所得结 果的好坏大量依靠丁用户的经验知识， 由上所述，我们不难发现，对于分支结构的建模和可视化，现有的方法或 者只注重全局建模和快速绘制，忽略丁分支处的局部细节特征，从而降低t 绘 制的真实感；或者考虑到分支处的局部细节特征，却无法达到快速、精确绘制 的效果。如何对一个具有分支结构的物体进行快速的绘制并且保留住其局部的 细节特征将是我们面临的一大难题，也足分支结构的建模和a j 视化中急需解决 的一个问题。 13 本文的研究内容 针对着分支结构的建模和可视化中出现的问题，本文研究的目标侧重于分 支结构的第二类建模方法，即关r 分支结构的局部细节特征的建模及相关快速 绘制问题。我们假定被研究的分支结构的物体具有以下两个条件： 该物体的骨架( 包括拓扑结构和几何结构) 己知 该物体的骨架具有可分性并具有一定的分级结构 第3 页 第一章绪论 本文的工作是基于由l i a m a 实验室开发的g r e e n l a b 模型的，该模型包括形 态发生和生理生态模型两部分，不仅可以模拟植物生长的随机过程，计算各个 周期产生的生物量，而且可以给出整个植物分支结构的骨架，包括各个器官的 大小、空间位置、方向等。该模型输出的植物分支结构的骨架完全可以满足我 们上述的两个假设，使得本文的工作可以继续进行。 本文的研究内容主要包括两个部分。第一部分是分支结构进行基于骨架的 几何建模，展示分支处光滑、连续的局部细节，同时引入子结构的概念，加速 和简化对整个系统结构和建模过程。第二部分主要实现对所建模的分支结构进 行点采样的工作，提出了基于子结构的点采样力法。通过对一系列基本单枝进 行基本的点采样算法，建立一个基本单枝的采样点库，而整个分支系统的点采 样工作是通过对基本单枝的采样点进行复制、变换、线性组合和融合操作得到 的。 本文的章节安排如下： 第一章绪论部分，介绍研究分支结构建模和可视化工作的意义、现状及存在的 问题，提出本文所要实现的目标和工作内容。 第二章研究现状概述，分别详细介绍分支结构的局部建模和可视化的具体相关 ， 工作，总结其优缺点，给出本文工作的设计思路来源。 第一章分支结构的几何建模，详细介绍本文对分支结构所采用的基于骨架的隐 式曲面建模工作，并提出基于子结构的系统建模方法。 第四章分支结构的点采样，详细介绍本文采用的点采样方法，并提出基于子结 构的整个系统点采样方法。 第五章软件开发与取得的结果，介绍开发的基于子结构的建模和点采样的软 什，并给出已取得的相关实验结果。 第六章结论与展望，对全文工作进行总结，并对后续的研究方向进行了展望。 1 4 本章小结 本章对分支结构的建模和可视化工作进行了扼要的综述，并介绍了该工作 研究的意义以及现存的问题，最后介绍了本论文所研究的目标和具体的内容。 第4 页 分支结构的建横和采样 第二章研究现状概述 5 2 1 引言 本文所研究的具有分支结构的物体( 简称“分支结构或分支系统”) ，指 其骨架具有树状分支结构的物体。如绪论所述，分支结构的建模主要可分为全 局建模和局部建模两类，本文所研究的建模工作侧重于后者，主要研究在已知 分支结构的骨架及几何参数的情况下，如何进行局部细节建模的问题。 2 2 分支结构的局部建模 分支结构的局部建模方法主要分为两类，一类是基于参数曲面( p a r 锄e t r i c s u r f a c e ) 的建模，另一类是基于隐式曲面( i m p l i c i ts u r f a c e ) 的建模。 2 2 1 基于参数曲面的建模方法 基于参数曲面的建模方法最早应归功于g r e 9 0 。y 和c h a r r o tf 17 】对b e z i e r 曲面 形式的拓展，他们为多边形引入分支表达式，这些方法在现在的c a d c a m 领 域还有着广泛的应用【4 0 。另个经典的工作是b l o o m e n t h a l 1 6 利用样条插值 的方法对枫树的分支结构进行造型。他通过计算分支之间的轮廓线，在各分支 与连接两分支的鞍点之间进行插值，从而得到一系列的样条曲线如图2 1 ，用该 种方法生成的分支结构易于进行纹理贴图，并可以用多边形的绘制方法直接绘 制，但是仍需要大量的计算，过程复杂。 另外，t o b l e r 等f 1 8 1 提出用细分曲面来建模分支系统，f e i 捌等f 1 9 采用相 似的方法对生物分支系统进行了重建。l l u s h 【2 0 】提出了用个连续的多边形网 格来表示树的分支结构，在分支处通过重新计算中间的轮廓，不断修正分支处 的几何错误从而得到分支处的连续曲面。 2 2 2 基于隐式曲面的建模方法 隐式曲面一般定义为满足隐式方程，( p ( 。，z ) ) = o 的点的集合，其 第5 页 第二章研究现状概述 图2 1b 1 0 0 m e n t h a l 用样条插值法得到的分支结构0 击值前所计算的分支处的基本轮廓 线( 左) ：得到的分文处一系列样条 l 线( 中) ：渲染后的枫树( 矗， 16 1 中p ( z ，：) 表示维空阃中的点坐标。相对于显示曲面和参数曲面来说，由于 其隐式定义，隐式曲面具有以下的优点使其为图形界所关注： 隐式方程可以表示显式方程不能表示的多值函数 隐式曲面可以定义几何实体，并根据隐式方程，( p ) 的值，易于判断点在几 何实体内部外部的信息； 隐式曲面定义的实体易于进行c s g ( c 0 s r u c t i v es d l i dg e o m e t r y ) 操作； 可以从骨架出发定义隐式曲面： 隐式曲面易于做变形和融合操作； 隐式曲面的这些优点，使得隐式曲面在对分支结构的建模中得到了广泛的应 用。隐式曲面的建模往往都是基于骨架的，如基于点、线段、曲线等骨架而产 生的相应的元球模型、圆柱模型、广义圆柱模型( g e n e r b l i z e dc y l i n d e r ) 及其相互 组合。 一类较简单的基于骨架建模的隐式曲面称为“距离曲面”( d i 8 t a n c es u r f a c e ) f 4 1 1f 14 ，即把隐函方程定义为关于点到骨架的几何距离的函数，如： ，( p ) ：筚一l ：o( 2 1 ) 其中p 表示三维空间中的点坐标，c 表示物体的线段骨架，d ( p ，g ) 表示点 到骨架的e u c l i d e a n 距离，r 表示物体的半径。当物体的骨架由一系列子线段 如 s e 9 m e 礼t ；i = 1 ，2 ，n 组成时，相应的隐式方程可睫之变为： ，( p ) ：塑鲤翟掣一l ：o ( 2 2 ) 第6 页 分支结构的建横和采样 当子线段s e 9 m 如的长度无限缩短时，我们可以用系列的线性子线段去近似 曲线骨架。基于几何距离的距离曲面计算简单，而且无论骨架是线段还足曲 面，只需要简单的比较求小操作，但是简单的代价就是所得的曲面仅仅是对原 来各部分实体的合并，所以当骨架是凸的时候，可以产生光滑的连接曲面 而当骨架是凹的时候，连接曲面在切线上是不连续的，会出现褶皱情况，如 图2 2 右图等值线所示 当分支结构由两个不同的骨架 e 。、g 2 组成时，我们可以采用融台的疗 法，如r o l l i n gb a l i 融合【“ 、g l o b a l 融合【l4 l 、r a n g e c o n t r o l k d 1 1 】融合等方 法，使两个骨架分别定义的实体光滑的连接在一起。其中常用的方法有r a n g e - c o l l t r o l l e d 融合法中的椭圆融合( e l l i p t i cb l e n d ) 1 l j 及超椭圆融合( s u p e r _ e l l i p t i c b l e n d ) 1 2 1 。但是这样的融合方法往往会引起分支处的场密度的提高，从而造成 分支处实际并不存在的膨胀，如图2 3 右所示，两个圆柱体的轮廓线在相交处发 生膨胀。 为了解决分支处产生的膨胀，b l o o m e n t h a lf 1 3 1 提出了一种基于过程的建模 方法。该方法定义隐式方程为输入是三维空间的点坐标、输出是一个实数值的 任意方程，在计算隐函数值的时候，它允许任意复杂的几何操作，而不仪仪局 限于简单的e u c l i d e a n 距离计算。例如2 4 所示，p 点处的函数值不再取决于点p 到两骨架的几何距离的加、减、求大、求小等简单几何操作( s i m p l em e t r i c ) ，而 是取决于点p 到所构成三角形底边的几何距离这样复杂的几何操作( c o m p o u n d m e t r i c l 。用该种方法生成的分支结构，不仅连接曲面光滑、连续，而且分支处 没有膨胀部分出现，可以保持各分支半径的一致性，但是该种方法只适用于 具有两个分支的结构。当 n 现多重分支时该隐式方程很难定义，并且相应 的”c o m p o u l mr n e t r i c ”几何距离难于计算。 图2 2 基于曲线骨架的距离曲面：骨架( 左) ：等值线t 右) 【1 4 第7 页 第二章研究现状概述 图2 3 崩s u p e l _ e l l l p t i c 法埘婀个别柱f t 进行融台：融合前眄个独立的恻柱体( 矗) ：融 合后得到的侧面轮廓线( i ) 【m 1 另类基于骨架的隐式曲面建模称为“卷积曲面” 1 5 【4 2 1 。该方法通过对 三维的直线段、曲线段、多边形骨架进行卷积，得到表面光滑的隐式曲面。采 用不同的卷积核函数时，该方法可以得到不同的曲面形状。b l o o m e i l t h a l 1 5 利 用卷积曲面对具有多个分支的结构进行造型如图2 5 ，该方法生成的分支结构避 免了在分支m 产生不必要的膨胀部分，而且定义简单，分支处连接光滑。但是 该方法需要进行卷积计算，当分支结构复杂、分支众多的时候，内存和计算时 间消耗很大，从而影响了建模的效率。 另外，w y 订l l 等人在所开发b 1 0 b t r e e 系统 4 3 i 的基础上，融入p c m ( p r e c i s e c o n t a c tm o d e l ) 技术，在分支处同时融入了连续和非连续的细节f 4 4 ，很好地模 拟了树干连接处的光滑曲面以及出现的褶皱、结痂等细节( 如图2 6 ) ，随后又 模拟了树的整个生长过程，并采样光线追踪的方法对所建模的隐式曲面进行绘 制( 如图2 6 ) ，但是这种方法建模过程耗时很多，效率不高。 图2 4 摹于过程建模的分支结构：e v a l 眦1 i o uo f f ( p 1 ( 1 e f t ) ；”e n v e l o p e ”c u r v e 【i n i d d l e ) s h a d e ds u r f a c e ( r i g l l t ) 【l3 】 第8 页 分支结构的建模和采样 图2 5 甚1 卷秘曲面建模的分支结构：分支结构的骨架( 左) ：渲染衍的分支曲砸 ( “) 【1 5 】 图2 6 基丁b l o b n e e 系统的分支结构建模：分支处连续和非连续的细节建模( 左) 4 4 ；渲染后的整个树f 结构( 右) 【4 5 】 2 2 3 分支结构的建模方法小结 综合前两小节的建模方法，我们不难发现，基于参数曲面的建模，虽然绘 制容易，但是建模过程往往过于复杂，为了在分支处得到光滑的连接曲面，需 要大量的计算：相比之下，采用隐式曲面的方法就显得简单、容易操作。由于 隐式曲面本身具有易融合的特性，当多加一个分支骨架到某个结构时，很容易 就得到由该分支结构重新定义的隐式方程，并自动生成光滑的连接曲面。但 是，由于隐式曲面缺少曲面上点的自然坐标信息，所以隐式曲面的绘制成为是 否片j 该种方法进行几何建模的重要因素。 2 3 分支结构的绘制方法 最简单的绘制分支结构的方法是将各个分支分成很多小段，每一小段用一 个圆柱体直接替代。这种方法操作非常简单，只需知道各个分支的三维几何信 第9 页 第二章研究现状概述 息即可进行绘制。目前g r e e n l a b 模型的可视化部分就是采用这样方法对树进行 绘制的，如图2 7 所示，我们可以得到很好的树的全局绘制图( 图2 7 左) ，但足 当我们靠近去观察这棵树的细节时，我们会发现在分支与分支连接处，由于两 个圆柱体相连而造成的不连续曲面( 图2 7 右) ，影响了视觉效果上的真实性。 图2 7g m l 曲开发的赢拟柿物的叫视化软件：生成的全景图( 序) ：枝十的局部细 仃( 右) ( 选自腾军自行升发的程序) 为了避免在分支处产生不连续曲面，如上小节所述，人们往往采用隐式 曲面的方法对分支结构进行建模，这里简单介绍一下隐式曲面的绘制方法。由 于隐式曲面无法自然显示点的三维坐标信息，所以隐式曲面并不能像参数曲面 一样可以直接进行绘制。一个直观的想法是要先得到隐式盐面上点的坐标，然 后在采用传统的面片绘制方法进行绘制。 一类较常用的方法就是将隐式曲面面片化，如m a r c l l i n gc u b ef 2 l 】的方法， 它在空间划分一系列的立方体，通过对每个小立方体顶点处隐函数值正负的判 断，从而找出与隐式曲面相交的立方体，并通过线性插值的方法，找出隐式曲 面与相交小立方体的交点，从而作为所构成多边形的顶点。用m a r c h i n gc u b e 的 方法对隐式曲面进行面片化，其准确程度取决于小立方体的大小，当空间划分 较粗，每个小立方体很大的时候，虽然计算迅速，但是容易丢失隐式曲面的局 部细节：当空间划分较细，每个小立方体很小的时候，虽然可以得到关于隐式 曲面更多细节，但是计算耗时却大大的增加了。另外，采用线性插值的方法求 曲面上点的坐标，本身就存在着很大的误差。 另一类方法就是采用光线追踪法( r a y t r a c i n g ) 【2 3 】【2 2 通过反向追踪光线 来计算光线与隐式曲面的交点( 如图2 - 8 ) 。该种方法是一种基于视点的渲染方 法，当视点改变时，需要重新计算光线与隐式曲面的交点，并且求交计算通常 都涉及到求解非线性方程的问题，所以计算量较大，且比较耗时。 第l o 页 分支结拘的筵模和采样 图2 8 光线追踪法：光线穿透两个融台的球协( 左) ；光线穿透后的四面( 右) 23 24 点绘制方法 当我