三维布局中八叉树节点的快速分解算法

本文在对八叉树子节点的顶点类型及构成三维实体精确ＣＳＧ模型的半空间的类型进行系统地分类的基础上，结合不同类型半空间的性质给出了一个三维实体的精确ＣＳＧ模型转换到八叉树模型的综合算法。通过对若干个不同的实体进行实际计算，结果表明该算法能够满足三维实体自动化布局的需要。     

三维实体布局的八叉树语言及优化算法

本文设计了一个八叉树操作语言，并利用该语言实现了三维实体布局的优化算法，该算法能从任一初始布局可行解迅速收敛到一个局部最优解上，从而明显改善初始布局方案。文章最后给出了一个简单的应用实例。     

复杂实体干涉检验的改进八叉树法

在基于结构立体几何的实体造型系统中，用改进的八叉树方法进行了复杂实体间的干涉检验，即避免了复杂实体间的求交运算，又很好地克服了传统八叉树方法精度低的缺点。本文提出的方法可以推广至机器人无碰路径规划，三维实体布局等所有需要进行干涉检验的领域。     

改进的八叉树模型在3D刀轨显示系统中的应用

在传统的八叉树模型的基础上增加了扩展八叉树结点,同时引入了混合式的八叉树教据结构,并将它们应用到数控加工的三维刀轨显示系统中;叙述了实体从B-rep表示法转换为相应的改进型八叉树模型的方法,并在这种改进的八叉树模型的基础上完成对零件加工过程的实时性仿真;最后通过运行实际的数控加工程序证明该算法的可行性和有效性.     

一种基于八叉树的三维实体内部可视化技术

鉴于传统的图形学-面图形学只能表达三维实体的表面的形状和属性，不能表达实体内部的属性，如纹理、密度场以及温度场等，因而在计算机图形学、CAD以及有限元分析等许多领域都需要一种新的可视化技术-三维实体的可视化技术，以表达实体内部的属性；三维实体的可视化技术是新兴的图形学-体图形学的一个重要组成部分，为了实现三维实体的可视化，针对CAD造型系统中的实际要求，根据体图形学的理论和八叉树的特点，提出了一种基于八叉树的实体内部可视化技术，该技术采用八叉树算法对边界数据结构表达的实体进行体元化。由于实体内部属性变化的不均匀，算法采用了不规则体元，以充分表达实体内部的细节，实际应用效果表明，该算法不但能充分表达实体内部属性，而且也具有一定的造型功能。     

基于八叉树空间分割的NURBS曲面重构方法

对三维模型和点云曲面重构方法进行深入研究,根据应用特点提出八叉树空间分割和N U RBS曲面重构方法。利用八叉树的快速收敛特性对三维实体的点云数据进行分割、精简,采用N U RBS方法对局部网格曲面进行重构;采用八叉树和四叉树相混合的数据结构,渐进地进行网格曲面的重构。存储结构采用扩展式八叉树结构,编码采用8进制前缀编码方法。利用O penG L设计一个实验模型系统验证了该算法的可行性和有效性。     

基于八叉树邻域分析的光线跟踪加速算法

八叉树是加速光线跟踪常用的层次划分结构,为加快八叉树跟踪光线的过程,论文 研究了运用八叉树邻域分析提高光线与八叉树节点之间的碰撞检测速度的方法,提出了一种结构 简单、计算效率更高的八叉树节点的邻域分析算法。运用该算法可由现碰撞节点快速计算出下一 碰撞节点,避免了采用大量递归搜索计算,从而提高了图像的渲染速度。实验结果表明,使用论 文提出的邻域分析进行碰撞检测,效率比传统算法提高了3 倍以上,大大提高了光线跟踪的速度。     

基于多级线性结构和规则分块的虚拟八叉树

提出一种基于多级线性结构和规则分块、无指针/无位置码的虚拟八叉树模型，具有高效的结点访问效率和存储空间压缩效率，实现了指针八叉树在时间效率、线性八叉树在空间效率两方面优势的统一。新模型能够对三维实体及其内部的非均质属性进行建模，可以保证各种可视化与分析算法的处理效率，在空间信息系统和体图形学等实体建模相关的领域中具有重要的研究意义和应用价值。     

3D GIS中线性八叉树空间索引的建立与查询算法研究

三维地理信息系统空间数据库具有数据量大、空间实体关系复杂、空间操作计算量大等特点。为了提高检索效率,必须建立高效的空间索引机制。八叉树空间索引是对二维GIS中四叉树索引进行扩展的一种三维空间数据结构,具有思路简单、容易理解和实现、查询速度快的优点。本文首先阐述了线性八叉树空间索引的原理,然后重点介绍了线性八叉树空间索引的建立和查询算法。     

基于三维点云数据的线性八叉树编码压缩算法*

