三维服装表面模型的离散Marching Cubes算法.pdf

《三维服装表面模型的离散Marching Cubes算法.pdf》由会员分享，可在线阅读，更多相关《三维服装表面模型的离散Marching Cubes算法.pdf（6页珍藏版）》请在三一文库上搜索。

1、第3 0 卷第4 期 2 0 0 9 年4 月 纺织学报 J o u r n a lo fT e x t i l eR e s e a r c h V 0 1 3 0 A p r N o 4 2 0 0 9 文章编号：0 2 5 3 9 7 2 1 ( 2 0 0 9 ) 0 4 - 0 1 2 9 0 6 三维服装表面模型的离散M a r c h i n gC u b e s 算法 黄敏1 ，张 剑2 ( 1 广东纺织职业技术学院服装艺术系，广东佛山5 2 8 0 4 1 ；2 华南理工大学计算机科学与T 程学院，广东广州5 1 0 6 4 1 ) 摘要对三维服装表面模型的重构简化算法进行了

2、研究。在三维表面模型和化简方面采用了离散M a r c h i n g C u b e s ( D i s c M c ) 算法，将离散的思想应用到三角面片的化简中，耗时插值计算量被降至最低，使得原有系统在重构效 率和效果上都有极大的改善。位于同一平面且相邻的三角面片都进行合并，可以达到很高的简化比，算法效率很 高，同时保持有限的精度损失，保持服装表面模型细微结构不会被D i s c M C 的简化过程所破坏，D I s c M C 优于其他算 法。从算法描述实验可知，D i s c M C 仅限于原始体数据的密度值都在网格点上，并且简化是一次性的，不会反复进行 简化，因此，非常适应于服装系统

3、的三维表面模型简化。 关键词三维表面重构；M a r c h i n gC u b e s 算法；三角面片；扫描；插值；服装 中图分类号：T S9 4 1 2 6文献标志码：A D i s c r e t eM a r c h i n gC u b e sa l g o r i t h mf o rs u r f a c em o d e lo f t h r e e d i m e n s i o n a lc o s t u m e H U A N GM i n l ，Z H A N GJ i a n 2 ( 1 D e p a r t m e n to fF a s h i o n &

4、A r t ，G u a n g d o n gI n s t i t u t eo fT e x t i l eT e c h n o l o g y ，F o s h a n ，G u a n g d o n g5 2 8 0 4 1 ，C h i n a ； 2 & h o do fC o m p u t e rS c - i e r l l c ea n d 西彬聊e 而曙，S o u t hC h i n aU n i v e r s i t yo fT e c h n o l o g y ，G u a n g z h o u ，G u a n g d o n g5 1 0 6 4

5、1 ，C h i n a ) A b s t r a c tT h ep a p e rc a r r i e so u tf u r t h e rr e s e a r c h e sa b o u tt h ea l g o r i t h mo fr e c o n s t r u c t i n ga n ds i m p l i f y i n gt h e s u r f a c em o d e lo ft h r e e d i m e n s i o n a lc o s t u m e ，a n da d o p t st h eD i s c r e t eM a r

6、c h i n gC u b e s ( D i s c M c ) a l g o r i t h mt o a p p l yt h e d i s c r e t ei d e at os i m p l i f y i n gt h e t r i a n g l ei n t e r f a c e ，t h u st h ei n t e r p o l a t i n gv a l u ew h i c h i st i m e - c o n s u m i n gi sr e d u c e dt ot h el o w e s t8 0t h a tt h er e b u

7、 i l d i n ge f f i c i e n c ya n de f f e c to ft h ef o r m e rs y s t e ma r eg r e a t l y i m p r o v e d T h et r i a n g l ei n t e r f a c e si nt h e8 a n l ep l a n ea n di nt h en e i g h h o u ra r ei n c o r p o r a t e d 。i tg e t s 锄e x c e l l e n t r a t i oo fs i m p l i f i c a t

8、 i o n ，h i s h e f f i c i e n c y o f t h e a l g o r i t h m ，k e e p s ar e s t r i c t e d l o s s o fp r e c i s i o na n dt h e m i c r o s t r u e t u r eo fs u r f a c em o d e lo fc o s t u m e sw i t h o u tb e i n gd e s t r o y e di nt h es i m p l i f y i n gp r o c e s so fD i s c M C

