| blob | 34d05eb311d19921f91314a70f5399b16382dfc3 |
1 This file is an attempt at explaining the internals of the FreeType
2 rasterizer. This component is quite general purpose and could
3 easily be integrated into other programs (but still under the
4 current license).
6 --------------------------------------------------------------------
8 The HOWs and WHYs of the FreeType rasterizer
10 by David Turner
13 I. Introduction
15 II. Rendering Technology
17 III. Implementation Details
19 IV. Gray-Level Support
23 I. Introduction
24 ===============
26 A rasterizer is a library in charge of converting a vectorial
27 representation of a shape into a bitmap. The FreeType rasterizer
28 has been developed to render the glyphs found in TrueType files,
29 made up of segments and second-order Beziers. This document is an
30 explanation of its design and implementation.
32 Though these explanations start from the basics, a knowledge of
33 common rasterization techniques is assumed.
36 --------------------------------------------------------------------
39 II. Rendering Technology
40 ========================
42 1. Requirements
43 ---------------
45 We will assume that all scaling/rotating/hinting/whatever has been
46 already done. The glyph is thus described, as in the TrueType
47 specification, by a list of points. Each point has an x and y
48 coordinate, as well as a flag that indicates whether the point is
49 _on_ or _off_ the curve.
51 More precisely:
53 - All point coordinates are in the 26.6 fixed float format as
54 defined by the specification. The orientation used is:
56 ^ y
57 | reference orientation
58 |
59 *----> x
60 0
62 This means that the `distance' between two neighbouring pixels
63 is 64 `units' (1 unit = 1/64th of a pixel).
65 Note that, for the rasterizer, pixel centers are located at
66 integer coordinates, i.e., (0.0, 0.0) is the coordinate of the
67 origin's center (unlike what happens within the TrueType
68 bytecode interpreter where this point's center lies at (0.5,
69 0.5)).
71 A pixel line in the target bitmap is called a `scanline'.
73 - A glyph is usually made of several contours, also called
74 outlines. A contour is simply a closed curve that delimits an
75 outer or inner region of the glyph. It is described by a series
76 of successive points of the points table.
78 Each point of the glyph has an associated flag that indicates
79 whether it is `on' or `off' the curve. Two successive `on'
80 points indicate a line segment joining the two points.
82 One `off' point amidst two `on' points indicates a second degree
83 Bezier parametric arc, defined by these three points (the `off'
84 point being the control point, and the `on' ones the start and
85 end points).
87 Finally, two successive `off' points forces the rasterizer to
88 create, during rendering, an `on' point amidst them, at their
89 exact middle. This greatly facilitates the definition of
90 successive Bezier arcs.
92 * # on curve
93 * off curve
94 __---__
95 #-__ _-- -_
96 --__ _- -
97 --__ # \
98 --__ #
99 -#
100 Two `on' points
101 Two `on' points and one `off' point
102 between them
104 *
105 # __ Two `on' points with two `off'
106 \ - - points between them. The point
107 \ / \ marked `0' is the middle of the
108 - 0 \ `off' points, and is a `virtual
109 -_ _- # on' point where the curve passes.
110 -- It does not appear in the point
111 * list.
114 The FreeType rasterizer, as intended to render TrueType glyphs,
115 does not support third order Beziers, usually found in Type 1
116 fonts. Type 1 support may lead to further development of the
117 engine (it is already part of FreeType 2.0).
119 The parametric form of a second-order Bezier is:
121 P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3
123 with t a real number in the range [0..1]
125 P1 and P3 are the endpoints, P2 the control point.
127 Note that the rasterizer does not use this formula. It exhibits,
128 however, one very useful property of Bezier arcs: Each point of
129 the curve is a weighted average of the control points.
131 As all weights are positive and always sum up to 1, whatever the
132 value of t, each arc point lies within the triangle defined by the
133 arc's three control points.
136 2. Profiles and Spans
137 ---------------------
139 The following is a basic explanation of the _kind_ of computations
140 made by the rasterizer to build a bitmap from a vector
141 representation. Note that the actual implementation is slightly
142 different, due to performance tuning and other factors.
144 However, the following ideas remain in the same category, and are
145 more convenient to understand.
147 a. Sweeping the shape
149 The best way to fill a shape is to decompose it into a number of
150 simple horizontal segments, then turn them on in the target
151 bitmap. These segments are called `spans'.
153 __---__
154 _-- -_
155 _- -
156 - \
157 / \
158 / \
159 | \
161 __---__ Example: filling a shape
162 _----------_ with spans.
163 _--------------
164 ----------------\
165 /-----------------\ This is typically done from the top
166 / \ to the bottom of the shape, in a
167 | | \ movement called a `sweep".
168 V
170 __---__
171 _----------_
172 _--------------
173 ----------------\
174 /-----------------\
175 /-------------------\
176 |---------------------\
179 In order to draw a span, the rasterizer must compute its
180 coordinates, which are simply the shape's contours'
181 x-coordinates taken on the y-scanlines.
184 /---/ |---| Note that there are usually
185 /---/ |---| several spans per scanline.
186 | /---/ |---|
187 | /---/_______|---| When rendering this shape to the
188 V /----------------| current scanline y, we must
189 /-----------------| compute the x values of the
190 a /----| |---| points a, b, c, and d.
191 - - - * * - - - - * * - - y -
192 / / b c| |d
195 /---/ |---|
196 /---/ |---| And then turn on the spans a-b
197 /---/ |---| and c-d.
198 /---/_______|---|
199 /----------------|
200 /-----------------|
201 a /----| |---|
202 - - - ####### - - - - ##### - - y -
203 / / b c| |d
205 b. Decomposing outlines into profiles
207 For each scanline during the sweep, we need the following
208 information:
210 o The number of spans on the current scanline, given by the
211 number of shape points intersecting the scanline (these are
212 the points a, b, c, and d in the above example).
214 o The x coordinates of these points.
216 These are computed before the sweep, in a phase called
217 `decomposition' which converts the glyph into *profiles*.
219 Put it simply, a `profile' is a contour's portion that can only
220 be either ascending or descending, i.e., it is monotonic in the
221 vertical direction (we will also say y-monotonic). There is no
222 such thing as a horizontal profile, as we shall see.
224 Here are a few examples:
227 this square
228 1 2
229 ---->---- is made of two
230 | | | |
231 | | profiles | |
232 ^ v ^ + v
233 | | | |
234 | | | |
235 ----<----
237 up down
240 this triangle
242 P2 1 2
244 |\ is made of two | \
245 ^ | \ \ | \
246 | | \ \ profiles | \ |
247 | | \ v ^ | \ |
248 | \ | | + \ v
249 | \ | | \
250 P1 ---___ \ ---___ \
251 ---_\ ---_ \
252 <--__ P3 up down
256 A more general contour can be made of more than two profiles:
258 __ ^
259 / | / ___ / |
260 / | / | / | / |
261 | | / / => | v / /
262 | | | | | | ^ |
263 ^ | |___| | | ^ + | + | + v
264 | | | v | |
265 | | | up |
266 |___________| | down |
268 <-- up down
271 Successive profiles are always joined by horizontal segments
272 that are not part of the profiles themselves.
274 Note that for the rasterizer, a profile is simply an *array*
275 that associates one horizontal *pixel* coordinate to each bitmap
276 *scanline* crossed by the contour's section containing the
277 profile. Note also that profiles are *oriented* up or down
278 along the glyph's original flow orientation.
280 In other graphics libraries, profiles are also called `edges' or
281 `edgelists'.
283 c. The Render Pool
285 FreeType has been designed to be able to run well on _very_
286 light systems, including embedded systems with very few memory.
288 A render pool will be allocated once; the rasterizer uses this
289 pool for all its needs by managing this memory directly in it.
290 The algorithms that are used for profile computation make it
291 possible to use the pool as a simple growing heap. This means
292 that this memory management is actually easy, and faster than
293 any kind of malloc()/free() combination.
295 Moreover, we'll see later that the rasterizer is able, when
296 dealing with profiles too large and numerous to lie all at once
297 in the render pool, to immediately decompose recursively the
298 rendering process into independent sub-tasks, each taking less
299 memory to be performed (see `sub-banding' below).
301 The render pool doesn't need to be large. A 4kByte pool is
302 enough for nearly all renditions, though nearly 100% slower than
303 a more confortable 16 or 32kByte pool (that was tested with
304 complex glyphs at sizes over 500 pixels).
306 d. Computing Profiles Extents
308 Remember that a profile is an array, associating a _scanline_ to
309 the x pixel coordinate of its intersection with a contour.
311 Though it's not exactly how the FreeType rasterizer works, it is
312 convenient to think that we need a profile's height before
313 allocating it in the pool and computing its coordinates.
315 The profile's height is the number of scanlines crossed by the
316 y-monotonic section of a contour. We thus need to compute these
317 sections from the vectorial description. In order to do that,
318 we are obliged to compute all (local and global) y-extrema of
319 the glyph (minima and maxima).
322 P2 For instance, this triangle has only
323 two y-extrema, which are simply
324 |\
325 | \ P2.y as an y-maximum
326 | \ P3.y as an y-minimum
327 | \
328 | \ P1.y is not an y-extremum (though it is
329 | \ a x-minimum, which we don't need).
330 P1 ---___ \
331 ---_\
332 P3
334 Note that the extrema are expressed in pixel units, not in
335 scanlines. The triangle's height is certainly (P3.y-P2.y+1)
336 pixel units, but its profiles' heights are computed in
337 scanlines. The exact conversion is simply:
339 - min scanline = FLOOR ( min y )
340 - max scanline = CEILING( max y )
342 A problem arises with Bezier Arcs. While a segment is always
343 necessarily y-monotonic (i.e., flat, ascending, or descending),
344 which makes extrema computations easy, the ascent of an arc can
345 vary between its control points.
347 P2
348 *
349 # on curve
350 * off curve
351 __-x--_
352 _-- -_
353 P1 _- - A non y-monotonic Bezier arc.
354 # \
355 - The arc goes from P1 to P3.
356 \
357 \ P3
358 #
360 We first need to be able to easily detect non-monotonic arcs,
361 according to their control points. I will state here, without
362 proof, that the monotony condition can be expressed as:
364 P1.y <= P2.y <= P3.y for an ever-ascending arc
366 P1.y >= P2.y >= P3.y for an ever-descending arc
368 with the special case of
370 P1.y = P2.y = P3.y where the arc is said to be `flat'.
372 As you can see, these conditions can be very easily tested.
373 They are, however, extremely important, as any arc that does not
374 satisfy them necessarily contains an extremum.
376 Note also that a monotonic arc can contain an extremum too,
377 which is then one of its `on' points:
379 P1 P2
380 #---__ * P1P2P3 is ever-descending, but P1
381 -_ is an y-extremum.
382 -
383 ---_ \
384 -> \
385 \ P3
386 #
388 Let's go back to our previous example:
390 P2
391 *
392 # on curve
393 * off curve
394 __-x--_
395 _-- -_
396 P1 _- - A non-y-monotonic Bezier arc.
397 # \
398 - Here we have
399 \ P2.y >= P1.y &&
400 \ P3 P2.y >= P3.y (!)
401 #
403 We need to compute the y-maximum of this arc to be able to
404 compute a profile's height (the point marked by an `x'). The
405 arc's equation indicates that a direct computation is possible,
406 but we'll rely on a different technique, which use will become
407 apparent a bit later.
409 Bezier arcs have the special property of being very easily
410 decomposed into two other sub-arcs, which are themselves Beziers
411 arcs. Moreover, it is easy to prove that there is at most one
412 y-extremum on each Bezier arc (for second degree ones).
414 For instance, the following arc P1P2P3 can be decomposed into
415 two sub-arcs Q1Q2Q3 and R1R2R3 that look like:
417 P2
418 *
419 # on curve
420 * off curve
423 Original Bezier Arc P1P2P3.
424 __---__
425 _-- --_
426 _- -_
427 - -
428 / \
429 / \
430 # #
431 P1 P3
436 P2
437 *
441 Q3 Decomposed into two subarcs
442 Q2 R2 Q1Q2Q3 and R1R2R3
443 * __-#-__ *
444 _-- --_
445 _- R1 -_ Q1 = P1 R3 = P3
446 - - Q2 = (P1+P2)/2 R2 = (P2+P3)/2
447 / \
448 / \ Q3 = R1 = (Q2+R2)/2
449 # #
450 Q1 R3 Note that Q2, R2, and Q3=R1
451 are on a single line which is
452 tangent to the curve.
454 We have then decomposed a non-y-monotonic bezier into two
455 smaller sub-arcs. Note that in the above drawing, both sub-arcs
456 are monotonic, and that the extremum is then Q3=R1. However, in
457 a more general case, only one sub-arc is guaranteed to be
458 monotonic. Getting back to our former example:
460 Q2
461 *
463 __-x--_ R1
464 _-- #_
465 Q1 _- Q3 - R2
466 # \ *
467 -
468 \
469 \ R3
470 #
472 Here, we see that, though Q1Q2Q3 is still non-monotonic, R1R2R3
473 is ever descending: we thus know that it doesn't contain the
474 extremum. We can then re-subdivide Q1Q2Q3 into two sub-arcs and
475 go on recursively, stopping when we encounter two monotonic
476 subarcs, or when the subarcs become simply too small.
478 We will finally find the y-extremum. Note that the iterative
479 process of finding an extremum is called `flattening'.
481 e. Computing Profiles coordinates
483 Once we have the height of each profile, we are able to allocate
484 it in the render pool. We now have to compute its coordinate
485 for each scanline.
487 In the case of segments, the computation is straightforward, and
488 uses good old Euclide (also known as Bresenham ;-). However,
489 for Bezier arcs, things get a little more complicated.
491 We assume that all Beziers that are part of a profile are the
492 result of `flattening' the curve, which means that they are all
493 y-monotonic (ascending or descending, and never flat). We now
494 have to compute the arcs' intersections with the profile's
495 scanlines. One way is to use a similar scheme to `flattening',
496 called `stepping'.
498 Consider this arc, going from P1 to
499 --------------------- P3. Suppose that we need to
500 compute its intersections with the
501 drawn scanlines. Again, this is
502 --------------------- feasible directly, if we dare
503 to compute one square root per
504 * P2 _---# P3 scanline (how great!).
505 ------------- _-- --
506 _-
507 _/ Rather, it is still possible to use
508 ---------/----------- the decomposition property in the
509 / same recursive way, i.e. subdivide
510 | the arc into subarcs until these
511 ------|-------------- get too small to cross more than
512 | one scanline!
513 |
514 -----|--------------- This is very easily done using a
515 | rasterizer-managed stack of
516 | subarcs.
517 # P1
519 f. Sweeping and Sorting the spans
521 Once all our profiles have been computed, we begin the sweep to
522 build (and fill) the spans.
524 As the TrueType specification uses the winding fill rule, we
525 place on each scanline the profiles present in two separate
526 lists.
528 One list, called the `left' one, only contains ascending
529 profiles, while the other `right' list contains the descending
530 profiles.
532 As each glyph is made of closed curves, a simple geometric
533 property is that the two lists necessarily contain the same
534 number of elements.
536 Creating spans is there straightforward:
538 1. We sort each list in increasing x order.
540 2. We pair each value of the left list, with its corresponding
541 value in the right one.
544 / / | | For example, we have here
545 / / | | four profiles. Two of
546 >/ / | | | them are ascending (1 &
547 1// / ^ | | | 2 3), while the two others
548 // // 3| | | v are descending (2 & 4).
549 / //4 | | | On the given scanline,
550 a / /< | | the left list is (1,3),
551 - - - *-----* - - - - *---* - - y - and the right one is
552 / / b c| |d (4,2) (sorted).
554 There are then two spans, joining
555 1 to 4 (i.e. a-b) and 3 to 2
556 (i.e. c-d)!
558 Sorting doesn't necessarily take much time, as in 99 cases out
559 of 100, the lists' order is kept from one scanline to the next.
560 We can thus implement it with two simple singly-linked lists,
561 sorted by a classic bubble-sort, which takes a minimum amount of
562 time when the lists are already sorted.
564 A previous version of the rasterizer used more elaborate
565 structures, like arrays to perform `faster' sorting. It turned
566 out that this old scheme is not faster than the one described
567 above.
569 Once the spans have been `created', we can simply draw them in
570 the target bitmap.
572 g. Drop-out control
574 To be continued.
577 --- end of raster.txt ---