In this paper, we introduce a novel method for intelligently resizing a wide range of volumetric data including fluids. Fluid carving, the technique we build upon, only supported particle-based liquid data, and because it was based on image-based techniques, it was constrained to rectangular boundaries. We address these limitations to allow a much more versatile method for volumetric post-processing. By enclosing a region of interest in our lattice structure, users can retarget regions of a volume with non-rectangular boundaries and non-axis-aligned motion. Our approach generalizes to images, videos, liquids, meshes, and even previously unexplored domains such as fire and smoke. We also present a seam computation method that is significantly faster than the previous approach while maintaining the same level of quality, thus making our method more viable for production settings where post-processing workflows are vital.

We present a method for intelligently resizing fluid simulation data using seam carving methods. While advances in post-processing techniques have allowed artists greater control over content late in the production process, this technology has largely remained confined to image processing. Our fluid carving system allows fluid simulation post-processing by performing content-aware non-uniform scaling on baked-out fluid simulation data. Specifically, we extend video seam carving techniques to 4-dimensional animated fluid volume data with a graph cut energy function based on mean curvature and kinetic energy. To reduce the complexity of performing graph cuts on 4D data, we provide a new graph construction formulation that greatly reduces the run-time and memory consumption, which are otherwise prohibitively expensive. We demonstrate that our system is useful for post-production fluid simulation changes and editable fluid FX libraries.

An Eulerian approach to fluid flow provides an efficient, stable paradigm for realistic fluid simulation. However, its traditional reliance on a fixed-resolution grid is not ideal for simulations that simultaneously exhibit both large and small-scale fluid phenomena. Octree-based fluid simulation approaches have provided the needed adaptivity, but the inherent weakness of a pointer-based tree structure has limited their effectiveness. We present a linear octree structure that provides a significant runtime speedup using these octree-based simulation algorithms. As memory prices continue to decline, we leverage additional memory when compared to traditional octree structures to provide this improvement. In addition to reducing the level of indirection in the data, because our linear octree is stored contiguously in memory as a simple Carray rather than a recursive set of pointers, we provide a more cache-friendly data layout than a traditional octree. In our testing, our approach yielded run-times that were 1.5 to nearly 5 times faster than the same simulations running on a traditional octree implementation.

Recent crowd simulation algorithms do path planning on complex surfaces by breaking 3D surfaces into a series of 2.5D planes. This allows for path planning on surfaces that can be mapped from 3D to 2D without distortion, such as multistory buildings. However, the 2.5D approach does not handle path planning on curved surfaces such as spheres, asteroids, or insect colonies. Additionally, the 2.5D approach does not handle the complexity of dynamic obstacle avoidance when agents can walk on walls or ceilings. We propose novel path planning and obstacle avoidance algorithms that work on surfaces as a whole instead of breaking them into a 2.5D series of planes. Our "whole surfaceâ approach simulates crowds on both multistory structures and highly curved topologies without changing parameters. We validate our work on a suite of 30 different meshes, some with over 100,000 triangles, with crowds of 1,000 agents. Our algorithm always averaged more than 40 FPS with virtually no stalling.

We present a new technique for interactive terrain generation. This approach provides two improvements over existing teerrain generation systems. First, we introduce an improved midpoint displacement algorithm that allows for arbitrary vertex insertion order.

Cognitive and behavioral models have become popular methods for creating autonomous self‐animating characters. Creating these models present the following challenges: (1) creating a cognitive or behavioral model is a time‐intensive and complex process that must be done by an expert programmer and (2) the models are created to solve a specific problem in a given environment and because of their specific nature cannot be easily reused. Combining existing models together would allow an animator, without the need for a programmer, to create new characters in less time and to leverage each model's strengths, resulting in an increase in the character's performance and in the creation of new behaviors and animations. This article provides a framework that can aggregate existing behavioral and cognitive models into an ensemble. An animator has only to rate how appropriately a character performs in a set of scenarios and the system then uses machine learning to determine how the character should act given the current situation. Empirical results from multiple case studies validate the approach.

Rule-based deduplication utilizes expert domain knowledge to identify and remove duplicate data records. Achieving high accuracy in a rule-based system requires the creation of rules containing a good combination of discriminatory clues. Unfortunately, accurate rule-based deduplication often requires significant manual tuning of both the rules and the corresponding thresholds. This need for manual tuning reduces the efficacy of rule-based deduplication and its applicability to real-world data sets. No adequate solution exists for this problem. We propose a novel technique for rule-based deduplication. We apply individual deduplication rules, and combine the resultant match scores via learning-based information fusion. We show empirically that our fused deduplication technique achieves higher average accuracy than traditional rule-based deduplication. Further, our technique alleviates the need for manual tuning of the deduplication rules and corresponding thresholds.

