Volume 30 (2011)
Permanent URI for this community
Browse
Browsing Volume 30 (2011) by Issue Date
Now showing 1 - 20 of 236
Results Per Page
Sort Options
Item Efficient Packing of Arbitrarily Shaped Charts for Automatic Texture Atlas Generation(The Eurographics Association and Blackwell Publishing Ltd., 2011) Nöll, Tobias; Stricker, Didier; Ravi Ramamoorthi and Erik ReinhardTexture atlases are commonly used as representations for mesh parameterizations in numerous applications including texture and normal mapping. Therefore, packing is an important post-processing step that tries to place and orient the single parameterizations in a way that the available space is used as efficiently as possible. However, since packing is NP hard, only heuristics can be used in practice to find near-optimal solutions. In this publication we introduce the new search space of modulo valid packings. The key idea thereby is to allow the texture charts to wrap around in the atlas. By utilizing this search space we propose a new algorithm that can be used in order to automatically pack texture atlases. In the evaluation section we show that our algorithm achieves solutions with a significantly higher packing efficiency when compared to the state of the art, especially for complex packing problems.Item Heat Walk: Robust Salient Segmentation of Non-rigid Shapes(The Eurographics Association and Blackwell Publishing Ltd., 2011) Benjamin, William; Polk, Andrew Wood; Vishwanathan, S. V. N.; Ramani, Karthik; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. LinSegmenting three dimensional objects using properties of heat diffusion on meshes aim to produce salient results. The few existing algorithms based on heat diffusion do not use the full knowledge that can be gained from heat diffusion and are sensitive to varying kinds of perturbations. Our simple algorithm, Heat Walk, converts the implicit information in the heat kernel to explicit knowledge about the pathways for maximum heat flow capacity. We develop a two stage strategy for segmentation. In the first stage we quickly identify regions which are dominated by heat accumulators by employing a greedy algorithm. The second stage partitions out dissipative regions from the previously discovered accumulative regions by using a KL-divergence based criterion. The resulting algorithm is both independent of human intervention and fast because of the globally aware directed walk along the maximal heat flow capacity. Extensive experimental evidence shows the method is robust to a variety of noise factors including topological short circuits, surface holes, pose variations, variations in tessellation, missing features, scaling, as well as normal and shot noise. Comparison with the Princeton Segmentation Benchmark (PSB) shows that our method is comparable with state of the art segmentation methods and has additional advantages of being robust and self contained. Based upon theoretical insight the convergence and stability of the Heat Walk is shown.Item State‐of‐the‐Art Report on Temporal Coherence for Stylized Animations(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bénard, Pierre; Bousseau, Adrien; Thollot, Joëlle; Eduard Groeller and Holly RushmeierNon‐photorealistic rendering (NPR) algorithms allow the creation of images in a variety of styles, ranging from line drawing and pen‐and‐ink to oil painting and watercolour. These algorithms provide greater flexibility, control and automation over traditional drawing and painting. Despite significant progress over the past 15 years, the application of NPR to the generation of stylized animations remains an active area of research. The main challenge of computer‐generated stylized animations is to reproduce the look of traditional drawings and paintings while minimizing distracting flickering and sliding artefacts present in hand‐drawn animations. These goals are inherently conflicting and any attempt to address the temporal coherence of stylized animations is a trade‐off. This state‐of‐the‐art report is motivated by the growing number of methods proposed in recent years and the need for a comprehensive analysis of the trade‐offs they propose. We formalize the problem of temporal coherence in terms of goals and compare existing methods accordingly. We propose an analysis for both line and region stylization methods and discuss initial steps towards their perceptual evaluation. The goal of our report is to help uninformed readers to choose the method that best suits their needs, as well as motivate further research to address the limitations of existing methods.Item Visual Boosting in Pixel-based Visualizations(The Eurographics Association and Blackwell Publishing Ltd., 2011) Oelke, Daniela; Janetzko, Halldor; Simon, Svenja; Neuhaus, Klaus; Keim, Daniel A.; H. Hauser, H. Pfister, and J. J. van WijkPixel-based visualizations have become popular, because they are capable of displaying large amounts of data and at the same time provide many details. However, pixel-based visualizations are only effective if the data set is not sparse and the data distribution not random. Single pixels - no matter if they are in an empty area or in the middle of a large area of differently colored pixels - are perceptually difficult to discern and may therefore easily be missed. Furthermore, trends and interesting passages may be camouflaged in the sea of details. In this paper we compare different approaches for visual boosting in pixel-based visualizations. Several boosting techniques such as halos, background coloring, distortion, and hatching are discussed and assessed with respect to their effectiveness in boosting single pixels, trends, and interesting passages. Application examples from three different domains (document analysis, genome analysis, and geospatial analysis) show the general applicability of the techniques and the derived guidelines.Item Event report: Eurographics 2011 Workshop on 3D Object Retrieval (EG 3DOR'2011)(The Eurographics Association and Blackwell Publishing Ltd., 2011) Eduard Groeller and Holly RushmeierItem Guided ProceduralModeling(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bene , Bedrich; tava, Ondrej; Mech, Radomir; Miller, Gavin; M. Chen and O. DeussenProcedural methods present one of the most powerful techniques for authoring a vast variety of computer graphics models. However, their massive applicability is hindered by the lack of control and a low predictability of the results. In the classical procedural modeling pipeline, the user usually defines a set of rules, executes the procedural system, and by examining the results attempts to infer what should be changed in the system definition in order to achieve the desired output. We present guided procedural modeling, a new approach that allows a high level of top-down control by breaking the system into smaller building blocks that communicate. In our work we generalize the concept of the environment. The user creates a set of guides. Each guide defines a region in which a specific procedural model operates. These guides are connected by a set of links that serve for message passing between the procedural models attached to each guide. The entire model consists of a set of guides with procedural models, a graph representing their connection, and the method in which the guides interact. The modeling process is performed by modifying each of the described elements. The user can control the high-level description by editing the guides or manipulate the low-level description by changing the procedural rules. Changing the connectivity allows the user to create new complex forms in an easy and intuitive way. We show several examples of procedural structures, including an ornamental pattern, a street layout, a bridge, and a model of trees. We also demonstrate interactive examples for quick and intuitive editing using physics-based mass-spring system.Item Motion Blur Rendering: State of the Art(The Eurographics Association and Blackwell Publishing Ltd., 2011) Navarro, Fernando; Serón, Francisco J.; Gutierrez, Diego; Eduard Groeller and Holly RushmeierMotion blur is a fundamental cue in the perception of objects in motion. This phenomenon manifests as a visible trail along the trajectory of the object and is the result of the combination of relative motion and light integration taking place in film and electronic cameras. In this work, we analyse the mechanisms that produce motion blur in recording devices and the methods that can simulate it in computer generated images. Light integration over time is one of the most expensive processes to simulate in high-quality renders, as such, we make an in-depth review of the existing algorithms and we categorize them in the context of a formal model that highlights their differences, strengths and limitations. We finalize this report proposing a number of alternative classifications that will help the reader identify the best technique for a particular scenario.Item CheckViz: Sanity Check and Topological Clues for Linear and Non-Linear Mappings(The Eurographics Association and Blackwell Publishing Ltd., 2011) Lespinats, Sylvain; Aupetit, Michaël; Eduard Groeller and Holly RushmeierMultidimensional scaling is a must-have tool for visual data miners, projecting multidimensional data onto a two-dimensional plane. However, what we see is not necessarily what we think about. In many cases, end-users do not take care of scaling the projection space with respect to the multidimensional space. Anyway, when using non-linear mappings, scaling is not even possible. Yet, without scaling geometrical structures which might appear do not make more sense than considering a random map. Without scaling, we shall not make inference from the display back to the multidimensional space. No clusters, no trends, no outliers, there is nothing to infer without first quantifying the mapping quality. Several methods to qualify mappings have been devised. Here, we propose CheckViz, a new method belonging to the framework of Verity Visualization. We define a two-dimensional perceptually uniform colour coding which allows visualizing tears and false neighbourhoods, the two elementary and complementary types of geometrical mapping distortions, straight onto the map at the location where they occur. As examples shall demonstrate, this visualization method is essential to help users make sense out of the mappings and to prevent them from over interpretations. It could be applied to check other mappings as well.Item Authoring Hierarchical Road Networks(The Eurographics Association and Blackwell Publishing Ltd., 2011) Galin, Eric; Peytavie, Adrien; Guérin, Eric; Benes, Bedrich; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. LinWe present a procedural method for generating hierarchical road networks connecting cities, towns and villages over large terrains. Our approach relies on an original geometric graph generation algorithm based on a non- Euclidean metric combined with a path merging algorithm that creates junctions between the different types of roads. Unlike previous work, our method allows high level user control by manipulating the density and the pattern of the network. The geometry of the highways, primary and secondary roads as well as the interchanges and intersections are automatically created from the graph structure by instantiating generic parameterized models.Item Shape Analysis with Subspace Symmetries(The Eurographics Association and Blackwell Publishing Ltd., 2011) Berner, Alexander; Wand, Michael; Mitra, Niloy J.; Mewes, Daniel; Seidel, Hans-Peter; M. Chen and O. DeussenWe address the problem of partial symmetry detection, i.e., the identification of building blocks a complex shape is composed of. Previous techniques identify parts that relate to each other by simple rigid mappings, similarity transforms, or, more recently, intrinsic isometries. Our approach generalizes the notion of partial symmetries to more general deformations. We introduce subspace symmetries whereby we characterize similarity by requiring the set of symmetric parts to form a low dimensional shape space. We present an algorithm to discover subspace symmetries based on detecting linearly correlated correspondences among graphs of invariant features. We evaluate our technique on various data sets. We show that for models with pronounced surface features, subspace symmetries can be found fully automatically. For complicated cases, a small amount of user input is used to resolve ambiguities. Our technique computes dense correspondences that can subsequently be used in various applications, such as model repair and denoising.Item Preface and Table of Contents(The Eurographics Association and Blackwell Publishing Ltd., 2011) Ravi Ramamoorthi and Erik ReinhardItem Prostate Cancer Visualization from MR Imagery and MR Spectroscopy(The Eurographics Association and Blackwell Publishing Ltd., 2011) Marino, Joseph; Kaufman, Arie; H. Hauser, H. Pfister, and J. J. van WijkProstate cancer is one of the most prevalent cancers among males, and the use of magnetic resonance imaging (MRI) has been suggested for its detection. A framework is presented for scoring and visualizing various MR data in an efficient and intuitive manner. A classification method is introduced where a cumulative score volume is created which takes into account each of three acquisition types. This score volume is integrated into a volume rendering framework which allows the user to view the prostate gland, the multi-modal score values, and the sur- rounding anatomy. A visibility persistence mode is introduced to automatically avoid full occlusion of a selected score and indicate overlaps. The use of GPU-accelerated multi-modal single-pass ray casting provides an inter- active experience. User driven importance rendering allows the user to gain insight into the data and can assist in localization of the disease and treatment planning. We evaluate our results against pathology and radiologists' determinations.Item Fruit Senescence and Decay Simulation(The Eurographics Association and Blackwell Publishing Ltd., 2011) Jr., Joseph T. Kider; Raja, Samantha; Badler, Norman I.; M. Chen and O. DeussenAging and imperfections provide important visual cues for realism. We present a novel physically-based approach for simulating the biological aging and decay process in fruits. This method simulates interactions between multiple processes. Our biologically-derived, reaction-diffusion model generates growth patterns for areas of fungal and bacterial infection. Fungal colony spread and propagation is affected by both bacterial growth and nutrient depletion. This process changes the physical properties of the surface of the fruit as well as its internal volume substrate. The fruit is physically simulated with parameters such as skin thickness and porosity, water content, flesh rigidity, ambient temperature, humidity, and proximity to other surfaces. Our model produces a simulation that closely mirrors the progression of decay in real fruits under similar parameterized conditions. Additionally, we provide a tool that allows artists to customize the input of the program to produce generalized fruit simulations.Item A Framework for Exploring Multidimensional Data with 3D Projections(The Eurographics Association and Blackwell Publishing Ltd., 2011) Poco, Jorge; Etemadpour, Ronak; Paulovich, F. V.; Long, T. V.; Rosenthal, P.; Oliveira, M. C. F.; Linsen, Lars; Minghim, R.; H. Hauser, H. Pfister, and J. J. van WijkVisualization of high-dimensional data requires a mapping to a visual space. Whenever the goal is to preserve similarity relations a frequent strategy is to use 2D projections, which afford intuitive interactive exploration, e.g., by users locating and selecting groups and gradually drilling down to individual objects. In this paper, we propose a framework for projecting high-dimensional data to 3D visual spaces, based on a generalization of the Least- Square Projection (LSP). We compare projections to 2D and 3D visual spaces both quantitatively and through a user study considering certain exploration tasks. The quantitative analysis confirms that 3D projections outperform 2D projections in terms of precision. The user study indicates that certain tasks can be more reliably and confidently answered with 3D projections. Nonetheless, as 3D projections are displayed on 2D screens, interaction is more difficult. Therefore, we incorporate suitable interaction functionalities into a framework that supports 3D transformations, predefined optimal 2D views, coordinated 2D and 3D views, and hierarchical 3D cluster definition and exploration. For visually encoding data clusters in a 3D setup, we employ color coding of projected data points as well as four types of surface renderings. A second user study evaluates the suitability of these visual encodings. Several examples illustrate the framework's applicability for both visual exploration of multidimensional abstract (non-spatial) data as well as the feature space of multi-variate spatial data.Item Context‐Based Coding of Adaptive Multiresolution Meshes(The Eurographics Association and Blackwell Publishing Ltd., 2011) Tycowicz, Christoph von; Kälberer, Felix; Polthier, Konrad; Eduard Groeller and Holly RushmeierMultiresolution meshes provide an efficient and structured representation of geometric objects. To increase the mesh resolution only at vital parts of the object, adaptive refinement is widely used. We propose a lossless compression scheme for these adaptive structures that exploits the parent–child relationships inherent to the mesh hierarchy. We use the rules that correspond to the adaptive refinement scheme and store bits only where some freedom of choice is left, leading to compact codes that are free of redundancy. Moreover, we extend the coder to sequences of meshes with varying refinement. The connectivity compression ratio of our method exceeds that of state‐of‐the‐art coders by a factor of 2–7. For efficient compression of vertex positions we adapt popular wavelet‐based coding schemes to the adaptive triangular and quadrangular cases to demonstrate the compatibility with our method. Akin to state‐of‐the‐art coders, we use a zerotree to encode the resulting coefficients. Using improved context modelling we enhanced the zerotree compression, cutting the overall geometry data rate by 7% below those of the successful Progressive Geometry Compression. More importantly, by exploiting the existing refinement structure we achieve compression factors that are four times greater than those of coders which can handle irregular meshes.Item Deformable 3D Shape Registration Based on Local Similarity Transforms(The Eurographics Association and Blackwell Publishing Ltd., 2011) Papazov, Chavdar; Burschka, Darius; Mario Botsch and Scott SchaeferIn this paper, a new method for deformable 3D shape registration is proposed. The algorithm computes shape transitions based on local similarity transforms which allows to model not only as-rigid-as-possible deformations but also local and global scale. We formulate an ordinary differential equation (ODE) which describes the transition of a source shape towards a target shape. We assume that both shapes are roughly pre-aligned (e.g., frames of a motion sequence). The ODE consists of two terms. The first one causes the deformation by pulling the source shape points towards corresponding points on the target shape. Initial correspondences are estimated by closestpoint search and then refined by an efficient smoothing scheme. The second term regularizes the deformation by drawing the points towards locally defined rest positions. These are given by the optimal similarity transform which matches the initial (undeformed) neighborhood of a source point to its current (deformed) neighborhood. The proposed ODE allows for a very efficient explicit numerical integration. This avoids the repeated solution of large linear systems usually done when solving the registration problem within general-purpose non-linear optimization frameworks. We experimentally validate the proposed method on a variety of real data and perform a comparison with several state-of-the-art approaches.Item Hatching for Motion Picture Production(The Eurographics Association and Blackwell Publishing Ltd., 2011) Umenhoffer, Tamás; Szécsi, László; Szirmay-Kalos, László; M. Chen and O. DeussenThis paper presents a hatching algorithm which - while also allows for an implementation in real-time - is integrated into the production pipeline of computer generated motion picture. Motion picture production pipelines impose special functional and quality requirements. From the functional point of view, the stages of modeling, 3D rendering, and compositing form a pipeline without feed-back, and frames are rendered independently, possibly on different computers. Thus, no temporal data can be shared between them while flicker free animation needs to be generated. Quality requirements can be grasped as that of dual consistency: the generated hatching must consistently follow object movement and deformation, and, at the same time, it should have a consistent pattern and density in image-space to provide the hand-crafted look. In order to meet both requirements, we apply a particle based method and develop an image-space density control mechanism using rejection sampling and low- discrepancy sequences. We also discuss the decomposition of rendering tasks according to the main stages of the production pipeline and demonstrate how the artist can define the illustration style in a convenient way.Item SQuad: Compact Representation for Triangle Meshes(The Eurographics Association and Blackwell Publishing Ltd., 2011) Gurung, Topraj; Laney, Daniel; Lindstrom, Peter; Rossignac, Jarek; M. Chen and O. DeussenThe SQuad data structure represents the connectivity of a triangle mesh by its "S table" of about 2 rpt (integer references per triangle). Yet it allows for a simple implementation of expected constant-time, random-access operators for traversing the mesh, including in-order traversal of the triangles incident upon a vertex. SQuad is more compact than the Corner Table (CT), which stores 6 rpt, and than the recently proposed SOT, which stores 3 rpt. However, in-core access is generally faster in CT than in SQuad, and SQuad requires rebuilding the S table if the connectivity is altered. The storage reduction and memory coherence opportunities it offers may help to reduce the frequency of page faults and cache misses when accessing elements of a mesh that does not fit in memory. We provide the details of a simple algorithm that builds the S table and of an optimized implementation of the SQuad operators.Item Review: Kd-tree Traversal Algorithms for Ray Tracing(The Eurographics Association and Blackwell Publishing Ltd., 2011) Hapala, M.; Havran, V.; Eduard Groeller and Holly RushmeierIn this paper we review the traversal algorithms for kd-trees for ray tracing. Ordinary traversal algorithms such as sequential, recursive, and those with neighbour-links have different limitations, which led to several new developments within the last decade. We describe algorithms exploiting ray coherence and algorithms designed with specific hardware architecture limitations such as memory latency and consumption in mind. We also discuss the robustness of traversal algorithms as one issue that has been neglected in previous research.Item The Natural 3D Spiral(The Eurographics Association and Blackwell Publishing Ltd., 2011) Harary, Gur; Tal, Ayellet; M. Chen and O. DeussenLogarithmic spirals are ubiquitous in nature. This paper presents a novel mathematical definition of a 3D logarithmic spiral, which provides a proper description of objects found in nature. To motivate our work, we scanned spiral-shaped objects and studied their geometric properties. We consider the extent to which the existing 3D definitions capture these properties. We identify a property that is shared by the objects we investigated and is not satisfied by the existing 3D definitions. This leads us to present our definition in which both the radius of curvature and the radius of torsion change linearly along the curve. We prove that our spiral satisfies several desirable properties, including invariance to similarity transformations, smoothness, symmetry, extensibility, and roundness. Finally, we demonstrate the utility of our curves in the modeling of several animal structures.