Consistent Volumetric Discretizations Inside Self‐Intersecting Surfaces

Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self‐intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet‐meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self‐intersections in the input surface. This enables volumetric processing on self‐intersecting models. We leverage conformalized mean‐curvature flow, which removes self‐intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.     

集群计算环境下的三维表面重建

讨论了一种在集群计算环境下将物体各个方向的表面片拼接起来形成物体完整表面的算法．通过采样计算出体素到每个表面片的最近距离,利用添加策略计算出每个体素的权重距离,再利用行进块算法抽取出物体表面．实验结果表明,该算法在普通的PC集群上并行计算,可以大大减少建模的时间,特别是在大数据量时,加速的效果更加明显。     

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.     

Computing Local Signed Distance Fields for Large Polygonal Models

The signed distance field for a polygonal model is a useful representation that facilitates efficient computation in many visualization and geometric processing tasks. Often it is more effective to build a local distance field only within a narrow band around the surface that holds local geometric information for the model. In this paper, we present a novel technique to construct a volumetric local signed distance field of a polygonal model. To compute the local field efficiently, exactly those cells that cross the polygonal surface are found first through a new voxelization method, building a list of intersecting triangles for each boundary cell. After their neighboring cells are classified, the triangle lists are exploited to compute the local signed distance field with minimized voxel‐to‐triangle distance computations. While several efficient methods for computing the distance field, particularly those harnessing the graphics processing unit's (GPU's) processing power, have recently been proposed, we focus on a CPU‐based technique, intended to deal flexibly with large polygonal models and high‐resolution grids that are often too bulky for GPU computation.     

基于压缩体素模型的鼓形刀空间扫描体构造方法及其应用

首先给出了鼓形刀空间扫描体构造公式并构造出其表面模型,利用Ray Casting方法将该表面模型进行离散,转化为压缩体素模型,该模型采用沿X,Y,Z3个坐标轴方向相互垂直的Dexel模型表示,各个Dexel模型之间按体素模型大小均匀分布．刀具空间扫描体模型和仿真工件模型之间的布尔运算转化为Dexel模型之间的一维布尔运算,简化了布尔操作并提高了操作速度．通过MarchingCubes方法提取数控加工仿真工件表面三角网格模型并进行图形显示,提高了仿真工件显示质量,NC编程人员可实时地从任意方向观察、验证仿真结果．该方法已成功地应用于基于压缩体素模型的五坐标数控加工仿真系统中,克服了现有五坐标数控加工仿真方法和商品化软件系统的不足．     

Computing on rays: A parallel approach for surface mesh modeling from multi-material volumetric data

Ray representation (Ray-rep) of a solid has been studied and used in the solid modeling community for many years because of its compactness and simplicity. This paper presents a parallel approach for mesh surface modeling from multi-material volume data using an extended Ray-rep as an intermediate, where every homogeneous region is enclosed by a set of two-manifold surface meshes on the resultant model. The approach consists of three major algorithms: firstly, an algorithm is developed to convert the given multi-material volumetric data into a Ray-rep for heterogeneous solid; secondly, filtering algorithm is exploited to process the rays of heterogeneous solid in parallel; and lastly, the adaptive mesh surfaces are generated from the Ray-rep through a dual-contouring like algorithm. Here the intermediate surfaces between two constituent materials can be directly extracted without building the volumetric mesh, and the manifold topology is preserved on each surface patch. Furthermore, general offset surface can be easily computed in this paradigm by designing a special parallel operator for the rays.     

Efficient Computation of Smoothed Exponential Maps

Many applications in geometry processing require the computation of local parameterizations on a surface mesh at interactive rates. A popular approach is to compute local exponential maps, i.e. parameterizations that preserve distance and angle to the origin of the map. We extend the computation of geodesic distance by heat diffusion to also determine angular information for the geodesic curves. This approach has two important benefits compared to fast approximate as well as exact forward tracing of the distance function: First, it allows generating smoother maps, avoiding discontinuities. Second, exploiting the factorization of the global Laplace–Beltrami operator of the mesh and using recent localized solution techniques, the computation is more efficient even compared to fast approximate solutions based on Dijkstra's algorithm.     

