Question about the implementation of Bezier Curves?

Question

I have read some tutorials for bezier curve such as this one http://www.codeproject.com/KB/recipes/BezirCurves.aspx.

The basic idea to create bezier curve is to use some control points and make decision how many new points need to be created. And then interpolate those new points.

Here is the question:

Assume I have 1000 points and I would like to interpolate 2000 points more. The number of control points I want to use is 5. The parameter t is in the range of [0, 1].

Givens points P0, P1, P2, P3, P4, P5, P6, ...P1000. I can use P0-P4 to generate new points, then what's next? use P5-P9 to generate new points??? I can immediately see there is a sudden transform between P4 and P5.

How can I solve this issue?

Thank you

///////////////////////////////////////////////////// Hello Stargazer712,

I understand your comments until it reaches the implementation method.

Assume we have the following points:

A1->A2->A3->A4->A5->A6->A7->A8 initial points

You said that we need to add a new point at the midpoint of every other pair.

My question is what the order of the new point is?

Let use use this annotation (A1+A3)/2 == A12

Now generated new points are

A13 A24 A35 A46 A57 A68 (this is what you mean "every other pair"?

Where should I insert those points into the original list?

The contour I am working on is extracted from binary image. The generated contour is zig-zag shape. After I apply this smooth method, it shape doesn't improve too much. I think the major reason is that the neighbors are near each other and make the interpolation not that useful.

Thank you

////////////////////////////////////////////////////

Answer 1

I think what you are trying to do is to create a smooth curve interpolating the points. To do this, you need to understand the following about Bezier curves:

Say we have two curves with points A1, A2, A3, A4, and B1, B2, B3, and B4.

If the two curves end on the same point, and if the last control point of the first is colinear with the first control point of the next, then the curves will be smooth. So in our example, if:

• A4 == B1
• A3, A4, and B2 are colinear (same as saying A3, B1, B2 are colinear)

Then the curves will be smooth.

In order to take an arbitrary list of points and make a smooth curve, we need to force these two conditions to be true.

To do this, lets say that we start with a set of points:

To force the above conditions, lets add some extra points. We'll place a new point at the midpoint of every other pair as shown:

We can now draw bezier curves between points 0-3, 3-6, 6-9, etc., and we can be sure that it will form a smooth curve:

Hope this helps!

EDIT: Here's a simple python program that implements exactly what was shown above (and I mean exactly). You need to have python and PIL installed:

from PIL import Image
import math

#
#   draws a single point on our image
#
def drawPoint( img, loc, size=5, color=(0,0,0) ):
    px = img.load()
    for x in range(size):
        for y in range(size):
            xloc = loc[0] + x - size/2
            yloc = loc[1] + y - size/2
            px[ xloc, yloc ] = color


#
#   draws a simple bezier curve with 4 points
#            
def drawCurve( img, points ):

    steps = 20
    for i in range(steps):

        t = i / float(steps)

        xloc = math.pow(1-t,3) * points[0][0] \
             + 3*t*math.pow(1-t,2) * points[1][0] \
             + 3*(1-t)*math.pow(t,2) * points[2][0] \
             + math.pow(t,3) * points[3][0]
        yloc = math.pow(1-t,3) * points[0][1] \
             + 3*t*math.pow(1-t,2) * points[1][1] \
             + 3*(1-t)*math.pow(t,2) * points[2][1] \
             + math.pow(t,3) * points[3][1]

        drawPoint( img, (xloc,yloc), size=2 )


#
#   draws a bezier curve with any number of points
#
def drawBezier( img, points ):

    for i in range(0,len(points),3):
        if( i+3 < len(points) ):
            drawCurve( img, points[i:i+4] )


#
#   draws a smooth bezier curve by adding points that
#   force smoothness
#
def drawSmoothBezier( img, points ):

    newpoints = []

    for i in range(len(points)):

        # add the next point (and draw it)
        newpoints.append(points[i])
        drawPoint( img, points[i], color=(255,0,0) )

        if( i%2 == 0 and i>0 and i+1<len(points) ):

            # calculate the midpoint
            xloc = (points[i][0] + points[i+1][0]) / 2.0
            yloc = (points[i][1] + points[i+1][1]) / 2.0

            # add the new point (and draw it)
            newpoints.append( (xloc, yloc) )
            drawPoint( img, (xloc, yloc), color=(0,255,0) )

    drawBezier( img, newpoints )



#   Create the image
myImage = Image.new("RGB",(627,271),(255,255,255))

#   Create the points
points = [  (54,172), 
            (121,60), 
            (220,204), 
            (284,56), 
            (376,159), 
            (444,40), 
            (515,228), 
            (595,72) ]

#   Draw the curve
drawSmoothBezier( myImage, points )

#   Save the image
myImage.save("myfile.png","PNG")

The line will follow the pattern of the points. If your result is zig-zagged, that's because that's what the lines looked like.