9、 I ti s v e r yo b v i o u st h a tt h eD i s c M Ci sa d v a n t a g e o u so v e ro t h e rs i m p l i f y i n ga l g o r i t h m s I na d d i t i o n ，i ti ss e e nf r o mt h e d e s e r i p t i v ee x p e r i m e n ta b o u tt h ea l g o r i t h mt h a tt h eD i s c M Ci so n l yc o n f i n e dt

10、 ot h ep o i n tw h o s ed e n s i t yo fr a W d a t ai so nt h e 蜊da n ds i m p l i f y i n gi sc o n d u c t e do n l yo n et i m er a t h e rt h a nr e p e a t e d l y ，t h e r e f o r e ，i ti sv e r y s u i t a b l ef o rs i m p l i f y i n gt h e3 - Ds u r f a c em o d e lo fc o s t u m e s K e

11、 yw o r d s r e c o n s t r u c t i o no ft h r e e d i m e n s i o n a li n t e r f a c e ；M a r c h i n gC u b e sa l g o r i t h m ；t r i a n g l ei n t e r f a c e ； s c a n ；i n t e r p o l a t i n gv a l u e ；c o s t u m e 随着计算机图形技术特别是硬件图形设备的不 断发展，服装三维表面在计算机中的表示逐渐趋于 三角面片网格模型，在三维服装的造型过程中，目前 最终的

12、造型结果一般都表示成为三角面片网格。所 以，计算机图形学界的各种表面简化算法也都是基 于三角面片网格进行的。 收稿日期：2 0 0 8 0 3 2 4修回日期：2 0 0 8 一t O 一1 7 基金项目：中国博士后科学基金资助项目( 2 0 0 r 7 0 4 1 0 8 2 5 ) ；广东省自然科学基金资助项目( 7 3 0 1 7 1 3 ) 作者简介：黄敏( 1 9 6 8 一) ，女。副教授，硕士。研究方向为服装设计与工程、服装C A D 技术。张剑，通讯作者。E - m a i l ：z j 3 3 1 9 8 9 6 1 6 3 c o m o 万方数据 PDF Watermar

13、k Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark 1 3 0 纺织学报第3 0 卷 1三角面片网格模型 三维表面模型的来源不同，它的三角面片集的 结构特点也不一样，主要表现在：1 ) 通过三维造型系 统产生的三角面片网格比较有规律，但是大小、形状 变化很大，在表面曲率大的地方三角面片比较密集， 曲率小的地方比较稀疏，这是一种比较理想的三角 面片结构，但这在三维系统对表面的各种参数已知， 且在形状比较规整的情况下才能得到；2 ) 通过三维 扫描设备得到的三角面片集合比较杂乱，但是大小、 形状差别不是很

14、大，三角面片分布的密度不随表面 曲率的变化而变化，对微小细节表达不够；3 ) 通过体 数据提取的表面模型分布均匀，三角面片分布的密 度不随表面曲率的变化而变化，可以通过降低取样 间隔来增强对微小细节的分辨能力，但是平坦部分 的三角面片密度也会随之上升，增大数据量。为 此，在服装三维系统有限的精度损失内，在三角面片 网格中去除网格中的冗余信息，使数据量变小，便于 处理和提高实时交互速度，并在三维表面通过不同 数目的三角面片进行近似，以便在需求和硬件能力 之间找到一个折衷点心o ，实现多分辨率模型 ( M u h i r e s o l u i o n ) o 2 三维表面模型简化算法 已提出的简

15、化算法有2 类：第1 类是在已经获 得三角面片网格之后依据一定的评价准则和简化算 法对三角面片实施简化；第2 类与三维表面重构过 程紧密结合，在等值面的生成过程中即随着表面曲 率的变化自适应地生成三角面片。 第1 类简化算法的应用范围比较广泛，它的原 始数据来源可以是第1 小节中提到的3 种来源中的 任何一种。这类算法一般由简化步骤和评价准则组 成。简化步骤包括顶点合并、面片合并、重新取样等 几种方法，并通过反复实施同一简化步骤直到达到 所需要求；评价准则是指在反复实施简化步骤的过 程中，每一步如何选取被合并的顶点或面片。如： H o p p e 的顶点合并的多精度模型b 1 ，C o h e

