Reconstruction of 3D Object Meshes from Silhouette Images

In this work we propose a method for computing mesh representations of 3D objects reconstructed from a set of silhouette images. Our method is based on the polygonization of volumetric reconstructions by using a modified version of the dual contouring method. In order to apply dual contouring on volumetric reconstruction from silhouettes we devised a method that is able to determine the discrete topology of the surface in relation to the octree cells. We also developed a new scheme for computing hermitian data representing the intersections of conic volumes with the octree cells and their corresponding normals with subpixel accuracy. Due to the discrete and extremely noisy nature of the data used in the reconstruction we had to devise a different criterion for mesh simplification that applies topological consistency tests only when the geometric error measure is beyond a given tolerance. We present results of the application of the proposed method in the extraction of a mesh corresponding to the surface of objects of a real scene.     

Automatic generation of LEGO building instructions from multiple photographic images of real objects

We introduce a system to reconstruct large scale LEGO models from multiple two dimensional images of objects taken from different views. We employ a unit voxel with an edge length ratio of 5:5:6 for the shape from silhouette method that reconstructs an octree voxel-based three dimensional model with color information from images. We then convert the resulting voxel model with color information into a LEGO sculpture. In order to minimize the number of LEGO bricks, we use a stochastic global optimization method, simulated annealing, to hollow the model as much as possible but keep its strength for portability. Several real complex LEGO models are provided to demonstrate the effectiveness of the proposed method.     

Out‐of‐Core Construction of Sparse Voxel Octrees

Voxel‐based rendering has recently received significant attention due to its potential in the context of efficiently rendering massively large and highly detailed scenes. Unfortunately, few scenes are available in the form of sparse voxel octrees. In this paper, we present an out‐of‐core algorithm for constructing a sparse voxel octree from a triangle mesh. Our algorithm allows the input triangle mesh, the output sparse voxel octree and, most importantly, the intermediate high‐resolution 3D voxel grid, to be larger than available memory. We demonstrate that our out‐of‐core algorithm can construct sparse voxel octrees from triangle meshes using only a fraction of the memory required by an in‐core algorithm in roughly the same time, and that our out‐of‐core algorithm can also handle extremely large triangle meshes.     

Discrete Ray-Tracing of Huge Voxel Spaces

The quality of images produced by Discrete Ray-Tracing voxel spaces is highly dependent on 3d grid resolution. The huge amount of memory needed to store such grids often discards discrete Ray-Tracing as a practical visualization algorithm. The use of an octree can drastically change this when most of space is empty, as such is the case in most scenes. Although the memory problem can be bypassed using the octree, the performance problem still remains. A known fact is that the performance of discrete traversal is optimal for quite low resolutions. This problem can be easily solved by dividing the task in two steps, working in two low resolutions instead of just one high resolution, thus taking advantage of optimal times in both steps. This is possible thanks to the octree property of representing the same scene in several different resolutions. This article presents a two step Discrete Ray-Tracing method using an octree and shows, by comparing it with the single step version, that a substantial gain in performance is achieved.     

Stable Real-Time Surgical Cutting Simulation of Deformable Objects Embedded with Arbitrary Triangular Meshes

Surgical simulators need to simulate deformation and cutting of deformable objects. Adaptive octree mesh based cutting methods embed the deformable objects into octree meshes that are recursively refined near the cutting tool trajectory. Deformation is only applied to the octree meshes; thus the deformation instability problem caused by degenerated elements is avoided. Biological tissues and organs usually contain complex internal structures that are ignored by previous work. In this paper the deformable objects are modeled as voxels connected by links and embedded inside adaptive octree meshes. Links swept by the cutting tool are disconnected and object surface meshes are reconstructed from disconnected links. Two novel methods for embedding triangular meshes as internal structures are proposed. The surface mesh embedding method is applicable to arbitrary triangular meshes, but these meshes have no physical properties. The material sub-region embedding method associates the interiors enclosed by the triangular meshes with physical properties, but requires that these meshes are watertight, and have no self-intersections, and their smallest features are larger than a voxel. Some local features are constructed in a pre-calculation stage to increase simulation performance. Simulation tests show that our methods can cut embedded structures in a way consistent with the cutting of the deformable objects. Cut fragments can also deform correctly along with the deformable objects.     

Constructing isosurfaces from CT data

An algorithm that automatically produces polygonal representations of 3-D structures within a volume from a set of cross-sectional images is presented. The method incorporates the requirements necessary for structure analysis to go beyond plain rendering. The algorithm is fully automatic, using local voxel values to determine the connectivity of the surface. The resulting polygons are coherently ordered and connected, and no polygon occurs more than once. Each surface is complete, that is, no holes occur (except as an option, on the boundaries of the volume). The algorithm can be used to describe and visualize normal as well as pathological anatomy     

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.     

A volumetric fusion technique for surface reconstruction from silhouettes and range data

Optical triangulation, an active reconstruction technique, is known to be an accurate method but has several shortcomings due to occlusion and laser reflectance properties of the object surface, that often lead to holes and inaccuracies on the recovered surface. Shape from silhouette, on the other hand, as a passive reconstruction technique, yields robust, hole-free reconstruction of the visual hull of the object. In this paper, a hybrid surface reconstruction method that fuses geometrical information acquired from silhouette images and optical triangulation is presented. Our motivation is to recover the geometry from silhouettes on those parts of the surface which the range data fail to capture. A volumetric octree representation is first obtained from the silhouette images and then carved by range points to amend the missing cavity information. An isolevel value on each surface cube of the carved octree structure is accumulated using local surface triangulations obtained separately from range data and silhouettes. The marching cubes algorithm is then applied for triangulation of the volumetric representation. The performance of the proposed technique is demonstrated on several real objects.     

