Degree Elevation

Usage of a PySide6 Example

Before I go into any details about programming or the tools/libraries used, let’s look at the user interface of a simple program I wrote about Bezier Curves and Degree Elevation:

The programm starts with a simple line between two circles. The circles are kind of handles, because you can select them and move them around. Later we will refer to them as Control Vertices (or CVs).

If we press the + key, we get a third handle or CV which I moved a bit in the screenshot above to get a degree 2 Bezier curve.

Pressing + again will not change the shape of the curve, but add another CV, so we have 4 CVs in total:

This algorithm to create an additional CV without changing the shape of the curve is called Degree Elevation.

Degree 3 curves are the most commonly used Bezier curves because they do have 4 CVs and that allows us to leave the plane and create real 3-dimensional curves. We also hear the term order a lot, which are simply the number of CVs you need to define a (order - 1) Bezier curve. Here we are not able to leave the plane (or canvas) but we can create a sine or cosine like curve:

You could think about a hair rubber band which you would stretch and place over the four CVs (which could be e.g. pins on a pinboard) or connect all CVs with each other (instead of just connecting the consecutive CVs). That area covered by all four CVs can be called convex hull and Bezier (as well as B-Spline) curves (and surfaces) are known to be completely inside their convex hulls.

If you press + again and again until you end up with a Bezier curve of order 10 you will notice that the polyline defined by consecutive CVs is converging against the Bezier curve itself. You could use that fact for example to judge how many points you would need to calculate on a Bezier curve to always end up with a “smooth” representation of the curve through many points of a polyline (connected by tiny straight lines). You would degree elevate a couple of times and calculate the length of the polyline (of the CVs) e.g. in pixels on a screen.

The Python Code

I do not want to go into much details of the source code (written in Python), but I just want to mention that I used PySide6, which allows you to use the C++ library Qt from within the Python programming language.

        # draw path
        pen = QPen()
        painter.strokePath(path, pen)
        if len(self.points) >= 3:
            spline = QPainterPath()
            pen = QPen()
            d = 0.0
            for i in range(len(self.points) - 1):
                d += QLineF(self.points[i], self.points[i+1]).length()
            d = int(d / float(len(self.points) - 1))
            for i in range(d + 1):
                t = float(i) / float(d)
                p = bezier(self.points, t)
                if i == 0:
                    spline.moveTo(p)
                else:
                    spline.lineTo(p)
            painter.strokePath(spline, pen)

The code above creates a Qt pen, and draws a (painter) path (or polyline) by first moving the pen to the location of the first CV, calculating a bunch of points on a Bezier curve (defined by the CVs), and connecting those by drawing a line between two consecutive points.

        if key == QtCore.Qt.Key_Plus:
            # add new point
            if len(self.points) == 2:
                point1 = self.points[0]
                point2 = self.points[1]
                newPoint = (point1 + point2) / 2.0
                self.points.insert(1, newPoint)

We started with a simple line (Bezier curve of degree 1 or order 2). If we press the + key on the keyboard we simply divide the line between both CVs and insert the new CV in the middle. Obviously this will still look like a line until you move the middle CV.

            else:
                newPoints = []
                newPoints.append(self.points[0])
                degree = len(self.points) - 1
                for i in range(degree):
                    t = 1.0 - float(i + 1) / float(degree + 1)
                    newPoints.append(self.points[i] * (1.0 - t) +
                                     self.points[i+1] * t)
                newPoints.append(self.points[-1])
                self.points = newPoints

Doing this for higher order Bezier curves is only slightly more complicated. Based on the degree or order of the Bezier curve you start dividing consecutive lines between CVs, e.g. for the degree 2 curve above you divide the first line and place the new CV at 2/3 of the original distance. The new third CV will be 1/3 of the distance between the second and third CV of the original curve. You will end up with the four CVs shown above, defining a degree 3 curve with the same shape.

def bezier(points, t):
    cvs = points[:]
    while len(cvs) >= 2:
        newCvs = []
        for i in range(len(cvs) - 1):
            newCvs.append(cvs[i] * (1.0 - t) + cvs[i+1] * t)
        cvs = newCvs
    p = cvs[0]
    return p

Calculating a point on the Bezier curve (defined for a parameter t varying between zero and one) is pretty much a similar process. For calculating e.g. a point for t=0.5 on a degree 3 Bezier curve (using 4 CVs) you would divide the three lines (connecting the four CVs) in the middle. The newly created points get connected to two lines, divided again, so we create another line, and finally dividing that last line will calculate the point on the curve. This can be done in a similar way for any t between zero and one and any degree or order. Connecting many points calculated that way for e.g. t=0.1, 0.2, 0.3, …, 1.0 will approximate the curve by a polyline. If you choose the step small enough you will not see any straight lines anymore, because the distance between two consecutive points is about a pixel width.

The remaining source code can be found and studied here. In a future blog I will talk about calculating those points multi-threaded using another programming language, called Rust and how to mix Python and Rust, so Python can be used for the graphical user interface (using the Qt library), and Rust can be used for speeding up algorithms regarding Bezier, B-Spline, and NURBS curves and surfaces.