计算机图形学 形体的表示

33
Байду номын сангаас
• 边(Edge) 边是一维几何元素，是两个邻面（正则形体） 或多个邻面（非正则形体）的交界。
正则形体中，不允许存在孤立边。
23
✓ 一对四式四叉树
每个结点有五个字段，其中四个字段用来 描述该结点的四个子结点的状态，另一个结点 存放指向子结点记录存放处的指针。这里要求 四个子结点对应的记录是依次连续存放的。
24
一个记录和一个结点对应，记录中描述的是四个 子结点的状态，指针给出的是四个子结点所对应记录 的存放处，这里还隐含地假定了子结点记录存放的次 序。这样对某个不是最后一层的某子结点，即使它已 经是叶结点，因而是不必要的，却也必须占据位置使 不会错误地存取其它同辈结点的记录。这使得存贮空 间仍然可能有浪费。
17
18
常用的三种表示四叉树的存储结构： ✓ 规则方式——规则四叉树 ✓ 线性方式——线性四叉树 ✓ 一对四方式——一对四式四叉树
19
✓ 规则四叉树
用五个字段的记录表示树中的每个结点， 其中一个用来描述结点的特性，即是灰、黑、 白三类结点中的哪一种;其余四个用于存放指向 四个子结点的指针。这是最普遍使用的表示树 形数据的存储结构方式，在早期将四叉树用于 图形显示或处理时常被采用。 缺点:大量的存储空间被指针所占用。
要计算交点个数，只要明确求出有多少次良性相 交。对可能性相交，分别计算与其两子树的良性相交 次数，然后以其和为交点个数。这时可递归进行，可 能一直进行到树叶一层才结束。
14
实践表明用带树方法表示曲线对提高计算 效率是有帮助的。另外两个带树对并、交等运 算是封闭的，与用象素阵列来表示图形的方法 比较节省空间需求。因此这种方法在许多领域 得到了广泛的应用。
5
设要表示的曲线是由经过适当选取已确定的一组 离散点P0，P1，…，Pn序列给出，则生成表示曲线的 分辨率为w0的带树的算法，可简略描述如下： 1.找出由起点P0，终点Pn确定的矩形带段，其中包含P0 至Pn的全部点，构造此矩形带段的对应结点并令为根。 2.找出P0至Pn之间距离连线P0Pn为最远的点Pk，然后对 P0至Pk和Pk至Pn这两组点分别做与步1中相同的构造矩 形带段及对应结点的操作，产生的两个结点，分别是 根的左右子结点。 3.反复执行上述操作，直到所产生结点的w=wl+wr≤w0。 这样的结点是叶结点。
几何信息描述形体的位置及大小。 拓扑信息描述形体各部分的数目及相互间
的连接关系。
30
形体往往有多个基本的部分（几何元素） 通过相应的连接组合而成，这也为复杂形体的 构造提供了一种基本的方法，由多个简单形体 组合形成较复杂的形体。形体本身的构造有一 定的层次性，低层部分组合构成上一层部分， 而上一层部分组合又可以构成更高一层的部分， 依次类推可形成多层结构。其中，每一层中的 部分，我们把它有称为几何元素。
9
10
判断两个矩形带段相互位置关系是三种可 能中哪一种的算法不难写出，设已有了这样的 算法。再设表示要求交的两曲线的带树己构造 得足够精确，因此在树叶一层，来自不同带树 的矩形带段或是不相交或是良性相交，而没有 可能性相交出现。这时，判断两树T1和T2表示 的两条曲线是否相交的算法，可以简略叙述如 下:
1
引入坐标系后，形体的图形信息就可以用数学方 法来表示。例如第四章讨论过的对曲线和曲面的处理， 已经广泛地应用于表示二维和三维图形的边界和表面。 还有很多其它的表示方法。各种不同的表示方法是针 对不同应用问题的需要而提出来的。不论选择什么表 示方法，有两点是必须考虑的。 第一是这种方法的覆盖域，即用该方法能定义形体范 围的大小。覆盖域大，则所设计出图形系统的造型能 力就强。 第二是该表示法蕴含信息的完整性，即由这种表示法 所决定的数据结构是否唯一地描述了一个实在的形体。
第六章 形体的表示及其数据结构
为了用计算机显示空间的任意形体及进行必要的图 形操作，需要解决如何组织和存放有关信息，使计算 机处理起来速度快，省空间，这就是形体的表示及数 据结构问题。 与空间任意形体有关的信息可以分为： 1. 图形信息指构成它们的点、线、面的位置，相互关 系及大小等； 2. 非图形信息指形体的颜色、亮度、质量、体积等一 些性质。 图形信息包括： 1. 几何信息：形体在空间的位置和大小； 2. 拓扑信息：组成形体各部分的数目及相互间的连接 关系。
3.1 若两个检查的结果都是不相交，则认为所表示曲线 不相交；
3.2 若两个检查中有一个是良性相交，则认为所表示曲 线相交；
3.3 若不是上述两情形，即出现可能性相交，则对可能 性相交的两个矩形带段中面积较大者，取其对应结点 的两个子结点，如此进行可直到树叶那一层。
12
这里只是简略地叙述了是否相交的判别。 经适当修改，这个算法可以计算求出包含交点 的区域。并且还可以做到在求得区域足够小时 再结束算法。当然，要求越精确，计算花费也 要增加。
8
➢ 两条用带树表示的曲线如何求交
利用带树求交，在较低分辨率就能满足要 求时，可以用较少的计算确定出包含交点的小 区域。注意到两个矩形带段S1和S2的位置关系 有如下三种: (1)不相交。 (2)良性相交，即S1的与起点至终点连线平行 的两条边都与S2相交，S2的与起点至终点连线 平行的两条边也都与S1相交。 (3)可能性相交，这时不是良性相交，但也不是 不相交。
01000000 4 321
27
四叉树表示的优点(与象素阵列表示相比)：
✓ 四叉树表示在存贮空间方面显然有很大节省。 ✓ 从图形的象素阵列求得四叉树表示，及从四叉树 表示恢复为象素阵列，都可以写出算法使之方便地 实现。 ✓ 四叉树是一种分层的表示方式，不同的层次对应 不同的分辨率，因此为按不同精确程度的图形显示 提供了很好的数据结构。 ✓ 四叉树做为一种与设备无关的图形表示，可以经 适当的转换在不同的设备上显示。
15
二、 平面图形的四叉树表示方法 假定一个平面图形是黑白的二值图形，
即组成图形象素阵列的仅有黑色象素值1，白 色象素值0，可以设表现图形的象素阵列由 2n×2n个象素组成，因若不然可补充上一定数 量的行与列的背景色象素值使满足所述要求。
16
表示图形的四叉树结构可以如下形成：设图形已 包括在2n×2n的正方形中，这个正方形是四叉树的根结 点。若图形整个地占据这个正方形，则图形就用该正 方形表示，否则将该正方形均分为四个小正方形，每 个小正方形边长为原正方形边长的一半，它们是根结 点的四个子结点，可编号为0，1，2，3。 再考查每个小正方形，若整个被图形占据，则标记相 应结点为1，可称为黑结点。若整个与图形不相交，则 标记相应结点为0，可称为白结点。若不是上述两情形， 即与图形部分相交，则称相应结点是灰结点并将其一 分为四。当再分生成小正方形边长达到一个象素单位 时，再分终止，此时一般应将仍是灰结点的改为黑结 点，如此形成了平面图形的四叉树表示。
因此尽管这种方式自然简单，容易被人接 受，但在存储空间利用率方面太差，所以使用 不多。
20
✓ 线性四叉树
考虑如何提高空间利用率。为此，它以某 一预先确定的次序遍历四叉树，例如以深度第 一的方式，将四叉树结构转换成一个线性表结 构，表中每个元素与一个结点对应。对结点的 描述可以多一些。
21
例：对前面图中所示四叉树，按上面想法转换 成线性四叉树如下：
此外还应该考虑表示方法是否简洁，是否提供了 便利的用户接口来支持系统的各项应用等等。
2
形体的表示方法通常可分为两类： 1. 边界表示：用边界将形体分为内部和外部。
例如曲线曲面； 2. 空间分区表示：描述形体的内部性质，将包
含形体的空间区域划分为一组小的非重叠的 连续实体。例如四叉树和八叉树。
3
第一节 二维形体的表示
13
➢ 如何确定一点是否在一封闭曲线内部
所使用的准则是：如果一点在区域之内，则从该 点引出的任一射线与区域的边界相交的次数为奇数， 否则就在区域外。这里要注意避免所引射线恰与曲线 相切的情形，为此一般可以多试几个不同方向的射线。 这样问题转化为前面刚刚讨论过的判别两曲线相交问 题，只是其中一条是射线，可用一棵宽度为零的带树 来表示。
一、二维图形的边界表示
用曲线表示二维图形的边界是很常见的。 由于曲线的复杂程度不同，应用中的环境不同， 要实施的操作及允许使用的计算资源也可能不 同，所以应当有多种多样的表示法。这一节讨 论带树法。
4
带树法 带树是一棵二叉树，树的每个结点对应一个矩形带 段，这样每个结点可由八个字段组成，前六个字段 描述矩形带段，后二个是指向两个子结点的指针， 即矩形带段的起点是(xb,yb)，终点是(xe,ye)。相对从 起点到终点的连线，矩形有两边与之平行，两边与 之垂直，平行两边与之距离分别为wl和wr。
28
第二节 三维几何模型
一、 几何元素
描述形体的信息包括结构、性质和行为等 多方面的信息，即图形信息和非图形信息。在 图形处理过程中是通过对包含有这些相关信息 的模型进行操作，最终得到需要的结果。模型 是根据图形处理的需要而建立起来的，它究竟 包含哪些形体信息比较合适取决于用户的需要。
29
图形信息代表着形体的结构及外观，它在 图形处理过程中是不可缺少的成分。 图形信息包括几何信息和拓扑信息
RA’abcdBCD’efgh 其中R表示根，字母右上角加’表示是灰结点， 其它描述没有标出。每个结点可以用固定个数 的字段，使得可以在内存中以紧凑的方式表示 出来，可以不用或用很少的指针。
22
这种方法节省存储空间，对一些运算也比 较方便，但也丧失了一些灵活性。例如为了存 取属于原图形右下角的子图形，那么必须先遍 历了其余三个子图形对应的所有结点后才能进 行。不能方便地以其它遍历方式对树的结点进 行存取，导致许多与此相关的运算效率很低。
32
在不同的空间中点有不同的表示方式： 一维空间：用一元组{t}表示； 二维空间：用二元组{x,y}或{x(t),y(t)}表示； 三维空间：用三元组{x,y,z}或{x(t),y(t),z(t)}表