Tool-path generation for sidewall machining

Presented in this paper is a tool-path generation procedure for sidewall machining, a process that is essential in the fabrication of many mechanical parts. While sculptured surface machining has received a significant amount of attention, there has been relatively less study of the technological requirements of sidewall machining. In this paper, three technological requirements are identified: (1) machining clean-up regions after rough machining, (2) avoiding unbalanced tool wear, and (3) retaining down-milling. For the generation of a roughing tool-path, the PWID offset algorithm is utilized. After roughing, it is necessary to identify the clean-up regions. Identifying these regions requires two major computations: a 2D-curve offsetting and a 2D-booleaning operation. To avoid these heavy operations, this paper proposes a method that identifies clean-up regions by making use of the byproducts (interfering ranges) of the PWID offset algorithm. As a result, it is possible to identify clean-up regions efficiently with minimum effort.     

Tool-path generation for Z-constant contour machining

For the Z-constant contour machining, a tool-path generation procedure is presented. The suggested procedure consists of two parts; (1) calculating the contours (tool-path-elements) by slicing the CL-surface with horizontal planes and (2) generating a tool-path by linking the contours. For the slicing algorithm, two algorithms are suggested, one is to slice a triangular mesh and the other is for a Z-map model. The second part, the linking problem, is approached from the technological requirements, such as considering the machining constraints among the tool-path-elements, minimizing the tool-path length and reflecting the oneway/zigzag linking options. To simplify the linking problem, we develop a data structure, called a TPE-net, providing information on the machining constraints among the tool-path-elements. By making use of the TPE-net, the tool-path linking problem becomes a touring problem so that every node has been traversed.     

测点数据生成刀具路径研究

为了提高反求加工的效率，提出由大规模测点数据直接生成粗、精加工刀具路径的算法．粗加工采用层切法分层切削材料，首先构造健壮的数据结构——层切网；然后计算无干涉刀位点，并把整个层切网划分为几个优化的子加工区域；最后应用优化的刀路链接法则得到粗加工刀具路径．精加工由大规模数据点构建三角曲面．为了避免干涉，需计算点、面和边的无干涉刀位点．实验结果表明，粗加工刀具路径算法具有较高的效率，只需要占用较小的内存空间；精加工可以成功地避免干涉并且获得可靠的表面精度．     

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.     

Contour-parallel offset machining without tool-retractions

Contour-parallel offset (CPO) machining uses successive offsets of the boundary curves of the machining region as the tool-path-elements (TPEs). For the efficiency of the CPO machining, it is very important to minimize the number of tool-retractions, which cause additional tool movements and do not contribute to the actual cutting. Presented in the paper is a CPO tool-path linking algorithm, which guarantees ‘zero’ number of tool-retractions. The algorithm employs the concept of a ‘TPE-net’ providing the information on the parent/child relationships among the TPEs. By planning a route through the TPE-net, a CPO tool-path without tool-retractions can be generated.     

Partitioning Trimmed Spline Surfaces into NonSelf-Occluding Regions for Visibility Computation

Computing the visible portions of curved surfaces from a given viewpoint is of great interest in many applications. It is closely related to the hidden surface removal problem in computer graphics, and machining applications in manufacturing. Most of the early work has focused on discrete methods based on polygonization or ray-tracing and hidden curve removal. In this paper we present an algorithm for decomposing a given surface into regions so that each region is either completely visible or hidden from a given viewpoint. Initially, it decomposes the domain of each surface based on silhouettes and boundary curves. To compute the exact visibility, we introduce a notion of visibility curves obtained by projection of silhouette and boundary curves and decomposition of the surface into nonoverlapping regions. These curves are computed using marching methods and we present techniques to compute all the components. The nonoverlapping and visible portions of the surface are represented as trimmed surfaces and we present a representation based on polygon trapezoidation algorithms. The algorithms presented use some recently developed algorithms from computational geometry like triangulation of simple polygons and point location. Given the nonoverlapping regions, we use an existing randomized algorithm for visibility computation. We also present results from a preliminary implementation of our algorithm.     

Five-axis tool path generation for a flat-end tool based on iso-conic partitioning

