计算机图形学第六优秀课件.ppt

《计算机图形学第六优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算机图形学第六优秀课件.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机图形学第六第1页，本讲稿共38页 本本 章章 重重 点点 理解并掌握常用的几种实体的表示方法，包括它们的基本原理、特点、数据结构等。难点难点：实体表示方法的算法实现。第2页，本讲稿共38页6.1 6.1 常用的几何模型常用的几何模型 计算机图形处理之前，首先要做的是将物体或场景模型化，也就是通过分析研究，将三维形体模型化，形成定量的描述；再将这些描述的信息以数字化的形式送入计算机，经过计算机处理后显示出相应的图形。物体或场景的模型化通常是采用几何模型的形式来表示。常用的几何模型有以下三种：第3页，本讲稿共38页1.1.线模型线模型 线模型表示的是物体的棱边，它全部是由点、直线或曲线组成。

2、对于仅用阴影棱线就能表示形状的物体，可以采用线模型。该模型的主要特点是结构简单，模型生成和处理容易，占用的内存容量较小，因此成本较低。但线模型由于仅用棱边来代表物体的形状，它只包含了三维物体的一部分形状信息，在信息的完整性方面是不足的。因此难以进行隐藏线消除，也不能描绘剖面图，也不可能根据它计算物体的其它物理量(例如体积、重量等)。第4页，本讲稿共38页第5页，本讲稿共38页2.2.表面模型表面模型 把线模型中棱线包围的部分定义为面，所形成的模型就是表面模型。采用表面模型，物体的边界确实可以全部定义，但是物体的实心部分在边界的哪一侧是不明确的，因为它只定义了单个的表面块，而且由于它们没有被结合

3、在一起，所以边界面不能明确地定义其所包围的实心部分，使设计者对物体缺乏整体的概念。第6页，本讲稿共38页3.3.实体模型实体模型 实体模型是从设计到生产过程中能够连贯使用的比较理想的模型，它与上述表面模型不同之处在于它确定了是表面的哪一侧存在实体这个问题。利用实体模型不仅能表示模型的颜色，而且还能进行阴影处理，并可对主要的特征如重量、力矩等进行定量的计算。第7页，本讲稿共38页第8页，本讲稿共38页6.2 6.2 实体的表示方法实体的表示方法一一 .构造实体几何表示法构造实体几何表示法(Constructive Solid Geometry)该方法简称 CSG 方法。1.基本原理 任何三维形体

4、都可由一些基本体素通过集合运算的方法来构造。常用的基本体素有：长方体、圆柱体、圆锥体、圆台体、环、球等。采用的集合运算是：并、交、差。在构造实体几何表示法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述。第9页，本讲稿共38页U*构造结果得到一棵表示物体的二叉树第10页，本讲稿共38页2.正则化集合运算 采用 CSG 方法构造出来的三维形体应该是一个正则点集，即：具有一定的形状；具有确定的封闭边界；占据有限的空间；不存在悬点、悬线、悬面。要使得构造出来的三维形体是一个正则点集，那么在其构造过程中所进行的集合运算即并，交，差运算不能是传统的集合的并，交，差运算，而应该是一种正则化的几

5、何运算。ABA B A*B第11页，本讲稿共38页 在构造实体的几何表示法中，体素也可以用半空间的集合运算组成。一个无边界的面可将三维空间分割成两个无边界的区域，每一个区域均称为半空间。若空间平面方程为：f(x,y,z)=0 记为 f i 则可定义半空间为：P f(x,y,z)0 或 P f(x,y,z)0 任一个凸多面体 F 都可表示为一组(n个)半空间的交：n F=f i i=1而任一个复杂形体都可表示为多个(m个)凸多面体的并：m F=Fj j=1第12页，本讲稿共38页3.CSG 表示法的数据结构 OP code (操作码)transform (坐标变换)primitive (基本体素

6、)left-subtree (左子树)Right-subtree (右子树)OP code 0 基本体素 1 求并 2 求差 3 求交CSG 表示法只定义了物体的构造方法 隐式模型。第13页，本讲稿共38页二.边界表示法(Boundary Representation)1.基本原理 边界表示法是通过描述物体的边界来表示一个实体。实体的边界面可以是平面多边形或曲面，通常情况下，曲面最终都是被近似地离散成多边形来处理的。v1v2v3v4v5e1e2e3f1 四棱锥面节点 f1 f2 f3 .边节点 e1 e2 e3 e4 .顶点节点 v1 v2 v3 (x1,y1,z1)()()拓扑信息几何信息第

