计算机图形学

目录

• 1 绪论
  • 1.1应用
  • 1.2定义
• 2 光栅设备
  • 2.1 光栅输入设备
  • 2.2 光栅输出设备
• 3 基本图形绘制
  • 3.1 图元扫描转换
  • 3.2 实区域填充
  • 3.3 图形反走样
• 4 *曲线与曲面
  • 4.1 概述
  • 4.2 参数曲线基础
    • 函数的常见表达形式
    • 曲线的表示形式
    • 曲线间连接的光滑度的度量
    • 曲线、曲面拟合方法
  • 4.3 参数多项式曲线
    • 概念
  • 4.4 三次Hermite曲线
  • 4.5 Bezier曲线
  • 4.6 B样条曲线
  • 4.7 曲面的生成
• 5 真实感绘制-图形裁剪
  • 5.1 点的裁剪
  • 5.2 直线段裁剪
    • 1直接求交算法:Cohen-Sutherland算法
    • 2中点分割裁剪算法
    • 3中点算法:梁友栋-barskey算法
  • 5.3 多边形裁剪
    • Sutherland-Hodgman算法
• 6 真实感绘制-图形变换
  • 6.1 变换的数学基础
  • 6.2 图形的几何变换
    • 相关概念
    • 图形的几何变换
  • 6.3 三维投影变换
  • 6.4 三维观察变换

1 绪论

1.1应用

科学计算可视化

地理信息系统(GIS)

娱乐

电脑游戏，电视广告，节目片头，科教演示(CAI)

多媒体

VR(虚拟现实、灵境)

自然景物的模拟(真实感图形绘制)

计算机动画

二维动画 ：图像变形，形状混合

三维动画 ：变形物体的动画，关节动画与人体动画 ，过程动画 ，关键帧动画

计算机艺术

1.2定义

图形 & 构成图形的要素

图形:

– 客观对象在人的视觉系统中产生的视觉印象

– 包括自然景物、拍摄到的图片等，可用用数学方法描述

构成图形的要素:

– 几何要素:刻画对象的轮廓、形状等

– 非几何要素:刻画对象的颜色、纹理等

计算机中表示图形的方法

点阵表示

• 枚举出图形中所有的点(强调图形由点构成) • 简称为图像(数字图像)。

参数表示

• 形状参数(方程或分析表达式的系数，线段的端点坐标等)+属性参数(颜色、线型等)来表示图形 • 简称为图形。

什么是计算机图形学

定义:计算机图形学是研究怎样用计 算机输入、生成(处理)、存储、显示 输出图形的一门学科。

计算机图形学的研究内容

具体概括为:图形硬件、光栅图形生成算法、曲线曲面造型、实体造型、真实感图形计算与显示算法，以及图形标准、图形交互技术、 科学计算可视化、计算机动画、自然景物仿真、虚拟现实等。

图形输入设备的发展

– 第一阶段:控制开关、穿孔纸等等

– 第二阶段:键盘

– 第三阶段:二维定位设备，如鼠标、光笔、图 形输入板、触摸屏等等，语音

– 第四阶段:三维输入设备(如空间球、数据手 套、数据衣)，用户的手势、表情等等

– 第五阶段:用户的思维

ACM SIGGRAPH会议(小知识)

– 全称 “the Special Interest Group on Computer Graphics and Interactive Techniques”

– 60年代中期，由Brown 大学的教授Andries van Dam (Andy) 和IBM公司的Sam Matsa发起

– 1974年，在Colorado大学召开了第一届SIGGRAPH 年会，并取得了巨大的成功

– 每年只录取大约50篇论文

常见的标准

通用的、与设备无关的图形包，图形标准

GKS (Graphics Kernel System) (第一个官方标准，1977)

PHIGS(Programmer’s Herarchical Iuteractive Graphics system)

非官方图形软件

广泛应用于工业界,成为事实上的标准

DirectX (MS)

Xlib(X-Window系统)

OpenGL(SGI)

Adobe公司Postscript

2 光栅设备

2.1 光栅输入设备

概念

