步进立方体算法的SOB数据结构的改进

为了对步进立方体算法进行加速,首先分析了在等值面生成时此算法出现蜕变点的原因1,并提出了相应的解决方法;然后论述了一种加速步进立方体方法的数据结构——基于层和对象(SOB)的结构,并同八叉树和行程编码方法进行了比较.实验数据表明当数据体中存在一个对象时,SOB方法和八叉树方法的绘制时间没有大的差别,而当数据体中存在多个对象或等值面时,虽然八叉树方法的绘制时间是SOB方法的几倍,但SOB方法的存储容量要比八叉树方法大一些.可见,在数据量不是很大的情况下,以差别不大的存储空间来换取较少的等值面生成时间是可行的,其比八叉树方法有较高的效率,尤其在用户需要选择感兴趣的对象进行绘制时,比八叉树和行程编码更具有灵活性.     

视点相关排序的硬件Occlusion查询MC算法

移动立方体(MC)算法是一种高质量的面绘制方法,要对大量三角面片实现实时绘制和交互操作,因而速度慢,交互性不好;提出一种方法利用显卡硬件实现Occlusion查询,将MC算法生成三角面片分割标记到不同的cube后,基于视点距离对cube进行先后Occlusion查询,检测并剔除对最终图像没有贡献的三角面片;实验数据表明,提出的方法对大规模体数据集进行表面绘制,绘制速度和交互性都得到了明显提高.方法应用在"高级三维PACS工作站"系统上,进行医学CT图像的三维重建表面绘制,取得了良好的效果.     

机载天线辐射特性并行计算与绘制技术

计算量过大是机载天线辐射特性分析的瓶颈问题,为此,提出一种基于等三角剖分的并行UTD计算与绘制算法,算法采用基于空间八叉树分割的模型框架半自动提取方法进行模型简化。给出一种全方位等三角剖分负载平衡方案,并采用sort-last并行图形绘制框架和Binary-swap图像合成算法进行并行绘制,将该算法在计算机集群上进行实现。实验结果表明,该算法能够有效节约计算时间,提高绘制效率,较好地满足了大型复杂飞行器机载天线的方向图特性分析需求。     

大规模战场电磁环境并行体绘制技术研究

提出了一种基于PC集群的大规模三维战场电磁环境并行绘制方法。该方法采用直接体绘制的三维体数据可视化方法;利用空间八叉树对电磁绘制区间进行空间分割,并采用先序遍历八叉树叶节点的方式进行任务分配;采用Binary-swap算法对各PC节点的生成图像逐次进行全屏幕深度合成。实验表明,该方法能够较好满足大规模战场电磁环境实时可视化的要求。     

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

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

八叉树编码的三维物体截面之比计算

三维物体截面面积之比反映了形体几何结构,是一种常用的指标,不同三维形体编码方式采取的截面面积估算方法不同。本文提出了空间八叉树编码表示的三维物体截面面积之比的计算方法,根据截面轴的类型分两种方法进行讨论,一种是垂直于坐标轴的截面;一种是垂直于任意方向轴的截面。两种方法都要进行八叉树到截面四叉树的转换。第一种转换直接通过遍历八叉树而生成特殊截面四叉树;第二种方法根据截面轴的方向,将八叉树进行三维变换,使截面轴与某个坐标轴重合,从而产生新的八叉树,然后利用第一种方法,产生截面四叉树,最后计算截面面积之比。     

八叉树编码的三维物体截面之比的计算

三维物体截面面积之比反映了形体几何结构,是一 种常用的指标,不同三维形体编码方式采取的截面面积估算方法不同。本文提出了空间八叉 树编码表示的三维物体截面面积之比的计算方法,根据截面轴的类型分两种方法进行讨论, 一种是垂直于坐标轴的截面;一种是垂直于任意方向轴的截面。两种方法都要进行八叉树到 截面四叉树的转换。第一种转换直接通过遍历八叉树而生成特殊截面四叉树;第二种方法根 据截面轴的方向,将八叉树进行三维变换,使截面轴与某个坐标轴重合,从而产生新的八叉 树,然后利用第一种方法,产生截面四叉树,最后计算截面面积之比。     

基于混合空间剖分八叉树场景管理技术的研究

基于传统八叉树和面向对象八叉树的设计思想提出了一种混合空间剖分八叉树的场景管理方法,对混合空间剖分八叉树的数据结构、生成算法及遍历方面进行了详细的论述,最后按照该思路结合所设计的一个虚拟场景有效地实现了场景管理,实验表明该方法很适于实时游戏及虚拟现实领域。     

基于线性八叉树的快速直接体绘制算法

提出了基于线性八叉树的加速体绘制算法.利用线性八叉树对物体进行空间剖分,光线投射法跨越体数据集中的空体素,以提高绘制的速度.针对光线穿越体数据时的特殊情况,改进线性八叉树邻域查找的方法,特别是不同尺寸的邻域查找方法,克服了层次八叉树邻域查找的低效率,同时提出了光线离开平面的简洁判定方法,方便光线下一个采样点的计算.实验结果表明,该算法能够有效地提高绘制的速度.     

移动立方体算法与移动四面体算法的对比与评估

等值面提取在标量场体数据可视化和隐函数曲面显示中具有重要应用,经典算法包括移动立方体算法和移动四面体算法,其核心是在立方体或四面体体素单元中用线性的三角面片逼近原始曲面.文中以可计算的代数曲面为例,对上述2种等值面提取算法的逼近精度、时间和空间效率等方面进行了详细的对比,为各种应用中等值面提取算法的选取提供了参考依据.     

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     

Efficient generation of isosurfaces in volume rendering

An efficient method for extracting isosurfaces from volume data is proposed. The method utilizes a modified branch-on-need octree to bypass regions of no current interest. In addition, during the generation of triangle meshes neighboring triangles are merged according to certain criteria. Methods are also given to significantly reduce the space required for octrees. The method is more efficient and generates far fewer triangles than the marching cube algorithm. The performance of the proposed method is compared with that of several existing methods.     

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

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

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.     

一种基于松散八叉树的复杂场景可见性裁剪算法

针对传统八叉树方法的不足,在采用松散八叉树组织场景、利用八叉树空间划分优点的同时弥补其局限性.为提高遮挡查询效率,将子节点依视点排序,针对复杂场景采用双层裁剪技术以进一步提高性能.实验结果表明,文中算法对深度复杂度高、面片数量大的复杂场景具有较好的裁剪效率,能够很好地满足实时绘制的要求.     

基于图片序列的三维表面重建

根据非透明物体内部不可见的实际,提出了一种基于图片序列的三维表面重建算法.该算法首先利用传统的八叉树算法重建出物体的三维模型,然后利用一种新颖的表面点提取算法提取出物体表面点,最后利用这些表面点进行三角网格剖分,进而重建出光滑的三维物体表面.在表面点的提取过程中,算法对处于不同状态(处于立方体的顶点、棱、面)的点赋予不...     

一种基于投影的散乱数据表面增量重建算法

针对3维散乱数据场提出了一种表面重建算法.根据空间曲面的局平特性和平面三角化的基本原则,在参考点的切平面上对邻域点按角度排序,应用可见性准则删除不可见点后,相邻邻域点和参考点形成三角网格.将平面上的网格关系对应到空间,以增量方式重建反映散乱数据场拓扑关系的空间曲面.设定角度阈值优化网格,判断空间曲面的边界和孔洞.对多个数据场进行重建并对结果进行分析.对多个数据场进行重建并对结果进行分析表明,算法具有原理简单,重建速度快,重建效果好的特点.     

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