constraint

In this paper we present a method for helping artists make artwork more accessible to casual users. We focus on the specific case of drawings, showing how a small number of drawings can be transformed into a richer object containing an entire family of similar drawings. This object is represented as a simplicial complex approximating a set of valid interpolations in configuration space. The artist does not interact directly with the simplicial complex. Instead, she guides its construction by answering a specially chosen set of yes/no questions. By combining the flexibility of a simplicial complex with direct human guidance, we are able to represent very general constraints on membership in a family. The constructed simplicial complex supports a variety of algorithms useful to an end user, including random sampling of the space of drawings, constrained interpolation between drawings, projection of another drawing into the family, and interactive exploration of the family.

Graphical user interfaces (GUI) provide intuitive and easy means for users to communicate with computers. However, construction of GUI software requires complex programming that is far from being intuitive. Because of the “semantic gap” between the textual application program and its graphical interface, the programmer himself must conceptually maintain the correspondence between the textual programming and the graphical image of the resulting interface. Instead, we propose a programming environment based on the programming by visual example (PBVE) scheme, which allows the GUI designers to “program” visual interfaces for their applications by “drawing” the example visualization of application data with a direct manipulation interface. Our system, TRIP3, realizes this with (1) the bi-directional translation model between the (abstract) application data and the pictorial data of the GUI, and (2) the ability to generate mapping rules for the translation from example application data and its corresponding example visualization. The latter is made possible by the use of generalization of visual examples, where the system is able to automatically generate generalized mapping rules from a given set of examples.

This paper presents the architecture for an extensible toolkit used in construction and rapid prototyping of three dimensional interfaces, interactive illustrations, and three dimensional widgets. The toolkit provides methods for the direct manipulation of 3D primitives which can be linked together through a visual programming language to create complex constrained behavior. Features of the toolkit include the ability to visually build, encapsulate, and parameterize complex models, and impose limits on the models. The toolkit's constraint resolution technique is based on a dynamic object model similar to those in prototype delegation object systems. The toolkit has been used to rapidly prototype tools for mechanical modelling, scientific visualization, construct 3D widgets, and build mathematical illustrations.

Many user interface toolkits use constraint solvers to maintain geometric relationships between graphic objects, or to connect the graphics to the application data structures. One efficient and flexible technique for maintaining constraints is multi-way local propagation, where constraints are represented by sets of method procedures. To satisfy a set of constraints, a local propagation solver executes one method from each constraint.

SkyBlue is an incremental constraint solver that uses local propagation to maintain a set of constraints as individual constraints are added and removed. If all of the constraints cannot be satisfied, SkyBlue leaves weaker constraints unsatisfied in order to satisfy stronger constraints (maintaining a constraint hierarchy). SkyBlue is a more general successor to the DeltaBlue algorithm that satisfies cycles of methods by calling external cycle solvers and supports multi-output methods. These features make SkyBlue more useful for constructing user interfaces, since cycles of constraints can occur frequently in user interface applications and multi-output methods are necessary to represent some useful constraints. This paper discusses some of applications that use SkyBlue, presents times for some user interface benchmarks and describes the SkyBlue algorithm in detail.

Cascading Style Sheets have been introduced by the W3C as a mechanism for controlling the appearance of HTML documents. In this paper, we demonstrate how constraints provide a powerful unifying formalism for declaratively understanding and specifying style sheets for web documents. With constraints we can naturally and declaratively specify complex behavior such as inheritance of properties and cascading of conflicting style rules. We give a detailed description of a constraint-based style sheet model, CCSS, which is compatible with virtually all of the CSS 2.0 specification. It allows more flexible specification of layout, and also allows the designer to provide multiple layouts that better meet the desires of the user and environmental restrictions. We also describe a prototype extension of the Amaya browser that demonstrates the feasibility of CCSS.

When involved in the visual design of graphical user interfaces, graphic designers can do more than providing static graphics for programmers to incorporate into applications. We describe a technique that allows them to provide examples of graphical objects at various key sizes using their usual drawing tool, then let the system interpolate their resizing behavior. We relate this technique to current practices of graphic designers, provide examples of its use and describe the underlying inference algorithm. We show how the mathematical properties of the algorithm allows the system to be predictable and explain how it can be combined with more traditional layout mechanisms.

With advances in pen-based computing devices, handwriting has become an increasingly popular input modality. Researchers have put considerable effort into building intelligent recognition systems that can translate handwriting to text with increasing accuracy. However, handwritten input is inherently ambiguous, and these systems will always make errors. Unfortunately, work on error recovery mechanisms has mainly focused on interface innovations that allow users to manually transform the erroneous recognition result into the intended one. In our work, we propose a mixed-initiative approach to error correction. We describe CueTIP, a novel correction interface that takes advantage of the recognizer to continually evolve its results using the additional information from user corrections. This significantly reduces the number of actions required to reach the intended result. We present a user study showing that CueTIP is more efficient and better preferred for correcting handwriting recognition errors. Grounded in the discussion of CueTIP, we also present design principles that may be applied to mixed-initiative correction interfaces in other domains.

The construction of application-specific Graphical User Interfaces (GUI) still needs considerable programming partly because the mapping between application data and its visual representation is complicated. This study proposes a system which generates GUIs by generalizing multiple sets of application data and its visualization examples. The most notable characteristic of the system is that programmers can interactively modify the mapping by “correcting” the system-generated visualization examples that represent the system's current notion of programmer's intentions. Conflicting mappings are automatically resolved via the use of constraint hierarchies.

