Implicit fitting of point cloud data using radial hermite basis functions

We describe a new technique for fitting noisy scattered point cloud data. The fitting surface is determined as zero level isosurface of a trivariate model which is an implicit least squares fit of the data based upon Radial Hermite Operators (RHO). We illustrate the value of these new techniques with several diverse applications.     

Direct isosurface visualization of hex-based high-order geometry and attribute representations

In this paper, we present a novel isosurface visualization technique that guarantees the accurate visualization of isosurfaces with complex attribute data defined on (un)structured (curvi)linear hexahedral grids. Isosurfaces of high-order hexahedral-based finite element solutions on both uniform grids (including MRI and CT scans) and more complex geometry representing a domain of interest that can be rendered using our algorithm. Additionally, our technique can be used to directly visualize solutions and attributes in isogeometric analysis, an area based on trivariate high-order NURBS (Non-Uniform Rational B-splines) geometry and attribute representations for the analysis. Furthermore, our technique can be used to visualize isosurfaces of algebraic functions. Our approach combines subdivision and numerical root finding to form a robust and efficient isosurface visualization algorithm that does not miss surface features, while finding all intersections between a view frustum and desired isosurfaces. This allows the use of view-independent transparency in the rendering process. We demonstrate our technique through a straightforward CPU implementation on both complex-structured and complex-unstructured geometries with high-order simulation solutions, isosurfaces of medical data sets, and isosurfaces of algebraic functions.     

Interactive direct rendering of trivariate B-spline scalarfunctions

This paper presents a direct rendering paradigm of trivariate B-spline functions that is able to incrementally update complex volumetric data sets in the order of millions of coefficients at interactive rates of several frames per second on modern workstations. This incremental rendering scheme can hence be employed in modeling sessions of volumetric trivariate functions, offering interactive volumetric sculpting capabilities. The rendering is conducted from a fixed viewpoint and in two phases. The first, preprocessing stage accumulates the effect that the coefficients of the trivariate function have on the pixels in the image. This preprocessing stage is conducted offline and only once per trivariate and viewing direction. The second stage conducts the actual rendering of the trivariate functions. As an example, during a volumetric sculpting operation, the artist can sculpt the volume and get a displayed feedback, in interactive rates     

Constructive sculpting of heterogeneous volumetric objects using trivariate B-splines

This paper deals with modeling heterogeneous volumetric objects as point sets with attributes using trivariate B-splines. In contrast to homogeneous volumes with uniform distribution of material and other properties, a heterogeneous volumetric object has a number of variable attributes assigned at each point. An attribute is a mathematical model of an object property of an arbitrary nature (material, photometric, physical, statistical, etc.). In our approach, the function representation (FRep) is used as the basic model for both object geometry and attributes represented independently using real-valued scalar functions of point coordinates. While FRep directly defines object geometry, for an attribute it specifies a space partition used to define the attribute function. We propose a volume sculpting scheme with multiresolution capability based on trivariate B-spline functions to define both object geometry and its attributes. A new trivariate B-spline primitive is proposed that can be used as a leaf in an FRep constructive tree. An interactive volume modeler based on trivariate B-splines and other simple primitives is described, with a real-time repolygonization of the surface during modeling. We illustrate that the space partition obtained in the modeling process can be applied to define attributes for the objects with an arbitrary geometry model such as BRep or homogeneous volume models.     

Isosurfaces Over Simplicial Partitions of Multiresolution Grids

We provide a simple method that extracts an isosurface that is manifold and intersection‐free from a function over an arbitrary octree. Our method samples the function dual to minimal edges, faces, and cells, and we show how to position those samples to reconstruct sharp and thin features of the surface. Moreover, we describe an error metric designed to guide octree expansion such that flat regions of the function are tiled with fewer polygons than curved regions to create an adaptive polygonalization of the isosurface. We then show how to improve the quality of the triangulation by moving dual vertices to the isosurface and provide a topological test that guarantees we maintain the topology of the surface. While we describe our algorithm in terms of extracting surfaces from volumetric functions, we also show that our algorithm extends to generating manifold level sets of co‐dimension 1 of functions of arbitrary dimension.     

Adaptive extraction and visualization of silhouette curves from volumetric datasets

An algorithm for silhouette extraction from volumetric data is presented. Trivariate tensor product B-spline functions are used to represent the data. An offline phase that arranges the data in a lookup table is employed to improve the computation time during an interactive session. A subdivision scheme is employed to extract the silhouette curves from an implicit trivariate B-spline function. The produced results are smooth, high-quality silhouette curves when compared to voxel-based silhouette extraction schemes.     

A method for constructing trivariate nonseparable compactly supported orthogonal wavelets

