带形状控制的自由曲线曲面参数样条

目的 样条曲线曲面的构造是工程制图中的一个重要部分。针对双曲抛物面上参数样条曲线的构造,在已有的研究基础上提出了一种样条方法使曲线曲面可以任意地逼近一个多边形或者一个网格。方法 在标准四面体内构造一个双曲抛物面,在该曲面上以基函数参数化的方法定义一种带形状参数的参数样条曲线曲面,样条基函数通过将双曲抛物面的有理参数化进行限定,生成单参数有理样条基函数。详细研究了样条的保形性及其端点性质。结果 样条曲线具有一个可变的形状控制因子,可以对曲线进行调整,能以任意精度逼近这个控制四边形或网格。对空间节点列,利用该样条可以生成G²-连续空间曲线,同样对于空间网格可以构造G²-连续的拟合曲面,它所对应的基函数可以是有理形式。结论 实验结果表明,本文在笔者已有的研究基础上提出的参数样条曲线可以通过重心坐标系变换适应为任意的四边形,除了空间四面体内的样条曲线,四面体退化成四边形同样可实现。     

C3连续的单位四元数插值样条曲线

目的 构造一类C³连续的单位四元数插值样条曲线,证明它的插值性和连续性,并把它应用于刚体关键帧动画设计中。方法 利用R³空间中插值样条曲线的5次多项式调配函数的累和形式构造了S³空间中单位四元数插值样条曲线,它不仅能精确通过一系列给定的方向,而且能生成C³连续的朝向曲线。结果 与Nielson的单位四元数均匀B样条插值曲线的迭代构造方法相比,所提方法避免了为获取四元数B样条曲线控制顶点对非线性方程组迭代求解的过程,提高了运算效率;与单位四元数代数三角混合插值样条曲线的构造方法（Su方法）相比,所提方法只用到多项式基,运算速度更快。本例中创建关键帧动画所需的时间与Nielson方法和Su方法相比平均下降了73%和33%。而且,相比前两种方法,所提方法产生的四元数曲线连续性更高,由C²连续提高到C³连续,这意味着动画中刚体的朝向变化更加自然。结论 仿真结果表明,本文方法对刚体关键帧动画设计是有效的,对实时性和流畅性要求高的动画设计场合尤为适用。     

3个控制顶点的类三次Bézier螺线

目的 为了使得过渡曲线的设计更为简单高效。提出基于3个控制顶点的类三次Bézier螺线。方法 通过对基函数的研究首先构造了3条在一定条件下曲率单调递减的类三次Bézier曲线,并由参数的对称性得另3条曲率单调递增的曲线。它们具有端点性、凸包性、几何不变性等三次Bézier曲线的基本性质,特点是只有3个控制顶点。接着严格地证明了此类曲线曲率单调的充分条件。 结果 有两条曲线比三次Bézier曲线的曲率单调条件范围大,且类三次Bézier螺线与三次Bézier螺线存在一定的位置关系。这6条曲线中有4条曲线的一个端点处曲率为零,可组合成4对类三次Bézier螺线来构造两圆弧间半径比例不受限制的S型和C型G²连续过渡曲线;剩下的两条曲线在两圆弧半径相差较大的情况下都可做不含曲率极值点的过渡曲线。最后用实例表明了此类曲线的有效性。结论 在过渡曲线设计中基于3个控制顶点的类三次Bézier螺线比三次Bézier螺线更为简单高效。     

Möbius变换下四次有理抛物-PH曲线的C2 Hermite插值

目的 曲线插值问题在机器人设计、机械工业、航天工业等诸多现代工业领域都有广泛的应用，而已知端点数据的Hermite插值是计算机辅助几何设计中一种常用的曲线构造方法，本文讨论了一种偶数次有理等距曲线，即四次抛物-PH曲线的C² Hermite插值问题。方法 基于M bius变换引入参数，利用复分析的方法构造了四次有理抛物-PH曲线的C² Hermite插值，给出了具体插值算法及相应的Bézier曲线表示和控制顶点的表达式。结果 通过给出"合理"的端点插值数据，以数值实例表明了该算法的有效性，所得12条插值曲线中，结合最小绝对旋转数和弹性弯曲能量最小化两种准则给出了判定满足插值条件最优曲线的选择方法，并以具体实例说明了与其他插值方法的对比分析结果。结论 本文构造了M bius变换下的四次有理抛物-PH曲线的C² Hermite插值，在保证曲线次数较低的情况下，达到了连续性更高的插值条件，计算更为简单，插值效果明显，较之传统奇数次PH曲线具有更加自然的几何形状，对偶数次PH曲线的相关研究具有一定意义。     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

分组渐进迭代逼近算法拟合数据点集

目的 在计算机辅助设计领域里,曲线或曲面的渐进迭代逼近（PIA）性质在插值与拟合问题中有着广泛的应用。如果直接使用PIA方法对所有的数据点集进行拟合,那么在拟合大规模数据点时就缺少一定的灵活性。为了进一步提高渐进迭代逼近方法在拟合大规模点集时的灵活性,提出基于分组的渐进迭代逼近方法。方法 首先对待拟合点集进行分组;其次对分组后的点集采用PIA方法或是基于最小二乘的渐进迭代逼近方法（LSPIA）来得到一组插值或拟合精度不断改善的曲线/曲面;最后运用曲线/曲面拼接算法保证曲线/曲面的连续性,得到1条/张插值或拟合于给定点集的曲线/曲面。结果 给定相同的数据点集,分别采用分组PIA方法,PIA方法和LSPIA方法进行拟合。分组PIA方法与PIA方法相比误差减少的倍数与组数相当;分组PIA方法与LSPIA方法相比误差减少一半。结论 本文将分组思想引入渐进迭代逼近方法之中,提出了基于分组的渐进迭代逼近方法。该分组算法适用于拟合大规模数据点集,在拟合过程中,可以提高渐进迭代逼近方法在拟合大规模点集时的灵活性;经过理论推导证明了曲线/曲面的迭代效率有所提高,且与PIA方法相比误差有较大的改善。     

基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患,以及服务器端全局路网索引利用效率低的缺陷,提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息,生成查询位置所在路段满足l-路段多样性的匿名查询序列,并将匿名查询序列提交LBS服务器,从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端,提出基于路网基本单元划分的分段式近邻查询处理策略,对频繁查询请求路网基本单元,构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构,实现基于索引的快速查找.对非频繁请求路网基本单元,采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价,在保证查询结果正确的同时,提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明,所提方法在兼顾查询准确性的同时,有效地提高了查询处理效率.     

任意三角形网格的基于二元四次箱样条分片C1曲面

提出一种以任意三角剖分为控制网格的二元箱样条曲面算法.二元三方向剖分是方向最少的三角剖分,建立在其上的二元三向四次箱样条在CAGD等领域有着广泛的应用.其规范的箱样条曲面计算仅适用于控制点的价数均为6的网格.从规范的算法出发,提出了一种任意价数控制网格的曲面计算算法,并对算法的连续性等进行了详细的分析.生成的曲面具有保凸性,且是分片C¹连续的.该算法可进行3D离散点全局或局部插值,并可应用于3D曲面重构等领域.     

基于能量优化G2连续插值三次样条曲线

给出了一种在能量优化意义下构造G²连续保形插值三次参数样条曲线的方法。具体步骤如下：（1）以曲线应变能最小为目标构造目标函数，通过解线性方程组，求出优化意义下的每个插值点处的最优切矢方向；（2）用文中给出的简易公式求出各插值点的曲率，进而计算出插值点处的切矢模长，使曲线满足G²连续、保形插值的条件；（3）用Hermite插值方法求出相邻两插值点间的曲线。实验结果显示了方法的有效性。     

G 2 interpolation and blending on surfaces

We introduce a method for curvature-continuous (G ²) interpolation of an arbitrary sequence of points on a surface (implicit or parametric) with prescribed tangent and geodesic curvature at every point. The method can also be used forG ² blending of curves on surfaces. The interpolation/blending curve is the intersection curve of the given surface with a functional spline (implicit) surface. For the construction of blending curves, we derive the necessary formulas for the curvature of the surfaces. The intermediate results areG ² interpolation/blending methods in IR².     

Constructing G 1 continuous curve on a free-form surface with normal projection

In this paper, we develop a new method for G ¹ continuous interpolation of an arbitrary sequence of points on an implicit or parametric surface with a specified tangent direction at every point. Based on the normal projection method, we design a G ¹ continuous curve in three-dimensional space and then project orthogonally the curves onto the given surface. With the techniques in classical differential geometry, we derive a system of differential equations characterizing the projection curve. The resulting interpolation curve is obtained by numerically solving the initial-value problems for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for a parametric case or in three-dimensional space for an implicit case. Several shape parameters are introduced into the resulting curve, which can be used in subsequent interactive modification such that the shape of the resulting curve meets our demand. The presented method is independent of the geometry and parameterization of the base surface, and numerical experiments demonstrate that it is effective and potentially useful in surface trim, robot, patterns design on surface and other industrial and research fields.     

Constructing up to G 2 continuous curve on freeform surface

This paper presents new methods for G ¹ and G ² continuous interpolation of an arbitrary sequence of points on an implicit or parametric surface with prescribed tangent direction and both tangent direction and curvature vector, respectively, at every point. We design a G ¹ or G ² continuous curve in three-dimensional space, construct a so-called directrix vector field using the space curve and then project a special straight line segment onto the given surface along the directrix vector field. With the techniques in classical differential geometry, we derive a system of differential equations for the projection curve. The desired interpolation curve is just the projection curve, which can be obtained by numerically solving the initial-value problems for a system of first-order ordinary differential equations in the parametric domain associated to the surface representation for the parametric case or in three-dimensional space for the implicit case. Several shape parameters are introduced into the resulting curve, which can be used in subsequent interactive modification such that the shape of the resulting curve meets our demand. The presented method is independent of the geometry and parameterization of the base surface, and numerical experiments demonstrate that it is effective and potentially useful in patterns design on surface.     

Interpolating G Bézier surfaces over irregular curve networks for ship hull design

We propose a local method of constructing piecewise G¹ Bézier patches to span an irregular curve network, without modifying the given curves at odd- and 4-valent node points. Topologically irregular regions of the network are approximated by implicit surfaces, which are used to generate split curves, which subdivide the regions into triangular and/or rectangular sub-regions. The subdivided regions are then interpolated with Bézier patches. We analyze various singular cases of the G¹ condition that is to be met by the interpolation and propose a new G¹ continuity condition using linear and quartic scalar weight functions. Using this condition, a curve network can be interpolated without modification at 4-valent nodes with two collinear tangent vectors, even in the presence of singularities. We demonstrate our approach in a ship hull.     

Constructing spherical curves by interpolation

Based on a composite conical surface patch, we develop new simple methods for up to G² continuous interpolation of an arbitrary sequence of points on a sphere with a specified tangent direction and curvature vector at every point. The resulting interpolation curve is the intersection of the given sphere and the composite conical surface patch. Unlike some existing methods, introduced into the method are several free parameters that can be used in subsequent interactive modification such that the resulting curve’s shape hits our demand, and the resulting curve can be expressed explicitly. Experiments demonstrate the method is effective and potentially useful in pattern design on sphere, sphere trim, robot, and other industrial and research fields.     

G2连续的低次避障代数样条曲线

为便于机器人在避障时能高速前进,把整体G2连续的低次避障曲线从参数形式拓展到代数样条形式上。首先,对导向折线段中除去首末线段的其他线段插入中点,以生成一组控制多边形;然后,根据各控制多边形和与之对应的障碍物,得到既能使曲线规避所有障碍物,又能使曲线在整体上保持G2连续的形状因子。低次避障代数样条曲线不仅能够直接得到与给定点之间的位置关系,还具有次数低、连续阶高、计算简单、保形性好和便于控制的优点。曲线在次数为3时更是具有局部可调性,其在设计时的灵活度得以增加。     

A constrained guided G continuous spline curve

A method for drawing a guided G¹ continuous planar spline curve that falls within a closed boundary is presented. The curve is composed of segments of quadratic polynomials (parabolas) and rational quadratics (conics) that join with continuous unit tangent vectors. The boundary is composed of straight line segments and circular arcs.     

GC 1 multisided Bézier surfaces

This paper presents a new method for generating a tangent-plane continuous (GC¹) multisided surface with an arbitrary number of sides. The method generates piecewise biquintic tensor product Bézier patches which join each other with G¹-continuity and which interpolate the given vector-valued first order cross-derivative functions along the boundary curves. The problem of the twist-compatibility of the surface patches at the center points is solved through the construction of normal-curvature continuous starlines and by the way the twists of surface patches are generated. This avoids the inter-relationship among the starlines and the twists of surface patches at the center points. The generation of the center points and the starlines has many degrees of freedom which can be used to modify and improve the quality of the resulting surface patches. The method can be used in various geometric modeling applications such as filling n-sided holes, smoothing vertices of polyhedral solids, blending multiple surfaces, and modeling surface over irregular polyhedral line and curve meshes.     

G2 Surface Interpolation Over General Topology Curve Networks

The basic idea of curve network‐based design is to construct smoothly connected surface patches, that interpolate boundaries and cross‐derivatives extracted from the curve network. While the majority of applications demands only tangent plane (G¹) continuity between the adjacent patches, curvature continuous connections (G²) may also be required. Examples include special curve network configurations with supplemented internal edges, “master‐slave” curvature constraints, and general topology surface approximations over meshes. The first step is to assign optimal surface curvatures to the nodes of the curve network; we discuss different optimization procedures for various types of nodes. Then interpolant surfaces called parabolic ribbons are created along the patch boundaries, which carry first and second derivative constraints. Our construction guarantees that the neighboring ribbons, and thus the respective transfinite patches, will be G² continuous. We extend Gregory's multi‐sided surface scheme in order to handle parabolic ribbons, involving the blending functions, and a new sweepline parameterization. A few simple examples conclude the paper.