Implicit and Nonparametric Shape Reconstruction from Unorganized Data Using a Variational Level Set Method

In this paper we consider a fundamental visualization problem: shape reconstruction from an unorganized data set. A new minimal-surface-like model and its variational and partial differential equation (PDE) formulation are introduced. In our formulation only distance to the data set is used as our input. Moreover, the distance is computed with optimal speed using a new numerical PDE algorithm. The data set can include points, curves, and surface patches. Our model has a natural scaling in the nonlinear regularization that allows flexibility close to the data set while it also minimizes oscillations between data points. To find the final shape, we continuously deform an initial surface following the gradient flow of our energy functional. An offset (an exterior contour) of the distance function to the data set is used as our initial surface. We have developed a new and efficient algorithm to find this initial surface. We use the level set method in our numerical computation in order to capture the deformation of the initial surface and to find an implicit representation (using the signed distance function) of the final shape on a fixed rectangular grid. Our variational/PDE approach using the level set method allows us to handle complicated topologies and noisy or highly nonuniform data sets quite easily. The constructed shape is smoother than any piecewise linear reconstruction. Moreover, our approach is easily scalable for different resolutions and works in any number of space dimensions.     

Memory‐Efficient Interactive Online Reconstruction From Depth Image Streams

We describe how the pipeline for 3D online reconstruction using commodity depth and image scanning hardware can be made scalable for large spatial extents and high scanning resolutions. Our modified pipeline requires less than 10% of the memory that is required by previous approaches at similar speed and resolution. To achieve this, we avoid storing a 3D distance field and weight map during online scene reconstruction. Instead, surface samples are binned into a high‐resolution binary voxel grid. This grid is used in combination with caching and deferred processing of depth images to reconstruct the scene geometry. For pose estimation, GPU ray‐casting is performed on the binary voxel grid. A one‐to‐one comparison to level‐set ray‐casting in a distance volume indicates slightly lower pose accuracy. To enable unlimited spatial extents and store acquired samples at the appropriate level of detail, we combine a hash map with a hierarchical tree representation.     

Practical Foldover‐Free Volumetric Mapping Construction

In this paper, we present a practically robust method for computing foldover‐free volumetric mappings with hard linear constraints. Central to this approach is a projection algorithm that monotonically and efficiently decreases the distance from the mapping to the bounded conformal distortion mapping space. After projection, the conformal distortion of the updated mapping tends to be below the given bound, thereby significantly reducing foldovers. Since it is non‐trivial to define an optimal bound, we introduce a practical conformal distortion bound generation scheme to facilitate subsequent projections. By iteratively generating conformal distortion bounds and trying to project mappings into bounded conformal distortion spaces monotonically, our algorithm achieves high‐quality foldover‐free volumetric mappings with strong practical robustness and high efficiency. Compared with existing methods, our method computes mesh‐based and meshless volumetric mappings with no prescribed conformal distortion bounds. We demonstrate the efficacy and efficiency of our method through a variety of geometric processing tasks.     

Hybrid mesh‐volume LoDs for all‐scale pre‐filtering of complex 3D assets

We address the problem of constructing appearance‐preserving level of details (LoDs) of complex 3D models such as trees. We propose a hybrid method that combines the strengths of mesh and volume representations. Our main idea is to separate macroscopic (i.e. larger than the target spatial resolution) and microscopic (sub‐resolution) surfaces at each scale and to treat them differently, because meshes are very efficient at representing macroscopic surfaces while sub‐resolution geometry benefits from volumetric approximations. We introduce a new algorithm that detects the macroscopic surfaces of a mesh for a given resolution. We simplify these surfaces with edge collapses and we provide a method for pre‐filtering their normal distributions and albedos. To approximate microscopic details, we use a heterogeneous microflake participating medium and we introduce a new artifact‐free voxelization algorithm that preserves local occlusion. Thanks to our macroscopic surface analysis, our algorithm is fully automatic and it generates seamless LoDs at arbitrarily coarse resolutions for a wide range of 3D models.     

