A volumetric fusion technique for surface reconstruction from silhouettes and range data

Optical triangulation, an active reconstruction technique, is known to be an accurate method but has several shortcomings due to occlusion and laser reflectance properties of the object surface, that often lead to holes and inaccuracies on the recovered surface. Shape from silhouette, on the other hand, as a passive reconstruction technique, yields robust, hole-free reconstruction of the visual hull of the object. In this paper, a hybrid surface reconstruction method that fuses geometrical information acquired from silhouette images and optical triangulation is presented. Our motivation is to recover the geometry from silhouettes on those parts of the surface which the range data fail to capture. A volumetric octree representation is first obtained from the silhouette images and then carved by range points to amend the missing cavity information. An isolevel value on each surface cube of the carved octree structure is accumulated using local surface triangulations obtained separately from range data and silhouettes. The marching cubes algorithm is then applied for triangulation of the volumetric representation. The performance of the proposed technique is demonstrated on several real objects.     

Generation of a finite element MESH from stereolithography (STL) files

The aim of the method proposed here is to show the possibility of generating adaptive surface meshes suitable for the finite element method, directly from an approximated boundary representation of an object created with CAD software. First, we describe the boundary representation, which is composed of a simple triangulation of the surface of the object. Then we will show how to obtain a conforming size-adapted mesh. The size adaptation is made considering geometrical approximation and with respect to an isotropic size map provided by an error estimator. The mesh can be used “as is” for a finite element computation (with shell elements), or can be used as a surface mesh to initiate a volume meshing algorithm (Delaunay or advancing front). The principle used to generate the mesh is based on the Delaunay method, which is associated with refinement algorithms, and smoothing. Finally, we will show that not using the parametric representation of the geometrical model allows us to override some of the limitations of conventional meshing software that is based on an exact representation of the geometry.     

利用立体图对的三维人脸模型重建算法

利用人脸正面立体图对重建三维人脸模型。无需三维激光扫描仪和通用人脸模型．获取立体图对并校正后，利用种子像素扩张算法实现图像匹配．种子像素选取算法能使足够数量的种子像素具有可靠视差；还提出了基于视差置信度的扩张算法，降低了视差图中大面积误匹配区域出现的可能性；最后，利用碟状粒子描述和Delaunay三角剖分重建三维人脸模型．实验结果表明，文中算法能够产生光滑逼真的三维人脸模型．     

散乱数据点的增量快速曲面重建算法

给出了一个新的散乱数据的曲面重建算法.算法充分利用邻近点集反映出的局部拓扑和几何信息,基于二维Delaunay 三角剖分技术快速地实现每个数据点的局部拓扑重建,然后通过自动矫正局部数据点的非法连接关系,以增量扩张的方式把局部三角网拼接成一张标准的整体二维流形网格.该算法在重建过程中能自动进行洞的检测,判断出散乱数据所蕴涵的开或闭的拓扑结构.实验结果表明,该算法高效、稳定,可以快速地直接重构出任意拓扑结构的二维流形三角形网格.     

On surface reconstruction: A priority driven approach

To reconstruct an object surface from a set of surface points, a fast, practical, and efficient priority driven algorithm is presented. The key idea of the method is to consider the shape changes of an object at the boundary of the mesh growing area and to create a priority queue to the advancing front of the mesh area according to the changes. The mesh growing process is then driven by the priority queue for efficient surface reconstruction. New and practical triangulation criteria are also developed to support the priority driven strategy and to construct a new triangle at each step of mesh growing in real time. The quality and correctness of the created triangles will be guaranteed by the triangulation criteria and topological operations. The algorithm can reconstruct an object surface from unorganized surface points in a fast and reliable manner. Moreover, it can successfully construct the surface of the objects with complex geometry or topology. The efficiency and robustness of the proposed algorithm is validated by extensive experiments.     

由任意形状轮廓线重建三维表面的方法研究

由一组二维轮廓线重建出物体的三维表面是医学数据可视化的一种主要绘制方式。当轮廓线比较复杂,例如当遇到非凸轮廓或相邻层轮廓线相差过大时,常用的三角化拼接方法就会失败。文章提出一种新的轮廓拼接方法能够处理任意形状的轮廓线。该方法的基本思想是对轮廓线进行凹凸性层次分析,然后将相邻轮廓线从外到内逐层拼接,从而构成一个三角化的物体表面。实验结果表明,该算法对于手动勾画和自动提取的轮廓线都可以给出较好的重建效果。     

各务异性网格生成及其在曲面三角化中的应用

