<4D F736F F F696E74202D20CAFDD7D6BCB8BACEB4A6C0EDBFCEBCFEA3ADCEE2BBB3D3EE2E707074>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20CAFDD7D6BCB8BACEB4A6C0EDBFCEBCFEA3ADCEE2BBB3D3EE2E707074>"

姻艾
5 years ago
Views:

1 数字几何处理概述吴怀宇

2 引言随着计算机运算能力和存储能力的大大提高以及图形处理器 (GPU) 的出现 ; 三维图形学技术在游戏工业影视工业制造工业虚拟现实和互联网 (Internet) 等领域应用已经越来越广泛 ; 人们也不再满足传统媒体通过固定视角对物体和环境进行观察, 而希望从全方位浸入式交互地与逼真的虚拟物体或虚拟环境进行交流

3 游戏工业影视工业应用之一

4 应用之二制造工业 CAD 结构材料的性能模拟 ;

5 应用之三三维数字城市 ( 城市导航 ; 灾难模拟和救护 ; 反恐演习 )

6 应用之四医学领域 ( 医学可视化病灶检测和观察辅助治疗 ); 考古复原, 对古生物的运动行为分析和模拟

7 虚拟现实教学训练应用之五

8 应用之六文化遗产保护艺术历史 ;

9 应用之七电子商务互联网 (Internet);

10 背景介绍与研究内容三维网格模型作为计算机图形学的主要数据载体, 也正逐渐成为继音频 (1 维 ) 图像 (2 维 ) 和视频 (2 维 + 时间维 ) 之后的第 4 代多媒体数据类型本文要所讨论的数字几何处理, 就是专门用来处理三维网格模型的数字媒体技术一门典型的交叉学科学术活动 : 计算机图形学 (SIGGRAPH EG) 计算机视觉与模式识别 (ICCV CVPR) 数字信号处理 (ICASSP) 多媒体技术 (ACM MM) 机器学习 (ICML AAAI)

11 数字几何处理 (DGP)

12 数字几何处理 (DGP) 数字几何模型是真实世界的各种物理实体的数字化表示, 亦即数字化的物理实体通过这些离散化的模型, 对现实世界的连续物理性质和规律进行逼近, 并保持必要的内蕴特征, 如一阶和二阶微分属性的保持数字几何处理的特点和难点 : 数据量大百万级的面片模型已越来越普遍拓扑复杂经采集得到的三维模型通常具有非常复杂的拓扑结构, 以及不同程度的几何拓扑缺失或者错误非均匀采样与非正则性任意流形曲面使现有数字信号处理的理论和方法不能直接用于解决其中的难题, 必须建立新的体系和方法

13 数字几何处理的研究内容三维模型的获取配准与重建几何拓扑的修复网格平滑与去噪

14 数字几何处理的研究内容重网格化和子分网格三维网格压缩网格分割

15 参数化交叉参数化 ( 一致对应 ) 网格形变编辑与动画 3D 数据重定向技术

16 数字几何处理研究实例模型转导任意流形曲面的一致对应一种用于实时分割 3D 网格的笔划式交互框架凸包交叉参数化用于形状保持网格处理的均值流形操作符

