A distance template for octree traversal in CPU-based volume ray casting

Several optimization techniques have been proposed to improve the speed of direct volume rendering. A hierarchical representation formed by an octree is a data structure to skip over transparent regions while requiring little preprocessing and data storage. However, in order to skip over an octant estimated to be transparent (a transparent octant), the distance from a boundary to another boundary of the octant should be calculated. Because the distance computation is expensive, we propose a precomputed data structure, the distance template, which stores direction and distance values from one boundary voxel on a face to all the boundary voxels on the remaining five faces. In the rendering step, if a ray reaches a transparent octant, it leaps over the octant by referring to the stored distance value.     

View Dependent Sequential Point Trees

Sequential point trees provide the state-of-the-art technique for rendering point models, by re-arranging hierarchical points sequentially according to geometric errors running on GPU for fast rendering. This paper presents a view dependent method to augment sequential point trees by embedding the hierarchical tree structures in the sequential list of hierarchical points. By the method,two kinds of indices are constructed to facilitate the points rendering in an order mostly from near to far and from coarse to fine. As a result, invisible points can be culled view-dependently in high efficiency for hardware acceleration, and at the same time, the advantage of sequential point trees could be still fully taken. Therefore, the new method can run much faster than the conventional sequential point trees, and the acceleration can be highly promoted particularly when the objects possess complex occlusion relationship and viewed closely because invisible points would be in a high percentage of the points at finer levels.     

Spectral volume rendering

Volume renderers for interactive analysis must be sufficiently versatile to render a broad range of volume images: unsegmented “raw” images as recorded by a 3D scanner, labeled segmented images, multimodality images, or any combination of these. The usual strategy is to assign to each voxel a three component RGB color and an opacity value α. This so-called RGBα approach offers the possibility of distinguishing volume objects by color. However, these colors are connected to the objects themselves, thereby bypassing the idea that in reality the color of an object is also determined by the light source and light detectors c.q. human eyes. The physically realistic approach presented, models light interacting with the materials inside a voxel causing spectral changes in the light. The radiated spectrum falls upon a set of RGB detectors. The spectral approach is investigated to see whether it could enhance the visualization of volume data and interactive tools. For that purpose, a material is split into an absorbing part (the medium) and a scattering part (small particles). The medium is considered to be either achromatic or chromatic, while the particles are considered to scatter the light achromatically, elastically, or inelastically. Inelastic scattering particles combined with an achromatic absorbing medium offer additional visual features: objects are made visible through the surface structure of a surrounding volume object and volume and surface structures can be made visible at the same time. With one or two materials the method is faster than the RGBα approach, with three materials the performance is equal. The spectral approach can be considered as an extension of the RGBα approach with greater visual flexibility and a better balance between quality and speed     

Volumetric segmentation using Weibull E-SD fields

This paper presents a coarse-grain approach for segmentation of objects with gray levels appearing in volume data. The input data is on a 3D structured grid of vertices v(i. j. k), each associated with a scalar value. In this paper, we consider a voxel as a /spl kappa/ /spl times/ /spl kappa/ /spl times/ /spl kappa/ cube and each voxel is assigned two values: expectancy and standard deviation (E-SD). We use the Weibull noise index to estimate the noise in a voxel and to obtain more precise E-SD values for each voxel. We plot the frequency of voxels which have the same E-SD, then 3D segmentation based on the Weibull E-SD field is presented. Our test bed includes synthetic data as well as real volume data from a confocal laser scanning microscope (CLSM). Analysis of these data all show distinct and defining regions in their E-SD fields. Under the guide of the E-SD field, we can efficiently segment the objects embedded in real and simulated 3D data.     

A contour tracing and coding algorithm for generating 2D contour codes from 3D classified objects

In 3D image data sets generated by voxel-based classification, each voxel is marked with a specific class label. Voxels of the same class label can form 3D objects of extremely complex shape. Interactively drawn regions are usually represented by their 2D region borders. In order to combine automatically classified with interactively drawn regions, a contour tracing and coding algorithm for generating optimized 2D contours from 3D classified objects is presented. A special conversion algorithm allows a chain or a crack code representation. An application to medical images shows the method's necessity and usefulness in dealing with highly complex regions.     

