bluuebunny/crossref_metadata_2025 huggingface dataset:
Exploiting purity for atomicity
Authors: Flanagan Cormac , Freund Stephen N. , Qadeer Shaz
Published: October 2004

The notion that certain procedures are
atomic
is a fundamental correctness property of many multithreaded software systems. A procedure is atomic if for every execution there is an equivalent serial execution in which the actions performed by any thread while executing the atomic procedure are not interleaved with actions of other threads. Several existing tools verify atomicity by using commutativity of actions to show that every execution
reduces
to a corresponding serial execution. However, experiments with these tools have highlighted a number of interesting procedures that, while intuitively atomic, are not reducible.In this paper, we exploit the notion of
pure
code blocks to verify the atomicity of such irreducible procedures. If a pure block terminates normally, then its evaluation does not change the program state, and hence these evaluation steps can be removed from the program trace before reduction. We develop a static analysis for atomicity based on this insight, and we illustrate this analysis on a number of interesting examples that could not be verified using earlier tools based purely on reduction. The techniques developed in this paper may also be applicable in other approaches for verifying atomicity, such as model checking and dynamic analysis.
Model checking XML manipulating software
Authors: Fu Xiang , Bultan Tevfik , Su Jianwen
Published: October 2004

The use of XML as the de facto data exchange standard has allowed integration of heterogeneous web based software systems regardless of implementation platforms and programming languages. On the other hand, the rich tree-structured data representation, and the expressive XML query languages (such as XPath) make formal specification and verification of software systems that manipulate XML data a challenge. In this paper, we present our initial efforts in automated verification of XML data manipulation operations using the SPIN model checker. We present algorithms for translating (bounded) XML data and XPath expressions to Promela, the input language of SPIN. The techniques presented in this paper constitute the basis of our Web Service Analysis Tool (WSAT) which verifies LTL properties of composite web services.
A formal approach for modeling and verification of RTCORBA-based applications
Authors: Rossi Matteo , Mandrioli Dino
Published: October 2004

We introduce a formal model for describing Real-Time CORBA-based applications, and a set of guidelines to formally check that the design of such an application is consistent with its specification. The model and the guidelines are then applied to the verification of a simple test application.
Verifying process models built using parameterized state machines
Authors: Lerner Barbara Staudt
Published: October 2004

Software process and work flow languages are increasingly used to define loosely-coupled systems of systems. These languages focus on coordination issues such as data flow and control flow among the subsystems and exception handling activities. The resulting systems are often highly concurrent with activities distributed over many computers. Adequately testing these systems is not feasible due to their size, concurrency, and distributed implementation. Furthermore, the concurrent nature of their activities makes it likely that errors related to the order in which activities are interleaved will go undetected during testing. As a result, verification using static analysis seems necessary to increase confidence in the correctness of these systems. In this paper, we describe our experiences applying LTSA to the analysis of software processes written in Little-JIL. A key aspect to the approach taken in this analysis is that the model that is analyzed consists of a reusable portion that defines language semantics and a process-specific portion that uses parameterization and composition of pieces of the reusable portion to capture the semantics of a Little-JIL process. While the reusable portion was constructed by hand, the parameterization and composition required to model a process is automated. Furthermore, the reusable portion of the model encodes the state machines used in the implementation of the Little-JIL interpreter. As a result, analysis is based not just on the intended semantics of the Little-JIL constructs but on their actual execution semantics. This paper describes how Little-JIL processes are translated into models and reports on analysis results, which have uncovered seven errors in the Little-JIL interpreter that were previously unknown as well as an error in a software process that had previously been analyzed with a different approach without finding the error.
A new approach for integration of min-area retiming and min-delay padding for simultaneously addressing short-path and long-path constraints
Authors: Sundararajan Vijay , Sapatnekar Sachin S. , Parhi Keshab K.
Published: October 2004

This article describes a polynomial time algorithm for min-area retiming for edge-triggered circuits to handle
both
setup and hold constraints. Given a circuit
G
and a target clock period
c
, our algorithm either outputs a retimed version of
G
satisfying setup and hold constraints or reports that such a solution is not possible, in
O
(∣V∣
3
log
∣
V
∣
log
(∣
V
∣
C
)) steps, where ∣
V
∣ corresponds to number of gates in the circuit and
C
is equal to the number of registers in the circuit. This is the first polynomial-time algorithm ever reported for min-area retiming with constraints on both long and short-paths. An alternative problem formulation that takes practical issues into consideration and lowers the problem complexity is also developed. Both the problem formulations have many parallels with the original formulation of
long path only
retiming by Leiserson and Saxe and all the speed improvements that have been obtained on that problem statement are also demonstrated in simulation for the approach presented here. Finally, a basis is provided for deriving efficient heuristics for addressing both long-path and short-path requirements by combining the techniques of retiming and min-delay padding.
The session token protocol for forensics and traceback
Authors: Carrier Brian , Shields Clay
Published: October 2004