像素：整个屏幕被扫描线分成 n 行，每行有 m 个点，每个点为一个像素。整个屏幕有 m × n 个像素。

设备

数字化仪是一种把图形转变成计算 机能接收的数字形式专用设备。基本工作原理是采用电磁感应技术。

扫描仪 ：平面图象扫描仪 &三维立体扫描仪，图形扫描仪是直接以像素信息进行扫描和存储的设备。

2.2 光栅输出设备

概念

图像刷新：由于CRT内侧的荧光粉在接受电子束的轰击时，只能维持短暂的发光， 根据人眼视觉暂留的特性，需要不断 进行刷新才能有稳定的视觉效果。图像的刷新频率等于帧扫描的频 率(帧频)，用每秒刷新的帧数表示; 目前刷新频率标准为每秒50~120帧。

行频、帧频：水平扫描频率为行频，垂直扫描频率为帧频。

逐行扫描、隔行扫描： 隔行扫描方式是先扫偶数行扫描线，再扫奇数行扫描线。

显示速度：指显示字符、图形特别是动态图像的速度，与显示器的分辨率及扫描频率有关。

分辨率：是指CRT在水平或垂直方向的单位长度 上能分辨出的最大光点(像素)数，分为水平分辨率和垂直分辨率。通常用屏幕上像素的数目来表示。比如 上述的 n 行，每行 m 点的屏幕分辨率为 m ×n。

点距：相邻像素点之间的距离。在同样面积大小的情况下，分辨 率越高，相邻像素点之间的距离越小，显示的字符或图像也就越清晰。

亮度等级与色彩等级：亮度等级又称灰度，主要指单色显示器的亮度变化;色彩等级是指像素颜色等级。

帧缓冲存储器(显示存储器)简称帧缓冲器，俗称显存。存储被刷新图像的信息，即存储屏幕上像素的颜色值。帧缓冲存储器的大小通 常用X方向(行)和Y方向 (列)可寻址的地址数的乘 积来表示，称为帧缓冲存储器的分辨率。帧缓存中单元数目与显示器上像素数目相同，单元与像素一一对 应;各单元的数值决定了其对应像素 的颜色。

黑白光栅扫描显示器

分为:1位帧缓存黑白光栅显示器 ，N位帧缓存灰度光栅显示器

灰度等级在光栅图形显示器中需要足够 的位面才能反映图形，存储器中的二进制位数被翻译成灰度等 级，范围是0到2的N次方-1之间。

彩色光栅扫描显示器

分辨率M*N、颜色个数K的光栅输出 设备，与显存大小V 的大小关系为:
$$
V >= M * N * [log 2 k]向上取整
$$
若存储器大小固定，则屏幕分辩率 与同时可用的颜色种数成反比关系。

显存问题– 高分辨率和真彩要求有大的显存

对于小显存如何完成大范围的显示颜色如何实现: 在不增加帧缓存单元位数的情况下，具有大范围内挑选颜色的能力。

解决方法:采用查色表(Lookup Table)或称彩色表 (Color Table)

查色表（look up Table）是一维线性表，其每一项的内容对应一种颜色，它的长度由帧缓存单元的位数决定，例如：每单元有8位，则查色表的长度为 2^8 =256。

简单的光栅扫描图形显示系统的结构

其中，帧缓存可为系统内存中的一块区域， 视频控制器能够直接存取该区域以刷新屏幕。

作用:建立帧缓存与屏幕像素之间 的一一对应，负责刷新。

光栅显示系统的特点

优点:

– 成本低

– 易于绘制填充图形

– 色彩丰富

– 刷新频率一定，与图形的复杂程度无关 – 易于修改图形

缺点:

– 需要扫描转换

– 会产生混淆

3 基本图形绘制

3.1 图元扫描转换

– 3.1.1 直线段扫描转换

基本思路

确定最佳逼近于该直线的一组象素

按扫描线顺序，对这些象素进行写操作

三个常用算法

(1)数值微分(Digital Differential Analyzer)算法

计算yi+1= kxi+1+b= k(xi+x) +b = kxi+b+kx= yi+kx

当x每递增1，y递增k(即直线斜率);

