区域子分割算法
窗口与多边形的覆盖关系
内含、相交、包围和分离
区域子分割算法
下列情况之一发生时，窗口足够简单，可 以直接显示
所ቤተ መጻሕፍቲ ባይዱ多边形均与窗口分离。该窗口置背景色 只有一个多边形与窗口相交，或该多边形包含 窗口，则先整个窗口置背景色，在对多边形在 窗口内部分扫描线算法绘制。 有一个多边形包围了窗口，或窗口与多个多边 形相交，但有一个多边形包围窗口，而且在最 前面最靠近观察点。
区域子分割算法
算法实现
假设全屏幕窗口分辨率为1024×1024。窗口以 左下角点（x，y）和边宽s定义。下图为使用 栈结构实现的区域子分割算法流图。由于算法 中每次递归的把窗口分割成四个与原窗口相似 的小窗口，故这种算法通常称为四叉树算法。
区域子分割算法
算法实现
光线投射算法
光线投射算法
考察由视点出发穿过观察屏幕的一象素而射入 场景的一条射线，则可确定出场景中与该射线 相交的物体。在计算出光线与物体表面的交点 之后，离象素最近的交点的所在面片的颜色为 该象素的颜色；如果没有交点，说明没有多边 形的投影覆盖此象素，用背景色显示它即可。
光线投射算法
算法描述
for（屏幕上的每一象素） { 形成通过该屏幕象素(u,v)的射线；
第九章、可见面判别算法
什么是可见面判别算法
在生成真实感图形时，从某一具体的位置观察， 空间中那些面是可见的，那些面是不可见的。 用于判断可见面与隐藏面的算法通常称为可见 面判别算法，也称为消隐算法。
常见消隐算法
图像空间消隐算法 景物空间消隐算法
第九章、消隐
图像空间消隐算法
图像空间（屏幕坐标系）消隐算法以屏幕像素 为采样单位，确定投影于每一像素的可见景物 表面区域，并将其颜色作为该像素的显示颜色。
深度缓存器算法
原理
先将待处理的景物表面上的采样点变换到图像 空间（屏幕坐标系），计算其深度值，并根据 采样点在屏幕上的投影位置，将其深度值与已 存贮在Z缓存器中相应像素处的原可见点的深 度值进行比较。如果新的采样点的深度（z值） 大于原可见点的深度，表明新的采样点遮住了 原可见点，则用该采样点处的颜色值更新帧缓 存器中相应像素的颜色值，同时用其深度值更 新Z缓存器中的深度值；否则，不做更改。
LOGO
区域子分割算法
区域子分割算法
区域子分割算法的基本思想是：把物体 投影到全屏幕窗口上，然后递归分割窗 口，直到窗口内目标足够简单，可以显 示为止。首先，该算法把初始窗口取作 屏幕坐标系的矩形，将场景中的多边形 投影到窗口内。如果窗口内没有物体则 按背景色显示；若窗口内只有一个面， 则把该面显示出来。否则，窗口内含有 两个以上的面，则把窗口等分成四个子 窗口。对每个小窗口再做上述同样的处 理。这样反复地进行下去。如果到某个 时刻，窗口仅有象素那么大，而窗口内 仍有两个以上的面，这时不必再分割， 只要取窗口内最近的可见面的颜色或所 有可见面的平均颜色作为该象素的值。
区间扫描线算法
扫描线与多边形的投影相交得到若干子区间
(a)两个平面在屏幕上的投影 (b)无贯穿的情形 (c) 相互贯穿的情形
区间扫描线算法
算法步骤
小区间上没有任何多边形，如[a4,a5]，这时该小区间 用背景色显示。 小区间上只有一个多边形，如[a1,a2][a5,a6]这时可以 对应多边形在该处的颜色显示。 小区间上存在两个或两个以上的多边,形如[a6,a7]，必 须通过深度测试判断哪个多边形可见。若允许物体表 面相互贯穿时，还必须求出它们在扫描平面(ZX平面) 的交点。用这些交点把该小区间分成更小的子区间(称 为间隔)，在这些间隔上决定哪个多边形可见。如将 [a2,a3]区间分成[a2,b][b,a3]两个子区间。为了确定某 间隔内那一多边形可见，可在间隔内任取一采样点(如 间隔中点)，分析该点处哪个多边形离视点最近，该多 边形即是在该间隔内可见的多边形。
for（场景中的每个物体）
将射线与该物体求交； If （存在交点） 以最近的交点所属的颜色显示象素(u,v) else 以背景色显示象素(u,v) }
光线投射算法
光线投射算法与Z缓冲器算法相比，它们 仅仅是内外循环颠倒了一下顺序，所以它 们的算法复杂度类似。区别在于光线投射 算法不需要Z缓冲器。为了提高本算法的效 率可以使用包围盒技术，空间分割技术以 及物体的层次表示方法等来加速。
深度缓存器算法
优缺点
优点，法原理简单，复杂度为O(N)，N为物体 表面采样点的数目，便于硬件实现。 缺点，占用存储单元多，它在实现反走样、透 明和半透明等效果方面的困难。同时，在处理 透明或半透明效果时，深度缓存器算法在每个 像素点处只能找到一个可见面，即它无法处理 多个多边形的累计颜色值。
景物空间消隐算法
景物空间消隐算法直接在景物空间（观察坐标 系）中确定视点不可见的表面区域，并将它们 表达成同原表面一致的数据结构。
第九章、消隐
图像空间消隐算法
深度缓存器算法 A缓存器算法 区间扫描线算法
景物空间消隐算法
BSP算法 多边形区域排序算法
介于二者之间
深度排序算法 区域细分算法 光线投射算法
深度缓存器算法
深度缓存器算法
深度缓存器算法最早由Catmull提出，是一种 典型的，也是最简单的图像空间面消隐算法， 但其所需的存储容量较大，不仅要有帧缓存器 来存放每个像素的颜色值，还需要有深度缓存 器来存放画面上每一像素对应的可见表面采样 点的深度值。由于通常选择z轴的负向为观察 方向，因此算法沿着观察系统的z轴来计算各 景物距离观察平面的深度，故该算法也称为Zbuffer算法。
区间扫描线算法
区间扫描线算法
每一条扫描线被空间中多边形的边界在屏幕的 投影分割成若干相互邻接的子区间，每一子区 间上只有一个可见面。因此，只要在每一个子 区间内任一点处，在投影于该处的各多边形中 找出在该处深度（z值）最大的多边形（最近 的多边形），则这一多边形为该扫描线子区间 内的唯一可见面，可按这一多边形的光照属性 和几何位置计算确定子区间内各像素的显示颜 色。这就是所谓的区间扫描线算法。区间扫描 线算法也是一种图像空间消隐算法。