逆向工程中NURBS曲面与直线交点快速计算

给出了一个能够方便地判断NURBS曲面片与空间直线的交点个数,并且超线性收敛的快速迭代算法。计算Krawczyk算子判断给定的NURBS曲面片和空间直线有无交点和有几个交点。再使用拟牛顿迭代法求出NURBS曲面片和空间直线上的交点。该算法在用点云数据检测曲面重构的误差时具有快速、准确的特点。     

Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods

A novel and efficient quasi-Monte Carlo method for estimating the surface area of digitized 3D objects in the volumetric representation is presented. It operates directly on the original digitized objects without any surface reconstruction procedure. Based on the Cauchy-Crofton formula from integral geometry, the method estimates the surface area of a volumetric object by counting the number of intersection points between the object's boundary surface and a set of uniformly distributed lines generated with low-discrepancy sequences. Using a clustering technique, we also propose an effective algorithm for computing the intersection of a line with the boundary surface of volumetric objects. A number of digitized objects are used to evaluate the performance of the new method for surface area measurement.     

Direct boolean intersection between acquired and designed geometry

In this paper, a new shape modeling approach that can enable direct Boolean intersection between acquired and designed geometry without model conversion is presented. At its core is a new method that enables direct intersection and Boolean operations between designed geometry (objects bounded by NURBS and polygonal surfaces) and scanned geometry (objects represented by point cloud data).We use the moving least-squares (MLS) surface as the underlying surface representation for acquired point-sampled geometry. Based on the MLS surface definition, we derive closed formula for computing curvature of planar curves on the MLS surface. A set of intersection algorithms including line and MLS surface intersection, curvature-adaptive plane and MLS surface intersection, and polygonal mesh and MLS surface intersection are successively developed. Further, an algorithm for NURBS and MLS surface intersection is then developed. It first adaptively subdivides NURBS surfaces into polygonal mesh, and then intersects the mesh with the MLS surface. The intersection points are mapped to the NURBS surface through the Gauss-Newton method.Based on the above algorithms, a prototype system has been implemented. Through various examples from the system, we demonstrate that direct Boolean intersection between designed geometry and acquired geometry offers a useful and effective means for the shape modeling applications where point-cloud data is involved.     

Automatic least-squares projection of points onto point clouds with applications in reverse engineering

A novel method for projecting points onto a point cloud, possibly with noise, is presented based on the point directed projection (DP) algorithm proposed by Azariadis P., Sapidis N. [Drawing curves onto a cloud of points for point-based modelling. Computer-Aided Design 2005; 37(1): 109–22]. The new method operates directly on the point cloud without any explicit or implicit surface reconstruction procedure. The presented method uses a simple, robust, and efficient algorithm: least-squares projection (LSP), which projects points onto the point cloud in a least-squares sense without any specification of the projection vector. The main contribution of this novel method is the automatic computation of the projection vector. Furthermore, we demonstrate the effectiveness of this approach through a number of application examples including thinning a point cloud, point normal estimation, projecting curves onto a point cloud and others.     

伪点云修正增强激光雷达数据

