Approximate Implicitization and Approximate Null Spaces

Approximate Implicitization

Tor Dokken and Oliver Barrowclough

SINTEF, Norway

June 22, 2010

Parametric and Implicit Representations

We will address rational parametric surfaces S_P = p(s₁,s₂)2^R3: (s₁,s₂)2^{Ω R2 ,}

wherep(s₁,s₂) = (p₁(s₁,s₂),p₂(s₁,s₂),p₃(s₁,s₂)), andp₁(s₁,s₂), p2(s1,s2), andp3(s1,s2)are bivariate polynomials or rational functions with the same denominator of degreen.

We will approximate these withimplicit surfaces de…ned as the zero set of a nontrivial trivariate polynomialq of degreem>0:

S_I = (x,y,z)2R³ :q(x,y,z) =0 .

Exact and Approximate Implicitization

A nontrivial polynomialq gives an exact implicitization ofp(s)if q(p(s)) =0, for all s2 Ω.

A nontrivial polynomialq gives an approximate implicitization of p(s)within the tolerance ε if there exists g(s)such that

q(p(s) +g(s)) =0, for all s2 ^Ω, and

max

s2Ωk^g(s)k ^ε.

Applications of the Implicitization

Applications:

I Intersection algorithms - detecting self-intersections,

I Ray tracing,

I Classi…cation - is a given point above, below or on the surface.

Approaches Approximate Implicitization:

I Dokken 1997 (Strong form),

I Sederberg et al. 1999 (Monoids),

I Wurm and Jüttler 2003 (Point based curves),

I Dokken and Thomassen 2006 (Weak form),

I Barrowclough and Dokken 2010 (Triangular Bézier, General Point Based).

Barycentric coordinates

Barycentric coordinates allow us to express any pointx2^{Rl as,} x=

l+1 i

∑

β_ia_i,

wherea_i 2 ^Rl are points de…ning the vertices of a non-degenerate simplex inR^l under the condition that

∑

I In R² the simplex is a triangle

I In R³ the simplex is a tetrahedron

In the reminder of the presentation we assume that the Bézier curves and surfaces are inside the simplex so all vertices expressed in barycentric coordinates are positive.

Multi index and vector notation

I We will use a vector and multi index notation for describing the rational parametric objects

I This allows us to describe the approach in a generic way p(s) =

∑

i2Iⁿ

c_iB_i,n(s),s2^Ω,

I where the basis functions B_i,n(s),i2 Iⁿ, satisfy the partition of unity property

i

∑

B_i,n(s) = 1,s2 ^{Ω, with} B_i,n(s) 0,s2 ^Ω,i2 I^n.

I The coe¢ cients are represented in projective spaceci 2 P, i2 Iⁿ, to also support rational parametrization.

Barycentric coordinates and Bernstein bases over Simplices

For bivariate barycentric coordinatess= (s₁,s₂,s₃), the triangular Bernstein basis polynomials of degreen are:

B_iⁿ(s) = ⁿ

i₁,i₂,i₃ s₁ⁱ¹s₂ⁱ²s₃ⁱ³, jⁱj=i₁+i₂+i₃ =n.

For trivariate barycentric coordinatesu= (u₁,u₂,u₃,u₄); the tetrahedral Bernstein basis polynomials of degreem are:

B_i^m(u) = ^m

i₁,i₂,i₃,i₄ u₁ⁱ¹u₂ⁱ²u₃ⁱ³u₄ⁱ⁴, jⁱj=i1+i2+i3+i4 =m.

Multinomial coe¢ cients:

n

i₁,i₂,i₃ = ^n!

i₁!i2!i3!.

Example: Bézier Curves and Surface

I For 2D Bézier curves l =2,n=n,i=i,ci = (ci,x,ci,y,ci,h) and I =f^{0,. . .,n}g^,giving

p(s) =

∑

c_i n

i (1 s)^{n i}sⁱ.

I For tensor product Bézier surfacesl =3, n= (n₁,n₂), i= (i1,i2),ci = (ci,x,ci,y,ci,z,ci,h)and

I =f(i1,i2)j^{0 i1 n1}^^{0 i2 n2}g^,giving, p(s) =

n1

i1

∑

i

∑

c_i1,i2 n₁ i₁

n₂

i₂ (1 s₁)^{n1 i1}s₁ⁱ¹(1 s₂)^{n2 i2}s₂ⁱ².

Example: Triangular Bézier Surface

