Scaling and positioning in RES

Introduction

Here we sketch the scaling and positioning algorithms that are assumed for RES. These algorithms may differ somewhat from those that have been developed by others for MdC, but this is difficult to determine precisely, since no such algorithms have been published, as far as I know.

To simplify the presentation, I will restrict myself here to the two operators ':' and '*'.

Assumptions

We assume there is a basic unit of length, referred to here as EM. In traditional typography, EM stands for the width of the capital letter 'M'. For hieroglyphic we primarily assume it corresponds to the height of a high glyph such as 'A1', which may be roughly equal to the width of a wide glyph such as 'N37'. Although such a unit of length could alternatively be called EX (the height of the capital letter 'X', it seems more practical to use the name EM, as common representations of fonts, such as TrueType, allow EM to be specified explicitly, but not EX.

We will refer to the dimensions of a glyph in the font as its natural size, i.e. the size the glyph has before any scaling is done. Although in most reasonable fonts 'A1' has height 1 EM, dimensions of other glyphs may differ somewhat. E.g. the height of 'X1' may be 0.25 EM in one font and 0.30 EM in another. To be more precise, we assume the natural height and width of glyphs to be determined by the height and width of the bounding boxes around them. This also holds for rotated glyphs, and the bounding boxes remain orientated w.r.t. the normal x-axis and y-axis.

Furthermore, we assume there is a parameter of the scaling algorithm referred to as the unit size or US, which is a length expressed in terms of EM. It is used for determining how much subgroups of a vert_group (i.e. a group composed by the operator ':') or hor_group (i.e. a group composed by the operator '*') need to be scaled down. The sub_groups that are wider or higher, resp., than 1 US are scaled down to become precisely 1 US wide or high, but those that are not will keep their sizes, which may be less than 1 US. (We never scale up.) Normally 1 US equals 1 EM, but in RES one may also specify other unit sizes.

There is furthermore a value that we will call SEP here. This is the minimum distance between subgroups of a vert_group or hor_group, before this vert_group or hor_group is itself scaled down. A typical value for SEP, which is determined by the font, may be somewhere in the order of 0.15 EM.

To keep the presentation simple, we will discuss scaling and positioning as if it were done by one single algorithm. This algorithm basically works bottom-up, but with one top-down step at each level. The algorithm is bottom-up in the sense that after scaling has been performed for a subgroup, its individual glyphs thereafter maintain their relative sizes when the entire subgroup must be scaled down due to its composition with one or more neighbouring subgroups. However, the amount of white space within, say, the vert_groups in a hor_group, can only be determined after all vert_groups in that hor_group have been scaled, and this requires one top-down step before computation resumes in the normal bottom-up fashion.

Notation

For convenience, we represent groups as Prolog terms. Allowable terms indicating top_groups are described by the following context-free grammar.

TOPGROUP -> VERTGROUP |
            HORGROUP |
            'g(' G ')'

VERTGROUP -> ':(' VERTSUBS ')'

VERTSUBS -> '[' VERTSUB ',' VERTSUB ']' |
            '[' VERTSUB '|' VERTSUBS ']'

VERTSUB -> HORGROUP |
           'g(' G ')'

HORGROUP -> '*(' HORSUBS ')'

HORSUBS -> '[' HORSUB ',' HORSUB ']' |
           '[' HORSUB '|' HORSUBS ']'

HORSUB -> VERTGROUP |
          'g(' G ')'

G -> 'A1' | 'A2' | ... i.e. all glyphs ...

As in most logical and functional programming languages, we assume that e.g. [ E1 | [E2, E3] ] and [E1, E2, E3] denote the same list. Thus, a VERTGROUP consists of functor ':' with an argument that is a list of at least 2 elements, each of which is a VERTSUB.

During execution of the algorithm, occurrences of glyphs will be assigned three values, and these occurrences will be represented as extended terms g(G,F,W,H), where F represents a factor that indicates by how much a glyph needs to be scaled down, and W and H represent the total amount of white space that needs to surround the glyph to the left and right ('W' is for 'width'), and to the top and bottom respectively ('H' is for 'height'). Initially, F is 1, and W and H are both 0. A typical case where H is nonzero is if a glyph occurs in isolation in a row, and this row is higher than the natural height of the glyph.

The same value W as above is also maintained at vert_groups, and the value H is maintained at hor_groups. In addition, groups obtain an argument that indicates the amount S of white space that should occur between each pair of consecutive subgroups. Initially this value is SEP. Thus groups are represented by terms of the form :(Ts,S,W) or *(Ts,S,H).

The width and height of terms are given by the following definitions:

width(g(G,F,W,H)) = F * width(G) + W
width(:(Ts,S,W)) = max(map width Ts) + W
width(*(Ts,S,H)) = sum(map width Ts) + S * (length(Ts) - 1)

height(g(G,F,W,H)) = F * height(G) + H
height(:(Ts,S,W)) = sum(map height Ts) + S * (length(Ts) - 1)
height(*(Ts,S,H)) = max(map height Ts) + H

where we assume that width(G) and height(G) yield the natural height and width of a glyph G. We further assume sum, max, and length compute the sum, the maximum, and the length of a list, and map is defined by:

map f [a_1,a_2,...,a_n] = [f(a_1),f(a_2),...,f(a_n)]

Below we will also use a function lambda informally defined by:

(lambda T exp(T)) v = exp(v)

where exp(T) denotes some expression with subexpression T.

The algorithm

We can now give the pseudo-code for the scaling and positioning algorithm. It consists of the function scale, which is applied on a term T denoting a top_group. The second and third arguments are positive sizes to express restrictions on the width or height, or they are 0 to indicate there are no such restrictions. The second argument is the width of a column if the text direction is vertical, and 0 otherwise. The third argument is the height of a row if the direction is horizontal, and 0 otherwise.

scale(g(G), W, H) = T_4
	where
	    T_0 = g(G,1,0,0)
	    T_1 = if W == 0
                   then T_0
                   else scale_down(T_0, min(1,W/width(T_0))
            T_2 = if H == 0
                   then T_1
                   else scale_down(T_1, min(1,H/height(T_1))
	    W' = max(W, width(T_2))
	    H' = max(H, height(T_2))
	    T_3 = distribute_width(T_2,W')
	    T_4 = distribute_height(T_3,H')
scale(:(Ts), W, H) = T_8
        where 
	    Ts_1 = map ( lambda T scale(T,0,0) ) Ts
	    Ts_2 = map ( lambda T scale_down(T,min(1,US/width(T) ) Ts_1
	    W' = max(map width Ts_2)
	    Ts_3 = map ( lambda T distribute_width(T,W') ) Ts_2
	    T_4 = :(Ts_3,SEP,0)
	    T_5 = if W == 0
		   then T_4
		   else scale_down(T_4, min(1,W/width(T_4))
	    T_6 = if H == 0
		   then T_5
		   else scale_down(T_5, min(1,H/height(T_5))
	    W'' = max(W, width(T_6))
	    H'' = max(H, height(T_6))
	    T_7 = distribute_width(T_6, W'')
	    T_8 = distribute_height(T_7, H'')
scale(*(Ts),W,H) = T_8
	where
        ...analogous...

where min obviously computes the minimum of its arguments.

We see that an isolated glyph is scaled down if the context dictates restrictions on width or height, and the glyph is centered if it is smaller than what the context dictates, by distributing surplus width or height. Note we never scale up, which explains the use of function min with first argument 1.

For a vert_group, we first apply the scaling algorithm recursively on each subgroup, and then scale down those subgroups that are wider than 1 US. The largest subgroup determines how wide the vert_group will be, and in the other subgroups we insert white space to match that width.

Thereafter we may scale down the vert_group in its entirety if needed to fit within the constraints of parameters W or H, and we distribute surplus width or height if the vert_group is smaller than what the context dictates.

The function scale_down makes all glyphs and white space in a group smaller, by a factor smaller than or equal to 1.

scale_down(g(G,F,W,H), F') = g(G, F'*F, F'*W, F'*H)
scale_down(:(Ts,S,W), F) = :(Ts', F*S, F*W)
        where 
	    Ts' = map (lambda T scale_down(T,F)) Ts
scale_down(*(Ts,S,H), F) = *(Ts', F*S, F*H)
        where 
	    Ts' = map (lambda T scale_down(T,F)) Ts

The function distribute_width distributes horizontal white space to make a glyph or group of glyphs the required width. In the case of a single glyph or a vert_group, it distributes the white space on the left and right. In the case of a hor_group however, the space is distributed evenly between the subgroups.

distribute_width(g(G,F,W,H), W') = g(G, F, W + W'', H)
        where
            W'' = W' - width(g(G,F,W,H))
distribute_width(:(Ts,S,W), W') = :(Ts, S, W + W'')
        where
	    W'' = W' - width(:(Ts,S,W))
distribute_width(*(Ts,S,H), W') = *(Ts, S + S', H)
        where
            S' = ( W' - width(*(Ts,S,H)) ) / (length(Ts)-1)

Note that W' above can never be negative due to the way it is called by scale.

The function distribute_height is analogous.

Separations between glyphs

In the above, we assumed a fixed value SEP. In reality, the minimum amount of separation between glyphs or groups of glyphs is determined by various factors. E.g. for an unscaled hor_group, the minimum distance between two subgroups is the product of three values:

The 'sep' value of the font, specified in the fonts file.
The 'sep' factor that can be influenced within RES, locally by arguments at operators, and globally in switches.
We investigate the glyphs occurring right-most in the left group and those occurring left-most in the right group, in other words, the glyph that border on the separation between the two groups. We determine how much these have already been scaled down, and take the maximum of these scaling factors.

Naturally, if the entire hor_group is scaled down, the distance computed in this way is multiplied by yet another factor.

That we investigate the glyphs internally in both subgroups is motivated by cases such as '(A1:A1)*(A1:A1)' versus 'A1*A1:A1*A1'. We would expect that both have roughly the same appearance, and that is indeed achieved here, since the '*' between the two occurrences of '(A1:A1)' introduces a smaller amount of white space than it would between two unscaled glyphs.

For the function insert, we do not investigate how much the glyphs in the first top_group have been scaled down, but we do investigate those in the second top_group that may border on the first top_group. Which those are depends on the specified place.

For boxes, we have a separate 'sep' value that is determined by the font. This is multiplied by the values for 'opensep' and 'closesep'. For 'undersep' and 'oversep' however, this only holds up to a value of 1, and a second linear mapping is used for values greater than 1, to ensure that a value of 10 represents half the inner distance between the two sides of the box; note that 9.99 is the largest real in RES.

Further issues

The fitting of subgroups can be conveniently incorporated into the algorithm above. This is to be done just before
```
	    T_4 = :(Ts_3,SEP,0)
```
in the definition of scale, and SEP here is to be replaced by the outcome of the fitting algorithm, which is possibly a negative number.
The algorithm is better not implemented literally as outlined above in light of rounding-off errors. Those errors originate in the rendering process of the font, which maps glyphs onto some discrete grid of pixels. It is best to do most of the scaling algorithm on the basis of integers, except at the level of individual glyphs, where floating-point numbers are maintained that indicate how much glyphs need to be scaled down, but the actual sizes are measured in terms of pixels after rendering.