Skip to content

RFC: new ExpoLayout Algorithm

Summary

The ExpoLayout Algorithm is an window layout algorithm, used in the Gridview, Overview, and Present Windows effects. The current algorithm sometimes makes inefficient use of screen space, and can generate undesirable window placements [0].

This RFC discusses issues with the current algorithm, proposes criteria for judging good algorithms, and proposes a new algorithm that (try to) satisfy the proposed criteria.

Concrete Proposals

  • Proposes new layout algorithm.
  • Tentative proposal to deprecate some of the old layout algorithms in favor of the new one.

I am happy to focus on the first proposal for now.

Demo

See the code at https://invent.kde.org/fanzhuyifan/expo-view.

The screenshots for the following demos are generated by Natural (no fill gap), Natural (fill gap), closest, and new algorithm, in that order.

Screenshot_20231215_211412 Screenshot_20231215_211426 Screenshot_20231215_211444 Screenshot_20231215_211456

Screenshot_20231215_205937 Screenshot_20231215_205952 Screenshot_20231215_210010 Screenshot_20231215_210120

Screenshot_20231215_210158 Screenshot_20231215_210205 Screenshot_20231215_210213 Screenshot_20231215_210223

The current algorithm

Abstractly, the ExpoLayout Algorithm takes as input the geometry of the available region, and the geometries of a list of windows. It positions and scales the windows such that they all fit in the available region without overlapping.

Currently, two different layout modes are supported, LayoutClosest and LayoutNatural, implemented by ExpoLayout::calculateWindowTransformationsClosest and ExpoLayout::calculateWindowTransformationsNatural, respectively.

In LayoutClosest the algorithm creates a rectangular grid of slots, and assign windows to those slots.

In LayoutNatural, the algorithm incrementally adjusts the windows, scaling or moving them, based on nearby available space and overlaps.

Since neither explicitly considers the window sizes, this often leads to suboptimal layouts.

Some concrete examples of problems

For example, see Screenshot_20231215_084700.png and Screenshot_20231215_084719. These two are all taken under the LayoutNatural mode.

The issues are

  • The xclock windows have drastically different sizes even though they originally have the same size
  • The screen space use is inefficient -- there are large gaps in the image on the right.

What makes a good layout algorithm?

A good layout algorithm should make efficient and aesthetic use of screen space, make incremental and aesthetic adjustments upon creation or deletion of window, and always be fast and robust.

Make efficient and aesthetic use of screen space

  • windows should try to use as much use of screen space as possible
  • windows should be aligned, when possible
  • the size differences between windows shouldn't be too big

Make incremental and aesthetic adjustments upon creation or deletion of window

  • Upon incremental changes to the windows (single addition or deletion), (most of the time) the layout shouldn't be completely different

Fast

  • The run time needs to be linear (up to logarithm factors) in the number of windows, and it should be at least as fast as the existing algorithm for the user

Robust

  • The algorithm must terminate and not crash for input containing all possible sizes, including negative, and extremely large

Algorithm proposal

The outline of the proposed algorithm is

  1. adjustSizesOfWindows
  2. findGoodPacking
  3. refinePacking

The details of those steps are described in the following sections. The most important part is the second step, findGoodPacking.

adjustSizesOfWindows

In this step, we

  • set minimum size of windows
  • set maximum size of windows (no bigger than screen)
  • optionally adjust sizes of windows such that they don't differ by too much
  • add margins

findGoodPacking

Changed to the O(n log n) algorithm in [2]. In this step, we use the Next-Fit Decreasing Height (NFDH) strip packing algorithm (O(n log n)) to pack a strip [1, 2].

We use binary search on the logarithm of the strip width to find the strip width such that the aspect ratio of the final packing is closest to the aspect ratio of the available region, within some tolerance.

Input:
    windows: sizes of windows
    area: size of available area
    tol: tolerance

sortedWindows = sort windows by decreasing (height, width, unique id)

targetRatio = area.height / area.width

stripWidthMin = max(width of window for window in sortedWindows)
stripWidthMax = sum(width of window for window in sortedWindows)

height, placementHigh = NFDH(stripWidthMin, sortedWindows)
ratioHigh = height / stripWidthMin

if ratioHigh <= targetRatio:
    return stripWidthMin, placementHigh

height, placementLow = NFDH(stripWidthMax, sortedWindows)
ratioLow = height / stripWidthMax

if ratioLow >= targetRatio:
    return stripWidthMax, placementLow

bestPlacement = ratioHigh - targetRatio < targetRatio - ratioLow ? placementHigh : placementLow

while (stripWidthMax / stripWidthMin > 1 + tol):
    stripWidth = sqrt(stripWidthMin * stripWidthMax)
    height, placement = NFDH(stripWidth, sortedWindows)
    ratio = height / stripWidth

    if ratio > targetRatio:
        ratioHigh = ratio
        placementHigh = placement
        stripWidthMin = stripWidth
    else:
        ratioLow = ratio
        placementLow = placement
        stripWidthMax = stripWidth

if (ratioHigh - targetRatio < targetRatio - ratioLow):
    return stripWidthMin, placementHigh
else:
    return stripWidthMax, placementLow

Since the algorithm performs binary search on the logarithm of the strip width, it needs very few iterations to converge.

refinePacking

In this step, we

  • scale the packing to fit the available area
  • add even horizontal spacing between windows of the same level
  • add even vertical spacing between the levels
  • center-align the windows of the same level

References

Edited by Yifan Zhu