全 文 ：　　文章编号:1004-6011(2008)01-0055-03
基于分形的三维枫树建模算法
厉　鹏
(辽东学院 信息技术学院 , 辽宁　118003)
摘　要:植物的自然形态结构虽然复杂多变 ,但都具有统计意义上的自相似性 ,其每一部分都相似
于整体.根据植物形态学原理和计算机图形学技术 ,采用分形技术绘制出枫树的主干枝;由于末端
枝条柔软相对弯曲 ,采用参数曲线拟合技术绘制;在环境和自身重力的影响下 ,自然的树干普遍存
在不同程度的弯曲.可采用分段技术绘制每段枝干 ,并通过弯曲系数调整树干的弯曲程度 ,最后根
据计算机试验结果给出枫树的 IFS码.
关键词:参数曲线拟合;迭代函数系统(IFS);分形;吸引子
中图分类号:TP311 文献标志码:A
3D Maple Tree Reconstruction Method Based on Fractal
Li Peng
(Informat ion Technology College , Eastern Liaoning University ,Dandong , Liaoning 118003)
Abstract:Plants are the important part in the sense of reality of the nature and the structure of them is
complexity , but most of them have the characteristic of self-similarity .This paper presented a new
method of drawing 3D maple t ree , adopted f ractal technology to prot ract f ixed and jiggled branches ,
and used parameter curve protract w aved branches.To make the shape look more naturally , each
branch wi th segments and a parameter to control the curve of branch are created.According to the
results of experiments , the codes of IFS (Iterated Function System)of maple are presented.
Key words:parameter curve;Iterated Function System (IFS);f ractal;at t racto r
　　收稿日期:2007-12-16
作者简介:厉　鹏(1976—),男,讲师 ,硕士研究生 ,研究方向:信息技术.
　　随着虚拟现实理论和技术的不断发展 ,对三维
场景显示的真实性和实时性要求越来越高.模拟植
物枝条的自然弯曲是再现植物形体的重要内容 ,也
是虚拟场景中绘制的难点.常用的建模方法主要
有:分形(fractal)方法 、L 系统和随机过程.目前主
要有两类生成弯曲枝条的方法:设定枝条各片段弯
曲角度和参数曲线拟合方法[ 1 ,2] .本文研究在
OpenGL 环境下以枫树为例实现弯曲枝条的绘制 ,
通过改进参数曲线拟合方法提高绘制速度.
1　原理及方法
定义 1 　变换 W :R 3 ※ R 3 具有形式为
W
x
y
z
=
a b c
d e f
g h k
x
y
z
+
u
v
r
.
其中 , a , b , c , d , e , f , g , h , k , u , v , r 为实数 ,称 W
为一个三维仿射变换.当 X ∈ R3 时 , 上式可写为
W(X)=AX +t ,其中 A =
a b c
d e f
g h k
, t =
u
v
r
.
t 为平移变换.
A 是 下面 四 种 仿 射变 换 的 复合 , 其 中
sx n 0 0
0 syn 0
0 0 szn
是控制叶片大小的缩放变换 ,
第 24 卷 第 1期
2008年 3月
北 京 建 筑 工 程 学 院 学 报
Journal o f Beijing University of Civil Engineering and A rchitecture
Vol.24 No.1
Mar.2007
1 0 0
0 cosγn -sinγn
0 sinγn cosγn
、
cosαn 0 sinαn
0 1 0
-sinαn 0 cosαn
和
cosβn -sinβn 0
sinβn cosβn 0
0 0 1
是分别控制枝干绕 X 轴 、Y
轴和Z 轴的旋转变换.
定理 1　设仿射变换 W :R 3 ※R3 形如 W(X)
=AX +t ,当且仅当谱半径 rσ(A)<1 时 ,变换 W
是压缩的.
其中谱半径 rσ(A)= supλ∈σ(A) λ ,式中 λ为矩阵
A 的特征值.
定理 2　一个迭代函数系统由一个完备度量空
间(X , d)和一个有限压缩映射集 Wn :X ※X ,
n=1 ,2 , … , N组成 ,用 IFS{X ;Wn , n=1 , 2 , …, N}
表示.则变换 W 定义为:W(B)= ∪N
n =1 W n(B) B
∈X(X)是完备空间(X(X), h(d))上具有压缩因
子 s 的压缩映射 ,即 h(W(A), W(B))≤sh(A ,
B), A , B ∈X(X),且 P =lim
n※∞Wn(B), P ∈X(X)
被称为 IFS (Iterated Function System)的吸引子 ,该
吸引子就是一个分形[ 3] .
定理 3　设(X , d)是度量空间 ,又设{W n , n =
1 ,2 , … , N}是(H(X), h(d))上的一族压缩映射 ,
相应于 Wn 的压缩比为sn ,由下式定义 W :H(X)※
H(X)W(B)=W 1(B)∪ W 2(B)…∪ Wn = ∪n
i=1 Wi
(B), B ∈ H(X)则 W 是具备压缩比为 s =max
{s1 , s2 , …, sn}的压缩映射.
2　算法实现
2.1　分形方法绘制树干
枫树的分枝模式属于合轴分枝模式.合轴分枝
树木的顶芽发育到一定时候死亡 ,由其下若干个侧
芽取而代之 ,形成强的侧枝接在主轴上 ,没有明显的
主干 ,形成了多个弯曲的主轴 ,整个树冠呈开张状.
枫树的固定枝干一般分 2到 4叉 ,分叉的角度一般
在45°左右.根据枫树树干的形态特点 ,以及定义 1 、
定理 1和定理 2给出枫树树干迭代函数系统由 3个
仿射变换构成 , IFS码如表 1.
由表 1给出的数据在 OpenG L环境下可以绘制
出枫树的树干 ,如图 1.
表 1　枫树的 IFS 码
n sx sy sz α β γ u v r
1 0.62 0.62 0.62 45 0 0 0 1.0 0
2 0.62 0.62 0.62 45 120 0 0 1.0 0
3 0.62 0.62 0.62 45 240 0 0 1.0 0
图 1　无弯曲枫树树干
2.2　调整树干弯曲算法
观查图 1 ,生成树干的方法中整个树体形态较
自然树体形态“笔直” ,不能体现自然树干的随机弯
曲.改进树干的画法采用分段画出 ,段与段间可以
加入随机弯曲系数[ 3 ,4] ,形成自然形态树干.考虑到
主干的弯曲程度不及侧枝弯曲程度的特点 ,对主干
和侧枝采用不同数目的分段和不同大小的弯曲系
数 ,来更好的表现树干的自然形态 ,分段后树干生成
的树形如图 2.
图 2　弯曲枫树树干
2.3　弯曲枝条的绘制
Prusinkiew icz和Weber 给出了不同的算法来绘
制弯曲的枝条.Prusinkiewicz[ 5]是分别给出所有枝
条的弯曲系数 ,即组成各枝条片段的初始方向矢量
及整个枝条的趋向性矢量 ,然后通过计算这两个矢
量的乘积得到每个片段的最终方向矢量 ,这样就得
到了弯曲的枝条.Weber[ 1]对植物的每个枝条设定
两个偏转角度 ,枝条的前半部和后半部分别以不同
的偏转角度向下和向上偏转 ,模拟出 S 型枝条形
状.虽然这两种方法都可以绘制出形象逼真的枝
条 ,但计算量很大 ,影响绘制速度.
56 北 京 建 筑 工 程 学 院 学 报 2008 年
2.3.1　二次曲线的一般参数方程
一般二次曲线的参数向量方程为:
Q(t)= at 2+bt+c
1+e1 t+e2 t 2 , t ∈[ 0 ,1] (1)
其中 , a , b , c 为常数向量 , e1 , e2 为常数.其所对应
的代数方程为:
x(t)=ax t
2+bxt +cx
1+e1 t+e2 t 2
y(t)=ayt 2+byt+cy
1+e1 t+e2 t 2
, t ∈[ 0 ,1] (2)
这里 ax , bx , cx , ay , by , cy 为参数方程的系数 ,
通常可以利用这种形式的参数方程来描述抛物线 、
双曲线 、椭圆等二次曲线.
给定 3个控制点 p0 , p1 , p2 并规定曲线的边界
条件:
当 t=0时 ,曲线过 p0 点 ,且切于p 0p1;
当 t=1时 ,曲线过 p2 点 ,且切于p 1p2.
将边界条件带入(2)式可以得出 ax , bx , cx , ay ,
by , cy 的值.因此只要给定 p0 , p1 , p2 3点的坐标就
可以确定曲线的位置 ,再给定 e1 , e2 便可确定曲线
的形状.
2.3.2　绘制弯曲的枫树枝条
当 e1=e2=0时 , Q(t)=at 2+bt +c , t ∈[ 0 ,
t]所对应的代数方程为
x(t)=ax t 2+bxt+cx
y(t)=ayt 2+byt+cy , t ∈[ 0 , t] (3)
给定 3个控制点 p0(x 0 , y 0), p1(x 1 , y 1), p2
(x 2 , y 2)则由其决定的抛物线参数方程的系数为:
cx=x 0
cy=y 0
bx=2(x 1-x0)
by =2(y 1-y 0)
ax =x 2-2 x 1+x 0
ay=y 2-2y 1+y 0
将(3)式离散化方程为:
x i=ax t 2i +bxt i+cx
y i=ayt 2i+by t i+cy (4)
其中 , t i=i＊dt , i=1 ,2 , …, N , N 是离散化后
所取点的个数 , dt 为相应的步长 ,求得相应的 x i ,
y i ,连接后拟合出相应的抛物线.随着枝条的增多
计算量也随之增加.根据观察可发现枫树枝条的弯
曲形状大体相似 ,这样可以用同一个拟合曲线 ,通过
改变枝条和枝干的夹角完成不同枝条的绘制.虽然
不能再现枫树真实的生长过程 ,但可以通过简单的
计算模拟出较为逼真的枫树实体 ,如图 3.
图 3　枫树
3　收敛性证明
度量空间(X , d)上的变换 f :X ※X 称作压缩
或压缩映射 ,如果存在一个常数 0≤s<1 ,使得:
d(f(x), f(y))≤sd(x , y), x , y ∈X
数 s称为压缩因子.由压缩映射定理 ,当映射
f 为压缩时 ,序列{f n(x):n=0 , 1 , 2 , …}收敛到其
不动点 x f ,即:
lim f n(x)=x f , x ∈ X ,
令 x 0 为一个初始向量 ,把迭代运用到定义1中
的 W(X)=AX +t ,则其第 k 次迭代为:
xk=W k(x0)=Akx0+ ∑k-1
i=0
A i t ,
当且仅当矩阵 A 的谱半径 rσ(A)<1时 ,有
limAk=0 ,
lim ∑k-1
i=0
A i=(I -A)-1 ,
故序列{x k}收敛到变换 W 的不动点
xf =(I -A)-1 t.
由定理 1可知 ,当且仅当谱半径 rσ(A)<1时 ,
变换 W 是压缩的 ,其中谱半径 rσ(A)= supλ∈σ(A) λ ,
式中 λ为矩阵 A 的特征值.
矩阵 A 的特征方程为:(A -λE)x =0它有非
零解的充分必要条件是系数行列式 ,即特征多项式
A-λE =0.
根据表 1的仿射变换可以求出矩阵 A 中的各
分量代入特征多项式 ,即
a-λ b c
d e-λ f
g h i-λ
=0.
解得 rσ(A1)=max{0.53 , 0.46 , 0.53}=0.76<
　　 (下转第 68页)
57　第 1 期 厉　鹏:基于分形的三维枫树建模算法
重要的.应加大技术标的评审比例.综合评定法要
有公开 、量化的标准来打分.把好评标的关 ,真正做
到评标方法合理 ,评标规则完善 ,才能维护招标人与
投标人的合法权益.
3　完善我国建设工程项目招标投标活
动的一些建议
　　首先 ,要加强对工程项目招标投标的前期准备
的审查.充分的前期准备无论对招标方还是投标方
都有很大好处 ,对招标方前期准备工作的审查可以
由专门的政府主管部门负责.
其次 ,加速工程项目招标投标代理机构和咨询
公司的发展 ,使之真正市场化.由招标代理机构承
担大量的工程招标业务 ,同时加强招标代理机构的
管理 、培训工作.招标代理机构工作水平的提高和
规范 ,对整个建筑市场招投标工作的规范将起到事
半功倍的效果.
第三 ,改变我国目前使用的定额制 ,加强企业定
额的编制.如果能改变现有的定额制 ,在经济表编
制时就可直接使用当时的实际单价或者企业可以获
得的单价.这不仅减少遗漏 ,还拉开了各企业间工
程造价的差距 ,有利于优质企业低价中标 ,更有利于
各投标企业在竞争中发展.
第四 ,增加评标过程的保密性 ,适当延长评标时
间.评标时间过短 ,导致评标只是一个走过场 ,不能
保证评标的质量.根据实际情况 ,适当延长评标时
间 ,可使业主能够选到满意的承包商.
最后 ,积极推广对招标投标的公证.公证部门
的参与 ,应当是实质性的参与 ,而不是形式上的参
与.公证机关必须对招标投标全部文件和资料进行
审核 、查证 ,保证招标投标双方当事人具有合法和符
合招标文件要求的招投标资格 ,保证招投标活动有
关文件的真实合法.公证机关必须对招投标活动进
行监督 ,保证每个环节及整个招投标活动的真实 、合
法.公证机关必须对出具公证书负责 ,对整个招投
标活动的真实性 、合法性予以确认 ,赋予其法律效
力.积极推广对招标投标活动的公证 ,对于规范招
投标行为 ,完善招投标机制 ,杜绝招投标活动中的违
法行为具有十分重要的意义.
参考文献:
[ 1] 　王平 , 李克坚.招投标·合同管理·索赔[ M] .北京:中
国电力出版社 , 2006
[ 2] 　中华人民共和国招标投标法
[ 3] 　王平 , 高永歌.招投标立法中出现的问题与对策探讨
[ J] .北京建筑工程学院学报 , 2005 , 21(4):75-77
[ 4] 　新疆建工集团公司(安装工程公司 、第六建筑工程工程
工程公司 、建筑总公司);建筑科学研究院;北京公路工
程公司等 21 家建筑企业调查问卷
[ 5] 　王平 , 李克坚.工程建设项目招标存在问题的对策探
讨[ J] .北京建筑工程学院学报 , 2007 , 23(2):78-80
[责任编辑:佟启巾]
(上接第 57页)
1 ,则变换 W 1是压缩的 ,依次可以验证 W 2 , W3 也
是压缩的 ,根据定理 3可知 W 是压缩的 ,则构造的
这个 IFS 的吸引子就是要得到的三维分形枫树.
4　结论
以枫树为例设计并绘制带有弯曲枝条的树种 ,
通过调整枝条和枝干之间的夹角 ,用同一个拟合曲
线绘制不同的枝条 ,减少了计算量 ,提高了枫树实体
生成的速度 ,在虚拟场景的实现中具有一定的应用
价值.根据定义1和定理 1求谱半径计算后可得枫树
的3个仿射变换矩阵的谱半径均满足 rσ(A)<1 ,所以
该 IFS存在吸引子 ,即迭代结果必然是一个紧集.
参考文献:
[ 1] 　Weber J , Penn J.Creation and rendering o f realistic trees
[ R] .In Proceeding s of SIGGRAPH 1995.Los Angeles ,
1995.New York:ACM Press , 1995:119-128
[ 2] 　Boudon F , Prusinkiewicz P , FEDERL P , et al.Interac-
tive design of bonsai tree models[ J] .Computer G raphic
Forum , 2003 , 22(3):591-600
[ 3] 　Deussen O , Lintermann B.A modeling method and user
interface for creating plants[ J] .Computer G raphic Fo-
rum , 1998 , 17(1):73-82
[ 4] 　Lintermann B , Deussen O.I nteractive modeling of plants
[ J] .IEEE Comput.Graph.Appl , 1999 , 19(1):56-65
[ 5] 　Prusinkiewicz P , Lindenmayer A.The algorithmic beau-
ty of plants[ M] .New York:Springer-Verlag , 1990
[责任编辑:佟启巾]
68 北 京 建 筑 工 程 学 院 学 报 2008 年