In this paper we present the Session Token Protocol (STOP), a new protocol that can assist in the forensic analysis of a computer involved in malicious network activity. It has been designed to help automate the process of tracing attackers who log on to a series of hosts to hide their identity. STOP utilizes the Identification Protocol infrastructure, improving both its capabilities and user privacy. On request, the STOP protocol saves user-level and application-level data associated with a particular TCP connection and returns a random token specifically related to that session. The saved data are not revealed to the requester unless the token is returned to the local administrator, who verifies the legitimacy of the need for the release of information. The protocol supports recursive traceback requests to gather information about the entire path of a connection. This allows an incident investigator to trace attackers to their home systems, but does not violate the privacy of normal users. This paper details the new protocol and presents implementation and performance results.
Modular authorization and administration
Authors: Wedde Horst F. , Lischka Mario
Published: October 2004

In large organizations the administration of access privileges (such as the assignment of access rights to a user in a particular role) is handled cooperatively through distributed administrators in various different capacities. A quorum may be necessary, or a veto may be possible for such a decision. In this paper, we present two major contributions: We develop a
role-based access control
(RBAC) approach for specifying distributed administration requirements, and procedures between administrators, or administration teams, extending earlier work on distributed (modular) authorization. While a comprehensive specification in such a language is conceivable it would be quite tedious to evaluate, or analyze, their operational aspects and properties in practice. For this reason we create a new class of extended Petri Nets called Administration Nets (Adm-Nets) such that any RBAC specification of (cooperative) administration requirements (given in terms of predicate logic formulas) can be embedded into an Adm-Net. This net behaves within the constraints specified by the logical formulas, and at the same time, it
explicitly
exhibits all needed operational details such as allowing for an efficient and comprehensive formal analysis of administrative behavior. We introduce the new concepts and illustrate their use in several examples. While Adm-Nets are much more refined and (behaviorally) explicit than workflow systems our work provides for a constructive step towards novel workflow management tools as well. We demonstrate the usefulness of Adm-Nets by modeling typical examples of administration processes concerned with sets of distributed authorization rules.
The myths of usability ROI
Authors: Rosenberg Daniel
Published: October 2004

As I have followed the ongoing discussion in our field about usability ROI, I have consistently had the feeling that this debate is taking place on a different planet than the one I am familiar with. From my perspective, as an executive overseeing the user experience (UE) group at the world's second largest software company, much of this debate is based on misconceptions. As I stated in a recent talk at Xerox PARC hosted by BayCHI [7], in my 20 plus years of experience, I have never been asked to produce an ROI analysis.
Log on, tune in, drop down
Authors: Becker Ken
Published: October 2004

Every one of us, I'll bet, can recall numerous encounters with Web drop-down lists that behave differently from what we expect. Sometimes they go off and act on our selections before we're ready, leaving us shrieking ("Stop, I haven't finished!"); other times we wait patiently for something to happen, not realizing we have to click a "Go" button. Arguing for consistency in the "Go" direction, Ken Becker explains why going "Go-less" overloads the drop-down and reduces user control.
    ---Elizabeth Buie
Graphics gems revisited
Authors: Guy Stephane , Soler Cyril
Published: October 2004

We present an algorithm for rendering faceted colored gemstones in real time, using graphics hardware. Beyond the technical challenge of handling the complex behavior of light in such objects, a real time high quality rendering of gemstones has direct applications in the field of jewelry prototyping, which has now become a standard practice for replacing tedious (and less interactive) wax carving methods. Our solution is based on a number of controlled approximations of the physical phenomena involved when light enters a stone, which permit an implementation based on the most recent -- yet commonly available -- hardware features such as fragment programs, cube-mapping.
Perceptual audio rendering of complex virtual environments
Authors: Tsingos Nicolas , Gallo Emmanuel , Drettakis George
Published: October 2004

We propose a real-time 3D audio rendering pipeline for complex virtual scenes containing hundreds of moving sound sources. The approach, based on auditory culling and spatial level-of-detail, can handle more than ten times the number of sources commonly available on consumer 3D audio hardware, with minimal decrease in audio quality. The method performs well for both indoor and outdoor environments. It leverages the limited capabilities of audio hardware for many applications, including interactive architectural acoustics simulations and automatic 3D voice management for video games.Our approach dynamically eliminates inaudible sources and groups the remaining audible sources into a budget number of clusters. Each cluster is represented by one impostor sound source, positioned using perceptual criteria. Spatial audio processing is then performed only on the impostor sound sources rather than on every original source thus greatly reducing the computational cost.A pilot validation study shows that degradation in audio quality, as well as localization impairment, are limited and do not seem to vary significantly with the cluster budget. We conclude that our real-time perceptual audio rendering pipeline can generate spatialized audio for complex auditory environments without introducing disturbing changes in the resulting perceived soundfield.
Making papercraft toys from meshes using strip-based approximate unfolding
Authors: Mitani Jun , Suzuki Hiromasa
Published: October 2004

