离散数字几何处理

离散数字几何处理第1页/共74页内容提要一、离散数字几何处理简介二、三角网格的参数化意义和目的前人工作和我们的最新研究成果参数化的例子及其应用三、三角网格的光顺意义和目的前人工作和我们的最新研究成果参数化的例子四、结论和未来的工作第2页/共74页一、数字几何处理简介几何表示参数曲面隐式曲面体数据多边形网格点数据网格变成主流的几何表达方式.第3页/共74页一、数字几何处理简介PositionNormalColorTextureBRDF…几何信息:N维第4页/共74页三维数字几何处理过程获取处理存储和传输应用(仿真,娱乐…)参数化光顺/去噪简化/压缩多分辨率编辑……第5页/共74页三角网格参数化猫头(135个顶点,257个三角形)平面参数化球面参数化第6页/共74页网格光顺和去噪3D网格模型的光顺可视化（刘新国2002）第7页/共74页

兔子基网格(162三角形)原始网格和LOD表示三角网格的简化第8页/共74页多分辨率编辑三角网格的编辑（周昆2002）第9页/共74页纹理映射球面凸组合参数化算法的纹理映射效果（胡国飞2003）第10页/共74页重网格化parameterizationresamplingABF参数化方法的Remeshing效果(Sheffer2000)第11页/共74页重网格化parameterizationresamplingremeshingMIPS参数化方法的Remeshing效果（Hormann1999）第12页/共74页曲面拟合parameterizationB-SplineSurface平面凸组合参数化方法曲面拟合效果(Floater1998)第13页/共74页几何形状过渡累进球面参数化方法的Morphing效果（Praun2003）第14页/共74页问题的描述研究内容前人工作我们的最新研究成果参数化的例子及其应用

二、三角网格参数化第15页/共74页问题的描述给定一个由空间点集组成的三角化网格和一个参数域，寻求一个参数域上的点到三角网格点的一一对应映射，并且在参数化域上保持原始网格的拓扑信息。第16页/共74页意义曲面拟合:通过参数化，把离散的3D数据点用一个光顺的参数曲面来拟合。纹理映射:利用表面网格参数化信息，把一幅纹理图像映射到三维网格上，使得表面网格看上去更加生动逼真。重网格化:利用参数化把三角化曲面转化成具有细分连通性的规则网格，并且在此基础上进一步作多分辨率分析。几何形状过渡:通过参数化到相同的参数域进行点对应，使得两个不同物体之间的平滑过渡。第17页/共74页研究内容

1保证参数化的有效性

三维网格二维参数化结果第18页/共74页研究内容2寻求某种几何度量的变形最小化不同的参数化方法下的纹理映射,具有不同的变形第19页/共74页研究内容保面积?保角?等距?2寻求某种几何度量的变形最小化第20页/共74页研究内容3具有线性时间空间复杂度的算法全局参数化方法：求解整体约束非线性系统局部参数化方法：求解局部线性系统第21页/共74页前人工作基于松弛参数化方法：

GraphEmbedding(Tutte60)平面凸组合(Floater97)球面松弛参数化(Alexa00)

球面凸组合(胡国飞和彭群生03)基于调和映射的方法调和映射(Pinkall93,Eck95)累进球面参数化(周昆02,Praun03)分割展平法整体Angle-Based-Flattening(Sheffer00)局部Bounded-Distortion-Piecewise(Sorkine02)第22页/共74页累进球面参数化(周昆2002)基本思路1生成带有局部参数化信息的累进网格表示。循环地执行边收缩操作，直到当前简化网格变成一个凸多面体（基网格）。对每次边收缩操作，收缩边的两个顶点按简化后生成的简化网格表面作局部参数化。2由于基网格是凸多面体，从基网格的中心投影可以得到相应的球面网格。对每次顶点分裂操作，使用局部参数化信息把两个分裂出来的顶点映射在单位球面上。3所有的顶点分裂操作执行完毕，球面参数化生成。第23页/共74页累进球面参数化流程edgecollapsesMiSpn,…,SpiM=MnM0vertexsplitsMnvertexsplitsMjvertexsplitsMiedgecollapsesMjSpi+1,…,SpjedgecollapsesM0Spj-1,…,Sp1第24页/共74页累进球面参数化实例第25页/共74页凸组合球面参数化(胡国飞2003)基本思路1球面投影：初始化2凸组合：松弛迭代求解球面新点3虚拟边界技术：改善边界变形特色1参数化解存在且唯一，数值解收敛于真实解2权值λ可控，局部保形第26页/共74页凸组合参数化实例3D网格模型的球面参数化第27页/共74页三、网格光顺和去噪问题的描述研究内容前人工作我们的最新研究成果参数化的例子及其应用第28页/共74页问题的描述在数据获取过程中，人为的扰动或者扫描仪本身的缺陷使得生成三维数据带有噪声(noise)。去噪是消除三维数据表面的局部几何突变，并在局部范围内保持形状变化的连贯性。光顺是在剔除噪声获取离散曲面更高阶光滑性的同时，保持网格模型的拓扑信息和几何特征不变性。第29页/共74页问题的描述重心约束的光顺算法（刘新国2001）第30页/共74页目标1体积保持(volume-preserving)Laplace光顺算子使得体积收缩第31页/共74页目标2特征保持(feature-preserving)牙齿，脊背等特征在光顺后得到保持(胡国飞2003)第32页/共74页目标3线性时间和空间复杂度－求解非线性系统－求解线性系统(多次)－求解线性系统(单步)第33页/共74页前人的工作1能量最小化方法(求解非线性系统)－薄膜能量(Morton92)：－薄板能量(Welch92)：－重心约束的磨光算法(刘新国02)优点:基于能量方程去除表面噪声，通过引入约束条件，可有效控制体积收缩和模型变形。缺点:非线性系统，运算时间长第34页/共74页前人的工作2基于Laplace的光顺算子(求解线性系统)

