一种基于八叉树结构表达的三维实体布局启发式算法

本文在利用八叉树结构表达三维实体布局块及布局空间的基础上,根据八叉树同构节点匹配的思想设计了一个三维实体布局的启发式算法,并提出了三环图方法,解决了八叉树节点的同构识别问题．理论分析及计算的结果表明了该算法对于具有任意形状和大小的布局对象的三维布局问题来说效果理想．     

Accelerating ARTS

A major fraction of ray-tracing computation time is spent on ray-object intersection calculation. To reduce this calculation cost, one method, ARTS, subdivides the 3-D object space into voxels and uses a 3-D line-drawing routine to simulate ray propagation in the subdivided space to select objects for intersection testing. Finer space subdivision gives better object selection resolution and fewer ray-object tests. However, as the subdivision increases, the improvement is offset by a linear degradation of the line-drawing-routine efficiency and a cubic growth of the memory requirement. We solve these time and memory scalability problems in ARTS using an adaptive 3-D line-drawing algorithm, which traverses space with multiple stepsizes, and a hybrid database that employs both the octree and the 3-D array data structures. The space traversal cost in our solution grows logarithmically with the subdivision increase, and the memory requirement grows only linearly.     

一种基于八叉树与流水线技术的快速碰撞检测算法

针对存在大量运动物体的虚拟环境,提出一种基于空间八叉树剖分与流水线技术的并行碰撞检测算法.通过八叉树剖分,把虚拟空间剖分成一系列的子空间,然后只对同一空间中的结点进行碰撞检测.对空间内的每个物体构建包围盒树,同一空间中的任意两棵包围盒树遍历构成任务树,把任务树中的任务分配给不同的进程进行碰撞检测,并采用流水线与多线程技...     

基于八叉树空间分割的三维点云模型密写

针对三维点云模型的信息隐藏,提出一种基于八叉树空间分割的空域密写算法。对经过主成分分析后的三维点云模型建立包围盒,利用八叉树空间分割得到小体元并记录分割过程,通过顶点位移将信息嵌入到小体元内的不同空间位置。实验结果表明,该算法在提取信息时不需要原始模型数据,具有嵌入量高、失真度低的特点,能够抵抗旋转、平移、均匀缩放和顶点重排序攻击,适合于任意网格的三维模型信息隐藏。     

Fast Collision Detection Algorithms with Applications to Particle Flow

In this paper, we present efficient algorithms for collision detection of arbitrarily shaped rigid moving objects in a variety of interactive as well as non-interactive environments. The algorithms primarily consist of two stages. The first stage involves finding candidate objects for possible collisions. The second stage involves detecting exact (within a prespecified tolerance) collision between these candidates. The primary data structure used in the algorithms is an octree. In the first stage, we build an octree for the enclosure containing the objects, which is used to detect possible collisions. Assuming spatial/temporal coherence i.e., that the particles move slowly or that the time sampling is fast enough, the average time complexity of this stage can be shown to be O(n) (excluding the time complexity for a one time octree construction), where n is the number of particles. In the second stage, we build a surface-octree for each object. If the objects are convex and assuming coherence, the expected time complexity to detect precise (within a prespecified tolerance) collision for each pair is a constant (excluding the time complexity for a one time surface-octree construction). Therefore, the overall expected time complexity for convex object collision detection is linear with respect to n. For the concave objects, complexity analysis is nontrivial to perform and instead we provide a very practical (almost linear time) algorithm. We apply our algorithms to particle flow simulations by simulating flow density conditions often arising in granular flows.     

Parallel processing of an object space for image synthesis using ray tracing

This paper presents a novel parallel processing system for image synthesis using ray tracing. An object space is divided into parts (subspaces), each of which is allocated to a processor. The processor detects, simultaneously the intersections of the surfaces of each object and a fixed number of rays over the whole space, and calculates the local intensity on an object in each subspace. The global intensities of pixels on a screen are calculated by the other kind of processors simultaneously. We also present the optimal data structure, based on an adaptive division algorithm, for parallel processing of the object space.     

An Adaptive Spatial Subdivision of the Object Space for Fast Collision Detection of Animated Rigid Bodies

