Ordering Points for Incremental TIN Construction from DEMs

The standard method of building compact triangulated surface approximations to terrain surfaces (TINs) from dense digital elevation models (DEMs) adds points to an initial sparse triangulation or removes points from a dense initial mesh. Typically, in each triangle in the current TIN, the worst fitting point, in terms of vertical distance, is selected. The order of insertion of the points is determined by the magnitude of the maximum vertical difference. This measure produces triangulations that minimize the maximum vertical distance between the TIN and the source DEM. Other approximation criteria are often used, however, including the root-mean-squared error or the mean absolute error, both for the vertical difference and normal difference, i.e., the distance in the direction of the normal to the triangular approximation. For these approximation criteria, we still select the worst fit point, but determine the insertion order by various sums of errors over the triangle. Experiments show that using these better evaluation measures significantly reduces the size of the TIN for a given approximation error.     

TIN generation and point-cloud compression for vehicle-based mobile mapping systems

The vehicle-based mobile mapping system (MMS) is effective for capturing dense 3D data of roads, roadside objects and buildings. Since discrete points are not convenient for many application systems, a triangulated irregular network (TIN) is often generated from point-clouds. However, TIN data require two or three times larger storage than point-clouds. If TIN models can be promptly generated while loading point-clouds, it would not be necessary to store huge TIN models on a hard disk. In this paper, we propose two efficient TIN generation methods according to types of laser scanners. One is the line-by-line TIN generation method, and the other is the GPS-time based method. These methods can quickly generate TIN models based on scan lines of laser scanners. In addition, we introduce a new compression method to reduce the loading time of point-clouds. Our compression method is also based on the scan lines of laser scanners. Since points captured by a MMS tend to be positioned on nearly straight lines, their data size can be significantly reduced by coding the second order differences.     

约束数据域的Delaunay三角剖分算法研究及应用

研究了一种约束Delaunay三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高了构网速度,并将该算法用于地面模型的构建中,实现了地形三维可视化。     

Estimation of average DEM accuracy under linear interpolation considering random error at the nodes of TIN model

The concept of a digital elevation model (DEM) can be used for a digital representation of any single‐valued surface such as a terrain relief model (digital terrain model, DTM). DEMs are widely used in remote sensing, geographical information systems (GIS), and virtual reality. Estimating the accuracy of a DEM is an essential issue in the acquisition of spatial data, particularly for applications that require a highly accurate DEM, such as engineering applications. The accuracy of a DEM is subject to many factors such as the number of sampling points, the spatial distributions of the sampling points, the methods used for interpolating surface elevations, the propagated error from the source data, and other factors. Of these factors, this study will focus on estimating the mean elevation error in a DEM surface that is caused by errors of component nodes in a triangulated irregular network (TIN). This paper will present a newly derived mathematical formula, with the details of the procedure used to derive this formula, to study the relationship between the errors at the TIN nodes and the propagated mean elevation error of a DEM surface that is linearly constructed from the TIN. We have verified the analytical formula by numerical simulation. The experimental results confirm the theoretical derivation of the formula.     

基于D-TIN剖分的三维人脑表面模型重建算法*

为解决人脑表面结构特征建模中CT以及MRI等二维图像显示所带来的信息遗漏、观察不便等缺陷,提出了基于D-TIN（Delaunay TIN）剖分的三维人脑表面模型建模策略。针对实体模型分层切片数据,以离散拟合思想为算法依据,采用Delaunay不规则三角网剖分技术,动态构建模型表面控制点之间的拓扑关系,以此生成三维人脑表面模型;进而结合OpenGL可视化工具,对模型进行可视化渲染,最终得到满足医学需要的三维人脑实体模型。该模型直观、清晰、全面地再现了人脑的表面结构,对脑部病变的认知、手术指导以及认知神经科学     

Efficient generation of discontinuity-preserving adaptive triangulations from range images

This paper presents an efficient technique for generating adaptive triangular meshes from range images. The algorithm consists of two stages. First, a user-defined number of points is adaptively sampled from the given range image. Those points are chosen by taking into account the surface shapes represented in the range image in such a way that points tend to group in areas of high curvature and to disperse in low-variation regions. This selection process is done through a noniterative, inherently parallel algorithm in order to gain efficiency. Once the image has been subsampled, the second stage applies a two and one half-dimensional Delaunay triangulation to obtain an initial triangular mesh. To favor the preservation of surface and orientation discontinuities (jump and crease edges) present in the original range image, the aforementioned triangular mesh is iteratively modified by applying an efficient edge flipping technique. Results with real range images show accurate triangular approximations of the given range images with low processing times.     

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

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

