Adaptive marching cubes

The marching cubes algorithm (MC) is a powerful technique for surface rendering that can produce very high-quality images. However, it is not suitable for interactive manipulation of the 3D surfaces constructed from high-resolution volume datasets in terms of both space and time. In this paper, we present an adaptive version of MC called adaptive marching cubes (AMC). It significantly reduces the number of triangles representing the surface by adapting the size of the triangles to the shape of the surface. This improves the performance of the manipulation of the 3D surfaces. A typical example with the volume dataset of size 256×256×113 shows that the number of triangles is reduced by 55%. The quality of images produced by AMC is similar to that of MC. One of the fundamental problems encountered with adaptive algorithms is thecrack problem. Cracks may be created between two neighboring cubes processed with different levels of subdivision. We solve the crack problem by patching the cracks using polygons of the smae shape as those of the cracks. We propose a simple, but complete, method by first abstracting 22 basic configurations of arbitrarily sized cracks and then reducing the handling of these configurations to a simple rule. It requires onlyO(n ²) working memory for an×n×n volume data set.     

Construction of simplified boundary surfaces from serial-sectioned metal micrographs

We present a method for extracting boundary surfaces from segmented cross-section image data. We use a constrained Potts model to interpolate an arbitrary number of region boundaries between segmented images. This produces a segmented volume from which we extract a triangulated boundary surface using well-known marching tetrahedra methods. This surface contains staircase-like artifacts and an abundance of unnecessary triangles. We describe an approach that addresses these problems with a voxel-accurate simplification algorithm that reduces surface complexity by an order of magnitude. Our boundary interpolation and simplification methods are novel contributions to the study of surface extraction from segmented cross-sections. We have applied our method to construct polycrystal grain boundary surfaces from micrographs of a sample of the metal tantalum.     

Approximating isosurfaces by guaranteed-quality triangular meshes

We describe a new method for approximating an implicit surface F by a piecewise-flat triangulated surface whose triangles are as close as possible to equilateral. The main advantage is improved mesh quality which is guaranteed for smooth surfaces. The GradNormal algorithm generates a triangular mesh that gives a piecewise-differentiable approximation of F, with angles between 35.2 and 101.5 degrees. As the mesh size approaches 0, the mesh converges to F through surfaces that are isotopic to F.     

Curvature-dependent triangulation of implicit surfaces

Implicit surfaces appear in many applications, including medical imaging, molecular modeling, computer aided design, computer graphics and finite element analysis. Despite their many advantages, implicit surfaces are difficult to render efficiently. Today's real-time graphics systems are heavily optimized for rendering triangles, so an implicit surface should be converted to a mesh of triangles before rendering. Our algorithm polyonalizes an implicit surface. The algorithm generates a mesh of close-to-equilateral triangles with sizes dependent on the local surface curvature. We assume that the implicit surface is connected and G¹ is smooth (that is, the tangent plane varies continuously over the surface). The algorithm requires an evaluator for the implicit function defined at all points in space, an evaluator for the function gradient defined at points near the surface, and a bounding box around the surface. The output of the algorithm is good for applications requiring a well-behaved triangulation, such as rendering systems and finite element partial differential equation (PDE) solvers     

Implicit modeling from polygon soup using convolution

We present a novel method for creating implicit surfaces from polygonal models. The implicit function is defined by convolving a kernel with the triangles in the polygonal model. By adopting a piecewise quartic polynomial kernel function with a finite support, we derive a convolution model that has a closed-form solution, and thus can be efficiently evaluated. The user only needs to specify an effective radius of influence to generate an implicit surface of desired closeness to the polygonal model. The resulting implicit surface is fast to evaluate, not requiring accumulating evaluation results using any hierarchical data structure, and can be efficiently ray-traced to reveal the detailed features.     

采用空间分割的平滑曲面重构算法

