Jump:
Tesi

Create personal sidebar
Tesi.TallEnginer1.21 - 25 Jul 2007 - 17:10 - LucaFurinitopic end

# Tall Engine

## "Abstract" definition of the algorithm

### Nodes of a Tall instance tree

In a Tall instance tree there are two different kinds of nodes:

• atomic objects (tall:object), holding pieces of content
• groups (tall:group and tall:context), holding together atomic objects and other groups and tying them with topological relationships

The engine has to compute / decide:

1. how many areas each object will create
2. what will be si precise size of each area
3. where will each area be positioned

In order to avoid the need to evaluate an exponential number of alternatives, we need to avoid as much as possible taking decisions with a top-down approach, starting from the root node and making several hypotheses each time a group is met; instead, we must follow a bottom-up approach, starting from the leaf nodes and working by "aggregation".

### General algorithm

The general principle is that:

• each atomic object (regadless of its piece of content being FO, SVG or whatever else) can speak with its parent in terms of areas and their dimensions
• each group is in charge of the placement of its direct children's areas

The algorithm is composed of two steps:

1. bottom-up phase: collect information about the potential size of areas
2. top-down phase: set a precise size and position for each area

In the first phase, we have that:

• each atomic object returns information about the areas it will create and their dimensions: the size of each area could either be expressed as a single fixed value or as a range, if there is one or two degrees of freedom
• each group returns to its parent an opaque object that summarizes a limited set of good layout alternatives for the children areas; this size of this object is likely to vary inside a range, because of the presence of under-specified areas or of multiple layouts that could be chosen

At the end of this phase, the "active node" is the Tall tree root (tall:context), which by definition must have a precise width and height.

Than the second phase starts:

• each group is given the width and height of the space it has to occupy, so that it can choose (among the possible layouts found before) the one that fits best, and the width and height of its child
• each atomic object, according to the given size and its properties, displays its piece of content in the allocated space

### Dimensions

In order to define the size of each object (in a rectangular-based model) we need two parameters, picked up among

• width (W)
• height (H)
• aspect ratio (R) (meant as W / H, just to avoid ambiguity)
• area (A)

• if two of them are given an exact value, the other two can be computed and will have fixed values too (0 degrees of freedom)
• if just one of them is given an exact value, the other three are free to vary inside their whole domain (1 degree of freedom); if one of the three is given a range, it is possible to compute the ranges of variation for the other two (1/2 degree of freedom? )
• if no one has an exact value, all four parameters vary inside a range (2 degrees of freedom)