Multi-view Occlusion Reasoning for Probabilistic Silhouette-Based Dynamic Scene Reconstruction

In this paper, we present an algorithm to probabilistically estimate object shapes in a 3D dynamic scene using their silhouette information derived from multiple geometrically calibrated video camcorders. The scene is represented by a 3D volume. Every object in the scene is associated with a distinctive label to represent its existence at every voxel location. The label links together automatically-learned view-specific appearance models of the respective object, so as to avoid the photometric calibration of the cameras. Generative probabilistic sensor models can be derived by analyzing the dependencies between the sensor observations and object labels. Bayesian reasoning is then applied to achieve robust reconstruction against real-world environment challenges, such as lighting variations, changing background etc. Our main contribution is to explicitly model the visual occlusion process and show: (1) static objects (such as trees or lamp posts), as parts of the pre-learned background model, can be automatically recovered as a byproduct of the inference; (2) ambiguities due to inter-occlusion between multiple dynamic objects can be alleviated, and the final reconstruction quality is drastically improved. Several indoor and outdoor real-world datasets are evaluated to verify our framework.     

Volume graphics

Volume graphics, which employs a volume buffer of voxels for 3D scene representation, is discussed. Volume graphics offers advantages over surface graphics: it is viewpoint independent, insensitive to scene and object complexity, and suitable for the representation of sampled and simulated data sets. Moreover, geometric objects can be mixed with these data sets. Volume graphics supports the visualization of internal structures and lends itself to the realization of block operations, constructive solid geometry modeling, irregular voxel sizes, and hierarchical representation. The problems associated with the volume buffer representation (such as discreteness, memory size, processing time, and loss of geometric representation) are discussed     

Using linked volumes to model object collisions, deformation,cutting, carving, and joining

In volume graphics, objects are represented by arrays or clusters of sampled 3D data. A volumetric object representation is necessary in computer modeling whenever interior structure affects an object's behavior or appearance. However, existing volumetric representations are not sufficient for modeling the behaviors expected in applications such as surgical simulation, where interactions between both rigid and deformable objects and the cutting, tearing, and repairing of soft tissues must be modeled in real time. Three-dimensional voxel arrays lack the sense of connectivity needed for complex object deformation, while finite element models and mass-spring systems require substantially reduced geometric resolution for interactivity and they can not be easily cut or carved interactively. This paper discusses a linked volume representation that enables physically realistic modeling of object interactions such as: collision detection, collision response, 3D object deformation, and interactive object modification by carving, cutting, tearing, and joining. The paper presents a set of algorithms that allow interactive manipulation of linked volumes that have more than an order of magnitude more elements and considerably more flexibility than existing methods. Implementation details, results from timing tests, and measurements of material behavior are presented     

Interactive simulation of robot milling for rapid shape prototyping

Rapid shape prototyping has become a prominent method to speed up the product development process in industry. Automatic robot milling, directly from CAD data, is an efficient technique to materialize the intended product shape quickly.

There are a number of situations in which previewing of this process is required. The end-user, i.e., the designer who intends to order a prototype, wishes to be informed about the quality of the result in terms of geometric appearance and accuracy, for example, by comparing it to the CAD model. Also, any systematic defects inherent in the prototyping process must be made visible. Furthermore, the developers of the prototyping system can take advantage of simulation in their efforts to improve the process.

The major technical problem in simulating the milling process is to model the volume removal operations efficiently, so that the stock-in-progress can be visualized at any moment. This article presents a method to perform such simulation while meeting stringent requirements, including the ability to handle the large number of robot movements in a single milling process (up to 10⁶, depending on the required spatial accuracy), high speed, and user-interactivity. Both the block of material that is being machined and the milling tool are internally represented by a 3D voxel structure to achieve real-time volume-removal operations on the material. All other objects, such as the robot and the work cell, keep their original B-spline surface representation, to enable high-quality visualization.

Implementation of the data structures and algorithms described here has resulted in a useful system for joint simulation of volume removal and robot motion.     

Constructive non-regularized geometry

