Abstracts for Mike Gleicher's publications

Electronic versions of many papers are available from another page. Higher level descriptions of the projects can be found off of my home page.

 
Michael Gleicher and James Masanz. Towards Virtual Videography. ACM Multimedia 2000. November, 2000, Los Angeles, CA. (Acrobat)
Videographers have developed an art of conveying events in video. Through choices made in cinematography, editing, and post-processing, effective video presentations can be created from events recorded with little or no intrusion. In this paper, we explore systems that bring videography to situations where cost or time issues preclude application of the art. Our goal is to develop {\em virtual videography,} that is, systems that can help automate the process of creating an effective video presentation from given footage. In this paper, we discuss how virtual videography systems can be constructed by combining image-based rendering to synthetically generate shots with image understanding to help choose what should be shown to the viewer. To this, visual effects can be added to enhance the presentation, lessening the degradation caused by the medium.

Michael Gleicher. Comparative Analysis of Constraint-Based Motion Editing Mathods. 2000 Workshop on Human Modeling and Animation, Seoul Korea. June 2000. (Acrobat)
Tools for assisting with editing human motion have become one of the most active research areas in the field of computer animation. Not surprisingly, the area has demonstrated some stunning successes in both research and practice. This paper explores the range of constraint-based techniques used to alter motions while preserving specific spatial features. We examine a variety of methods, defining a taxonomy of these methods that is categorized by the mechanism employed to enforce temporal constraints. We pay particular attention to a less explored category of approaches that we term per-frame inverse kinematics plus filtering, and show how these methods may provide an easier to implement system that has many of the benefits of other approaches.
Michael Gleicher. Retargetting Motion to New Characters. Proceedings of SIGGRAPH 98. In Computer Graphics Annual Conference Series, 1998.
In this paper, we present a technique for retargetting motion: the problem of adapting an animated motion from one character to another. Our focus is on adapting the motion of one articulated figure to another figure with identical structure but different segment lengths, although we use this as a step when considering less similar characters. Our method creates adaptations that preserve desirable qualities of the original motion. We identify specific features of the motion as constraints that must be maintained. A spacetime constraints solver computes an adapted motion that re-establishes these constraints while preserving the frequency characteristics of the original signal. We demonstrate our approach on motion capture data.

Michael Gleicher. Projective Registration with Difference Decomposition. Proceedings of CVPR '97 (IEEE Conference on Computer Vision and Pattern Recognition).
Current methods for registering image regions perform well when the transformations are simple or the image regions are large. In this paper, we present a new method that is better able to handle small image regions as they deform with non-linear transformations. We introduce \emph{difference decompositon,} a novel approach to solving the registration problem. The method is a generalization of previous methods and can better handle non-linear transforms. Although the methods are general, we focus on projective transformations and introduce \emph{piecewise-projective} transformations for modeling the motions of non-planar objects. We conclude with examples from our prototype implementation.

Michael Gleicher. Motion Editing with Spacetime Constraints. Proceedings of the 1997 Symposium on Interactive 3D Graphics.
In this paper, we present a method for editing a pre-existing motion such that it meets new needs yet preserves as much of the original quality as possible. Our approach enables the user to interactively position characters using direct manipulation. A spacetime constraints solver finds these positions while considering the entire motion. This paper discusses the three central challenges of creating such an approach: defining a constraint formulation that is rich enough to be effective, yet simple enough to afford fast solution; providing a solver that is fast enough to solve the constraint problems at interactive rates; and creating an interface that allows users to specify and visualize changes to entire motions. We present examples with a prototype system that permits interactive motion editing for articulated 3D characters on personal computers.

Michael Gleicher and Peter Litwinowicz. Constraint-Based Motion Adaptation. The Journal of Visualization and Computer Animation, 9:1 (1998) 65-94. Earlier version appears as Apple Computer Technical Report TR 96-153.
Today's computer animators have access to many systems and techniques to author high quality motion. Unfortunately, available techniques typically produce a particular motion for a specific character. In this paper, we present a constraint-based approach to adapt previously created motions to new situations and characters. We combine constraint methods that compute changes to motion to meet specified needs, with motion-signal processing methods that modify signals yet preserve desired properties. This allows the adaptation of motions to meet new goals while retaining much of their original quality.

Michael Gleicher. Image Snapping. Proceedings of SIGGRAPH 95. In Computer Graphics Annual Conference Series, 1995.
Cursor snapping is a standard method for providing precise pointing in direct manipu- lation graphical interfaces. In this paper, we introduce image snapping, a variant of cursor snapping that works in image-based programs such as paint systems. Image snapping moves the cursor location to nearby features in the image, such as edges. It is implemented by using gradient descent on blurred versions of feature maps made from the images. Interaction techniques using cursor snapping for image segmentation and curve tracing are presented