Collision detection tests between objects dominate run time simulation of rigid body animation. Traditionally, hierarchical bounding box tests are used to minimize collision detection time. But the bounding boxes do not take shapes of the objects into account which results in a large number of collision detection tests. We propose an adaptive spatial subdivision of the object space based on octree structure to rectify this problem. We also present a technique for efficiently updating this structure periodically during the simulation.     

Stable Real-Time Surgical Cutting Simulation of Deformable Objects Embedded with Arbitrary Triangular Meshes

Surgical simulators need to simulate deformation and cutting of deformable objects. Adaptive octree mesh based cutting methods embed the deformable objects into octree meshes that are recursively refined near the cutting tool trajectory. Deformation is only applied to the octree meshes; thus the deformation instability problem caused by degenerated elements is avoided. Biological tissues and organs usually contain complex internal structures that are ignored by previous work. In this paper the deformable objects are modeled as voxels connected by links and embedded inside adaptive octree meshes. Links swept by the cutting tool are disconnected and object surface meshes are reconstructed from disconnected links. Two novel methods for embedding triangular meshes as internal structures are proposed. The surface mesh embedding method is applicable to arbitrary triangular meshes, but these meshes have no physical properties. The material sub-region embedding method associates the interiors enclosed by the triangular meshes with physical properties, but requires that these meshes are watertight, and have no self-intersections, and their smallest features are larger than a voxel. Some local features are constructed in a pre-calculation stage to increase simulation performance. Simulation tests show that our methods can cut embedded structures in a way consistent with the cutting of the deformable objects. Cut fragments can also deform correctly along with the deformable objects.     

Octree-R: an adaptive octree for efficient ray tracing

Ray tracing requires many ray-object intersection tests. A way of reducing the number of ray-object intersection tests is to subdivide the space occupied by objects into many nonoverlapping subregions, called voxels, and to construct an octree for the subdivided space. We propose the Octree-R, an octree-variant data structure for efficient ray tracing. The algorithm for constructing the Octree-R first estimates the number of ray-object intersection tests. Then, it partitions the space along the plane that minimizes the estimated number of ray-object intersection tests. We present the results of experiments for verifying the effectiveness of the Octree-R. In the experiment, the Octree-R provides a 4% to 47% performance gain over the conventional octree. The result shows the more skewed the object distribution (as is typical for real data), the more performance gain the Octree-R achieves     

Generating octrees from object silhouettes in orthographic views

An algorithm to construct the octree representation of a three-dimensional object from silhouette images of the object is described. The images must be obtained from thirteen viewing directions corresponding to the three face views, six edge views, and four corner views of an upright cube. These views where chosen because they provide a simple relationship between pixels in the image and the octant labels in the octree, thus replacing the computation of detecting intersections between the octree space and the objects by a table lookup operation. The average ratio of the object volume to the octree volume is found to be greater than 90%. The sequential use made of the chosen viewing directions results in a coarse-to-fine acquisition of occupancy information. The number and order of the viewpoints used provides a mechanism for trading accuracy of the representation against the computational effort needed to obtain the representation     

An octree-based method for shape from inconsistent silhouettes

Shape-from-Silhouette (SfS) is the widely known problem of obtaining the 3D structure of an object from its silhouettes. Two main approaches can be employed: those based on voxel sets, which perform an exhaustive search of the working space, and those based on octrees, which perform a top-down analysis that speeds up the computation. The main problem of both approaches is the need for perfect silhouettes to obtain accurate results. Perfect background subtraction hardly ever happens in realistic scenarios, so these techniques are restricted to controlled environments where the consistency hypothesis can be assumed. Recently, some approaches (all of them based on voxel sets) have been proposed to solve the problem of inconsistency. Their main drawback is the high computational cost required to perform an exhaustive analysis of the working space. This paper proposes a novel approach to solve SfS with inconsistent silhouettes from an octree based perspective. The inconsistencies are dealt by means of the Dempster–Shafer (DS) theory and we employ a Butterworth function for adapting threshold values in each resolution level of the octree. The results obtained show that our proposal provides higher reconstruction quality than the standard octree based methods in realistic environments. When compared to voxel set approaches that manage inconsistency, our method obtains similar results with a reduction in the computing time of an order of magnitude.     

A single-pass GPU ray casting framework for interactive out-of-core rendering of massive volumetric datasets

