（计算机科学与技术专业论文）基于gpu实现的自适应八叉树纹理绘画技术研究.pdf

同防科技人学研究叶i 院l ：转；硕十学何论文 摘要 当前，虽然基于二维图像映射定义的传统二维纹理已得到广泛应用，但是它 有很多局限性。这是因为很多三维模型在纹理空问中进行参数化是非常困难的， 例如含有隐式表面、细分表面和高密度或高细节的多边形网格。 三维体纹理不存在这一问题，通过将其空间坐标直接作为纹理坐标来使用， 能在体元素构建的同时就获得纹理坐标，并做到采样均匀、坐标连续、无扭曲等。 但是体纹理也存在个难题，就是随着分辨率的提高，其内存占用增长迅速甚至 难以实现，这影响了体纹理在科学成像等应用上的使用。 八叉树纹理是体纹理的一种，其基本思想是将体元素中和模型表面相交的那 些节点以八叉树结构进行存储，达到大大节约内存空间的目的。八叉树结构提供 了一种有效的纹理存储和纹理查找手段，因而成为目前三维纹理映射中最通用的 数据结构。不过当分辨率较高时，八叉树纹理依然存在占用过多内存和构建过慢 的问题，因此目前也只应用于较小型物体的建模上。 基于八叉树纹理定义，本文构建并使用一种新型的基于g p u ( 图形处理单元) 实现的自适应八叉树纹理。和传统的八叉树纹理映射算法相比，自适应八叉树纹 理占用了更少的存储空问，而且本文的算法基于g p u 实现了纹理查询，故有更快 的查找速度。此外，本文在这种自适应八叉树纹理的g p u 实现基础上引入了三线 性插值和m i p m a p p i n g 技术，提高了渲染效果。 以基于g p u 实现的自适应八叉树纹理为基础，本文设计并实现了一种像素级 自动绘画技术，该技术能以三维纹理映射的方式，简单有效的将精美的二维图像 绘制到三维模型表面，并保持了原图像的高细节和真实感。在设计和实现过程中， 针对出现的问题，本文又提出并实现了区域上色、断点修复等方法，最终获得的 实验结果效果良好。 术 主题词：八叉树，自适应八叉树纹理，g p u ，纹理查询，像素级自动绘画技 第1 页 圃防科技人学研究十院l ：桦硕十学忙论文 a b s t r a c t t r a d i t i o n a lt e x t u r i n gu s i n gf ls e to ft w od i m e n s i o n a li m a g em a p si sa ne s t a b l i s h e d a n dw i d e s p r e a dp r a c t i c e h o w e v e r ，i th a sm a n yl i m i t a t i o n s p a r a m e t e r i z i n gam o d e l i n t e x t u r es p a c ei sv e r yd i 硒c u l t ，p a r t i c u l a r l yw i t hr e p r e s e n t a t i o n ss u c ha si m p l i c i ts u r f a c e s ， s u b d i v i s i o ns u r f a c e s ，a n dv e r yd e n s eo rd e t a i l e dp o l y g o n a lm e s h e s s o l i dt e x t u r e sm a p p i n gc a ns o l v et h i sp r o b l e m t h e yu s eas u r f a c e sp o s i t i o ni n3 d s p a c ea st e x t u r ec o o r d i n a t e s ，w h i c hi s c r e a t e dw i t ht h ev o x e l s a ta n yp a r t i c u l a r r e s o l u t i o nt h e i rs a m p l e sa t eu n i f o r m l yd i s t r i b u t e da c r o s ss p a c ei nt h er e g i o nt h es u r f a c e o c c u p i e s i na d d i t i o n ，t h e s ec o o r d i n a t e sa r ec o n t i n u o u s ，a n dw i l l n o tc a u s ea n yd i s t o r t i o n b u tt h e i rm e m o r yu s a g eg r o w sw i t ht h ec u b eo ft h er e s o l u t i o n t h i sh a sm a d et h e m i m p r a c t i c a lf o rg e n e r a lu s e a n dc o n f i n e dt h e i ru s et os c i e n t i f i ci m a g i n g o c t r e et e x t u r ei sak i n do fv o l u m et e x t u r e s i tu s e so c t r e ed a t as t r u c t u r et os t o r et h e s u b s e to ft h ev o l u m et h a ta c t u a l l yi n t e r s e c t st h es u r f a c eo fam o d e l t h eo c t r e et e x t u r e s a l es p a r s e a n dt h e yp r o v i d ea ne f 6 c i e n tw a yt os t o r ea n dl o o ku pt h e s et e x t u r e s n o w t h e ya r et h eg e n e r i cd a t as t r u c t u r e sf o rg r a p h i c sh a r d w a r e h o w e v e r , t h e yh a v e t h es a m e t r o u b l eo nm e m o r y t h e ya r eu s u a u yu s e do nc h a r a c t e r sa n dp r o p st h a ta r es m a l la n d n e e dt ob es e tu pq u i c k l y b a s e do na l la d a p t i v eo c 缸e et e x t u r e sm e t h o d ，t h i sp a p e ru s e sak i n do f3 d v o l u m e t r i ct e x t u r ea p p r o a c hw h i c hh a sl e s ss t o r a g er e q u i r e m e n t st og e n e r a l o c 打e e t e x t u r e sm a p s i na d d i t i o n ，i td e p e n d so nt e x t u r el o o k u pi nt h eo p u ( o r a p hp r o c e s s i n g u n i t ) w h i c hp a r t i c u l a r l yl o o k u p f a s t e rt h a nt h ep r o g r a m o t h e r w i s e ，t r i 。l i n e a r i n t e r p o l a t i o na n dm i p m a p p i n gi su s e dt or e n d e r b e a e r b a s e do na d a p t i v eo c t r e et e x t u r e sa n dg p u ，t h i sp a p e rd e s i g na n dr e a l i z ea n a u t o m a t i cp a i n t i n gm e t h o da tp i x e ll e v e l t h i si sa3 dt e x t u r em a p p i n g ，w h i c hc a l l r e n d e ra2 dp i c t u r et ot h es u r f a c eo fm o d e lh i g h p o w e r e d t os o l v et h ep r o b l e m sw h i c h w e r ef o u n di nt h ed e s i g n ，t h i sp a p e rp r e s e n ts o m et e c h n i q u e s ，s u c ha sp a i n t i n go na c e r t a i nr e g i o na n df i xt l l ed i s c o n t i n u o u sc u t s t h ef i n a lr e s u l ti sg o o d k e yw o r d s ：o c t r e e ，a d a p t i v eo c t r e et e x t u r e s ，g p u ，t e x t u r e sl o o k u p ， a u t o m a t i cp a i n t i n gm e t h o da tp i x e il e v e l 一一一一一一 第1 i 页 围防科技人学研究，卜院l ：稃硕十学伊论文 表目录 表2 1 对l a d d y 模型采用不同纹理时的内存占用对比表1 6 表4 1 规则八叉树和自适应八叉树的相关数据对比3 5 第1 i i 页 旧防科技人学研究乍院l ：w 硕+ 学位论文 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图2 1 3 图3 1 图3 2 图3 3 图 图 图 图 4 5 6 7 图3 8 图3 9 图3 1 0 图3 11 图3 1 2 图3 1 3 图3 1 4 图4 1 图4 2 图4 3 图4 4 图目录 纹理映射示意图3 节点和叶节点的结构示意图8 节点定义伪代码9 八叉树的构建过程示意图9 八叉树节点的细分和三维直观尺寸图1 0 纹理空间中的节点尺寸直观图1 0 八叉树节点的存储示意图。l l 构建和存储八叉树纹理的部分伪代码1 l 八又树和自适应八叉树的结构对比1 2 只在局部区域有高细节表现需求的模型1 2 自适应八叉树的构建过程示意图1 3 构建自适应八叉树纹理的伪代码1 3 实验效果图1 4 体纹理、八叉树纹理和自适应八叉树纹理内存占用对比曲线图1 6 问接池存储结构示意图1 9 创建间接池纹理的伪代码2 0 纹理查找过程2 l 树查找的伪代码2 2 使用8 个样本的三线性插值2 4 直接的线性插值造成的走样2 4 用三线性插值修正由直接的线性插值造成的走样2 5 线性插值所需节点没有全都包含在树中：2 5 节点5 的扩大包围盒包含节点l ，则将节点5 连到树中并插值2 6 需要正确线性插值的节点都已存入树中2 6 三线性插值算法伪代码2 7 m i p m a p p i n g 树示意图2 8 m i p m a p p i r t g 纹理存储示意图2 8 m i p m a p p i n g 实现算法伪代码2 9 读墩位图的部分代码3 2 在j ：维平确i 上看到的三维物体的投影【3 5 l 3 3 逆向投影绘画算法示意图3 4 逆阳投影绘画算法的。史现伪代码一3 4 第1 v 页 围防科技人学研究q i 院i ：稚硕十乎仲论文 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 1l 图4 1 2 图4 1 3 图4 1 4 图4 图4 图4 图4 图4 1 9 图4 2 0 图4 2 l 树深度为8 时的桃架宝f i 构图3 5 树深度为9 时的框架结构图和效果图3 6 部分效果图3 6 程序输入的模型和b m p 图像3 7 大尺寸图片绘画效果3 7 小尺寸图片和绘画效果3 8 出现断点的原因示意图3 9 平均插值断点修复的伪代码4 0 第一种断点修复前后效果对比4 0 解决第二种断点的区域上色示意图4 l 区域上色算法的伪代码4 2 颜色选择界面4 2 a n g e lf i s h 模型素材及绘画效果4 3 f i s h 模型素材及绘画效果4 4 c y l i n d e r 模型素材及绘画效果4 5 v a s e 模型素材及绘画效果4 6 b u n n y 模型素材及绘画效果4 7 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究_ 1 - 作及耳( 搿o l l 究成果。尽我所知，除了文中特别加以标注和致谢的地力外，论j t 中不包分其池人l 二 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机 勾的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均t l j 在沦 中作了明确的说明并表示谢意。 学位论文题目： 垫i 鲤! 塞毽鲍鱼适应墨挝煞竖丝照捷：! 王! a 赴一一 学位论文作者签名：垄叠垒 日期：伽7 年，- 同舻日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：基王垒堕塞垫鲍自重廑墨挝纹垄绘鱼蕉垄逝壅 学位论文作者签名：丕整日期：弘帅7 年，- 月争日 作者指导教师签名：塑查日期：。叼年忽月矿日 国防科技人学研究叶i 院f ：群硕十学何沦丈 第一章绪论 如何在计算机中表示图形，以及如何利用计算机进行图形的生成、处理和显 示的相关原理与算法，构成了计算机图形学的主要研究内容1 1 1 。图形通常由点、线、 面、体等几何元素和灰度、色彩、线型、线宽等非几何属性组成。可以说，计算 机图形学的一个重要研究内容就是要利用计算机产生令人赏心悦目的真实感图 形。 在计算机中重现真实世界场景的过程叫做真实感绘制。真实感绘制的主要任 务是要模拟真实物体的物理属性，即物体的形状、光学性质、表面的纹理和粗糙 程度，以及物体间的相对位置、遮挡关系等等。其基本任务就是在计算机中生成 三维场景的真实感图像。 对于场景中的物体、要产生具有高度真实感的图形，颜色是最重要的部分【2 j 。 通常只要分别计算r 、g 、b 三个分量的光强值，就可以得到某个像素点上的颜色 值，给入以某种颜色的感觉。颜色是外来的光刺激作用于人的视觉器官而产生的 主观感觉。近代的三色学说原理认为，任何一种颜色都可以通过红、绿、蓝三原 色按照不同比例混合来得到。通常用于彩色阴极射线管等彩色光栅图形显示设备 中的r g b 颜色模型，是我们使用最多、最熟悉的颜色模型。 但是简单的将一种颜色应用到多边形模型上，却往往由于其表面过于光滑和 单调，看起来反而不真实。这是因为在现实世界中的物体，其表面通常有它的表 面细节，即各种纹理，如刨光的木材表面上有木纹，建筑物墙壁上有装饰图案， 机器外壳表面有文字说明它的名称、型号等。它们是通过颜色色彩或明暗度变化 体现出来的表面细节，这种纹理称为颜色纹理。另一类纹理则是由于不规则的细 小凹凸造成的，例如橘子皮表面的皱纹，它们被称为几何纹理，是基于物体表面 的微观几何形状的表面纹理。通常我们大量使用的是颜色纹理，这时的纹理一般 都是二维图像纹理，可以用纹理映射的方法将纹理映射到三维物体的表面。 1 1 课题背景 虽然纹理映射只是一条将某个颜色分配到某个像素的规则，与任何光照模型 无关1 3 j ，但它依然是一科t 用于增加多边形模型细节外观的非常有效和高效的技术。 纹理中不仅可以存储颜色信息，而且可以存储用于凹凸映射的法线，以及各种着 色属性，以产生引人注意的表i f l i 效果。纹理映射最流行的实现策略是在建模阶段 将纹理空l 、日j 坐标与多边形的顶点相关联。绘制引擎的任务就是对每一个多边形内 的像素求出其相应的纹理空l 日j 坐标1 4 j 。 第1 页 国防科技人。7 7 纠f 究乍院i ：n 硕十￥：何沦丈 然i m ，纹则映划通常郜；岳婴将例格参数化，这。过氍足通过分配给每个州格 顶点一个2 d 纹理坐标来完成的。如果是简单的可解析的几何体，例如网杠体，能 轻易将其参数化，那么纹理向物体表嘶的映射就很容易了。但是现实世界中这类 物体却是很少的，对于大部分网格模型来晚，将其参数化都是很难的件事，而 且这一艰难的参数化过程通常会带来扭曲和裂缝，特别是在很复杂的网格上。 目前最常用的二维纹理映射对于提高图形的真实感有很大的作用，但是由于 纹理域是二维的，而图形场景物体一般是三维的，这样在纹理映射的时候是一种 非线性映射，在曲率变化很大的曲面区域就会产生纹理变形，极大地降低了图像 的真实感。而且对于二维纹理映射，当模型包含一些非正规拓扑表面时，纹理的 连续性是得不到保证的，很容易出现扭曲和断裂。 现在，可以通过将纹理定义在包围物体的体( v o l u m e ) 上来避免2 d 参数化。 d e b r y 等( 2 0 0 2 ) 和b e n s o n 、d a v i s ( 2 0 0 2 ) 已经展示了如何将3 d 层次数据结构 八叉树纹理( o e t r e et e x t u r e ) 用于高效存储一个网格表面的颜色信息，而且无 需纹理坐标。这种方法有两个优点：第一，颜色只存储在物体表面与体相交的地 方，因此可以减少内存需求；第二，物体表面是规则采样的，生成的纹理并不会 带来任何扭曲。但是八叉树纹理仍然存在和体纹理同样的缺陷，其占用的内存空 间会随分辨率的提高迅速增加，对于大型和大数据量的网格模型来说，使用3 d 的 八叉树纹理来进行纹理映射时其内存开销和建树时问依然是个很大的难题。 本文着眼于利用基于g p u 实现的自适应八叉树纹理来存储网格表面的颜色信 息，以进一步减少内存需求、加速纹理查找、减少建树时间；并以此为基本技术 手段，将高细节的2 d 位图图像自动绘制到3 d 网格表面，构建出高细节3 d 纹理。 1 2 1 纹理映射 1 2 研究现状概述 纹理映射一词最早由c a t m u l l l 5 l 提出，其实质是从二维纹理平面到三维模型表 面的一个映射【6 】【7 1 。将已知的纹理坐标和相应的几何坐标联系起来，就可以将纹理 图粘贴到网格表面，但很可能因应用各种变换而被扭曲变形【引，如图1 1 所示。目 前广为应用和f 1 益成熟的各种二维纹理映射算法，在一定的约束条件下已经能达 到很好的表面效果。 传统上，为了参数化模型而建立：维纹理坐标域的工作要么由专家手工来做， 要么用m a i l l o t l 9 1 或者p i p o n i 1 0 l 的技巧e i 动生成，但这些方法都会在映射时引入断 点、扭曲或拉伸，如图1 1 b 所示。 第2 页 圆防科技人学讲究生院i 群唢h 学位沧史 鏊盔 ( a ) 一维纹理平面 c b ) 二维纹理映射到三维模型表面 幽1 1 纹理映射示意嘲 虽然有些技巧和方法可以将多边形网孔处的拉伸影响降到最小，但在进行 二维纹理映射时还是会有其它问胚出现。因此二维纹理映射对于那些包含有隐式 表面( i m p l i c i ts u r f a c e s ) 吡峨自适应区域( a d a p t i v ed i s t a n c ef i e l d s ) i 哪的多边形 网格几乎是难以应用的。而能自动生成纹理坐标的三维纹理映射解决了这一矛盾。 12 2 体纹理 1 9 8 5 年p e f l m i l4 j 和p e a c h e y t ” 分别独立扩展了纹理映射的概念提出了3 d 体 纹理。他们认识到可以用3 d 空间中的表面位置作为纹理坐标，将纹理映射到复曲 面。a k e l e y l “i 描述了种硬件执行方法。他们的j 二作现在已经成为o p e n g l 1 ”图形 标准的部分。1 9 9 1 年l a u 一”1 等人发表了关于体着色的相关文章。此外还有些 近似的相关方法。如t u r k 1 9 1 发展了一种方法，用规则分布的表面采样来表现反射 纹理。p f i s t e r l 2 0 l 等人扩展了这一概念，在采样点处表现表面自身，用更一致的两格 采样来代替随机采样形成一种分层深度立方体表示法口”。f d s k e n ”魄出了自适 应区域的概念来对表面建模。另一种将纹理映射到多边形的方法广泛应用于网孔 简化b ，嘲，1 2 4 ，瞄】。该方法为每个网孔创建个纹理贴片，这些贴片之间填充 上边界信息以保持连续性，然后将这些贴片合成为规则纹理。g o r t l e r t ”i 等人还提 出了一种通过一维线性采样来改造图像的方法。 因为体纹理坐标能自动生成，人们从手工赋予模型坐标的繁琐工作中解脱m 泉。但用体纹理进行高品质纹理建模将占用丈量存储空问，困此3 d 纹理的发展速 度比起2 d 纹理来缓慢得多。 123 八叉树纹理 八义树纹理是体纹理的种变形。1 9 8 4 年t a m m i n e n 的著作就介绍了基f 八义树的图像在3 d 图像处州的相关科目中的应用。s i g g r a p h 2 0 0 2 会议t d a v i d b e n s o l i 和j o e l d a v i s t 2 3 l 攫文提f “了种川八叉树实现纹理映射的方法， d a v i d d e b r y l 2 9 l 等人的文章也独赴发胜了种近似于八叉树实现纹理映射的方 第3 页 同防科技人学研究牛院i 转! 硕十学俯论丈 法。 八叉树是一种规则的层次数据结构。树的第一个节点即根节点，是一个立方 体。每个节点有8 个子节点或者没有子节点，且这8 个子节点是对父节点的一一个2 2 2 的规则细分。其中不含有予节点的叫做叶节点。在一个包含了3 d 模型的八 叉树中，那些包含了模型表面的节点被更细致地划分，而余下的空节点则成为了 叶节点。八叉树每个维度每细分一次，其分辨率都将增大到原来的两倍。因此， 要达到一个2 5 6 2 5 6 2 5 6 的分辨率，总共需要8 层。八叉树结构广泛应用于许 多领域，如空间形变【3 0 1 、多边形网格几何建模【3 1 i 和隐表面1 3 2 j 的 h 关问题等。 用八叉树这种稀疏结构来存储纹理，除了节省内存外，还有查找速度快等优 点。更主要的是，在绘图时间上做到了极大的节约，因为和传统体纹理一样，使 用八叉树纹理无需再为每个模型的纹理坐标进行手工赋值。 八叉树纹理一经提出即成为三维体纹理的常用结构，目前许多三维纹理映射 方面的应用都是以八叉树纹理为基础的。 1 2 4g p u 目前计算机图形学正处于前所未有的发展时期1 3 3 1 ，g p u 技术以令人惊异的速 度在发展。不仅操作性能得到了提高，计算质量和图形编程的灵活性也逐渐得以 改善。如今我们已经进入可编程的g p u 时代。图形硬件流水线的固有组成和元件 被打破，再造为可编程的、平行传递信息的处理器。 g p u 的一个显著效果就是快。可编程的g p u 是很灵敏的。以前困难的图形问 题在性能极大提高的设备上变得轻而易举。图形程序员现在可以用新的算法和技 术做实验，而这在像c p u 那样缓慢的单线串行处理器上是不可能的。g p u 的并行 流处理性质加之灵活性和可编程性，允许开发新的算法并将其投入实验。现代的 g p u 运行浮点计算比今天的c p u 快得多；而且，如果c p u 限制了应用程序的性 能，使得g p u 有空闲周期，可以把工作卸给g p u ，让我们的应用程序得以全速运 转。因此，g p u 可以显著的增快图形处理速度，它也成为了目前图形程序员进行 图形编程所不可缺少的工具和手段。此外，要使用g p u 的原因还在于它能支持更 大的八叉树深度，进一步提高分辨率。 1 - 2 5g p u 上的八叉树纹理和类八叉树纹理 到了现在，在g p u 上实现八叉树纹：理1 3 4 1 后，八义树纹理的性能得到了进一步 提高。相比体纹理，用八叉树结构来存储纹理时，颜色只存储在物体表面与体相 交的地方，因此叮以减少内存需求，而且在物体表面i 的采样也是均匀的。虽然对 于大数掘转的模型柬说，八叉树纹理仍然会因占用了太多存储空i h j 而被限制使 j ， 第4 页 国防科技人学研究乍院i ：群硕十。子：伊沦艾 甚盒f i i j j 实现，但作为图形馊件上彦i 川的通川数捌乡占构| 3 刊之一，八义树还匙仃着 很重要的作用和广阔的应用空问。近几年，各种图肜学会议和期于0 一l 发表的文章 许多都足以八叉树结构和g p u 作为实现基础的，如j o h n d o w e n s i 拍l ， d a v i d l u e b k e l 3 7 j 等人的文章叙述了对g p g p u 的应用，y u t a k a o h t a k e l 3 8 l ， j o c h e n s t i b m u t h l 3 9 i 等人的文章则将八叉树用于点云模型等的表面重建过程中。国内 近年针对八叉树的不足，也出现了如分块的混合八叉树【4 0 1 、g p u 加速的八叉树体 绘制【4 i 】等从不同角度对八叉树进行改善的方法。 2 0 0 5 年s i g g r a p h 会议上，j o e k n i s s 4 2 j 等人撰文提出并实现了种在g p u 上实现的类八叉树结构( o c t r e e 1 i k e d ) 交互式绘画系统，能在模型表面以不同的 分辨率进行交互式绘画，其实质也就是通过绘画产生一种区域自适应的类八叉树 纹理。在此前人们都认为由于g p u 支持上的限制，八叉树结构很难在g p u 中使 用，该文提出了一种使八叉树甚至n 3 树能在g p u 上实现并高速运行的方法和数 据结构。该文第二作者a a r o n e l i o t l e f o h n l 3 5 】在其博士论文中详细介绍了实现上述 系统所用到的一些技术，包括g l i f l 数据结构、物理页以及页表转换器等。虽然通 过这些技术提高了交互性和数据的随机存取等性能，但是这需要额外的用于物理 页和页表的g p u 内存开销，也就是说三维纹理的内存瓶颈问题依然存在，因此该 方法仅适用于高性能计算机。 1 3 1 研究目标 1 3 研究目标和研究内容 本文的研究目标主要是以g p u 上的八叉树纹理1 3 4 j 为基础，构建出g p u 上的 自适应八叉树纹理，并以此为基础进行像素级水平的自动绘画，将一幅高细节的 二维b m p 图像绘制到网格表面，同时得到维持了高细节的三维纹理，最终获得一 个具有真实感的表面效果。即用三维纹理映射的方式达到和目前流行的二维纹理 映射、以及使用前述交互式绘画系统所得到的近似的效果，同时保持传统三维纹 理的优点，能自动生成纹理坐标且采样均匀，并突破传统三维纹理的瓶颈，进一 步减少内存需求，还能维持局部的高细节表现力，同时构建出个用八叉树结构 保存的三维纹理。 1 3 2 研究内容和主要创新点 根掘研究目标，本文的研究内容t 要包括以下几个部分： 一、自适应八叉树纹理的构建、存储和肖找。以八叉树纹理的结构为基础， 进行自适应八叉树纹理的构建和存储，实现城大限度节省内存的目的。 第5 页 刚防科妓人学硼究牛院l ：烈硕十予：何沦文 二、种g p u 一1 - 的f i 适s 蓝j t , 义树纹理的构建利实现。在g p u 上实蜕这种臼 适应八叉树纹理后，能利用g p u 的高速图形处理功能，加快纹理查找速度，使自 适应八叉树的构建和查找能实时进行，提高人机交互性能。本文使用n v i d i a 开 发的c g 工具编写c g 代码程序来实现对g p u 的访问功能，提高了这种臼适应八叉 树纹理的构建和查找速度，再加上三线性插值和m i p m a p p i n g 等技术，对渲染效果 进行优化。 三、以上述自适应八叉树纹理为基础进行一种像素级自动绘画技术设计。主 要包括b m p 位图的读取、逆向投影绘画算法、区域上色、断点修复等技术，以这 种在g p u 上实现的自适应八叉树纹理为基础，将b m p 位图逐点绘画到网格表面 并得到一个良好的最终效果，同时还得到一个以八又树结构存储的高细节三维纹 理。所谓像素级既是指这种自适应八叉树纹理的叶节点尺寸，也是指绘画时将b m p 位图的每个像素点颜色逐一的上色到相应的叶节点。最终以三维纹理映射的方式， 达到近似二维纹理映射的效果，同时节省了大量的手工赋值纹理坐标的时间，占 用内存也较少。 本文的主要创新点是自适应八又树纹理的构建和使用，设计了一种基于g p u 实现的自适应八叉树纹理，进而提出并实现了以前者为基础的一种像素级自动绘 画技术。 1 4 论文结构 本论文共分为五章，各章节的内容如下。 第一章为绪论，主要介绍了本论文的研究背景：纹理映射，体纹理，八叉树 纹理，以及g p u 。并对国内外的研究现状及课题研究的目的、内容和主要创新点 进行了概述。 第二章为自适应八叉树纹理，主要介绍传统八叉树的构建和存储，自适应八 叉树的构建和存储，自适应八叉树纹理的查找，以及部分实验结果，和自适应八 叉树纹理与规则八叉树纹理的内存占用比较。 第三章为一种基于g p u 实现的自适应八叉树纹理，主要包含g p u 相关介绍， 在g p u 上如何实现一种自适应八叉树的结构层次设计，以及增加渲染效果的三线 性插值和m i p m a p p i n g 技术等。 第四章为一种像素级自动绘画技术，主要介绍了位图文件的读取、逆向投影 绘删算法、区域上色等技术，和对断点进行的修复，以及最后得到的实验结果。 最后是结束语，对比其它相关工作，总结了本文的工作和存在的不足之处， 并对将来的 ：作进行了展望。 第6 页 【日防科技人学研究乍院i ：群硕十学何论文 第二章自适应八叉树纹理 2 1 前言 在动画设计、3 d 游戏等应用中，随着计算机的计算速度与精度不断提高、功 能不断增强，其图形越来越生动和丰富多彩，对纹理映射的性能要求也越来越高。 前面已经提到，进行二维纹理映射的前提是先将网格进行参数化以获得二维 纹理坐标，但是这一参数化过程是一个很艰难的工作，往往会带来各种意想不到 的扭曲和裂缝，特别是那些包含有隐式表面或自适应区域的多边形网格。 三维体纹理的出现解决了这一问题。由于三维体纹理是将网格模型的空间坐 标作为纹理坐标来使用，也就是说将两者合二为一，因此不再需要进行参数化了， 也就避免了二维纹理映射的难题。但是体纹理的缺陷在于占用的存储空间过大， 因为其占用的内存是随着立方体分辨率的提高而迅速增加的，这导致了它不够实 用，也限制了它在急救和科学成像上的使用。但体纹理还是有自己的优良特性的， 例如，在任意精度的分辨率下，其采样都均匀分布在表面占据的区域中。此外， 它的坐标在不同几何类型间的边界处也是连续的，而且不依赖于实际的纹理分配。 考虑到在视觉效应产业中，我们主要是关注于表面上的颜色，也就是说几乎 所有的细节都是集中在模型表面上的，那么它们的表现就和二维纹理相似，占用 的存储空间近似与分辨率的平方成比例增长。因此又出现了八叉树纹理的概念， 它只对体的子集与模型表面相交的那一部分用八叉树的结构进行存储，形成了一 种稀疏纹理，大大节省了存储空间。八叉树纹理能更好的体现三维物体的真实感 和细节，又有节省存储空问和不会带来扭曲的特点。但是对于规则八叉树纹理来 说，即使只是在模型表面一个很小的局部有高分辨率需求，规则八叉树也要将所 有表面都细分到同样的高分辨率程度，因此对于有大表面积的模型或海量数据模 型来说，八叉树纹理也会占用大量的存储空间，甚至不可实现。 本文所提及的自适应八叉树纹理主要针对局部的高分辨率需求，能较好的解 决内存占用问题，同时保持了八叉树纹理的传统优点。解决内存占用这一三维纹 理的瓶颈问题，是本文使用并构建自适应八叉树纹理的最主要原因。 在本文的程序设计+ 和实现中，是采用模块设计的方式来进行的：将不同的功 能分成小同的阶段，削一个一个的模块来实现，用事先胤定的、名称容易理解的 变量柬进行参数传递，达到易读、易改、易控制的l j j 的。 实现思路由构建初始八叉树丌始，逐步提高分辨率，根掘指定或需求在局部 进行节点细分，先细分一次，成功实现后改为细分任意次，最终获得指定分辨率 的叶节点，随后可存叶节点中进行上色等应用。 第7 页 同防科技人学研究乍院i ：烈硕十学何论文 卜- l 山分刖介绍八义树纹理的构建和存储，白适j 、砭八义树纹理的构建和存储， 以及两苔各自占用存储窄问的对比等i 、u j 题。 2 2 八叉树纹理的构建和存储 在本文的实现中，程序输入的第一个参数就是网格模型文件。要通过将纹理 定义在包围物体的体上柬避免2 d 参数化，首先要将包围网格的体进行细分，并以 八叉树这样一个稀疏结构来进行体元素的存储。 第一步要先将网格模型读入程序，用数组存储网格模型的顶点信息和三角形 面信息。然后构建一个单位立方体，将其作为包围网格的体，再根据存储的顶点 信息和三角形面信息将网格成比例缩放到单位立方体中。这样就获得了网格模型 的包围盒，后续的所有操作都是以包围盒为基础来进行的。 下一步按照指定层次或者说树深度进行体的细分。构建八叉树要在每个维度 上都进行二分细分，那么要达到2 5 6 2 5 6 x 2 5 6 的分辨率，需要进行8 次，即 2 8 = 2 5 6 。采用递归的方式，利用程序的重复性构建出八叉树结构。树节点之间用指 针连接在一起。每个节点包含一个指向其子节点的指针数组，显然对于八叉树结 构来说，这个数组有八个元素。子节点可以是另一个含有子节点的节点或者是叶 节点，一个叶节点中只包含一个数据域。在本文实现的程序中，最后得到的叶节 点中只存储范围为0 - - 2 5 5 的r g b 颜色值。 节点和叶节点的内部结构如图2 1 所示。节点内主要包含两种指针数组，一种 是指向其子节点的指针数组，存储的是子节点的地址，另一种是直接存储其空子 节点即叶节点的颜色值。如果节点内不再包含网格表面，则不需要再细分，也就 不再有子节点，那么节点就转变为叶节点，其内部只包含一个数组，用来存储r g b 数值。 叶节点磨色 予节点索l 图2 1：1 ，点和叶节点的结构示意罔 第8 页 叁一 撼防 杖人学研究生院i 程珂i 学位论立 o c t r e e n o d e + c h i i d s 8 1 ； o c l r e e n o d e * p a r e n t ： o c t r e c t r c e+ 1 h e ： o c t r e e g p u + g p u p o i n t ： i 眦 d e p t i ： o c t r c e b o x b o x ； s i d ：l i s t p o l y s b o o l v i s i t c d ； 指向子节点的指针数纽 指向父节点的指针 传递树指针 对应于g p u 的指针 节点的树深度 节点的包围盒 存储节点内部所有三角形面的地址 访问标志 图2 2 节点定义伪代码 八叉树的根节点即昂初的单位立方体，每次细分都产生8 个节点( 这对应于 完全八叉树的情况) ，树深度增加一层，因此可以用递归的方式产生整个八叉树 结构。其创建过程如图2 3 所示。 a | 囝 ( a ) 建立包用盒 ( b ) 第一次细分峙点 绥一蓊 ( c ) 锖_ 二次细分节点 ( d ) 七次细分后得到深度为8 的八义树 崮2 3 八义树的构建过程示意剖 又因为八叉树纹理的纹理坐标也即空i e l j 坐标，那么在上述过程中也就同时得 到了纹理坐标和最终的八叉树纹理。 在本文的实现中，八叉树是被存储在一个8 位的r g b a 三维纹理一p 的，虽然 已经出现了支持三维纹理可视化的软件，但本文的程序宴现并没有涉及这点，固 为这不是本文的研究目标。因此八叉树各个节点的三维直观尺寸、父节点和于节 第9 页 国防科技人学研究l 院i 雅硕 ? 学似隆文 见，木文用罔2 4 束进行八叉树细分的图解随明。 树的各个层次的节点的i 维直删尺寸并不相同，比如根节点就是最初的单位 立方体，第二层节点则为其细分扶后的单元竹点，依此类推，每细分一次，节 点的三维直观尺寸都会缩小成父节点的八分之 。 t 一 西| 日 回回回 第一丧簟骨 ( 树耀麈2 ) ( 材潭庄3 ) 图2 4 八义树节点的细分自l 三维直观尺寸翻 但实际上任何一个节点由于其内部结构相同，各节点所占用的真实内存宅间 大小却是相同的，因此从纹理空b j 的角度来看，各个节点的尺寸是相同的，如图 2 5 所示。 根节点 羊一挺细分的干节皂 目15 纹理m 1 - 的柑点j o n i 观陶 那么在进行内存分配叫，片先要申请一块足够大的地址宅m 。8 位的r g b a 纹理，在缚个通道f ：鳢多能编m2 5 6 种不旧的r o b 值，这提供了个3 8 2 4 位 的地址空例这个地址空l l j 叫以编码的八义树对大多数应j h 程序米| 兑足够大了。 第1 0 页 嘲防科拙人 觅1 院lf + 顿l 牛恤沦史 下步按照八义树构建的顺垮，每次创建的新竹 划m 存储到所i t l 请的内存 巾。l i i 。递f n 砸l 州，连续f f j 内存- l 所存储的节点l l t as - , 井小足按照层层的顺 序，i f t j 魁如| l i j i ) i 序避上巧那样，存储完个竹 的子甘点所n 存储f个社止的r 节点。如刚26 所示。 3 d 空问十 的 工树 薹；亲j 喜饕嚣垃蠹嚣妒 幽2 6 , s t 义树1 r 点的存储示意幽 构建和存储八叉树纹理的部分伪代码如图27 所示。 n e wo c t r e e ； n e wm e m o w ； c r e a t el i s to f p o i n t e r s ： n e wo c i r e e r o o l ： s u b d i v i d en o d e ： f o r 遍历八个子节点 i f 节点内台有网格表向 s u b d i v i d en o d e ： e l s e r e n e w a l ： 色 1 建新八叉树 申请足够大的内存空m 创建指针列表 创建八叉树根节点 构建八叉对 递归细分节点 上色 更新节点和纹理 刚27 栅建莆i 存储八义树纹理的部分伪代码 2 3自适应八叉树纹理的构建和存储 将儿_ 艾树鳆进为f l 适应八义树是实现像系级绘i 1 i 技术的走踺。l i li 分辨牢增 大到像索级时，舰! j ! f j 八叉树的构建时叫山是极长的，j h 】勺内存嘲也迅述增大， 对j ：人型嘲格模型或海量数越：的设鬯托节小能实现。1 4 f j i s t t 叉树纹理也仪应用在 小型物体l ，根本原n 就住七。托使刷f - i 适应八义树纹理时，撒捌丧山i 细肯不 | i ：| ，埘表面k 域进行r 分辨年的1 适应，町以节省 j 人蛙枞糙表l 1 部分会占用的 存储窄间冈此可戍川于部分人州h 格模型l - 。如嘲2 8 对比所1 i 。 第1 | 页 闰防利技凡学嘶究生院l 拌倾 学 1 1 _ 论立 钕惫