一个有效的沿三维直线的体素遍历整数算法

沿着三维直线进行体素遍历的算法在医学图像处理及其它三维图形和图像应用中是一个非常重要和基础的算法，该文在研究了二维平面中像素的直线遍历算法的基础上，提出了一个以二维平面中遍历算法为基础的沿三维直线的体素遍历算法，该算法是第一个整数遍历算法，因此没有其它算法所产生的累计误差，另外，该算法所用的判断公式是非常精炼的，因此计算量很小；文章最后将该算法与现有的体素遍历算法进行了比较，比较的结果表明，该算法不仅没有累计误差，而且执行速度也是最快的。     

三维面心立方网格下的直线生成算法

以菱形十二面体为体素构成的三维面心立方(Face-Centered Cubic,FCC)网格是六角网格在三维的一种推广,直线生成算法在三维图形和图像应用中是一个非常重要和基础的算法.文中首先研究了二维六角网格下基于附属菱形空间的直线生成算法,然后将其推广至三维FCC网格,得到了一种FCC网格下的直线生成算法,该算法在三维方形网格下的Bresenham算法的基础上,利用附属平行六面体空间的平行六面体与FCC网格空间的体素之间的一一对应关系生成直线.该算法应用简单的判断公式,一步最多可生成3个体素,且只涉及到整数运算,因而没有累计误差.     

理想材料零件的锥束CT投影仿真

针对锥束CT在理想材料零件研制中的应用需求,给出了基于拓展体素模型的CT仿真零件材料信息表示方法.在体素模型的投影图像仿真计算中,提出了一种三维射束与体素模型的快速遍历与求交算法,并结合Simpson积分公式实现了投影直线积分的高效高精度计算.实验结果验证了该算法的有效性.     

基于数字距离变换的3D模型骨架提取算法

在获得三维模型体素表示的基础上 ,通过比较模型体素及其 2 6连通域体素到模型轮廓的最小欧式距离 ,提出了一种利用骨架体素 2 6连通域的对称性进行三维模型骨架体素提取的算法 整个算法只需遍历一次体数据集即可自动完成模型骨架的提取过程 .实验表明 ,该算法具有较高的效率和精度 .     

直线Bresenham生成算法的三维推广

直线Bresenham生成算法仅适用于二维直线的生成,文中巧妙地利用直线在两个坐标平面的投影,将二维直线Bresenham算法推广到三维,用于空间直线的生成,给出了一个具体实例,并分析了计算误差和算法效率,结果表明,三维直线Bresenham生成算法具有高效和高精度的特点,可用于数空机床和快速成型机的空间直线插补。     

中点画线算法的三维推广

以往的中点画线算法仅适用于二维直线的生成一该文巧妙地利用直线在两个坐标平面内的投影，将二维中点画线算法推广到三维，用于空间直线的生成，给出了一个具体实例，并分析了计算误差和算法效率。结果表明，三维中点画线算法具有高效和高精度的特点，可在实际工作中用于空间直线生成、空间直线插补和运动控制等方面。     

三维虚拟环境中二维平面动态实时渲染方法

为实现三维虚拟世界中二维平面动态实时渲染,提出一种有效的方法并通过实验验证了其可行性。通过在三维虚拟环境中加载该方法,不仅可以实现用户与三维环境中图像交互,而且可以在该系统上集成传统的二维图像业务,弥补了当前三维虚拟世界技术对二维平面业务支持不足的缺点。     

基于决策树分类的体绘制加速技术

为了提高体绘制速度,提出一种新的算法。该算法通过决策树对体素分类,同时采用行程编码辅助模型存储决策树分类结果。在遍历体素模型时,只访问感兴趣的体素分类,而忽略那些空的和不感兴趣的体素分类,减少了体素的计算量。实验结果表明,此算法不仅保持了图像的绘制质量,而且明显提高了体绘制速度。     

基于MITK的血管三维重建

利用二维血管内超声图像序列重建三维血管模型,并对三维模型进行虚拟剖切,可以方便地看到内部组织,便于观察和诊断.针对血管内超声图像亮度变化小、形状特征不明显和图像分割效果不好等问题,基于MITK平台,采用光线投射算法对二维超声图像序列进行体绘制三维重建.对重建模型进行旋转、缩放和任意平面裁剪等交互操作,裁剪掉一部分无关体素,有助于医生观察血管的内部结构和细节信息.此外,通过调节体素的阻光度值,可以得到层次清晰的三维血管模型.     

FP-Growth算法的改进

基于FP树的FP-Growth算法在挖掘频繁模式过程中需要两次扫描事务集来建立FP树,这不仅降低了算法的效率,而且给数据库服务器带来负担.在原有经典FP-Growth算法的基础上,提出一种基于二维表的方法对原算法进行改进,改进算法通过使用二维向量记录频繁度仅需遍历一次事务集,从而省略FP-Growth算法在生成新条件FP树时对条件模式基的第一次遍历,大大缩短了建立FP树的时间.实验结果表明,该算法的改进优于经典算法.     