We propose a new method for producing unfolded papercraft patterns of rounded toy animal figures from triangulated meshes by means of strip-based approximation. Although in principle a triangulated model can be unfolded simply by retaining as much as possible of its connectivity while checking for intersecting triangles in the unfolded plane, creating a pattern with tens of thousands of triangles is unrealistic. Our approach is to approximate the mesh model by a set of continuous triangle strips with no internal vertices. Initially, we subdivide our mesh into parts corresponding to the features of the model. We segment each part into zonal regions, grouping triangles which are similar topological distances from the part boundary. We generate triangle strips by simplifying the mesh while retaining the borders of the zonal regions and additional cut-lines. The pattern is then created simply by unfolding the set of strips. The distinguishing feature of our method is that we approximate a mesh model by a set of continuous strips, not by other ruled surfaces such as parts of cones or cylinders. Thus, the approximated unfolded pattern can be generated using only mesh operations and a simple unfolding algorithm. Furthermore, a set of strips can be crafted just by bending the paper (without breaking edges) and can represent smooth features of the original mesh models.
A simple manifold-based construction of surfaces of arbitrary smoothness
Authors: Ying Lexing , Zorin Denis
Published: October 2004

We present a smooth surface construction based on the manifold approach of Grimm and Hughes. We demonstrate how this approach can relatively easily produce a number of desirable properties which are hard to achieve simultaneously with polynomial patches, subdivision or variational surfaces. Our surfaces are
C
∞
-continuous with explicit nonsingular
C
∞
parameterizations, high-order flexible at control vertices, depend linearly on control points, have fixed-size local support for basis functions, and have good visual quality.
Interactive digital photomontage
Authors: Agarwala Aseem , Dontcheva Mira , Agrawala Maneesh , Drucker Steven , Colburn Alex , Curless Brian , Salesin David , Cohen Michael
Published: October 2004

We describe an interactive, computer-assisted framework for combining parts of a set of photographs into a single composite picture, a process we call "digital photomontage." Our framework makes use of two techniques primarily: graph-cut optimization, to choose good seams within the constituent images so that they can be combined as seamlessly as possible; and gradient-domain fusion, a process based on Poisson equations, to further reduce any remaining visible artifacts in the composite. Also central to the framework is a suite of interactive tools that allow the user to specify a variety of high-level image objectives, either globally across the image, or locally through a painting-style interface. Image objectives are applied independently at each pixel location and generally involve a function of the pixel values (such as "maximum contrast") drawn from that same location in the set of source images. Typically, a user applies a series of image objectives iteratively in order to create a finished composite. The power of this framework lies in its generality; we show how it can be used for a wide variety of applications, including "selective composites" (for instance, group photos in which everyone looks their best), relighting, extended depth of field, panoramic stitching, clean-plate production, stroboscopic visualization of movement, and time-lapse mosaics.
Lazy snapping
Authors: Li Yin , Sun Jian , Tang Chi-Keung , Shum Heung-Yeung
Published: October 2004

In this paper, we present
Lazy Snapping
, an interactive image cutout tool. Lazy Snapping separates coarse and fine scale processing, making object specification and detailed adjustment
easy
. Moreover, Lazy Snapping provides instant visual feedback,
snapping
the cutout contour to the true object boundary efficiently despite the presence of ambiguous or low contrast edges. Instant feedback is made possible by a novel image segmentation algorithm which combines graph cut with pre-computed over-segmentation. A set of intuitive user interface (UI) tools is designed and implemented to provide flexible control and editing for the users. Usability studies indicate that Lazy Snapping provides a better user experience and produces better segmentation results than the state-of-the-art interactive image cutout tool, Magnetic Lasso in Adobe Photoshop.
Volumetric illustration
Authors: Owada Shigeru , Nielsen Frank , Okabe Makoto , Igarashi Takeo
Published: October 2004

This paper presents an interactive system for designing and browsing volumetric illustrations. Volumetric illustrations are 3D models with internal textures that the user can browse by cutting the models at desired locations. To assign internal textures to a surface mesh, the designer cuts the mesh and provides simple guiding information to specify the correspondence between the cross-section and a reference 2D image. The guiding information is stored with the geometry and used during the synthesis of cross-sectional textures. The key idea is to synthesize a plausible cross-sectional image using a 2D texture-synthesis technique, instead of sampling from a complete 3D RGB volumetric representation directly. This simplifies the design interface and reduces the amount of data, making it possible for non-experts to rapidly design and use volumetric illustrations. We believe that our system can enrich human communications in various domains, such as medicine, biology, and geology.
Stereological techniques for solid textures
Authors: Jagnow Robert , Dorsey Julie , Rushmeier Holly
Published: October 2004

