空间离散点集三维建模及简化算法研究

【作者】 陈杰；

【导师】 方源敏；

【作者基本信息】 昆明理工大学 ， 地球探测与信息技术， 2012， 博士

【摘要】 在本论文中,以空间离散点集为对象,研究了三维形状的重建算法。首先从数学的角度出发,针对建模问题做出了相关的定义；然后结合空间形状自身固有的特点,从几何的角度指出了非法构造；最后进行了关于建模算法的研究。具体包括如下内容：1.从多角度研究了点集自身所具有的特征,包括坐标分布,尺度空间,Pearson积距相关系数,点集偏差和各项统计特征量等。通过对点集的研究,能够有效的掌握点集自身的特点,无论是进行聚类分析,三维建模还是点集精简等都有着重要的指导作用。实际上,结合到空间形状千变万化的特点,对点群进行聚类分群,然后单独建模,最后再进行子模型的融合是非常明确的一种建模流程。在本论文的后续研究中,涉及到了几种建模算法,每种建模算法的表达能力各有不同,在掌握点集特性的前提下,能够选择相对较优的算法完成具体的建模任务。2.在定义的基础上,研究了向量平衡点约束条件下几何式三维建模算法,该算法立足于空间点和三棱锥的位置关系：点在棱锥内部、点在棱锥侧面上、点在棱锥外部和共棱点等情况,研究了一种粗粒度的建模算法。虽然本算法对空间形状的表达能力有限,但通过反求三维激光扫描仪的站心坐标,对单站激光点云和呈球形分布的点云仍有着较好的表达效果。本算法可作为层次化建模的基石。3.对于给定的输入点集,在自然顺序下建模面临着一系列的问题。在综合分析前述算法的基础上,针对给定点集进行建模的过程中面临着对面片格网进行优化的问题,可划分为建模前优化,建模中优化和建模后优化三种。其中,建模中优化和建模后优化是针对基本面片而言的。为了能够有效的衡量面片的质量,提出了面片正则度的概念。建模前优化实际上是对点集进行排序的问题。同时,为了能够从既有点集中快速检索和查询满足特定区域条件的点集,在分析了“暴力”算法时滞性的基础上引入了k-d树来替代执行相同的任务。以欧拉定理为出发点,推导出了最近邻平均邻居数理论为后续基于潜在连接点集的构模算法服务。4.点集中的点均采样自空间对象表面。立足于“距离较近的点”相对“距离较远的点”间存在拓扑连接的可能性要大,研究了基于潜在连接点集的构模算法。理论上,实变函数和泛函分析中的相关理论为该采样子集进行三维重建提供了理论上的指导。在理论的基础上,研究了三种空间近邻：数学近邻、空间定向近邻和自然近邻,并讨论了各自具有的优缺点,进而在此基础上研究了各自潜在连接点集的建立方法。在近邻的基础上研究了一种表面拓扑推进的三维建模算法。结合空间对象点云自身的分布特性,本算法对空间孔洞等这样的一般化概念有了一定的表达能力。5.从积分几何的角度出发,研究了给定点集凸集的性质,并在此基础上实现了一种空间凸壳的构造算法。在空间凸壳中,面积越大的面和边长越长的边所在的面对原始模型细节忽略的可能性越大。但是,面积最大的面和边长最长的边之间存在着潜在的矛盾。研究了一种协调机制来解决这种矛盾,最后在此基础上实现了一种以空间凸包为核心,点集中剩余的点为约束,进行空间收缩来建立初始格网和在局部投影面上投影来实现对空间对象的建模。该算法对空间实体的表达能力较强,而对空间孔洞的表达则是其瓶颈。6.在研究了前述几种建模算法后,需要对构成空间形状更为一般化的“孔洞”进行研究。除了在理论上阐述了相关的性质外,从二维平面的孔洞出发,研究了相应的性质,并结合VORONOI图研究了一种二维平面带孔洞对象的建模算法；然后将该二维的概念扩展到三维空间中,实现了一种三维空间中带孔洞的更一般化对象的建模算法,最终的实验证明了本算法的有效性和其较强的建模能力。7.随着数据采集技术的不断发展,针对空间目标物进行采样获取到的表面数据的精细程度越来越高。高密度的数据为高精度的虚拟仿真现实世界提供了可能,但是针对其进行建模,处理和分析等所带来的计算开销增加了对计算设备性能的依赖。构成模型的点集中的点数通常是巨大的,为了能够便于后续的空间分析等,需要对构成模型的格网进行简化操作。以针对空间点云进行建模而形成的空间格网为研究对象,研究了在参数控制下的并行简化算法。主要步骤包括：第一,根据空间网格中各点的拓扑关系,建立相应的K-邻接表；第二,计算相互独立点集；第三,以邻接表中的表头元素为中心,对与其相邻的点计算投影平面,并在该平面上完成K值的计算；第四,将原始模型变换到K值空间,研究对象在K值空间的分布特征；第五,以K值为对象,根据给定的控制参数对相互独立点集中的点进行并行简化处理,迭代进行直到满足特定的条件；最后,用构成空间形体的多个格网进行了简化实验。实验证明,本算法能够有效的解决空间模型的简化问题,同时也能够在参数的控制下使简化后模型的失真程度在控制范围之内。本算法能够充分利用当今的并行计算单元如GPU等。更多还原

