第8章 可见面判断算法.ppt

一 计算机工程学院 真实感图形生成 三维图形消除隐藏线的处理 在前面章节中介绍了三维图形变换 从而可画出物体的轴测图 但是这种方法是将物体上的所有棱线全部画出 不能考虑物体上哪些棱线是可见的 哪些是不可见的 这就造成了表达物体的不确切性 如图a所示 作投影变换是表示的物体b呢还是物体c 2 a b c 上图所示物体还仅仅是一个单个物体 但物体往往由多个形体或在一个形体上存有不同结构组成 情况会更复杂 因此 要画出确定的立体感更强的轴测图时 利用计算机自动地判别棱线或立体表面的可见性 将那些不可见的棱线消去不画或画成虚线 这项工作称为消除隐藏线 或隐藏面 简称消隐 由于图形的表现形式不同 消隐对象也不同 对于线框图是要消除隐藏线 对于用不同灰度的表面构成的图形 是要消除隐藏面 无 3 论是消除隐藏线还是消除隐藏面 需要程序准确 可靠地判别出棱线的可见性 这不是件容易的事情 因此消隐是计算机绘图中的难点之一 本例以凸多面体为例 介绍消除隐藏线的原理 计算方法 还介绍任意平面立体的消隐方法 4 消除隐藏线的原理 一 基本概念凸多面体是由若干个平面围成的立体 而每个平面又都是由凸多边形组成 所以 若某个多边形表面是可见的 则该表面上的所有的线均可见 若某个多边形表面为不可见 则该表面上所有的线均不可见 如果画出可见面上所有的线 消去不可见面上所有的线 那么就画出了凸多面体消隐后的立体图 5 二 平面的可见性由于组成凸多面体的各个表面是由凸多边形围成的 因此我们先来讨论多边形平面的投影性质 每个平面均有其法线 如图中R平面 有法线N 当法线N确定后平面R就为有向平面 引出法线方向的面称为平面的正面 与法线相反的面 称为平面的背面 平面向某一投影面投影后 平面的可见性有以下几种情况 1 平面的正面朝着观察者 投影后平面为可见 6 N法线 R 正面 背面 2 平面的背面朝着观察者 投影后平面为不可见 3 平面垂直于投影面时 投影后平面积聚为一条线 平面视为可见 7 三 立体表面的可见性组成凸多面体的各个表面均有其法线 我们可用它的外法线来描述 所谓外法线 其方向是由物体的内部指向物体的外部 8 立体经过投影后 通常是在V面 XOY平面 输出正投影图 此时V面是投影面 则视线的反向与OY轴平行 所以外法线与OY轴的夹角反应了外法线与视线的夹角 根据这一夹角的大小 就可以判别出该法线所在的平面的可见性 有以下几种情况 1 当 90时 则平面的正面朝向观察者 该平面为可见 2 当 90时 则平面的背面朝向观察者 该平面为不可见 9 3 当 90时 则平面的正面垂直于投影面 投影积聚成一条线 该平面为可见 4 当 0时 则平面的正面平行于投影面 该平面为可见 10 消隐的计算方法 一 平面的矢量由空间解析几何可知 如有矢量a和矢量b 则它们烦人矢量积a b 必垂直于矢量a和b所决定的平面 因此矢量积a b就是矢量a和b所在平面的法矢量 法矢量的方向按右手坐标系定义 11 a b a b 对于物体的任一表面 为保证正确地得到它的外法线 我们规定 当观察者面对平面的外表面时 在该平面上以逆时针方向顺序取三个点 各点的坐标为D x1 y1 z1 E x2 y2 z2 F x3 y3 z3 根据矢量积定义平面的法矢量为N U V矢量N的方向就是平面P的外法线方向 12 13 14 真实感图形绘制流程 15 取景变换 1 5 场景坐标系场景的局部坐标系完成物体的造型场景的世界坐标系 整体坐标系 放入待绘制的场景 定义物体之间的相互位置 观察坐标系也称摄像机坐标系 或者视点坐标系完成取景变换所需建立的第一个坐标系 16 取景变换 2 5 建立观察坐标系的步骤确定观察参考点 即视点位置可以设在任何位置通常选在靠近或在物体的表面将视点位置取为视点坐标系的原点确定观察方向 即视线方向一般取深度坐标轴 即ze轴的正向为简便起见 设为总是指向场景坐标系的原点确定观察平面 即视平面位置一般取过视点且垂直于视线方向的平面 即xeye平面 17 取景变换 3 5 场景坐标系一般取右手坐标系观察坐标系通常取左手坐标系符合人们的观察习惯 18 取景变换 4 5 将物体投影到观察平面之前必须将场景坐标系中的点转换到观察坐标系中这一过程称为取景变换 也称视向变换包括平移和旋转的一系列几何变换的级联取景变换矩阵 19 取景变换 5 5 场景坐标系原点平移到视点位置E绕xe轴逆时针旋转90 绕ye轴顺时针旋转 角绕xe轴逆时针旋转 角调整x轴指向对x轴作对称变换 20 消隐算法 按实现方式不同分为两大类 景物空间 objectspace 消隐算法直接在视点坐标系中确定视点不可见的表面区域将它们表达成同原表面一致的数据结构侧重于景中各物体之间的几何关系图像空间 imagespace 消隐算法在投影屏幕上 以屏幕像素为采样单位 确定投影于每一像素的可见景物表面区域将其颜色作为该像素的显示光亮度侧重于向屏幕投影后形成的图像 21 背面剔除算法 背面剔除算法 22 隐藏面的消除 Roberts算法 1 9 Roberts算法景物空间消隐算法1963年 Roberts于MIT提出 23 隐藏面的消除 Roberts算法 2 9 基本思想消除被物体自身遮挡的边和面再用每个物体留下的边与其它物体比较适用范围凸体凹体怎么办 分解成若干凸体的组合 24 隐藏面的消除 Roberts算法 3 9 体矩阵平面方程ax by cz d 0 25 隐藏面的消除 Roberts算法 4 9 求平面方程ax by cz d 0的系数利用不共线三点坐标利用平面的法向量平面法向量 n ai bj ckd ax1 by1 cz1 利用MartinNewell方法 26 隐藏面的消除 Roberts算法 5 9 已知 S xyz1 P abcd 若S在平面上则S P 0若点S不在平面上则点积的正负号标识点在平面的哪一侧约定 若点S在体内一侧则S P 0若点S在体外一侧则S P 0 27 隐藏面的消除 Roberts算法 6 9 体矩阵不一定保证体内点都满足S P 0如何得到正确的体矩阵 对体矩阵V进行校正在体内找一试验点S若某平面方程系数P与S的点积符号为负则将该方程系数均乘以 1 28 隐藏面的消除 Roberts算法 7 9 自隐藏面的判别假设视点 位于z轴正向的无穷远处视线方向 z轴负向的无穷远点E 00 10 用E作为试验点判定一平面是自隐藏面的条件E V 0点积值为负 表示E位于这些平面的外侧 29 隐藏面的消除 Roberts算法 8 9 体内试验点 正确的体矩阵 30 隐藏面的消除 Roberts算法 9 9 用E 00 10 作为体内试验点 31 隐藏面的消除 画家算法 1 3 画家算法1972年M E Newell受画家由远至近作画的启发景物空间消隐算法 32 隐藏面的消除 画家算法 2 3 基本步骤生成深度优先级队列据视点距离远的多边形优先级低 排在队列的前端据视点距离近的多边形优先级高 排在队列的后端从队列中依次取出多边形 计算其表面光亮度写入帧缓冲器直到队列中所有多边形的光亮度都计算完毕 并写入帧缓冲器 33 隐藏面的消除 画家算法 3 3 优点 透明或半透明物体图形的动态显示飞行训练模拟器中显示飞机着陆时的情景场景中的物体是不变的 只是视点在变化只要事先把不同视点的景物的优先级队列算出再实时地采用画家算法来显示图形就可以实现图形的快速消隐与显示 34 隐藏面消除 Weiler Atherton算法 1 3 Weiler Atherton算法景物空间消隐算法基于Weiler Atherton多边形裁剪操作 35 隐藏面消除 Weiler Atherton算法 2 3 基本步骤1 深度预排序 形成景物多边形表将变换到屏幕坐标系中的景物表面按各顶点的z最小值进行排序2 当前具有最大z值的景物表面作为裁剪多边形CP深度最大 离视点最近3 用CP对景物多边形表中排在后面的表面进行裁剪产生内部多边形Pin和外部多边形Pout 36 隐藏面消除 Weiler Atherton算法 3 3 4 比较Pc与Pin的深度 检查Pc是否真正离视点最近是 则Pc为可见表面不是 则取Pin为新的Pc 重复步骤3 5 将位于Pc之外的景物表面组成外裁剪结果多边形表取表中深度最大的表面为Pc 重复步骤3 6 递归进行直到外裁剪结果多边形表为空时为止 37 隐藏面的消除 BSP树算法 1 2 BSP树算法BinarySpacePartitioning景物空间消隐算法基于BSP树 对景物表面进行二叉分类与画家算法类似 景物多边形由远至近绘制特别适合的场合场景中物体位置固定不变 仅视点移动 38 隐藏面的消除 BSP树算法 2 2 基本步骤选一剖分平面P1 将场景空间分割成两个半空间剖分结果表示为一棵BSP树叶节点 景物左分支 位于剖分平面前面的景物右分支 位于剖分平面后面的景物依据视点位置 对子空间进行分类包含视点的子空间标识为 front 另一侧子空间标识为 back 递归搜索该BSP树 优先绘制标识为 back 的子空间中所含的景物 39 隐藏面消除 深度缓冲器算法 1 8 深度缓冲器算法Depth bufferalgorithm图像空间消隐算法1975年 Catmull提出 40 隐藏面消除 深度缓冲器算法 2 8 基本思想将投影到显示屏上的每一个象素所对应的多边形表面的深度进行比较取最靠近视点的表面的属性值作为该像素的属性值用Z buffer记录该表面在该像素点的深度用frame buffer记录该表面在该像素点的颜色或亮度值 41 隐藏面消除 深度缓冲器算法 3 8 深度缓冲器帧缓冲器的扩充也称Z Buffer算法 42 隐藏面消除 深度缓冲器算法 4 8 流程 for 场景中的每一个多边形 扫描转换该多边形 for 多边形所覆盖的每一个像素点 x y 计算多边形在该像素点的深度值z x y if z x y Z buf中对应此像素点 x y 的z值 把多边形在 x y 处的深度值z x y 存入Z buf中的 x y 处 把多边形在 x y 处的亮度值存入f buf中的 x y 处 当所有的多边形都处理完后 帧缓冲器中的内容即为消除隐藏面后的图像 43 隐藏面消除 深度缓冲器算法 5 8 优点简单在象素级上以近物代替远物 易于消除隐藏面 并准确显示复杂曲面之间的交线 计算量呈线性复杂度场景中景物表面采样点的数目无需对各景物表面片作深度预排序景物表面上的可见点可按任意次序写入深度缓冲器和帧缓冲器易于硬件实现图形工作站上配置由硬件实现的深度缓冲器算法很多微型机上都装有基于深度缓冲器算法的图形加速卡 44 隐藏面消除 深度缓冲器算法 6 8 缺点需要很大的存储空间象素数目为500 500 深度值采用浮点类型 4字节 除刷新缓存外 还需500 500 4 1M字节的额外存储空间在实现反走样 处理透明和半透明等效果方面存在困难 并由此会产生巨大的处理时间开销由于在帧缓冲器内的同一象素点上可见表面的写入顺序是不确定的 所以可能导致画面上的局部错误 45 隐藏面消除 深度缓冲器算法 7 8 改进一 减少需要相对测试的多边形平面数最小最大测试 46 隐藏面消除 深度缓冲器算法 8 8 改进二 利用连贯性计算深度水平方向竖直方向 改进三 降低对存储空间的需求图像空间划分为4 16甚至更多的子正方形或条状区域在最小情况下 只对应一条扫描线的深度缓冲器扫描线相关算法 47 隐藏面的消除 扫描线相关算法 1 3 扫描线相关算法按扫描线顺序处理一帧画面在扫描平面 ZOX平面 上解决消隐问题由视点和扫描线所决定深度缓冲器算法的一维版本深度缓冲器所需的存储空间屏幕水平分辨率 每个深度值所占的存储位数 48 隐藏面的消除 for 每条扫描线 将扫描线帧缓冲器f buf置成背景色 将扫描线深度缓冲器Z buf置成最小值 for 每个多边形 求出该多边形与当前扫描线的相交区间 for 相交区间内每个象素点 x y 计算多边形在该处的深度值z if 多边形在该处的深度值z Z buf在该处的值 用多边形在该处的深度值z取代Z buf在该处的值 用多边形在该处的亮度值取代f buf在该处的值 用f buf的内容显示当前扫描线 49 隐藏面的消除 扫描线相关算法 3 3 缺点在每一个被多边形覆盖像素处需要计算深度值被多个多边形覆盖的像素需要多次计算深度值 改进在一条扫描线上 以区间为单位确定多边形的可见性 50 隐藏面的消除 Warnock算法 1 4 Warnock算法图像空间消隐算法区域的连贯性也称区域细分area subdivision实质分而治之 51 隐藏面的消除 Warnock算法 2 4 基本思想观察整个窗口区域判别窗口是否单纯窗口内无任何可见物体窗口已被一个可见面片完全充满将非单纯的窗口四等分为四个子窗口对每个子窗口再进一步判别是否是单纯的直到窗口单纯或窗口边长已缩至一个象素点为止即使1024 1024分辨率视图被细分10次后 也能使每个子窗口覆盖一个像素 52 隐藏面的消除 Warnock算法 3 4 关键步骤 判别窗口是否单纯 53 隐藏面的消除 Warnock算法 4 4 基本步骤对每个窗口判断与多边形分离仅包含一个多边形与一个多边形相交被一个多边形所包围且窗口内无其它多边形至少被一个多边形所包围 且此多边形距离视点最近否则继续细分窗口 并重复以上测试 54 光线投射算法 1 4 RayCastingAppel提出建立在几何光学基础之上对于包含曲面 特别是球面的场景效率高 55 光线投射算法 2 4 基本思想观察者之所以能看见景物光源发出的光照射到物体上的结果其中一部分光到达人的眼睛引起视觉到达观察者眼中的光由物体表面反射通过表面折射或透射若从光源出发跟踪光线则只有极少量的光能到达观察者的眼睛效率低从视点或像素出发 仅对穿过像素的光线反向跟踪当光线路径到达一个可见的不透明物体的表面时停止追踪 56 将景物通过透视投影变换到图像空间反向跟踪一条穿过像素点的光线决定它与场景中的哪一景物表面相交交点按深度排序需求出该光线与景物表面的所有可能的交点具有最大z值的交点对应的面就是屏幕上该像素对应的可见面离视点最近该像素处的显示值由相应物体的属性决定对屏幕上所有像素都进行如上处理后 算法结束 假设视点位于z轴正向投影平面 屏幕