We describe the use of traditional stereological methods to synthesize 3D solid textures from 2D images of existing materials. We first illustrate our approach for aggregate materials of spherical particles, and then extend the technique to apply to particles of arbitrary shapes. We demonstrate the effectiveness of the approach with side-by-side comparisons of a real material and a synthetic model with its appearance parameters derived from its physical counterpart. Unlike ad hoc methods for texture synthesis, stereology provides a disciplined, systematic basis for predicting material structure with well-defined assumptions.
TensorTextures
Authors: Vasilescu M. Alex O. , Terzopoulos Demetri
Published: October 2004

This paper introduces a tensor framework for image-based rendering. In particular, we develop an algorithm called TensorTextures that learns a parsimonious model of the bidirectional texture function (BTF) from observational data. Given an ensemble of images of a textured surface, our nonlinear, generative model explicitly represents the multifactor interaction implicit in the detailed appearance of the surface under varying photometric angles, including local (per-texel) reflectance, complex mesostructural self-occlusion, interreflection and self-shadowing, and other BTF-relevant phenomena. Mathematically, TensorTextures is based on multilinear algebra, the algebra of higher-order tensors, hence its name. It is computed through a decomposition known as the
N
-mode SVD, an extension to tensors of the conventional matrix singular value decomposition (SVD). We demonstrate the application of TensorTextures to the image-based rendering of natural and synthetic textured surfaces under continuously varying viewpoint and illumination conditions.
Shell texture functions
Authors: Chen Yanyun , Tong Xin , Wang Jiaping , Lin Stephen , Guo Baining , Shum Heung-Yeung
Published: October 2004

We propose a texture function for realistic modeling and efficient rendering of materials that exhibit surface mesostructures, translucency and volumetric texture variations. The appearance of such complex materials for dynamic lighting and viewing directions is expensive to calculate and requires an impractical amount of storage to precompute. To handle this problem, our method models an object as a shell layer, formed by texture synthesis of a volumetric material sample, and a homogeneous inner core. To facilitate computation of surface radiance from the shell layer, we introduce the
shell texture function
(STF) which describes voxel irradiance fields based on precomputed fine-level light interactions such as shadowing by surface mesostructures and scattering of photons inside the object. Together with a diffusion approximation of homogeneous inner core radiance, the STF leads to fast and detailed raytraced renderings of complex materials.
Textureshop
Authors: Fang Hui , Hart John C.
Published: October 2004

We combine existing techniques for shape-from-shading and texture synthesis to create a new tool for texturing objects in photographs. Our approach clusters pixels with similar recovered normals into patches on which texture is synthesized. Distorting the texture based on the recovered normals creates the illusion that the texture adheres to the undulations of the photographed surface. Inconsistencies in the recovered surface are disguised by the graphcut blending of the individually textured patches. Further applications include the generation of detail on manually-shaded painting, extracting and synthesizing a displacement map from a texture swatch, and the embossed transfer of normals from one image to another, which would be difficult to create with current image processing packages.
Flow-based video synthesis and editing
Authors: Bhat Kiran S. , Seitz Steven M. , Hodgins Jessica K. , Khosla Pradeep K.
Published: October 2004

This paper presents a novel algorithm for synthesizing and editing video of natural phenomena that exhibit continuous flow patterns. The algorithm analyzes the motion of textured particles in the input video along user-specified flow lines, and synthesizes seamless video of arbitrary length by enforcing temporal continuity along a second set of user-specified flow lines. The algorithm is simple to implement and use. We used this technique to edit video of water-falls, rivers, flames, and smoke.
Feature matching and deformation for texture synthesis
Authors: Wu Qing , Yu Yizhou
Published: October 2004

One significant problem in patch-based texture synthesis is the presence of broken features at the boundary of adjacent patches. The reason is that optimization schemes for patch merging may fail when neighborhood search cannot find satisfactory candidates in the sample texture because of an inaccurate similarity measure. In this paper, we consider both curvilinear features and their deformation. We develop a novel algorithm to perform feature matching and alignment by measuring structural similarity. Our technique extracts a feature map from the sample texture, and produces both a new feature map and texture map. Texture synthesis guided by feature maps can significantly reduce the number of feature discontinuities and related artifacts, and gives rise to satisfactory results.
Near-regular texture analysis and manipulation
Authors: Liu Yanxi , Lin Wen-Chieh , Hays James
Published: October 2004