Michael Gleicher. A Differential Approach to Graphical Interaction. Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, 1994.
Direct manipulation has become the preferred interface for controlling graphical objects. Despite its success, the ad hoc manner with which such interfaces have been designed and implemented restricts the types of interactive controls. This dissertation presents a new approach that provides a systematic method for implementing flexible, combinable interactive controls. This differential approach to graphical interaction uses constrained optimization to couple user controls to graphical objects in a manner that permits a variety of controls to be freely combined. The differential approach provides a new set of abstractions that enable new types of interaction techniques and new ways of modularizing applications.

The differential approach views graphical object manipulation as an equation solving problem: Given the desired values for the user specified controls, find a configuration of the graphical objects that meet these constraints. To solve these equations in a suf- ficiently general manner, the differential approach controls the motion of the objects over time. At any instant in time, controls specify desired rates of change that form linear constraints on the time derivatives of the parameters. An optimization objective selects a particular value when these constraints do not determine a unique solution. The differential approach solves these constrained optimization problems to compute the derivatives of the parameters. An ordinary differential equation solver uses these rates to compute object motions.

This thesis addresses the issues in using numerical techniques to provide interactive control of graphical objects. Techniques are presented to solve the constrained optimi- zation problems efficiently and to dynamically define equations in response to system events. The thesis introduces an architecture, called \stm, that encapsulates these numerical needs. A graphics toolkit, constructed with \stm, provides the features of the differential approach yet hides the underlying machinery from the applications programmer.

The thesis demonstrates the differential approach by applying it to a variety of inter- action problems, including manipulation of 2D and 3D objects, lighting, and camera control. Demonstrated interaction techniques include novel methods for some specific interaction tasks. A number of prototype applications, including 3D object construc- tion and mechanisms sketching, demonstrate the tools and the approach.

Michael Gleicher and Andrew Witkin. Drawing With Constraints. The Visual Computer, 11 (1):39-51, 1994.
The success of constraint-based approaches to drawing has been limited by difficulty in creating constraints, solving them, and presenting them to users. In this paper, we discuss techniques used in the Briar drawing program to address all of these issues. Briar廣 approach separates the problem of initially establishing constraints from that of maintaining them during subsequent editing. We describe how non-constraint- based drawing tools can be augmented to specify constraints in addition to positions. These constraints are then maintained as the user drags the model, allowing the user to explore configurations consistent with the constraints. Visual methods are provided for displaying and editing the constraints.

Michael Gleicher. Practical Issues in Graphical Constraints. In V. Saraswat and P. Van Hentenryck, eds. Principles and Practice of Constraint Programming. MIT Press, 1994.
Use of constraint-based techniques in interactive graphics applications poses a variety of unique challenges to system implementors. This paper begins by describing how interface concerns create demands on interactive, constraint-based, graphical applications. We will discuss why such applications must be able to handle systems of non-linear constraints, and survey some of the techniques available to solve them. Employing these numerical algorithms in the contexts of interactive systems provides a set of challenges, including dynamically setting up the equations to be solved and achieving adequate performance and scalability. This paper will explore these issues and describe the methods we have used in our efforts to address them.

Michael Gleicher. A Graphics Toolkit Based on Differential Constraints. Proceedings UIST '93, November, 1993.
This paper describes Bramble, a toolkit for constructing graphical editing applications. The primary focus of Bramble is improve support for graphical manipulation by employing differential constraint techniques. A constraint engine capable of managing non-linear equations maps interactive controls and constraints to object parameters. This allows objects to provide mathematical outputs that are easily composed, rather than exposing their internal structure or requiring special purpose interaction techniques. The model of interaction used with the differential approach has a continuous notion of time, which provides the continuous motion required for graphical manipulation. Bramble provides a LISP-like extension language and support for other application features such as windows and buttons. The paper concludes with examples of interaction techniques defined in Bramble and applications built with Bramble.

Michael Gleicher and Andrew Witkin. Supporting Numerical Computations in Interactive Contexts. Proceedings Graphics Interface '93, pages 138-145, May 1993.
As computational performance becomes more readily available, there will be an increasing variety of interactive graphical applications with iterative numerical tech- niques at their core. In this paper, we consider how to support the unique demands of such applications. In particular, we focus on how to set up the numerical problems which must be solved. In the context of interactive systems, this requires the ability to dynamically compose systems of equations and rapidly evaluate them and their derivatives. We present an approach called Snap-Together Mathematics for doing this.

Michael Gleicher and Andrew Witkin. Through-the-Lens Camera Control. Computer Graphics, 26:2, pages 331-340, July 1992. Proceedings of SIGGRAPH '92.
In this paper we introduce Through-the-Lens Camera Control, a body of techniques that permit a user to manipulate a virtual camera by controlling and constraining fea- tures in the image seen through its lens. Rather than solving for camera parameters directly, constrained optimization is used to compute their time derivatives based on desired changes in user-defined controls. This effectively permits new controls to be defined independent of the underlying parameterization. The controls can also serve as constraints, maintaining their values as others are changed. We describe the tech- niques in general and work through a detailed example of a specific camera model. Our implementation demonstrates a gallery of useful controls and constraints and pro- vides some examples of how these may be used in composing images and animations.

