计算机图形学·25 消隐2 区域子分算法-光线投射算法

本文为记录专业课计算机图形学的部分笔记，参考教材为Angel的第八版交互式计算机图形学——基于WebGL 2.0的自顶向下方法。

1、区域子分算法的由来：①Z缓存器算法，将像素孤立来考虑，未利用相邻像素之间存在的属性的连贯性，即区域的连贯性，所以算法效率不高；②区间扫描线Z缓存器算法仅利用了扫描线的连贯性。实际上，可见多边形至少覆盖了绘图窗内的一块区域，如果能将这类区域找出来，则避免了在每个像素处计算深度值，消隐问题也就解决了。
基本思路：
首先，将场景中的多边形投影到绘图窗口内（假设它为边长为k的正方形）
然后，判断窗口/多边形关系是否足够简单：
若是足够简单，则按简单关系来处理，并且算法结束；
否则将窗口进一步分为四块（左上，右上，左下，右下）。对此四个小窗口重复上述过程，直到窗口仅为一个像素大小。
此时可能有多个多边形覆盖了该像素，计算它们的深度值，以最靠近观察点的颜色显示该像素即可。

何谓“窗口/多边形关系足够简单？”
存在下列情况之一，即可称为窗口/多边形关系足够简单：
①窗口为空，即多边形与窗口的关系是分离的——取背景色，图中（a）
②窗口仅内含一个多边形，或者一个多边形与窗口相交——此时先对多边形投影进行裁剪，再对裁剪结果进行分别上色，图中（b）和（c）
③有一个多边形的投影包围了窗口，并且它是最靠近观察点的——，以该多边形颜色上色，图中（d）

如何判别多边形与窗口的分离与包围关系？可以使用例如编码方法——区域编码：多边形顶点的编码/多边形边的编码/多边形的编码。
2、光线投射算法（Ray casting）基本思路：
①将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交。
②如果有交点，用深度值z最大 (视点最近/小的) 的交点所属的多边形的颜色显示相应的像素；
③如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示即可。