Full Papers 2010 - CGF 29-Issue 2

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/13882

Browse

Now showing 1 - 20 of 54

Tetrahedral Embedded Boundary Methods for Accurate and Flexible Adaptive Fluids
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Batty, Christopher; Xenos, Stefan; Houston, Ben
When simulating fluids, tetrahedral methods provide flexibility and ease of adaptivity that Cartesian grids find difficult to match. However, this approach has so far been limited by two conflicting requirements. First, accurate simulation requires quality Delaunay meshes and the use of circumcentric pressures. Second, meshes must align with potentially complex moving surfaces and boundaries, necessitating continuous remeshing. Unfortunately, sacrificing mesh quality in favour of speed yields inaccurate velocities and simulation artifacts. We describe how to eliminate the boundary-matching constraint by adapting recent embedded boundary techniques to tetrahedra, so that neither air nor solid boundaries need to align with mesh geometry. This enables the use of high quality, arbitrarily graded, non-conforming Delaunay meshes, which are simpler and faster to generate. Temporal coherence can also be exploited by reusing meshes over adjacent timesteps to further reduce meshing costs. Lastly, our free surface boundary condition eliminates the spurious currents that previous methods exhibited for slow or static scenarios. We provide several examples demonstrating that our efficient tetrahedral embedded boundary method can substantially increase the flexibility and accuracy of adaptive Eulerian fluid simulation.
Shared Sampling for Real-Time Alpha Matting
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Gastal, Eduardo S. L.; Oliveira, Manuel M.
Image matting aims at extracting foreground elements from an image by means of color and opacity (alpha) estimation. While a lot of progress has been made in recent years on improving the accuracy of matting techniques, one common problem persisted: the low speed of matte computation. We present the first real-time matting technique for natural images and videos. Our technique is based on the observation that, for small neighborhoods, pixels tend to share similar attributes. Therefore, independently treating each pixel in the unknown regions of a trimap results in a lot of redundant work. We show how this computation can be significantly and safely reduced by means of a careful selection of pairs of background and foreground samples. Our technique achieves speedups of up to two orders of magnitude compared to previous ones, while producing high-quality alpha mattes. The quality of our results has been verified through an independent benchmark. The speed of our technique enables, for the first time, real-time alpha matting of videos, and has the potential to enable a new class of exciting applications.
User-Controllable Color Transfer
(The Eurographics Association and Blackwell Publishing Ltd, 2010) An, Xiaobo; Pellacini, Fabio
This paper presents an image editing framework where users use reference images to indicate desired color edits. In our approach, users specify pairs of strokes to indicate corresponding regions in both the original and the reference image that should have the same color style . Within each stroke pair, a nonlinear constrained parametric transfer model is used to transfer the reference colors to the original. We estimate the model parameters by matching color distributions, under constraints that ensure no visual artifacts are present in the transfer result. To perform transfer on the whole image, we employ optimization methods to propagate the model parameters defined at each stroke location to spatially-close regions of similar appearance. This stroke-based formulation requires minimal user effort while retaining the high degree of user control necessary to allow artistic interpretations. We demonstrate our approach by performing color transfer on a number of image pairs varying in content and style, and show that our algorithm outperforms state-of-the-art color transfer methods on both user-controllability and visual qualities of the transfer results.
Synthesis of Responsive Motion Using a Dynamic Model
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Ye, Yuting; Liu, C. Karen
Synthesizing the movements of a responsive virtual character in the event of unexpected perturbations has proven a difficult challenge. To solve this problem, we devise a fully automatic method that learns a nonlinear probabilistic model of dynamic responses from very few perturbed walking sequences. This model is able to synthesize responses and recovery motions under new perturbations different from those in the training examples. When perturbations occur, we propose a physics-based method that initiates motion transitions to the most probable response example based on the dynamic states of the character. Our algorithm can be applied to any motion sequences without the need for preprocessing such as segmentation or alignment. The results show that three perturbed motion clips can sufficiently generate a variety of realistic responses, and 14 clips can create a responsive virtual character that reacts realistically to external forces in different directions applied on different body parts at different moments in time.
Interactive High-Quality Visualization of Higher-Order Finite Elements
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Ueffinger, Markus; Frey, Steffen; Ertl, Thomas
Higher-order finite element methods have emerged as an important discretization scheme for simulation. They are increasingly used in contemporary numerical solvers, generating a new class of data that must be analyzed by scientists and engineers. Currently available visualization tools for this type of data are either batch oriented or limited to certain cell types and polynomial degrees. Other approaches approximate higher-order data by resampling resulting in trade-offs in interactivity and quality. To overcome these limitations, we have developed a distributed visualization system which allows for interactive exploration of non-conforming unstructured grids, resulting from space-time discontinuous Galerkin simulations, in which each cell has its own higher-order polynomial solution. Our system employs GPU-based raycasting for direct volume rendering of complex grids which feature non-convex, curvilinear cells with varying polynomial degree. Frequency-based adaptive sampling accounts for the high variations along rays. For distribution across a GPU cluster, the initial object-space partitioning is determined by cell characteristics like the polynomial degree and is adapted at runtime by a load balancing mechanism. The performance and utility of our system is evaluated for different aeroacoustic simulations involving the propagation of shock fronts.
Mesh Decomposition with Cross-Boundary Brushes
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Zheng, Youyi; Tai, Chiew-Lan
We present a new intuitive UI, which we call cross-boundary brushes, for interactive mesh decomposition. The user roughly draws one or more strokes across a desired cut and our system automatically returns a best cut running through all the strokes. By the different natures of part components (i.e., semantic parts) and patch components (i.e., flatter surface patches) in general models, we design two corresponding brushes: part-brush and patch-brush. These two types of brushes share a common user interface, enabling easy switch between them. The part-brush executes a cut along an isoline of a harmonic field driven by the user-specified strokes. We show that the inherent smoothness of the harmonic field together with a carefully designed isoline selection scheme lead to segmentation results that are insensitive to noise, pose, tessellation and variation in user s strokes. Our patch-brush uses a novel facet-based surface metric that alleviates sensitivity to noise and fine details common in region-growing algorithms. Extensive experimental results demonstrate that our cutting tools can produce user-desired segmentations for a wide variety of models even with single strokes. We also show that our tools outperform the state-of-art interactive segmentation tools in terms of ease of use and segmentation quality.
Adding Depth to Cartoons Using Sparse Depth (In)equalities
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Sykora, D.; Sedlacek, D.; Jinchao, S.; Dingliana, J.; Collins, S.
This paper presents a novel interactive approach for adding depth information into hand-drawn cartoon images and animations. In comparison to previous depth assignment techniques our solution requires minimal user effort and enables creation of consistent pop-ups in a matter of seconds. Inspired by perceptual studies we formulate a custom tailored optimization framework that tries to mimic the way that a human reconstructs depth information from a single image. Its key advantage is that it completely avoids inputs requiring knowledge of absolute depth and instead uses a set of sparse depth (in)equalities that are much easier to specify. Since these constraints lead to a solution based on quadratic programming that is time consuming to evaluate we propose a simple approximative algorithm yielding similar results with much lower computational overhead. We demonstrate its usefulness in the context of a cartoon animation production pipeline including applications such as enhancement, registration, composition, 3D modelling and stereoscopic display.
Heat Transfer Simulation for Modeling Realistic Winter Sceneries
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Marechal, N.; Guerin, E.; Galin, E.; Merillou, S.; Merillou, N.
This paper presents a physically based method for simulating the heat transfers between the different environmental elements to synthesize realistic winter sceneries. We simulate the snow fall over the ground, as well as the conductive, convective and radiative thermal transfers using a finite volume method according to the variations of air and dew point temperatures, the amount of snow, cloud cover and day-night cycles. Our approach takes into account phase changes such as snow melting into water or water freezing into ice.
Fast and Efficient Skinning of Animated Meshes
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Kavan, L.; Sloan, P.-P.; O Sullivan, C.
Skinning is a simple yet popular deformation technique combining compact storage with efficient hardware accelerated rendering. While skinned meshes (such as virtual characters) are traditionally created by artists, previous work proposes algorithms to construct skinning automatically from a given vertex animation. However, these methods typically perform well only for a certain class of input sequences and often require long pre-processing times. We present an algorithm based on iterative coordinate descent optimization which handles arbitrary animations and produces more accurate approximations than previous techniques, while using only standard linear skinning without any modifications or extensions. To overcome the computational complexity associated with the iterative optimization, we work in a suitable linear subspace (obtained by quick approximate dimensionality reduction) and take advantage of the typically very sparse vertex weights. As a result, our method requires about one or two orders of magnitude less pre-processing time than previous methods.
Isosurfaces Over Simplicial Partitions of Multiresolution Grids
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Manson, Josiah; Schaefer, Scott
We provide a simple method that extracts an isosurface that is manifold and intersection-free from a function over an arbitrary octree. Our method samples the function dual to minimal edges, faces, and cells, and we show how to position those samples to reconstruct sharp and thin features of the surface. Moreover, we describe an error metric designed to guide octree expansion such that flat regions of the function are tiled with fewer polygons than curved regions to create an adaptive polygonalization of the isosurface. We then show how to improve the quality of the triangulation by moving dual vertices to the isosurface and provide a topological test that guarantees we maintain the topology of the surface. While we describe our algorithm in terms of extracting surfaces from volumetric functions, we also show that our algorithm extends to generating manifold level sets of co-dimension 1 of functions of arbitrary dimension.
Articulated Billboards for Video-based Rendering
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Germann, Marcel; Hornung, Alexander; Keiser, Richard; Ziegler, Remo; Wuermlin, Stephan; Gross, Markus
We present a novel representation and rendering method for free-viewpoint video of human characters based on multiple input video streams. The basic idea is to approximate the articulated 3D shape of the human body using a subdivision into textured billboards along the skeleton structure. Billboards are clustered to fans such that each skeleton bone contains one billboard per source camera. We call this representation articulated billboards.In the paper we describe a semi-automatic, data-driven algorithm to construct and render this representation, which robustly handles even challenging acquisition scenarios characterized by sparse camera positioning, inaccurate camera calibration, low video resolution, or occlusions in the scene. First, for each input view, a 2D pose estimation based on image silhouettes, motion capture data, and temporal video coherence is used to create a segmentation mask for each body part. Then, from the 2D poses and the segmentation, the actual articulated billboard model is constructed by a 3D joint optimization and compensation for camera calibration errors. The rendering method includes a novel way of blending the textural contributions of each billboard and features an adaptive seam correction to eliminate visible discontinuities between adjacent billboards textures.Our articulated billboards do not only minimize ghosting artifacts known from conventional billboard rendering, but also alleviate restrictions to the setup and sensitivities to errors of more complex 3D representations and multiview reconstruction techniques. Our results demonstrate the flexibility and the robustness of our approach with high quality free-viewpoint video generated from broadcast footage of challenging, uncontrolled environments.
Fast High-Dimensional Filtering Using the Permutohedral Lattice
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Adams, Andrew; Baek, Jongmin; Davis, Myers Abraham
Many useful algorithms for processing images and geometry fall under the general framework of high-dimensional Gaussian filtering. This family of algorithms includes bilateral filtering and non-local means. We propose a new way to perform such filters using the permutohedral lattice, which tessellates high-dimensional space with uniform simplices. Our algorithm is the first implementation of a high-dimensional Gaussian filter that is both linear in input size and polynomial in dimensionality. Furthermore it is parameter-free, apart from the filter size, and achieves a consistently high accuracy relative to ground truth (> 45 dB). We use this to demonstrate a number of interactive-rate applications of filters in as high as eight dimensions.
Bidirectional Search for Interactive Motion Synthesis
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Lo, Wan-Yen; Zwicker, Matthias
We present an approach to improve the search efficiency for near-optimal motion synthesis using motion graphs. An optimal or near-optimal path through a motion graph often leads to the most intuitive result. However, finding such a path can be computationally expensive. Our main contribution is a bidirectional search algorithm. We dynamically divide the search space evenly and merge two search trees to obtain the final solution. This cuts the maximum search depth almost in half and leads to significant speedup. To illustrate the benefits of our approach, we present an interactive sketching interface that allows users to specify complex motions quickly and intuitively.
Practical quad mesh simplification
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Tarini, Marco; Pietroni, Nico; Cignoni, Paolo; Panozzo, Daniele; Puppo, Enrico
In this paper we present an innovative approach to incremental quad mesh simplification, i.e. the task of producing a low complexity quad mesh starting from a high complexity one. The process is based on a novel set of strictly local operations which preserve quad structure. We show how good tessellation quality (e.g. in terms of vertex valencies) can be achieved by pursuing uniform length and canonical proportions of edges and diagonals. The decimation process is interleaved with smoothing in tangent space. The latter strongly contributes to identify a suitable sequence of local modification operations. The method is naturally extended to manage preservation of feature lines (e.g. creases) and varying (e.g. adaptive) tessellation densities. We also present an original Triangle-to-Quad conversion algorithm that behaves well in terms of geometrical complexity and tessellation quality, which we use to obtain the initial quad mesh from a given triangle mesh.
Exact and Robust (Self-)Intersections for Polygonal Meshes
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Campen, Marcel; Kobbelt, Leif
We present a new technique to implement operators that modify the topology of polygonal meshes at intersections and self-intersections. Depending on the modification strategy, this effectively results in operators for Boolean combinations or for the construction of outer hulls that are suited for mesh repair tasks and accurate mesh-based front tracking of deformable materials that split and merge. By combining an adaptive octree with nested binary space partitions (BSP), we can guarantee exactness (= correctness) and robustness (= completeness) of the algorithm while still achieving higher performance and less memory consumption than previous approaches. The efficiency and scalability in terms of runtime and memory is obtained by an operation localization scheme. We restrict the essential computations to those cells in the adaptive octree where intersections actually occur. Within those critical cells, we convert the input geometry into a plane-based BSP-representation which allows us to perform all computations exactly even with fixed precision arithmetics. We carefully analyze the precision requirements of the involved geometric data and predicates in order to guarantee correctness and show how minimal input mesh quantization can be used to safely rely on computations with standard floating point numbers. We properly evaluate our method with respect to precision, robustness, and efficiency.
Perceptually-motivated Real-time Temporal Upsampling of 3D Content for High-refresh-rate Displays
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Didyk, Piotr; Eisemann, Elmar; Ritschel, Tobias; Myszkowski, Karol; Seidel, Hans-Peter
High-refresh-rate displays (e. g., 120 Hz) have recently become available on the consumer market and quickly gain on popularity. One of their aims is to reduce the perceived blur created by moving objects that are tracked by the human eye. However, an improvement is only achieved if the video stream is produced at the same high refresh rate (i. e. 120 Hz). Some devices, such as LCD TVs, solve this problem by converting low-refresh-rate content (i. e. 50 Hz PAL) into a higher temporal resolution (i. e. 200 Hz) based on two-dimensional optical flow.In our approach, we will show how rendered three-dimensional images produced by recent graphics hardware can be up-sampled more efficiently resulting in higher quality at the same time. Our algorithm relies on several perceptual findings and preserves the naturalness of the original sequence. A psychophysical study validates our approach and illustrates that temporally up-sampled video streams are preferred over the standard low-rate input by the majority of users. We show that our solution improves task performance on high-refresh-rate displays.
Frontmatter EG 2010
(The Eurographics Association and Blackwell Publishing Ltd, 2010)
SoundRiver: Semantically-Rich Sound Illustration
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Jaenicke, H.; Borgo, R.; Mason, J. S. D.; Chen, M.
Sound is an integral part of most movies and videos. In many situations, viewers of a video are unable to hear the sound track, for example, when watching it in a fast forward mode, viewing it by hearing-impaired viewers or when the plot is given as a storyboard. In this paper, we present an automated visualization solution to such problems. The system first detects the common components (such as music, speech, rain, explosions, and so on) from a sound track, then maps them to a collection of programmable visual metaphors, and generates a composite visualization. This form of sound visualization, which is referred to as SoundRiver, can be also used to augment various forms of video abstraction and annotated key frames and to enhance graphical user interfaces for video handling software. The SoundRiver conveys more semantic information to the viewer than traditional graphical representations of sound illustration, such as phonoautographs, spectrograms or artistic audiovisual animations.
Sketching Clothoid Splines Using Shortest Paths
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Baran, Ilya; Lehtinen, Jaakko; Popovic, Jovan
Clothoid splines are gaining popularity as a curve representation due to their intrinsically pleasing curvature, which varies piecewise linearly over arc length. However, constructing them from hand-drawn strokes remains difficult. Building on recent results, we describe a novel algorithm for approximating a sketched stroke with a fair (i.e., visually pleasing) clothoid spline. Fairness depends on proper segmentation of the stroke into curve primitives - lines, arcs, and clothoids. Our main idea is to cast the segmentation as a shortest path problem on a carefully constructed weighted graph. The nodes in our graph correspond to a vastly overcomplete set of curve primitives that are fit to every subsegment of the sketch, and edges correspond to transitions of a specified degree of continuity between curve primitives. The shortest path in the graph corresponds to a desirable segmentation of the input curve. Once the segmentation is found, the primitives are fit to the curve using non-linear constrained optimization. We demonstrate that the curves produced by our method have good curvature profiles, while staying close to the user sketch.
gProximity: Hierarchical GPU-based Operations for Collision and Distance Queries
(The Eurographics Association and Blackwell Publishing Ltd, 2010) Lauterbach, C.; Mo, Q.; Manocha, D.
We present novel parallel algorithms for collision detection and separation distance computation for rigid and deformable models that exploit the computational capabilities of many-core GPUs. Our approach uses thread and data parallelism to perform fast hierarchy construction, updating, and traversal using tight-fitting bounding volumes such as oriented bounding boxes (OBB) and rectangular swept spheres (RSS). We also describe efficient algorithms to compute a linear bounding volume hierarchy (LBVH) and update them using refitting methods. Moreover, we show that tight-fitting bounding volume hierarchies offer improved performance on GPU-like throughput architectures. We use our algorithms to perform discrete and continuous collision detection including self-collisions, as well as separation distance computation between non-overlapping models. In practice, our approach (gProximity) can perform these queries in a few milliseconds on a PC with NVIDIA GTX 285 card on models composed of tens or hundreds of thousands of triangles used in cloth simulation, surgical simulation, virtual prototyping and N-body simulation. Moreover, we observe more than an order of magnitude performance improvement over prior GPU-based algorithms.

Browse

Browsing Full Papers 2010 - CGF 29-Issue 2 by Issue Date

Results Per Page

Sort Options