16、 n 等的简化 包围盒算法1 ，T a o s o n gH e 等的基于体元的三维物 体简化算法口 。 第2 类算法的应用范围相对狭窄，只能用于从 体数据中提取三维表面的重构算法之中，但相对 第1 类算法而言更好地利用了体数据的空间相关 性。它不用像第1 类算法那样反复从所有节点或者 面片中进行选择，而只要在三维表面重构的过程中 自适应地实施简化，避免了很多节点坐标的插值计 算，因此，算法的效率更高。同时，由于第1 类算法 节点之间没有空间的相关性，为了达到实用的效率， 不得不以更高的精度损失为代价，所以相对第2 类 算法的精度损失也比较小，即本文研究的离散 M a r c h i n gC

17、 u b e s 算法( D i s c M C ) 妯oo 3 离散M a r c h i n gC u b e s 算法 3 1 基本原理 离散M a r c h i n gC u b e s 算法简称D i s c M C ，它将三 维表面的重构和简化过程融为一体，在等值面生成 过程中自适应完成面片合并。与其他简化算法相 比，D i s c M C 具有效率高，简化比例高，损失精度小等 优点，属于从体数据中提取t 三维表面的重构算法。 D i s c M C 还采用非常简捷的办法解决了经典M a r c h i n g C u b e s 算法中的二义性问题口j 。 图1 用一个简单例子

18、示出了D i s c M C 算法流程。 其中a 图是4 个相邻的体元( C u b e s ) ，带有黑点的内 侧9 个顶点位于等值面内，另外9 个顶点位于等值 面外；b 图为用经典的M a r c h i n gC u b e s 算法构造等值 面三角面片的结果；c 、d 、e3 图说明了D i s c M C 的构 造和简化流程。经典M a r c h i n gC u b e s 算法直接根据 这4 个体元顶点的内外状态构造出8 个三角面片， 这些三角面片顶点是根据所在边的2 个顶点的密度 值通过插值计算得出。 3 2 算法步骤 D i s c M C 中“离散”的思想就是延后插值计算

19、，之 前生成的三角面片全部用离散值表示，也就是说，三 角面片所处平面的位置、方向，在所处体元中的位 置、形态全部都是离散量，仅有有限数目的可能 取值。 3 2 1 扫描 首先，所有与等值面相交的体元被逐一扫描，根 据其8 个顶点的内外状态按照规定好的方式生成三 角面片。在扫描过程中，所有生成的三角面片只是 用它所在体元的位置和其形态的编号进行记录，并 不计算实际的顶点坐标值。三角面片生成后就马上 根据其所处的平面方向和位置存储在1 个2 层的链 表结构中，如图2 所示。第1 个层次存储2 6 个不同 的平面方向，每个元素指向另一个链表，该链表存储 了这个方向上的一系列平行的平面；第2 个层次上

20、 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark 第4 期 黄敏等：三维服装表面模型的离散M a r c h i n gC u b e s 算法 ， 1 3 1 M a r c h i n gC u b e s 扫描值 D i s c r e t eM a r c h i n gC u b e 离散值 画p 画p 画 C 图1 F i g I I N C I D E N C E S 生成面 de D i s c M C 的算法流程 F l o wo fD i s

21、c M C a l g o r i t h m 图2 存储三角面片的2 层链表结构 F i g 2 S t r u c t u r ea b o u tt w ol a y e rc h a i nt a b l eo fm e m o r y 硒彻西ei n t e r f a c e 每一个元素均是一个链表，存储该平面上已生成的 三角面片，这样存储的三角面片只需用它在该平面 上的位置信息记录即可，这样也便于后面合并过程 的进行。图中以Z = C 平面为例画出了这个2 层链 表结构的示意图。 3 2 2 合并 三角面片生成后，将所有邻接且位于同一平面 的三角面片合并成大的多边形，再将得到的多

