The 2-Immerse Layout Engine Packing Algorithm
In a technical post, AVIVA VAKNIN from 2-IMMERSE partner Cisco outlines the operation of the algorithm behind the project’s layout engine.
The motivation for the 2-IMMERSE layout service is to provide a cloud based, highly available layout engine that could provide a layout for a dynamically varying set of digital application components over a set of varying viewing devices. The service manages the set of devices and running components and provides the layout engine with a full layout specification for each layout computation. It then returns a list of components per device, with region, position and size.
The layout engine computes a rectangular layout of rectangles onto a set of rectangles. The primary use case is to compute layout arrangements for digital components over a set of viewing devices, e.g. several video playbacks and a control panel that will run over a video wall comprised of many monitors. The service is comprised of a REST interface and a layout engine. The layout engine is unique in that (1) it computes a layout over a set of rectangular display regions and (2) the rectangles, or digital components, may be heavily constrained.
The input to the packer algorithm includes a list of rectangular regions (logical rectangular display areas, mapped onto underlying physical devices), their associated device information, and a list of rectangular components and associated constraints to be packed.
The output is a list of components per device, with region, position and size for each placed component where all coordinates are relative to the top left corner which is at (0,0).
The algorithm is multi-pass; since the primary application is for digital media applications, the number of components and displays is small, thus efficiency is not a prime consideration, but rather the generating of optimal and aesthetic layouts.
Pass One begins by sorting the regions in decreasing size order and sorting the components in decreasing priority order using size as a secondary sort constraint. The component sizes are not fixed, thus the packing engine computes a first approximation to the number of components that will fit into the given region set, and then sorts the highest priority components that will fit, in decreasing size order.
The destination regions are stored in a list of nodes, initialized with one node per region, all marked as unoccupied. When the packer places a component into a region, and the incoming component does not utilize an entire dimension (e.g. due to aspect ratio or maximum size constraints) the node will be split into two or three regions rather than two, as seen in Fig. 1.
If the packer does not find an unoccupied appropriate node for the component, it attempts to split and occupied node and populate the second half with the new component. The packer uses the preferred size, minimum size, anchor, and aspect ratio constraints to determine how to fit the components.
Pass Two attempts to fit in any unplaced components in the first pass due to lack of space: if not all components were laid out, the packer will successively reduce the size of all the components using a decreasing reduction factor. The packer then chooses the layout that fits the highest number of components, and if they are all equal it chooses that with the least white space.
Pass Three re-arranges the layout so that is more aesthetic, i.e., avoids holes in the centre of the displays, minimises white space, and collates white space to the right and bottom of the rectangle. The packer sorts the resultant nodes in position order, starting at the top left and moving right, then down, and packs the components again using the internal packer loop, choosing the layout that maximises real estate coverage as well as the number of placed components.
The result is that the packing algorithm always adheres to the defined constraints, provides a good distribution of the components over the regions, and generates aesthetic layouts, particularly when constraints do not include maximum sizes.
Sample video layouts
Video component constraints: aspect ratio = 16:9 and minimum width = 50%
