B样条是工业造型中自由曲线曲面的标准表达形式，在CAD系统中广泛运用。插值和拟合算法是一类由离散数据生成连续曲线曲面的方法，它们是B样条曲线曲面的基础构造算法。本文针对实际运用中各类不同的输入输出要求，分别讨论几种B样条曲线曲面的插值拟合算法。论文的具体内容如下：关于曲线插值，提出B样条曲线向多目标点的延伸算法。算法根据输入曲线生成边界条件相同的均匀B样条曲线，然后逐步延伸到各个目标点。算法使用均匀节点构造延伸曲线，利用均匀B样条曲线加速求解过程，从而使得时间效率高于前人方法。关于曲线拟合，提出由三视图点集重建空间B样条曲线的拟合算法。算法通过逐步跟踪法从平面离散点中提取出空间有序点集，对原数据重新分组并求解能量函数，迭代优化之后获得结果曲线。算法自动生成初始曲线，并能有效处理输入视图中投影曲线的自重叠问题。关于曲面插值，提出B条曲面插值四边网格的算法改进。前人算法存在一些缺陷，有些情况下结果曲面不能达到二阶几何连续。本文指出这些问题并进行修正，提高了插值曲线的阶数，证明了系数矩阵的奇异性并提出修改方法，使得结果曲面严格满足G2连续。关于曲面拟合，提出由网格模型构造B样条曲面的拟合算法。算法根据顶点参数化结果划分输入网格，生成各个子网格，组成树形结构；对于每个子网格分别使用B样条曲面拟合，由父节点到子节点的顺序依次构造结果曲面。算法使用较少数目的B样条曲面拟合网格模型，结果达到G2连续。提出基于细分剪枝的点投影算法改进。在插值拟合方法中，点投影操作被频繁使用，直接影响着算法效率。本文提出计算离散点到控制点集凸包投影距离的近似方法，将其运用于点投影算法中排除不相关的曲线段/曲面片，使得投影算法的时间效率高于前人方法。
B-spline is the standard representation of free-form curves and surfaces in computer aided design. The fitting algorithms try to generate continuous curves or surfaces from discrete data, and they are the important tools of constructing B-spline curves and surfaces in practice. The researchers have developed many kinds of fitting methods for different applications. Based on the different requirements for the input or output data, the paper proposes several fitting algorithms, which are summarized as the following:As for curve interpolation, an extension algorithm for the B-spline curve is proposed. We convert the original curve into a uniform B-spline curve segment and then extend the segment stepwise to pass through every target point. Curve clamping and unclamping are used in the method, and algorithms of uniform B-spline curves are also utilized. The time efficiency of the algorithm is significantly improved with the help of the evaluation methods for uniform B-splines.As for curve approximation, an approximation method of reconstructing space curves from orthogonal views is proposed. We obtain a set of ordered sampling points through tracking the planar views simultaneously. Then we reorganize the input points with the help of the sampling points and compute the resulting curve through minimizing an assigned energy function. The algorithm can construct the initial curves automatically, and the situation can be effectively handled where the projection curves in the views are self-overlapping.As for surface interpolation, an improvement is made for the method that B-spline surfaces interpolate quadrangular meshes. The original method has several mistakes, which make the resulting surfaces possibly fail to have $G^2$ continuity. We point out and try to correct this mistakes. We reassign the degrees of the spanning curves and efficiently handle the situation where the linear system is singular. The resulting surfaces can be ensured G2 continuity after our adjustment.As for surface approximation, an approximation method of constructing B-spline surfaces from an input mesh is proposed. For a mesh model that is difficult to fit with one B-spline surface, we divide it into several patches that form a tree structure, and for each patch, we use one B-spline surface for fitting. We estimate the knot vectors of B-spline surfaces first and then evaluate the control points through energy function minimization. Normally, only a few patches are required in our method, and G2 (or higher) continuity can be achieved between the adjacent surfaces.An improvement is made for the point projection method based on recursively subdivision. Point projection is frequently used in the fitting methods. Recursively subdivision is widely used in the the point projection algorithms. In order to remove unnecessary NURBS curve or surface patches, a clipping method is presented based on the distance approximation between the source point and the convex hull of the control points. With our method the performance of the point projection algorithms is improved.
