12 Dec

Robust Segmentation of Multiple Intersecting Manifolds from Unoriented Noisy Point Clouds

image-93
image-93
We present a method for extracting complex manifolds with an arbitrary number of (self-) intersections from unoriented point clouds containing large amounts of noise. Manifolds are formed in a three-step process. First, small flat neighbourhoods of all possible orientations are created around all points. Next, neighbourhoods are assembled into larger quasi-flat patches, whose overlaps give the global connectivity structure of the point cloud. Finally, curved manifolds are extracted from the patch connectivity graph via a multiple-source flood fill. The manifolds can be reconstructed into meshed surfaces using standard existing surface reconstruction methods. We demonstrate the speed and robustness of our method on several point clouds, with applications in point cloud segmentation, denoising and medial surface reconstruction.We present a method for extracting complex manifolds with an arbitrary number of (self) intersections from unoriented point clouds containing large amounts of noise. Manifolds are formed in a three step process. First, small flat neighborhoods of all possible orientations are created around all points. Next, neighborhoods are assembled into larger quasi-flat patches, whose overlaps determine the global connectivity structure of the point cloud. Finally, curved manifolds, as well as their intersection curves, are extracted from the patch connectivity graph via a multiple-source flood fill. The extracted manifolds can be straightforwardly reconstructed into polygonal surfaces using standard surface reconstruction methods.
Read more »
10 Dec

Interactive Simulation of Rigid Body Dynamics in Computer Graphics

image-94
image-94
Interactive rigid body simulation is an important part of many modern computer tools, which no authoring tool nor game engine can do without. Such high-performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems. This paper is a self contained state-of-the-art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which have evolved and matured over the past 20 years. Furthermore, the paper communicates the mathematical and theoretical details in a pedagogical manner. This paper is not only a stake in the sand on what has been done, it also seeks to give the reader deeper insights to help guide their future research.Interactive rigid body simulation is an important part of many modern computer tools, which no authoring tool nor game engine can do without. Such high performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems. This paper is a self contained state-of-the-art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which have evolved and matured over the past 20 years. Furthermore, the paper communicates the mathematical and theoretical details in a pedagogical manner.
Read more »
10 Dec

Low-Cost Subpixel Rendering for Diverse Displays

image-95
image-95
Subpixel rendering increases the apparent display resolution by taking into account the subpixel structure of a given display. In essence, each subpixel is addressed individually, allowing the underlying signal to be sampled more densely. Unfortunately, naïve subpixel sampling introduces colour aliasing, as each subpixel only displays a specific colour (usually R, G and B subpixels are used). As previous work has shown, chromatic aliasing can be reduced significantly by taking the sensitivity of the human visual system into account. In this work, we find optimal filters for subpixel rendering for a diverse set of 1D and 2D subpixel layout patterns. We demonstrate that these optimal filters can be approximated well with analytical functions. We incorporate our filters into GPU-based multi-sample anti-aliasing to yield subpixel rendering at a very low cost (1–2 ms filtering time at HD resolution). We also show that texture filtering can be adapted to perform efficient subpixel rendering. Finally, we analyse the findings of a user study we performed, which underpins the increased visual fidelity that can be achieved for diverse display layouts, by using our optimal filters.Subpixel rendering increases the apparent display resolution by taking into account the subpixel structure of a given display. In essence, each subpixel is addressed individually, allowing the underlying signal to be sampled more densely. Unfortunately, naïve subpixel sampling introduces colour aliasing, as each subpixel only displays a specific colour (usually R, G, and B subpixels are used). As previous work has shown, chromatic aliasing can be reduced significantly by taking the sensitivity of the human visual system into account. In this work, wefind optimal filters for subpixel rendering for a diverse set of 1D and 2D subpixel layout patterns.
Read more »
05 Dec

Time Line Cell Tracking for the Approximation of Lagrangian Coherent Structures with Subgrid Accuracy

