by Jean-Yves Quéinec
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.
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
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.
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.
This geometrical solution is completely empirical, but gives excellent results.
This method is coded in the PB1 Delphi project.
A screen dump of the program appears below:
|Draw and distort polygons using Bézier curves and an original
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,
Square to circle transformation,
26 Feb 2005
since 12 Jan 2001