Solid modelling is concerned with the construction and manipulation of unambiguous computer representations of solid objects. These representations permit us to distinguish the interior, the boundary and the complement of a solid. They are conveniently specified in Constructive Solid Geometry (CSG) by a construction tree that has solid primitives as leaves and rigid body motions or regularized Boolean operations as internal nodes. Algoriths for classifying sets with respect to CSG trees and for evaluating the boundaries of the corresponding solids are known, at least for simple geometric domains. Emerging CAD applications require that we extend the domain of solid modellers to support more general and more structured geometric objects. The focus is on dimensionally non-homogeneous, non-closed pointsets with internal structures. These entities are well suited for dealing with mixed-dimensional (‘non-manifold’) objects in ⁿ that have dangling or missing boundary elements, and that may be composed of several regions. A boundary representation for such objects has been described elsewhere. We propose to specify and represent inhomogeneous objects in terms of Constructive Non-Regularized Geometry (CNRG) trees that extend the domain of CSG by supporting non-regularized primitive shapes as leaves, and by providing more general set-theoretic and topological operators at interior nodes. Filtering operations are also provided that construct CNRG objects from aggregates of selected regions of other CNRG objects. A syntax and semantics of the operators in CNRG are presented, and some basic algorithms for classifying pointsets with respect to the regions of objects represented by CNRG trees are outlined.     

Adaptive cell division for ray tracing

In ray tracing the two most commonly used data structures are the octree and uniform cell division. The octree structure allows efficient adaptive subdivision of space, while taking care of the spatial coherence of the objects in it; however, the tree structure locating the next node in the path of a ray is complex and time consuming. The cell structure, on the other hand, can be stored in a three-dimensional array, and each cell can be efficiently accessed by specifying three indices. However, such a uniform cell division does not take care of object coherence. The proposed data structure combines the positive features of the above data structures while minimising their disadvantages. The entire object space is implicitly assumed to be a three-dimensional grid of cells. Initially, the entire object space is a single voxel which later undergoes “adaptive cell division.” But, unlike in the octree structure, where each voxel is divided exactly at the middle of each dimension, in adaptive cell division, each voxel is divided at the nearest cell boundary. The result is that each voxel contains an integral number of cells along each axis. Corresponding to the implicit cell division we maintain a three-dimensional array, with each array element containing the voxel number which is used to index into the voxel array. The voxel array is used to store information about the structure of each voxel, in particular, the objects in each voxel. While a ray moves from one voxel to another we always keep track of the cell through which the ray is currently passing. Since only arrays are involved in accessing the next voxel in the path of the ray, the operation is very efficient.     

Displaying of details in subvoxel accuracy

Under the volume segmentation in voxel space,a lot of details,some fine and thin objects,are ignored.In order to accurately display these details,this paper has developed a methodology for volume segmentation in subvoxel space.In the subvoxel space,most of the “bridges”between adjacent layers are broken down.Based on the subvoxel space,an automatic segmentation algorithm reserving details is discussed.After segmentation,volume data in subvoxel space are reduced to original voxel space.Thus,the details with width of only one or several voxels are extracted and displayed.     

基于点云数据的单木三维绿量估算方法

针对不同树种的树叶疏密及空间结构不同,提出基于激光点云数据,顾及冠层叶面积密度的树木三维绿量（Living Vegetation Volume, LVV）计算方法。该方法首先根据树木局部点云的主方向相似度和局部点云轴向分布密度分离枝干与树叶,剔除非光合作用成分,提取树叶点云;然后建立体元模型,引入Graham算法确定分层树冠边界,获取激光接触频率,从而基于体元冠层分析（Voxel-based Canopy Profiling, VCP）方法求出冠层叶面积密度（Leaf Area Density, LAD）;最后分层棱柱体积乘以叶面积密度,累加得到树木的三维绿量。利用Riegl VZ-400地面激光扫描仪获取13棵不同形状和树种的树木点云数据,利用该方法估算各树木三维绿量,并与传统的凸包法和台积法的结果对比。实验结果表明,台积法计算的三维绿量值最大,凸包法计算的三维绿量次之,顾及冠层叶面积密度的树木三维绿量方法计算的三维绿量值最小,为台积法的36.69%,为凸包法的47.80%。相比传统方法,顾及冠层叶面积密度的树木三维绿量计算方法侧重光合作用组分叶片点云的统计,并考虑了树冠内部树叶分布情况,更符合树木的实际情况,能充分利用三维点云数据特性,反映树冠内部三维绿量分布。     

