A survey on Mesh Segmentation Techniques

We present a review of the state of the art of segmentation and partitioning techniques of boundary meshes. Recently, these have become a part of many mesh and object manipulation algorithms in computer graphics, geometric modelling and computer aided design. We formulate the segmentation problem as an optimization problem and identify two primarily distinct types of mesh segmentation, namely part segmentation and surface‐patch segmentation. We classify previous segmentation solutions according to the different segmentation goals, the optimization criteria and features used, and the various algorithmic techniques employed. We also present some generic algorithms for the major segmentation techniques.     

River Networks for Instant Procedural Planets

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view‐dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly‐through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly‐throughs.     

gProximity: Hierarchical GPU‐based Operations for Collision and Distance Queries

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.     

Hierarchical Deformation of Locally Rigid Meshes

We propose a method for calculating deformations of models by deforming a low‐resolution mesh and adding details while ensuring that the details we add satisfy a set of constraints. Our method builds a low‐resolution representation of a mesh by using edge collapses and performs an as‐rigid‐as‐possible deformation on the simplified mesh. We then add back details by reversing edge‐collapses so that the shape of the mesh is locally preserved. While adding details, we deform the mesh to match the predicted positions of constraints so that constraints on the full‐resolution mesh are met. Our method operates on meshes with arbitrary triangulations, satisfies constraints over the full‐resolution mesh and converges quickly.     

Image Interpolation by Pixel-Level Data-Dependent Triangulation

We present a novel image interpolation algorithm. The algorithm can be used in arbitrary resolution enhancement, arbitrary rotation and other applications of still images in continuous space. High‐resolution images are interpolated from the pixel‐level data‐dependent triangulation of lower‐resolution images. It is simpler than other methods and is adaptable to a variety of image manipulations. Experimental results show that the new “mesh image” algorithm is as fast as the bilinear interpolation method. We assess the interpolated images' quality visually and also by the MSE measure which shows our method generates results comparable in quality to slower established methods. We also implement our method in graphics card hardware using OpenGL which leads to real‐time high‐quality image reconstruction. These features give it the potential to be used in gaming and image‐processing applications.     

Efficient GPU Data Structures and Methods to Solve Sparse Linear Systems in Dynamics Applications

We present graphics processing unit (GPU) data structures and algorithms to efficiently solve sparse linear systems that are typically required in simulations of multi‐body systems and deformable bodies. Thereby, we introduce an efficient sparse matrix data structure that can handle arbitrary sparsity patterns and outperforms current state‐of‐the‐art implementations for sparse matrix vector multiplication. Moreover, an efficient method to construct global matrices on the GPU is presented where hundreds of thousands of individual element contributions are assembled in a few milliseconds. A finite‐element‐based method for the simulation of deformable solids as well as an impulse‐based method for rigid bodies are introduced in order to demonstrate the advantages of the novel data structures and algorithms. These applications share the characteristic that a major computational effort consists of building and solving systems of linear equations in every time step. Our solving method results in a speed‐up factor of up to 13 in comparison to other GPU methods.     

Efficient Image‐Based Proximity Queries with Object‐Space Precision

We present an efficient algorithm for object‐space proximity queries between multiple deformable triangular meshes. Our approach uses the rasterization capabilities of the GPU to produce an image‐space representation of the vertices. Using this image‐space representation, inter‐object vertex‐triangle distances and closest points lying under a user‐defined threshold are computed in parallel by conservative rasterization of bounding primitives and sorted using atomic operations. We additionally introduce a similar technique to detect penetrating vertices. We show how mechanisms of modern GPUs such as mipmapping, Early‐Z and Early‐Stencil culling can optimize the performance of our method. Our algorithm is able to compute dense proximity information for complex scenes made of more than a hundred thousand triangles in real time, outperforming a CPU implementation based on bounding volume hierarchies by more than an order of magnitude.     

Reconstructing Animated Meshes from Time‐Varying Point Clouds

In this paper, we describe a novel approach for the reconstruction of animated meshes from a series of time‐deforming point clouds. Given a set of unordered point clouds that have been captured by a fast 3‐D scanner, our algorithm is able to compute coherent meshes which approximate the input data at arbitrary time instances. Our method is based on the computation of an implicit function in ?⁴ that approximates the time‐space surface of the time‐varying point cloud. We then use the four‐dimensional implicit function to reconstruct a polygonal model for the first time‐step. By sliding this template mesh along the time‐space surface in an as‐rigid‐as‐possible manner, we obtain reconstructions for further time‐steps which have the same connectivity as the previously extracted mesh while recovering rigid motion exactly. The resulting animated meshes allow accurate motion tracking of arbitrary points and are well suited for animation compression. We demonstrate the qualities of the proposed method by applying it to several data sets acquired by real‐time 3‐D scanners.     