面绘制是科学计算可视化中一个重要的研究方向，移动立方体是实现面绘制的一个重要算法，八叉树是一种有效的表示三维物体的方法，该文在八叉树生成的基础上，提出一种基于空间分割的表面重构算法，将绘制空间分别按X轴、Y轴和Z轴进行分割，生成的树的节点个数小于等于8个，与八叉树方法相比，减少了所生成叶结点数量，再通过移动立方体算法生成三角面片。三角面片通过平滑处理，提高了图形显示质量。     

Polygonization of implicit surfaces with sharp features by edge-spinning

This paper presents an adaptive approach for polygonization of implicit surfaces. The algorithm generates a well-shaped triangular mesh with respect to a given approximation error. The error is proportional to a local surface curvature estimation. Polygonization of surfaces of high curvature, as well as surfaces with sharp features, is possible using a simple technique combined with a particle system approach. The algorithm is based on a surface tracking scheme, and it is compared with other algorithms based on a similar principle, such as the marching cube and the marching triangle algorithms.     

Real-Time Ray Tracing of Implicit Surfaces on the GPU

Compact representation of geometry using a suitable procedural or mathematical model and a ray-tracing mode of rendering fit the programmable graphics processor units (GPUs) well. Several such representations including parametric and subdivision surfaces have been explored in recent research. The important and widely applicable category of the general implicit surface has received less attention. In this paper, we present a ray-tracing procedure to render general implicit surfaces efficiently on the GPU. Though only the fourth or lower order surfaces can be rendered using analytical roots, our adaptive marching points algorithm can ray trace arbitrary implicit surfaces without multiple roots, by sampling the ray at selected points till a root is found. Adapting the sampling step size based on a proximity measure and a horizon measure delivers high speed. The sign test can handle any surface without multiple roots. The Taylor test that uses ideas from interval analysis can ray trace many surfaces with complex roots. Overall, a simple algorithm that fits the SIMD architecture of the GPU results in high performance. We demonstrate the ray tracing of algebraic surfaces up to order 50 and nonalgebraic surfaces including a Blinn's blobby with 75 spheres at better than interactive frame rates.     

隐式曲面的快速适应性多边形化算法

通过将隐式曲面多边形化过程分为“构造”和“适应性采样”两个阶段，实现了隐式曲面多边形逼近网格的适应性构造．通过基于空间延展的Marching Cubes方法得到隐式曲面较为粗糙的均匀多边形化逼近，根据曲面上的局部曲率分布，运用适应性细分规则对粗糙网格进行细分迭代，并利用梯度下降法将细分出的新顶点定位到隐式曲面上；最终得到的多边形网格是适应性的单纯复形网格，其在保持规定逼近精度的前提下，减少了冗余三角形的产生，网格质量有明显改善．该算法可用于隐式曲面的交互式可视化过程．     

Optimized surface discretization of functionally defined multi-material objects

We present in this paper an algorithm for meshing implicit surfaces based on the Delaunay triangulation of a point-set adaptively sampled on an implicit surface. To improve the quality of the resulting triangular mesh, we use at each iteration a mesh optimization algorithm with the following objectives: optimizing the connectivity, retrieving the sharp features, regularizing the triangles shapes and minimizing the approximation error. Then, we extend this algorithm in order to handle functionally defined heterogeneous object surfaces, while maintaining a good quality for the triangles’ shapes and the mesh features (geometrical sharp features and boundaries between different materials).     

隐式曲面的多分辨率法向网格逼近

法向网格是一种新型的曲面多分辨率描述方式，其中每个层次都可以表示为其前一个粗糙层次的法向偏移．文中提出一种基于法向网格表示的隐式曲面多分辨率网格逼近算法．首先通过基于空间剖分技术的多边形化算法获得隐式曲面的粗糙逼近网格，并利用网格均衡化方法对粗糙网格进行优化，消除其中的狭长三角形；然后利用法向细分规则迭代地对网格中的三角面片进行细分，并利用区间算术技术沿法向方向对隐式曲面进行逼近．最终生成的隐式曲面分片线性逼近网格为法向网格．该逼近网格为隐式曲面提供了一种多分辨率表示，网格具有细分连通性，其数据量较传统的多边形化算法所生成的网格有大幅度的压缩．该算法可用于隐式曲面的多级绘制、累进传输及相关数字几何处理．     

