Full Papers 2009 - CGF 28-Issue 2
Permanent URI for this collection
Browse
Browsing Full Papers 2009 - CGF 28-Issue 2 by Issue Date
Now showing 1 - 20 of 57
Results Per Page
Sort Options
Item Complex Barycentric Coordinates with Applications to Planar Shape Deformation(The Eurographics Association and Blackwell Publishing Ltd, 2009) Weber, Ofir; Ben-Chen, Mirela; Gotsman, CraigItem Scalable real-time animation of rivers(The Eurographics Association and Blackwell Publishing Ltd, 2009) Yu, Qizhi; Neyret, Fabrice; Bruneton, Eric; Holzschuch, NicolasMany recent games and applications target the interactive exploration of realistic large scale worlds. These worlds consist mostly of static terrain models, as the simulation of animated fluids in these virtual worlds is computationally expensive. Adding flowing fluids, such as rivers, to these virtual worlds would greatly enhance their realism, but causes specific issues: as the user is usually observing the world at close range, small scale details such as waves and ripples are important. However, the large scale of the world makes classical methods impractical for simulating these effects. In this paper, we present an algorithm for the interactive simulation of realistic flowing fluids in large virtual worlds. Our method relies on two key contributions: the local computation of the velocity field of a steady flow given boundary conditions, and the advection of small scale details on a fluid, following the velocity field, and uniformly sampled in screen space.Item Implicit Contact Handling for Deformable Objects(The Eurographics Association and Blackwell Publishing Ltd, 2009) Otaduy, Miguel A.; Tamstorf, Rasmus; Steinemann, Denis; Gross, MarkusWe present an algorithm for robust and efficient contact handling of deformable objects. By being aware of the internal dynamics of the colliding objects, our algorithm provides smooth rolling and sliding, stable stacking, robust impact handling, and seamless coupling of heterogeneous objects, all in a unified manner. We achieve dynamicsawareness through a constrained dynamics formulation with implicit complementarity constraints, and we present two major contributions that enable an efficient solution of the constrained dynamics problem: a time stepping algorithm that robustly ensures non-penetration and progressively refines the formulation of constrained dynamics, and a new solver for large mixed linear complementarity problems, based on iterative constraint anticipation. We show the application of our algorithm in challenging scenarios such as multi-layered cloth moving at high velocities, or colliding deformable solids simulated with large time steps.Item Color correction for tone mapping(The Eurographics Association and Blackwell Publishing Ltd, 2009) Mantiuk, R.; Mantiuk, R.; Tomaszewska, A.; Heidrich, W.Tone mapping algorithms offer sophisticated methods for mapping a real-world luminance range to the luminance range of the output medium but they often cause changes in color appearance. In this work we conduct a series of subjective appearance matching experiments to measure the change in image colorfulness after contrast compression and enhancement. The results indicate that the relation between contrast compression and the color saturation correction that matches color appearance is non-linear and smaller color correction is required for small change of contrast. We demonstrate that the relation cannot be fully explained by color appearance models. We propose color correction formulas that can be used with existing tone mapping algorithms. We extend existing global and local tone mapping operators and show that the proposed color correction formulas can preserve original image colors after tone scale manipulation.Item Arches: a Framework for Modeling Complex Terrains(The Eurographics Association and Blackwell Publishing Ltd, 2009) Peytavie, A.; Galin, E.; Grosjean, J.; Merillou, S.In this paper, we present a framework for representing complex terrains with such features as overhangs, arches and caves and including different materials such as sand and rocks. Our hybrid model combines a volumetric discrete data structure that stores the different materials and an implicit representation for sculpting and reconstructing the surface of the terrain. Complex scenes can be edited and sculpted interactively with high level tools. We also propose an original rock generation technique that enables us to automatically generate complex rocky sceneries with piles of rocks without any computationally demanding physically-based simulation.Item Completion and Reconstruction with Primitive Shapes(The Eurographics Association and Blackwell Publishing Ltd, 2009) Schnabel, Ruwen; Degener, Patrick; Klein, ReinhardWe consider the problem of reconstruction from incomplete point-clouds. To find a closed mesh the reconstruction is guided by a set of primitive shapes which has been detected on the input point-cloud (e.g. planes, cylinders etc.). With this guidance we not only continue the surrounding structure into the holes but also synthesize plausible edges and corners from the primitives intersections. To this end we give a surface energy functional that incorporates the primitive shapes in a guiding vector field. The discretized functional can be minimized with an efficient graph-cut algorithm. A novel greedy optimization strategy is proposed to minimize the functional under the constraint that surface parts corresponding to a given primitive must be connected. From the primitive shapes our method can also reconstruct an idealized model that is suitable for use in a CAD system.Item Shape Decomposition using Modal Analysis(The Eurographics Association and Blackwell Publishing Ltd, 2009) Huang, Qi-Xing; Wicke, Martin; Adams, Bart; Guibas, LeonidasWe introduce a novel algorithm that decomposes a deformable shape into meaningful parts requiring only a single input pose. Using modal analysis, we are able to identify parts of the shape that tend to move rigidly. We define a deformation energy on the shape, enabling modal analysis to find the typical deformations of the shape. We then find a decomposition of the shape such that the typical deformations can be well approximated with deformation fields that are rigid in each part of the decomposition. We optimize for the best decomposition, which captures how the shape deforms. A hierarchical refinement scheme makes it possible to compute more detailed decompositions for some parts of the shape.Although our algorithm does not require user intervention, it is possible to control the process by directly changing the deformation energy, or interactively refining the decomposition as necessary. Due to the construction of the energy function and the properties of modal analysis, the computed decompositions are robust to changes in pose as well as meshing, noise, and even imperfections such as small holes in the surface.Item Spectral-Based Group Formation Control(The Eurographics Association and Blackwell Publishing Ltd, 2009) Takahashi, Shigeo; Yoshida, Kenichi; Kwon, Taesoo; Lee, Kang Hoon; Lee, Jehee; Shin, Sung YongGiven a pair of keyframe formations for a group consisting of multiple individuals, we present a spectral-based approach to smoothly transforming a source group formation into a target formation while respecting the clusters of the involved individuals. The proposed method provides an effective means for controlling the macroscopic spatiotemporal arrangement of individuals for applications such as expressive formations in mass performances and tactical formations in team sports. Our main idea is to formulate this problem as rotation interpolation of the eigenbases for the Laplacian matrices, each of which represents how the individuals are clustered in a given keyframe formation. A stream of time-varying formations is controlled by editing the underlying adjacency relationships among individuals as well as their spatial positions at each keyframe, and interpolating the keyframe formations while producing plausible collective behaviors over a period of time. An interactive system of editing existing group behaviors in a hierarchical fashion has been implemented to provide flexible formation control of large crowds.Item LazyBrush: Flexible Painting Tool for Hand-drawn Cartoons(The Eurographics Association and Blackwell Publishing Ltd, 2009) Sykora, Daniel; Dingliana, John; Collins, StevenIn this paper we present LazyBrush, a novel interactive tool for painting hand-made cartoon drawings and animations. Its key advantage is simplicity and flexibility. As opposed to previous custom tailored approaches [SBv05, QWH06] LazyBrush does not rely on style specific features such as homogenous regions or pattern continuity yet still offers comparable or even less manual effort for a broad class of drawing styles. In addition to this, it is not sensitive to imprecise placement of color strokes which makes painting less tedious and brings significant time savings in the context cartoon animation. LazyBrush originally stems from requirements analysis carried out with professional ink-and-paint illustrators who established a list of useful features for an ideal painting tool. We incorporate this list into an optimization framework leading to a variant of Potts energy with several interesting theoretical properties. We show how to minimize it efficiently and demonstrate its usefulness in various practical scenarios including the ink-and-paint production pipeline.Item Out-of-core Data Management for Path Tracing on Hybrid Resources(The Eurographics Association and Blackwell Publishing Ltd, 2009) Budge, Brian; Bernardin, Tony; Stuart, Jeff A.; Sengupta, Shubhabrata; Joy, Kenneth I.; Owens, John D.We present a software system that enables path-traced rendering of complex scenes. The system consists of two primary components: an application layer that implements the basic rendering algorithm, and an out-of-core scheduling and data-management layer designed to assist the application layer in exploiting hybrid computational resources (e.g., CPUs and GPUs) simultaneously. We describe the basic system architecture, discuss design decisions of the system s data-management layer, and outline an efficient implementation of a path tracer application, where GPUs perform functions such as ray tracing, shadow tracing, importance-driven light sampling, and surface shading. The use of GPUs speeds up the runtime of these components by factors ranging from two to twenty, resulting in a substantial overall increase in rendering speed. The path tracer scales well with respect to CPUs, GPUs and memory per node as well as scaling with the number of nodes. The result is a system that can render large complex scenes with strong performance and scalability.Item A Part-aware Surface Metric for Shape Analysis(The Eurographics Association and Blackwell Publishing Ltd, 2009) Liu, Rong; Zhang, Hao; Shamir, Ariel; Cohen-Or, DanielThe notion of parts in a shape plays an important role in many geometry problems, including segmentation, correspondence, recognition, editing, and animation. As the fundamental geometric representation of 3D objects in computer graphics is surface-based, solutions of many such problems utilize a surface metric, a distance function defined over pairs of points on the surface, to assist shape analysis and understanding. The main contribution of our work is to bring together these two fundamental concepts: shape parts and surface metric. Specifically, we develop a surface metric that is part-aware. To encode part information at a point on a shape, we model its volumetric context - called the volumetric shape image (VSI) - inside the shape s enclosed volume, to capture relevant visibility information. We then define the part-aware metric by combining an appropriate VSI distance with geodesic distance and normal variation. We show how the volumetric view on part separation addresses certain limitations of the surface view, which relies on concavity measures over a surface as implied by the well-known minima rule. We demonstrate how the new metric can be effectively utilized in various applications including mesh segmentation, shape registration, part-aware sampling and shape retrieval.Item Importance Sampling Spherical Harmonics(The Eurographics Association and Blackwell Publishing Ltd, 2009) Jarosz, Wojciech; Carr, Nathan A.; Jensen, Henrik WannIn this paper we present the first practical method for importance sampling functions represented as spherical harmonics (SH). Given a spherical probability density function (PDF) represented as a vector of SH coefficients, our method warps an input point set to match the target PDF using hierarchical sample warping. Our approach is efficient and produces high quality sample distributions. As a by-product of the sampling procedure we produce a multi-resolution representation of the density function as either a spherical mip-map or Haar wavelet. By exploiting this implicit conversion we can extend the method to distribute samples according to the product of an SH function with a spherical mip-map or Haar wavelet. This generalization has immediate applicability in rendering, e.g., importance sampling the product of a BRDF and an environment map where the lighting is stored as a single high-resolution wavelet and the BRDF is represented in spherical harmonics. Since spherical harmonics can be efficiently rotated, this product can be computed on-the-fly even if the BRDF is stored in local-space. Our sampling approach generates over 6 million samples per second while significantly reducing precomputation time and storage requirements compared to previous techniques.Item Into the Blue: Better Caustics through Photon Relaxation(The Eurographics Association and Blackwell Publishing Ltd, 2009) Spencer, B.; Jones, M.W.The photon mapping method is one of the most popular algorithms employed in computer graphics today. However, obtaining good results is dependent on several variables including kernel shape and bandwidth, as well as the properties of the initial photon distribution. While the photon density estimation problem has been the target of extensive research, most algorithms focus on new methods of optimising the kernel to minimise noise and bias. In this paper we break from convention and propose a new approach that directly redistributes the underlying photons. We show that by relaxing the initial distribution into one with a blue noise spectral signature we can dramatically reduce background noise, particularly in areas of uniform illumination. In addition, we propose an efficient heuristic to detect and preserve features and discontinuities. We then go on to demonstrate how reconfiguration also permits the use of very low bandwidth kernels, greatly improving render times whilst reducing bias.Item Linear Time Super-Helices(The Eurographics Association and Blackwell Publishing Ltd, 2009) Bertails, FlorenceThin elastic rods such as cables, phone coils, tree branches, or hair, are common objects in the real world but computing their dynamics accurately remains challenging. The recent Super-Helix model, based on the discrete equations of Kirchhoff for a piecewise helical rod, is one of the most promising models for simulating non-stretchable rods that can bend and twist. However, this model suffers from a quadratic complexity in the number of discrete elements, which, in the context of interactive applications, makes it limited to a few number of degrees of freedom - or equivalently to a low number of variations in curvature along the mean curve. This paper proposes a new, recursive scheme for the dynamics of a Super-Helix, inspired by the popular algorithm of Featherstone for serial multibody chains. Similarly to Featherstone s algorithm, we exploit the recursive kinematics of a Super-Helix to propagate elements inertias from the free end to the clamped end of the rod, while the dynamics is solved within a second pass traversing the rod in the reverse way. Besides the gain in linear complexity, which allows us to simulate a rod of complex shape much faster than the original approach, our algorithm makes it straightforward to simulate tree-like structures of Super-Helices, which turns out to be particularly useful for animating trees and plants realistically, under large displacements.Item Energy Aware Color Sets(The Eurographics Association and Blackwell Publishing Ltd, 2009) Chuang, Johnson; Weiskopf, Daniel; Moeller, TorstenWe present a design technique for colors with the purpose of lowering the energy consumption of the display device. Our approach is based on a screen space variant energy model. The result of our design is a set of distinguishable iso-lightness colors guided by perceptual principles. We present two variations of our approach. One is based on a set of discrete user-named (categorical) colors, which are analyzed according to their energy consumption. The second is based on the constrained continuous optimization of color energy in the perceptually uniform CIELAB color space. We quantitatively compare our two approaches with a traditional choice of colors, demonstrating that we typically save approximately 40 percent of the energy. The color sets are applied to examples from the 2D visualization of nominal data and volume rendering of 3D scalar fields.Item Dominant Texture and Diffusion Distance Manifolds(The Eurographics Association and Blackwell Publishing Ltd, 2009) Lu, Jianye; Dorsey, Julie; Rushmeier, HollyTexture synthesis techniques require nearly uniform texture samples, however identifying suitable texture samples in an image requires significant data preprocessing. To eliminate this work, we introduce a fully automatic pipeline to detect dominant texture samples based on a manifold generated using the diffusion distance. We define the characteristics of dominant texture and three different types of outliers that allow us to efficiently identify dominant texture in feature space. We demonstrate how this method enables the analysis/synthesis of a wide range of natural textures. We compare textures synthesized from a sample image, with and without dominant texture detection. We also compare our approach to that of using a texture segmentation technique alone, and to using Euclidean, rather than diffusion, distances between texture features.Item Structure from silhouettes: a new paradigm for fast sketch-based design of trees(The Eurographics Association and Blackwell Publishing Ltd, 2009) Wither, J.; Boudon, F.; Cani, M.-P.; Godin, C.Modeling natural elements such as trees in a plausible way, while offering simple and rapid user control, is a challenge. This paper presents a method based on a new structure from silhouettes paradigm. We claim that sketching the silhouettes of foliage at multiple scales is quicker and more intuitive for a user than having to sketch each branch of a tree. This choice allows us to incorporate botanical knowledge, enabling us to infer branches that connect in a plausible way to their parent branch and have a correct distribution in 3D. We illustrate these ideas by presenting a seamless sketch-based interface, used for sketching foliage silhouettes from the scale of an entire tree to the scale of a leaf. Each sketch serves for inferring both the branches at that level and construction lines to serve as support for sub-silhouette refinement. When the user finally zooms out, the style inferred for the branching systems he has refined (in terms of branch density, angle, length distribution and shape) is duplicated to the unspecified branching systems at the same level. Meanwhile, knowledge from botany is again used for extending the branch distribution to 3D, resulting in a full, plausible 3D tree that fits the user-sketched contours. As our results show, this system can be of interest to both experts and novice users. While experts can fully specify all parts of a tree and over-sketch specific branches if required, any user can design a basic 3D tree in one or two minutes, as easily as sketching it with paper and pen.Item Simulation of two-phase flow with sub-scale droplet and bubble effects(The Eurographics Association and Blackwell Publishing Ltd, 2009) Mihalef, Viorel; Metaxas, Dimitris; Sussman, MarkWe present a new Eulerian-Lagrangian method for physics-based simulation of fluid flow, which includes automatic generation of sub-scale spray and bubbles. The Marker Level Set method is used to provide a simple geometric criterion for free marker generation. A filtering method, inspired from Weber number thresholding, further controls the free marker generation (in a physics-based manner). Two separate models are used, one for sub-scale droplets, the other for sub-scale bubbles. Droplets are evolved in a Newtonian manner, using a density-extension drag force field, while bubbles are evolved using a model based on Stokes Law. We show that our model for sub-scale droplet and bubble dynamics is simple to couple with a full (macro-scale) Navier-Stokes two-phase flow model and is quite powerful in its applications. Our animations include coarse grained multiphase features interacting with fine scale multiphase features.Item Fast GPU-based Adaptive Tessellation with CUDA(The Eurographics Association and Blackwell Publishing Ltd, 2009) Schwarz, Michael; Stamminger, MarcCompact surface descriptions like higher-order surfaces are popular representations for both modeling and animation. However, for fast graphics-hardware-assisted rendering, they usually need to be converted to triangle meshes. In this paper, we introduce a new framework for performing on-the-fly crack-free adaptive tessellation of surface primitives completely on the GPU. Utilizing CUDA and its flexible memory write capabilities, we parallelize the tessellation task at the level of single surface primitives. We are hence able to derive tessellation factors, perform surface evaluation as well as generate the tessellation topology in real-time even for large collections of primitives. We demonstrate the power of our framework by exemplarily applying it to both bicubic rational Bezier patches and PN triangles.Item Feature Preserving Point Set Surfaces based on Non-Linear Kernel Regression(The Eurographics Association and Blackwell Publishing Ltd, 2009) Oeztireli, A. C.; Guennebaud, G.; Gross, M.Moving least squares (MLS) is a very attractive tool to design effective meshless surface representations. However, as long as approximations are performed in a least square sense, the resulting definitions remain sensitive to outliers, and smooth-out small or sharp features. In this paper, we address these major issues, and present a novel point based surface definition combining the simplicity of implicit MLS surfaces [SOS04,Kol05] with the strength of robust statistics. To reach this new definition, we review MLS surfaces in terms of local kernel regression, opening the doors to a vast and well established literature from which we utilize robust kernel regression. Our novel representation can handle sparse sampling, generates a continuous surface better preserving fine details, and can naturally handle any kind of sharp features with controllable sharpness. Finally, it combines ease of implementation with performance competing with other non-robust approaches.