Singing and speaking are two fundamental forms of human communication. From a modeling perspective however, speaking can be seen as a subset of singing. We present VOCAL, a system that automatically generates expressive, animator-centric lower face animation from singing audio input. Articulatory phonetics and voice instruction ascribe additional roles to vowels (projecting melody and volume) and consonants (lyrical clarity and rhythmic emphasis) in song. Our approach directly uses these insights to define axes for Melodic-accent and Pitch-sensitivity (Ma-Ps), which together provide an abstract space to visually represent various singing styles. In our system. vowels are processed first. A lyrical vowel is often sung tonally as one or more different vowels. We perform any such vowel modifications using a neural network trained on input audio. These vowels are then dilated from their spoken behaviour to bleed into each other based on Melodic-accent (Ma), with Pitch-sensitivity (Ps) modeling visual vibrato. Consonant animation curves are then layered in, with viseme intensity modeling rhythmic emphasis (inverse to Ma). Our evaluation is fourfold: we show the impact of our design parameters; we compare our results to ground truth and prior art; we present compelling results on a variety of voices and singing styles; and we validate these results with professional singers and animators.

The comprehensive visual modeling of fluid motion has historically been a challenging task, due in no small part to the difficulties inherent in geometries that are non-manifold, open, or thin. Modern geometric cut-cell mesh generators have been shown to produce, both robustly and quickly, workable volumetric elements in the presence of these problematic geometries, and the resulting volumetric representation would seem to offer an ideal infrastructure with which to perform fluid simulations. However, cut-cell mesh elements are general polyhedra that often contain holes and are non-convex; it is therefore difficult to construct the explicit function spaces required to employ standard functional discretizations, such as the Finite Element Method. The Virtual Element Method (VEM) has recently emerged as a functional discretization that successfully operates with complex polyhedral elements through a weak formulation of its function spaces. We present a novel cut-cell fluid simulation framework that exactly represents boundary geometry during the simulation. Our approach enables, for the first time, detailed fluid simulation with "in-the-wild" obstacles, including ones that contain non-manifold parts, self-intersections, and extremely thin features. Our key technical contribution is the generalization of the Particle-In-Cell fluid simulation methodology to arbitrary polyhedra using VEM. Coupled with a robust cut-cell generation scheme, this produces a fluid simulation algorithm that can operate on previously infeasible geometries without requiring any additional mesh modification or repair.

Although geometry arising "in the wild" most often comes in the form of a surface representation, a plethora of geometrical and physical applications require the construction of volumetric embeddings either of the geometry itself or the domain surrounding it. Cartesian cut-cell-based mesh generation provides an attractive solution in which volumetric elements are constructed from the intersection of the input surface geometry with a uniform or adaptive hexahedral grid. This choice, especially common in computational fluid dynamics, has the potential to efficiently generate accurate, surface-conforming cells; unfortunately, current solutions are often slow, fragile, or cannot handle many common topological situations. We therefore propose a novel, robust cut-cell construction technique for triangle surface meshes that explicitly computes the precise geometry of the intersection cells, even on meshes that are open or non-manifold. Its fundamental geometric primitive is the intersection of an arbitrary segment with an axis-aligned plane. Beginning from the set of intersection points between triangle mesh edges and grid planes, our bottom-up approach robustly determines cut-edges, cut-faces, and finally cut-cells, in a manner designed to guarantee topological correctness. We demonstrate its effectiveness and speed on a wide range of input meshes and grid resolutions, and make the code available as open source.

Abstract Motion capture is often retargeted to new, and sometimes drastically different, characters. When the characters take on realistic human shapes, however, we become more sensitive to the motion looking right. This means adapting it to be consistent with the physical constraints imposed by different body shapes. We show how to take realistic 3D human shapes, approximate them using a simplified representation, and animate them so that they move realistically using physically‐based retargeting. We develop a novel spacetime optimization approach that learns and robustly adapts physical controllers to new bodies and constraints. The approach automatically adapts the motion of the mocap subject to the body shape of a target subject. This motion respects the physical properties of the new body and every body shape results in a different and appropriate movement. This makes it easy to create a varied set of motions from a single mocap sequence by simply varying the characters. In an interactive environment, successful retargeting requires adapting the motion to unexpected external forces. We achieve robustness to such forces using a novel LQR‐tree formulation. We show that the simulated motions look appropriate to each character's anatomy and their actions are robust to perturbations.

