单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,,,,报告人：李桂清,,合作教授：鲍虎军,,浙江大学,CAD＆CG,国家重点实验室,2019－09－25,,细分模式构造及拟合,博士后出站报告,报告人：李桂清细分模式构造及拟合博士后出站报告,一 细分曲面定义,二 细分曲面构造,三 一个细分曲面拟合系统,四 结论,,2,一 细分曲面定义2,第一部分 基本概念,3,第一部分 基本概念3,什么是细分曲面,(,Subsivision surfaces,),？,,初始控制网格,,重复加细,(,Refinement),,,网格序列,,,极限曲面,,不断细分生成网格序列,4,什么是细分曲面(Subsivision surfaces)？,,细分曲面特点,,特点：,,复杂拓扑、,多分辨率、简单、局部、稳定,,应用,,,计算机图形学,计算机动画,,,Maya, Wavefront,等商业3,D,造型系统支持,,,数字几何处理(,DGP),的基本工具,5,细分曲面特点 特点：5,任意拓扑模型,6,任意拓扑模型6,复杂模型,7,复杂模型7,多分辨率表示,(,Multiresolution,),,渐进传输,,多分辨率显示,,多分辨率编辑,8,多分辨率表示(Multiresolution) 渐进传输,存在的问题,高阶细分曲面构造,细分曲面质量,细分曲面整合,动态细分,大规模数据拟合。
9,存在的问题高阶细分曲面构造9,第二部分 细分模式构造,10,第二部分 细分模式构造10,,,拓扑规则：新网格顶点的连接关系,,,插入顶点,,连接顶点,,删除部分点、线、面(可选,),,几何规则：新网格顶点的位置计算,,,计算新网格顶点的规则,,线性、有限支承、仿射不变性等,,细分模式构造要素,11,细分模式构造要素11,数学上的完备性,为构造通用细分模式提供,素材,改善曲面质量,,满足特殊应用的要求,意义,12,数学上的完备性意义12,Kobbelt,四边形网格插值模式，2019,拓扑规则：1－4分裂算子,几何规则：,四点插值模式的,张量积,存在问题,,,奇异顶点（入度）处细分规则的构造不直观,,,虚拟点使问题变复杂,,,曲率发散,,2,一个改进的四边形网格插值细分,13,Kobbelt四边形网格插值模式，20192 一个改进的四,拓扑规则：1－4分裂算子,,,,2.1,拓扑规则,,1-4分裂,,,,,,,,,,,,,,,,,14,拓扑规则：1－4分裂算子 2.1 拓扑规则1-4分裂14,,,,2.2 KOBBELT,的几何规则,,,,,,,(,a),规则,E-,顶点模板; (,b),非规则,E-,顶点模板; (,c) F-,顶点模板.,,,,,,,,,,,,,,,,,,,,,-1,9,9,-1,15,2.2 KOBBELT 的几何规则(a) 规则E-顶点模,,,,KOBBELT,构造思想,,1 沿两个方向用四点插值模式得到的面顶点应相同,2 奇异点附近的边点越来越对称,16,KOBBELT 构造思想1 沿两个方向用四点插值模式得到的,规则,大模板,分解(,F-,顶点),,小模板推广,,合成非规则大模板,2.3,几何规则构造新方法,,,,,,,,,,,,,,,,,,,分解,推广,合成,平均,Fourier,分析,17,规则大模板分解(F-顶点) 2.3 几何规则构造新方法分解,规则,大模板,,,,,,小模板,,,,1,-9,-9,1,1,-9,-9,1,-9,81,81,-9,-9,81,81,-9,,,1,-6,-3,-6,36,18,18,-3,9,,,建立细分矩阵,18,规则大模板 1-9-911-9-91-98181-9-981,建立,细分矩阵,：,,DFT,:,,Fourier,系数推广：,逆,DFT,2.4,非规则小,模板,,19,建立细分矩阵： 2.4 非规则小模板19,Z,orin,方法, 2000,,,细分矩阵 的构造：,,,特征根：,,,特征映射,,,正则性,,单射性,,2.5,连续性讨论,,3-邻域的,一个扇区,20,Zorin方法, 2000 2.5 连续性讨,,有界曲率,,有界曲率条件： 或,,,,,∆： 本文的方法,,,,x： Kobbelt,的插值细分,,21,有界曲率 有界曲率条件：,边界,与折痕,,,,,任意多边形网格,,把多边形看成,特殊的四边形,,2.6,任意多边形网格,,-1,9,9,-1,,3,6,-1,,,,E-,顶点,E-,顶点,F-,顶点,F-,顶点,22,边界与折痕 2.6 任意多边形网格-199-136-1E-,可分面种类,,,例,,2.7,自适应细分,,,,,,,,,,,,,,,,,,,,,,,,,,,最大细分深度8,5625顶点,,6088,面,24面,,23,可分面种类 2.7 自适应细分最大细分深度85625顶点,2.8,例子,,,,,,,三角网格，3次,四边形网格，4次,任意多边形网格，3次,24,2.8 例子三角网格，3次四边形网格，4次任意多边形网格,尖锐特征,均细分,6,次,25,尖锐特征均细分6次25,,,,与,Kobbelt,方法比较,,,,,,,Kobbelt,方法，,本文方法，均6次,26,与Kobbelt方法比较Kobbelt方法，本文方法，均6,一个改进,Kobbelt,插值细分,,,方法,＊,大模板分解的思想,＊,矩阵块的,Fourier,分析,,,改进,＊新模板有坚实数学基础，而非拼凑,＊,极限曲面曲率有界，而非发散,2.9,小结,27,一个改进Kobbelt插值细分 2.9 小结27,4－8,模式：,Velho & Zorin 2019,,4-8,分裂,,3-4,网格,,内边，外边,,,几何规则,,,3,细分,,,4-8分裂,,,a,a,a,a,b,c,c,c,c,c,c,a =1/4, b = ½, c = 1/(2n),,28,4－8模式：Velho & Zorin 20193,分裂算子:,,,每个面插入新点,,,每条边生成一个新四边形,,,3.1,拓扑规则,,,1次,,2次,29,分裂算子: 3.1 拓扑规则1次2次2,,,3.2,几何规则,,,1,1,1,1,,c,c,c,c,c,c,b,30,3.2 几何规则1111ccccccb30,边界：５次Ｂ样条，分奇偶步,,奇数步：插入边点，用三次Ｂ样条细分,,偶,数步：不插边点，用两次平均,,,3.3,开网格,31,边界：５次Ｂ样条，分奇偶步 3.3 开网格31,任意多边形规则,,,只在第一次细分时用,,与前一章类似,3.3,任意多边形网格,32,任意多边形规则 3.3 任意多边形网格32,,,3.4,自适应细分,33, 3.4 自适应细分33,细分规则,,,,运行效率,,,3.5,与4－8 模式的比较,4-8,34,细分规则 3.5 与4－8 模式的比较4-834,3.6,与其它模式的比较,Doo-Sabin,Loop,Sqrt(2),控制网格,35,3.6 与其它模式的比较Doo-SabinLoopS,,特征值,,,,,,特征映射,,n=3..8,,3.7,连续性讨论,36,特征值 3.7 连续性讨论36,提出四边形网格,sqrt(2),插值模式,与４－８模式相比,,,提出一种改进的权值,,运行效率更高,,,适用于任意多边形网格,包括三角网格,,,无须预处理,3.8,小结,37,提出四边形网格sqrt(2)插值模式 3.8 小结37,Kobbelt,插值细分,2019,,,1-4分裂，四边形网格,Butterfly,插值细分,1990,2019,,,１-4分裂，三角网格,插值,sqrt(3),细分,2000,,sqrt(3),分裂，三角网格,插值,sqrt(2),细分（本文）,,sqrt(2),分裂，四边形网格,,4,插值 细分,38,Kobbelt 插值细分,20194 插值 细分,,分裂算子,（第３章已讨论）,,,,4.1,拓扑规则,,1次,39,分裂算子（第３章已讨论） 4.1 拓扑规则1次3,规则情形,（十字模板）,,非规则情形,,,分解,,4.2,几何规则,,,,b,b,b,b,b,b,b,b,a,a,a,a,,a = 10/32,b = -1/32,,,0,0,0,0,e,e,d,d,c,c = 1/２,d = 3/8,e = -1/8,40,规则情形（十字模板） 4.2 几何规则bbbbbbb,非规则,情形,,,,,,几何规则,,,,0,0,0,0,e,e,d,d,c,,,合成,平均,推广（,DFT）,,41,非规则 几何规则0000eeddc合成平均推广（DFT,,,4.3,推广到任意多边形网格,任意多边形规则,,,只在第一次细分时用,,与第二章做法类似,42,4.3 推广到任意多边形网格 任意多边形规则42,建立细分矩阵,,,特征值,,,特征映射,,4.4,连续性,17,18,19,20,0,1,3,7,13,21,2,4,8,14,22,5,6,9,15,23,10,11,12,16,24,25,26,27,四次,43,建立细分矩阵 4.4 连续性17181920013,,,4.5,例子,7次,10次,12次,6次,6次,44,4.5 例子7次10次12次6次6次44,一个新的插值细分:层次更丰富,支持任意多边形输入,,数值分析表明应是,C1,连续,,4.4,小结,45,一个新的插值细分:层次更丰富 4.4 小结45,第三部分 用细分曲面拟 合三角网格,46,第三部分 用细分曲面拟 合三角网格46,拓扑规则：1－4分裂,,,,,Loop,模式，1987,(,Hoppe,改进,1994),每条边插入一个新顶点(右图蓝色顶点)，,同一个三角形的新顶点两两相连,,,,,,,,,,,分裂,47,拓扑规则：1－4分裂Loop 模式，1987 (Hoppe改,V-,顶点模板：线性组合,,,,,E-,顶点模板,,,,几何规则,(1),1/8,1/8,3/4,,边界,V-,顶点,,,,内部,V-,顶点，其中,n,为邻点个数。
1/8,1/8,3/8,3/8,,,,,边界,E-,顶点,1/2,1/2,,内部,E-,顶点,48,V-顶点模板：线性组合几何规则(1)1/81/83/4,与边界规则相同,尖锐特征,,,,尖锐旧顶点,尖锐新顶点,49,与边界规则相同尖锐特征尖锐旧顶点尖锐新顶点49,Loop,模式----矩阵表示,,,第,j,层细分,第,j+1,层细分,50,Loop 模式----矩阵表示第j层细分第j+1层细分50,边界和尖锐特征顶点极限位置,Mask,,Loop,模式----极限位置,,,内部顶点极限位置,Mask,51,边界和尖锐特征顶点极限位置Mask Loop 模式----极,极限位置的矩阵表示,(1),,,,,,极限曲面,第,j,层细分,52,极限位置的矩阵表示(1)极限曲面第j层细分52,极限位置的矩阵表示,(2),,,,,,53,极限位置的矩阵表示(2)53,5. 2,重构系统的整个流程,简化,优化,,重采样,拟合,预处理,细分,输入：三角网格,M,输出：细分曲面,S,,,54,5. 2 重构系统的整个流程简化优化 重采样拟合预处理细分,5. 3,预处理,两个面的夹角,<,阈值(如136度),,输入网格,预处理后,55,5. 3 预处理两个面的夹角<阈值(如136度)输入网格预处,5.4,,三角网格简化（,Simplification）,目的：,少量三角形表示形状,方法,,计算顶点代价（,QEM）,:,顶点到面的距离,,,,代价计算的模板,56,5.4 三角网格简化（Simplification）,,,按该权值排序（降序）,,逐个删除顶点直到满足循环中止条件,＞误差精度,＞顶点个数（百分比）,,删除顶点后，局部剖分,删除,v,57, 按该权值排序（降序）删除顶点后，局部剖分删除v57,简化结果—基网格,,原始网格,简化结果-基网格,58,简化结果—基网格原始网格简化结果-基网格58,几何优化,,,Laplace,算子,,,,,切向分量,,5.5,基网格优化,Laplace,算子模板,59,几何优化5.5 基网格优化Laplace算子模板59,拓扑优化,,,,删除入度为3的顶点,,,,,边调换（,Swap),,60,拓扑优化60,优化结果,优化前的基网格,优化后的基网格,61,优化结果优化前的基网格优化后的基网格61,5.6,,网格点重采样,(,Resampling,),基网格细分（,一次,）,估计最近点,,,,,,,,,,,细分,求交,,,62,5.6 网格点重采样(Resampling )基网格细,,,重采样结果,,,,,63,重采样结果63,5.7,,建立拟合方程,,,,拟合方程,极限矩阵,细分矩阵,控制顶点向量,采样点向量,64,5.7 建立拟合方程拟合方程极限矩阵细分矩阵控制顶点向,,求解,最小二乘法建立线性方程组,,,共轭梯度法－－迭代求解,,,,,优化后的网格作为初始解,稀疏矩阵,存储,,,65,求解最小二乘法建立线性方程组65,实例,原始网格,简化网格,控制网格,极限曲面,Mechpart,,66,实例原始网格简化网格控制网格极限曲面Mechpart 66,Fandisk,极限曲面,原始网格,67,Fandisk极限曲面原始网格67,Manequin,,极限曲面,原始网格,68,Manequin 极限曲面原始网格68,效 果 比 较,,左：本文,中：原始网格,右：原来结果,69,效 果 比 较 左：本文69,5.9 结论,,,讨论了细分曲面拟合系统,,,简化过程中记录相关三角形表,,,引入几何优化,,,求交方法作重采样,,,70,5.9 结论 讨论了细分曲面拟合系统70,第四部分 结论,71,第四部分 结论71,* 一个改进的插值细分,* 四边形网格的 细分,* 插值 细分,* 一个细分曲面拟合系统,6 本文内容,,72,* 一个改进的插值细分6 本文内容 72,完善连续性分析,拟合方法加速,,超大规模网格拟合,能量最小约束,,,将来工作,73,完善连续性分析 将来工作73,结束,谢谢!,74,结束谢谢!74,。