基于分形递归算法的树木真实感绘制

1、-888-0引言快速真实地模拟树在风中的摇曳一直是计算机图形学中的一个挑战性问题。作为自然场景的重要组成部分,树木的真实感模拟也得到人们的广泛重视。树木种类繁多,形态各异,复杂的结构使其无论在造形、存储还是在绘制上都存在着相当的困难。树在风中的运动是一个相当复杂的流固耦合问题,准确快速地计算树在风中的变形并不是一件容易的事情。迄今为止有关树的建模研究比较多,但关于树的动画的研究较少。吴恩华等人提出基于图像的方法,从真实照片中抽取树的骨架,并基于此重建树的三维模型,然后通过对主要枝干的变形采用非线性力学方程组积分的运算,对摇摆的枝条变形采用波动方程求解,以获得整棵树的变形。柳有权等人探讨了基于物

2、理的快速变形计算及真实感的成像。Sakagu-chi 采用数据场方式来表示树周围的风场并以此计算风力。Jones 等则采用L 系统构造树的模型,并基于数据场空间计算风的衰减,再根据过程变形模型算出树枝的变形1。本文主要讨论基于分形递归算法的三维真实树的生成方法,讨论采用过程函数来描述风场的方法。介绍分形树建模的一般方法,并引出一种三维树的建模方法;介绍利用函数参数控制树的变形,从而实现树木运动姿态的快速真实感成像。1树的建模递归是指一个过程直接或间接地调用其自身的一种算法。实质上,递归是利用计算机中压栈和出栈的功能,重复地运用某些规则来生成嵌套的结构。分形的自我相似、自我复制和自我嵌套,让人很

