4435102
An interface for sketching 3D curves
The ability to specify nonplanar 3D curves is of fundamental importance in 3D modeling and animation systems. Effective techniques for specifying such curves using 2D input devices are desirable, but existing methods typically require the user to edit the curve from several viewpoints. We present a novel method for specifying 3D curves with 2D input from a single viewpoint. The user rst draws the curve as it appears from the current viewpoint, and then draws its shadow on the oor plane. The system correlates the curve with its shadow to compute the curve's 3D shape. This method is more natural than existing methods in that it leverages skills that many artists and designers have developed from work with pencil and paper.
7017581
Multi-finger cursor techniques
The mouse cursor acts as a digital proxy for a finger on graphical displays. Our hands, however, have ten fingers and many degrees of freedom that we use to interact with the world. We posit that by creating graphical cursors that reflect more of the hand's physical properties, we can allow for richer and more fluid interaction. We demonstrate this idea with three new cursors that are controlled by the user's fingers using a multi-point touchpad. The first two techniques allow for simultaneous control of several properties of graphical objects, while the third technique makes several enhancements to object selection.
6477925
Constructive solid geometry for polyhedral objects
Constructive Solid Geometry (CSG) is a powerful way of describing solid objects for computer graphics and modeling. The surfaces of any primitive object (such as a cube, sphere or cylinder) can be approximated by polygons. Being abile to find the union, intersection or difference of these objects allows more interesting and complicated polygonal objects to be created. The algorithm presented here performs these set operations on objects constructed from convex polygons. These objects must bound a finite volume, but need not be convex. An object that results from one of these operations also contains only convex polygons, and bounds a finite volume; thus, it can be used in later combinations, allowing the generation of quite complicated objects. Our algorithm is robust and is presented in enough detail to be implemented.
6983775
Modeling surfaces of arbitrary topology using manifolds
Manifolds describe complicated objects that are locally $\Re\sp{n}$ by defining a set of overlapping maps from the object to $\Re\sp{n}$. In this thesis we present a general technique for inverting that process: we define a complicated object from a set of overlapping subsets of $\Re\sp{n}$. We first present a constructive definition that describes how to perform such a construction in general. We then apply this construction to the particular problem of defining surfaces of arbitrary topology. The surface is built in two steps: we build a manifold with the correct topology then embed the manifold into $\Re\sp3$ using traditional spline techniques. The surface inherits many of the properties of B-splines: local control, a compact representation, and guaranteed continuity of arbitrary degree. The surface is specified using a polyhedral control mesh instead of a rectangular one; the resulting surface approximates the polyhedral mesh much as a B-spline approximates its rectangular control mesh. Like a B-spline, the surface is a single, continuous object.
795737
Navigating documents with the virtual scroll ring
We present a technique for scrolling through documents that is simple to implement and requires no special hardware. This is accomplished by simulating a hardware scroll ring--a device that maps circular finger motion into vertical scrolling. The technique performs at least as well as a mouse wheel for medium and long distances, and is preferred by users. It can be particularly useful in portable devices where screen-space and space for peripherals is at a premium.
2239491
Voice as sound: using non-verbal voice input for interactive control
We describe the use of non-verbal features in voice for direct control of interactive applications. Traditional speech recognition interfaces are based on an indirect, conversational model. First the user gives a direction and then the system performs certain operation. Our goal is to achieve more direct, immediate interaction like using a button or joystick by using lower-level features of voice such as pitch and volume. We are developing several prototype interaction techniques based on this idea, such as "control by continuous voice", "rate-based parameter control by pitch," and "discrete parameter control by tonguing." We have implemented several prototype systems, and they suggest that voice-as-sound techniques can enhance traditional voice recognition approach.
45717332
Fast Abstract Interpretation Using Sequential Algorithms
interpretation in the framework introduced by Cousot and Cousot requires finding fixpoints of continuous functions between abstract lattices [CC77]. Very often these abstract functions are expressed as typed ,~-expressions, even when the language being analysed isn't functional--for example an abstract interpretation derived from a denotational semantics in the style of Nielson [Nie82] will naturally be in this form. So implementing an abstract interpreter often requires an evaluator for ,k-expressions over lattices. Of course, evaluation must always terminate--even when the result is the bottom element of the lattice concerned. In practice this evaluation is intractable. The problem is caused by function types: lattices of functions grow more than exponentially in the size of their type. A-expressions of quite simple types therefore denote functions that are too enormous to manipulate efficiently. Attempts to find clever representations of functions (as frontiers) have really failed to solve the problem [HH92], and in practice the intractability is avoided by avoiding functions--function types may be abstracted as the one point type, discarding all information about function values, or analyses may be constructed from a more intensional semantics in which 'function' values are closures (code-environment pairs), so that true functions do not appear. Such approaches are forced to make more or less ad hoc approximations, at a cost in accuracy, and moreover cannot yield faithful implementations of the many analyses in the literature in which functions are abstracted as functions. In this paper we describe an approach which we hope will make evaluation of )~-expressions over finite lattices tractable in practice. Our basic idea is to save time by computing only part of the value of each ,kexpression. For example, to compute the value of the application el e2 it's not necessary to compute the value of el precisely. We only need to know what value el returns when applied to e2 --one point in the graph of the function, rather than the whole graph. Moreover, if el is a constant function, we may not need to compute the value of e2 at all. Or if e2 is itself a function, el may only apply it to a couple of different arguments, and so we may only need to know its value at a few points rather than its entire graph. Our intention is to lazily compute only as much as is needed of each expression, in the hope that in normal cases this will be only a tiny proportion of the whole. This idea is also at the heart of Young's pending analysis [YH86] and Launchbury's use of minimal function graphs [Lau91] to represent just the part of the graph that is needed, but these approaches are really confined to first-order functions. Our contribution is to extend the same idea smoothly to the higher-order case.
8892107
Generalising monads to arrows
Abstract Monads have become very popular for structuring functional programs since Wadler introduced their use in 1990. In particular, libraries of combinators are often based on a monadic type. Such libraries share (in part) a common interface, from which numerous benefits flow, such as the possibility to write generic code which works together with any library. But, several interesting and useful libraries are fundamentally incompatible with the monadic interface. In this paper I propose a generalisation of monads, which I call arrows, with significantly wider applicability. The paper shows how many of the techniques of monadic programming generalise to the new setting, and gives examples to show that the greater generality is useful. In particular, three non-monadic libraries for efficient parsing, building graphical user interfaces, and programming active web pages fit naturally into the new framework.
42717421
Global variables in Haskell
Haskell today provides good support not only for a functional programming style, but also for an imperative one. Elements of imperative programming are needed in applications such as web servers, or to provide efficient implementations of well-known algorithms, such as many graph algorithms. However, one element of imperative programming, the global variable, is surprisingly hard to emulate in Haskell. We discuss several existing methods, none of which is really satisfactory, and finally propose a new approach based on implicit parameters. This approach is simple, safe, and efficient, although it does reveal weaknesses in Haskell's present type system.
27745403
Type Specialisation for the lambda-Calculus; or, A New Paradigm for Partial Evaluation Based on Type Inference
958035
A Loop-Detecting Interpreter for Lazy, Higher-Order Programs
Interpreters that detect some forms of non-termination have a variety of applications, from abstract interpretation to partial evaluation. A simple and often used strategy is to test for a repeated state, but this cannot handle infinite values (such as first-class functions) or unevaluated states such as arise in lazy programs. In this paper we propose using Berry and Curien’s theory of sequential algorithms as a semantic foundation for loop detection: we obtain straightforwardly a loop detector for lazy higher-order functional programs, which is more effective than the simple strategy even for strict first order cases.