Any royal road to Bezier curves...?

[Warren Francis]

I'm fairly new to Python (2-3 months) and I'm trying to figure out a simple
way to implement Bezier curves... So far I've tried the following:

http://runten.tripod.com/NURBS/
....which won't work because the only compiled binaries are for Windows 2000,
python 2.1. I'm on Windows XP (for now), using Python 2.4. I downloaded
the source distribution, but the header files aren't included, so I'm not
sure how to compile it.

It appears there's some bezier functionality in the python that comes
Blender... but I'm not savvy enough yet to try and extract whatever makes
beziers work there, to make it work in my general-purpose Python programs.

Basically, I'd like to specify a curved path of an object through space. 3D
space would be wonderful, but I could jimmy-rig something if I could just
get 2D... Are bezier curves really what I want after all?

Any thoughts would be much appreciated. I've got some ideas I want to test,
but if I can't find a simple implementation of curves, I'm going to get so
bogged down in trying to do that part, I'll never get to what I'm excited
about.

Warren

 

[Robert Kern]

I'm fairly new to Python (2-3 months) and I'm trying to figure out a simple
way to implement Bezier curves... So far I've tried the following:

http://runten.tripod.com/NURBS/
...which won't work because the only compiled binaries are for Windows 2000,
python 2.1. I'm on Windows XP (for now), using Python 2.4. I downloaded
the source distribution, but the header files aren't included, so I'm not
sure how to compile it.

It appears there's some bezier functionality in the python that comes
Blender... but I'm not savvy enough yet to try and extract whatever makes
beziers work there, to make it work in my general-purpose Python programs.

Basically, I'd like to specify a curved path of an object through space. 3D
space would be wonderful, but I could jimmy-rig something if I could just
get 2D...

There's some 2D code (which could be trivially adapted to 3D) in
PIDDLE/Sping. In the latest Sping download, look in the file pid.py at
the Canvas.curvePoints() method.

http://piddle.sourceforge.net/

Are bezier curves really what I want after all?

I dunno. It depends on how much flexibility you need.

--
Robert Kern
(e-mail address removed)

"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter

 

[Terry Hancock]

I'm fairly new to Python (2-3 months) and I'm trying to
figure out a simple way to implement Bezier curves... So
far I've tried the following:

http://runten.tripod.com/NURBS/
...which won't work because the only compiled binaries are
for Windows 2000, python 2.1. I'm on Windows XP (for
now), using Python 2.4. I downloaded the source
distribution, but the header files aren't included, so I'm
not sure how to compile it.

NURBS are not actually Bezier curves, AFAIK, they are a
superset of some kind (which means they're probably better
to use, but harder to implement).

It appears there's some bezier functionality in the python
that comes Blender... but I'm not savvy enough yet to try
and extract whatever makes beziers work there, to make it
work in my general-purpose Python programs.

Not a specific recommendation, and I don't know if it's
any more comprehensible, but you will find that Skencil also
implements Bezier curves (in 2D). Skencil is mostly in
Python, but uses a lot of C, so I don't know if it handles
beziers in Python or C (I'm still learning my way around the
code, myself).

Inkscape, of course, does too, but in C.
http://www.inkscape.org

Basically, I'd like to specify a curved path of an object
through space. 3D space would be wonderful, but I could
jimmy-rig something if I could just get 2D... Are bezier
curves really what I want after all?

Or NURBS, yeah, probably.

 

[Tom Anderson]

Basically, I'd like to specify a curved path of an object through space.
3D space would be wonderful, but I could jimmy-rig something if I could
just get 2D... Are bezier curves really what I want after all?

No. You want a natural cubic spline:

http://mathworld.wolfram.com/CubicSpline.html

This is a fairly simple curve, which can be fitted through a series of
points (called knots) in space of any dimensionality, without the need to
specify extra control points (unlike a Bezier curve), and which has the
nice property of minimising the curvature of the curve - it's the shape
you'd get if you ran a springy wire through your knots. It usually looks
pretty good too.

Google will help you find python implementations.

There are other kinds of splines - Catmull-Rom, B-spline (a generalisation
of a Bezier curve), Hermite - but they mostly don't guarantee to pass
through the knots, which might make them less useful to you.

