《三维图形程序设计基本算法》由会员分享，可在线阅读，更多相关《三维图形程序设计基本算法（55页珍藏版）》请在金锄头文库上搜索。
1、2024/7/241Part3Part3 计算机图形学基本算法计算机图形学基本算法3.1 3.1 扫描转换扫描转换( (光栅化光栅化) )3.2 3.2 线段的扫描转换线段的扫描转换3.3 3.3 区域填充算法区域填充算法 多边形域的填充多边形域的填充 扫描线填充算法扫描线填充算法 种子填充算法种子填充算法3.4 3.4 裁剪算法裁剪算法3.5 3.5 走样及反走样走样及反走样3.6 3.6 光照模型及明暗处理光照模型及明暗处理3.7 3.7 可见面判别算法可见面判别算法2024/7/2423.1 3.1 扫描转换扫描转换图图1 1 具有一位帧缓存的黑白显示器工作原理具有一位帧缓存的黑白显示器
2、工作原理显示器显示器 显卡显卡 帧缓存帧缓存屏幕屏幕存储位存储位象素象素2024/7/2433.1 3.1 扫描转换扫描转换图图2 2 具有具有8位帧缓存的彩色显示器工作原理位帧缓存的彩色显示器工作原理2024/7/244扫扫描描转转换换或或光光栅栅化化：在在显显示示器器上上显显示示一一个个图图形形的的过过程程, , 就就是是确确定定一一个个象象素素集集合合及及其其颜色过程，包括线的光栅化和面的光栅化颜色过程，包括线的光栅化和面的光栅化2024/7/2452024/7/246扫描转换线段：扫描转换线段：一个象素宽度一个象素宽度有限个象素点有限个象素点3.2 3.2 线段的扫描转换线段的扫描转换
3、理想线段：理想线段：没有宽度没有宽度无数个点无数个点1 数值微分法数值微分法(DDA)(DDA)2 Bresenham画线算法画线算法2024/7/247已已知知线线段段的的两两端端点点，线线段段的的方方程程是是y=mx+by=mx+b，对对其其进进行行扫扫描描转转换换。假假设设线线段段的的斜斜率率 ，让让x x从从左左端端点点到到右右端端点点变变化化，每每步步递递增增1 1个个象象素素，计计算算对对应应的的y y的坐标，可得到一系列线段上的象素。的坐标，可得到一系列线段上的象素。1 1 数值微分法数值微分法 相邻点横纵坐标的递推关系：相邻点横纵坐标的递推关系：2024/7/2482024/7
4、/249：x x每步递增每步递增1 1个象素，个象素，y y递增递增m(m(直线斜率直线斜率) ) ：可可将将x x和和y y的的规规则则交交换换，y y每每步步递递增增1 1个个象象素素，计计算对应的算对应的x x的坐标的坐标 ：x x每步递减每步递减1 1个象素，个象素，y y减少减少m(m(直线斜率直线斜率) ) ：同同样样可可将将x x和和y y的的规规则则交交换换，y y每每步步递递减减1 1个个象象素素，x x减少减少1/m1/m从从左左向向右右从从右右向向左左2024/7/24102 Bresenham2 Bresenham画线算法画线算法2024/7/2411 向右向右绘绘制制
5、的的直直线线 向左向左绘绘制直制直线线2024/7/2412 在在 处，候选象素到线处，候选象素到线段段y y坐标差值坐标差值d2 d2 和和d1:d1:若若 d1 d2, d1 d2, d1d2, 则取上面的象素则取上面的象素B B对对 两点间的两点间的线段进行扫描转换线段进行扫描转换向右向右绘绘制制2024/7/2413其中其中 定定义义 为为BresenhamBresenham画画线线算法中第算法中第k k步的步的决策参数决策参数： 设设 为线段左右两端点的水平垂直偏离量，则为线段左右两端点的水平垂直偏离量，则 2024/7/2414 给定线段从左向右绘制，给定线段从左向右绘制， ，所，
6、所以以 的符号与的符号与 的符号相同，有：的符号相同，有：0 0，则，则 , ,那么那么 象素比象素比 象象素更接近于线段，选择绘制素更接近于线段，选择绘制 ；0 0，约定绘制，约定绘制 。 0 0，则，则 , ,那么那么 象素比象素比 象素更接近于线段，选择绘制象素更接近于线段，选择绘制 ；2024/7/2415时的时的BresenhamBresenham画线算法：画线算法：1 1输入线的两个端点，并将左端点存储在输入线的两个端点，并将左端点存储在 中；中；2 2将将 装入帧缓冲存储器中，画出第一个点；装入帧缓冲存储器中，画出第一个点；3 3计算决策参数的第一个值：；计算决策参数的第一个值：
7、；4 4从从k=0k=0开始，在沿线的每个开始，在沿线的每个 处，进行下列检测：处，进行下列检测：假如假如 ，下一个待画点是，下一个待画点是 , ,且且 ；否则下一个待画点是否则下一个待画点是 ，且，且 ；5 5重复步骤重复步骤4 4，共，共 -1-1次。次。 2024/7/24162024/7/24172024/7/24182024/7/24193.3 3.3 区域填充算法区域填充算法 填充方式填充方式实心填充实心填充图案填充图案填充实心填实心填充方法充方法扫描线填充算法扫描线填充算法种子填充算法种子填充算法2024/7/2420一、多边形域的实心填充扫描线填充算法一、多边形域的实心填充扫描
8、线填充算法 多边形扫描线填充算法的基本思想多边形扫描线填充算法的基本思想: :按扫描线顺序，计算按扫描线顺序，计算每条扫描线与多边形的相交区间，再用要求的颜色显示这些每条扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素。区间的象素。2024/7/2421多边形扫描线填充算法，对于一多边形扫描线填充算法，对于一条扫描线，可分为四个步骤：条扫描线，可分为四个步骤：1. 1. 求交求交：计算扫描线与多边形各边的交点；：计算扫描线与多边形各边的交点；2. 2. 排序排序：把所有交点按递增顺序进行排序；：把所有交点按递增顺序进行排序；3. 3. 交点配对交点配对：对排序交点从头到尾两两配：对排
9、序交点从头到尾两两配对，第一个与第二个配对对，第一个与第二个配对, ,第三个与第四个第三个与第四个配对等等。每对交点就代表扫描线与多边形配对等等。每对交点就代表扫描线与多边形的一个相交区间；的一个相交区间；4. 4. 区间填色区间填色：把这些相交区间内的象素置成填充色。：把这些相交区间内的象素置成填充色。 2024/7/2422假定假定当扫描线与多边形的顶点相交时，当扫描线与多边形的顶点相交时， 交点只算一个交点只算一个 ? ? 解决办法：解决办法：问题：当扫描线与多边形顶点相交时，问题：当扫描线与多边形顶点相交时，交点的取舍问题交点的取舍问题 扫扫 描描 线线y=2: y=2: 2 2，8
10、8，2 2求交求交 22，22，8 8 排序排序 2 2，2 2，8 8 交点配对交点配对扫扫 描描 线线y=7: y=7: 1111，9 9，2 2 22，99，11 11 2 2，9 9 ，11112 2，8 8 22，88 2 2，8 8 n共享顶点的两条边分别落在扫描线的两侧，与顶点的交点只算共享顶点的两条边分别落在扫描线的两侧，与顶点的交点只算1 1个；个；n共享顶点的两条边在扫描线的同侧，与顶点的交点算为共享顶点的两条边在扫描线的同侧，与顶点的交点算为0 0个或个或2 2个：个： 顶点是多边形的局部顶点是多边形的局部最高点最高点，交点数算，交点数算0 0个；个； 顶点是多边形的局部
11、顶点是多边形的局部最低点最低点，交点数算，交点数算2 2个；个；1111，9 9 99，11 11 9 9 ，11112024/7/2423 种子填充算法的基本思想是如在种子填充算法的基本思想是如在区域内部有一象素已知，由此出发找区域内部有一象素已知，由此出发找到区域内的所有象素。到区域内的所有象素。四向四向算法算法八向八向算法算法 种子填充算法用在边界定义的区种子填充算法用在边界定义的区域，该算法也可称为边界填充算法。域，该算法也可称为边界填充算法。种子填种子填充算法充算法二、种子填充算法二、种子填充算法四向联四向联通区域通区域八向联八向联通区域通区域2024/7/24243.4 3.4 裁
12、剪算法裁剪算法 用计算机显示图形时，必须确定图用计算机显示图形时，必须确定图形中哪些部分落在指定区域内，哪些形中哪些部分落在指定区域内，哪些部分落在指定区域外，这个处理过程部分落在指定区域外，这个处理过程称为称为裁剪裁剪。指定区域称为。指定区域称为裁剪窗口裁剪窗口，一般把裁剪窗口定义为矩形一般把裁剪窗口定义为矩形。2024/7/2425 对于点（对于点（x,y)x,y)的裁剪，只要判别如下不等式：的裁剪，只要判别如下不等式：一、点裁剪一、点裁剪2024/7/2426线段与裁剪窗口的位置关系：线段与裁剪窗口的位置关系： 线段不能明确判定其与裁剪窗口的位置关系，必须通线段不能明确判定其与裁剪窗口的
13、位置关系，必须通过交点计算，得到线段在裁剪窗口内的部分并显示。过交点计算，得到线段在裁剪窗口内的部分并显示。 线段明显落在裁剪窗口外，丢弃该线段；线段明显落在裁剪窗口外，丢弃该线段；二、线段裁剪二、线段裁剪 线段完全落在裁剪窗口内，显示该线段；线段完全落在裁剪窗口内，显示该线段；2024/7/2427*1*1*Cohen-SutherlandCohen-Sutherland线段裁剪算法线段裁剪算法 采用编码方法，每个区都用一采用编码方法，每个区都用一个四位二进制区域码表示该区与裁个四位二进制区域码表示该区与裁剪窗口的位置关系：剪窗口的位置关系： 裁剪窗口的右上方区域裁剪窗口的右上方区域: :
14、上下右左上下右左裁剪窗口的正下方区域裁剪窗口的正下方区域: :裁剪窗口区的区域码裁剪窗口区的区域码: :00000000 判定一条线段与裁剪窗口的位置关系，可先求出线段两判定一条线段与裁剪窗口的位置关系，可先求出线段两端点所在区的区域码端点所在区的区域码code1code1和和code2code2。设端点的坐标为。设端点的坐标为 ： 1010101001000100*1*1*1*1*1*1101010100100010000000000100110010001000101010101100010000010001001100110*0*0*0*0*0*0*0*02024/7/2428 有了端点
15、的区域码有了端点的区域码code1code1和和code2code2，可方便快速地判定线段，可方便快速地判定线段与裁剪窗口的位置关系：与裁剪窗口的位置关系： code1code20显示显示线段线段 两端点的区域码都为两端点的区域码都为00000000，两端点在裁剪窗口区两端点在裁剪窗口区两端点的区域码至少有一两端点的区域码至少有一位同时为位同时为1 1，两端点同在裁，两端点同在裁剪窗口的上方、下方、右剪窗口的上方、下方、右方或左方方或左方丢弃丢弃线段线段 code1|code2 code1|code20 0code1code1code2code20 0 code1code1code2code2
16、0 0 均不成立均不成立 求交点求交点计算计算不能判定线段与裁剪窗口不能判定线段与裁剪窗口的位置关系的位置关系2024/7/2429 图 线、圆的走样走样走样(aliasing): (aliasing): 用有限个象素来表示连续的图形而引起的失真。用有限个象素来表示连续的图形而引起的失真。反走样反走样(anti(antialiasing): aliasing): 用于减少或消除走样现象的技术。用于减少或消除走样现象的技术。3.5 3.5 走样及反走样走样及反走样2024/7/2430 狭小图形的遗失或闪烁狭小图形的遗失或闪烁需要显示的静态小三角形屏幕上显示结果:小三角形遗失需要显示的运动小三角
17、形屏幕上显示结果：小三角形闪烁 图形的边界呈阶梯状图形的边界呈阶梯状一、走样的表现形式一、走样的表现形式 图形细节失真图形细节失真图图形细节失真2024/7/2431 纹理的走样纹理的走样纹理贴纹理的模型建筑物几何模型图 纹理的走样2024/7/24322024/7/24332024/7/24342024/7/24352024/7/24362024/7/24372024/7/24382024/7/24392024/7/24402024/7/2441图 分辨率提高一倍阶梯程度减小一倍1 1 提高分辨率提高分辨率2 2 过采样过采样过采样的过采样的基本思想基本思想是：高分辨率计算，低分辨率显示。是
18、：高分辨率计算，低分辨率显示。高高分分辨辨率率计计算算：将将屏屏幕幕上上的的象象素素划划分分成成多多个个子子象象素素，然然后计算出各个子象素的颜色值后计算出各个子象素的颜色值( (或灰度值或灰度值) )。低低分分辨辨率率显显示示：对对一一个个象象素素内内子子象象素素的的颜颜色色值值求求平平均均值值( (可可以以取取简简单单平平均均，也也可可取取加加权权平平均均) )，将将平平均均值值作作为为该该象素的颜色值显示。象素的颜色值显示。二、反走样的方法二、反走样的方法2024/7/2442线线段段过过采采样样的的具具体体方方法法：统统计计每每个个象象素素沿沿线线路路径径的的子子象象素素数数目目，象象
19、素素的的灰灰度度等等级级正正比比于于这这个个子子象象素素数数目。目。(1) 理想直线(2) 直线扫描转换(3) 划分成多个子象素 (4) 过采采样结果把一个象素划分成把一个象素划分成 个子象素，设个子象素，设为为系系统统支支持持的的最最大大灰灰度度，s s为为象象素素沿沿线线路路径径的的子子象象素素数数目目，则则象象素素的的灰灰度值：度值：过采样的过采样的基本思想基本思想是：高分辨率计算，低分辨率显示。是：高分辨率计算，低分辨率显示。2024/7/24432024/7/24442024/7/2445第十章第十章1 13.6 3.6 光照模型与明暗处理光照模型与明暗处理一、基本光照模型一、基本光
20、照模型一个物体表面即使不直接暴露在光源下，只要其周围一个物体表面即使不直接暴露在光源下，只要其周围的物体被照亮，它也可能看得见，称为环境光。环境光没的物体被照亮，它也可能看得见，称为环境光。环境光没有空间或方向上的特征，在所有方向上和所有物体表面上有空间或方向上的特征，在所有方向上和所有物体表面上投射的环境光数量都恒定不变。投射的环境光数量都恒定不变。 p 环境光（环境光（Ambient lightAmbient light） 物体表面上某点的环境光强度物体表面上某点的环境光强度可用公式表示为：可用公式表示为：其中表示场景中的环境光的其中表示场景中的环境光的大小，大小， 为环境光反射的系数。为
21、环境光反射的系数。2024/7/2446第十章第十章3 3 粗糙的物体表面往往将入射光向各个方向反射，这种粗糙的物体表面往往将入射光向各个方向反射，这种光线的散射现象称为漫反射。假定物体为理想漫反射体，光线的散射现象称为漫反射。假定物体为理想漫反射体，即光线被物体表面漫反射后向各个方向以同等光强度发散，即光线被物体表面漫反射后向各个方向以同等光强度发散，而与观察方向无关。而与观察方向无关。光源q q物体表面上某点的漫反射光物体表面上某点的漫反射光强度可用公式表示为：强度可用公式表示为：其中其中 为光源的强度，参数为光源的强度，参数 在在0与与1之间，为漫反射的系数。之间，为漫反射的系数。 N
22、NL Lp漫反射（漫反射（Diffuse reflection）2024/7/2447第十章第十章4 4V Vj j光源q qN NL L观察点q qR R图中用图中用R表示一个理想镜面反射方向的单位向量，表示一个理想镜面反射方向的单位向量，L表示表示指向光源的单位向量，指向光源的单位向量，V为指向观察点的单位向量，角度为指向观察点的单位向量，角度 是是V与与R之间的夹角。之间的夹角。Phong镜面反射模型：镜面反射模型：其中其中 为光源的强度，参数为光源的强度，参数 在在0与与1之间，为镜面反射的系数，之间，为镜面反射的系数，为镜面反射参数。为镜面反射参数。 H Hp镜镜面反射（面反射（Sp
23、ecular reflection）2024/7/2448第十章第十章5 5物体表面上某点处的光强度为：物体表面上某点处的光强度为：环境光漫反射镜面反射环境光漫反射环境光p光照模型的合并光照模型的合并(点光源点光源)：为环境光强度和光源强度：为环境光强度和光源强度 ：和物体的材质属性有关：和物体的材质属性有关 ：与该点的：与该点的位置位置有关有关 ：该点处的：该点处的法向量法向量 2024/7/2449第十章第十章6 6该方法中物体每个多边形上所有点该方法中物体每个多边形上所有点都采有相同的法向量：所在平面的法向都采有相同的法向量：所在平面的法向量。对于每一个多边形，只需根据其平量。对于每一个
24、多边形，只需根据其平面法向量计算一次光强度，多边形上每面法向量计算一次光强度，多边形上每个可见点均按这个光强度进行显示。个可见点均按这个光强度进行显示。 明暗处理就是利用光照模型来计算物体表面点的光强度。明暗处理就是利用光照模型来计算物体表面点的光强度。按照点法向量计算方法的不同，明暗处理方法可分为三种：按照点法向量计算方法的不同，明暗处理方法可分为三种： 二、明暗处理二、明暗处理pFlat shading2024/7/2450V VN N1 1N N2 2N N3 3N N4 4第十章第十章7 7n计算各个多边形顶点处的平均单位法向量；计算各个多边形顶点处的平均单位法向量；n对多边形顶点根据
25、光照模型计算该点光强度；对多边形顶点根据光照模型计算该点光强度；n在多边形表面上，将顶点光强度进行线性插值，在多边形表面上，将顶点光强度进行线性插值，得到各点的光强度。得到各点的光强度。采用Flat shading 曲面不光滑 采用Gouraud shading曲面比较光滑 pGouraud shading2024/7/2451第十章第十章8 8采用Gouraud shading表面上有马赫带效应n计算各个多边形顶点处的平均单位法向量；计算各个多边形顶点处的平均单位法向量；n在多边形表面上，将顶点法向量进行线性插值，得到各点法向量；在多边形表面上，将顶点法向量进行线性插值，得到各点法向量；n根
26、据光照模型计算多边形表面上各点的光强度。根据光照模型计算多边形表面上各点的光强度。采用Phong shading 曲面光滑 pPhong shading2024/7/2452 对于组成三维物体的一个多边形，有对于组成三维物体的一个多边形，有前向面前向面和和后向面后向面之分。之分。第九章第九章3 3 多边形的前向面多边形的前向面对着观察方向对着观察方向多边形是多边形是可见的可见的多边形的前向面不多边形的前向面不对着观察方向对着观察方向多边形外法向多边形外法向量与观察向量量与观察向量与之间的夹角与之间的夹角钝钝角角锐锐角角多边形是多边形是不可见的不可见的2024/7/2453观察向量与多边观察向量
27、与多边形外法向量之间形外法向量之间的夹角为钝角的夹角为钝角多边形的前向面多边形的前向面对着观察者对着观察者观察向量与多边观察向量与多边形外法向量之间形外法向量之间的夹角为锐角的夹角为锐角多边形的前多边形的前向面不对着向面不对着观察者观察者观察向量与多边形法向量的点积为：观察向量与多边形法向量的点积为：设组成三维物体的多边形平面方程为：设组成三维物体的多边形平面方程为：设观察方向向量为设观察方向向量为各多边形平面的法向量为外法向量。各多边形平面的法向量为外法向量。多边形是多边形是可见的可见的多边形是多边形是不可见的不可见的第九章第九章4 42024/7/2454 1 x=0 (1,0,0)第九章
28、第九章6 6例：如图一个三维坐标系中有一个长度为例：如图一个三维坐标系中有一个长度为1的立方体，从观察点的立方体，从观察点(2,2,2)向原点处观察，此时立方体中哪些面不可见。向原点处观察，此时立方体中哪些面不可见。解：观察向量为（解：观察向量为（2,2 ,2 ） 六个面的方程及外法向量分别为：六个面的方程及外法向量分别为：平面方程平面方程 外法向量外法向量 2 -y=0 (0,-1,0) 3 -z=0 (0,0,-1) 4 x=1 (1,0,0) 5 y=1 (0,1,0) 6 z=1 (0,0,1)观察向量与正方体六个面外法向量的点积用矩阵表示为：观察向量与正方体六个面外法向量的点积用矩阵
29、表示为：2024/7/24第九章第九章6 6作业题作业题3 31 1 简述简述BresenhamBresenham画线算法的原理。画线算法的原理。2 2 说明多边形扫描线填充算法的四个步骤以及说明多边形扫描线填充算法的四个步骤以及该算法必须解决的问题。该算法必须解决的问题。3 3 简述简述Cohen-SutherlandCohen-Sutherland线段裁剪算法的原理线段裁剪算法的原理4 4 列出几种常见的走样现象，简述消除直线走列出几种常见的走样现象，简述消除直线走样的方法。样的方法。5 5 简述基本光照模型的种类及其含义。简述基本光照模型的种类及其含义。 6 6 画图说明可见面判别的方法画图说明可见面判别的方法