We present an adaptive out-of-core technique for rendering massive scalar volumes employing single-pass GPU ray casting. The method is based on the decomposition of a volumetric dataset into small cubical bricks, which are then organized into an octree structure maintained out-of-core. The octree contains the original data at the leaves, and a filtered representation of children at inner nodes. At runtime an adaptive loader, executing on the CPU, updates a view and transfer function-dependent working set of bricks maintained on GPU memory by asynchronously fetching data from the out-of-core octree representation. At each frame, a compact indexing structure, which spatially organizes the current working set into an octree hierarchy, is encoded in a small texture. This data structure is then exploited by an efficient stackless ray casting algorithm, which computes the volume rendering integral by visiting non-empty bricks in front-to-back order and adapting sampling density to brick resolution. Block visibility information is fed back to the loader to avoid refinement and data loading of occluded zones. The resulting method is able to interactively explore multi-gigavoxel datasets on a desktop PC.     

一种改进的八元树三维目标表示方法

利用八元树表示三维物体是一种十分有效的方法。传统指针表示的八元树结构具有占据内存容量大、节点间关系少等缺点。在分析了物体的空间布局和八元树结构的基础上,文章提出了一种改进的八元树三维表示方法。从医学图像三维重建的实验结果看,提出的方法可行并且在内存存储结构和访问方式等方面优于传统的表示方法。     

运用改进的八叉树算法实现精确碰撞检测

提出一种精确碰撞检测算法,通过计算空间多面体之间距离实现碰撞检测功能.在计算2个多面体之间距离时,运用空间层次划分技术高效地寻找多面体中充分接近的三角面片,然后在这些三角面片中进行距离计算,以提高算法效率;同时运用改进的八叉树层次分割算法,与基本八叉树算法相比,减少了算法的空间复杂度.文中算法已经在超导Tokamak实验装置（EAST）虚拟装配仿真系统的碰撞检测模块中得到应用,通过实验比较,证明了该算法的可行性.     

An algorithm for converting the boundary representation of a CAD model to its octree representation

Present CAD systems store the solid model of an object using a convenient representation. Boundary models and CSG (Constructive Solid Geometry) models are the most frequently used representations. Based on recent research findings, octree representation of an object presents a promising approach in solving problems in the areas of Computer Graphics, Manufacturing and Robotics. The most notable use of octree representations is in CAD-based robotic path planning problems. Octree models have also been used in fast rendering of 3-D solid models using ray tracing methods. This paper presents an algorithm for converting the boundary representation of polyhedral models to its octree representation. Such an algorithm would provide the link between an object generated using a solid modelling system and the application involving an octree representation of an object. The algorithm is demonstrated by converting a polyhedral boundary model of a sample object to its octree representation.     

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     

Octree Representation and Its Applications in CAD

In this paper,a survey of octree representation and its applications in CAD is presented.The octree representation may be categorized as pure octree representation and polytree(or extended octree),and the latter is actually a boundary representation decomposed by octree.Linear octree which is a variant of regular octree representation has the advantage of saving memory space.The mapping between Cartesian coordinates and node addresses in linear octree is discussed.Then,algorithms for converting a boundary representation of 3D object into an octree are investiged and major approaches for transforming an octree encoded object are presented.After that,some of the applications of octree representation in CAD are listed,in particular,the applications in solid modeling,in accelerating ray tracing and in generating meshes for FEM.     

基于室内动静结合分割的射线跟踪加速方法

密闭环境的信道建模在许多应用场景中具有重要作用。在空间内障碍物较多时，传统射线跟踪算法在运算过程中会有无用的求交点次数过多的问题，使得算法的计算效率较低。为此，提出一种基于空间分割的射线跟踪加速方法。该方法根据三维空间中物体的分布情况，合理地结合静态与动态两种空间分割加速方法，大幅度减少了射线与空间内物体的求交点次数，提高了算法的计算效率。仿真分析表明，在相同预测精度的三维环境下，与原始算法对比，使用静态空间分割的射线跟踪算法随着分割等级的提升计算效率提高了至少50.2%；而与只使用静态空间分割的算法对比，使用静态与动态空间分割结合的加速方法的计算效率在已经提高的基础上至少还能提升8.9%。