八叉树结构是三维数据建模中研究和应用最为广泛的栅格数据结构。由于三维扫描的点云数据是基于物体表面的,其空间离散程度远大于三维实体数据,一般的线性八叉树编码压缩方法都是基于实体数据的,不能直接应用于三维点云数据。提出的改进的线性八叉树地址码（Morton码）的方法可大大提高它的连续性,有效降低八叉树的深度,提高数据的压缩比,改进后的Morton码还可以应用多种编码压缩算法进一步压缩。     

Symmetry identification of a 3-D object represented by octree

An algorithm for identifying symmetry of a 3-D object given by its octree is presented, and the symmetry degree (a measure of object symmetry) is proposed. The algorithm is based on traversals of the octree obtained by the principal axis transform of an input octree. An object can be in an arbitrary position and with arbitrary orientation within the octree space, and a wide range of symmetries represented by groups of proper and improper rotations can be identified. It is shown that the octree data structure supports these operations well, especially for objects whose symmetry types are simpler or equal in complexity with a fourfold rotational symmetry. The operation of the algorithm is illustrated using some synthetic test objects. The results, which are composed of identified symmetry types and the corresponding symmetry degrees, were satisfactory     

基于空间分解的集装箱布局启发式算法及布局空间利用率规律

针对集装箱布局提出了一种利用三叉树结构表达三维矩形物体布局状态空间的方法。通过将布避空间依据分割,每次放入相对于当前布局空间来说是满足特定折最优布局块,将该布局块定位于当前布局空间后部的左下角,来完成不同大小的三维矩形全的布局方案的确定,并给出试验结果。     

三维形体的形态学运算及应用

本文首先讨论了边界表示的物体的形态学运算问题。文中讨论了任意形状的物体，包括凸物体和非凸物体；引入了负形体的概念；并提出了２Ｄ和３Ｄ连续物体的Ｍｉｎｋｏｗｓｋｉ运算的统一算法。利用这一算法，提出了３Ｄ任意形体间的变形新算法，把边界表示的物体的形态学运算的概念扩展到任意曲线和任意曲面上，并且介绍了３Ｄ物空间中曲线的概念和３Ｄ物空间双参数曲面的概念。文中任意形体的３Ｄ变形算法能很好地解决具有不同拓扑结构的３Ｄ边界表示的物体之间的变形问题。     

A generic scheme for progressive point cloud coding

In this paper, we propose a generic point cloud encoder that provides a unified framework for compressing different attributes of point samples corresponding to 3D objects with arbitrary topology. In the proposed scheme, the coding process is led by an iterative octree cell subdivision of the object space. At each level of subdivision, positions of point samples are approximated by the geometry centers of all tree-front cells while normals and colors are approximated by their statistical average within each of tree-front cells. With this framework, we employ attribute-dependent encoding techniques to exploit different characteristics of various attributes. All of these have led to significant improvement in the rate-distortion (R-D) performance and a computational advantage over the state of the art. Furthermore, given sufficient levels of octree expansion, normal space partitioning and resolution of color quantization, the proposed point cloud encoder can be potentially used for lossless coding of 3D point clouds.     

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.     

An Algorithm for Perspective Viewing of Objects Represented by Octrees

A new algorithm is presented for viewing three-dimensional objects, represented by an octree, from an arbitrary location. The algorithm generates aperspective view of the objects while eliminating hidden surfaces. The viewer can be located anywhere inside or outside the objects. The algorithm presented in this short notefixes an artifact that is generated by a previously published algorithm due to Meagher when the viewer is located in certain regions in space. The new algorithm traverses the octree in a back-to-front order and recursively chooses correct orders for visiting the sons of non-leaf nodes.     

Octree generation from object silhouettes in perspective views

Octrees are useful for object representation when fast access to coarse spatial occupancy information is necessary. This paper presents an efficient algorithm for generating octrees from multiple perspective views of an object. The algorithm first obtains a polygonal approximation of the object silhouette. This polygon is then decomposed into convex components. For each convex component, a pyramid is formed treating the view point as its apex and the convex components as a cross section. The octree representation of each of these pyramids is obtained by performing intersection detection of the object with the cubes corresponding to octree nodes. The intersection detection step is made efficient by decomposing it into a coarse-to-fine sequence of intersection tests. The octree for one silhouette is obtained by taking the union of octrees obtained for each component. An intersection of octrees corresponding to different viewing directions gives the final octree of the object. An implementation of the algorithm is given. The accuracy of the octree representation of the objects is evaluated. The ratio of the actual volume of the object to the volume of the object reconstructed from the octree representation is used as a performance index of the algorithm.     

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.     

Collision-free object movement using vector fields

Presents a technique for automatically providing animation and collision avoidance in a general-purpose computer graphics system. The technique, which relies on an expanded notion of vector fields, allows users to set up and animate objects easily, then prevents objects from colliding as the animation proceeds. This technique automatically generates volume octree vector fields around objects in a scene. These vector fields affect object motion and animation, and also provide for automatic collision avoidance for arbitrary objects. Applications of collision avoidance in an animation system encompass any scene containing object movement above or around other objects