Drawing a clamped uniform cubic B-spline using Cairo

Question

I have a bunch of coordinates which are the control points of a clamped uniform cubic B-spline on the 2D plane. I would like to draw this curve using Cairo calls (in Python, using Cairo's Python bindings), but as far as I know, Cairo supports Bézier curves only. I also know that the segments of a B-spline between two control points can be drawn using Bézier curves, but I can't find the exact formulae anywhere. Given the coordinates of the control points, how can I derive the control points of the corresponding Bézier curves? Is there any efficient algorithm for that?

Answer 1

Does Converting B-spline curve to Bezier spline curve help?

Answer 2

Okay, so I searched a lot using Google and I think I came up with a reasonable solution that is suitable for my purposes. I'm posting it here - maybe it will be useful to someone else as well.

First, let's start with a simple Point class:

from collections import namedtuple

class Point(namedtuple("Point", "x y")):
    __slots__ = ()

    def interpolate(self, other, ratio = 0.5):
        return Point(x = self.x * (1.0-ratio) + other.x * float(ratio), \
                     y = self.y * (1.0-ratio) + other.y * float(ratio))

A cubic B-spline is nothing more than a collection of Point objects:

class CubicBSpline(object):
    __slots__ = ("points", )

    def __init__(self, points):
        self.points = [Point(*coords) for coords in points]

Now, assume that we have an open uniform cubic B-spline instead of a clamped one. Four consecutive control points of a cubic B-spline define a single Bézier segment, so control points 0 to 3 define the first Bézier segment, control points 1 to 4 define the second segment and so on. The control points of the Bézier spline can be determined by linearly interpolating between the control points of the B-spline in an appropriate way. Let A, B, C and D be the four control points of the B-spline. Calculate the following auxiliary points:

1. Find the point which divides the A-B line in a ratio of 2:1, let it be A'.
2. Find the point which divides the C-D line in a ratio of 1:2, let it be D'.
3. Divide the B-C line into three equal parts, let the two points be F and G.
4. Find the point halfway between A' and F, this will be E.
5. Find the point halfway between G and D', this will be H.

A Bézier curve from E to H with control points F and G is equivalent to an open B-spline between points A, B, C and D. See sections 1-5 of this excellent document. By the way, the above method is called Böhm's algorithm, and it is much more complicated if formulated in a proper mathematic way that accounts for non-uniform or non-cubic B-splines as well.

We have to repeat the above procedure for each group of 4 consecutive points of the B-spline, so in the end we will need the 1:2 and 2:1 division points between almost any consecutive control point pairs. This is what the following BSplineDrawer class does before drawing the curves:

class BSplineDrawer(object):
    def __init__(self, context):
        self.ctx = context

    def draw(self, bspline):
        pairs = zip(bspline.points[:-1], bspline.points[1:])
        one_thirds = [p1.interpolate(p2, 1/3.) for p1, p2 in pairs)
        two_thirds = [p2.interpolate(p1, 1/3.) for p1, p2 in pairs)

        coords = [None] * 6
        for i in xrange(len(bspline.points) - 3):
            start = two_thirds[i].interpolate(one_thirds[i+1])
            coords[0:2] = one_thirds[i+1]
            coords[2:4] = two_thirds[i+1]
            coords[4:6] = two_thirds[i+1].interpolate(one_thirds[i+2])

            self.context.move_to(*start)
            self.context.curve_to(*coords)
            self.context.stroke()

Finally, if we want to draw clamped B-splines instead of open B-splines, we simply have to repeat both endpoints of the clamped B-spline three more times:

class CubicBSpline(object):
    [...]
    def clamped(self):
        new_points = [self.points[0]] * 3 + self.points + [self.points[-1]] * 3
        return CubicBSpline(new_points)

Finally, this is how the code should be used:

import cairo

surface = cairo.ImageSurface(cairo.FORMAT_ARGB32, 600, 400)
ctx = cairo.Context(surface)

points = [(100,100), (200,100), (200,200), (100,200), (100,400), (300,400)]
spline = CubicBSpline(points).clamped()

ctx.set_source_rgb(0., 0., 1.)
ctx.set_line_width(5)
BSplineDrawer(ctx).draw(spline)