Soft Articulated Characters with Fast Contact Handling

Fast contact handling of soft articulated characters is a computationally challenging problem, in part due to complex interplay between skeletal and surface deformation. We present a fast, novel algorithm based on a layered representation for articulated bodies that enables physically-plausible simulation of animated characters with a high-resolution deformable skin in real time. Our algorithm gracefully captures the dynamic skeleton-skin interplay through a novel formulation of elastic deformation in the pose space of the skinned surface. The algorithm also overcomes the computational challenges by robustly decoupling skeleton and skin computations using careful approximations of Schur complements, and efficiently performing collision queries by exploiting the layered representation. With this approach, we can simultaneously handle large contact areas, produce rich surface deformations, and capture the collision response of a character/s skeleton.     

Object-Space Visibility Ordering for Point-Based and Volume Rendering

This paper presents a method to accelerate algorithms that need a correct and complete visibility ordering of their data for rendering. The technique works by pre‐sorting primitives in object‐space using three lists (one for each axis: X, Y and Z), and then combining the lists using graphics hardware by rendering each list to a texture and merging the textures in the end. We validate our algorithm by applying it to the splatting technique using several types of rendering, including point‐based rendering and volume rendering. We also detail our hardware implementation for volume rendering using point sprites.     

Embedded Implicit Stand-Ins for Animated Meshes: A Case of Hybrid Modelling

In this paper, we address shape modelling problems, encountered in computer animation and computer games development that are difficult to solve just using polygonal meshes. Our approach is based on a hybrid-modelling concept that combines polygonal meshes with implicit surfaces. A hybrid model consists of an animated polygonal mesh and an approximation of this mesh by a convolution surface stand-in that is embedded within it or is attached to it. The motions of both objects are synchronised using a rigging skeleton. We model the interaction between an animated mesh object and a viscoelastic substance, which is normally represented in an implicit form. Our approach is aimed at achieving verisimilitude rather than physically based simulation. The adhesive behaviour of the viscous object is modelled using geometric blending operations on the corresponding implicit surfaces. Another application of this approach is the creation of metamorphosing implicit surface parts that are attached to an animated mesh. A prototype implementation of the proposed approach and several examples of modelling and animation with near real-time preview times are presented.     

Occlusion-Driven Scene Sorting for Efficient Culling

Image space occlusion culling is a powerful approach to reduce the rendering load of large polygonal models. However, occlusion culling is not for free; it trades overhead costs with the rendering costs of the possibly occluded geometry. Meanwhile, occlusion queries based on image space occlusion culling are supported on modern graphics hardware. However, a significant consumption of fillrate bandwidth and latency costs are associated with these queries. In this paper, we propose new techniques to reduce redundant occlusion queries. Our approach uses several "Occupancy Maps" to organize scene traversal. The respective information is accumulated efficiently by hardware‐supported asynchronous occlusion queries. To avoid redundant requests, we arrange these multiple occlusion queries according to the information of the Occupancy Maps. Our presented technique is conservative and benefits from a partial depth order of the geometry.     

Guided Image Filtering for Interactive High‐quality Global Illumination

Interactive computation of global illumination is a major challenge in current computer graphics research. Global illumination heavily affects the visual quality of generated images. It is therefore a key attribute for the perception of photo‐realistic images. Path tracing is able to simulate the physical behaviour of light using Monte Carlo techniques. However, the computational burden of this technique prohibits interactive rendering times on standard commodity hardware in high‐quality. Trying to solve the Monte Carlo integration with fewer samples results in characteristic noisy images. Global illumination filtering methods take advantage of the fact that the integral for neighbouring pixels may be very similar. Averaging samples of similar characteristics in screen‐space may approximate the correct integral, but may result in visible outliers. In this paper, we present a novel path tracing pipeline based on an edge‐aware filtering method for the indirect illumination which produces visually more pleasing results without noticeable outliers. The key idea is not to filter the noisy path traced images but to use it as a guidance to filter a second image composed from characteristic scene attributes that do not contain noise by default. We show that our approach better approximates the Monte Carlo integral compared to previous methods. Since the computation is carried out completely in screen‐space it is therefore applicable to fully dynamic scenes, arbitrary lighting and allows for high‐quality path tracing at interactive frame rates on commodity hardware.     

Non‐iterative Second‐order Approximation of Signed Distance Functions for Any Isosurface Representation