For triangular Bézier surfacesl =3,n=n,i= (i1,i2,i3), c_i= (c_i,x,c_i,y,c_i,z,c_i,h)and

Iⁿ=f(i₁,i₂,i₃)j^{0 i1,i2,i3 n}^ⁱ¹+i₂+i₃ =ng^, giving,

p(s) =

∑

i1+i2+i3=n

c_i1,i2,i3 n

i₁i₂i₃ s₁ⁱ¹s₂ⁱ²s₃ⁱ³, with (s1,s2,s3)barycentric coordinates inΩ R².

Implicit Surfaces and Algebraic Distance

The intention is to …nd a polynomialq describing an implicit surface that approximatesp(s) in the tetrahedral Bernstein basis of degreem

q(u) =

∑

jⁱj=m

b_iB_i^m(u).

The task is to …nd the unknown valuesb_i for jⁱj=m that satisfy the approximation criteria.

The algebraic distance between an implicitly de…ned surface and a pointu₀2 ^P3 is the valueq(u_o).

Implicitization and exact degrees

I A rational parametric 2D curve of degree n has an implicit degree of at mostm=n.

I A parametric surfaces of bi-degree (n₁,n₂) has an implicit degree of at mostm=2n₁n₂.

I A parameter surface of total degree n has an implicit degree of at most m=n².

Approximate implicitization allows algebraic curve and surface approximations with lower degrees than the exact degreem while using ‡oating point arithmetic.

Approximate Implicitization

We attempt to minimize the algebraic distance, givenp(s) and a chosen degreem of q:

I Original Approach: Minimize the algebraic distance point wise:

min

k^bk=1max

s2Ωj^q(p(s))j^,

I Weak Approach: Minimize the integral of the squared algebraic distance:

min

k^bk=1

Z

Ω(q(p(s)))²ds,

I Point based approach: Minimize the squared algebraic distance for a set of points p(s_k),k =1,. . .,N

min

k^bk=1

∑

(q(p(s_k)))².

Original Approach

De…ne a matrixD by the values (d_i,j)_jij=m,j2J

m,n, a vector B^mn(s) = (B^mn(s))_j2Jm,n and a vectorb= (b_i)_jij=m. q(p(s)) =

∑

jⁱj=m

biB_i^m(p(s))

=

∑

jⁱj=m

b_i

∑

j2J^m,n

d_i,jB_j^mn(s)

!

=

∑

j2J^m,n

B_j^mn(s)

∑

jⁱj=m

d_i,jb_i

!

= B^mn(s)^TDb.

Letσmin be the smallest singular value ofD.

min

k^bk=1max

s2Ω j^q(p(s))j ^max_s

2Ωk^Bmn(s)k2 min

k^bk=1k^Dbk2 σmin.

Original Approach

I For 2D curves J^m,n=J^m,n=f^{1,. . .,mn}g

I For triangular Bézier surfaces J^m,n= J^m,n=f^j:j^jj=mng^,

I For tensor Bézier surfaces

J^m,n=Jm,(n1,n2) =f(j₁,j₂):1 j₁ mn₁^^{1 j2 mn2}g^. To summarize the approach:

I To produce Dmultiply out the coordinate functions ofp(s) according to

B_i^m(p(s)) =

∑

j2J^m,n

d_i,jB_j^mn(s)

! .

I Perform SVD onD= (di,j)_jij=m,j2J

m,n.

I Choose the coe¢ cients b_min = (b_i)_jij=m corresponding to the smallest singular valueσmin in the SVD as the solution to the approximation problem.

Weak Approach

Z

Ω(q(p(s)))²ds = b^TD^T Z

ΩB^mn(s)B^mn(s)^Tds Db.

= b^TD^TADb

= b^TD^TU^TΣΣUDb

= k^ΣUDbk²2.

withA=U^TΣΣUthe singular value decomposition ofA. For the triangular Bézier surfaceAlooks like.

a_i,j =

Z

ΩB_i^mn(s)B_j^mn(s)ds= (^mn_i )(^mn_j ) (^2mn_i+j)

Z

ΩB_i^2mn_+j (s)ds

= (^mn_i )(^mn_j ) (^2mn_i+j)

1

(2mn+1)(2mn+2)^.

Numerical Weak Approach

The integral in weak approximate implicitization can also be evaluated numerically. Using the factorization

q(p(s)) =

∑

jⁱj=m

b_iB_i^m(p(s))

Z