image-96
image-96
Lagrangian coherent structures (LCSs) have become a widespread and powerful method to describe dynamic motion patterns in time-dependent flow fields. The standard way to extract LCS is to compute height ridges in the finite-time Lyapunov exponent field. In this work, we present an alternative method to approximate Lagrangian features for 2D unsteady flow fields that achieve subgrid accuracy without additional particle sampling. We obtain this by a geometric reconstruction of the flow map using additional material constraints for the available samples. In comparison to the standard method, this allows for a more accurate global approximation of LCS on sparse grids and for long integration intervals. The proposed algorithm works directly on a set of given particle trajectories and without additional flow map derivatives. We demonstrate its application for a set of computational fluid dynamic examples, as well as trajectories acquired by Lagrangian methods, and discuss its benefits and limitations. Lagrangian Coherent Structures (LCS) have become a widespread and powerful method to describe dynamic motion patterns in time-dependent flow fields. The standard way to extract LCS is to compute height ridges in the Finite Time Lyapunov Exponent (FTLE) field. In this work, we present an alternative method to approximate Lagrangian features for 2D unsteady flow fields that achieves subgrid accuracy without additional particle sampling. We obtain this by a geometric reconstruction of the flow map using additional material constraints for the available samples. The illustration shows four approximations of LCS at different time steps in subgrid accuracy computed from a triangular grid containing 60 times 120 sample points for a heated cylinder simulation.
Read more »
30 Nov

On Perception of Semi-Transparent Streamlines for Three-Dimensional Flow Visualization

image-97
image-97
One of the standard techniques to visualize three-dimensional flow is to use geometry primitives. This solution, when opaque primitives are used, results in high levels of occlusion, especially with dense streamline seeding. Using semi-transparent geometry primitives can alleviate the problem of occlusion. However, with semi-transparency some parts of the data set become too vague and blurry, while others are still heavily occluded. We conducted a user study that provided us with results on perceptual limits of using semi-transparent geometry primitives for flow visualization. Texture models for semi-transparent streamlines were introduced. Test subjects were shown multiple overlaying layers of streamlines and recorded how many different flow directions they were able to perceive. The user study allowed us to identify a set of top scoring textures. We discuss the results of the user study, provide guidelines on using semi-transparency for three-dimensional flow visualization and show how varying textures for different streamlines can further enhance the perception of dense streamlines. We also discuss the strategies for dealing with very high levels of occlusion. The strategies are per-pixel filtering of flow directions, when only some of the streamlines are rendered at a particular pixel, and opacity normalization, a way of altering the opacity of overlapping streamlines with the same direction. We illustrate our results with a variety of visualizations.One of the standard techniques to visualize three-dimensional flow is to use geometry primitives. This solution, when opaque primitives are used, results in high levels of occlusion, especially with dense streamline seeding. Using semi-transparent geometry primitives can alleviate the problem of occlusion. However, with semi-transparency some parts of the data set become too vague and blurry, while others are still heavily occluded. We conducted a user study that provided us with results on perceptual limits of using semi-transparent geometry primitives for flow visualization. Texture models for semi-transparent streamlines were introduced. Test subjects were shown multiple overlaying layers of streamlines and recorded how many different flow directions they were able to perceive. The user study allowed us to identify a set of top scoring textures. We discuss the results of the user study, provide guidelines on using semi-transparency for three-dimensional flow visualization and show how varying textures for different streamlines can further enhance the perception of dense streamlines. We also discuss the strategies for dealing with very high levels of occlusion. The strategies are per-pixel filtering of flow directions, when only some of the streamlines are rendered at a particular pixel, and opacity normalization, a way of altering the opacity of overlapping streamlines with the same direction. We illustrate our results with a variety of visualizations.
Read more »
30 Nov

Modelling of Non-Periodic Aggregates Having a Pile Structure

image-98
image-98
This paper presents a procedure for modelling aggregates such as piles that consist of arbitrary components. The method generates an aggregate of components that need to be accumulated, and an aggregate shape represents the surface of the target aggregate. The number of components and their positions and orientations are controlled by five parameters. The components, the aggregate shape and the parameters are the inputs for the method which involves placement and refinement steps. In the placement step, the orientation and initial position of a component are determined by a non-periodic placement such that each component overlaps its neighbours. In the refinement step, to construct a pile structure, the position of each component is adjusted by reducing the overlap.This paper presents a procedure for modelling aggregates such as piles that consist of arbitrary components. The method generates an aggregate of components that need to be accumulated, and an aggregate shape represents the surface of the target aggregate. The number of components and their positions and orientations are controlled by five parameters. The components, the aggregate shape and the parameters are the inputs for the method which involves placement and refinement steps. In the placement step, the orientation and initial position of a component are determined by a non-periodic placement such that each component overlaps its neighbours. In the refinement step, to construct a pile structure, the position of each component is adjusted by reducing the overlap.
Read more »
30 Nov

