搜索
离散数字几何处理彭群生胡国飞浙江大学CAD&CG国家重点实验室2003年09月24日长沙内容提要一、离散数字几何处理简介二、三角网格的参数化意义和目的前人工作和我们的最新研究成果参数化的例子及其应用三、三角网格的光顺意义和目的前人工作和我们的最新研究成果参数化的例子四、结论和未来的工作一、数字几何处理简介几何表示参数曲面隐式曲面体数据多边形网格点数据网格变成主流的几何表达方式.一、数字几何处理简介PositionNormalColorTextureBRDF…几何信息:N维三维数字几何处理过程获取处理存储和传输应用(仿真,娱乐…)参数化光顺/去噪简化/压缩多分辨率编辑……三角网格参数化猫头(135个顶点,257个三角形)网格光顺和去噪3D网格模型的光顺可视化（刘新国2002）兔子基网格(162三角形)原始网格和LOD表示三角网格的简化多分辨率编辑三角网格的编辑（周昆2002）纹理映射球面凸组合参数化算法的纹理映射效果（胡国飞2003）重网格化parameterizationresamplingABF参数化方法的Remeshing效果(Sheffer2000)重网格化parameterizationresamplingremeshingMIPS参数化方法的Remeshing效果（Hormann1999）曲面拟合parameterizationB-SplineSurface平面凸组合参数化方法曲面拟合效果(Floater1998)几何形状过渡累进球面参数化方法的Morphing效果（Praun2003）问题的描述研究内容前人工作我们的最新研究成果参数化的例子及其应用二、三角网格参数化问题的描述给定一个由空间点集组成的三角化网格和一个参数域，寻求一个参数域上的点到三角网格点的一一对应映射，并且在参数化域上保持原始网格的拓扑信息。3iP3iP3iP意义曲面拟合:通过参数化，把离散的3D数据点用一个光顺的参数曲面来拟合。纹理映射:利用表面网格参数化信息，把一幅纹理图像映射到三维网格上，使得表面网格看上去更加生动逼真。重网格化:利用参数化把三角化曲面转化成具有细分连通性的规则网格，并且在此基础上进一步作多分辨率分析。几何形状过渡:通过参数化到相同的参数域进行点对应，使得两个不同物体之间的平滑过渡。研究内容1保证参数化的有效性三维网格二维参数化结果研究内容2寻求某种几何度量的变形最小化不同的参数化方法下的纹理映射,具有不同的变形研究内容保面积?保角?等距?2寻求某种几何度量的变形最小化研究内容3具有线性时间空间复杂度的算法全局参数化方法：求解整体约束非线性系统局部参数化方法：求解局部线性系统前人工作基于松弛参数化方法：GraphEmbedding(Tutte60)平面凸组合(Floater97)球面松弛参数化(Alexa00)球面凸组合(胡国飞和彭群生03)基于调和映射的方法调和映射(Pinkall93,Eck95)累进球面参数化(周昆02,Praun03)分割展平法整体Angle-Based-Flattening(Sheffer00)局部Bounded-Distortion-Piecewise(Sorkine02)累进球面参数化(周昆2002)基本思路1生成带有局部参数化信息的累进网格表示。循环地执行边收缩操作，直到当前简化网格变成一个凸多面体（基网格）。对每次边收缩操作，收缩边的两个顶点按简化后生成的简化网格表面作局部参数化。2由于基网格是凸多面体，从基网格的中心投影可以得到相应的球面网格。对每次顶点分裂操作，使用局部参数化信息把两个分裂出来的顶点映射在单位球面上。3所有的顶点分裂操作执行完毕，球面参数化生成。累进球面参数化流程edgecollapsesMiSpn,…,SpiM=MnM0vertexsplitsMnvertexsplitsMjvertexsplitsMiedgecollapsesMjSpi+1,…,SpjedgecollapsesM0Spj-1,…,Sp1累进球面参数化实例凸组合球面参数化(胡国飞2003)基本思路1球面投影：初始化2凸组合：松弛迭代求解球面新点3虚拟边界技术：改善边界变形特色1参数化解存在且唯一，数值解收敛于真实解2权值λ可控，局部保形凸组合参数化实例3D网格模型的球面参数化三、网格光顺和去噪问题的描述研究内容前人工作我们的最新研究成果参数化的例子及其应用问题的描述在数据获取过程中，人为的扰动或者扫描仪本身的缺陷使得生成三维数据带有噪声(noise)。去噪是消除三维数据表面的局部几何突变，并在局部范围内保持形状变化的连贯性。光顺是在剔除噪声获取离散曲面更高阶光滑性的同时，保持网格模型的拓扑信息和几何特征不变性。问题的描述重心约束的光顺算法（刘新国2001）目标1体积保持(volume-preserving)Laplace光顺算子使得体积收缩目标2特征保持(feature-preserving)牙齿，脊背等特征在光顺后得到保持(胡国飞2003)目标3线性时间和空间复杂度－求解非线性系统－求解线性系统(多次)－求解线性系统(单步)前人的工作1能量最小化方法(求解非线性系统)－薄膜能量(Morton92)：－薄板能量(Welch92)：－重心约束的磨光算法(刘新国02)优点:基于能量方程去除表面噪声，通过引入约束条件，可有效控制体积收缩和模型变形。缺点:非线性系统，运算时间长前人的工作2基于Laplace的光顺算子(求解线性系统)优点:线性系统，算法简单，运算速度快缺点:需要多次迭代才能达到光顺效果，容易导致过光顺，体积收缩的情况改进算法：λ|μ方法(Taubin95)HC算法(Vollmer99)HC算法前人的工作3鲁棒的顶点预测方法网格的双边滤波器(Freishman03,Jones03)－图像的双边滤波器是把象素到邻域点的距离以及该象素的亮度值与邻域点的亮度值之差作为两个参数。－Freishman网格双边滤波把点与周围邻域点的距离以及该距离向量与该点的法向的内积作为双边滤波器两个参数。－Jones把点与周围邻域三角形重心的距离以及与该点到周围邻域三角形的距离作为双边滤波器的两个参数。优点:无需迭代,算法简单,运算速度快.缺点:邻域难确定，邻域过小，容易导致过光顺和特征加强等。邻域过大导致运算时间增大。重心约束的磨光算法(刘新国02)网格曲面能量离散曲面的磨光——能量最小化重心约束能量最小化局部迭代求解结果结果三步顶点预测滤波器(胡国飞03)算法特色：1三步预测：利用两次双边滤波器（SOT和FOV）和一次准Laplacian滤波来三步预测顶点。2限于局部邻域：根据顶点的二阶邻域三角形，一阶邻域顶点以及顶点本身预测新点。3区分特征和噪声：有效排除了二阶邻域以外噪声对它的干扰，通过顶点局部邻域的几何信息来预测顶点的方法既能有效地剔除噪声又能保持网格的凹凸特征。邻域SOT:二阶邻域三角形FOV:一阶邻域顶点特征和噪声噪声:孤立的顶点扰动是噪声，因为它只牵涉到一阶邻域三角形的局部几何变形，我们予以剔除。特征:顶点及其一阶邻域顶点沿同一方向上的波动，且与其二阶邻域三角形的形状变化趋势一致，我们认为它是一种三角网格的局部特征，给予保持甚至增强。SOT光顺将顶点投影到其二阶邻域三角形所在平面上，再把所得投影点的加权平均作为该顶点的估计，对于变化平滑的特征，将产生过估计，对于突变的噪声，会导致欠估计。最后使得凹凸特征被放大，而噪声被削弱。SOT光顺利用点和二阶邻域三角形的几何关系，进行双边滤波准Laplacian光顺噪声点对于原始网格数据来讲毕竟只占小部分，为了减小第一步处理对大部分正常顶点位置的估计误差，我们取原顶点和第一次预测位置的加权平均作第二次估计，称之为准Laplacian光顺：基于FOV预测顶点沿顶点的法线方向，以平均曲率为权值，移动各顶点，使得模型表面趋于最小曲面。FOV预测将使得噪声点快速调整到符合局部邻域变化趋势的曲面上。基于FOV预测顶点优点:－通过鲁棒的顶点预测进行光顺，无需迭代；－避免过光顺和特征加强等；－算法简单，运算速度快.(a)原始网格(b)噪声网格(c)一次光顺(d)二次光顺三步顶点预测滤波器光顺效果结果结果三步顶点预测算法：恐龙的光顺结果结果三步顶点预测算法：小噪声和大噪声的剔除效果Laplace20Taubin20FreishmanJonesOurMethod结果三步预测非迭代算法噪声网格80次Laplace40次Taubin三步预测数据对比今后的工作1拓展到点模型和体数据模型。2自适应特征识别，使得光顺模型具有特征保持性。3引进球面调和分析，建立一种数字几何的新的频谱分析方法。谢谢大家！局部参数化凸组合球面参数化凸组合球面投影初始化：以模型中心为球心,做模型包围球,把所有顶点投射到球面上边界处理虚拟边界的生成凸组合中心点是周围邻域点的凸组合Laplacian光顺Laplace算子各项同性扩散噪声λ|μ方法Taubin引进新的算子来减缓体积收缩其中图像双边滤波器图像的双边滤波器