An Integer One-Pass Algorithm for Voxel Traversal

Voxel traversing along a line in a uniformly divided voxel space is frequently needed in different applications of computer graphics. The paper presents a new integer one‐pass algorithm for this problem. In 2D, the proposed approach is based on a modification of the well‐known Bresenham algorithm. The algorithm is then extended in 3D where a special case may occur. It is characterized by a simple discriminator. A derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic. In this way, the accumulation of rounding errors is completely eliminated, and a robust and compact implementation can be easily achieved. One of the main advantages of the proposed algorithm is that it visits 1–3 voxels during each iteration thus assuring its efficiency. The algorithm has been compared with other algorithms for voxel traversing by measuring spent CPU time. For comparison, Cleary & Wyvill's, Amanatides & Woo's, and Code‐based algorithm have been used. The proposed algorithm is faster than the referenced algorithms.     

A General Multi-step Algorithm for Voxel Traversing Along a Line

Traversing voxels along a three dimensional (3D) line is one of the most fundamental algorithms for voxel‐based applications. This paper presents a new 6‐connectivity integer algorithm for this task. The proposed algorithm accepts voxels having different sizes in x, y and z directions. To explain the idea of the proposed approach, a 2D algorithm is firstly considered and then extended in 3D. This algorithm is a multi‐step as up to three voxels may be added in one iteration. It accepts both integer and floating‐point input. The new algorithm was compared to other popular voxel traversing algorithms. Counting the number of arithmetic operations showed that the proposed algorithm requires the least amount of operations per traversed voxel. A comparison of spent CPU time using either integer or floating‐point arithmetic confirms that the proposed algorithm is the most efficient. This algorithm is simple, and in compact form which also makes it attractive for hardware implementation.     

3D line voxelization and connectivity control

Voxelization algorithms that convert a 3D continuous line representation into a discrete line representation have a dual role in graphics. First, these algorithms synthesize voxel-based objects in volume graphics. The 3D line itself is a fundamental primitive, also used as a building block for voxelizing more complex objects. For example, sweeping a 3D voxelized line along a 3D voxelized circle generates a voxelized cylinder. The second application of 3D line voxelization algorithms is for ray traversal in voxel space. Rendering techniques that cast rays through a volume of voxels are based on algorithms that generate the set of voxels visited (or pierced) by the continuous ray. Discrete ray algorithms have been developed for traversing a 3D space partition or a 3D array of sampled or computed data. These algorithms produce one discrete point per step, in contrast to ray casting algorithms for volume rendering, which track a continuous ray at constant intervals, and to voxelization algorithms that generate nonbinary voxel values (for example, partial occupancies). Before considering algorithms for generating discrete lines, we introduce the topology and geometry of discrete lines     

An Efficient Code-Based Voxel-Traversing Algorithm

The paper considers an efficient approach to traversing a uniformly-subdivided space pierced by a line segment. A voxel, as the basic constituent element of the uniformly subdivided space, is restricted to having the form of a cube. The algorithm works in two steps. In the first step, the so-called Bresenham voxels are identified and, by comparing their position codes, their type of connectivity is determined. To achieve the required connectivity between neighbouring voxels, the second step of the algorithm is applied to find the missing voxels. In this way, the algorithm efficiently switches between face-, edge- and vertex-connectivity. Although the algorithm works with oating-point precision, it is extremely computationally efficient, and tests of speed compared with the Müller, Cleary & Wyvill, Amanatides & Woo, and Zemčik algorithms are described.     

结合体元数据结构的机载LIDAR建筑物检测

目的 目前,点云、栅格格网及不规则三角网等建筑物检测中常用的离散机载激光雷达（LIDAR）点云数据表达方式存在模型表达复杂、算法开发困难、结果表达不准确及难以表达多返回数据等缺点。为此,针对LIDAR点云体元结构模型构建及在此基础上的建筑物检测展开研究,提出一种基于体元的建筑物检测算法。方法 首先将点云数据规则化为二值（即1、0值,分别表示体元中是否包含有激光点）3D体元结构。然后利用3D滤波算法将上述体元结构中表征数据点的体元分类为地面和非地面体元。最后,依据建筑物边缘的接近直线、跳变特性从非地面体元中搜寻建筑物边缘作为种子体元进而标记与其3D连通的非地面体元集合为建筑物体元。结果 实验基于ISPRS（international society for photogrammetry and remote sensing）提供的包含了不同的建筑物类型的城区LIDAR点云数据测试了"邻域尺度"参数的敏感性及提出算法的精度。定量评价的结果表明：56邻域为最佳邻域尺度;建筑物的检测质量可达到95%以上——平均完整度可达到95.61%、平均正确率可达95.97%。定性评价的结果表明：对大型、密集、不规则形状、高低混合及其他屋顶类型比较特殊的复杂建筑物均可成功检测。结论 本文提出的建筑物检测算法采用基于体元空间邻域关系的搜索标记方式,可有效实现对各类建筑目标特别是城市建筑目标的检测,检测结果易于建模3D建筑物模型。     

