Approximating the Generalized Voronoi Diagram of Closely Spaced Objects

We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show example applications of the GVD in 2D and 3D.     

Fast Gradient-Domain Video Processing Using Octree Data Structure

We present a fast gradient domain video processing using hierarchical data structure which subdivides the processing region into an octree data. It is hard to handle large video processing by solving a 3D Poisson equation, as the derived linear system is usually large. Solving the system requires large memory space and long computational time, which makes it intractable on a standard computer. To address the scalability problem, rather than processing the video in the gradient-domain pixel by pixel, we perform the video processing in a reduced space using octree data structure, which significantly reduces the variables. We show that the proposed octree approach is efficient in both seamless and mixing gradient-domain video processing. The method enables to perform video processing in greatly reduced computational time and memory space, while receiving visually identical results with that computed from the full solution.     

用于建立三维GIS的八叉树编码压缩算法

复杂的空间数据结构在三维GIS领域中占有突出的地位,它直接关系到GIS的功能和效率,为了有效地进行三维GIS大量数据的存储和管理,重点讨论了三维GIS栅格数据结构中的八叉树编码压缩技术,由于Morton码值的排序是实现八叉树编码压缩的基础,为此,根据Morton码排序的特殊性,提出了采用时间复杂度为O（n）的计数排序算法,使排序速度大为撇提高,在此基础上进行压缩处理,并对算法的时间及空间复杂度进行了分析,在PC机上进行的模拟实验结果表明,在目标复杂度一定的前提下,八叉树存储数据占用空间小（当分割阶次为9阶时,八叉树存储量只占栅格存储量的4.32%）,是一种较为理想的描述复杂海量地理空间数据的压缩结构。     

改进的八叉树数据结构

1 引言随着计算机图形学的飞速发展,三维物体的有效表示变得越来越重要,其中,八叉树表示法(octreerepresentation)以其数据结构简单、算法实现方便等特点,成为最广泛使用的三维物体的表示法之一。八叉树表示法产生于70年代末、80年代初,然而原有的八叉树数据结构存在着冗余,并且这种冗余已经存在了     

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

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

八元树三维表示法的磁盘存储与恢复

八元树是一种优秀的三维空间表示方法。从序列断层图像或者三维数据场建立八元树的三维表示是一个比较费时的复杂过程。为了省略每次从原始数据重新构造八元树的过程,将内存中已经建立好的八元树结构以文件的方式保存到磁盘上。当再次做八元树的三维处理应用时,再直接从保存的磁盘文件恢复出八元树。文中提出了一种快速有效的八元树三维表示法的磁盘存储与恢复算法,并实验验证了其可行性。     

Viewing Transformations of Voxel-Based Objects Via Linear Octrees

This article gives three viewing-transformation algorithms for displaying on a screen 3D pictures represented by linear octrees. All the procedures take advantage of the recursive labeling used to identify the successive decomposition of an object into octants. The first algorithm performs transformations directly on the linear octree, while the second and third algorithms determine the 3D border of the given object first and then project onto the screen the surface voxels thus found. All the algorithms perform the viewing transformations in O(RN) time, where R is the resolution of the picture and N is the number of elements in the linear octree. One of the algorithms provides views of the object at different layers of gray level, while another allows internal views.     

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     

常用色彩量化算法的性能分析

本文在讨论了几种常用的色彩量化算法思想的基础上，重点分析了我们在文献１中给出的一种基于八叉树的色彩量化方法的算法性能，并对这几种方法给以分析比较。     

3-D object decomposition with extended octree model and its application in geometric simulation of NC machining

The paper discusses the development of a prototype solid modeling system based on the extended octree modeling approach and its applications in 3-D NC machining simulation and automatic verification. Along with a simple hierarchical data structure, the extended octree model uses the face boundary information (i) to represent complex objects, (ii) to improve object representational accuracy, and (iii) to accelerate the model updating procedures in a graphic simulation process. The improved representational accuracy makes it possible to carry out automatic NC program verification by generating the machined model of the part through the simulation and comparing it with the designed model of the part. The paper also addresses the issues of model conversions from CSG and B-Rep schemes to the corresponding extended octree models and the issues of carrying out Boolean operations on those extended octree models. A prototype system has been implemented and is integrated with AutoCAD AME solid modeler for object modeling and for NC simulation purpose.     

Hidden Octree Node Removal as a Pipeline Process

A processing pipeline solution to the generation and display of octree encoded 3-D objects is described. Particular emphasis is given to an algorithm which removes that part a of linear octree code which describes parts of the object which are invisible from a prescribed viewing position. The scope of the algorithm is restricted to viewing directions which are parallel to the Cartesian axes and to orthogonal projections. The algorithm is specifically designed to operate as a single stage within a pipeline of processes.     

Virtual Volumetric Graphics on Commodity Displays Using 3D Viewer Tracking

Three dimensional (3D) displays typically rely on stereo disparity, requiring specialized hardware to be worn or embedded in the display. We present a novel 3D graphics display system for volumetric scene visualization using only standard 2D display hardware and a pair of calibrated web cameras. Our computer vision-based system requires no worn or other special hardware. Rather than producing the depth illusion through disparity, we deliver a full volumetric 3D visualization—enabling users to interactively explore 3D scenes by varying their viewing position and angle according to the tracked 3D position of their face and eyes. We incorporate a novel wand-based calibration that allows the cameras to be placed at arbitrary positions and orientations relative to the display. The resulting system operates at real-time speeds (～25 fps) with low latency (120–225 ms) delivering a compelling natural user interface and immersive experience for 3D viewing. In addition to objective evaluation of display stability and responsiveness, we report on user trials comparing users’ timings on a spatial orientation task.     