Determining effective control strategies and solutions for high-degree-of-freedom humanoid characters has been a difficult, ongoing problem. A controller is only valid for a subset of the states of the character, known as the domain of attraction (DOA). This article shows how many states that are initially outside the DOA can be brought inside it. Our first contribution is to show how DOA expansion can be performed for a high-dimensional simulated character. Our second contribution is to present an algorithm that efficiently increases the DOA using random trees that provide denser coverage than the trees produced by typical sampling-based motion-planning algorithms. The trees are constructed offline but can be queried fast enough for near-real-time control. We show the effect of DOA expansion on getting up, crouch-to-stand, jumping, and standing-twist controllers. We also show how DOA expansion can be used to connect controllers together.

The rich signals we extract from facial expressions imposes high expectations for the science and art of facial animation. While the advent of high-resolution performance capture has greatly improved realism, the utility of procedural animation warrants a prominent place in facial animation workflow. We present a system that, given an input audio soundtrack and speech transcript, automatically generates expressive lip-synchronized facial animation that is amenable to further artistic refinement, and that is comparable with both performance capture and professional animator output. Because of the diversity of ways we produce sound, the mapping from phonemes to visual depictions as visemes is many-valued. We draw from psycholinguistics to capture this variation using two visually distinct anatomical actions: Ja w and L ip, wheresound is primarily controlled by jaw articulation and lower-face muscles, respectively. We describe the construction of a transferable template jali 3D facial rig, built upon the popular facial muscle action unit representation facs. We show that acoustic properties in a speech signal map naturally to the dynamic degree of jaw and lip in visual speech. We provide an array of compelling animation clips, compare against performance capture and existing procedural animation, and report on a brief user study.

Abstract Synthesizing controllers for rotational movements in feature space is an open research problem and is particularly challenging because of the need to precisely regulate the character's global orientation, angular momentum and inertia. This paper presents feature‐based controllers for a wide variety of rotational movements, including cartwheels, dives and flips. We show that the controllers can be made robust to large external disturbances by using a time‐invariant control scheme. The generality of the control laws is demonstrated by providing examples of the flip controller with different apexes, the diving controller with different heights and styles, the cartwheel controller with different speeds and straddle widths, etc. The controllers do not rely on any input motion or offline optimization.

Sampling a scene by tracing rays and reconstructing an image from such pointwise samples is fundamental to computer graphics. To improve the efficacy of these computations, we propose an alternative theory of sampling. In contrast to traditional formulations for image synthesis, which appeal to nonconstructive Dirac deltas, our theory employs constructive reproducing kernels for the correspondence between continuous functions and pointwise samples. Conceptually, this allows us to obtain a common mathematical formulation of almost all existing numerical techniques for image synthesis. Practically, it enables novel sampling based numerical techniques designed for light transport that provide considerably improved performance per sample. We exemplify the practical benefits of our formulation with three applications: pointwise transport of color spectra, projection of the light energy density into spherical harmonics, and approximation of the shading equation from a photon map. Experimental results verify the utility of our sampling formulation, with lower numerical error rates and enhanced visual quality compared to existing techniques.

