This method for approximate implicitization has been developed at Linz. It is characterized by the simultaneous approximation of sampled point data P_i (x_i, y_i, z_i) and estimated normals  n_i  at these points. The method produces an approximate implicit representation of the form f(x, y,z) = sum (C_i  B_i(x, y, z)) with basis B_i(x, y, z) and a certain coefficients C_i. 

The points P_i (x_i, y_i, z_i)   are organized into segments. The segmentation is realized by a simple region growing process. Simultaneously while building the segments we propagate the orientation of the estimated normals. This is simply done by checking the scalar product of the normal of the point which is to be added and the normal of the closest point that already belongs to the segment. If this product is negative, then the orientation of the normal is needs to be swapped. In order to control the shape of the resulting surface, an additional tension term is optimized. It pulls the approximating surface towards a simpler shape. The implicit function is obtained as the minimum of a convex quadratic objective function

sum  f(x_i, y_i,z_i)²  +  w || grad(f(x_i, y_i,z_i)) - n_i ||²  + ``tension''

where w is a positive weight controls the influence of the estimated normal vector n_i  to the resulting surface. This method is fully general, i.e., it can be applied to any space of functions, not only to piecewise polynomials. For practical applications, however, fast evaluation of basis functions is important. For this reason we implemented the algorithm for trivariate tensor-product B-splines. In this case, the basis functions ensure global smoothness, and the resulting system of linear equations is sparse.

Choice of the spline space

The domain of interest is divided into cubes of the same size. This is done by specifying a cell-size. In order to guarantee an integer number of cells, the bounding box of the input surface is enlarged a bit. The domain of the spline functions consists only of the ``active cells'', i.e cubes that containing data, and its neighbors. Another input parameter is the degree d of the spline function. We choose the knot vector with simple knots in the interior, so the continuity is C^d-1.

Due to the compact support of the B-splines, the implementation is relatively fast because of the sparsity of the resulting linear system of equations. Consequently, even complicated singular surfaces can be implicitized. The figure below shows a surface with two self-intersecting curve. It has been approximately implicitized by tetrahedral polynomial (left), tensor product polynomials (middle) and tensor product spline (right). By using spline functions, one may avoid unwanted branches completely.