Trimming local and global self-intersections in offset curves/surfaces using distance maps

A robust and efficient algorithm for trimming both local and global self-intersections in offset curves and surfaces is presented. Our scheme is based on the derivation of a rational distance map between the original curve or surface and its offset. By solving a bivariate polynomial equation for an offset curve or a system of three polynomial equations for an offset surface, all local and global self-intersection regions in offset curves or surfaces can be detected. The zero-set of polynomial equation(s) corresponds to the self-intersection regions. These regions are trimmed by projecting the zero-set into an appropriate parameter space. The projection operation simplifies the analysis of the zero-set, which makes the proposed algorithm numerically stable and efficient. Furthermore, in a post-processing step, a numerical marching method is employed, which provides a highly precise scheme for self-intersection elimination in both offset curves and surfaces. The effectiveness of our approach is demonstrated using several experimental results.     

On the effective tool path planning algorithms for sculptured surface manufacture

This paper describes the cutter path planning and cutter interference (gouging) analysis algorithms developed to generate optimal tool path for manufacturing sculptured surfaces on three axes CNC machine tools. Cutter path planning algorithm approximates the parametric curves on three dimensional surfaces by a sequence of straight line segments and generates optimal tool paths by minimizing the number of interpolation points while keeping the path deviations within the specified tolerances. Cutter interference analysis algorithm checks for the self intersection of an offset surface and determines the self-intersection curve. The tool path is then planned over the cutter contact (CC) surface after removing the CC data that lies inside the self-intersection curve. Finally, the effectiveness of these algorithms is demonstrated by implementing them in CAD/CAM system.     

一种参数多项式曲面片的逐点生成算法

在计算机绘图中，一般来说，曲线实际上是由折线代替，而曲面实为小平面拼接而成，在使计算量降到最低的情况下画出真正的曲线方面，已有许多文章研究了曲线的逐点生成方法，并取得了一定的进展，但是尚无有效的快速逐点生成曲面的方法，为了快速逐点生成曲面，在建立多项式函数递推计算公式和算法的基础上，给出了一种逐点生成参数多项式曲面片的算法，由于此算法中只用到整数加法运算，且点数的适当选取可使计算量达到极小，因此是一种很有效的算法，该方法还可以加以改进，而用于有理函数，这无疑对有理曲线曲面（如NURBS曲线曲面）的快速生成以及对计算机图形学的其他一些领域都是有意义的。     

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.     

Implicit simplicial models for adaptive curve reconstruction

Parametric deformable models have been extensively and very successfully used for reconstructing free-form curves and surfaces, and for tracking nonrigid deformations, but they require previous knowledge of the topological type of the data, and good initial curve or surface estimates. With deformable models, it is also computationally expensive to check for and to prevent self-intersections while tracking deformations. The implicit simplicial models that we introduce in this paper are implicit curves and surfaces defined by piecewise linear functions. This representation allows for local deformations, control of the topological type, and prevention of self-intersections during deformations. As a first application, we also describe an algorithm for 2D curve reconstruction from unorganized sets of data points. The topology, the number of connected components, and the geometry of the data are all estimated using an adaptive space subdivision approach. The main four components of the algorithm are topology estimation, curve fitting, adaptive space subdivision, and mesh relaxation     

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.     

基于分段Bezier曲线的手绘雕刻图案矢量化

针对手绘复杂雕刻图案的特点,利用分段三次Bezier曲线实现手绘复杂雕刻图案的矢量化。提出一种自适应区分线条图案和区域块图案及提取区域块图案边界的解决方案。依据检测的角点信息将得到的轮廓边界分解成若干条独立的线段。曲线拟合时,为提高拟合精度,根据线段数据点到曲线的偏移量对线段进一步细分,提出一种实现分段曲线光滑连接的新方法。实验结果表明,该方法对手绘复杂雕刻图案的矢量化具有算法复杂度低、矢量化效果较好的优势,有广泛的实用性。     

Self-intersection detection and elimination in freeform curves and surfaces

We present several algorithms for self-intersection detection, and possible elimination, in freeform planar curves and surfaces. Both local and global self-intersections are eliminated using a binormal-line criterion and a simple direct algebraic elimination procedure that enables the direct solution of the algebraic (self-)intersection constraints.All algorithms have been fully implemented and tested. Examples are presented for applications in self-intersection detection, self-intersection-free metamorphosis of curves, and proper trimming of self-intersections in offset curves.     

平面NURBS曲线的等距线算法：圆弧法矢近似法

本文根据产生曲线的特征点与它的等距线的特征点的对应关系,给出了一种平面NURBS曲线的等距线表示方法——圆弧法矢近似法。这种方法的特点是:(1)等距线与产生曲线具有统一的NURBS表示;(2)计算简单、几何意义明确、近似精度高。     

B样条曲线的等距算法及应用

等距曲线的拓扑结构是等距算法中的核心因素之一。该文以B样条曲线为例,给出了一种基于关键点的等距算法。它应用了自适应离散等手段并给出了关键点的求解方法,同时利用关键点确定等距线各个分段的取舍,从而有效地去除自交的情况,使得计算出的等距曲线有着正确的拓扑结构。该文的算法已应用于商业软件OpenCAD中。     

非均匀有理B样条曲线优化匹配组合

目的 为了解决从曲线库(轮廓线集合)中筛选出与期望曲线相匹配的相似曲线段问题,研究基于Kabsch算法的NURBS(非均匀有理B样条)曲线优化匹配组合方法。方法 首先提出一种基于Kabsch算法的曲线相似性判断方法,针对两条NURBS曲线上相同个数点阵,经最优旋转和平移变换得到其最小均方根偏差,进而依据基于最小均方根偏差和相似度指标判断曲线相似性;在此基础上,提出一种类似二分查找法的曲线优化匹配组合方法,对于给定相似度和最小搜索步长,通过曲线分割和相似性判断得到期望曲线分割段数最少的相似组合曲线。结果 给定一条期望的3D曲线,在相似度为0.025和最小搜索步长为0.05情况下,采用所提方法从包含4条3D曲线的曲线库中依次筛选出10段基元构建相似组合曲线。结论 提出了一种新的NURBS曲线优化匹配组合方法,实验结果表明,对不同期望曲线能高效稳定构建相对应的相似组合曲线,适用于类似碎片拼接重构问题。     

An offset algorithm for polyline curves

Polyline curves which are composed of line segments and arcs are widely used in engineering applications. In this paper, a novel offset algorithm for polyline curves is proposed. The offset algorithm comprises three steps. Firstly, the offsets of all the segments of polyline curves are calculated. Then all the offsets are trimmed or joined to build polyline curves that are called untrimmed offset curves. Finally, a clipping algorithm is applied to the untrimmed offset curves to yield the final results. The offset algorithm can deal with polyline curves that are self-intersection, overlapping or containing small arcs. The new algorithm has been implemented in a commercial system TiOpenCAD 8.0 and its reliability is verified by a great number of examples.     

曲面交线的B样条优化逼近

目前，在比较成熟的商业几何核心系统中，曲面的交线是一种基于位置算子的“精确”表示或称为“过程”表示．这样的交线如果用在几何建模操作中，必须输出为系统支持的曲线表示(如B样条表示)．现有的几何核心系统中曲面交线的B样条逼近算法存在控制点数目过多和连续性偏低(C^1)的缺点，导致下游操作结果太复杂且连续性低．基于此，提出了一种曲面交线的B样条逼近算法，使控制点数目减少为原来的三分之一，而连续阶上升为C^2．该算法已经在SolidWorks系统中得到应用，效果良好．     

平面NURBS曲线的导矢及其等距线

本文首先给出了计算NURBS曲线导矢的递推公式,在此基础上,给出了生成平面NURBS曲线等距线的算法。     

平面曲线的offset逼近

文章给出了一种用三次Bezier曲线逼近平面曲线精确offset的方法。利用逼近曲线与精确offset曲线的对应点,法向尽可能相同这一性质构造具有较好的连续性的目标函数。此外,给出新的误差函数,该函数比常用的误差函数更能反映两曲线在一点处的真实距离。     

曲线描述的一种方法:夹角链码

提出了一种有效的曲线编码和描述方法--夹角链码.夹角链码的思想框架是:首先将曲线用一串有方向的等长度的线段来表述,根据相邻线段之间的夹角差形成一串角度序列,即夹角链码来描述这条曲线.描述曲线的直线段的数目由面积法则来决定,并且待处理的曲线将被分割成相等数目的线段.该方法最大的一个优点是曲线的描述具有平移、拉伸和旋转的不变性.该方法的一个实际应用在于,将某一个地区的合成孔径雷达(synthetic aperture Radar,简称SAR)图像与地图相匹配.     

Medial axis of a planar region by offset self-intersections

The medial axis (MA) of a planar region is the locus of those maximal disks contained within its boundary. This entity has many CAD/CAM applications. Approximations based on the Voronoi diagram are efficient for linear-arc boundaries, but such constructions are more difficult if the boundary is free. This paper proposes an algorithm for free-form boundaries that uses the relation between MA and offsets. It takes the curvature information from the boundary in order to find the self-intersections of successive offset curves. These self-intersection points belong to the MA and can be interpolated to obtain an approximation in Bézier form. This method also approximates the medial axis transform by using the offset distance to each self-intersection.     

Hardware support for adaptive tessellation of Bézier surfaces based on local tests

Bézier representations have been widely employed as a standard way of designing complex scenes with very good quality results. These surfaces are usually tessellated, in the software application, into triangle models to be rendered. Then, the final image is generated in the graphics card so that its triangle rendering capabilities are exploited.In this work we present an adaptive tessellation algorithm and the corresponding architecture to be implemented in hardware. The objective of the proposal is to avoid the potential bottleneck associated with the transmission of complex triangular models from CPU to graphics cards. The algorithm we propose is based on a layer strip representation method and a new data management that permits generation and efficient storage of the tessellated mesh. The corresponding architecture has to be included as an additional unit at the input of the graphics card. As a consequence, the transmission requirements from CPU to graphics card are greatly reduced as the tessellation is performed in the graphics card. On the other hand, the adaptive strategy employed permits selection of the number of triangles of the final mesh as a trade off between computational requirements and quality of the final mesh. The efficient data management proposed, together with the low storage requirements of the architecture, makes it a good candidate for its hardware implementation and inclusion in future graphics cards.     

插值给定数据点的四次PH曲线构造

目的 PH （Pythagorean hodograph）曲线由于具备有理等距曲线、弧长可精确计算等优良的几何性质,广泛应用于数控加工和路径规划等方面。曲线插值是曲线构造的主要手段之一,虽然对PH曲线的Hermite插值方法进行了广泛研究,但插值给定数据点的构造方法仍有待突破,为推广四次PH曲线的应用范围,提出了一种新的四次PH曲线的3点插值问题解决方法。方法 从四次PH曲线的代数充分必要条件出发,在该曲线的Bézier控制多边形中引入辅助控制顶点,指出其中实参数的几何意义,该实参数可作为形状调节因子对构造曲线进行交互。对给定的3个平面型值点进行参数化确定相应的参数值;通过对四次PH曲线一阶导数积分得到曲线的显式表达,其中包含一个待定复常量,将给定的约束点代入曲线的显式表达式得到关于待定复常量的一元二次复方程,求解该复方程并反求Bézier控制顶点得到符合约束条件的四次PH曲线。结果 实验对通过构造插值给定数据点的四次PH曲线进行比较,当形状调节因此改变时,曲线形状可进行有效交互。每次交互得到两条四次PH曲线,通过弧长、弯曲能量、绝对旋转数的计算得到最优曲线,并构造得到PH曲线的等距线。结论 本文方法给定的形状调节参数具有明确的代数意义和几何意义,本文方法易于实现,可有效进行交互。