蓝噪声采样及高质量网格生成方法

CASIA OpenIR > 毕业生 > 博士学位论文

	蓝噪声采样及高质量网格生成方法
	郭建伟
	2016-05-31
学位类型	工学博士
英文摘要	在多媒体处理与计算机图形学领域，采样是指在给定区域内产生满足一定分布特性的点集图案。其中，最重要的一种采样技术称为蓝噪声采样，它是指采样点集分布既满足随机性又满足均匀性，同时在频域上具有缺乏低频能量、能量径向对称等重要的频谱特征，这些性质在图像点绘、重要性采样、渲染、纹理合成、几何处理等方面有着广泛的应用。另一方面，网格模型是三维几何表示的基本形式，网格生成是用一个离散元素集合来近似表示一个给定的封闭区域。它是连接计算机图形学和工业界的重要桥梁，因此高质量网格生成成为了图形学以及数字几何处理领域的一个研究热点。虽然蓝噪声采样以及网格生成分别都有几十年的研究历史，但是很少有工作将两者结合起来同时研究。本文一方面研究如何在二维和三维网格曲面上进行高质量和高效率的蓝噪声采样，包括等半径的均匀采样和变半径的自适应采样；另一方面将深入探索蓝噪声采样与网格生成之间的关系，并且提出高质量网格生成的框架，可以控制生成网格的最小角；在此基础上，我们进一步将这些技术推广到三维形体的内部，生成高质量的四面体网格。论文主要研究工作和贡献总结如下：（1）二维泊松圆盘采样点集的快速三角化。对最大化泊松圆盘采样（以下简称MPS）点集进行Delaunay三角化，得到的网格具有许多良好的几何性质。但是前人的方法不能处理变半径的采样以及非最大化采样的情况。针对这些问题，我们提出了一种更为简单和快速的算法对泊松采样点集进行Delaunay三角化，同时采用GPU对其进行加速，可以极大地提高算法的效率。（2）网格曲面上的快速最大化泊松圆盘采样及网格生成。本文研究网格曲面上的快速最大化泊松圆盘采样方法，提出了利用细分网格和局部冲突检测的方式实现采样，大大减小了对内存的需求；进而利用最大化点集进行重新网格化，并通过一种优化的手段使得网格的质量满足用户的需求。该方法特别适合解决传统方法在模型相近或者自相交区域容易产生拓扑错误的问题。（3）基于最远点优化的蓝噪声采样及曲面重新网格化。我们重点研究基于最远点优化（以下简称FPO）的二维非均匀采样和曲面上的采样，提出采用正则三角化/Power图对非均匀FPO进行理论分析，并且提出了一个完整的方法框架计算曲面上的最远点插入位置，从而得到高质量的蓝噪声采样以及高质量的网格。（4）基于最大化泊松圆盘采样的四面体网格生成。给定一个封闭的网格曲面模型，我们将上述的MPS采样方法应用到三维形体内部。本方法首先在三维形体的边界表面进行MPS采样，根据表面采样点集提取表面网格，并使用一种松弛方法对表面网格进行边界保护；然后在三维形体内部进行体采样，根据体采样点集，使用三维Delaunay三角化方法或者三维正则三角化方法，提取得到四面体网格；最后提出一种网格优化的方法来消除四面体网格中的薄片，从而提高网格的质量。; Although blue noise sampling and mesh generation has decades of research history, respectively, few work combine both at the same time. In this paper, we present several efficient blue noise sampling methods in 2D domain and on surfaces, including uniform sampling and adaptive sampling. We also explore the relationship between blue noise sampling and mesh generation, and put forward the framework of mesh generation with high quality, where we can control the generated minimum angle. Based on these, we further generalize the sampling technology to the interior of 3d models, to generate high quality tetrahedral mesh. The main research content and contributions of this paper include: (1) Efficient triangulation of 2D Poisson-disk sampled point sets. If a sampled point set satisfies the maximal Poisson-disk Sampling (MPS) and minimal distance properties, the corresponding Delaunay triangulation of such a point set satisfies many nice geometric properties. However, previous approach cannot triangulate non-maximal or non-uniform Poisson-disk point sets. Therefore, we present a simple yet efficient algorithm for triangulating a 2D input domain containing a Poisson-disk sampled point set. We also design a GPU version of our algorithm to speedup the triangulation. (2) Efficient maximal Poisson-disk sampling and remeshing on surfaces. We study the problem of maximal Poisson-disk sampling on mesh surfaces. We present a simple approach that generalizes the 2D maximal sampling framework to surfaces. The key observation is to use a subdivided mesh as the sampling domain for conflict checking and void detection. Our method gains several improvements upon the state-of-the-art surface MPS algorithm, including smaller memory footprint, faster conflict checking, and remeshing with valid topology. (3) Blue noise sampling and remeshing with farthest point optimization. We present a new technique for non-uniform blue noise sampling and remeshing on surfaces. Our approach is based on the FPO framework to find the farthest point, using the concept of the regular triangulation and the power diagram. We are able to achieve high quality remeshing superior to the state-of-the-art approaches of blue noise remeshing. (4) Tetrahedral meshing via maximal Poisson-disk sampling. We propose a simple yet effective method to generate 3D-conforming tetrahedral meshes from closed 2-manifold surfaces. Our approach is inspired by recent work on maximal Poisson-disk sampling (MPS), which can generate well-distributed point sets in arbitrary domains. We first perform MPS on the boundary of the input domain, we then sample the interior of the domain, and we finally extract the tetrahedral mesh from the samples by using 3D Delaunay or regular triangulation for uniform or adaptive sampling, respectively. We also propose an efficient optimization strategy to protect the domain boundaries and to remove slivers.
关键词	蓝噪声采样重新网格化四面体网格化网格质量优化
文献类型	学位论文
条目标识符	http://ir.ia.ac.cn/handle/173211/11670
专题	毕业生_博士学位论文
作者单位	中国科学院自动化研究所
第一作者单位	中国科学院自动化研究所
推荐引用方式 GB/T 7714	郭建伟. 蓝噪声采样及高质量网格生成方法[D]. 北京. 中国科学院大学,2016.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
最终版_博士学位论文_郭建伟.pdf（14659KB）	学位论文		限制开放	CC BY-NC-SA