Image Space Rendering of Point Clouds Using the HPR Operator

image-99
image-99
The hidden point removal (HPR) operator introduced by Katz et al. [KTB07] provides an elegant solution for the problem of estimating the visibility of points in point samplings of surfaces. Since the method requires computing the three-dimensional convex hull of a set with the same cardinality as the original cloud, the method has been largely viewed as impractical for real-time rendering of medium to large clouds. In this paper we examine how the HPR operator can be used more efficiently by combining several image space techniques, including an approximate convex hull algorithm, cloud sampling, and GPU programming. Experiments show that this combination permits faster renderings without overly compromising the accuracy.The hidden point removal (HPR) operator introduced by Katz et al. [KTB07] provides an elegant solution for the problem of estimating the visibility of points in point samplings of surfaces. Since the method requires computing the three-dimensional convex hull of a set with the same cardinality as the original cloud, the method has been largely viewed as impractical for real-time rendering of medium to large clouds. In this paper we examine how the HPR operator can be used more efficiently by combining several image space techniques, including an approximate convex hull algorithm, cloud sampling, and GPU programming. Experiments show that this combination permits faster renderings without overly compromising the accuracy.
Read more »
22 Nov

Multi-Scale Kernels Using Random Walks

image-100
image-100
We introduce novel multi-scale kernels using the random walk framework and derive corresponding embeddings and pairwise distances. The fractional moments of the rate of continuous time random walk (equivalently diffusion rate) are used to discover higher order kernels (or similarities) between pair of points. The formulated kernels are isometry, scale and tessellation invariant, can be made globally or locally shape aware and are insensitive to partial objects and noise based on the moment and influence parameters. In addition, the corresponding kernel distances and embeddings are convergent and efficiently computable. We introduce dual Green's mean signatures based on the kernels and discuss the applicability of the multi-scale distance and embedding. Collectively, we present a unified view of popular embeddings and distance metrics while recovering intuitive probabilistic interpretations on discrete surface meshes.We introduce novel multi-scale kernels using the random walk framework and derive corresponding embeddings and pairwise distances. The fractional moments of the rate of continuous time random walk (equivalently diffusion rate) are used to discover higher order kernels (or similarities) between pair of points. The formulated kernels are isometry, scale and tessellation invariant, can be made globally or locally shape aware and are insensitive to partial objects and noise based on the moment and influence parameters. In addition, the corresponding kernel distances and embeddings are convergent and efficiently computable.
Read more »
20 Nov

Stackless Multi-BVH Traversal for CPU, MIC and GPU Ray Tracing

image-101
image-101
Stackless traversal algorithms for ray tracing acceleration structures require significantly less storage per ray than ordinary stack-based ones. This advantage is important for massively parallel rendering methods, where there are many rays in flight. On SIMD architectures, a commonly used acceleration structure is the MBVH, which has multiple bounding boxes per node for improved parallelism. It scales to branching factors higher than two, for which, however, only stack-based traversal methods have been proposed so far. In this paper, we introduce a novel stackless traversal algorithm for MBVHs with up to four-way branching. Our approach replaces the stack with a small bitmask, supports dynamic ordered traversal, and has a low computation overhead. We also present efficient implementation techniques for recent CPU, MIC (Intel Xeon Phi) and GPU (NVIDIA Kepler) architectures.Stackless traversal algorithms for ray tracing acceleration structures require significantly less storage per ray than ordinary stack-based ones. This advantage is important for massively parallel rendering methods, where there are many rays in flight. On SIMD architectures, a commonly used acceleration structure is the multi bounding volume hierarchy (MBVH), which has multiple bounding boxes per node for improved parallelism. It scales to branching factors higher than two, for which, however, only stack-based traversal methods have been proposed so far. In this paper, we introduce a novel stackless traversal algorithm for MBVHs with up to 4-way branching.
Read more »
16 Nov

Subdivision Surfaces with Creases and Truncated Multiple Knot Lines

image-102
image-102
We deal with subdivision schemes based on arbitrary degree B-splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B-splines and NURBS systems.We deal with subdivision schemes based on arbitrary degree B-splines. We focus on extraordinary knots which exhibit various levels of complexity in terms of both valency and multiplicity of knot lines emanating from such knots. The purpose of truncated multiple knot lines is to model creases which fair out. Our construction supports any degree and any knot line multiplicity and provides a modelling framework familiar to users used to B-splines and NURBS systems.
Read more »