effects/overview: implement new layout algorithm

Replace old "closest" and "natural" layout algorithms with new layout algorithm. The new layout algorithm tries to

• use screen space efficiently, given diverse geometries of windows
• be aesthetically pleasing
• and minimize movement of windows from initial positions.

More concretely, find a layered layout, where each layer, or strip, is a row or column. Ensure that different strips have similar widths, and use binary search to find a packing with similar aspect ratio to the layout area. Within each strip, minimize horizontal movement (for rows) or vertical movement (for columns) of windows.

Run time is O(n) (up to log factors), where n is the number of windows.

CCBUG: 453749 BUG: 450263 BUG: 477833 BUG: 478097 BUG: 477830

Demo

Natural (old) Closest (old)

Smart (new)

Video Demo

Update: added some tweaks so that windows stay closer to their original positions while not making the packing worse. (The lags seem to be caused by my prime+external display setup, and is not related to this MR)

closer

placement in columns in portrait mode: portrait

Original:

Screencast_20240118_084837

Trying it out

Currently there are two ways to try out this new layout algorithm. You can either compile this MR and choose smart in settings->desktop effects->present windows & overview.

Or you could directly try it out by compiling https://invent.kde.org/fanzhuyifan/expo-view

Feedback

Pinging the @teams/vdg for

• general feedback

- [ ] tuning some parameters in layoutcon‎fig.kcfgc‎ Now they are Q_Properties defined in expolayout.h

• discussion on what we want to do with the old layout algorithms. Do we want to keep them or replace them?

Incompatible changes

The m_spacing attribute of ExpoLayout is no longer respected. The algorithm no longer tries to handle absolute spacing. Instead, it uses relative spacing (relative to the size of the windows), with preconfigured defaults.

Related RFC (with algorithm description): #189 (closed)