目的 激光雷达在自动驾驶中具有重要意义,但其价格昂贵,且产生的激光线束数量仍然较少,造成采集的点云密度较稀疏。为了更好地感知周围环境,本文提出一种激光雷达数据增强算法,由双目图像生成伪点云并对伪点云进行坐标修正,进而实现激光雷达点云的稠密化处理,提高3D目标检测精度。此算法不针对特定的3D目标检测网络结构,是一种通用的点云稠密化方法。方法 首先利用双目RGB图像生成深度图像,根据先验的相机参数和深度信息计算出每个像素点在雷达坐标系下的粗略3维坐标,即伪点云。为了更好地分割地面,本文提出了循环RANSAC （random sample consensus）算法,引入了一个分离平面型非地面点云的暂存器,改进复杂场景下的地面分割效果。然后将原始点云进行地面分割后插入KDTree （k-dimensional tree）,以伪点云中的每个点为中心在KDTree中搜索若干近邻点,基于这些近邻点进行曲面重建。根据曲面重建结果,设计一种计算几何方法导出伪点云修正后的精确坐标。最后,将修正后的伪点云与原始激光雷达点云融合得到稠密化点云。结果 实验结果表明,稠密化的点云在视觉上具有较好的质量,物体具有更加完整的形状和轮廓,并且在KITTI （Karlsruhe Institute of Technology and Toyota Technological Institute）数据集上提升了3D目标检测精度。在使用该数据增强方法后,KITTI数据集下AVOD （aggregate view object detection）检测方法的AP_3D-Easy （average precision of 3D object detection on easy setting）提升了8.25%,AVOD-FPN （aggregate view object detection with feature pyramid network）检测方法的AP_BEV-Hard （average precision of bird’s eye view on hard setting）提升了7.14%。结论 本文提出的激光雷达数据增强算法,实现了点云的稠密化处理,并使3D目标检测结果更加精确。     

基于快速Delaunay三角化的散乱点曲面重建算法

针对现有三维重建算法速度较慢的问题,提出了一种基于快速Delaunay三角化的散乱数据点的三维重建算法。首先,提出一种新的平面Delaunay三角化插入点目标三角形定位算法,利用插入点的方向搜索线与三角形是否相交以及交点个数加速目标三角形定位,不用额外判断点是否在三角形内;其次,自动检测曲面漏洞,利用凸壳的边界拼接方法进行漏洞弥补。实验结果表明,本算法不仅能较好地重建出三维模型,而且有较高的效率。     

一般点模型的交互式布尔运算

提出了一个适用于一般点模型的交互式布尔运算算法,此算法由4个步骤组成．首先将点模型表示为自适应的三色八叉树,然后利用自适应八叉树结构加速内外测试．对于局部采样密度不一致的相交区域或曲率太大容易导致较大求交误差的地方,实行了自适应细分加密采样;重采样相交的部分以获得更精确的求交结果．与已有的点模型布尔运算方法相比,该算法适用于一般的实测点云数据,包括少量噪声的点模型、非均匀采样以及不同分辨率点模型之间的交互式布尔运算。     

基于特征点动态选择的三维人脸点云模型重建

针对典型的点云配准方法中伪特征点过多导致配准效率低和配准结果不精确的问题,提出一种基于特征点动态选择的三维人脸点云模型重建方法。该方法在粗配准阶段,采用动态特征矩阵求解法获取粗匹配特征变换矩阵以避免伪特征点的干扰。在精配准过程中,采用二次加权法向量垂直距离法在人脸流形表面选择更有效的特征点以减少伪特征点的数量,并采用基于特征融合与局部特征一致性的迭代最近点方法进行精配准。经过对比实验验证了算法的可行性,实验结果表明,提出算法能够实现高精度且快速的三维人脸点云模型重建,且均方根误差达到1.816 5 mm,相较于其他算法,在模型重建精度和效率方面都有所提升,具有良好的应用前景。     

利用Voronoi协方差矩阵重建隐式曲面

目的 针对含少量离群点的噪声点云,提出了一种Voronoi协方差矩阵的曲面重建方法。方法 以隐函数梯度在Voronoi协方差矩阵形成的张量场内的投影最大化为目标,构建隐函数微分方程,采用离散外微分形式求解连续微分方程,从而将曲面重建问题转化为广义特征值求解问题。在点云空间离散化过程中,附加最短边约束条件,避免了局部空间过度剖分。并引入概率测度理论定义曲面窄带,提高了算法抵抗离群点能力,通过精细剖分曲面窄带,提高了曲面重建精度。结果 实验结果表明,该算法可以抵抗噪声点和离群点的影响,可以生成不同分辨率的曲面。通过调整拟合参数,可以区分曲面的不同部分。结论 提出了一种新的隐式曲面重建方法,无需点云法向、稳健性较强,生成的三角面纵横比好。     

