一种单站地面激光扫描点云的构网方法转让专利
申请号 : CN200810047480.1
文献号 : CN101266694B
文献日 : 2010-06-09
发明人 : 黄先锋 , 张帆
申请人 : 武汉大学
摘要 :
本发明涉及单站地面激光扫描点云的构网方法，包括以下步骤：定义投影球面，将单站激光扫描点云投影到投影球面；构建初始三角网；将点云投影后得到的数据点依次插入初始三角网，所述插入方式包括三个步骤，搜索包含待插入数据点的三角形；局部重构三角网，即在搜索到待插入数据点所在的三角形后，连接该点与该三角形的三边形成三个新的三角形；对局部重构得到的三角网进行球面LOP局部优化；删除构建初始三角网的6个交点，得到投影点球面Delaunay三角网；将投影点球面Delaunay三角网中的数据点反投影到原始位置，得到单站激光扫描点云的目标三角网。本发明提供的技术方案在逆向工程技术领域具有重大意义，能够大幅提高地面激光扫描技术进行对象表面重建的效率。
权利要求 :
1.一种单站地面激光扫描点云的构网方法，其特征在于：采用球面投影方式实现单站激光扫描点云的构网，具体包括以下步骤，
步骤1，定义投影球面，将单站激光扫描点云以中心投影方式投影到投影球面，所述投影球面是以激光发射中心点为球心的球面，球面直径根据被测物与激光发射中心点的距离设定；
步骤2，构建初始三角网，所述初始三角网是采用三维坐标系的坐标轴与投影球面的6个交点构成的一个封闭的球面Delaunay三角网；
步骤3，将点云投影后得到的每个数据点依次插入初始三角网，所述插入方式包括以下三个步骤，
步骤3.1，搜索包含待插入数据点的三角形；
步骤3.2，局部重构三角网，即在步骤3.1搜索到待插入数据点所在的三角形后，删除该三角形，并连接该点与该三角形的三边，形成三个新的三角形；
步骤3.3，对局部重构得到的三角网进行球面LOP局部优化；
步骤4，删除构建初始三角网的6个交点，对三角网进行局部重构并进行球面LOP局部优化，得到投影点球面Delaunay三角网；
步骤5，将投影点球面Delaunay三角网中的数据点反投影到原始位置，得到单站激光扫描点云的目标三角网。
2.根据权利要求1所述的构网方法，其特征在于：在执行步骤3.1中采用球面有向搜索策略，即以任意三角形为起点判断数据点与该三角形三条有向边的关系，如果该点在某边的负方向上，则以包含该边的邻接三角形为起点继续搜索，直到搜索到包含该点的三角形为止。
3.根据权利要求2所述的构网方法，其特征在于：判断数据点与三角形中有向边的关系利用如下公式，
通过V的符号判断点α(Xα，Yα，Zα)与球面线段ab的位置关系，其中球面线段ab的端点坐标轴位置为(Xa，Ya，Za)和(Xb，Yb，Zb)。
4.根据权利要求1或2或3所述的构网方法，其特征在于：所述球面LOP局部优化利用如下公式，
通过W的符号判断点β(Xβ，Yβ，Zβ)与三角形Δcde的位置关系，其中Δcde的各端点坐标轴位置为(Xc，Yc，Zc)和(Xd，Yd，Zd)、(Xe，Ye，Ze)。
说明书 :
技术领域
本发明属于逆向工程技术领域，特别涉及利用地面激光扫描技术进行对象表面重建时，针对单站地面激光扫描点云的构网方法。
背景技术
地面激光扫描系统采用非接触主动测量方式直接获取高精度三维数据，具有扫描速度快、实时性强、精度高、主动性强、全数字特征等特点，是一种高效的数据获取模式，在逆向工程技术等领域有着广泛的应用。地面激光扫描仪内部，通过两个同步反射镜快速而有序地旋转，将激光脉冲发射体发出的窄束激光脉冲依次扫过被测区域，测量每个激光脉冲从发出经被测物表面再返回仪器所经过的时间(或者相位差)来计算距离，同时扫描控制模块控制和测量每个脉冲激光的角度，最后计算出激光点在被测物体上的3维坐标。这些激光扫描点即为对象表面的采样点，一般数量巨大，被总称为“点云”。
实际应用中由于处理的需要，例如：可视化、数据简化等，通常需要对离散点进行三角化构成三角网。三维离散点的三角网构建算法种类繁多，可分为直接法和间接法两大类。
直接法是直接在三维空间中利用点与点之间的关系对点集构网，主要包括雕刻算法，距离函数算法和表面生长法等，此类方法的优点是用真三维TIN较真实的描述对象的表面，但其最大的问题就是在点密度不均匀或存在噪声的情况下，难以判断点与点之间的真正邻接关系，以至于容易出现表面空洞、面片重叠、法向不一致等构网错误，此外，直接法由于涉及到三维空间分析等，在数据量大的情况下会占用较多的系统资源，算法效率较低。
间接法主要指映射法，该类方法算法将局部的邻近点投影到切平面上进行二维三角化，然后拼接成整体的三维表面模型，该类方法把复杂的三维问题简化为二维问题，具有较高的效率，但是其结果依赖于K邻域大小的选取，而且将三维点集平行投影到平面上也容易导致点与点之间的邻接关系判断错误。
实际应用中由于处理的需要，例如：可视化、数据简化等，通常需要对离散点进行三角化构成三角网。三维离散点的三角网构建算法种类繁多，可分为直接法和间接法两大类。
直接法是直接在三维空间中利用点与点之间的关系对点集构网，主要包括雕刻算法，距离函数算法和表面生长法等，此类方法的优点是用真三维TIN较真实的描述对象的表面，但其最大的问题就是在点密度不均匀或存在噪声的情况下，难以判断点与点之间的真正邻接关系，以至于容易出现表面空洞、面片重叠、法向不一致等构网错误，此外，直接法由于涉及到三维空间分析等，在数据量大的情况下会占用较多的系统资源，算法效率较低。
间接法主要指映射法，该类方法算法将局部的邻近点投影到切平面上进行二维三角化，然后拼接成整体的三维表面模型，该类方法把复杂的三维问题简化为二维问题，具有较高的效率，但是其结果依赖于K邻域大小的选取，而且将三维点集平行投影到平面上也容易导致点与点之间的邻接关系判断错误。
发明内容
本发明目的在于提供一种新的单站地面激光扫描点云的构网方法，能够正确判断点之间的邻接关系。
本发明的技术方案包括以下步骤：
步骤1，定义投影球面，将单站激光扫描点云以中心投影方式投影到投影球面，所述投影球面是以激光发射中心点为球心的球面；
步骤2，构建初始三角网，所述初始三角网是采用三维坐标系的坐标轴与投影球面的6个交点构成的一个封闭的球面Delaunay三角网；
步骤3，将点云投影后得到的每个数据点依次插入初始三角网，所述插入方式包括以下三个步骤，
步骤3.1，搜索包含待插入数据点的三角形；
步骤3.2，局部重构三角网，即在步骤3.1搜索到待插入数据点所在的三角形后，删除该三角形，并连接该点与该三角形的三边，形成三个新的三角形；
步骤3.3，对局部重构得到的三角网进行球面LOP局部优化；
步骤4，删除构建初始三角网的6个交点，对三角网进行局部重构并进行球面LOP局部优化，得到投影点球面Delaunay三角网；
步骤5，将投影点球面Delaunay三角网中的数据点反投影到原始位置，得到单站激光扫描点云的目标三角网。
而且，在执行步骤3.1中采用球面有向搜索策略，即以任意三角形为起点判断数据点与该三角形三条有向边的关系，如果该点在某边的负方向上，则以包含该边的邻接三角形为起点继续搜索，直到搜索到包含该点的三角形为止。
而且，判断数据点与三角形中有向边的关系利用如下公式，
通过V的符号判断点α(Xα，Yα，Zα)与球面线段ab的位置关系。
而且，所述球面LOP局部优化利用如下公式，
通过W的符号判断点β(Xβ，Yβ，Zβ)与三角形Δcde的位置关系。
本发明创造性地提出采用球面投影代替平行投影，克服了平行投影时必然会产生点的重叠、遮挡等问题，构建三角网的结果能够正确反映扫描点云中点与点之间的关系。本发明还提出了球面有向搜索策略和新的球面LOP局部优化方法，解决了构建三角网过程中大数据量的计算效率问题。
本发明的技术方案包括以下步骤：
步骤1，定义投影球面，将单站激光扫描点云以中心投影方式投影到投影球面，所述投影球面是以激光发射中心点为球心的球面；
步骤2，构建初始三角网，所述初始三角网是采用三维坐标系的坐标轴与投影球面的6个交点构成的一个封闭的球面Delaunay三角网；
步骤3，将点云投影后得到的每个数据点依次插入初始三角网，所述插入方式包括以下三个步骤，
步骤3.1，搜索包含待插入数据点的三角形；
步骤3.2，局部重构三角网，即在步骤3.1搜索到待插入数据点所在的三角形后，删除该三角形，并连接该点与该三角形的三边，形成三个新的三角形；
步骤3.3，对局部重构得到的三角网进行球面LOP局部优化；
步骤4，删除构建初始三角网的6个交点，对三角网进行局部重构并进行球面LOP局部优化，得到投影点球面Delaunay三角网；
步骤5，将投影点球面Delaunay三角网中的数据点反投影到原始位置，得到单站激光扫描点云的目标三角网。
而且，在执行步骤3.1中采用球面有向搜索策略，即以任意三角形为起点判断数据点与该三角形三条有向边的关系，如果该点在某边的负方向上，则以包含该边的邻接三角形为起点继续搜索，直到搜索到包含该点的三角形为止。
而且，判断数据点与三角形中有向边的关系利用如下公式，
通过V的符号判断点α(Xα，Yα，Zα)与球面线段ab的位置关系。
而且，所述球面LOP局部优化利用如下公式，
通过W的符号判断点β(Xβ，Yβ，Zβ)与三角形Δcde的位置关系。
本发明创造性地提出采用球面投影代替平行投影，克服了平行投影时必然会产生点的重叠、遮挡等问题，构建三角网的结果能够正确反映扫描点云中点与点之间的关系。本发明还提出了球面有向搜索策略和新的球面LOP局部优化方法，解决了构建三角网过程中大数据量的计算效率问题。
附图说明
图1本发明投影球面和初始三角网示意图；
图2本发明实施例的球面有向搜索示意图；
图3本发明球面LOP局部优化示意图；
图4本发明实施例的流程图；
图5本发明实施例的数据结构示意图。
图6本发明与现有技术的构网效率对比图。
图2本发明实施例的球面有向搜索示意图；
图3本发明球面LOP局部优化示意图；
图4本发明实施例的流程图；
图5本发明实施例的数据结构示意图。
图6本发明与现有技术的构网效率对比图。
具体实施方式
本发明的技术方案包括以下步骤：
步骤1，定义投影球面，将单站激光扫描点云以中心投影方式投影到投影球面，所述投影球面是以激光发射中心点为球心的球面；
地面激光扫描仪扫描方式是底座固定，激光脉冲发射方向随着扫描头在垂直方向上下摆动，同时在水平方向上缓慢转动，通过记录激光脉冲的方向和经目标表面发射后返回的时间(或相位差)来计算目标表面三维坐标。当扫描视场较大时，如果将全部扫描点直接通过平行投影的方式投影到一个平面上，必然会产生点的重叠、遮挡等问题，构出的三角网无法正确反映对象表面的情况和表面点之间的邻接关系。但是，扫描点可认为是由激光发射中心出发的射线与目标表面的交点，所以，点云中所有扫描点对激光发射中心点都是可视的，如果将扫描点通过中心投影的方式投影到以激光发射中心点为球心的球面上则可避免上述错误，能解决需要解决的技术问题。
本实施例定义的投影球面可参见附图1中以O点为球心的球面，激光发射中心点就出于O点。球面直径则可根据被测物与激光发射中心点的距离设定。
步骤2，构建初始三角网，所述初始三角网是采用三维坐标系的坐标轴与投影球面的6个交点构成的一个封闭的球面Delaunay三角网；
本实施例构建的初始三角网可参见附图1，三维坐标系的坐标轴XYZ与投影球面的6个交点ABCDEF构成的一个封闭的球面Delaunay三角网，这个初始三角网包括8个三角形ΔABE、ΔADE、ΔCDE、ΔBCE、ΔADF、ΔCDF、ΔBCF、ΔABF。
步骤3，将点云投影后得到的每个数据点依次插入初始三角网，所述插入方式包括以下三个步骤3.1～3.3。每个数据点插入时都执行这三个步骤，因此在初始三角网的基础上，三角网具体构成被不断改变。
步骤3.1，搜索包含待插入数据点的三角形；
本发明提供了进一步技术方案，以提高搜索效率：在执行步骤3.1中采用球面有向搜索策略，即以任意三角形为起点判断数据点与该三角形三条有向边的关系，如果该点在某边的负方向上，则以包含该边的邻接三角形为起点继续搜索，直到搜索到包含该点的三角形为止。
更进一步的技术方案是：判断数据点与三角形中有向边的关系利用如下公式，
按照空间坐标轴标注的一般原则，点α的坐标轴位置标注为(Xα，Yα，Zα)，球面线段ab的端点坐标轴位置为(Xa，Ya，Za)和(Yb，Yb，Zb)，通过公式计算结果V的符号判断点α(Xα，Ya，Zα)与球面线段ab的位置关系。这种方案简单巧妙，用于判断位置关系具有很高效率。
参见附图2的实施例，寻找包括P点的三角形，从ΔKLJ开始搜索，将P点坐标和球面线段KJ带入公式(1)，根据V值符号判断出P点在KJ负方向，因此继续以同样的方法搜索到ΔKJM、ΔJGM、ΔMGI、ΔIGH，直到判断出P点处于ΔIGH内。
步骤3.2，局部重构三角网，即在步骤3.1搜索到待插入数据点所在的三角形后，删除该三角形，并连接该点与该三角形的三边，形成三个新的三角形；
以附图2的实施例来看，就是构成ΔPIG、ΔPGH、ΔPHI，原来的ΔIGH删去。当然，在几何意义上，I、G、H三点仍够成三角形，但在三角构网中不予考虑。
步骤3.3，对局部重构得到的三角网进行球面LOP局部优化；
上一步骤3.2中为三角网中加入了三个新的三角形，这些三角形与其相邻三角形构成的三角网不一定符合球面Delaunay准则。所谓球面Delaunay准则为：以三角网内任何一个三角形的外接圆为底的较小球冠上不包含第四点，若出现四点共圆的情况，则连接该凸四边形的较短的对角线形成2个新三角形。因此需要进行球面LOP优化，以便实现插入数据点后仍满足球面Delaunay准则。
现有技术中已有球面LOP局部优化解决方案，为了便于实施，本发明提供了一种新的球面LOP局部优化方案，所述球面LOP局部优化利用如下公式，
按照空间坐标轴标注的一般原则，点β的坐标轴位置为(Xβ，Yβ，Zβ)，Δcde的各端点坐标轴位置为(Xc，Yc，Zc)和(Xd，Yd，Zd)、(Xe，Ye，Ze)，通过公式计算结果W的符号判断点β(Xβ，Yβ，Zβ)与三角形Δcde的位置关系。
参见附图3实施例，点T插入三角网后，与相邻ΔSQR之间的位置关系通过代入公式(2)进行判断。在附图3的(a)部分，由于点T处在ΔSQR的正方向上，而圆心O处在ΔSQR的负方向上，因此，ΔSQR和ΔSTQ不符合球面Delaunay准则；(b)部分展现了优化后的形态，交换了四边形STQR的对角线后得到了ΔQRT和ΔSTR，点Q与圆心O都位于ΔSTR的负方向，同时，点S与圆心O也都位于ΔQRT的负方向，因此，这两个三角形符合球面Delaunay准则。
步骤4，删除构建初始三角网的6个交点，对三角网进行局部重构并进行球面LOP局部优化，得到投影点球面Delaunay三角网；
执行完步骤3，所有数据点插入三角网后，将步骤2中构建初始三角网的6个交点ABCDEF从当前三角网中删除，对删除后留下的空洞局部重构三角网并进行球面LOP局部优化，局部优化方法与步骤3.3相同。此时的三角网是能够完整反映数据点位置关系的成果，本发明称之为投影点球面Delaunay三角网。
步骤5，将投影点球面Delaunay三角网中的数据点反投影到原始位置，得到单站激光扫描点云的目标三角网。由于投影点球面Delaunay三角网中的数据点来自扫描点云的投影，因此在最后进行反投影变换，得到反映待测物真实位置信息的目标三角网。
为了便于实施，本发明提供了实施例的具体工作流程，可供实现自动化处理。参见附图4：首先单站激光扫描点云；然后定义投影球面并将扫描点投影到该球面；构建初始三角网；将投影到球面的数据点逐点插入三角网，插入方法为球面有向搜索插入点所在的三角形，在插入的数据点与所包含的三角形处局部重构三角网，球面LOP局部优化三角网；得到插入数据点后的三角网；判断是否处理完所有插入的数据点，以便通过判断循环执行插入直到满足条件；删除初始三角网并局部修补，即删除6个交点；得到投影点球面Delaunay三角网；保持球面构网关系将插入的数据点反投影到原始位置，通过反投影得到的点构建三角网结果，即满足对象表面重建需要的目标三角网。
为了便于实施，本发明还提供了实施例的数据结构，参见附图5：在球面Delaunay三角网数据结构SD-TIN中包含：顶点数组Vertex Array，用于保存全部点；三角形数组Triangle Array，用于保存全部三角形。描述顶点的数据结构标记为VERTEX m：，m为顶点序号(m＝1，2，3，4，…)，其中包含有：扫描点原始坐标X、Y、Z，扫描点投影到球面后的数据点坐标ProjectedX、ProjectedY、ProjectedZ。描述三角形的数据结构标记为TRIANGLE n：，n为三角形的序号(n＝1，2，3，4，…)，其中包含有：第i个顶点Vertex i，i为顶点序号(i＝1，2，3)；第j个邻接三角形Neighbor j，j为邻接三角形序号(j＝1，2，3)。
与现有技术相比，本发明的构网效率与效果更佳。附图5中，展示了将本发明与目前最普及的逆向工程商业软件Geomagic Studio 9的构网效果与效率进行对比的结果。图中横坐标为扫描点数量，单位为万点；纵坐标为构网时间，单位为秒。从数据中可知，本发明的构网效率要优于Geomagic Studio 9的效率，而且当扫描点数量大于400万时，Geomagic Studio 9就会因为内存不足而中断，而本发明可以有效的对数千万的数据点进行构网。而且，在点密度不均匀或曲率较大时，用Geomagic Studio 9构出的三角网会出现空洞，而本发明的方法可以避免此类问题。
步骤1，定义投影球面，将单站激光扫描点云以中心投影方式投影到投影球面，所述投影球面是以激光发射中心点为球心的球面；
地面激光扫描仪扫描方式是底座固定，激光脉冲发射方向随着扫描头在垂直方向上下摆动，同时在水平方向上缓慢转动，通过记录激光脉冲的方向和经目标表面发射后返回的时间(或相位差)来计算目标表面三维坐标。当扫描视场较大时，如果将全部扫描点直接通过平行投影的方式投影到一个平面上，必然会产生点的重叠、遮挡等问题，构出的三角网无法正确反映对象表面的情况和表面点之间的邻接关系。但是，扫描点可认为是由激光发射中心出发的射线与目标表面的交点，所以，点云中所有扫描点对激光发射中心点都是可视的，如果将扫描点通过中心投影的方式投影到以激光发射中心点为球心的球面上则可避免上述错误，能解决需要解决的技术问题。
本实施例定义的投影球面可参见附图1中以O点为球心的球面，激光发射中心点就出于O点。球面直径则可根据被测物与激光发射中心点的距离设定。
步骤2，构建初始三角网，所述初始三角网是采用三维坐标系的坐标轴与投影球面的6个交点构成的一个封闭的球面Delaunay三角网；
本实施例构建的初始三角网可参见附图1，三维坐标系的坐标轴XYZ与投影球面的6个交点ABCDEF构成的一个封闭的球面Delaunay三角网，这个初始三角网包括8个三角形ΔABE、ΔADE、ΔCDE、ΔBCE、ΔADF、ΔCDF、ΔBCF、ΔABF。
步骤3，将点云投影后得到的每个数据点依次插入初始三角网，所述插入方式包括以下三个步骤3.1～3.3。每个数据点插入时都执行这三个步骤，因此在初始三角网的基础上，三角网具体构成被不断改变。
步骤3.1，搜索包含待插入数据点的三角形；
本发明提供了进一步技术方案，以提高搜索效率：在执行步骤3.1中采用球面有向搜索策略，即以任意三角形为起点判断数据点与该三角形三条有向边的关系，如果该点在某边的负方向上，则以包含该边的邻接三角形为起点继续搜索，直到搜索到包含该点的三角形为止。
更进一步的技术方案是：判断数据点与三角形中有向边的关系利用如下公式，
按照空间坐标轴标注的一般原则，点α的坐标轴位置标注为(Xα，Yα，Zα)，球面线段ab的端点坐标轴位置为(Xa，Ya，Za)和(Yb，Yb，Zb)，通过公式计算结果V的符号判断点α(Xα，Ya，Zα)与球面线段ab的位置关系。这种方案简单巧妙，用于判断位置关系具有很高效率。
参见附图2的实施例，寻找包括P点的三角形，从ΔKLJ开始搜索，将P点坐标和球面线段KJ带入公式(1)，根据V值符号判断出P点在KJ负方向，因此继续以同样的方法搜索到ΔKJM、ΔJGM、ΔMGI、ΔIGH，直到判断出P点处于ΔIGH内。
步骤3.2，局部重构三角网，即在步骤3.1搜索到待插入数据点所在的三角形后，删除该三角形，并连接该点与该三角形的三边，形成三个新的三角形；
以附图2的实施例来看，就是构成ΔPIG、ΔPGH、ΔPHI，原来的ΔIGH删去。当然，在几何意义上，I、G、H三点仍够成三角形，但在三角构网中不予考虑。
步骤3.3，对局部重构得到的三角网进行球面LOP局部优化；
上一步骤3.2中为三角网中加入了三个新的三角形，这些三角形与其相邻三角形构成的三角网不一定符合球面Delaunay准则。所谓球面Delaunay准则为：以三角网内任何一个三角形的外接圆为底的较小球冠上不包含第四点，若出现四点共圆的情况，则连接该凸四边形的较短的对角线形成2个新三角形。因此需要进行球面LOP优化，以便实现插入数据点后仍满足球面Delaunay准则。
现有技术中已有球面LOP局部优化解决方案，为了便于实施，本发明提供了一种新的球面LOP局部优化方案，所述球面LOP局部优化利用如下公式，
按照空间坐标轴标注的一般原则，点β的坐标轴位置为(Xβ，Yβ，Zβ)，Δcde的各端点坐标轴位置为(Xc，Yc，Zc)和(Xd，Yd，Zd)、(Xe，Ye，Ze)，通过公式计算结果W的符号判断点β(Xβ，Yβ，Zβ)与三角形Δcde的位置关系。
参见附图3实施例，点T插入三角网后，与相邻ΔSQR之间的位置关系通过代入公式(2)进行判断。在附图3的(a)部分，由于点T处在ΔSQR的正方向上，而圆心O处在ΔSQR的负方向上，因此，ΔSQR和ΔSTQ不符合球面Delaunay准则；(b)部分展现了优化后的形态，交换了四边形STQR的对角线后得到了ΔQRT和ΔSTR，点Q与圆心O都位于ΔSTR的负方向，同时，点S与圆心O也都位于ΔQRT的负方向，因此，这两个三角形符合球面Delaunay准则。
步骤4，删除构建初始三角网的6个交点，对三角网进行局部重构并进行球面LOP局部优化，得到投影点球面Delaunay三角网；
执行完步骤3，所有数据点插入三角网后，将步骤2中构建初始三角网的6个交点ABCDEF从当前三角网中删除，对删除后留下的空洞局部重构三角网并进行球面LOP局部优化，局部优化方法与步骤3.3相同。此时的三角网是能够完整反映数据点位置关系的成果，本发明称之为投影点球面Delaunay三角网。
步骤5，将投影点球面Delaunay三角网中的数据点反投影到原始位置，得到单站激光扫描点云的目标三角网。由于投影点球面Delaunay三角网中的数据点来自扫描点云的投影，因此在最后进行反投影变换，得到反映待测物真实位置信息的目标三角网。
为了便于实施，本发明提供了实施例的具体工作流程，可供实现自动化处理。参见附图4：首先单站激光扫描点云；然后定义投影球面并将扫描点投影到该球面；构建初始三角网；将投影到球面的数据点逐点插入三角网，插入方法为球面有向搜索插入点所在的三角形，在插入的数据点与所包含的三角形处局部重构三角网，球面LOP局部优化三角网；得到插入数据点后的三角网；判断是否处理完所有插入的数据点，以便通过判断循环执行插入直到满足条件；删除初始三角网并局部修补，即删除6个交点；得到投影点球面Delaunay三角网；保持球面构网关系将插入的数据点反投影到原始位置，通过反投影得到的点构建三角网结果，即满足对象表面重建需要的目标三角网。
为了便于实施，本发明还提供了实施例的数据结构，参见附图5：在球面Delaunay三角网数据结构SD-TIN中包含：顶点数组Vertex Array，用于保存全部点；三角形数组Triangle Array，用于保存全部三角形。描述顶点的数据结构标记为VERTEX m：，m为顶点序号(m＝1，2，3，4，…)，其中包含有：扫描点原始坐标X、Y、Z，扫描点投影到球面后的数据点坐标ProjectedX、ProjectedY、ProjectedZ。描述三角形的数据结构标记为TRIANGLE n：，n为三角形的序号(n＝1，2，3，4，…)，其中包含有：第i个顶点Vertex i，i为顶点序号(i＝1，2，3)；第j个邻接三角形Neighbor j，j为邻接三角形序号(j＝1，2，3)。
与现有技术相比，本发明的构网效率与效果更佳。附图5中，展示了将本发明与目前最普及的逆向工程商业软件Geomagic Studio 9的构网效果与效率进行对比的结果。图中横坐标为扫描点数量，单位为万点；纵坐标为构网时间，单位为秒。从数据中可知，本发明的构网效率要优于Geomagic Studio 9的效率，而且当扫描点数量大于400万时，Geomagic Studio 9就会因为内存不足而中断，而本发明可以有效的对数千万的数据点进行构网。而且，在点密度不均匀或曲率较大时，用Geomagic Studio 9构出的三角网会出现空洞，而本发明的方法可以避免此类问题。