Texture mapping using surface flattening via multidimensionalscaling

Presents a novel technique for texture mapping on arbitrary surfaces with minimal distortion by preserving the local and global structure of the texture. The recent introduction of the fast marching method on triangulated surfaces has made it possible to compute a geodesic distance map from a given surface point in O(n lg n) operations, where n is the number of triangles that represent the surface. We use this method to design a surface flattening approach based on multi-dimensional scaling (MDS). MDS is a family of methods that map a set of points into a finite-dimensional flat (Euclidean) domain, where the only data given is the corresponding distance between every pair of points. The MDS mapping yields minimal changes of the distances between the corresponding points. We then solve an "inverse" problem and map a flat texture patch onto a curved surface while preserving the structure of the texture     

基于网格优化的隐式曲面自适应多边形化

隐式曲面多边形化是隐式曲面绘制的一种常用算法.基于网格优化的隐式曲面快速自适应多边形化算法,首先用多边形化算法生成一个粗糙的初始网格,再利用网格优化方法从网格顶点位置、规则性和网格法向三个方面对粗糙网格进行调整,最后根据网格的局部曲率用多边形细分策略细分优化后的网格.实验结果表明,该算法在网格生成速度和网格规则性上都胜于Marching Cubes的多边形化算法,恢复的隐式曲面能较好地反映形状特征.     

曲率约束的隐式曲面三角网格化

提出一种有效的隐式曲面三角网格化算法。从隐式曲面上的一个种子点开始,生成网格的边界作为扩张多边形,且该多边形最小角对应的顶点为扩张点,计算从扩张点处欲生成的三角网格,为了防止新生成的三角网格和已经存在的三角网格重叠,要进行冲突检测。在隐式曲面三角网格化的过程中,扩张多边形是不断变化的,需要重复上述步骤,直至没有扩张多边形时结束。该算法分别应用于解析隐式曲面和变分隐式曲面的三角网格化。实验结果表明,该算法不需要重新网格化的步骤,生成的三角网格具有较高的质量,且三角网格随曲率适应性变化,因此说明了该算法的有效性。     

Evolution of T-spline level sets for meshing non-uniformly sampled and incomplete data

Given a large set of unorganized point sample data, we propose a new framework for computing a triangular mesh representing an approximating piecewise smooth surface. The data may be non-uniformly distributed, noisy, and may contain holes. This framework is based on the combination of two types of surface representations, triangular meshes and T-spline level sets, which are implicit surfaces defined by refinable spline functions allowing T-junctions. Our method contains three main steps. Firstly, we construct an implicit representation of a smooth (C ² in our case) surface, by using an evolution process of T-spline level sets, such that the implicit surface captures the topology and outline of the object to be reconstructed. The initial mesh with high quality is obtained through the marching triangulation of the implicit surface. Secondly, we project each data point to the initial mesh, and get a scalar displacement field. Detailed features will be captured by the displaced mesh. Finally, we present an additional evolution process, which combines data-driven velocities and feature-preserving bilateral filters, in order to reproduce sharp features. We also show that various shape constraints, such as distance field constraints, range constraints and volume constraints can be naturally added to our framework, which is helpful to obtain a desired reconstruction result, especially when the given data contains noise and inaccuracies.     

Segment Tracing Using Local Lipschitz Bounds

We introduce Segment Tracing, a new algorithm that accelerates the classical Sphere Tracing method for computing the intersection between a ray and an implicit surface. Our approach consists in computing the Lipschitz bound locally over a segment to improve the marching step computation and accelerate the overall process. We describe the computation of the Lipschitz bound for different operators and primitives. We demonstrate that our algorithm significantly reduces the number of field function queries compared to previous methods, without the need for additional accelerating data-structures. Our method can be applied to a vast variety of implicit models ranging from hierarchical procedural objects built from complex primitives, to simulation-generated implicit surfaces created from many particles.     