Abstract Monte Carlo rendering algorithms generally rely on some form of importance sampling to evaluate the measurement equation. Most of these importance sampling methods only take local information into account, however, so the actual importance function used may not closely resemble the light distribution in the scene. In this paper, we present Table‐driven Adaptive Importance Sampling (TAIS), a sampling technique that augments existing importance functions with tabular importance maps that direct sampling towards undersampled regions of path space. The importance maps are constructed lazily, relying on information gathered during the course of sampling. During sampling the importance maps act either in parallel with or as a preprocess to existing importance sampling methods. We show that our adaptive importance maps can be effective at reducing variance in a number of rendering situations.

We present a novel technique for behavioral animation through data‐driven behavior synthesis. This technique has two key features: it provides natural character behavior and has a programming‐by‐demonstration interface. Thus we can quickly create compelling autonomous virtual agents that exhibit stylized behavior. First, the human user demonstrates behavior for the character by specifying its high‐level actions (e.g., with a joystick) during an interactive session. Each demonstration is recorded as a sequence of discrete actions. Later, the character synthesizes novel behavior by concatenating segments of action sequences. The choice of segments is guided by simulations that predict fitness. Thus our technique operates such as a cognitive model, providing a character with deliberative decision making. The actions are abstract and can be mapped to any pertinent motions, even procedurally synthesized motions. Thus our technique complements character animation algorithms. We empirically show that our O(logn) technique is scalable, robust when provided with sufficient data, produces effective behavior for a number of problem domains, and is faster than traditional planning. Also, the interface is intuitive enough that character behavior can be created by nontechnical users.

We present a fast 8-bit median filter implementation based on a separability argument. Our strategy is to start with a naive separable implementation of the median filter which displays O(1) time complexity per pixel, and then optimize this implementation to reduce the time constant. The optimizations that we employ include (a) lowering the histogram memory requirements by using unsigned shorts or bytes as histogram elements, (b) consolidating operations by performing multiple short additions with a single integer addition, (c) employing SSE instructions to further speed up the histogram updates, and (d) updating only the part of the histogram that contains the median. We show that by employing these rather straightforward optimizations, we can achieve filter speeds that approach the performance of the fastest proprietary median filters currently in use.

We present a new method for generating large numbers of accurate point correspondences between two wide baseline images. This is important for structure-from-motion algorithms, which rely on many correct matches to reduce error in the derived geometric structure. Given a small initial correspondence set we iteratively expand the set with nearby points exhibiting strong affine correlation, and then we constrain the set to an epipolar geometry using RANSAC. A key point to our algorithm is to allow a high error tolerance in the constraint, allowing the correspondence set to expand into many areas of an image before applying a lower error tolerance constraint. We show that this method successfully expands a small set of initial matches, and we demonstrate it on a variety of image pairs.

The ability for a given agent to adapt on-line to better interact with another agent is a difficult and important problem. This problem becomes even more difficult when the agent to interact with is a human, because humans learn quickly and behave nondeterministically. In this paper, we present a novel method whereby an agent can incrementally learn to predict the actions of another agent (even a human), and thereby can learn to better interact with that agent. We take a case-based approach, where the behavior of the other agent is learned in the form of state–action pairs. We generalize these cases either through continuous k-nearest neighbor, or a modified bounded minimax search. Through our case studies, our technique is empirically shown to require little storage, learn very quickly, and be fast and robust in practice. It can accurately predict actions several steps into the future. Our case studies include interactive virtual environments involving mixtures of synthetic agents and humans, with cooperative and/or competitive relationships.

We present Energy Redistribution (ER) sampling as an unbiased method to solve correlated integral problems. ER sampling is a hybrid algorithm that uses Metropolis sampling-like mutation strategies in a standard Monte Carlo integration setting, rather than resorting to an intermediate probability distribution step. In the context of global illumination, we present Energy Redistribution Path Tracing (ERPT). Beginning with an inital set of light samples taken from a path tracer, ERPT uses path mutations to redistribute the energy of the samples over the image plane to reduce variance. The result is a global illumination algorithm that is conceptually simpler than Metropolis Light Transport (MLT) while retaining its most powerful feature, path mutation. We compare images generated with the new technique to standard path tracing and MLT.