Deformation Transfer( 形变传递 ) (R. W. Sumner et al.

17 1 模型转导在 SIGGRAPH 2001 和 2004 分别提出 Expression Cloning 和 Deformation Transfer 技术, 用来将源网格的形变克隆 / 传递到目标网格上 Deformation Transfer( 形变传递 ) (R. W. Sumner et al., SIGGRAPH 2004) Expression Cloning( 表情克隆 ) (J. Noh et al., SIGGRAPH 2001)

18 模型转导动机 : 现在我们考虑与此相似但不相同的一个问题, 即不给定源参考模型, 而是直接将源形变模型的姿态传递到目标参考模型我们将其称之为模型转导 (Model Transduction)

19 模型转导如果源和目标参考模型具有不同的姿态, 形变传递方法 (DF) 无法得到令人满意的结果而使用我们的模型转导方法 (MT), 即使在缺少源参考模型的情况下, 狮子模型也能正确地模仿猫的姿态

20 模型转导具体思路为首先求解出目标参考模型和源模型的一致对应, 并通过计算局部仿射变换来得到姿态网格, 然后根据曲面局部微分几何属性进行求解

21 模型转导第一步 : 建立对应并生成匹配网格我们需要在源网格和目标网格之间建立对应首先, 用户在网格模型上标识出一些特征对应点这些特征点通常位于目标的生物测量位置, 如肩膀, 肘部和腕部特征对应时应注意保持语义上的一致, 如 : 头 - 头, 腿 - 腿然后, 我们采用将在第二章提出的一致对应方法生成一个兼容匹配网格, 即在源和目标模型之间建立一个一致对应

22 模型转导第二步 : 获得姿态网格我们的目标是获得一个用于姿态表征的网格, 其首先通过拆解 (de-attach) 参考目标网格上的所有三角形而保持它们不被扭曲, 然后将每个三角形贴 (re-attach) 到匹配网格的对应三角形上为了保证刚体变换 ( 即没有扭曲 ), 我们首先对每一个三角形计算仿射变换, 然后从中提取旋转和平移分量

23 模型转导第二步 : 获得姿态网格奇异值分解 (SVD) 从仿射矩阵中提取旋转分量和扭曲缩放分量 : T Q = A D B = ( A B )( B D B ) = R S k k k k k k k k k k k 其中 A B R 为旋转矩阵, D = diag( d, d, d ), d k k k k k k k k = ( λk + λk + λk )/3( λk为 Qk的奇异值 ) R k 我们使用矩阵对目标网格三角形进行旋转, 并将其平移到匹配网格三角形上来获得姿态三角形

24 模型转导第三步 : 基于细节保持约束和平滑约束对姿态三角形进行重新组合姿态网格的三角形是分离的, 因此实际上并没有形成一个真正意义上的网格为了将这些三角形面片组合起来形成最终的重定向结果, 我们将彼此邻接的三角形放置在一起, 并施加必要的微分细节保持约束和平滑约束

25 模型转导第一项指出形状细节在经过变换之后仍被保持 ; ( 描述形状细节的离散微分算子将在第 5 章介绍 ) 第二项指出形变在邻接三角形之间应该是平滑的 ; 最后一项将平移运动施加在非连接的三角形上 ; 优化问题最终归结为一个稀疏线性系统的求解, 结果返回最优的顶点位置

26 模型转导

27 其他应用之一 : 各种网格编辑操作之后的姿态修正由 MAYA 生成由我们的方法自动进行修正

28 其他应用之二 : 基于 3D 运动捕捉数据的免骨架形变动画通过我们的免骨架蒙皮技术 (skeleton-free skinning technique), 运动捕捉 (motion capture: Mocap) 所获得标识点数据可直接用来驱动角色模型, 即无需对这些标识点建立骨架结构此外, 我们方法的计算复杂度与标识点的数目无关, 这是因为这些点仅以二次平方形式来作为求解系统的空间约束

29 本例小节提出了一种在不同三角网格间传递姿态的有效方法模型转导方法首先从源模型中提取姿态信息并将其直接重定向到目标模型, 而无需构架骨架结构或使用额外的参考源网格来获得源形变

30 数字几何处理研究实例模型转导任意流形曲面的一致对应一种用于实时分割 3D 网格的笔划式交互框架凸包交叉参数化用于形状保持网格处理的均值流形操作符

31 2 任意流形曲面的一致对应提出在任意流形网格之间建立一致对应的一种新框架不同于存在的方法, 该方法直接把源网格的拓扑映射到目标网格上, 而无需建立中间域和进行网格分割, 这样有效地避免了处理各种不稳定的复杂情况 ( 如高亏格复杂的边界等等 ) 相比于以前的方法, 该方法需要更少的特征对应点 marker, 具有更快的速度且更鲁棒

32 任意流形曲面的一致对应已有的方法属于间接方法首先需要构造一个临时的公共参数化域然后, 对每个模型分别建立和公共参数化域之间的子映射最后, 模型之间的映射通过子映射的合成来获得然而, 对于这些间接方案, 如何高效并鲁棒地构造良好的 (well-shaped) 兼容分块 (patch layouts) 是一项困难的任务, 尤其在拓扑复杂或者狭长的区域此外, 在合成映射的过程中, 子映射的误差可能会被放大, 这样可能导致最终的交叉映射在某些地方会有大的误差间接方案的另一个缺点是 : 虽然映射在每一个分块中是连续的, 但分块边界的过渡部分可能并不连续的

33 任意流形曲面的一致对应直接在 3D-3D 空间构造形状保持对应, 而无需将 3D 表面分割并展平到 2D 平面中去 ( 即通常的 3D-2D-2D-3D 过程 ), 这样有效避免了误差放大分区边界的不连续, 以及各种需要小心处理的情况, 如交叉, 阻塞, 轮转次序, 等等这种直接的构建方法显式地考虑形状保持属性, 关键点检测和匹配方案也显著地减少了逼近误差, 即使在输入模型之间具有非常不同的几何特征和采样率时也可取得好的效果

34 一致对应框架的三个步骤 (a) 首先, 提出了一种新的均值拉普拉斯匹配方案, 其旨在直接在 3D 空间计算形状保持对应 (b) 然后, 为了使输出的兼容网格能够更精确地匹配目标网格的重要特征, 我们引入了一种快速有效的方法来检测关键点并利用它们来很好地匹配目标网格的特征和轮廓 (c) 最后, 提出了一种顶点重分配和投影方法, 其通过局部保角的方式来进一步优化初始匹配结果初始结果的每一个顶点被渐进地投影到目标模型上以确保生成完全的曲面匹配

35 (a) 均值拉普拉斯匹配方案该匹配方案基于能量最小化框架旨在获得形状保持 ( 保角 ) 对应, 并避免了少数标识点所可能导致的局部最优问题我们的能量最小化框架包括三项 : 均值拉普拉斯能量项 E l, 渐进匹配项 E g, 和全局约束项 E c

36 (a) 均值拉普拉斯匹配方案第一项是均值拉普拉斯能量项 E l 拉普拉斯线性操作符对网格提供了一种有效的微分表征顶点 v i 的拉普拉斯微分坐标定义为 v i 和 1- 邻平均的差值 :

37 (a) 均值拉普拉斯匹配方案拉普拉斯坐标是顶点 v i 和邻接顶点的平均差向量如果设置每一个顶点的向量为 0, 则我们构建了一个平滑能量即, 平滑地分布每个顶点, 使之尽可能近地靠近它的 1- 邻居重心网格中所有顶点的拉普拉斯表征用矩阵形式可以描述为 :

38 (a) 均值拉普拉斯匹配方案然而, 拉普拉斯表征形式并不能捕捉到源网格的几何属性 :

39 (a) 均值拉普拉斯匹配方案考虑并入源网格的几何属性, 如考虑局部曲面形状的尺寸角度和方向这里, 我们考虑均值坐标, 其具有形状保持和低角度扭曲的优良性质 :

40 (a) 均值拉普拉斯匹配方案均值拉普拉斯表征形式成功地反映了源网格的局部形状信息, 如狮子腿部和腹部上的线状条纹被不失真地映射到猫模型上 :

41 (a) 均值拉普拉斯匹配方案第二项为渐进匹配项 E g 按照一致对应的定义, 我们希望兼容网格和目标网格有相同的几何, 即兼容网格应该和目标表面尽可能地逼近采用渐进逼近尺度来作为匹配尺度在只有少数标识点的情况下, 仍取得较好的结果

42 (a) 均值拉普拉斯匹配方案第三项为全局约束顶点 ; 需要在两个输入网格上标记出一些标识点这些标识点用来担当全局约束, 即先验知识这样我们利用这些标识点来初始化整个对应过程其中 C 是全局约束点的索引集合,c i 是标识点在目标网格的对应位置

43 (a) 均值拉普拉斯匹配方案最终的目标函数 E 为三个误差函数的加权和由粗到精的两步优化策略该优化系统实际上是将源网格延展到目标网格来生成兼容网格, 这样隐式地保证了兼容网格和源网格有等同的拓扑连接

44 (b) 关键点检测与特征匹配在经过均值拉普拉斯匹配之后, 兼容网格一般都可以很好地逼近目标网格但如果目标网格的几何特征比源网格复杂很多时, 兼容网格可能会缺失这些高频特征, 这样就会导致轮廓的塌缩

45 关键点检测以前方法的缺点主要是因为它们没有区分网格各个顶点的不同重要性, 而是视所有顶点同样的重要性在我们的设置中, 检测那些对特征捕捉和误差减少其重要作用的顶点, 并给予它们特别的关注此外, 为了减少局部扭曲, 这些点在数量上和尺度分布上都应在合适的范围内

46 关键点检测采用离散高斯曲率, 这一曲面的重要内蕴特征, 来作为关键特征度量为了计算关键顶点, 首先按照离散高斯曲率的大小对目标网格中所有顶点构建一个降序序列, 对逼近局部邻居的区域进行生长为了判别一个顶点是否在局部区域之内, 我们提供了一个独立于模型尺寸的半径距离度量

47 关键点自动检测这个度量在高曲率区域将产生更多的特征顶点, 而在平坦区域将产生较少的特征点特征点的数目总计为网格顶点数的 1/10~1/50 可以看出不仅成功捕捉到了显著特征, 同时和以前的方法相比, 这些点在数量上和尺度分布上保持在合适的范围内

48 关键点特征匹配检测到目标网格上的关键顶点之后, 需要将它们映射到源网格上以获得精确的匹配由于我们统一的框架, 这个过程也是简单而直接的其中 S 为关键点的索引集合与目标网格取得很好地匹配轮廓不再塌缩

49 (c) 顶点重分配和投影方案由于是全局优化, 初始的匹配结果不能保证兼容网格上的所有顶点都落在目标网格的表面上此外, 关键点约束有时也会引入一些形状扭曲提出一种新的顶点重分配和投影方案, 通过局部保形 ( 角度保持 ) 的方式来进一步优化初始匹配结果基于伞操作符 (umbrella operator), 我们的形状保持操作符被设计用于优化网格的内部顶点伞操作符用来优化一个网格的膜能量, 其根据顶点 v i 的 1- 邻邻居的凸组合来改变该顶点的位置

50 顶点重分配和投影方案初始结果的每一个顶点被投影到目标模型的表面上以确保获得完全的曲面匹配, 同时保持了源网格的表面特征

51 更多的实验结果

52 实验该框架在数值上是有效的, 使用一个稀疏 LU 求解器, 在 Pentium IV 3.0GHz 的计算机上,5.5K 顶点的模型只需要 0.6 秒进行 LU 分解,0.03 秒的时间进行回代关键点算法也非常快速以 bumpy sphere 模型 (11444 个面片 ) 为例, 检测过程只需 0.25 秒

53 实验该方法比以前的方法需要更少的标识点以 lion 模型和 cat 模型为例, 与 [12] 中 77 个标识点和 [124] 中的 68 个标识点相对照, 本方法仅需要 18 个标识点就可获得一个好的对应结果

54 本例小节在本实例中, 提出了一个新的框架在任意拓扑网格之间建立鲁棒的一致对应均值拉普拉斯匹配方法直接在 3D-3D 空间保持形状属性而无需分割网格通过检测关键顶点, 该方案精确地逼近目标模型的轮廓和重要特征顶点重分配和投射方法不仅按照局部保形的方式优化了全局匹配结果, 且确保了完全的曲面匹配

55 数字几何处理研究实例模型转导任意流形曲面的一致对应一种用于实时分割 3D 网格的笔划式交互框架凸包交叉参数化用于形状保持网格处理的均值流形操作符

56 3 笔划式网格分割及基于角度的特征感知尺度网格分割是一个有用的工具, 可用于 : 建模, 检索, 交叉参数化, morphing, 等笔划式 (Sketch-based) 分割的动机 : 在实际的应用中, 最终输出结果往往只有为数不多的部件 ( 一般 5~8, 通常小于 10) 而全自动分割方法受不同参数不同模型的影响, 结果往往不能满足用户需求所以用户会更乐意使用简单的交互方式来自己决定输出结果 [Katz et al. SIGGRAPH 03]

57 笔划式网格分割及基于角度的特征感知尺度使用笔划式交互方法, 用户只要随意地在屏幕上画几笔笔划, 我们的系统就可给出想要的分割结果, 而且可以实现跨尺度分割

58 笔划式网格分割及基于角度的特征感知尺度系统的三个部分 : (1) 基于顶点的区域扩散 (2) 基于面片的区域扩散 (3) 边界规整

59 第一步 : 基于顶点的区域扩散基于角度的特征感知尺度 ( 顶点情况 ) 我们定义状态量和过程量需要考察两个方面 : 过程量的大小, 以及状态量改变的大小 :

60 根据凹凸程度这些物理上的意义, 特征感知尺度按照过程量 a pro 和状态量 a sta 来定义 : V f ( s, t) = (1+ cos( a ))(1+ sin( a ) ) d pro sta ns est = (1 + )(1 + ns nt ) e st 同时反映了离散微分几何特征, 如曲率张量和高斯像的曲线长度而且该尺度是尺寸独立的, 即与模型的大小无关

61 使用这个尺寸独立的感知尺度, 用区域扩散算法来实现网格模型分割 :

62 第二步 : 用于面片扩散的特征感知尺度类似的, 定义用于面片扩散的特征感知尺度 : f ( st, ) = cos( a ) = n n F F F d sta s t

63 第三步边界规整基于凸包体积属性和角度连续属性进行边界规整人类感知通常沿着主曲率的负极值来分割物体这暗示着有意义的分割部件在某种意义上而言是凸形的因此我们采用凸包拟合策略, 以便在边界区域构造更加紧致的凸包单边增量凸包调整策略 : 该策略测试如果将一个边界上的面片从源部件移至目标部件时, 目标部件边界区域的凸包体积是否会增大如果否, 则将该面片移至目标部件 U a ring b a ring Vol( CH ( Fi fi )) Vol( CH ( Fi )) a ring Vol( CH ( F )) i < T d

64 第三步边界规整双边动态凸包调整策略 : 该策略测试如果将一个边界上的面片从源部件移至目标部件时, 两个部件的凸包体积之和是否会减少如果是, 则将该面片移至目标部件 a ring b ring VolCH ( ( F )) + VolCH ( ( F )) > i U a ring b b ring b Vol( CH ( F f )) + Vol( CH ( F f )) i i i i i

65 第三步边界规整最后, 按照对一个规则边界的视在感知来调整边界, 即最小化邻接边界角之差 :

66 分割结果用户界面分割框架是实时的, 并且易于使用

67 分割结果

68 分割结果分割方法的运行时间统计 :

69 本例小节在本实例中, 提出了一个基于笔划的网格分割框架, 提高了用户的操作体验特征感知尺度独立于模型的大小和尺寸同时这些尺度具有清晰的物理意义并反映了离散微分几何特征此外, 边界规整算法取得了视觉满意的分割边界

70 数字几何处理研究实例模型转导任意流形曲面的一致对应一种用于实时分割 3D 网格的笔划式交互框架凸包交叉参数化用于形状保持网格处理的均值流形操作符

71 4 凸包交叉参数化不同于目前的平面参数化球面参数化柱面参数化和三角 patch 参数化, 提出一种新的参数化框架 : 凸包交叉参数化 ( Convex Hull Cross-Parameterization) 利用了凸包的优良属性, 如良好的逼近能力和对内部点的线性凸表征能力动机 : 结合前面的 sketch-based 分割框架因为根据视觉感知特性, 分割后的部件在某种意义上可以看成 ( 更接近于 ) 凸的

72 凸包交叉参数化 (a) 为了在两个输入网格之间建立交叉参数化, 我们希望参数化域既不能太松也不能太紧太规则的域, 比如球 (b), 平面, 圆柱, 和大的三角区块, 因为太通用而不能很好地逼近复杂的网格, 即域太松 (c) 而把目标网格本身作为参数化域, 则太紧当两个网格具有显著不同的几何时, 可能会陷入局部最优 (d) 我们的方法首先对网格进行分割, 然后采用凸包作为合适的参数化域

73 流程图凸包交叉参数化

74 凸包交叉参数化利用分割时产生的兼容边界来保持连续性连续性保持有利于减少部件边界上的扭曲误差因为相邻部件边界上的顶点按照平均弧长比例映射到相同的目标边界位置上, 这样边界位置的映射连续性就被自然地得到保持无需对边界进行拉直以构建三角或四角区块, 可以直接将任意的自然边界作为连续性约束以获得平滑的边界过渡

76 本例小节在本实例中, 提出了一种新的分而治之的交叉参数化方法, 其首先对两个输入网格构造兼容分割, 然后使用凸包作为中间参数化域来逐部件地进行映射计算基于部件的分割方法不仅对输入网格生成了有意义的分割, 也加速了整个方案凸包交叉参数化方法将复杂形状的映射转化成两个简单凸形状集合的映射, 化繁为简

77 数字几何处理研究实例模型转导任意流形曲面的一致对应一种用于实时分割 3D 网格的笔划式交互框架凸包交叉参数化用于形状保持网格处理的均值流形操作符

78 5 均值流形操作符均值流形操作符是定义在流形曲面上的形状保持操作符该操作符可以编 / 解码网格曲面的细节几何信息和参数化的拓扑信息该操作符旨在构造一个弱的向量场而保持线性属性使得我们的网格编辑系统即使在大角度形变的情况下仍可以获得满意的形变结果动机 : 拉普拉斯微分坐标虽然是线性的, 但却具有矢量属性, 即不是旋转不变的而存在的旋转不变表征形式虽然具有标量属性, 但却导致复杂费时的非线性优化而均值流形操作符构造一个弱的向量场 ( 准标量场 ) 而保持准线性属性, 这样在以上两种表征形式之间取得了一个很好的平衡可看作是原始微分表征的局部线性嵌入 (LLE), 旋转不变

79 Mean-Value Manifold Operator Non-zero vector Laplacian coordinates: zero vector, but only in 2D star-shaped case Mean-value coordinates: weak vector (close to zero vector) and nice parameterization property Mean-value manifold operator:

80 均值流形操作符

81 均值流形操作符通常非常少的迭代 ( 在实验中 t<5, 而在 [128] 中 t 20) 即可收敛并取得视觉满意的形变结果根据分析, 非线性的程度与顶点 1- 邻局部微分坐标的幅值有关如果具有较小的幅值且被合理地优化 ( 如皆为正值 ), 那么迭代过程就会更快且更稳定

82 使用均值流形操作符进行形状保持的网格平滑还可以将均值流形操作符应用到网格平滑操作上, 用于去除表面上的噪声信号得益于统一的线性框架, 网格平滑操作也非常简单具体地, 网格平滑方法可用如下的二次能量函数表征平滑方法具有参数化保持性质 ( parameterization - preserving) 此外, 由于是基于约束的全局平滑, 该方法有效避免了在结果曲面上的局部塌缩

83 使用均值流形操作符进行形状保持的网格平滑

84 本例小节在本实例中, 基于均值流形操作符, 提出了一个统一的形状保持网格处理框架, 用于网格编辑, 网格平滑, 还有前面章节提到的模型转导和一致对应等等均值流形操作符是一个形状保持操作符, 其可以鲁棒地对局部参数化和几何信息进行编解码, 并在网格表面上构建一个弱向量场能够对细节和参数化信息进行保持并产生良好形状的结果曲面具有快的收敛速度和线性内存消耗, 且易于实现

85 总结与展望数字几何处理是一门年轻并且非常活跃的新学科, 所包含的研究内容也非常广泛, 从三维模型的获取配准与重建几何拓扑修复网格平滑与去噪重网格化, 到三维网格压缩网格分割参数化一致对应网格形变编辑与动画 3D 数据重定向技术等数字几何处理与数字图像处理本质上都是一种处理离散数字信号的技术, 因此将信号处理的方法引入到数字几何处理中将是重要的方向手段而成功的关键是如何考虑和解决三维网格模型任意弯曲非均匀采样并缺乏规则参数化域的内在特点和难点计算机视觉机器学习和计算机图形学这三门学科的联系日臻紧密如何将学习的方法引入到网格模型的分割动画数据修复等方面是令人感兴趣的方向

87 3D Visual Computing and Robotics Group Feature Line Detection on 3D Mesh Tao Luo

88 Outline Introduction of mesh processing Multi-scale feature line detection Application in digital archaeology Conclusions

89 Data types Polygonal mesh Point cloud

90 Mesh processing Mesh compression Mesh simplification Mesh segmentation Mesh smoothing Mesh editing Feature extraction Geometry Connectivity [P. Alliez et al. 2004]

91 Mesh processing Mesh compression Mesh simplification Mesh segmentation Mesh smoothing Mesh editing Feature extraction [J. Talton 2004] 12,000 2,

92 Mesh processing Mesh compression Mesh simplification Mesh segmentation Mesh smoothing Mesh editing Feature extraction [S. Katz et al. 2003]

93 Mesh processing Mesh compression Mesh simplification Mesh segmentation Mesh smoothing Mesh editing Feature extraction [Tasdizen et al. 2002]

94 Mesh processing Mesh compression Mesh simplification Mesh segmentation Mesh smoothing Mesh editing Feature extraction [K. Zhou et al. 2005] [A. Sharf et al. 2006] [M. Alexa 2002]

95 Mesh processing Mesh compression Mesh simplification Mesh segmentation Mesh smoothing Mesh editing Feature extraction Line feature

96 Feature lines View-dependent lines Silhouettes, Suggestive Contours, Apparent Ridges, etc. View-independent lines Boundaries, Creases, Demarcating Curves, etc.

97 Goal : Detect the creases on meshes, along which the surface bends sharply. Applications Mesh segmentation Mesh simplification Non-photorealistic rendering (line drawings) Shape recognition etc.

98 Definition of creases The loci of points where the larger principal curvature in absolute value takes a positive maximum (negative minimum) along its corresponding curvature line Ridges kmax > kmin, emax = 0, emax tmax < 0 Valleys kmin < kmax, emin = 0, emin tmin > 0

99 Previous methods Detect creases using the differential information on a surface Put emphasis on reliable estimation of curvature and curvature derivatives Noiseless meshes References Y. Ohtake, A. Belyaev, and H.-P. Seidel, Ridgevalley lines on meshes via implicit surface fitting, SIGGRAPH 2004 S. Yoshizawa, A. Belyaev, and H.-P. Seidel, Fast and robust detection of crest lines on meshes, SPM S. Rusinkiewicz, Estimating Curvatures and Their Derivatives on Triangle Meshes, 3DPVT 2004.

100 Y. Ohtake, A. Belyaev, and H.-P. Seidel, Ridge-valley lines on meshes via implicit surface fitting, SIGGRAPH 2004

101 S. Yoshizawa, A. Belyaev, and H.-P. Seidel, Fast and robust detection of crest lines on meshes, SPM 2005.

102 Redundant lines are detected due to noise and it is difficult to distinguish them from real creases. Combine information at multiple scales to eliminate redundant lines instead of smoothing directly. [S. Rusinkiewicz, 2004]

103 Multi-scale crease detection on noisy meshes General idea Generate the discrete 3D multi-scale representation. Probabilistic estimation of local scale Estimation of curvature and curvature derivatives across all the scales Trace creases by connecting the curvature extrema points detected on the mesh edges with curvature information at selected local scales. Optional post-processing steps

104 Two issues Discrete 3D multi-scale representation Scale selection in discrete 3D scale space

105 Discrete multi-scale representation Mark Pauly, Leif P. Kobbelt, Markus Gross, Point-Based Multiscale Surface Representation, ACM Transactions on Graphics 06 Approximations at successively higher levels of smoothness. Using local weighted least squares fitting, a smooth approximation of a point cloud can be obtained.

106 Motivated by the good performance of anisotropic diffusion in 2D image processing Pietro Perona and Jitendra Malik, Scale- Space and Edge Detection Using Anisotropic Diffusion, PAMI 1990

107 Anisotropic diffusion Extension to 3D mesh F is an estimation of normal variations on meshes v = div( g( F ) v) t ( ) ( ) g x = x c g is a monotonically decreasing function whose value between 0 and 1 Smooth less around the features and get preservation of features

108 Normal variation the face normal variations between the adjacent faces sharing an edge fjk, v i ( fj ) ( f ) 1 F i = arccos n, n di k

109 Vertex gradient operator v j vi v = : v v d j di i j i Vertex is updated as follows, 1 v j v i v v + g F + g F vj v d i i d j d i ( ( ) ( )) i i i j

110 Discrete 3D multi-scale representation A series of meshes at different levels of smoothness Features are preserved in the discrete scale space. The correspondence of vertices between different scales is kept and the connectivity is not changed.

Probabilistic estimation of local scale Minimum Description Length Basic idea: for a given set of hypotheses H and data set D, we should try to find the hypothesis or

111 Probabilistic estimation of local scale Minimum Description Length Basic idea: for a given set of hypotheses H and data set D, we should try to find the hypothesis or combination of hypotheses in H that compresses D most. Description length L M t = L M + L ε ( ) ( ) ( ) Smoothed meshes residual 0 t t ε = M t 0 M t { M, t = 1,... m} t = + noise

112 Description lengths ( t ) 1 2 ( ) ε L M L ε t t t ε = v v 2 t 0 Local description length at each vertex given the local scale 2 ( ( ) ( )) = λ + ε ( ) ( ) L M v t v t v 0 tv Likelihood at each vertex given a local scale 1 pˆ k ( v) = P( M 0 ( v) t( v) = tk ) = e Z t 2 v 2 ( λ tk ε ( v) ) + t k

113 Scale selection with a prior MRF model Some prior knowledge about the distribution of local scales Piecewise constant Discontinuous at sharp features Related to variation between normals of adjacent vertices

114 Posterior distribution Pt ( t) P( M0 t) P( t M0 ) = P( M ) Estimate the posterior marginal probabilities by minimizing the function The optimal local scale 0 ( ) = ( ) ˆ ( ) + α ( ) ( ) v ( ) = max * t v t k ( ) kmax = arg max p v k k 2 2 U p pv pv pv pu vu, vu,

115 Results Distribution of local scales at vertices Maximum likelihood Maximum posterior probability

116 Smoothed mesh with local scales Smoothed mesh Noisy mesh

117 Multi-scale ridges and valleys Estimate curvatures and curvature derivatives across all scales. Curvature information is available only at selected local scales. Connect the zero-crossing points of first-order curvature derivatives on original mesh edges.

118 Estimate the curvature and its derivatives S. Rusinkiewicz, Estimating Curvatures and Their Derivatives on Triangle Meshes, 3DPVT Inspired by the algorithm of estimating per-vertex normal, namely taking a weighted average of the normals of faces touching a vertex. First compute the properties per-face, then estimate the value at each vertex as a weighted average over the immediately adjacent faces.

119 Detection of ridge vertices For every mesh edge, check whether it contains a ridge vertex. If the angle between principal directions of adjacent vertices is obtuse, emax ( v2 ) = emax ( v2 ), tmax ( v2 ) = tmax ( v2 ) Condition 1 max ( ) ( ) > min emax ( v1 ) emax ( v 2 ) < 0 k v k v

120 Condition 2 emax ( v ) i ( v 3 i v ) i tmax ( vi) > 0 Approximate a zero-crossing using linear interpolation p = ( ) + ( ) ( ) + ( ) e v v e v v max 2 1 max 1 2 e v e v max 1 max 2 k max ( p) = ( ) ( ) + ( ) ( ) e ( v ) + e ( v ) e v k v e v k v max 2 max 1 max 1 max 2 max 1 max 2

121 Connecting ridge vertices For a mesh triangle, if two ridge vertices are detected on edges If all three edges contain ridge vertices,

122 Creases detected directly Creases at a single scale Creases using our method

John Novatnack, Ko Nishino, Ali Shokoufandeh, Extracting 3D Shape Features in Discrete Scale-Space, 3DPVT 06 Parameterize the surface of the mesh model on a 2D plane and

123 John Novatnack, Ko Nishino, Ali Shokoufandeh, Extracting 3D Shape Features in Discrete Scale-Space, 3DPVT 06 Parameterize the surface of the mesh model on a 2D plane and construct a dense normal map Computer a dense distortion map Construct a discrete scale-space by successively convolving the normal map with distortion-adapted Gaussian kernels.

124 Comparison [Novatnack et al., 2006,2007] Parameterization is time consuming. The scale space is constructed in a regular 2D representation. The feature is blurred by Gaussian convolving.

125 A stele model Max Planck model

126 Digital archaeology

127 Digital archaeology

128 3D aided line drawing

129 Efficiency------Time cost Photo 20m 8.5m Parallel projection map Traditiona l method Our method Saved time 480 hours 8 hours (for modeling) 24 hours (for line drawing) 448 hours Outside elevation Line drawing

130 The Variocana

131 The Variocana model Traditional method Our method Saved time 360 hours 4 hours (for modeling) + 2 minutes (for line drawing) about 356 hours

132

133 Conclusions Propose a multi-scale strategy to reduce redundant detection due to noise Generate a discrete multi-scale representation of a triangular mesh based on an anisotropic diffusion method Present a probabilistic method for local scale selection based on minimum description length principle with a prior MRF model Provide assistance for archeologists to draw line drawing

134 Thanks

Move Component Object selection Component selection UV Maya Hotkeys editor Maya USING MAYA POLYGONAL MODELING 55

Move Component Object selection Component selection UV Maya Hotkeys editor Maya USING MAYA POLYGONAL MODELING 55 3 55 62 63 Move Component 63 70 72 73 73 Object selection Component selection UV Maya Hotkeys editor Maya 55 USING MAYA POLYGONAL MODELING Maya: Essentials Maya Essentials F8 Ctrl F9 Vertex/Face F9 F10