注意:上述分析的算法仅适用于|k|≤1的情形。此时，x每增加1,y最多增加1。

当 |k|>1时，必须把x，y地位互换且y增1，则x增1/k。

DDA算法是一个增量算法:在一次迭代计算中，每一步的x、y值是用前一步的值加上一个增量来获得的。

该方法直观，但y和k需要 浮点表示、以及y的舍入运 算，这不利于硬件实现。

void DDALine(int x0,int y0,int x1,int y1,int color)
{
    int x;
    float dx, dy, y, k;
    dx = x1-x0; dy=y1-y0; k=dy/dx ; y=y0;
    for (x=x0; x<=x1; x++)
    {
        DrawPixel (x, int(y+0.5), color);
        y=y+k;
    }
}

(2)中点画线法

基本思路(原理)—位置关系

计算效率改进：由于只用d 的符号作判 断，为了只包含整数运算, 可以用2d代替d来摆脱小数，提高效率。

具体见PPT

void midPoint Line (int x0,int y0,int x1, int y1,int color)
{ 
    int a, b, d1, d2, d, x, y;
    a=y0-y1; 
    b=x1-x0; 
    d=2*a+b; 
    d1=2*a ;
    d2=2* (a+b);
    x=x0;
    y=y0;
    drawpixel(x, y, color); 
    while (x<x1) 
    {
        if (d<0) {x++; y++; d+=d2; } 
        else {x++; d+=d1;} 
        drawpixel (x, y,color);
    } /* while */
} /* mid PointLine */

(3)Bresenham画线算法

基本思路(原理)—位置关系：由误差项符号决定下一个象素取正右方像素还是右上方像素。

初始值ε(x2)= k -0.5 (k为斜率)

ε(xi+2)= ε(xi+1) + k -1 当ε(xi+1)≥0

ε(xi+2)= ε(xi+1) + k 当ε(xi+1)≤0

Bresenham算法改进内容：

上述Bresenham算法在计算斜率时 (判断直线走向)用到除法。

此外，在计算误差项时用到小数， 由于算法中只用到误差项的符号来判断，因此，如下替换不会改变算法性质: **e’=2*e*dx**

Bresenham算法优点：

整数运算，速度快;精度高;乘2可用移位运算，适于硬件实现。

BresenhamLine(x0,y0,x1,y1,color)
{
    int x0,y0,x1,y1,color;
    int x,y,dx,dy;
    float k,e;
    dx = x1-x0;
    dy = y1-y0;
    e = -dx; 
    x=x0; y=y0; 
    for( i=0; i<=dx; i++)
    {
        drawpixel(x,y,color); 
        x++; 
        e=e+2*dy;
        if(e >=0)
        { 
            y++;
            e=e-2*dx;
        }
    } 
 }

– 3.1.2 圆弧扫描转换

圆弧的扫描转换

1.确定最佳逼近于该圆弧的一组像素

2.按扫描线顺序，对这些像素进行写操作

中点画圆法

midPointCircle(int r, int color) 
{ 
    int x,y;
    float d;
    x=0; y=r; d=1.25-r; 
    drawpixel(x,y,color); 
    while(x<y)
    {
         if(d<0)
            { d+ = 2*x+3; x++ }
         else
            {d+ = 2*(x-y) + 5; x++;y--; }
    } 
}

算法改进：为了进一步提高算法的效率，可以将上 面的算法中的浮点数改写成整数，将 乘法运算改成加法运算，即仅用整数 与加减法实现中点画圆法:使用 e= d-0.25 代替d因 d0 = 1.25 – R=1-R+0.25，d0-0.25 = 1-R，因此 e0 = d0- 0.25 = 1-R

Bresenham画圆算法

d0=3-2R

当di<0时:取Hi,此时yi=yi-1 则 di+1= di +4xi-1+7

当di ≥ 0时:取Li,此时yi=yi-1 - 1，则 di+1=di +4(xi-1-yi-1)+11

– 3.1.3 椭圆弧扫描转换-中点画法

