Elitist clonal selection algorithm for optimal choice of free knots in B-spline data fitting

Data fitting with B-splines is a challenging problem in reverse engineering for CAD/CAM, virtual reality, data visualization, and many other fields. It is well-known that the fitting improves greatly if knots are considered as free variables. This leads, however, to a very difficult multimodal and multivariate continuous nonlinear optimization problem, the so-called knot adjustment problem. In this context, the present paper introduces an adapted elitist clonal selection algorithm for automatic knot adjustment of B-spline curves. Given a set of noisy data points, our method determines the number and location of knots automatically in order to obtain an extremely accurate fitting of data. In addition, our method minimizes the number of parameters required for this task. Our approach performs very well and in a fully automatic way even for the cases of underlying functions requiring identical multiple knots, such as functions with discontinuities and cusps. To evaluate its performance, it has been applied to three challenging test functions, and results have been compared with those from other alternative methods based on AIS and genetic algorithms. Our experimental results show that our proposal outperforms previous approaches in terms of accuracy and flexibility. Some other issues such as the parameter tuning, the complexity of the algorithm, and the CPU runtime are also discussed.     

Education-driven research in CAD

We argue for a new research category, named education-driven research (EDR), which fills the gap between traditional field-specific research that is not concerned with educational objectives and research in education that focuses on fundamental teaching and learning principles and possibly on their customization to broad areas (such as mathematics or physics), but not to specific disciplines (such as CAD). The objective of EDR is to simplify the formulation of the underlying theoretical foundations and of specific tools and solutions in a specialized domain, so as to make them easy to understand and internalize. As such, EDR is a difficult and genuine research activity, which requires a deep understanding of the specific field and can rarely be carried out by generalists with primary expertise in broad education principles. We illustrate the concept of EDR with three examples in CAD: (1) the Split and Tweak subdivisions of a polygon and its use for generating curves, surfaces, and animations; (2) the construction of a topological partition of a plane induced by an arbitrary arrangement of edges; and (3) a romantic definition of the minimal and Hausdorff distances. These examples demonstrate the value of using analogies, of introducing evocative terminology, and of synthesizing the simplest fundamental building blocks. The intuitive understanding provided by EDR enables the students (and even the instructor) to better appreciate the limitations of a particular solution and to explore alternatives. In particular, in these examples, EDR has allowed the author to: (1) reduce the cost of evaluating a cubic B-spline curve; (2) develop a new subdivision curve that is better approximated by its control polygon than either a cubic B-spline or an interpolating 4-point subdivision curve; (3) discover how a circuit inclusion tree may be used for identifying the faces in an arrangement; and (4) rectify a common misconception about the computation of the Hausdorff error between triangle meshes. We invite the scientific community to encourage the development of EDR by publishing its results as genuine research contributions in peer-reviewed professional journals.     

参数三次B样条曲线的一种整体光顺方法

本文在能量法的基础上，提出了一种新的目标函数，给出了参数三次Ｂ样条曲线的一种新的整体光顺方法。利用这种方法得到的曲线不仅具有较小的应变能，而且曲率变化比较均匀，具有很好的光顺效果。该方法能推广到对曲面的光顺。     

带有给定切线多边形的保形有理三次B样条曲线

本文给出了带有给定切线多边形的保形有理三次Ｂ样条曲线，其部分权因子可通过选取切点的位置来确定，由此方法还导出了保形有理三次Ｂ样条插值曲线，最后，给出了两个例子。     

一种等高线自动加密算法

本文给出的算法可以在间距较大的等高线之间形成新的等高线，该算法以任意直线与B-样条曲线求变算法为基础。新等高践的形成建立在原有等高线和已知的离散点等客观信息基础之上，等高线加密效果好。     

基于B-样条曲线的线缆变形仿真

线缆变形仿真是线缆辅助设计和维修过程仿真需要解决的核心问题,也是目前虚拟现实技术研究的热点之一。B-样条曲线是计算几何学的重要理论成果,已经广泛应用于计算机辅助设计。本文首先对B-样条函数的概念进行了简单介绍,分析了用三次开放B-样条曲线进行线缆变形仿真的优越性;然后将全局能量优化方法与高度坐标置零法结合求解曲线控制点的坐标,建立关于已知两端点位置和通过指定点的线缆模型;用Lagrange乘子法建立指定点有切矢约束的线缆模型。这种方法描述的是处于平衡状态的线缆变形,计算量小,模型逼真,而且形状控制方便,能够实现线缆布线指导和维修过程仿真。     

Spline-based meshfree method with extended basis

In this work, an extension has been performed on the analysis basis of spline-based meshfree method (SBMFM) to stabilize its solution. The potential weakness of the SBMFM is its numerical instability from using regular grid background mesh. That is, if an extremely small trimmed element is produced by the trimming curves that represent boundaries of the analysis domain, it can induce an excessively large condition number in global system matrix. To resolve the instability problem, the extension technique of the weighted extended B-spline (WEB-spline) is implemented in the SBMFM. The basis functions with very small trimmed supports are extrapolated by neighboring basis functions with some special scheme so that those basis functions can be condensed in the solution process. In order to impose essential boundary conditions in the SBMFM with extended basis, Nitsche's method is implemented. Using numerical examples, the presented SBMFM with extended basis is shown to be valid and effective. Moreover, the condition number of the system is well-managed guaranteeing the stability of the numerical analysis.     

基于空间加权互信息的非刚性医学图像配准

互信息作为相似性测度标准在医学图像配准领域应用广泛,尤其是在刚性配准研究中,能实现较高配准精度和非常稳健的配准效果。然而由于非线性形变的复杂性,在非刚性配准领域,对基于互信息的配准方法进行深入研究势在必行。提出的方案采用基于B样条的自由变换模型模拟医学图像中解剖结构的非线性形变,同时根据变换模型,考虑空间信息对配准效果的影响,以空间加权的方式对互信息方法进行改进。使用对大规模参数优化效果较好的LBFGS方法对配准参数进行优化,编程实现程序,并通过实验对效果进行验证和分析。实验结果显示,该方案配准精度明显优于传统的互信息方法。     

Total curvature variation fairing for medial axis regularization

We present a new fairing method for planar curves, which is particularly well suited for the regularization of the medial axis of a planar domain. It is based on the concept of total variation regularization. The original boundary (given as a closed B-spline curve or several such curves for multiply connected domains) is approximated by another curve that possesses a smaller number of curvature extrema. Consequently, the modified curve leads to a smaller number of branches of the medial axis. In order to compute the medial axis, we use the state-of-the-art algorithm from [1] which is based on arc spline approximation and a domain decomposition approach. We improve this algorithm by using a different decomposition strategy that allows to reduce the number of base cases from 13 to only 5. Moreover, the algorithm reduces the number of conic arcs in the output by approx. 50%.