内那一多边形可见,可在间隔内任取一采样点(如间隔中点),分析该点处哪个多边形离视点最近,该多边形 即是在该间隔内可见的多边形 27.3.5区域子分割算法( karnack算法) 区域子分割算法的基本思想是:把物体投影到全屏幕窗口上,然后递归分割窗口,直到窗口内目标 足够简单,可以显示为止。首先,该算法把初始窗口取作屏幕坐标系的矩形,将场景中的多边形投影 到窗口内。如果窗口内没有物体则按背景色显示;若窗口内只有一个面,则把该面显示出来。否则, 窗口内含有两个以上的面,则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反 复地进行下去。如果到某个时刻,窗口仅有象素那么大,而窗口内仍有两个以上的面,这时不必再分 割,只要取窗口内最近的可见面的颜色或所有可见面的平均颜色作为该象素的值 图2.7.22区域子分的过程 窗口与多边形的覆盖关系有四种:内含、相交包围和分离。如图所示。 图2.7.23(a)内含(b)多边形与窗口相交(c)包围(d)窗口和多边形分离 下列情况之一发生时,窗口足够简单,可以直接显示: (1)所有多边形均与窗口分离。该窗口置背景色 (2)只有一个多边形与窗口相交,或该多边形包含窗口,则先整个窗口置背景色,在对多边形在窗口内 部分扫描线算法绘制。 (3)有一个多边形包围了窗口,或窗口与多个多边形相交,但有一个多边形包围窗口,而且在最前面最 靠近观察点。 假设全屏幕窗口分辨率为1024×1024。窗口以左下角点(x,y)和边宽s定义。下图为使用栈结构 实现的区域子分割算法流图。由于算法中每次递归的把窗口分割成四个与原窗口相似的小窗口,故这 种算法通常称为四叉树算法。 全屏幕窗口(40,1024)压入堆 从栈中出窗口(xys 检查口与物体的盖系 内目标简单 呈示口内目[呈示象京][=2 杷窗口分四 个于窗口入 (x+s,7,s) zz+s, s) (+s, y+s, s)内那一多边形可见，可在间隔内任取一采样点（如间隔中点），分析该点处哪个多边形离视点最近，该多边形 即是在该间隔内可见的多边形。 2.7.3.5 区域子分割算法 (Warnack 算法) 区域子分割算法的基本思想是：把物体投影到全屏幕窗口上，然后递归分割窗口，直到窗口内目标 足够简单，可以显示为止。首先，该算法把初始窗口取作屏幕坐标系的矩形，将场景中的多边形投影 到窗口内。如果窗口内没有物体则按背景色显示；若窗口内只有一个面，则把该面显示出来。否则， 窗口内含有两个以上的面，则把窗口等分成四个子窗口。对每个小窗口再做上述同样的处理。这样反 复地进行下去。如果到某个时刻，窗口仅有象素那么大，而窗口内仍有两个以上的面，这时不必再分 割，只要取窗口内最近的可见面的颜色或所有可见面的平均颜色作为该象素的值。 图 2.7.22 区域子分的过程 窗口与多边形的覆盖关系有四种：内含、相交包围和分离。如图所示。 图 2.7.23 (a)内含 (b)多边形与窗口相交(c)包围 (d)窗口和多边形分离 下列情况之一发生时，窗口足够简单，可以直接显示： (1)所有多边形均与窗口分离。该窗口置背景色 (2)只有一个多边形与窗口相交，或该多边形包含窗口，则先整个窗口置背景色，在对多边形在窗口内 部分扫描线算法绘制。 (3)有一个多边形包围了窗口，或窗口与多个多边形相交，但有一个多边形包围窗口，而且在最前面最 靠近观察点。 假设全屏幕窗口分辨率为 1024×1024。窗口以左下角点（x，y）和边宽 s 定义。下图为使用栈结构 实现的区域子分割算法流图。由于算法中每次递归的把窗口分割成四个与原窗口相似的小窗口，故这 种算法通常称为四叉树算法