cubic bezier -> quadratic bezier

cubic bezier -> quadratic bezier

Post by Sigurd Lersta » Wed, 27 Dec 2000 21:46:34



Hello,

Does anyone have any source-code to convert from cubic beziers to quadratic
beziers, I know it involves approximation and subdivision, but I'm not
exactly a mathematical genius so some source code or some very detailed not
to advanced step by step explanations would be very nice..

thanks in advance,

--
Sigurd Lerstad

 
 
 

cubic bezier -> quadratic bezier

Post by Dave Eberl » Fri, 29 Dec 2000 01:15:27



Quote:> Does anyone have any source-code to convert from cubic beziers to
quadratic
> beziers, I know it involves approximation and subdivision, but I'm not
> exactly a mathematical genius so some source code or some very detailed
not
> to advanced step by step explanations would be very nice..

No doubt there are many ways to do the reduction.  The following method
reduces a single cubic Bezier curve to a single quadratic Bezier curve.  If
the cubic Bezier curve is X(t) with control points P0, P1, P2, and P3 and if
the quadratic Bezier curve is Y(t) with control points Q0, Q1, and Q2, set
Q0 = P0 and Q2 = P3 (make the end points match).  Select Q1 to minimize the
squared error Integral(0,1) |X(t)-Y(t)|^2 dt.  The result is Q1 =
(-P0+3*P1+3*P2-P3)/4.  If you do not like the end point equality
constraints, a variation you could use is to compute all of Q0, Q1, and Q2
by the minimization process.

For a more "global" reduction, suppose you have a piecewise cubic Bezier
curve with control points P0 through P_{3N} (P0 through P3 define first
curve, P3 through P6 define second curve, and so on).   The first curve is
defined for t in [0,1],  the second curve is defined for t in [1,2], and so
on, the last curve is defined for t in [N-1,N].  You want a set of control
points Q0 through Q_{2M} that define a piecewise quadratic Bezier curve (Q0
through Q2 define first curve, Q2 through Q4 define second curve, and so
on).  You choose M as small as you like.  The first curve is defined for t
in [0,N/M], the second curve is defined for t in [N/M,2*N/M], and so on, the
last curve is defined for t in [N*(M-1)/M,N].  Determine the Q_i by
minimizing Integral(0,1) |X(t)-Y(t)|^2 dt.  The details are tedious, but you
wind up with a linear system to solve.  Any equality constraints like Q0 =
P0 and Q_{2*M} = P_{3*N} only reduce the number of equations in the linear
system.

--
Dave Eberly

http://www.magic-software.com

 
 
 

cubic bezier -> quadratic bezier

Post by Sigurd Lersta » Fri, 29 Dec 2000 20:16:47


Thanks for the answer,

You don't happen to know of any source-code to do this, as I must admit I
didn't really understand a lot :)

thanks again,

--
Sigurd Lerstad

> > Does anyone have any source-code to convert from cubic beziers to
> quadratic
> > beziers, I know it involves approximation and subdivision, but I'm not
> > exactly a mathematical genius so some source code or some very detailed
> not
> > to advanced step by step explanations would be very nice..

> No doubt there are many ways to do the reduction.  The following method
> reduces a single cubic Bezier curve to a single quadratic Bezier curve.
If
> the cubic Bezier curve is X(t) with control points P0, P1, P2, and P3 and
if
> the quadratic Bezier curve is Y(t) with control points Q0, Q1, and Q2, set
> Q0 = P0 and Q2 = P3 (make the end points match).  Select Q1 to minimize
the
> squared error Integral(0,1) |X(t)-Y(t)|^2 dt.  The result is Q1 =
> (-P0+3*P1+3*P2-P3)/4.  If you do not like the end point equality
> constraints, a variation you could use is to compute all of Q0, Q1, and Q2
> by the minimization process.

> For a more "global" reduction, suppose you have a piecewise cubic Bezier
> curve with control points P0 through P_{3N} (P0 through P3 define first
> curve, P3 through P6 define second curve, and so on).   The first curve is
> defined for t in [0,1],  the second curve is defined for t in [1,2], and
so
> on, the last curve is defined for t in [N-1,N].  You want a set of control
> points Q0 through Q_{2M} that define a piecewise quadratic Bezier curve
(Q0
> through Q2 define first curve, Q2 through Q4 define second curve, and so
> on).  You choose M as small as you like.  The first curve is defined for t
> in [0,N/M], the second curve is defined for t in [N/M,2*N/M], and so on,
the
> last curve is defined for t in [N*(M-1)/M,N].  Determine the Q_i by
> minimizing Integral(0,1) |X(t)-Y(t)|^2 dt.  The details are tedious, but
you
> wind up with a linear system to solve.  Any equality constraints like Q0 =
> P0 and Q_{2*M} = P_{3*N} only reduce the number of equations in the linear
> system.

