医学体数据中基于局部特征尺寸的Delaunay四面体化算法*

为了从医学体数据构建面向虚拟手术仿真系统的器官实体模型,提出一种基于局部特征尺寸的Delaunay四面体化算法。首先采用Marching Cubes算法和外存模型简化技术从体数据中得到器官等值面简化模型,提出重心射线法去除内部冗余网格,获得器官多面体表面;然后基于局部特征尺寸构建表面顶点保护球,结合Delaunay细分算法生成边界一致的初始四面体网格;最后提出基于随机扰动的空间分解法快速生成内部节点,并逐点插入到四面体网格中优化单元质量。该算法克服了Delaunay细分算法无法处理锐角输入的缺点,并从理论     

面向四面体网格生成的Delaunay refinement器官表面重建

为满足生物医学仿真系统对器官几何模型在Delaunay表面重构和四面体建模两方面的需求,提出一种面向四面体网格生成的Delaunay refinement表面重构算法.算法将从医学体数据中经过等值面提取和简化的初始表面作为输入和边界限定条件,为每个限定点计算局部特征尺寸并构建保护球,计算保护球与限定线段的交点并与限定点一起作为初始点集,生成Delaunay辅助四面体网格,引入一个迭代细分过程恢复边界,最终获得Delaunay重构表面.针对细分过程中的收敛性问题,文中给出了详细的理论证明和算法实例.此外,通过Delaunay四面体生成的对比实验表明该算法在Delaunay器官表面重构和四面体建模两方面兼具有效性和优越性.     

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

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

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

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

用鞍点保证拓扑正确的快速等值面提取技术

等值面提取是研究三维数据场可视化的有效方法。针对已有的一些等值面提取算法存在的二义性问题,提出了用鞍点保证拓扑正确的快速等值面提取算法。用二线性插值和三线性插值函数来近似计算立方体表面和内部点的值,根据立方体中面鞍点和体鞍点个数的不同,将立方体剖分成不同数目的四面体。这种剖分只和原始数据的属性有关,与给定的等值无关,因此在数据不变的情况下只需要剖分一次。最后,用分层分组的方法将四面体分类到不同组中,避免在等值面提取过程中访问那些不含有等值面的四面体,从而提高了算法的速度。该算法在等值平滑变化或是随机变化时都能保持良好的特性。     

从表面重构的体数据实现3维网格剖分

目的 针对有限元分析中网格最优化问题,提出一种改进的生成四面体网格的自组织算法。方法 该算法首先应用几何方法将三角形表面模型重新构造成规定大小的分类体数据,同时由该表面模型建立平衡八叉树,计算用以控制网格尺寸的3维数组;然后将体数据转换成邻域内不同等值面的形态一致的边界指示数组;结合改进的自组织算法和相关3维数据的插值函数,达到生成四面体网格的目的。结果 实验结果对比表明,该方法能够生成更高比例的优质四面体,增强了对扁平面体的抑制能力,同时很好地保证了边界的一致。结论 在对封闭的3维表面网格进行有限元建模时,本文算法为其提供了一种有效、可靠的途径。     

从表面重构的体数据实现三维网格剖分

针对有限元分析中网格最优化问题,本文提出一种改进的生成四面体网格的自组织算法。该算法首先应用几何方法将三角形表面模型重新构造成规定大小的分类体数据,同时由该表面模型建立平衡八叉树,计算用以控制网格尺寸的三维数组;然后将体数据转换成邻域内不同等值面的形态一致的边界指示数组;结合改进的自组织算法和相关三维数据的插值函数,达到生成四面体网格的目的。实验对比表明,该方法能够生成更高比例的优质四面体,同时很好地保证了边界的一致。在对封闭的三维表面网格进行有限元建模时,本文算法为其提供了一种有效、可靠的途径。     

硬件加速的等值面提取与绘制