Shape‐Up: Shaping Discrete Geometry with Projections

We introduce a unified optimization framework for geometry processing based on shape constraints. These constraints preserve or prescribe the shape of subsets of the points of a geometric data set, such as polygons, one‐ring cells, volume elements, or feature curves. Our method is based on two key concepts: a shape proximity function and shape projection operators. The proximity function encodes the distance of a desired least‐squares fitted elementary target shape to the corresponding vertices of the 3D model. Projection operators are employed to minimize the proximity function by relocating vertices in a minimal way to match the imposed shape constraints. We demonstrate that this approach leads to a simple, robust, and efficient algorithm that allows implementing a variety of geometry processing applications, simply by combining suitable projection operators. We show examples for computing planar and circular meshes, shape space exploration, mesh quality improvement, shape‐preserving deformation, and conformal parametrization. Our optimization framework provides a systematic way of building new solvers for geometry processing and produces similar or better results than state‐of‐the‐art methods.     

Freeform Shape Representations for Efficient Geometry Processing

The most important concepts for the handling and storage of freeform shapes in geometry processing applications are parametric representations and volumetric representations. Both have their specific advantages and drawbacks. While the algebraic complexity of volumetric representations is independent from the shape complexity, the domain of a parametric representation usually has to have the same structure as the surface itself (which sometimes makes it necessary to update the domain when the surface is modified). On the other hand, the topology of a parametrically defined surface can be controlled explicitly while in a volumetric representation, the surface topology can change accidentally during deformation. A volumetric representation reduces distance queries or inside/outside tests to mere function evaluations but the geodesic neighborhood relation between surface points is difficult to resolve. As a consequence, it seems promising to combine parametric and volumetric representations to effectively exploit both advantages. In this talk, a number of projects are presented and discussed in which such a combination leads to efficient and numerically stable algorithms for the solution of various geometry processing tasks. Applications include global error control for mesh decimation and smoothing, topology control for level‐set surfaces, and shape modeling with unstructured point clouds.     

Fast ray-tracing of rectilinear volume data using distancetransforms

The paper discusses and experimentally compares distance based acceleration algorithms for ray tracing of volumetric data with an emphasis on the Chessboard Distance (CD) voxel traversal. The acceleration of this class of algorithms is achieved by skipping empty macro regions, which are defined for each background voxel of the volume. Background voxels are labeled in a preprocessing phase by a value, defining the macro region size, which is equal to the voxel distance to the nearest foreground voxel. The CD algorithm exploits the chessboard distance and defines the ray as a nonuniform sequence of samples positioned at voxel faces. This feature assures that no foreground voxels are missed during the scene traversal. Further, due to parallelepipedal shape of the macro region, it supports accelerated visualization of cubic, regular, and rectilinear grids. The CD algorithm is suitable for all modifications of the ray tracing/ray casting techniques being used in volume visualization and volume graphics. However, when used for rendering based on local surface interpolation, it also enables fast search of intersections between rays and the interpolated surface, further improving speed of the process     

Extended linked voxel structure for point-to-mesh distance computation and its application to NC collision detection

When working with milling or polishing robots and large workpieces it is necessary to check not only the milling or polishing tool for collision, but it is also necessary to check the remaining arms of the robot for collision. In most of the cases the arms of the robot do not collide with the workpiece and so applying an existing collision detection algorithm to the arms of the robot slows the process down. In this paper, we present an algorithm for quickly assuring non-collisions, which is especially targeted at collisions of the arms of the robot with a workpiece. The algorithm is based on an extended voxel structure. More precisely, we extend a voxel structure by adding distance values to the corner of the voxels and by linking empty voxels to non-empty voxels to accelerate finding the desired voxel. This ensures that we only need to consider a small subset of the triangles describing the workpiece’s surface, namely those triangles that are close to the possible collision area. The triangles within each non-empty voxel are stored in a bsp-tree. For empty voxels, we save information about the distances to the mesh. This setup speeds up the point-to-mesh distance calculation, especially for points close to the mesh. The extra distance information in empty voxels enables a fast distance estimation and hence a fast early collision check.     

