In machine learning, data is usually represented in a (flat) Euclidean space where distances between points are along straight lines. Researchers have recently considered more exotic (non-Euclidean) Riemannian manifolds such as hyperbolic space which is well suited for tree-like data. In this paper, we propose a representation living on a pseudo-Riemannian manifold of constant nonzero curvature. It is a generalization of hyperbolic and spherical geometries where the non-degenerate metric tensor need not be positive definite. We provide the necessary learning tools in this geometry and extend gradient method optimization techniques. More specifically, we provide closed-form expressions for distances via geodesics and define a descent direction to minimize some objective function. Our novel framework is applied to graph representations.

Dynamic effects such as waves, splashes, fire, smoke, and explosions are an integral part of stylized animations. However, such dynamics are challenging to produce, as manually sketching key-frames requires significant effort and artistic expertise while physical simulation tools lack sufficient expressiveness and user control. We present an interactive interface for designing these elemental dynamics for animated illustrations. Users draw with coarse-scale energy brushes which serve as control gestures to drive detailed flow particles which represent local velocity fields. These fields can convey both realistic and artistic effects based on user specification. This painting metaphor for creating elemental dynamics simplifies the process, providing artistic control, and preserves the fluidity of sketching. Our system is fast, stable, and intuitive. An initial user evaluation shows that even novice users with no prior animation experience can create intriguing dynamics using our system.

In this article we derive an equation for the velocity of an arbitrary time-evolving implicit surface. Strictly speaking, only the normal component of the velocity is unambiguously defined. This is because an implicit surface does not have a unique parametrization. However, by enforcing a constraint on the evolution of the normal field we obtain a unique tangential component. We apply our formulas to surface tracking and to the problem of computing velocity vectors of a motion blurred blobby surface. Other possible applications are mentioned at the end of the article.

This paper presents a unified dynamics solver developed by the author which was first released in AutodeskTMMAYA 8.5. The solver however is a standalone library which could potentially be used in other applications. Current dynamics solvers are usually fine tuned for specific effects such as rigid bodies or cloth. Handling the interaction between these solvers is often problematic as one of them takes precedence over the others. In our Nucleus solver we model all matter as a simplicial complex: a generalization of a triangle mesh that also includes points, curves and solids. This allows interactions such as collisions between various elements of different dimensionality. The internal deformations such as stretch and bend are handled through constraints instead of springs. This makes the simulation more stable for stiff materials such as cloth. Through mutual interactions and constraints many interesting phenomena emerge automatically. The basic philosophy behind Nucleus is that complexity arises by combining simple constraints.

We describe a new interaction technique, called HoverCam, for navigating around 3D objects at close proximity. When a user is closely inspecting an object, the camera motions needed to move across its surface can become complex. For tasks such as 3D painting or modeling small detail features, users will often try to keep the camera a small distance above the surface. To achieve this automatically, HoverCam intelligently integrates tumbling, panning, and zooming camera controls into a single operation. This allows the user to focus on the task at hand instead of continuously managing the camera position and orientation. In this paper we show unique affordances of the technique and define the behavior and implementation of HoverCam. We also show how the technique can be used for navigating about data sets without well-defined surfaces such as point clouds and curves in space.

In computer graphics applications such as feature animation and games there is a need to produce convincing simulations of phenomena such as smoke, water, cloth and rigid bodies. Computational physics is the natural framework for such simulations. The physical equations describing most of these phenomena are well known and have been extensively studied over the last couple of centuries by the physics community. Which solution technique to use in practice depends on the application. In computer graphics it is desirable to have fast and stable simulations. Ideally, the simulations should run in realtime. This is important of course in games but also in movie production houses where animators have to fine tune the parameters of the simulation. On the other hand it is also desirable that these simulations are easy to implement. This makes the code easier to maintain in a commercial system. Our experience has been that good solutions very often result in simple algorithms which are relatively easy to code. This paper mainly focuses on the simulation of fluids such as smoke, water and fire. Our fluid solver which was first introduced in Stam (1999) relies on a spatial discretization of space into voxels. The physical quantities describing the fluid such as velocity and density are assumed to be constant in each voxel. These values are updated over each time step to create an animation of a fluid flow.

We describe a novel method for controlling physics-based fluid simulations through gradient-based nonlinear optimization. Using a technique known as the adjoint method , derivatives can be computed efficiently, even for large 3D simulations with millions of control parameters. In addition, we introduce the first method for the full control of free-surface liquids. We show how to compute adjoint derivatives through each step of the simulation, including the fast marching algorithm, and describe a new set of control parameters specifically designed for liquids.

Abstract In this paper we introduce a new subdivision operator that unifies triangular and quadrilateral subdivision schemes. Designers often want the added flexibility of having both quads and triangles in their models. It is also well known that triangle meshes generate poor limit surfaces when using a quad scheme, while quad‐only meshes behave poorly with triangular schemes. Our new scheme is a generalization of the well known Catmull‐Clark and Loop subdivision algorithms. We show that our surfaces are C 1 everywhere and provide a proof that it is impossible to construct such a C 2 scheme at the quad/triangle boundary. However, we provide rules that produce surfaces with bounded curvature at the regular quad/triangle boundary and provide optimal masks that minimize the curvature divergence elsewhere. We demonstrate the visual quality of our surfaces with several examples. ACM CSS: I.3.5 Computer Graphics— Curve, surface, solid, and object representations