Adaptation (online learning) by autonomous virtual characters, due to interaction with a human user in a virtual environment, is a difficult and important problem in computer animation. In this article we present a novel multi-level technique for fast character adaptation. We specifically target environments where there is a cooperative or competitive relationship between the character and the human that interacts with that character.In our technique, a distinct learning method is applied to each layer of the character's behavioral or cognitive model. This allows us to efficiently leverage the character's observations and experiences in each layer. This also provides a convenient temporal distinction between what observations and experiences provide pertinent lessons for each layer. Thus the character can quickly and robustly learn how to better interact with any given unique human user, relying only on observations and natural performance feedback from the environment (no explicit feedback from the human). Our technique is designed to be general, and can be easily integrated into most existing behavioral animation systems. It is also fast and memory efficient.

Abstract Behavioral and cognitive modeling for virtual characters is a promising field. It significantly reduces the workload on the animator, allowing characters to act autonomously in a believable fashion. It also makes interactivity between humans and virtual characters more practical than ever before. In this paper we present a novel technique where an artificial neural network is used to approximate a cognitive model. This allows us to execute the model much more quickly, making cognitively empowered characters more practical for interactive applications. Through this approach, we can animate several thousand intelligent characters in real time on a PC. We also present a novel technique for how a virtual character, instead of using an explicit model supplied by the user, can automatically learn an unknown behavioral/cognitive model by itself through reinforcement learning. The ability to learn without an explicit model appears promising for helping behavioral and cognitive modeling become more broadly accepted and used in the computer graphics community, as it can further reduce the workload on the animator. Further, it provides solutions for problems that cannot easily be modeled explicitly. Copyright © 2004 John Wiley & Sons, Ltd.

Abstract We present a particle‐based algorithm for modeling highly viscous liquids. Using a numerical time‐integration of particle acceleration and velocity, we apply external forces to particles and use a convenient organization, the adhesion matrix, to represent forces between different types of liquids and objects. Viscosity is handled by performing a momentum exchange between particle pairs such that momentum is conserved. Volume is maintained by iteratively adjusting particle positions after each time step. We use a two‐tiered approach to time stepping that allows particle positions to be updated many times per frame while expensive operations, such as calculating viscosity and adhesion, are done only a few times per frame. The liquid is rendered using an implicit surface polygonization algorithm, and we present an implicit function that convolves the liquid surface with a Gaussian function, yielding a smooth liquid skin. Copyright © 2004 John Wiley & Sons, Ltd.

We present a technique to perform occlusion culling for hierarchical terrains at run-time. The algorithm is simple to implement and requires minimal pre-processing and additional storage, yet leads to 2-4 times improvement in framerate for views with high degrees of occlusion. Our method is based on the well-known occlusion horizon algorithm. We show how to adapt the algorithm for use with hierarchical terrains. The occlusion horizon is constructed as the terrain is traversed in an approximate front to back ordering. Regions of the terrain are compared to the horizon to determine when they are completely occluded from the viewpoint. Culling these regions leads to significant savings in rendering.

We present a new terrain decimation technique called a Quadtree Morph, or Q-morph. The new approach eliminates the usual popping artifacts associated with polygon reduction, replacing them with less objectionable smooth morphing. We show that Q-morphing is fast enough to create a view-dependent terrain model for each frame in an interactive environment. In contrast to most Geomorph algorithms, Q-morphing does not use a time step to interpolate between geometric configurations. Instead, the geometry motion in a Q-morph is based solely on the position of the viewer.

Large textures cause bottlenecks in real time applications that often lead to a loss of interactivity. These performance bottlenecks occur because of disk and network transfer, texture translation, and memory swapping. We present a software solution that alleviates the problems associated with large textures by treating texture as a bandwidth limited resource rather than a finite resource. As a result the display of large textures is reduced to a caching problem in which texture memory serves as the primary cache for texture data, main memory the secondary cache, and local disk the tertiary cache. By using this cache hierarchy, applications are able to maintain real time performance while displaying textures hundreds of times larger than can fit into texture memory.

Abstract Vectorfields have traditionally been used in computer graphics as a means of visualizing models over time. This paper presents a system which extends the use of vector fields as an interactive tool for physically based three dimensional particle systems and soft objects. The techniques implemented in the system provide the user with new flexibility in animation, modeling and simulation. This paper describes bounded interactive vectorfields and how they can be used to manipulate particle systems and a class of soft objects. Applications to animation, modeling and simulation are also presented.