MidpointEllipe(a,b, color) 
{ 
    int a,b,color;
    int x,y; float d1,d2;
    x = 0; y = b;
    d1 = b*b +a*a*(-b+0.25); 
    putpixel(x,y,color);
    while( b*b*(x+1) < a*a*(y-0.5)) 
    {
        
        if(d1<0)
        {
            d1 +=b*b*(2*x+3);
            x++; 
        }
        else
        {
            d1 +=(b*b*(2*x+3)+a*a*(-2*y+2));
            x++; y--;
        } 
        putpixel(x,y,color);
    }//上部分
    d2 = sqr(b*(x+0.5)) +sqr(a*(y-1)) – sqr(a*b); 
    while(y >0)
    {
        if (d2 <0) 
            { d2 +=b*b*(2*x+2)+a*a*(-2*y+3); x++; y--;}
        else
            {d2 += a*a*(-2*y+3); y--; } 
        putpixel(x,y,color); 
    }
}

3.2 实区域填充

点在多边形内的包含性检验：

• 检验夹角之和：若夹角和为0，则点p在多边形外；若夹角和为360°， 则点p在多边形内。
• 射线法检验交点数：交点数=偶数(包括0) ，点在多边形之外；交点数 = 奇数，点在多边形之内。
• 包围盒法

填充扩大化(边界取舍)问题：规定落在右/上方扫描线上象素不被填充

原理：利用图形的空间连贯性和扫描线的连贯性

顶点交点的计数(取舍)问题：根据交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数来判断选取该点的个数

区域填充的简单思路与问题：

• 基本思路: 所有扫描线与所有的边求交、排 序、配对、填充。
• 规律是: 每条扫描线只与少数的边相交，甚至整个多边形都不相交。

3.2.1 扫描线填充算法---扫描线的顺序

– 有序边表算法

空间连续性规律:

• 边的连续性:当某边与当前扫描线相交时，它很可能与下一条扫描线相交;

• 扫描线的连续性:当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序，很可能相同或非常相似。

相关概念：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL(Active Edge Table)。

基本思想：

连贯性的存在:多边形的边的连贯性 &扫描线的连贯性

下一条扫描线的活性边表 -> 只需对当前扫描线的活性边表作更新即可得到

具体实现:活性边表的转换与更新

删除旧边:删除与下条 扫描线不再相交的边

插入新边:插入与下条扫描线新相交的边

调整交点顺序:得到新 的活动边表(按照x递增)

活性边表的建立--表中需存放的信息:

x:当前扫描线与边的交点;

△x=-b/a=1/k :从当前扫 描线到下一条扫描线之 间的x增量;

ymax:边所交的最高扫描线 (边何时不再与下条扫描线相交)

新边表的建立: 依据扫描线顺序，存放第一次出现的边(已出现过的边不计)。

存放的信息:

x:扫描线与该边的初始交点(下端点)

△x:从当前扫描线到下一条扫描线之 间的x增量

ymax:该边的最大y值(最高扫描线)

有序边表算法—具体描述

对第i条扫描线 -> 第i+1条扫描线->最终填充

step1:把新边表NET[i]中的边结点，用插入排序(与交点计数法则有关)法插入活性边表AET(期初为空)，使之按X坐标递增顺序排序;

step2:遍历AET表(结合交点计数规则):把配对交点之间的区间(左闭右开)上的各象素(X,Y)，用drawpixel(x,y,color)改写象素颜色值;

step3:遍历AET表:把 i = Ymax的结点从AET表中删除，并把i < Ymax的结果点的X值递增△X;

step4:对下一条(第i+1条)扫描线，重复以上过程

优点:

– 对每个像素只访问一次

– 与输入/出细节无关 -> 设备无关

缺点:

– 数据结构复杂

– 只适合软件实现

– 边填充算法

• 优点:

– 最适合于有帧缓存的显示器

– 可按任意顺序处理多边形的边

– 算法简单:仅访问与该边有交点的扫描线上右方的像素

• 缺点:

– 对复杂图形，每一像素可能被访问多次，输入/输出量大

– 图形输出不能与扫描同步进行，只有全部画 完才能打印

边填充算法(改进)—栅栏填充算法

• 基本思想:

经过多边形的某个顶点，在多边形内部建立一个与扫描线垂直的“栅栏”，当扫描线与多边形边有交点，就将交点与栅栏之间的象素取补。若交点位于栅栏左边，则将交点之右，栅栏之左的所有象素取补;若交点位于栅栏右边，则将栅栏之右，交点之左的象素取补。

• 3.2.2 种子填充算法---内部一个点出发

• 种子填充指先将区域的一点赋予指定的颜色， 然后将该颜色扩展到整个区域的过程。
• 种子填充算法要求区域是连通的

– 简单种子算法(4连通边界)

种子像素入栈,当栈非空时，重复以下步骤:

(1)栈顶像素出栈

(2)将出栈象素置成填充色

(3)按右、上、左、下(逆时针)顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈

void FloodFill4(int x,int y,int fillColor,int oldColor)
{
    int current;
    current = getpixel(x, y); 
    if (current == oldColor)
    {
        putpixel(x, y, fillColor);
        BoundaryFill4(x+1, y, fillColor, oldColor);
        BoundaryFill4(x-1, y, fillColor, oldColor);
        BoundaryFill4(x, y+1, fillColor, oldColor);
        BoundaryFill4(x, y-1, fillColor, oldColor);
    } 
}

• 优点:

该算法也可以填充有孔区域

• 缺点:

(1) 有些象素会入栈多次，降低算法效率; 栈结构占空间。

(2) 递归执行，算法简单，但效率不高。区 域内每一象素都引起一次递归，进/出栈， 费时费内存。

• 改进算法，减少递归次数，提高效率。 解决方法是用扫描线种子填充算法

– 扫描线种子算法

• 目标:减少递归层次

• 适用于边界表示的4连通区域

扫描线种子填充算法(基本思想)

1在任意不间断区间中只取一个种子像素(不间断区间指在一条扫描线上一组相邻元素)

2 填充当前扫描线上的该段区间;

3然后确定与这一区段相邻的上、下两条扫描线上位于区域内的区段，并依 次把它们保存起来;

4反复进行这个过程，直到所保存的各区段都填充完毕。

扫描线种子填充算法(详细描述)

种子像素入栈,当栈非空时，重复以下步骤:

(1)栈顶像素出栈

(2)沿扫描线对出栈像素的左、右像素进行填充，直到遇到边界像素为止

(3)将上述区间内最左、最右像素记为xl和xr

(4)在区间[xl,xr]中检查与当前扫描线相邻的上、下两条扫描线上的像素是否全为边界像素、或已填充的像素。若为非边界、未填充的像素，则把每一区间的最右像素取为种子像素入栈

3.3 图形反走样

反走样概念

• 用离散量表示连续量引起的失真现象称之为走样(aliasing) 。

• 用于减少或消除走样现象的技术称为反走样(antialiasing)。

反走样的方法

• 提高分辨率(硬件、软件方法)

提高分辨率---硬件方法：把显示器分辨率提高一倍，直线经过两倍的象素，锯齿个数也会增加一倍， 但同时每个阶梯的宽度也减小了一倍，所以显示出的直线段看起来就平直光滑了一些。

硬件方法评价：方法简单，但代价非常大，显示器的水平、竖直分辩率各提高1倍， 则显示器的点距减少1倍，帧缓存容量则增加到原来的4倍，而扫描转换同样大小的图元却要花4倍时间；而且只能减轻而不能彻底消除锯齿问题。

提高分辨率---软件方法：高分辨率计算低分辨率显示，把每个像素分为四个子像素，扫描转换算法求得各子像素的灰度值，然后对四像素的灰度值简单平均，作为该像素的灰度值。

软件方法评价：只能减轻而不能消除锯齿问题。

• 简单区域取样

两点假设:1.象素是数学上抽象的点，它的面积为0，它的亮度由覆盖该点的图形的亮度所

决定;2.直线段是数学上抽象直线段，它的宽度为0。

现实:像素的面积不为0;直线段的宽度至少为1个像素。

