基于任意六面体单元数据场的可视化研究

任意８节点六面体单元是有限元分析中常见、且有效的体单元。为了有效地实现对任意六面体剖分结构的结果可视化,提出了基于体单元节点相关性的等值面构造算法,可简捷地确定出等值面的位置,进而得出任意剖面上的等值线,该等值面构造算法突破了以往算法中受规则立方体单元的限制,而且简单可行、实用可靠。     

移动立方体算法与移动四面体算法的对比与评估

等值面提取在标量场体数据可视化和隐函数曲面显示中具有重要应用,经典算法包括移动立方体算法和移动四面体算法,其核心是在立方体或四面体体素单元中用线性的三角面片逼近原始曲面.文中以可计算的代数曲面为例,对上述2种等值面提取算法的逼近精度、时间和空间效率等方面进行了详细的对比,为各种应用中等值面提取算法的选取提供了参考依据.     

剖面数据场中的三维表面建模

在三维表面建模技术中,Marching Cubes算法是应用最为广泛的方法之一。该算法简单高效,但与此同时,研究人员也发现它存在一些不足。在构造等值面时,Marching Cubes算法要把所有体素全部检测一遍,即使有些体素没有和等值面相交,这影响了算法效率;此外在这个过程中,Marching Cubes算法还会忽略掉一些本来在等值面上的点,降低了表面重建的精度。针对这些问题,本文对算法进行了改进。在构造等值面时,不检测空的体素以提高算法的速度,并且把一些被忽略的等值点添加进来以提高算法的精度。     

空间相关MC算法的VTK实现

移动立方体是面绘制的经典算法,但要求对所有空间所有体素进行处理,执行效率不高.通过对空间相关性进行研究,即六面体体素如果与等值面相交,则等值面一定会在该六面体的6个面的方面延续,对标准的MC算法进行改进,只处理那些与等值面相交的六面体体素.可视化工具包封装了许多常用的可视化算法,为研究人员提供了极大的便利.通过空间相关性,对VTK中已有库函数vtkMarchingCubes进行改进,提高了原有算法的执行速度,同时又扩充了VTK已有的类.     

基于间隔树的等值面提取加速算法的改进

等值面提取是体绘制算法的一个重要方面。该文对一种等值面提取加速算法的数据结构和搜索算法提出改进的方法，并用 ＭＡＴＬＡＢ语言在微机上加以实现，获得了预期的效果。     

基于医学体数据生成四面体网格的方法

为了从医学体数据直接构造四面体网格,提出一种基于栅格的网格生成算法.该算法的主要思想是从背景栅格中提取并填充代表区域边界的等值面.首先,对医学体数据进行预处理与采样,构建一个背景栅格.其次,用对偶方法从栅格提取三角表面网格,用于分段线性逼近等值面.然后,对栅格中所有位于等值面之内或与等值面相交的立方体,用预定义的模板分解成四面体单元.最后,用Laplacian平滑技术优化四面体网格.在均匀网格的基础上,研究了自适应网格生成算法,在保持网格几何精度的同时精简单元数量,以提高有限元计算效率.给出了从CT数据生成人体股骨远端四面体网格的实例,该网格模型被用于虚拟膝关节镜手术.     

对体可视化Marching Cube算法的改进

提出一个由三维数据计算等值面中点的算法,它在两方面对标准Ｍａｒｃｈｉｎｇ Ｃｕｂｅ算法进行了改进。第一个改进是：在等值面上样本点的状态依赖于它所连接的边同等值面相交的数目;第二个改进是：两相邻样本点中等值面多边形顶点被定位于中点,使得共面三角片合并为一个多边莆,减少了生成多边形的数量,提高了算法效率。     

一种新的抽取等值面的四面体分解方法

