| blob | 95d9e24010b15ed02af5bb338985bc1ecf3abba8 |
2 How FreeType's rasterizer work
4 by David Turner
6 Revised 2007-Feb-01
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.
14 I. Introduction
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
27 I. Introduction
28 ===============
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.
38 While these explanations start from the basics, a knowledge of
39 common rasterization techniques is assumed.
42 II. Rendering Technology
43 ========================
45 1. Requirements
46 ---------------
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.
52 - All point coordinates are in the 26.6 fixed float format. The
53 used orientation is:
56 ^ y
57 | reference orientation
58 |
59 *----> x
60 0
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).
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.
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)
87 TrueType bytecode interpreter FreeType rasterizer
90 A pixel line in the target bitmap is called a `scanline'.
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.
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.
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).
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.
113 The parametric form of a second-order Bézier curve is:
115 P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3
117 (P1 and P3 are the end points, P2 the control point.)
119 The parametric form of a third-order Bézier curve is:
121 P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4
123 (P1 and P4 are the end points, P2 and P3 the control points.)
125 For both formulae, t is a real number in the range [0..1].
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.
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.
136 In the following, only second-order curves are discussed since
137 rasterization of third-order curves is completely identical.
139 Here some samples for second-order curves.
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
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.
164 2. Profiles and Spans
165 ---------------------
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.
172 However, the following ideas remain in the same category, and are
173 more convenient to understand.
176 a. Sweeping the Shape
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'.
182 __---__
183 _-- -_
184 _- -
185 - \
186 / \
187 / \
188 | \
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
199 __---__
200 _----------_
201 _--------------
202 ----------------\
203 /-----------------\
204 /-------------------\
205 |---------------------\
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.
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
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
235 b. Decomposing Outlines into Profiles
237 For each scanline during the sweep, we need the following
238 information:
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).
244 o The x coordinates of these points.
246 x coordinates are computed before the sweep, in a phase called
247 `decomposition' which converts the glyph into *profiles*.
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.
254 Here are a few examples:
257 this square
258 1 2
259 ---->---- is made of two
260 | | | |
261 | | profiles | |
262 ^ v ^ + v
263 | | | |
264 | | | |
265 ----<----
267 up down
270 this triangle
272 P2 1 2
274 |\ is made of two | \
275 ^ | \ \ | \
276 | | \ \ profiles | \ |
277 | | \ v ^ | \ |
278 | \ | | + \ v
279 | \ | | \
280 P1 ---___ \ ---___ \
281 ---_\ ---_ \
282 <--__ P3 up down
286 A more general contour can be made of more than two profiles:
288 __ ^
289 / | / ___ / |
290 / | / | / | / |
291 | | / / => | v / /
292 | | | | | | ^ |
293 ^ | |___| | | ^ + | + | + v
294 | | | v | |
295 | | | up |
296 |___________| | down |
298 <-- up down
301 Successive profiles are always joined by horizontal segments
302 that are not part of the profiles themselves.
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.
310 In other graphics libraries, profiles are also called `edges' or
311 `edgelists'.
314 c. The Render Pool
316 FreeType has been designed to be able to run well on _very_
317 light systems, including embedded systems with very few memory.
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.
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).
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).
338 d. Computing Profiles Extents
340 Remember that a profile is an array, associating a _scanline_ to
341 the x pixel coordinate of its intersection with a contour.
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.
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).
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
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:
372 - min scanline = FLOOR ( min y )
373 - max scanline = CEILING( max y )
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.
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 #
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:
399 P1.y <= P2.y <= P3.y for an ever-ascending arc
401 P1.y >= P2.y >= P3.y for an ever-descending arc
403 with the special case of
405 P1.y = P2.y = P3.y where the arc is said to be `flat'.
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.
411 Note also that a monotonic arc can contain an extremum too,
412 which is then one of its `on' points:
415 P1 P2
416 #---__ * P1P2P3 is ever-descending, but P1
417 -_ is an y-extremum.
418 -
419 ---_ \
420 -> \
421 \ P3
422 #
425 Let's go back to our previous example:
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 #
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.
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).
454 For instance, the following arc P1P2P3 can be decomposed into
455 two sub-arcs Q1Q2Q3 and R1R2R3:
458 P2
459 *
460 # on curve
461 * off curve
464 original Bézier arc P1P2P3.
465 __---__
466 _-- --_
467 _- -_
468 - -
469 / \
470 / \
471 # #
472 P1 P3
476 P2
477 *
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.
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:
502 Q2
503 *
505 __-x--_ R1
506 _-- #_
507 Q1 _- Q3 - R2
508 # \ *
509 -
510 \
511 \ R3
512 #
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.
521 We will finally find the vertical extremum. Note that the
522 iterative process of finding an extremum is called `flattening'.
525 e. Computing Profiles Coordinates
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.
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.
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'.
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
565 f. Sweeping and Sorting the Spans
567 Once all our profiles have been computed, we begin the sweep to
568 build (and fill) the spans.
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.
574 One list, called the `left' one, only contains ascending
575 profiles, while the other `right' list contains the descending
576 profiles.
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.
582 Creating spans is thus straightforward:
584 1. We sort each list in increasing horizontal order.
586 2. We pair each value of the left list with its corresponding
587 value in the right list.
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).
600 There are then two spans, joining
601 1 to 4 (i.e. a-b) and 3 to 2
602 (i.e. c-d)!
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.
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.
616 Once the spans have been `created', we can simply draw them in
617 the target bitmap.
619 ------------------------------------------------------------------------
621 Copyright 2003, 2007 by
622 David Turner, Robert Wilhelm, and Werner Lemberg.
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.
631 --- end of raster.txt ---
633 Local Variables:
634 coding: utf-8
635 End: