（计算机应用技术专业论文）基于gpu的四面体网格细分算法与应用.pdf

浙江人学硕十学位论文 摘要 摘要 细分技术是计算机图形学研究的热点方向，其研究成果在多个领域得到应 用。体细分作为细分技术的一个分支，主要应用于自由变形。在自由变形时，如 果控制网格( 体网格) 过于稀疏，变形后的模型会在控制网格体之间出现不连续 的现象。如果对控制网格细分后再变形，可以减少这种不连续性，但是非常耗时。 因此，本文提出在g p u 内进行体网格的细分。近几年，随着g p u 技术的发展，g p u 的浮点计算性能大大提高，甚至超过了当代主流c p u 。许多重要的算法已经被改 进以达到平衡c p u 和g p u 之间的工作量的目的。 本文介绍了一种已有的四面体网格细分算法。虽然这种算法可以消除变形中 出现的不连续现象，但是其运行时间复杂度相当高。随后，本文分析并改进了这 种细分算法，将算法框架改变为c p u 内预计算和g p u 内实时计算两部分。这种细 分方法的引入，加快了体细分速度，从而实现了实时细分的目的。 最后，本文将这个细分框架运用于自由变形技术。本文对自由变形算法稍加 改变，使最后重心坐标插值部分适合在g p u 内执行，从而形成了一个完整的实时 变形框架。 关键词：g p u ，控制网格，细分，自由变形 浙江大学硕士学位论文 a b s t r a c t ab s t r a c t m e s hs u b d i v i s i o nh a sa l w a y sb e e np a i dm u c ha t t e n t i o nt oa n dw i d e l ya p p l i e di n m a n ya r e a s a sab r a n c ho fm e s hs u b d i v i s i o n ，v o l u m e t r i cm e s hs u b d i v i s i o ni sm a i n l y a p p l i e d i nf r e e f o r m d e f o r m a t i o n d u r i n g f r e e f o r m d e f o r m a t i o n ，a p p a r e n t d i s c o n t i n u i t ya r t i f a c t sa p p e a ri nt h ed e f o r m a t i o nr e s u l tw h e nt h ec o n t r o lm e s hi st o o c o a r s e v o l u m e t r i cm e s hs u b d i v i s i o no nt h ec o n t r o lm e s hc a nd e c r e a s et h e d i s c o n t i n u i t yb u tt a k e sal o to ft i m e t h u s ，w ep r o p o s et op u tv o l u m e t r i cm e s h s u b d i v i s i o ni n t og p u i nt h ep a s td e c a d e s ，a l o n gw i t hg p u d e v e l o p s ，t h ep e r f o r m a n c e o ff l o mc o m p u t i n gi ng p uh a sb e e ne s c a l a t e d an u m b e ro fi m p o r t a n ta l g o r i t h m sh a v e b e e nm o d i f l e dt or e b a l a n c et h ew o r k l o a db e t w e e nc p ua n dg p u t l l i sp a p e ri n t r o d u c e dar e f i n e da l g o r i t h mo ft e t r a h e d r a lm e s h e s a l t h o u g ht h i s a l g o r i t h mc o u l da v o i dd i s c o n t i n u i t ya r t i f a c t sd u r i n gd e f o r m a t i o n ，i t st i m ec o m p l e x i t yi s v e r yh i g h w er e v i s e dt h i ss u b d i v i s i o na l g o r i t h m n e wa l g o r i t h mi sd i v i d e di n t ot w o p a r t s ：( 1 ) p r e - c o m p u t i n gi nc p u ( 2 ) c o m p u t i n gi ng p u t l l i sn e wa l g o r i t h ms a v e da l o to f t i m ei nc o m p u t i n gt e t r a h e d r a ls u b d i v i s i o n ，a n dm a k e st h es u b d i v i s i o nr e a l t i m e a tl a s t ，w ea p p l i e dt h i sn e wm e t h o do nt h ef r e e f o r md e f o r m a t i o n a f t e rw ep u t t h el a s t s t e po ff r e e f r o md e f o r m a t i o n ( w h i c hi si n t e r p o l a t i o no fb a r y c e n t r i c c o o r d i n a t e s ) i n t og p u ，w ef i n i s h e dar e a l t i m ef r e e f o r md e f o r m a t i o nf r a m ew o r kw i t h t e t r a h e d r a ls u b d i v i s i o n k e y w o r d s ：g p u ，v o l u m e t r i cm e s h ，s u b d i v i s i o n ，f r e e f o r md e f o r m a t i o n 浙江夫学硕士学位论文 图目录 图目录 图1 1 细分曲面。下图为控制网格，右上角为细分后结果。l 图1 2 稀疏的控制网格变形结果2 图1 3 对控制网格细分后的变形结果2 图1 4 左图为鼠( f ) ，右图为鼠( f ) 自己卷积自己的图像4 图1 5 网格细分结果5 图1 6 细分种类7 图1 7l o o p 细分法则8 图1 8 传统流水线1 l 图1 9 可编程管线1 2 图2 1 在二维情况下无结构的网格和结构化的网格变形区别一1 4 图2 2 一般细分1 5 图2 3 对八面体和四面体的分割方法1 6 图2 4 质心权值一1 7 图2 5 线性分割的权值2 0 图2 6 由两个四面体 k 面体对共享的面进行细分后的结果。2 l 图2 7 度为3 到1 0 的边的特征映射2 3 图2 8 变形映射。2 4 图2 9 简单网格细分过程一2 5 图2 1 0b u n n y 模型控制网格细分过程2 5 图2 11d i n o s a u r 模型2 6 图2 1 2b u n n y 模型变形结果2 7 图3 1 质心权值2 8 图3 2 子单元顶点与包含它的上一层网格体的位置关系2 9 图3 3 边上新生成的点3 0 图3 4 网格上原有的点3 0 图3 5 八面体内新生成的点3 1 图3 6 新生成的特殊点一3 2 图3 7 细分过程3 3 图3 8 三角形网格的分割3 4 图3 9 以一个网格块为单位细分一3 4 图3 1 0 将一个四面体网格分割成三部分3 5 图3 1 1 分割后三部分各自细分后组装成整体3 5 图3 1 2 表面分块细分过程中可丢弃最外一环3 6 图3 1 3 表面点与体的位置关系3 6 i i i 浙江大学硕十学位论文 图目录 图3 1 4 查询表结构3 8 图3 1 5g p u 内非规则点与规则点渲染3 8 图3 1 6 顶点类型g 的s h a d e r 实现3 9 图4 1l a t t i c e 4 2 图4 2 实时变形框架4 3 图4 3 控制网格内部点和表面点4 5 图4 4 重心坐标查询表一4 8 图4 5g p u 内计算流程4 9 i v 浙江大学硕士学位论文表目录 表目录 表1 i 细分分类表7 表2 1c p u 内细分所需时间2 7 表3 1g p u 内细分所需时间4 0 v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿盘鲎或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位敝储躲犯一 签字嗍。扩年月多日 学位论文版权使用授权书 本学位论文作者完全了解逝鎏盘堂有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝姿盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：j 摹争扩一 签字同期：形年么月同 导师签名： 签字同期： 浙江大学硕十学位论文第l 章绪论 第1 章绪论 细分技术一直是计算机图形学研究的热点方向。传统的细分技术主要关注于 曲面造型，直到1 9 9 6 年，m a c c r a c k e n 和j o y 提出了第一个体网格细分的算法【1 1 ， 从而将细分技术应用到了变形领域。此后，体网格细分技术不断发展。 细分的基本概念出现于上世纪四十年代末，但是当时细分并没有在图形学中 得到应用。随着时间推移，由于细分和多分辨率( m u l t i r e s o l u t i o n ) 技术的密切联 系，细分技术成为处理复杂几何的有力工具，从而在图形学领域中被逐渐广泛采 纳。传统的细分技术用于生成分段光滑的曲面( p i e c e w i s es m o o t hs u r f a c e ) ( 见图 1 1 ) 。 图1 - l 细分曲面。下图为控制网格，右上角为细分后结果。 控制网格( 体网格) 的细分虽然出现得比较晚，但是其意义深远，应用广泛。控 制网格往往和自由变形结合在一起。自由变形通过控制网格的变形来驱动模型的 变形。在自由变形时，如果控制网格过于稀疏，变形后的模型会在控制网格体之 间出现不连续的现象。如果将控制网格进行细分后，可以得到更细的控制网格。 使用细分后的控制网格进行自由变形，可以减少模型的不连续现象。图1 2 显示 了使用比较稀疏的控制网格对d e n s e b a r 进行自由变形的结果，而图1 3 则是使用 细分后的控制网格的结果。可以发现，图1 2 中的d e n s e b a r 在变形过程中，模型 浙江大学硕士学位论文 第l 章绪论 在网格体之间有明显的不连续现象。 ，燕 l 尽弧 _ 卜、 ：i 1 r 绻 ( a ) 控制网格 ( b ) 变形结果 图1 2 稀疏的控制网格变形结果 ( a ) 控制网格 ( b ) 变形结果 图1 3 对控制网格细分后的变形结果 由于体网格的细分算法往往很耗时间，所以这种细分还无法应用到实时变 形。但是，如果利用g p u 的高性能计算能力，可以将体网格细分算法改进后送 入g p u 里运行，从而大幅度提高细分的速度，甚至可以达到实时。 近几年由于半导体产业的迅速发展和芯片集成度越来越高，g p u 的性能飞速 发展。g p u 的浮点计算性能甚至超过了当代主流c p u 。在d i r e c t x8 0 推出时， g p u 上增加了可编程s h a d i n g ，o p e n g l 也提供了相应的功能。随之，g p g p u 也 就诞生了。许多重要的算法( 如粒子系统( p a r t i c l es y s t e m s ) 【2 1 ，碰撞检测( c o l l i s i o n 2 浙江大学硕士学位论文第l 章绪论 d e t e c t i o n ) 1 3 、细胞自动机( c e l l u l a ra u t o m a t a ) 1 4 1 、全局光照( g l o b a li l l u m i n a t i o n ) 【5 1 以及其它数值计算) 1 6 , 7 1 己被改进以达到平衡c p u 和g p u 之间的工作量的目 的。由于g p u 是可编程并且运行时为多个流同时进行，算法执行速度可以大大 地提高。 g p u 计算是由g p u 内的着色器来实现的。这个计算过程需要依赖规则的数 据分布( 通常通过纹理的形式传入g p u ) 。对于不规则的访问需要与c p u 进行交 互。而在细分算法中，除了一些特殊点外，大量的点都可以通过规则访问来生成。 这样就给g p u 内细分算法的实现带来了可行性。对于细分过程中大量规则点的 计算，可以通过预计算离线访问的模式方式来进行，从而可以把预计算完的数据 通过纹理的方式传送给g p u ，在g p u 内进行细分计算来提高计算速度。 本文主要研究基于g p u 的体网格细分算法。本章从细分算法和g p u 技术两 方面来介绍本文的技术背景和相关工作。 1 1 细分算法 细分算法作用是在任意的初始网格( 网格可以是面网格也可以是体网格) 基 础上生成光滑曲面或体。很多游戏和商用图形学软件都已经开始用细分来处理曲 面造型。 1 1 1 连续性定义 任何函数都可以定义为分段常数坐标函数： x ( f ) = , x i b o ( t ) ， 其中b o ( t ) 为b o x 函数： 鼠( f ) = 1i f 0 t 3 时= 3 8 刀。 l o o p 还给出了计算顶点切向量的公式： = 等珊 乞= 等黝 公式( 1 1 6 ) 公式( 1 1 7 ) 其中只，指的是顶点的1 - r i n g 领域( 一环领域) ，即和该点直接相连的点，并且是 按照逆时针方向排列。该点的法向可以由x t ：得，但是这个值是近似的。顶点法 向的标准算法应当是所有包括该点的三角面法向的平均，这个方法的计算结果和 标准方法的误差很小，而且叉乘计算的复杂度非常低。 浙江大学硕：上学位论文 第l 章绪论 1 2g p u 技术 g p u 是图形处理单元( g r a p h i c sp r o c e s s i n gu n i t ) 的简称，这种专用图形绘 制硬件在个人电脑，工作站以及游戏专用平台上都被广泛使用。g p u 内部用硬件 实现了很多图形学的基本操作，使得其绘制能力远远超过了c p u 。近几年，可编 程图形硬件诞生，而且g p u 的并行性显著提高，这些都使g p u 在执行计算复杂度 很高的算法时速度比c p u 更快。g p g p u ( g e n e r a l p u r p o s ec o m p u t a t i o no ng p u s ) 的主要研究方向就是提高g p u 用于高复杂度算法的计算性能。 1 2 1g p u 的发展 二十世纪七十年代末出现了集成度很低的图形芯片，这就是现代g p u 的鼻祖。 这些芯片只是提供有限的位块传输( b i t b l t ) 功能，并不支持基本的绘图功能。 但是随着芯片技术的突飞猛进，图形芯片功能也逐渐强大起来，并且开始出现2 d 图形加速卡。 二十世纪八十年代，i b m 发布了8 5 1 4 图形标准，虽然这个没有成为p c 的标 准，但是它是最早用硬件实现2 d 基本操作的标准，可以说是g p u 历史上的里程 碑。在这个标准里，图形加速卡已经有了独立指令集并提供例如画线，区域填充 和块图传输等强大功能。 二十世纪九十年代，微软发布了w i n d o w s 操作系统。在这个操作系统里，出 现了g u i ( g r a p h i c su s e ri n t e r f a c e ) ，深受用户喜爱。这个大大推动了 g d i ( g r a p h i c sd e v i c ei n t e r f a c e ) 的发展。至此，图形芯片的2 d 功能已经很完 善了，而很多图形公司开始着手图形芯片的3 d 功能开发。1 9 9 6 年，3 d f x 公司发 布了第一款具有硬件加速的3 d 显卡v o o d o o 。1 9 9 9 年，n v i d i a 公司发布了 g e f o r c e 2 5 6 ，把矩阵变换和光照计算集成到了图形流水线中。 二十一世纪是g p u 发展的黄金时代。g p u 的浮点计算性能大大提高，同时出 现了可编程s h a d i n g 。这使得g p u 的灵活性大大提高，得以适应很多复杂的算法。 9 浙江大学硕七学位论文 第l 章绪论 1 2 2g p u 的特点 由于g p u 是专门用于图形加速计算的，因此其所有的计算都使用浮点计算。 至少到目前为止在g p u 内还没有专门用于位或者整数计算的指令。g p u 的存储 系统实际上是一个二维的分段存储空间( 包括一个区段号用于读取图像和一个二 维地址表示坐标) 。在整个g p u 运算过程中，没有任何间接写指令，输出的写地 址由光栅处理器确定。这个地址是不能被程序改变的，这对于一般的算法来说是 很大的挑战，很多算法需要改进后才能适合g p u 运算。另外，不同的碎片处理 程序( f r a g m e n ts h a d e r ) 在处理过程中是不能通信的。实际上，碎片处理器是一 个s i m d 数据并行执行单元，在所有的碎片中独立执行代码。 尽管有上述约束，但是g p u 还是可以有效地执行多种运算，从线性代数和 信号处理到数值仿真。这些都要归功于如g l s l 和h l s l 这样的g p u 着色语言 的出现。这些语言的语法类似于c 程序，用户通过它们可以编写出顶点程序 ( v e r t e xs h a d e r ) 和片断程序( f r a g m e n ts h a d e r ) ，然后编译成g p u 内可以执行 的汇编语言。由美国斯坦福大学开发的b r o o k 语言则把g p u 着色语言推向了更 高的层次。b r o o k 是c 语言的延伸，整合了可以直接映射到g p u 的简单数据并行 编程构造。经g p u 存储和操作的数据被形象地比喻成“流 ( s t r e a m ) ，类似于标 准c 中的数组。核心( k e r n e l ) 是在流上操作的函数。在一系列输入流上调用一 个核心函数意味着在流元素上实施了隐含的循环，即对每一个流元素调用核心 体。b r o o k 还提供了约简机制，例如对一个流中所有的元素进行和、最大值或乘 积计算。b r o o k 还完全隐藏了图形a p i 的所有细节，并把g p u 中类似二维存储器 系统这样许多用户不熟悉的部分进行了虚拟化处理。用b r o o k 编写的应用程序包 括线性代数子程序、快速傅立叶转换、光线追踪和图像处理。利用a t i 的x 8 0 0 x t 和n v i d i a 的g e f o r c e6 8 0 0u l t r a 型g p u ，在相同高速缓存、s s e 汇编优化p e n t i u m 4 执行条件下，许多此类应用的速度提升高达7 倍之多。 1 2 3 可编程流水线 传统的固定流水线，比如d 3 d 与o p e n g l ，如同一个电路图，上面有很多开 l o 浙江大学硕十学位论文第l 章绪论 关。我们可以打开或者关闭这些开关，还可以设置各个处理单元的参数达到控制 处理的方法，但是不管怎样整个系统的功能是确定的。你只能使用或者不使用某 些功能。这样的图形处理流水线被叫做固定流水线。如图1 8 所示为o p e n g l 的 固定绘制管线。 图1 8 传统流水线 在早期，图形程序开发者只能按照绘制的固定流水线进行开发。如果想实现 一些新的技术或者创意，必须等到新的3 da p i 发布或者等到图形卡生产厂商在 自己实现的o p e n g l 标准中添加新的功能。 当可编程流水线出现以后，这种限制就被打破了，开发者可以控制渲染过程。 c p u 将几何数据图元( 通常是三角形) 顶点的形式传送给g p u 。g p u 先在v e r t e x s h a d e r 中完成顶点处理，如是光照计算，坐标变换等操作。然后，再p i x e l f r a g m e n t s h a d e r 中完成像素处理，如纹理查询，颜色操作等。s h a d e r 是开发者编写的小程 序，他们是一些符合特定语法( 可以是g l s l 或h l s l ) 的脚本，被编译后送入g p u 进行运行。每次应用程序执行时都会把这些脚本送入g p u ，如果要实现不同的绘 制效果，只需要改写这些s h a d e r 就可以了。 浙江大学硕七学位论文第1 章绪论 a p p l i c a t i o n v e r t e x s h a d e r f r a g m e n t s h a d e r f r a m eb u f f e r 图1 9 可编程管线 图1 9 显示了渲染过程被v e r t e xs h a d e r 和f r a g m e n ts h a d e r 接管。这两部分代表了 g p u 的可编程能力。它们都是典型的流处理机( s t r e a mp r o c e s s o r ) ，这种流处理机 与向量处理机的区别在于，它不具有大容量的块存存储器用于读写，只是直接在 芯片上利用临时寄存器作流数据的操作。对于g p u 而言，图形流数据分别是顶 点图元和光栅化后的像素。按照图形处理的特点，g p u 流处理的元素为4 个单元 的向量，可以用于表示三维齐次坐标，三维空间齐次向量，颜色等。可编程流水 线的出现伴随着g p u 的迅速发展，开发者从原来的限制中解脱来了。随之关于 g p u 的新技术和新算法不断出现。 1 2 4g p u 编程语言 s h a d e r 这个词最早出现于闻名世界的3 d 公司p i x a r 开发的软件系统 r e n d e r m a n 。这个软件是用来描述整个场景的：从相机位置到几何对象再到最后 的渲染。r e n d e r m a n 在1 9 8 8 年出现，但是直到1 9 9 5 年在第一部全3 d 动画片玩 具总动员( t o ys t o r y ) 里显示了其威力后，才让人体会到其强大功能。 经过多年的发展，终于在2 0 0 1 年和2 0 0 2 年，普通显卡上也出现了着色语言 ( s h a d i n gl a n g u a g e ) 。在这一年，微软的d i r e t x 8 和8 1 实现了s h a d e rm o d e l1 0 到1 3 ，随后在d i r e c t x9 中提出了高级着照色语言h l s l ( h i g h l e v e ls h a d i n g l a n g u a g e ) 。在这之前，需要使用类似于汇编语言的语法来编写s h a d e r ，而h l s l 的出现让丌发者可以使用类似c 这样的高级语言来编写s h a d e r ，这样就使开发者 可以把精力更多地转移到算法上去了。同年n v i d i a 提出了c g ，随之a r b 也提 出了g l s l ( o p e n g ls h a d i n gl a n g u a g e ) 。h l s l ，c g 和g l s l 的语法基本一致， 1 2 浙江大学硕士学位论文第1 章绪论 一般在d i r e c t 3 d 环境中使用h l s l ，o p e n g l 环境中使用c g 或者g l s l 。 1 2 5g p g p u ( 基于g p u 的通用计算) g p g p u 是g e n e r a l p u r p o s ec o m p u t a t i o no ng p u s 的简称，主要是进行利用 g p u 来完成通用计算的研究。随着g p u 技术的高速发展，g p u 计算性能的大幅 度提高，g p u 已经不被局限于传统的图形学绘制计算了。很多其他算法都已经被 改进用于g p u 内计算，包括：高级绘制，全局光照明，计算机视觉，动态模拟， 基础数据压缩和数值算法等。 适合用于g p u 计算的算法一般具有这些特征：算法密集、高度并行、控制 简单、分多个阶段执行以及前馈( f e e df o r w a r d ) 流水线等。在计算过程中，一般把 大量的数据以纹理的形式送入g p u 然后通过g p u 的流处理器计算后再输出到帧 缓冲。计算结果在帧缓冲中以纹理的格式表达，每一个像素代表一个数据。通过 读取帧缓冲，可以得到计算结果。细分算法的高度规则性正好适合g p u 内的计 算，本文将g p u 用于体网格的细分算法。 浙江人学硕十学位论文 第2 章体例格细分算法 第2 章体网格细分算法 体网格是用来定义变形的一种工具，通过一定的方法将体网格变形后，再通 过插值可以得到变形后的模型。如果能找到一种细分方法s ，对基础体网格昂细 分后得到的网格p 是g 连续的那么，插值后得到的模型也是g 连续的。 p 七= s e o公式( 2 1 ) 一般的自由变形如果使用稀疏的体网格进行变形，就会使模型在网格体之间 出现不连续现象，而对稀疏的体网格细分后再变形得到的结果就不会出现这样的 情况。 2 1 无结构体网格的细分 所谓无结构的体网格是相对于结构化的体网格来说的。无结构的体网格是指 其内部的体的大小是均匀的，而不是大小不一根据特定的情况来设定的( 比如可 以将模型的一个手用一个网格包围，而另一个手用多个网格包围) 。 ( a ) ( ” 图2 1 在二维情况下无结构的网格和结构化的网格变形区别 图2 1 显示了二维情况下的这两种网格体。图2 1 ( a ) 左图显示了一个老鼠大脑图在 无结构的均匀四边形网格内的情况，图2 1 ( b ) 左图显示了根据老鼠大脑结构而特 别构造的结构化四边形网格。 2 1 1 无结构体网格细分算法简介 现在出现的体网格细分方法不是非常多，最早的体网格细分是山m a c c r a c k e n 1 4 浙江大学硕士学位论文第2 章体刚格细分算法 和j o y 在9 5 年提出的。他们提出了一种六面体网格细分的方法，但是这个方法 使用了过多的特殊情况，使得证明这个方法的连续性非常困难。b a j a jc ta l 则提出 了一种不同的六面体网格细分方法【引。可以很容易证明这种方法在网格内部都是 连续的，除了在基本网格的顶点上。 2 1 2 无结构体网格细分的缺点 ( 1 ) 为一个模型构造合适的无结构的体网格是一件很困难的事。 ( 2 ) 对无结构的体网格进行变形后得到的结果不如结构化的体网格结果好。图 2 1 ( a ) 为无结构网格体内的变形结果，图2 1 ( b ) 为结构化网格体内的变形结果， 后者要比前者好很多。 2 2 光滑的四面体网格细分 s c h a e f e r 等提出了一种光滑四面体网格细分的方法，并且这种方法可以用于 结构化体网格【9 1 。因为在实际中我们使用的多数都是组织过的体网格，因此这种 细分方法更具有应用价值。 2 2 1 一般四面体网格的细分 一般来讲，当对四面体进行细分时，我们可以分为两步，如图2 2 显示。 一锄斗，? 舟 图2 2 般细分 第一步，取叫面体每条边的中点，然后将这些巾点连起来形成4 个叫面体和1 个 八面体。第二步，把这个八面体的对应点连起来，使这个八面体变成4 个四面体。 但是这种方法存在着缺陷。由于将1 个八面体分成四个四面体方法有3 种( 对应 浙江大学硕士学位论文第2 章体网格细分算法 3 条对角线) ，这样就失去了一般性。这样导致体网格细分完成后，对体网格的连 续性分析就相当困难了。细分结果的连续性将沿着对角线的方向来，而每次细分， 对角线的选取都必须按照上一层的对角线来进行。更为关键的是，在基础网格上， 每个四面体都必须选择一个特定的对角线使得任何连续性分析都要遍历这些所 有的对角线情况。 2 2 2 改进的四面体网格细分 为了消除在细分过程中出现的对角线特殊性，s c h a e f e r 等引入一种新的细分 方法。这种细分方法在上面的第二步时不再切割八面体，而是将其保留下来。当 继续进行细分的时候，为八面体构造一种类似的细分方法，如图2 3 所示。 图2 3 对八面体和四面体的分割方法 由于这种细分结束后网格内保留有八面体和四面体两种形体，所以这种细分被称 为四面体八面体细分。这种细分方法分为线性分割和平滑两步。 2 2 2 1 线性分割 ( 1 ) 对于原网格内的每一个四面体，我们还是取每条边的中点，然后连成一个八 面体和四个四面体。( 如图2 3 第一行) ( 2 ) 对于原网格内的每个八面体，我们去每条边的中点和八面体的重心( 取八面体 六个点的平均值) ，然后将这些点连起来，形成六个八面体和八个四面体。( 如 图2 3 第二行) 1 6 浙江大学硕十学位论文第2 章体网格细分算法 2 2 2 2 平滑 将所有的体分割完后，要对每个体的顶点进行移动。在第一步分割结束后， 我们把每个分割后的四面体八面体单独看待，称其为子单元( c e l l ) 。对于每个 子单元( 分割后的四面体或八面体) ，子单元内每个顶点的都乘上图2 4 所示的 质心权值。对于四面体，被移动的点乘以兰1 6 ，而与其相连的点乘以旦4 8 。对于八 11 面体，被移动的点乘以三8 ，与其相连的点乘以击，而与其相对的点乘以丢。最 后，对于网格内的每个点，我们取包含它的那个子单元内这个点所对应的值，然 后将这些值加起来取平均。尽管在质心权值中存在负值( 弓) ，但是由线性分割和 平滑所得到的细分规则是凸线性组合的。 图2 4 质心权值 整个细分过程都是通过质心权值来表达的，所以这个细分方法很容易在计算 机上实现。我们首先计算线性分割，并把计算所得值赋给每个子单元顶点。然后， 在每个子单元内按照质心权值对顶点进行移动。最后，根据入度求每个点的值。 下面给出计算流程： 1 7 2 3 连续性分析 给定一个四面体基础网格p o ，需要分析其细分变形后的连续性。这个分析过 程可以分四种情况进行。 ( 1 ) 当点x 在四面体基础网格内部。 ( 2 ) 当点x 在由两个四面体共享的一个面上。 ( 3 ) 当点x 在由几个四面体共享的边上。 ( 4 ) 当点x 在基础网格的顶点上。 浙江大学硕十学位论文第2 章体网格细分算法 2 3 1 基础网格内部 首先看一下对一个四面体进行连续线性细分所得到的标准网格。假设这个四 面体网格的四个顶点为( 1 ，o ，o ，0 ) ，( 0 ，1 ，o ，o ) ，( 0 ，o ，1 ，o ) ，( o ，o ，0 ，1 ) ，经过k 1 次的连续线性细分后所得到的标准网格的每个顶点应该是去( f o ，如，毛) 。在这里 二 f ，是非负整数，并且加起来的值为2 。我们将基础网格放在平面而+ 五+ 而+ 为= l 上使得每个坐标都是对称的，并消除了任何方向性。 如果网格顶点的坐标可以为负数，我们可以通过细分法则得到一系列连续的 标准网格m 。可是，在两层这样的标准网格m 和m “1 之间，缩放关系很复杂( 由 于它们的位置关系) 。所以，我们把基础网格m o 平移到以原点为质心，那么所得 到的网格丝将在平面而+ 五+ 屯+ 而= o 上面。而网格的定点形式是瓴，之，毛) ， 1 在这里f ，的和为0 。经过平移后，对蛭进行细分得到扩大的网格寺心。 二 对这个无缩放的网格进行线性细分( 不做平滑这一步) 可以用一个以原点为 中心的帽函数刀( x ) 来表示。从这个细分法则的得到的帽函数为： 11 2 1 6 m 两( 2 卅吉荟犯卜哆) + 吉善刀( 2 x - y i i _ - ) 厶，= 1 v l 公式( 2 2 ) 这里的向量4 和所用来定义标准网格m 的偏移。这些向量与犯上在原点卜r i n g 领域内的顶点相对应( 见图2 5 ) ： 艿= 捐 歹0 ( 1 ，一1 ，0 ，o ) y = 排列( 1 ，一1 ，0 ，o ) 排列所得到的结果是没有重复的，它们和图2 5 右侧内的顶点一一对应( 艿有1 2 个元素，而y 有6 个元素) 。 1 9 浙江大学硕士学位论文第2 章体网格细分算法 i 被光滑点 豳上层体边上的点 小体内点 图2 5 线性分割的权值 接下来看一下平滑这一步对网格的作用。如果把第二节中提到的质心权值法 则应用到原点的卜r i n g 邻域内并进行平均值计算，这样得到的一组权值和原点 卜r i n g 邻域一一对应。而这些权值刚好是线性细分权值的i 1 。这是由于这组质心 权值是通过特别计算得到的。 这样就意味着在基础网格内部，经过两步前面所述的细分法则：线性细分， 平滑所得到的细分权值相当于公式( 2 2 ) 所示的帽函数在自己身上离散卷积结 果的i 1 。w a r r e n 在 1 0 中的结论显示，用一组细分权值在另一组细分权值上做离 散卷积所得到的新的权值所对应的基函数，就是对原来权值所对应的基函数的连 续卷积。在这里，帽函数，2 ( x ) 自己卷积自己的结果即为这种四面体细分法则所定 义的基函数。甩( 石) 是c o 连续的，那么它自己卷积自己所得到的结果即为一个c 2 连 续的函数。因此，这个细分法则在基础网格内部是c ，连续的。 2 3 2 基础网格的面上 虽然可以通过卷积的形式来分析基础网格内部的连续性，但是对于其它情况 浙江大学硕十学位论文第2 章体网格细分算法 ( 在面上，边上或顶点上) 则需要使用一些特殊的方法。这是因为对一个结构化的 网格进行线性细分后，虽然在基础网格内部是统一的，但是在四面体的面之间却 已经不统一了。细分后，在基础网格内的每一个面其实都是由一对四面体八面 体共享的。更确切地讲，通过线性细分所得到的无限网格m ，其实是对网格内每 个面所对应的四面体i ) k 面体对进行细分后得到的两个结果m ，进行结合的结果， 如图2 6 所示。 、 l i i i l ， ， 图2 6 由两个四面体) k 面体对共享的面进行细分后的结果。 为了证明这种细分法则是c 2 连续的，这里使用l e v i n 几e v i n 1 1 提出的联合 谱半径测试来分析四面体i l k 面体对之间的面的连续性。可以发现l e v i n l e v i n 对三角形四边形网格的分析与这里的面网格分析很相似：两个标准网格通过一 个内部的面被分开。 如果s 是网格m r 对应的细分矩阵，首先计算这个矩阵特征值五，和特征向量 z ；对应的方程： & ，= z 公式( 2 3 ) l e vin l e vin 的c 2 连续性测试需要检测三个条件： ( 1 ) 检测特征值兄j 是否具有如下形式： 2 l 浙江大学硕十学位论文第2 章体网格细分算法 l ，! ，! ，三，! ，! ，! ，! ，! ，三，! ，一i 公式( 2 4 ) 1 2 2 2 2 4 4 4 4 4 4 4 “、7 可以发现，子空问特征向量( z 。，z ：，z 3 ) 表达了m 厂。因此，这些向量构成了一个特 征表并覆盖了整个空问。 ( 2 ) 特征向量z 护，z 9 所对应的特征方程在特征映射后是否是二次方程。 ( 3 ) 这个细分法则的联合谱半径必须小于三4 。 第一个条件比较容易检测，只需求出细分矩阵的特征向量乃和特征值乃。第 二个条件可以通过二次插值的方法来进行检测。但是第三个条件的检测就比较麻 烦了。 图2 6 表示了一个基础网格内部的面被细分后的内部情况。为了进行联合谱 半径测试，我们必须构造4 个细分矩阵墨表达了图2 6 左边的四边形细分后成为 右边的四个子四边形。每个子四边形都是原四边形缩放并平移后得到的，并且从 他们得到墨。 构建完s 后，我们使用s 构建一个对角矩阵形，使得： 形- 1 & 形= ( 含荨) - 1 墨形= ( 孑荨) f ， 公式( 2 5 ) 这里a 是由公式( 2 4 ) 中对应的特征值组成的对角矩阵，而谚是对角线上的元素 和a 一样的上三角矩阵。可以用墨里的特征向量来构造，而且这些特征向量对 应于a 的特征值。 结下来进行联合谱半径测试，计算： 气k ，e ) = ( 坳0 k 蚓i o o ) 去 公式( 2 6 ) 在这罩。 1 ，4 ) 。如果对于某些k 可得纠 丑五以 ( 2 ) 由特征向= m z i ，z ：，z 3 构成的特征映射表是正则映射，并且单射的。 ( 3 ) 联合光谱半径( 1 ( k ，艺) ) 必须要比乃小。 第二个条件使连续性分析简化为谱半径中的功能测试。 由于m 。的边可能会被1 1 个四面体共享，这就使得z 1 ，z ：，z 3 的求解成为了一个 有n 种情况的符号函数。由于这个n 是不确定的，在这里计算了n 为3 到1 0 的 情况，并把结果可视化为图2 7 。 叼罾臼磅 国囝窃国 图2 7 度为3 到1 0 的边的特征映射 在这里，对细分法则进行这三个条件测试，分别讨算出一条边两端所对应的两个 浙江大学硕士学位论文第2 章体网格细分算法 细分矩阵s ，最。对于度为l o 以 3 ，计算得到的特征值为1 ，a ，五，圭，。对于 n = 3 ，则找不到一个k 使它满足联合光谱半径的条件。 2 3 4 基础网格顶点上 和边上的情况一样，目前还没有方法用于分析基础网格顶点上的连续性。但 是通过类似的方法可以认为在基础网格定点上是基本连续的，虽然在有些特殊点 上是不连续的。 2 4 在自由变形中的应用 假设r 为控制网格，x 为控制网格里的一点。那么作用于r 上的变形映射会 使r 里的x 变换到厂似) 里的新位置厂( z ) 。如果对尺进行c 连续的细分后再进行 变形映射f ，那么f 在局部范围内即为c 连续。图2 8 显示了变形映射的过程。 f 图2 8 变形映射 在实际的体变形中，我们首先对基础网格p 进行k 次连续细分，得到一个逼 近极限网格p 舒的网格p 。然后，我们对于每个在p 内的点x ，找到包含它的四 面体或八面体，并计算出这个四面体八面体对于这个点的凸组合使得： x = 群 l 公式( 2 6 ) 其中p ；为e k 上的顶点。对p o 进行变形得到群，再对p i o , z - z i i 群。那么 变形函数f ( x ) 可以表示为： 2 4 浙江大学硕士学位论文 第2 章体网格细分算法 2 5 实验结果 厂( x ) = 哆钟公式( 2 7 ) f 本章的算法在一台1 g 内存，3 0 g h zc p u 电脑上实现，所有计算都使用c p u 。 图2 9 显示了一个由两个四面体构成的体网格被细分的过程。图2 1 0 为b u n n y 模型的控制网格被细分过程。值得注意的是，由于在细分过程中，控制网格会收 缩，所以我们在构造控制网格的时候要适当地扩大控制网格。这样经过几次细分 后的控制网格仍旧可以包围住模型。 、 图2 9 简单网格细分过程 图2 1 0b u n n y 模型控制网格细分过程 图2 1 1 显示了用细分后的控制网格来驱动模型变形的过程。每次变形时，首先对 浙