基于GPU的八叉树结构纹理研究与应用

八叉树结构纹理的应用很好地解决了复杂模型表面2D纹理映射的不足,GPU的高速发展,为八叉树结构纹理在GPU上的现实提供了解决方案。本文将八叉树结构纹理编码为2D纹理,并以节点的广度优先遍历方式在GPU上进行存储,在片段程序访问时提出一种自顶向下的查找方法。实验证明,本文方法取得了准确的纹理映射效果并提高了效率。该方法可以应用于任何需要在复杂物体表面上存储信息的情况。     

基于八叉树结构的三维体素模型检索

随着VR/AR技术发展以及三维模型的广泛应用,实现三维检索具有越来越重要的现实意义.基于模型的检索较好地保留了模型的空间信息和几何特征,其不仅包含模型的表面信息而且还包含模型的内部属性.但是,基于模型的检索往往存在着高存储、高计算的问题.为了解决该问题,本文研究了三维模型预处理及三维模型表示的方法,提出了一种基于八叉树...     

点云数据在深度学习中表示方法的研究

为了实现在深度学习中能够端到端表示点云模型,提出基于八叉树和K-D树（OctKD）的点云数据表示方法。该方法将无组织的点云转换为体素空间,在体素空间对三维模型进行八叉树剖分,改进了八叉树编码方式;构建节点间的邻接关系,在GPU端并行构建八叉树;为了克服八叉树编码检索效率低的问题,采用三维K-D树索引单个三维空间点。实验结果表明该方法能够真实反映模型本身的细节特征,提高了点云模型的构造时间和检索效率。这种新的数据结构实现将点云转换为卷积神经网络可以接收的数据形式。     

Incremental Polygonization of Implicit Surfaces

This paper describes an incremental polygonization technique for implicit surfaces built from skeletal elements. Our method is dedicated to fast previewing in an interactive modeling system environment. We rely on an octree decomposition of space combined with Lipschitz conditions to recursively subdivide cells until a given level of precision is reached and converge to the implicit surface. We use a trilinear interpolation approximation of the field function to create a topologically consistent tessellation characterized by an adjacency graph. Our algorithm aims at updating the mesh locally in regions of space where changes in the potential field occurred. Therefore, we propose an octree inflating and deflating strategy to preserve the octree structure as much as possible and to avoid useless or redundant computations. Timings show that our incremental algorithm dramatically speeds up the overall polygonization process for complex objects.     

Diamond Hierarchies of Arbitrary Dimension

Nested simplicial meshes generated by the simplicial bisection decomposition proposed by Maubach [ Mau95 ] have been widely used in 2D and 3D as multi-resolution models of terrains and three-dimensional scalar fields, They are an alternative to octree representation since they allow generating crack-free representations of the underlying field. On the other hand, this method generates conforming meshes only when all simplices sharing the bisection edge are subdivided concurrently. Thus, efficient representations have been proposed in 2D and 3D based on a clustering of the simplices sharing a common longest edge in what is called a diamond. These representations exploit the regularity of the vertex distribution and the diamond structure to yield an implicit encoding of the hierarchical and geometric relationships among the triangles and tetrahedra, respectively. Here, we analyze properties of d -dimensional diamonds to better understand the hierarchical and geometric relationships among the simplices generated by Maubach's bisection scheme and derive closed-form equations for the number of vertices, simplices, parents and children of each type of diamond. We exploit these properties to yield an implicit pointerless representation for d -dimensional diamonds and reduce the number of required neighbor-finding accesses from O ( d !) to O ( d ).     

Isosurface extraction and spatial filtering using Persistent OcTree (POT)

We propose a novel Persistent OcTree (POT) indexing structure for accelerating isosurface extraction and spatial filtering from volumetric data. This data structure efficiently handles a wide range of visualization problems such as the generation of view-dependent isosurfaces, ray tracing, and isocontour slicing for high dimensional data. POT can be viewed as a hybrid data structure between the interval tree and the Branch-On-Need Octree (BONO) in the sense that it achieves the asymptotic bound of the interval tree for identifying the active cells corresponding to an isosurface and is more efficient than BONO for handling spatial queries. We encode a compact octree for each isovalue. Each such octree contains only the corresponding active cells, in such a way that the combined structure has linear space. The inherent hierarchical structure associated with the active cells enables very fast filtering of the active cells based on spatial constraints. We demonstrate the effectiveness of our approach by performing view-dependent isosurfacing on a wide variety of volumetric data sets and 4D isocontour slicing on the time-varying Richtmyer-Meshkov instability dataset.     

Etree: a database-oriented method for generating large octree meshes

This paper presents the design, implementation, and evaluation of the etree, a database-oriented method for large out-of-core octree mesh generation. The main idea is to map an octree to a database structure and perform all octree operations by querying and updating the database. We apply two standard database techniques, the linear octree and the B-tree, to index and store the octants on disk. Then we introduce two new techniques, auto-navigation and local balancing, to address the special needs of mesh generation. Preliminary evaluation suggests that the etree method is an effective way of generating very large octree meshes on desktop machines.