三维离散点采样表面基于全局优化的纹理合成算法

提出了一个直接在三维离散点采样表面上进行基于全局优化的纹理合成算法．算法首先对点模型表面进行基于协方差分析的递归式聚类削分，然后通过对各初始聚类进行优化调整和区域生长，得到更为均匀的计算单元块且使相邻单元块间具有重叠区域．基于所得到的计算单元块和样本纹理，在点模型表面上建立了一个全局的纹理合成能量方程，并采用最大期卑值算法迭代优化求解出一个全局的能量最小值．在全局优化算法中，通过加入的约束条件，进而给出了点模型颜色纹理的修复算法和流引导的可控纹理合成算法．由于点模型表面离散点元的稠密性，通过对离散点元的法向基于纹理合成结果进行相应的扰动，进一步增强了表面纹理的几何粗糙感．实验结果表明，该文的算法在点采样几何表面上有效地保持了生成的纹理结构和视觉效果的连续性和平滑性，得到了令人满意的结果。     

自适应的基于点云的CAD模型重建方法

基本的随机抽样一致性(RANSAC)算法无法根据点云模型的噪声自适应地设定分割参数,并有效判断点云数据是否被合理分割。针对该问题,提出了一种自适应的基于点云模型的计算机辅助设计(CAD)模型重建方法。该方法采用RANSAC算法从点云数据中提取基本形状体素,使用直方图法分析点到相应形状体素表面的投影距离。对分割不合理的区域,按照该点云面片的高斯噪声设置新的分割参数,再次进行形状提取。经过一定轮数的迭代,该方法可以合理提取点云模型中的细小形状体素。然后通过校准形状体素的位置和方向、根据相邻形状体素之间的交线裁剪形状体素,实现CAD模型的重建。最后,以误差分布图和直方图分析了原始点云数据中点到CAD模型表面投影距离,有70.71%的点的投影距离不超过点云模型包围盒高度的1%。实验结果表明,以点云包围盒高度的1%为尺度向实验数据中加入噪声时,该方法仍能够通过自适应设置分割参数提取出合理的细小体素。     

Meshless thin-shell simulation based on global conformal parameterization

This paper presents a new approach to the physically-based thin-shell simulation of point-sampled geometry via explicit, global conformal point-surface parameterization and meshless dynamics. The point-based global parameterization is founded upon the rigorous mathematics of Riemann surface theory and Hodge theory. The parameterization is globally conformal everywhere except for a minimum number of zero points. Within our parameterization framework, any well-sampled point surface is functionally equivalent to a manifold, enabling popular and powerful surface-based modeling and physically-based simulation tools to be readily adapted for point geometry processing and animation. In addition, we propose a meshless surface computational paradigm in which the partial differential equations (for dynamic physical simulation) can be applied and solved directly over point samples via moving least squares (MLS) shape functions defined on the global parametric domain without explicit connectivity information. The global conformal parameterization provides a common domain to facilitate accurate meshless simulation and efficient discontinuity modeling for complex branching cracks. Through our experiments on thin-shell elastic deformation and fracture simulation, we demonstrate that our integrative method is very natural, and that it has great potential to further broaden the application scope of point-sampled geometry in graphics and relevant fields.     

面向RGBD深度数据的快速点云配准方法

