shaulp@pnet02.gryphon.com (Shaul Peleg) (07/18/89)
I am currently writing a small 3d object editor on the Amiga and I am having
trouble with BEZIER curves (implementation). I have found several sources
including actual source code.. but I feel that this source code cannot show
anyone besides the author (and other such highly-educated people) how to
SIMPLY implement the curves. What I need is simple source code or areference
to a good book. The discusiion in Foley&Van Dam cannot help me much.
[ I am in 10th grade.. not much complicated math traimning,eh? ]
My goal: to produce a bezier curve on screen that can be interactively
positioned.
Thank you,
Shaul Peleg
UUCP: {ames!elroy, <backbone>}!gryphon!pnet02!shaulp
INET: shaulp@pnet02.gryphon.com stuart@rennet.cs.wisc.edu (Stuart Friedberg) (09/12/89)
kaush@moncam.co.uk (Kaush Kotak) writes: >Help! I need info on how to split a single (cubic) bezier curve into two. >Given a t-value & 4 control points, how do I find values for the new control >points? There is probably a more direct method, but you can convert your Bezier curve to a B-spline, find the point at the t-value, and add a knot there with multiplicity 4 (for a cubic curve). The result is two concatenated curves joined at the knot. I used the articles listed below as sources for most of my spline and Bezier curve manipulation routines. The first one provides an algorithm to introduce a new knot to a spline. (Let me distinguish knot vertex <x,y> from knot parameters <t>.) You can convert a B-spline to a (sequence of) Bezier curve(s) by expanding each knot parameter to multiplicity 4 (for cubic curves). The control points for the (concatenated) Bezier segment(s) are the new knot vertices, 4 for each Bezier curve. The t parameter ranges between the two knot parameter values at either end. If I remember correctly (and I may be mistaken here), you can convert a Bezier curve to a B-spline trivially by treating every control point as a knot vertex, and use one knot parameter of multiplicity 4 (for cubic curves) with the value for the beginning of the curve segment (typically 0). Discrete B-Splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics Elaine Cohen, Tom Lyche, and Richard Riesenfeld Computer Graphics and Image Processing, Vol. 14, No. 2, pp. 87-111, 1980 On Calculating with B-Splines Carl deBoor Journal of Approximation Theory, Vol. 6, No. 1(?), pp. 50-62, 1972 Rational B-Splines for Curve and Surface Representation Wayne Tiller IEEE Computer Graphics and Applications, Vol. 3, No. 6, pp. 61-69, 1983 Automatic Construction of a Cubic B-Spline Representation for a General Curve O. Lozover & K. Preiss Computers and Graphics, Vol. 7, No. 2, pp. 149-153, 1983 Offsets of Two-Dimensional Profiles Wayne Tiller and Eric G. Hanson IEEE Computer Graphics and Applications, Vol. 4, No. 9, pp. 36-46, 1984 Computing Offsets of B-Spline Curves Sabine Coquillart Computer-Aided Design, Vol. 19, No. 6, pp. 305-309, 1987 /* three dimensional case */
jp@Apple.COM (John Peterson) (09/13/89)
> You can convert a B-spline to a (sequence of) Bezier curve(s) by > expanding each knot parameter to multiplicity 4 (for cubic curves). > The control points for the (concatenated) Bezier segment(s) are the new > knot vertices, 4 for each Bezier curve. The t parameter ranges > between the two knot parameter values at either end. Actually, to convert B-Spline to Bezier curves making the internal knots have a multiplicity of 3 is sufficient (for the cubic case). For doing knot inseration on curves, Boehm's method is much faster than the Oslo algorithm. (Boehm, "Inserting new knots into B-Spline Curves," CAD, July 1980). If you want to learn all about splines and knot vectors, the classic reference is: "An Introduction to Splines for use in Computer Graphics and Geometric Modeling", by Bartels, Beatty and Barsky (Morgan Kaufman, 1987). Cheers, jp
robert@randu.sgi.com (Robert Skinner) (09/13/89)
In article <8358@spool.cs.wisc.edu>, stuart@rennet.cs.wisc.edu (Stuart Friedberg) writes: > kaush@moncam.co.uk (Kaush Kotak) writes: > >Help! I need info on how to split a single (cubic) bezier curve into two. > >Given a t-value & 4 control points, how do I find values for the new control > >points? > > There is probably a more direct method, but .... [ description deleted ] There is a very simple way to do this from a construction you probably already know. To find a point at t=t0 along a Bezier with the control points A, B, C, and D. find the points t0 of the way from A to B, B to C and C to D: (You should draw a picture to follow along.) E = A + t0*(B - A) F = B + t0*(C - B) G = C + t0*(D - C) repeat with the two segments you get: H = E + t0*(F - E) I = F + t0*(G - F) and repeat again with the last segment: J = H + t0*(I - H) You know J is on the curve, and it turns out that (A, E, H, J) and (J, I, G, D) are the control points for your two curves. Robert
spencer@eecs.umich.edu (Spencer W. Thomas) (09/13/89)
In article <34676@apple.Apple.COM> jp@Apple.COM (John Peterson) writes:
For doing knot inseration on curves, Boehm's method is much faster
than the Oslo algorithm. (Boehm, "Inserting new knots into B-Spline
Curves," CAD, July 1980).
Actually, John, Lyche and Moerken ("Making the Oslo Algorithm more
Efficient", SIAM J. Numer. Anal. 23, 1986, 663-675.) show that,
properly tuned, the Oslo algorithm is equivalent to Boehm's method for
single knot insertions, and more efficient for simultaneous insertion
of multiple knots.
"Our Algorithm 2 reduces to Boehm's method when t is obtained
from r by adding one knot."
Some operation count data is found in (Lyche et al, "Knot line
refinement algorithms for tensor product B-spline surfaces", CAGD 2,
1985, 133-139.) The original Oslo 1 slightly outperforms Boehm when
dealing with (3-D) tensor product surfaces, and the improved algorithm
is significantly faster. Their table (for an n x m tensor product
surface, n >= m):
Algorithm = flops n = m = 10
Oslo 1 72(m-3/2)(n-1) + 36(n+m-3) 6120
Oslo 2 324(m-3/2)(n-1) 24786
Improved Oslo 1 45(m-3/2)(n-1) + 12(n+m-3) 3647
Improved Oslo 2 108(m-3/2)(n-1) 8262
Boehm 81((m-2)(n-2)-1) 5103
(Note that the asymptotic behaviour is well characterized by the
leading coefficient, so that the advantage that Boehm has over Oslo 1
initially will disappear with larger values of n and m.
--
=Spencer (spencer@eecs.umich.edu)adg@otter.hpl.hp.com (Adrian Geisow) (09/13/89)
Let the original control points be b(j), j=0,3.
Let p(0,j) = b(j), j=0,3
Let p(i,j) = (1-t).p(i-1,j) + t.p(i-1,j+1), i=1,3; j=0,3-i
The two new sets of control points are then
{p(i,0)}, i=0,3 and {p(3,0),p(2,1),p(1,2),p(0,3)}
This process generalizes for Bezier curves of all orders.
Adrian Geisowschi@hpcupt1.HP.COM (Shan Chi) (09/14/89)
Given four control points p0, p1, p2, and p3, you may calculate the new control points qi and ri as follows: q0 = p0 q1 = (p0+p1)/2 q2 = q1/2 + (p1+p2)/2 r0 = q3 r1 = (p1+p2)/4 + r2/2 r2 = (p2+p3)/2 r3 = p3 q3 = (q2+r1)/2
schi@hpcupt1.HP.COM (Shan Chi) (09/14/89)
I must have been dreaming while I was reading the question. The previous
response by me was only for the case when the splitting point is at t=0.5. Now
here is what I think the right answer.
-----------------------------------------------------------------------------
Let the Bezier curve be P(t) = T M P, 0 <= t <= 1
where
T = [t^3 t^2 t 1], M = [-1 3 -3 1] and P = [ P0 ]
[3 -6 3 0] [ P1 ]
[-3 3 0 0] [ P2 ]
[ 1 0 0 0] [ P3 ]
Suppose we split at t=x, then the two new curves are:
Q(t) = P(xt) = T Dq M P, 0 <= t <= 1, and
R(t) = P((1-x)t+x) = T Dr M P, 0 <= t <= 1
where Dq = [x^3 0 0 0] and Rq = [(1-x)^3 0 0 0]
[0 x^2 0 0] [3x(1-x)^2 (1-x)^2 0 0]
[0 0 x 0] [3(1-x)x^2 2x(1-x) (1-x) 0]
[0 0 0 1] [x^3 x^2 x0 1]
Now we rearrange them into Bezier form.
Q(t) = T M M^-1 Dq M P = T M (M^-1 Dq M P), and
R(t) = T M M^-1 Dr M P = T M (M^-1 Dr M P)
where M^-1 is the inverse matrix of M.
Therefore,
Pq = M^-1 Dq M P, and
Pr = M^-1 Dr M P
are the two sets of new control points.
Note that (M^-1 Dq M) and (M^-1 Dr M) are functions of x and can be
pre-computed if x is relatively constant.
Hope this time I am not dreaming. :-)schi@hpcupt1.HP.COM (Shan Chi) (09/15/89)
Yet another solution!
-----------------------------------------------------------------------------
Let the Bezier curve be P(t) = T M P, 0 <= t <= 1
where
T = [t^3 t^2 t 1], M = [-1 3 -3 1] and P = [ P0 ]
[3 -6 3 0] [ P1 ]
[-3 3 0 0] [ P2 ]
[ 1 0 0 0] [ P3 ]
Suppose we split at t=x, then the two new curves are:
Q(t) = P(xt) = T Dq M P, 0 <= t <= 1, and
R(t) = P((1-x)t+x) = T Dr M P, 0 <= t <= 1
where Dq = [x^3 0 0 0] and Rq = [(1-x)^3 0 0 0]
[0 x^2 0 0] [3x(1-x)^2 (1-x)^2 0 0]
[0 0 x 0] [3(1-x)x^2 2x(1-x) (1-x) 0]
[0 0 0 1] [x^3 x^2 x0 1]
Now we rearrange them into Bezier form.
Q(t) = T M M^-1 Dq M P = T M (M^-1 Dq M P), and
R(t) = T M M^-1 Dr M P = T M (M^-1 Dr M P)
where M^-1 is the inverse matrix of M.
Therefore,
Pq = M^-1 Dq M P, and
Pr = M^-1 Dr M P
are the two sets of new control points.
Note that (M^-1 Dq M) and (M^-1 Dr M) are functions of x and can be
pre-computed if x is relatively constant.