一种基于三维Delaunay三角化的曲面重建算法

提出一种基于三维Delaunay三角化的区域增长式曲面重建方法。该方法以空间点云的Delaunay三角化为基础,结合局部区域增长的曲面构造,较以往方法具有人为参与更少、适用范围更广的优点。算法采用增量式插入点的方式构建空间Delaunay划分,采用广度优先算法,以外接圆最小为准则从Delaunay三角化得到的四面体中抽取出合适的三角片构成曲面。该算法的设计无须计算原始点集的法矢,且孔洞系数对重建的结果影响很小,重建出的三角网格面更符合原始曲面的几何特征。无论待建曲面是否是封闭曲面,本算法均可获得较好的重建效果。     

Approximating Shortest Paths on Weighted Polyhedral Surfaces

One common problem in computational geometry is that of computing shortest paths between two points in a constrained domain. In the context of Geographical Information Systems (GIS), terrains are often modeled as Triangular Irregular Networks (TIN) which are a special class on non-convex polyhedra. It is often necessary to compute shortest paths on the TIN surface which takes into account various weights according to the terrain features. We have developed algorithms to compute approximations of shortest paths on non-convex polyhedra in both the unweighted and weighted domain. The algorithms are based on placing Steiner points along the TIN edges and then creating a graph in which we apply Dijkstra's shortest path algorithm. For two points s and t on a non-convex polyhedral surface P , our analysis bounds the approximate weighted shortest path cost as || Π'(s,t)|| ≤ ||Π(s,t)|| + W |L| , where L denotes the longest edge length of \cal P and W denotes the largest weight of any face of P . The worst case time complexity is bounded by O(n ⁵ ) . An alternate algorithm, based on geometric spanners, is also provided and it ensures that ||Π' (s,t)|| ≤β(||Π(s,t)|| + W|L|) for some fixed constant β >1 , and it runs in O(n ³ log n) worst case time. We also present detailed experimental results which show that the algorithms perform much better in practice and the accuracy is near-optimal. Received April 15, 1998; revised February 15, 1999.     

规则DEM地形数据转换为TIN模型的迭代搜索算法

在实际应用中由于规则网格DEM的数据量大而不便存储,而且某些分析计算也经常需要使用TIN模型的DEM,需要将网格DEM转成TIN模型的DEM。采用迭代搜索算法将网格转化为DTIN。在DTIN的生成算法中,对点的定位算法和空外接圆判断算法进行了改进和优化,从而提高了算法的整体执行效率。     

由等高线重构曲面的HASMOC方法应用研究

HASM优化控制方法（High Accuracy Surface Modeling-Optimal Control,HASMOC）是在高精度曲面建模（HASM）方法的基础上,增加更多约束条件方程后形成的一种方法。通过对等高线间格网点高程范围的约束优化控制,最小化HASM基本方程的模,HASMOC方法既能保证地形曲面的整体光滑性,又保证地形曲面对于原始等高线数据的忠实性。实际案例表明,HASMOC方法得到的地形曲面结果优于TIN方法的地形曲面模拟结果;比较分析地形曲面的回放等高线、地形光滑程度和地形曲面的高程分布频率等,可以看出,HASMOC方法能较好地克服TIN的缺点。     

基于三角形网格的浓密视差图提取

提出一种基于三角形网格的浓密视差图提取算法。用SUSAN算法从立体图像对中提取某一幅图像的特征点,用Delaunay的方法将特征点三角化,然后再进行视差的计算,最终得到浓密的视差图。该算法将SUSAN算法和DT(Dalau-nay triangulation)网格结合起来,使算法更加简单化,实现了浓密视差图的快速提取。     

基于三角形网格的浓密视差图提取

提出一种基于三角形网格的浓密视差图提取算法。用SUSAN算法从立体图像对中提取某一幅图像的特征点，用Delaunay的方法将特征点三角化．然后再进行视差的计算，最终得到浓密的视差图。该算法将SUSAN算法和DT（Dalaunay triangulation）N格结合起来，使算法更加简单化，实现了浓密视差图的快速提取。     

通用点线面集Delaunay三角剖分与动态编辑

总结并提出了一种通用点线面集Delaunay三角剖分与动态编辑的统一算法。可以实现离散点的Delaunay三角剖分,约束线、面的Delaunay三角剖分,任意多边形内带特征约束(包括点、线、面)的三角剖分,一般Delaunay三角剖分的外边界都是其离散点集的凸包,且内岛屿一般没有挖掉,本算法实现了Delaunay三角剖分时内、外边界的保界处理。     

