曲面变形的水平集方法

文中作者提出一种曲面变形的新方法.首先引入一个一阶能量范函,然后通过对其极小化诱导出一个水平集形式的二阶几何偏微分方程,从而将曲面变形过程转化为一个三维体上的隐式模型的演化过程.模型演化所产生的系列变形曲面被描述成一个密集取样的三维体上水平集函数的演化.实验结果显示大尺度的形变以及拓扑结构的自动改变均能理想地实现.作者采用C2光滑的B样条作为水平集函数,从而获得了高质量的曲面.伺时,作者的方法还具有其它一些优点,比如简单的用户输入、灵活的数学模型以及稳健的数值算法.     

Feature conversion based on decomposition and combination of swept volumes

In this paper, an approach is proposed for converting design features into machining features based on decomposition and combination of swept volumes. In the approach, delta volumes between a negative swept volume and a positive swept volume, which are directly generated from original design features, are decomposed into a set of smaller negative swept volumes first. Then, the negative swept volumes are combined to form maximal swept features, each of which represents a set of machining features with the same cutting-paths. Since sweeping is a common characteristic of different type features, the maximal swept features can serve as an intermediate representation for the different types of feature-based models; in particular, they can be conveniently converted into milling features or turning features, common features or user-specific features, and their alternatives.     

Precise algebraic-based swept volumes for arbitrary free-form shaped tools towards multi-axis CNC machining verification

This paper presents an algebraic based approach and a computational framework for the simulation of multi-axis CNC machining of general freeform tools. The boundary of the swept volume of the tool is precisely modeled by a system of algebraic constraints, using B-spline basis functions. Subdivision-based solvers are then employed to solve these equations, resulting in a topologically guaranteed construction of the swept volume. The presented algebraic-based method readily generalizes to accept tools of arbitrary free-form shape as input, and at the same time, delivers high degree of precision.Being a common representation in CNC simulations, the computed swept volume can be reduced to a dexels’ representation. Several multi-axis test cases are exhibited using an implementation of our algorithm, demonstrating the robustness and efficacy of our approach.     

Image-Swept Volumes

Many graphical objects can be represented by swept volumes (including its subset — generalised cylinders) by sweeping 2D or 3D templates along 3D trajectories. In this paper, we present a new approach for constructing swept volumes using image templates. We utilise scalar fields as our underlying data type, and employ volume ray casting techniques for rendering swept volumes in their original sweeping specifications as well as in their voxelised approximations. In addition to some simple image‐swept volumes, we also treat multi‐channel image templates, video templates, generalised sweeps, and self‐intersecting trajectories. This approach enables us to model swept volumes with heterogeneous interiors and amorphous effects. It also facilitates the use of constructive volume geometry for creating complex scenes in both modelling and rendering space.     

Boundary of the volume swept by a free-form solid in screw motion

The swept volume of a moving solid is a powerful computational and visualization concept. It provides an excellent aid for path and accessibility planning in robotics and for simulating various manufacturing operations. It has proven difficult to evaluate the boundary of the volume swept by a solid bounded by trimmed parametric surfaces undergoing an arbitrary analytic motion. Hence, prior solutions use one or several of the following simplifications: (1) approximate the volume by the union of a finite set of solid instances sampled along the motion; (2) approximate the curved solid by a polyhedron; and (3) approximate the motion by a sequence of simpler motions. The approach proposed here is based on the third type of simplification: it uses a polyscrew (continuous, piecewise-helical) approximation of the motion. This approach leads to a simple algorithm that generates candidate faces, computes the two-cells of their arrangement, and uses a new point-in-sweep test to select the correct cells whose union forms the boundary of the swept volume.     

Geometric Modeling for Swept Volume of Moving Solids

The modeling of swept volume is important in simulating the interference between a moving solid and its environment. This article presents a novel method for modeling swept voume by computing a family of critical curves from a moving solid. Based on this approach, a system has been developed for real-time verification of NC tool paths using computer graphics.     

Sweeping of an object held by a robotic end-effector

