Interpolating an arbitrary topology mesh by a smooth surface plays an important role in geometric modeling and computer graphics. In this paper we present an efficient new algorithm for constructing a Doo-Sabin subdivision surface that interpolates a given mesh. By introducing additional degrees of freedom, the control vertices of the Doo-Sabin subdivision surface can be obtained directly with no need to solve any initial or intermediate large systems. The control points are computed by modifying the geometric rules of the first step of Doo-Sabin subdivision scheme and the resulting surface interpolates given vertices and optionally normal vectors at the vertices. The method has several merits for surface modeling purposes: (1) Efficiency: we obtain a generalized quadratic B-spline surface to interpolate a given mesh in a robust and simple manner. (2) Simplicity: we use only simple geometric rules to construct a smooth surface interpolating given data. (3) Locality: the perturbation of a given vertex only influences the surface shape near this vertex. (4) Freedom: for each vertex, there is one degree of freedom to adjust the shape of the interpolation surface. These features make surface interpolation using Doo-Sabin surface very simple and thus make the method itself suitable for interactive free-form shape design.

Subdivision surface is an efficient geometric modeling tool that is generated by repeated approximation or interpolation from an initial control mesh. For each time of subdivision the old mesh will be split and the vertexes of the mesh will be refined for a new mesh. Most existing algorithms aim to construct a smooth subdivision surface by smoothing the vertexes of the split mesh. When some features are desired, special rules or parameters should often be applied. In this paper a new nonstationary subdivision method is presented for surface modeling by recursive interpolation from an initial triangular control mesh. For each time of subdivision the mesh itself is a piecewise linear approximation to the final surface, and more details will be added to the surface when the triangles have been split and replaced by more refined subtriangles. We compute every interpolated edge vertex as a solution to the problem of least square fitting of the edge and its neighboring triangles. Sharp features as well as flat regions can be kept well during subdivision. To obtain a visually smooth subdivision surface in the limit, the normal at the vertexes of old meshes will be used as constraint for every time of subdivision. The main advantage of this new method is that the interpolated vertexes depend on the local geometry of the mesh, but not the valences of the mesh. The examples we have tested show that the interpolating surfaces by this new method can inherit the shape of initial course mesh more fairly and naturally.

It is desirable to approximate a smooth curve by arc splines with the fewest segments within a prescribed tolerance. We present an efficient algorithm for fitting planar smooth curves by arc splines. The main idea is that we construct the optimal arc spline by optimizing the interpolating biarc curve. The scheme consists of three steps: sampling the curve based on consecutive tangent deviation; construct the interpolating arc spline; and reduce the arc number to the minimum within a prescribed tolerance. The algorithm can control the approximating error efficiently and results in the fewest number of arc segments.