|
Todd examines and implements Bezier curves by using the literal rendering technique and the deCastejau method.
July 01, 1990
URL:http://www.drdobbs.com/cpp/drawing-character-shapes-with-bezier-cur/184408379
Todd is a programmer/analyst with the Institute of Geophysics and Planetary Physics at UCLA where he works on various software projects. He is writing a book, Dynamic Data Structures, which will be published by Academic Press, late in 1990. Todd can be reached at 1104 N. Orchard, Burbank, CA 91506
Text is the most common medium of exchanging ideas, theories, and concepts. As we all learned in school, the building blocks of printed text are typographic characters. A complete set of characters of a certain design or style is known as a "font." Currently, there exist more than 10,000 different font designs for the Roman alphabet.
Until the last few years, most computer systems did not devote resources to presenting text in any but the most primitive form: either dot-matrix or stroked characters. With increased computing power, larger memory, and higher resolution displays and printers, personal computer systems can now handle typographic characters with greater fidelity than before.
In this article, we'll take a look at one of the most common ways for representing and rendering typographic character shapes on a computer -- the Bezier curve.
A Bezier curve is a parametric curve that is specified using a small number of points. This implies a compact and efficient means for storing the definition of a character shape. Bezier curves have other properties that make them particularly useful for representing the shapes found in typographic characters (see next section).
The Bezier curve was originally developed in the early 1970s by the French mathematician Pierre Bezier for Renault (the automaker), as a way to describe the three-dimensional shapes and surfaces of cars. In the two-dimensional world, Bezier curves were not used until recently by manufacturers of digital typesetting equipment. Instead, they relied on straight lines, circles, and arcs to represent typographic shapes -- mostly because these were well-understood and easy to compute efficiently.
Adobe, in its implementation of the Postscript page description language, was the first mainstream manufacturer to use Bezier curves. Since then, other manufacturers have followed suit.
The equation that defines a general Bezier curve is a polynomial. This polynomial can be of any order or degree, but as the order increases, so does the computational requirement. Rather than try to model a complex shape with a higher-degree polynomial, it is more practical to construct a composite curve that is built by joining together several simpler Bezier curves. These simpler curves are of degree three -- the cubic Bezier form.
With this form, a Bezier curve segment is specified by four points, called "control points." Two of these points define the positions of the curve's end points. The other two points control the shape of the curve. Figure 1 shows the important features of a cubic Bezier curve (hereafter referred to simply as Bezier curve).
A Bezier curve has several properties that make it well suited to representing typographic characters, the first being that the defined shape is both continuous and smooth.
Second, the curve is tangent to the line formed by the end point and the nearest control point. This is useful in creating smooth curves that consist of one or more curve segments joined together. The reason is that if the two curve segments are joined properly then the resulting curve will also be continuous. This occurs if the adjacent curve segments share a common end point, and if the nearest control points for each curve, as well as the common end point, are all collinear.
Third, because the curves are defined by parametric equations, the fonts, which are built up from the curves can be scaled and sized at the time of display. This is done by multiplying the results derived from the equations by some scaling factor.
Bezier curves are also well behaved under other kinds of mathematical transformations, such as rotation and shearing. This was a problem with the line/arc representation used by many digital type manufacturers: The shapes were well behaved for scaling and translation, but not for shearing. (A sheared circle does not remain a circle but becomes an ellipse.)
In addition, Bezier curves have the property of being bounded by the control points, which define it. No portion of the curve extends beyond the edges of the box formed by drawing lines between adjacent control points. If you collapse the box so that all the control points are collinear, then the Bezier curve defines a straight line. This means that Bezier curves can be used to represent both the straight and the curved features of a character.
Finally, Bezier curves can be computed relatively efficiently using a method known as the "deCasteljau" algorithm. While not as fast as Bresenham or other circle-drawing methods, it is fast enough for modern microprocessors.
The general form of a Bezier curve segment is:
_n_ n!
r (t) = \ _____________ ai ti (1-t) n-i
/___ i! (n - 1)!
i = 0
The cubic form of the Bezier curve, for a two-dimensional coordinate space, can be more easily described by a pair of parametric equations, which determine the x and y coordinates of points on the curve.
The x component of a Bezier curve is defined by the formula:
x(t) = (1 - t)3x1 + 3t(1- t)2x2 + 3t2(1-t)x3 + t3x4
The formula for y is the same, except y replaces x in the equation above. The variable t is the parameter for the equation and is varied from 0 to 1.
When you design a font it is important to draw the character shapes at a size that will ensure that all features of the font can be accurately captured. Also, because it is possible that the font may be enlarged greatly (for example, as part of a billboard), it is best to draw the prototypical font at an equally large scale.
In Adobe's implementation, character shapes are defined on a grid of 1000 x 1000 points, where a point is 1/72 of an inch. An 11-inch page is approximately 825 points long. So, for typical publishing applications this is a reasonable choice.
Characters within a font have certain features or attributes (see Figure 2), which are used in their design. One attribute is the baseline. This is a horizontal line that passes through the font and is used for vertical alignment of a character. All (or nearly all) parts of an "a" remain above its baseline, while the tail of a "g" (also known as its descender) extends below.
Another feature is the sidebearings. This is the amount of space on the left and right sides of a character. The sidebearings can be different for each character in a font, but typically are the same. The sidebearings are included in the total width of the character. In mono-spaced fonts (such as computer line-printer fonts), the character width is the same for all characters. Typographic fonts have proportionally spaced characters, where each character's width depends on its individual design.
You may have heard or read about "hints" buried in the definitions of Postscript fonts (Type 1 Adobe format). These hints describe minor adjustments to the way in which the shape is calculated as the size of the letter becomes very small. This is necessary because the typical display device is a raster device -- composed of discrete pixels. As the letter is reduced in size, there may be some distortion of the character due to round-off errors related to the calculations of which pixel a line is in. The "hints" provide information to the rendering system so that the distortion is minimized, and the shape is consistent with the font designer's original intent.
The most straightforward way of rendering a Bezier curve is to use the parametric equations shown earlier. It is not too difficult to express these two equations in C, Pascal, or Fortran, using floating-point values. To calculate a series of points along the curve, just vary the parameter t from 0 to 1 in fractional increments and calculate the corresponding values for x and y.
A faster but less straightforward method of rendering Bezier curves is the deCasteljau algorithm. With this approach, the control box, which surrounds the Bezier curve is divided into two smaller control boxes. These boxes are each successively divided into two smaller boxes, and so on, in a recursive manner, until a specific degree of accuracy is obtained.
At that time, the specific segments of each of the smallest control boxes are drawn. The net result is that the Bezier curve is approximated by a series of straight-line segments. The first order bounding box is defined by the points a0, b0, c0, d0. One of the second order bounding boxes is defined by the points a0, a1, a2, a3. The other second order bounding box is defined by the points a3, b2, c1, d0. Figure 3 shows how all these points relate to one another. The point a1 is calculated by finding the midpoint of the line that connects a0 and b0. The other points (a2, a3, b1, b2, and c1) are calculated in a similar manner.
Listing One, page 102, contains the entire source for a program, which displays a character shape represented by a composite Bezier curve.
To do this, we must first have a function that will draw a Bezier curve segment. In the listing is a function called draw_bezier1( ). This function accepts a variable of type BEZIER_BOX, which contains the x and y coordinates of the four control points for the Bezier curve segment. The function then calculates the points on the Bezier curve from the parametric equations (as discussed earlier), and draws line segments between them.
A second function, called draw_bezier2( ), takes the same arguments as draw_bezier1( ), but draws the curves using the deCasteljau rendering method, also discussed earlier.
Both the functions draw_bezier1( ), and draw_bezier2( ) have been written so that the accuracy at which the Bezier curves are drawn can be adjusted. For draw_bezier1( ), the Bezier curve is approximated by drawing straight lines between points, which are separated by a distance, which is on the order of the resolution of the display device.
This display threshold value is maintained in the variable DPU. To arrive at an appropriate value for DPU, calculate the maximum resolution of the screen and divide that by the size of the prototypical font. Because the DPU depends on the resolution of the display device, the application is somewhat device-dependent.
For draw_bezier2( ), the display threshold is determined by the function accurate( ). In this implementation, how you determine when the approximation is accurate enough, is to keep a simple count of the number of times the curve has been subdivided. The variable B_cutoff contains the number of divisions, which are considered accurate. The variable B_level contains the current division count. For screens of resolution of about 600 x 400, a cut-off of 3 is quite good and nearly as accurate as the literal rendering employed in draw_bezier1( ). If a cut-off of 4 is used, the resulting characters are indistinguishable between draw_ bezier1( ) and draw_bezier2( ).
To make drawing a particular character easier, I included a function called draw_letter( ). This function allows you to place the character anywhere on the screen. It also allows you to define the color of the font outline, the fill color, the desired point size to display the character, and the rendering function.
Another argument to draw_letter( ) is an array of BEZIER_BOX variables. This should contain a series of Bezier curve definitions which, when drawn collectively, will result in the desired character. The array of curve definitions is ended by a sentinel curve definition whose first x coordinate is set to BFLAG. The second x, y pair of this sentinel curve is the coordinates of a point inside the character's outline. This point is used by the fill function.
When you run the program, you will see a series of "a" letterforms printed on the same line in decreasing size. You can choose which rendering method you would like by supplying either the letter "d" (for deCasteljau) or the letter "l" (for literal) as the first command-line argument. You must specify one of these.
Although my first implementation of drawing fonts with Bezier curves used the literal rendering method, I was amazed at the difference in speed with which the characters were rendered with the deCasteljau method. At the same time, the quality of the presentation was the same as with the literal method. Table 1 presents some of these timings.
Method Cut-off Time(sec)
---------------------------------
deCasteljau 3 6
deCasteljau 4 11
literal * 55
These timings were performed on an AT compatible 286 running at 12.5 MHz with a Hercules graphics display system.
There are a few calls in the source that are unique to Turbo C. These are related to Turbo C's graphics library and area: closegraph( ), floodfill( ), initdriver( ), lineto( ), moveto( ), setcolor( ), setfillstyle( ), and setlinestyle( ). One call whose arguments may need changing is initdriver( ). The last argument in this call is the path to where the device drivers are stored. You may need to change this to match your system's configuration.
There is a lot of room for extending this program. The most obvious is that the font has only one character in it -- the letter a. This allows for only limited expression. It actually took me a couple of hours to develop the letter (from scratch) to an acceptable form. Some letters in the alphabet should be easier and a few would be harder.
Another improvement would be to design a structure that would contain character-width information for an entire font. I chose not to do this for reasons of simplicity.
Other possible improvements include speeding up the renderer and improving quality at low-resolutions by adding a hinting mechanism.
_DRAWING CHARACTER SHAPES WITH BEZIER CURVES_ by Todd King
[LISTING ONE]
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.
/*-----------------------------------------------------------
BEZIER.C An application which draws characters (or anything else)
defined as a collection of Bezier curves. As is this programs
works fine on all displays except CGA in the 320x200 mode since
it expects a screen that is 640x200. To also use the deCasteljau method.
------------------------------------------------------------*/
#include <graphics.h>
#include <conio.h>
/* Definitions for defining fonts */
#define POINT_DEF 1000.0 /* The point size fonts are defined in */
#define BFLAG -POINT_DEF - 1 /* A Special flag used as a sentinal */
#define BNULL 0.0 /* For readability */
float DPU = 600.0 / POINT_DEF; /* The step between pixels */
/* Paramters for controlling the deCasteljau rendering method */
int B_cutoff = 3;
int B_level = 0;
/* Structures for defining Bezier bounding boxes */
typedef struct {
float x, y;
} XY;
typedef struct {
XY a, b, c, d;
} BEZIER_BOX;
/* Do a little letter doodling */
main(argc, argv)
int argc;
char *argv[];
{
int draw_bezier1();
int draw_bezier2();
int (*draw_fun)();
char label[80];
int gdriver = DETECT, gmode;
BEZIER_BOX lower_a[] = {
{ { 0.0, 591.0}, { 0.0, 864.0}, {1000.0, 864.0}, {1000.0, 591.0} },
{ {1000.0, 591.0}, {1000.0, 591.0}, {1000.0, 45.0}, {1000.0, 45.0} },
{ {1000.0, 45.0}, {1000.0, 45.0}, { 727.0, 45.0}, { 727.0, 45.0} },
{ { 727.0, 45.0}, { 727.0, 45.0}, { 727.0, 136.0}, { 727.0, 136.0} },
{ { 727.0, 136.0}, { 727.0, 0.0}, { 0.0, 0.0}, { 0.0, 227.0} },
{ { 0.0, 227.0}, { 0.0, 545.0}, { 727.0, 545.0}, { 727.0, 364.0} },
{ { 727.0, 364.0}, { 727.0, 500.0}, { 727.0, 500.0}, { 727.0, 545.0} },
{ { 727.0, 545.0}, { 727.0, 727.0}, { 272.0, 727.0}, { 272.0, 592.0} },
{ { 272.0, 592.0}, { 272.0, 592.0}, { 0.0, 592.0}, { 0.0, 592.0} },
{ { 636.0, 280.0}, { 636.0, 90.0}, { 136.0, 119.0}, { 136.0, 250.0} },
{ { 136.0, 250.0}, { 136.0, 437.0}, { 636.0, 437.0}, { 636.0, 280.0} }, { { BFLAG, BNULL}, { 909.0, 228.0}, { BNULL, BNULL}, { BNULL, BNULL} }
};
if(argc != 2) {
print_usage();
}
/* Check options */
switch(argv[1][0]) {
case 'd': /* deCasteljau rendering */
case 'D':
strcpy(label, "deCasteljau rendering:");
draw_fun = draw_bezier2;
break;
case 'l': /* Literal rendering */
case 'L':
strcpy(label, "Literal rendering:");
draw_fun = draw_bezier1;
break;
default:
printf("Unknown option: %c\n", argv[1][0]);
print_usage();
break;
}
/* NOTE: the following pathname may need to be modified for your system. */
initgraph(&gdriver, &gmode, "C:\\turboc");
if(gdriver < 0 ) {
printf("Unable to initialize graphics, error code: %d", gdriver);
exit(0);
}
/* Now draw the letters with both rendering methods */
outtextxy(1, 1, label);
draw_letter(30.0, 160.0, lower_a, 180.0,
WHITE, SLASH_FILL, WHITE, draw_fun);
draw_letter(220.0, 160.0, lower_a, 120.0,
WHITE, SOLID_FILL, WHITE, draw_fun);
draw_letter(350.0, 160.0, lower_a, 90.0,
BLUE, LINE_FILL, BLUE, draw_fun);
draw_letter(450.0, 160.0, lower_a, 40.0,
WHITE, SOLID_FILL, WHITE, draw_fun);
draw_letter(500.0, 160.0, lower_a, 20.0,
WHITE, LINE_FILL, WHITE, draw_fun);
draw_letter(530.0, 160.0, lower_a, 10.0,
WHITE, SOLID_FILL, WHITE, draw_fun);
outtextxy(1, 190, "Press any key to continue...");
getch();
closegraph();
}
/*---------------------------------------------------
Draws a letter at a given location of a given size. The
outline color, fill color and fill style are also specified.
----------------------------------------------------*/
draw_letter(at_x, at_y, letter, size,
outline_color, fill_style, fill_color, draw_bezier)
float at_x, at_y;
BEZIER_BOX letter[];
float size;
int outline_color;
int fill_style;
int fill_color;
int draw_bezier();
{
int i = 0;
BEZIER_BOX bline;
float scale;
scale = size / POINT_DEF;
setcolor(outline_color);
setfillstyle(fill_style, fill_color);
setlinestyle(SOLID_LINE, 0, NORM_WIDTH);
while(letter[i].a.x != BFLAG) {
bline.a.x = at_x + (letter[i].a.x * scale);
bline.a.y = at_y - (letter[i].a.y * scale);
bline.b.x = at_x + (letter[i].b.x * scale);
bline.b.y = at_y - (letter[i].b.y * scale);
bline.c.x = at_x + (letter[i].c.x * scale);
bline.c.y = at_y - (letter[i].c.y * scale);
bline.d.x = at_x + (letter[i].d.x * scale);
bline.d.y = at_y - (letter[i].d.y * scale);
draw_bezier(&bline);
i++;
}
floodfill((int)(at_x + letter[i].b.x * scale),
(int)(at_y - letter[i].b.y * scale),
fill_color);
}
/*---------------------------------------------
Draws a bezier curve as defined by the passed Bezier bounding box.
-----------------------------------------------*/
draw_bezier1(bcurve)
BEZIER_BOX *bcurve;
{
float x, y;
float tm;
float t;
moveto((int)bcurve->a.x, (int)bcurve->a.y);
for(t = 0.0; t <= 1.0; t += 0.01) {
x = (1 - t) * (1 - t) * (1 - t) * bcurve->a.x
+ 3 * t * (t - 1) * (t - 1) * bcurve->b.x
+ 3 * t * t * (1 - t) * bcurve->c.x
+ t * t * t * bcurve->d.x;
y = (1 - t) * (1 - t) * (1 - t) * bcurve->a.y
+ 3 * t * (t - 1) * (t - 1) * bcurve->b.y
+ 3 * t * t * (1 - t) * bcurve->c.y
+ t * t * t * bcurve->d.y;
lineto((int)x, (int)y);
}
}
/*-------------------------------------------------------
Draws a bezier curve as a series of line segments.
This uses the deCasteljau algorithm.
--------------------------------------------------------*/
draw_bezier2(bcurve)
BEZIER_BOX *bcurve;
{
extern int B_level;
BEZIER_BOX b_box;
XY a0, d0;
XY a1, a2, a3;
XY b1, b2;
XY c1;
if(accurate(bcurve) == 1) {
draw_hull(bcurve);
return(0);
}
B_level++;
a0.x = bcurve->a.x;
a0.y = bcurve->a.y;
d0.x = bcurve->d.x;
d0.y = bcurve->d.y;
a1.x = a0.x + (bcurve->b.x - a0.x)/2;
a1.y = a0.y + (bcurve->b.y - a0.y)/2;
b1.x = bcurve->b.x + (bcurve->c.x - bcurve->b.x)/2;
b1.y = bcurve->b.y + (bcurve->c.y - bcurve->b.y)/2;
c1.x = bcurve->c.x + (bcurve->d.x - bcurve->c.x)/2;
c1.y = bcurve->c.y + (bcurve->d.y - bcurve->c.y)/2;
a2.x = a1.x + (b1.x - a1.x)/2;
a2.y = a1.y + (b1.y - a1.y)/2;
b2.x = b1.x + (c1.x - b1.x)/2;
b2.y = b1.y + (c1.y - b1.y)/2;
a3.x = a2.x + (b2.x - a2.x)/2;
a3.y = a2.y + (b2.y - a2.y)/2;
b_box.a.x = a0.x;
b_box.a.y = a0.y;
b_box.b.x = a1.x;
b_box.b.y = a1.y;
b_box.c.x = a2.x;
b_box.c.y = a2.y;
b_box.d.x = a3.x;
b_box.d.y = a3.y;
draw_bezier2(&b_box);
b_box.a.x = a3.x;
b_box.a.y = a3.y;
b_box.b.x = b2.x;
b_box.b.y = b2.y;
b_box.c.x = c1.x;
b_box.c.y = c1.y;
b_box.d.x = d0.x;
b_box.d.y = d0.y;
draw_bezier2(&b_box);
B_level--;
return(0);
}
/*----------------------------------------------
Determines if the bezier curve has been determined with enough accuracy.
Returns 1 if the passed Bezier bounding box is accurate enough, 0 otherwise.
-------------------------------------------------*/
accurate(b_box)
BEZIER_BOX *b_box;
{
extern int B_level;
extern int B_cutoff;
if(B_level >= B_cutoff) {
return(1);
} else {
return(0);
}
}
/*--------------------------------------------------
Draws a hull as defined by a Bezier bounding box.
-----------------------------------------------------*/
draw_hull(b_box)
BEZIER_BOX *b_box;
{
moveto((int) b_box->a.x, (int) b_box->a.y);
lineto((int) b_box->b.x, (int) b_box->b.y);
lineto((int) b_box->c.x, (int) b_box->c.y);
lineto((int) b_box->d.x, (int) b_box->d.y);
}
/*-------------------------------------------------------
Prints the usage message then exits.
---------------------------------------------------------*/
print_usage()
{
printf("Prints a series of lower case 'a's in decreasing size. You may\n");
printf("select between deCasteljau or literal rendering methods.\n");
printf("Proper usage:\n");
printf("\n");
printf(" bezier d|l\n");
printf("\n");
printf("If 'd' option is specified the deCasteljau rendering method\n");
printf("is used. If 'l' option is specified a literal Bezier rendering\n");
printf("method is used.\n");
exit(0);
}