A near-regular texture deviates geometrically and photometrically from a regular congruent tiling. Although near-regular textures are ubiquitous in the man-made and natural world, they present computational challenges for state of the art texture analysis and synthesis algorithms. Using regular tiling as our anchor point, and with user-assisted lattice extraction, we can explicitly model the deformation of a near-regular texture with respect to geometry, lighting and color. We treat a deformation field both as a function that acts on a texture and as a texture that is acted upon, and develop a multi-modal framework where each deformation field is subject to analysis, synthesis and manipulation. Using this formalization, we are able to construct simple parametric models to faithfully synthesize the appearance of a near-regular texture and purposefully control its regularity.
Rigid fluid
Authors: Carlson Mark , Mucha Peter J. , Turk Greg
Published: October 2004

We present the
Rigid Fluid
method, a technique for animating the interplay between rigid bodies and viscous incompressible fluid with free surfaces. We use distributed Lagrange multipliers to ensure two-way coupling that generates realistic motion for both the solid objects and the fluid as they interact with one another. We call our method the
rigid fluid
method because the simulator treats the rigid objects as if they were made of fluid. The rigidity of such an object is maintained by identifying the region of the velocity field that is inside the object and constraining those velocities to be rigid body motion. The rigid fluid method is straightforward to implement, incurs very little computational overhead, and can be added as a bridge between current fluid simulators and rigid body solvers. Many solid objects of different densities (
e.g.
, wood or lead) can be combined in the same animation.
A virtual node algorithm for changing mesh topology during simulation
Authors: Molino Neil , Bao Zhaosheng , Fedkiw Ron
Published: October 2004

We propose a virtual node algorithm that allows material to separate along arbitrary (possibly branched) piecewise linear paths through a mesh. The material within an element is fragmented by creating several replicas of the element and assigning a portion of real material to each replica. This results in elements that contain both real material and empty regions. The missing material is contained in another copy (or copies) of this element. Our new virtual node algorithm automatically determines the number of replicas and the assignment of material to each. Moreover, it provides the degrees of freedom required to simulate the partially or fully fragmented material in a fashion consistent with the embedded geometry. This approach enables efficient simulation of complex geometry with a simple mesh, i.e. the geometry need not align itself with element boundaries. It also alleviates many shortcomings of traditional Lagrangian simulation techniques for meshes with changing topology. For example, slivers do not require small CFL time step restrictions since they are embedded in well shaped larger elements. To enable robust simulation of embedded geometry, we propose new algorithms for handling rigid body and self collisions. In addition, we present several mechanisms for influencing and controlling fracture with grain boundaries, prescoring, etc. We illustrate our method for both volumetric and thin-shell simulations.
BD-tree
Authors: James Doug L. , Pai Dinesh K.
Published: October 2004

We introduce the Bounded Deformation Tree, or BD-Tree, which can perform collision detection with reduced deformable models at costs comparable to collision detection with rigid objects. Reduced deformable models represent complex deformations as linear superpositions of arbitrary displacement fields, and are used in a variety of applications of interactive computer graphics. The BD-Tree is a bounding sphere hierarchy for output-sensitive collision detection with such models. Its bounding spheres can be updated after deformation in any order, and at a cost independent of the geometric complexity of the model; in fact the cost can be as low as one multiplication and addition per tested sphere, and at most linear in the number of reduced deformation coordinates. We show that the BD-Tree is also extremely simple to implement, and performs well in practice for a variety of real-time and complex off-line deformable simulation examples.
Deformation transfer for triangle meshes
Authors: Sumner Robert W. , Popović Jovan
Published: October 2004

Deformation transfer applies the deformation exhibited by a source triangle mesh onto a different target triangle mesh. Our approach is general and does not require the source and target to share the same number of vertices or triangles, or to have identical connectivity. The user builds a correspondence map between the triangles of the source and those of the target by specifying a small set of vertex markers. Deformation transfer computes the set of transformations induced by the deformation of the source mesh, maps the transformations through the correspondence from the source to the target, and solves an optimization problem to consistently apply the transformations to the target shape. The resulting system of linear equations can be factored once, after which transferring a new deformation to the target mesh requires only a backsubstitution step. Global properties such as foot placement can be achieved by constraining vertex positions. We demonstrate our method by retargeting full body key poses, applying scanned facial deformations onto a digital character, and remapping rigid and non-rigid animation sequences from one mesh onto another.
VisualIDs
Authors: Lewis J. P. , Rosenholtz Ruth , Fong Nickson , Neumann Ulrich
Published: October 2004

