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 Bziers. 34 Meanwhile it has been extended to render third-order Bzier 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) Bzier 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) Bzier 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 Bzier arcs. 112 113 The parametric form of a second-order Bzier 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 Bzier 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 Bzier 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 Bzier 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 Bzier 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 Bzier 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 Bzier arcs have the special property of being very easily 449 decomposed into two sub-arcs, which are themselves Bzier arcs. 450 Moreover, it is easy to prove that there is at most one vertical 451 extremum on each Bzier 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 Bzier 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 Bzier 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 Bzier arcs, the job is a little more complicated. 534 535 We assume that all Bziers 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-2018 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: 636
