Offsetting operations on non-manifold topological models

This paper describes non-manifold offsetting operations that add or remove a uniform thickness from a given non-manifold topological model. The mathematical definitions and properties of the non-manifold offsetting operations are investigated first, and then an offset algorithm based on the definitions is proposed and implemented using the non-manifold Euler operators proposed in this paper. In this algorithm, the offset elements of minimal size for the vertices, edges and faces of a given non-manifold model are generated first. Then, they are united into a single body using the non-manifold Boolean operations. In order to reduce computation time and numerical errors, the intersections between the offset elements are calculated considering the origins of the topological entities during union. Finally, all topological entities that are within the offset distance are detected and removed in turn. In addition to the original offset algorithm based on mathematical definitions, some variant offset algorithms, called sheet thickening and solid shelling, are proposed and implemented for more practical and efficient solid modeling of thin-walled plastic or sheet metal parts. In virtue of the proposed non-manifold offset operation and its variations, different offsetting operations for wireframes, sheets and solids can be integrated into one and applied to a wide range of applications with a great potential usefulness.     

A new approach to z-level contour machining of triangulated surface models using fillet endmills

Precision z-level contour machining is important for various computer-aided manufacturing (CAM) applications such as pocket machining and high-speed machining (HSM). This paper presents a new z-level contour tool-path generation algorithm for NC machining of triangulated surface models. Traditional approaches of z-level machining rely on the creation of accurate CL (cutter location) surfaces by surface offsetting or high-density z-map generation, which is computationally expensive and memory demanding. In contrast, this paper presents a novel approach to the generation of CL data directly from the section polygon of a triangulated surface model. For each polygon vertex of the contour, the offset direction is determined by the normal to the edge, while the offset distance is not fixed but is determined from the cutter shape and the part surface. An interference-free tool-path computation algorithm using fillet endmills is developed. Since there is no need to create a complete CL surface or high-density z-map grids, this proposed method is highly efficient and more flexible, and can be directly applied to triangulated surfaces either tessellated from CAD models, or reconstructed from 3D scanned data for reverse engineering (RE) applications.     

Error analysis of reparametrization based approaches for curve offsetting

This paper proposes an error analysis of reparametrization based approaches for planar curve offsetting. The approximation error in Hausdorff distance is computed. The error is bounded by O(rsin²β), where r is the offset radius and β is the angle deviation of a difference vector from the normal vector. From the error bound an interesting geometric property of the approach is observed: when the original curve is offset in its convex side, the approximate offset curve always lies in the concave side of the exact offset, that is, the approximate offset is contained within the region bounded by the exact offset curve and the original curve. Our results improve the error estimation of the circle approximation approaches, as well as the computation efficiency when the methods are applied iteratively for high precision approximation.     

Offset of curves on tessellated surfaces

Geodesic offset of curves on surfaces is an important and useful tool of computer aided design for applications such as generation of tool paths for NC machining and simulation of fibre path on tool surfaces in composites manufacturing. For many industrial and graphic applications, tessellation representation is used for curves and surfaces because of its simplicity in representation and for simpler and faster geometric operations. The paper presents an algorithm for computing offset of curves on tessellated surfaces. A curve on tessellation (COT) is represented as a sequence of 3D points, with each line segment of every two consecutive points lying exactly on the tessellation. With an incremental approach of the algorithm to compute offset COT, the final offset curve position is obtained through several intermediate offset curve positions. Each offset curve position is obtained by offsetting all the points of COT along the tessellation in such a way that all the line segments gets offset exactly along the faces of tessellation in which the line segments are contained. The algorithm, based entirely on tessellation representation, completely eliminates the formation of local self-intersections. Global self-intersections if any, are detected and corrected explicitly. Offset of both open and closed tessellated curves, either in a plane or on a tessellated surface, can be generated using the proposed approach. The computation of offset COT is very accurate within the tessellation tolerance.     

Uniform offsetting of polygonal model based on Layered Depth-Normal Images

Uniform offsetting is an important geometric operation for computer-aided design and manufacturing (CAD/CAM) applications such as rapid prototyping, NC machining, coordinate measuring machines, robot collision avoidance, and Hausdorff error calculation. We present a novel method for offsetting (grown and shrunk) a solid model by an arbitrary distance r. First, offset polygons are directly computed for each face, edge, and vertex of an input solid model. The computed polygonal meshes form a continuous boundary; however, such a boundary is invalid since there exist meshes that are closer to the original model than the given distance r as well as self-intersections. Based on the problematic polygonal meshes, we construct a well-structured point-based model, Layered Depth-Normal Image (LDNI), in three orthogonal directions. The accuracy of the generated point-based model can be controlled by setting the tessellation and sampling rates during the construction process. We then process all the sampling points in the model by using a set of point filters to delete all the invalid points. Based on the remaining points, we construct a two-manifold polygonal contour as the resulting offset boundary. Our method is general, simple and efficient. We report experimental results on a variety of CAD models and discuss various applications of the developed uniform offsetting method.     