Polygonization of implicit surfaces

This paper discusses a numerical technique that approximates an implicit surface with a polygonal representation. The implicit function is adaptively sampled as it is surrounded by a spatial partitioning. The partitioning is represented by an octree, which may either converge to the surface or track it. A piecewise polygonal representation is derived from the octree.

The technique is insensitive to the complexity of the implicit function, allowing the designer great latitude. With a polygonal representation of the surface available, certain computational economies result; in particular, the roots to the function need not be solved each time the surface is rendered.     

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

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

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.     

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

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

From A Medial Surface To A Mesh

Medial surfaces are well‐known and interesting surface skeletons. As such, they can describe the topology and the geometry of a 3D closed object. The link between an object and its medial surface is also intuitively understood by people. We want to exploit such skeletons to use them in applications like shape creation and shape deformation. For this purpose, we need to define medial surfaces as Shape Representation Models (SRMs). One of the very first task of a SRM is to offer a visualization of the shape it describes. However, achieving this with a medial surface remains a challenging problem. In this paper, we propose a method to build a mesh that approximates an object only described by a medial surface. To do so, we use a volumetric approach based on the construction of an octree. Then, we mesh the boundary of that octree to get a coarse approximation of the object. Finally, we refine this mesh using an original migration algorithm. Quantitative and qualitative studies, on objects coming from digital modeling and laser scans, shows the efficiency of our method in providing high quality surfaces with a reasonable computational complexity.     

A flexible multi-volume shader framework for arbitrarily intersecting multi-resolution datasets

We present a powerful framework for 3D-texture-based rendering of multiple arbitrarily intersecting volumetric datasets. Each volume is represented by a multi-resolution octree-based structure and we use out-of-core techniques to support extremely large volumes. Users define a set of convex polyhedral volume lenses, which may be associated with one or more volumetric datasets. The volumes or the lenses can be interactively moved around while the region inside each lens is rendered using interactively defined multi-volume shaders. Our rendering pipeline splits each lens into multiple convex regions such that each region is homogenous and contains a fixed number of volumes. Each such region is further split by the brick boundaries of the associated octree representations. The resulting puzzle of lens fragments is sorted in front-to-back or back-to-front order using a combination of a view-dependent octree traversal and a GPU-based depth peeling technique. Our current implementation uses slice-based volume rendering and allows interactive roaming through multiple intersecting multi-gigabyte volumes.     

A TV Prior for High-Quality Scalable Multi-View Stereo Reconstruction

We present a scalable multi-view stereo method able to reconstruct accurate 3D models from hundreds of high-resolution input images. Local fusion of disparity maps obtained with semi-global matching enables the reconstruction of large scenes that do not fit into main memory. Since disparity maps may vary widely in quality and resolution, careful modeling of the 3D errors is crucial. We derive a sound stereo error model based on disparity uncertainty, which can vary spatially from tenths to several pixels. We introduce a feature based on total variation that allows pixel-wise classification of disparities into different error classes. For each class, we learn a disparity error distribution from ground-truth data using expectation maximization. We present a novel method for stochastic fusion of data with varying quality by adapting a multi-resolution volumetric fusion process that uses our error classes as a prior and models surface probabilities via an octree of voxels. Conflicts during surface extraction are resolved using visibility constraints and preference for voxels at higher resolutions. Experimental results on several challenging large-scale datasets demonstrate that our method yields improved performance both qualitatively and quantitatively.     

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.     

基于体素模型与卷积神经网络的三维模型分类算法

针对传统三维模型分类算法时间复杂度较高、分类准确率较低等问题,提出一种基于体素模型与卷积神经网络的三维模型分类算法。将原始模型表示为八叉树结构的体素模型以优化模型的性状表达,使用设计的卷积神经网络对体素模型进行特征提取以及分类运算。实验结果表明,与其他三维模型分类算法相比,该分类算法的显存占用较小,同时具有较低的时间复杂度和较高的分类能力。     

Interactive Indirect Illumination Using Voxel Cone Tracing

Indirect illumination is an important element for realistic image synthesis, but its computation is expensive and highly dependent on the complexity of the scene and of the BRDF of the involved surfaces. While off‐line computation and pre‐baking can be acceptable for some cases, many applications (games, simulators, etc.) require real‐time or interactive approaches to evaluate indirect illumination. We present a novel algorithm to compute indirect lighting in real‐time that avoids costly precomputation steps and is not restricted to low‐frequency illumination. It is based on a hierarchical voxel octree representation generated and updated on the fly from a regular scene mesh coupled with an approximate voxel cone tracing that allows for a fast estimation of the visibility and incoming energy. Our approach can manage two light bounces for both Lambertian and glossy materials at interactive framerates (25–70FPS). It exhibits an almost scene‐independent performance and can handle complex scenes with dynamic content thanks to an interactive octree‐voxelization scheme. In addition, we demonstrate that our voxel cone tracing can be used to efficiently estimate Ambient Occlusion.     

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.