A broadly applicable formulation for calculating the swept volume generated by an object held by a manipulator's end-effector is presented. While the problem of determining the workspace of a robot arm has been extensively addressed in the literature, this rarely addressed problem is of significance to path planning, collision detection, plant layout, and robot design. The totality of points touched by a geometric entity moved in space using a number of joints is defined as the swept volume. The formulation and accompanying experimental code are presented and are aimed at providing the reader with a replicable computer algorithm. Calculating the swept volume is based on The Implicit Function theorem and is shown to be any number of degrees of freedom yielding the exact representation of the swept volume. By considering the sweep equation as a vector function defined on a manifold (possibly with boundaries), it is shown that stratification of the various sub-manifolds yields varieties that can be depicted in R³. A measure of the computational complexity is presented to give the reader a sense of the robustness of this method as well as its difficulties. An experimental computer code is developed using a symbolic manipulator that performs the automated calculations necessary to calculate the varieties and to visualize the manifold.     

Radial Supershapes for Solid Modeling

In the previous work, an efficient method has been proposed to represent solid objects as multiple combinations of globally deformed supershapes. In this paper, this framework is applied with a new supershape implicit function that is based on the notion of radial distance and results are presented on realistic models composed of hundreds of hierarchically globally deformed supershapes. An implicit equation with guaranteed differential properties is obtained by simple combinations of the primitives' implicit representations using R-function theory. The surface corresponding to the zero-set of the implicit equation is efficiently and directly polygonized using the primitives' parametric forms. Moreover, hierarchical global deformations are considered to increase the range of shapes that can be modeled. The potential of the approach is illustrated by representing complex models composed of several hundreds of primitives inspired from CAD models of mechanical parts.     

Global optimization of tool path for five-axis flank milling with a conical cutter

In this paper, optimum positioning of the conical cutter for five-axis flank milling of slender surfaces is addressed from the perspective of approximating the tool envelope surface to the data points on the design surface following the minimum zone criterion recommended by ANSI and ISO standards for tolerance evaluation. Based on the observation that a conical surface can be treated as a canal surface, i.e. envelope surface of one-parameter family of spheres, the swept envelope of a conical cutter is represented as a sphere-swept surface. Then, an approach is presented to efficiently compute the signed distance between a point in space and the swept surface without constructing the swept surface itself. The first order differential increment of the signed point-to-surface distance with respect to the differential deformation of the tool axis trajectory surface is derived. By using the distance function, tool path optimizations for semi-finish and finish millings are formulated as two constrained optimization problems in a unified framework, and a sequential approximation algorithm along with a hierarchical algorithmic structure is developed for the optimization. Numerical examples are given to confirm the validity and efficiency of the proposed approach. Comparing with the existing approaches, the present one improves the machining accuracy greatly. The rationale developed applies to general rotary cutters.     

The stencil buffer sweep plane algorithm for 5-axis CNC tool path verification

A new algorithm based on the sweep plane approach to determine the machined part geometry in 5-axis machining with general APT tools is presented. Undercut and overcut can be determined. Collision detection between the toolholder, workpiece and workpiece fixture can also be detected. The subtraction of the removed material is obtained for each sweep plane by using a stencil buffer. A flat plane is swept through the blank part, fixture and tool swept volume geometry. The intersections of sweep planes and the swept tool volume are computed based on the canonical representation of a cone, torus and sphere. The necessary data to compute all the intersections is stored in a text file, here called the M-Plane file (Memory Plane). The equations of the intersections are approximated by a polygon with variable accuracy. The resulting APT tool intersection in each sweep plane is then clipped against the blank workpiece intersection with the current sweep plane. The stencil buffer provides automatically the union of all tool intersections and the subtraction from the blank workpiece. This algorithm provides a 3D geometric model of the tool swept volume. The display algorithm is based on the Painter's algorithm, but there is no time consuming sorting from back to front required, as the sweep proceeds from back to front. The accuracy of the algorithm can be varied as a function of the requirements by changing the polygon approximation and the distance between the sweep planes.     

设计特征模型到分析特征模型的自动转换方法

针对有限元分析建模的需求,提出一种将工程零件的设计特征模型自动转换为相应的分析特征模型的方法.首先将设计特征模型分解为所有正特征剩余体的集合,然后从各正特征剩余体中分解出一组扫成体和非扫成体,再采用基于二维轮廓的方法从各扫成体中确定出候选分析特征区域,最后通过合成候选分析特征区域得到真正的分析特征区域,并在此基础上生成分析特征和分析特征模型.实验结果表明该方法是有效的.     

High accuracy NC milling simulation using composite adaptively sampled distance fields

