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

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

绘制数据场等值面的中点递归剖分算法

众所周知,在用Lorensen和Cline的跟踪立方体(Marching Cubes)算法绘制三维数据场等值面时会产生二义性.针对这个问题,基于divide-and-conquer的思路,提出了一个从三维数据场中抽取等值面的新算法--中点递归剖分算法,实验结果表明,该算法首先将Marching Cubes算法中会产生二义性的立方体进行递归剖分,直到不存在二义性的立方体/六面体为止;然后抽取等值面只需利用非二义性立方体模式的等值面拓扑查找表即可完成;实验结果表明,该算法简单、高效、容易实现.此外,还给出了剖分算法的正确性和收敛性的构造性证明,并简明扼要地对算法的复杂度进行了分析.     

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

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

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

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

用自适应的三线性逼近方法构造等值面

在三维空间数据场中构造等值面是科学计算可视化的有效方法，本文提出了一个新的等值面构造方法，新算法建立在对立方体面上的边有效连结的基础上，本文给出了由边连结成多边形的快速方法，详细讨论了多边形的三角化过程，然后，提出了一个自适应的三角形剖分方法，使产生的子三角形网格能满足用户规定的容差，成为等值面的更为精确的多边形逼近，最后给出了用新的算法生成的等值面图形。     

用于构造等值面的剖玢方体算法的改进及应用

本文以传统的用于构造等值的剖分立方体算法为基础，提出了算法加速的几点改进方法。给出了新的数据结构及算法，在三维算值面实时操作中有重要的意义。     

用于构造等值面的剖分立方体算法的改进及应用

本文以传统的用于构造等值面的剖分立方体（ＤｉｖｉｄｉｎｇＣｕｂｅｓ）算法为基础，提出了算法加速的几点改进方法。给出的新的数据结构及算法，在三维等值面实时操作中有重要的意义。结合所提出的算法，给出了三维图象所表示的物体的交互测量方法。最后，以医学ＣＴ和ＭＲ数据为背景，实现了上述方法。结果表明，本方法较原算法的效率有很大的提高，便于实时交互操作     

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

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

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

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

基于最近邻Marching Cubes的医学图像三维重建

在医学图像三维可视化中,移动立方体算法（Marching Cubes,MC）是面绘制的经典算法。针对MC算法计算插值点导致执行速度慢、效率不高的缺点,提出一种基于最近邻逼近的MC算法,该方法在n次等分点量化序列中寻找等值面最近邻点代替线性或非线性插值,既避免了插值的大量计算又保证了误差精度,还可改善三角面片结构。利用可视化工具开发包VTK对人体脸部和脚部CT数据集进行三维重建,实验表明改进算法明显缩短了绘制时间,提高了重建效率。     

Integration of volume decompression and out-of-core iso-surface extraction from irregular volume data

Volume datasets tend to grow larger and larger as modern technology advances, thus imposing a storage constraint on most systems. One general solution to alleviate this problem is to apply volume compression on volume datasets. However, as volume rendering is often the most important reason why a volume dataset was generated in the first place, we must take into account how a volume dataset could be efficiently rendered when it is stored in a compressed form. Our previous work [21] has shown that it is possible to perform an on-the-fly direct volume rendering from irregular volume data. In this paper, we further extend that work to demonstrate that a similar integration can also be achieved on iso-surface extraction and volume decompression for irregular volume data. In particular, our work involves a dataset decomposition process, where instead of a coordinate-based decomposition used by conventional out-of-core iso-surface extraction algorithms, we choose to use a layer-based structure. Each such layer contains a collection of tetrahedra whose associated scalar values fall within a specific range, and can be compressed independently to reduce its storage requirement. The layer structure is particularly suitable for out-of-core iso-surface extraction, where the required memory exceeds the physical memory capacity of the machine that the process is running on. Furthermore, with this work, we can perform on-the-fly iso-surface extraction during decompression, and the computation only involves the layer that contains the query value, rather than the entire dataset. Experiments show that our approach can improve the performance up to ten times when compared with the results based on traditional coordinate-based approaches.     

基于Kriging和Marching cube算法的地学3维形态模拟

地质构造的复杂性和勘查数据的不完备性,决定了对地质要素(地质体和场)的空间形态进行3维模拟是一个面临众多技术难题的艰巨任务。针对此问题,探讨了一种利用空间插值和等值面勾绘来建立地质要素的接近真实的3维可视化模型的方法。Kriging算法,由于其在揭示空间数据非均匀、各向异性分布规律方面具有良好表现,因而被用于对不完备地学数据进行空间插值,即先将分散的不规则分布的数据转换成规则分布的网格数据;再通过Marching cube算法实现由网格离散点构建光滑3维等值曲面;最后通过OpenGL接口实现等值曲面的计算机3维重绘。整个过程采用VC .net结合OpenGL编程完成。应用这种方法,可实现有限钻孔取样分析数据的矿体品位3维等值面模拟和电磁测深2维反演数据的电阻率3维等值面模拟,其模拟结果接近于传统勘探方法解释的结果,而且其效率高得多,也更加直观,证明此方法是有效的和实用的。     