Traditionally, for the flat-end tool, due to the intertwined dependence relationship between its axis and reference point, most 5-axis tool-path generation algorithms take a decoupled two-stage strategy: first, the so-called cutter contact (CC) curves are placed on the part surface; then, for each CC curve, tool orientations are decided that will accommodate local and/or global constraints such as minimum local gouging and global collision avoidance. For the former stage, usually simplistic “offset” methods are adopted to determine the cutter contact curves, such as the iso-parametric or iso-plane method; whereas for the latter, a common practice is to assign fixed tilt and yaw angle to the tool axis regardless the local curvature information and, in the case of considering global interference, the tool orientation is decided solely based on avoiding global collision but ignoring important local machining efficiency issues. This independence between the placement of CC curves and the determination of tool orientations, as well as the rigid way in which the tilt and yaw angle get assigned, incurs many undesired problems, such as the abrupt change of tool orientations, the reduced efficiency in machining, the reduced finishing surface quality, the unnecessary dynamic loading on the machine, etc. In this paper, we present a 5-axis tool-path generation algorithm that aims at alleviating these problems and thus improving the machining efficiency and accuracy. In our algorithm, the CC curves are contour lines on the part surface that satisfy the iso-conic property — the surface normal vectors on each CC curve fall on a right small circle on the Gaussian sphere, and the tool orientations associated to a CC curve are determined by the principle of minimum tilt (also sometimes called lead) angle that seeks fastest cutting rate without local gouging. Together with an elaborate scheme for determining the step-over distance between adjacent CC curves that seeks maximum material removal, the presented algorithm offers some plausible advantages over most existing 5-axis tool-path generation algorithms, particularly in terms of reducing the angular velocity and acceleration of the rotary axes of the machine. The simulation experiments of the proposed algorithm and their comparison with a leading commercial CAM software toolbox are also provided that demonstrate the claimed advantages.     

On Multigrid Convergence of Local Algorithms for Intrinsic Volumes

Local digital algorithms based on n×?×n configuration counts are commonly used within science for estimating intrinsic volumes from binary images. This paper investigates multigrid convergence of such algorithms. It is shown that local algorithms for intrinsic volumes other than volume are not multigrid convergent on the class of convex polytopes. In fact, counter examples are plenty. On the other hand, for convex particles in 2D with a lower bound on the interior angles, a multigrid convergent local algorithm for the Euler characteristic is constructed. Also on the class of r-regular sets, counter examples to multigrid convergence are constructed for the surface area and the integrated mean curvature.     

Techniques for accelerating B-rep based parallel machining simulation

Continued progress in the area of solid modeller based machining process simulation is hindered by the complexity growth that occurs for a large number of tool-paths, n. For this reason, many researchers have adopted the Z-buffer approach. Boundary-representation (B-rep), however, remains the dominant choice for commercial computer aided design and manufacturing software. In this paper, it is shown that, under practical 2 1/2 D machining assumptions, the total number of tool-path neighbour pairs is O(n), and therefore the average ratio of simulated to subtracted tool-paths remains constant. Tool-path neighbours are grouped and simulated in parallel, greatly reducing wall clock running time. Running time is further reduced by filtering the intersection graph for edges and faces that are relevant to the cutter immersion. This information is subsequently used to discard irrelevant and time consuming intersection operations. Overall, a 90% decrease in wall clock running time was achieved.     

An epitrochoidal pocket—A new canned cycle for CNC milling machines

A machining strategy for milling a particular set of pockets with epitrochoidal boundary is proposed. The method is suitable to be integrated into the controller of a CNC milling machine and is particularly useful for machining chambers of rotary internal combustion engines (Wankel), rotary piston pumps and generally epitrochoidal-shaped housings. Motion generation is achieved by an algorithm which utilizes real-time CNC interpolation providing the highest possible accuracy, of which the milling machine is capable. The surface quality is controlled by applying roughing and finishing passes. The whole machining task can be programmed in a single block of the part program. Finally, the effectiveness of the proposed method is verified by simulation tests of the generated tool path.     

Tool-path generation of planar NURBS curves