We describe a new approach to shape representation called a composite adaptively sampled distance field (composite ADF) and describe its application to NC milling simulation. In a composite ADF each shape is represented by an analytic or procedural signed Euclidean distance field and the milled workpiece is given as the Boolean difference between distance fields representing the original workpiece volume and distance fields representing the volumes of the milling tool swept along the prescribed milling path. The computation of distance field of the swept volume of a milling tool is handled by an inverted trajectory approach where the problem is solved in tool coordinate frame instead of a world coordinate frame. An octree bounding volume hierarchy is used to sample the distance functions and provides spatial localization of geometric operations thereby dramatically increasing the speed of the system. The new method enables very fast simulation, especially of free-form surfaces, with accuracy better than 1 micron, and low memory requirements. We describe an implementation of 3 and 5-axis milling simulation.     

Dynamic Catmull-Clark subdivision surfaces

Recursive subdivision schemes have been extensively used in computer graphics, computer-aided geometric design, and scientific visualization for modeling smooth surfaces of arbitrary topology. Recursive subdivision generates a visually pleasing smooth surface in the limit from an initial user-specified polygonal mesh through the repeated application of a fixed set of subdivision rules. We present a new dynamic surface model based on the Catmull-Clark subdivision scheme, a popular technique for modeling complicated objects of arbitrary genus. Our new dynamic surface model inherits the attractive properties of the Catmull-Clark subdivision scheme, as well as those of the physics-based models. This new model provides a direct and intuitive means of manipulating geometric shapes, and an efficient hierarchical approach for recovering complex shapes from large range and volume data sets using very few degrees of freedom (control vertices). We provide an analytic formulation and introduce the “physical” quantities required to develop the dynamic subdivision surface model which can be interactively deformed by applying synthesized forces. The governing dynamic differential equation is derived using Lagrangian mechanics and the finite element method. Our experiments demonstrate that this new dynamic model has a promising future in computer graphics, geometric shape design, and scientific visualization     

Ray casting free‐form deformed‐volume objects

A collection of techniques is developed in this paper for ray casting free‐form deformed‐volume objects with high quality and efficiency. The known inverse ray deformation approach is combined with free‐form deformation to bend the rays to the opposite direction of the deformation, producing an image of the deformed volume without generating a really deformed intermediate volume. The local curvature is estimated and used for the adaptive selection of the length of polyline segments, which approximate the inversely deformed ray trajectories; thus longer polyline segments can be automatically selected in regions with small curvature, reducing deformation calculation without losing the spatial continuity of the simulated deformation. We developed an efficient method for the estimation of the local deformation function. The Jacobian of the local deformation function is used for adjustments of the opacity values and normal vectors computed from the original volume, guaranteeing that the deformed spatial structures are correctly rendered. The popular ray casting acceleration techniques, like early ray termination and space leaping, are incorporated into the deformation procedure, providing a speed‐up factor of 2.34–6.56 compared to the non‐optimized case. Copyright © 2003 John Wiley & Sons, Ltd.     

Computing swept volumes

The swept volume problem is practical, difficult and interesting enough to have received a great deal of attention over the years, and the literature contains much discussion of methods for computing swept volumes in many situations. The method presented here permits an arbitrary polyhedral object (given in a typical boundary representation) to be swept through an arbitrary trajectory. A polyhedral approximation to the volume swept by this moving object is computed and output in a typical boundary representation. A number of examples are presented demonstrating the practicality of this method. Copyright © 2000 John Wiley & Sons, Ltd.     

复杂曲面加工精度检验中曲面法矢与刀具扫描体求交算法的研究

提出了一种用于实现矢量与扫描体（代表五轴数控加工铣刀的运动）求交的有效算法,该算法首先对曲面法矢和刀具扫描体进行预处理,将曲面法矢与刀具扫描体之间的求交问题转化为有向线段与三角网格之间的求交计算,然后建立有向线段和三角网格的求交子集,减少了不必要的求交计算,提高了乍法的效率。文中举例说明了该算法在复杂曲面NC精度检验中的应用。     

Boolean operations with implicit and parametric representation of primitives using R-functions

