Renewed interest in improving the layout algorithm (for use in the
non-activity zoom levels) has prompted me to create a document
summarizing the goals of the layout, the current approach, and a few
alternate approaches for consideration. My primary goal was to
specify the requirements we wish to evaluate the possible approaches
against, and to clarify my (potentially naive) first attempt at
satisfying them. My hope is that others will see obvious ways to
improve the current approach, or have much better solutions they can
put forward (preferably in code!).
Please see the attached document for details. Thanks!
- Eben
A SEMI-SMART LAYOUT ALGORITHM FOR FREEFORM VIEWS
We desire an algorithm which optimizes the placement of a collection of
elements
(the set E) of various sizes (and/or weights) so as to minimize overlap while
also minimizing memory usage and maximizing speed.
1 REQUIREMENTS
We'll discuss the merits and limitations of proposed algorithms based upon
their
adherence with a general set of requirements, in addition to their memory
requirements and speed. The set of requirements we hope to fulfill are:
1. Minimize overlap of elements
2. Support a suggested position for each element
3. Support a suggested radius for each element (in a polar coordinate system)
4. Support addition and removal of elements
5. Support changes in size of elements (both expansion and contraction)
6. Support fixed elements (locked in place)
Other considerations include minimizing the total amount of positional change
incurred by a given operation on the layout (addition, removal, scaling, etc.).
Since the goal is to have a smooth layout in which elements shift (animated)
into place, we hope to minimize both the number of elements that need to move
and the distance they need to move for any given operation.
2 THE CURRENT ALGORITHM
The algorithm currently proposed (although it differs in several key ways from
that currently implemented in Sugar) makes use of a weight matrix to make
optimal placements, and uses a simple collision detection scheme to handle
addition, removal, and scaling of elements.
2.1 The grid
The algorithm is built upon a weight matrix which tracks the placement of all
elements. This matrix manifests as a 2D integer array containing values in the
range [0, 255].
When visualizing the matrix, think instead of an image, where each cell
represents a pixel, and the value stored at (x,y) represents the brightness of
that pixel. Think of this image as a topographical map of sorts, with bright
areas representing peaks and dark areas representing valleys.
2.2 Assigning weights
When managing the matrix, we strive to make the weights assigned accurately
represent the topology of the elements in the layout. Given an element, e,
having dimensions m x n, we create an element matrix of the same dimensions
within which which we assign weights to individual cells.
The most correct approach (assuming no knowledge about the element other than
its dimensions) is to apply weights to the cells of the element matrix in a
gaussian fashion, such that the element is represented as a rounded surface,
with the middle receiving the highest weight. This method is most consistent
with the interpretation of the table as a topographical map, since it results
in
smooth gradients representing hills and valleys, with the centroid given the
highest weight (collisions are "worse" the more they overlap).
However, this approach also takes much effort, since the weight of each cell
must be calculated. By extreme simplification, we could assign a constant
value
to each cell. This uniform approach takes no extra calculation, but results in
a plateau rather than a hill, which poses problems in placement. A better
solution, which takes only trivial calculation, uses a linear gradient. Using
the linear model, we can visualize the element as a pyramid rather than a hill,
which still maintains the important (for placement) property that there is a
delta between two adjacent values.
The following example illustrates a sample of the weights for a 5x5 element.
Note that the three examples are not normalized (themselves, or with respect to
each other).
Gaussian Linear Uniform
0 1 2 1 0 1 1 1 1 1 1 1 1 1 1
1 4 6 4 1 1 2 2 2 1 1 1 1 1 1
2 6 9 6 2 1 2 3 2 1 1 1 1 1 1
1 4 6 4 1 1 2 2 2 1 1 1 1 1 1
0 1 2 1 0 1 1 1 1 1 1 1 1 1 1
Finally, we define the total weight of a given element, W_e, to be the sum over
the weights of the cells of the element matrix.
2.2 Placement
Placement of a new element is relatively straightforward given the weight
matrix, since we can think of finding a good placement as rolling the new
element into a valley - an area of low weight. We define the weight of a given
placement, W_p to be the sum of the weights of the cells of the weight matrix
where the element matrix overlaps. In other words, if we have an element of
dimensions m x n positioned (with its upper left corner) at (x,y), we sum the
cells of the weight matrix (i,j) with i: [y, y + n - 1] and j: [x, x + m - 1].
Placing an element amounts to summing the values of the element matrix with the
weight matrix at the corresponding positions. We can also "pick up" an element
by subtracting it's element matrix.
Rather than finding the truly optimal placement by testing every cell, we
instead make a number of trial placements, retaining the best solution found:
the lowest value of W_p. The algorithm "short-circuits" if a placement is found
such that W_p = 0, since this means there are no collisions at all.
Once we have a best fit placement, we calculate (in O(n) time) the set of
elements, C, which collide with the newly placed element e (and which are not
fixed/locked). The goal is to then "roll" both e and the members of C into
best-fit valleys. We do so by calculating the minimum of the weights of the
current position and the four positions directly adjacent to each element
(left,
right, above, and below). Here you can see why we need weight deltas between
adjacent cells of the element matrix: without, we can end up in a circumstance
where an element is contained completely within another, thus sitting "on the
plateau", such that the weight in all directions is equal to the current weight
even though we should be trying hard to push the new element outside the
containing one.
When the current position for each element in C is better than (or equal to)
all
adjacent positions, we terminate the algorithm. Note also that we do NOT
recurse on collision checks; instead, we only attempt to adjust the position of
the elements which collide directly with the newly placed element.
2.3 Supporting a suggested position and radius
We support suggested positions for elements by skipping the trial step, instead
using the passed coordinate as the input to the remainder of the algorithm.
Supporting a suggested radius is also relatively simple. By creating a
separate
trial algorithm which takes a position and a radius, we can limit the trial
placements to points on the circle of the appropriate radius.
2.4 Scaling
Scaling up is trivial, as we simply subtract the element matrix from the weight
matrix, calculate a new element matrix for the new dimensions of the element,
and then perform the placement algorithm again using its current location.
Scaling down is nearly the same, however we must consider the set of adjacent
elements, A, in addition to the set C of colliding elements. This ensures
that,
as the element shrinks, those around it can roll into the freed space, even if
they weren't colliding with the shrinking element. The rest of the process
remains the same.
Removal, of course, is the same as scaling down, except we don't re-place the
removed element.
3 OPTIMIZATIONS OF THE CURRENT ALGORITHM
3.1 Down-sampling
Naturally, maintaing the weight matrix has large overhead, especially as the
number of pixels increases. We can reduce memory consumption and increase
speed
by down-sampling the grid, allowing each cell to represent more than a single
pixel.
Down-sampling comes at the cost of accuracy, since the placement algorithm can
only return coordinates on the granularity of the grid. This makes it
impossible, for instance, to place an element at exactly (x,y) unless x mod
CELL_SIZE and y mod CELL_SIZE are both equal to 0.
It may also be possible to test placements without summing over the entire
region, since we can assume some amount of continuity in the topology. In
other words, we might check every other cell, or every 4th cell, to determine
the weight of a given placement, W_p. This could drastically reduce the number
of reads into the matrix.
3.2 Quad Trees
Quad trees could be used in place of the table of weights. To conceptualize,
we
recursively divide the area into quads (each node in the tree has 4 children),
and the weight of each node is calculated as the sum of the weights of its
branches.
I'm not entirely certain of the details of this algorithm, or how the boundary
conditions are handled, but overall it's a relatively straightforward
optimization of the grid algorithm. Placement is much faster, since we can
quickly narrow in on the best branch to place in, and the overhead of
maintaining a large matrix of values is overcome.
4 OTHER POSSIBLE ALGORITHMS
4.1 A pseudo-spring algorithm
I'll spend little time describing this algorithm, as it's relatively simple.
The basic concept is similar to the grid algorithm described above, sans grid.
No record of the current configuration is retained. Instead, we find a
potential placement location by trials, minimizing collisions. We then simply
"push" any colliding elements away from the new element by an amount
proportional to their sizes and in the direction of the angle between them.
Without hacking up a simple version of this, it's hard to tell how well it will
behave in practice. It's also unclear to me upon first glance how scaling and
removal should be handled.
4.2 "Real" physics
Using Box2D as an engine for the layout has been proposed. To do so, we need
to
determine what type of physical (and, of course, 2D) simulation will result in
a
system with the desired properties.
The most obvious solution is to take advantage of a much faster and more
accurate collision detection, adjusting the system to minimize overlap
according
to its own algorithms. This has the advantage of providing (I suspect)
near-zero overlap among ALL elements (not just those colliding with the placed
element), since it will recursively perform checks against all elements.
However, this also means that it's likely to cause updates across the entire
screen for nearly every operation when the screen is somewhat dense, which
could
have adverse effects on the animation of the elements into their assigned
positions.
Another alternative would include use of springs, electrically charged
particles, or both, though I think these types of systems (which are often used
in generating force directed graphs) tend to run on order n-cubed in the number
of nodes (elements).
_______________________________________________
Sugar mailing list
[email protected]
http://lists.laptop.org/listinfo/sugar
