# Curves and surfaces in computer aided geometric design - Yamaguchi F.

**Download**(direct link)

**:**

**75**> 76 77 78 79 80 81 .. 90 >> Next

h — h 1 1 Î

2.8 —14 2.8-1

t-j — tA 1 4^ 1

2.8 t5 2.8-2

to

5-2

= 0.933

- 0.6

= 0.267

Using these values of aj9 we determine new curve defining vectors Qj from Eq. (6.136). Since otj= 1 Ñ/^2), Qo = Qo, Qi — Qi> 0,2 —Qi- (*j = Q 0 = 6), Q6 — Q5, C^7= áá j C?8 = 67 j Q9 = 08 • The remaining curve defining vectors are:

Fig. 6.51. Insertion of a knot at ? = 2.8 into the curve of Example 6.4 (Example 6.10)

320

6. The Â-Spline Approximation

Q3— (1 àç)Ñ?2 + àç6ç

= (1-0.933) [30 50]+0.933 [40 55]

= [39.33 54.67]

?4 = (1-îå4)(>ç + à4 Q4

= (1 -0.6) [40 55] + 0.6 [60 20]

=[52 34]

Q5 = (1 — a5) 64 + a5 Q5

= (1-0.267) [60 20] + 0.267 [80 90]

= [65.34 38.69]

A graph of the curve after the knot is inserted is shown in Fig. 6.51.

6.15 Curve Generation by Geometrical Processing 31 )

G. M. Chaikin announced a method for generating curves procedurally, using a very simple geometrical algorithm, without depending on mathematical representations. This can be easily understood from DeBoor’s algorithm in Sect. 6.13.

Q i

Fig. 6.52. Diagram explaining Chaikin’s algorithm (1)

6.15 Curve Generation by Geometrical Processing

321

Suppose that a polygon Q0, Qu ..., Qn is given, as shown in Fig. 6.52(a). Find the midpoints of all of the sides except for the two end sides, and label the polygon formed from these midpoints R0, Rl9 ...,R2n-2 (Fig. 6.52(b)). Figure 6.53(a) shows just the vertex Ri(B) of the initially given polygon and the midpoints Ri_1(A) and /?I + 1(C) of the two sides attached to it.

Letting P be the midpoint of the line segment formed by connecting the midpoints of sides A Â and BC, we have:

A+B B+C

2 + 2 A + 2B+C

P =----------------=-------------. (6.138)

This point P becomes one point on the curve being generated. This division produces a set of 2 sides on either side of point P. Equation (6.138) can be applied to both of these sides. We push the set of 2 sides on the right side, for example, into the stack and then apply Eq. (6.138) again to the set of 2 sides on the left. This operation is repeated, pushing the set of 2 sides on the right into the stack each time, until the length of the set of 2 sides on the left reaches a certain limit. At this point the contents of the stack are poped up and similar

Â(Þ

Fig. 6.53. Diagram explaining Chaikin’s algorithm (2)

322

6. The Â-Spline Approximation

Fig. 6.54. Example of a curve generated by Chaikin’s method

operations are performed on them until the stack is empty. This generates a sequence of lines on the curve corresponding to /?ã_15 Rif Ri+If the above processing is performed for all groups of /?ã_15 Rt, Ri+1 (i=l, 3, ..., 2n — 3), a curve corresponding to the given polygon Q0, Ql} Qn is generated. An example of such a curve is shown in Fig. 6.54.

As can be understood from the curve generation process, the curve is completely determined by only the 3 points /?ã_l5 /?ã, Ri+l. The curve segment has one end at R{_t and the other end at Ri + 1. Its slope at /?ã_! is in the direction of the line segment R^^, and its slope at Ri+1 is in the direction of the line segment R{Ri+l. Since the curve passes through the point P calculated with Eq. (6.138), it is clear that this curve is a parabola (refer to Sect. 7.3). Let us find the equation of this parabola. Writing the curve function in the form

P(t) = [t2 t 1]

we obtain:

P{t) = [2t 1 0]

(6.139)

(6.140)

Since we have the relations P(0) = Rl_1, P(l) = Ri + l, P(0) = p(Ri — Ri_l), P( 1) = q(Rl + l — Ri), the following equation is obtained:

6.15 Curve Generation by Geometrical Processing

323

ß.-1 "0 0 1"

^[ + 1 1 1 1

1) 0 1 0

_q(Rl+1 -Ù 2 1 0

(6.141)

Converting the first matrix on the right-hand side into a square matrix gives:

Rt-1 î î A

^i+1 1111 Â

p(*i-*i-1) 0 10 1 Ñ

ji(Ri+i Ri) 2 10 1 Î

(6.142)

This implies:

À~ î î -1 ' Ri-1 “

Â 1111 ^i+i

Ñ 0 10 1 p{Ri-Ri-1)

Î 2 10 1 ji{Ri+1 ~Rd_

- 1 +

O 1 1"

~2

1 1 2 1

1 1 “I 1

1 1 2 l

~2_

p â ó*.-. 1

1 1+J

Ri-1 Ri + 1

i)

Q(R-i+1 ~ Ri)

l-yWi+yG’-M-fl-fW.

(6.143)

Equating the 4-th rows of the matrices on both sides gives:

324

which implies:

p = q = 2. Therefore:

6. The Â-Spline Approximation

A- Rt - j — 2 Rt + +!

B = IR-lRi^

_C_ *,-1

(6.145)

so the parabola function P(t) becomes: P(t) = [t2 t 1]

= [f2 t 1]

= [f2 t 1]

Rt -1 — é1+1

1 -2 1

-2

1 -2 1Ï rt-Ï

2 2 Î Ä,

1 o oj L^+J

= [(l-f)2 2t(l-0 f2]

= LBoAt) Blt2(t) B2t2(t)-]

-ß.-1 Ri Ë+iJ

*,+i.

(i= 1,3, 2n —3) (6.146)

It is clear that P{t) is a quadratic Bezier curve corresponding to the sequence of vertices Rl_l, Rt, It is easy to confirm that the following relation holds in this case (Fig. 6.55):

4)-Sai3f±fci- 'Gb-«-

Let us now convert this into an expression in terms of the initially given sequence of vertices /?,_2, Rt, Rl + 2 rather than /??_ls /?,, Rl + l. Since we have the relations:

*,-i = *, + i =

Ë.-2 + Ë, 2

^i + ^i + 2

6.16 Interpolation of a Sequence of Points with a Â-Spline Curve

325

Fig. 6.55.

Relation between Chaikin’s curve and polygon

**75**> 76 77 78 79 80 81 .. 90 >> Next