We present a new and efficient algorithm to accurately polygonize an implicit surface generated by multiple Boolean operations with globally deformed primitives. Our algorithm is special in the sense that it can be applied to objects with both an implicit and a parametric representation, such as superquadrics, supershapes, and Dupin cyclides. The input is a constructive solid geometry tree (CSG tree) that contains the Boolean operations, the parameters of the primitives, and the global deformations. At each node of the CSG tree, the implicit formulations of the subtrees are used to quickly determine the parts to be transmitted to the parent node, while the primitives' parametric definition are used to refine an intermediary mesh around the intersection curves. The output is both an implicit equation and a mesh representing its solution. For the resulting object, an implicit equation with guaranteed differential properties is obtained by simple combinations of the primitives' implicit equations using R-functions. Depending on the chosen R-function, this equation is continuous and can be differentiable everywhere. The primitives' parametric representations are used to directly polygonize the resulting surface by generating vertices that belong exactly to the zero-set of the resulting implicit equation. The proposed approach has many potential applications, ranging from mechanical engineering to shape recognition and data compression. Examples of complex objects are presented and commented on to show the potential of our approach for shape modeling.     

Complete swept volume generation, Part I: Swept volume of a piecewise C-continuous cutter at five-axis milling via Gauss map

In this paper, we present a methodology to generate swept volume of prevailing cutting tools undergoing multi-axis motion and it is proved to be robust and amenable for practical purposes with the help of a series of tests. The exact and complete SV, which is closed from the tool bottom to the top of the shaft, is generated by stitching up envelope profiles calculated by Gauss map.The novel approach finds the swept volume boundary for five-axis milling by extending the basic idea behind Gauss map. It takes piecewise C¹-continuous tool shape into account. At first, the tool shape is transformed from Euclidean space into Tool map (T-Map) on the unit sphere and the velocity vector of a cutter is transformed into Contact map (C-Map) using Gauss map. Then, closed intersection curve is found between T-Map and C-Map on the Gaussian sphere. At last, the inverse Gauss map is exploited to get envelope profile in Euclidean space from the closed curve in the range. To demonstrate its validity, a cutting simulation kernel for five-axis machining has been implemented and applied to mold and die machining.     

Applying the swept rule for solving explicit partial differential equations on heterogeneous computing systems

Applications that exploit the architectural details of high-performance computing (HPC) systems have become increasingly invaluable in academia and industry over the past two decades. The most important hardware development of the last decade in HPC has been the general purpose graphics processing unit (GPGPU), a class of massively parallel devices that now contributes the majority of computational power in the top 500 supercomputers. As these systems grow, small costs such as latency—due to the fixed cost of memory accesses and communication—accumulate in a large simulation and become a significant barrier to performance. The swept time-space decomposition rule is a communication-avoiding technique for time-stepping stencil update formulas that attempts to reduce latency costs. This work extends the swept rule by targeting heterogeneous, CPU/GPU architectures representing current and future HPC systems. We compare our approach to a naive decomposition scheme with two test equations using an MPI+CUDA pattern on 40 processes over two nodes containing one GPU. The swept rule produces a factor of 1.9 to 23 speedup for the heat equation and a factor of 1.1 to 2.0 speedup for the Euler equations, using the same processors and work distribution, and with the best possible configurations. These results show the potential effectiveness of the swept rule for different equations and numerical schemes on massively parallel compute systems that incur substantial latency costs.

     

Complete swept volume generation — Part II: NC simulation of self-penetration via comprehensive analysis of envelope profiles

In this paper the swept volume with self-penetration (or self-intersection) of the cutter is presented. The complete swept volume (SV), which describes the side and bottom shape of a milling cutter undergoing self-penetration, is generated by using the Gauss map method proposed in the authors’ previous paper [Lee SW, Nestler A. Complete swept volume generation—part I: swept volume of a piecewise C¹-continuous cutter at five-axis milling via Gauss map. Computer-Aided Design 2011; 43(4): 427–41]. Based on the Gauss map method, the comprehensive analysis of envelope profiles of the tool is accomplished. Through the analysis the necessary condition of the self-penetration of the cutter at five-axis movement is identified. After having classified movement types of the milling cutter in an in-depth manner, the topologically consistent boundary of SV is generated by trimming the invalid facets interior to the SV. To demonstrate the validity of the proposed method, a cutting simulation kernel for five-axis machining has been implemented and applied to cavity machining examples such as intake ports of automobile engines and so forth where the self-penetration occurs. The proposed method is proved to be robust and amenable for the practical purpose of the NC simulation.