22、边形 划分为尽可能大的凸多边形，最后再将得到的凸多 边形划分成三角形。这样，合并过程又分合并、分 割、三角形划分。 合并：将扫描步骤中产生的在同一平面又相邻 的小三角面片合并，形成大的多边形。在合并过程 中，每个在扫描过程中形成的同一平面上的三角面 片被重新以“异或”模式写入一个二维数组，这样，这 些三角面片就自然“合并”。数组中仅剩下合并后多 边形的边界。另外，所有三角面片的水平边也不需 要记录，只要记录垂直边和斜边就可以表示多边形 边界。合并的多边形有可能是凹多边形或者中间带 孔的多边形，在编程时必须考虑。 分割：将合并得到的多边形分割为一个个小凸 多边形，以便进行下一步的三角形分割。凸多

23、边形 分割是按水平方向自上而下进行。分割完成后，每 个凸多边形的信息便从二维数组中提取出来，按照 逆时针的顺序将其顶点存储在一个链表中，由于每 个凸多边形的顶点数最多是8 ，所以实现中用数组 存储效率更高。 三角形划分：将分割得到的各个凸多边形最后 化分为三角形，形成三角面片网格模型。因为多数 三维图形库( 如O p e n G L ) 在进行光照渲染时一般先 计算出顶点的光照效果，再根据顶点的颜色采用插 值的方法计算三角面片中间部分的色彩o ，如果从 一个顶点引出太多的三角面片，将影响三维服装的 渲染效果，所以，在三角形划分中，尽量采用三角形 条带的划分方法( 即按“之”字形划分) ，少采用

24、扇状 的划分方法。 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark 1 3 2 纺织学报第3 0 卷 三角形划分看起来非常简单，只要按“之”字形 的连接方法即可轻松地完成任何一个凸多边形的三 角形划分，但是，当三角面的顶点最终经过插值计算 后，在“T ”型节点处就会出现裂痕，这是因为插值计 算之后，顶点的坐标将发生偏移，不一定再位于其相 邻三角形的相应边上。解决办法就是找出所有这样 的“T ”型节点，把它们也加到自己所属的凸多边形 当中，然后再进行三角形划分。这时

25、，单纯的采用 “之”字形的三角形条带划分方法就不行了，这将导 致产生面积为零的三角形面片，但是，在每个凸多边 形开始划分的时候仍然尽量按照“之”字形的规则进 行划分，直到最后只剩下一个三角形且所有的“T ” 型节点都位于一条边上的时候再采用扇状的划分方 法进行划分。 3 2 3 插值 三角面片的节点的坐标值通过线性插值计算， 同经典的M a r c h i n gC u b e s ( M C ) 算法一样。以x 坐标 为例，有 菇1d l + 戈5d 5 知2 百百 式中：茗。、菇，、菇，为节( 顶) 点位；d ，、d ，为节点1 与节 点5 的体密度值。， 这里与经典M C 算法的不同之处

26、是D i s c M C 的 节点有可能位于体元中央，可用下述算法程序来对 它的坐标进行插值计算。 4 算法程序 在W i n d o w s 环境下，采用V i s u a lC + + 6 0 编 程n 】，应用M F C 、O p e n G L 等相关技术，其D i s c M C 算 法实现的框架伪代码如下： 清除当前正在显示的三维表面的数据结构； 从断层轮廓线文件( V O L ) 或者C T 数据与处理 文件( P R E ) 中读取原始数 i f 从V O L 文件中读取数据 通过轮廓线数据进行体数据的填充； 清除断层轮廓线的数据结构； f o r ( 对每一个物体) 初始化存

27、储扫描形成的三角面片的两层链表 结构I N C I D E N C E ； f o r ( 对每个个体元) 查表找到对应的三角面片分布情况； 将每一个三角面片根据其平面方向和所处位 置加入I N C I D E N C E 初始化三角面片链表F a c e L i s t 、顶点链表 P o i n t L i s t 和多边形链表P o l f o r ( 对I N C I D E N C E 中的每一个平面) 清空用于合并的二维数组M e r g e r ； f o r ( 对于该平面上的每个三角形或矩形) 查表找到该三角形或矩形的边对应于 M e r g e r 中的编号； ， 以异或模