方法步骤:(1)、将直线段看作具有一定宽度的狭长矩形 (2)、当直线段与某象素有交时，求出两者相交区域的面积 (3)、根据相交区域的面积，确定该象素的亮度值。

缺点:

• 象素的亮度与相交区域的面积成正比， 而与相交区域落在象素内的位置无关， 这仍然会导致锯齿效应。
• 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。

4 *曲线与曲面

4.1 概述

形状表示与设计的要求

(1)易于实现光滑连接

(2)形状易于预测、控制和修改

(3)几何意义直观， 设计不必考虑其数学表达

4.2 参数曲线基础

函数的常见表达形式

标量函数:平面曲线 :y = f(x) 空间曲线 :y = f(x) z = g(x)

矢量函数:平面曲线 :P(t) = [x(t),y(t)]空间曲线 :P(t) = [x(t),y(t),z(t)]

曲线的表示形式

非参数表示

参数表示

参数矢量表示

参数表示的优点

1)可满足几何不变性的要求。

2)有更大的*度来控制曲线、曲面的形状

3)对曲线、曲面进行变换，可对其参数方程直接进行几何变换。

4)便于处理斜率为无穷大的情形，不会因此而中断计算。

5)便于用户把低维空间中曲线、曲面扩展到高维 空间去。

6)规格化的参数变量t∈[0, 1]，使其相应的几 何分量是有界的，而不必用另外的参数去定义 边界。

7)易于用矢量和矩阵表示几何分量，简化了计算。

曲线间连接的光滑度的度量

参数连续性

几何连续性

直观的、易于交互控制的连续性

0阶几何连续

曲线P=P(t)在 t = t0 处0阶几何连续:如果它 在 t0处位置连续，即:p(t0-)=p(t0+)，记为GC0

1阶几何连续

曲线P=P(t)在t = t0 处1阶几何连续:如果它在该处 GC0 ,并且切矢量方向连续:

记为GC1

2阶几何连续

曲线P=P(t)在 t = t0 处2阶几何连续:如果它在 t0 处:

(1)GC1 (即:切矢量方向连续)

​ (2)副法线矢量方向连续 B(t0-)=B(t0+)

(3)曲率相等 k(t0-) = k(t0+)

曲线、曲面拟合方法

已知条件

一系列有序的离散数据点 （型值点、控制点 ）

边界条件

连续性要求

生成方法

插值

点点通过型值点（型值点：曲线上的点）

插值算法:线性插值、抛物样条插值、Hermite插值

逼近

在一定的误差范围内曲线贴近型值点

最小二乘法、回归分析

拟合

构造曲线的轮廓线贴近型值点或控制点（控制点：控制曲线的点，但曲线不一定过）

Bezier曲线、B样条曲线等

生成曲线的视觉要求：光顺(满足的条件)---不拐来拐去

具有二级几何连续

不存在多余的拐点和奇异点

曲率变化比较小

4.3 参数多项式曲线

概念

位置矢量

几何矩阵

控制顶点

基矩阵

基函数

代数系数矩阵

几何系数矩阵/ 条件边界矩阵 / 几何矩阵

调和函数

4.4 三次Hermite曲线

形状控制

改变端点位置矢量

调节切矢量 P0',P1'的方向

调节切矢量 P0 ',P1' 的长度

优缺点

优点

简单，易于理解

缺点

难以给出两个端点处的切线矢量作为初始条件

不方便

所有参数插值曲线的缺点:

只限于作一条每点都通过给定数据点的曲线

只适用于插值场合，如外形的数学放样

不适合于外形设计

4.5 Bezier曲线

Hermit曲线需要知道起点、终点的切矢，这在实 际工作中很难确定，如果将切矢用位矢代替，问题 就会迎刃而解，Bezier就是从这点入手的。

Bezier基函数--Bernstein多项式

Bernstein基函数的性质

Bezier曲线的性质

Bezier曲线的递推(de Casteljau)算法

优缺点：

优点:形状控制直观, 设计灵活

缺点:

所生成的曲线与特征多边形的外形相距较远

局部控制能力弱，因为曲线上任意一点都是所有给定顶点值的加权平均

