Volume 32 (2013)

Permanent URI for this community

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

Browse

Now showing 1 - 12 of 12

An Algorithm for Random Fractal Filling of Space
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Shier, John; Bourke, Paul; Holly Rushmeier and Oliver Deussen
Computational experiments with a simple algorithm show that it is possible to fill any spatial region with a random fractalization of any shape, with a continuous range of pre‐specified fractal dimensions D. The algorithm is presented here in 1, 2 or 3 physical dimensions. The size power‐law exponent c or the fractal dimension D can be specified ab initio over a substantial range. The method creates an infinite set of shapes whose areas (lengths, volumes) obey a power law and sum to the area (length and volume) to be filled. The algorithm begins by randomly placing the largest shape and continues using random search to place each smaller shape where it does not overlap or touch any previously placed shape. The resulting gasket is a single connected object.Computational experiments with a simple algorithm show that it is possible to fill any spatial region with a random fractalization Q1 of any shape, with a continuous range of pre‐specified fractal dimensions D. The algorithm is presented here in 1, 2 or 3 physical dimensions. The size power‐law exponent c or the fractal dimension D can be specified ab initio over a substantial range. The method creates an infinite set of shapes whose areas (lengths, volumes) obey a power law and sum to the area (length and volume) to be filled.
As-Rigid-As-Possible Distance Field Metamorphosis
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Weng, Yanlin; Chai, Menglei; Xu, Weiwei; Tong, Yiying; Zhou, Kun; B. Levy, X. Tong, and K. Yin
Widely used for morphing between objects with arbitrary topology, distance field interpolation (DFI) handles topological transition naturally without the need for correspondence or remeshing, unlike surface-based interpolation approaches. However, lack of correspondence in DFI also leads to ineffective control over the morphing process. In particular, unless the user specifies a dense set of landmarks, it is not even possible to measure the distortion of intermediate shapes during interpolation, let alone control it. To remedy such issues, we introduce an approach for establishing correspondence between the interior of two arbitrary objects, formulated as an optimal mass transport problem with a sparse set of landmarks. This correspondence enables us to compute non-rigid warping functions that better align the source and target objects as well as to incorporate local rigidity constraints to perform as-rigid-as-possible DFI. We demonstrate how our approach helps achieve flexible morphing results with a small number of landmarks.
Connectivity Editing for Quad-Dominant Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Peng, Chi-Han; Wonka, Peter; Yaron Lipman and Hao Zhang
We propose a connectivity editing framework for quad-dominant meshes. In our framework, the user can edit the mesh connectivity to control the location, type, and number of irregular vertices (with more or fewer than four neighbors) and irregular faces (non-quads). We provide a theoretical analysis of the problem, discuss what edits are possible and impossible, and describe how to implement an editing framework that realizes all possible editing operations. In the results, we show example edits and illustrate the advantages and disadvantages of different strategies for quad-dominant mesh design.
Exploring Local Modifications for Constrained Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Deng, Bailin; Bouaziz, Sofien; Deuss, Mario; Zhang, Juyong; Schwartzburg, Yuliy; Pauly, Mark; I. Navazo, P. Poulin
Mesh editing under constraints is a challenging task with numerous applications in geometric modeling, industrial design, and architectural form finding. Recent methods support constraint-based exploration of meshes with fixed connectivity, but commonly lack local control. Because constraints are often globally coupled, a local modification by the user can have global effects on the surface, making iterative design exploration and refinement difficult. Simply fixing a local region of interest a priori is problematic, as it is not clear in advance which parts of the mesh need to be modified to obtain an aesthetically pleasing solution that satisfies all constraints. We propose a novel framework for exploring local modifications of constrained meshes. Our solution consists of three steps. First, a user specifies target positions for one or more vertices. Our algorithm computes a sparse set of displacement vectors that satisfies the constraints and yields a smooth deformation. Then we build a linear subspace to allow realtime exploration of local variations that satisfy the constraints approximately. Finally, after interactive exploration, the result is optimized to fully satisfy the set of constraints. We evaluate our framework on meshes where each face is constrained to be planar.
Fast and Robust Approximation of Smallest Enclosing Balls in Arbitrary Dimensions
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Larsson, Thomas; Källberg, Linus; Yaron Lipman and Hao Zhang
In this paper, an algorithm is introduced that computes an arbitrarily fine approximation of the smallest enclosing ball of a point set in any dimension. This operation is important in, for example, classification, clustering, and data mining. The algorithm is very simple to implement, gives reliable results, and gracefully handles large problem instances in low and high dimensions, as confirmed by both theoretical arguments and empirical evaluation. For example, using a CPU with eight cores, it takes less than two seconds to compute a 1:001-approximation of the smallest enclosing ball of one million points uniformly distributed in a hypercube in dimension 200. Furthermore, the presented approach extends to a more general class of input objects, such as ball sets.
Global Selection of Stream Surfaces
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Esturo, Janick Martinez; Schulze, Maik; Rössl, Christian; Theisel, Holger; I. Navazo, P. Poulin
Stream surfaces are well-known and widely-used structures for 3D flow visualization. A single surface can be sufficient to represent important global flow characteristics. Unfortunately, due to the huge space of possible stream surfaces, finding the globally most representative stream surface turns out to be a hard task that is usually performed by time-consuming manual trial and error exploration using slight modifications of seed geometries. To assist users we propose a new stream surface selection method that acts as an automatic preprocessing step before data analysis. We measure stream surface relevance by a novel surface-based quality measure that prefers surfaces where the flow is aligned with principal curvature directions. The problem of seed structure selection can then be reduced to the computation of simple minimal paths in a weighted graph spanning the domain. We apply a simulated annealing-based optimization method to find smooth seed curves of globally near-optimal stream surfaces. We illustrate the effectiveness of our method on a series of synthetic and real-world data sets.
Non-Oriented MLS Gradient Fields
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Chen, Jiazhou; Guennebaud, Gaël; Barla, Pascal; Granier, Xavier; Holly Rushmeier and Oliver Deussen
We introduce a new approach for defining continuous non-oriented gradient fields from discrete inputs, a fundamental stage for a variety of computer graphics applications such as surface or curve reconstruction, and image stylization. Our approach builds on a moving least square formalism that computes higher‐order local approximations of non‐oriented input gradients. In particular, we show that our novel isotropic linear approximation outperforms its lower‐order alternative: surface or image structures are much better preserved, and instabilities are significantly reduced. Thanks to its ease of implementation (on both CPU and GPU) and small performance overhead, we believe our approach will find a widespread use in graphics applications, as demonstrated by the variety of our results.We introduce a new approach for defining continuous non‐oriented gradient fields from discrete inputs, a fundamental stage for a variety of computer graphics applications such as surface or curve reconstruction, and image stylization. Our approach builds on a moving least square formalism that computes higher‐order local approximations of non‐oriented input gradients. In particular, we show that our novel isotropic linear approximation outperforms its lower‐order alternative: surface or image structures are much better preserved, and instabilities are significantly reduced.
Quad‐Mesh Generation and Processing: A Survey
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Bommes, David; Lévy, Bruno; Pietroni, Nico; Puppo, Enrico; Silva, Claudio; Tarini, Marco; Zorin, Denis; Holly Rushmeier and Oliver Deussen
Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semi‐regular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrisation and remeshing.Triangle meshes have been nearly ubiquitous in computer graphics, and a large body of data structures and geometry processing algorithms based on them has been developed in the literature. At the same time, quadrilateral meshes, especially semi‐regular ones, have advantages for many applications, and significant progress was made in quadrilateral mesh generation and processing during the last several years. In this survey we discuss the advantages and problems of techniques operating on quadrilateral meshes, including surface analysis and mesh quality, simplification, adaptive refinement, alignment with features, parametrization, and remeshing.
Soft Folding
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Zhu, Lifeng; Igarashi, Takeo; Mitani, Jun; B. Levy, X. Tong, and K. Yin
We introduce soft folding, a new interactive method for designing and exploring thin-plate forms. A user specifies sharp and soft folds as two-dimensional(2D) curves on a flat sheet, along with the fold magnitude and sharpness of each. Then, based on the soft folds, the system computes the three-dimensional(3D) folded shape. Internally, the system first computes a fold field, which defines local folding operations on a flat sheet. A fold field is a generalization of a discrete fold graph in origami, replacing a graph with sharp folds with a continuous field with soft folds. Next, local patches are folded independently according to the fold field. Finally, a globally folded 3D shape is obtained by assembling the locally folded patches. This algorithm computes an approximation of 3D developable surfaces with user-defined soft folds at an interactive speed. The user can later apply nonlinear physical simulation to generate more realistic results. Experimental results demonstrated that soft folding is effective for producing complex folded shapes with controllable sharpness.
Sparse Iterative Closest Point
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Bouaziz, Sofien; Tagliasacchi, Andrea; Pauly, Mark; Yaron Lipman and Hao Zhang
Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp.
Towards Multifield Scalar Topology Based on Pareto Optimality
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Huettenberger, Lars; Heine, Christian; Carr, Hamish; Scheuermann, Gerik; Garth, Christoph; B. Preim, P. Rheingans, and H. Theisel
How can the notion of topological structures for single scalar fields be extended to multifields? In this paper we propose a definition for such structures using the concepts of Pareto optimality and Pareto dominance. Given a set of piecewise-linear, scalar functions over a common simplical complex of any dimension, our method finds regions of ''consensus'' among single fields' critical points and their connectivity relations. We show that our concepts are useful to data analysis on real-world examples originating from fluid-flow simulations; in two cases where the consensus of multiple scalar vortex predictors is of interest and in another case where one predictor is studied under different simulation parameters. We also compare the properties of our approach with current alternatives.
Visualizing Robustness of Critical Points for 2D Time-Varying Vector Fields
(The Eurographics Association and Blackwell Publishing Ltd., 2013) Wang, Bei; Rosen, Paul; Skraba, Primoz; Bhatia, Harsh; Pascucci, Valerio; B. Preim, P. Rheingans, and H. Theisel
Analyzing critical points and their temporal evolutions plays a crucial role in understanding the behavior of vector fields. A key challenge is to quantify the stability of critical points: more stable points may represent more important phenomena or vice versa. The topological notion of robustness is a tool which allows us to quantify rigorously the stability of each critical point. Intuitively, the robustness of a critical point is the minimum amount of perturbation necessary to cancel it within a local neighborhood, measured under an appropriate metric. In this paper, we introduce a new analysis and visualization framework which enables interactive exploration of robustness of critical points for both stationary and time-varying 2D vector fields. This framework allows the end-users, for the first time, to investigate how the stability of a critical point evolves over time. We show that this depends heavily on the global properties of the vector field and that structural changes can correspond to interesting behavior. We demonstrate the practicality of our theories and techniques on several datasets involving combustion and oceanic eddy simulations and obtain some key insights regarding their stable and unstable features.

Browse

Browsing Volume 32 (2013) by Subject "and systems"

Results Per Page

Sort Options