Michael Gleicher and Michael Kass. An Interval Refinement Technique for Surface Intersection. Proceedings Graphics Interface '92, pages 242-249, May 1992.
This paper describes a technique for computing the intersections of two parametric surfaces based on interval arithmetic. The algorithm, which can be stopped and restarted at any point, uses search techniques to refine its description of the intersec- tions progressively. Interval arithmetic provides guaranteed points on the intersection curves to within a user-specified tolerance. These points are connected into polygons and used to triangulate the trimmed surfaces. We provide details of an implementation and give examples of the algorithm廣 use.

Michael Gleicher. Briar: A Constraint-Based Drawing Program. SIGGRAPH Video Review, 77, May 1992. CHI '92 formal video program.

Extended abstract appears in CHI 92 Proceedings, pages 661-661. An excerpt:

The accompanying video demonstrates Briar. Segments describe the basic features, beginning with snapping and continuing on to show how augmented snapping speci- fies constraints and how alignment objects are used to specify other relationships. The equilateral triangle example, taken from, shows how quickly constrained models can be created with snap-dragging. Other segments demonstrate how con- straints are used to aid in manipulation and are deleted. The example of a V-Engine shows how easily a constrained model can be assembled. The subsequent example shows some of Briar廣 special features for drawing and animating planar mecha- nisms. The segment on grouping shows how Briar is able to mix standard drawing program features with constraints.

Michael Gleicher. Integrating Constraints and Direct Manipulation. Proceedings of the 1992 Symposium on Interactive 3D graphics, pages 171-174, March, 1992.
In this paper, we present techniques for integrating constraint and direct manipulation approaches to geometric modeling. Direct manipulation positioning techniques are augmented to provide the option of making the relationships they establish persistent. Differential constraint techniques are used to maintain these relationships during sub- sequent editing. Issues in displaying and editing constraints are also addressed. By integrating constraints with direct manipulation, it is possible to build systems that provide the power of explicit representation of geometric relationships and the prop- erties which make direct manipulation so attractive.

William Welch, Michael Gleicher, and Andrew Witkin. Manipulating Surfaces Differentially. Proceedings Compugraphics '91, September, 1991.
We want to create interactive surface design systems which provide intuitive inter- faces to parametric surface representations. In this paper, we show how the technique of Differential Manipulation can be used in constructing such interfaces. It allows sur- face manipulation issues to be treated separately from surface representation issues. Arbitrary differentiable functions of representation parameters can be used to control the surface. Constraint and optimization techniques can be used to enhance interac- tion and control many surface degrees of freedom at once. We provide examples of the technique廣 use in our interactive surface modeling program.

Michael Gleicher and Andrew Witkin. Differential Manipulation. Proceedings Graphics Interface '91, pages 61-67, June, 1991.
Direct manipulation has proven to be an excellent method for interacting with geometric objects. Unfortunately, traditional approaches for implementing direct manipulation suffer from a lack of generality, requiring the system designer to hand craft interfaces to different types of objects. In this paper we present Differential Manipula- tion, a new paradigm for direct manipulation of geometric objects. By interpreting graphical entities as physical objects, we obtain a uniform interface to a wide variety of geometric objects, making it simple to add new types of complicated or compound objects. Geometric constraints fit neatly into the paradigm.

Michael Gleicher and Andrew Witkin. Snap Together Mathematics. In Edwin Blake and Peter Weisskirchen, editors, Advances in Object Oriented Graphics 1: Proceedings of the 1990 Eurographics Workshop on Object Oriented Graphics. Springer-Verlag, 1991.

NOTE: This paper superceded the GI '93 paper.

Large numbers of applications involve building complicated mathematical models out of predefined functions and repeatedly evaluating the combined function and its derivatives. For interactive applications it is important that the evaluations be efficient and that the model can be altered dynamically. Snap Together Mathematics is a facility that provides this functionality. Primitive functions are defined at compile time and can be composed dynamically to create larger models. Evaluation of both the composed function and its derivatives is accomplished by traversal of the expression graph. The sparse derivative matrix of a subset of a model廣 outputs with respect to any set of its inputs can be computed efficiently. Snap together mathematics is implemented as a set of class definitions that provide a base for application specific objects. Among the applications we have developed are interactive systems for geometric modeling, constrained optimization, and constrained dynamics.

Andrew Witkin, Michael Gleicher and William Welch. Interactive Dynamics. Computer Graphics, 24(2):11-21, March 1990. Proceedings 1992 Symposium on Interactive 3D Graphics.
Our goal is to use physical simulation as an interactive medium for building and manipulating a wide range of models. A key to achieving this goal is the ability to create complex physical models dynamically by simply snapping pieces together, integrating the process of model creation into the ongoing simulation. We present a mathematical and computational formalism that makes this possible, allowing encapsulated objects, constraints, and forces to be combined dynamically and simulated efficiently. The formulation handles arbitrary objects, including non-rigid bodies. We describe an implementation for interactive dynamics, and discuss applications to mechanism construction, interactive optimization, data fitting and animation.

Last modified: 16:47 Mar 2, 2001