优点:线性系统，算法简单，运算速度快

缺点:需要多次迭代才能达到光顺效果，容易导致过光顺，体积收缩的情况

改进算法：

λ|μ方法(Taubin95)

HC算法(Vollmer99)第35页/共74页HC算法第36页/共74页前人的工作3鲁棒的顶点预测方法网格的双边滤波器(Freishman03,Jones03)－图像的双边滤波器是把象素到邻域点的距离以及该象素的亮度值与邻域点的亮度值之差作为两个参数。－Freishman网格双边滤波把点与周围邻域点的距离以及该距离向量与该点的法向的内积作为双边滤波器两个参数。－Jones把点与周围邻域三角形重心的距离以及与该点到周围邻域三角形的距离作为双边滤波器的两个参数。

优点:无需迭代,算法简单,运算速度快.

缺点:邻域难确定，邻域过小，容易导致过光顺和特征加强等。邻域过大导致运算时间增大。第37页/共74页重心约束的磨光算法(刘新国02)网格曲面能量离散曲面的磨光——能量最小化

第38页/共74页第39页/共74页重心约束第40页/共74页能量最小化第41页/共74页局部迭代求解第42页/共74页结果第43页/共74页结果第44页/共74页三步顶点预测滤波器(胡国飞03)算法特色：1三步预测：利用两次双边滤波器（SOT和FOV）和一次准Laplacian滤波来三步预测顶点。2限于局部邻域：根据顶点的二阶邻域三角形，一阶邻域顶点以及顶点本身预测新点。3区分特征和噪声：有效排除了二阶邻域以外噪声对它的干扰，通过顶点局部邻域的几何信息来预测顶点的方法既能有效地剔除噪声又能保持网格的凹凸特征。第45页/共74页邻域SOT:二阶邻域三角形FOV:一阶邻域顶点第46页/共74页特征和噪声噪声:

孤立的顶点扰动是噪声，因为它只牵涉到一阶邻域三角形的局部几何变形，我们予以剔除。特征:

顶点及其一阶邻域顶点沿同一方向上波动，且与其二阶邻域三角形的形状变化趋势一致，我们认为它是一种三角网格的局部特征，给予保持甚至增强。第47页/共74页SOT光顺将顶点投影到其二阶邻域三角形所在平面上，再把所得投影点的加权平均作为该顶点的估计，对于变化平滑的特征，将产生过估计，对于突变的噪声，会导致欠估计。最后使得凹凸特征被放大，而噪声被削弱。第48页/共74页SOT光顺利用点和二阶邻域三角形的几何关系，进行双边滤波第49页/共74页准Laplacian光顺噪声点对于原始网格数据来讲毕竟只占小部分，为了减小第一步处理对大部分正常顶点位置的估计误差，我们取原顶点和第一次预测位置的加权平均作第二次估计，称之为准Laplacian光顺：第50页/共74页基于FOV预测顶点沿顶点的法线方向，以平均曲率为权值，移动各顶点，使得模型表面趋于最小曲面。FOV预测将使得噪声点快速调整到符合局部邻域变化趋势的曲面上。第51页/共74页基于FOV预测顶点第52页/共74页优点:

－通过鲁棒的顶点预测进行光顺，无需迭代；

－避免过光顺和特征加强等；

－算法简单，运算速度快.第53页/共74页

(a)原始网格(b)噪声网格(c)一次光顺(d)二次光顺三步顶点预测滤波器光顺效果结果第54页/共74页结果三步顶点预测算法：恐龙的光顺结果第55页/共74页结果

三步顶点预测算法：小噪声和大噪声的剔除效果Laplace20Taubin20FreishmanJonesOurMethod第56页/共74页结果三步预测非迭代算法噪声网格80次Laplace40次Taubin三步预测第57页/共74页数据对比第