Isotopic Reconstruction of Surfaces with Boundaries

We present an algorithm for the reconstruction of a surface with boundaries (including a non-orientable one) in three dimensions from a sufficiently dense sample. It is guaranteed that the output is isotopic to the unknown sampled surface. No previously known algorithm guarantees isotopic or homeomorphic reconstruction of surfaces with boundaries. Our algorithm is surprisingly simple. It 'peels' slivers greedily from an α-complex of a sample of the surface. No other post-processing is necessary. We provide several experimental results from an implementation of our basic algorithm and also a modified version of it.     

Geodesic-Controlled Developable Surfaces for Modeling Paper Bending

We present a novel and effective method for modeling a developable surface to simulate paper bending in interactive and animation applications. The method exploits the representation of a developable surface as the envelope of rectifying planes of a curve in 3D, which is therefore necessarily a geodesic on the surface. We manipulate the geodesic to provide intuitive shape control for modeling paper bending. Our method ensures a natural continuous isometric deformation from a piece of bent paper to its flat state without any stretching. Test examples show that the new scheme is fast, accurate, and easy to use, thus providing an effective approach to interactive paper bending. We also show how to handle non-convex piecewise smooth developable surfaces.     

On Discrete Killing Vector Fields and Patterns on Surfaces

Symmetry is one of the most important properties of a shape, unifying form and function. It encodes semantic information on one hand, and affects the shape's aesthetic value on the other. Symmetry comes in many flavors, amongst the most interesting being intrinsic symmetry, which is defined only in terms of the intrinsic geometry of the shape. Continuous intrinsic symmetries can be represented using infinitesimal rigid transformations, which are given as tangent vector fields on the surface – known as Killing Vector Fields. As exact symmetries are quite rare, especially when considering noisy sampled surfaces, we propose a method for relaxing the exact symmetry constraint to allow for approximate symmetries and approximate Killing Vector Fields, and show how to discretize these concepts for generating such vector fields on a triangulated mesh. We discuss the properties of approximate Killing Vector Fields, and propose an application to utilize them for texture and geometry synthesis.     

带尖锐特征的Loop细分曲面拟合系统

实现了一个基于带尖锐特征的Loop细分曲面的三角网格拟合系统,其基本原理来自文献,但在系统设计层面对原算法作了相当大的补充和完善．整个系统框架包括尖锐特征提取、保持尖锐特征的三角网格简化、保持尖锐特征的网格平滑和拓扑优化、基于最近点策略的重采样和线性拟合系统求解．所得到的拟合曲面质量较原来的结果有了显著提高。     

Fast Parallel Construction of Smooth Surfaces from Meshes with Tri/Quad/Pent Facets

Polyhedral meshes consisting of triangles, quads, and pentagons and polar configurations cover all major sampling and modeling scenarios. We give an algorithm for efficient local, parallel conversion of such meshes to an everywhere smooth surface consisting of low‐degree polynomial pieces. Quadrilateral facets with 4‐valent vertices are ‘regular’ and are mapped to bi‐cubic patches so that adjacent bi‐cubics join C² as for cubic tensor‐product splines. The algorithm can be implemented in the vertex and geometry shaders of the GPU pipeline and does not use the fragment shader. Its implementation in DirectX 10 achieves conversion plus rendering at 659 frames per second with 42.5 million triangles per second on input of a model of 1300 facets of which 60% are not regular.     

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.     

High-Resolution Volumetric Computation of Offset Surfaces with Feature Preservation

We present a new algorithm for the efficient and reliable generation of offset surfaces for polygonal meshes. The algorithm is robust with respect to degenerate configurations and computes (self‐)intersection free offsets that do not miss small and thin components. The results are correct within a prescribed ε‐tolerance. This is achieved by using a volumetric approach where the offset surface is defined as the union of a set of spheres, cylinders, and prisms instead of surface‐based approaches that generally construct an offset surface by shifting the input mesh in normal direction. Since we are using the unsigned distance field, we can handle any type of topological inconsistencies including non‐manifold configurations and degenerate triangles. A simple but effective mesh operation allows us to detect and include sharp features (shocks) into the output mesh and to preserve them during post‐processing (decimation and smoothing). We discretize the distance function by an efficient multi‐level scheme on an adaptive octree data structure. The problem of limited voxel resolutions inherent to every volumetric approach is avoided by breaking the bounding volume into smaller tiles and processing them independently. This allows for almost arbitrarily high voxel resolutions on a commodity PC while keeping the output mesh complexity low. The quality and performance of our algorithm is demonstrated for a number of challenging examples.     

Fast and Robust Normal Estimation for Point Clouds with Sharp Features

This paper presents a new method for estimating normals on unorganized point clouds that preserves sharp features. It is based on a robust version of the Randomized Hough Transform (RHT). We consider the filled Hough transform accumulator as an image of the discrete probability distribution of possible normals. The normals we estimate corresponds to the maximum of this distribution. We use a fixed‐size accumulator for speed, statistical exploration bounds for robustness, and randomized accumulators to prevent discretization effects. We also propose various sampling strategies to deal with anisotropy, as produced by laser scans due to differences of incidence. Our experiments show that our approach offers an ideal compromise between precision, speed, and robustness: it is at least as precise and noise‐resistant as state‐of‐the‐art methods that preserve sharp features, while being almost an order of magnitude faster. Besides, it can handle anisotropy with minor speed and precision losses.     

Least Squares Subdivision Surfaces

The usual approach to design subdivision schemes for curves and surfaces basically consists in combining proper rules for regular configurations, with some specific heuristics to handle extraordinary vertices. In this paper, we introduce an alternative approach, called Least Squares Subdivision Surfaces (LS), where the key idea is to iteratively project each vertex onto a local approximation of the current polygonal mesh. While the resulting procedure haves the same complexity as simpler subdivision schemes, our method offers much higher visual quality, especially in the vicinity of extraordinary vertices. Moreover, we show it can be easily generalized to support boundaries and creases. The fitting procedure allows for a local control of the surface from the normals, making LS³ very well suited for interactive freeform modeling applications. We demonstrate our approach on diadic triangular and quadrangular refinement schemes, though it can be applied to any splitting strategies.     

Enclosing Surfaces for Point Clusters Using 3D Discrete Voronoi Diagrams

Point clusters occur in both spatial and non-spatial data. In the former context they may represent segmented particle data, in the latter context they may represent clusters in scatterplots. In order to visualize such point clusters, enclosing surfaces lead to much better comprehension than pure point renderings.
We propose a flexible system for the generation of enclosing surfaces for 3D point clusters. We developed a GPU-based 3D discrete Voronoi diagram computation that supports all surface extractions. Our system provides three different types of enclosing surfaces. By generating a discrete distance field to the point cluster and extracting an isosurface from the field, an enclosing surface with any distance to the point cluster can be generated. As a second type of enclosing surfaces, a hull of the point cluster is extracted. The generation of the hull uses a projection of the discrete Voronoi diagram of the point cluster to an isosurface to generate a polygonal surface. Generated hulls of non-convex clusters are also non-convex. The third type of enclosing surfaces can be created by computing a distance field to the hull and extracting an isosurface from the distance field. This method exhibits reduced bumpiness and can extract surfaces arbitrarily close to the point cluster without losing connectedness.
We apply our methods to the visualization of multidimensional spatial and non-spatial data. Multidimensional clusters are extracted and projected into a 3D visual space, where the point clusters are visualized. The respective clusters can also be visualized in object space when dealing with multidimensional particle data.     

Interpolatory and Mixed Loop Schemes

This paper presents a new interpolatory Loop scheme and an unified and mixed interpolatory and approximation subdivision scheme for triangular meshes. The former which is C¹ continuous as same as the modified Butterfly scheme has better effect in some complex models. The latter can be used to solve the “popping effect” problem when switching between meshes at different levels of resolution. The scheme generates surfaces coincident with the Loop subdivision scheme in the limit condition having the coefficient k equal 0. When k equal 1, it will be changed into a new interpolatory subdivision scheme. Eigen‐structure analysis demonstrates that subdivision surfaces generated using the new scheme are C¹ continuous. All these are achieved only by changing the value of a parameter k. The method is a completely simple one without constructing and solving equations. It can achieve local interpolation and solve the “popping effect” problem which are the method's advantages over the modified Butterfly scheme.     

GPU-Assisted High Quality Particle Rendering

Visualizing dynamic participating media in particle form by fully solving equations from the light transport theory is a computationally very expensive process. In this paper, we present a computational pipeline for particle volume rendering that is easily accelerated by the current GPU. To fully harness its massively parallel computing power, we transform input particles into a volumetric density field using a GPU-assisted, adaptive density estimation technique that iteratively adapts the smoothing length for local grid cells. Then, the volume data is visualized efficiently based on the volume photon mapping method where our GPU techniques further improve the rendering quality offered by previous implementations while performing rendering computation in acceptable time. It is demonstrated that high quality volume renderings can be easily produced from large particle datasets in time frames of a few seconds to less than a minute.     

A Local/Global Approach to Mesh Parameterization

We present a novel approach to parameterize a mesh with disk topology to the plane in a shape‐preserving manner. Our key contribution is a local/global algorithm, which combines a local mapping of each 3D triangle to the plane, using transformations taken from a restricted set, with a global “stitch” operation of all triangles, involving a sparse linear system. The local transformations can be taken from a variety of families, e.g. similarities or rotations, generating different types of parameterizations. In the first case, the parameterization tries to force each 2D triangle to be an as‐similar‐as‐possible version of its 3D counterpart. This is shown to yield results identical to those of the LSCM algorithm. In the second case, the parameterization tries to force each 2D triangle to be an as‐rigid‐as‐possible version of its 3D counterpart. This approach preserves shape as much as possible. It is simple, effective, and fast, due to pre‐factoring of the linear system involved in the global phase. Experimental results show that our approach provides almost isometric parameterizations and obtains more shape‐preserving results than other state‐of‐the‐art approaches. We present also a more general “hybrid” parameterization model which provides a continuous spectrum of possibilities, controlled by a single parameter. The two cases described above lie at the two ends of the spectrum. We generalize our local/global algorithm to compute these parameterizations. The local phase may also be accelerated by parallelizing the independent computations per triangle.     

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.     

Learning Line Features in 3D Geometry

Feature detection in geometric datasets is a fundamental tool for solving shape matching problems such as partial symmetry detection. Traditional techniques usually employ a priori models such as crease lines that are unspecific to the actual application. Our paper examines the idea of learning geometric features. We introduce a formal model for a class of linear feature constellations based on a Markov chain model and propose a novel, efficient algorithm for detecting a large number of features simultaneously. After a short user‐guided training stage, in which one or a few example lines are sketched directly onto the input data, our algorithm automatically finds all pieces of geometry similar to the marked areas. In particular, the algorithm is able recognize larger classes of semantically similar but geometrically varying features, which is very difficult using unsupervised techniques. In a number of experiments, we apply our technique to point cloud data from 3D scanners. The algorithm is able to detect features with very low rates of false positives and negatives and to recognize broader classes of similar geometry (such as “windows” in a building scan) even from few training examples, thereby significantly improving over previous unsupervised techniques.     

Map Displays for the Analysis of Scalar Data on Cerebral Aneurysm Surfaces

Cerebral aneurysms result from a congenital or evolved weakness of stabilizing parts of the vessel wall and potentially lead to rupture and a life-threatening bleeding. Current medical research concentrates on the integration of blood flow simulation results for risk assessment of cerebral aneurysms. Scalar flow characteristics close to the aneurysm surface, such as wall shear stress, form an important part of the simulation results. Aneurysms exhibit variable surface shapes with only few landmarks. Therefore, the exploration and mental correlation of different surface regions is a difficult task. In this paper, we present an approach for the intuitive and interactive overview visualization of near wall flow data that is mapped onto the surface of a 3D model of a cerebral aneurysm. We combine a multi-perspective 2D projection map with a standard 3D visualization and present techniques to facilitate the correlation between a 3D model and a related 2D map. An informal evaluation with 4 experienced radiologists has shown that the map-based overview actually improves the surface exploration. Furthermore, different color schemes were discussed and, as a result, an appropriate color scheme for the visual analysis of the wall shear stress is presented.     

Dynamic Sampling and Rendering of Algebraic Point Set Surfaces

Algebraic Point Set Surfaces (APSS) define a smooth surface from a set of points using local moving least‐squares (MLS) fitting of algebraic spheres. In this paper we first revisit the spherical fitting problem and provide a new, more generic solution that includes intuitive parameters for curvature control of the fitted spheres. As a second contribution we present a novel real‐time rendering system of such surfaces using a dynamic up‐sampling strategy combined with a conventional splatting algorithm for high quality rendering. Our approach also includes a new view dependent geometric error tailored to efficient and adaptive up‐sampling of the surface. One of the key features of our system is its high degree of flexibility that enables us to achieve high performance even for highly dynamic data or complex models by exploiting temporal coherence at the primitive level. We also address the issue of efficient spatial search data structures with respect to construction, access and GPU friendliness. Finally, we present an efficient parallel GPU implementation of the algorithms and search structures.     

Context-Aware Skeletal Shape Deformation

We describe a system for the animation of a skeleton-controlled articulated object that preserves the fine geometric details of the object skin and conforms to the characteristic shapes of the object specified through a set of examples. The system provides the animator with an intuitive user interface and produces compelling results even when presented with a very small set of examples. In addition it is able to generalize well by extrapolating far beyond the examples.