> --
> Dave Eberly

> http://www.magic-software.com

 
 
 

cubic bezier -> quadratic bezier

Post by Dave Eberl » Sat, 30 Dec 2000 05:14:00



Quote:> You don't happen to know of any source-code to do this, as I must admit I
> didn't really understand a lot :)

I do not currently have the time to put together an
implementation for the least-squares algorithm.
However, the following algorithm might satisfy the
needs of your application.  This one is easier to
implement.

Given a piecewise cubic Bezier curve, sample
it to obtain points P(0) through P(2*N).  You get
to choose N any way you like.  If you want to
sample the points to be uniformly spaced by
arc length, I do have code at my web site for
this.  I also have code for other subdivision
schemes.

Construct a quadratic Bezier curve that contains
the points P(0), P(1), P(2):
X(t) = (1-t)^2*P(0)+2*t*(1-t)*(2*P(1)-(P(1)+P(2))/2)+t^2*P(2)
So X(0) = P(0), X(1/2) = P(1), and X(1) = P(2).
Do the same for (P(2),P(3),P(4)), (P(4),P(5),P(6)),
and so on.  You now have a piecewise quadratic
Bezier curve that contains all the samples you
selected from the piecewise cubic Bezier curve.

--
Dave Eberly

http://www.magic-software.com

 
 
 

cubic bezier -> quadratic bezier

Post by PROF D. Rogers {EAS FA » Sun, 31 Dec 2000 00:27:10


G'day,

I have not been following this one closely but if all the poster
wants to do is to go from a cubic (degree 3) Bezier curve to a
quadratic (degree 2) Bezier curve, then there are standard
algorithms for doing this quite simply. Robin Forrest gave the
algorithm as early as 1972. The technique is discussed, with a
worked example, in the Introduction to NURBS, With Historical
Perspective book (Section 3.13, p. 102)
(www.nar-associates.com/nurbs).
It is also discussed in The NURBS Book (Section 5.6, p 212) in
the context of degree reduction of a B-spline curve.

Note that it is not possible to degree reduce all Bezier
curves and that the reduction process is an approximation
process.

Dave Rogers



!! You don't happen to know of any source-code to do this, as I must admit I
!! didn't really understand a lot :)
!
!I do not currently have the time to put together an
!implementation for the least-squares algorithm.
!However, the following algorithm might satisfy the
!needs of your application.  This one is easier to
!implement.
!
!Given a piecewise cubic Bezier curve, sample
!it to obtain points P(0) through P(2*N).  You get
!to choose N any way you like.  If you want to
!sample the points to be uniformly spaced by
!arc length, I do have code at my web site for
!this.  I also have code for other subdivision
!schemes.
!
!Construct a quadratic Bezier curve that contains
!the points P(0), P(1), P(2):
!X(t) = (1-t)^2*P(0)+2*t*(1-t)*(2*P(1)-(P(1)+P(2))/2)+t^2*P(2)
!So X(0) = P(0), X(1/2) = P(1), and X(1) = P(2).
!Do the same for (P(2),P(3),P(4)), (P(4),P(5),P(6)),
!and so on.  You now have a piecewise quadratic
!Bezier curve that contains all the samples you
!selected from the piecewise cubic Bezier curve.
!
!--
!Dave Eberly

!http://www.magic-software.com
!
!
!

 
 
 

cubic bezier -> quadratic bezier

Post by Dave Eberl » Sun, 31 Dec 2000 03:23:09




Quote:> G'day,

> I have not been following this one closely but if all the poster
> wants to do is to go from a cubic (degree 3) Bezier curve to a
> quadratic (degree 2) Bezier curve, then there are standard
> algorithms for doing this quite simply.

The first sentence of my post to the original question:
"No doubt there are many ways to do the reduction."

The poster did not specify if he has a single cubic curve
that he wants to reduce to a single quadratic curve, or
if he has a piecewise cubic curve that he wants to reduce
to a piecewise quadratic curve.  My first post to his
question suggested algorithms for each.

Quote:> Robin Forrest gave the algorithm as early as 1972.

I think "the" should have been "an".  As I said, there
are many ways to do a reduction in degree.

Quote:> The technique is discussed, with a
> worked example, in the Introduction to NURBS, With Historical
> Perspective book (Section 3.13, p. 102)
> (www.nar-associates.com/nurbs).

I believe some time ago you also responded to one of
my posts where I suggested using a least-squares
method to minimize the L2 integral norm between the
original curve and its approximated curve, the response
being to use the "standard" algorithm by Piegl-Tiller
(as described in your book).  I am curious what objections,
if any, you have to the global least-squares approach.
This approach does not force you to use any of the original
knots.  You choose your "knot budget", so to speak, and
construct the approximation curve using a global measure
of error.  For a single cubic curve that can be exactly
reduced to a quadratic, the least-squares method produces
exactly that quadratic.

Quote:> Note that it is not possible to degree reduce all Bezier
> curves and that the reduction process is an approximation
> process.

The original poster already acknowledged that the
reduction may be an approximation.  Not sure what you
mean by "it is not possible to degree reduce all Bezier
curves".  You can always choose a smaller degree
Bezier curve as an approximation to a larger degree
one.  It is only a matter of how good/bad an approximation
your application is willing to tolerate.

--
Dave Eberly

http://www.magic-software.com

 
 
 

cubic bezier -> quadratic bezier

Post by willem veenhove » Sun, 31 Dec 2000 05:19:13




> > G'day,

> > [snip: what profs do all the time]

> I believe some time ago you also responded to one of my posts where
> I suggested using ...

Hi Dave,

I had the same experience with another 'prof' in this community, and I
am sure other serious posters did too. I guess the habit of ignoring
what you had written and bluntly posting a lecture from one of their
books just comes with the job ;)