Modifying free-formed NURBS curves and surfaces for offsetting without local self-intersection

This paper presents an algorithm of modifying free-formed NURBS curve/surface for offsetting without local self-intersecting. The method consists of (1) sampling a number of points from a progenitor curve/surface based on second derivatives; (2) checking the curvature or maximum curvature of the progenitor curve/surface at the sampled points; (3) inserting corresponding knots of sampled points; (4) repositioning control points till the curvature/maximum curvature of the curve/surface everywhere are less than the reciprocal of offset distance. The method is efficient and is able to obtain better offsetting results.     

离散曲面的等距面生成算法

离散曲面的等距面生成问题是一个不同于传统的等距面计算的新问题。拟对该问题展开研究并提出一个有效的离散曲面的等距面生成算法。该算法通过计算离散曲面的包络面上的离散体元而生成等距面。所提算法可以有效地解决等距计算过程中发生的拓扑、自相交等现象。实验结果表明了该算法的有效性。     

Interpolation by geometric algorithm

We present a novel geometric algorithm to construct a smooth surface that interpolates a triangular or a quadrilateral mesh of arbitrary topological type formed by n vertices. Although our method can be applied to B-spline surfaces and subdivision surfaces of all kinds, we illustrate our algorithm focusing on Loop subdivision surfaces as most of the meshes are in triangular form. We start our algorithm by assuming that the given triangular mesh is a control net of a Loop subdivision surface. The control points are iteratively updated globally by a simple local point-surface distance computation and an offsetting procedure without solving a linear system. The complexity of our algorithm is O(mn) where n is the number of vertices and m is the number of iterations. The number of iterations m depends on the fineness of the mesh and accuracy required.     

Computing offsets of trimmed NURBS surfaces

Offsetting of trimmed NURBS surfaces is one of the widely used functionalities in the design and manufacture simulations of composite laminates. This paper presents an approach for the offsetting of a trimmed NURBS surface. The approach has been developed mainly to meet the stringent accuracy requirements in the simulation of composite laminate design and manufacturing processes. However, the approach is applicable for the offset of a general trimmed NURBS surface. Though the method is based on known techniques in literature, the practical approach and the treatment of the subject presented is unique and has not been reported earlier. The basic approach consists of offsetting the underlying surface, offsetting of all the trimming loops and the creation of offset trimmed surface using the offset surface and the offset trimming loops. This is a unified offset approach for trimmed surfaces where in the offset of underlying surface and the offset of trimming loops are obtained using the same approach. The approach has better error control and results in less number of control points. Further the approach can be extended to obtain offsets of a general B-Rep. The approach has been used in the creation of offset surfaces of various aircraft components.     

Computing non-self-intersecting offsets of NURBS surfaces

A new approach for the computation of non-self-intersecting offset surface of a single G₁ continuous NURBS surface has been presented. The approach recognizes special surfaces, i.e. planes, spheres, cones and cylinders, and offsets them precisely. An approximate offset surface within the specified tolerance is computed for a general free form surface. The method for a general free form surface consists of (1) sample offset surface based on second derivatives; (2) eliminate sample points which can give self-intersections; (3) surface fitting through the remaining sample points; and (4) removal of all the removable knots of the surface. The approach checks for self-intersections in the offset surface and removes the same automatically, if any. The non-self-intersecting offsets for surface of extrusion and surface of revolution are obtained by removing the self-intersections in the offset generator and profile curves respectively using point sampling, cleaning of sampled points, curve fitting and knot removal. The approach has better control on error. It generates offset surface with less number of control points and degree. The methodology works only for a class of problems where in the offset of a single G₁ surface is still a single connected surface without having any holes. The offset methodology has been demonstrated through three types of surfaces namely surface of revolution, surface of extrusion and a general free form surface. This approach has been extensively used in creation of offset surfaces of composite laminate components. The presented approach can also be used to check for self-intersections in any general surface and to remove the same, if any, with little modifications, as long as the cleaned surface is a single connected surface.     

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.     

Mitered offset for profile machining

In profile machining, it is very important to protect sharp vertices from being eroded. To meet this technological requirement, this paper proposes a mitered offsetting algorithm, which can be used for profiling tool path generation. The proposed algorithm is based on the pair-wise interference-detection (PWID) offset algorithm suggested by Choi and Park (Comput-Aided Des 31 (1999) 735). For mitered offsetting, we expand the PWID offset algorithm by developing a new method to remove global interference.     