控制顶点数增多时，生成曲线的阶数也增高

控制顶点数较多时，多边形对曲线的控制能力减弱

曲线拼接需要附加条件，不太灵活

4.6 B样条曲线

对于B样条曲线来说，特征多边形每增加一个顶点，就相应增加一段B样条曲线。因此，B样条曲线 很好地解决了曲线段的连接问题。

特殊外形设计

相切于控制多边形边的曲线--两顶点重合

含有尖点的曲线---三顶点重合

反向弧切接效果---用三点共线的方法

接入一段直线---可用四点共线的方法

优缺点

优点:

与控制多边形的外形更接近

局部修改能力

任意形状，包括尖点、直线的曲线

易于拼接

阶次低，与型值点数目无关，计算简便

缺点:

不能精确表示圆

4.7 曲面的生成

5 真实感绘制-图形裁剪

图形裁剪：确定图形中哪些部分落在显示区之内，哪些落在显示区之外,以便只 显示落在显示区内的那部分图形。图形裁剪算法，直接影响图形系统的效率。

5.1 点的裁剪

P点在窗口内的条件是: xL <=x<=xR and yB <=y<=yT 否则，P点就在窗口外。

5.2 直线段裁剪

直线段裁剪算法是复杂图形裁剪的基础。 复杂的曲线可以通过折线段来近似，从而 裁剪问题也可以化为直线段的裁剪问题。

裁剪线段与窗口的关系: (1)完全可见; (2)完全不可见; (3)其它。

一个概念:显然不可见:即在窗口的某条边的 延长线的非窗口一侧。

1直接求交算法:Cohen-Sutherland算法

编码顺序：上下右左

基本思想

对于每条线段P1P2分为三种情况处理:

(1)若P1P2完全在窗口内，则显示该线段P1P2。

(2)若P1P2显然不可见，则丢弃该线段。

(3)若线段不满足(1)或(2)的条件，则线段与 窗口的边相交，在交点处把线段分为两段。 其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。

算法描述

–若P1P2完全在窗口内:code1=0,且code2=0,则“取”

–若P1P2显然在窗口外:code1&code2≠0，说明在窗口 的某一侧,则“弃”(显然不可见)

–否则，求线段与某一边的交点,在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一 段重复上述处理。

直线裁剪算法小结

优点:简单，易于实现。按上，下， 右，左的顺序依次进行，处理之后， 剩余部分就是可见的了。

特点:用编码方法可快速判断线段的完全可见和显然不可见。

缺点:本算法对于其它形状的窗口未 必同样有效。

2中点分割裁剪算法

可见点:落在窗口内的点

基本思想：找最近可见点

中点分割方法

从P0出发找距离P0最近可见点的中点分割方法

– 先求出P0P1的中点Pm

– 若P0Pm不是显然不可见的(说明P0P1在窗口 中有可见部分)，则距P0最近的可见点一 定落在P0Pm上，则用P0Pm代替P0P1;

– 否则取PmP1代替P0P1；

– 再对新的P0P1求中点Pm。重复上述过程， 直到PmP0长度小于给定的控制常数为止， 此时Pm收敛于交点，即为P0最近可见点。

从P1出发找距离P1最近可见点采用上面类似方法

中点分割裁剪算法---完整描述

从P0点出发找出离P0最近的可见点，和从P1点出发找出离P1最近的可见点。这两个可见 点的连线就是原线段的可见部分。

与Cohen-Sutherland算法一样:首先对线段端点进行编码，并把线段与窗口的关系分为 三种情况，对前两种情况(完全在内、显然不可见)，进行同样的处理。对于第三种情况，用中点分割的方法求出线段与窗口的交点:A和B,它们分别为距P0和P1最近的可见点，并保留之，其它段弃之。

3中点算法:梁友栋-barskey算法

算法步骤(核心思想)

5.3 多边形裁剪

Sutherland-Hodgman算法

存在的问题:对凸多边形，本算法可以得到 正确的结果;但对凹多边形，如图所示显示出一条多余的直线。 因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点，在裁剪后的多边形有两个或多个分离部分出现。

