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.     

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.     

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     

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.     

一种基于小波变换的三维体数据压缩算法

该文结合三维小波变换与八叉树算法,提出了一种新的三维体数据压缩算法。该算法利用小波的多分辩率分析能力对体数据进行压缩,同时结合了八叉树特点对体数据进行编码、存储与重构。实际应用表明该算法能较好地对体数据进行压缩,并且能快速地进行重构和随机地访问体单元数据。     

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

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

The sweep plane algorithm for global collision detection with workpiece geometry update for five-axis NC machining

A new algorithm based on the sweep plane approach for global collision detection for five-axis NC machining is presented. This algorithm takes into account not only collisions between the tool and workpiece, but also collisions between the other parts of the CNC machine, especially the change of the workpiece geometry is included in the detection process. The workpiece and machine bodies are firstly approximated by an octree of bounding spheres. Collision detection is conducted between these spheres. If there is any interference between these bounding spheres, their subspheres are further tested. The subdivision process is recursively performed until the resolution reaches the desired precision level. If there is no interference between the spheres, there is no need to subdivide any more. When the interference is detected between the spheres in the last octree level, the slices within these colliding spheres are further checked by using the sweep plane algorithm to determine whether the enclosed objects really collide with each other. In the sweep plane algorithm, most of the slices of the moving bodies stay parallel and their collisions are detected by checking the interference between these parallel slices using 2D polygon clipping. Whereas, if the slices are not parallel to the reference slicing direction (due to the rotary axes), the interference detection is conducted by examining overlaps of the projections of these slices on the three perpendicular planes XY,YZ, and ZX. The accuracy of the algorithm can be adjusted by changing the distance between the sweep planes. The algorithm can be applied to any five-axis CNC machines.     

Thinning algorithms based on quadtree and octree representations

Thinning is a critical pre-processing step to obtain skeletons for pattern analysis. Quadtree and octree are hierarchical data representations in image processing and computer graphics. In this paper, we present new 2-D area-based and 3-D surface-based thinning algorithms for directly converting quadtree and octree representations to skeletons. The computational complexity of our thinning algorithm for a 2-D or a 3-D image with each length N is respectively O(N²) or O(N³), which is more efficient than the existing algorithms of O(N³) or O(N⁴). Furthermore, our thinning algorithms can lessen boundary noise spurs and are suited for parallel implementation.     

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

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

一种有效的序列断层图象的八元树构造算法

利用八元树进行物体的三维重是一种十分有效的方法。本文针对医国学图象处理中的实体三维重建顺分析了序断层图象的空间布局和八元树结构的荐,提出了一种通过断层序列图象直接建立八元树的快速算法,并易于在微机上编程实现该算法。     

Topological analysis of 3D building models using a spatial query language

The paper presents parts of the development of a spatial query language for building information models. Such a query language enables the spatial analysis of building information models and the extraction of partial models that fulfill certain spatial constraints. Among other features, it includes topological operators, i.e. operators that reflect the topological relationships between 3D spatial objects. The paper presents definitions of the semantics of the topological operators within, contain, touch, overlap, disjoint and equal in 3D space by using the 9-intersection model. It further describes a possible implementation of the topological operators by means of an octree-based algorithm. The recursive algorithm presented in this article relies on a breadth-first traversal of the operands’ octree representations and the application of rules that are based on the color of the octants under examination. Because it successively increases the discrete resolution of the spatial objects employed, the algorithm enables the user on the one hand to handle topological relationships in a fuzzy manner and on the other hand to trade-off between computational effort and the required accuracy. The article also presents detailed investigations on the runtime performance of the developed algorithm.     

A linear-time algorithm for linearL 1 approximation of points

In this paper we present a linear-time algorithm for approximating a set ofn points by a linear function, or a line, that minimizes theL ₁ norm. The algorithmic complexity of this problem appears not to have been investigated, although anO(n ³) naive algorithm can be easily obtained based on some simple characteristics of an optimumL ₁ solution. Our linear-time algorithm is optimal within a constant factor and enables us to use linearL ₁ approximation of many points in practice. The complexity ofL ₁ linear approximation of a piecewise linear function is also touched upon.     

Efficient implementation of algorithms for approximate exponentiation