It has been widely used in CAD field for many years and gradually applied in CAM area with the prevalence of NURBS interpolator equipped in CNC controllers. But few of them provide the tool radius compensation function. In order to achieve the goal of generating tool-path, an algorithm was presented to offset NURBS curves by an optimum process for CAD/CAM systems in this paper. NURBS format is ideal for HSM applications, but not all NURBS outputs are equal and standard. Basically, there are two different ways to generate NURBS tool-paths; one is to fit a NURBS curve to the conventional tool-path output, the other one is to generate a NURBS tool-path from the start. The main targets for the tool-path of this paper are: (1) To keep a constant distance d between progenitor curve C(t) and offset curve C_d(t) on the normal direction of C(t); (2) to alternate the order k of the basis function in offset curve C_d(t); (3) to oscillate the number of control points of offset curve C_d(t) and compare it with progenitor curve C(t). In order to meet the tolerance requirements as specified by the design, this study offsets the NURBS curves by a pre-described distance d. The principle procedure consists of the following steps: (1) construct an evaluating bound error function; (2) sample offset point-sequenced curves based on first derivatives; (3) give the order of NURBS curve and number of control points to compute all initial conditions and (4) optimize the control points by a path searching algorithm.     

Robust stabilizing regions of fractional-order PDμ controllers of time-delay fractional-order systems

This study investigates the robust stabilizing regions with stability degrees of fractional-order PD^μ controllers for time-delay fractional-order systems. By the D-decomposition technology, we identify the stabilizing regions by three types of curves, i.e., the real root boundary (RRB) curves, complex root boundary (CRB) curves and infinite root boundary (IRB) lines. The existence conditions and computing methods of RRB curves, CRB curves and IRB lines are proposed to determine the boundaries of the potential stabilizing regions. The Test Lines and the principle of the identifying the stabilizing regions are presented to find the real stabilizing regions with a given stability degree. To deal with noises existing in the feedback signals, fractional-order PD^μ controllers involving filers are adopted. Meanwhile, the robust stabilizing regions are also analyzed via IRB curves, CRB curves and IRB lines with stability degrees. Finally, some illustrative examples are offered to verify the effectiveness of depicting algorithms of the robust stabilizing regions for PD^μ controllers with no filer or filers, respectively.     

Material side tracing and curve refinement for pencil-cut machining of complex polyhedral models

In this paper, a new Material-Side-Tracing method and a pencil-cut curve refinement technique are proposed for 3-axis pencil-cut path generation. Pencil-cut machining has been used to remove remaining material at highly curved regions or corners after the finishing process. Procedures of evaluating and extracting valid pencil-cut points are developed by taking practical cases into account. With the strategy of using material-side information in the tracing process, smooth and clean pencil-cut curves can be generated even if the actual adjacent pencil-cut curves are very close. A technique of pencil-cut curve refinement is presented to overcome the limitation due to the discrete CL-net intervals, and the smooth pencil-cut paths are made complete at sharp corners. Computer implementation and practical examples are also presented in this paper. The proposed techniques can be used in the CAD/CAM systems to generate pencil-cut paths for machining complex polyhedral models.     

Filling n-sided regions with G 1 triangular Coons B-spline patches

Filling n-sided regions is an essential operation in shape and surface modeling. Positional and tangential continuities are highly required in designing and manufacturing. We propose a method for filling n-sided regions with untrimmed triangular Coons B-spline patches, preserving G ¹ continuity exactly. The algorithm first computes a central point, a central normal, the central, and the corner derivative vectors. Then the region is split into n triangular areas by connecting the central point to each corner of the boundary. These inner curves and all cross-boundary derivatives are computed fulfilling G ¹ compatibility conditions. And finally, the triangular patches are generated in the Coons B-spline form, one boundary of which is regressed to the central vertex. Neither positional nor tangential error is introduced by this method. And only one degree elevation is needed.     

Generative regular-freeform surface recognition for generating material removal volume from stock model

The present paper illustrates the development of generative surface recognition for regular and freeform. To obtain the final form of product, material removal volume generation from a stock model is also discussed. Only a few studies integrated the regular and freeform surfaces to provide a comprehensive definition of surface recognition as well as for the volumetric estimation of removal material in finishing and roughing operations. The current research deploys a comprehensive surface recognition approach that can recognise both regular and freeform surfaces based on the geometry as well as loop entity of a face. In contrast to the regular surface that can be categorised into a particular group of geometrical shape, such as cylindrical shape, the proposed approach enables the recognition of a freeform surface that cannot be defined as a generic geometrical shape. In addition, the new method also simplifies the existing surface recognition for regular surfaces. The material removal volumes created consist of machining volumes for finishing and roughing operations needed to be machined to obtain the final form of the product. The present research provides a unique user customisation feature that enables user to specify the volumetric thickness for material removal volume in the finishing operation as well as the size for the stock model. These estimated volumes are prepared for subsequent manufacturing applications, such as sequencing of machining operation.     

