opengl算法学习---消隐

图形系统

图形生成
应用程序:顶点
帧缓存:像素
每个顶点与每个像素都要处理

图形系统实现的两种策略

基于对象空间

基于图像空间

图形绘制系统四阶段

建模->几何处理->光栅化->片元处理

建模：
定义几何对象的顶点数据库

几何处理：
投影、图元装配、裁剪、着色
作用于顶点数据

光栅化：
像素赋颜色
扫描转换
视口变换
屏幕坐标

片元处理
片元赋颜色
隐藏面消除
纹理颜色

消隐

当将三维场景投影到二维平面的时候，需要确定哪些多边形是可见的，哪些是不可见的
消隐:消除被遮挡的不可见的线或面
未经消隐的图形存在的问题：杂乱，二义性

后向面消除

外法向:每个多边形指向物体外部的法向量
前向面:外法向与视线方向夹角为钝角
后向面:外法向与视线方向夹角为锐角

Z-Buffer算法

绘制物体时，每一个所生成像素的深度即z坐标，保存在一个缓冲区中，称为z缓冲区或深度缓冲区
Z缓冲区中的单元与屏幕像素单元一一对应
如果场景中另外一个物体也在同一个像素生成渲染结果，绘制系统就会比较二者的深度，保留距离视点较近的物体。然后将这个所保留的深度保存到深度缓冲区中根据深度缓冲区可正确地实现较近的物体遮挡较远的物体

帧缓冲器一保存各像素颜色值
Z缓冲器一保存各像素处物体深度值
z缓冲器中的单元与帧缓冲器中的单元一一对应

算法思路

当要显示某个点时，首先检查该点处的深度值是否大于该像素对应的深度值
如果大于，说明当前点更靠近视点，用它的颜色替换像素原来的颜色
否则说明当前像素处，当前点被前面所绘制的点遮挡，不可见，像素颜色值不改变

伪代码

1）初始化:
depthBuffer(x,y)=最小值(最远深度)
frameBuffer(x, y)=I背景
2)消隐绘制:
    for(每一个多边形)
        for(该多边形所覆盖的每个像素(x, y))
            计算该多边形在该像素的深度值z(x, y);
        if(z(x, y)>depthBuffer(x, y))
        {depthBuffer(x, y)=z，
            frameBuffer(x, y)=I(x, y)}

计算采样点(x, y)的深度z (x, y)

假定多边形的平面方程为:Ax+By+Cz+D=Oo

扫描线上所有后继点的深度值

当处理下一条扫描线y=y-1时，该扫描线上与多边形相交的最左边(x最小)交点的X值可以利用上一条扫描线上的最左边的X值计算:

深度信息

利用透视变换中伪深度

问题

当深度值比较小时，深度比较常会产生错误
当深度值比较小时，真实深度值上的一个小变化映射到伪深度值后变为极小的变化
两个接近的深度值有可能会被映射为相同的伪深度值，这可能会在深度比较时导致错误
因此需要使用更多的位来表示伪深度值24位或32位

优缺点

z缓冲器算法在像素级上以近物取代远物，与形体在屏幕上的出现顺序无关
优点: 1)简单稳定，利于硬件实现
2)不需要整个场景的几何数据
缺点: 1)需要一个额外的z缓冲器
2)在每个多边形占据的每个像素处都要计算深度值，计算量大

扫描线Z-buffer算法

Z缓冲器算法中所需要的z缓冲器容量较大，为克服这个缺点可以将整个绘图区域分割成若干个小区域
按区域显示，这样z缓冲器的单元数只要等于一个区域内像素的个数就可以
如果将小区域取成屏幕上的扫描线，就得到扫描线z缓冲器算法

将窗口分割成扫描线

画家算法

画家首先绘制距离较远的场景，然后用绘制距离较近的场景覆盖较远的部分
首先将场景中的多边形根据深度进行排序，然后按照顺序进行绘制
这样可自然解决可见性问题

下列情况无法正确排序
1.多边形循环遮挡 2.多边形相互穿透

解决办法:分割成两个

算法思想

