Using Constraints for Flexible Document Layout

Alan Borning
University of Washington
http://www.cs.washington.edu/homes/borning

Richard Lin
Monash University
http://www.cs.monash.edu.au/~rlin

Kim Marriott
Monash University
http://www.cs.monash.edu.au/~marriott

Peter Stuckey
University of Melbourne
http://www.cs.mu.oz.au/~pjs

Introduction

A major limitation of current internet publishing technology is insufficient layout control. We want flexible and powerful ways to specify layout, but these layout specifications must accommodate a wide variety of media and viewers. A rigid static layout, such as that used in classical publishing, is inadequate in the context of electronic viewing. In contrast to print publishing, the capabilities of the media used for viewing are not known in advance. Different browser types, monitor sizes and ratios, colour or black-and-white monitors render it virtually impossible to design pages that look good on all device types. The situation becomes more complicated when interactive resizing of windows and frames, printing, or communication conditions such as varying bandwidths are taken into consideration. Not only is it necessary to take into account the viewing media capabilities, the viewer's needs and capabilities also need to be considered. For example, font sizes and colours need to be alterable to fit the requirements of sight-impaired viewers. On top of this, the layout of documents that are created dynamically, such as those that display database or search engine query results, can only be predetermined to a small degree. In the ideal case their layout should be generated automatically based on an abstract style specification.

Constraint based-specification provides a general approach to this problem. Constraints have been used for many years in interactive graphical applications for such things as specifying window and page layout, specifying relationships among parts of a drawing, specifying animations, maintaining consistency between application data and a view of that data, maintaining consistency between multiple views, and representing physical laws in simulations. They allow the designer to specify what are the desired properties of the system, rather than how these properties are to be maintained. Constraints also make it easy to specify partial information about an attribute, instead of a specific value, thus making it easier to combine specifications from multiple sources.

It is thus natural to consider constraint-based tools to aid in authoring web documents. We have built a prototype system (described more fully in [Borning 97a]) that allows web authors to employ constraints to specify page layout, including figure placement and column widths and spacing. Some of these constraints will be requirements that must be satisfied, while others may be preferences of different strengths that can be relaxed if need be. In addition, authors can use several constraint style sheets to specify alternate sets of constraints to be used under different circumstances, for example, for a one versus a two-column layout. The conditions under which a style sheet is applicable are, of course, also specified as constraints.

Constraints may be imposed by the viewer of the document as well as by the author. These constraints may arise from the capabilities of the system which renders the document or the preferences or constraints of the human viewer. Like those of the author, some of the viewer's constraints can be preferences as well as requirements. The final appearance of the document is thus in effect the result of a negotiation between the author and the viewer -- where this negotiation is carried out by solving the set of required and preferential constraints imposed by both parties.

The internet's underlying client/server model implies two possible system architectures. In one model, both the web authoring tool and the web browser can perform runtime constraint solving. The web author uses the solver while constructing and testing the pages and applets, while the viewer uses a different solver on the viewing machine to determine the final page layout by solving the combined constraints from the author and viewer. In this case a compact representation of the constraints, along with the content of the page, additional layout information and applets, is shipped over the network for each page. In addition, the runtime solver must be shipped once and saved on the viewer's machine. In the alternative model, the web author again uses a powerful runtime constraint solver, but a more restricted set of constraints is available to the viewer. Using projection [Harvey 97], the authoring tool compiles a Java program representing a plan for satisfying the author's constraints and the predetermined kinds of constraints that the viewer may impose. This program is then shipped to the viewer's machine---a runtime constraint solver is not needed on the client side. A combination of the two approaches is also possible -- and in fact our prototype uses such a combination.

Constraint-Based Page Layout

Our approach is to use constraints to specify the core aspects of the design layout. The constraints capture the ``semantics'' of the design, those aspects that must hold true for the layout to be appealing. In our prototype, the designer can specify placement of the document elements using linear arithmetic equalities and inequalities. Such constraints allow easy specification of table, column, and image placement in a way that scales gracefully.

The following example, taken from [Borning 97a], explains the underlying idea. Consider the page layout shown in Figure 1a. We require that the text is arranged in two columns, that figures A and B are centered in the first and second columns respectively, and that the tops of the two figures are aligned horizontally. These layout constraints are captured by the following equalities and inequalities:


