[doc] 一种参数多项式曲面片的逐点生成算法

[doc] 一种 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 多项式曲面片的逐点生成算法 一种参数多项式曲面片的逐点生成算法 第7卷(A版)第7期 2002年7月 中国图象图形 JournalofImageandGraphics Vo1.7(A),No.7 Ju1.2002 一 种参数多项式曲面片的逐点生成算法 黄有度朱功勤 (合肥工业大学数学与信息科学系,合肥230009) 摘要在计算机绘图中,一般来说,曲线实际上是由折线代替,而曲面实为小平面拼接而成.在使计算量降到最 低的情况下画出真正的曲线方面,已有许多文章研究了曲线的逐点生成 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ,并取得了一定的进展,但是尚无有效 的快速逐点生成曲面的方法.为了快速逐点生成曲面,在建立多项式函数递推计算公式和算法的基础上,给出了一 种逐点生成参数多项式曲面片的算法,由于此算法中只用到整数加法运算,且点数的适当选取可使计算量达到极 小,因此是一种很有效的算法.该方法还可加以改进,而用于有理函数, 这无疑对有理曲线曲面(如NURBS曲线曲 面)的快速生成以及对计算机图形学的其他一些领域都是有意义的. 关键词参数多项式曲面快速逐点生成整数加法运算Bernstein基函 数 中图法分类号:TP391.41文献标识码:A文章编 号:1006—8961(2002)07—0663—04 APoint?-by—-PointGeneratingAlgorithm forParametricPolynomialSurface HUANGYou—du.ZHUGong—qin (Dept.ofMathematics&InformationScience.HeiUniversityofTechnology,Hei230009 AbstractIncomputerdrawing,generally,curvesarerepresentedbylinesegmentsandsurfacesaretessellatedup withsmallplanepatches.Todrawgenuinecurveandreducecomputationalcostsasmuchaspossible,curve— generatingpoint—by—pointhasbeenstudiedinmanypapers.somegoodresultshavebeenachieved.Butthereis lackofeffectiveapproachesforfastsurface—generating.Ifwesupposethatsu rfacesconsistofpointsofspacelattice andthecoordinatesofpointsonasurfacecouldbecalculatedonebyone,thenwewouldobtainthesurface.There arealreadysomealgorithmsforcalculatingpolynomialcurvesonaplane,wec angeneralizedthemtospacecurves andsurfaces.Thispaperpresentsanalgorithmbasedonrecursiveformulasandalgorithmsforpolynomialto by—point.inwhicho generateaparametricpolynomialsurfacepatchpoint— nlyintegraladditiveoperationis employed,andproperlychoosingpointnumberminimizesthecomputationalCOSTS,SOitisquiteefficient.The methodinthealgorithmcanbemodifiedforrationalfunction,thereforeitisofsignificanceinfastgenerating parametricrationa1curveandsurface(suchasNURBScurveandsurface),aswel1asinmanyotherareasof ComputerGraphics. KeywordsParametricpolynomialsurface,Fastgeneratingpoint—by—poin t,Integraladditiveoperation,Bernstein bases 0引言 曲线的逐点生成算法已有较多的研究引,但 有关曲面逐点生成算法的研究尚未见到,许多绘图 基金项目:国家自然科学基金(19671002) 收稿日期:2001—05—08;改回日期:2001—09—28 软件所绘曲面皆为小平面拼接而成,无论是 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 几 何体的表面(球面,锥面等)还是Bezier曲面都是如 此M.本文给出了空间参数多项式曲面片的逐点生 成算法,计算中只用到整数加法,因此计算量很小. 实验证明,那些广泛应用的Bezier曲面片和Coons 664中国图象图形第7卷(A版) 曲面片等都可用它来生成. 与平面上曲线逐点生成算法所采用的方法类 似,这里也假设曲面是由空间三维点阵中的点组成, 且每一坐标面上点阵的规模与像素一致.用该方法 逐点求出曲面上每一点的坐标,即得到整个曲面片. 本文方法的主要思想是把曲面片看作由曲线拼 成,通过逐条生成曲线,即得到曲面.由于构成多项 式曲面片的曲线是多项式曲线,因此可用文献E53的 方法来生成. 1多项式曲线的逐点生成算法简述 设曲线的参数多项式方程为—(t), = (,),O,1,为计算方便,且不影响精度,可设 其系数为有理数,那/z,依次求出,一?(on)的 +1个整数坐标点,即构成曲线.为使曲线连续, 不能小于maxI(,)I和maxI(,)I.但由于越Of1Of1 大,计算量也越大,因此,选取 :max{maxI(,)l,maxl(,)I),可使计算量达Of1’Of1’ 到极小. 由于像素坐标必须为整数,因此由—(,) 化为如下的整数方程 Nx,一()+2,(1) 所确定,其中,常数?为一个正整数,,和z,为由i 决定的整数,且『,()为的整系数多项式. 设式(1)中各数已确定,把z—z…一, ()一+1)一A)代入式(1),整理得 Nx+l一(+1)一?()+2,+?? 由此式可按下面各种情况确定z…和…: ?若一?()+2一N ,则,一1(即 件1一,+1),2,+1一一A)+2,+?; ?若一?()+Zi>N ,则,一一1(即 z+l—z一1),2,+1一一A)+2—N; ?若一<一?()+zl,则::=o(即 …一,),2…一一A)+2,. 由选取的和2,(max『(t)『, 一 <z,N) ,可保证一<一?()+z,, 从而一<…N. 用上述方法可逐次得到z,i一1,2,…,n,所用 到的差分?(,)可由下面公式得出 A()一A(一1)+A(一1) 由于h次多项式的h阶差分恒为常数,因此在求出 i=0时的各阶差分后,以后的各阶差分都可根据上 式用一次加法得到. 2参数多项式曲面片的逐点算法 设曲面片的参数方程为:P—P(r,S),0r, 51,即z—(r,S),=(r,5),2—2(r,S),其中 x(r,5),y(r,5),z(r,5)为r,S的二元多项式,并设其 系数为有理数.取r一音,5一,o<i,n,则 ()一f,1一丛(2)\,,,,j』 其中,f(i,)是i,的整系数多项式,?是一个正整 数.当 . 至{}},}Osc})时,由式(2)易证明, 当i或增加1时,增量的绝对值不大于1,f(i,) 增量的绝对值不大于?.由于z取整数值,且曲面 与曲线的逐点计算类似,因此可把式(2)改写为 Nx一f(,)+e(3) 其中,”,和ei,j为整数,且,『.对一0,依次取 i一0,1,…,,可按文献E53中多项式曲线逐点算法 由式(3)求得各n.和e?,对每个固定的”.和e, 再依次取一0,1,…,,即可求得各和e. 对和z也可作同样的处理.这样所得各点 P一(z,?Zi,j),i,:0,…,,2,即组成所求的曲 面片.为保证曲面的连续性,应取为,z关于r, S的偏导数的绝对值的共同上界. 由于许多绘图软件(如OpenGL)具有深度检测 功能,可自行解决消隐问题,因此本算法中不再对消 隐问题加以考虑. 3逐点计算时,点数咒的确定 由上节算法的推导知,参数r,S方向上的点数 应满足 > o maX {{{,{{,{{,{{,{考{,{{} 因此应求出,,z关于r,S的偏导数绝对值的上 界.下面分几种情况讨论: (1)m次三角形I3~zier曲面片计算公式为 第7期黄有度等:一种参数多项式曲面片的逐点生成算法 P=??PBz(r,)0r,s,r+1(4) 其ee,P为控制点,(,.,S)为二元Bernstein基函 数 f__差rtsI(卜r—s)…一,o,,i+jGm既()一 l而u…’ 【0其他 (5) BZ,(,.,5)满足 一 … [-Bm--1)一所]1 一 … FB,71一孵]) 这样即可得 m--1--1-- (P+一P)Bz1(rl 警=萎妻ccr,)j 由于?B7()三1,所以 aP ‘ X{l) (8) ? X{l一P.jI) 若以上两式右端的P分别换为,Y,z,则可求得6 个值,而不小于该6个值的整数,即可作为的值. (2)四边形B~zier曲面片可由如下一代数多项 式表示 P—P(,.,5),O,.,51 设P(,一,5)对,一是m次多项式,对5是h次多项式, 则四边形B~zier曲面片方程可表示为 P一??PB…(,一)B(5)(9) 其中,B…(,.)和B?()为Bernstein基函数;四边形 B6zier曲面也可表示为 h P一??,一(1o)i:O,一O 由B:.()一kEB,一1.一1()一B?一1()]和 ?B?()三1,易得 aP 一max{.厂) (12) }aPj?x{IP+一PI) 同样,如以上两式右端的P分别换为,Y,z,则可求得 6个值,而不小于该6个值的整数,即可作为的值. 4曲面绘制实例 两个三次三角形B~zier曲面片P,Q的各控制 点分别为P和q?(,J,矗三三=0,i++矗一3),各控制 点坐标数据如下(为使两曲面光滑连接,P附近的控 制点q需适当选取,以使两曲面相邻的控制三角形 构成平行四边形): P?一(18O,2O,150), P210一(100,60,100),P20】一(200,18O,380), P120一(1OO,12O,160),P1】1一(16O,140,400), P】02一(300,12O,1O0), P030一(40,200,60),P021一(200,200,360), P012一(1O0,220,60),PD03一(300,200,300); qsoo==:Poo3? q210一po12,q201一户012+Poos--Plo2, q120=P021,q1】1一P021+P012一P?1, q102一(240,200,200), q030=P030,qo21一P03O+P02】一Pl20, q0】2一(50,300,220),q003一(180,360,140). 图1为用VC一4.2编制的本文算法程序所生 成的曲面(已用简单的光照模型进行了处理),曲面 由P,Q两曲面片光滑拼接而成,P在上,Q在下.左 边的是曲面在Xy坐标面上的投影,右边的是曲面 在yZ坐标面上的投影. 薹恫5结论通过下式(见文献[5]或文献[7])转化为式(9)J=口 C:C; 0c,ol ji OO … C: … =i jj 0coo 1 C2 1 1 C: B0. () B1.() .() 本文给出了参数多项式曲面的逐点生成算法, 此算法可逐点计算曲面上点的空间坐标,由于只用 到整数加法,故计算速度很快.曲面生成中的消隐问 题可通过适当选取节点的排列方向或利用深度缓冲 区(Z缓冲区)来解决.本算法还可在如下几方面进 行改进或推广: 中国图象图形第7卷(A版) 图1用本文算法生成的曲面 (1)有理曲线,曲面的逐点生成算法; (2)研究曲面光照模型的逐点生成计算等.由于 光照模型中,涉及的三角函数可由有理函数表示,故 以上两个问题实为同一个问题,即均为有理函数的 逐点计算问题.另外,有理函数比多项式复杂得多, 这将在其他文章中进行讨论; (3)用离散值i/.来代替连续变量t时,的取 值取决于曲线(面)函数导数绝对值的最大值,但在 导数绝对值较小处,算出的点可能重叠,将造成计算 量的浪费,但若分段选取或固定而使迭代步长 可变,则又使算法大大复杂化,这些方法未必可取. 因此如何进一步节省计算量也是值得深入探讨的 问题. 参考文献 1BresenhamJE.Algorithmsforcomputercontrolofadigital plotter[J].IBMSystemsJournal,1965,4(1):25,33. 2BresenhamJE.Alinearalgorithmforincrementaldigitaldisplay ofcirculararcsEJ].CommunicationsoftheACM,1977,2O(2): 1OO,1O6. 3HuynhNP,NatlawitD.EfficientalgorithmforBeziercurres [J].ComputerAidedGeometricDesign,2000,17(3): 247,250. 4刘勇奎,石教英.曲线的整数型生成算法EJ].计算机,1998, 21(3):27O,280. 5黄有度,朱功勤.参数多项式曲线的快速逐点生成算法EJ].计算 机,2000,23(4):393,397. 6贾志刚.精通OpenGL~M].北京:电子工业出版社,1998. 7施法中.计算机辅助几何设计与非均匀有理B样条 (cAGD~.NURBS)[M].北京:北京航空航天大学出版社,1994. 黄有度1949年生,硕士,现为合肥工 业大学数学与信息科学系教授.研究方向 为计算数学和计算机图形学. 朱功勤1938年生,现为合肥工业大 学数学与信息科学系教授兼中国科技大学 数学系博士生导师.研究方向为计算数学.