Books in black and white
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics

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

Yamaguchi F. Curves and surfaces in computer aided geometric design - Tokyo, 1988. - 390 p. Previous << 1 .. 69 70 71 72 73 74 < 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 Previous << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 90 >> Next 