We present a sparse analytic representation for spherical functions, including those expressed in a Spherical Harmonic (SH) expansion, that is amenable to fast and accurate rotation on the GPU. Exploiting the fact that each band- l SH basis function can be expressed as a weighted sum of 2 l + 1 rotated band- l Zonal Harmonic (ZH) lobes, we develop a factorization that significantly reduces this number. We investigate approaches for promoting sparsity in the change-of-basis matrix, and also introduce lobe sharing to reduce the total number of unique lobe directions used for an order- N expansion from N 2 to 2 N -1. Our representation does not introduce approximation error, is suitable for any type of spherical function (e.g., lighting or transfer), and requires no offline fitting procedure; only a (sparse) matrix multiplication is required to map to/from SH. We provide code for our rotation algorithms, and apply them to several real-time rendering applications.

We present an algorithm for the simulation of incompressible fluid phenomena that is computationally efficient and leads to visually convincing simulations with far fewer degrees of freedom than existing approaches. Rather than using an Eulerian grid or Lagrangian elements, we represent vorticity and velocity using a basis of global functions defined over the entire simulation domain. We show that choosing Laplacian eigenfunctions for this basis provides benefits, including correspondence with spatial scales of vorticity and precise energy control at each scale. We perform Galerkin projection of the Navier-Stokes equations to derive a time evolution equation in the space of basis coefficients. Our method admits closed-form solutions on simple domains but can also be implemented efficiently on arbitrary meshes.

Abstract Light transport is often characterized within a high‐dimensional space although practitioners have long known that it commonly behaves as a much lower‐dimensional phenomenon. We study theeffective dimensionof light transport over a neighborhood on the scene manifold and show that under plausible assumptions the dimensionality is characterized by the spectrum of the spatio‐spectral concentration problem. This allows us to improve existing estimates for the dimension in computer graphics using a more insightful derivation and for the first time we obtain optimal representations. The relevance of our results for existing rendering applications is discussed.

Abstract We present a real‐time relighting and shadowing method for dynamic scenes with varying lighting, view and BRDFs. Our approach is based on a compact representation of reflectance data that allows for changing the BRDF at run‐time and a data‐driven method for accurately synthesizing self‐shadows on articulated and deformable geometries. Unlike previous self‐shadowing approaches, we do not rely on local blocking heuristics. We do not fit a model to the BRDF‐weighted visibility, but rather only to the visibility that changes during animation. In this manner, our model is more compact than previous techniques and requires less computation both during fitting and at run‐time. Our reflectance product operators can re‐integrate arbitrary low‐frequency view‐dependent BRDF effects on‐the‐fly and are compatible with all previous dynamic visibility generation techniques as well as our own data‐driven visibility model. We apply our reflectance product operators to three different visibility generation models, and our data‐driven model can achieve framerates well over 300Hz.

We propose the SOHO wavelet basis—the first spherical Haar wavelet basis that is both orthogonal and symmetric, making it particularly well suited for the approximation and processing of all-frequency signals on the sphere. We obtain the basis with a novel spherical subdivision scheme that defines a partition acting as the domain of the basis functions. Our construction refutes earlier claims doubting the existence of a basis that is both orthogonal and symmetric. Experimental results for the representation of spherical signals verify that the superior theoretical properties of the SOHO wavelet basis are also relevant in practice.

There are many challenges associated with the integration of synthetic and real imagery. One particularly difficult problem is the automatic extraction of salient parameters of natural phenomena in real video footage for subsequent application to synthetic objects. We can ensure that the hair and clothing of a synthetic actor placed in a meadow of swaying grass will move consistently with the wind that moved that grass. The video footage can be seen as a controller for the motion of synthetic features, a concept we call video input driven animation (VIDA). We propose a schema that analyzes an input video sequence, extracts parameters from the motion of objects in the video, and uses this information to drive the motion of synthetic objects. To validate the principles of VIDA, we approximate the inverse problem to harmonic oscillation, which we use to extract parameters of wind and of regular water waves. We observe the effect of wind on a tree in a video, estimate wind speed parameters from its motion, and then use this to make synthetic objects move. We also extract water elevation parameters from the observed motion of boats and apply the resulting water waves to synthetic boats.