Ω(q(p(s)))²ds=

Z

Ω

∑

jⁱj=m

biB_i^m(p(s))

!2

ds=b^TMb

mi,,j=

Z

ΩB_i^m(p(s))B_j^m(p(s))ds= (^m_i)(^m_j) (^2m_i+j)

Z

ΩB_i^2m_+j(p(s))ds.

Exploiting symmetries within this algorithm can signi…cantly reduce the computation time.

Point Based Approach

Letυ(i) be a lexicographical ordering such thatB_i^m(s) =B^m

υ(i)(s), b_i =b_υ(i) and let L= (^m+₃³) be the number of basis functions

∑

(q(p(s_k)))² =

∑

∑

biB_i^m(p(s_k))

!2

= 0 BB BB BB

@

B₁^m(p(s1) . . . B_L^m(p(s1)

... ...

B₁^m(p(s_k) . . . B_L^m(p(s_k) ... B₁^m(p(s_N) . . . B_L^m(p(s_N)

1 CC CC CC A b

2

2

= k^Cbk²2 =b^TC^TCb.

Point Based Approach

Now looking at columnci thei^th column ofC

(c_i)^T = B_i^m(p(s₁)) . . . B_i^m(p(s_k)) . . . B_i^m(p(s_N)) .

The polynomialB_i^m(p(s))is a polynomialB_i^mn(s) of degreemn in the variabless. The number of basis functions K in the polynomial space used for describingB_i^mn(s)depends on p(s)being a curve, a tensor product Bézier surface or a triangular Bézier surface:

I In the curve caseK =mn+1.

I In the tensor product Bézier surface case K = (mn₁+1) (mn₂+1).

I In the triangular Bézier surface caseK = (^mn₂⁺²).

Point Based Approach

Now choosing the number of interpolation points toN =K we can pose interpolation problems using the basis functionsB_j^mn(s)from the original approach to reproduceB_i^m(p(s))and its coe¢ cients d_i

Gd_i = c_i,with G = B_j^mn(s_k) _j

2J^m,n,k=1,...,K .

ProvidedGis nonsingular the rows d_i of the matrixD= (d_i) of the original approach can be expressed

d_i=G ¹c_i.

Using this we get vu ut

∑

k=1

(q(p(s_k)))² = k^Cbk2

= GG ¹Cb ₂ =k^GDbk2.

Relations between Approaches

Letσmin be the smallest singular value ofD.

I Original Approach:

min

k^bk=1max

s2Ωj^q(p(s))j= min

k^bk=1k^Dbk2 σmin.

I Weak Approach: Letλmax be the largest eigenvalue of Σ min

k^bk=1

r_Z

Ω(q(p(s)))²ds= min

k^bk=1k^ΣUDbk2 λmaxσmin.

I Point based approach: LetGbe nonsingular and g_max its largest eigenvalue

min

k^bk=1

vu ut

∑

k=1

(q(p(s_k)))² = min

k^bk=1k^GDbk ^gmaxσmin.

Convergence

I Curves in R² are approximated with convergence O(h^(m+1)(2m+2)).

m 1 2 3 4 5 6

rate 2 5 9 14 20 35

I Surfaces inR³ are approximated with convergence O(h

j1 6

p(9+12m³+72m²+132m ¹₂k

).

m 1 2 3 4 5 6

rate 2 3 5 7 10 12

Singular Bézier Triangle

c₂₀₀ = (0,0,0),

c110 = (0,0,1), c101= (0,1,0),

c₀₂₀ = (0,0,0), c₀₁₁= (1,0,0), c₀₀₂ = (0,0,0).

Figure: Exact (left) and approximate (right) implicitization of the parametric triangular Bézier surface (middle).

Several Patches Simultaneously

Parametric Quadratic Cubic Quartic

The original approach stacks the matrices:

D= 0 B@

D₁ ... D_r

1 CA.

The weak and point based approaches sum the matrices:

M =

∑

M_i,

C =

∑

Ci.

Conclusion

I Approximate implicitization combines algebraic geometry, computer aided design and linear algebra to o¤er a family of methods for the approximation of parametric curves and surfaces by algebraic curves and surfaces.

I The methods have proven high convergence.

I The methods employ stable numerical methods.

Acknowledgements: This work has been supported by the European Community under the Marie Curie Initial Training Network "SAGA - Shapes, Geometry and Algebra" Grant

Agreement Number 21458, and by the Research Council of Norway through the IS-TOPP program.