解决这个问题有多种方法:

一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。

二是修改本算法:沿着任何一个裁剪窗 口边检查顶点表，并实施正确的连接。

此外，还可用Weiler-Atherton算法。

6 真实感绘制-图形变换

6.1 变换的数学基础

齐次坐标：就是由n+1维向量表示一个n维向量。如n维向量 (P1,P2, ... ,Pn)表示为(hP1,hP2,hPn,...,h)，其中h** 称为哑坐标。

• 同一点的齐次坐标不是唯一的，因为h可以取 不同的值。
• 普通坐标与齐次坐标的关系为“一对多”
• 由:普通坐标xh→齐次坐标;由:齐次坐标÷h→普通坐标。
• 当h=1时产生的齐次坐标称为“规格化坐标”。

齐次坐标的作用

1 将各种变换用阶数统一的矩阵来表示。提供了一个点从一个坐标系变换到另一坐标系的有效方法。

2 便于表示无穷远点。

3 齐次坐标变换矩阵形式对直线、平面、多 边形、多面体变换具有图形拓扑关系保持不变的特性。

4 变换具有统一表示形式的优点 ：便于变换合成&便于硬件实现

6.2 图形的几何变换

相关概念

用户域

程序员用来定义草图的整个自然空间(WD)

• 用户域是一个实数域，理论上是连续无限的。
• 人们所要描述的图形均在用户域中 定义。

窗口区

用户指定的任一区域(W )

• 窗口区W 小于或等于用户域WD
• 小于用户域的窗口区W 叫做用户域的子域
• 窗口可以有多种类型，矩形窗口、圆形 窗口、多边形窗口等。
• 窗口可以嵌套，即在第一层窗口中可再 定义第二层窗口，在第i层窗口中可再定义第i+1层窗口等。

屏幕域(DC)

设备输出图形的最大区域， 是有限的整数域。

视图区

任何小于或等于屏幕域的区域

• 视图区用设备坐标定义在屏幕域中
• 当窗口区显示在视图区时，需做窗口区到视图区的坐标转换
• 视图区可以有多种类型:圆形、矩形、 多边形等
• 视图区也可以嵌套

关系

用户域->屏幕域

窗口区->视图区

图形的几何变换

作用

把用户坐标系(用户域)与设备坐标系(屏幕域)联系起来

可由简单图形生成复杂图形

可用二维图形表示三维形体

可实现动态显示

图形变换

对图形的几何信息经过几何变换后产生新的图形

图形变换的两种形式

图形不变，坐标系改变

图形改变，坐标系不变

二维图形的显示流程图

6.3 三维投影变换

平行投影:投影中心到投影平面距离为无限

透视投影:投影中心到投影平面距离为有限

正、斜平行投影:按投影方向与 投影平面是否垂直进行分类

正三面投影:投影平面与 一个坐标轴垂直，或者说与一个坐标平面平行

正等侧投影:投影平面与三个坐 标轴成相等的夹角(或其法线与 每个坐标轴的夹角相等)，投影 后，三个轴的变形系数相等。

正二轴侧投影:投影平面与两个 坐标轴成固定夹角(或其法线与 两个坐标轴的夹角相等)，投影 后，两个轴的变形系数相等。

正三轴侧投影:投影平面与三个坐标轴之 间的夹角不相等(或其法线与每个坐标轴 的夹角都不相等)，投影后，每个轴的变 形系数都不相等。

斜二侧投影:投影平面的法线与两个坐标轴的夹角相等。

斜等侧投影:投影平面的法线与每个坐标轴的夹角相等。

灭点(消失点)/主灭点:视线(投影线) 从视点(观察点)出发，汇聚于一点称 为灭点。在坐标轴上的灭点称为主灭点。 主灭点就是投影平面相交于坐标轴的数量，以此为依据分为以上的三种。

单/一点透视:投影平面与坐标系的一个轴垂直

二点透视:投影平面与一个轴平行，与另两轴呈相同的固定角度

三点透视:投影平面与三 个轴均呈相同固定角度

6.4 三维观察变换