Volume 30 (2011)

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 236

A Parallel SPH Implementation on Multi-Core CPUs
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Ihmsen, Markus; Akinci, Nadir; Becker, Markus; Teschner, Matthias; Eduard Groeller and Holly Rushmeier
This paper presents a parallel framework for simulating fluids with the Smoothed Particle Hydrodynamics (SPH) method. For low computational costs per simulation step, efficient parallel neighbourhood queries are proposed and compared. To further minimize the computing time for entire simulation sequences, strategies for maximizing the time step and the respective consequences for parallel implementations are investigated. The presented experiments illustrate that the parallel framework can efficiently compute large numbers of time steps for large scenarios. In the context of neighbourhood queries, the paper presents optimizations for two efficient instances of uniform grids, that is, spatial hashing and index sort. For implementations on parallel architectures with shared memory, the paper discusses techniques with improved cache-hit rate and reduced memory transfer. The performance of the parallel implementations of both optimized data structures is compared. The proposed solutions focus on systems with multiple CPUs. Benefits and challenges of potential GPU implementations are only briefly discussed.
Localized Delaunay Refinement for Volumes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Dey, Tamal K.; Slatton, Andrew G.; Mario Botsch and Scott Schaefer
Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state-of-the-art meshing tool provided by CGAL.
Fast Extraction of High-quality Crease Surfaces for Visual Analysis
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Barakat, Samer; Andrysco, N.; Tricoche, Xavier; H. Hauser, H. Pfister, and J. J. van Wijk
We present a novel algorithm for the efficient extraction and visualization of high-quality ridge and valley surfaces from numerical datasets. Despite their rapidly increasing popularity in visualization, these so-called crease surfaces remain challenging to compute owing to their strongly nonlinear and non-orientable nature, and their complex boundaries. In this context, existing meshing techniques require an extremely dense sampling that is computationally prohibitive. Our proposed solution intertwines sampling and meshing steps to yield an accurate approximation of the underlying surfaces while ensuring the geometric quality of the resulting mesh. Using the computation power of the GPU, we propose a fast, parallel method for sampling. Additionally, we present a new front propagation meshing strategy that leverages CPU multiprocessing. Results are shown for synthetic, medical and fluid dynamics datasets.
Evaluation of the Visibility of Vessel Movement Features in Trajectory Visualizations
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Willems, Niels; Wetering, Huub van de; Wijk, Jarke J. van; H. Hauser, H. Pfister, and J. J. van Wijk
There are many visualizations that show the trajectory of a moving object to obtain insights in its behavior. In this user study, we test the performance of three of these visualizations with respect to three movement features that occur in vessel behavior. Our goal is to compare the recently presented vessel density by Willems et al. [WvdWvW09] with well-known trajectory visualizations such as an animation of moving dots and the space-time cube. We test these visualizations with common maritime analysis tasks by investigating the ability of users to find stopping objects, fast moving objects, and estimate the busiest routes in vessel trajectories. We test the robustness of the visualizations towards scalability and the influence of complex trajectories using small-scale synthetic data sets. The performance is measured in terms of correctness and response time. The user test shows that each visualization type excels for correctness for a specific movement feature. Vessel density performs best for finding stopping objects, but does not perform significantly less than the remaining visualizations for the other features. Therefore, vessel density is a nice extension in the toolkit for analyzing trajectories of moving objects, in particular for vessel movements, since stops can be visualized better, and the performance for comparing lanes and finding fast movers is at a similar level as established trajectory visualizations.
An Optimal Transport Approach to Robust Reconstruction and Simplification of 2D Shapes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Goes, Fernando de; Cohen-Steiner, David; Alliez, Pierre; Desbrun, Mathieu; Mario Botsch and Scott Schaefer
We propose a robust 2D shape reconstruction and simplification algorithm which takes as input a defect-laden point set with noise and outliers. We introduce an optimal-transport driven approach where the input point set, considered as a sum of Dirac measures, is approximated by a simplicial complex considered as a sum of uniform measures on 0- and 1-simplices. A fine-to-coarse scheme is devised to construct the resulting simplicial complex through greedy decimation of a Delaunay triangulation of the input point set. Our method performs well on a variety of examples ranging from line drawings to grayscale images, with or without noise, features, and boundaries.
Bertin was Right: An Empirical Evaluation of Indexing to Compare Multivariate Time-Series Data Using Line Plots
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Aigner, W.; Kainz, C.; Ma, R.; Miksch, S.; Eduard Groeller and Holly Rushmeier
Line plots are very well suited for visually representing time-series. However, several difficulties arise when multivariate heterogeneous time-series data is displayed and compared visually. Especially, if the developments and trends of time-series of different units or value ranges need to be compared, a straightforward overlay could be visually misleading. To mitigate this, visualization pioneer Jacques Bertin presented a method called indexing that transforms data into comparable units for visual representation. In this paper, we want to provide empirical evidence for this method and present a comparative study of the three visual comparison methods linear scale with juxtaposition, log scale with superimposition and indexing. Although for task completion times, indexing only shows slight advantages, the results support the assumption that the indexing method enables the user to perform comparison tasks with a significantly lower error rate. Furthermore, a post-test questionnaire showed that the majority of the participants favour the indexing method over the two other comparison methods.
A Linear Variational System for Modelling From Curves
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Andrews, James; Joshi, Pushkar; Carr, Nathan; Eduard Groeller and Holly Rushmeier
We present a linear system for modelling 3D surfaces from curves. Our system offers better performance, stability and precision in control than previous non‐linear systems. By exploring the direct relationship between a standard higher‐order Laplacian editing framework and Hermite spline curves, we introduce a new form of Cauchy constraint that makes our system easy to both implement and control. We introduce novel workflows that simplify the construction of 3D models from sketches. We show how to convert existing 3D meshes into our curve‐based representation for subsequent editing and modelling, allowing our technique to be applied to a wide range of existing 3D content.
Improved Stochastic Progressive Photon Mapping with Metropolis Sampling
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Chen, Jiating; Wang, Bin; Yong, Jun-Hai; Ravi Ramamoorthi and Erik Reinhard
This paper presents an improvement to the stochastic progressive photon mapping (SPPM), a method for robustly simulating complex global illumination with distributed ray tracing effects. Normally, similar to photon mapping and other particle tracing algorithms, SPPM would become inefficient when the photons are poorly distributed. An inordinate amount of photons are required to reduce the error caused by noise and bias to acceptable levels. In order to optimize the distribution of photons, we propose an extension of SPPM with a Metropolis-Hastings algorithm, effectively exploiting local coherence among the light paths that contribute to the rendered image. A well-designed scalar contribution function is introduced as our Metropolis sampling strategy, targeting at specific parts of image areas with large error to improve the efficiency of the radiance estimator. Experimental results demonstrate that the new Metropolis sampling based approach maintains the robustness of the standard SPPM method, while significantly improving the rendering efficiency for a wide range of scenes with complex lighting.
On Neighbourhood Matching for Texture-by-Numbers
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Sivaks, Eliyahu; Lischinski, Dani; Eduard Groeller and Holly Rushmeier
Texture-by-Numbers is an attractive texture synthesis framework, because it is able to cope with non-homogeneous texture exemplars, and provides the user with intuitive creative control over the outcome of the synthesis process. Like many other exemplar-based texture synthesis methods, its basic underlying mechanism is neighbourhood matching. In this paper we review a number of commonly used neighbourhood matching acceleration techniques, compare and analyse their performance in the specific context of Texture-by-Numbers (as opposed to ordinary unconstrained texture synthesis). Our study indicates that the standard approaches are not optimally suited for the Texture-by-Numbers framework, often producing visually inferior results compared to searching for the exact L2nearest neighbour. We then show that performing Texture-by-Number using the Texture Optimization framework in conjunction with an efficient FFT-based search is able to produce good results in reasonable running times and with a minimal memory overhead.
On Approximation of the Laplace-Beltrami Operator and the Willmore Energy of Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Hildebrandt, Klaus; Polthier, Konrad; Mario Botsch and Scott Schaefer
Discrete Laplace Beltrami operators on polyhedral surfaces play an important role for various applications in geometry processing and related areas like physical simulation or computer graphics. While discretizations of the weak Laplace Beltrami operator are well-studied, less is known about the strong form. We present a principle for constructing strongly consistent discrete Laplace Beltrami operators based on the cotan weights. The consistency order we obtain, improves previous results reported for the mesh Laplacian. Furthermore, we prove consistency of the discrete Willmore energies corresponding to the discrete Laplace Beltrami operators.
Rational Bi-cubic G2 Splines for Design with Basic Shapes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Karciauskas, Kestutis; Peters, Jörg; Mario Botsch and Scott Schaefer
The paper develops a rational bi-cubic G<sup>2</sup> (curvature continuous) analogue of the non-uniform polynomial C<sup>2</sup> cubic B-spline paradigm. These rational splines can exactly reproduce parts of multiple basic shapes, such as cyclides and quadrics, in one by default smoothly-connected structure. The versatility of this new tool for processing exact geometry is illustrated by conceptual design from basic shapes.
Preface and Table of Contents
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bing-Yu Chen and Jan Kautz and Tong-Yee Lee and Ming C. Lin
Event report: Symposium on Computer Animation 2010
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Eduard Groeller and Holly Rushmeier
Variable Bit Rate GPU Texture Decompression
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Olano, Marc; Baker, Dan; Griffin, Wesley; Barczak, Joshua; Ravi Ramamoorthi and Erik Reinhard
Variable bit rate compression can achieve better quality and compression rates than fixed bit rate methods. None the less, GPU texturing uses lossy fixed bit rate methods like DXT to allow random access and on-the-fly decompression during rendering. Changes in games and GPUs since DXT was developed make its compression artifacts less acceptable, and texture bandwidth less of an issue, but texture size is a serious and growing problem. Games use a large total volume of texture data, but have a much smaller active set. We present a new paradigm that separates GPU decompression from rendering. Rendering is from uncompressed data, avoiding the need for random access decompression. We demonstrate this paradigm with a new variable bit rate lossy texture compression algorithm that is well suited to the GPU, including a new GPU-friendly formulation of range decoding, and a new texture compression scheme averaging 12.4:1 lossy compression ratio on 471 real game textures with a quality level similar to traditional DXT compression. The total game texture set are stored in the GPU in compressed form, and decompressed for use in a fraction of a second per scene.
ImPrEd: An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Simonetto, Paolo; Archambault, Daniel; Auber, David; Bourqui, Romain; H. Hauser, H. Pfister, and J. J. van Wijk
PrEd [Ber00] is a force-directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler-like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overlyrestrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundaries. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEd proves to be consistently faster than PrEd.
Component-wise Controllers for Structure-Preserving Shape Manipulation
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Zheng, Youyi; Fu, Hongbo; Cohen-Or, Daniel; Au, Oscar Kin-Chung; Tai, Chiew-Lan; M. Chen and O. Deussen
Recent shape editing techniques, especially for man-made models, have gradually shifted focus from maintaining local, low-level geometric features to preserving structural, high-level characteristics like symmetry and parallelism. Such new editing goals typically require a pre-processing shape analysis step to enable subsequent shape editing. Observing that most editing of shapes involves manipulating their constituent components, we introduce component-wise controllers that are adapted to the component characteristics inferred from shape analysis. The controllers capture the natural degrees of freedom of individual components and thus provide an intuitive user interface for editing. A typical model usually results in a moderate number of controllers, allowing easy establishment of semantic relations among them by automatic shape analysis supplemented with user interaction. We propose a component-wise propagation algorithm to automatically preserve the established inter-relations while maintaining the defining characteristics of individual controllers and respecting the user-specified modeling constraints. We extend these ideas to a hierarchical setup, allowing the user to adjust the tool complexity with respect to the desired modeling complexity. We demonstrate the effectiveness of our technique on a wide range of manmade models with structural features, often containing multiple connected pieces.
Eurographics Workshops VCBM 2008 and 2010
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Wiebel, Alexander; Botha, Charl; Preim, Bernhard; Eduard Groeller and Holly Rushmeier
Visualizing the Positional and Geometrical Variability of Isosurfaces in Uncertain Scalar Fields
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Pfaffelmoser, Tobias; Reitinger, Matthias; Westermann, Rüdiger; H. Hauser, H. Pfister, and J. J. van Wijk
We present a novel approach for visualizing the positional and geometrical variability of isosurfaces in uncertain 3D scalar fields. Our approach extends recent work by Pöthkow and Hege [PH10] in that it accounts for correlations in the data to determine more reliable isosurface crossing probabilities. We introduce an incremental updatescheme that allows integrating the probability computation into front-to-back volume ray-casting efficiently. Our method accounts for homogeneous and anisotropic correlations, and it determines for each sampling interval along a ray the probability of crossing an isosurface for the first time. To visualize the positional and geometrical uncertainty even under viewing directions parallel to the surface normal, we propose a new color mapping scheme based on the approximate spatial deviation of possible surface points from the mean surface. The additional use of saturation enables to distinguish between areas of high and low statistical dependence. Experimental results confirm the effectiveness of our approach for the visualization of uncertainty related to position and shape of convex and concave isosurface structures.
Interactive Modeling of City Layouts using Layers of Procedural Content
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Lipp, Markus; Scherzer, Daniel; Wonka, Peter; Wimmer, Michael; M. Chen and O. Deussen
In this paper, we present new solutions for the interactive modeling of city layouts that combine the power of procedural modeling with the flexibility of manual modeling. Procedural modeling enables us to quickly generate large city layouts, while manual modeling allows us to hand-craft every aspect of a city. We introduce transformation and merging operators for both topology preserving and topology changing transformations based on graph cuts. In combination with a layering system, this allows intuitive manipulation of urban layouts using operations such as drag and drop, translation, rotation etc. In contrast to previous work, these operations always generate valid, i.e., intersection-free layouts. Furthermore, we introduce anchored assignments to make sure that modifications are persistent even if the whole urban layout is regenerated.
Temporal Visualization of Boundary-based Geo-information Using Radial Projection
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Drocourt, Y.; Borgo, Rita; Scharrer, K.; Murray, T.; Bevan, S. I.; Chen, M.; H. Hauser, H. Pfister, and J. J. van Wijk
This work is concerned with a design study by an interdisciplinary team on visualizing a 10-year record of seasonal and inter-annual changes in frontal position (advance/retreat) of nearly 200 marine terminating glaciers in Greenland. Whilst the spatiotemporal nature of the raw data presents a challenge to develop a compact and intuitive visual design, the focus on coastal boundaries provides an opportunity for dimensional reduction. In this paper, we report the user-centered design process carried out by the team, and present several visual encoding schemes that have met the requirements including compactness, intuitiveness, and ability to depict temporal changes and spatial relations. In particular, we designed a family of radial visualization, where radial lines correspond to different coastal locations, and nested rings represent the evolution of the temporal dimension from inner to outer circles. We developed an algorithm for mapping glacier terminus positions from Cartesian coordinates to angular coordinates. Instead of a naive uniform mapping, the algorithm maintains consistent spatial perception of the visually-sensitive geographical references between their Cartesian and angular coordinates, and distributes other termini positions between primary locations based on coastal distance. This work has provided a useful solution to address the problem of inaccuracy in change evaluation based on pixel-based visualization [BPC*10].

Browse

Browsing Volume 30 (2011) by Issue Date

Results Per Page

Sort Options