28、式将每条边写入M e r g e r ； 至上而下扫描M e r g e r ，将合并的图形划分为 凸多边形，加人P o l y L i s t ， _ ，一 ； 将P o l y L i s t 中涉及到的顶点加入P o i n t L i s t ，同时 建立聩点的逆向索引； f o r ( P o l y L i s t 中的每个凸多边形) 检查其边界上( 不含端点) 是否有点在 P o i n t L i s t 中； 找到这样的“T ”型点，加入该多边形，同时做 标记； ， 进行“之”字形的三角形划分，生成的三角面 片加入F a c e L i s t i f ( 不能划分完) 进行

29、扇状划分； 清除P o l y L i s t ； 清除I N C I D E N C E ； 将F a c e L i s t 中的数据转移到数组F a c e A r r a y 中； 清除F a c e L i s t ；将P o i n t L i s t 中的数据转移到 数组V e r t e x A r r a y 中，同时进行插值； 清除P o i n t L i s t ； 对所有顶点计算其法向量； 进行O p e n G L 的有关设置，准备显示。 5实验分析 5 1 运行数据比较 运行环境P e n t i u m 1G R A M ，W i n d o w s2 0 0

30、0 P r o f e s s i o n a l 。表1 列出了裤膝关节部位模型轮廓和 膝关节部位模型断层轮廓线数据实验结果的比较， 其中膝关节部位模型轮廓是预处理数据。 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark 第4 期黄敏等：三维服装表面模型的离散M a r c h i n gC u b e s 算法 。1 3 3 。 从表1 可以看出，在重构时间、三角面片数量方 面M e d 3 D 2 均优于M e d V i e w ，一般来说，随着取样间 隔的

31、缩短，三角面片网格密度增大，M e d 3 D 2 的三角 面片缩减比例也随之升高，也就是说，在高密度的三 角面片网格上，M e d 3 D 2 的简化效果更加明显。 5 2 重构效果比较 三角面片格式的简化使得存储空间减少、交互 速度提高，但这不能以重构服装表面精度和效果的 损失为代价。图3 为由D I C O M 和M e d 3 D 2 重构出 膝关节部位模型轮廓的效果图。可以看出，M e d 3 D 2 重构得到的三维表面与采用经典M a r c h i n gC u b e s 算 法的D I C O M 重构得到的三维表面从质量上无明显 差别，甚至在微小细节的表现上M e d 3

32、D 2 还优于 D I C O M ，这是由于M e d 3 D 2 在第1 步扫描时比经典的 M a r c h i n gC u b e s 多引入了1 个体元中间的点，从而对 于微小细节的表现更加充分。 图3D I C O M 和M e d 3 D 2 重构效果比较 F i g 3R e c o 咖c 6 I l ge f f e c tc o m p a r e dD I C O M ( a ) w i t hM e d 3 D 2 ( b ) 5 3简化效果 D i s c M C 简化过程是M e d 3 D 2 的算法核心，也是 M e d 3 D 2 优于其他系统( M e d

33、 V i e w ，D I C O M ) 的关键部 分。图4 显示了M e d 3 D 2 三角面片简化的效果。可 以看出，由于取样是均匀的，简化前的三角面片分布 基本上是均匀的，而简化后三角面片分布则随着三 维表面曲率的变化而变化，曲率大的地方，三角面片 分布密集，表面相对平坦的地方，三角面片的面积也 比较大。采用了“之”字形和扇状分割相结合的三角 形划分算法，简化后的三角面片网格也没有出现过 畸形。 图4M e d 3 D 2 的简化效果 F i g 4 E f f e c ts i m p l i f i e do fM e d 3 D 2 ( a ) U n s i m p l i