3、自然地想到可以利用递归算法来生成分形图。分形递归算法是一种分形图形的生成方法,其主要原理就是设定基本的图形生成元,然后让计算机按照基本生成员的绘制规则反复在每一个层次上重画,直到达到预先设置的开关条件为止,就可以生成各种各样的图形。1.1树的基本建模方法图1是一种简单的二维分叉树的生成元,设A 点坐标为(,B 点坐标为(,C 点坐标为(1,D 点坐标为(2,为枝干与主干的夹角。按此生成元绘制分形树的步骤如下:绘制主干AB ,即 ,=21 =,+收稿日期:2006-01-12E-mail :blxxf作者简介:姚雪峰(1977-,男,黑龙江虎林人,研究生,研究方向为计算仿真技术;秦文虎(1969

4、-,男,江苏南京人,副教授,研究方向为控制、仿真与虚拟现实技术。基于分形递归算法的树木真实感绘制姚雪峰,秦文虎(东南大学仪器科学与工程系,江苏南京210018摘要:快速真实地模拟树在风中的摇曳一直是计算机图形学中的一个挑战性问题,作为自然场景的重要组成部分,树木的真实感模拟也得到人们的广泛重视。树木种类繁多,形态各异,复杂的结构使其无论在造形、存储还是在绘制上都存在着相当的困难。大多数园林设计软件很难构建模型参数可变的三维树。研究了一种简易的基于分形递归算法的建模方法,利用过程参数控制树的摇曳,使模型的真实感更强,变形计算更容易,得到了令人满意的实验效果。关键词:真实感;树;分形;递归算法;过

5、程参数;计算机图形学中图法分类号:TP391文献标识码:A 文章编号:1000-7024(200704-0888-02Realistic rendering of trees based on fractal recursion algorithmYAO Xue-feng,QING Wen-hu(Department of Instrument Science and technology,Southeast University,Nanjing 210018,China Abstract :Fast and realistically simulating the tree swaying

6、in wind is still a challenge topic in computer graphics.As a very important part of natural scenery,realistic rendering of trees has attracted much attention.Trees have various types with different shapes and due to their complex structures ,realistic modelings ,rendering and storage of trees are al

7、ways a tedious task.Constructing a 3D tree model which owns alterable parameters is difficult for most of garden design software.A simple generation method based on fractal recursion algorithm is researched.Having utilized process parameters to control the sway of tree ,the model of tree was more re

8、alistic and de-formation computation is more easier.Experimental results are satisfactory.Key words :realistic;tree;fractal;recursion algorithm;process parameters;computer graphics2007年2月计算机工程与设计Feb.2007第28卷第4期Vol.28No.4Computer Engineering and Design-889 -;计算D 点坐标,/3,0+,0+;将步骤中>,>1,再绘制 ,0,>

9、;2,再绘制 ,£¬Ö÷¸ÉÓëY 轴的夹角为。在空间直角坐标系中解算在(,1=/×cos 1=/ ;+2× cos ;= / ;= /11+2×cos ;= / ;= /11+2×cos + ;= / 1/cos11+2× sin11+2× cos 1/cos 11+2× cosatan ;=/11+2× cos atan ;点(2,½ÇµÄ±ä»¯

10、80;Ó¶ø¿ØÖÆÒ¡Ò··ù¶È±ä»¯£¬´Ó¶øÄ£ÄâÊ÷µÄÒ¡Ò·£¬È¡µÃÁ˽ϺÃ

11、81;ÄЧ¹û¡£Í¼3描述了单帧图像的绘制过程。风力模拟算法:drawLeaf (float x,float y,float z,float L,float ,float 1=/×cosµÄÖµÓÉÍⲿʱ ÖÓº¯ÊýÌṩ¡£+2× s

12、in1=/× sinX Y11、111111、111YX(注意:符号L 、R 、F 、B 分别代表相对观察者左、右、前、后各点。 22,1,1-892-索父块的空间分别为(2568+1和(25616+1。表1是灰度排列分类法编码方案的实验结果。图2是原始标准图像和经4×4和8×8分块压缩编码后的解码图像。5结束语本文所采用的算法是将图像分割为标准方块大小,使用灰度排列分类法的编码方案,从而有效地减少了父块搜索空间,缩短了编码时间。但是该算法在分割时未考虑图像的本身特性。在今后的工作中可尝试采用自适应的分割方法,例如将图像划分为不等大小的矩形或三角形,也可将图像先分

13、割成固定大小的块,然后再根据图像的特性将块合并为不规则的多边形。另外在搜索算法中也可加入一些辅助的智能搜索算法79。参考文献:1曾文曲,文有为,孙炜.分形小波与图像压缩M .沈阳:东北大学出版社,2002.2Erjun zhao,Dan Liu.Fractal image compression:A review C .US:Proceedings of the Third International Conference on Infor-mation Technology and Application,IEEE,2005.756-759.3Belloulata K,Konrad J.Fr

14、actal image compression with region-based functionality J .IEEE Transaction on Image Processing,2002,11(4:351-362.4Farhadi G.An enhanced fractal image compression based on quadtree partition C .US:Proceedings of the 3rd International Symposium on Image and Signal,IEEE,2003.213-218.5SK.Mitra C A,Murt

15、hy M K Kundu.Fractal image compression using iterated function system with probabilities C .US:Pro-ceedings of the International Conference on Information Tech-nology Coding and Computing,IEEE,2001.191-195.6Barnley M F.Fractal image compression M .US:AK Peters,1993.7Tong CS,Wong M.Adaptive approxima

16、te nearest neighbour sea-rch for fractal image compression J .IEEE Transactions on Ima-ge Processing,2002,11(6:605-615.8Zumbakis T,V alantina J.A new approach to improving fractal image compression times C .US:Proceedings of the 4th Interna-tional Image and Signal Processing and Analysis,IEEE,2005.4

17、68-473.9Aggarwal A,Kunal R.Partitioned fractal image compression for binary image using genetic algorithm C .US:Proceedings of Network,Sensing and Control,IEEE,2005.734-737.(上接第889页表14×4和8×8灰度排列分类法编码方案的实验结果块的大小 4×48×8父块的搜索范围主类1:8671主类2:20616主类3:32714主类1:7208主类2:20959主类3:29914编码时间

18、43'28''34'36''压缩比4:116:1PSNR32.9527.33图2原始标准图像和经44和88分块压缩编码后的解码图像××(a 原始标准Lenna 图像(b 44分块压缩的解码图像×(c 88分块压缩的解码图像×3结束语快速真实地模拟树在风中的摇曳一直是计算机图形学中的一个挑战性问题,树的建模方法很多,比如文法构图法、IFS 构图法等。本文提出并实现了一种简易的基于分形递归算法的三维真实树的生成方法,利用过程参数控制树的摇曳。如何更高效地处理复杂树模型的基于物理的快速变形计算,是值得进一步研究的课题。参考文献:1柳有权,王文成,吴恩华.快速真实地生成树的自然摇曳J .计算机学报,2005,7(28:2-3.2孙博文.分形算法与程序设计Visual C+实现M .北京:科学出版社,2004.3冯金辉.树在风中的摇曳基于物理的计算机动画D .北京:中国科学院软件研究所,1999.4陈彦云,严涛,张晓鹏,等.基于分类及环境特征的树木真实感绘制J .软件学报,2001,12(1:1-2.5李福清,王小铭.植物模拟建模的新策略J .华南师范大学学报(自