《第7章消除隐藏线和隐藏面.ppt》由会员分享，可在线阅读，更多相关《第7章消除隐藏线和隐藏面.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章第七章 消除隐藏线和隐藏面的算法消除隐藏线和隐藏面的算法 给出一个三维形体，要画出确定的立给出一个三维形体，要画出确定的立体感强的投影视图，必须决定形体上哪些体感强的投影视图，必须决定形体上哪些线线或哪些或哪些面面是是不可见不可见的，不可见的部分不的，不可见的部分不显示，这就是显示，这就是消除隐藏线与隐藏面消除隐藏线与隐藏面的问题。的问题。1?2哪些部分是不可见的，与观察位置有哪些部分是不可见的，与观察位置有关。对某个确定的视点，需要确定遮挡关关。对某个确定的视点，需要确定遮挡关系。系。面消隐面消隐：当采用面模型显示物体时，：当采用面模型显示物体时，确确定可见面，消除场景中物体的不可见面
2、，定可见面，消除场景中物体的不可见面，即消除隐藏面。即消除隐藏面。线消隐线消隐：当：当显示采用线框模型表示的物显示采用线框模型表示的物体时，要消除不可见的线，即隐藏线的消体时，要消除不可见的线，即隐藏线的消除。除。3确定可见性的基本思想非常简单，但用确定可见性的基本思想非常简单，但用计算机程序实现时，一般要涉及到相当复杂计算机程序实现时，一般要涉及到相当复杂的计算。针对不同的需要，提出了各种不同的计算。针对不同的需要，提出了各种不同的算法。的算法。假设：三维形体表示为假设：三维形体表示为多边形多边形表面形成的集表面形成的集合，投影约定为沿着合，投影约定为沿着z轴正向的轴正向的正交正交投影投影消
3、除隐藏面算法：消除隐藏面算法：图象空间算法（图象空间算法（ImageSpaceMethods）客体空间算法客体空间算法（ObjectSpaceMethods）4图象空间算法图象空间算法对显示设备上每一个可分对显示设备上每一个可分辨辨象素象素进行判断，看组成物体的多个多进行判断，看组成物体的多个多边形表面中哪一个在该象素上可见，即边形表面中哪一个在该象素上可见，即要对每一象素检查所有的表面。要对每一象素检查所有的表面。客体空间算法客体空间算法把注意力集中在分析要显把注意力集中在分析要显示示形体形体各部分之间的关系上，这种算法各部分之间的关系上，这种算法对每一个组成形体的表面，都要与其它对每一个组
4、成形体的表面，都要与其它各表面进行比较，以便消去不可见的面各表面进行比较，以便消去不可见的面或面的不可见部分。每步比较都可能涉或面的不可见部分。每步比较都可能涉及较多的计算。及较多的计算。5第一节第一节 线面比较法消除隐藏线线面比较法消除隐藏线 多面体的面可见性多面体的面可见性 凸多面体的可见面就是朝向观察位凸多面体的可见面就是朝向观察位置的面。置的面。设观察方向由设观察方向由指向观察位置指向观察位置的一个的一个方向向量方向向量k给出，所考查的面的外法向给出，所考查的面的外法向量是量是n，则这两个向量的夹角为则这两个向量的夹角为。若若0 /2时，所考查面是可见的，时，所考查面是可见的，否则就是
5、不可见的。否则就是不可见的。67设设 则则若分子为若分子为正正，则，则 ,面为可见；面为可见；若分子为若分子为负负，则，则 ，面为不可见；，面为不可见；若分子为若分子为零零，则，则 ，此面退化为线。，此面退化为线。8 例：设空间有一个四面体，顶点例：设空间有一个四面体，顶点A，B，C，D的坐标依次是的坐标依次是(0,0,0)，(2,0,1)，(4,0,0)，(3,2,1)。从。从z轴正向无穷远处轴正向无穷远处观察，求各面的可见性。观察，求各面的可见性。观察方向向量是观察方向向量是k=(0,0,1)，三角面，三角面DAB的法向量是：的法向量是：9 面面DAB为可见面。类似计算可知，面为可见面。类
6、似计算可知，面DBC是可见面，面是可见面，面ADC是不可见面，面是不可见面，面ACB退化为线。退化为线。10 利用外法线就可以判断凸多面体上各利用外法线就可以判断凸多面体上各表面的可见性，由此就能解决对单个凸多表面的可见性，由此就能解决对单个凸多面体的隐藏线和隐藏面的消除问题。面体的隐藏线和隐藏面的消除问题。对于一个凸多面体对于一个凸多面体，若某个面可见。，若某个面可见。则该面上所有线均可见，若某个面不可见则该面上所有线均可见，若某个面不可见,则该面轮廓线以外的线都不可见。于是判则该面轮廓线以外的线都不可见。于是判断出可见面，只显示可见面及与之有关的断出可见面，只显示可见面及与之有关的线段，就
7、画出了消隐后的图形。这个方法线段，就画出了消隐后的图形。这个方法只适用于单个凸多面体。只适用于单个凸多面体。11对于非凸多面体或多个形体对于非凸多面体或多个形体，这个，这个方法通常做为预处理步骤，即先使用这方法通常做为预处理步骤，即先使用这个方法排除往后不必考虑的不可见面。个方法排除往后不必考虑的不可见面。只考虑选出的只考虑选出的可能可见面可能可见面中哪些是可见中哪些是可见或部分可见的。或部分可见的。消除隐藏线的线面比较法的第一步消除隐藏线的线面比较法的第一步就是利用外法线就是利用外法线判断出所有可能的可见判断出所有可能的可见面面，可能可见面上的线段是可能可见线。，可能可见面上的线段是可能可见
8、线。再再依次用每一条可能可见线，与每一个依次用每一条可能可见线，与每一个可能可见面比较可能可见面比较，从而确定出可见线、，从而确定出可见线、隐藏线及可见线上的隐藏部分。隐藏线及可见线上的隐藏部分。12可能可见线和可能可见面的比较可能可见线和可能可见面的比较范围检查范围检查显然，如果不发生遮挡，就必定不显然，如果不发生遮挡，就必定不是隐藏线。可以通过简单的范围检查发是隐藏线。可以通过简单的范围检查发现这类情况，以避免往后不必要的现这类情况，以避免往后不必要的Z方方向的深度比较。向的深度比较。13一个多边形表面的投影范围一个多边形表面的投影范围 14如图所示，多边形表面如图所示，多边形表面ABCD
9、在在ZV=0平面上的正投影是平面上的正投影是ABCD，包含，包含ABCD且四边分别平行于且四边分别平行于XV和和YV轴的轴的最小矩形最小矩形PQRS就是就是ABCD的范围，找的范围，找出出PQRS的方法被称为的方法被称为包围盒方法包围盒方法。范围检查也称为范围检查也称为最大最小检验最大最小检验，即通，即通过比较有关的最大或最小值来判定范围的过比较有关的最大或最小值来判定范围的交迭情形。交迭情形。15空间任一线段，只有其投影与多边形表面空间任一线段，只有其投影与多边形表面的的投影范围发生交迭投影范围发生交迭时，才可能与多边形表面时，才可能与多边形表面有遮档关系。有遮档关系。16 按按xv方向对投
10、影范围的检查，可分别方向对投影范围的检查，可分别计算出投影线段和多边形表面计算出投影线段和多边形表面投影范围投影范围x坐坐标的最大值和最小值，设分别是标的最大值和最小值，设分别是 若若xmax1xmin2或者或者xmax2xmin1，线段和，线段和多边形表面就必然没有遮挡关系。多边形表面就必然没有遮挡关系。yv方向也可以类似地做范围检查，可方向也可以类似地做范围检查，可以避免消除隐藏面时很多不必要的深度比以避免消除隐藏面时很多不必要的深度比较。较。1718z zv v方向的范围检查（深度检验）方向的范围检查（深度检验）粗略的深度检验粗略的深度检验 在此范围检查中若线段的最大在此范围检查中若线段
11、的最大z坐标坐标zmax1小于多边形表面最小的小于多边形表面最小的z坐标坐标zmin2，则，则线段完全在表面前面，根本不发生遮挡现线段完全在表面前面，根本不发生遮挡现象，可以不必再往下做精确的深度检验。象，可以不必再往下做精确的深度检验。19 精确深度检验精确深度检验设空间一条线段设空间一条线段P1P2和一个平面多边形和一个平面多边形表面如图所示，过线段两端表面如图所示，过线段两端P1，P2各做一条各做一条与与zv轴平行的直线轴平行的直线l1和和l2，这两条直线与平面，这两条直线与平面相交于点相交于点P1，P2，为直线两端点在平，为直线两端点在平面上的投影点。显然两组对应点面上的投影点。显然两
12、组对应点P1和和P1，P2和和P2的的xv坐标和坐标和yv坐标相同，比较坐标相同，比较zv坐坐标：标：若若z1z1且且z2z2，则线段不会被遮挡；，则线段不会被遮挡；若若z1z1且且z2z2，则线段有可能被遮，则线段有可能被遮挡，还需要做进一步检查。挡，还需要做进一步检查。2021如果不是上述两种情况，必发生线如果不是上述两种情况，必发生线段与表面相交。可以用求直线与平面交段与表面相交。可以用求直线与平面交点的方法点的方法求出交点求出交点，显然这时被交点分，显然这时被交点分开而得到的两条线段，恰好分别属于前开而得到的两条线段，恰好分别属于前面说明的两种情形。面说明的两种情形。22 直线直线l1
13、 1的参数方程：的参数方程：x=x1，y=y1，z=z1+t，代入平面方程得：代入平面方程得：求交点求交点平面方程：平面方程：解得：解得：若若t0则则z1z1，若，若t0则则z1z1。23进一步检查进一步检查这时要对平面遮挡了线段的哪些部分这时要对平面遮挡了线段的哪些部分做精确的计算。做精确的计算。24检查出某一段子线段是否可见检查出某一段子线段是否可见取子线段上任意一点，若这点在多取子线段上任意一点，若这点在多边形表面各边线的投影所形成的封闭多边形表面各边线的投影所形成的封闭多边形内，这子线段就不可见，否则就可边形内，这子线段就不可见，否则就可见。见。25 空间一条线段可能被一个多边形表面遮
14、挡的消除隐藏空间一条线段可能被一个多边形表面遮挡的消除隐藏线的算法的步骤如下：线的算法的步骤如下：xv方向和方向和yv方向的方向的范围检查范围检查；若不能判断，则接着做若不能判断，则接着做zv方向的范围检查即方向的范围检查即粗略的粗略的深度比较深度比较；若还不能判断就再进行若还不能判断就再进行精确的深度比较精确的深度比较；计算线段两端点在可能遮挡它的平面上的计算线段两端点在可能遮挡它的平面上的投影点投影点，比较相应的比较相应的z坐标。这时可能出现线段与平面相交，坐标。这时可能出现线段与平面相交，需要需要求交点求交点，交点把线段分成两部分。，交点把线段分成两部分。对确实被平面遮挡的部分做精确计算
15、，求出线段对确实被平面遮挡的部分做精确计算，求出线段的投影与遮挡平面上多边形表面边框投影的所有的投影与遮挡平面上多边形表面边框投影的所有交交点点，这些交点把线段的投影分成可见和不可见的一，这些交点把线段的投影分成可见和不可见的一些子线段。对些子线段。对子线段子线段的可见性，先取上面一点做点的可见性，先取上面一点做点的的包含性包含性检验来进行判断。检验来进行判断。26考虑一条线段被考虑一条线段被多个多个多边形表面遮挡而产多边形表面遮挡而产生需要解决的消除隐藏线情况时，可依次判断生需要解决的消除隐藏线情况时，可依次判断被每个多边形表面遮挡产生的隐藏部分。只要被每个多边形表面遮挡产生的隐藏部分。只要
16、被每一个多边形都不能遮挡的公共部分才需要被每一个多边形都不能遮挡的公共部分才需要显示。显示。27第二节第二节曲面隐藏线消除的浮动水平线算法曲面隐藏线消除的浮动水平线算法 这种曲面也可以由这种曲面也可以由和和两族曲线来表示。隐藏线消除就是要去掉这两两族曲线来表示。隐藏线消除就是要去掉这两族曲线中被遮挡的部分。族曲线中被遮挡的部分。曲面方程曲面方程2829设设平面平面 是最靠近观察者的，从平面是最靠近观察者的，从平面 上的曲线上的曲线 开始，对水平方向每个象开始，对水平方向每个象素的对应素的对应x坐标值坐标值，计算，计算一个比较简单的方法：一个比较简单的方法：先考虑对应先考虑对应的一族曲线的消隐算
17、的一族曲线的消隐算法。如果图形显示器在水平方向有法。如果图形显示器在水平方向有M个像素，个像素，则建立则建立M个内存单元个内存单元yu(j)，称为上浮水平线数，称为上浮水平线数组，在这些单元中先放上初值，初值应取成小组，在这些单元中先放上初值，初值应取成小于于。30 若若 ，则点，则点 是可见是可见点，并把点，并把 内容成内容成 。若。若 ，则，则 为不可见，就不改变为不可见，就不改变 的内容。的内容。对对平面上的曲线完成上述工作平面上的曲线完成上述工作后，再对平面后，再对平面上的曲线重复上述上的曲线重复上述工作，这样按工作，这样按z值递减方向一条一条曲线值递减方向一条一条曲线处理过去，就得到
18、一组消除隐藏线的曲处理过去，就得到一组消除隐藏线的曲线族了。线族了。31 图图c c点附近的线虚部分应是可见的，但按上点附近的线虚部分应是可见的，但按上述算法却成了不可见了。为了解决这个问题，述算法却成了不可见了。为了解决这个问题，可另建立可另建立M M个单元个单元 ，可称之为下浮水平线，可称之为下浮水平线数组。数组。C32 初值取成初值取成 或比这更大一或比这更大一点的数，每次求出点的数，每次求出 若若则则为可见，并如下修改相应的值为可见，并如下修改相应的值33 如果函数如果函数 是用离散点形式是用离散点形式 给出，则可如下处给出，则可如下处理。这时的理。这时的 单元个数不是由显示单元个数不
19、是由显示器在器在x x方向的象素个数来定，而是根据给定方向的象素个数来定，而是根据给定的离散点在的离散点在x x方向的个数来定。方向的个数来定。基本想法是用线性插值法所得直线来代基本想法是用线性插值法所得直线来代替两个点之间的曲线。替两个点之间的曲线。34 若上述判断结果为若上述判断结果为 均为均为不可见，则认为平面不可见，则认为平面 上的从上的从 的一段曲线为不可见。若两点均为可见，则用的一段曲线为不可见。若两点均为可见，则用这两点的连线代替原来这两点之间的曲线，并这两点的连线代替原来这两点之间的曲线，并认为可见的，若这两点中有一点可见，如图的认为可见的，若这两点中有一点可见，如图的A A点
20、，另一点则为不可见，如图中的点，另一点则为不可见，如图中的B B点，这时要点，这时要求出求出ABAB连线和连线和CDCD连线的交点连线的交点E E。AEAE部分为可见，部分为可见，EBEB为不可见为不可见。35 一般用一般用 两族曲线来表示一两族曲线来表示一曲面时常用斜投影。曲面时常用斜投影。为了得到消隐后曲面表示，不能对两族曲为了得到消隐后曲面表示，不能对两族曲线分别消隐再叠加在一起，正确的做法是对两线分别消隐再叠加在一起，正确的做法是对两族曲线一起做，即处理好平面族曲线一起做，即处理好平面 上上 一段曲线后，马上处理一段曲线后，马上处理 平面上平面上 的一段曲线，的一段曲线，对这两族曲线用
21、公共的对这两族曲线用公共的和和消隐消隐。3637第三节第三节 深度排序算法深度排序算法 深度排序算法的主要步骤：深度排序算法的主要步骤：1.把把所所有有的的多多边边形形按按顶顶点点最最大大z坐坐标标值值进进行排序。行排序。2.解解决决当当多多边边形形z范范围围发发生生交交迭迭时时出出现现的的不明确问题。不明确问题。3.按最大按最大z坐标值逐渐减小的次序，对每坐标值逐渐减小的次序，对每个多边形进行扫描转换。个多边形进行扫描转换。38 算法的基本思想是按多边形离观察算法的基本思想是按多边形离观察位置的位置的距离距离进行排序，然后按照进行排序，然后按照距离减距离减小小的次序，把每个多边形内部点应有的
22、的次序，把每个多边形内部点应有的象素值送入帧缓存存贮器中。象素值送入帧缓存存贮器中。算法考查多边形的深度次序是在客算法考查多边形的深度次序是在客体空间中进行，图形显示时覆盖步骤是体空间中进行，图形显示时覆盖步骤是在图象空间中实现，所以是一个在图象空间中实现，所以是一个客体空客体空间和图象空间间和图象空间的混合算法。的混合算法。3940不明确问题检验方法不明确问题检验方法 所有多边形按顶点最大所有多边形按顶点最大z坐标值排坐标值排序后得到一个排序表，设序后得到一个排序表，设P是排在表中是排在表中最后的那个多边形。在把最后的那个多边形。在把P扫描转换送扫描转换送入更新缓冲存贮器中之前，必须对在入更
23、新缓冲存贮器中之前，必须对在z坐标范围与其发生交迭的每个多边形进坐标范围与其发生交迭的每个多边形进行检查。行检查。设设Q是排在是排在P前面并且前面并且z坐标范坐标范围与其发生交迭的一个多边形，对围与其发生交迭的一个多边形，对Q与与P的次序关系进行检查。的次序关系进行检查。41检查可以按下面列出的五个步骤进行，每检查可以按下面列出的五个步骤进行，每个步骤判断一种情况。各步骤实现检查的复杂个步骤判断一种情况。各步骤实现检查的复杂程度逐渐增加，只要某一个步骤成功，就可以程度逐渐增加，只要某一个步骤成功，就可以立即结束检查。立即结束检查。1.多边形的多边形的x坐标范围不相交迭，所以多边形不坐标范围不相
24、交迭，所以多边形不相交迭。相交迭。2.多边形的多边形的y坐标范围不相交迭，所以多边形不坐标范围不相交迭，所以多边形不相交迭。相交迭。3.P整个在整个在Q远离观察点的一侧。远离观察点的一侧。4.Q整个在整个在P的靠近观察点的一侧。的靠近观察点的一侧。5.多边形在多边形在z=0平面上的投影本身不相交迭。平面上的投影本身不相交迭。42图图7-13第三步检查为真第三步检查为真图图7-14第三步检查为假，第三步检查为假，第四步为真第四步为真PQ第五步检查为真第五步检查为真43 如果所有这五步检查都为假，就假定如果所有这五步检查都为假，就假定P是遮挡了是遮挡了Q，交换交换P和和Q在排序表中的位置。重新进行
25、上述的五步在排序表中的位置。重新进行上述的五步检查。检查。如果仍做交换，算法会永远循环下去而没有结如果仍做交换，算法会永远循环下去而没有结果。果。为了避免循环，可以做一个限制。当做过首次五为了避免循环，可以做一个限制。当做过首次五步检查后，发生某个多边形被移到排序表的末尾时，步检查后，发生某个多边形被移到排序表的末尾时，就立即加上一个标记，以后就不能再做移动。出现再就立即加上一个标记，以后就不能再做移动。出现再次应该移动时，次应该移动时，用一个多边形所在的平面，把另一个用一个多边形所在的平面，把另一个多边形剪裁分为两个多边形剪裁分为两个。在对某个多边形一分为二完成。在对某个多边形一分为二完成后
26、，把原来的多边形舍弃，把得到的两个新多边形按后，把原来的多边形舍弃，把得到的两个新多边形按深度次序插入到原来的排序表中，然后就可以再开始深度次序插入到原来的排序表中，然后就可以再开始五步检查，算法和以前一样进行下去。五步检查，算法和以前一样进行下去。44PQ45该算法可以应用于对隐藏边的消除。该算法可以应用于对隐藏边的消除。将更新缓冲器全部用某个象素值将更新缓冲器全部用某个象素值v0加以初加以初始化，然后每次对一个多边形做扫描转换始化，然后每次对一个多边形做扫描转换时，都将其边界置为需要的不同于时，都将其边界置为需要的不同于v0的某的某个象素值个象素值v1，将其内部置为原来的象素值，将其内部置
27、为原来的象素值v0。这样，先被扫描转换的某个多边形，。这样，先被扫描转换的某个多边形，如果与后扫描转换的某个新的多边形发生如果与后扫描转换的某个新的多边形发生交迭，原多边形边的被遮挡部分将被新多交迭，原多边形边的被遮挡部分将被新多边形填充的内部值边形填充的内部值v0所湮没，从而实现了所湮没，从而实现了隐藏线的消除。隐藏线的消除。46第四节第四节画家算法画家算法 画家算法又称深度优先级表法，它是深度排序算画家算法又称深度优先级表法，它是深度排序算法的一种具体实现。法的一种具体实现。这种方法是先把屏幕置成背景色，再把物体的各这种方法是先把屏幕置成背景色，再把物体的各个面按其离视点的远近进行排序。离
28、视点远者在表头，个面按其离视点的远近进行排序。离视点远者在表头，离视点近者在表尾，构成深度优先级表。然后，从表离视点近者在表尾，构成深度优先级表。然后，从表头至表尾逐个取出多边形，投影到屏幕上，显示多边头至表尾逐个取出多边形，投影到屏幕上，显示多边形所包含的实心区域。由于后显示的图形取代先显示形所包含的实心区域。由于后显示的图形取代先显示的画面，而后显示的图形所代表的面离视点更近，所的画面，而后显示的图形所代表的面离视点更近，所以，由远及近地绘制各面，就相当于清除隐藏面。这以，由远及近地绘制各面，就相当于清除隐藏面。这与油画家作画的过程类似，先画远景，再画中景，最与油画家作画的过程类似，先画远
29、景，再画中景，最后画近景。由于这个原因，此算法习惯上称作画家算后画近景。由于这个原因，此算法习惯上称作画家算法或油画算法。法或油画算法。47 首先介绍数据文件的格式，然后介绍程序所使用首先介绍数据文件的格式，然后介绍程序所使用的数据结构，再接着介绍程序的算法流程图，最后对的数据结构，再接着介绍程序的算法流程图，最后对个别子程序功能作一些解释。个别子程序功能作一些解释。物体采用边界表示模式存储。数据文件由若干三物体采用边界表示模式存储。数据文件由若干三元组和若干四元组组成。三元组表示物体顶点的坐标。元组和若干四元组组成。三元组表示物体顶点的坐标。四元组表示物体的某个面由那些顶点构成，每个面顶四元
30、组表示物体的某个面由那些顶点构成，每个面顶点个数都是点个数都是4 4个。如图个。如图7.157.15所示，为一个立方体的数所示，为一个立方体的数据文件。据文件。边界表示：边界表示：三元组表示物体顶点的坐标。三元组表示物体顶点的坐标。四元组表示物体的某个面由哪些顶点构成，每个面四元组表示物体的某个面由哪些顶点构成，每个面顶点个数都是顶点个数都是4个。个。488100110111101000010011001612342673658751484378562149 程序中所使用的数据结构包括：程序中所使用的数据结构包括：点记录点记录(vertex)、面记录、面记录(patch)和排序数组。和排序数组
31、。点记录由五个域构成：其中，三个域用于存点记录由五个域构成：其中，三个域用于存储点的空间坐标，另外两个域用于存储点的投储点的空间坐标，另外两个域用于存储点的投影（屏幕）坐标。影（屏幕）坐标。面记录由四个域组成，每个域存放对应的顶面记录由四个域组成，每个域存放对应的顶点号。点号。排序数组的每个元素有两个域，其中一个域排序数组的每个元素有两个域，其中一个域存放面与视点的距离，另一个域存放该面的面存放面与视点的距离，另一个域存放该面的面号。号。50ReadkeyboardReadkeyboard：打打开开物物体体的的边边界界表表示示数数据据文文件件，从从键键盘盘读读进进旋旋转转角角和和透透视视角角，
32、物物体体表表面面的颜色参数（色彩和饱和度），光源方向。的颜色参数（色彩和饱和度），光源方向。VerticesVertices：读读进进顶顶点点的的空空间间坐坐标标，计计算算物物体体的的包包围围球球半半径径，把把物物体体缩缩小小到到单单位位球球中中去，计算物体各顶点在屏幕上的投影坐标去，计算物体各顶点在屏幕上的投影坐标。开始开始51PatchesPatches：读读进进面面定定义义数数据据，求求出出各各面面与与视视点点的的距距离离，把把面面号号与与距距离离放放进进排排序序数数组组。然然后后以以面面与与视视点点的的距距离离为为参参照照值值，对对数数组组进进行行排排序。序。GmodeGmode：使使
33、终终端端进进入入图图形形状状态态，设备参数初始化设备参数初始化SetpenSetpen：建立查色表建立查色表52PaintingPainting：从从排排好好序序的的数数组组中中依依次次取取出出一一面面号号，计计算算对对应应面面的的法法向向量量，再再计计算算该该面面的的光光强，然后显示该面。强，然后显示该面。AmodeAmode：终端返回文字状态。终端返回文字状态。结束结束53第五节第五节z 缓冲算法缓冲算法 z 缓冲算法缓冲算法(深度缓冲算法深度缓冲算法)是一种最简是一种最简单的图象空间算法。单的图象空间算法。对每一个点，这个算法不仅需要有一个对每一个点，这个算法不仅需要有一个更更新缓冲器新
34、缓冲器存储各点的象素值，而且还需要有一存储各点的象素值，而且还需要有一个个z 缓冲存储器缓冲存储器存储相应的存储相应的z值。帧缓冲存储值。帧缓冲存储器初始化为背景值，器初始化为背景值，z缓冲存储器初始化为可缓冲存储器初始化为可以表示的最大以表示的最大z值。值。对每一个多边形，对每一个多边形，不必不必进行深度排序算法进行深度排序算法要求的要求的初始排序初始排序，立即就可以逐个进行扫描转，立即就可以逐个进行扫描转换。换。54在扫描转换时，对每个多边形内部的任意点在扫描转换时，对每个多边形内部的任意点（x,y），实施如下步骤：），实施如下步骤：1.计算在点计算在点(x,y)处多边形的深度值处多边形的
35、深度值z(x,y)。2.如果计算所得的如果计算所得的z(x,y)值，小于在值，小于在z 缓冲存缓冲存储器中点储器中点 x y 处记录的深度值，那么就做：处记录的深度值，那么就做：1)把值把值z x y 送入送入z 缓冲存储器的点处。缓冲存储器的点处。2)把多边形在深度把多边形在深度z(x y 处应有的象素处应有的象素值，送入更新缓冲存储器的点值，送入更新缓冲存储器的点 x y 处。处。55 算法中算法中深度计算深度计算，可通过多边形的，可通过多边形的顶点坐标求出所在平面的方程，然后再顶点坐标求出所在平面的方程，然后再使用平面方程，对每个点使用平面方程，对每个点 x x y y，解出相解出相应的
36、应的z z。平面方程平面方程 ，解出解出 是：是：56则在点（则在点（x+x,y）处的深度值就是处的深度值就是设在点（设在点（x,y）处的深度值是）处的深度值是z1:57z 缓冲算法的工作流程：缓冲算法的工作流程：帧缓冲区置成背景色；帧缓冲区置成背景色；z 缓冲区置成最缓冲区置成最大大z值；值；for(各个多边形各个多边形)扫描转换该多边形；扫描转换该多边形；for(计算多边形所覆盖的每个象素（计算多边形所覆盖的每个象素（x,y）)计算多边形在该象素的深度值计算多边形在该象素的深度值Z(x,y)；if(Z(x,y)小于小于Z缓冲区中的缓冲区中的(x,y)处的值处的值)把把Z(x,y)存入存入Z
37、缓冲区中的缓冲区中的(x,y)处；处；把多边形在把多边形在(x,y)处的亮度值存入帧缓存区处的亮度值存入帧缓存区的的(x,y)处；处；58第六节第六节 扫描线算法扫描线算法 扫扫描描线线算算法法是是图图像像空空间间算算法法，它它建建立立图图像像是是通通过过每每次次处处理理一一条条扫扫描描线线来来完完成成的的。这这个个算算法法是是第第二二章章讨讨论论的的多多边边形形填填充充的的扫扫描描线线算算法法的的推推广广。在在多多边边形形填填充充的的扫扫描描线线算算法法中中，只只是是对对一一个个多多边边形形做做扫扫描描转转换换，而这里是而这里是同时对多个多边形同时对多个多边形做扫描转换。做扫描转换。59 首
38、先首先建立一个建立一个边表边表ET。ET中各登记项按中各登记项按边的较小的边的较小的y坐标递增排列；每一登记项下的坐标递增排列；每一登记项下的“吊桶吊桶”，按所记，按所记x坐标递增排列。坐标递增排列。“吊桶吊桶”中各项的内容依次是：中各项的内容依次是：1.与较小的与较小的y坐标对应的端点的坐标对应的端点的x坐标坐标xmin。2.边的另一端点的较大的边的另一端点的较大的y坐标坐标ymax。3.x的增量的增量x，它实际上是边的斜率的倒数，它实际上是边的斜率的倒数，是从一条扫描线走到下一条扫描线时，按是从一条扫描线走到下一条扫描线时，按x方方向递增的步长。向递增的步长。4.边所属多边形的标记。边所属
39、多边形的标记。60 ABCDEF两个多边两个多边形在形在z zv v=0=0平面上的平面上的投影投影 设有两个空间的三角形设有两个空间的三角形ABC、DEF,各各顶点的坐标依次是顶点的坐标依次是（1,1,10）,（2,5,10）,（5,3,10）,（3,4,5）,（4,6,5）,（6,2,5）。）。61两个多边形建立的两个多边形建立的“吊桶吊桶”已排序的边表已排序的边表 62还还需要一个需要一个多边形表多边形表PT(polygonTable)，其中，其中要包含下列信息：要包含下列信息：每个多边形所在平面方程的系数。在需要比较每个多边形所在平面方程的系数。在需要比较深度时，要通过所在（深度时，要
40、通过所在（x,y），根据平面方程解），根据平面方程解出深度出深度z。每个多边形的亮度或颜色值。实际做扫描转换每个多边形的亮度或颜色值。实际做扫描转换时应用。时应用。一个一个“进入进入退出退出”标志，初值为标志，初值为“假假”。在。在扫描转换处理时，用以标记扫描线对该多边形扫描转换处理时，用以标记扫描线对该多边形是是“进入进入”，还是，还是“退出退出”。63操作通过一个活动边表操作通过一个活动边表AET进行。进行。64 通通过过以以上上的的讨讨论论，可可以以写写出出整整个个扫扫描描线算法实施的步骤：线算法实施的步骤：首首先先正正确确形形成成边边表表ET和和多多边边形形表表PT之之后后，然然后后实
41、实施施步步骤骤与与第第二二章章叙叙述述的的多多边边形形填填充充的的扫扫描描线线算算法法的的实实施施步步骤骤基基本本相相同同，只只是是需需要要把把那那里里的的步步骤骤：在在扫扫描描线线y上上，按按照照AET表表提提供供的的x坐坐标标对对，用用color实实施施填充修改加细如下：填充修改加细如下：651将将实实施施扫扫描描转转换换时时遍遍查查AET表表中中各各“吊吊桶桶”的的指指针针i初初始始置置为为1，扫扫描描线线正正在在多多少少个个多多边边形形内内的的累累计计数数值值s初初始始置置为为零零，将将活活动动多多边边形形表表，即即扫扫描描线线正正在在通通过过的的多多边边形形按按深深度度递递增增次次序
42、序排排列列而而形形成成的的表表，记记为为P，初始置为空。，初始置为空。2设设第第i个个“吊吊桶桶”记记录录的的相相应应多多边边形形是是A。若若A的的“进进入入/退退出出”标标记记FA为为“假假”，则则改改FA为为“真真”，将将A加加到到表表P的的前前面面，s增增加加1。否否则则，FA即即为为“真真”，则则改改FA为为“假假”，将，将P中的中的A去掉，去掉，s减少减少1。66 3若若s=0，则到则到5。（这时扫描线不在。（这时扫描线不在任何多边形内，正通过背景，不必做扫任何多边形内，正通过背景，不必做扫描转换。）描转换。）若若s=1，则到则到4。（这时扫描线只在一个。（这时扫描线只在一个多边形内
43、，不必做深度比较，去做扫描多边形内，不必做深度比较，去做扫描转换。）转换。）若前面两个判断都为若前面两个判断都为“假假”，扫描线至，扫描线至少在两个多边形内，应做深度比较。对少在两个多边形内，应做深度比较。对表表P前面两个多边形做深度比较，比较前面两个多边形做深度比较，比较后放回应保证后放回应保证P表中的多边形按深度递表中的多边形按深度递增的次序。增的次序。674对第对第i个和第个和第i+1个个“吊桶吊桶”存有的存有的x坐标指示的扫描线上的一段，按照坐标指示的扫描线上的一段，按照P表表最前面多边形指示的亮度或颜色，实施最前面多边形指示的亮度或颜色，实施扫描转换。扫描转换。5i增加增加1，若，若
44、i所指已无所指已无“吊桶吊桶”，步骤，步骤结束，去下一步骤结束，去下一步骤(删除删除y=ymax的边的边;x=x+dx;排序；排序；y=y+1;将将ET中中y对应的对应的各吊桶加入各吊桶加入AET)。否则，回到步骤。否则，回到步骤2。6869 i is s P PPTPT表表FABC FDEFFABC FDEF 说明说明 1 11 1(ABC(ABC)truetrue1 1 到到3 3填填ABCABC的亮度或颜色值的亮度或颜色值 2 22 2(DEF,(DEF,ABC)ABC)truetrue在在步步骤骤3 3发发生生深深度度比比较较，比比较较结结果果DEFDEF更靠近观察者，它仍在更靠近观察
45、者，它仍在P P表前面，表前面，3 3到到3 3 填填DEFDEF的亮度或颜色值的亮度或颜色值 3 31 1(DEF(DEF)falsefalse3 3 到到5 5填填DEFDEF的亮度或颜色值的亮度或颜色值 4 40 0()false70 如果按照步骤如果按照步骤3的条件决定是否做深度比的条件决定是否做深度比较，会有许多深度比较是不必要的。例如，假较，会有许多深度比较是不必要的。例如，假定有一个大的多边形定有一个大的多边形GHIJ在两个三角形在两个三角形ABC和和DEF的后面。在扫描线的后面。在扫描线y=离开边离开边CB时，按时，按步骤步骤3的条件判断，扫描线还同时在的条件判断，扫描线还同时
46、在DEF和和GHIJ中，应该做深度比较，但是在大多数可以中，应该做深度比较，但是在大多数可以假定假定没有多边形穿透另一个多边形的情况下没有多边形穿透另一个多边形的情况下，DEF和和GHIJ的深度关系并没有变化，深度比较的深度关系并没有变化，深度比较是不必要的。是不必要的。所以，如果扫描线从一个所以，如果扫描线从一个被遮挡被遮挡的多边形的多边形中走出，深度比较将是中走出，深度比较将是不必要的；不必要的；扫描线从一扫描线从一个个遮挡遮挡了其它多边形的多边形中走出，深度比了其它多边形的多边形中走出，深度比较才可能较才可能必要。必要。71三个多边形三个多边形72 事实上前面给出的算法基本步骤没有很事实
47、上前面给出的算法基本步骤没有很好地利用深度的相关性。深度相关性是指多好地利用深度的相关性。深度相关性是指多个多边形之间的深度关系，常常对于一组相个多边形之间的深度关系，常常对于一组相邻的扫描线来说是不变化的。如果在某条扫邻的扫描线来说是不变化的。如果在某条扫描线上，在描线上，在AET表中保存的边及次序关系，表中保存的边及次序关系，与在前面一条扫描线上时完全相同，那么深与在前面一条扫描线上时完全相同，那么深度关系就不会变化，深度比较也就并不必要度关系就不会变化，深度比较也就并不必要了。了。7374 75背景的处理背景的处理:最简单的办法最简单的办法是把更新缓冲存储器整个是把更新缓冲存储器整个初始
48、化为某个合适的值，于是算法就只需初始化为某个合适的值，于是算法就只需处理扫描线在多边形内的情形。处理扫描线在多边形内的情形。定义一个大的矩形，让他包含了客体中定义一个大的矩形，让他包含了客体中所有的多边形，位于比其它多边形都更远所有的多边形，位于比其它多边形都更远离观察者的平行于投影平面的一个平面上，离观察者的平行于投影平面的一个平面上，并具有某个合适的亮度或颜色值。并具有某个合适的亮度或颜色值。修改算法。使得每当扫描线不在任何多修改算法。使得每当扫描线不在任何多边形内时，就往帧缓冲存储器中送入背景边形内时，就往帧缓冲存储器中送入背景的象素值。的象素值。76第七节第七节 区域分割算法区域分割算
49、法 区域分割算法区域分割算法将投影平面分割成区域将投影平面分割成区域，考，考察区域内的图象。如果容易确定在这个区域内察区域内的图象。如果容易确定在这个区域内某些多边形是可见的，那么就可以显示那些可某些多边形是可见的，那么就可以显示那些可见的多边形，完成对这一区域的显示任务。否见的多边形，完成对这一区域的显示任务。否则，就将区域再分割成小的区域，对小的区域则，就将区域再分割成小的区域，对小的区域递归地进行判断。由于区域逐渐变小，在每个递归地进行判断。由于区域逐渐变小，在每个区域内的多边形逐渐变小，最终总可以判定哪区域内的多边形逐渐变小，最终总可以判定哪些多边形是可见的。些多边形是可见的。这个算法
50、利用了区域的相关性，这种相关这个算法利用了区域的相关性，这种相关性是指位于适当大小的区域内的所有象素，表性是指位于适当大小的区域内的所有象素，表示的其实是同一个表面。示的其实是同一个表面。77 在在递递归归分分割割的的每每一一步步，要要显显示示客客体体中中每每个个多多边边形形的的投投影影多多边边形形与与所所考考察察区区域域之之间间的的关关系系，必必然是下列四种之一：然是下列四种之一：1.1.包包围围的的多多边边形形，即即多多边边形形全全部部包包含含了了所所考考察察的区域。的区域。2.2.相交的多边形，即多边形所考察的区域相交。相交的多边形，即多边形所考察的区域相交。3.3.被被包包含含的的多多