Incremental Polygonization of Implicit Surfaces

This paper describes an incremental polygonization technique for implicit surfaces built from skeletal elements. Our method is dedicated to fast previewing in an interactive modeling system environment. We rely on an octree decomposition of space combined with Lipschitz conditions to recursively subdivide cells until a given level of precision is reached and converge to the implicit surface. We use a trilinear interpolation approximation of the field function to create a topologically consistent tessellation characterized by an adjacency graph. Our algorithm aims at updating the mesh locally in regions of space where changes in the potential field occurred. Therefore, we propose an octree inflating and deflating strategy to preserve the octree structure as much as possible and to avoid useless or redundant computations. Timings show that our incremental algorithm dramatically speeds up the overall polygonization process for complex objects.     

Topology correction of segmented medical images using a fast marching algorithm

We present here a new method for correcting the topology of objects segmented from medical images. Whereas previous techniques alter a surface obtained from a binary segmentation of the object, our technique can be applied directly to the image intensities of a probabilistic or fuzzy segmentation, thereby propagating the topology for all isosurfaces of the object. From an analysis of topological changes and critical points in implicit surfaces, we derive a topology propagation algorithm that enforces any desired topology using a fast marching technique. The method has been applied successfully to the correction of the cortical gray matter/white matter interface in segmented brain images and is publicly released as a software plug-in for the MIPAV package.     

壳空间剖分的隐式曲面三角化

提出了一种曲率自适应的壳空间剖分隐式曲面三角形化新方法.新方法首先采用粒子系统对隐式曲面进行采样,通过高斯曲率约束粒子的生成,使生成的网格模型在曲率大的区域具有较多的小三角形,在曲率小的区域具有较少的大三角形,从而使网格模型更好地逼近隐式曲面.新方法在每个采样粒子处沿曲面法线正负方向延伸适当距离得到两个附加点,对所有附加点进行四面体化形成对隐式曲面逼近的壳空间四面体网格,在每个壳空间四面体中抽取三角形,所有抽取的三角形拼合得到隐式曲面的三角网格表示.与以往方法相比,新的三角网格化方法更具有鲁棒性,可一次性获得高质量的三角形网格.最后给出了对常用隐式曲面进行三角化的实例比较,显示了新方法的有效性.     

Skeleton Marching-based Parallel Vascular Geometry Reconstruction Using Implicit Functions

Fast high-precision patient-specific vascular tissue and geometric structure reconstruction is an essential task for vascular tissue engineering and computer-aided minimally invasive vascular disease diagnosis and surgery. In this paper, we present an effective vascular geometry reconstruction technique by representing a highly complicated geometric structure of a vascular system as an implicit function. By implicit geometric modelling, we are able to reduce the complexity and level of difficulty of this geometric reconstruction task and turn it into a parallel process of reconstructing a set of simple short tubular-like vascular sections, thanks to the easy-blending nature of implicit geometries on combining implicitly modelled geometric forms. The basic idea behind our technique is to consider this extremely difficult task as a process of team exploration of an unknown environment like a cave. Based on this idea, we developed a parallel vascular modelling technique, called Skeleton Marching, for fast vascular geometric reconstruction. With the proposed technique, we first extract the vascular skeleton system from a given volumetric medical image. A set of sub-regions of a volumetric image containing a vascular segment is then identified by marching along the extracted skeleton tree. A localised segmentation method is then applied to each of these sub-image blocks to extract a point cloud from the surface of the short simple blood vessel segment contained in the image block. These small point clouds are then fitted with a set of implicit surfaces in a parallel manner. A high-precision geometric vascular tree is then reconstructed by blending together these simple tubular-shaped implicit surfaces using the shape-preserving blending operations. Experimental results show the time required for reconstructing a vascular system can be greatly reduced by the proposed parallel technique.