In the opposite direction on the mathematical rigour scale, there's what i
call the blended quadratic spline, which i invented as a simpler and more
malleable alternative to the cubic spline. It's a piecewise parametric
spline, like the cubic, but rather than calculating a series of pieces
which blend together naturally, using cubics and linear algebra, it uses
simple quadratic curves fitted to overlapping triples of adjacent knots,
then interpolates ('blends') between them to draw the curve. It looks very
like a cubic spline, but the code is simpler, and the pieces are local -
each piece depends only on nearby knots, rather than on all the knots, as
in a cubic spline - which is a useful property for some jobs. Also, it's
straightforward to add the ability to constrain the angle at which the
curve passes through a subset of the knots (you can do it for some knots,
while leaving others 'natural') by promoting the pieces to cubics at the
constrained knots and constraining the appropriate derivatives. Let me
know if you want more details on this. To be honest, i'd suggest using a
proper cubic spline, unless you have specific problems with it.

tom

 

[Tom Anderson]

No. You want a natural cubic spline:

In a fit of code fury (a short fit - this is python, so it didn't take
long), i ported my old java code to python, and tidied it up a bit in the
process:

http://urchin.earth.li/~twic/splines.py

That gives you a natural cubic spline, plus my blended quadratic spline,
and a framework for implementing other kinds of splines.

tom

 

[Scott David Daniels]

The Bezier gives control points with natural interpretations and a
nice "within the convex hull" property. I happen to like Beziers to
control curves which are aestheticly, rather than computationally
defined.

 

[Claudio Grondi]

http://en.wikipedia.org/wiki/De_Casteljau's_algorithm

has a Python example implementation of qubic Bezier curves available.

Claudio

 

[Claudio Grondi]

http://en.wikipedia.org/wiki/De_Casteljau's_algorithm

has a Python example implementation of qubic Bezier curves available.

