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

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

基于动态局部更新体素模型的虚拟加工仿真算法研究

为提高虚拟加工仿真算法的仿真速度和精度,提出一种新的基于动态局部更新体素模型的虚拟加工仿真算法.该算法利用体素节点间的邻接关系,实现虚拟加工仿真的动态局部更新.算法在初始化阶段建立虚拟毛坯的八叉树结构体素模型,并建立任意体素6-邻接关系遍历算法.在虚拟加工几何仿真阶段,利用刀具和毛坯相对运动的时空一致性,从毛坯上一帧已...     

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     

Geometric probing of dense range data

A new method is presented for the efficient and reliable pose determination of 3D objects in dense range image data. The method is based upon a minimalistic Geometric Probing strategy that hypothesizes the intersection of the object with some selected image point, and searches for additional surface data at locations relative to that point. The strategy is implemented in the discrete domain as a binary decision tree classifier. The tree leaf nodes represent individual voxel templates of the model, with one template per distinct model pose. The internal nodes represent the union of the templates of their descendant leaf nodes. The union of all leaf node templates is the complete template set of the model over its discrete pose space. Each internal node also encodes a single voxel which is the most common element of its child node templates. Traversing the free is equivalent to efficiently matching the large set of templates at a selected image seed location. The method was implemented and extensive experiments were conducted for a variety of combinations of tree designs and traversals under isolated, cluttered, and occluded scene conditions. The results demonstrated a tradeoff between efficiency and reliability. It was concluded that there exist combinations of tree design and traversal which are both highly efficient and reliable     

Multiresolution volume visualization with a texture-based octree

Although 3D texture-based volume rendering guarantees image quality almost interactively, it is difficult to maintain an interactive rate when the technique has to be exploited on large datasets. In this paper, we propose a new texture memory representation and a management policy that substitute the classical one-texel per voxel approach for a hierarchical approach. The hierarchical approach benefits nearly homogeneous regions and regions of lower interest. The proposed algorithm is based on a simple traversal of the octree representation of the volume data. Driven by a user-defined image quality, defined as a combination of data homogeneity and importance, a set of octree nodes (the cut) is selected to be rendered. The degree of accuracy applied for the representation of each one of the nodes of the cut in the texture memory is set independently according to the user-defined parameters. The variable resolution texture model obtained reduces the texture memory size and thus texture swapping, improving rendering speed.     

Fast ray-tracing of rectilinear volume data using distancetransforms

The paper discusses and experimentally compares distance based acceleration algorithms for ray tracing of volumetric data with an emphasis on the Chessboard Distance (CD) voxel traversal. The acceleration of this class of algorithms is achieved by skipping empty macro regions, which are defined for each background voxel of the volume. Background voxels are labeled in a preprocessing phase by a value, defining the macro region size, which is equal to the voxel distance to the nearest foreground voxel. The CD algorithm exploits the chessboard distance and defines the ray as a nonuniform sequence of samples positioned at voxel faces. This feature assures that no foreground voxels are missed during the scene traversal. Further, due to parallelepipedal shape of the macro region, it supports accelerated visualization of cubic, regular, and rectilinear grids. The CD algorithm is suitable for all modifications of the ray tracing/ray casting techniques being used in volume visualization and volume graphics. However, when used for rendering based on local surface interpolation, it also enables fast search of intersections between rays and the interpolated surface, further improving speed of the process     

DKD: a fast k‐d tree update design for dynamic scenes

We design dynamic k‐d (DKD) tree based on classical k‐d tree for animated scene rendering. Our method can inherit the benefit of efficient traversal of k‐d tree and minimize time cost to update DKD tree, making it well suited for animated geometry. DKD employs primitive reset, redistribution to reflect the updated positions of geometry, and leaf node incremental growing to avoid the deterioration of hierarchy quality due to refitting. Our experiments show that DKD has a significant rendering performance improvement than selected existing methods. Copyright © 2016 John Wiley & Sons, Ltd.     

基于相邻层间相似性和空体素跳跃的体绘制加速算法研究