1)先把屏幕置成背景色
2)先将场景中的物体按其距观察点的远近进行排序，结果放在一张线性表中;(线性表构造:距观察点远的称优先级低，放在表头;距观察点近的称优先级高，放在表尾。该表称为深度优先级表)
3)然后按照从远到近(从表头到表尾)的顺序逐个绘制物体。

算法步骤

一种针对多边形的排序算法如下:
Step 1：将场景中所有多边形存入一个线性表，记为L;
Step 2：如果L中仅有一个多边形，算法结束;否则根据每个多边形的Zmin对它们预排序。不妨假定多边形P落在表首，即Zmin (P)为最小。再记Q为L一{P}(表中其余多边形)中任意一个;
Step 3：判别P，Q之间的关系，有如下二种:
(1):对所有的Q，有Zmax(P) < Zmin(Q）则多边形P的确距观察点最远，它不可能遮挡别的多边形。返回第二步
(2) 存在某一个多边形Q，使Zmax (P)>Zmin(Q)，需进一步判别

2 利用包围盒排序
A)若P, Q的投影P‘，Q‘的包围盒不相交(图a)，则P,Q表中的次序不重要，令L= L- {P},返回step 2;否则进行下一步
B)若P的所有顶点位于Q所在平面的不可见的一侧(图b)则P, Q关系正确，令L= L- {P}，返回step 2;否则进行下一步
c)若Q的所有顶点位于P所在平面的可见的一侧(图C），则P, Q关系正确，令L=L-{P}，返回step 2;否则进行下一步
D)对P, Q投影P‘，Q‘求交，若P‘，Q‘不相交(图d)，则P, Q在表中的次序不重要，令L=L-{P}，返回step 2;否则在它们所相交的区域中任取一点，计算P, Q在该点的深度值，如果P的深度小，则P, Q关系正确，令L=L-{P}，返回step 2;否则交换P, Q，返回step 3.

包围盒技术

应用一避免盲目求交
定义:一个形体的包围盒指的是包围它的简单形体。
一个好的包围盒要具有两个条件:
包围盒充分紧密包围着形体;
对其的测试比较简单。

分析

深度排序计算量大
遇到多边形相交，或多边形循环重叠的情形，还必须分割多边形
画家算法的这些缺陷导致了深度缓冲技术的发展

光线跟踪算法

将通过绘图窗口内每一个像素的投影线与场景中的所有多边形求交
如果有交点，用深度值最大的交点(最近的)所属的多边形的颜色显示相应的像素
如果没有交点，说明没有多边形的投影覆盖此像素，用背景色显示即可

算法原理

算法描述

1.通过视点和投影平面(显示屏幕)上的所有像素点作一入射线，形成投影线。
2.将任一投影线与场景中的所有多边形求交。
3.若有交点，则将所有交点按z值的大小进行排序，取出最近交点所属多边形的颜色;若没有交点，则取出背景的颜色。
4.将该射线穿过的像素点置为取出的颜色。

伪代码

for(图像中的每条扫描线)
      for(扫描线上的每个像素)
      { 确定从投影中心穿过像素的投影线;
        for(场景中每一个多边形)
              将投影线与多边形求交;
        if(有交点)
              以最近交点所属多边形的颜色显示该像素
        else
              以背景色显示该像素
      }

消隐问题分析

与观察对象有关:消隐目标
与视点有关:消隐判断标准
消隐依据:三维坐标
消隐结果:二维坐标
以视点为标准将对象按空间位置远近进行排序

解决方案

先三维排序，再绘制二维->画家算法
二维绘制，同时依据三维判定可见性->Z-Buffer算法

物体空间消隐:以场景物体各个面为处理单元
将场景物体各个面与其它面比较，确定其可见性
设场景中有k个多边形，显示区域为m*n个像素,则物体空间消隐运算量与k有关

图像空间消隐:以投影平面上各像素为处理单元
对投影平面上各像素，确定距视点最近物体，以该物体表面颜色来显示像素
设场景中有k个多边形，显示区域为m*n个像素，则图像空间消隐运算量与k n m有关