In this paper, we propose efficient numerical techniques for Butterworth filtering and implicit fairing of large irregular triangle meshes, where the corresponding filters are rational polynomials and the resulting large linear systems need to be solved iteratively. We show that significant speed-up can be achieved for Butterworth filtering by factorizing the linear system in the complex domain. As for implicit fairing, with our estimate of the optimal extrapolation parameter /spl omega/, successive overrelaxation (SOR) offers great improvements, both in speed and space usage, over the more familiar conjugate gradient type solvers.

In this paper, we develop a simple, eigenspace matching algorithm for closed 3D contours. Our algorithm relies on a novel method which normalizes the Fourier descriptors (FDs) of a 3D contour with respect to two of its FD coefficients corresponding to the lowest non-zero frequencies. The remaining matching task only involves vertex shift and rotation about the z-axis. Our approach is inspired by the observation that the traditional Fourier transform of a 1D signal is equivalent to the decomposition of the signal into a linear combination of the eigenvectors of a smoothing operator. It turns out that our FD normalization is equivalent to aligning the limit plane approached by the sequence of progressively smoothed 3D contours with the xy-plane.

Many key problems in computer graphics require the computation of integrals. Due to the nature of the integrand and of the domain of integration, these integrals seldom can be computed analytically. As a result, numerical techniques are used to find approximate solutions to these problems. While the numerical analysis literature offers many integration techniques, the choice of which method to use for specific computer graphic problems is a difficult one. This choice must be driven by the numerical efficiency of the method, and ultimately, by its visual impact on the computed image. In this paper, we begin to address these issues by methodically analyzing deterministic and stochastic numerical techniques and their application to the type of one-dimensional problems that occur in computer graphics, especially in the context of linear light source integration. In addition to traditional methods such as Gauss-Legendre quadratures, we also examine Voronoi diagram-based sampling, jittered quadratures, random offset quadratures, weighted Monte Carlo, and a newly introduced method of compounding known as a difficulty driven compound quadrature .We compare the effectiveness of these methods using a three-pronged approach. First, we compare the frequency domain characteristics of all the methods using periodograms. Next, applying ideas found in the numerical analysis literature, we examine the numerical and visual performance profiles of these methods for seven different one-parameter problem families. We then present results from the application of the methods for the example of linear light sources. Finally, we summarize the relative effectiveness of the methods surveyed, showing the potential power of difficulty-driven compound quadratures.

We propose the use of interactive, user-in-the-loop techniques for controlling physically-based animated characters. With a suitably designed interface, the continuous and discrete input actions afforded by a standard mouse and keyboard allow for the creation of a broad range of motions. We apply our techniques to interactively control planar dynamic simulations of a bounding cat, a gymnastic desk lamp, and a human character capable of walking, running, climbing, and various gymnastic behaviors. The interactive control techniques allows a performer's intuition and knowledge about motion planning to be readily exploited. Video games are the current target application of this work.

