基于夹角变化趋势的多边形自动搜索和生成算法

利用左转算法生成多边形是GIS中面域组织和拓扑关系建立的常用算法。根据算法规则,对于由顺时针方向和逆时针方向建立的多边形都可以生成多边形文件,这就会产生一些重复多边形和无效的多边形。为此,提出了基于夹角变化趋势判断多边形搜索方向的算法,根据左转或右转算法得到的点组顺序,分别计算由起始点出发的弧段的方位角,根据相邻弧段夹角的和来判断多边形的搜索方向,实现了每一多边形都是由左转算法生成,完成了多边形的自动建立。该算法有效地判断了多边形的搜索方向,避免了无效多边形的生成。     

连接不相交线段成简单多边形(链)的算法及其实现

提出一个如何连接平面上n条线段与一个简单多边形或者简单多边形链的实际问题，并证明了连接平面上线段集S成一简单多边形链的一个充分条件——S中有一条线段连接凸壳CH（S）中不相领顶点。提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先农层计算线段集S的凸壳，并将这些凸壳改变为简单多边形；然后计算各多边形之间的交点，进而删去这些交点；最后俣并若干个简单多边形为一个简单多边形。当S中线段数目n较大时，用分治思想设计分治算法，较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。     

一个基于图的多边形拓扑关系生成算法

提出了一个基于图的多边形拓扑关系自动生成算法。该算法只需利用图中弧与多边形的拓扑信息,避免了多边形内角的计算与比较,算法中根据图的拓扑特征采取有效的策略,加快了多边形自动生成的速度。给出了算法的实例。     

基于结点等效变化的缓冲区生成算法

目标缓冲区生成的算法一般都要经过两个阶段，即单个目标缓冲区多边形的独立生成过程和多个目标缓冲区多边形间的重叠合并过程。本文将要生成的缓冲区边界凹侧结点做等效变化成两个相等的点，且定义其连接关系为圆弧，从而取得了边连接的循环运算，便于处理和计算，消除了凸凹两侧缓冲边界数据链不一致性的表达，只寥寥几行代码实现了折线单目标缓冲区的生成，并且易于缓冲边界拓扑关系的建立。     

隐式曲面快速多边形化

隐式曲面多边形化是隐式曲面绘制的常用算法。该文提出了一个隐式曲面快速多边形化算法。首先用Bloo-menthal的多边形化算法生成一个粗糙的初始网格,再进行网格优化提高网格规则性,最后用多边形细分策略细分优化后的网格。实验结果表明,该算法在网格生成速度和网格规则性上都胜于Bloomenthal的多边形化算法。     

一个基于图的多边形拓扑关系生成算法

本文提出了一种基于图的多边形拓扑关系自动生成算法和实例。该算法只需利用图中弧与多边的拓扑信息,避免了多边形内角的计算与比较,算法中根据图的拓扑特征采有效的策略,加快了多边形自动生成的速度。     

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

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

一种新的基于中心线的双线巷道自动生成算法

针对目前双线巷道自动生成算法存在的问题,提出了一种新的基于中心线的双线巷道自动生成算法。该算法实现原理:由巷道中心线分别向两侧偏移巷道宽度的1/2距离,生成不等宽的双线巷道,双线首尾相接再生成多边形区域;任取两条巷道,求一条巷道的多边形区域与另一条巷道的双线的交点,并判断相邻两交点之间的双线是否在多边形区域内,若在多边形区域内,且一条巷道在另一条巷道的上方或相互贯通,则裁剪掉这部分双线巷道;遍历所有巷道使两两之间都经过这种方法处理,最终生成相互贯通或交叉的双线巷道图。     

多边形的矩形分解问题及其算法

本文研究了多边形的矩形分解问题，提出了一个将多边形分解为矩形的新的算法，它可以应用于ＶＬＳＩ ＣＡＤ中的ＰＧ数据生成，文中叙述了算法的详细步骤，并用一实例表现了算法思想。     

基于平面扫描的双线圆弧缓冲区生成算法

在GIS领域,线目标实体的缓冲区生成有很多算法,常见的双线圆弧法存在结果多边形自相交和失真问题,处理起来相当复杂。在双线圆弧法基础上提出一种基于平面扫描技术的线目标缓冲区生成算法,在扫描过程中处理多边形自相交问题,同时能够避免失真现象。算法的时间复杂度为O（nlbn）。     

A type-merging algorithm for extracting an isosurface from volumetric data

A new approach for reducing the number of triangles representing an isosurface in volumetric data is presented. The basic idea is to classify the configurations of the marching cubes approach into types. Surface patches traversing neighboring cubes of the same type can be merged into patches, which can be approximated with fewer and larger triangles. Experimental results show that the number of triangles is about 50% of that obtained with the marching cubes algorithm, with comparable image quality. The execution time is somewhat longer than that of the marching cubes algorithm.     

移动立方体算法的研究和改进

CT三维重建技术是辅助医生对病情进行分析和显示的有效工具,它极大地提高了医疗诊断的准确性。移动立方体法（Marching Cubes,MC）是一种经典的医学图像三维重建算法,但是在实际使用中还是存在着一些缺点。针对传统MC算法出现的两个问题：（1）用直线代替双曲线来构造等值面会产生误差;（2）重建过程中大量时间耗费在检查空立方体上,提出了一种改进的MC算法,分别通过切片图像间的插值和基于分割的快速查找法来对此进行解决。通过实验表明,改进的MC算法比起传统MC算法,在三维重建的效果和效率上都得到了很大的提高。     

