形体的表示及其数据结构.ppt
95页
第六章第六章 形体的表示及其数据结构形体的表示及其数据结构 与空间任意形体有关的信息可以分为与空间任意形体有关的信息可以分为图形信息图形信息和和非图形信息非图形信息两类图形信息指两类图形信息指构成它们的点、线、面的位置构成它们的点、线、面的位置, ,相互关系及相互关系及大小等大小等; ;非图形信息指形体的颜色、亮度、非图形信息指形体的颜色、亮度、质量、体积等一些性质质量、体积等一些性质 形体的图形信息又可以分为形体的图形信息又可以分为几何信息几何信息和和拓扑信息拓扑信息两类几何信息指形体在空间两类几何信息指形体在空间的位置和大小的位置和大小, ,拓扑信息指组成形体各部分拓扑信息指组成形体各部分的数目及相互间的连接关系的数目及相互间的连接关系 第一节第一节 二维形体的表示二维形体的表示 •二维图形的边界表示二维图形的边界表示 折线法和带树法折线法和带树法 折线法就是用多段线段形成的折线去折线法就是用多段线段形成的折线去逼近曲线逼近曲线 折线表示曲线应该解决的关键问题是折线表示曲线应该解决的关键问题是: :如何恰当地确定曲线上一系列点如何恰当地确定曲线上一系列点, ,使之在某使之在某些判定准则下达到最优。
些判定准则下达到最优 设已经用某种方法取得了曲线上足够设已经用某种方法取得了曲线上足够多的点多的点,使连接那些点的折线可以很好地表使连接那些点的折线可以很好地表达该曲线问题是达该曲线问题是:怎样在其中选择怎样在其中选择尽可能尽可能少少的点的点,使选出的点仍能较好地表达原曲线使选出的点仍能较好地表达原曲线具体地说具体地说,使选出的点满足以下二条准则使选出的点满足以下二条准则: (1)共线性共线性 设设Pj和和Pk是选出的两点是选出的两点,则在则在Pj到到Pk之间所有点到直线之间所有点到直线PjPk的垂直距离的垂直距离,应小于某个预先给定的限制阈值应小于某个预先给定的限制阈值ε0,这里这里ε0>0,是一个可以由应用问题需要而确定的是一个可以由应用问题需要而确定的很小的正数很小的正数若不小于若不小于ε0,应寻找距离为最应寻找距离为最大之点并考虑是否可以在该点将这一段大之点并考虑是否可以在该点将这一段分分裂裂为两段 (2)设选出的连续三点是设选出的连续三点是Pi,Pj,Pk,则向量则向量PiPj与与PjPk的夹角的夹角α的绝对值的绝对值,应大于某个应大于某个预先给定的限制阈值预先给定的限制阈值α0。
若小于若小于α0,则则Pj不应选取而应考虑是否能将不应选取而应考虑是否能将Pi至至Pj和和Pj至至Pk两段合并两段合并 设设有有曲曲线线上上n+1个个点点的的坐坐标标序序列列,各各点点依依次次编编号号为为0,1,2,…,n;为为使使删删去去各各点点距距留留下下前前后后二二点点所所形形成成直直线线的的距距离离不不很很大大而而预预先先给给定定的的阈阈值值ε0;为为使使选选出出连连续续三三点点所所成成向向量量夹夹角角不不很很小小而而预预先先给给定定的的阈阈值值α0;参参数数k0表表示示每每次次向向前前检检查查k0个点 1.〔〔初初始始化化〕〕 i←0,j←0,k←k0,输输出出点点编编号号0,s←1{i记记最最近近己己选选之之点点,初初始始起起点点0为为必必选选,j记记待待检检查查之之点点,算算法法中中保保持持i≤j,待待检检查查线线是是点点j到到k的的直线}2.〔〔共共线线性性检检查查〕〕检检查查点点j到到k间间各各点点共共线线性性若若不不能能通通过过,距距离离直直线线PjPk最最远远的的点点是是m,则则k←m返返回回本本步步开开头头否否则则继继续续{本本步步必必能能通通过过,因最坏在因最坏在k=j+1时能通过。
时能通过}3.〔〔暂暂定定j前前后后两两线线方方向向〕〕L2←点点j到到k的的方方向向,若若i=j则则L1←L2,到到6;否否则则继继续续{L2是是暂暂定定找找到到从从j向向后后的的新新线线方方向向,L1是是前前次次找找到到原原有有线线方方向向} 4.〔〔向向量量夹夹角角检检查查〕〕检检查查Pi,Pj,Pk三三点点形形成成二二向向量量L1和和L2的的夹夹角角的的绝绝对对值值,若若可可以以通通过过即即应应发发生生合合并并,做做j←i然然后后返返2,否否则则继继续续{本本步步检检查查通通过过即即点点j不不能能选选取取,而而要要检检查查原原i到到k的直线}5.〔〔找找到到一一个个选选取取点点〕〕i←j,L1←点点j到到k的的方方向向,输出点编号输出点编号j,s←s+16.〔〔准准备备下下次次〕〕j←k,k←k+k0,若若k>n则则k←n,若若j≤n-1则返则返2,否则继续否则继续 7.〔〔最后取点最后取点〕〕输出点编号输出点编号n,算法结束算法结束 P0P1P2P3P4P5P6i←0,j←0,k←k0 (3) PjPk即即P0P3,若通过；若通过；j ←k,k ←k+ k0 , PjPk即即P3P6 带树法带树法 带树是一棵二叉树带树是一棵二叉树,树的每个结点对树的每个结点对应一个矩形带段应一个矩形带段,这样每个结点可由八个这样每个结点可由八个字段组成字段组成,前六个字段描述矩形带段前六个字段描述矩形带段,后二后二个是指向两个子结点的指针个是指向两个子结点的指针, 即矩形带段即矩形带段的起点是的起点是(xb,yb),终点是终点是(xe,ye)。
相对从相对从起点到终点的连线起点到终点的连线,矩形有两边与之平行矩形有两边与之平行,两边与之垂直两边与之垂直,平行两边与之距离分别为平行两边与之距离分别为wl和和wr 设设要要表表示示的的曲曲线线是是由由经经过过适适当当选选取取已已确确定定的的一一组组离离散散点点P0,P1,…,Pn序序列列给给出出,则则生生成成表表示示曲曲线线的的分分辨辨率率为为w0的的带带树树的的算算法法,可可简略描述如下简略描述如下:1. 找找出出由由起起点点P0,终终点点Pn确确定定的的矩矩形形带带段段,其其中中包包含含P0至至Pn的的全全部部点点,构构造造此此矩矩形形带带段段的的对对应应结点并令为根结点并令为根2. 找找出出P0至至Pn之之间间距距离离连连线线P0Pn为为最最远远的的点点Pk,然然后后对对P0至至Pk和和Pk至至Pn这这两两组组点点分分别别做做与与步步1中中相相同同的的构构造造矩矩形形带带段段及及对对应应结结点点的的操操作作,产生的两个结点产生的两个结点,分别是根的左右子结点分别是根的左右子结点3. 反复执行上述操作反复执行上述操作,直到所产生结点的直到所产生结点的w=wl+wr ≤w0。
这样的结点是叶结点这样的结点是叶结点 BINARY *Create(float P,int i,int j，，float W)/* BINARY带树节点类型带树节点类型 P[i]至至P[j]描述折线表示的曲线描述折线表示的曲线 W为分辨率为分辨率 */{ Search(P,i,j-i+1,wl,wr); //确定确定P[i]至至P[j]所有点所形成的矩所有点所形成的矩 形带段的宽度形带段的宽度 root=new(BINARY); //获取带树节点获取带树节点 CBINARY(root,wl,wr,P,i,j); //构造根节点构造根节点 if (wl+wr<=W) return root; //返回带树根节点返回带树根节点 else { maxdis(P,i,j,k);//找出距找出距Pi与与Pj连线垂直距离最远的点连线垂直距离最远的点Pk t1= Create( P,i,k, W); //构造构造P[i]至至P[k]点间的带树点间的带树 t2= Create( P,k,j, W); //构造构造P[k]至至P[j]点间的带树点间的带树 Left(root,t1); //t1作为作为root左子树左子树 Right(root,t2); // t2作为作为root右子树右子树 return(root);// } } 设表示曲线有设表示曲线有5个点个点(3,7)(9,12),(15,4),(18,5),(20,7) ,取分辨率取分辨率w0=1,则上述算法构造的带树则上述算法构造的带树 以不同的分辨率显示用带树表示的曲线以不同的分辨率显示用带树表示的曲线 设给出允许的分辨率为设给出允许的分辨率为w*,表示曲线的带表示曲线的带树的分辨率为树的分辨率为w0,并设并设w0≤w*,则显示算法可则显示算法可简略描述如下简略描述如下: 从根结点开始从根结点开始,若当前正考查结点的若当前正考查结点的W=wl+wr ≤w*,则显示该结点对应的矩形带段则显示该结点对应的矩形带段;若不然若不然,即即W> w*则转去分别考查该结点的则转去分别考查该结点的左右两个子结点左右两个子结点,对子结点做同样的处理。
左对子结点做同样的处理左右子结点都被显示的结点就认为是被显示了右子结点都被显示的结点就认为是被显示了,按此看法按此看法,显示带树表示的曲线就是显示带树显示带树表示的曲线就是显示带树的结点 void void Display(BINARYDisplay(BINARY * *root,floatroot,float W,floatW,float W*) W*) /* BINARY /* BINARY带树节点类型带树节点类型rootroot带树根指针带树根指针 W W带树分辨率带树分辨率 W*W*显示分辨率显示分辨率 * */ /{ if (W>W*) { { if (W>W*) { printf(“error”);returnprintf(“error”);return; }; } else else if( if( Width(rootWidth(root)<=W* ) )<=W* ) { { DisplayLine(rootDisplayLine(root); ); // //Width(rootWidth(root) )为为wlwl与与wrwr之和函数之和函数 ////DisplayLine(rootDisplayLine(root) )显示带树为显示带树为两端点线段两端点线段 return;return; } } else { else { Display(rootDisplay(root->->left,W,Wleft,W,W*); //*); //显显示左子树示左子树 Display(rootDisplay(root->->right,W,Wright,W,W*); //*); //显示右子树显示右子树 return;return; } }} } 带树表示的曲线求交带树表示的曲线求交 两个矩形带段两个矩形带段S1和和S2的位置关系有如下三种的位置关系有如下三种:(1) 不相交。
不相交2) 良良性性相相交交,即即S1的的与与起起点点至至终终点点连连线线平平行行的的两两条条边边都都与与S2相相交交,S2的的与与起起点点至至终终点点连连线线平平行的两条边也都与行的两条边也都与S1相交3) 可能性相交可能性相交,这时不是良性相交这时不是良性相交,但也不是但也不是不相交 设设表表示示要要求求交交两两曲曲线线的的带带树树己己构构造造得得足足够够精精确确,即即在在树树叶叶一一层层,来来自自不不同同带带树树的的矩矩形形带带段段或或是是不不相相交交或或是是良良性性相相交交,而而没没有有可可能能性性相交出现相交出现 两两带带树树T1和和T2表表示示的的两两条条曲曲线线是是否否相相交交的算法的算法,可以简略叙述如下可以简略叙述如下: 若若T1和和T2对对应应的的矩矩形形带带段段互互不不相相交交,那那么么它们代表的曲线不相交它们代表的曲线不相交; 若若T1和和T2对应的矩形带段良性相交对应的矩形带段良性相交,那么那么它们代表的曲线相交它们代表的曲线相交; 若若T1和和T2对应的矩形带段可能性相交对应的矩形带段可能性相交,且且T1的面积大于或等的面积大于或等T2的面积的面积,那么分别执行那么分别执行T2与与T1的左右两个儿子结点的相交性检查。
的左右两个儿子结点的相交性检查 若若T1的面积小于的面积小于T2的面积的面积,则把它们则把它们位置对换一下再如上进行两个检查若两位置对换一下再如上进行两个检查若两个检查的结果都是不相交个检查的结果都是不相交,则认为所表示曲则认为所表示曲线不相交线不相交;若两个检查中有一个是良性相交若两个检查中有一个是良性相交,则认为所表示曲线相交则认为所表示曲线相交;若不是上述两情形若不是上述两情形,即出现可能性相交即出现可能性相交,则对可能性相交的两个则对可能性相交的两个矩形带段中面积较大者矩形带段中面积较大者,取其对应结点的两取其对应结点的两个子结点个子结点,如此进行可直到树叶那一层如此进行可直到树叶那一层 实践表明用带树方法表示曲线对提高实践表明用带树方法表示曲线对提高计算效率是有帮助的另外两个带树对计算效率是有帮助的另外两个带树对并、并、交等运算是封闭的交等运算是封闭的,与用象素阵列来表示图与用象素阵列来表示图形的方法比较空间需求也算是节省的形的方法比较空间需求也算是节省的 •平面图形的四叉树表示方法平面图形的四叉树表示方法 假定一个平面图形是假定一个平面图形是黑白黑白的二值图形的二值图形,即组成图形象素阵列的仅有黑色象素值即组成图形象素阵列的仅有黑色象素值1,白白色象素值色象素值0,设表现图形的象素阵列由设表现图形的象素阵列由2n×2n个个象素组成。
象素组成 表示该图形的四叉树结构可以如下形成表示该图形的四叉树结构可以如下形成:图形显然包括图形显然包括2n×2n的正方形中，这个正方形的正方形中，这个正方形是四叉树的根结点是四叉树的根结点 若图形整个地占据这个正方形若图形整个地占据这个正方形,则图形就则图形就用该正方形表示用该正方形表示,否则将该正方形均分为四个否则将该正方形均分为四个小正方形，每个小正方形边长为原正方形边小正方形，每个小正方形边长为原正方形边长的一半长的一半.它们是根结点的四个子结点它们是根结点的四个子结点,可编可编号为号为0,1,2,3 再考查每个小正方形再考查每个小正方形,若整个被图若整个被图形占据形占据,则标记相应结点为则标记相应结点为1,可称为可称为黑结黑结点点若整个与图形不相交若整个与图形不相交,则标记相应则标记相应结点为结点为0，可称为，可称为白结点白结点 若不是上述两情形，即与图形部分若不是上述两情形，即与图形部分相交，则称相应结点是相交，则称相应结点是灰结点灰结点并将其一并将其一分为四当再分生成小正方形边长达到分为四。
当再分生成小正方形边长达到一个一个象素单位象素单位时，再分终止，此时一般时，再分终止，此时一般应将仍是灰结点的改为黑结点，如此形应将仍是灰结点的改为黑结点，如此形成了平面图形的四叉树表示成了平面图形的四叉树表示 TREE * tree_4(Box b,Graph g)// b为正方形为正方形 g为二维形体为二维形体 TREE为四叉树结为四叉树结点类型点类型{ if (g包含包含b) { 构造树根结点构造树根结点root（属性为黑）（属性为黑）;return(root)；；} else if (b与与g之交集为空之交集为空) {return null；；} else { b分成分成b0,b1,b2,b3四个相同小正方形四个相同小正方形; 构造树根结点构造树根结点root（属性为灰）；（属性为灰）； r1=tree_4(b0,g); r2=tree_4(b1,g); r3=tree_4(b2,g); r4=tree_4(b3,g); r1,r2,r3,r4链接为链接为root结点的四个子结结点的四个子结点；点； return(root); }} 四叉树的存储结构，即四叉树的存储结构，即规则方式、线规则方式、线性方式和一对四方式性方式和一对四方式，相应的四叉树也就，相应的四叉树也就称为规则四叉树、线性四叉树和一对四式称为规则四叉树、线性四叉树和一对四式四叉树。
四叉树 规则四叉树是用五个字段的记录来表规则四叉树是用五个字段的记录来表示树中的每个结点，其中一个用来描述结示树中的每个结点，其中一个用来描述结点的特性，即是灰、黑、白三类结点中的点的特性，即是灰、黑、白三类结点中的哪一种其余四个用于存放指向四个子结哪一种其余四个用于存放指向四个子结点的指针点的指针 线性四叉树以某一预先确定的次序遍历线性四叉树以某一预先确定的次序遍历四叉树形成一个线性表结构四叉树形成一个线性表结构 RA’abcdBCD’efgh其中其中R表示根，字母表示根，字母右上角加右上角加’表示是灰结点表示是灰结点 一对四式四叉树的存储结构一对四式四叉树的存储结构 每个结每个结点有五个字段，其中四个字段用来描述该点有五个字段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的指针放指向子结点记录存放处的指针四个子四个子结点对应的记录是依次连续存放的结点对应的记录是依次连续存放的 为节省存贮空间为节省存贮空间,有两个途径可以采取。
有两个途径可以采取一个是增加计算量；另一个途径是在记录中一个是增加计算量；另一个途径是在记录中再增加一个字节再增加一个字节,一分为四一分为四,每个子结点对应每个子结点对应2位位,表示它的子结点在指针指向区域中的偏移表示它的子结点在指针指向区域中的偏移 第二节第二节 三维几何模型三维几何模型 •几何元素几何元素 形体的模型主要指的就是包含图形信形体的模型主要指的就是包含图形信息所形成的模型息所形成的模型 形体本身的构造有一定的层次性，低形体本身的构造有一定的层次性，低层部分组合构成上一层部分，而上一层部层部分组合构成上一层部分，而上一层部分组合又可以构成更高一层的部分，依此分组合又可以构成更高一层的部分，依此类推可形成多层结构其中，每一层中的类推可形成多层结构其中，每一层中的部分，我们把它有称为几何元素部分，我们把它有称为几何元素 点点 它它是是0维维几几何何元元素素，，有有端端点点、、交交点点、、切切点点、、孤立点等形式孤立点等形式 曲曲线线、、曲曲面面的的应应用用中中会会涉涉及及到到三三种种类类型型 的点：的点：型值点型值点 相应曲线、曲面必然经过的点。
相应曲线、曲面必然经过的点控制点控制点 相应曲线、曲面不一定经过的点，仅相应曲线、曲面不一定经过的点，仅 用于确定位置和形状用于确定位置和形状插值点插值点 在型值点之间插入的一系列点，用于在型值点之间插入的一系列点，用于 提高曲线曲面的输出精度提高曲线曲面的输出精度 不同的空间中点的表示方式不同的空间中点的表示方式 一维空间中用一元组一维空间中用一元组{t}表示；表示； 二维空间中用二元组二维空间中用二元组{x,y}或或{x(t),y(t)}表示；表示； 三维空间中用三元组三维空间中用三元组{x,y,z}或或{x(t),y(t),z(t)}表示表示 点是几何造型中的最基本的元素，曲线、点是几何造型中的最基本的元素，曲线、曲面和其它形体都可以用有序的点集描述曲面和其它形体都可以用有序的点集描述 用计算机存储、管理、输出形体的实质就用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理是对点集及其连接关系的处理。
边边 边边是是一一维维几几何何元元素素，，是是两两个个邻邻面面（（正正则则形形体体））或或多多个个邻邻面面（（非非正正则则形形体体））的的交交界界边边分分直直线线边边和和曲曲线线边边直直线线边边由由起起点点和和终终点点两两端端点点确确定定；；曲曲线线边边由由一一系系列列型型值值点点或或控控制制点点表表示示，，也可以用显示、隐式方程描述也可以用显示、隐式方程描述环环 环是有序有向边（直线段或曲线段）组环是有序有向边（直线段或曲线段）组成的面的封闭边界环中的边不能相交，相邻成的面的封闭边界环中的边不能相交，相邻两条边共享一个端点环有内外之分，确定面两条边共享一个端点环有内外之分，确定面的最大外边界的环称之为的最大外边界的环称之为外环外环，通常其边按，通常其边按逆逆时针方向时针方向排序而把确定面中内孔或凸台边界排序而把确定面中内孔或凸台边界的环称之为的环称之为内环内环，其边相应外环排序方向相反，，其边相应外环排序方向相反，通常按通常按顺时针顺时针方向排序方向排序 面面 面面是是二二维维元元素素，，是是形形体体上上一一个个有有限限、、非非零零的的区区域，它由域，它由一个外环和若干个内环所界定一个外环和若干个内环所界定。
面面有有方方向向性性，，一一般般用用其其外外法法向向量量作作为为该该面面的的正正向向若若一一个个面面的的外外法法向向量量向向外外，，此此面面为为正正；；否否则则，，为反向面为反向面体体 体是三维几何元素，由封闭表面围成的空间，体是三维几何元素，由封闭表面围成的空间，它是欧氏空间它是欧氏空间R R3 3中非空、有界的封闭子集，其边界中非空、有界的封闭子集，其边界是有限面的并集在实际应用中，要求形体是正则是有限面的并集在实际应用中，要求形体是正则形体，即形体上任意一点的足够小的邻域在拓扑上形体，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆不满足上述要求的形体称应是一个等价的封闭圆不满足上述要求的形体称为非正则形体存在悬面、悬边的形体是非正则形为非正则形体存在悬面、悬边的形体是非正则形体 体素体素 体体素素是是可可以以用用有有限限个个尺尺寸寸参参数数定定位位和和定定型型的体，常有下面三种定义形式的体，常有下面三种定义形式一组单元实体一组单元实体 长方体、圆柱体、圆锥体、球体长方体、圆柱体、圆锥体、球体扫扫描描体体 由由参参数数定定义义的的一一条条（（一一组组））截截面面轮轮廓廓线线沿沿一一条条（（一一组组））空空间间参参数数曲曲线线作作扫扫描描运运动动而而产产生的形体。
生的形体用代数半空间定义的形体用代数半空间定义的形体，在此半空间中点集，在此半空间中点集可定义可定义{(x,y,z)|f(x,y,z) ≤0}此处的此处的f应是不应是不可约的多项式可约的多项式形体的层次结构形体的层次结构 点点→边边→环环→面面→外壳外壳→形体 运动轨迹运动轨迹初始运动面初始运动面 在几何造型中最基本的几何元素是在几何造型中最基本的几何元素是点（点（V）、）、边边(E)、、面面(F),这三种元素一这三种元素一共有九种连接关系共有九种连接关系 •线框、表面及实体表示线框、表面及实体表示 常用的常用的多面体多面体表示法是表示法是三表表示法三表表示法，即，即采用三个表采用三个表: :顶点表顶点表, ,用来存放多面体各顶点用来存放多面体各顶点的坐标的坐标; ;边表边表, ,指出哪两个顶点之间有多面体指出哪两个顶点之间有多面体的边；的边；面表面表，指出哪些边围成了多面体的表，指出哪些边围成了多面体的表面 任意多面体容易得到它的三表表示任意多面体容易得到它的三表表示, ,但任但任意三张表却不一定表示了一个真实的多面体。
意三张表却不一定表示了一个真实的多面体这里必须满足的条件至少有以下几项这里必须满足的条件至少有以下几项: :顶点表顶点表中的每个顶点至少是中的每个顶点至少是三边三边的端点的端点; ;边表中的每边表中的每条边是条边是两个多边形两个多边形面的公共边；每个多边形面的公共边；每个多边形面是封闭的等等面是封闭的等等 x xy yz z1 10 00 01 11 10 00 01 10 00 00 00 01 10 01 11 11 11 10 01 11 10 00 01 11 12 22 23 33 34 44 41 15 56 66 67 77 78 88 85 51 15 52 26 63 37 74 48 81 110105 59 92 211116 610103 312127 711114 49 98 812125 56 67 78 83 32 21 14 4顶点表顶点表面表面表边表边表 空间正二空间正二十面体十面体V20, 的三表表示的三表表示 引人一个引人一个正数正数Φ>0,它它满足二次方满足二次方程程Φ2-Φ-1=0,因此因此Φ=(1+ )/2≈1.618034。
XYZ 编号编号xyz编号编号xyz11Φ0123-1Φ01213-ΦΦ001-12431-10-Φ1 0Φ14-Φ0-13201-Φ211Φ0330-1Φ221-Φ0340-1-Φ 边边 编编号号 边边 编编号号 1 11111，，131316162121，，32322 21212，，141417172222，，33333 32121，，232318182222，，34344 42222，，242419192323，，31315 53131，，333320202323，，32326 63232，，343421212424，，33337 71111，，212122222424，，34348 81111，，222223233131，，1111边边 编编号号 边边 编编号号 9 912,2312,2324243131，，1212101012,2412,2425253232，，1313111113,2113,2126263232，，1414121213,2213,2227273333，，1111131314,2314,2328283333，，1212141414,2414,2429293434，，1313151521,3121,3130303434，，1414 面编号面编号 面编号面编号 1 17 7，，2323，，151511112525，，6 6，，29292 28 8，，1717，，272712123030，，6 6，，26263 31111，，1616，，252513131111，，1 1，，7 74 42929，，2828，，121214148 8，，1 1，，12125 59 9，，1919，，242415159 9，，2 2，，13136 62828，，2121，，101016161414，，2 2，，10107 72626，，2020，，131317171919，，3 3，，15158 81414，，2222，，303018181616，，3 3，，20209 92727，，5 5，，232319191717，，4 4，，212110102424，，5 5，，282820202222，，4 4，，1818 •三维实体表示方法三维实体表示方法 从用户角度来看，形体以特征表示和构从用户角度来看，形体以特征表示和构造的实体几何表示比较适宜；从计算机对形造的实体几何表示比较适宜；从计算机对形体的存储管理和操作运算角度看，以边界表体的存储管理和操作运算角度看，以边界表示最为实用。
示最为实用 1 构造的实体几何法构造的实体几何法 构造的实体几何构造的实体几何(CSG:Constructive Solid Geometry)法是指任意复杂的形体都可法是指任意复杂的形体都可以用简单形体以用简单形体(体素体素)的组合来表示的组合来表示 形体的形体的CSG表示可看成是一棵有序的二表示可看成是一棵有序的二叉树，称为叉树，称为CSG树其终端结点或是体素，树其终端结点或是体素，如长方体、圆锥等；或是刚体运动的变换参如长方体、圆锥等；或是刚体运动的变换参数，如平移参数数，如平移参数Tx等；非终端结点或是正则等；非终端结点或是正则的集合运算，一般有交、并、差运算；的集合运算，一般有交、并、差运算； 或是刚体的几何变换，如平移、旋转等或是刚体的几何变换，如平移、旋转等 采用采用BNF范式可定义范式可定义CSG树若下：树若下：
变换和正则集合运算算子 CSG表示的优点：表示的优点： 数数据据结结构构比比较较简简单单，，数数据据量量比比较较小小，，内内部数据的管理比较容易；部数据的管理比较容易； 每个每个CSG表示都和一个实际的有效形体所对应；表示都和一个实际的有效形体所对应；CSG表表示示可可方方便便地地转转换换成成Brep表表示示，，从从而而可可支支持持广泛的应用；广泛的应用； 比较容易修改比较容易修改CSG表示形体的形状表示形体的形状CSG表示的缺点：表示的缺点： 产产生生和和修修改改形形体体的的操操作作种种类类有有限限，，基基于于集集合运算对形体的局部操作不易实现；合运算对形体的局部操作不易实现； 由于形体的边界几何元素由于形体的边界几何元素(点、边、面点、边、面)是是隐含地表示在隐含地表示在CSG中，故显示与绘制中，故显示与绘制CSG表示表示的形体需要较长的时间的形体需要较长的时间 并 2 2 特征表示特征表示 特特征征表表示示是是从从应应用用层层来来定定义义形形体体，，因因而而可可以以较较好好地地表表达达设设计计者者的的意意图图，，为为制制造造和和检检验验产产品品和和形形体体提提供供技技术术依依据据和和管管理理信信息息。
从从功功能能上上看可分为形状、精度、材料和技术特征看可分为形状、精度、材料和技术特征 形状特征：体素、孔、槽、键等形状特征：体素、孔、槽、键等 精度特征：形位公差、表面粗糙度等；精度特征：形位公差、表面粗糙度等； 材料特征：材料硬度、热处理方法等；材料特征：材料硬度、热处理方法等； 技术特征：形体的性能参数和特征等技术特征：形体的性能参数和特征等 形状特征单元是一个有形的几何实体，是形状特征单元是一个有形的几何实体，是一组可加工表面的集合如采用长、宽、高三一组可加工表面的集合如采用长、宽、高三尺寸表示的长方体；采用底面半径及高度表示尺寸表示的长方体；采用底面半径及高度表示的圆柱体均是可选用的形状特征单元的圆柱体均是可选用的形状特征单元 形状特征单元的形状特征单元的BNF范式可定义如下：范式可定义如下： <形形状状特特征征单单元元>::=<体体素素>|<形形状状特特征征单单元元><集集合合运运算算><形形状状特特征征单单元元>|<体体素素><集集合合运运算算><体体素素>|<体体素素><集集合合运运算算><形形状状特特征征单单元元>|<形形状状特特征征单单元元><集集合合运运算算><形形状特征过渡单元状特征过渡单元>;<体体素素>::=长长方方体体|圆圆柱柱体体|球球体体|圆圆锥锥体体|棱棱锥锥体体|棱柱体棱柱体|棱台体棱台体|圆环体圆环体|楔形体楔形体|圆角体圆角体|…；；<集合运算集合运算>::=并并|交交|差；差；<形状特征过渡单元形状特征过渡单元>::=外圆角外圆角|内圆角内圆角|倒角。
倒角 3 3 边界表示边界表示 边界表示详细记录了构成形体的所有几何边界表示详细记录了构成形体的所有几何元素的几何信息及其相互连接关系元素的几何信息及其相互连接关系——拓扑关系，拓扑关系，便于直接存取构成形体的各个面、面的边界以便于直接存取构成形体的各个面、面的边界以及各个顶点的定义参数，有利于以面、边、点及各个顶点的定义参数，有利于以面、边、点为基础的各种几何运算和操作为基础的各种几何运算和操作 形体的边界表示就是用面、环、边、点来形体的边界表示就是用面、环、边、点来定义形体的位置和形状例如，一个长方体由定义形体的位置和形状例如，一个长方体由六个面围成，对应有六个环，每个环由四条边六个面围成，对应有六个环，每个环由四条边界定义，每条边又由两个端点定义而圆柱体界定义，每条边又由两个端点定义而圆柱体则由上顶面、下底面和圆柱面所围成，对应有则由上顶面、下底面和圆柱面所围成，对应有上顶面圆环、下底面圆环上顶面圆环、下底面圆环 Brep表示的优点是：表示的优点是： 表表示示形形体体的的点点、、边边、、面面等等几几何何元元素素是是显显式式表表示示的的，，使使得得绘绘制制Brep表表示示形形体体的的速速度度较较快快，，而且比较容易确定几何元素间的连接关系；而且比较容易确定几何元素间的连接关系； 对形体的对形体的Brep表示可有多种操作和运算。
表示可有多种操作和运算Brep表示的缺点是：表示的缺点是： 数数据据结结构构复复杂杂，，需需要要大大量量的的存存储储空空间间，，维维护内部数据结构的程序比较复杂；护内部数据结构的程序比较复杂； 修改形体的操作比较难以实现；修改形体的操作比较难以实现； Brep表示并不一定对应一个有效形体，即需要表示并不一定对应一个有效形体，即需要有专门的程序来保证有专门的程序来保证Brep表示形体的有效性、表示形体的有效性、正则性等正则性等 八叉树八叉树 假设要表示的形体假设要表示的形体V可以放在一个充分大可以放在一个充分大的正立方体的正立方体C内内,C的边长为的边长为2n,形体形体V C ,它的它的八又树表示可以递归定义为八又树表示可以递归定义为: 八叉树每个结点与八叉树每个结点与C的一个子立方体对应，的一个子立方体对应，树根就和树根就和C本身对应如果本身对应如果V=C,那么那么V八叉树八叉树仅有树根如果仅有树根如果V≠C,则将则将C均分为八个子立均分为八个子立方体方体,每个子立方体对应根结点的一个子结点每个子立方体对应根结点的一个子结点。
只要某个子立方体不是完全空白或完全被只要某个子立方体不是完全空白或完全被V所占据所占据,它就要被八等分它就要被八等分,从而它对应的结点从而它对应的结点也有了八个子结点这样的递归判断及可能也有了八个子结点这样的递归判断及可能分割一直进行分割一直进行,直到结点对应的立方体或完全直到结点对应的立方体或完全空白空白,或完全被占据或完全被占据,或其大小已是预先规定或其大小已是预先规定的体素大小的体素大小. 这时对它与这时对它与V V之交作一定的之交作一定的““舍入舍入””, ,使体素或认为是空白使体素或认为是空白, ,或认为是被或认为是被V V占据的这里所谓的体素占据的这里所谓的体素, ,就是指被分就是指被分割后得到的小立方体割后得到的小立方体 通常称对应立方体被形体通常称对应立方体被形体V V完全占完全占据的结点为据的结点为黑结点黑结点, ,完全不占据的为完全不占据的为白白结点结点, ,部分被占据的为部分被占据的为灰结点灰结点 存贮结构存贮结构, , 有常规的、线性的、有常规的、线性的、一对八式的八叉树等等一对八式的八叉树等等 八叉树方法的主要优点在于八叉树方法的主要优点在于, ,可以非常方可以非常方便地实现形体的便地实现形体的集合运算集合运算 。
八叉树表示的三维形体的几何变换八叉树表示的三维形体的几何变换 比例变换比例变换 旋转变换旋转变换 相对通过原点的一条任意方向相对通过原点的一条任意方向的直线做旋转任意角度的旋转变换的直线做旋转任意角度的旋转变换 构成原形体的构成原形体的直立直立的正立方体经绕原点任的正立方体经绕原点任意轴线旋转任意角度后意轴线旋转任意角度后, , 一般都成为一般都成为斜置斜置的为了使变换后形体的八叉树仍对应一系列直立为了使变换后形体的八叉树仍对应一系列直立的正立方体的正立方体, ,必须对被斜置立方体部分占据体必须对被斜置立方体部分占据体素做出选择素做出选择, ,即或认为是占据即或认为是占据, ,为黑结点为黑结点, ,或认或认为不占据为不占据, ,为白结点为白结点, ,这就必然带来一定的误差这就必然带来一定的误差而且执行多次变换后而且执行多次变换后, ,误差积累会大到产生严误差积累会大到产生严重的错误重的错误 第第一一项项措措施施是是保保持持一一个个原原始始的的八八叉叉树树做做为为参参考考的的源源树树。
设设指指定定了了一一次次变变换换R1,接接着着又又要要做做变变换换R2,可可以以计计算算出出复复合合变变换换R=R1·R2,然然后后对对原原始始的的八八叉叉树树做做一一次次变变换换这这样样来来避避免免误误差差的的积累 第二项措施是为了尽量减少第二项措施是为了尽量减少"舍入舍入"误差误差,可可以规定一个当前正要重建的八叉树以规定一个当前正要重建的八叉树,如果它的最如果它的最底层叶结点对应的体素是部分地为显示对象所底层叶结点对应的体素是部分地为显示对象所占据，那么当且仅当这个体素的中心位于某个占据，那么当且仅当这个体素的中心位于某个黑变换后立方体内时黑变换后立方体内时,这个体素才被规定为黑这个体素才被规定为黑,否则就规定为白这样规定使得一般不会产生否则就规定为白这样规定使得一般不会产生原来不存在的孔洞，而不这样规定原来不存在的孔洞，而不这样规定,例如简单地例如简单地规定部分被占据的体素都为白规定部分被占据的体素都为白,则可能在做则可能在做450左右旋转时原来黑立方体变换为部分占据若干左右旋转时原来黑立方体变换为部分占据若干体素而被指定为白体素而被指定为白,在变换后形体中间出现断裂。
在变换后形体中间出现断裂 设己采取了上述两项措施设己采取了上述两项措施, ,已知形体变换已知形体变换前的八叉树表示前的八叉树表示T T1 1, ,己计算出己计算出 要要做做的的复复合合变变换换R,R,要要确确定定变变换换后后形形体体的的八叉树表示八叉树表示T T2 2, ,可以写出如下的算法框架：可以写出如下的算法框架：1. 1. 遍遍历历形形体体原原来来的的八八叉叉树树T T1 1, ,对对遇遇到到的的每每个个黑黑结点结点, ,做下述步做下述步2 22. 2. 对对遇遇到到黑黑结结点点对对应应的的正正立立方方体体做做相相应应变变换换, ,得得它它新新的的一一般般来来说说是是斜斜置置的的新新位位置置若若这这位位置置已已超超出出定定义义八八叉叉树树的的充充分分大大正正立立方方体体C C之之外外, ,报告出错报告出错; ;否则执行下述的步否则执行下述的步3 33. 3. 从要计算求出的目标树从要计算求出的目标树T T2 2的根开始的根开始, ,检查检查2 2中中确定的处于新位置立方体与确定的处于新位置立方体与T T2 2中结点对应的直中结点对应的直立的正立方体是否相交立的正立方体是否相交, ,分以下三种情况进行分以下三种情况进行处理处理: : (1) 1) 不不相相交交, ,说说明明正正考考查查直直立立正正立立方方体体未未被被占占据据, ,可保持为白结点可保持为白结点, ,不做处理。
不做处理2) (2) 直直立立的的正正立立方方体体整整个个被被占占据据, ,即即它它在在变变换换后后" "斜置斜置" "立方体内立方体内, ,置对应结点为黑结点置对应结点为黑结点3) (3) 在在上上述述两两条条均均不不成成立立时时, ,生生成成当当前前结结点点的的八八个个子子结结点点, ,对对八八个个子子结结点点对对应应的的八八个个直直立立子子立立方方体体, ,依依次次再再递递归归执执行行步步3 3如如果果最最终终这这八八个个结结点点被被标标上上同同样样特特性性, ,比比方方为为黑黑结结点点, ,则则应应再再删删掉掉这这八八个个子子结结点点而而把把它它们们的的共共同父结点置为黑同父结点置为黑 算法中算法中, ,主要工作是检查某个直立的正主要工作是检查某个直立的正立方体与一个斜置的正立方体是否相交立方体与一个斜置的正立方体是否相交, ,对所有黑结点对应正立方体处理相同对所有黑结点对应正立方体处理相同, ,使得使得操作可以并行进行操作可以并行进行 线性八叉树线性八叉树 在对立方体做八等分时在对立方体做八等分时,按一致的方式按一致的方式, 对分出的子立方体进行编号。
若再分共进对分出的子立方体进行编号若再分共进行行n层，则每个结点可以用层，则每个结点可以用n位的八进制数位的八进制数的数串的数串来表示来表示,数串从左至右数串从左至右,第一位对应第一位对应第一次划分，第二位对应第二位划分，依第一次划分，第二位对应第二位划分，依此类推据此整个八叉树就可以根据对其据此整个八叉树就可以根据对其做深度第一遍历而依次列出的黑结点的编做深度第一遍历而依次列出的黑结点的编号序列来表示号序列来表示 前图所示三维形体前图所示三维形体,其线性八叉树表示是其线性八叉树表示是: {0x,10,12,13,14,2x,4x,6x,7x} 求并运算求并运算 C1UC2 两棵线性八叉树两棵线性八叉树:C1={122,123,301,302,303,305,307}C2={12x,300,302,304,306} 将将C2的的各各结结点点依依次次插插入入到到C1的的适适当当位位置置,使使插插入入后后编编号号渐渐增增这这一一性性质质保保持持不不变变当当C2中中结结点点可可以以包包含含C1中中若若干干结结点点时时,则则取取而而代代之之另另外外,如如果果插插入入后后可可以以进进行行结结点点"压压缩缩",也也应应该该立立即即进行进行:C1UC2={12x,300,301,302,303,304,305,306,307} ={12x,30x} 线性八叉树表示形体的显示线性八叉树表示形体的显示 当观察位置是当观察位置是x1>0,y1<0,z1>0时时,最可最可能被遮挡看不见的是编号能被遮挡看不见的是编号2的子立方体的子立方体,全全部依次排出可以是部依次排出可以是26034715 zl>0,y1<0,x1>0 优先级优先级26034715。
前图表示形体的线性前图表示形体的线性八叉树八叉树{0x,10,12,13,14,2x,4x,6x,7x} 按结点应显示次序排按结点应显示次序排出的序列就是出的序列就是:{2x,6x,0x,4x,7x,12,10,13,14} z z1 1 y y1 1 x x1 1 优先级优先级<0<0<0<0<0<07356124073561240<0<0<0<0>0>03712560437125604<0<0>0>0<0<05174306251743062<0<0>0>0>0>01530742615307426>0>0<0<0<0<06247035162470351>0>0<0<0>0>02603471526034715>0>0>0>0<0<04065217340652173>0>0>0>0>0>00421653704216537 第三节第三节 分形分形 •分形的概念分形的概念 三分康托三分康托(Cantor)集集 设设E0是闭区间是闭区间[0,1],即即E0是满足是满足0≤x≤1的实的实数数x组成的点集组成的点集;E1是是E0去掉中间去掉中间1/3之后的点集之后的点集,即即E1是两个闭区间是两个闭区间[0，，1/3]和和[1/3，，2/3];E2是分是分别去掉别去掉E1中两个区间的中间中两个区间的中间1/3之后的点集之后的点集,即即E2已经是四个闭区间。
此过程要继续进行已经是四个闭区间此过程要继续进行,Ek是是2k个长度为个长度为1/3k的闭区间组成的点集三分康托集的闭区间组成的点集三分康托集F是属于所有的是属于所有的Ek的点组成的集的点组成的集,即即 F可以看成是集序列可以看成是集序列Ek当当k趋于无穷时的极限趋于无穷时的极限只能画出只能画出k取定时的某个取定时的某个Ek当k充分大时充分大时,Ek是是对对F的很好的近似的表现的很好的近似的表现 三三分分康康托托集集是是区区间间[0,1]中中的的可可以以展展成成以以3为底的幕级数的下面形式的数组成的为底的幕级数的下面形式的数组成的:a13-1+a23-2+a33-3… 其中其中ai的取值限制为的取值限制为0或或2,不取不取1为看清这一为看清这一事实事实,注意从注意从E0得到得到E1时时,去掉的是去掉的是ai=1的数的数,从从E1得得E2时时,去掉的是去掉的是a2=1的数的数,并以此类推并以此类推 三三分分康康托托集集具具有有的的一一些些值值得得注注意意的的特特征征,这些特征对许多其它的分形也是大体上适合的。
这些特征对许多其它的分形也是大体上适合的 (1) F是是自自相相似似的的E1的的两两个个区区间间[0，，1/3]，，[1/3，，2/3]的的每每一一个个,其其内内部部F的的部部分分与与F整整体体相似相似,相似比为相似比为1/3 (2) (2) F F具具有有““精精细细结结构构””，，即即它它包包含含有有任任意意小小比比例的细节例的细节 (3) F(3) F的实际定义是简单的和明确的的实际定义是简单的和明确的 (4) (4) 传传统统的的几几何何学学很很难难描描述述F F的的性性质质, ,因因为为F F不不是是满满足足某某些些简简单单条条件件的的点点的的轨轨迹迹, ,也也不不是是任任何何简简单的方程的解的集合单的方程的解的集合5) (5) F F的的局局部部几几何何性性质质也也很很难难描描述述, ,在在它它的的每每点点附附近都有大量被各种不同间隔分开的其它点近都有大量被各种不同间隔分开的其它点6) (6) 按传统几何学中的长度概念按传统几何学中的长度概念,F,F的长度为零的长度为零就是说就是说, ,尽管从不可数集合这点上说尽管从不可数集合这点上说F F是一个相是一个相当大的集当大的集, ,但它却没有长度但它却没有长度, ,或者说长度不能对或者说长度不能对F F的形状或大小提供有意义的描述。
的形状或大小提供有意义的描述 von Koch曲线曲线 称集合称集合F是分形是分形,即认为它具有即认为它具有 下面典型的性质下面典型的性质: (1) F具有精细的结构，即有任意小比例的细节具有精细的结构，即有任意小比例的细节 (2) F是如此的不规则以至它的整体和局部都不能是如此的不规则以至它的整体和局部都不能 用传统的几何语言来描述用传统的几何语言来描述 (3) F具具有有某某种种自自相相似似的的形形式式,可可能能是是近近似似的的或或是是统统 计的 (4) 一般地一般地,F的的"分形维数分形维数"大于它的拓扑维数大于它的拓扑维数 (5) 在大多数令人感兴趣的情形下在大多数令人感兴趣的情形下,F以非常简单以非常简单 的方法定义的方法定义,可能由迭代产生可能由迭代产生 HausdorffHausdorff维数维数 考考虑虑一一个个简简单单的的几几何何图图形形, ,取取一一个个边边长长为为1 1的的正正方方形形, ,若若每每边边扩扩大大2 2倍倍, ,则则正正方方形形面面积积放放大大4 4倍倍, ,其其数数学学表表达达式式为为2 22 2=4,=4,这这是是2 2维维图图形形。
对对3 3维维图图形形, ,如如考考虑虑边边长长为为1 1的的立立方方体体, ,令令每每边边长长放放大大2 2倍倍, ,则则立立方体体积扩大方体体积扩大8 8倍倍, ,其数学表达式为其数学表达式为2 23 3=8=8 类类似似地地, ,对对一一个个DfDf维维的的几几何何对对象象, ,若若每每边边长长扩扩大大L L倍倍, ,则则这这个个几几何何对对象象相相应应地地放放大大K K倍倍, ,归归纳纳前前述述结果结果, ,D Df f,L,K,L,K三者间的关系式应为三者间的关系式应为: : L LDfDf=K=K 解解D Df f, , D Df f= =lnK/lnLlnK/lnL （（1 1）） 这这里里D Df f不不必必是是整整数数这这就就是是HausdorffHausdorff引引人人的维数概念的维数概念, ,可以称为可以称为HausdorffHausdorff维数 假假定定有有一一个个单单位位正正方方形形, ,把把它它每每边边三三等等分分得得九九个个小小的的正正方方形形, ,九九个个小小正正方方形形面面积积总总和和是是原原单单位位正正方方形形面面积积, ,即即9×(1/3)9×(1/3)2 2=1=1。
现现在在我我们们把把D Df f维维的的几几何何对对象象等等分分为为N N个个小小的的几几何何图图形形, ,则则每每个个小小图图形形每每维维缩缩小小为为原原来来的的r r倍倍, ,而而N N个小图形的总和应有个小图形的总和应有N·rN·rDfDf=1=1 这时解出这时解出 , ,有有: : （（2 2）） 容易看出式容易看出式(1)(1)和和(2)(2)本质上是相同的本质上是相同的, ,即这样引入的也是即这样引入的也是HausdorffHausdorff维数维数 von von KochKoch曲曲线线, ,每每次次分分为为4 4个个小小图图形形, ,每每个个小小图图形形缩缩小小1/31/3倍倍, ,故故其其HausdorffHausdorff维维数数 为：为： 分形一般算法分形一般算法 规则分形的生成算法。
对算法的输入是规则分形的生成算法对算法的输入是事先给定的一个整数事先给定的一个整数k k、、源形源形E E0 0及生成规则及生成规则, ,算法操作步骤如下算法操作步骤如下: : 1.1.〔〔初初始始化化〕〕i←0,j←1,i←0,j←1,队队Q←φ,AQ←φ,A0 0←E←Eo o;{;{用用在在第第i i层层表表示示正正处处在在生生成成E Ei i的的阶阶段段对对m≥2,m≥2,设设生生成成规规则则指指明明了了E Ei i由由m m个个E Ei+1i+1组组成成, ,则则在在第第i i层层共共应应生生成成m mi i个个部部分分图图形形用用A A0 0记记一一个个部部分分图图形形,j,j是是己己生生成成部部分分图图形形的的数数目目第第i i层层部部分分图图形形要要在在第第i+1i+1层层再再分分, ,故故生生成成后后要要送送到到一一个个先先进进先先出出的队的队Q Q中等待中等待;};}2.2.〔〔一一次次生生成成〕〕依依据据生生成成规规则则, ,由由一一个个部部分分图图形形A A0 0, ,计算它的计算它的m m个分解部分个分解部分A A1 1,A,A2 2, …A, …Am m; ;3.3.〔〔图形绘制图形绘制〕〕对对A Al l,A,A2 2, …,A, …,Am m做图形绘制做图形绘制; ;4.4.〔〔存存贮贮〕〕队队Q←(AQ←(A1 1,A,A2 2,…,A,…,Am m){){生生成成各各部部分分图图形依次加到队尾形依次加到队尾;};} 5.5.〔〔准准备备下下次次〕〕A A0 0←←队队Q;{Q;{从从队队取取出出一一个个部部分分图图 形形;};}6.6.〔〔 第第 i i层层 是是 否否 结结 束束 〕〕 j←j+1,j←j+1,若若 j>mj>mi i, ,则则j←1;i←i+1;j←1;i←i+1;7.7.〔〔结束判断结束判断〕〕若若i>k,i>k,则算法结束则算法结束; ;否则返回步否则返回步2 2 von Koch von Koch曲线曲线 其源形其源形E E0 0可以是一条线段可以是一条线段, , 记其端点坐标为记其端点坐标为P P0 0,P,P1 1。
在算法步在算法步1,1,应令应令A A0 0=E=E0 0= =(P(Po o,P,Pl l ), ),在算法步在算法步2,2,需要依据需要依据P Po o,P,P1 1 , ,计算图中计算图中P P2 2,P,P3 3,P,P4 4三点的坐标三点的坐标 这样这样m=4,m=4,分别得到四个部分图形是分别得到四个部分图形是A1=(PA1=(P0 0,P,P2 2),A),A2 2=(P=(P2 2,P,P3 3),A),A3 3=(P=(P3 3,P,P4 4),A),A4 4=(P=(P4 4,P,P1 1) )在算法步在算法步3,3,可画出四条线段可画出四条线段P P0 0P P2 2,P,P2 2 P P3 3, P, P3 3 P P4 4, , P P4 4P P1 1, ,擦去前次画线时可能画出的擦去前次画线时可能画出的P P2 2P P4 4部分 •Von KochVon Koch算法算法 利用利用自相似自相似变换来绘制分形变换来绘制分形 设设D D是是欧欧氏氏空空间间R Rn n的的闭闭子子集集, ,映映射射S:D→DS:D→D称称为为是是D D上上的的压压缩缩，，如如果果对对所所有有D D上上的的点点x,y,x,y,存存在在一一个个数数c,0 如如果果其其中中等等号号成成立立, ,即即若若|S(x)-|S(x)-S(y)|=c|x-y|,S(y)|=c|x-y|,则则S S把把一一个个集集变变成成了了它它的的几几何何相似集相似集, ,此时映射此时映射S S称为是相似的称为是相似的 设设S S1 1,…,,…,S Sn n是是压压缩缩, ,称称D D的的子子集集F F对对变变换换S S1 1, …,, …,S Sn n是不变的是不变的, ,如果如果 三分康托集的情形三分康托集的情形, ,这时令这时令S S1 1,S,S2 2是是R→RR→R的变换的变换, ,分别由分别由 P P0 0和和P P1 1的坐标是的坐标是(0,0)(0,0)和和(1,0),(1,0),则可以则可以计算求出计算求出P P2 2,P,P3 3,P,P4 4的坐标是的坐标是 自相似变换自相似变换S S1 1和和S S2 2是平面变换是平面变换, ,可一般地可一般地设变换矩阵为设变换矩阵为: : 第一个变换第一个变换S S1 1把点把点P P0 0,P,P1 1,P,P3 3, ,依次变到依次变到P Po o, , P P3 3,P,P2 2, ,这就得到这就得到: : 于是有 第二个变换第二个变换S S2 2把点把点P P0 0,P,P1 1,P,P3 3, ,依次变到依次变到P P3 3,P,P1 1,P,P4 4，，这就得到：这就得到： 因此因此 绘制绘制von Kochvon Koch曲线曲线1.1.〔〔初始化初始化〕〕x x1 1←0,y←0,y1 1←0,s←1,u←1;{(x←0,s←1,u←1;{(x1 1,y,y1 1) )为初始点。 为初始点} }2.2.〔〔变换变换〕〕3.3.〔〔画点画点〕〕在显示表面画点在显示表面画点(x(x2 2,y,y2 2) )和和(x(x3 3,y,y3 3););4.4.〔〔存贮存贮〕〕P Ps s←(x←(x2 2,y,y2 2),P),Ps+1s+1←(x←(x3 3,y,y3 3),s←s+2;),s←s+2;5.5.〔〔准备下次准备下次〕〕(x(x1 1,y,y1 1)←P)←Pu u,u←u+1;,u←u+1;6.6.〔〔是否结束是否结束〕〕若若u>ku>k则算法结束则算法结束, ,否则返步否则返步2 2 上面的变换能产生很紧松树树枝的图象上面的变换能产生很紧松树树枝的图象 •Julia和和Mandelbrot集集 设有复数域上如下形式的二次函数设有复数域上如下形式的二次函数: f(z)=z2+c 其中其中c是复数值常数是复数值常数,做迭代操作做迭代操作: zn+1= zn2+c,n=0,1,2,… 研究的问题是研究的问题是:1.给给定定z0,当当参参数数c在在什什么么范范围围内内取取值值能能保保证证|zn|有界有界2.当当c给定给定,如何选取如何选取z0,使使|zn|有界有界? 上述迭代上述迭代,当当c=0时时,可以有以下三种情况可以有以下三种情况:1. 序序列列中中的的数数按按模模来来说说越越来来越越小小,且且趋趋于于零零。 这这时时说说零零是是z→z2的的吸吸引引子子所所有有与与坐坐标标原原点点相相距距小于小于1的点都产生趋向零的序列的点都产生趋向零的序列2. 序序列列中中的的数数按按模模来来说说越越来来越越大大,且且趋趋向向无无穷穷,这这时时"无无穷穷"也也称称为为过过程程的的吸吸引引子子与与坐坐标标原原点点的的距离超过距离超过1的所有点都产生趋向无穷的序列的所有点都产生趋向无穷的序列;3. 距距坐坐标标原原点点为为1的的点点,序序列列总总是是产产生生在在上上面面两两个个吸吸引引区区域域之之间间的的边边界界上上,此此时时边边界界恰恰为为复复平平面面上上的单位圆周的单位圆周 对于上述迭代对于上述迭代,当当c≠ 0时时,吸引子不再是零吸引子不再是零,吸引区域的边界不再是光滑的吸引区域的边界不再是光滑的,而是具有而是具有自似形自似形的分形结构的分形结构,这种边界称为这种边界称为Julia集 在复平面上，使在复平面上，使z→z2+c的迭代过程成的迭代过程成为有界的复参数为有界的复参数c的集合叫做的集合叫做Mandelbrot 设复平面上的迭代过程是设复平面上的迭代过程是: zk+1=zk2+c分离实部和虚部分离实部和虚部,记记zk =xk+yki,c=p+qi,有有 设计算机显示屏幕的图形分辨率是设计算机显示屏幕的图形分辨率是a×b点点,可显示颜色是可显示颜色是k+1种种,以数字以数字0到到k表示表示,0表示黑色。 表示黑色取定取定p和和q的值的值,考虑平面上每一点考虑平面上每一点(x,y),探讨吸探讨吸引区域的结构及其边界即引区域的结构及其边界即Julia集1.〔〔选定参数选定参数〕〕xmin ← -1.5,ymin ← -1.5,xmax ← 1.5,ymax ← 1.5,M← 100,并令并令△△x ← (xmax - xmin )/(a-1), △△y ← (ymax- ymin)/(b-1);{这里这里(xmin , ymin)(xmax, ymax)区域是考查的复平面范围区域是考查的复平面范围,M是指是指定的一个阈值定的一个阈值,超过它算是已达到无穷超过它算是已达到无穷;K是可显是可显示颜色的数目示颜色的数目}2.〔〔逐点着色逐点着色〕〕对所有点对所有点(nx,ny),nx=0,1,…,a-1, ny=0,1,…,b-1,完成以下循环后算法结束完成以下循环后算法结束 2.1〔〔置初值置初值〕〕x0 ← xmin + nx·△△x ,y0 ← ymin + ny ·△△y ,k ← 0;2.2〔〔一次迭代一次迭代〕〕 ,k ← k+1; 2.3〔〔判断判断〕〕r ← 。 若若r>M,则选择颜色则选择颜色k,转步转步2.4;若若k=K,则选择颜色则选择颜色0,即黑色即黑色,转步转步2.4;若若r≤ M且且k 完成以下循环后算法结束 2.12.1〔〔置初值置初值〕〕p0 ← pmin + nx·△△p ,q0 ← qmin + nq ·△△q ,k ← 0; x0 ← 0,y0 ← 0 2.2〔〔一次迭代一次迭代〕〕 k ← k+1; ; 2.32.3〔〔判断判断〕〕r r ← ← 若若r>M,则选择颜色则选择颜色k,转步转步2.4;若若k=K,则选择颜色则选择颜色0,即黑色即黑色,转步转步2.4;若若r≤ M且且k
