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.     

Linear octrees by volume intersection

The paper describes a new algorithm for constructing a 3D approximation of an object from three orthogonal 2D silhouettes. The 2D views are represented as binary arrays and 3D approximation is obtained as a linear octree. The algorithm makes use of volume intersection of three cylinders obtained by sweeping three views in respective directions. The algorithm takes less time than an existing algorithm which makes use of three quadtrees and an octree for 2D and 3D image representation, respectively. Unlike the previous algorithm, the present algorithm does not require any preprocessing stage or condensation. It is Shown that the proposed algorithm is of o(T), where T is the total number of nodes in the resulting octree.     

视觉显著性的八叉树颜色量化方法

针对彩色图像颜色量化过程中整体层次与局部细节之间存在的问题,提出视觉显著性的八叉树颜色量化方法。将视觉注意机制引入图像颜色量化中,分析视觉显著性模型获取视觉显著图方法及理论,根据八叉树颜色量化方法中对细节量化不足的缺陷,结合显著图进行颜色频度统计,增加视觉显著区域的颜色频度。将该方法与八叉树颜色量化图像进行比较验证,可见量化后的颜色具有丰富的层次感,图像细节失真度降低,轮廓清晰。     

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

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

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.     

Hierarchical data structures and algorithms for computer graphics.II. Applications

For pt.I see ibid., vol.8, no.3, p.48-68, May (1988). Advanced applications for preliminary display methods are focused on, with emphasis on the octree. Topics include use of the quadtree as a basis for hidden-surface algorithms, parallel and perspective projection methods to display a collection of objects represented by an octree, and the use of octrees to facilitate such image-rendering techniques as ray tracing and radiosity     

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     

Applications of quadtree, octree, and binary tree decomposition techniques to shape analysis and pattern recognition

The binary tree, quadtree, and octree decomposition techniques are widely used in computer graphics and image processing problems. Here, the techniques are reexamined for pattern recognition and shape analysis applications. It has been shown that the quadtree and octree techniques can be used to find the shape hull of a set of points in space while their n-dimensional generalization can be used for divisive hierarchical clustering. Similarly, an n-dimensional binary tree decomposition of feature space can be used for efficient pattern classifier design. Illustrative examples are presented to show the usefulness and efficiency of these hierarchical decomposition techniques.     

基于Fisher判据的自适应彩色图像量化算法

提出了一种基于Fisher判据的自适应彩色图像量化算法。首先用八叉树算法把原始图像量化为256种颜色,然后根据人类的视觉特性,参照NBS距离与人类视觉对颜色差别的定量关系,自动确定初始聚类中心及聚类数目,在此基础上,用Fisher判据自动确定出初始类中心的一个同组,从而实现图像的量化。实验结果表明所提算法无需事先给定颜色量化数目,在量化数目相同的情况下,量化效果明显优于八叉树算法和k均值算法。     

一种基于GPU实现的自适应八叉树纹理绘画算法

当前,虽然基于二维图像映射定义的传统二维纹理已得到广泛应用。但是它有很多局限性。这是因为很多三维模型在纹理空间中进行参数化是非常困难的,例如隐式表面、细分表面和高密度或高细节的多边形网格。基于八叉树纹理定义,提出了一种新型的自适应八叉树纹理绘画算法。和传统的八叉树纹理映射算法相比,不但占用更少的存储空间,而且实现了基于GPU的纹理查询,有更快的查找速度。     

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.     

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     

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

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

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.     

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.     

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

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

广义线性八元树表示及物体的广义三维重建

提出物体的广义线性八元树表示法,推广线性八元树的构造方法完成物体的广义三 维重建--广义线性八元树表示,从而为物体三维重建降低约束、增加灵活性.     

Visualization of Isosurfaces with Parametric Cubes

To render images from volume datasets, an interpolation method also called reconstruction is needed. The level of details of the resultant image closely depends on the filter used for reconstruction. We propose here a new filter producing C ¹ continue surfaces. The provided image quality is better than current high-quality algorithms, like splatting or trilinear raycasting, where tiny details are often eliminated. In contrast with other studied high quality filters that are practically unusable, our algorithm has been implemented interactively on a modest platform thanks to an efficient implementation using parametric cubes. We also demonstrate the interest of a min-max octree in the visualization of isosurfaces interactively thresholded.     

Discrete shading of three-dimensional objects from medial axis transform

In this paper, we present a discrete shading technique using medial axis transform (MAT) of 3D binary image data based on digital generalized octagonal distances. Our method is computationally attractive as it does not require the explicit computation of surface normals. We have compared our results with images rendered from voxel and octree representations while using analytical surface rendered images as bench marks. The quality of rendering by our method is certainly superior to those obtained from voxel and octree representations.