Splatting是经典的基于物序的直接体绘制方法,运算数据量的多少制约着算法绘制图像的速度。为了进一步提升绘制速度,采用基于相邻层间相似性和空体素跳跃相结合的方法进行加速,在读取数据过程中对图片中的三维纹理数据进行筛选,并使用足迹表对筛选后的三维纹理数据进行二维投影,利用相邻层间相似性计算每一个点的灰度值,并根据灰度值将数据分类,算出对成像没有影响的空体素,跳过其绘制过程从而加速算法。实验结果显示,该算法能够在保证绘制图像质量的基础上,在一定程度上解决和改善Splatting算法数据的空间相关性和运算效率的问题。     

沿三维直线的非单位体素遍历的多步整数算法

提出一种只用整数运算的沿三维直线的体素遍历算法,适用的体素空间可以分割成非单位的和非正方体的.首先研究了二维平面中的体素直线遍历算法,然后提出一种以二维平面中的遍历算法为基础的沿三维直线的体素遍历算法.该算法是一个多步整数遍历算法,每一步可以遍历最多3个体素,且所用的判断公式非常精炼,不仅计算量很小而且没有累计误差.与现有的体素遍历算法进行比较的结果表明,该算法不仅没有累计误差,而且执行速度也是最快的.     

一种体绘制专用体系结构存储器的设计

提出了一种适合Ray Casting算法的体绘制专用体系结构的存储模型。根据处理器数目的不同，体数据被划分为不同的子体。子体依据其空间坐标位置的不同被分配到不同处理单元，子体内的体素被分配到相应处理单元的存储器的对应位置。说明了子体在处理器间的分配方式以及体素在存储器内的编址和寻址方式。     

Efficient data-parallel tree-traversal for BlobTrees

The hierarchical implicit modelling paradigm, as exemplified by the BlobTree, makes it possible to support not only Boolean operations and affine transformations, but also various forms of blending and space warping. Typically, the resulting solid is converted to a boundary representation, a triangle mesh approximation, for rendering. These triangles are obtained by evaluating the corresponding implicit function (field) at the samples of a dense regular three-dimensional grid and by performing a local iso-surface extraction at each voxel. The performance bottleneck of this rendering process lies in the cost of the tree traversal (which typically must be executed hundreds of millions of times) and in the cost of applying the inverses of the space transformations associated with some of the nodes of the tree to the grid samples.Tree pruning is commonly used to reduce the number of samples for which the field value must be computed. Here, we propose a complementary strategy, which reduces the costs of both the traversal and of applying the inverses of the blending and warping transformations that are associated with each evaluation.Without blending or warping, a BlobTree can be reduced to a CSG tree only containing Boolean nodes and affine transformations, which can be reordered to increase memory coherence. Furthermore, the cumulative effects of the affine transformations can be precomputed via matrix multiplication. We propose extensions of these techniques from CSG trees to the fully general BlobTrees. These extensions are based on tree reordering, bottom-up traversal, and caching of the combined matrix for uninterrupted runs of affine transformations in the BlobTree.We show that these new techniques result in an order of magnitude performance improvement for rendering large BlobTrees on modern Single Program Multiple Data (SPMD) devices.     

Improved perspective visibility ordering for object-order volume rendering

Finding a correct a priori back-to-front (BTF) visibility ordering for the perspective projection of the voxels of a rectangular volume poses interesting problems. The BTF ordering presented by Frieder et al. [6] and the permuted BTF presented by Westover [14] are correct for parallel projection but not for perspective projection [12]. Swan presented a constructive proof for the correctness of the perspective BTF (PBTF) ordering [12]. This was a significant improvement on the existing orderings. However, his proof assumes that voxel projections are not larger than a pixel, i.e. voxel projections do not overlap in screen space. Very often the voxel projections do overlap, e.g. with splatting algorithms. In these cases, the PBTF ordering results in highly visible and characteristic rendering artefacts. In this paper we analyse the PBTF and show why it yields these rendering artefacts. We then present an improved visibility ordering that remedies the artefacts. Our new ordering is as good as the PBTF, but it is also valid for cases where voxel projections are larger than a single pixel, i.e. when voxel projections overlap in screen space. We demonstrate why and how our ordering works at fundamental and implementation levels.     

Interactive Ray Tracing of Large Models Using Voxel Hierarchies