But after all we all read those books, and therefore I think these
people also do a lot of good work for this group ...

willem

 
 
 

cubic bezier -> quadratic bezier

Post by PROF D. Rogers {EAS FA » Sun, 31 Dec 2000 13:16:53


G'day Willem,

I do believe that I acknowledged that I had not
been following the thread.

In addition, `profs' have a responsiblity to make
sure that people `educate' themselves. Many times
that means suggesting somewhere where the questioner
can find the answer rather than just giving it to them.

Finally, because I have CTS in both hands I cannot
type that much. Hence, I prefer to direct individuals
to work already available rather than type it all
here.

Sorry,

Dave Rogers





>> > G'day,

>> > [snip: what profs do all the time]

>> I believe some time ago you also responded to one of my posts where
>> I suggested using ...

>Hi Dave,

>I had the same experience with another 'prof' in this community, and I
>am sure other serious posters did too. I guess the habit of ignoring
>what you had written and bluntly posting a lecture from one of their
>books just comes with the job ;)

>But after all we all read those books, and therefore I think these
>people also do a lot of good work for this group ...

>willem

 
 
 

cubic bezier -> quadratic bezier

Post by Sigurd Lersta » Tue, 02 Jan 2001 16:38:02


Hello, thanks for answering.

I went to that page, but it wasn't clear to me what C source code did the
reduction, could it be that the reduction algorithm in C isn't available on
that page?

thanks again,

--
Sigurd Lerstad

Quote:> G'day,

> I have not been following this one closely but if all the poster
> wants to do is to go from a cubic (degree 3) Bezier curve to a
> quadratic (degree 2) Bezier curve, then there are standard
> algorithms for doing this quite simply. Robin Forrest gave the
> algorithm as early as 1972. The technique is discussed, with a
> worked example, in the Introduction to NURBS, With Historical
> Perspective book (Section 3.13, p. 102)
> (www.nar-associates.com/nurbs).
> It is also discussed in The NURBS Book (Section 5.6, p 212) in
> the context of degree reduction of a B-spline curve.

> Note that it is not possible to degree reduce all Bezier
> curves and that the reduction process is an approximation
> process.

> Dave Rogers

 
 
 

cubic bezier -> quadratic bezier

Post by Dave Eberl » Wed, 03 Jan 2001 12:58:07



Quote:> But after all we all read those books, and therefore I think these
> people also do a lot of good work for this group ...