We present efficient implementations of algorithms for the following fundamental problem: Given as input three positive integers x, y and j, compute the leading j digits of xy. A special case of this problem (k=2 and j=1) was recently studied by Hirvensalo and Karhumaki [M.Hirvensalo, J.Karhumaki, Computing partial information out of uncomputable one—The first digit of n² to base 3 as an example, in: Mathematical Foundations of Computer Science, in: Lecture Notes in Computer Science, Springer-Verlag, Inc., 2002] for which they presented a polynomial time algorithm. Specifically an algorithm of bit complexity O(n²log³nloglogn) where n=|y| is the number of digits in y. But their algorithm is not efficient in practice. For example, finding the leading digit of y² where y is a 500 digit positive integer takes several hours. Hirvensalo and Karhumaki's algorithm is based on computing a rational approximation to ln2 (and a few other constants) to a high-degree of precision. Our approach is fundamentally different from theirs: we use a modified addition chain algorithm in which the multiplication is truncated to varying number of digits at various steps, followed by a self-tester that validates the truncation. Our algorithm runs several orders of magnitude faster. For example, on an input in which x and y have a few thousand digits, our program computes the leading 1000 digits in under 3 minutes. Since the approximate exponentiation has many application [B.Ravikumar, A Las Vegas randomized approximation algorithm for approximate exponentiation and its applications, in preparation] we hope that our algorithm will stimulate further research on this problem.     

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.     

Rigidity checking of 3D point correspondences under perspectiveprojection

An algorithm is described which rapidly verifies the potential rigidity of three-dimensional point correspondences from a pair of two-dimensional views under perspective projection. The output of the algorithm is a simple yes or no answer to the question “Could these corresponding points from two views be the projection of a rigid configuration?” Potential applications include 3D object recognition from a single previous view and correspondence matching for stereo or motion over widely separated views. The rigidity checking problem is different from the structure-from-motion problem because it is often the case that two views cannot provide an accurate structure-from-motion estimate due to ambiguity and ill conditioning, whereas it is still possible to give an accurate yes/no answer to the rigidity question. Rigidity checking verifies point correspondences using 3D recovery equations as a matching condition. The proposed algorithm improves upon other methods that fall under this approach because it works with as few as six corresponding points under full perspective projection, handles correspondences from widely separated views, makes full use of the disparity of the correspondences, and is integrated with a linear algorithm for 3D recovery due to Kontsevich (1993). Results are given for experiments with synthetic and real image data. A complete implementation of this algorithm is being made publicly available     

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.     

针对全空子数据体的GPU体绘制

目的 体绘制是3维数据可视化的主要方法之一。用于体绘制的数据体中包含有大量的空体素,导致光线投射算法进行没有意义的重采样计算,必然降低绘制算法效率。针对全空子数据体体绘制低效问题,提出基于GPU体高效绘制方法。方法 利用八叉树数据结构组织数据,有效管理包含许多空体素的子数据体。通过绘制八叉树非全空叶子节点子数据体表面,使光线投射算法中起始和终止重采样位置更接近数据体中的可视部分,同时根据八叉树全空节点子数据体判定纹理查询结果,计算合适的跳跃步长,快速跳过八叉树中全空节点子数据体。结果 当数据体中空体素较多时,确定合适的八叉树深度,有效地跳过数据体中的空体素,减少体绘制运算量,实现对原基于体包围盒表面绘制的GPU光线投射算法的加速。结论 设计不透明度函数,凸显数据体中层位面,并将算法成功应用于地震数据可视化,取得很好应用效果。     

Shape recovery from turntable sequence using rim reconstruction

This paper makes use of both feature points and silhouettes to deliver fast 3D shape recovery. The algorithm exploits object silhouettes in two views to establish a 3D rim curve, which is defined with respect to the two frontier points arising from two views. The images of this 3D rim curve in the two views are matched using cross-correlation technique. A 3D planar rim curve is then reconstructed using point-based reconstruction method. A set of 3D rim curves enclosing the object can be obtained from an image sequence captured under circular motion. Silhouettes are further utilized to check for mismatched rim points. The proposed method solves the problem of reconstruction of concave object surface, which is usually left unresolved in general silhouette-based reconstruction methods. In addition, the property of the reconstructed 3D rim curves allows fast surface extraction. Experimental results with real data are presented.     

Two-stage continuation algorithms for Bloch waves of Bose-Einstein condensates in optical lattices

Bloch waves of Bose-Einstein condensates (BEC) in optical lattices are extremum nonlinear eigenstates which satisfy the time-independent Gross-Pitaevskii equation (GPE). We describe an efficient Taylor predictor-Newton corrector continuation algorithm for tracing solution curves of parameter-dependent problems. Based on this algorithm, a novel two-stage continuation algorithm is developed for computing Bloch waves of 1D and 2D Bose-Einstein condensates (BEC) in optical lattices. We split the complex wave function into the sum of its real and imaginary parts. The original GPE becomes a couple of two nonlinear eigenvalue problems defined in the real domain with periodic boundary conditions. At the first stage we use the chemical potential μ as the continuation parameter. The Bloch wavenumber k(kx,ky), and the coefficient of the cubic term are treated as the second and third continuation parameters, respectively. Then we compute the Bloch bands/surfaces for the 1D/2D problem with linear counterparts. At the second stage we use μ and k/kx or ky as the continuation parameters simultaneously with two constraint conditions. The states without linear counterparts in the GPE can be obtained via states with linear counterparts. Numerical results are reported for both 1D and 2D problems.