Figure 1a: Two Column output

Constraint (1) states that the page width, PW, is the sum of the widths of the left, middle and right gutters LG, MG, and RG, and the two columns, CW1 and CW2 . Constraint (2) states that the two columns have equal width; (3) states that the left and right gutters are equal and are 1/20 of the width of the columns; (4) states that the middle gutter is of fixed size (0.7 cm); (5) states that the x value of the midpoint of Figure A is at the center of the first column; (6) states that Figure B is centered in the second column; while the last equality (7) enforces that the two figures are horizontally aligned. The inequalities (8) and (9) enforce that the columns are wide enough for Figures A and B.

For a given value of the page width PW we can find a solution to the other variables that satisfies these constraints and that gives us a layout. For instance, if PW = 21.7 cm then LG = RG = MG = 0.5 cm and CW1 = CW2 = 10 cm. Conversely, if PW = 42.7 cm then LG = RG = 1.0 cm, MG = 0.7 cm and CW1 = CW2 = 20 cm. Note how the left and right margins scale with respect to the page size while the middle gutter has an absolute size.

This model is, however, a little too simple. In particular it does not allow the designer to state preferences for values. We therefore extend our model to allow the user to specify that an inequality or equality is preferred but not required, so that the constraint should be satisfied when possible but does not need to be. Constraint hierarchies [Borning 92] formalize such preferences. A constraint hierarchy consists of collections of constraints each labelled with a strength. There is a distinguished strength label required: such constraints must be satisfied. The other strength labels denote preferences. There can be an arbitrary number of such strengths, and constraints with stronger strength labels are satisfied in preference to ones with weaker strength labels. In our example, the equalities and inequalities given earlier are required constraints and we have used weak to label non-required constraints. Given a system of constraints and preferred values, the constraint solver must find a solution to the variables that satisfies the required constraints and which is as close as possible to the preferred values.

In the previous example, we have required that the columns be wide enough for Figures A and B. If they are not, then this is not an appropriate layout. For instance, if the width of Figure A and B is 10 cm, then we cannot solve the constraints when the page width is less than 21.3 cm. In this case the designer might wish to use a single column with the example layout is shown in Figure 1b.


Figure 1b: Single Column output

To accommodate such situations, our model allows the designer to provide multiple constraint style sheets. Each style sheet includes linear arithmetic constraints that define the layout of the design and that dictate when the design is appropriate. During manipulation by the viewer, the viewing tool will choose the appropriate style sheet and lay out the document subject to the constraints in the sheet. As the viewer changes the requirements, the document will be redisplayed using the current style sheet until the constraints are inconsistent with the viewer's desires. In this case the viewing tool will choose another style sheet for the document which is consistent with the viewer's constraints.

For instance, if the viewer of our example document originally displays the document in a window of width 28 cm, then resizes the window to 20 cm, the design will change from two column to one column. If the viewer now resizes it back to 28 cm, the design will change back to two column.

As a more complex example of constraint-based page layout, consider the web page shown in Figure 2a and Figure 2b. These figures show two constraint style sheets, the first for a narrow page with one column layout and the second for a wider page with two column layout. In each, layout constraints ensure that the central abacus figure is centered and that the surrounding labels remain appropriately aligned as the window is resized or other edits performed. Each style sheet contains approximately 110 constraints.


Figure 2a: Narrow page output


Figure 2b: Wide page output

Prototype System

Our prototype system consists of the document authoring tool, the viewing tool and the constraint solver. The constraint-based authoring tool is used by the designer to construct the constraint style sheets and document contents. Ideally the designer should not need to think in terms of arithmetic constraints or even be aware of the real nature of the constraints. At present pre-defined templates are used for this purpose, but further research is required. The viewing tool integrates constraints from the designer with those of the viewer, check which constraint style sheet is appropriate, resolve the constraints, and then display the document contents using the values from the solution to place elements in the layout.