Here my port to Tkinter (doesn't need PIL)

from Tkinter import *
master = Tk()
objTkCanvas = Canvas(master, width=110, height=180)
objTkCanvas.pack()

def midpoint((x1, y1), (x2, y2)):
return ((x1+x2)/2, (y1+y2)/2)

MAX_LEVEL = 5
def drawCubicBezierCurveToCanvas(P1, P2, P3, P4, level=1):
# global MAX_LEVEL
# global objTkCanvas
if level == MAX_LEVEL:
objTkCanvas.create_line(P1[0],P1[1],P4[0],P4[1], fill='red', width=1.5)
else:
L1 = P1
L2 = midpoint(P1, P2)
H = midpoint(P2, P3)
R3 = midpoint(P3, P4)
R4 = P4
L3 = midpoint(L2, H)
R2 = midpoint(R3, H)
L4 = midpoint(L3, R2)
R1 = L4
drawCubicBezierCurveToCanvas(L1, L2, L3, L4, level+1)
drawCubicBezierCurveToCanvas(R1, R2, R3, R4, level+1)
#:if/else level == MAX_LEVEL
#:def draw_curve(P1, P2, P3, P4, level=1)

objTkCanvas.create_rectangle(10, 10, 100, 100, fill="yellow")
objTkCanvas.create_line( 10, 20, 100, 20, fill="green")
objTkCanvas.create_line( 10, 30, 100, 30, fill="green")
objTkCanvas.create_line( 10, 40, 100, 40, fill="green")
objTkCanvas.create_line( 10, 50, 100, 50, fill="green")
objTkCanvas.create_line( 10, 60, 100, 60, fill="green")
objTkCanvas.create_line( 10, 70, 100, 70, fill="green")
objTkCanvas.create_line( 10, 80, 100, 80, fill="green")
objTkCanvas.create_line( 10, 90, 100, 90, fill="green")
objTkCanvas.create_line( 20, 10, 20, 100, fill="green")
objTkCanvas.create_line( 30, 10, 30, 100, fill="green")
objTkCanvas.create_line( 40, 10, 40, 100, fill="green")
objTkCanvas.create_line( 50, 10, 50, 100, fill="green")
objTkCanvas.create_line( 60, 10, 60, 100, fill="green")
objTkCanvas.create_line( 70, 10, 70, 100, fill="green")
objTkCanvas.create_line( 80, 10, 80, 100, fill="green")
objTkCanvas.create_line( 90, 10, 90, 100, fill="green")

drawCubicBezierCurveToCanvas((10,10),(100,100),(100,10),(100,100))

objTkCanvas.create_text( 10, 130, anchor='sw', text='Bezier curve:',
font='Arial 10')
objTkCanvas.create_text( 10, 140, anchor='sw', text=' P1=( 10, 10)',
font='Courier 8')
objTkCanvas.create_text( 10, 150, anchor='sw', text=' P2=(100,100)',
font='Courier 8')
objTkCanvas.create_text( 10, 160, anchor='sw', text=' P3=(100, 10)',
font='Courier 8')
objTkCanvas.create_text( 10, 170, anchor='sw', text=' P4=(100,100)',
font='Courier 8')

mainloop() # show the Tkinter window with the diagram of the cubic Bezier
curve

 

[Warren Francis]

For my purposes, I think you're right about the natural cubic splines.
Guaranteeing that an object passes through an exact point in space will be
more immediately useful than trying to create rules governing where control
points ought to be placed so that the object passes close enough to where I
intended it to go. Thanks for the insight, I never would have found that on
my own. At least not until Google labs comes out with a search engine that
gives names for what you're thinking of. ;-)

I know this is a fairly pitiful request, since it just involves parsing your
code, but I'm new enough to this that I'd benefit greatly from an couple of
lines of example code, implementing your classes... how do I go from a set
of coordinates to a Natural Cubic Spline, using your python code?

Thanks for all the help, everybody!

Warren

 

[Tom Anderson]

For my purposes, I think you're right about the natural cubic splines.
Guaranteeing that an object passes through an exact point in space will
be more immediately useful than trying to create rules governing where
control points ought to be placed so that the object passes close enough
to where I intended it to go.

Right so. I wrote that code the first time when i was in a similar spot
myself - trying to draw maps with nice smooth roads etc based on a fairly
sparse set of points - so i felt your pain.

Thanks for the insight, I never would have found that on my own. At
least not until Google labs comes out with a search engine that gives
names for what you're thinking of. ;-)

You're in for a wait - i think that feature's scheduled for summer 2006.

I know this is a fairly pitiful request, since it just involves parsing
your code, but I'm new enough to this that I'd benefit greatly from an
couple of lines of example code, implementing your classes... how do I
go from a set of coordinates to a Natural Cubic Spline, using your
python code?

Pitiful but legit - i haven't documented that code at all well. If you go
right to the foot of my code, you'll find a simple test routine, which
shows you the skeleton of how to drive the code. It looks a bit like this
(this is slightly simplified):

def test_spline():
knots = [(0, 0), (0, 1), (1, 0), (0, -2), (-3, 0)] # a spiral
trace = []
c = NaturalCubicSpline(tuples2points(knots))
u = 0.0
du = 0.1
lim = len(c) + du
while (u < lim):
p = c(u)
trace.append(tuple(p))
u = u + du
return trace

tuples2points is a helper function which turns your coordinates from a
list of tuples (really, an iterable of length-2 iterables) to a list of
Points. The alternative way of doing it is something like:

curve = NaturalCubicSpline()
for x, y in knot_coords:
curve.knots.append(Point(x, y))
do_something_with(curve)

tom

 

[Warren Francis]

If you go right to the foot of my code, you'll find a simple test routine,

which shows you the skeleton of how to drive the code.

Oops... my request just got that much more pitiful. Thanks for the
help.

Warren

 

[Scott David Daniels]

For my purposes, I think you're right about the natural cubic splines.
Guaranteeing that an object passes through an exact point in space will be
more immediately useful than trying to create rules governing where control
points ought to be placed so that the object passes close enough to where I
intended it to go. Thanks for the insight, I never would have found that on
my own. At least not until Google labs comes out with a search engine that
gives names for what you're thinking of. ;-)

I know this is a fairly pitiful request, since it just involves parsing your
code, but I'm new enough to this that I'd benefit greatly from an couple of
lines of example code, implementing your classes... how do I go from a set
of coordinates to a Natural Cubic Spline, using your python code?

Thanks for all the help, everybody!

Warren

Half the points on a cubic Bezier curve are knots -- points through
which the curve must pass. If you have four points for a bezier:
a
d
b c

Then the curve must pass through a and d, and it should be tangent
to a-b at a, and tangent to c-d at d. All parts of the curve must lie
within the convex hull of a-b-c-d (that is, the largest quadrilateral
with those four corners). It is simple to subdivide a bezier curve into
a pair that produce the same curve (so you can cut them nicely). If you
connect two curves together, the tangent requirement is enough to make the
joint look smooth:

a e f
d
b c g

In this diagram, there are two curves: a-b-c-d and d-e-f-g. If c-d-e is
a line, then the connection will look smooth.

This is why it is so easy to work with beziers, lots of properties make
visual sense. In fact I've even used the bezier algorithm to control
not only x, y, and z, but also r, g, and b. Controlling all six, I can
enforce smooth controllable color transitions that I can even tweak to
satisfy my visual aesthetic. The convex hull property guarantees me
that all colors will exit. Knots-only systems go outside the hulls,
so colors don't make as much sense.

--Scott David Daniels
(e-mail address removed)