Given a shape (set of closed trajectories) and a transformation matrix M, we will say that the shape is mapped using M when all points and cubics that comprise each of the shape's trajectories are transformed using M.

Given a shape (set of closed trajectories) in the DCS we will say that the shape is approximated when all cubics, in each of the shape's trajectories, are replaced by piecewise linear approximations. Since the shape is in the DCS, it is possible to make piecewise linear approximations as a function of device resolution.

An approximated shape exists as a collection of polygons, which may be mutually intersecting, self intersecting and concave.

An approximated shape is reduced when the polygons that make up the shape are converted into a collection of disjoint, convex polygons which tile the interior of the shape. The locus of the shape's interior is determined by applying a wrap number convention. There are a number of known tiling algorithms [1,2,3].

An approximated reduced shape will be called clipped if each of its convex polygons has been clipped against the set of the convex polygons that make up a clipping region.

The above concepts are used freely in the process of displaying a shape. Of equal importance is the description of the basic operation that is carried out by the device dependent part of the system.

In situations where high performance is required, character fonts are designed to work with a given display type, i.e., a character is defined to be a mask whose resolution and scanning characteristics are the same as the device's. Also the bounding shape of a character mask is a rectangle. Under these circumstances, the mapping taking the mask in SCS to VCS, when concatenated with the device's mapping from VCS to DCS, will be the identity mapping (with, perhaps, an application-introduced translation component). Since this is the case, the bounding rectangle of the mask will map into a rectangle in the DCS. If in addition the source color is solid black and the bounding rectangle is not clipped, the scan conversion process reduces to the one-to-one transfer of pixels in one rectangle to pixels in another. To avoid checking for the identity transformation for each character, the combined transformation from SCS to VCS to DCS can be noted as an identity in the display context. If no operations that change transformations (other than translation) take place between the display of succesive characters, then no transformation checking need be done.

If any of the above conditions is not true, then the optimization fails and the more general machinery will display the character.

The rotation, scaling and sampling of sources and masks can be computationally expensive. To reduce this computation the following steps are taken (the discussion centers on the handling of sources, but the same discussion applies to masks).

Scan conversion, in the device coordinate system (DCS), is carried out pixel-by-pixel along successive scan lines. If the unit vector (1,0) representing the delta vector between successive pixels in a scan line is mapped through S—1 (the mapping from the device coordinate system to the source coordinate system), then the delta vector ds between required sample positions in the source is obtained. Successive sample positions in the source that correspond to the successive pixels along the scan line can be incrementally computed by mapping the beginning of the scan line in the DCS through S—1, and incrementally adding ds to obtain the position of the next sample to be used in the scan line. This optimization replaces a general point transformation with two additions.

An additional artifact, a bounding rectangle associated with a shape, can be introduced after mapping into the DCS. Bounding rectangles can be used to short cut the amount of computing done by the shape reduction and clipping machinery; i.e., if a bounding rectangle is exterior to the set of clipping regions, then the associated shape need not be processed further. On the other hand, if a bounding rectangle is totally within the clipping region, then the shape need not be clipped since it is totally within the region.