基于人类视觉特性的梯度骨架标记提取算法

针对分水岭算法预处理阶段的标记提取问题,提出一种基于人类视觉特性的梯度骨架标记提取算法。通过标记梯度图像的谷点组成贯通整幅梯度图像的骨架,在不同彩色空间中根据背景亮度自动选取阈值,并从骨架中剔除大于该阈值的鞍点,使骨架离散为各自连通的小骨架群,将每个小骨架作为独立标记。实验结果表明,该算法能够解决传统算法参数选取困难的问题,在抑制分水岭算法过分割边缘的基础上获得更好的分割结果。     

Selectively meshed surface representation

Surface rendering is an important technique for volume visualization. Any surface rendering algorithm has two phases—surface generation and rendering. We present a new surface rendering algorithm, which focuses on constructing the surface in a manner that speeds up the rendering phase. The motivation behind this is to reduce the response time for surface manipulations such as interactive rotations. We utilize a MC-like (Marching Cubes) approach to calculate the intersection points and their normals for each cube. But we dynamically link the intersection points to form triangles within the cube according to the locations of the last and the next visited neighboring cubes so that a good meshed surface can be generated. The difficulty with such an approach is that thousands of special cases need to be considered. But, we have found that the occurrence of five specific configurations out of the 14 basic MC cube configurations account for over 95% of all the cubes intersected by the iso-surface in most data sets. We process cubes belonging to these five configurations in a mesh mode, and the rest are processed in a non-mesh mode. As a result, the number of special cases are reduced substantially. Then a very careful analysis of the five configurations for mesh processing leads to just 136 cases, which makes the algorithm very simple. Test results show that the rendering time is almost halved compared to the time required for the rendering of a non-meshed surface generated by MC.     

基于多尺度的Marching Cube改进算法

在医学图像三维重建中,经典的等值面重建算法Marching Cube是一种比较常用的算法。该算法具有可以在给定阈值的情况下提取任意三维数据场的等值面的优点,但因需计算大量的数据和三角面片而使得该算法速度较慢。提出了使用不同尺度的等值面重建理论,实现了一个多尺度的Marching Cube算法,经过实验对比,该算法比原Marching Cube算法具有效率高、速度快的优点。     

遥感影像道路的多点同时快速行进提取方法

研究提出了一种基于多点同时快速行进构建最短路径,提取遥感影像道路的方法。该方法依据道路灰度、梯度或边缘特征构建行进速度项,以多个道路特征点作为起始种子点,多点同时快速行进提取遥感影像最小能量图,并以起始种子点为中心点,按照最小能量值对图像区域进行划分,提取相邻区域对应起始点对行进过程中最先接触的鞍点,设定判定准则从鞍点中选取有效鞍点,剔除可能提取的错误捷径,从有效鞍点出发,沿最小能量值减小且梯度变化最快方向逆向搜索至对应起始点对提取最短路径,最终连接最短路径作为提取的道路。研究将该方法应用到ETM+、IKONOS、航空影像等遥感影像数据中,进行不同空间分辨率、不同大小、不同路网条件下道路提取的实验。结果表明该方法仅需少量的道路特征点作为先验知识,即可实现各类型道路信息的提取。提取的道路连续,无需细化、断线连接等后处理,能够实现多条道路的同时提取,具有较高的提取效率。     

Fast generation and display of iso-surface wireframes

The paper presents a method for generating and displaying wireframe approximations to surfaces of constant value (or iso-surfaces). Input to the method is a data grid, a volume decomposition with each of whose vertices is associated a scalar value. During a preprocessing phase, the method constructs a threshold-independent data structure based upon the given data grid. The data structure relates the edges of an iso-surface wireframe to the edges of the data grid, for all possible threshold values. During the subsequent rendering phase, the data structure supports efficient generation and display of the iso-surface wireframe corresponding to any selected threshold value. The technique is efficient enough to form the basis for an interactive software system for visualizing iso-surfaces.     

基于MC算法的光刻仿真微结构的三维重建

在深度光刻中为了仿真微结构的形状,需要利用三维光场分布的数据对其进行三维重建。而MC(Marching Cubes)算法是三维重建中构造等值面的代表性的方法之一。以MC算法为基础,首先介绍了如何利用MC算法来绘制三维光场数据的等值面,然后分析将等值面和边界所围成的空洞补全的方法,最后研究了如何利用有限元分析软件的参数化设计语言将生成的面模型转换成实体模型。该方法重建的几何模型不但可以用于微结构形状误差分析,而且还可方便的用于建立有限元模型,直接应用于有限元分析。     

保持特征的点云自适应网格重建

由于3维扫描点云通常存在噪音和缺失数据,提出了一种鲁棒的点云网格重建算法。对张量矩阵方法估计的点云法向进行增强特征处理,在频域中进行3维快速傅里叶变换,提取粗糙离散等值面。原始点云经梯度方向迭代移动后,过滤噪音和剔除离群点,并修补点云缺失数据。点云被自适应筛选后,利用圆球相交的方法生成新的三角形。实验表明,该算法具有快速、稳定可靠和内存消耗小的优点。