1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/modules/freetype2/docs/raster.txt Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,635 @@
1.4 +
1.5 + How FreeType's rasterizer work
1.6 +
1.7 + by David Turner
1.8 +
1.9 + Revised 2007-Feb-01
1.10 +
1.11 +
1.12 +This file is an attempt to explain the internals of the FreeType
1.13 +rasterizer. The rasterizer is of quite general purpose and could
1.14 +easily be integrated into other programs.
1.15 +
1.16 +
1.17 + I. Introduction
1.18 +
1.19 + II. Rendering Technology
1.20 + 1. Requirements
1.21 + 2. Profiles and Spans
1.22 + a. Sweeping the Shape
1.23 + b. Decomposing Outlines into Profiles
1.24 + c. The Render Pool
1.25 + d. Computing Profiles Extents
1.26 + e. Computing Profiles Coordinates
1.27 + f. Sweeping and Sorting the Spans
1.28 +
1.29 +
1.30 +I. Introduction
1.31 +===============
1.32 +
1.33 + A rasterizer is a library in charge of converting a vectorial
1.34 + representation of a shape into a bitmap. The FreeType rasterizer
1.35 + has been originally developed to render the glyphs found in
1.36 + TrueType files, made up of segments and second-order Béziers.
1.37 + Meanwhile it has been extended to render third-order Bézier curves
1.38 + also. This document is an explanation of its design and
1.39 + implementation.
1.40 +
1.41 + While these explanations start from the basics, a knowledge of
1.42 + common rasterization techniques is assumed.
1.43 +
1.44 +
1.45 +II. Rendering Technology
1.46 +========================
1.47 +
1.48 +1. Requirements
1.49 +---------------
1.50 +
1.51 + We assume that all scaling, rotating, hinting, etc., has been
1.52 + already done. The glyph is thus described by a list of points in
1.53 + the device space.
1.54 +
1.55 + - All point coordinates are in the 26.6 fixed float format. The
1.56 + used orientation is:
1.57 +
1.58 +
1.59 + ^ y
1.60 + | reference orientation
1.61 + |
1.62 + *----> x
1.63 + 0
1.64 +
1.65 +
1.66 + `26.6' means that 26 bits are used for the integer part of a
1.67 + value and 6 bits are used for the fractional part.
1.68 + Consequently, the `distance' between two neighbouring pixels is
1.69 + 64 `units' (1 unit = 1/64th of a pixel).
1.70 +
1.71 + Note that, for the rasterizer, pixel centers are located at
1.72 + integer coordinates. The TrueType bytecode interpreter,
1.73 + however, assumes that the lower left edge of a pixel (which is
1.74 + taken to be a square with a length of 1 unit) has integer
1.75 + coordinates.
1.76 +
1.77 +
1.78 + ^ y ^ y
1.79 + | |
1.80 + | (1,1) | (0.5,0.5)
1.81 + +-----------+ +-----+-----+
1.82 + | | | | |
1.83 + | | | | |
1.84 + | | | o-----+-----> x
1.85 + | | | (0,0) |
1.86 + | | | |
1.87 + o-----------+-----> x +-----------+
1.88 + (0,0) (-0.5,-0.5)
1.89 +
1.90 + TrueType bytecode interpreter FreeType rasterizer
1.91 +
1.92 +
1.93 + A pixel line in the target bitmap is called a `scanline'.
1.94 +
1.95 + - A glyph is usually made of several contours, also called
1.96 + `outlines'. A contour is simply a closed curve that delimits an
1.97 + outer or inner region of the glyph. It is described by a series
1.98 + of successive points of the points table.
1.99 +
1.100 + Each point of the glyph has an associated flag that indicates
1.101 + whether it is `on' or `off' the curve. Two successive `on'
1.102 + points indicate a line segment joining the two points.
1.103 +
1.104 + One `off' point amidst two `on' points indicates a second-degree
1.105 + (conic) Bézier parametric arc, defined by these three points
1.106 + (the `off' point being the control point, and the `on' ones the
1.107 + start and end points). Similarly, a third-degree (cubic) Bézier
1.108 + curve is described by four points (two `off' control points
1.109 + between two `on' points).
1.110 +
1.111 + Finally, for second-order curves only, two successive `off'
1.112 + points forces the rasterizer to create, during rendering, an
1.113 + `on' point amidst them, at their exact middle. This greatly
1.114 + facilitates the definition of successive Bézier arcs.
1.115 +
1.116 + The parametric form of a second-order Bézier curve is:
1.117 +
1.118 + P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3
1.119 +
1.120 + (P1 and P3 are the end points, P2 the control point.)
1.121 +
1.122 + The parametric form of a third-order Bézier curve is:
1.123 +
1.124 + P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4
1.125 +
1.126 + (P1 and P4 are the end points, P2 and P3 the control points.)
1.127 +
1.128 + For both formulae, t is a real number in the range [0..1].
1.129 +
1.130 + Note that the rasterizer does not use these formulae directly.
1.131 + They exhibit, however, one very useful property of Bézier arcs:
1.132 + Each point of the curve is a weighted average of the control
1.133 + points.
1.134 +
1.135 + As all weights are positive and always sum up to 1, whatever the
1.136 + value of t, each arc point lies within the triangle (polygon)
1.137 + defined by the arc's three (four) control points.
1.138 +
1.139 + In the following, only second-order curves are discussed since
1.140 + rasterization of third-order curves is completely identical.
1.141 +
1.142 + Here some samples for second-order curves.
1.143 +
1.144 +
1.145 + * # on curve
1.146 + * off curve
1.147 + __---__
1.148 + #-__ _-- -_
1.149 + --__ _- -
1.150 + --__ # \
1.151 + --__ #
1.152 + -#
1.153 + Two `on' points
1.154 + Two `on' points and one `off' point
1.155 + between them
1.156 +
1.157 + *
1.158 + # __ Two `on' points with two `off'
1.159 + \ - - points between them. The point
1.160 + \ / \ marked `0' is the middle of the
1.161 + - 0 \ `off' points, and is a `virtual
1.162 + -_ _- # on' point where the curve passes.
1.163 + -- It does not appear in the point
1.164 + * list.
1.165 +
1.166 +
1.167 +2. Profiles and Spans
1.168 +---------------------
1.169 +
1.170 + The following is a basic explanation of the _kind_ of computations
1.171 + made by the rasterizer to build a bitmap from a vector
1.172 + representation. Note that the actual implementation is slightly
1.173 + different, due to performance tuning and other factors.
1.174 +
1.175 + However, the following ideas remain in the same category, and are
1.176 + more convenient to understand.
1.177 +
1.178 +
1.179 + a. Sweeping the Shape
1.180 +
1.181 + The best way to fill a shape is to decompose it into a number of
1.182 + simple horizontal segments, then turn them on in the target
1.183 + bitmap. These segments are called `spans'.
1.184 +
1.185 + __---__
1.186 + _-- -_
1.187 + _- -
1.188 + - \
1.189 + / \
1.190 + / \
1.191 + | \
1.192 +
1.193 + __---__ Example: filling a shape
1.194 + _----------_ with spans.
1.195 + _--------------
1.196 + ----------------\
1.197 + /-----------------\ This is typically done from the top
1.198 + / \ to the bottom of the shape, in a
1.199 + | | \ movement called a `sweep'.
1.200 + V
1.201 +
1.202 + __---__
1.203 + _----------_
1.204 + _--------------
1.205 + ----------------\
1.206 + /-----------------\
1.207 + /-------------------\
1.208 + |---------------------\
1.209 +
1.210 +
1.211 + In order to draw a span, the rasterizer must compute its
1.212 + coordinates, which are simply the x coordinates of the shape's
1.213 + contours, taken on the y scanlines.
1.214 +
1.215 +
1.216 + /---/ |---| Note that there are usually
1.217 + /---/ |---| several spans per scanline.
1.218 + | /---/ |---|
1.219 + | /---/_______|---| When rendering this shape to the
1.220 + V /----------------| current scanline y, we must
1.221 + /-----------------| compute the x values of the
1.222 + a /----| |---| points a, b, c, and d.
1.223 + - - - * * - - - - * * - - y -
1.224 + / / b c| |d
1.225 +
1.226 +
1.227 + /---/ |---|
1.228 + /---/ |---| And then turn on the spans a-b
1.229 + /---/ |---| and c-d.
1.230 + /---/_______|---|
1.231 + /----------------|
1.232 + /-----------------|
1.233 + a /----| |---|
1.234 + - - - ####### - - - - ##### - - y -
1.235 + / / b c| |d
1.236 +
1.237 +
1.238 + b. Decomposing Outlines into Profiles
1.239 +
1.240 + For each scanline during the sweep, we need the following
1.241 + information:
1.242 +
1.243 + o The number of spans on the current scanline, given by the
1.244 + number of shape points intersecting the scanline (these are
1.245 + the points a, b, c, and d in the above example).
1.246 +
1.247 + o The x coordinates of these points.
1.248 +
1.249 + x coordinates are computed before the sweep, in a phase called
1.250 + `decomposition' which converts the glyph into *profiles*.
1.251 +
1.252 + Put it simply, a `profile' is a contour's portion that can only
1.253 + be either ascending or descending, i.e., it is monotonic in the
1.254 + vertical direction (we also say y-monotonic). There is no such
1.255 + thing as a horizontal profile, as we shall see.
1.256 +
1.257 + Here are a few examples:
1.258 +
1.259 +
1.260 + this square
1.261 + 1 2
1.262 + ---->---- is made of two
1.263 + | | | |
1.264 + | | profiles | |
1.265 + ^ v ^ + v
1.266 + | | | |
1.267 + | | | |
1.268 + ----<----
1.269 +
1.270 + up down
1.271 +
1.272 +
1.273 + this triangle
1.274 +
1.275 + P2 1 2
1.276 +
1.277 + |\ is made of two | \
1.278 + ^ | \ \ | \
1.279 + | | \ \ profiles | \ |
1.280 + | | \ v ^ | \ |
1.281 + | \ | | + \ v
1.282 + | \ | | \
1.283 + P1 ---___ \ ---___ \
1.284 + ---_\ ---_ \
1.285 + <--__ P3 up down
1.286 +
1.287 +
1.288 +
1.289 + A more general contour can be made of more than two profiles:
1.290 +
1.291 + __ ^
1.292 + / | / ___ / |
1.293 + / | / | / | / |
1.294 + | | / / => | v / /
1.295 + | | | | | | ^ |
1.296 + ^ | |___| | | ^ + | + | + v
1.297 + | | | v | |
1.298 + | | | up |
1.299 + |___________| | down |
1.300 +
1.301 + <-- up down
1.302 +
1.303 +
1.304 + Successive profiles are always joined by horizontal segments
1.305 + that are not part of the profiles themselves.
1.306 +
1.307 + For the rasterizer, a profile is simply an *array* that
1.308 + associates one horizontal *pixel* coordinate to each bitmap
1.309 + *scanline* crossed by the contour's section containing the
1.310 + profile. Note that profiles are *oriented* up or down along the
1.311 + glyph's original flow orientation.
1.312 +
1.313 + In other graphics libraries, profiles are also called `edges' or
1.314 + `edgelists'.
1.315 +
1.316 +
1.317 + c. The Render Pool
1.318 +
1.319 + FreeType has been designed to be able to run well on _very_
1.320 + light systems, including embedded systems with very few memory.
1.321 +
1.322 + A render pool will be allocated once; the rasterizer uses this
1.323 + pool for all its needs by managing this memory directly in it.
1.324 + The algorithms that are used for profile computation make it
1.325 + possible to use the pool as a simple growing heap. This means
1.326 + that this memory management is actually quite easy and faster
1.327 + than any kind of malloc()/free() combination.
1.328 +
1.329 + Moreover, we'll see later that the rasterizer is able, when
1.330 + dealing with profiles too large and numerous to lie all at once
1.331 + in the render pool, to immediately decompose recursively the
1.332 + rendering process into independent sub-tasks, each taking less
1.333 + memory to be performed (see `sub-banding' below).
1.334 +
1.335 + The render pool doesn't need to be large. A 4KByte pool is
1.336 + enough for nearly all renditions, though nearly 100% slower than
1.337 + a more comfortable 16KByte or 32KByte pool (that was tested with
1.338 + complex glyphs at sizes over 500 pixels).
1.339 +
1.340 +
1.341 + d. Computing Profiles Extents
1.342 +
1.343 + Remember that a profile is an array, associating a _scanline_ to
1.344 + the x pixel coordinate of its intersection with a contour.
1.345 +
1.346 + Though it's not exactly how the FreeType rasterizer works, it is
1.347 + convenient to think that we need a profile's height before
1.348 + allocating it in the pool and computing its coordinates.
1.349 +
1.350 + The profile's height is the number of scanlines crossed by the
1.351 + y-monotonic section of a contour. We thus need to compute these
1.352 + sections from the vectorial description. In order to do that,
1.353 + we are obliged to compute all (local and global) y extrema of
1.354 + the glyph (minima and maxima).
1.355 +
1.356 +
1.357 + P2 For instance, this triangle has only
1.358 + two y-extrema, which are simply
1.359 + |\
1.360 + | \ P2.y as a vertical maximum
1.361 + | \ P3.y as a vertical minimum
1.362 + | \
1.363 + | \ P1.y is not a vertical extremum (though
1.364 + | \ it is a horizontal minimum, which we
1.365 + P1 ---___ \ don't need).
1.366 + ---_\
1.367 + P3
1.368 +
1.369 +
1.370 + Note that the extrema are expressed in pixel units, not in
1.371 + scanlines. The triangle's height is certainly (P3.y-P2.y+1)
1.372 + pixel units, but its profiles' heights are computed in
1.373 + scanlines. The exact conversion is simple:
1.374 +
1.375 + - min scanline = FLOOR ( min y )
1.376 + - max scanline = CEILING( max y )
1.377 +
1.378 + A problem arises with Bézier Arcs. While a segment is always
1.379 + necessarily y-monotonic (i.e., flat, ascending, or descending),
1.380 + which makes extrema computations easy, the ascent of an arc can
1.381 + vary between its control points.
1.382 +
1.383 +
1.384 + P2
1.385 + *
1.386 + # on curve
1.387 + * off curve
1.388 + __-x--_
1.389 + _-- -_
1.390 + P1 _- - A non y-monotonic Bézier arc.
1.391 + # \
1.392 + - The arc goes from P1 to P3.
1.393 + \
1.394 + \ P3
1.395 + #
1.396 +
1.397 +
1.398 + We first need to be able to easily detect non-monotonic arcs,
1.399 + according to their control points. I will state here, without
1.400 + proof, that the monotony condition can be expressed as:
1.401 +
1.402 + P1.y <= P2.y <= P3.y for an ever-ascending arc
1.403 +
1.404 + P1.y >= P2.y >= P3.y for an ever-descending arc
1.405 +
1.406 + with the special case of
1.407 +
1.408 + P1.y = P2.y = P3.y where the arc is said to be `flat'.
1.409 +
1.410 + As you can see, these conditions can be very easily tested.
1.411 + They are, however, extremely important, as any arc that does not
1.412 + satisfy them necessarily contains an extremum.
1.413 +
1.414 + Note also that a monotonic arc can contain an extremum too,
1.415 + which is then one of its `on' points:
1.416 +
1.417 +
1.418 + P1 P2
1.419 + #---__ * P1P2P3 is ever-descending, but P1
1.420 + -_ is an y-extremum.
1.421 + -
1.422 + ---_ \
1.423 + -> \
1.424 + \ P3
1.425 + #
1.426 +
1.427 +
1.428 + Let's go back to our previous example:
1.429 +
1.430 +
1.431 + P2
1.432 + *
1.433 + # on curve
1.434 + * off curve
1.435 + __-x--_
1.436 + _-- -_
1.437 + P1 _- - A non-y-monotonic Bézier arc.
1.438 + # \
1.439 + - Here we have
1.440 + \ P2.y >= P1.y &&
1.441 + \ P3 P2.y >= P3.y (!)
1.442 + #
1.443 +
1.444 +
1.445 + We need to compute the vertical maximum of this arc to be able
1.446 + to compute a profile's height (the point marked by an `x'). The
1.447 + arc's equation indicates that a direct computation is possible,
1.448 + but we rely on a different technique, which use will become
1.449 + apparent soon.
1.450 +
1.451 + Bézier arcs have the special property of being very easily
1.452 + decomposed into two sub-arcs, which are themselves Bézier arcs.
1.453 + Moreover, it is easy to prove that there is at most one vertical
1.454 + extremum on each Bézier arc (for second-degree curves; similar
1.455 + conditions can be found for third-order arcs).
1.456 +
1.457 + For instance, the following arc P1P2P3 can be decomposed into
1.458 + two sub-arcs Q1Q2Q3 and R1R2R3:
1.459 +
1.460 +
1.461 + P2
1.462 + *
1.463 + # on curve
1.464 + * off curve
1.465 +
1.466 +
1.467 + original Bézier arc P1P2P3.
1.468 + __---__
1.469 + _-- --_
1.470 + _- -_
1.471 + - -
1.472 + / \
1.473 + / \
1.474 + # #
1.475 + P1 P3
1.476 +
1.477 +
1.478 +
1.479 + P2
1.480 + *
1.481 +
1.482 +
1.483 +
1.484 + Q3 Decomposed into two subarcs
1.485 + Q2 R2 Q1Q2Q3 and R1R2R3
1.486 + * __-#-__ *
1.487 + _-- --_
1.488 + _- R1 -_ Q1 = P1 R3 = P3
1.489 + - - Q2 = (P1+P2)/2 R2 = (P2+P3)/2
1.490 + / \
1.491 + / \ Q3 = R1 = (Q2+R2)/2
1.492 + # #
1.493 + Q1 R3 Note that Q2, R2, and Q3=R1
1.494 + are on a single line which is
1.495 + tangent to the curve.
1.496 +
1.497 +
1.498 + We have then decomposed a non-y-monotonic Bézier curve into two
1.499 + smaller sub-arcs. Note that in the above drawing, both sub-arcs
1.500 + are monotonic, and that the extremum is then Q3=R1. However, in
1.501 + a more general case, only one sub-arc is guaranteed to be
1.502 + monotonic. Getting back to our former example:
1.503 +
1.504 +
1.505 + Q2
1.506 + *
1.507 +
1.508 + __-x--_ R1
1.509 + _-- #_
1.510 + Q1 _- Q3 - R2
1.511 + # \ *
1.512 + -
1.513 + \
1.514 + \ R3
1.515 + #
1.516 +
1.517 +
1.518 + Here, we see that, though Q1Q2Q3 is still non-monotonic, R1R2R3
1.519 + is ever descending: We thus know that it doesn't contain the
1.520 + extremum. We can then re-subdivide Q1Q2Q3 into two sub-arcs and
1.521 + go on recursively, stopping when we encounter two monotonic
1.522 + subarcs, or when the subarcs become simply too small.
1.523 +
1.524 + We will finally find the vertical extremum. Note that the
1.525 + iterative process of finding an extremum is called `flattening'.
1.526 +
1.527 +
1.528 + e. Computing Profiles Coordinates
1.529 +
1.530 + Once we have the height of each profile, we are able to allocate
1.531 + it in the render pool. The next task is to compute coordinates
1.532 + for each scanline.
1.533 +
1.534 + In the case of segments, the computation is straightforward,
1.535 + using the Euclidean algorithm (also known as Bresenham).
1.536 + However, for Bézier arcs, the job is a little more complicated.
1.537 +
1.538 + We assume that all Béziers that are part of a profile are the
1.539 + result of flattening the curve, which means that they are all
1.540 + y-monotonic (ascending or descending, and never flat). We now
1.541 + have to compute the intersections of arcs with the profile's
1.542 + scanlines. One way is to use a similar scheme to flattening
1.543 + called `stepping'.
1.544 +
1.545 +
1.546 + Consider this arc, going from P1 to
1.547 + --------------------- P3. Suppose that we need to
1.548 + compute its intersections with the
1.549 + drawn scanlines. As already
1.550 + --------------------- mentioned this can be done
1.551 + directly, but the involved
1.552 + * P2 _---# P3 algorithm is far too slow.
1.553 + ------------- _-- --
1.554 + _-
1.555 + _/ Instead, it is still possible to
1.556 + ---------/----------- use the decomposition property in
1.557 + / the same recursive way, i.e.,
1.558 + | subdivide the arc into subarcs
1.559 + ------|-------------- until these get too small to cross
1.560 + | more than one scanline!
1.561 + |
1.562 + -----|--------------- This is very easily done using a
1.563 + | rasterizer-managed stack of
1.564 + | subarcs.
1.565 + # P1
1.566 +
1.567 +
1.568 + f. Sweeping and Sorting the Spans
1.569 +
1.570 + Once all our profiles have been computed, we begin the sweep to
1.571 + build (and fill) the spans.
1.572 +
1.573 + As both the TrueType and Type 1 specifications use the winding
1.574 + fill rule (but with opposite directions), we place, on each
1.575 + scanline, the present profiles in two separate lists.
1.576 +
1.577 + One list, called the `left' one, only contains ascending
1.578 + profiles, while the other `right' list contains the descending
1.579 + profiles.
1.580 +
1.581 + As each glyph is made of closed curves, a simple geometric
1.582 + property ensures that the two lists contain the same number of
1.583 + elements.
1.584 +
1.585 + Creating spans is thus straightforward:
1.586 +
1.587 + 1. We sort each list in increasing horizontal order.
1.588 +
1.589 + 2. We pair each value of the left list with its corresponding
1.590 + value in the right list.
1.591 +
1.592 +
1.593 + / / | | For example, we have here
1.594 + / / | | four profiles. Two of
1.595 + >/ / | | | them are ascending (1 &
1.596 + 1// / ^ | | | 2 3), while the two others
1.597 + // // 3| | | v are descending (2 & 4).
1.598 + / //4 | | | On the given scanline,
1.599 + a / /< | | the left list is (1,3),
1.600 + - - - *-----* - - - - *---* - - y - and the right one is
1.601 + / / b c| |d (4,2) (sorted).
1.602 +
1.603 + There are then two spans, joining
1.604 + 1 to 4 (i.e. a-b) and 3 to 2
1.605 + (i.e. c-d)!
1.606 +
1.607 +
1.608 + Sorting doesn't necessarily take much time, as in 99 cases out
1.609 + of 100, the lists' order is kept from one scanline to the next.
1.610 + We can thus implement it with two simple singly-linked lists,
1.611 + sorted by a classic bubble-sort, which takes a minimum amount of
1.612 + time when the lists are already sorted.
1.613 +
1.614 + A previous version of the rasterizer used more elaborate
1.615 + structures, like arrays to perform `faster' sorting. It turned
1.616 + out that this old scheme is not faster than the one described
1.617 + above.
1.618 +
1.619 + Once the spans have been `created', we can simply draw them in
1.620 + the target bitmap.
1.621 +
1.622 +------------------------------------------------------------------------
1.623 +
1.624 +Copyright 2003, 2007 by
1.625 +David Turner, Robert Wilhelm, and Werner Lemberg.
1.626 +
1.627 +This file is part of the FreeType project, and may only be used,
1.628 +modified, and distributed under the terms of the FreeType project
1.629 +license, LICENSE.TXT. By continuing to use, modify, or distribute this
1.630 +file you indicate that you have read the license and understand and
1.631 +accept it fully.
1.632 +
1.633 +
1.634 +--- end of raster.txt ---
1.635 +
1.636 +Local Variables:
1.637 +coding: utf-8
1.638 +End:
