Mean shift denoising of point-sampled surfaces

This paper presents an anisotropic denoising/smoothing algorithm for point-sampled surfaces. Motivated by the impressive results of mean shift filtering on image denoising, we extend the concept to 3D surface smoothing by taking the vertex normal and the curvature as the range component and the vertex position as the spatial component. Then the local mode of each vertex on point-based surfaces is computed by a 3D mean shift procedure dependent on local neighborhoods that are adaptively obtained by a kdtree data structure. Clustering pieces of point-based surfaces of similar local mode provides a meaningful model segmentation. Based on the adaptively clustered neighbors, we finally apply a trilateral point filtering scheme that adjusts the position of sample points along their normal directions to successfully reduce noise from point-sampled surfaces while preserving geometric features.     

Smooth surface extraction from unstructured point-based volume data using PDEs

Smooth surface extraction using partial differential equations (PDEs) is a well-known and widely used technique for visualizing volume data. Existing approaches operate on gridded data and mainly on regular structured grids. When considering unstructured point-based volume data where sample points do not form regular patterns nor are they connected in any form, one would typically resample the data over a grid prior to applying the known PDE-based methods. We propose an approach that directly extracts smooth surfaces from unstructured point-based volume data without prior resampling or mesh generation. When operating on unstructured data one needs to quickly derive neighborhood information. The respective information is retrieved by partitioning the 3D domain into cells using a kd-tree and operating on its cells. We exploit neighborhood information to estimate gradients and mean curvature at every sample point using a four-dimensional least-squares fitting approach. Gradients and mean curvature are required for applying the chosen PDE-based method that combines hyperbolic advection to an isovalue of a given scalar field and mean curvature flow. Since we are using an explicit time-integration scheme, time steps and neighbor locations are bounded to ensure convergence of the process. To avoid small global time steps, we use asynchronous local integration. We extract the surface by successively fitting a smooth auxiliary function to the data set. This auxiliary function is initialized as a signed distance function. For each sample and for every time step we compute the respective gradient, the mean curvature, and a stable time step. With these informations the auxiliary function is manipulated using an explicit Euler time integration. The process successively continues with the next sample point in time. If the norm of the auxiliary function gradient in a sample exceeds a given threshold at some time, the auxiliary function is reinitialized to a signed distance function. After convergence of the evolution, the resulting smooth surface is obtained by extracting the zero isosurface from the auxiliary function using direct isosurface extraction from unstructured point-based volume data and rendering the extracted surface using point-based rendering methods.     

Touch-based haptics for interactive editing on point set surfaces

A modeling paradigm for haptics-based editing on point set surfaces exploits implicit surfaces, physics-based modeling, point-sampled surfaces, and haptic. We propose a point-based geometry representation that we initially designed for dynamic physics-based sculpting, but can easily generalize to other relevant applications such as data modeling and human-computer interaction. By extending the idea of the local reference domain in the moving least square (MLS) surface model to the construction of a local and global surface distance field, we naturally incorporate Hua and Qin's dynamic implicit volumetric model into our deformation of the point-based geometry, which not only facilitates topology change but also affords dynamic sculpting and deformation.     

Surface processing methods for point sets using finite elements

We present a framework for processing point-based surfaces via partial differential equations (PDEs). Our framework efficiently and effectively brings well-known PDE-based processing techniques to the field of point-based surfaces. At the core of our method is a finite element discretization of PDEs on point surfaces. This discretization is based on the local assembly of PDE-specific mass and stiffness matrices, using a local point coupling computation. Point couplings are computed using a local tangent plane construction and a local Delaunay triangulation of point neighborhoods. The definition of tangent planes relies on moment-based computation with proven scaling and stability properties. Once local stiffness matrices are obtained, we are able to easily assemble global matrices and efficiently solve the corresponding linear systems by standard iterative solvers. We demonstrate our framework by several types of PDE-based surface processing applications, such as segmentation, texture synthesis, bump mapping, and geometric fairing.     

Trimming local and global self-intersections in offset curves/surfaces using distance maps

A robust and efficient algorithm for trimming both local and global self-intersections in offset curves and surfaces is presented. Our scheme is based on the derivation of a rational distance map between the original curve or surface and its offset. By solving a bivariate polynomial equation for an offset curve or a system of three polynomial equations for an offset surface, all local and global self-intersection regions in offset curves or surfaces can be detected. The zero-set of polynomial equation(s) corresponds to the self-intersection regions. These regions are trimmed by projecting the zero-set into an appropriate parameter space. The projection operation simplifies the analysis of the zero-set, which makes the proposed algorithm numerically stable and efficient. Furthermore, in a post-processing step, a numerical marching method is employed, which provides a highly precise scheme for self-intersection elimination in both offset curves and surfaces. The effectiveness of our approach is demonstrated using several experimental results.     

基于多尺度核函数的散乱点云数据过滤方法*

针对光滑曲面采样散乱点云含有噪声及异常数据的问题,提出了一种基于多尺度核函数的过滤处理方法。采用核密度估计技术及均值漂移跟踪算法对原始点云数据进行聚类,结合局部似然函数来测度一个三维点位于采样曲面上的概率,利用过滤后的极大似然点集精确地逼近采样曲面,最后结合经典网格化算法能够获得较好的曲面重构效果。处理实例证明,该方法实用性好,不仅能够很好地抑制不同幅值的噪声,同时也能够探测到异常数据并进行自动清除。     

基于加权渐进插值的Loop 细分曲面等距逼近

等距曲面在CAD/CAM 领域有着重要的作用,由于细分曲面没有整体解 析表达式,使得计算细分曲面等距比参数曲面更加困难。针对目前已有的两种等距面逼近算 法进行了改进,利用加权渐进插值技术避免了传统细分等距逼近算法产生网格偏移的问题。 此外,提出了针对边界等距处理方案,使得等距后的细分曲面在内部和边界都均匀等距。该 方法无需求解线性方程组,具有全局和局部特性,能够处理闭网格和开网格,为Loop 细分 曲面数控加工奠定了良好的基础算法。最后给出的实例验证了算法的有效性。     

Surface extraction from multi-field particle volume data using multi-dimensional cluster visualization

Data sets resulting from physical simulations typically contain a multitude of physical variables. It is, therefore, desirable that visualization methods take into account the entire multi-field volume data rather than concentrating on one variable. We present a visualization approach based on surface extraction from multi-field particle volume data. The surfaces segment the data with respect to the underlying multi-variate function. Decisions on segmentation properties are based on the analysis of the multi-dimensional feature space. The feature space exploration is performed by an automated multi-dimensional hierarchical clustering method, whose resulting density clusters are shown in the form of density level sets in a 3D star coordinate layout. In the star coordinate layout, the user can select clusters of interest. A selected cluster in feature space corresponds to a segmenting surface in object space. Based on the segmentation property induced by the cluster membership, we extract a surface from the volume data. Our driving applications are Smoothed Particle Hydrodynamics (SPH) simulations, where each particle carries multiple properties. The data sets are given in the form of unstructured point-based volume data. We directly extract our surfaces from such data without prior resampling or grid generation. The surface extraction computes individual points on the surface, which is supported by an efficient neighborhood computation. The extracted surface points are rendered using point-based rendering operations. Our approach combines methods in scientific visualization for object-space operations with methods in information visualization for feature-space operations.     

Feature-Based Deformable Surface Detection with Self-Occlusion Reasoning

This paper presents a method for detecting a textured deformed surface in an image. It uses (wide-baseline) point matches between a template and the input image. The main contribution of the paper is twofold. First, we propose a robust method based on local surface smoothness capable of discarding outliers from the set of point matches. Our method handles large proportions of outliers (beyond 70% with less than 15% of false positives) even when the surface self-occludes. Second, we propose a method to estimate a self-occlusion resistant warp from point matches. Our method allows us to realistically retexture the input image. A pixel-based (direct) registration approach is also proposed. Bootstrapped by our robust point-based method, it finely tunes the warp parameters using the value (intensity or color) of all the visible surface pixels. The proposed framework was tested with simulated and real data. Convincing results are shown for the detection and retexturing of deformed surfaces in challenging images.     

Shape from texture for smooth curved surfaces in perspective projection

Projective distortion of surface texture observed in a perspective image can provide direct information about the shape of the underlying surface. Previous theories have generally concerned planar surfaces; this paper presents a systematic analysis of first- and second-order texture distortion cues for the case of a smooth, curved surface. In particular, several kinds of texture gradients are analyzed and are related to surface orientation and surface curvature. The local estimates obtained from these cues can be integrated to obtain a global surface shape, and it is shown that the two surfaces resulting from the well-known tilt ambiguity in the local foreshortening cue typically have qualitatively different shapes. As an example of a practical application of the analysis, a shape-from-texture algorithm based on local orientation-selective filtering is described, and some experimental results are shown.     

Nonuniform bilateral filtering for point sets and surface attributes

With the proliferation of three-dimensional (3D) scanning tools and the popularity of point sets in geometry processing and rendering, there is a need for developing smoothing techniques for the point sets and surface attributes defined at these points. In this paper, we present a nonuniform bilateral filtering (NBF) method for point sets and surface attributes based on local geometry feature. In order to adapt the algorithm to irregular sampling, local sampling density is introduced to traditional bilateral filtering, and a global approach for volume preservation is proposed. Experiments show that our approach is stable, effective and easy to use.     

Splat representation of parametric surfaces

Point and splat-based representations have become a suitable technique both for modeling and rendering complex 3D shapes. Converting other kinds of models as parametric surfaces to splat-based representations will allow to mix surface and splat-based models and to take advantage of the existing point-based rendering methods. In this work, we present an approach to convert a parametric surface into a splat-based representation. It works in parametric space, performs an adaptive sampling based on the surface curvature and a given error tolerance and uses power Voronoi diagrams. The goal is to approximate the surface with an optimized set of elliptical splats.     

Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes

Tools for the automatic decomposition of a surface into shape features will facilitate the editing, matching, texturing, morphing, compression and simplification of three-dimensional shapes. Different features, such as flats, limbs, tips, pits and various blending shapes that transition between them, may be characterized in terms of local curvature and other differential properties of the surface or in terms of a global skeletal organization of the volume it encloses. Unfortunately, both solutions are extremely sensitive to small perturbations in surface smoothness and to quantization effects when they operate on triangulated surfaces. Thus, we propose a multi-resolution approach, which not only estimates the curvature of a vertex over neighborhoods of variable size, but also takes into account the topology of the surface in that neighborhood. Our approach is based on blowing a spherical bubble at each vertex and studying how the intersection of that bubble with the surface evolves. We describe an efficient approach for computing these characteristics for a sampled set of bubble radii and for using them to identify features, based on easily formulated filters, that may capture the needs of a particular application.     

Multi-Level Partition of Unity Algebraic Point Set Surfaces

We present a multi-level partition of unity algebraic set surfaces (MPU-APSS) for surface reconstruction which can be represented by either a projection or in an implicit form. An algebraic point set surface (APSS) defines a smooth surface from a set of unorganized points using local moving least-squares (MLS) fitting of algebraic spheres. However, due to the local nature, APSS does not work well for geometry editing and modeling. Instead, our method builds an implicit approximation function for the scattered point set based on the partition of unity approach. By using an octree subdivision strategy, we first adaptively construct local algebraic spheres for the point set, and then apply weighting functions to blend together these local shape functions. Finally, we compute an error-controlled approximation of the signed distance function from the surface. In addition, we present an efficient projection operator which makes our representation suitable for point set filtering and dynamic point resampling. We demonstrate the effectiveness of our unified approach for both surface reconstruction and geometry modeling such as surface completion.     

Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes

Tools for the automatic decomposition of a surface into shape features will facilitate the editing, matching, texturing, morphing, compression and simplification of three-dimensional shapes. Different features, such as flats, limbs, tips, pits and various blending shapes that transition between them, may be characterized in terms of local curvature and other differential properties of the surface or in terms of a global skeletal organization of the volume it encloses. Unfortunately, both solutions are extremely sensitive to small perturbations in surface smoothness and to quantization effects when they operate on triangulated surfaces. Thus, we propose a multi-resolution approach, which not only estimates the curvature of a vertex over neighborhoods of variable size, but also takes into account the topology of the surface in that neighborhood. Our approach is based on blowing a spherical bubble at each vertex and studying how the intersection of that bubble with the surface evolves. We describe an efficient approach for computing these characteristics for a sampled set of bubble radii and for using them to identify features, based on easily formulated filters, that may capture the needs of a particular application.     

Point-based probabilistic surfaces to show surface uncertainty

Efficient and informative visualization of surfaces with uncertainties is an important topic with many applications in science and engineering. In these applications, the correct course of action may depend not only on the location of a boundary, but on the precision with which that location is known. Examples include environmental pollution borderline detection, oil basin edge characterization, or discrimination between cancerous and healthy tissue in medicine. We present a method for producing visualizations of surfaces with uncertainties using points as display primitives. Our approach is to render the surface as a collection of points and to displace each point from its original location along the surface normal by an amount proportional to the uncertainty at that point. This approach can be used in combination with other techniques such as pseudocoloring to produce efficient and revealing visualizations. The basic approach is sufficiently flexible to allow natural extensions; we show incorporation of expressive modulation of opacity, change of the stroke primitive, and addition of an underlying polygonal model. The method is used to visualize real and simulated tumor formations with uncertainty of tumor boundaries. The point-based technique is compared to pseudocoloring for a position estimation task in a preliminary user study.     

Efficient feature tracking of time-varying surfaces using multi-scale motion flow propagation

This paper presents a framework for efficient feature tracking of time-varying surfaces. The framework can not only capture the dynamic geometry features on time-varying surfaces, but can also compute the accurate boundaries of the geometry features. The basic idea of the proposed approach is using the multi-scale motion flow and surface matching information to propagate the feature frame on time-varying surfaces. We first define an effective multi-scale geometry motion flow for the time-varying surfaces, which efficiently propagates the geometry features along the time direction of the time-varying surfaces. By combining both the approximately invariant signature vectors and geometry motion flow vectors, we also incorporate the shape matching into the system to process feature tracking for time-varying surfaces in large deformation while with low frame sampling rate. Our approach does not depend on the topological connection of the underlying surfaces. Thus, it can process both mesh-based and point-based time-varying surfaces without vertex-to-vertex correspondence across the frames. Feature tracking results on different kinds of time-varying surfaces illustrate the efficiency and effectiveness of the proposed method.     

Modeling and rendering of points with local geometry

We present a novel rendering primitive that combines the modeling brevity of points with the rasterization efficiency of polygons. The surface is represented by a sampled collection of Differential Points (DP), each with embedded curvature information that captures the local differential geometry in the vicinity of that point. This is a more general point representation that, for the cost of a few additional bytes, packs much more information per point than the traditional point-based models. This information is used to efficiently render the surface as a collection of local geometries. To use the hardware acceleration, the DPs are quantized into 256 different types and each sampled point is approximated by the closest quantized DP and is rendered as a normal-mapped rectangle. The advantages to this representation are: 1) The surface can be represented more sparsely compared to other point primitives, 2) it achieves a robust hardware accelerated per-pixel shading - even with no connectivity information, and 3) it offers a novel point-based simplification technique that factors in the complexity of the local geometry. The number of primitives being equal, DPs produce a much better quality of rendering than a pure splat-based approach. Visual appearances being similar, DPs are about two times faster and require about 75 percent less disk space in comparison to splatting primitives.     

Fuzzy Statistics Estimation in Supporting Multidatabase Query Optimization

Advances in networking and database technology have made global information sharing a reality. Multidatabase systems (MDBSs) represent a promising approach to addressing the challenges of achieving interoperability among multiple pre-existing databases that are highly autonomous and possibly heterogeneous. The performance of an MDBS is greatly dependent on effectiveness of multidatabase query optimization (MQO). However, the unavailability of and uncertainty in the statistics essential to query optimization have made multidatabase query optimization (MQO) significantly more challenging than distributed query optimization. This research undertook to develop a fuzzy statistics-based MQO approach to addressing statistics estimation and uncertainty problems in an MDBS environment. We analyzed the statistics needed in an MDBS environment and classified them into three categories: point-based, distribution-function-based and dependency-based. Fuzzy numbers were adopted to represent point-based statistics, and a fuzzy polynomial regression method was developed for estimating distribution function-based statistics (i.e., attribute or join selectivity) from a set of subquery results. For dependency-based statistics, a fuzzy regression method was employed for estimating logical-parameter-based local cost functions. Furthermore, methods for ranking the fuzzy numbers that are fundamental to fuzzy-statistics-based MQO were also discussed. The proposed fuzzy statistics estimation methods were illustrated using examples to demonstrate its applicability in supporting MQO.