Graphics


Smoothing Algorithm Using Bézier Curves

by Jean-Yves Quéinec


Introduction

I needed a smoothing algorithm for my LQprofil program. LQprofil is designed for scale modelers, who have to draw and print airfoils templates, i.e., a plate cut to the shape used to build scaled airfoils sections. An airfoils section (such as NACA airfoils) is defined by an array of points. I tried existing routines, but none gave good results for me. Some of them produced less or excessive smoothed curves, and frequently the smoothed curves didn't go through the defined points. I decided to create my own algorithm, with a smoothing factor, and draw curves exactly through the points. Bézier curves seemed to be suitable to solve the problem.

Bézier Curves

Pierre Bézier was a French engineer who was working the Renault company. Bézier equations uses 4 points: two points of the curve (P1 and P4) and two control points (see the diagram below).  P2 is located at the "right" side of P1, and P3 is located at the "left" side of P4.

Bézier equations are parametric equations  in a variable t, and are symmetrical relative to x and y:

Bx(t) = (1-t)3  x P1x + 3 x (1-t)2 x t x P2x + 3 x (1-t) x t2 x P3x + t3 x P4x
By(t) = (1-t)3  x P1y + 3 x (1-t)2 x t x P2y + 3 x (1-t) x t2 x P3y + t3 x P4y

The above figure shows a geometrical construction for points P1, P2, P3, and P4 with t = 0.5.

The t parameter (varying from 0 to 1) cuts the P1-P4 segment to intervals, according to the wanted accuracy.
When t = 0 results are B.x = P1.x and By= P1.y
When t = 1 results are B.x = P4.x and By= P4.y

If one has NB1 points for the curve, one needs a total of NB2 = NB1*3 +1 points, because between each point P of the curve we have to build two control points named PC1 and PC2. The points of the curve, and associated control points, are stored in the BB array of Tpoints BB := array[0..NB2] of Tpoints.

One can say that a P point of the curve, which is not an end point, has a prior "left" control point of P2 type, and has a next "right" control point of P1 type. The Bézier curve goes through the P1 and P4 points, and the curve appearance depends on the two control points, P2 and P3. To solve the curve smoothing problem, we have to find a method for building the control points P2 and P3.

First approach

To smooth the Pn edges of the green polyline, one can intuitively imagine that the smoothing curve should be tangent to a segment, which is parallel to the segment (Pn-3, Pn+3). It joins the prior and next points relative to the current point. The above figure shows how to draw the PC1 control point, located to the "right" of the curve point Pn. S1a is the middle of the Pn S1 segment and PC1 is located on the segment (S1a , Pn+3). The length of the (S1a , PC1) segment is about 1/3 of the (S1, Pn+3) segment length.

In brief :

The particular case of the end points (n= 0 and n = NB2) offers 2 possibilities depending on whether the curve is closed or open. When the curve is closed, P(0) = P(NB), one can execute the smoothing algorithm because the next and prior points are known. When the curve is open P(0) has no prior PC2 point. We shall consider that PC2 and P(0) are the same. Idem for the PC1 conrol point of the last point P(NB2).

This method gives some good results with simple curves, but doesn't work fine in all cases. For example, a hexagon is transformed into a potatoïd (looks like a potato). The next step will try find a more flexible solution. For example, the algorithm should be able to transform progressively a square to a circle.

Geometrical control points construction

This geometrical solution is completely empirical, but gives excellent results.

  1. S1 is the symmetrical point of P[n-1] in relation to P[n]
  2. S2 is the symmetrical point of P[n+2] in relation to P[n]
  3. S1a and S2a are the homothetical points of S1 and S2 with a smooth factor varying from 0.0 to 1.5. This allows to weight the prior and next points positions before drawing the curve. A smooth factor of zero produces a straight line P[n], P[n+1]. the figure above shows a smooth factor of 0.75.
    A smooth of factor excessively curves the line. A smooth factor of 1.05 produces a circle from a square.
  4. M is the middle point of the segment P[n-1] , P[n]
  5. S1b is the middle point of the segment S1a , P[n-1]
  6. S2b is the middle point of the segment S2a , P[n]
  7. The PC1 control point is the middle point of the segment M , S1b
  8. The PC2 control point is the middle point of the segment M , S2b

 This method is coded in the PB1 Delphi project.

A screen dump of the program appears below:

 
Program Description Keywords

PB1

Draw and distort polygons using Bézier curves and an original smoothing algorithm.

This algorithm provides an adjustable smooth parameter, able to transform a square to a circle.  

Bezier curves are drawn with a NOTXOR pen, option not available with the API windows function Polybezier.  Simply by clicking on the polygon edges or on the Bézier control points, you can obtain many complex shapes, such as flowers. The areas may be coloured.

Smoothing algorithm with smooth factor,
Bézier curves,
Square to circle transformation,
Grid pattern,
Drawing flowers.

Download:  Jean-YvesQueincBezierCurves.zip

Updated
26 Feb 2005


since 12 Jan 2001