计算机图形学 消隐PPT课件

第11课隐藏了吗？基本概念？提高冲裁算法效率的一般方法是什么？画家算法？z缓冲区算法？扫描线z缓冲区算法？区域子分割算法？光源投影算法，基本概念，生成逼真度的方法之一：在三维场景中删除相互阻挡关系面和删除线曲面模型和线框模型对象曲面：平面和曲面面删除对象：由平面多边形组成的多面体，基本概念，剔除算法的分类1)类：窗口中的每个像素作为处理单元；For(窗口中的每个像素)确定距视点最近的对象，用该对象曲面的颜色显示像素2)类：场景中的对象作为处理单位；For(场景中的每个对象)与场景中的其他对象相比，确定曲面的可见部分；显示对象曲面的可见部分。，基本概念，算法复杂性假定场景中有k个对象，每个对象曲面平均由h个多边形组成，显示区域中有xn个像素，则第一个算法的复杂性如下：O(mnkh)第二种算法的复杂性为O(kh)*(kh)，提高剔除算法效率的常用方法，使用一致性将透视投影转换为平行投影边界框技术背面剔除空间分割技术对象层次表示，提高消隐算法效率的一般方法1，利用一致对象一致性表面的一致性区域一致性扫描线的一致性深度一致性，提高消隐算法效率的一般方法2，将透视投影消除平行投影与透视之间的紧密关系实施(1)，消除必须在投影之前进行；2)物体之间的遮挡与投影中心(视点)的选择相关；3)对象之间的阻挡关系与投影方法有关，提高去除算法效率的一般方法3，添加图12.3面去除步骤的三维图形显示流程图p285(参见图8.30p162)图12.4首先将透视投影转换为平行投影，从南面去除p285(参见图8.33p167)。(避免除法，提高效率)，提高去除算法效率的一般方法4，定义边界框技术：一种形式的边界框意味着围绕它的简单形状。例如，该技术通常用于避免盲目交叉考试。各种事物之间的比较等。好的边界框要具备两个条件。包围的和紧紧地包围的；对它的测试比较简单。示例：使用矩形连接和长方体连接提高算法效率.提高剔除算法效率的常用方法5，背面剔除外部法线和投影方向(观察方向)之间的角度前后面(背面)剔除标准：对象曲面闭合，背面始终遮挡在前面，因此始终不可见。提高移除算法效率的常用方法6，空间分割技术标准：场景中的对象，其投影在投影平面上是否有重叠部分？有互阻的可能性吗？)对于完全没有相互阻挡关系的对象，应避免进行这些不必要的测试。方法：将投影平面上的窗拆分为多个较小的区域。针对每个小区域，为具有相交部分的表内的对象创建表。从小区域判断那个物体可见的时候，比较一下该区域相关物体表中的物体就可以了。提高移除算法效率的常用方法6，比较复杂性：假设每个小区域的相关对象表中平均有h个对象，场景中有k个对象，则显然h比k小得多，因为场景中的对象分布很分散。第二种剔除方法表明，算法的复杂性为O(h*h)，比O(k*k)小得多。提高剔除算法效率的一般方法7，对象层次表示：模型转换的树表示原理：减少场景中的对象数，从而降低算法复杂性。如何：如果将父节点表示的对象视为子节点表示的对象的边界框，并且两个父节点之间没有阻挡关系，则无需对这两个子节点执行其他测试。父节点之间的阻挡关系可以通过两者之间的边界框进行预测。，画家算法，起源：画家的绘图顺序暗示了绘画对象之间相互遮挡关系算法的基本思想：1)首先按距视点的距离对场景中的对象进行排序，然后将结果放在一个线性表中；(定线表格规划：远离观测点的标称优先度较低，放置在标头中；将接近观测点的高优先级放置在表末尾。此表格称为深度优先顺序表格。(2)然后从表头到底部依次绘制一个对象。画家算法，核心：如何按深度(近)排列场景中的对象以设置深度优先级表？多边形的排序算法如下：在标准化投影坐标系uvn中，n坐标非常接近观察者，因为投影方向是n轴的负方向。记住多边形P的每个顶点n坐标的最小值和最大值nmin(P)nmax(P)。算法：画家算法Step1:将场景中所有多边形都写为l的线性表(连接的表或数组)中。如果Step2: l只有一个多边形，算法将终止。否则，将根据每个多边形的nmin预先对齐。假设多边形P位于表格的开头，则nmin(P)最小。q是l p (表格中剩馀的多边形)之一。Step3:将P、Q之间的关系分为以下两种：step3.1:对所有Q都有nmax(P)nmin(Q)，需要进一步确定。如果step3.2.1 P，Q投影P，Q 的边界框彼此不相交，则P，Q在表中不重要，因此返回l=l P ，step2。否则，请继续下一步。如果Step3.2.2 p的所有顶点都位于Q所在平面的不可见一侧，则l=l P 返回step2，因为P，Q关系正确。否则，请继续下一步。如果Step3.2.3 q的所有顶点都位于P所在平面的可见一侧，则返回l=l P ，step2，因为P，Q关系正确。否则，请继续下一步。Step3.2.4与P，Q投影P ，Q 相交，并且P ，Q 不相交，则表中P，Q的顺序并不重要，因此返回l=l P ，step2。否则，在相交区域的任意点计算P，Q的深度值，如果P的深度小，则P，Q关系正确，因此将l=l P 返回到step2。否则，交换P，Q，返回step3。无法处理此算法。多边形循环阻挡多边形互穿解决方案：分为两个，z缓冲区算法，来源：帧缓冲区存储每个像素颜色值z缓冲区-存储每个像素的对象深度值z缓冲区中的单元与帧缓冲区中的单元一一对应。首先，将z缓冲区中单元格的初始值设置为-1(主体的最小n值，具体取决于规范)。要更改像素的颜色值，首先要确保当前多边形的深度值大于该像素的原始深度值(存储在该像素的“z缓冲区”单元中的值)，如果大于，则当前多边形将更接近观察点，并将像素的原始颜色替换为该颜色。否则，这意味着当前多边形在当前像素中被前面绘制的多边形遮挡，不可见，像素的颜色值保持不变。z缓冲区算法，算法说明：for(v=0；VZ缓冲区的第一个(u，v)单位值帧缓冲区的第一个(u，v)单位值是当前多边形颜色。设置z缓冲区的第一个(u，v)单位值为d。，Z缓冲区算法，优点：简单、可靠，适合硬件实现：1)需要额外的Z缓冲区2)计算每个多边形占用的每个像素的深度值，大计算，扫描线z缓冲区算法，来源：如果z缓冲区算法所需的z缓冲区容量较大，为了克服这一缺点，可以将整个绘图区域划分为较小的区域，然后再划分为一个区域，这样z缓冲区中的单元数等于一个区域内的像素数。如果把小区域带到屏幕上的扫描线，就会得到扫描线z缓冲区算法。扫描线z缓冲区算法，算法描述for(v=0；VZ缓冲区中的u单位值)帧缓冲区中的u，v单位值是当前多边形颜色。设定z缓冲区的u单位值为d。，本地子分割算法，来源：z缓冲算法和扫描线z缓冲算法都隔离像素，不利用相邻像素之间存在的属性的一致性，即区域的一致性，因此算法效率不高。实际可见的多边形至少复盖了图形窗口中的一个区域。如果可以找到这些区域，则无需计算每个像素的深度值，从而解决了隐藏问题。区域子分割算法，算法基本思路：首先将场景中的多边形投影到绘图窗口(假定角长度为k的正方形)，以确保窗口足够简单；算法结束后：否则，将窗口进一步分为四个块(左上、右上、左下、右下)。对这四个小窗口重复此操作，直到窗口大小为一个像素。在这种情况下，可以使用多个多边形复盖像素，计算深度值，并将其显示为最近的颜色。区域子算法，窗口够简单吗？1)窗口为空。也就是说，多边形与窗的关系被分离。2)窗口中只有一个多边形。也就是说，一个多边形与窗口的关系是包含还是相交。多边形投影在填充修剪结果之前被修剪。3)围绕窗口的多边形的投影距离使用该多边形颜色填充窗口的观察点最近。如何确定区域子分割算法，多边形与窗的分离和边界关系？编码方法