In this paper we introduce a method to simulate fluid flows on smooth surfaces of arbitrary topology: an effect never seen before. We achieve this by combining a two-dimensional stable fluid solver with an atlas of parametrizations of a Catmull-Clark surface. The contributions of this paper are: (i) an extension of the Stable Fluids solver to arbitrary curvilinear coordinates, (ii) an elegant method to handle cross-patch boundary conditions and (iii) a set of new external forces custom tailored for surface flows. Our techniques can also be generalized to handle other types of processes on surfaces modeled by partial differential equations, such as reaction-diffusion. Some of our simulations allow a user to interactively place densities and apply forces to the surface, then watch their effects in real-time. We have also computed higher resolution animations of surface flows off-line.

We describe a method for controlling smoke simulations through user-specified keyframes. To achieve the desired behavior, a continuous quasi-Newton optimization solves for appropriate "wind" forces to be applied to the underlying velocity field throughout the simulation. The cornerstone of our approach is a method to efficiently compute exact derivatives through the steps of a fluid simulation. We formulate an objective function corresponding to how well a simulation matches the user's keyframes, and use the derivatives to solve for force parameters that minimize this function. For animations with several keyframes, we present a novel multiple-shooting approach. By splitting large problems into smaller overlapping subproblems, we greatly speed up the optimization process while avoiding certain local minima.

In this paper, we propose a new approach to numerical smoke simulation for computer graphics applications. The method proposed here exploits physics unique to smoke in order to design a numerical method that is both fast and efficient on the relatively coarse grids traditionally used in computer graphics applications (as compared to the much finer grids used in the computational fluid dynamics literature). We use the inviscid Euler equations in our model, since they are usually more appropriate for gas modeling and less computationally intensive than the viscous Navier-Stokes equations used by others. In addition, we introduce a physically consistent vorticity confinement term to model the small scale rolling features characteristic of smoke that are absent on most coarse grid simulations. Our model also correctly handles the inter-action of smoke with moving objects.

Subdivision rules have traditionally been designed to generate smooth surfaces from polygonal meshes. In this paper we propose to employ subdivision rules as a polygonal modeling tool, specifically to add additional level of detail to meshes. However, existing subdivision schemes have several undesirable properties making them ill suited for polygonal modeling. In this paper we propose a general set of subdivision rules which provides users with more control over the subdivision process. Most existing subdivision schemes are special cases. In particular, we provide subdivision rules which blend approximating spline based schemes with interpolatory ones. Also, we generalize subdivision to allow any number of refinements to be performed in a single step.

The reflection of light from surfaces is a fundamental problem in computer graphics. Although many reflection models have been proposed, few take into account the wave nature of light. In this paper, we derive a new class of reflection models for metallic surfaces that handle the effects of diffraction. Diffraction is a purely wave-like phenomenon and cannot be properly modeled using the ray theory of light alone. A common example of a surface which exhibits diffraction is the compact disk. A characteristic of such surfaces is that they reflect light in a very colorful manner. Our model is also a generalization of most reflection models encountered in computer graphics. In particular, we extend the He-Torrance model to handle anisotropic reflections. This is achieved by rederiving, in a more general setting, results from surface wave physics which were taken for granted by other researchers. Specifically, our use of Fourier analysis has enabled us to tackle the difficult task of analytically computing the Kirchhoff integral of surface scattering.

Building animation tools for fluid-like motions is an important and challenging problem with many applications in computer graphics.The use of physics-based models for fluid flow can greatly assist in creating such tools.Physical models, unlike key frame or procedural based techniques, permit an animator to almost effortlessly create interesting, swirling fluid-like behaviors.Also, the interaction of flows with objects and virtual forces is handled elegantly.Until recently, it was believed that physical fluid models were too expensive to allow real-time interaction.This was largely due to the fact that previous models used unstable schemes to solve the physical equations governing a fluid.In this paper, for the first time, we propose an unconditionally stable model which still produces complex fluid-like flows.As well, our method is very easy to implement.The stability of our model allows us to take larger time steps and therefore achieve faster simulations.We have used our model in conjuction with advecting solid textures to create many fluid-like animations interactively in two-and three-dimensions.

In this paper we disprove the belief widespread within the computer graphics community that Catmull-Clark subdivision surfaces cannot be evaluated directly without explicitly subdividing.We show that the surface and all its derivatives can be evaluated in terms of a set of eigenbasis functions which depend only on the subdivision scheme and we derive analytical expressions for these basis functions.In particular, on the regular part of the control mesh where Catmull-Clark surfaces are bi-cubic B-splines, the eigenbasis is equal to the power basis.Also, our technique is both easy to implement and efficient.We have used our implementation to compute high quality curvature plots of subdivision surfaces.The cost of our evaluation scheme is comparable to that of a bi-cubic spline.Therefore, our method allows many algorithms developed for parametric surfaces to be applied to Catmull-Clark subdivision surfaces.This makes subdivision surfaces an even more attractive tool for free-form surface modeling.

This paper addresses the problem of realistically simulating the motion of tree‐branches subjected to turbulence. Since the resulting motion is random in nature, we model it as a stochastic process. We synthesize this process directly by filtering a white noise in the Fourier domain. The filter is constructed by performing a modal analysis of the tree. We use a sophisticated numerical technique which is able to compute the first few significant modes of large trees. The main advantage of our technique over previous methods is that we are able to compute complicated motions without the necessity of integrating dynamical equations over time. Consequently, a user can view and manipulate tree‐motions in real‐time. Our technique can be further extended to other flexible structures such as two‐dimensional plates.

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...

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...