计算机图形学 第2版 教学课件 徐长青形体的表示及其数据结构.ppt

在线教务辅导网： ://
教材其余课件及动画素材请查阅在线教务辅导网
QQ:349134187 或者直接输入下面地址：
第六章 形体的表示及其数据结构
与空间任意形体有关的信息可以分为图形信息和非图形信息两为1,可称为黑结点。假设整个与图形不相交,那么标记相应结点为0，可称为白结点。
假设不是上述两情形，即与图形局部相交，那么称相应结点是灰结点并将其一分为四。当再分生成小正方形边长到达一个象素单位时，再分终止，此时一般应将仍是灰结点的改为黑结点，如此形成了平面图形的四叉树表示
四叉树的存储结构，即规那么方式、线性方式和一对四方式，相应的四叉树也就称为规那么四叉树、线性四叉树和一对四式四叉树。
规那么四叉树是用五个字段的记录来表示树中的每个结点，其中一个用来描述结点的特性，即是灰、黑、白三类结点中的哪一种。其余四个用于存放指向四个子结点的指针。
线性四叉树以某一预先确定的次序遍历四叉树形成一个线性表结构 。
RA’abcdBCD’efgh。其中R表示根，字母右上角加’表示是灰结点。
一对四式四叉树的存储结构 每个结点有五个字段，其中四个字段用来描述该结点的四个子结点的状态，另一个结点存放指向子结点记录存放处的指针。四个子结点对应的记录是依次连续存放的。
为节省存贮空间,有两个途径可以采取。一个是增加计算量；另一个途径是在记录中再增加一个字节,一分为四,每个子结点对应2位,表示它的子结点在指针指向区域中的偏移。
第二节 三维几何模型
几何元素
形体的模型主要指的就是包含图形信息所形成的模型。
形体本身的构造有一定的层次性，低层局部组合构成上一层局部，而上一层局部组合又可以构成更高一层的局部，依此类推可形成多层结构。其中，每一层中的局部，我们把它有称为几何元素。
点
它是0维几何元素，有端点、交点、切点、孤立点等形式。
曲线、曲面的应用中会涉及到三种类型的点：
型值点 相应曲线、曲面必然经过的点。
控制点 相应曲线、曲面不一定经过的点，仅用于确定位置和形状。
插值点 在型值点之间插入的一系列点，用于提高曲线曲面的输出精度。
不同的空间中点的表示方式
一维空间中用一元组{t}表示；
二维空间中用二元组{x,y}或{x(t),y(t)}表示；
三维空间中用三元组{x,y,z}或{x(t),y(t),z(t)}表示；
点是几何造型中的最根本的元素，曲线、曲面和其它形体都可以用有序的点集描述。
用计算机存储、管理、输出形体的实质就是对点集及其连接关系的处理。
边
边是一维几何元素，是两个邻面〔正那么形体〕或多个邻面〔非正那么形体〕的交界。边分直线边和曲线边。直线边由起点和终点两端点确定；曲线边由一系列型值点或控制点表示，也可以用显示、隐式方程描述。
环
环是有序有向边〔直线段或曲线段〕组成的面的封闭边界。环中的边不能相交，相邻两条边共享一个端点。环有内外之分，确定面的最大外边界的环称之为外环，通常其边按逆时针方向排序。而把确定面中内孔或凸台边界的环称之为内环，其边相应外环排序方向相反，通常按顺时针方向排序。
面
面是二维元素，是形体上一个有限、非零的区域，它由一个外环和假设干个内环所界定。面有方向性，一般用其外法向量作为该面的正向。假设一个面的外法向量向外，此面为正；否那么，为反向面。
体
体是三维几何元素，由封闭外表围成的空间，它是欧氏空间R3中非空、有界的封闭子集，其边界是有限面的并集。在实际应用中，要求形体是正那么形体，即形体上任意一点的足够小的邻域在拓扑上应是一个等价的封闭圆。不满足上述要求的形体称为非正那么形体。存在悬面、悬边的形体是非正那么形体。
体素
体素是可以用有限个尺寸参数定位和定型的体，常有下面三种定义形式。
一组单元实体 长方体、圆柱体、圆锥体、球体。
扫描体 由参数定义的一条〔一组〕截面轮廓线沿一条〔一组〕空间参数曲线作扫描运动而产生的形体。
用代数半空间定义的形体，在此半空间中点集可定义{(x,y,z)|f(x,y,z) 0}此处的f应是不可约的多项式。
形体的层次结构
点→边→环→面→外壳→形体。
在几何造型中最根本的几何元素是点〔V〕、边(E)、面(F),这三种元素一共有九种连接关系
线框、外表及实体表示
常用的多面体表示法是三表表示法，即采用三个表:顶点表,用来存放多面体各顶点的坐标;边表,指出哪两个顶点之间有多面体的边；面表，指出哪些边围成了多面体的外表。
任意多面体容