We first introduce trivariate multiresolution analysis and trivariate orthogonal wavlets. We then give a method for constructing a class of trivariate nonseparable compactly supported orthogonal scaling functions and the related wavelets. Finally, we study the regularity of these wavelets. We can get arbitrarily smooth trivariate orthogonal wavelets.     

基于距离倒数加权法的等值面绘制简化算法

对常用的几种等值面绘制算法进行了分析,考查了其计算的复杂度,提出一种基于距离倒数加权的简易算法.该算法的基本思想是:利用计算机图像的像素离散性,结合实际工程应用上有一些情况中采样点位置稳定不变的特点,不需要先生成等值线,而是逐一扫描所有像素,以简单的函数计算其等值面彩色值.通过与已知曲面函数的理想等值面对比分析表明,该算法在采样点达到一定密度时拟合较好.给出了主要数据结构和算法的C语言实现.     

Particle systems for efficient and accurate high-order finite element visualization

Visualization has become an important component of the simulation pipeline, providing scientists and engineers a visual intuition of their models. Simulations that make use of the high-order finite element method for spatial subdivision, however, present a challenge to conventional isosurface visualization techniques. High-order finite element isosurfaces are often defined by basis functions in reference space, which give rise to a world-space solution through a coordinate transformation, which does not necessarily have a closed-form inverse. Therefore, world-space isosurface rendering methods such as marching cubes and ray tracing must perform a nested root finding, which is computationally expensive. We thus propose visualizing these isosurfaces with a particle system. We present a framework that allows particles to sample an isosurface in reference space, avoiding the costly inverse mapping of positions from world space when evaluating the basis functions. The distribution of particles across the reference space isosurface is controlled by geometric information from the world-space isosurface such as the surface gradient and curvature. The resulting particle distributions can be distributed evenly or adapted to accommodate world-space surface features. This provides compact, efficient, and accurate isosurface representations of these challenging data sets.     

Constructing Isosurfaces from 3D Data Sets Taking Account of Depth Sorting of Polyhedra

Creating and rendering intermediate geometric primitives is one of the approaches to visualisze data sets in 3D space.Some algorithms have been developed to construct isosurface from uniformly distributed 3D data sets.These algorithms assume that the function value varies linearly along edges of each cell.But to irregular 3D data sets,this assumption is inapplicable.Moreover,the detth sorting of cells is more complicated for irregular data sets,which is indispensable for generating isosurface images or semitransparent isosurface images,if Z-buffer method is not adopted.In this paper,isosurface models based on the assumption that the function value has nonlinear distribution within a tetrahedron are proposed.The depth sorting algorithm and data structures are developed for the irregular data sets in which cells may be subdivided into tetrahedra.The implementation issues of this algorithm are discussed and experimental results are shown to illustrate potentials of this technique.     

On the fractal dimension of isosurfaces

A (3D) scalar grid is a regular n1 x n2 x n3 grid of vertices where each vertex v is associated with some scalar value sv. Applying trilinear interpolation, the scalar grid determines a scalar function g where g(v) = sv for each grid vertex v. An isosurface with isovalue σ is a triangular mesh which approximates the level set g(-1)(σ). The fractal dimension of an isosurface represents the growth ;in the isosurface as the number of grid cubes increases. We define and discuss the fractal isosurface dimension. Plotting the fractal ;dimension as a function of the isovalues in a data set provides information about the isosurfaces determined by the data set. We present statistics on the average fractal dimension of 60 publicly available benchmark data sets. We also show the fractal dimension is highly correlated with topological noise in the benchmark data sets, measuring the topological noise by the number of connected components in the isosurface. Lastly, we present a formula predicting the fractal dimension as a function of noise and validate the formula with experimental results.     

Scalable isosurface visualization of massive datasets on commodity off-the-shelf clusters

Tomographic imaging and computer simulations are increasingly yielding massive datasets. Interactive and exploratory visualizations have rapidly become indispensable tools to study large volumetric imaging and simulation data. Our scalable isosurface visualization framework on commodity off-the-shelf clusters is an end-to-end parallel and progressive platform, from initial data access to the final display. Interactive browsing of extracted isosurfaces is made possible by using parallel isosurface extraction, and rendering in conjunction with a new specialized piece of image compositing hardware called Metabuffer. In this paper, we focus on the back end scalability by introducing a fully parallel and out-of-core isosurface extraction algorithm. It achieves scalability by using both parallel and out-of-core processing and parallel disks. It statically partitions the volume data to parallel disks with a balanced workload spectrum, and builds I/O-optimal external interval trees to minimize the number of I/O operations of loading large data from disk. We also describe an isosurface compression scheme that is efficient for progress extraction, transmission and storage of isosurfaces.     

Reconstruction of volume data with quadratic super splines