Marching Cubes算法是一种从三维数据场中抽取等值面的简单有效的算法。然而，该算法并不能保证抽取出的等值面的拓扑同三维数据场的数据保持一致，即等值面的拓扑存在二义性。解决这个问题的方法是，将三维数数据场中每一个立方体网格单元分解为五个四面体单元，从每一个四面体单元中抽取等值面。但是，在分解过程中由于分解二义义性的存在，等值面的拓扑仍然存在二义性。本文采用24-分解方法解决了这个问题，生成了拓扑正确的等值面。     

基于等值面优化重建医学图像的改进算法

医学图像可视化技术利用二维医学图像序列重建出三维模型,为医生提供了直观、全面、准确的病灶和正常组织信息.传统的方法直接采用由序列轮廓线生成的三角片来拟合曲面,重建的速度与效果均有限.为了提高医学三维图像的重建速度和效果,在对用于构造等值面的MCfMarching cubes)算法进行分析的基础上,提出一种三点线性插值法代替相邻多边形顶点的位置,并对等值面法向矢量场进行平滑,实现了目标图像的三维重建.     

利用VTK进行三维肠道重建算法的改进

肠道CT的三维重建是提高肠道疾病诊疗准确性的迫切需要。利用可视化工具包VTK并结合VC++,实现了肠道三维重建。经典三维重建Marching Cubes（简称MC）算法会产生二义性,针对常用的渐近线法消除二义性计算量大的问题,提出了一种改进的MC算法：采用线性插值法求出二义性面与等值面的交点,然后分别连接二义性面对边上的交点形成两条相交直线,最后通过判断直线交点的状态值,来唯一地确定等值线的连接方式,从而快速重建出三维肠道。实验结果表明,利用改进的MC算法比起传统MC算法,在三维重建的质量和效率上都得到了很大的提高。     

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.     

High‐quality rendering of smooth isosurfaces

Animation and visualization of rectilinear data require interpolation schemes for smooth image generation. Piecewise trilinear interpolation, the de facto standard for interpolating rectilinear data, usually leads to significant visual artifacts in the resulting imagery. These artifacts reduce the confidence in the resulting visualization and may even lead to false interpretations of the data. This paper is concerned with the generation of smooth isosurface image sequences, obtained by casting rays through the image plane and computing their intersections with an isosurface. We describe a novel solution to this problem: we replace trilinear interpolation by tricubic interpolation, smoothing out the artifacts in the images; and we simplify the ray–isosurface intersection calculations by rotating and resampling the original rectilinear data in a second rectilinear grid—a grid with one family of grid planes parallel to the image plane. Our solution significantly reduces artifacts in individual images and leads to smooth animations. Copyright © 1999 John Wiley & Sons, Ltd.     

Interactive point-based isosurface exploration and high-quality rendering

We present an efficient point-based isosurface exploration system with high quality rendering. Our system incorporates two point-based isosurface extraction and visualization methods: edge splatting and the edge kernel method. In a volume, two neighboring voxels define an edge. The intersection points between the active edges and the isosurface are used for exact isosurface representation. The point generation is incorporated in the GPU-based hardware-accelerated rendering, thus avoiding any overhead when changing the isovalue in the exploration. We call this method edge splatting. In order to generate high quality isosurface rendering regardless of the volume resolution and the view, we introduce an edge kernel method. The edge kernel upsamples the isosurface by subdividing every active cell of the volume data. Enough sample points are generated to preserve the exact shape of the isosurface defined by the trilinear interpolation of the volume data. By employing these two methods, we can achieve interactive isosurface exploration with high quality rendering.     

一种改进的MC算法

为了对等值面与子等值面进行提取和分组,在MC算法原理的基础上,提出了一种改进的等值面提取与子等值面分组算法。该算法首先将数据场分解为点、棱边、面与体元的拓扑结构;然后在整个数据场范围内求所有棱边与等值面的交点,并在面内连接交点形成面与等值面的交线,交线在体元内连接生成空间多边形;接着通过三角化各个体元内的空间多边形得到由顶点表与三角形表组成的等值面数据;最后根据三角形在顶点处的连接关系,采用种子算法对属于同一子等值面的三角形与顶点进行标记,属于同一子等值面的顶点与三角形将被存放在独立的顶点表与三角形表中。实验结果表明,该算法可以高效地实现等值面提取与子等值面的分组。     