This was not the tone I intended by my post.  I was not saying to Prof.
Rogers "don't post to this group"; I appreciate it when he does.  My point
was that sometimes CG folks just say "here is the standard algorithm".  I
like to rock the boat sometimes and propose alternate algorithms from the
perspective of a mathematician.  I really am curious why the "standard"
algorithms are presented as if they are the "best" choice.  (Another pet
peeve:  I dislike the question "What is the best way to do foo."  Computer
Science is the science of trade-offs.  "Best" is relative to what your
constraints are.  An algorithm that minimizes memory usage might not
minimize execution time, and vice versa.)

Regarding polynomial approximation, the earliest important result I know of
is the Weierstrass Theorem (from 1885, a bit before the 1972 result by R.
Forrest, although the 1972 result is specialized):  If f(x) is a continous
function on [a,b], and if e > 0 is arbitrarily small, there exists an n-th
degree polynomial p(x) such that |f(x)-p(x)| <= e for all x in [a,b].
Effectively, this says that you select the maximum error e that you can
tolerate.  There must be a polynomial p(x) (generally n becomes quite large
for e small) for which the L-infinity norm of the difference between f and p
is bounded by the specified error term.  Variations on this theorem include
the popular L2 norm, the bound being Integral([a,b]) |f(x)-p(x)|^2 dx <= e.
What the Weierstrass Theorem says is that the polynomials form a dense
subset of the continuous functions on [a,b].  However, if you want the
degree n to be fixed, the set of n-th degree polynomials is not dense.  The
natural question is to ask which of the n-th degree polynomials minimizes
the L2 norm of f-p, so you now have a least-squares problem that I proposed
earlier as a solution to the original poster's problem.

Regarding degree reduction, there are typically two goals.  One is to reduce
the memory usage (fewer control points), the other is to speed-up execution
(lower degree polynomials are faster to evaluate than higher degree
polynomials.  But just as important is:  How much error is there between the
approximation and the original function.  While Prof. Rogers book mentions
the parametric error for the Piegl-Tiller, there is no analysis given to
measure any type of "global error" (as the Lp norms provide).  The reason I
like the least-squares solution is that the global error is mathematically
quantifiable.  Moreover, you specify the error *first* and construct an
approximation that produces no more error than that amount.  An a posteriori
error bound is less appealing to my mathematical inclinations.

And for the record, Prof. Rogers book "An Introduction to NURBS:  A
Historical Perspective" is an excellent book that provides an "engineering"
approach to the topic--good for the practitioner.  If you prefer a more
mundane and highly mathematical approach, try Farin's "NURBS" book, but it
is not really for the mathematical faint-of-heart.  (I like both books.)

--
Dave Eberly

http://www.magic-software.com

 
 
 

cubic bezier -> quadratic bezier

Post by PROF D. Rogers {EAS FA » Thu, 04 Jan 2001 12:14:51



G'day,

No, there is not C source code on that page for knot removal. I
don't think I implemented it in C. However, there is pseudocode
in the book in Section 3.15 that can be used to implement the C
code. There is also an actual C code listing in the original 1992
Tiller paper that is even a bit more general.

Here is the complete reference

Tiller, W., Knot-removal algorithms for NURBS curves and
surfaces, CAD, Vol. 24, No. 8, pp. 445-453, 1992

Sorry if I mislead you.

Dave Rogers

!Hello, thanks for answering.
!
!I went to that page, but it wasn't clear to me what C source code did the
!reduction, could it be that the reduction algorithm in C isn't available on
!that page?
!
!thanks again,
!
!--
!Sigurd Lerstad
!
!! G'day,
!!
!! I have not been following this one closely but if all the poster
!! wants to do is to go from a cubic (degree 3) Bezier curve to a
!! quadratic (degree 2) Bezier curve, then there are standard
!! algorithms for doing this quite simply. Robin Forrest gave the
!! algorithm as early as 1972. The technique is discussed, with a
!! worked example, in the Introduction to NURBS, With Historical
!! Perspective book (Section 3.13, p. 102)
!! (www.nar-associates.com/nurbs).
!! It is also discussed in The NURBS Book (Section 5.6, p 212) in
!! the context of degree reduction of a B-spline curve.
!!
!! Note that it is not possible to degree reduce all Bezier
!! curves and that the reduction process is an approximation
!! process.
!!
!! Dave Rogers
!
!
!