Although existing GUIs have a sense of space, they provide no sense of place. Numerous studies report that users misplace files and have trouble wayfinding in virtual worlds despite the fact that people have remarkable visual and spatial abilities. This issue is considered in the human-computer interface field and has been addressed with alternate display/navigation schemes. Our paper presents a fundamentally graphics based approach to this 'lost in hyperspace' problem. Specifically, we propose that spatial display of files is not sufficient to engage our visual skills;
scenery
(distinctive visual appearance) is needed as well. While scenery (in the form of custom icon assignments) is already possible in current operating systems, few if any users take the time to manually assign icons to all their files. As such, our proposal is to generate visually distinctive icons ("VisualIDs")
automatically
, while allowing the user to replace the icon if desired. The paper discusses psychological and conceptual issues relating to icons, visual memory, and the necessary relation of scenery to data. A particular icon generation algorithm is described; subjects using these icons in simulated file search and recall tasks show significantly improved performance with little effort. Although the incorporation of scenery in a graphical user interface will introduce many new (and interesting) design problems that cannot be addressed in this paper, we show that automatically created scenery is both beneficial and feasible.
Motion doodles
Authors: Thorne Matthew , Burke David , van de Panne Michiel
Published: October 2004

In this paper we present a novel system for sketching the motion of a character. The process begins by sketching a character to be animated. An animated motion is then created for the character by drawing a continuous sequence of lines, arcs, and loops. These are parsed and mapped to a parameterized set of output motions that further reflect the location and timing of the input sketch. The current system supports a repertoire of 18 different types of motions in 2D and a subset of these in 3D. The system is unique in its use of a cursive motion specification, its ability to allow for fast experimentation, and its ease of use for non-experts.
MathPad
2
Authors: LaViola Joseph J. , Zeleznik Robert C.
Published: October 2004

We present
mathematical sketching
, a novel, pen-based, modeless gestural interaction paradigm for mathematics problem solving. Mathematical sketching derives from the familiar pencil-and-paper process of drawing supporting diagrams to facilitate the formulation of mathematical expressions; however, with a mathematical sketch, users can also leverage their physical intuition by watching their hand-drawn diagrams animate in response to continuous or discrete parameter changes in their written formulas. Diagram animation is driven by implicit associations that are inferred, either automatically or with gestural guidance, from mathematical expressions, diagram labels, and drawing elements. The modeless nature of mathematical sketching enables users to switch freely between modifying diagrams or expressions and viewing animations. Mathematical sketching can also support computational tools for graphing, manipulating and solving equations; initial feedback from a small user group of our mathematical sketching prototype application, MathPad
2
, suggests that it has the potential to be a powerful tool for mathematical problem solving and visualization.
Target-driven smoke animation
Authors: Fattal Raanan , Lischinski Dani
Published: October 2004

In this paper we present a new method for efficiently controlling animated smoke. Given a sequence of target smoke states, our method generates a smoke simulation in which the smoke is driven towards each of these targets in turn, while exhibiting natural-looking interesting smoke-like behavior. This control is made possible by two new terms that we add to the standard flow equations: (i) a driving force term that causes the fluid to carry the smoke towards a particular target, and (ii) a smoke gathering term that prevents the smoke from diffusing too much. These terms are explicitly defined by the instantaneous state of the system at each simulation timestep. Thus, no expensive optimization is required, allowing complex smoke animations to be generated with very little additional cost compared to ordinary flow simulations.
An approximate global illumination system for computer generated films
Authors: Tabellion Eric , Lamorlette Arnauld
Published: October 2004

Lighting models used in the production of computer generated feature animation have to be flexible, easy to control, and efficient to compute. Global illumination techniques do not lend themselves easily to flexibility, ease of use, or speed, and have remained out of reach thus far for the vast majority of images generated in this context. This paper describes the implementation and integration of indirect illumination within a feature animation production renderer. For efficiency reasons, we choose to partially solve the rendering equation. We explain how this compromise allows us to speed-up final gathering calculations and reduce noise. We describe an efficient ray tracing strategy and its integration with a micro-polygon based scan line renderer supporting displacement mapping and programmable shaders. We combine a modified irradiance gradient caching technique with an approximate lighting model that enhances caching coherence and provides good scalability to render complex scenes into high-resolution images suitable for film. We describe the tools that are made available to the artists to control indirect lighting in final renders. We show that our approach provides an efficient solution, easy to art direct, that allows animators to enhance considerably the quality of images generated for a large category of production work.
Triple product wavelet integrals for all-frequency relighting
Authors: Ng Ren , Ramamoorthi Ravi , Hanrahan Pat
Published: October 2004