Lazy Solid Texture Synthesis

Existing solid texture synthesis algorithms generate a full volume of color content from a set of 2D example images. We introduce a new algorithm with the unique ability to restrict synthesis to a subset of the voxels, while enforcing spatial determinism. This is especially useful when texturing objects, since only a thick layer around the surface needs to be synthesized. A major difficulty lies in reducing the dependency chain of neighborhood matching, so that each voxel only depends on a small number of other voxels. Our key idea is to synthesize a volume from a set of pre‐computed 3D candidates, each being a triple of interleaved 2D neighborhoods. We present an efficient algorithm to carefully select in a pre‐process only those candidates forming consistent triples. This significantly reduces the search space during subsequent synthesis. The result is a new parallel, spatially deterministic solid texture synthesis algorithm which runs efficiently on the GPU. Our approach generates high resolution solid textures on surfaces within seconds. Memory usage and synthesis time only depend on the output textured surface area. The GPU implementation of our method rapidly synthesizes new textures for the surfaces appearing when interactively breaking or cutting objects.     

Windows NT I/O 子系统对象结构分析

在面向对象技术中，数据结构被封装到一个对象中，对外部不可见，它们同外部的通信通过一组定义好的访问接口函数完成的，在Ｗｉｎｄｏｗｓ ＮＴ系统中使用面向对象技术来管理所有的数据结构，在Ｗｉｎｄｏｗｓ ＮＴ输入输出子系统中的各个部分，都采用对象来描述，它们在Ｉ／Ｏ管理器的作用下，统一协调地完成系统的输入输出功能。     

一种基于结构张量的运动物体分割方法

视频中运动物体的分割是众多视频应用的前提。视频可以看作是三维时空中的对象,通过邻域的灰度值的结构方向来分析视频的运动。提出了时空结构张量进行运动物体分割的方法。首先分析了视频中物体的运动与灰度的变化的关系,然后删除了三维结构张量中与时间无关的信息,并将此时空结构张量用于视频中运动物体的分割。实验表明时空结构张量运动物体分割方法相对于传统的结构张量,分割准确,计算简单。     

Terrestrial laser scanning for estimating urban tree volume and carbon content

The acquisition of single-tree-related information is an important task, especially in urban areas where there is an increasing interest in standing carbon stock. Therefore, an easy and robust method was developed to extract the volume, diameter at breast height (DBH) and height of single trees from point clouds of terrestrial laser scanning. For data acquisition, nine trees were scanned from several positions and the resulting high-resolution point clouds (20–60 million points) were analysed by an algorithm based on voxel structure. First, noise reduction was carried out, followed by filling of voxels inside the stem and branches through the intersection of four orthogonal viewing directions. After the elimination of erroneously generated fillings, volume was determined layer-wise for each cross section. For quality assessment, nine deciduous trees were selected, cut, weighed and analysed for wet specific gravity and carbon content in order to provide a control value. The estimated volumes agree with the control value within a range of –5.1% to +14.3%. This is also the case with DBH values; however, heights are systematically underestimated.     

Handling small features in isosurface generation using Marching Cubes

The Marching Cubes (MC) algorithm is a well-known surface-rendering algorithm for volume visualization. However, it has problems in handling small features having a size of one voxel. There are two possible kinds of small features, denoted by type A and type B. The type A feature occurs when at least one cube face has an intersection point in each of its four edges. The type A feature also leads to the “hole problem” due to the ambiguity in the topology. The type B feature occurs when a cube has at least one edge with values of both of its ends being above or below the threshold. We show that if type B features are to be represented with the same accuracy as the type A ones, it would be very computation-intensive and unacceptable for interactive applications. For such applications, there is no need to represent type A features with high accuracy by using complicated methods suggested in the past literature. We present a new approach to handle the type A features which is much simpler than the previous approaches and is also more efficient. This new method is consistent in the sense that all types of small features having the same level of detail are represented with equal accuracy.     

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

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