Farin G. Curves and Surfaces for CAGD. A Practical Guide

Подождите немного. Документ загружается.

372 Chapter 20 Geometric Continuity for Surfaces

20.5 Rectangle-Rectangle

We now consider two tensor product Bezier patches with a common boundary

curve of degree n, illustrated in Figure 20.4. Consider any point x(^) on this

curve. It may be constructed using the (univariate) de Casteljau algorithm. The

de Casteljau algorithm yields the tangent of a curve as a by-product, namely, as

the difference of the two intermediate points

b^~^

and h^~^. In Figure 20.4, those

two points are labeled q/^ and q^. It now follows that the tangent plane of the left

patch in Figure 20.4 is spanned by the points p, q^, q^ and that of the right patch

is spanned by q^, q^, r, where

p(t) = j2PiB';(t)

i=0

and

r(0 = X^r,B^(0.

i=0

We could now follow a similar development, as in the previous section, but a little

trick will give us our desired G^ condition easily. Let us simply degree elevate the

common boundary curve from degree nton-\-l. Call the degree elevated control

points qo,..., q„+i (see Section 6.1 for the degree elevation procedure). Now we

are in the situation of the previous section! Namely, we have n-\-l control points

q3 = q4

Figure 20.4 G^ continuity for rectangular

patches:

the shaded quadrilateral must be planar as it varies

along the common boundary. The case of a cubic boundary curve is shown.

20.4 Rectangle-Triangle 373

p^,

n + 2 control points 4, and n +

control points r^. Our situation is equivalent

to that of a G^ join between two triangular patches of degree

n-\-l.

The desired G^ condition is therefore given by

—TT |"[^iP/-i + ^i^i-i\ -

A-i + M All

n-\-

1 t- J

(20.6)

where / varies from 0 to « + 1.

The geometric interpretation is analogous to that of the preceding section.

20.4 Rectangle-Tk*iangle

This situation, illustrated in Figure 20.5, is now treated in a completely analogous

way. We assume that both patches have a common boundary curve of degree n. If

we degree elevate the triangular patch (Section 17.7), we have the control point

rows

Po? • • • ? P«

(from the tensor product patch), qo,..., q„+i (the degree elevated

common boundary curve), and

IQ,

..., r„ (from the degree elevated triangular

patch).

Thus the G^ condition is

q3 = q4

Figure 20.5 G^ continuity for triangular and rectangular patches: the shaded quadrilateral must be

planar as it varies along the common boundary. The case of a cubic boundary curve is

shown.

374 Chapter 20 Geometric Continuity for Surfaces

n +

= - (1 - ~^) [[^oPi + ^or/] - [Moq/ + Moq^+il] .

again with / ranging from 0 to « + 1.

(20.7)

20.5 ^^Filling

in"

Rectangular Patches

Suppose that we were given the boundary curves of two bicubic patches, as shown

in Figure 20.4. At the endpoints of the common boundary curve, we assume that

the three curves meeting there have coplanar tangents. Can we find interior Bezier

points pi, p2 and r^,

such that the two patches will have a continuously varying

tangent plane along the common boundary? We shall employ the G^ condition

(20.6) for this purpose. As a first step, we determine a^ and

from po,

qo?

TQ,

and ofi, Pi from

P3,

q3,13,

^4.

There are three equations in (20.6) that involve our four unknowns

p^,

p2 and

r^,

12-

After some suitable modification, they are of the form

«oPi + (1 - «o)ri = rhsl,

«lPl + (1 - «i)ri + aoP2 + (1 - ^0)^2 = rhs2,

^iP2 + (1

—

oid^i =

rhs3.

We have abbreviated the right-hand sides of the equations somewhat.

These may be written in matrix form:

with

A =

Ax = b,

Qfl

1 — Qfi

1 — OfQ

Oil (1 - Q^l)

(20.8)

= [pi, p2, r^,

12]^,

and b = [rhsl, rhs2,

rhs3]^.

Since the rows of A are linearly

independent, the underdetermined system (20.8) always has solutions. One way

of finding one is as follows: suppose we already have an estimate x = [pi,

p2,

f 2]

for the unknowns. Then one solves the system

AA^Y = h-Ax

20.7 Theoretical Aspects 375

for y, and the solution is given by

+ A^y.

This solution stays as close as possible to the initial guess x; see [86].

The

and pj could, for instance, be generated by Adini's twists (see Section

16.3).

This idea was carried out by Sarraga

[536],

[537] in a slightly different

context.

20.6 ^Tilling in'' Tk-iangular Patches

Let us reconsider Figure 20.1. Do our G^ conditions allow us to complete the

cubic curve network such that the resulting surface will be G^? In our notation,

the undetermined points are p^ and r^. There are two G^ equations that involve

these points. They are of the form

Qfipi + (1 - Qfi)ri = rhsl,

Qfopi + (1 -

oiQ)ri

= rhs2.

The coefficient matrix of this system:

A =

ai 1

—

Q?!

«0 1-^0

is singular if

= a^. Therefore, in this case, we are not guaranteed to have a

solution (see Piper [483] for an explicit counterexample).

We can, however, solve the problem if we resort to quartics. After we degree

elevate all boundary curves, we now have to determine unknown control points

Pl,

p2 and r^, ti- This is exactly the situation from the preceding section and is

solved in exactly the same way. B. Piper [483] first used quartics to solve this

kind of Hermite interpolation problem.

20.7 Theoretical Aspects

We have developed an approach to geometric continuity that is powerful enough

to solve several applications-oriented problems. It is practical, but it is not

general: there are G^ surfaces that do not satisfy the condition (20.4); see

Problems. T. DeRose has developed conditions that are both necessary and

sufficient for G^ continuity of adjacent Bezier patches.

376 Chapter 20 Geometric Continuity for Surfaces

Several authors (consuh the surveys by Boehm [77], Herron

[322],

and Gre-

gory [291]) define geometric continuity of surfaces in the following way: two

surfaces that share a common boundary curve are called C if, for every point

of the boundary curve, a reparametrization exists such that both surfaces are C^

in a neighborhood of that point. For the case r = 1, this definition yields tangent

plane continuity. Its advantage is that it also works for higher orders; the price to

be paid is that it is rather abstract. For the case of G^ continuity, another popular

definition is to require a common Dupin's indicatrix along the boundary curve

(see Section 19.12, Kahmann

[350],

and Pegna and Wolter [459]).

20.8 Problems

1 In Section 20.1 we saw an example of triangular patch boundaries that

could not be completed to construct an overall C^ surface. Find similar

examples for tensor product patches.

2 Show that the G^ conditions (20.4) include the case of strict contmuity

(17.23) between triangular patches.

3 Construct surfaces that are G^ yet do not satisfy (20.4).

A Consider eight triangular patches, assembled so as to form eight octants

of a spherelike surface. Show that this closed surface cannot be C^, that

is,

one cannot find a region in the plane that comprises eight triangles that

have a C^ map that maps them to the surface.

PI Construct a spherelike G^ surface that is made up of six biquartic patches

having a cubelike connectivity.

Surfaces with

Arbitrary Topology

I he surfaces that we have met so far are best suited for shapes that are the

image of some part of the plane—of a rectangle in the case of B-spline or Bezier

surfaces, of a triangulated region in the case of composite Bezier triangles. This

limits the topology of these surfaces; for example, it is not possible to construct

even a sphere without introducing degenerate patches while using a C^ map of a

part of the plane. Even shapes that have the topology of a planar region may be

too complex to model with one tensor product surface; just imagine modeling

a glove that way. The complexity issue may be tackled using the approach of

hierarchical B-spline surfaces as proposed by Forsey and Bartels

[245].

But even

with this method, arbitrary topology is not achievable.

In this chapter, we will investigate methods that are suited for the construction

of shapes of arbitrary complexity and/or topology. We can present only a brief

selection of methods; more literature on the topic:

[177],

[596], [595],

[594],

[289], [290], [293], [321], [431], [627], [398], [561].

The first in-depth study of

recursive subdivision processes goes back to U. Reif

[503].

The basic concepts of

surface topology are nicely explained in

[323].

21.1 Recursive Subdivision Curves

We already encountered Chaikin's algorithm in Section 8.4. Starting with a

polygon, it produces a sequence of refined polygons that ultimately converge

to the uniform quadratic B-spline curve defined by the initial polygon.

This principle may be applied to higher-degree uniform splines; we discuss the

cubic case here. If we double a uniform knot sequence by inserting the midpoint

577

378 Chapter 21 Surfaces with Arbitrary Topology

Figure 21.1 Subdivision curves: one step of cubic B-spline curve subdivision.

of every knot, new control points d] are generated from the existing ones by

setting

d«:

1(1)

3, 1.

1 1

(21.1)

4Vi-^d«

+ 1

4 4 0"

1 6 1

0 4 4

^k-i~

dfe

dfe+i_

See Figure 21.1 for an illustration. We may analyze the resulting curve by

exploiting the fact that we are dealing with a cubic B-spline curve. However,

that analysis may also be carried out without this knowledge. Let us investigate

the limit of the sequence d^, d^^^

d^^,....

We may write the recursion in matrix

form as

^ik

L ^lk+1 -I

and abbreviate it as

D^i^=AD. (21.2)

The matrix A has eigenvalues 1, 2? ^ ^^^ ^^y ^^ diagonalized^ as

A = EAE-\

where

1 The process of diagonalization is a standard linear algebra procedure.

21.1 Recursive Subdivision Curves 379

E =

1 1 2

1 0 -1

1 -1 2

-2

1 "

-3

A =

"1 0

0 i

_0 0

The matrix E contains A's eigenvectors, and the diagonal matrix A contains A's

eigenvalues.

For the next iteration, v^e have

Using our diagonalization for A, w^e get

= EAE-^E-^AE = EA^E'^

(21.3)

and further

Taking the limit r ^^ oo yields

= EA'E-\

A~ = £A~£-i.

Since

this becomes

A^ = -

1 0 0"

0 0 0

1 4 1

implying that all three points d^_i, d^, d^+j converge to the same point (d^_i +

4d^ + d^+l)/6. This result is no surprise since we know^ v^e are dealing v^ith

B-spline curves. It does illustrate, how^ever, a general principle that is ubiquitous

in all subdivision theory, namely, that convergence analysis is normally carried

out via an eigenvalue analysis.

Subdivision may also be used to generate interpolating curves. The basic four-

point principle w^as developed by Dyn, Levin, and Gregory

[178], [176].

Let a

380 Chapter 21 Surfaces with Arbitrary Topology

Figure 21.2 Subdivision curves: one step of the four-point scheme.

sequence of points p^ be given; then successively construct new sequences by

setting

P^NP.

(21.4)

^—O.-

+ 9o.- + 90;

—

T1.

P2/+1 = T2t"P^-i +

^P^'

"^ ^P^+i ~ P^+2]'

For an illustration, see Figure 21.2. The point

P2/+1

is the result of applying cubic

Lagrange interpolation at uniform knots, see

[519].

At each level of the subdivision process, the points of the previous step are

retained; this causes the scheme to interpolate to the initial set of points. The

limit curve is C\ but fails to be C^.

21.2 Doo-Sabin Surfaces

The fundamental idea of this kind of surface goes back to Chaikin's algorithm;

see Section 8.4. There, v^e started w^ith a polygon, iteratively applied a refinement

procedure to it, and observed that in the limit vjt ended up vv^ith a smooth curve.

M. Sabin and D. Doo asked if this principle could be carried over to surfaces:

start with a polyhedron, iteratively apply a refinement procedure to it, and see if

a smooth surface would result.

They then came up with the following algorithm, illustrated in Fig. 21.3

and documented in

[174]:

input: an arbitrary closed polyhedron with vertices

p^.

These vertices form (straight) edges and (not necessarily planar) faces, thus

defining the topology of the polyhedron. The refinement step now becomes:

For each face, compute new vertices

v^-

by averaging the vertices v^ of the

face as follows:

(1)

E«';^/

(21.5)

21.2 Doo-Sabin Surfaces 381

Figure 21.3 The Doo-Sabin algorithm: a new polyhedron is constructed by a refinement procedure,

where the aij are given by

3+2 cos

n±5_

2n(i-j)

(21.6)

Construct a new polyhedron from these new vertices.

Step 2 needs some more explanation. The new polyhedron will have faces that

are constructed according to three different rules:

2a. The F-faces are found by cyclically connecting the

V^-

of each original face.

2b.

The E-faces are found by considering any two original faces sharing a

common edge: there are exactly four midpoints on the lines connecting

each face centroid with the edge endpoints. These four points produce a

four-sided face.

2c.

The

V-faces

are formed by considering all E-faces around an original vertex.

They surround a face that is "centered" on that vertex.

As we keep repeating the algorithm, it produces mostly four-sided faces. The

only non-four-sided faces are V-faces generated by those initial vertices whose

valency^ is not four, or F-faces whose initial faces are not four sided. These faces

give rise to limit points whose valency is not four, so-called extraordinary vertices.

In fact, it is not hard to see that after the first step the valency of every new

vertex is four. In this manner, large regions of the new polyhedra are covered with

nets that have a tensor product structure. Doo-Sabin surfaces are thus "mostly"

biquadratic B-splines. See Figure 21.4 for an example.

2 The valency of a vertex is the number of edges emanating from it.