Midpoint Algorithm (Divide and Conquer Method) for Drawing a Simple Bezier Curve

• Download demo - 7.45 KB
• Download source - 17.6 KB

Introduction

A Bezier curve is a parametric curve frequently used in computer graphics and related fields. In vector graphics, Bezier curves are used to model smooth curves that can be scaled indefinitely. There are many ways to construct a Bezier curve. This simple program uses the midpoint algorithm of constructing a Bezier curve. To show the nature of the divide and conquer approach in the algorithm, a recursive function has been used to implement the construction of the piece of Bezier curve.

Constructing a Bezier Curve

This program builds a Bezier curve based on three points that can be adjusted manually. The below animation shows what exactly happens in the code while we construct a Bezier curve with two iterations of the midpoint method.

The points that are shown in red are the initial points. After giving the initial points, it calculates the mid points of each line that lies between the three initial points. These newly calculated mid points are shown in green. The points that turn their color to blue will be on the final Bezier curve. The order of the color changing is identical to the order of calculating points for the Bezier curve in the code. The Bezier curve that is approximated using the given points and two iterations is shown by a set of straight lines with the color red.

Using the Code

Classes

• Class BezierCurve: The class that is responsible for constructing the Bezier curve.
• Class CustomCanvas: The class that is responsible for the graphical view and points manipulation of the curve.

Functions

private void CreateBezier(PointF ctrl1, PointF ctrl2, PointF ctrl3)
{
    bezierPoints = new List<PointF>();
    bezierPoints.Clear();
    bezierPoints.Add(ctrl1); // add the first control point
    PopulateBezierPoints(ctrl1, ctrl2, ctrl3, 0);
    bezierPoints.Add(ctrl3);// add the last control point
}

This function takes three points as parameters and then populates the list of points of the curve. The point ctrl1 (point in the starting end of the curve) is obviously in the curve so it is added to the list without doing any calculation. Then it invokes the function PopulateBezierPoints to calculate the rest of the points on the curve. Finally, the point ctrl3 is added to the list because obviously it is the point at the other end of the curve.

private void PopulateBezierPoints(PointF ctrl1, PointF ctrl2, 
             PointF ctrl3, int currentIteration)
{
    if (currentIteration < iterations)
    {
        //calculate next mid points
        PointF midPoint1 = MidPoint(ctrl1, ctrl2);
        PointF midPoint2 = MidPoint(ctrl2, ctrl3);
        PointF midPoint3 = MidPoint(midPoint1, midPoint2); 
                //the next control point
        currentIteration++;
        PopulateBezierPoints(ctrl1, midPoint1, 
                             midPoint3, currentIteration);//left branch
        bezierPoints.Add(midPoint3); 
                //add the next control point
        PopulateBezierPoints(midPoint3, midPoint2, ctrl3, currentIteration);
                //right branch
    }
}

This function takes the three initial points with the currentIteration number as the parameter. This function is recursively called and at the beginning, the current iteration number is zero. The number of iterations in the algorithm should be set before invoking this function.

This function simply gets the midpoint of the first two points, the midpoint of the last two points from the given three points, and the midpoint of the above two new midpoints if currentIteration is less than the number of iterations that is to be iterated in the algorithm (the value of the variable iterations is the value that has been selected by the user from the user interface). After calculating the three new midpoints, we get a pair of three points. One set of points in this pair is to construct the left part of the curve and the other set of points is for constructing the right part of the curve. According to the order of invoking this recursive function, it adds the points in the curve from the left part to the right part of the curve to the list. You can refer to the above animation to get a better idea of the order of execution of this function.

private PointF MidPoint(PointF controlPoint1, PointF controlPoint2)
{
    return new PointF(
    (controlPoint1.X + controlPoint2.X) / 2,
    (controlPoint1.Y + controlPoint2.Y) / 2
    );
}

This function takes two points as parameters and returns the midpoint of them.

How to Use

The program allows you to specify the three initial points and the number of iterations. Then you can observe the smoothness and the number of points on the Bezier curve. In addition to that, you can move the initial points by dragging them.

Remarks

Use of a recursion function for constructing a Bezier curve is not practical when the curve becomes more complex and smoother. In a such case, we have to use some efficient methods to construct a Bezier curve.