BADF: Bounding Volume Hierarchies Centric Adaptive Distance Field Computation for Deformable Objects on GPUs

We present a novel algorithm BADF (Bounding Volume Hierarchy Based Adaptive Distance Fields) for accelerating the construction of ADFs (adaptive distance fields) of rigid and deformable models on graphics processing units. Our approach is based on constructing a bounding volume hierarchy (BVH) and we use that hierarchy to generate an octree-based ADF. We exploit the coherence between successive frames and sort the grid points of the octree to accelerate the computation. Our approach is applicable to rigid and deformable models. Our GPU-based (graphics processing unit based) algorithm is about 20x--50x faster than current mainstream central processing unit based algorithms. Our BADF algorithm can construct the distance fields for deformable models with 60k triangles at interactive rates on an NVIDIA GTX GeForce 1060. Moreover, we observe 3x speedup over prior GPU-based ADF algorithms.     

代数双曲空间中拟Legendre 基的应用

鉴于Legendre 基等正交基在代数多项式空间中的广泛应用,论文在深入 研究代数双曲空间的拟Legendre 基性质的基础上,给出了其在反函数逼近和等距曲线逼近 上的应用。利用多项式和双曲函数的混合多项式序列来逼近反函数,并通过实例证明给出方 法的有效性;对基曲线的法矢曲线进行逼近,构造H-Bézier 曲线的等距曲线的最佳逼近, 这种方法直接求得逼近曲线的控制顶点,计算简单,截断误差小。     

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.     

“Meshsweeper”: dynamic point-to-polygonal mesh distanceand applications

We introduce a new algorithm for computing the distance from a point to an arbitrary polygonal mesh. Our algorithm uses a multiresolution hierarchy of bounding volumes generated by geometric simplification. Our algorithm is dynamic, exploiting coherence between subsequent queries using a priority process and achieving constant time queries in some cases. It can be applied to meshes that transform rigidly or deform nonrigidly. We illustrate our algorithm with a simulation of particle dynamics and collisions with a deformable mesh, the computation of distance maps and offset surfaces, the computation of an approximation to the expensive Hausdorff distance between two shapes, and the detection of self-intersections. We also report comparison results between our algorithm and an alternative algorithm using an octree, upon which our method permits an order-of-magnitude speed-up     

A method to generate soft shadows using a layered depth image and warping

We present an image-based method for propagating area light illumination through a layered depth image (LDI) to generate soft shadows from opaque and nonrefractive transparent objects. In our approach, using the depth peeling technique, we render an LDI from a reference light sample on a planar light source. Light illumination of all pixels in an LDI is then determined for all the other sample points via warping, an image-based rendering technique, which approximates ray tracing in our method. We use an image-warping equation and McMillan's warp ordering algorithm to find the intersections between rays and polygons and to find the order of intersections. Experiments for opaque and nonrefractive transparent objects are presented. Results indicate our approach generates soft shadows fast and effectively. Advantages and disadvantages of the proposed method are also discussed.     

Solid model edit distance: a multi-application and multi-level schema for CAD model retrieval

We present the solid model edit distance(SMED),a powerful and flexible paradigm for exploiting shape similarities amongst CAD models.It is designed to measure the magnitude of distortions between two CAD models in boundary representation(B-rep).We give the formal definition by analogy with graph edit distance,one of the most popular graph matching methods.To avoid the expensive computational cost potentially caused by exact computation,an approximate procedure based on the alignment of local structure sets is provided in addition.In order to verify the flexibility,we make intensive investigations on three typical applications in manufacturing industry,and describe how our method can be adapted to meet the various requirements.Furthermore,a multilevel method is proposed to make further improvements of the presented algorithm on both effectiveness and efficiency,in which the models are hierarchically segmented into the configurations of features.Experiment results show that SMED serves as a reasonable measurement of shape similarity for CAD models,and the proposed approach provides remarkable performance on a real-world CAD model database.     

一种误差可控的地图边界线的等距线计算方法

在边境地区无线电台站审查、协调需要较高精度地理数据的背景下,提出了一种基于距离场的地图边界线的等距线计算方法。该方法使用规则栅格点构建距离场,通过对误差来源的分析,得到了用栅格点间距表示的误差上界。实际计算时,只需设定一个允许的最大误差值,即可自动完成对指定边界线的计算,得到多边形表示的所需精度的等距线。实验表明基于距离场的方法是可行的并且具有可控的精度,计算的等距线已应用到边境台站的技术审查中。