体数据中边界点计算的新方法

为了提高三维重构的精度,分析了Marching Cubes方法所产生的误差,提出获得边界点的新方法.新方法依据阈值区分出边界内、边界外和边界像素,利用这3个像素的像素值来决定边界点的位置.并且针对边界点的位置,提出了三角形网格结构的调整方法.理论分析表明,当边界在像素级别上是直线段时,新方法能够直接计算出精确的边界点.区分等值点和边界点,基于边界点,给出了不同于MC方法的等值点计算方法.最后用CT数据实例比较了新方法和MC方法.     

像素的移动体素面绘制算法

移动立方体算法是最具影响力的等值面构造算法。本文以移动立方体算法为基础,提出了像素点移动体素面绘制算法。根据物体表面的显示特性和体素特点,利用像素点组成的边界体素绘制物体的等值面,实现物体表面的三维重建。在实验中,对一组CT图像中的骨骼组织进行三维表面重建和显示,并与用Matlab绘制函数重建的三维结果进行比较。实验分析表明,该算法能对物体进行三维重建,避免了二义性问题,但重建表面不光滑,重建花费的时间较长。     

基于MC算法的CT序列图像快速成型文件生成方法

快速成型技术在医学领域有着广泛而重要的应用,为了从医学图像中得到快速成型文件,详细论述了MC(marchingcubes)算法生成STL文件的步骤及需要注意的问题,并将其与轮廓连接生成STL文件的方法进行比较,说明了所提方法优势及可行性。方法先对CT序列图像进行阈值分割、区域增长等图像预处理,然后用MC算法得到用三角片组成的几何模型,最后根据文件格式标准,生成STL文件,其中着重讨论了STL文件中三角面片顶点顺序如何确定这一问题。     

等值面抽取技术在超声探头声场模拟中的应用

为了更好地研究超声波声场,提出了以等值面方式来表现超声探头的声场分布;运用并改进了经典的MC（Marching Cubes）算法得出了圆盘和矩形两种超声探头声源的三维声场等值面描述.实验表明改进后的算法能获得较好的效果.     

Multiresolution Isosurface Extraction with Adaptive Skeleton Climbing

An isosurface extraction algorithm which can directly generate multiresolution isosurfaces from volume data is introduced. It generates low resolution isosurfaces, with 4 to 25 times fewer triangles than that generated by marching cubes algorithm, in comparable running times. By climbing from vertices (0-skeleton) to edges (1-skeleton) to faces (2-skeleton), the algorithm constructs boxes which adapt to the geometry of the true isosurface. Unlike previous adaptive marching cubes algorithms, the algorithm does not suffer from the gap-filling problem. Although the triangles in the meshes may not be optimally reduced, it is much faster than postprocessing triangle reduction algorithms. Hence the coarse meshes it produces can be used as the initial starts for the mesh optimization, if mesh optimality is the main concern.     

Graphics processing unit‐based triangulations of Blinn molecular surfaces

Computing the surface of a molecule (e.g., a protein) plays an important role in the analysis of its geometric structure as needed in the study of interactions between proteins, protein folding, protein docking, and so forth. There are a number of algorithms for the computation of molecular surfaces and their triangulations, but only a few take advantage of graphics processing unit computing. This paper describes a graphics processing unit‐based marching cubes algorithm to triangulate molecular surfaces. In the end of the paper, a performance analysis of three implementations (i.e., serial CPU, CUDA, and OpenCL) of the marching cubes‐based triangulation algorithm takes place as a way to realize beforehand how molecular surfaces can be rendered in real‐time in the future. Copyright © 2011 John Wiley & Sons, Ltd.     

Automatic Generation of Multiresolution Boundary Representations

The paper focuses on automatic simplification algorithms for the generation of a multiresolution family of solid models from an initial boundary representation of a polyhedral solid. An algorithm for general polyhedra based on an intermediate octree representation is proposed. Simplified elements of the multiresolution family approximate the initial solid within increasing tolerances. A discussion among different octree-based simplification methods and the standard marching cubes algorithm is presented.     

A hierarchical stochastic modelling approach for reconstructing lung tumour geometry from 2D CT images

ABSTRACT

Lung cancer is one of the deadliest cancers in both men and women. Nowadays, several methods are used to cure this cancer including surgery and radiotherapy. These methods require prior knowledge about the shape of tumours. This type of knowledge may also help physicians to determine the cancer type. In this paper we propose a novel approach for 3D reconstruction of tumour geometry from a sequence of 2D images. The proposed approach consists of two phases: tumour segmentation from computed tomography (CT) images and 3D shape reconstruction. Segmentation is conducted using snake optimisation and Gustafson–Kessel clustering. For 3D reconstruction, first, we propose a new approach to interpolate some intermediate slices between original slices. Then, the well-known marching cubes algorithm is used for surface reconstruction. Eventually, we smoothen the surface using an explicit fairing algorithm. Experiments show that our new approach can highly improve the quality and the accuracy of the reconstructed tumour shape.