The constraint solver is a key component of this architecture. It needs to support the following:

  1. Incremental constraint solving, including incremental addition, deletion, and resolving of constraints for changing user inputs.
  2. Hierarchies of constraints with required and preferential constraints.
  3. Efficient computation of a solution, since it should not cause additional delay in retrieving a document. In addition, direct manipulation requires fast incremental computation of new solutions for good interaction.
  4. Geometric and non-geometric constraints. Geometric constraints naturally arise in layout while non-geometric constraints arise when specifying non-geometric attributes of text and graphics such as font sizes, type and colour.

These are rather strong requirements. Indeed probably the main reason why constraints are not more widely used in computer graphics is that current constraint solvers do not come close to meeting these requirements. Fortunately, as part of the prototype implementation we have developed a Java solver that meets the first three requirements; we believe that with recent advances in constraint solving technology it will be possible to meet all of them. It provides fast incremental linear arithmetic constraint solving and solves the constraint hierarchy by translating it into a linear programming problem [Borning 97b].

Related Work

Cascading style sheets (CSS1 and CSS2) [Lie 96, Lie 98] partially address these issues by providing a number of new constructs for defining the layout of a page. For example, with CSS it is possible to specify font sizes, style attributes, colours, etc in a separate style sheet. Authors as well as viewers can define style sheets, and the final appearance of the document is determined by merging these style sheets into a single hierarchical style definition. The principal difference between CSS1 and constraint style sheets is that cascaded style sheets allow one to specify a particular value for a given attribute (or in some cases a percentage), while constraint style sheets allow more general constraints, i.e. partial specifications, to be given for these attributes. For example, a cascaded style sheet can include a rule specifying that the left margin of a layout element is a particular value. On the other hand, a constraint style sheet can include an arbitrary linear constraint on the left margin, which might constrain it to be less than twice some other value. (Constraining it to have a particular value is just a special case of the general constraint mechanism.) CSS2 moves further in the direction of general constraints, and includes such things as requirements that a floating box be placed as far as possible to the left in its enclosing box. Another difference is that we allow the appearance to change interactively as the viewer resizes the page. This means that the server must provide multiple style files, and the viewer must choose the style file that is compatible with the reader's requirements, and change this choice dynamically. In addition, we also support figure layout (although a similar extension to cascaded style sheets is expected [Lie 96] in future versions).

The <table> environment in HTML 3.0 can be viewed as providing certain constraints, including preferences as well as requirements, for example, desired cell width expressed either as an absolute quantity (in pixels) or as a percentage of the total table width; again, however, there is no general constraint capability.

Weitzman and Wittenburg [Weitzman 94] have investigated the use of relational grammars for document design. Their work is closely related to ours since in effect they use a grammar which details a class of constraint layout styles. However their interest is in specifying and recognizing layout styles rather than constraint solving. They only consider rather weak constraint solving techniques based on local propagation. Indeed, it seems rather natural to combine their work with ours.

Future Work

Our plans for future work include the following projects.

Bibliography

[Borning 92]
Alan Borning, Bjorn Freeman-Benson, and Molly Wilson. Constraint hierarchies. Lisp and Symbolic Computation, 5(3):223-270, September 1992.
[Borning 97a]
Alan Borning, Richard Lin and Kim Marriott. Constraints for the Web. In Fifth ACM International Multi-Media Conference, pp. 173--182. Seattle, November 1997. http://www.acm.org/sigmm/MM97/papers/borning/constraints.html
[Borning 97b]
Alan Borning, Kim Marriott, Peter Stuckey, and Yi Xiao. Solving linear arithmetic constraints for user interface applications. In Proceedings of the 1997 ACM Symposium on User Interface Software and Technology, October 1997.
[Harvey 97]
Warwick Harvey, Peter Stuckey, and Alan Borning. Compiling constraint solving using projection. In Proceedings of the 1997 Conference on Principles and Practice of Constraint Programming (CP97), October 1997.
[Lie 96]
Hakon Wium Lie and Bert Bos. Cascading style sheets, level 1. W3C Recommendation, December 1996. http://www.w3.org/pub/TR/REC-CSS1
[Lie 98]
Hakon Wium Lie and Bert Bos. Cascading style sheets, level 2. W3C Working Draft, 28 January 1998. http://www.w3.org/TR/WD-CSS2
[Weitzman 94]
L. Weitzman and K Wittenburg. Automatic generation of multimedia documents using relational grammars. In Proceedings of 2nd ACM Conference on Multimedia, 1994.