增删点后的Voronoi 图生成算法

Voronoi 图可广泛应用于模式识别、计算机图形学、计算机辅助设计、地 理信息系统等领域。利用Voronoi 图及其对偶图Delaunay 三角网构建的不规则三角网TIN 能充分地反映地形地貌特征,对TIN 的统一管理和动态调用可较好地应用到数字高程模型 的建立中。通过联机增量和减量算法来来实现增删点后的Voronoi 图的生成,具有能够动态 修改点集、速度快、效率高等优势。     

Minimal roughness property of the Delaunay triangulation

A set of scattered data in the plane consists of function values measured on a set of data points in R². A surface model of this set may be obtained by triangulating the set of data points and constructing the Piecewise Linear Interpolating Surface (PLIS) to the given function values. The PLIS is combined of planar triangular facets with vertices at the data points. The roughness measure of a PLIS is the L² norm squared of the gradient of the piecewise linear surface, integrated over the triangulated region and obviously depends on the specific triangulation. In this paper we prove that the Delaunay triangulation of the data points minimizes the roughness measure of a PLIS, for any fixed set of function values. This Theorem connects for the first time, as far as we know, the geometry of the Delaunay triangulation with the properties of the PLIS defined over it.     

GenLab: A MATLAB®-based program for structural analysis of folds mapped by GPS or seismic methods

GenLab is a MATLAB^® code for structural analysis of digitally and seismically mapped horizons based on the geometrical model of the developable surface. This model is chosen because surfaces of this type result from the bending of a non-stretching stratum and because deviation from developable geometry implies that bed stretching during folding has occurred. The model is therefore linked with straining of the horizon and can be used for highlighting regions of deformation expressed by brittle fracturing or ductile deformation. Mathematically, a developable surface is one upon which straight lines (generators) can be drawn, and along these generators the orientations of tangent planes of the surface remain constant. Our method involves treating real geological surfaces as approximations to developable surfaces and determines the generator lines at different points on the surface. At these points we consider strip samples of the surface radiating in different directions and examine the variability of strike and dip within each sample strip. The radial scan-line length parameter is user-defined, and the optimal value can be easily identified by geostatistical analysis of the depth data. The local plunge lines (the approximation to the generatrix of a developable fold) are therefore identified as the direction associated with the least variation of surface attitude, i.e., the most constant strike and dip. The map pattern obtained by analyzing the plunges and trends of plunge lines across an area allows identification of domains where folding accords closely with a developable geometry. Such domains are recognized from straight plunge lines, defining parallel or convergent patterns. According to the model, deviations from these patterns correspond to regions of structural complexity associated with ductile or brittle straining of the surface being analyzed. The plunge-line analysis therefore offers a useful technique with potential for predicting strained zones and automatic fault recognition. GenLab allows the rapid implementation of this analysis and uses the matrix capabilities and contouring functions of MATLAB.     

基于三角形不规则网模型的快速体素化方法

为了改善在大数据量时体素化效率不高的缺点,针对三角形不规则网（TIN）模型的三角网特性,提出了一种快速简单的体素化算法。首先通过细划三角面片,将面体素化转换为简单的点体素化生成体表面模型,然后利用深度缓存原理快速寻找初始种子体素进行体内填充。实验结果表明,对于精细复杂的大规模TIN模型,算法能确实有效地生成逼近原模型的26-连通的体素模型,且具有高效的时间效率。     

基于SURF描述子的遥感影像配准

针对多源遥感影像的配准问题,提出一种基于SURF描述子的匹配算法,该算法具有稳健及高精度特性,采用SURF匹配算法得到同名点,利用一次多项式、Forstner算子和最小二乘原理由粗及精地剔除残差较大的同名点,利用提取的密集同名点构建三角网,对影像进行分块精确纠正。实验结果表明,该算法能够实现多源遥感影像的高精度配准。     

Terrain Reconstruction from Contours by Skeleton Construction

Generating terrain models from contour input is still an important process. Most methods have been unsatisfactory, as they either do not preserve the form of minor ridges and valleys, or else they are poor at modeling slopes. A method is described here, based on curve extraction and generalization techniques, that is guaranteed to preserve the topological relationships between curve segments. The skeleton, or Medial Axis Transform, can be extracted from the Voronoi diagram of a well-sampled contour map and used to extract additional points that eliminate cases of flat triangles in a triangulation. Elevation estimates may be made at these points. Based on this approach it is possible to make reasonable estimates of slopes for terrain models, and to extract meaningful intermediate points for triangulated irregular networks (TINs).