重叠区域找重策略和插值方法的研究

介绍了重叠区域问题中常用的找重策略以及插值方法,首先在找重策略方面引入基于网格的kd树数据结构,提高了找重的效率;在插值方法研究方面详细介绍了逆距离插值方法,并引入有限单元法中的型函数思想实现双线性/三线性插值,这种基于型函数的线性插值方法具有严格二阶精度、计算简单的优点。实验结果表明这些方法是非常有效的。     

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.     

基于改进MC算法和分数阶混沌的CT图像三维重建和加密方案

在现代医疗领域的病理诊断与手术实操中,需要对CT进行三维重建实现二维图像的三维可视化以提高诊断和操作的正确性。针对目前三维重建耗时过长、精度欠佳等问题,提出了一种改进的MC算法,采用包围盒分割算法提取包含等值面的体素,有效提高了重建效率;利用三线性插值法计算等值面与体素的交点信息,从而提高了重建精度。为保障医疗信息在云存储以及网络传输的安全性,提出了一种基于分数阶Lorenz混沌的三维模型加密方案,实现了重建数据在频域的混沌加密。实验结果表明,改进的MC算法具有良好的重建效率和重建精度,提出的加密方案能有效地保护重建后的三维数据,并能抵抗穷举攻击、差分攻击和统计攻击。     

Ray-cast volume rendering accelerated by incremental trilinear interpolation and cell templates

Two related ideas for improving the speed of ray-cast volume rendering are studied in this paper. The first is an incremental algorithm for trilinear interpolation, a method commonly used in ray-cast volume rendering to calculate sample values. The incremental algorithm can expedite trilinear interpolation when many samples along a ray are located in one cell. The second is an efficient hybrid volume rendering restricted to parallel projection. In the preprocessing stage, acell template is created to store the information used by the incremental trilinear interpolation. When a cell is parallel projected, the information is retrieved from the template to compute the cell contribution. Because the algorithm with only one template may cause aliasing, an antialiasing technique exploiting multiple cell templates is proposed. With our method, ray-cast volume rendering can be accelerated considerably.     

Topological equivalence between a 3D object and the reconstruction of its digital image

Digitization is not as easy as it looks. If one digitizes a 3D object even with a dense sampling grid, the reconstructed digital object may have topological distortions and, in general, there exists no upper bound for the Hausdorff distance. This explains why so far no algorithm has been known which guarantees topology preservation. However, as we will show, it is possible to repair the obtained digital image in a locally bounded way so that it is homeomorphic and close to the 3D object. The resulting digital object is always well-composed, which has nice implications for a lot of image analysis problems. Moreover, we will show that the surface of the original object is homeomorphic to the result of the marching cubes algorithm. This is really surprising since it means that the well-known topological problems of the marching cubes reconstruction simply do not occur for digital images of r-regular objects. Based on the trilinear interpolation, we also construct a smooth isosurface from the digital image that has the same topology as the original surface. Finally, we give a surprisingly simple topology preserving reconstruction method by using overlapping balls instead of cubical voxels. This is the first approach of digitizing 3D objects which guarantees topology preservation and gives an upper bound for the geometric distortion. Since the output can be chosen as a pure voxel presentation, a union of balls, a reconstruction by trilinear interpolation, a smooth isosurface, or the piecewise linear marching cubes surface, the results are directly applicable to a huge class of image analysis algorithms. Moreover, we show how one can efficiently estimate the volume and the surface area of 3D objects by looking at their digitizations. Measuring volume and surface area of digital objects are important problems in 3D image analysis. Good estimators should be multigrid convergent, i.e., the error goes to zero with increasing sampling density. We will show that every presented reconstruction method can be used for volume estimation and we will give a solution for the much more difficult problem of multigrid-convergent surface area estimation. Our solution is based on simple counting of voxels and we are the first to be able to give absolute bounds for the surface area.