图形硬件的发展为通用计算提供了新的平台.利用图形硬件的高密集和并行运算能力,将非规则四面体网格数据映射为纹理,在GPU中从每个四面体提取等值面片,并将其绘制到纹理而得到最终等值面.基于Cg着色器编程语言实现三维雷达作用范围表现的实验结果表明:该方法有效的减轻了CPU负担,提高了等值面提取速度,适于实时应用.     

医学体数据中四面体化方法的研究进展*

四面体化方法一直是网格生成研究的热点,然而将其应用于医学体数据的器官几何建模仍存在诸多难点.根据医学体数据的结构特点,首先阐述了Marching cubes重构器官表面的原理和研究新进展,然后以有限元方法为应用背景,按照体数据的两种处理方式,从基于表面建模和基于体素建模两方面进行讨论,分别研究与比较三种四面体化方法在不...     

基于二维轮廓序列的膝关节三维重建

提出了一个基于二维轮廓序列的四面体网格生成方法,用于医学图像三维几何模型重构.该方法首先对各选定的断层图像提取目标轮廓并做分支匹配等处理,然后生成各轮廓内部平面域的三角网格,最后在相邻断层之间根据三角网格连接四面体单元.该方法被应用于人体膝关节虚拟手术系统的三维几何建模,得到的膝部股骨模型包含494个节点和2 046个四面体单元,膝部脂肪模型包含2 854个节点和14011个四面体单元,这些模型被成功地应用于膝关节手术仿真,从而证明了该三维模型重建方法的可行性和有效性.     

3D finite element meshing from imaging data

This paper describes an algorithm to extract adaptive and quality 3D meshes directly from volumetric imaging data. The extracted tetrahedral and hexahedral meshes are extensively used in the finite element method (FEM). A top-down octree subdivision coupled with a dual contouring method is used to rapidly extract adaptive 3D finite element meshes with correct topology from volumetric imaging data. The edge contraction and smoothing methods are used to improve mesh quality. The main contribution is extending the dual contouring method to crack-free interval volume 3D meshing with boundary feature sensitive adaptation. Compared to other tetrahedral extraction methods from imaging data, our method generates adaptive and quality 3D meshes without introducing any hanging nodes. The algorithm has been successfully applied to constructing quality meshes for finite element calculations.     

An automatic 3D mesh generation method for domains with multiple materials

This paper describes an automatic and efficient approach to construct unstructured tetrahedral and hexahedral meshes for a composite domain made up of heterogeneous materials. The boundaries of these material regions form non-manifold surfaces. In earlier papers, we developed an octree-based isocontouring method to construct unstructured 3D meshes for a single material (homogeneous) domain with manifold boundary. In this paper, we introduce the notion of a material change edge and use it to identify the interface between two or several different materials. A novel method to calculate the minimizer point for a cell shared by more than two materials is provided, which forms a non-manifold node on the boundary. We then mesh all the material regions simultaneously and automatically while conforming to their boundaries directly from volumetric data. Both material change edges and interior edges are analyzed to construct tetrahedral meshes, and interior grid points are analyzed for proper hexahedral mesh construction. Finally, edge-contraction and smoothing methods are used to improve the quality of tetrahedral meshes, and a combination of pillowing, geometric flow and optimization techniques is used for hexahedral mesh quality improvement. The shrink set of pillowing schemes is defined automatically as the boundary of each material region. Several application results of our multi-material mesh generation method are also provided.     

Meshing of porous foam structures on the micro-scale

A semi-automatic block-structured grid generation technique for hexahedral meshing of porous open cell Kelvin foam structures for investigation of the pore scale fluid flow is presented. The performance of the algorithm is compared with a tetrahedral full automatic Delaunay meshing technique. In the first part of the paper the meshing strategies are explained. In the second part grid generation times, simulation times and the mesh quality are evaluated. For this Computational Fluid Dynamics (CFD) simulations for both a diffusion-dominated case (Re = 0.129) and a convection-dominated case (Re = 129) are carried out and analysed on four different cell resolutions of each mesh type. For the quality evaluation three different a posteriori error estimates are studied for the two mesh types on the different mesh sizes. The results are: the block-structured grid generation technique is about 10–20 times faster than the tetrahedral full automatic technique. While the mean field error estimates are comparable for both meshes, the maximum field error estimates for the block-structured meshes are only half of those for the tetrahedral meshes. Reaching simulation results of the same quality the hexahedral mesh needs about 20–40% less iterations with comparable mesh sizes. The time per iteration for the hexahedral meshes are up to 94% smaller than for the tetrahedral meshes. This makes the semi-automatic block-structured grid generation technique especially suitable for parameter studies and for the investigation of micro-scale flows in foam structures consisting of large quantities of Kelvin cells.     