This paper focuses on efficient rendering based on pre-computed light transport, with realistic materials and shadows under all-frequency direct lighting such an environment maps. The basic difficulty is representation and computation in the 6D space of light direction, view direction, and surface position. While image-based and synthetic methods for real-time rendering have been proposed, they do not scale to high sampling rates with variation of both lighting and viewpoint. Current approaches are therefore limited to lower dimensionality (only lighting or viewpoint variation, not both) or lower sampling rates (low frequency lighting and materials). We propose a new mathematical and computational analysis of pre-computed light transport. We use
factored
forms, separately pre-computing and representing visibility and material properties. Rendering then requires computing
triple product integrals
at each vertex, involving the lighting, visibility and BRDF. Our main contribution is a general analysis of these triple product integrals, which are likely to have broad applicability in computer graphics and numerical analysis. We first determine the computational complexity in a number of bases like point samples, spherical harmonics and wavelets. We then give efficient linear and sublinear-time algorithms for Haar wavelets, incorporating non-linear wavelet approximation of lighting and BRDFs. Practically, we demonstrate rendering of images under new lighting and viewing conditions in a few seconds, significantly faster than previous techniques.
Efficient BRDF importance sampling using a factored representation
Authors: Lawrence Jason , Rusinkiewicz Szymon , Ramamoorthi Ravi
Published: October 2004

High-quality Monte Carlo image synthesis requires the ability to importance sample realistic BRDF models. However, analytic sampling algorithms exist only for the Phong model and its derivatives such as Lafortune and Blinn-Phong. This paper demonstrates an importance sampling technique for a wide range of BRDFs, including complex analytic models such as Cook-Torrance and measured materials, which are being increasingly used for realistic image synthesis. Our approach is based on a compact factored representation of the BRDF that is optimized for sampling. We show that our algorithm consistently offers better efficiency than alternatives that involve fitting and sampling a Lafortune or Blinn-Phong lobe, and is more compact than sampling strategies based on tabulating the full BRDF. We are able to efficiently create images involving multiple measured and analytic BRDFs, under both complex direct lighting and global illumination.
Speaking with hands
Authors: Stone Matthew , DeCarlo Doug , Oh Insuk , Rodriguez Christian , Stere Adrian , Lees Alyssa , Bregler Chris
Published: October 2004

We describe a method for using a database of recorded speech and captured motion to create an animated conversational character. People's utterances are composed of short, clearly-delimited phrases; in each phrase, gesture and speech go together meaningfully and synchronize at a common point of maximum emphasis. We develop tools for collecting and managing performance data that exploit this structure. The tools help create scripts for performers, help annotate and segment performance data, and structure specific messages for characters to use within application contexts. Our animations then reproduce this structure. They recombine motion samples with new speech samples to recreate coherent phrases, and blend segments of speech and motion together phrase-by-phrase into extended utterances. By framing problems for utterance generation and synthesis so that they can draw closely on a talented performance, our techniques support the rapid construction of animated characters with rich and appropriate expression.
Style-based inverse kinematics
Authors: Grochow Keith , Martin Steven L. , Hertzmann Aaron , Popović Zoran
Published: October 2004

This paper presents an inverse kinematics system based on a learned model of human poses. Given a set of constraints, our system can produce the most likely pose satisfying those constraints, in real-time. Training the model on different input data leads to different styles of IK. The model is represented as a probability distribution over the space of all possible poses. This means that our IK system can generate any pose, but prefers poses that are most similar to the space of poses in the training data. We represent the probability with a novel model called a Scaled Gaussian Process Latent Variable Model. The parameters of the model are all learned automatically; no manual tuning is required for the learning component of the system. We additionally describe a novel procedure for interpolating between styles.Our style-based IK can replace conventional IK, wherever it is used in computer animation and computer vision. We demonstrate our system in the context of a number of applications: interactive character posing, trajectory keyframing, real-time motion capture with missing markers, and posing from a 2D image.
Spacetime faces
Authors: Zhang Li , Snavely Noah , Curless Brian , Seitz Steven M.
Published: October 2004

We present an end-to-end system that goes from video sequences to high resolution, editable, dynamically controllable face models. The capture system employs synchronized video cameras and structured light projectors to record videos of a moving face from multiple viewpoints. A novel spacetime stereo algorithm is introduced to compute depth maps accurately and overcome over-fitting deficiencies in prior work. A new template fitting and tracking procedure fills in missing data and yields point correspondence across the entire sequence without using markers. We demonstrate a data-driven, interactive method for inverse kinematics that draws on the large set of fitted templates and allows for posing new expressions by dragging surface points directly. Finally, we describe new tools that model the dynamics in the input sequence to enable new animations, created via key-framing or texture-synthesis techniques.
Keyframe-based tracking for rotoscoping and animation
Authors: Agarwala Aseem , Hertzmann Aaron , Salesin David H. , Seitz Steven M.
Published: October 2004