网格生成技术在工程分析，科学计算可视化等领域有着重要的意义，为了快速进行曲面三角化，提出了一种二维各向异性网格生成方法，通过引入椭圆距离和椭圆矩阵，定义了三角形的外接椭圆，从而将Delaunay三角化方法扩展到各向异性环境中，并讨论了各向异性网格的性质，随后将各向异性网格方法应用在曲面三角化当中，并将曲面的第一基本形式作为参数域的椭圆矩阵，同时给出了曲面Delaunay三角化的定义，从而成功地利用了各向异性网格方法对曲面进行三角化，实践证明，不仅其速度要大大快于传统的三角化方法，并且该方法能统一处理各种二次曲面和裁剪NURBS曲面。     

Voxel-based surface area estimation: from theory to practice

Consider a complex, highly convoluted three-dimensional object that has been digitized and is available as a set of voxels. How can one estimate the (original, continuous) area of a region of interest on the surface of the object? The problem appears in the analysis of segmented MRI brain data and in other three-dimensional imaging applications. Several difficulties arise. First, due to the complexity of the surface and its foldings, the region of interest and its intended boundary can be concealed and are therefore difficult to delineate. Second, the correct surface topology on intricate voxel sets may not be obvious. Third, the surface area of a digital voxel world is generally very different than the area of the underlying continuous surface. These problems can be partly circumvented by transforming the voxel data to a polyhedral surface representation. Our challenge is to accomplish the task while maintaining the original voxel representation. Estimators for the continuous surface area of digital objects have been available for some time. However, the known methods are limited to fairly smooth and “well-behaved” surfaces. This research bridges the gap between the available surface area estimation theory, that applies to idealized settings, and the reality of MRI brain data. Surface connectivity ambiguities are alleviated by considering the object/background boundary voxel faces rather than the border voxels themselves. The region of interest on the surface is delimited by growing geodesic paths between user-provided anchor points. Surface estimation is extended to admit surfaces with higher curvature than previously considered. Performance evaluation results are provided, and operation on MRI brain data is demonstrated.     

医学图像三维重建中的关键算法

该文主要讨论了基于序列图像的三维重建中的两个关键算法:特征数据点列的重采样算法与三角化算法。把Douglas-Peucker线性简化算法应用在特征边界的重采样上,数据的压缩比得到了明显的改善,也显著地提高了可视化速度。并使用一种简单的三角化算法,对重采样后的数据点列进行三角化,实现目标的三维重建。     

基于VTK的散乱点集三角网重建算法研究

散乱点数据在机械产品测量造型、地理信息系统等众多领域来说都较易得到。为使VTK可视化平台中的数据处理及面显示应用面更广,本文设计了基于平坦度的自适应增量的网格构造算法,将散乱点数据格式转换成VTK数据格式,从而利用VTK流水线机制进行面绘制。该算法实现了空间直接三角剖分,而且动态调整逼近误差。实验证明,该算法能
高效、可靠地生成贴近原始曲面的三角网格,并取得较理想的VTK绘制效果。该算法对于三角剖分问题和VTK可视化平台的数据处理具有一定的理论和实际意义。     

A Delaunay-based region-growing approach to surface reconstruction from unorganized points

This paper presents a Delaunay-based region-growing (DBRG) surface reconstruction algorithm that holds the advantages of both Delaunay-based and region-growing approaches. The proposed DBRG algorithm takes a set of unorganized sample points from the boundary surface of a three-dimensional object and produces an orientable manifold triangulated model with a correct geometry and topology that is faithful to the original object. Compared with the traditional Delaunay-based approach, the DBRG algorithm requires only one-pass Delaunay computation and needs no Voronoi information because it improves the non-trivial triangle extraction by using a region-growing technique. Compared with the traditional region-growing methods, the proposed DBRG algorithm makes the surface reconstruction more systematic and robust because it inherits the structural characteristics of the Delaunay triangulation, which nicely complements the absence of geometric information in a set of unorganized points. The proposed DBRG algorithm is capable of handling surfaces with complex topology, boundaries, and even non-uniform sample points. Experimental results show that it is highly efficient compared with other existing algorithms.     

一种带岛屿约束数据域的三角网剖分算法研究

文中对多边形内部三角剖分算法及具有属性的带岛屿的约束数据域的D－三角剖分算法进行了研究，提出了一种适用于多边形内部的基于“最小内角优先原则“D－三角剖分算法及适用于多边形内，外部构网通用三角剖三角剖分算法，算法充分考虑到了构网数据域中存在多种不同属性块，并成功将算法应用于工程项目之中。     

实现3D离散点优化三角划分的三维算法

