一类非线性细分格式的保凸与分形性质

一类非线性细分格式的保凸与分形性质丁友东(上海大学计算机学院上海200072)华宣积(复旦大学数学系上海200433)2000.9.261YoudongDing摘要在分析经典插值细分格式的基础上，本文提出了一类函数型非线性离散细分格式，它具有保凸性质：在满足一定条件时,这种格式保证了对于凸数据，其每一步细分多边形都是凸的，从而极限曲线也是凸的。数值例子说明，在不光滑情况下这种格式往往会产生具有分形性质的曲线。2000.9.262YoudongDing1引言曲线曲面生成是CAD/CG领域一个重要的研究内容经典方法：

离散连续离散

(Bézier方法)(deCasteljau算法)(控制点数学表达式曲线曲面离散点)优点:易于分析…缺点:计算量大2000.9.263YoudongDing离散细分方法根据初始数据由计算机直接生成曲线曲面或其它几何形体的一类方法:

离散离散(控制点细分离散点)优点:只须存储离散点列，适合计算机存储和绘制曲线曲面的特点，可以大大加快计算和生成的速度2000.9.264YoudongDing保形性与插值性的协调Bézier方法:有很好的保形性，但插值性差(端点插值)离散细分方法:有很好的插值性,但保形性差(受线性权因子的限制)如何兼顾保形性和插值性是几何造型的许多实际问题要处理的问题2000.9.265YoudongDing离散细分方法的历史1975年,Chaikin、Riesenfeld等提出光滑曲线曲面快速生成的离散细分算法1987年,Dyn等提出经典插值两步型四点细分格式1991年,Cararetta、Dahmen、Micchelli等提出稳定细分法(StationarySubdivisionScheme)国内:1980s,梁友栋、金通光等提出“割角法”2000.9.266YoudongDing离散细分方法的历史(续)1990s,有广泛讨论和应用(包括国内丁玮、齐东旭在分形曲线生成上的讨论,骆岩林、汪国昭在地形地貌模拟上的应用等)1992年,Dyn

、刘鼎元等提出了一种参数型离散点列的保凸插值细分格式(对凸数据)1994年,LeMehaute等讨论了一类函数型离散保凸插值细分方法2000年,丁友东等也提出了一种对参数型离散点列的保凸插值细分格式(对一般数据)2000.9.267YoudongDing离散细分方法的历史(续)上述方法共同点:均须对每个细分点进行独立判断，选择相应的参数,虽然每步采用线性细分格式，但总的格式不是稳定的，即每步采用不同的线性权因子，这样就需要花费大量的非计算时间2000.9.268YoudongDing本文工作在分析经典插值细分格式的基础上，提出一类函数型非线性离散细分格式，在一定的条件下,这种格式保证了对于凸数据，其每一步细分多边形都是凸的，从而极限曲线也是凸的。有趣的是，当选取合适参数时，这种格式往往产生具有分形性质的曲线2000.9.269YoudongDing2一类非线性插值细分格式2000.9.2610YoudongDing多边形曲线的定义2000.9.2611YoudongDing引理2000.9.2612YoudongDing收敛性(定理1)2000.9.2613YoudongDing保凸性(定理2)2000.9.2614YoudongDing保凸性(定理3)2000.9.2615YoudongDing单调递减性质2000.9.2616YoudongDing单调递减性质(图示)2000.9.2617YoudongDing细分格式(*)的推广2000.9.2618YoudongDing细分格式(*)的推广(续)2000.9.2619YoudongDing细分格式(*)的推广(续)2000.9.2620YoudongDing收敛性(定理4)2000.9.2621YoudongDing保凸性(定理5)2000.9.2622YoudongDing保凸性(定理6)2000.9.2623YoudongDing函数F(x,y)的其它取法2000.9.2624YoudongDing分形性质

当合适的参数被选取时,极限曲线出现分形结构(实际上,每细分一次就是一次递归,细分格式就象生成分形图形的生成元,反复递归生成复杂的具有分形结构的图形)2000.9.2625YoudongDing3数值算例数据：{yi}={16.0,9.0,4.0,1.0,0.0,1.0,4.0,9.0,16.0}2000.9.2626YoudongDing(1)经典格式，参数满足保凸条件2000.9.2627YoudongDing(2)经典格式,参数不满足保凸条件2000.9.2628YoudongDing(3)经典格式,极限曲线有分形性质2000.9.2629YoudongDing(4)非线性格式,参数满足保凸条件2000.9.2630YoudongDing(5)非线性格式,参数不满足保凸条件2000.9.2631YoudongDing(6)非线性格式,极限曲线有分形性质2000.9.2632YoudongDing进一步的工作考虑这类细分格式的应用结合应用找出特定的细分格式(函数F(x