To main content

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  [0,1]x[0,1].  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 and  their respective coeffiicient vectors  represent alternative implicit approximations to p(s,t). If m = 2nk we 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.

Category

Academic lecture

Language

English

Affiliation

  • SINTEF Digital / Mathematics and Cybernetics

Presented at

The 16th Conference of the International Linear Algebra Society (ILAS)

Place

Pisa, Italy

Date

21.06.2010 - 25.06.2010

Organizer

International Linear Algebra Society

Year

2010

View this publication at Cristin