Template-based finite-element mesh generation from medical images

The finite-element (FE) method is commonly used in biomedical engineering to simulate the behaviour of biological structures because of its ability to model complex shapes in a subject-specific manner. However, generating FE meshes from medical images remains a bottleneck. We present a template-based technique for semi-automatically generating FE meshes which is applicable to prospective studies of individual patients in which FE meshes must be generated from scans of the same structure taken at different points in time to study the effects of disease progression/regression. In this "template-based" meshing approach, the baseline FE (tetrahedral) volume mesh is first manually aligned with the follow-up images. The triangulated surface of the mesh is then automatically deformed to fit the imaged organ boundary. The deformed surface nodes are then smoothed using a Laplacian smoothing algorithm to correct triangle (surface nodes) distortion and thus preserve triangle quality. Finally, the internal mesh nodes are smoothed to correct distorted tetrahedral elements and thus preserve tetrahedral element quality. This template-based approach is shown to be as accurate and precise as the previous technique used by our group, while preserving element quality and volume.     

Multiresolution representation and visualization of volume data

A system to represent and visualize scalar volume data at multiple resolution is presented. The system is built on a multiresolution model based on tetrahedral meshes with scattered vertices that can be obtained from any initial dataset. The model is built off-line through data simplification techniques, and stored in a compact data structure that supports fast on-line access. The system supports interactive visualization of a representation at an arbitrary level of resolution through isosurface and projective methods. The user can interactively adapt the quality of visualization to requirements of a specific application task and to the performance of a specific hardware platform. Representations at different resolutions can be used together to further enhance interaction and performance through progressive and multiresolution rendering     

Tetrahedral finite element mesh generation from NURBS solid models

In this paper, the development and the implementation of a tetrahedral meshing algorithm for generation of finite element meshes from NURBS solid models is presented. The meshing algorithm is based on a Delaunay technique, and makes use of some spatial data structures. The algorithm is capable of generating both uniform and varying size four-node and ten-node tetrahedral meshes. The algorithm has been implemented in a building block approach as part of a software library. It has been used as a practical tool in engineering design processes. Several representative test cases illustrate the effectiveness of the automatic solid mesh generator.     

A grid-based algorithm for the generation of hexahedral element meshes

An algorithm for the generation of hexahedralelement meshes is presented. The algorithm works in two steps: first the interior of the volume is filled with a regular grid; then the boundary region is meshed by using basically twodimensional operations.The algorithm was designed for use in the fem-simulation of metal forming processes where a remeshing must be done very often. In principle, it can be used for meshing any geometry with hexahedral elements and examples of meshes for geometries arising from various applications are given. The algorithm is checked against the criteria proposed by Sabin [1] (Advances in Engineering Software, 13, 220–225).     

Adaptive extraction of time-varying isosurfaces

We present an algorithm for adaptively extracting and rendering isosurfaces from compressed time-varying volume data sets. Tetrahedral meshes defined by longest edge bisection are used to create a multiresolution representation of the volume in the spatial domain that is adapted overtime to approximate the time-varying volume. The reextraction of the isosurface at each time step is accelerated with the vertex programming capabilities of modern graphics hardware. A data layout scheme which follows the access pattern indicated by mesh refinement is used to access the volume in a spatially and temporally coherent manner. This data layout scheme allows our algorithm to be used for out-of-core visualization.