目的 真实物体的3维重建一直是计算机图形学、机器视觉等领域的研究热点。针对基于RGBD数据的非匀速非固定角度旋转物体的3维重建问题,提出一种利用旋转平台重建物体3维模型的配准方法。方法 首先通过Kinect采集位于旋转平台上目标物的深度数据和颜色数据,对齐融合并使用包围盒算法去除背景噪声和不需要的外部点云,获得带有颜色信息的点云数据。并使用基于标定物不同角度上的点云数据标定出旋转平台中心轴的位置,从而获得Kinect与旋转平台之间的相对关系;然后通过曲率特征对目标点云进行特征点提取并寻找与相邻点云的对应点;其中对于特征点的选取,首先针对点云中的任意一点利用kd-tree搜寻其k个邻近点,对这些点进行曲面拟合,进而计算其高斯曲率,将高斯曲率绝对值较大的n个点作为点云的特征点。n的取值由点云的点个数、点密度和复杂度决定,具体表现为能反映物体的大致轮廓或表面特征信息即可。对于对应点的选取,考虑到欧氏距离并不能较好反映点云中的点对在旋转过程中的对应关系,在实际配准中,往往会因为点云重叠或距离过远等原因找到大量错误的对应点。由于目标物在扫描过程中仅绕旋转轴进行旋转,因此采用圆弧最小距离寻找对应点可有效减少错误点对。随后,使用二分迭代寻找绕中心轴的最优旋转角度以满足点云间的匹配误差最小;最后,将任意角度获取的点云数据配准到统一的坐标系下并重建模型。结果 使用斯坦福大学点云数据库和自采集数据库分别对该方法和已有方法在算法效率和配准结果上进行对比实验,实验结果显示在拥有平均75 000个采样点的斯坦福大学点云数据库上与传统ICP算法和改进ICP算法相比,迭代次数分别平均减少86.5%、57.5%,算法运行时间分别平均减少87%、60.75%,欧氏距离误差平方和分别平均减少70%、22%;在具有平均57000个采样点的自采集点云数据库上与传统ICP算法和改进ICP算法相比,迭代次数分别平均减少94%、75%,算法运行时间分别平均减少92%、69%,欧氏距离误差平方和分别平均减少61.5%、30.6%;实验结果显示使用该方法进行点云配准效率较高且配准误差更小;和KinectFusion算法相比在纹理细节保留上也表现出较好的效果。结论 本文提出的基于旋转平台标定的点云配准算法,利用二分迭代算法能够有效降低算法复杂度。与典型ICP和改进的ICP算法的对比实验也表明了本文算法的有效性。另外,与其他方法在具有纹理的点云配准对比实验中也验证了本文配准方法的优越性。该方法仅采用单个Kinect即可实现对非匀速非固定角度旋转物体的3维建模,方便实用,适用于简单快速的3维重建应用场合。     

基于闭环理论的自由曲面测量与实时重构

寻求更优的测量方法和更精确的重构模式一直是逆向工程中的研究重点。基此,对具有自由曲面特征的产品逆向,提出一种自适应测量、实时重构和在线评价的方法。依据几何特性,测量实物外形并用高次Bézier曲线拟合,微分推演探测点及矢量,指导三坐标测量机CMM（Coordinate Measuring Machining）自适应探测完整实物点云;借助非均匀B-spline架构曲面模型,基于扫描网格和实物特征从以上重构的曲面上抽取关键检测点,在线引导CMM确定上述检测点在实物上的准确位置并评价已构曲面误差,若误差高于阀值就将检测点加入更新曲面,逐步提高直至满足几何精度,集成测→构→评→添的全闭环逆向过程,建立精确的实物数字化模型。实例验证表明,该方法可利用曲面的几何特性,让测点分布随曲面曲率变化而呈疏密变化,以获得高质量的原始数据点云,实时模型重构、在线评价并及时添加检测点修正模型,可完整表述曲面的几何信息,可使重构模型精度达微米级。     

Detail-generating geometry completion for point-sampled geometry

In this paper, we present a novel method for detail-generating geometry completion over point-sampled geometry. The main idea consists of converting the context-based geometry completion into the detail-based texture completion on the surface. According to the influence region of boundary points surrounding a hole, a smooth patch covering the hole is first constructed using radial base functions. By applying region-growing clustering to the patch, the patching units for further completion with geometry details is then produced, and using the trilateral filtering operator formulated by us, the geometry-detail texture of each sample point on the input geometry is determined. The geometry details on the smooth completed patch are finally generated by optimizing a constrained global texture energy function on the point-sampled surfaces. Experimental results demonstrate that the method can achieve efficient completed patches that not only conform with their boundaries, but also contain the plausible 3D surface details.     

