A new interpolation algorithm for tracing planar equidistant curves

The aim of this paper is to propose an interpolation algorithm for tracing the equidistant (bisector) of two planar curves. The structure of the algorithm may be adapted accordingly so as to be used either for purely computing purposes or for presentation purposes. As a computing tool, the algorithm is suitable for computation of offset intersections and construction of Voronoi diagrams. In this case the step size is adjusted appropriately in order to reach the desired position in a small number of steps but with high accuracy. As a presentation tool, it may be embedded in a CAD system, entrusted with the task of drawing equidistants or even it may be used for plotting equidistants by driving the plotting tip. In this case, a fixed step size is selected to satisfy the specific precision requirements of the presentation. The development of the algorithm is achieved by treating equidistant generation as a locus-tracing problem. Using analytic concepts and the locus-defining geometric property, we formulate two sophisticated constructive operations. The repeated application of these operations generates a succession of points on the desired path (the locus) accurately and efficiently.     

A CNC interpolation algorithm for boundary machining

This paper presents an efficient and accurate algorithm for machining boundaries formed at the intersection of two surfaces, an important manufacturing problem in CNC machining. The algorithm is developed using a locus tracing technique implemented on the basis of Danielson's step selection rules. A vertical ball-end milling cutter moves along the considered boundary, in contact with the two surfaces. The algorithm guides the center of the spherical end of the cutter, to maintain exact contact (within 1 step) along the entire path. A seamless formulation is used, allowing the contact points to move freely from the ball-end to the cutter periphery and vice-versa. The surfaces forming the boundary may be implicitly or parametrically defined. The reliability of the algorithm is demonstrated for both cases, by treating a complex boundary machining example. The boundary considered is formed by the intersecting quadratic surfaces of a sphere and an elliptic hyperboloid.     

Pipelined data parallel algorithms-I: concept and modeling

The basic concept of pipelined data-parallel algorithms is introduced by contrasting the algorithms with other styles of computation and by a simple example (a pipeline image distance transformation algorithm). Pipelined data-parallel algorithms are a class of algorithms which use pipelined operations and data level partitioning to achieve parallelism. Applications which involve data parallelism and recurrence relations are good candidates for this kind of algorithm. The computations are ideal for distributed-memory multicomputers. By controlling the granularity through data partitioning and overlapping the operations through pipelining, it is possible to achieve a balanced computation on multicomputers. An analytic model is presented for modeling pipelined data-parallel computation on multicomputers. The model uses timed Petri nets to describe data pipelining operations. As a case study, the model is applied to a pipelined matrix multiplication algorithm. Predicted results match closely with the measured performance on a 64-node NCUBE hypercube multicomputer     

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.     

Computing exact aspect graphs of curved objects: Algebraic surfaces

This article presents an algorithm for computing the exact aspect graph of an opaque solid bounded by a smooth algebraic surface. Orthographic projection is assumed. The algorithm is based on a catalog of visual events available from singularity theory. It uses curve tracing, cell decomposition, homotopy continuation, and ray tracing to construct the regions of the view sphere delineated by visual-event curves. The algorithm has been fully implemented, and examples are presented.     

平面轮廓的螺旋填充轨迹生成算法

在快速成型和数控领域中对平面轮廓区域的填充是比较繁琐复杂的步骤。为充分扬弃顶点偏置和线段偏置的优缺点,提出了顶点线段混合偏置算法,即在凹点处采用线段偏置,而在凸点处则采用顶点偏置或插入线段方式;为优化起落刀次数,提出用对角曲线连接偏置曲线形成螺旋轨迹的算法,即在归类相同的相邻两条偏置曲线中,以顶点较多的作为主偏置曲线,利用K-D树在相邻多边形查找主偏置曲线每个顶点的最近点,依次求出对角曲线的离散点并且连接获得螺旋轨迹。     

Coverage path planning on three‐dimensional terrain for arable farming

Field operations should be done in a manner that minimizes time and travels over the field surface and is coordinated with topographic land features. Automated path planning can help to find the best coverage path so that the field operation costs can be minimized. Intelligent algorithms are desired for both two‐dimensional (2D) and three‐dimensional (3D) terrain field coverage path planning. The algorithm of generating an optimized full coverage pattern for a given 2D planar field by using boustrophedon paths has been investigated and reported before. However, a great proportion of farms have rolling terrains, which have a considerable influence on the design of coverage paths. Coverage path planning in 3D space has a great potential to further optimize field operations. This work addressed four critical tasks: terrain modeling and representation, coverage cost analysis, terrain decomposition, and the development of optimized path searching algorithm. The developed algorithms and methods have been successfully implemented and tested using 3D terrain maps of farm fields with various topographic features. Each field was decomposed into subregions based on its terrain features. A recommended “seed curve” based on a customized cost function was searched for each subregion, and parallel coverage paths were generated by offsetting the found “seed curve” toward its two sides until the whole region was completely covered. Compared with the 2D planning results, the experimental results of 3D coverage path planning showed its superiority in reducing both headland turning cost and soil erosion cost. On the tested fields, on average the 3D planning algorithm saved 10.3% on headland turning cost, 24.7% on soil erosion cost, 81.2% on skipped area cost, and 22.0% on the weighted sum of these costs, where their corresponding weights were 1, 1, and 0.5, respectively. © 2011 Wiley Periodicals, Inc.     

Pencil curve detection from visibility data

The trajectory of the ball-center point of a ball-end mill slid along a concave-edge region on a part surface becomes a pencil curve, and the ball-end milling along the pencil curve is called pencil curve machining. Presented in the paper is a procedure for computing pencil curves for 3-axis sculptured surface machining. The proposed algorithm traces pencil curves from an offset triangular mesh having numerous intersections (self-intersections). Since the outer skin of an offset triangular mesh makes the valid CL-surface, pencil curves can be obtained by connecting valid intersections lying on the outer skin of the offset mesh. The underlying concept of the proposed algorithm is that visible intersections are always valid for pencil curves. To obtain the visibility data of intersections, the proposed algorithm uses a graphics board, which performs hidden surface removal at a rate of up to a million polygons per second. Various examples have been tested with implementation of the algorithm, and some examples are presented for illustration.     

Contour offset approach to spiral toolpath generation with constant scallop height

Recently, the application of high-speed machining (HSM) is recognized as an economically viable manufacturing technology. Even though more HSM centers have increasingly been utilized, the conventional toolpath generation methods are usually employed in practice. But the conventional methods have inherent limitations for the HSM application.This paper presents a new toolpath generation algorithm for high-speed finish cutting process. In order to minimize the fluctuation of cutting load and the possibility of chipping on the cutting edge in HSM, a spiral topology toolpath that is to cut continuously with the minimum number of cutter retractions during the cutting operations is developed. This algorithm begins with the contour offset procedure along the boundary curve of the sculptured surface being machined. In the offset procedure, the offset distance is determined such that the scallop height maintains a constant roughness to ensure higher levels of efficiency and quality in high-speed finish machining. Then, the spiral path is generated as a kind of the diagonal curve between the offset curves. This path strategy is able to connect to a neighbor path without a cutter retraction. Therefore, the minimum tool retraction toolpath can be generated. And, it allows the sculptured surface incorporating both steeper and flatter areas to be high-speed machined. Based on these techniques, experimental results are given to verify the proposed approach.     

一个雕塑实体的布尔操作算法

给出了一个雕塑实体布尔操作的现实算法,在保证效率和精确性的同时确保鲁棒性是算法的目标,实体模型通过裁剪曲面片和半边数据结构来表达几何和拓扑信息。采用了层次求交和交线跟踪的方法来保证曲面片分割和区域分类的一致性,从而克服实践中常见的退化情况。该算法也可以方便地扩展到非流形模型的布尔操作。作为一个实体造型系统的一部分,该算法已经在ＳＧＩ工作站上实现。     

轮廓平移无跳刀连接刀路环树优化算法

提出一个无跳刀的轮廓平移刀路轨迹优化算法．根据刀路环之间父环和子环关系,提出“刀路环树”的概念,将加工刀路的一次环切定义为一个“刀路环向量”,并将刀路环的各个属性定义为刀路环向量的分量．根据无跳刀轨迹的要求,针对刀路环树的各个刀路环向量进行遍历,以获得了一个无跳刀的轮廓平移刀路轨迹算法,并通过与其他算法比较,证明该算法无跳刀、无重复切削,并且可以自动执行．     

基于遗传算法的曲面最短路径求解

对曲面上两点间最短路径的求解是一个应用非常广泛，但理论求解困难的问题。遗传算法是一种新型的、较成熟的全局随机搜索算法，具有优良的性态。该文将遗传算法引入到曲面最短路径寻优的问题中。首先在离散化的模拟数字高程上依据起点和终点，以实数编码产生一系列初始群体，定义相应的适应度函数，然后对群体进行复制、交叉和变异等操作，求解出一条曲面上两点间的最短路径。在文章的最后给出了一个数值仿真实例来了证明该算法的有效性和实用性。     

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.     

一种改进的射线跟踪路径搜索算法

基于几何光学原理的射线跟踪信道建模方法能够对场强、时延、到达角等多径信息进行精确预测,该方法多用多边形或三角构建三维场景模型。为了提高射线跟踪的路径搜索效率,提出一种改进的三角化射线跟踪路径搜索算法。在原带符号体积法中加入对实际不相交三角形的排除过程,简化判断过程,减小计算量。以三个不同类型的场景模型为例,对改进前后的算法进行仿真比较。结果表明,改进的路径搜索算法比原算法运算速度更快,且场景模型越复杂,效率提高越明显。     

螺旋曲面的等距曲面

考察了螺旋曲面生成两种等距曲面的方法：由螺旋面直接作等距曲面,由螺旋遄的端面型线生成等距曲线,再由等距曲线生成螺旋面,提出了截向等距曲面的概念,指出了与通常意义下的等距曲面之间的关系,并给出了它们之间的关系表达式。最后的实例表明,两种等距曲面的互不蕴含关系。两种方法在具有自主版权的三维造型系统Ｇｅｍｓ５．０中得到实现。     

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.     

基于控制点的二值图像边界矢量化算法

提出一种二值图像边界矢量化算法,实现从图像到图形的自动转换.先通过边界跟踪算法获取二值图像的边界,并利用SUSAN方法计算出边界上的角点,根据距离关系计算角点间的普通控制点,最后运用角点和这些普通控制点的3次B样条曲线拟合边界.实验结果表明算法有效实现了图像矢量化,解决了边界矢量化问题,具有较强的实用性.     

利用相关性的快速块拼贴纹理合成

通过总结已有的纹理合成算法,采用基于样图的纹理合成方式提出了一种快速块拼贴纹理合成算法。该算法基于纹理的相关性,在搜索最佳目标纹理块时,通过相关位置偏移技术在样图中映射出已合成块的地址,适时加入螺旋搜索方法,利用块边界匹配算法将搜索到的地址块进行匹配,直到找到符合误差阈值的纹理块然后进行输出合成。通过实验发现,算法在处理随机性纹理和结构性纹理时都能取得比原先算法更好的合成效果,合成时间也大大加快。     

Method for intersecting algebraic surfaces with rational polynomial patches

The paper presents a hybrid algorithm for the computation of the intersection of an algebraic surface and a rational polynomial parametric surface patch. This algorithm is based on analytic representation of the intersection as an algebraic curve expressed in the Bernstein basis; automatic computation of the significant points of the curve using numerical techniques, subdivision and convexity properties of the Bernstein basis; partitioning of the intersection domain at these points; and tracing of the resulting monotonic intersection segments using coarse subdivision and faceting methods coupled with Newton techniques. The algorithm described in the paper treats intersections of arbitrary order algebraic surfaces with rational biquadratic and bicubic patches and introduces efficiency enhancements in the partitioning and tracing parts of the solution process. The algorithm has been tested with up to degree four algebraics and bicubic patches.     

System for supply network management

Strategies and algorithms for operational planning and control are quite important to successful operations of a supply network. Implementation of a strategy requires substantial information system support, but few detailed designs of such systems have appeared in the literature. We designed an information system for a centralized management concept that could handle any type of strategy or algorithm. We developed algorithms for two different strategies deemed important by researchers and practitioners, push and pull, and implemented them in system modules. This information system performed well in simulations of the management of operations of an example six-stage supply network. This system provides an example for operational development as well as a platform for laboratory experiments.