Hybrid Booleans

In this paper, we present a novel method to compute Boolean operations on polygonal meshes. Given a Boolean expression over an arbitrary number of input meshes we reliably and efficiently compute an output mesh which faithfully preserves the existing sharp features and precisely reconstructs the new features appearing along the intersections of the input meshes. The term "hybrid" applies to our method in two ways: First, our algorithm operates on a hybrid data structure which stores the original input polygons (surface data) in an adaptively refined octree (volume data). By this we combine the robustness of volumetric techniques with the accuracy of surface-oriented techniques. Second, we generate a new triangulation only in a close vicinity around the intersections of the input meshes and thus preserve as much of the original mesh structure as possible (hybrid mesh). Since the actual processing of the Boolean operation is confined to a very small region around the intersections of the input meshes, we can achieve very high adaptive refinement resolutions and hence very high precision. We demonstrate our method on a number of challenging examples.     

Approximate on‐Surface Distance Computation using Quasi‐Developable Charts

There is a vast number of applications that require distance field computation over triangular meshes. State‐of‐the‐art algorithms have quadratic or sub‐quadratic worst‐case complexity, making them impractical for interactive applications. While most of the research on this subject has been focused on reducing the computation complexity of the algorithms, in this work we propose an approximate algorithm that achieves similar results working in lower resolutions of the input meshes. The creation of lower resolution meshes is the essence of our proposal. The idea is to identify regions on the input mesh that can be unfolded into planar regions with minimal area distortion (i.e. quasi‐developable charts). Once charts are computed, their interior is re‐triangulated to reduce the number of triangles, which results in a collection of simplified charts that we call a base mesh. Due to the properties of quasi‐developable regions, we are able to compute distance fields over the base mesh instead of over the input mesh. This reduces the memory footprint and data processed for distance computations, which is the bottleneck of these algorithms. We present results that are one order of magnitude faster than current exact solutions, with low approximation errors.     

Streaming 3D deforming surfaces with dynamic resolution control

Real‐time streaming of shape deformations in a shared distributed virtual environment is a challenging task due to the difficulty of transmitting large amounts of 3D animation data to multiple receiving parties at a high frame rate. In this paper, we present a framework for streaming 3D shape deformations, which allows shapes with multi‐resolutions to share the same deformations simultaneously in real time. The geometry and motion of deforming mesh or point‐sampled surfaces are compactly encoded, transmitted, and reconstructed using the spectra of the manifold harmonics. A receiver‐based multi‐resolution surface reconstruction approach is introduced, which allows deforming shapes to switch smoothly between continuous multi‐resolutions. On the basis of this dynamic reconstruction scheme, a frame rate control algorithm is further proposed to achieve rendering at interactive rates. We also demonstrate an efficient interpolation‐based strategy to reduce computing of deformation. The experiments conducted on both mesh and point‐sampled surfaces show that our approach achieves efficient performance even if deformations of complex 3D surfaces are streamed. Copyright © 2013 John Wiley & Sons, Ltd.     

Computing the medial surface of a 3-D boundary representation model

Medial surface, the skeletal abstraction of a solid shape, can be used in applications such as shell (solid) mesh generation, robot path planning, and feature recognition. Unfortunately, computing the medical surface is very difficult. Those few algorithms proposed invariably need to solve systems of non-linear polynomial equations, which requires complicated numerical techniques. Recently, an algorithm has been proposed by the authors that is applicable to a polyhedral model. It uses voxel-bisector intersection relationships to calculate the intersection points and, from these, constructs the boundaries of the medical surface patches. Unfortunately, it does not handle the degenerate cases. This paper extends the scope of the voxel-bisector intersection algorithm by proposing a supplementary algorithm to detect the existence of the degenerate intersection curve in a specified region (voxel). An enhancement to the voxel-bisector intersection algorithm by using the Voronoi territory, which needs no polynomial root-finding scheme, is also proposed.