📄 raster.txt
字号:
How FreeType's rasterizer work
by David Turner
Revised 2003-Dec-08
This file is an attempt to explain the internals of the FreeType
rasterizer. The rasterizer is of quite general purpose and could
easily be integrated into other programs.
I. Introduction
II. Rendering Technology
1. Requirements
2. Profiles and Spans
a. Sweeping the Shape
b. Decomposing Outlines into Profiles
c. The Render Pool
d. Computing Profiles Extents
e. Computing Profiles Coordinates
f. Sweeping and Sorting the Spans
I. Introduction
===============
A rasterizer is a library in charge of converting a vectorial
representation of a shape into a bitmap. The FreeType rasterizer
has been originally developed to render the glyphs found in
TrueType files, made up of segments and second-order B閦iers.
Meanwhile it has been extended to render third-order B閦ier curves
also. This document is an explanation of its design and
implementation.
While these explanations start from the basics, a knowledge of
common rasterization techniques is assumed.
II. Rendering Technology
========================
1. Requirements
---------------
We assume that all scaling, rotating, hinting, etc., has been
already done. The glyph is thus described by a list of points in
the device space.
- All point coordinates are in the 26.6 fixed float format. The
used orientation is:
^ y
| reference orientation
|
*----> x
0
`26.6' means that 26 bits are used for the integer part of a
value and 6 bits are used for the fractional part.
Consequently, the `distance' between two neighbouring pixels is
64 `units' (1 unit = 1/64th of a pixel).
Note that, for the rasterizer, pixel centers are located at
integer coordinates. The TrueType bytecode interpreter,
however, assumes that the lower left edge of a pixel (which is
taken to be a square with a length of 1 unit) has integer
coordinates.
^ y ^ y
| |
| (1,1) | (0.5,0.5)
+-----------+ +-----+-----+
| | | | |
| | | | |
| | | o-----+-----> x
| | | (0,0) |
| | | |
o-----------+-----> x +-----------+
(0,0) (-0.5,-0.5)
TrueType bytecode interpreter FreeType rasterizer
A pixel line in the target bitmap is called a `scanline'.
- A glyph is usually made of several contours, also called
`outlines'. A contour is simply a closed curve that delimits an
outer or inner region of the glyph. It is described by a series
of successive points of the points table.
Each point of the glyph has an associated flag that indicates
whether it is `on' or `off' the curve. Two successive `on'
points indicate a line segment joining the two points.
One `off' point amidst two `on' points indicates a second-degree
(conic) B閦ier parametric arc, defined by these three points
(the `off' point being the control point, and the `on' ones the
start and end points). Similarly, a third-degree (cubic) B閦ier
curve is described by four points (two `off' control points
between two `on' points).
Finally, for second-order curves only, two successive `off'
points forces the rasterizer to create, during rendering, an
`on' point amidst them, at their exact middle. This greatly
facilitates the definition of successive B閦ier arcs.
The parametric form of a second-order B閦ier curve is:
P(t) = (1-t)^2*P1 + 2*t*(1-t)*P2 + t^2*P3
(P1 and P3 are the end points, P2 the control point.)
The parametric form of a third-order B閦ier curve is:
P(t) = (1-t)^3*P1 + 3*t*(1-t)^2*P2 + 3*t^2*(1-t)*P3 + t^3*P4
(P1 and P4 are the end points, P2 and P3 the control points.)
For both formulae, t is a real number in the range [0..1].
Note that the rasterizer does not use these formulae directly.
They exhibit, however, one very useful property of B閦ier arcs:
Each point of the curve is a weighted average of the control
points.
As all weights are positive and always sum up to 1, whatever the
value of t, each arc point lies within the triangle (polygon)
defined by the arc's three (four) control points.
In the following, only second-order curves are discussed since
rasterization of third-order curves is completely identical.
Here some samples for second-order curves.
* # on curve
* off curve
__---__
#-__ _-- -_
--__ _- -
--__ # \
--__ #
-#
Two `on' points
Two `on' points and one `off' point
between them
*
# __ Two `on' points with two `off'
\ - - points between them. The point
\ / \ marked `0' is the middle of the
- 0 \ `off' points, and is a `virtual
-_ _- # on' point where the curve passes.
-- It does not appear in the point
* list.
2. Profiles and Spans
---------------------
The following is a basic explanation of the _kind_ of computations
made by the rasterizer to build a bitmap from a vector
representation. Note that the actual implementation is slightly
different, due to performance tuning and other factors.
However, the following ideas remain in the same category, and are
more convenient to understand.
a. Sweeping the Shape
The best way to fill a shape is to decompose it into a number of
simple horizontal segments, then turn them on in the target
bitmap. These segments are called `spans'.
__---__
_-- -_
_- -
- \
/ \
/ \
| \
__---__ Example: filling a shape
_----------_ with spans.
_--------------
----------------\
/-----------------\ This is typically done from the top
/ \ to the bottom of the shape, in a
| | \ movement called a `sweep'.
V
__---__
_----------_
_--------------
----------------\
/-----------------\
/-------------------\
|---------------------\
In order to draw a span, the rasterizer must compute its
coordinates, which are simply the x coordinates of the shape's
contours, taken on the y scanlines.
/---/ |---| Note that there are usually
/---/ |---| several spans per scanline.
| /---/ |---|
| /---/_______|---| When rendering this shape to the
V /----------------| current scanline y, we must
/-----------------| compute the x values of the
a /----| |---| points a, b, c, and d.
- - - * * - - - - * * - - y -
/ / b c| |d
/---/ |---|
/---/ |---| And then turn on the spans a-b
/---/ |---| and c-d.
/---/_______|---|
/----------------|
/-----------------|
a /----| |---|
- - - ####### - - - - ##### - - y -
/ / b c| |d
b. Decomposing Outlines into Profiles
For each scanline during the sweep, we need the following
information:
o The number of spans on the current scanline, given by the
number of shape points intersecting the scanline (these are
the points a, b, c, and d in the above example).
o The x coordinates of these points.
x coordinates are computed before the sweep, in a phase called
`decomposition' which converts the glyph into *profiles*.
Put it simply, a `profile' is a contour's portion that can only
be either ascending or descending, i.e., it is monotonic in the
vertical direction (we also say y-monotonic). There is no such
thing as a horizontal profile, as we shall see.
Here are a few examples:
this square
1 2
---->---- is made of two
| | | |
| | profiles | |
^ v ^ + v
| | | |
| | | |
----<----
up down
this triangle
P2 1 2
|\ is made of two | \
^ | \ \ | \
| | \ \ profiles | \ |
| | \ v ^ | \ |
| \ | | + \ v
| \ | | \
P1 ---___ \ ---___ \
---_\ ---_ \
<--__ P3 up down
A more general contour can be made of more than two profiles:
__ ^
/ | / ___ / |
/ | / | / | / |
| | / / => | v / /
| | | | | | ^ |
^ | |___| | | ^ + | + | + v
| | | v | |
| | | up |
|___________| | down |
<-- up down
Successive profiles are always joined by horizontal segments
that are not part of the profiles themselves.
For the rasterizer, a profile is simply an *array* that
associates one horizontal *pixel* coordinate to each bitmap
*scanline* crossed by the contour's section containing the
profile. Note that profiles are *oriented* up or down along the
glyph's original flow orientation.
In other graphics libraries, profiles are also called `edges' or
`edgelists'.
c. The Render Pool
FreeType has been designed to be able to run well on _very_
light systems, including embedded systems with very few memory.
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -