保单调插值的奇异混合三角/双曲B样条

为了使得插值曲线保单调,设计了两类新的平面参数曲线及其保单调插值算法.计算奇异混合函数,把三角/双曲多项式B样条曲线与奇异多边形通过奇异混合函数混合,无需解方程组或繁琐的迭代,得到自动插值给定平面点列且C2(或G1)连续的带形状参数的复合曲线,尤其能得到摆线、螺旋线、双曲线、悬链线等各类超越曲线.通过把插值曲线的导矢分量转化为类Bernstein多项式,并且利用Bernstein多项式非负的充要条件,得到插值曲线单调的充要条件,获得形状参数合适的取值范围. 该方法简单方便,所得参数范围保证了插值曲线保单调.     

过测地线的近似极小直纹曲面设计

为了在服装鞋帽制造业及材料剪裁中采用过给定测地线且具有近似最小面积的直纹曲面,提出一种直纹曲面算法.该算法将过给定测地线的曲面设计和近似极小曲面的逼近技术进行有机结合,把直纹曲面表示成含2个参变量的形式;利用变分法的思想进行最优化,并分别在弧长参数和一般参数下对其进行了讨论.最后通过一些实例验证了文中算法的正确性和有效性.     

带边界约束的4片相邻三角Bézier曲面的近似合并

基于Jacobi基的性质以及条件极值问题的求解,对4片相邻三角Bézier曲面进行了近似合并.首先利用Jacobi基的正交性及其与Bézier基之间的基转换矩阵,得到合并前后三角Bézier曲面距离函数的L2范数;为了保证合并前后三角Bézier曲面在边界C0连续以及角点处高阶连续,控制顶点必须满足一系列线性约束.为得到与原曲面距离最小的近似合并曲面,只需要利用Lagrange乘子法解决带线性约束的条件极值即可.合并三角Bézier曲面的控制顶点可用矩阵显式表达,且合并的逼近误差可由合并前后曲面距离函数的L1范数形式精确给出.通过提高合并三角Bézier曲面的次数,可减小合并误差、改善合并效果.数值实例表明,该方法计算简单、直接,适用性强,逼近效果佳.     

信息处理中有效维持动态有序集的新方法

文中研究了信息搜索及信息处理领域中的一个重要问题,就是如何有效地维持关键字为位串的动态有序集,以支持查找、加入、删除、求最值等操作.基于前人的研究成果,我们提出了一种性质更为完备的二叉树(RBT,rich binary tree).它同时具备二叉搜索树和数字查找树的性质;并且,所有结点都保存了它与祖先结点中次大者和次小者的最高差别位.于是,动态有序集的维持转化为对树结点的动态操作并且保证RBT的性质不变.该方法的最坏复杂度是O(L),其中L是关键字的字长.因为一般对象在计算机中都是以二进制形式存储的,所以该方法具有明显的应用潜力及可观的经济效益.文中的RBT可视为一种通用的数据结构,可以非常高效地解决与序有关的问题,比如查找、排序和维持优先队列等.例如,实验证明对于长关键字的排序,我们的算法基本上线性增长,优于快速排序,而且支持常数时间的动态插入和动态删除.     

无局部自交的轴变形新方法

提出了一种无局部自交的轴变形的新算法.不同于传统的方法,新方法通过调整轴曲线的控制顶点及形状来调整轴曲线的曲率,从而避免物体发生局部自交.另外,文中还给出了一种快速判断轴变形中物体发生局部自交的方法,并给出了快速求解交点并去除自交的算法.上述方法计算量少,效率高,能应用于实时的计算机动画和几何造型系统中,具有广泛的应用前景.     

有理三角B-B曲面多项式逼近的一个有效算法

将美国计算机图形专家Sederberg提出的有理曲线多项式逼近的思想与算法推广到工程中广泛采用的三角域上的有理曲面.主要工作是:给定一张有理三角B-B曲面,通过将多项式三角B-B曲面的控制顶点表示成相同次数的有理三角B-B曲面的形式,即将多项式曲面的移动控制顶点看作在有理三角B-B曲面上的移动点,并添加约束条件,构造了三角域上的Hybrid曲面;适当地选取有理三角B-B曲面的1次Hybrid曲面表示,推导了彼此等同但次数相邻的两张Hybrid曲面之间控制顶点的递推公式;利用Hybrid曲面移动控制顶点凸包内的一点来代替该移动控制顶点,得到了多项式三角B-B曲面逼近有理三角B-B曲面的一个算法,并在文中给出了数值实例.这些结果可以明显地提高计算机辅助几何设计系统的数据可换性与计算效率.     

一类平面参数曲线的保单调插值

曲线、曲面的保形插值是几何外形设计的一个重点和难点课题,而保单调和保凸是保形的两个基本内容.研究了一类带有形状可调参数的平面参数曲线的保单调插值方法.其基本思想是:首先构造带有形状可调参数(的一类平面(-B样条插值曲线,再把其一阶导矢的两个分量分别转化为Bernstein多项式,从而利用Bernstein多项式的正性条件,得到此曲线为单调的充要条件,即形状参数(的取值范围,简单、快捷地实现此参数样条曲线的保单调插值.实例计算及绘图验证了理论推导的正确性与有效性.该方法的方便、有效使其易于在工程实践中获得广泛应用.     

基于非均匀Catmull-Clark细分方法的曲线插值

带有复杂型曲线插值约束的细分曲面的生成,是计算机图形学及几何造型技术等领域所关心的一个问题.鉴于此,提出了一种高效的可以插值三次NURBS曲线的细分曲面生成方法.只需在被插值曲线的控制多边形两侧构造具有对称性质的四边形,构成对称网格带;证明了对该对称网格带应用Sederberg等人提出的非均匀Catmull-Clark细分规则以后,它将收敛于这条被插值曲线.因此,含有这种对称网格带的多面体网格的细分极限曲面即为满足曲线插值约束的细分曲面.应用该方法,既可以插值单条NURBS曲线,也可以插值由多条NURBS曲线组成的曲线网格.因此,该方法广泛适用于产品外形和图形软件设计.     

三维带符号的欧氏距离变换及其应用

距离变换是图像处理中历史悠久的研究课题．该文将二维带符号的欧氏距离变换推广到三维，对其进行了优化，分析了它的计算复杂度，并应用于解决计算机图形学中的两个重要问题：第一，将图形对象的三角网格表示转换为它的距离场表示．即首先将三角网格模型离散为体素表示，利用三维带符号的距离变换，将求空间一点到图形对象的最短距离的全局搜索过程，转化为求这一点到离它最近的特征体素所包含的图形对象部分的局部搜索过程；第二，利用类似的思想，求两张空间曲面之间的最短距离．     

基于内在变量的空间三角网格的形状混合

本文给出了基于内在变量插值的空间三角网格形状混合的内在解算法。