Alain Fournier, 1943-2000 An Appreciation There are thinkers of great repute and intellect who would suggest that any objective measure of humankind is in fact a mismeasure. While I am not of a mood to argue the general point either way, it certainly applies to Alain Fournier. I write this appreciation of him so that those who do not know him may be inspired to discover him, and so that those who do know him are able to reflect further on his remarkable life. I beg the reader to indulge me in a rather personal reverie, for it is not possible to have known Alain without having a deep personal response to him. Allow me to recount very briefly Alain's accomplishments. His early training was in chemistry. After emigrating from France to Canada in the 1970's, he co-wrote a textbook on the topic, and he taught pre-college chemistry in Quebec. His career in computer graphics spanned only about 20 years. He received a Ph.D. in computer science at the University of Texas at Dallas, and reported the results of his Ph.D. work on stochastic modelling in a seminal paper in 1980 with Don Fussell and Loren Carpenter. He then went on to an outstanding academic career first at the University of Toronto and subsequently at the University of British Columbia. >From the outset he played on the international stage, especially in Europe and in North America. He has contributed to ACM-TOG as an author, as co-Guest Editor of a special issue (1987), and he was an Associate Editor from 1990-1992. Alain's early contributions to computer graphics on the modelling of natural phenomena were brilliant in themselves, but perhaps more importantly they advocated a methodology that required validation against real visual phenomena. This set the bar at the right level scientifically. His approach, which he once called "impressionistic graphics" both revolutionised the field and drove it forward. Perhaps the best example of this work is his beautiful paper on the depiction of ocean waves with Bill Reeves. His subsequent work on illumination models, light transport, rendering, and sampling and filtering is remarkable for its far-sightedness and depth. His theoretical work in computer graphics and computational geometry made us think about the limits of both fields. Alain's approach to solving problems was at once courageous and rational. Were he to ask himself (as I'm sure he did) for a response to T.S. Eliot's musing, I'm sure his answer would be his inimitable "Piece of cake! OK kiddos, here's what we'll do." And he would rush forward, leaving us to linger happily in his slipstream. Endlessly resourceful and tirelessly innovative, he would mould ideas of amazing insight into work that also inspired others, often much later, to take up the challenge. If C.P. Snow were ever in need of a prototypical person to bridge the "Two Cultures" of Science and Art, Alain would be it. He was blessed with an irrepressible enthusiasm to communicate his understanding and his curiosity about the universe, and he did so in whatever language was most appropriate. He wrote wonderful mathematics, algorithms, prose and poetry. His vocabulary in English and in French was gently intimidating, for even in intimidation he was benevolent. It seemed that his intellect was able to synthesise everything he ever learned. He would routinely interject a Latin "bon mot" into the papers we were writing or practise writing Kanji on the napkins on which we were doing research. We rarely did research in an office. How I miss those days. His art served him as innately and intuitively as did his science. He wrote exquisite poetry that was both challenging and tender. One day I hope that his work will be more available to the general public. I also hope that Alain's accomplishments will in time be formally recognised by the wider computer graphics community. Alain's wit, his innate "jeu d'esprit", was legend. His fondness for good jokes, especially Groucho Marx gags, allowed some but not all of us to overlook his weakness for Jerry Lewis. There are few on this earth who have been blessed with a wider array of talents, and fewer still who had more to say and more to contribute than Alain. And yet, Alain had a sensibility that is common to scientists and artists who have done many great things in their lives: apart from a lovely retrospective paper he wrote for Graphics Interface in 1994, he did not look back sympathetically on his work to derive satisfaction from his accomplishments. He was rooted in the present, and he suffered from the belief that he was only as good as his last project. In the end he may well have believed in Eliot's sentiment: I have heard the mermaids singing, each to each. I do not think that they will sing to me. Oh, but they have always sung to you, Alain. It was just that the melody was lost amid the clamour of disease. Alain did not separate the personal and professional. His were passions that required no qualifying adjective. He loved those close to him with an abandon and devotion that that was disarming and humbling. Anyone who knew him knew that he was extraordinarily close to his wife and his daughter. They were his greatest joys, his most provocative muses. They were the foundation upon which he built his life. Leonard Cohen, among others, said that you can't let the facts get in the way of the truth. The facts are that Alain Fournier, a great innovator in our field, died of lymphoma in the early hours of 14 August, 2000, and is survived by his daughter Ariel, his wife Adrienne, and a legion of admirers. The truth is that the sun seems to shine less brightly now that he is not among us. The truth is that he has broadened the minds and moved the hearts of many people around the world. To those who have never known Alain, I express particular sympathy, for there are few people we encounter in life with the ability to make us better than we thought we could be. Such, in truth and in fact, is the measure of this man. It was difficult not to love Alain. With such a beguiling package of brilliance and benevolent eccentricity, it was simply a matter of time and a question of degree. A unique and wonderful person has left us. Requiescat in pace, my friend. --Eugene Fiume, November 2000. (The quotations from T.S. Eliot are taken from his poem, "The Love Song of J. Alfred Prufrock".)

Finding effective interactive deformation techniques for complex geometric objects continues to be a challenging problem in modeling and animation.We present an approach that is inspired by armatures used by sculptors, in which wire curves give definition to an object and shape its deformable features.We also introduce domain curves that define the domain of deformation about an object.A wire together with a collection of domain curves provide a new basis for an implicit modeling primitive.Wires directly reflect object geometry, and as such they provide a coarse geometric representation of an object that can be created through sketching.Furthermore, the aggregate deformation from several wires is easy to define.We show that a single wire is an appealing direct manipulation deformation technique; we demonstrate that the combination of wires and domain curves provide a new way to outline the shape of an implicit volume in space; and we describe techniques for the aggregation of deformations resulting from multiple wires, domain curves and their interaction with each other and other deformation techniques.The power of our approach is illustrated using applications of animating figures with flexible articulations, modeling wrinkled surfaces and stitching geometry together.

Seemingly simple behaviors such as human walking are difficult to model because of their inherent instability.Kinematic animation techniques can freely ignore such intrinsically dynamic problems, but they therefore also miss modeling important motion characteristics.On the other hand, the effect of balancing can emerge in a physically-based animation, but it requires computing delicate control strategies.We propose an alternative method that adds closedloop feedback to open-loop periodic motions.We then apply our technique to create robust walking gaits for a fully-dynamic 19 degree-of-freedom human model.Important global characteristics such as direction, speed and stride rate can be controlled by changing the open-loop behavior alone or through simple control parameters, while continuing to employ the same local stabilization technique.Among other features, our dynamic "human" walking character is thus able to follow desired paths specified by the animator.

A definitive understanding of irradiance behavior in penumbral regions has been hard to come by, mainly due to the computational expense of determining the visible parts of an area light source. Consequently, sampling strategies have been mostly ad hoc, and evaluation of the resulting approximations has been difficult. In this paper, the structure of penumbral irradiance is investigated empirically and numerically. This study has been made feasible by the use of the discontinuity mesh and the backprojection, an efficient data structure representing visibility in regions of partial occlusion. Regions of penumbrae in which irradiance varies nonmonotonically are characterized empirically, and numerical tests are performed to determine the frequency of their occurrence. This study inspired the development of two algorithms for the construction of interpolating approximations to irradiance: one algorithm reduces the number of edges in the mesh defining the interpolant domain; and the other algorithm chooses among linear, quadratic, and mixed interpolants based on irradiance monotonicity. Results from numerical tests and images are presented that demonstrate good performance of the new algorithms for various realistic test configurations.

Developing a visually convincing model of fire, smoke, and other gaseousphenomena is among the most difficult and attractive problems in computer graphics. We have created new methods of animating a wide range of gaseous phenomena, including the particularly subtle problem of modelling "wispy" smoke and steam, using far fewer primitives than before. One significant innovation is the reformulation and solution of the advection-diffusion equation for densities composed of "warped blobs". These blobs more accurately model the distortions that gases undergo when advected by wind fields. We also introduce a simple model for the flame of a fire and its spread. Lastly, we present an efficient formulation and implementation of global illumination in the presence of gases and fire. Our models are specifically designed to permit a significant degree of user control over the evolution of gaseous phenomena. Keywords: fire, smoke, gaseous phenomena, diffusion, advection, warped blobbies, light tra...

Abstract The main preoccupations of research in computer‐aided geometric design have been on shape‐specification techniques for polynomial curves and surfaces, and on the continuity between segments or patches. When modelling with such techniques, curves and surfaces can be compressed or expanded arbitrarily. There has been relatively little work on interacting with direct spatial properties of curves and surfaces, such as their arc length or surface area. As a first step, we derive families of parametric piecewise polynomial curves that satisfy various positional and tangential constraints together with arc‐length constraints. We call these curves isometric curves. A space curve is defined as a sequence of polynomial curve segments, each of which is defined by the familiar Hermite or Bézier constraints for cubic polynomials; as well, each segment is constrained to have a specified arc length. We demonstrate that this class of curves is attractive and stable. We also describe the numerical techniques used that are sufficient for achieving real time interaction with these curves on low‐end workstations.

The fast identification of shadow regions due to area light sources is necessary for realistic rendering and for discontinuity meshing for global illumination. A new shadow-determination algorithm is presented that uses a data structure, called a backprojection, to represent the visible portion of a light source from any point in the scene. A complete discontinuity meshing algorithm is described for polyhedral scenes and area light sources, which includes an important class of light/geometry interactions that have not been implemented before. A fast incremental algorithm for computing backprojections is also described. The use of spatial subdivision, and heuristics based on computed statistics of typical scenes, results in efficient mesh and backprojection computation. Results of the implementation show that the use of the backprojection and discontinuity meshing permits accelerated high-quality rendering of shadows using both ray-casting and polygon-rendering with interpolants.

The realistic depiction of smoke, steam, mist and water reacting to a turbulent field such as wind is an attractive and challenging problem. Its solution requires interlocking models for turbulent fields, gaseous flow, and realistic illumination. We present a model for turbulent wind flow having a deterministic component to specify large-scale behaviour, and a stochastic component to model turbulent small-scale behaviour. The small-scale component is generated using space-time Fourier synthesis. Turbulent wind fields can be superposed interactively to create subtle behaviour. An advection-diffusion model is used to animate particle-based gaseous phenomena embedded in a wind field, and we derive an efficient physically-based illumination model for rendering the system. Because the number of particles can be quite large, we present a clustering algorithm for efficient animation and rendering. CR Categories and Subject Descriptors: I.3.7 [Com- puter Graphics]: Three-Dimensional Graphics...

Abstract The study of common classes of diffuse emitters, such as planar convex polygons, reveals several interesting properties of the functions of illumination these emitters cast on receiver surfaces. Some properties, such as the position of the maximum and the curvature are of particular interest for sampling and reconstruction of illumination across receivers. A computationally efficient approach is presented that identifies these properties, and uses them to select samples of illurnination. In addition these properties are used to determine upper bounds on the error due to linear and quadratic interpolants. These bounds are then used to adaptively subdivide the non‐uniform sampling grid, resulting in accurate reconstruction. Results show that the method reduces the error compared to uniform approaches, and produces more consistent animated sequences.

No abstract available.

A prevailing trend in computer graphics is the demand for increasingly realistic global illumination models and algorithms. Despite the fact that the computational power of uniprocessors is increasing, it is clear that much greater computational power is required to achieve satisfactory throughput. The obvious next step is to employ parallel processing. The advent of affordable, tightly-coupled multiprocessors makes such an approach widely available for the first time. We propose a tightly-coupled parallel decomposition of FIAT, a global illumination algorithm, based on space subdivision and power balancing, that we have recently developed. This algorithm is somewhat ambitious, and severely strains existing uniprocessor environments. We discuss techniques for reducing memory contention and maximising parallelism. We also present empirical data on the actual performance of our parallel solution. Since the model of parallel computation that we have employed is likely to persist for quite some time, our techniques are applicable to other algorithms based on space subdivision.

The use of physically-based techniques for computer animation can result in realistic object motion. The price paid for physically-based motion synthesis lies in increased computation and information requirements.1 We introduce a new approach to realistic motion specification based on state-space controllers. A user specifies a motion by defining a goal in terms of a set of destination states. A state-space controller is then constructed, which provides an optimal-control solution that guides the object from an arbitrary starting configuration to a goal. Motions are optimized with respect to time and control energy. Becasue controllers are specified in terms of destination states only, it is easy to reuse the same controller to produce different motions (from different starting states), or to create a complex sequence of motions by concatenating several controllers. An implementation of state-space controllers is presented, in which realistic motions can be produced in real time. Several examples will be considered.

Formal specification has long been advocated in programming methodology, and is becoming increasingly popular in computer graphics to characterise the semantics of components of graphics systems. Unfortunately, formal specifications tend to sacrifice realism for abstraction. The result is often a specification that is not as relevant to real graphics systems as it could be. This paper suggests that the use of sharper mathematical tools, together with the use of object orientation (i.e., data abstraction with inheritance) provides a way of resolving this problem. As an example, we attempt to specify formally classes of bitmaps and images. These are particularly interesting choices, for bitmaps and images are mutable, bitmaps can have a perceived effect on images, and their semantics depends on context.

This paper presents an interactive system for motion control that emphasizes object interaction. The fundamental mechanism provided to support interaction between objects is the field. We present a new technique called dynamic splines which dynamically generates a trajectory under field control. Dynamic splines mimic the kinematic behaviour of a particle moving in a field, yet, it is computationally inexpensive compared to full physical dynamic approaches. We also show how to extend the field approach to specify tracking behaviour.

A new class of geometric mappings is introduced to computer graphics, and the utility of this class is illustrated by applying it to texture mapping. When mapping a texture onto a surface such as a polygon, the entire texture can rarely be mapped without some clipping or non-linear transformation. Is it possible to map a texture bijectively to an arbitrary polygon such that the entire texture is mapped? This paper presents a solution to this problem. A new class of mapping techniques based on conformal mapping is proposed. The technique allows one to construct a continuous, bijective map from a polygonal texture space (e.g., a square) to an arbitrary convex polygon. The resulting map is texture-independent. The theory and .an implementation of conformal texture mapping is discussed, and several simple filtering techniques to support it are outlined. Conformal mapping extends the range of geometric mapping techniques, and is pertinent to many areas of computer graphics. Other examples of the potential utility of conformal mappings are also discussed.

Object orientation and concurrency are inherent to computer animation. Since the pieces of an animation can come from various media such as computer-generated imagery, video, and sound, the case for object orientation is all the stronger. However, languages for expressing the temporal co-ordination of animated objects have been slow in coming. We present such a language in this paper. Since the movements that an animated object can perform are also encapsulated as objects in our system, the scripting language can also be used to specify motion co-ordination. Such \u2018 motion objects\u201d can be applied to any animated object. The syntax, semantics, and implementation of this language will be described, and we shall show how to specify device-independent computer animation.

Most object-oriented systems lack two useful facilities: the ability of objects to migrate to new environments and the ability of objects to acquire new operations dynamically. This paper proposes Knos, an object-oriented environment that supports these actions. Knos' operations, data structures, and communication mechanisms are discussed. Knos objects “learn” by exporting and importing new or modified operations. The use of such objects as intellectual support tools is outlined. In particular, various applications involving cooperation, negotiation, and apprenticeship among objects are described.

Popular approaches to speeding up scan conversion often employ parallel processing. Recently, several special-purpose parallel architectures have been suggested. We propose an alternative to these systems: the general-purpose ultracomputer, a parallel processor with many autonomous processing elements and a shared memory. The “serial semantics/parallel execution” feature of this architecture is exploited in the formulation of a scan conversion algorithm. Hidden surfaces are removed using a single scanline, z-buffer algorithm. Since exact anti-aliasing is inherently slow, a novel parallel anti-aliasing algorithm is presented in which subpixel coverage by edges is approximated using a look-up table. The ultimate intensity of a pixel is the weighted sum of the intensity contribution of the closest edge, that of the “losing” edges, and that of the background. The algorithm is fast and accurate, it is attractive even in a serial environment, and it avoids several artifacts that commonly occur in animated sequences.

An innovative design for an interactive paint program has been developed based on multiple processes and message passing. Traditional paint programs combine interrupt-driven support of a graphical input device, such as a mouse or tablet, with the coloring of pixels in a raster display. We advocate a different design methodology which is illustrated in our implementation. The multiple processes and message passing primitives provided by some real-time operating systems encourage the design of parallel-program architectures and anthropomorphic programming structures, analogous to artist procedures and the metaphors of Smalltalk.