7、14页，本讲稿共38页2.多面体及欧拉(Euler)公式 组成平面多面体的基本元素是：顶点、棱边和面。一个实体的表面必须满足闭合性，即构成实体的基本元素之间必须满足一定的条件，其简单的检验方法就是欧拉公式。设简单平面多面体的顶点数、棱边数和面数分别用V、E、F来表示，则:V E+F=2V=8 E=12 F=6第15页，本讲稿共38页对于非简单多面体则应满足广义欧拉公式：V E+F H=2(C G)其中 V、E、F 的含义与前相同；H 表示多面体表面上孔的个数；C 表示独立的不相连接的多面体的个数；G 表示贯穿多面体的孔的个数。V=24 H=3E=36 C=1F=15 G=124 36+15 3

8、=2(11)第16页，本讲稿共38页3.边界表示法的数据结构 拓扑信息是边界表示法中用于表示实体边界的主要信息之一。实体的面、边、点之间的拓扑关系有以下 9 种类型：vvvvvEvvvvvFvEEEEEEEEEEEEFvFFFEFFFFFFFvvv Ev FE vE EE FF vF EF F第17页，本讲稿共38页翼边结构翼边结构：边界表示法中常用的一种数据结构叫翼边结构翼边结构，它是以边为中心来组织数据的。v1v2EFLFRERcwERccELcwELccv1v2FLFRErcc Ercw Elcc ELcw第18页，本讲稿共38页 边界表示法将拓扑信息与几何信息分开表示，其优点是：便于查

9、询物体中的各元素（点、边、面等）。容易支持对物体的各种局部操作（如倒角）。对具有相同拓扑结构，而大小尺寸不同的一类物体，可用统 一的数据结构来表示。便于在数据结构上附加各种非几何信息（如光洁度、硬度 等）。倒角操作第19页，本讲稿共38页三.扫描表示法(Sweep)1.基本原理 空间的点、线、面沿着某一路径扫描时，所形成的轨迹可用来定义一个一维的、二维的或三维的物体。在三维形体表示中，主要采用平移扫描法和旋转扫描法。2.平移扫描法：将一个二维的面沿着一个指定的方向平行移动，其轨迹便形成了一个三维形体。第20页，本讲稿共38页 3.旋转扫描法：将一个二维的面绕一条母线（旋转轴）旋转，其轨迹便形成

10、了一个三维形体。4.广义扫描法：若在平移扫描的过程中可改变截面的大小和形状，甚至改变移动的方向，便可形成复杂的三维形体。第21页，本讲稿共38页第22页，本讲稿共38页四.八叉树表示法 1.基本原理 将所要表示的三维形体占据的空间分割成大小不同的立方体网格，并用这样一个立方体序列来描述实体。2.表示方法xyzFFFFPEEEFEFEFPEEEEEEFFEEP F(FULL)充满 E(EMPTY)无关 P(PARTIAL)相交第23页，本讲稿共38页3.数据结构 1 2 3 4 5 6 7 8 9 10其中：1节点标志域 2指向父节点的指针。若为根节点时，该域为0。310指向八个子节点的指针。若

11、为终端节点时，这些域的状态为空。八叉树表示的特点：定义形式简单。易于实现物体间的集合运算(并、交、差)。可简化消隐算法，便于计算物体的体积、质量等。存储量大。第24页，本讲稿共38页改进：线性八叉树，前例可表示为：1，2，3，4，51，53，55，565，566，P PFFFFFFFFF第25页，本讲稿共38页五.分形表示法 欧氏几何的主要描述工具是：直线、平滑的曲线、平面、边界整齐的平滑曲面。这些工具在描述一些抽象图形或人造物体的形态时是非常有力的，但对一些复杂的自然景象形态就显得无能为力了。为了解决复杂图形的生成，分数维(Fractal)造型技术应运而生。第26页，本讲稿共38页 从Koc