Free-form shapes: An integrated CAD/CAM system

After describing the primary aims and the structure of the implemented CAD/CAM system, the interactive design process is presented. Particular attention is paid to those components which are of primary importance due to their direct contact with the user. A CNC option for real-time tool-path generation and some details of roughing and finishing are also presented.     

Offset tool-path linking for pocket machining

For die-cavity pocketing, contour-parallel offset (CPO) machining is the most popular machining strategy. CPO tool-path generation for pocketing includes geometrical and technological issues: (1) a 2D-curve offsetting algorithm; and (2) optimizing technological objectives, such as tool-path linking. The 2D-curve offsetting solution has been widely studied, because it has so many potential applications. However, though the tool-path linking may seriously affect the machining performance, there have been few reported investigations on optimizing the CPO tool-path linking. This paper presents a CPO tool-path linking procedure optimizing technological objectives, such as dealing with islands (positive and negative) and minimizing tool retractions, drilling holes and slotting. Main features of the proposed algorithm are as follows: (1) a data structure, called a ‘TPE-net’, is devised to provide information on the parent/child relationships among the tool-path-elements; (2) the number of tool retractions is minimized by a ‘tool-path-element linking algorithm’ finding a tour through the TPE-net; and (3) the number of drilling holes is minimized by making use of the concept of the ‘free space’ (negative islands or already machined region).     

A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space

We present here a new and efficient algorithm for planning collision-free motion of a line segment (a rod or a “ladder”) in two-dimensional space amidst polygonal obstacles. The algorithm uses a different approach than those used in previous motion-planning techniques, namely, it calculates the boundary of the (three-dimensional) space of free positions of the ladder, and then uses this boundary for determining the existence of required motions, and plans such motions whenever possible. The algorithm runs in timeO(K logn) =O(n ² logn) wheren is the number of obstacle corners and whereK is the total number of pairs of obstacle walls or corners of distance less than or equal to the length of the ladder. The algorithm has thus the same complexity as the best previously known algorithm of Leven and Sharir [5], but if the obstacles are not too cluttered together it will run much more efficiently. The algorithm also serves as an initial demonstration of the viability of the technique it uses, which we expect to be useful in obtaining efficient motion-planning algorithms for other more complex robot systems.     

基于自适应边界向量提取的多尺度v-支持向量机建模

针对v-支持向量机(v-SVM)用于大规模、多峰样本建模时易出现训练速度慢和回归精度低的问题,提出基于边界向量提取的多尺度v-SVM建模方法.该方法采用一种自适应边界向量提取算法,从训练样本中预提取出包含全部支持向量的边界向量集,以缩减训练样本规模,并通过求解多尺度v-SVM二次规划问题获取全局最优回归模型,从多个尺度上对复杂分布样本进行逼近.仿真结果表明,基于边界向量提取的多尺度v-SVM比v-SVM具有更好的回归结果.     

A Distributed Mincut/Maxflow Algorithm Combining Path Augmentation and Push-Relabel

We propose a novel distributed algorithm for the minimum cut problem. Motivated by applications like volumetric segmentation in computer vision, we aim at solving large sparse problems. When the problem does not fully fit in the memory, we need to either process it by parts, looking at one part at a time, or distribute across several computers. Many mincut/maxflow algorithms are designed for the shared memory architecture and do not scale to this setting. We consider algorithms that work on disjoint regions of the problem and exchange messages between the regions. We show that the region push-relabel algorithm of Delong and Boykov (A scalable graph-cut algorithm for N-D grids, in CVPR, 2008) uses Θ(n ²) rounds of message exchange, where n is the number of vertices. Our new algorithm performs path augmentations inside the regions and push-relabel style updates between the regions. It uses asymptotically less message exchanges, $O(\mathcal{B}^{2})$ , where $\mathcal{B}$ is the set of boundary vertices. The sequential and parallel versions of our algorithm are competitive with the state-of-the-art in the shared memory model. By achieving a lower amount of message exchanges (even asymptotically lower in our synthetic experiments), they suit better for solving large problems using a disk storage or a distributed system.