Real-time NURBS interpolation using FPGA for high speed motion control

Modern motion control adopts NURBS (Non-Uniform Rational B-Spline) interpolation for the purpose of achieving high-speed and high-accuracy performance. However, in conventional control architectures, the computation of the basis functions of a NURBS curve is very time-consuming due to serial computing constraints. In this paper, a novel FPGA (Field Programmable Gate Array) based motion controller utilizing its high-speed parallel computing power is proposed to realize the Cox-de Boor algorithm for second and higher degrees NURBS interpolation. The motion control algorithm is also embedded in the FPGA chip to implement real-time control and NURBS interpolation simultaneously for multi-axis servo systems. The proposed FPGA-based motion controller is capable of performing the Cox-de Boor algorithm and the IIR (Infinite Impulse Response) control algorithm in about 46 clock cycles, as compared to the 1303 clock cycles by the traditional approach. Numerical simulations and experimental tests using an X-Y table verify the outstanding computation performance of the FPGA-based motion controller. The result indicates that shorter sampling time (10 μs) can be achieved for NURBS interpolation which is highly critical to the success of high-speed and high-accuracy motion control.     

Isogeometric analysis for strain field measurements

In this paper, the potential of isogeometric analysis for strain field measurement by digital image correlation is investigated. Digital image correlation (DIC) is a full field kinematics measurement technique based on gray level conservation principle and the formulation we adopt allows for using arbitrary displacement bases. The high continuity properties of Non-Uniform Rational B-Spline (NURBS) functions are exploited herein as an additional regularization of the initial ill-posed problem. k-Refinement is analyzed on an artificial test case where the proposed methodology is shown to outperform the usual finite element-based DIC. Finally a fatigue tensile test on a thin aluminum sheet is analyzed. Strain localization occurs after a certain number of cycles and combination of NURBS into a DIC algorithm clearly shows a great potential to improve the robustness of non-linear constitutive law identification.     

Robust uniform triangulation algorithm for computer aided design

This paper presents a new robust uniform triangulation algorithm that can be used in CAD/CAM systems to generate and visualize geometry of 3D models. Typically, in CAD/CAM systems 3D geometry consists of 3D surfaces presented by the parametric equations (e.g. surface of revolution, NURBS surfaces) which are defined on a two dimensional domain. Conventional triangulation algorithms (e.g. ear clipping, Voronoi-Delaunay triangulation) do not provide desired quality and high level of accuracy (challenging tasks) for 3D geometry. The approach developed in this paper combines lattice tessellation and conventional triangulation techniques and allows CAD/CAM systems to obtain the required surface quality and accuracy. The algorithm uses a Cartesian lattice to divide the parametric domain into adjacent rectangular cells. These cells are used to generate polygons that are further triangulated to obtain accurate surface representation. The algorithm allows users to control the triangle distribution intensity by adjusting the lattice density. Once triangulated, the 3D model can be used not only for rendering but also in various manufacturing and design applications. The approach presented in this paper can be used to triangulate any parametric surface given in S(u,v) form, e.g. NURBS surfaces, surfaces of revolution, and produces good quality triangulation which can be used in CAD/CAM and computer graphics applications.     

Constrained multisine input signals for plant-friendly identification of chemical process systems

This paper considers the use of constrained minimum crest factor multisine signals as inputs for plant-friendly identification testing of chemical process systems. The methodology presented here effectively integrates operating restrictions, information-theoretic requirements, and state-of-the-art optimization techniques to design minimum crest factor multisine signals meeting important user-specified time and frequency domain properties. A series of optimization problem formulations relevant to problems in linear, nonlinear, and multivariable system identification are presented; these culminate with their application to the modeling of the Weischedel–McAvoy high-purity distillation column problem, a demanding nonlinear and highly interactive system. The effectiveness of these signals for modeling for control purposes and the ability to incorporate a priori nonlinear models in the signal design procedure are demonstrated in this distillation system case study.     

A convergence theorem for the fuzzy subspace clustering (FSC) algorithm

We establish the convergence of the fuzzy subspace clustering (FSC) algorithm by applying Zangwill's convergence theorem. We show that the iteration sequence produced by the FSC algorithm terminates at a point in the solution set S or there is a subsequence converging to a point in S. In addition, we present experimental results that illustrate the convergence properties of the FSC algorithm in various scenarios.     

NURBS体的DEXEL化与布尔运算

NURBS曲面与NURBS体造型技术是目前复杂体造型的重要工具,但复杂体之间的布尔运算求交困难。将NURBS曲面围成的体与NURBS体体素化(VOXEL化)为由一系列平面凸四边形或三角形表示的体,通过DEXEL射线组群与四边形或三角形求交,实现NURBS体的DEXEL化。在同一DEXEL模型空间实现复杂NURBS体之间的布尔运算,所有运算是线性的。该方法可推广到在逆向工程中生成的由三角面表示的体。在Java2.0与Java3D环境下编程实现并验证了该算法,给出了一个机械零件设计实例。     

The convergence rate of the sandwich algorithm for approximating convex functions

The Sandwich algorithm approximates a convex function of one variable over an interval by evaluating the function and its derivative at a sequence of points. The connection of the obtained points is a piecewise linear upper approximation, and the tangents yield a piecewise linear lower approximation. Similarly, a planar convex figure can be approximated by convex polygons. Different versions of the Sandwich algorithm use different rules for selecting the next evaluation point. We consider four natural rules (interval bisection, slope bisection, maximum error rule, and chord rule) and show that the global approximation error withn evaluation points decreases by the order ofO(1/n ²), which is optimal. By special examples we show that the actual performance of the four rules can be very different from each other, and we report computational experiments which compare the performance of the rules for particular functions.     

Biarc approximation of polygons within asymmetric tolerance bands

We present an algorithm for approximating a simple planar polygon by a tangent-continuous approximation curve that consists of biarcs. Our algorithm guarantees that the approximation curve lies within a user-specified tolerance from the original polygon. If requested, the algorithm can also guarantee that the original polygon lies within a user-specified distance from the approximation curve. Both symmetric and asymmetric tolerances can be handled. In either case, the approximation curve is guaranteed to be simple. Simplicity of the approximation curve is achieved by restricting it to a ‘tolerance band’ which represents the user-specified tolerance and which takes into account bottlenecks of the input polygon. The tolerance band itself is computed by means of a regular grid and so-called k-dops. The basic algorithm is readily extended to compute biarc approximations of collections of polygonal curves simultaneously. Experimental results demonstrate that this algorithm computes biarc approximations of an n-vertex polygon with a close-to-minimum number of biarcs in roughly time.     

Efficient Hausdorff Distance computation for freeform geometric models in close proximity

We present an interactive-speed algorithm for computing the Hausdorff Distance (HD) between two freeform geometric models represented with NURBS surfaces. The algorithm is based on an effective technique for matching a surface patch from one model to the corresponding nearby surface patch on the other model. To facilitate the matching procedure, we employ a bounding volume hierarchy (BVH) for freeform NURBS surfaces, which provides a hierarchy of Coons patches and bilinear surfaces approximating the NURBS surfaces (Kim et al., 2011 [1]). Comparing the local HD upper bound against a global HD lower bound, we can eliminate the majority of redundant surface patches from further consideration. The resulting algorithm and the associated data structures are considerably simpler than the previous BVH-based HD algorithms. As a result, we can compute the HD of two freeform geometric models efficiently and robustly even when the two models are in close proximity. We demonstrate the effectiveness of our approach using several experimental results.     

Filling n-sided regions with NURBS patches

n -sided region with G ^ɛ continuous NURBS patches that interpolate boundary curves and approximate given cross-boundary derivatives. The NURBS surfaces joining along inner or boundary curves have normal vectors that do not deviate more than the user-specified angular tolerance ɛ. The method is general in that there are no restrictions on the number of boundary curves, and the cross-boundary derivatives can be specified independently. To satisfy all conditions, only one degree elevation is needed.     

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.     

A New Representation and Algorithm for Constructing Convex Hulls in Higher Dim ensional Spaces

This paper presents a new and simple scheme to describe the convex hull in R^d,which only uses three kinds of the faces of the convex hull.i.e.,the d-1-faces,d-2-faces and 0-faces.Thus,we develop and efficient new algorithm for constructing the convex hull of a finite set of points incrementally.This algorithm employs much less storage and time than that of the previously-existing approaches.The analysis of the runniing time as well as the storage for the new algorithm is also theoretically made.The algorithm is optimal in the worst case for even d.     

女性束裤舒适性的凸肚体数字化修正

以女性凸肚体为研究对象,在保证人体穿着舒适度的前提下,采用NURBS曲线变形算法对腹部体型进行个性化数字修正。将修正后曲线用Hausdorff距离的误差评判方法与标准人体曲线对比,选出最优的束裤修正曲线。研究表明,该方法不仅能满足人体穿着舒适度,而且能更准确真实地再现凸肚体试穿束裤后的体型修正曲线,达到既舒适又美观的效果,从而为虚拟试衣决策提供重要的参考依据。     

NURBS曲线自动光顺的一种有效算法

提出了一种局部光顺NURBS曲线的算法。算法建立在重复删除和插入节点的过程中，这个重复删除和插入的节点通过一个光顺准则自动选择。此算法自动找出NURBS曲线需要修改的那一点，局部修改控制多边形，使生成的新曲线更加光顺。     

基于当前基线垂直落差最大化的凸壳递归新算法

本文依据同构化凸壳构造基本定理,率先发现并证明了凸壳顶点的分布域性态与垂直落差特性;首次给出当前基线垂直落差最大化的二维点集凸壳算法构造创新思想,提出了比迄今最优秀凸壳算法之一的快凸壳算法效率更高的、基于当前垂直落差最大化的凸壳递归新算法,指出了它具有进一步改造为并行算法的潜力.该新算法的主要特点是:1)找出初始点分布域的所有最外点(其个数,下限为3,上限为8),作为所求凸壳的初始顶点.2)删除这些最外点所构成最外点凸多边形(其边数,下限为3,上限为8)所覆盖的凸壳内点后,把所剩点分布域,分为若干个初始子分布域(其个数,下限为0,上限为4).3) ①对各个非空初始子分布域顺次调用本新算法的递归过程子算法,分别在各初始子分布域中找出其当前基线垂直落差最大点(其个数,下限为1,上限为2),并作为其各初始子分布域内凸壳的新顶点;②删除当前基线与垂直落差最大点所构成基线凸多边形(其边数,下限为3,上限为4)内的凸壳内点后,把所剩点分布域,分为多个更小的子分布域(其个数,下限为0,上限为2);③对各个更小的当前子分布域,分别递归调用过程子算法,以找出其当前基线的垂直落差最大点作为凸壳新顶点.     

基于双群双域四向水平倾角最小化圈绕的凸壳并行新算法

本文针对现行凸壳算法(诸如:串行类的卷包裹凸壳算法、格雷厄姆凸壳算法等,并行类的折半分治凸壳算 法、快速凸壳算法等)效率不高的缺点,根据同构化凸壳构造基本定理,利用工作站机群优点,提出了效率更高的双群(即:其机群分为2个子机群)、双域(即:其数据分布域分为2个子分布域)、四向(即:其每个子分布域内凸壳顶点的寻找方向均各自为顺时针、逆时针2个寻找方向)水平倾角最小化圈绕的凸壳并行新算法.     

Combining graph connectivity &; dominant set clustering for video summarization

The paper presents an automatic video summarization technique based on graph theory methodology and the dominant sets clustering algorithm. The large size of the video data set is handled by exploiting the connectivity information of prototype frames that are extracted from a down-sampled version of the original video sequence. The connectivity information for the prototypes which is obtained from the whole set of data improves video representation and reveals its structure. Automatic selection of the optimal number of clusters and hereafter keyframes is accomplished at a next step through the dominant set clustering algorithm. The method is free of user-specified modeling parameters and is evaluated in terms of several metrics that quantify its content representational ability. Comparison of the proposed summarization technique to the Open Video storyboard, the Adaptive clustering algorithm and the Delaunay clustering approach, is provided.

Mixed controllers for SISO discrete time systems

In this paper we present a methodology for designing mixed controllers. These controllers allow for minimizing the worst-case peak output due to a persistent disturbance, while, at the same time, satisfying an norm constraint upon some closed-loop transfer function of interest. Thus, they are of interest for applications dealing with mixed time/frequency domain performance specifications. The main result of the paper shows that suboptimal mixed controllers can be obtained by solving a sequence of problems, each one consisting of a finite-dimensional convex optimization and a standard, unconstrained problem.     

NURBS曲线曲面插补算法基于S12的测试

传统的基于直线和圆弧的插补算法已经不能满足数控技术发展的需要,采用基于自由曲线的插补算法是大势所趋。目前关于NURBS曲线插补的研究大部分还停留在单段的研究上,没有突破传统数控技术的范围。在目前开放式数控技术日益重要的情况下,提出了基于整条曲线或者整个曲面的插补算法,并将该算法应用在S12单片机上进行测试,测试结果显示能够满足要求。