Hjem til forsiden

Approximate implicitization by factorization
Approximate implicitization is a fairly new approach for implicitizing parametric curves, surfaces and hypersurfaces. The GAIA assessment project the preceded GAIA II was based on the work in [Dokken97] on approximate implicitization. In GAIA II we have addressed alternative approaches for approximate implicitization, such as approximation with lower order piecewise algebraic curves and surfaces and weak approximate implicitization based on numeric integration.

The original approach to approximate implicitization

The orignal approach to approximate implicitization is based on studying the combination of a know parametric represented manifold and an unknown algebraic hypersurface. To simplify the notation we focus on finding an approximate implicit surface q(x,y)=0 of degree m>0, with (unknown) coefficients organized in a vector b to a parametric curve p(s), s∈[0,1] of degree n. The combination q(p(s)) is a polynomial of degree mn in s. Let q(p(s)) be represented in a Bernstein basis and assemble the Bernstein basis in the vector α(s). Since the Bernstein basis is a partition of unity we have that ||α(s)||2≤ 1. Now looking in more detail we get  

              |q(p(s))| = |(Db)Tα(s)| ≤ ||Db||2||α(s)||2≤ ||Db||2.

If we find ||b||2≠ 0 such that Db=0 then we have found an exact implicit representation of p(s). Let  σminbe the smallest singular value of D and  bmin be the corresponding coefficients. Then we c an limit the pointwise error by the singular value  |q(p(s))|≤||Dbmin||2min, and we have an algebraic approximation to p(s).

Stable numeric methods exist for building the matrixf D, the convergence rate is very good, e.g. cubic approximate implicitization has 9th order convergence. The approach is also valid for parametric surfaces and higher dimensional manifolds with described by a rational parametrization. For more details consult [Dokken01]  and [Dokken03].

Weak approximate implicitization

The original approach for approximate implicitization was dependent on using a basis that is partition of unity such as the Berstein basis or B-spline basis. In the weak approximate implicitization we integrate the square of q(p(s)) over the parameter domain and the result can be formulated

       ∫[a,b](q(p(s))2ds = bTAb.

The eigenvectors and egenvalues of A are closely related to the singular values and all properties of the original appoach to approximate implicitization are inherited, and the approach is also valid for rational parametric surfaces and higher dimensional rational parametric manifolds. If we use numerical integration instead of exact integration then we can approximate general procedural curves such as offsets.

Piecewise approximate implicitization

 A natural extension to approximate implicitization is to use a piecewise polynomial for representing the algebraic surface. Two approaches have been tried out in GAIA II.

  • AT SINTEF we have tried to just to replace the implicit  q by a tensor product piecewise polynomial.
  • At Johannes Kepler University the gradient directions of the implicit have been estimated and used when constructing the implicit function.

When comparative test have been run, the approach using estimated normals give the best surfaces. In the future the SINTEF approach should be extended to also use estimated normals.



Published May 25, 2005