We propose an efficient approach for interactive visualization of massive models with CPU ray tracing. A voxel‐based hierarchical level‐of‐detail (LOD) framework is employed to minimize rendering time and required system memory. In a pre‐processing phase, a compressed out‐of‐core data structure is constructed, which contains the original primitives of the model and the LOD voxels, organized into a kd‐tree. During rendering, data is loaded asynchronously to ensure a smooth inspection of the model regardless of the available I/O bandwidth. With our technique, we are able to explore data sets consisting of hundreds of millions of triangles in real‐time on a desktop PC with a quad‐core CPU.     

多分辨率BSP树的生成及应用

CAD和科学可视化应用要求能够让用户对复杂场景进行交互式显示或者处理,因此,多细节层次技术被广泛应用于图形系统中以提高处理效率.通过构造一种新的BSP(binaryspacepartitioningtree)树形式来加速多细节层次模型的绘制,这种技术已成功地应用于所开发的多分辨率模型编辑系统.同时,详细描述了新的BSP树结构的构造和绘制过程.     

结合可见性处理的顺序点模型树

将点模型的树节点按照各自的误差进行顺序排列,就形成了顺序点模型树,这样,就能方便地利用GPU(图形处理器)来高速绘制点模型,但这种方法缺乏对可见性的高效处理,不便于处理大型复杂的模型,因为这些模型中各个部分之间的遮挡关系复杂,且每次成像所需的树节点的误差跨度大,导致了大量不可见的树节点也要绘制,为此,文章提出一种结合可见性处理的顺序点模型树,即在根据误差顺序排列树节点时,融入一些可见性信息,这样,绘制时,不仅能保留顺序点模型树高效利用GPU的优点,还能避免处理大量的不可见但满足误差要求的树节点,实验表明,相比于顺序点模型树,新方法的绘制速度更快,加速率至少在20％,特别是在处理大规模复杂模型时的加速率更高,能达67％以上。     

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.     

针对全空子数据体的GPU体绘制

目的 体绘制是3维数据可视化的主要方法之一。用于体绘制的数据体中包含有大量的空体素,导致光线投射算法进行没有意义的重采样计算,必然降低绘制算法效率。针对全空子数据体体绘制低效问题,提出基于GPU体高效绘制方法。方法 利用八叉树数据结构组织数据,有效管理包含许多空体素的子数据体。通过绘制八叉树非全空叶子节点子数据体表面,使光线投射算法中起始和终止重采样位置更接近数据体中的可视部分,同时根据八叉树全空节点子数据体判定纹理查询结果,计算合适的跳跃步长,快速跳过八叉树中全空节点子数据体。结果 当数据体中空体素较多时,确定合适的八叉树深度,有效地跳过数据体中的空体素,减少体绘制运算量,实现对原基于体包围盒表面绘制的GPU光线投射算法的加速。结论 设计不透明度函数,凸显数据体中层位面,并将算法成功应用于地震数据可视化,取得很好应用效果。     

基于层次聚类树的点曲面视点相关绘制

针对点曲面的视点相关绘制问题,提出了一个新的表面基层次聚类简化算法。区别于普遍采用的空间剖分基策略,该算法的显著优势在于能够运用法向锥半角误差标准有效跟踪曲面的起伏变化,并以此为聚类简化过程提供可靠的全局误差控制。离线简化阶段,连同各种预定义的聚类约束条件,算法构造了点曲面模型的连续层次多分辨率表达。实时绘制阶段,层次可见性裁剪以及优化的树遍历提高了系统的整体性能。此外,通过引入附加的轮廓增强机制,在较大的屏幕投影误差和较高的模型简化率情况下,系统仍然能够保证较好的绘制视觉质量。     

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

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

Quantizing Intersections Using Compact Voxels

Efficient intersection queries are important for ray tracing. However, building and maintaining the acceleration structures is demanding, especially for fully dynamic scenes. In this paper, we propose a quantized intersection framework based on compact voxels to quantize the intersection as an approximation. With high‐resolution voxels, the scene geometry can be well represented, which enables more accurate simulation of global illumination, such as detailed glossy reflections. In terms of memory usage in our graphics processing unit implementation, voxels are binarized and compactly encoded in a few 2D textures. We evaluate the rendering quality at various voxel resolutions. Empirically, high‐fidelity rendering can be achieved at the voxel resolution of 1 K³ or above, which produces images very similar to those of ray tracing. Moreover, we demonstrate the feasibility of our framework for various illumination effects with several applications, including first‐bounce indirect illumination, glossy refraction, path tracing, direct illumination, and ambient occlusion.