12、h的雪花图形 Mandelbrot的海岸线问题设N为每一步细分的数目 S为细分时的放大或缩小倍数则分数维定义为：log N log（1/S）D=雪花边线的分数维：N=4；S=1/3 log 4 log 3 D=1.2619第27页，本讲稿共38页 分数维的计算已有大量试验性的研究成果：例如 海岸线 1 D 1.3 山地表面 2.1 D 2.9 河流水系 1.1 D 1.85 云 D 1.35 人肺 D 2.17 血管 D 2.3 人脑表面 2.73 D 2.79第28页，本讲稿共38页分数维造型的常用模型有：随机插值模型模拟海岸线和山等自然景象；粒子系统模型模拟动态变化的火焰、烟等；正规文法模

13、型模拟植物（树）的生长；迭代函数系统模型模拟云彩等景物。第29页，本讲稿共38页第30页，本讲稿共38页第31页，本讲稿共38页第32页，本讲稿共38页 Koch 曲线曲线(1)Koch 曲线的生成规则迭代初始把原线段去掉中间的三分之一，代之以底边在被去线段上的等边三角形的两腰；以后每一步的迭代都是这样的重复。第33页，本讲稿共38页 Koch曲线（其它分形集也是如此）可以由简单的图形（生成元），迭代产生。在这里，Koch曲线的生成元是：生成元表示：约定记号，用一个字符串符号表示。设：F从当前点开始，向前移动一距离d L向左（逆时针）转一定角 R向右（顺时针）转一定角则Koch曲线的生成元可表

14、示为：T F L F R R F L F（60）第34页，本讲稿共38页 曲线由把每一折线段反复迭代成缩小比例的三分之一的生成元而成。即字符串T F L F R R F L F 中的每一个F 又是字符串 T 本身。每次迭代后，生成的曲线长是原来曲线长的三分之四倍。可见，无数次迭代后，Koch 曲线将变得具有无限长度。并且，Koch 曲线是永远不自相交的。第35页，本讲稿共38页（2）生成Koch 曲线的程序 函数 side：用于绘制Koch 曲线的生成元，xa,ya,xb,yb：线段的起点和终点坐标；a：线段的方向角；n：迭代次数（递归深度）。void side(float xa,ya,xb,

15、yb,a,int n)float x1,y1,x2,y2,x3,y3,dl,a1,a2;int xs,ys,xe,ye;if(n=0)xs=(int)(xa+0.5);ys=(int)(ya+0.5);xe=(int)(xb+0.5);ye=(int)(yb+0.5);moveto(xs,480-ys);lineto(xe,480-ye);else第36页，本讲稿共38页 dl=sqrt(xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)/3.;x1=xa+(xb-xa)/3.;y1=ya+(yb-ya)/3.;side(xa,ya,x1,y1,a,n-1);a1=a+AF;x2=x

16、1+dl*cos(a1);y2=y1+dl*sin(a1);side(x1,y1,x2,y2,a1,n-1);a2=a1-2.*AF;x3=x2+dl*cos(a2);y3=y2+dl*sin(a2);side(x2,y2,x3,y3,a2,n-1);side(x3,y3,xb,yb,a,n-1);/end of else/end of side第37页，本讲稿共38页 本本 章章 小小 结结1。三维形体（被描述的对象）在计算机中的表示是用计算机绘 制三维形体的前提，实际上就是采用某种表示方法及其相应 的数据结构来描述三维形体描述三维形体。2。实体模型实体模型能够比较完整地描述三维形体，因此是最常用的一 类几何模型。3。构造实体几何表示法（CSG）、边界表示法、八叉树表示法、扫描表示法(Sweep)等都是实体模型的具体表示方法实体模型的具体表示方法。它们 各有特色，可根据具体情况来采用。但它们都还无法描述象 自然景象这样的复杂图形。第38页，本讲稿共38页