Cisco – 2-IMMERSE

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%

Things to come

JOHN WYVER writes: In just under a month, on 6 and 7 March, the Tommy Flowers Institute at BT’s Adastral Park is hosting ‘The Future of TV’, a two-day conference for post-graduate researchers and industry experts about quite what television is today and where it’s headed. Members of the 2-IMMERSE group have been centrally involved in the planning of the event, both James Walker from Cisco and I will be presenting at it, and BT’s Doug Williams and Ian Kegel will be chairing sessions. Other BT colleagues will be involved in break-out sessions and panels. A key objective for 2-IMMERSE is to highlight the opportunities which we believe object-based broadcasting can provide for the television industry. Attendance is free and you can sign up for it here.

(more…)

Introducing the 2-IMMERSE Layout Service

JAMES WALKER from Cisco contributes a technical post:

Within the 2-IMMERSE platform, we need to be able to orchestrate a set of ‘distributed media application’ components across the participating multiscreen devices, whether that is a connected TV and a tablet at home, or several large TVs and the phones of many individuals phones in a pub watching a football match. This multiscreen orchestration needs to be done in a way that supports the media application producers’ intent, makes best and most appropriate use of the devices available, and allows the user to personalise the presentation to suit their preferences. The implementation also needs to scale, potentially to broadcast audience size.

In the 2-IMMERSE Architecture, the Layout Service is responsible for this multiscreen orchestration role. As such:

The Layout Service understands what devices are participating in the experience, and what their presentation capabilities are (we call this group of devices a context)
On starting a distributed media application, the Layout Service loads a set of authored component presentation ‘rules’ used to determine the layout of the components as they are instantiated.
The Layout Service responds to requests to instantiate, update and terminate components, which come from the timeline service (which is responsible for the temporal orchestration of distributed media application components)
The Layout Service responds to client requests to personalise and modify component layout.

The Layout Service will re-evaluate layout as required, but typically not as a result of a direct client request. For example, the timeline service may introduce a new component and so the layout needs to be updated. This requires that we have a mechanism to push layout updates to clients, and for that the Layout Service uses the platform’s websocket service.

The layout model defines two different types of device; communal and personal. Where there is more than one communal device they are treated as a group with components laid out across them, but not duplicated. Personal devices are treated as being independent from a layout perspective.

Each device can optionally have a set of regions defined. These regions can represent a partitioning of the screen area of that device, but equally can represent a ‘virtual’ layout surface that the client device can manage presentation of. As examples, we have used regions as a way of having companion app ‘drawers’ that can slide to reveal components, or to support overlay component presentation on a TV.

Components are laid out as non-overlapping rectangles within device screens and regions, and it is the clients’ responsibility to populate the components into the layout provided by the service. You can think of the layout as a ‘wireframe’ which the clients populate. We have developed a simple layout renderer tool that visualises a layout, and you can see an example screen shot of this here:

In 2-IMMERSE we have adopted HTML clients and components so it is natural that the layout of the components in the browser is achieved using CSS. However, we have tried to avoid assuming CSS as the client layout mechanism so the that service could be used by non-HTML clients.

The component presentation ‘rules’ allow a distributed media application author to define how components should be presented with a vocabulary of constraints which include:

Component priority (highest takes precedence)
Minimum size (pixels, percent or inches)
Preferred size (pixels, percent or inches)
Fixed aspect ratio
Target regions
Anchor (top, bottom, left, right)
Margin
Component dependency (only layout A if B has been laid out)
Component device dependency (only layout A if B has been laid out on this device)
Device capability requirements (supports audio, touch interaction etc.)

For each component, a set of constraints is defined for both communal and personal devices so presentation can be tailored appropriately. Currently, constraints are defined on a per-component basis, but we are changing this model to allow constraint definitions to be more flexibly referenced and shared by components. We have also added an API to allow modification of constraints on-the-fly.

In the constraint vocabulary, we are striving to give authors the ability to determine how components should be placed in a flexible way, and ensure the components get placed on the appropriate device, even when it’s difficult to anticipate every combination of devices that might be available in a particular user’s environment.

Currently the ability for a user to override and personalise layout is limited to modifying component priorities (which gives the ability to show or hide components on different devices). We will extend these personalisation capabilities driven by use-cases in forthcoming trials.

A fairly high proportion of these layout features have now been implemented and more recently we have been looking at improving scalability and performance. One area that of future work that emerged during the initial Watching Theatre at Home trial has been taking bandwidth requirement of components into consideration as part of the layout model, and this is an area that the project will be tackling in the near future.