We describe a new approach to rotoscoping --- the process of tracking contours in a video sequence --- that combines computer vision with user interaction. In order to track contours in video, the user specifies curves in two or more frames; these curves are used as keyframes by a computer-vision-based tracking algorithm. The user may interactively refine the curves and then restart the tracking algorithm. Combining computer vision with user interaction allows our system to track any sequence with significantly less effort than interpolation-based systems --- and with better reliability than "pure" computer vision systems. Our tracking algorithm is cast as a spacetime optimization problem that solves for time-varying curve shapes based on an input video sequence and user-specified constraints. We demonstrate our system with several rotoscoped examples. Additionally, we show how these rotoscoped contours can be used to help create cartoon animation by attaching user-drawn strokes to the tracked contours.
High-quality video view interpolation using a layered representation
Authors: Zitnick C. Lawrence , Kang Sing Bing , Uyttendaele Matthew , Winder Simon , Szeliski Richard
Published: October 2004

The ability to interactively control viewpoint while watching a video is an exciting application of image-based rendering. The goal of our work is to render dynamic scenes with interactive viewpoint control using a relatively small number of video cameras. In this paper, we show how high-quality video-based rendering of dynamic scenes can be accomplished using multiple synchronized video streams combined with novel image-based modeling and rendering algorithms. Once these video streams have been processed, we can synthesize any intermediate view between cameras at any time, with the potential for space-time manipulation.In our approach, we first use a novel color segmentation-based stereo algorithm to generate high-quality photoconsistent correspondences across all camera views. Mattes for areas near depth discontinuities are then automatically extracted to reduce artifacts during view synthesis. Finally, a novel temporal two-layer compressed representation that handles matting is developed for rendering at interactive rates.
Fair morse functions for extracting the topological structure of a surface mesh
Authors: Ni Xinlai , Garland Michael , Hart John C.
Published: October 2004

Morse theory reveals the topological structure of a shape based on the critical points of a real function over the shape. A poor choice of this real function can lead to a complex configuration of an unnecessarily high number of critical points. This paper solves a relaxed form of Laplace's equation to find a "fair" Morse function with a user-controlled number and configuration of critical points. When the number is minimal, the resulting Morse complex cuts the shape into a disk. Specifying additional critical points at surface features yields a base domain that better represents the geometry and shares the same topology as the original mesh, and can also cluster a mesh into approximately developable patches. We make Morse theory on meshes more robust with teflon saddles and flat edge collapses, and devise a new "intermediate value propagation" multigrid solver for finding fair Morse functions that runs in provably linear time.
An intuitive framework for real-time freeform modeling
Authors: Botsch Mario , Kobbelt Leif
Published: October 2004

We present a freeform modeling framework for unstructured triangle meshes which is based on constraint shape optimization. The goal is to simplify the user interaction even for quite complex freeform or multiresolution modifications. The user first sets various boundary constraints to define a custom tailored (abstract) basis function which is adjusted to a given design task. The actual modification is then controlled by moving one single 9-dof manipulator object. The technique can handle arbitrary support regions and piecewise boundary conditions with smoothness ranging continuously from
C
0
to
C
2
. To more naturally adapt the modification to the shape of the support region, the deformed surface can be tuned to bend with anisotropic stiffness. We are able to achieve real-time response in an interactive design session even for complex meshes by precomputing a set of scalar-valued basis functions that correspond to the degrees of freedom of the manipulator by which the user controls the modification.
Interactive modeling of topologically complex geometric detail
Authors: Peng Jianbo , Kristjansson Daniel , Zorin Denis
Published: October 2004

Volume textures aligned with a surface can be used to add topologically complex geometric detail to objects in an efficient way, while retaining an underlying simple surface structure.Adding a volume texture to a surface requires more than a conventional two-dimensional parameterization: a part of the space surrounding the surface has to be parameterized. Another problem with using volume textures for adding geometric detail is the difficulty in rendering implicitly represented surfaces, especially when they are changed interactively.In this paper we present algorithms for constructing and rendering volume-textured surfaces. We demonstrate a number of interactive operations that these algorithms enable.
Mesh editing with poisson-based gradient field manipulation
Authors: Yu Yizhou , Zhou Kun , Xu Dong , Shi Xiaohan , Bao Hujun , Guo Baining , Shum Heung-Yeung
Published: October 2004

In this paper, we introduce a novel approach to mesh editing with the Poisson equation as the theoretical foundation. The most distinctive feature of this approach is that it modifies the original mesh geometry implicitly through gradient field manipulation. Our approach can produce desirable and pleasing results for both global and local editing operations, such as deformation, object merging, and smoothing. With the help from a few novel interactive tools, these operations can be performed conveniently with a small amount of user interaction. Our technique has three key components, a basic mesh solver based on the Poisson equation, a gradient field manipulation scheme using local transforms, and a generalized boundary condition representation based on local frames. Experimental results indicate that our framework can outperform previous related mesh editing techniques.