Using low-discrepancy sequences and the Crofton formula to compute surface areas of geometric models

The surface area of a geometric model, like its volume, is an important integral property that needs to be evaluated frequently and accurately in practice. In this paper, we present a new quasi-Monte Carlo method using low-discrepancy sequences for computing the surface area of a 3D object. We show that the new method is more efficient than a Monte Carlo method using pseudo-random numbers. This method is based on the Cauchy-Crofton formula from integral geometry, and it computes the surface area of a 3D body B by counting the number of intersection points between the boundary surface of B and a set of straight lines in E³. Low discrepancy sequences are used to generate the set of lines in E³ to reduce the estimation errors that would be caused by using statistically uniformly distributed lines. We study and compare two different methods for generating 3D random lines, and demonstrate their validity theoretically and experimentally. Experiments suggest that the new quasi-Monte Carlo method is also more efficient than the conventional approach based on surface tessellation.     

散乱点云数据的高阶平滑隐式曲面重建

针对三维扫描或三维重建获取的散乱点云数据曲面重建问题, 提出基于拉普拉斯规则化的高阶平滑算法。首先, 计算点云数据的包围盒并离散化得到体素空间; 其次, 在体素空间根据隐式曲面的梯度和点云位置、法向信息建立目标函数, 并通过对目标函数的拉普拉斯规则化达到控制重建曲面光顺效果的目的; 再次, 根据最优化原理将重建问题转换为一个稀疏线性方程组求解问题; 最后, 通过步进立方体算法得到重建曲面的三角网格表示。定性和定量的实验结果表明, 该方法重建曲面绘制效果和精确度优于常用的Poisson方法。     

规则特征曲面点云法向估计

目的 针对特征曲面点云法矢估计不准确,点云处理时容易丢失曲面的细节特征等问题,提出基于高斯映射的特征曲面散乱点云法向估计法。方法 首先,用主成分分析法粗略地估算点云法向和特征点;其次,将特征点的各向同性邻域映射到高斯球,用K均值聚类法对高斯球上的数据分割成多个子集,以最优子集对应的各向异性邻域拟合曲面来精确估算特征点的法向量;最后,通过测试估计法向与标准法向的误差来评价估计法矢的准确性,并且将估计的法向应用到点云曲面重建中来比较特征保留效果。结果 本文方法估计的法向最小误差接近0,对噪声有较好的鲁棒性,重建的曲面能保留曲面的尖锐特征,相比于其他法向估计法,所提出的方法估计的法向更准确。结论 本文方法能够比较准确的估算尖锐特征曲面法向量,对噪声鲁棒性强,具有较高的适用性。     

Robust Segmentation of Multiple Intersecting Manifolds from Unoriented Noisy Point Clouds

We present a method for extracting complex manifolds with an arbitrary number of (self‐) intersections from unoriented point clouds containing large amounts of noise. Manifolds are formed in a three‐step process. First, small flat neighbourhoods of all possible orientations are created around all points. Next, neighbourhoods are assembled into larger quasi‐flat patches, whose overlaps give the global connectivity structure of the point cloud. Finally, curved manifolds are extracted from the patch connectivity graph via a multiple‐source flood fill. The manifolds can be reconstructed into meshed surfaces using standard existing surface reconstruction methods. We demonstrate the speed and robustness of our method on several point clouds, with applications in point cloud segmentation, denoising and medial surface reconstruction.     

一种高效的支持向量回归三维点云修补算法*

给出了一种基于支持向量回归的三维点云空洞修补算法,该算法首先将残缺区域边界点集向邻近区域的切平面投影,投影点集作为训练数据集,通过支持向量回归,得到残缺区域所服从的隐式曲面方程,完成修补。为提高算法效率,将该修补问题转换为等价的最小包含球问题,降低了算法的复杂度。该修补算法能够较好地使修补点云与原始点云平滑融合,具有很好的恢复效果。