7238760
Analyzing bounding boxes for object intersection
Heuristics that exploit bouning boxes are common in algorithms for rendering, modeling, and animation. While experience has shown that bounding boxes improve the performance of these algorithms in practice, the previous theoretical analysis has concluded that bounding boxes perform poorly in the worst case. This paper reconciles this discrepancy by analyzing intersections among <italic>n</italic> geometric objects in terms of two parameters: α an upper bound on the <italic>aspect ratio</italic> or elongatedness of each object; and &sgr; an upper bound on the <italic>scale factor</italic> or size disparity between the largest and smallest  objects. Letting <italic>K<subscrpt>o</subscrpt></italic> and <italic>K<subscrpt>b</subscrpt></italic> be the number of intersecting object       pairs and bounding box pairs, respectively, we analyze a ratio measure of the   bounding boxes'  efficiency, <inline-equation> <f> <g>r</g>=K<inf>b</inf>/<fen lp="par">n+K<inf>o</inf><rp post="par"></fen> </f> </inline-equation>. The analysis proves that <inline-equation> <f> <g>r</g>=O<fen lp="par"><g>a</g><rad><rcd><g>s</g></rcd></rad> <lim align="r"><op><rf>log</rf></op><ul>2</ul></lim><g>s</g><rp post="par"></fen> </f> </inline-equation> and <inline-equation> <f> <g>r</g>=<g>W</g><fen lp="par"><g>a</g><rad><rcd><g>s</g></rcd></rad> <rp post="par"></fen></f> </inline-equation>.
 One important consequence is that if α and &sgr; are small constants (as is often the case in practice), then<italic>K<subscrpt>b</subscrpt></italic>= <italic>O</italic>(<italic>K<subscrpt>o</subscrpt></italic>)+<italic>O</italic>(<italic>n</italic>, so an algorithm that uses bounding boxes has time complexity proportional to the number of actual object intersections. This theoretical result validates the efficiency that bounding boxes have demonstrated in practice. Another consequence of our analysis is a proof of the output-sensitivity of an algorithm for reporting all intersecting pairs in a set of <italic>n</italic> convex polyhedra with constant α and &sgr;. The algorithm takes time <italic>O</italic>(<italic>n</italic>log<supscrpt><italic>d</italic>−1</supscrpt><italic>n</italic>+<italic>K<subscrpt>o</subscrpt></italic>log<supscrpt><italic>d</italic>−1</supscrpt><italic>n</italic>) for dimension <italic>d</italic> = 2, 3. This running time improves on the performance of previous algorithms, which make no assumptions about α and &sgr;.
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.
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.
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.
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.
7653698
Reversing Abstract Interpretations
Program analyses are often presented as one of two brands: forwards or backwards. In this paper we explore the significance of the direction of analysis, and show how arbitrary abstract interpretations may be reversed.
17667421
Assessing undergraduate experience of continuous integration and test-driven development
A number of agile practices are included in software engineering curricula, including test-driven development. Continuous integration often is not included, despite it becoming increasingly common in industry to code, test, and integrate at the same time. This paper describes a study whereby software engineering undergraduates were given a short intensive experience of test-driven development with continuous integration using an environment that imitated a typical industrial circumstance. Assessment was made of students' agile experience rather than of project deliverables, using a novel set of process measures that examined students' participation and performance in agile testing. Results showed good participation by student pairs, and clear understanding of agile processes and configuration management. Future work will investigate automation of the assessment of continuous integration and configuration management server data.
14884785
Projections for Polymorphic First-Order Strictness Analysis
We apply the categorical properties of polymorphic functions to compile-time analysis, specifically projection-based strictness analysis. First we interpret parameterised types as functors in a suitable category, and show that they preserve monics and epics. Then we define “strong” and “weak” polymorphism, the latter admitting certain projections that are not polymorphic in the usual sense. We prove that, under the right conditions, a weakly polymorphic function is characterised by a single instance. It follows that the strictness analysis of one simple instance of a polymorphic function yields results that apply to all. We show how this theory may be applied. In comparison with earlier polymorphic strictness analysis methods, ours can apply polymorphic information to a particular instance very simply. The categorical approach simplifies our proofs, enabling them to be carried out at a higher level, and making them independent of the precise form of the programming language to be analysed. The major limitation of our results is that they apply only to first-order functions.
15979240
Type specialization
Permission to make digital/hard copy of part or all of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee.
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.