网站地图 | 联系我们 | English | 意见反馈 | 主任信箱
 
首页 中心概况 新闻动态 科研进展 交流合作 人才培养 研究队伍 人才招聘 政策规章 数学交叉科学传播
科研进展
科研成果
研究专题
获奖
现在位置:首页 > 科研进展 > 科研成果
曲面蓝噪声网格生成算法方面取得进展
【打印】【关闭】

2015-10-31 | 编辑:文\先进制造部

目前,先进制造部高档数控研究课题组在曲面蓝噪声网格生成算法方面取得进展。

随着计算机技术和三维扫描技术的发展, 网格模型已成为具有复杂几何的三维形体在计算机中表示的主要方法之一。常见的网格模型包括三角网格、四边网格及多边形网格。其中,三角网格因其简单的结构及易于操作性受到了更加广泛的关注及应用。常见的三角网格数据的获取有三种途径:(1)通过激光扫描仪扫描;(2)通过对连续曲面离散化; (3)通过等值面提取得到网格数据。通过这些直接手段得到的网格数据通常有数据量大、三角形网格质量差等缺点,不能直接应用于几何建模、有限元模拟或计算机动画中。因此,高质量的三角网格生成方法已成为图形学以及数字几何处理领域的研究热点。

现有的高质量三角网格生成方法的研究主要针对如何提高三角形的质量,而忽略了网格顶点的整体分部。而在许多领域的应用中,都要求采样点的整体分布既满足随机性又满足均匀性,这些性质统称为蓝噪声性质。蓝噪声性质和人类的视觉感知系统密切相关,在图像合成,真实感绘制,机器人路径规划等领域有着大量应用。现有的蓝噪声采样方法大致分成三类:(1)泊松圆盘采样方法及其变种;(2) 基于Lloyd 迭代的优化方法;(3) 基于样本或者某些规则的生成方法。虽然蓝噪声采样以及网格生成分别都有几十年的研究历史,但很少有工作将两者结合起来同时研究。我们与沙特KAUST可视化中心合作,已成功研究了系列基于最大化泊松圆盘采样(Maximal Possion Disk Sampling--MPS)及最远点优化(Farthest Point Optimization--FPO)的曲面蓝噪声采样算法,并利用优化的采样点重新生成高质量三角网格,极大程度上克服了现有的网格生成方法生成的网格顶点分布差、不适于物理模拟、且不易控制最小角度的缺点。

近日,我们进一步将三维曲面的蓝噪声采样问题诠释为在容积限制(capacity constraint)下的最优输运(optimal transport)问题。容积限制是控制曲面采样点局部的疏密程度的重要手段。在此前涉及容积限制的曲面采样方法中,容积限制仅做为重心Voronoi图(Centroidal Voronoi Tessellation--CVT)能量函数的正则化子,因而不能得到准确满足。我们的方法可以保证生成的采样数据精确满足容积限制,从而保证蓝噪声网格的(基于密度函数的)均匀性。

下图为各种曲面采样方法与我们的新方法在密度函数(density-adaptive)指导下的均匀性对比。图中各列从左至右依次为:最大化泊松圆盘采样法(Maximal Possion Disk Sampling--MPS)、最远点优化法(Farthest Point Optimization--FPO)、经典CVT方法(Centroidal Voronoi Tessellation)、容积限制下的CVT方法(capacity-constrained Centroidal Voronoi Tessellation)、及我们新的最优输运法(optimal transport)。 第一行图示为各种方法的曲面采样结果;第二行是在该采样结果下的限制权图(restricted Power Diagram), 不同颜色代表该权图对偶的三角化中相应的三角型的不同度数(valence = 3,4,5,6,7);第三行代表实际容积与期望容积的相差情况,从蓝至红代表差值由小变大;第四行是代表采样均匀性的频谱图 ,震荡越大代表与期望差值越大;最后一行是各方法的各向异性图(即不均匀性,震荡越大表示均匀性越差)。可以看出, 我们的新方法生成的采样点集及网格数据比已有的经典方法具有更好的蓝噪声性质。

欢迎访问国家数学与交叉科学中心 
地址:北京海淀区中关村东路55号 邮编:100190 电话: 86-10-62613242 Fax: 86-10-62616840 邮箱: ncmis@amss.ac.cn