【Abstract】 Taken the spatial unorganized points as the research object, a set of three dimensional shape reconstruction algorithms are studied in this paper. From a view of the mathmatics, related definitions are made towards the modelling problems. Then, the illegal constructions are pointed out based on the geometric features of the spatial object’s shape. The specific research content includes:1. The features of a given spatial unorganized points set are studied from several different aspects such as the coordinate distribution, scale space, Pearson product-moment correlation coefficient, the deviation of the points and point of view of the statistics. By doing this, the features of points can be quantitated so as to help cluster analysising, three dimensional modelling, model simplification, etc. In fact, the spatial shape is usually complex in sense; it cannot be built through a general algorithm. It’s easy to find that splitted the points to a series of child points set, bulit models separately and then fusion them together is an effective process. There are several modelling algorithms are studied in the paper, each of them has the different ability in expressing the spatial object. Based on these statistical values, appropriate algorithm can be selected to build the model.2. A coarse algorithm is implemented based on the relationship between point and the existed facet under the rules of the outside normal direction and the optimize principle that the minimum angle is maximized. There are four relationships between the point which is waiting for inserting and the existed facets in facet list:point in the pyramid internal, point on the side facet, external point and collinear point. Although the expression ablity of the algorithm is limited, it can be effectively used in point cloud of single station and spherical point cloud by calculating the center coordinates of the3D laser scanner as the virtual center. This algorithm also can be used as the cornerstone in the process of hierarchical modeling.3. There are many problems of shape reconstruction in a random order of inserting points. An operation of optimization to the mesh facets can be introduced. According to the optimization moment, it can be partitioned into three phases:before modelling, modelling and modelling finished. Optimization in modelling and after can be seen as the level of local reconstruction among the basic meshes; the optimization before modelling actually is a sorting process to the input points. In order to measure the quality of the model, a variable which is used to describe the regular degree of the basic facet is introduced. The time delay is also another serious problem which is obviousily occured in point quering opreation without optimization. In order to improve the query efficiency the k-d tree is introduced. From the Euler’s theorem, the nearest neighbor average number theory is studied for the follow-up using of the shape reconstruction algorithm based on the potential connection points set.4. Points are sampled from the surface of objects. Based on the principle that the point is closer together is possibily to be connectted topology together then the point is far way from each other, a modelling algorithm is studied. Theoretically, a support of reconstruction to the sampled points is provided from the view of the real varialble theory and functional analysis. There are three types of close neighbors:mathmatics neighbors, spatial orientation neighbors and natural neighbors. The advantages and disadvantages are studied respectively; the algorithm of building potential connection points set is also studied. A modelling algorithm with the potential connection points set is implemented based on the priciple of the neighbors. This algorithm has a stronger ability then the algorithm studied above.5. Convex hull is an important structure. The properties are studied from the point of view of the integral geometry, and a spatial convex hull construction algorithm is implemented. In convex hull, the details can easily be ignored the greater the area of the face and the side length of the longer face in the original object. There are potential conflicts between the largest surface and the side length of the longest side. A coordination mechanism is introduced to resolve this contradiction. An algorithm is implemented that the convex hull is treated as the core and other points are seen as the constraint. The initial grid model is constructed by contracting the space until meet the quit condition. The excess points are projected to its nearest plane, and then constructed the shape on the local projection plane with the DELAUNAY rule. The algorithm has a greater ability to express the space entity, but it can not be used effectively to the objects with holes.6. The hole is most a common element in spatial objects. Followed the aforementioned several reconstruction algorithms, it is necessarily needed to deeply study the features of the "holes" for building more general shapes. From the holes of the two dimensional plane, a two dimensional complex shape reconstruction is studied combined with the Voronoi diagram. Extend the concepts to the three dimensional space, an algorithm is studied in order to express the more common objects with holes. The ultimate experiments prove that the algorithm can be effectively used in objects with holes.7. With the rapid development of data acquisition technology, the precision of point cloud of target object becoming more and more sophisticated. It’s possible to build a high accuracy virtual simulation of the real world with the high-density data, but for its modelling and analyzing, the time-consuming is also growing. The amount of the model’s vertices is usually huger and an operation of simplification is necessarily needed. The spatial mesh model built through point cloud is treated as the studied object, and a parallel algorithm of simplification under the control of the parameter is studied. The steps are as follows:first, the K-adjacency table is established according to the topology of spatial mesh points; second, the independent set of points is calculated; third, the header element in each item of K-adjacency is taken as the center point, the projection plane is calculated with its neighbour points, then the K value is calculated; forth, the original model is transformed into the K value space, and the feature distribution of the model is studied; fifth, the model is simplified with the K value compared with the input parameter, loops until meet the condition; finally, the experiment is carried on series of spatial meshes. It’s proved that the algorithm not only can simplify the model effectively, but also the degree of distortion is also under the control. This algorithm can take full use of the modern parallel chips such as GPU.更多还原