论文摘要
本文主要研究基于二元四次Box样条的多进制细分算法。在文中,我们对二进制Loop （?）田分算法进行了推广,首次得到了规则三角形网格上的M进制细分算法的掩模的显式表达式。通过构造和分析M进制细分算法的特征矩阵,得到了细分矩阵的次优势特征值是2重实特征值与细分算法的特征映射是单射的必要条件相结合的等价条件。在Reif给出的结论的基础上,得到了M进制细分极限曲面C1光滑的充分条件。构造了一种四进制细分算法,并利用计算机代数系统证明了当奇异点的价在3到20之间时,所生成的细分极限曲面满足我们所给出的细分极限曲面达到C1光滑的充分条件。还利用计算机代数系统证明了当奇异点的价在3到20之间时,三进制Loop细分算法的极限曲面是C1光滑的,并给出了细分矩阵的次优势特征值的一个取值范围,证明了在此范围内,细分极限曲面都是C1光滑的。本文的结论克服了二进制细分算法的局限性,在实际应用中可以根据需要灵活选择所需进制的细分算法,同时也为形成完整的多进制细分理论奠定了基础。论文由五章组成,第一章是绪论,对细分的发展概况、基础知识、本文的具体安排及创新点进行了叙述。第二、三、四、五章是作者的研究成果。在第二章中,从样条函数空间S42（△）的Box样条Q（x, y）的Fourier变换形式的加细方程出发,推导出了Q（x,y）的M进制细分掩模的计算方法。利用此方法,对任意确定的M,都能直接计算得到细分掩模。还严格证明了在M进制细分过程中,在一个三角形上生成的所有新点为围绕此三角形的一层三角形环的所有顶点的线性组合。在第三章中,利用生成函数方法得到了样条函数空间S42（△）的Box样条Q（x,y）的M进制细分掩模的显式表达式,同时推导出了不同进制的细分掩模之间的关系。并给出了一种计算M进制细分掩模的简单方法。在第四章中,将S42（△）的Box样条的M进制细分规则推广到任意三角形网格,构造并分析了M进制细分算法的细分矩阵和特征映射,得到了细分极限曲面达到C1光滑的充分条件。构造了一种四进制细分算法,并利用计算机代数系统证明了当奇异点的价在3到20之间时,所生成的细分极限曲面是C1光滑的。还利用计算机代数系统构造并分析了三进制Loop （?）田分算法的细分矩阵和特征映射,证明了当奇异点的价在3到20之间时,细分极限曲面是C1光滑的；同时确定了细分矩阵的次优势特征值的一个取值范围,证明了在此范围内,细分极限曲面都是C1光滑的,并给出了一种更简单和易于推广的计算三进制Loop （?）田分掩模的方法,对价为4和5的奇异点,利用所得到的掩模系数能够更快地生成细分极限曲面。最后还推导了S74（△）中的Box样条的M进制加细方程,并就二进制细分算法推导了规则顶点和边点的细分掩模。第五章给出了实际操作中的一种M进制细分掩模公式,并给出了计算实例。1.首先,利用Fourier逆变换和对四个参数的取值结果的分析,得到了计算二元四次Box样条Q（x,y）的M进制细分掩模的方法。利用此方法,对任意确定的M,都可以直接计算得到细分掩模。还严格证明了在M进制细分过程中,在一个三角形上生成的所有新点为围绕此三角形的一层三角形环的所有顶点的线性组合。在前期的工作中,我们已经得到了Q（x,y）的Fourier变换形式的加细方程：定理1：设M≥2为整数,则S42（△）中的Box样条Q（x,y）满足如下的M进制加细方程其中要求11和12的奇偶性相同且利用Fourier逆变换,我们得到其中11和12的奇偶性相同且13和14的奇偶性相同且将细分之后得到的点利用细分之前的点线性表示为通过对公式（3）中的11、12、13和14在取值范围内的讨论,我们得到如下结论：（1）新顶点（0,0）的掩模为（2）新边点（2/M,0）的掩模为（3）新边点（k/M,0）,4≤k≤M的掩模为（4）新边点所在边的第1邻边上的第一个新面点（3/M,1/M）的掩模为（5）新边点所在边的第1邻边上的其余新面点（k/M,1/M）,k为奇数且5≤k≤M的掩模为（6）新边点所在边的其余邻边上的新面点（r/M,s/M）,r和s同奇偶,5≤r≤M,2≤s≤M/3,r≥3s的掩模为定理2：采用M进制三角形细分算法时,在一个三角形上生成的所有新点为围绕此三角形的一层三角形环的所有顶点的线性组合,具体公式为（5）式至（10）式。2.其次,我们利用生成函数的方法推导出了Q（x,y）的M进制细分掩模的显式表达式,推导出了不同进制的细分掩模之间的关系。还给出了一种得到M进制细分掩模的简单方法。利用Q（x,y）的Fourier变换与Box样条N（2,2,2）（x1,x2）的Fourier变换的关系式,我们推导出[G（ξ1,ξ2）]2的生成函数为并得到细分掩模cm-i,n-j,与生成函数的系数b（p,q）之间的关系式：然后,我们推导了生成函数的系数b（p,q）的计算公式,再利用（11）式,得到了Q（x,y）的M进制细分掩模的显式表达式,与前面的（5）式至（10）式是一致的。设RM1（△）表示对规则初始网格△进行的第1次M进制细分,我们证明了定理3：设M=M1·M2,则推论1：设M=M1·M2……Mk,k为正整数,则进一步,我们给出了一种得到细分掩模的简单方法：在一个正六边形的每条边上均匀地取2M-1个点,利用这些点对正六边形进行三方向的三角形剖分,将生成函数的所有系数按照x和y的次数由小到大的次序依次从左到右列于正六边形的所有顶点上,通过对特定点沿着六个方向的2次M个单位的平移,就可以得到相应的掩模系数。3.再次,我们将二元四次Box样条的M进制细分规则推广到任意三角形网格,构造并分析了M进制细分算法的细分矩阵和特征映射,得到了细分极限曲面达到C1光滑的充分条件。构造了一种四进制细分算法,并利用计算机代数系统证明了当奇异点的价在3到20之间时,所生成的细分极限曲面是C1光滑的。构造并分析了三进制Loop细分算法的细分矩阵和特征映射,利用计算机代数系统证明了当奇异点的价在3到20之间时,细分极限曲面是C1光滑的,同时确定了细分矩阵的次优势特征值的一个取值范围,证明了在此范围内,细分极限曲面都是C1光滑的。进一步给出了一种更简单并易于推广的计算三进制Loop细分掩模的方法,对价为4和5的奇异点,利用所得到的掩模系数能够更快地生成细分极限曲面。最后还推导了二元七次Box样条的M进制加细方程,并就二进制细分推导了规则顶点和边点的细分掩模。概括如下：（1）细分极限曲面是C1光滑的充分条件定理4：设价为n的奇异点及最靠近奇异点的边点的细分掩模分别由α及γi,i=0,…,n-1决定,则细分矩阵的次优势特征值是2重实特征值且是Ai（j=1,n-1）的一个特征值的充要条件是细分掩模满足如下条件推论2：设价为n的奇异点及最靠近奇异点的边点的细分掩模分别由α及γi,若细分算法的特征映射是正则的、单射的,且细分掩模满足如下条件k=0则对几乎所有的初始控制网格,极限曲面是C1光滑的。（2）三进制Loop细分算法的细分矩阵及特征映射的构造和分析对三进制Loop （?）细分算法,构造具有分块循环结构的细分矩阵A利用离散Fourier变换计算得到与A酉相似的分块对角矩阵A。A的块Ai,j=0,…,n-1的特征值集合给出了A的11n个特征值其中A的2重次优势实特征值为λ1,所以有利用计算机代数系统Mathematica8.0,计算A1相应于特征值λ1的11阶复特征向量v,得到由v构造细分矩阵A相应于特征值λ1的11n阶特征向量v,对v取共轭v,利用v的实部和虚部得到细分算法的特征映射x（u,v）的11n个控制点坐标。再构造相应于特征映射x的子段x。（u,v）的81个Bezier点bj,j=1,…,81。将x0（u,v）正规化,利用81个正规化的Bezier点bj,j=1,…,81计算x0（u,v）的v向导数的49个Bezier点bv,k0,k=1,…,49。这些Bezier点bv,k0都是λ1和n的函数。再利用计算机代数系统Mathematica8.0来计算并判断bv,k0的分量的正性。取α=5/9,3≤n≤20,得到如下结论：1) Loop给出的选择：取λ1=1/3,结果为：对3≤n≤20,通过符号计算判断都有xv0的Bezier点bv,k0按分量是正的,即三进制Loop细分极限曲面是C1光滑的。当n=3时,若取λ1=1/9,此时通过符号计算判断xv0的Bezier点bv,k0按分量都是非负的,但其中会出现一些分量为零（精确值）的情况,不能证明三进制Loop细分极限曲面是C1光滑的。当取λ1>1/9时,通过符号计算判断xv0的Bezier点bv,k0按分量是正的,即三进制Loop （?）田分极限曲面是C1光滑的。所以我们建议对λ1在（1/9,1/3]之间取值,例如取λ1=1/6。2）我们给出的细分矩阵的次优势特征值λ1的取值范围：定理5：设三进制Loop细分算法的细分矩阵的2重次优势特征值为则当3≤n≤20且λ1∈(1/9,1/2]时,细分极限曲面是C1光滑的。定理中的λ1的上界是最优的。若考虑n=3的情况,则λ1尽量在大于1/9的范围内取值。在实际应用中,对于一般的n,我们建议λ1在(1/9,1/3]之间取值,以保证三进制Loop细分极限曲面都是C1光滑的。（3）一种三进制Loop细分算法边点的掩模计算公式定义利用下式计算掩模系数{γi}：相应的特征值为利用我们给出的掩模公式,在规则点和价为3的点处与三进制Loop细分算法的掩模是一致的,对于价为4和5的奇异点,利用我们给出的方法得到的掩模系数能更快地生成C1光滑的极限曲面。由于实际应用中遇到的奇异点多为4价或5价的,此时利用我们给出的掩模不仅能保证细分算法生成的极限曲面是C1光滑的,而且计算更简单、算法收敛更快,同时易于推广到一般的多进制细分算法。（4）一种四进制细分算法的构造在规则点处,采用规则情况的四进制细分规则（掩模见图2.9）在奇异点附近,奇异点的第二层环上顶点的掩模与规则情况的掩模相同,在奇异点一层环内的顶点利用特征多项式和离散Fourier逆变换来计算掩模系数。具体如下：新顶点：奇异顶点权为α,奇异点周围一层环上的顶点权为1-a/n。参考值：新第一边点：奇异顶点权为β（1）,奇异点周围一层环上的顶点权为γk（1）k=0,1,2,...,n-1。当3≤n≤5时,引入特征多项式：并令参考值：β（1）120/256=15/32。相应特征值为：n≥6时,令并令参考值：β（1）=15/32,μ=1/4。新第二边点：奇异顶点权为β（2）,奇异点周围一层环上的顶点权为γk（2）,k=0,1,2,...,n-1,第二层环上的顶点权采用规则情形的掩模系数。引入特征多项式：并令参考值：β（2）=87/256。新面点：奇异顶点权为β（3）,奇异点周围一层环上的顶点权为γk（3）,k=0,1,2,...,n-1,第二层环上的顶点权采用规则情形的掩模系数。引入特征多项式：并令参考值：我们利用计算机代数系统证明了当3≤n≤20时,按照我们给出的构造方法生成的四进制细分极限曲面都是C1光滑的。4.最后,我们给出了实际操作中的一种M进制细分掩模公式,并给出了计算实例。我们分析得到了一种满足（15）—（17）式、凸包性、对称性和掩模单调递减性质的M进制细分掩模公式：在规则点（n=6）处,掩模公式由（5）至（10）式给出。在奇异点（n≠6）处：（1）对新顶点,掩模公式为（2）对最靠近顶点的第一个新边点,掩模公式如下：若n=3,则若n=4,则若n=5,则若n≥7,则（3）其余新边点和面点,取点P00、P10、P20、P30、Pn-20、Pn-10作为环绕V0的点（点数不足时重复V0补足）,将V0视为规则顶点,利用规则顶点的新边点和新面点的掩模公式计算。