Many user interface toolkits use constraint solvers to maintain geometric relationships between graphic objects, or to connect the graphics to the application data structures. One efficient and flexible technique for maintaining constraints is multi-way local propagation, where constraints are represented by sets of method procedures. To satisfy a set of constraints, a local propagation solver executes one method from each constraint.

SkyBlue is an incremental constraint solver that uses local propagation to maintain a set of constraints as individual constraints are added and removed. If all of the constraints cannot be satisfied, SkyBlue leaves weaker constraints unsatisfied in order to satisfy stronger constraints (maintaining a constraint hierarchy). SkyBlue is a more general successor to the DeltaBlue algorithm that satisfies cycles of methods by calling external cycle solvers and supports multi-output methods. These features make SkyBlue more useful for constructing user interfaces, since cycles of constraints can occur frequently in user interface applications and multi-output methods are necessary to represent some useful constraints. This paper discusses some of applications that use SkyBlue, presents times for some user interface benchmarks and describes the SkyBlue algorithm in detail.

This paper describes a domain-specific debugger for one-way constraint solvers. The debugger makes use of several new techniques. First, the debugger displays only a portion of the dataflow graph, called a constraint slice, that is directly related to an incorrect variable. This technique helps the debugger scale to a system containing thousands of constraints. Second, the debugger presents a visual representation of the solver's data structures and uses color encodings to highlight changes to the data structures. Finally, the debugger allows the user to point to a variable that has an unexpected value and ask the debugger to suggest reasons for the unexpected value. The debugger makes use of information gathered during the constraint satisfaction process to generate plausible suggestions. Informal testing has shown that the explanatory capability and the color coding of the constraint solver's data structures are particularly useful in locating bugs in constraint code.

Constraints have been playing an important role in the user interface field since its infancy. A prime use of constraints in this field is to automatically maintain geometric layouts of graphical objects. To facilitate the construction of constraint-based user interface applications, researchers have proposed various constraint satisfaction methods and constraint solvers. Most previous research has focused on either local propagation or linear constraints, excluding more general nonlinear ones. However, nonlinear geometric constraints are practically useful to various user interfaces, e.g., drawing editors and information visualization systems. In this paper, we propose a novel constraint solver called Chorus, which realizes various powerful nonlinear geometric constraints such as Euclidean geometric, non-overlapping, and graph layout constraints. A key feature of Chorus is its module mechanism that allows users to define new kinds of geometric constraints. Also, Chorus supports "soft" constraints with hierarchical strengths or preferences (i.e., constraint hierarchies). We describe its framework, algorithm, implementation, and experimental results.

Constraints have been playing an important role in the user interface field since its infancy. A prime use of constraints in this field is to automatically maintain geometric layouts of graphical objects. To facilitate the construction of constraint-based user interface applications, researchers have proposed various constraint satisfaction methods and constraint solvers. Most previous research has focused on either local propagation or linear constraints, excluding more general nonlinear ones. However, nonlinear geometric constraints are practically useful to various user interfaces, e.g., drawing editors and information visualization systems. In this paper, we propose a novel constraint solver called Chorus, which realizes various powerful nonlinear geometric constraints such as Euclidean geometric, non-overlapping, and graph layout constraints. A key feature of Chorus is its module mechanism that allows users to define new kinds of geometric constraints. Also, Chorus supports "soft" constraints with hierarchical strengths or preferences (i.e., constraint hierarchies). We describe its framework, algorithm, implementation, and experimental results.

Current constraint solving techniques for interactive graphical applications cannot satisfactorily handle constraints such as non-overlap, or containment within non-convex shapes or shapes with smooth edges. We present a generic new technique for efficiently handling such kinds of constraints based on trust regions and linear arithmetic constraint solving. Our approach is to model these more complex constraints by a dynamically changing conjunction of linear constraints. At each stage, these give a local approximation to the complex constraints. During direct manipulation, linear constraints in the current local approximation can become active indicating that the current solution is on the boundary of the trust region for the approximation. The associated complex constraint is notified and it may choose to modify the current linear approximation. Empirical evaluation demonstrates that it is possible to (re-)solve systems of linear constraints that are dynamically approximating complex constraints such as non-overlap sufficiently quickly to support direct manipulation in interactive graphical applications.

This paper describes a domain-specific debugger for one-way constraint solvers. The debugger makes use of several new techniques. First, the debugger displays only a portion of the dataflow graph, called a constraint slice, that is directly related to an incorrect variable. This technique helps the debugger scale to a system containing thousands of constraints. Second, the debugger presents a visual representation of the solver's data structures and uses color encodings to highlight changes to the data structures. Finally, the debugger allows the user to point to a variable that has an unexpected value and ask the debugger to suggest reasons for the unexpected value. The debugger makes use of information gathered during the constraint satisfaction process to generate plausible suggestions. Informal testing has shown that the explanatory capability and the color coding of the constraint solver's data structures are particularly useful in locating bugs in constraint code.

Constraints have been playing an important role in the user interface field since its infancy. A prime use of constraints in this field is to automatically maintain geometric layouts of graphical objects. To facilitate the construction of constraint-based user interface applications, researchers have proposed various constraint satisfaction methods and constraint solvers. Most previous research has focused on either local propagation or linear constraints, excluding more general nonlinear ones. However, nonlinear geometric constraints are practically useful to various user interfaces, e.g., drawing editors and information visualization systems. In this paper, we propose a novel constraint solver called Chorus, which realizes various powerful nonlinear geometric constraints such as Euclidean geometric, non-overlapping, and graph layout constraints. A key feature of Chorus is its module mechanism that allows users to define new kinds of geometric constraints. Also, Chorus supports "soft" constraints with hierarchical strengths or preferences (i.e., constraint hierarchies). We describe its framework, algorithm, implementation, and experimental results.