34、f i e d ； ( b ) S i m p l i f i e d 6 结语 从上述算法描述的实验结果可以看出，D i s c M C 具有以下特点：1 ) 由于D i s c M C 算法的主要部分是 基于离散值，耗时插值计算量被降至最低，故算法效 率很高；2 ) 简化后的三维表面与原来的表面拓扑同 态，而其他简化算法( 特别是采用顶点合并的一类算 法) 并没有这个性质；3 ) 由于位于同一平面且相邻的 三角面片都进行合并，所以如果初始三维表面比较 平坦，可以达到很高的简化比，同时保持有限的精度 损失；4 ) 可以保持细微结构，只要某细微结构在 第1 次的扫描中能够体现出来，则它就不会被

35、 D i s c M C 的简化过程所破坏，这也是D i s e M C 优于其 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark 1 3 4 纺织学报第3 0 卷 他简化算法的地方。 当然，D i s c M C 也有其不足：1 ) D i s c M C 仅限于应 用在M a r c h i n gC u b e s 算法的场合，即原始体数据的密 度值都在网格点上，这也是几乎所有第2 类算法的 不足之处；2 ) D i s c M C 的简化是一次性的，不像很多

36、 第1 类算法那样可以根据用户要求反复进行简化， 直到要求得到满足。这一特性在多分辨率模型、三 维模型网络渐进传输等应用环境中是关键的，但是 在服装三维系统中并非必需；所以，采用D i s c M C 算 法作为服装三维系统的表面模型简化算法是非常合 适的。 F Z X B 参考文献： I H U A N GM i n ，Z H A N GJ i a n Av i e w - d r e s sb a s e dM 9 0 f i t h m f o rr e b u i l d i n g3 Dm o d e l s J J o u r n a lo f D o n g h u a U n

37、i v e r s i t y ，2 0 0 5 ( 5 ) ：8 2 8 7 2 张剑，黄敏服装C A D 技术 M 北京：清华大学出版 社，2 0 0 3 ：1 9 3 2 Z H A N GJ i a n ，H U A N GM i n D r e s sC A D sT e c h n i q u e M 3 4 5 】 6 7 8 B e i j i n g ：T s i n g h u aU n i v e r s i t yP r e s s 。2 0 0 3 ：1 9 3 2 H U G H E SH o p p e P r o g r e s s i v em e s h e

38、 s J C o m p u t e r G r a p h i c s ，2 0 0 6 ，3 0 ( 6 ) ：1 3 一1 7 J O NC o h e n S i m p l i f i c a t i o ne n v e l o p e s J C o m p u t e r G r a p h i c s ，2 0 0 6 ，3 0 ( 6 ) ：6 4 6 9 H ET a o s o n g 。H O N GL V o x e b b a s e do b j e c ts i m p l i f i c a t i o n C P r o c e e d i n g sV

39、i s u a l i z a t i o n9 5 A t l a n t a ：I E E EC o m p u t e r S o c i e t yP r e s s ，1 9 9 5 ：2 9 6 3 0 3 黄敏，杨念，张剑基于雅可比算法的三维着装模特 儿模型重建 J 东华大学学报，2 0 0 7 ，3 0 ( 5 ) ：4 2 4 6 H U A N GM i n 。Y A N GN i a n ，Z H A N GJ i a n T h er e c o n s t r u c to f w e a r - h u m a nb o d y B3 Dm o d e lb a s

40、 e do nj a c o h ia l g o r i t h m J J o u r n a lo fD o n s h 呻U n i v e r s i t y ，2 0 0 7 ，3 0 ( 5 ) ：4 2 4 6 M O O R ED C o m p a c tI s o c o n t o u r sF r o mS a m p l e dD a t a M s L ：G r a p h i c sG e m sA c a d e l I l i cP r e s s ，2 0 0 6 ：2 3 2 8 周长发科学与工程V i s u a lC + + M 北京：清华大 学出版

41、社，2 0 0 2 ：l l l 一1 3 5 Z H O UC h n g f a S c i e n t i f i cK n o w l e d g eT o g e t h e rw i t h P r o j e c t V i s u a lC + + M B e i j i n g ：T s i n g h u aU n i v e r s i t yP r e s s ， 2 0 0 2 ：1 1 1 1 3 5 万方数据 PDF Watermark Remover DEMO : Purchase from www.PDFWatermarkR to remove the watermark