Note: actually, we can always work with limited ranges (so width and height will never vary inside [0, +inf[: each object cannot be bigger than the whole media, or so small to be it can hardly be seen.

If we consider a node in the Tall tree by itself, we could have six different situations:

1. the size of the object is compoletely defined by its own properties: the tall:object will return a fixed width and height, and the tall:group parent can only decide where to put it
2. the width is locked, but the object can be vertically stretched and shrinked
3. the height is locked, but the object can be horizontally stretched and shrinked
4. the aspect ratio is locked, but the object can be proportionally scaled
5. the area is locked, but the object can stretch in either directions (and will shrink in the other one)
6. no parameter of the object is locked

If we consider a node with respect to the whole tall tree, we can see at which point (up along the ancestor-or-self axis) will the remaining degrees of freedom be lost, and if the object is over-constrained.

#### 2 degrees of freedom

If an object has no geometric information that must be preserved, the only limits come from the context width (wC) and height (hC)

known parameters W H R A
no one [0, wC] [0, hC] [0, +inf[ [0, wC * hC]

#### 1 degree of freedom

There is a geometric parameter with a precise and fixed value, and the ranges for the remaining three are computed using context width and height

known parameters W H R A
W w [0, hC] [w / hC, +inf[ [0, w * hC]
H [0, wC] h [0, wC / h] [0, wC * h]
R [0, min{wC, hC * r}] [0, min{hC, wC / r}] r [0, min{wC2 / r, hC2 * r}]
A [a / hC, wC] [a / wC, hC] [a / hC2, wC2 / a] a

In general, the known parameter can have a range value

known parameters W H R A
W [wmin, wmax] [0, hC] [wmin / hC, +inf[ [0, wmax * hC]
R [0, min{wC, hC * rmax}] [0, min{hC, wC / rmin}] [rmin, rmax] [0, min{wC2 / rmin, hC2 * rmax}]
H [0, wC] [hmin, hmax] [0, wC / hmin] [0, wC * hmax]
A [amin / hC, wC] [amin / wC, hC] [amin / hC2, wC2 / amin] [amin, amax]

#### 0 degrees of freedom

If two geometric parameters have a precise value, we can compute the precise value for the other two; the size of the object is completely determined and we do not need any context information

known parameters W H R A
W and H w h w / h w * h
W and R w w / r r w2 / r
W and A w a / w w2 / a a
H and R h * r h r h2 * r
H and A a / h h a / h2 a
R and A sqrt(a * r) sqrt(a / r) r a

In a more general situation, the two known parameters will have a range value: this can happen

• if an object is explicitly given a range value by the user,
• or when there two similarities between a group of objects, some of the objects have precise dimensions (so that some kind of medium value can be computed) and the other ones have no constraint (so they can be set to some range values around the medium ones)

known parameters W H R A
W and H [wmin, wmax] [hmin, hmax] [wmin / hmax, wmax / hmin] [wmin * hmin, wmax * hmax]
W and R [wmin, wmax] [wmin / rmax, wmax / rmin] [rmin, rmax] [wmin2 / rmax, wmax2 / rmin]
W and A [wmin, wmax] [amin / wmax, amax / wmin] [wmin2 / amax, wmax2 / amin] [amin, amax]
H and R [hmin * rmin, hmax * rmax] [hmin, hmax] [rmin, rmax] [hmin2 * rmin, hmax2 * rmax]
H and A [amin / hmax, amax / hmin] [hmin, hmax] [amin / hmax2, amax / hmin2] [amin, amax]
R and A [sqrt(amin * rmin), sqrt(amax * rmax)] [sqrt(amin / rmax), sqrt(amax / rmin)] [rmin, rmax] [amin, amax]

• when we work with fully-specified objects (= objects whose four dimensions are all precise values), we can use the two dimensions that we prefer
• if there is a known value (either a precise one or a range one) and one degree of freedom, we must keep using the parameter with the known value, and another one we like, otherwise when re-computing the other parameters we could obtain different ranges
• if there are two known values (either precise ones or range ones) we must keep using those parameters

In other words, the formulas given before are useful while examining a particular object, but we must keep well clear the distinction between the constrained parameters and the free ones.

### Similarities

The `similarity` property applies to `tall:group` objects, and contains a list of properties whose values should be similar for all the group members; the involved properties can be:

• "direct" geometrical properties: width, height, aspect ratio and area, with a direct mapping upon the parameters we are working on
• "indirect" geometrical properties: they affect a geometric parameter, without being one of them (for example, font-size affects the area of a text object)
• style properties, with no impact on the output geometry (color, background, ...)

#### Similarity set

The first step to perform when the members of a group have some similarities is to define a set of values that are considered "similar enough". This calculation depends on:

• the property datatype
• if it is numberic, then the set of similar values will be a range, and we must just find its minimum and maximum
• if it is a color, there can probably be several ways to define whether (and how much) two colors are similar, each of them using a particular function to compute the "distance" between two colors
• if it is a font family, the panose properties could be used
• ... what else can we have? ...
• the number of the objects having an explicitly set value for that property
• if there is none,
• if there is only a precise value, the similarity set will contain all the values whose distance from the precise value is smaller than a threshold
• if there are several precise values we can compute a "barycentre" and use the threshold to define the similarity set (maybe extending it, if necessary, to include all the precise values)
• if there are range values, the intersection of all the ranges can be a good starting point; should it be empty, we could reduce each range to its barycentre, compute a weighted overall barycentre and finally defining the similarity set using the threshold ( the weight should probably be inversely proportional to the range width)
• if we have both precise and range values, we can always use the weighted barycentre method, using some default weight for the precise values

It must be noticed that all properties (even style properties) are to some extent affected by the layout choice: for example, let us consider a situation like this:

```    <tall:group similarity="color">
<tall:object color="#111111">...</tall:object>
<tall:object>...</tall:object>
<tall:object>...</tall:object>
<tall:object>...</tall:object>
<tall:object color="#EEEEEE" importance="low">...</tall:object>
</tall:group>
```

All the objects should have a "similar" color: if all of them survive in the final output, we expect the initially colourless objects to be some medium grey, but if the unimportant object is discarded we want them to be much more similar to the dark object.

#### Similarity and priority

Similarity relationships define ranges, but in the end a precise value must is needed, and I think that `importance` is the property that can control how to choose it.

If all objects have the same importance, similarity could well become equality.

Otherwise, a property range could be given an "importance direction", stating which side of the range contains the values for important objects (for example, a bigger width / height / area is associated with a higher importance, while lighter colors are less noticeable and should be given to unimportant objects.

## (some contents not yet translated)

Copyright © 1999-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Fabio's Wiki? Send feedback