We propose a new approach to reconstruct nondiscrete models from gridded volume samples. As a model, we use quadratic trivariate super splines on a uniform tetrahedral partition. We discuss the smoothness and approximation properties of our model and compare to alternative piecewise polynomial constructions. We observe, as a nonstandard phenomenon, that the derivatives of our splines yield optimal approximation order for smooth data, while the theoretical error of the values is nearly optimal due to the averaging rules. Our approach enables efficient reconstruction and visualization of the data. As the piecewise polynomials are of the lowest possible total degree two, we can efficiently determine exact ray intersections with an isosurface for ray-casting. Moreover, the optimal approximation properties of the derivatives allow us to simply sample the necessary gradients directly from the polynomial pieces of the splines. Our results confirm the efficiency of the quasi-interpolating method and demonstrate high visual quality for rendered isosurfaces.     

Computing Contour Trees for 2D Piecewise Polynomial Functions

Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.     

On marching cubes

A characterization and classification of the isosurfaces of trilinear functions is presented. Based upon these results, a new algorithm for computing a triangular mesh approximation to isosurfaces for data given on a 3D rectilinear grid is presented. The original marching cubes algorithm is based upon linear interpolation along edges of the voxels. The asymptotic decider method is based upon bilinear interpolation on faces of the voxels. The algorithm of this paper carries this theme forward to using trilinear interpolation on the interior of voxels. The algorithm described here will produce a triangular mesh surface approximation to an isosurface which preserves the same connectivity/separation of vertices as given by the isosurface of trilinear interpolation.     

Exact and efficient computation of moments of free-form surface and trivariate based geometry

Two schemes for computing moments of free-form objects are developed and analyzed. In the first scheme, we assume that the boundary of the analyzed object is represented using parametric surfaces. In the second scheme, we represent the boundary of the object as a constant set of a trivariate function. These schemes rely on a pre-computation step which allows fast re-evaluation of the moments when the analyzed object is modified. Both schemes take advantage of a representation that is based on the B-spline blending functions.     

Trivariate Biharmonic B‐Splines

In this paper, we formulate a novel trivariate biharmonic B‐spline defined over bounded volumetric domain. The properties of bi‐Laplacian have been well investigated, but the straightforward generalization from bivariate case to trivariate one gives rise to unsatisfactory discretization, due to the dramatically uneven distribution of neighbouring knots in 3D. To ameliorate, our original idea is to extend the bivariate biharmonic B‐spline to the trivariate one with novel formulations based on quadratic programming, approximating the properties of localization and partition of unity. And we design a novel discrete biharmonic operator which is optimized more robustly for a specific set of functions for unevenly sampled knots compared with previous methods. Our experiments demonstrate that our 3D discrete biharmonic operators are robust for unevenly distributed knots and illustrate that our algorithm is superior to previous algorithms.     

Convolution surfaces for arcs and quadratic curves with a varying kernel

A convolution surface is an isosurface in a scalar field defined by convolving a skeleton, comprising of points, curves, surfaces, or volumes, with a potential function. While convolution surfaces are attractive for modeling natural phenomena and objects of complex evolving topology, the analytical evaluation of integrals of convolution models still poses some open problems. This paper presents some novel analytical convolution solutions for arcs and quadratic spline curves with a varying kernel. In addition, we approximate planar higher-degree polynomial spline curves by optimal arc splines within a prescribed tolerance and sum the potential functions of all the arc primitives to approximate the field for the entire spline curve. Published online: November 20, 2002     

Nonparametric estimation of the tree structure of a nested Archimedean copula

One of the features inherent in nested Archimedean copulas, also called hierarchical Archimedean copulas, is their rooted tree structure. A nonparametric, rank-based method to estimate this structure is presented. The idea is to represent the target structure as a set of trivariate structures, each of which can be estimated individually with ease. Indeed, for any three variables there are only four possible rooted tree structures and, based on a sample, a choice can be made by performing comparisons between the three bivariate margins of the empirical distribution of the three variables. The set of estimated trivariate structures can then be used to build an estimate of the target structure. The advantage of this estimation method is that it does not require any parametric assumptions concerning the generator functions at the nodes of the tree.     

Mesh Optimization for Polygonized Isosurfaces

In this paper, we propose a method for improvement of isosurface polygonizations. Given an initial polygonization of an isosurface, we introduce a mesh evolution process initialized by the polygonization. The evolving mesh converges quickly to its limit mesh which provides with a high quality approximation of the isosurface even if the isosurface has sharp features, boundary, complex topology. To analyze how close the evolving mesh approaches its destined isosurface, we introduce error estimators measuring the deviations of the mesh vertices from the isosurface and mesh normals from the isosurface normals. A new technique for mesh editing with isosurfaces is also proposed. In particular, it can be used for creating carving effects.