Signed distance functions (SDF) to explicit or implicit surface representations are intensively used in various computer graphics and visualization algorithms. Among others, they are applied to optimize collision detection, are used to reconstruct data fields or surfaces, and, in particular, are an obligatory ingredient for most level set methods. Level set methods are common in scientific visualization to extract surfaces from scalar or vector fields. Usual approaches for the construction of an SDF to a surface are either based on iterative solutions of a special partial differential equation or on marching algorithms involving a polygonization of the surface. We propose a novel method for a non‐iterative approximation of an SDF and its derivatives in a vicinity of a manifold. We use a second‐order algebraic fitting scheme to ensure high accuracy of the approximation. The manifold is defined (explicitly or implicitly) as an isosurface of a given volumetric scalar field. The field may be given at a set of irregular and unstructured samples. Stability and reliability of the SDF generation is achieved by a proper scaling of weights for the Moving Least Squares approximation, accurate choice of neighbors, and appropriate handling of degenerate cases. We obtain the solution in an explicit form, such that no iterative solving is necessary, which makes our approach fast.     

Anti-Aliased Lines Using Run-Masks

In recent work, a set of line digitization algorithms based on the hierarchy of runs in the digital line has unified and generalized the iterative line‐drawing algorithms used in computer graphics. In this paper, the additional structural information generated by these algorithms is leveraged to describe a run‐based approach to draw anti‐aliased line segments in which anti‐aliased run‐masks are substituted for the individual run lengths as the line is being drawn. The run‐masks are precomputed using a prefiltering technique such that one or more run‐masks are defined for each of the one or two possible run lengths that occur in the line. The run‐masks can be defined for any order or level of the hierarchy of runs in the digital line and the technique is illustrated using runs of pixels. Comparing the use of run‐masks to applying the prefiltering technique for each pixel in the line, a line of similar visual quality can be produced more efficiently. We place no restrictions on the placement of the end points of the line, which may reside anywhere on the two‐dimensional plane.     

Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

Bounding Volume Hierarchies of Slab Cut Balls

We introduce a bounding volume hierarchy based on the Slab Cut Ball. This novel type of enclosing shape provides an attractive balance between tightness of fit, cost of overlap testing, and memory requirement. The hierarchy construction algorithm includes a new method for the construction of tight bounding volumes in worst case O(n) time, which means our tree data structure is constructed in O(n log n) time using traditional top‐down building methods. A fast overlap test method between two slab cut balls is also proposed, requiring as few as 28–99 arithmetic operations, including the transformation cost. Practical collision detection experiments confirm that our tree data structure is amenable for high performance collision queries. In all the tested benchmarks, our bounding volume hierarchy consistently gives performance improvements over the sphere tree, and it is also faster than the OBB tree in five out of six scenes. In particular, our method is asymptotically faster than the sphere tree, and it also outperforms the OBB tree, in close proximity situations.     

Adaptive Surface Texture Synthesis Using Round‐Shaped Neighbourhoods

This paper presents a novel surface texture synthesis method, which is capable of producing high‐quality results by performing the synthesis within an effective multi‐resolution scheme using an adaptive texture similarity metric. Compared with related works, our method allows us to directly carry out multi‐resolution synthesis without involving complicated operations such as mesh hierarchy and partitioning on the target surface. Also, the adaptive similarity metric focuses on measuring texture properties at different scales ranging from local to global, allowing for consistency within differently‐sized texture structures. Further, with the introduced round shaped neighbourhoods, we can save considerable amount of computation for the surface texture synthesis over variable texture directions. Experimental results are provided and comparisons are made against other latest works.     

An Analysis of the In‐Out BRDF Factorization for View‐Dependent Relighting

Interactive rendering with dynamic natural lighting and changing view is a long‐standing goal in computer graphics. Recently, precomputation‐based methods for all‐frequency relighting have made substantial progress in this direction. Many of the most successful algorithms are based on a factorization of the BRDF into incident and outgoing directions, enabling each term to be precomputed independent of viewing direction, and re‐combined at run‐time. However, there has so far been no theoretical understanding of the accuracy of this factorization, nor the number of terms needed. In this paper, we conduct a theoretical and empirical analysis of the BRDF in‐out factorization. For Phong BRDFs, we obtain analytic results, showing that the number of terms needed grows linearly with the Phong exponent, while the factors correspond closely to spherical harmonic basis functions. More generally, the number of terms is quadratic in the frequency content of the BRDF along the reflected or half‐angle direction. This analysis gives clear practical guidance on the number of factors needed for a given material. Different objects in a scene can each be represented with the correct number of terms needed for that particular BRDF, enabling both accuracy and interactivity.