Path planning in complex 3D environments using a probabilistic roadmap method

This paper presents a 3D path planning algorithm for an unmanned aerial vehicle （UAV） in complex environments. In this algorithm, the environments are divided into voxels by octree algorithm. In order to satisfy the safety requirement of the UAV, free space is represented by free voxels, which have enough space margin for the UAV to pass through. A bounding box array is created in the whole 3D space to evaluate the free voxel connectivity. The probabilistic roadmap method （PRM） is improved by random sampling in the bounding box array to ensure a more efficient distribution of roadmap nodes in 3D space. According to the connectivity evaluation, the roadmap is used to plan a feasible path by using A＊ algorithm. Experimental results indicate that the proposed algorithm is valid in complex 3D environments.     

Novel Techniques for Robust Voxelization and Visualization of Implicit Surfaces

Voxelization is the transformation of geometric surfaces into voxels. Up to date this process has been done essentially using incremental algorithms. Incremental algorithms have the reputation of being efficient but they lack an important property: robustness. The voxelized representation should envelop its continuous model. However, without robust methods this cannot be guaranteed. This article describes novel techniques of robust voxelization and visualization of implicit surfaces. First of all our recursive subdivision voxelization algorithm is reviewed. This algorithm was initially inspired by Duff's image space subdivision method. Then, we explain the algorithm to voxelize implicit surfaces defined in spherical or cylindrical coordinates. Next, we show a new technique to produce infinite replications of implicit objects and their voxelization method. Afterward, we comment on the parallelization of our voxelization procedure. Finally we present our voxel visualization algorithm based on point display. Our voxelization algorithms can be used with any data structure, thanks to the fact that a voxel is only stored once the last subdivision level is reached. We emphasize the use of the octree, though, because it is a convenient way to store the discrete model hierarchically. In a hierarchy the discrete model refinement is simple and possible from any previous voxelized scene thanks to the fact that the voxelization algorithms are robust.     

USSCD：一个基于均匀空间分割的快速碰撞检测算法

对于存在大量运动物体的虚拟环境，碰撞检测往往成为影响系统计算效率的瓶颈，为提高多体碰撞检测的效率，提出了一个基于均匀空间分割的快速多体碰撞检测算法——USSCD，该算法首先将物体空间均匀分割成一系列单元格，然后在每个单元格，通过基于AVL排序的扫描排除法进行碰撞检测，同时依据物体的分布密度，提出了一个计算单元格尺寸的优化方法，通过一系列实验，测试了USSCD算法的性能，并与I-COLLIDE算法进行比较，实验结果表明，在均匀分布条件下，当物体数量较大时，USSCD的效率高于I-COLLIDE算法，而且，USSCD算法的效率基本不受物体运动相关性的影响。     

Decision trees for accelerating unimodal, hybrid and multimodal rendering models

This paper deals with the rendering of segmented unimodal, hybrid and aligned multimodal voxel models. We propose a data structure that classifies the segmented voxels into categories, so that whenever the model has to be traversed, only the selected categories are visited and the empty and non-selected voxels are skipped. This strategy is based on: (i) a decision tree, called the rendering decision tree (RDT), which represents the hierarchy of the classification process and (ii) an intermediate run-length encoding (RLE) of the classified voxel model. The traversal of the voxel model given a user query consists of two steps: first, the RDT is traversed and the set of selected categories computed; next, the RLE is visited, but the non-selected runs are skipped and only the voxels of the original model that are codified are accessed in selected runs of the RLE. This strategy has been used to render a voxel model by back-to-front traversal and splatting as well as to construct 3D textures for hardware-driven 3D texture mapping. The results show that the voxel model traversal is significantly accelerated.     

A fast 3D seed-filling algorithm

The 3D seed-filling algorithm that fills consecutive object voxels at a time has shown higher efficiency than the method of filling only one voxel at a time. However, it searches seeds for filled voxels already containing no seeds. This paper presents a fast 3D seed-filling algorithm that uses a 2D pointer array of linked lists to avoid the redundant seed searches. The linked lists record the spans of filled voxels. Five comparison cases determine the current filling span, and the neighboring spans for searching seeds are either non-overlapping, or completely or partially overlapping. Seed searches are executed only for the non-overlapping span or part (in the case of the partial overlapping span) to minimize the searches. The experimental results show that the proposed algorithm is effective in eliminating the redundant seed searches and achieves high efficiency.