本文系统研究了３Ｄ离散数据的直接三角划分，并解决了与多值曲面相对应离散数据的分片三角划分问题。实现这一算法的关键是将这些与多值曲面相对应的离散数据按有关的特征线分解，慢之转化成较简单的问题分别进行处理。目前，这种分片三角划分算法已在Ｂｅｚｉｅｒ三角曲面插值中取得了良好的效果。     

Surface reconstruction using Delaunay triangulation for applications in life sciences

The Delaunay triangulation is an established method to define neighborhood relations in multi-particle systems. In particular, this method was employed for interacting multi-cellular systems in Biology. The extension of this method to a sub-cellular level that considers the membrane and the inner structure of cells is not straight forward and subject of this article. It is the objective to use a three-dimensional Delaunay-triangulation as a basis for the definition of a triangulation of a subset of particles that form a surface.An essential problem of this objective is the conservation of the number of particles belonging to the surface. This excludes established surface reconstruction algorithms. The presented algorithm allows the definition of a triangulation within a subset of particles attributed to a surface without the deletion of particles. A particular challenge is the deletion of connection that infer three-dimensional structures in the surface. The presented method is suitable for many configurations. Its performance and its limitations are analyzed and discussed.The developed algorithm for the reconstruction of connections in a surface is suitable to be used for simulations of biological cells because of the inherent conservation of the number of particles attributed to the membrane.     

复杂非均质地层的等值线生成算法研究

等值线图是复杂油气藏地质研究中的一类重要表示形式。针对地层数据特点,研究和分析了复杂非均质地层数据等值线绘制方法的不足,提出一种新的分区方法,实现了带断层的数据集合划分。基于Delaunay三角剖分算法,并以几何多边形为雏形,建立了带约束的三角网格模型。采用约束Delaunay三角网的拓扑结构,选用改进的反距离加权插值算法,有效地解决了断层两侧高程值问题,并结合实际应用要求在VC++与OpenSceneGraph的开发环境下,实现了非均质带断层的地层等值线的绘制。通过对国内某采油厂的实际油气储集地层数据等值线图的绘制和可视化,证明了方法的可行性和准确性。     

Direct generation of extended STL file from unorganized point data

An extended STL file format is presented in this paper. Differing with existing solutions, it proposes a new format to produce and store triangles. The format uses a cluster unit composed of several triangles. The main advantages of the format are that it contains both geometry and topological information and has improved storage capability. Direct generation of the extended STL from the scanned data has a great advantage in that it can reduce the time and error in modeling process. In order to obtain the format from unorganized point cloud, a new triangulation algorithm was introduced. The algorithm is based on reconstructing the relative Delaunay triangulation of the sample points on the surface. Other advantages of the extended STL format were also presented in this paper.     

Shape description by medial surface construction

The medial surface is a skeletal abstraction of a solid that provides useful shape information, which compliments existing model representation schemes. The medial surface and its associated topological entities are defined, and an algorithm for computing the medial surface of a large class of B-rep solids is then presented. The algorithm is based on the domain Delaunay triangulation of a relatively sparse distribution of points, which are generated on the boundary of the object. This strategy is adaptive in that the boundary point set is refined to guarantee a correct topological representation of the medial surface     

一个利用法矢的散乱点三角剖分算法

曲面上散乱点的三角剖分在曲面重建中发挥着重要作用,借助于曲面上的法矢信息和三维Delaunay三角剖分算法,该文给出了一种新的散乱点三角剖分算法,输入一组散乱点以及所在曲面S在这些散乱点处的一致定向的法矢信息,该算法将产生一张插值散乱点的三角网格曲面M,并且曲面M可以近似地看成是曲面S的三角剖分,算法的主要步骤分为两步：首先通过曲面S的一致定向的法矢信息,在曲面S的同一侧添加辅助点,利用这些辅助点来剔除Delaunay三角剖分中产生的不需要的三角片;然后将剩余的三角片连接成一张完整的网格曲面,与基于中轴的三角剖分算法相比,该文算法需要更少和更简单的计算,与局部三角剖分算法相比,该文算法可以更有效地避免重建后的曲面产生自交,该文的算法可用于任意拓扑的光滑曲面重建。     

基于LiDAR点云数据的三角网构建算法

在现有Delaunay三角网生长法的基础上进行改进,提出了一种三角网生长算法.该算法对大规模点云进行等格网分块,自适应确定搜索范围.通过在构建过程中对生成的基线进行分组和排序,动态删除封闭点,提高了构建三角网的速度;通过在整个点集范围内进行搜索,避免了通过插值所产生的误差和模块之间的拼接过程.利用此算法对大规模LiDAR点云数据进行构网,结果表明了该算法的有效性.