1 |
|
2 How FreeType's rasterizer work |
|
3 |
|
4 by David Turner |
|
5 |
|
6 Revised 2007-Feb-01 |
|
7 |
|
8 |
|
9 This file is an attempt to explain the internals of the FreeType |
|
10 rasterizer. The rasterizer is of quite general purpose and could |
|
11 easily be integrated into other programs. |
|
12 |
|
13 |
|
14 I. Introduction |
|
15 |
|
16 II. Rendering Technology |
|
17 1. Requirements |
|
18 2. Profiles and Spans |
|
19 a. Sweeping the Shape |
|
20 b. Decomposing Outlines into Profiles |
|
21 c. The Render Pool |
|
22 d. Computing Profiles Extents |
|
23 e. Computing Profiles Coordinates |
|
24 f. Sweeping and Sorting the Spans |
|
25 |
|
26 |
|
27 I. Introduction |
|
28 =============== |
|
29 |
|
30 A rasterizer is a library in charge of converting a vectorial |
|
31 representation of a shape into a bitmap. The FreeType rasterizer |
|
32 has been originally developed to render the glyphs found in |
|
33 TrueType files, made up of segments and second-order Béziers. |
|
34 Meanwhile it has been extended to render third-order Bézier curves |
|
35 also. This document is an explanation of its design and |
|
36 implementation. |
|
37 |
|
38 While these explanations start from the basics, a knowledge of |
|
39 common rasterization techniques is assumed. |
|
40 |
|
41 |
|
42 II. Rendering Technology |
|
43 ======================== |
|
44 |
|
45 1. Requirements |
|
46 --------------- |
|
47 |
|
48 We assume that all scaling, rotating, hinting, etc., has been |
|
49 already done. The glyph is thus described by a list of points in |
|
50 the device space. |
|
51 |
|
52 - All point coordinates are in the 26.6 fixed float format. The |
|
53 used orientation is: |
|
54 |
|
55 |
|
56 ^ y |
|
57 | reference orientation |
|
58 | |
|
59 *----> x |
|
60 0 |
|
61 |
|
62 |
|
63 `26.6' means that 26 bits are used for the integer part of a |
|
64 value and 6 bits are used for the fractional part. |
|
65 Consequently, the `distance' between two neighbouring pixels is |
|
66 64 `units' (1 unit = 1/64th of a pixel). |
|
67 |
|
68 Note that, for the rasterizer, pixel centers are located at |
|
69 integer coordinates. The TrueType bytecode interpreter, |
|
70 however, assumes that the lower left edge of a pixel (which is |
|
71 taken to be a square with a length of 1 unit) has integer |
|
72 coordinates. |
|
73 |
|
74 |
|
75 ^ y ^ y |
|
76 | | |
|
77 | (1,1) | (0.5,0.5) |
|
78 +-----------+ +-----+-----+ |
|
79 | | | | | |
|
80 | | | | | |
|
81 | | | o-----+-----> x |
|
82 | | | (0,0) | |
|
83 | | | | |
|
84 o-----------+-----> x +-----------+ |
|
85 (0,0) (-0.5,-0.5) |
|
86 |
|
87 TrueType bytecode interpreter FreeType rasterizer |
|
88 |
|
89 |
|
90 A pixel line in the target bitmap is called a `scanline'. |
|
91 |
|
92 - A glyph is usually made of several contours, also called |
|
93 `outlines'. A contour is simply a closed curve that delimits an |
|
94 outer or inner region of the glyph. It is described by a series |
|
95 of successive points of the points table. |
|
96 |
|
97 Each point of the glyph has an associated flag that indicates |
|
98 whether it is `on' or `off' the curve. Two successive `on' |
|
99 points indicate a line segment joining the two points. |
|
100 |
|
101 One `off' point amidst two `on' points indicates a second-degree |
|
102 (conic) Bézier parametric arc, defined by these three points |
|
103 (the `off' point being the control point, and the `on' ones the |
|
104 start and end points). Similarly, a third-degree (cubic) Bézier |
|
105 curve is described by four points (two `off' control points |
|
106 between two `on' points). |
|
107 |
|
108 Finally, for second-order curves only, two successive `off' |
|
109 points forces the rasterizer to create, during rendering, an |
|
110 `on' point amidst them, at their exact middle. This greatly |
|
111 facilitates the definition of successive Bézier arcs. |
|
112 |
|
113 The parametric form of a second-order Bézier curve is: |
|
114 |
|
115 P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3 |
|
116 |
|
117 (P1 and P3 are the end points, P2 the control point.) |
|
118 |
|
119 The parametric form of a third-order Bézier curve is: |
|
120 |
|
121 P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4 |
|
122 |
|
123 (P1 and P4 are the end points, P2 and P3 the control points.) |
|
124 |
|
125 For both formulae, t is a real number in the range [0..1]. |
|
126 |
|
127 Note that the rasterizer does not use these formulae directly. |
|
128 They exhibit, however, one very useful property of Bézier arcs: |
|
129 Each point of the curve is a weighted average of the control |
|
130 points. |
|
131 |
|
132 As all weights are positive and always sum up to 1, whatever the |
|
133 value of t, each arc point lies within the triangle (polygon) |
|
134 defined by the arc's three (four) control points. |
|
135 |
|
136 In the following, only second-order curves are discussed since |
|
137 rasterization of third-order curves is completely identical. |
|
138 |
|
139 Here some samples for second-order curves. |
|
140 |
|
141 |
|
142 * # on curve |
|
143 * off curve |
|
144 __---__ |
|
145 #-__ _-- -_ |
|
146 --__ _- - |
|
147 --__ # \ |
|
148 --__ # |
|
149 -# |
|
150 Two `on' points |
|
151 Two `on' points and one `off' point |
|
152 between them |
|
153 |
|
154 * |
|
155 # __ Two `on' points with two `off' |
|
156 \ - - points between them. The point |
|
157 \ / \ marked `0' is the middle of the |
|
158 - 0 \ `off' points, and is a `virtual |
|
159 -_ _- # on' point where the curve passes. |
|
160 -- It does not appear in the point |
|
161 * list. |
|
162 |
|
163 |
|
164 2. Profiles and Spans |
|
165 --------------------- |
|
166 |
|
167 The following is a basic explanation of the _kind_ of computations |
|
168 made by the rasterizer to build a bitmap from a vector |
|
169 representation. Note that the actual implementation is slightly |
|
170 different, due to performance tuning and other factors. |
|
171 |
|
172 However, the following ideas remain in the same category, and are |
|
173 more convenient to understand. |
|
174 |
|
175 |
|
176 a. Sweeping the Shape |
|
177 |
|
178 The best way to fill a shape is to decompose it into a number of |
|
179 simple horizontal segments, then turn them on in the target |
|
180 bitmap. These segments are called `spans'. |
|
181 |
|
182 __---__ |
|
183 _-- -_ |
|
184 _- - |
|
185 - \ |
|
186 / \ |
|
187 / \ |
|
188 | \ |
|
189 |
|
190 __---__ Example: filling a shape |
|
191 _----------_ with spans. |
|
192 _-------------- |
|
193 ----------------\ |
|
194 /-----------------\ This is typically done from the top |
|
195 / \ to the bottom of the shape, in a |
|
196 | | \ movement called a `sweep'. |
|
197 V |
|
198 |
|
199 __---__ |
|
200 _----------_ |
|
201 _-------------- |
|
202 ----------------\ |
|
203 /-----------------\ |
|
204 /-------------------\ |
|
205 |---------------------\ |
|
206 |
|
207 |
|
208 In order to draw a span, the rasterizer must compute its |
|
209 coordinates, which are simply the x coordinates of the shape's |
|
210 contours, taken on the y scanlines. |
|
211 |
|
212 |
|
213 /---/ |---| Note that there are usually |
|
214 /---/ |---| several spans per scanline. |
|
215 | /---/ |---| |
|
216 | /---/_______|---| When rendering this shape to the |
|
217 V /----------------| current scanline y, we must |
|
218 /-----------------| compute the x values of the |
|
219 a /----| |---| points a, b, c, and d. |
|
220 - - - * * - - - - * * - - y - |
|
221 / / b c| |d |
|
222 |
|
223 |
|
224 /---/ |---| |
|
225 /---/ |---| And then turn on the spans a-b |
|
226 /---/ |---| and c-d. |
|
227 /---/_______|---| |
|
228 /----------------| |
|
229 /-----------------| |
|
230 a /----| |---| |
|
231 - - - ####### - - - - ##### - - y - |
|
232 / / b c| |d |
|
233 |
|
234 |
|
235 b. Decomposing Outlines into Profiles |
|
236 |
|
237 For each scanline during the sweep, we need the following |
|
238 information: |
|
239 |
|
240 o The number of spans on the current scanline, given by the |
|
241 number of shape points intersecting the scanline (these are |
|
242 the points a, b, c, and d in the above example). |
|
243 |
|
244 o The x coordinates of these points. |
|
245 |
|
246 x coordinates are computed before the sweep, in a phase called |
|
247 `decomposition' which converts the glyph into *profiles*. |
|
248 |
|
249 Put it simply, a `profile' is a contour's portion that can only |
|
250 be either ascending or descending, i.e., it is monotonic in the |
|
251 vertical direction (we also say y-monotonic). There is no such |
|
252 thing as a horizontal profile, as we shall see. |
|
253 |
|
254 Here are a few examples: |
|
255 |
|
256 |
|
257 this square |
|
258 1 2 |
|
259 ---->---- is made of two |
|
260 | | | | |
|
261 | | profiles | | |
|
262 ^ v ^ + v |
|
263 | | | | |
|
264 | | | | |
|
265 ----<---- |
|
266 |
|
267 up down |
|
268 |
|
269 |
|
270 this triangle |
|
271 |
|
272 P2 1 2 |
|
273 |
|
274 |\ is made of two | \ |
|
275 ^ | \ \ | \ |
|
276 | | \ \ profiles | \ | |
|
277 | | \ v ^ | \ | |
|
278 | \ | | + \ v |
|
279 | \ | | \ |
|
280 P1 ---___ \ ---___ \ |
|
281 ---_\ ---_ \ |
|
282 <--__ P3 up down |
|
283 |
|
284 |
|
285 |
|
286 A more general contour can be made of more than two profiles: |
|
287 |
|
288 __ ^ |
|
289 / | / ___ / | |
|
290 / | / | / | / | |
|
291 | | / / => | v / / |
|
292 | | | | | | ^ | |
|
293 ^ | |___| | | ^ + | + | + v |
|
294 | | | v | | |
|
295 | | | up | |
|
296 |___________| | down | |
|
297 |
|
298 <-- up down |
|
299 |
|
300 |
|
301 Successive profiles are always joined by horizontal segments |
|
302 that are not part of the profiles themselves. |
|
303 |
|
304 For the rasterizer, a profile is simply an *array* that |
|
305 associates one horizontal *pixel* coordinate to each bitmap |
|
306 *scanline* crossed by the contour's section containing the |
|
307 profile. Note that profiles are *oriented* up or down along the |
|
308 glyph's original flow orientation. |
|
309 |
|
310 In other graphics libraries, profiles are also called `edges' or |
|
311 `edgelists'. |
|
312 |
|
313 |
|
314 c. The Render Pool |
|
315 |
|
316 FreeType has been designed to be able to run well on _very_ |
|
317 light systems, including embedded systems with very few memory. |
|
318 |
|
319 A render pool will be allocated once; the rasterizer uses this |
|
320 pool for all its needs by managing this memory directly in it. |
|
321 The algorithms that are used for profile computation make it |
|
322 possible to use the pool as a simple growing heap. This means |
|
323 that this memory management is actually quite easy and faster |
|
324 than any kind of malloc()/free() combination. |
|
325 |
|
326 Moreover, we'll see later that the rasterizer is able, when |
|
327 dealing with profiles too large and numerous to lie all at once |
|
328 in the render pool, to immediately decompose recursively the |
|
329 rendering process into independent sub-tasks, each taking less |
|
330 memory to be performed (see `sub-banding' below). |
|
331 |
|
332 The render pool doesn't need to be large. A 4KByte pool is |
|
333 enough for nearly all renditions, though nearly 100% slower than |
|
334 a more comfortable 16KByte or 32KByte pool (that was tested with |
|
335 complex glyphs at sizes over 500 pixels). |
|
336 |
|
337 |
|
338 d. Computing Profiles Extents |
|
339 |
|
340 Remember that a profile is an array, associating a _scanline_ to |
|
341 the x pixel coordinate of its intersection with a contour. |
|
342 |
|
343 Though it's not exactly how the FreeType rasterizer works, it is |
|
344 convenient to think that we need a profile's height before |
|
345 allocating it in the pool and computing its coordinates. |
|
346 |
|
347 The profile's height is the number of scanlines crossed by the |
|
348 y-monotonic section of a contour. We thus need to compute these |
|
349 sections from the vectorial description. In order to do that, |
|
350 we are obliged to compute all (local and global) y extrema of |
|
351 the glyph (minima and maxima). |
|
352 |
|
353 |
|
354 P2 For instance, this triangle has only |
|
355 two y-extrema, which are simply |
|
356 |\ |
|
357 | \ P2.y as a vertical maximum |
|
358 | \ P3.y as a vertical minimum |
|
359 | \ |
|
360 | \ P1.y is not a vertical extremum (though |
|
361 | \ it is a horizontal minimum, which we |
|
362 P1 ---___ \ don't need). |
|
363 ---_\ |
|
364 P3 |
|
365 |
|
366 |
|
367 Note that the extrema are expressed in pixel units, not in |
|
368 scanlines. The triangle's height is certainly (P3.y-P2.y+1) |
|
369 pixel units, but its profiles' heights are computed in |
|
370 scanlines. The exact conversion is simple: |
|
371 |
|
372 - min scanline = FLOOR ( min y ) |
|
373 - max scanline = CEILING( max y ) |
|
374 |
|
375 A problem arises with Bézier Arcs. While a segment is always |
|
376 necessarily y-monotonic (i.e., flat, ascending, or descending), |
|
377 which makes extrema computations easy, the ascent of an arc can |
|
378 vary between its control points. |
|
379 |
|
380 |
|
381 P2 |
|
382 * |
|
383 # on curve |
|
384 * off curve |
|
385 __-x--_ |
|
386 _-- -_ |
|
387 P1 _- - A non y-monotonic Bézier arc. |
|
388 # \ |
|
389 - The arc goes from P1 to P3. |
|
390 \ |
|
391 \ P3 |
|
392 # |
|
393 |
|
394 |
|
395 We first need to be able to easily detect non-monotonic arcs, |
|
396 according to their control points. I will state here, without |
|
397 proof, that the monotony condition can be expressed as: |
|
398 |
|
399 P1.y <= P2.y <= P3.y for an ever-ascending arc |
|
400 |
|
401 P1.y >= P2.y >= P3.y for an ever-descending arc |
|
402 |
|
403 with the special case of |
|
404 |
|
405 P1.y = P2.y = P3.y where the arc is said to be `flat'. |
|
406 |
|
407 As you can see, these conditions can be very easily tested. |
|
408 They are, however, extremely important, as any arc that does not |
|
409 satisfy them necessarily contains an extremum. |
|
410 |
|
411 Note also that a monotonic arc can contain an extremum too, |
|
412 which is then one of its `on' points: |
|
413 |
|
414 |
|
415 P1 P2 |
|
416 #---__ * P1P2P3 is ever-descending, but P1 |
|
417 -_ is an y-extremum. |
|
418 - |
|
419 ---_ \ |
|
420 -> \ |
|
421 \ P3 |
|
422 # |
|
423 |
|
424 |
|
425 Let's go back to our previous example: |
|
426 |
|
427 |
|
428 P2 |
|
429 * |
|
430 # on curve |
|
431 * off curve |
|
432 __-x--_ |
|
433 _-- -_ |
|
434 P1 _- - A non-y-monotonic Bézier arc. |
|
435 # \ |
|
436 - Here we have |
|
437 \ P2.y >= P1.y && |
|
438 \ P3 P2.y >= P3.y (!) |
|
439 # |
|
440 |
|
441 |
|
442 We need to compute the vertical maximum of this arc to be able |
|
443 to compute a profile's height (the point marked by an `x'). The |
|
444 arc's equation indicates that a direct computation is possible, |
|
445 but we rely on a different technique, which use will become |
|
446 apparent soon. |
|
447 |
|
448 Bézier arcs have the special property of being very easily |
|
449 decomposed into two sub-arcs, which are themselves Bézier arcs. |
|
450 Moreover, it is easy to prove that there is at most one vertical |
|
451 extremum on each Bézier arc (for second-degree curves; similar |
|
452 conditions can be found for third-order arcs). |
|
453 |
|
454 For instance, the following arc P1P2P3 can be decomposed into |
|
455 two sub-arcs Q1Q2Q3 and R1R2R3: |
|
456 |
|
457 |
|
458 P2 |
|
459 * |
|
460 # on curve |
|
461 * off curve |
|
462 |
|
463 |
|
464 original Bézier arc P1P2P3. |
|
465 __---__ |
|
466 _-- --_ |
|
467 _- -_ |
|
468 - - |
|
469 / \ |
|
470 / \ |
|
471 # # |
|
472 P1 P3 |
|
473 |
|
474 |
|
475 |
|
476 P2 |
|
477 * |
|
478 |
|
479 |
|
480 |
|
481 Q3 Decomposed into two subarcs |
|
482 Q2 R2 Q1Q2Q3 and R1R2R3 |
|
483 * __-#-__ * |
|
484 _-- --_ |
|
485 _- R1 -_ Q1 = P1 R3 = P3 |
|
486 - - Q2 = (P1+P2)/2 R2 = (P2+P3)/2 |
|
487 / \ |
|
488 / \ Q3 = R1 = (Q2+R2)/2 |
|
489 # # |
|
490 Q1 R3 Note that Q2, R2, and Q3=R1 |
|
491 are on a single line which is |
|
492 tangent to the curve. |
|
493 |
|
494 |
|
495 We have then decomposed a non-y-monotonic Bézier curve into two |
|
496 smaller sub-arcs. Note that in the above drawing, both sub-arcs |
|
497 are monotonic, and that the extremum is then Q3=R1. However, in |
|
498 a more general case, only one sub-arc is guaranteed to be |
|
499 monotonic. Getting back to our former example: |
|
500 |
|
501 |
|
502 Q2 |
|
503 * |
|
504 |
|
505 __-x--_ R1 |
|
506 _-- #_ |
|
507 Q1 _- Q3 - R2 |
|
508 # \ * |
|
509 - |
|
510 \ |
|
511 \ R3 |
|
512 # |
|
513 |
|
514 |
|
515 Here, we see that, though Q1Q2Q3 is still non-monotonic, R1R2R3 |
|
516 is ever descending: We thus know that it doesn't contain the |
|
517 extremum. We can then re-subdivide Q1Q2Q3 into two sub-arcs and |
|
518 go on recursively, stopping when we encounter two monotonic |
|
519 subarcs, or when the subarcs become simply too small. |
|
520 |
|
521 We will finally find the vertical extremum. Note that the |
|
522 iterative process of finding an extremum is called `flattening'. |
|
523 |
|
524 |
|
525 e. Computing Profiles Coordinates |
|
526 |
|
527 Once we have the height of each profile, we are able to allocate |
|
528 it in the render pool. The next task is to compute coordinates |
|
529 for each scanline. |
|
530 |
|
531 In the case of segments, the computation is straightforward, |
|
532 using the Euclidean algorithm (also known as Bresenham). |
|
533 However, for Bézier arcs, the job is a little more complicated. |
|
534 |
|
535 We assume that all Béziers that are part of a profile are the |
|
536 result of flattening the curve, which means that they are all |
|
537 y-monotonic (ascending or descending, and never flat). We now |
|
538 have to compute the intersections of arcs with the profile's |
|
539 scanlines. One way is to use a similar scheme to flattening |
|
540 called `stepping'. |
|
541 |
|
542 |
|
543 Consider this arc, going from P1 to |
|
544 --------------------- P3. Suppose that we need to |
|
545 compute its intersections with the |
|
546 drawn scanlines. As already |
|
547 --------------------- mentioned this can be done |
|
548 directly, but the involved |
|
549 * P2 _---# P3 algorithm is far too slow. |
|
550 ------------- _-- -- |
|
551 _- |
|
552 _/ Instead, it is still possible to |
|
553 ---------/----------- use the decomposition property in |
|
554 / the same recursive way, i.e., |
|
555 | subdivide the arc into subarcs |
|
556 ------|-------------- until these get too small to cross |
|
557 | more than one scanline! |
|
558 | |
|
559 -----|--------------- This is very easily done using a |
|
560 | rasterizer-managed stack of |
|
561 | subarcs. |
|
562 # P1 |
|
563 |
|
564 |
|
565 f. Sweeping and Sorting the Spans |
|
566 |
|
567 Once all our profiles have been computed, we begin the sweep to |
|
568 build (and fill) the spans. |
|
569 |
|
570 As both the TrueType and Type 1 specifications use the winding |
|
571 fill rule (but with opposite directions), we place, on each |
|
572 scanline, the present profiles in two separate lists. |
|
573 |
|
574 One list, called the `left' one, only contains ascending |
|
575 profiles, while the other `right' list contains the descending |
|
576 profiles. |
|
577 |
|
578 As each glyph is made of closed curves, a simple geometric |
|
579 property ensures that the two lists contain the same number of |
|
580 elements. |
|
581 |
|
582 Creating spans is thus straightforward: |
|
583 |
|
584 1. We sort each list in increasing horizontal order. |
|
585 |
|
586 2. We pair each value of the left list with its corresponding |
|
587 value in the right list. |
|
588 |
|
589 |
|
590 / / | | For example, we have here |
|
591 / / | | four profiles. Two of |
|
592 >/ / | | | them are ascending (1 & |
|
593 1// / ^ | | | 2 3), while the two others |
|
594 // // 3| | | v are descending (2 & 4). |
|
595 / //4 | | | On the given scanline, |
|
596 a / /< | | the left list is (1,3), |
|
597 - - - *-----* - - - - *---* - - y - and the right one is |
|
598 / / b c| |d (4,2) (sorted). |
|
599 |
|
600 There are then two spans, joining |
|
601 1 to 4 (i.e. a-b) and 3 to 2 |
|
602 (i.e. c-d)! |
|
603 |
|
604 |
|
605 Sorting doesn't necessarily take much time, as in 99 cases out |
|
606 of 100, the lists' order is kept from one scanline to the next. |
|
607 We can thus implement it with two simple singly-linked lists, |
|
608 sorted by a classic bubble-sort, which takes a minimum amount of |
|
609 time when the lists are already sorted. |
|
610 |
|
611 A previous version of the rasterizer used more elaborate |
|
612 structures, like arrays to perform `faster' sorting. It turned |
|
613 out that this old scheme is not faster than the one described |
|
614 above. |
|
615 |
|
616 Once the spans have been `created', we can simply draw them in |
|
617 the target bitmap. |
|
618 |
|
619 ------------------------------------------------------------------------ |
|
620 |
|
621 Copyright 2003, 2007 by |
|
622 David Turner, Robert Wilhelm, and Werner Lemberg. |
|
623 |
|
624 This file is part of the FreeType project, and may only be used, |
|
625 modified, and distributed under the terms of the FreeType project |
|
626 license, LICENSE.TXT. By continuing to use, modify, or distribute this |
|
627 file you indicate that you have read the license and understand and |
|
628 accept it fully. |
|
629 |
|
630 |
|
631 --- end of raster.txt --- |
|
632 |
|
633 Local Variables: |
|
634 coding: utf-8 |
|
635 End: |
|