Approximate Implicitization and Approximate Null Spaces

Abstract

Easy conversion of elementary curves and surfaces (lines, circles, ellipses, planes, spheres, cylinders, cones,. . . ) to rational parametric and implicit representations is central in many algorithms used in CAD-systems. For rational Bézier and NURBS-surfaces no such easy conversion exists, a rational parametric surface of bi-degree (n,k) has in the general case an algebraic degree of 2nk giving the bi-cubic Beziér surface a degree 18 implicit representation. Essential to approximate implicitization is the combination of a rational parametric surface p(s,t), (s,t) in&nbsp; [0,1]x[0,1].&nbsp;&nbsp;with the algebraic surface to be found q(x,y,z,h) = 0. The degree m of q, should satisfy 0 < m ≤ 2nk. The combination results in the following factorization, q(p(s,t))=a(s,t)Db, where b contains the unknown coefficients of q, and a(s,t) is an array that contains basis function represented in the tensor product Bernstein basis. Similar expressions exist for rational parametric curves and triangular Bézier surfaces. The smallest singular values of D&nbsp;and&nbsp;&nbsp;their respective coeffiicient vectors&nbsp; represent alternative implicit approximations to p(s,t). If m = 2nk we&nbsp;know that an exact solution exists and that the smallest singular value will be zero. The problem of finding an approximate algebraic representation of p(s,t) has been refomulated to a problem of finding an approximate null space of the matrix D. One obvious choice is Singular Value Decomposition, however, alternative direct elimination methods also exist.

Approximate Implicitization and Approximate Null Spaces