计算机图形学第七章
- 格式：ppt
- 大小：787.50 KB
- 文档页数：76
下载文档原格式
合集下载
计算机图形学基础教程
在计算机图形学中，样条曲线是指 由多项式曲线段连接而成的曲线，在每 段的边界处满足特定的连续性条件，而 样条曲面则可用两组正交样条曲线来描 述。
7.1.2 曲线曲面的表示形式
曲线曲面的可以采用显式方程、隐函数 方程和参数方程表示。
首先看一下直线的表示形式：已知直线 的起点坐标P1（x1，y1）和终点坐标P2 （x2，y2）,直线的显式方程表示为：
px[13]=180;py[13]=0;
px[14]=225;py[14]=71;
px[15]=270;py[15]=100;
px[16]=315;py[16]=71;
px[17]=360;py[17]=0;
}
void CTestView::DrawPoint()//绘制型值点 {
CClientDC dc(this); CPen NewPen,*OldPen; CBrush NewBrush,*OldBrush; NewPen.CreatePen(PS_SOLID,1,RGB(255,255,0)); OldPen=dc.SelectObject(&NewPen); NewBrush.CreateSolidBrush(RGB(0,0,0)); OldBrush=dc.SelectObject(&NewBrush); for(int i=1;i<N;i++) {
图7-1 汽车的曲面
7.1 基本概念
7.1.1 样条曲线曲面 7.1.2 曲线曲面的表示形式 7.1.3 拟合和逼近 7.1.4 连续性条件
7.1.1 样条曲线曲面
在汽车制造厂里，传统上采用样条 绘制曲线的形状。绘图员弯曲样条（如 弹性细木条）通过各型值点，其它地方 自然过渡，然后沿样条画下曲线，即得 到样条曲线（Spline Curve)。
7.1.2 曲线曲面的表示形式
曲线曲面的可以采用显式方程、隐函数 方程和参数方程表示。
首先看一下直线的表示形式：已知直线 的起点坐标P1（x1，y1）和终点坐标P2 （x2，y2）,直线的显式方程表示为：
px[13]=180;py[13]=0;
px[14]=225;py[14]=71;
px[15]=270;py[15]=100;
px[16]=315;py[16]=71;
px[17]=360;py[17]=0;
}
void CTestView::DrawPoint()//绘制型值点 {
CClientDC dc(this); CPen NewPen,*OldPen; CBrush NewBrush,*OldBrush; NewPen.CreatePen(PS_SOLID,1,RGB(255,255,0)); OldPen=dc.SelectObject(&NewPen); NewBrush.CreateSolidBrush(RGB(0,0,0)); OldBrush=dc.SelectObject(&NewBrush); for(int i=1;i<N;i++) {
图7-1 汽车的曲面
7.1 基本概念
7.1.1 样条曲线曲面 7.1.2 曲线曲面的表示形式 7.1.3 拟合和逼近 7.1.4 连续性条件
7.1.1 样条曲线曲面
在汽车制造厂里，传统上采用样条 绘制曲线的形状。绘图员弯曲样条（如 弹性细木条）通过各型值点，其它地方 自然过渡，然后沿样条画下曲线，即得 到样条曲线（Spline Curve)。
计算机图形学智慧树知到答案章节测试2023年中国地质大学(武汉)
第一章测试1.计算机图形学产生图形，计算机图像学产生图像。
（）A:对B:错答案:B2.下列哪项不属于计算机图形学的应用领域？（）A:虚拟现实B:游戏实时显示C:科学计算可视化D:计算机辅助设计E:数字电影制作F:识别图片中的动物答案:F3.本课程将讲不讲解以下哪个内容？（）A:动画生成B:真实感图像生成C:曲线生成D:游戏制作答案:D4.使用OPENGL画带颜色的直线，需要调用不同的函数，分别指定颜色和起始点坐标。
（）A:错B:对答案:B5.在OPENGL中定义的结点仅包含位置信息。
（）A:对B:错答案:B第二章测试1.四面体的表面建模中，可用四个三角形来描述四面体的表面，每个三角形包含三个点，因此，四面体中点的总个数为（）。
A:12B:6C:4D:9答案:C2.三次BEZIER曲线有几个控制点？（）A:3B:5C:4D:6答案:C3.三次BEZIER曲线经过几个控制点？（）A:3B:4C:2D:1答案:C4.不经过Y轴的斜线绕Y轴旋转得到的曲面是（）A:半球面B:球面C:柱面D:圆台面答案:B5.BEZIER曲线上的所有点都是由控制点经过插值得到的。
（）A:错B:对答案:A第三章测试1.通过变换可以将单位圆变成长半轴2短轴0.5的椭圆，具体实施步骤是（）。
A:水平方向做平移变换，竖值方向做平移变换B:水平方向做拉伸变换，竖值方向做平移变换C:水平方向做收缩变换，竖值方向做拉伸变换D:水平方向做拉伸变换，竖值方向做收缩变换答案:B2.变换前后二线夹角保持不变的保角变换有（）A:镜像B:旋转C:平移D:缩放答案:D3.水平方向的剪切变换，如果表达为x’=ax+by y’=c x+dy,则有（）。
A:b=1,c=1,d=0B:a=0,b=1,c=1C:a=1,b=0,d=1D:a=1,c=0,d=1答案:D4.正交变换不包括（）。
A:剪切B:镜像C:旋转D:平移答案:A5.变换的复合运算不满足交换律。
计算机图形学总复习
第一章：（蓝色字体为部分答案）●计算机图形学的定义？计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科。
●计算机图形学常见的应用领域有哪些？（应用领域的标题）●计算机图形学的相关学科有哪些？和计算机图形学互逆的学科是？●CRT中为什么需要刷新？刷新频率是什么？由于荧光物质存在余晖时间，为了让荧光物质保持一个稳定的亮度值，电子束必须不断的重复描绘出原来的图形，这个过程叫做刷新刷新频率：每秒钟重绘屏幕的次数（次/秒、HZ)●彩色CRT和单色CRT的区别：⏹在荧光屏的内表面安装一个影孔板，用于精确定位像素的位置⏹CRT屏幕内部涂有很多组呈三角形的荧光粉，每一组由三个荧光点，三色荧光点由红、绿、蓝三基色组成（一组荧光点对应一个像素）⏹三支电子枪, 分别与三基色相对应●光栅扫描显示器中帧缓存是什么？位面是什么？⏹存储用于刷新的图像信息。
也就是存储屏幕上像素的颜色值。
⏹帧缓存的单位是位面。
⏹光栅扫描显示器屏幕上有多少个像素，该显示器的帧缓存的每个位面就有多少个一位存储器●1024×1024像素组成的24位真彩色光栅扫描显示器所需要的最小帧缓存是多少？第二章●什么是CDC？在微软基类库MFC中，CDC类是定义设备上下文对象的基类，所有绘图函数都在CDC基类中定义。
⏹简述CDC的4个派生类的名称，以及作用CClientDC类：显示器客户区设备上下文类CClientDC只能在窗口的客户区（不包括边框、标题栏、菜单栏以及状态栏的空白区域）进行绘图CMetaFileDCCMetaFileDC封装了在一个Windows图元文件中绘图的方法CPaintDC类该类一般用在响应WM_PAINT消息的成员函数OnPaint()中使用CWindowDC类整个窗口区域的显示器设备上下文类，包括客户区和非客户区（即窗口的边框、标题栏、菜单栏以及状态栏）⏹什么是映射模式？映射模式定义了Windows如何将绘图函数中指定的逻辑坐标映射为设备坐标输出到显示器或者打印机上。
计算机图形学_完整版 ppt课件
三维观察设备 虚拟现实系统的输出显示设备 ……
输入设备
键盘、鼠标 按钮盒、旋钮 跟踪球、空间球 操作杆 触觉反馈设备 数据手套、数据衣 数字化仪 扫描仪 触摸板 光笔 ……
硬拷贝设备
打印机 喷墨 激光 ……
绘图仪 台式 大型滚动传送式 ……
图形硬件系统组成模块示意图：
或称图形坐标系、用户坐标系、全局坐标系 如在世界坐标系中进行装配
观察坐标系（viewing coordinate）
对场景进行观察所对应的坐标系 对象经变换到该场景的一个二维投影——投影变换
规范化坐标系（normalized coordinate）
可使图形软件与特定输出设备的坐标范围无关 坐标范围：-1～1，或0 ～ 1 等等
在场景中对物体移动、旋转、缩 放、扭曲等，或转换模型坐标系
3D→2D，并对观察区域进行裁 剪和缩放
一种伪变换，对窗口上的最终输 出进行移动、缩放等
三维几何变换
可用4×4矩阵操作统一表示二维和三维几何变换
缩放、旋转、 对称、错切等
平移
投影
整体缩放
基本变换：平移、旋转、缩放
复合变换：可由平移、旋转、缩放和其他变换的矩阵乘积 （合并）形成。
图元的绘制、显示过程
顶点 法向量、颜色、纹理… 像素
图元操作、像素操作 光栅化（扫描转换）
像素信息 帧缓存 显示器
调用底层函数，如 setPixel (x,y)；将当 前像素颜色设定值存 入帧缓存的整数坐标 位置（x,y）处。
图元描述与操作
几何图元由一组顶点（Vertex）描述 这一组顶点可以是一个或是多个。每个顶点信息二维或 三维，使用 2~4 个坐标。顶点信息由位置坐标、颜色 值、法向量、纹理坐标等组成。
输入设备
键盘、鼠标 按钮盒、旋钮 跟踪球、空间球 操作杆 触觉反馈设备 数据手套、数据衣 数字化仪 扫描仪 触摸板 光笔 ……
硬拷贝设备
打印机 喷墨 激光 ……
绘图仪 台式 大型滚动传送式 ……
图形硬件系统组成模块示意图：
或称图形坐标系、用户坐标系、全局坐标系 如在世界坐标系中进行装配
观察坐标系（viewing coordinate）
对场景进行观察所对应的坐标系 对象经变换到该场景的一个二维投影——投影变换
规范化坐标系（normalized coordinate）
可使图形软件与特定输出设备的坐标范围无关 坐标范围：-1～1，或0 ～ 1 等等
在场景中对物体移动、旋转、缩 放、扭曲等，或转换模型坐标系
3D→2D，并对观察区域进行裁 剪和缩放
一种伪变换，对窗口上的最终输 出进行移动、缩放等
三维几何变换
可用4×4矩阵操作统一表示二维和三维几何变换
缩放、旋转、 对称、错切等
平移
投影
整体缩放
基本变换：平移、旋转、缩放
复合变换：可由平移、旋转、缩放和其他变换的矩阵乘积 （合并）形成。
图元的绘制、显示过程
顶点 法向量、颜色、纹理… 像素
图元操作、像素操作 光栅化（扫描转换）
像素信息 帧缓存 显示器
调用底层函数，如 setPixel (x,y)；将当 前像素颜色设定值存 入帧缓存的整数坐标 位置（x,y）处。
图元描述与操作
几何图元由一组顶点（Vertex）描述 这一组顶点可以是一个或是多个。每个顶点信息二维或 三维，使用 2~4 个坐标。顶点信息由位置坐标、颜色 值、法向量、纹理坐标等组成。
计算机图形学第讲优秀课件
的和减去一张双线性插值曲面得到的：
r (u, v) r1 (u, v) r2 (u, v) r3 (u, v)
r r 1 2 ( u ( u , v , ) v ) ( 1 ( 1 u ) v r ) ( r 0 ( , u v , ) 0 ) u r v ( r 0 , ( v u ) , 1 )r(u,v)(1u,u) r r 1 00 0
计算机图形学第讲
第7章 曲线与曲面
曲线曲面的计算机辅助设计源于20世纪60年代的飞机和汽车工业。
Ø1963年美国波音公司的Ferguson提出用于飞机设计的参数三次方程；
Ø1962年法国雷诺汽车公司的Bézier于提出的以逼近为基础的曲线曲面设 计系统UNISURF，此前de Casteljau大约于1959年在法国另一家汽车公司 雪铁龙的CAD系统中有同样的设计，但因为保密的原因而没有公布；
u1u
m
及其上的及调配函数
i
(u)
参数v的分割：v0v1 vn 及其上的及调 配函数 i (u)
r (u, v)
v
定义在uv 平面的矩形区域上的这
张曲面称为张量积曲面。 张量积曲面的特点是将曲面问题化
解为简单的曲线问题来处理，适用于
映
射
u
拓扑上呈矩形的曲面形状。
空间域
参数域
a00
r(u, v) (0(u)
x x(u,v)
其参数表达式为：y y(u,v)
z z(u,v)
曲面的矢量方程为：
r r(u,v) r(x(u,v), y(u,v), z(u,v))
参数u、v的变化区间常取为单位正方形，即u,v∈[0,1]。x，y，
z都是u和v二元可微函数。当(u，v)在区间[0，1]之间变化时，
计算机图形学第七章
2020/4/11
扫描线算法
• 扫描线算法利用了相邻像素之间的连贯 性，避免了反复求交的运算。
• 扫描线算法综合利用了区域的连贯性， 扫描线的连贯性和边的连贯性。
2020/4/11
区域的连贯性
• 假设多边形P的顶点Pi(xi,yi),i=0,1,2…n
• 各个顶点Pi的纵坐标按yi递减排序：
•
yi0, yi1, yi2… yin
•
flood-fill-4(x+1,y,old_color,new_color)
x域累加Δx，即x:=x+Δx • 5)将当前扫描线的纵坐标值y累加1，即
y:=y+1
2020/4/11
扫描线算法的优缺点
• 优点：效率高。 • 缺点：程序复杂，需要排序。
2020/4/11
边缘填充算法
• 由于扫描线算法需要对多边形的边进行 排序，如果采用求余的方法，就不用对 边进行排序了。
2020/4/11
2020/4/11
interior_point如何变化
• 此布尔变量起始在多边形外，初始值为 false，每碰到一个边界像素，就取反。
2020/4/11
边界标志算法的优缺点
• 优点：避免了对帧缓冲器中大量元素的 多次赋值，速度与扫描线算法相当。
• 缺点：需逐条扫描线对帧缓冲器中的元 素进行搜索和比较。
具体表现形式
• 内点表示的4连通区域 • 边界表示的4连通区域 • 内点表示的8连通区域 • 边界表示的8连通区域
2020/4/11
两种连通性的边界不同
• 同一个区域可以看成是4连通区域，也可 以看成是8连通区域，但是两者的边界是 不同的。
• 4连通区域的边界是8连通区域； 8连通 区域的边界是4连通区域。
扫描线算法
• 扫描线算法利用了相邻像素之间的连贯 性，避免了反复求交的运算。
• 扫描线算法综合利用了区域的连贯性， 扫描线的连贯性和边的连贯性。
2020/4/11
区域的连贯性
• 假设多边形P的顶点Pi(xi,yi),i=0,1,2…n
• 各个顶点Pi的纵坐标按yi递减排序：
•
yi0, yi1, yi2… yin
•
flood-fill-4(x+1,y,old_color,new_color)
x域累加Δx，即x:=x+Δx • 5)将当前扫描线的纵坐标值y累加1，即
y:=y+1
2020/4/11
扫描线算法的优缺点
• 优点：效率高。 • 缺点：程序复杂，需要排序。
2020/4/11
边缘填充算法
• 由于扫描线算法需要对多边形的边进行 排序，如果采用求余的方法，就不用对 边进行排序了。
2020/4/11
2020/4/11
interior_point如何变化
• 此布尔变量起始在多边形外，初始值为 false，每碰到一个边界像素，就取反。
2020/4/11
边界标志算法的优缺点
• 优点：避免了对帧缓冲器中大量元素的 多次赋值，速度与扫描线算法相当。
• 缺点：需逐条扫描线对帧缓冲器中的元 素进行搜索和比较。
具体表现形式
• 内点表示的4连通区域 • 边界表示的4连通区域 • 内点表示的8连通区域 • 边界表示的8连通区域
2020/4/11
两种连通性的边界不同
• 同一个区域可以看成是4连通区域，也可 以看成是8连通区域，但是两者的边界是 不同的。
• 4连通区域的边界是8连通区域； 8连通 区域的边界是4连通区域。
计算机图形学知识要点
单元分解法优缺点
优点
表示简单 容易实现几何变换 基本体素可以按需选择，表示范围较广 可以精确表示物体 物体的表示不唯一 物体的有效性难以保证 空间位置枚举表示----同样大小立方体粘合在一起表示 物体 八叉树表示----不同大小的立方体粘合在一起表示物体 单元分解表示----多种体素粘合在一起表示物体
阴极射线管(CRT)：光栅扫描图形显示器； 平板显示器：液晶显示器、等离子体显示板等； 光点、像素、帧缓存（frame buffer）、位平面；三种 分辨率（屏幕、显示、存储）； 黑白、灰度、彩色图形的实现方法（直接存储颜色数据、 颜色查找表）； 光栅图形显示子系统的结构
基本概念
第四章 图形的表示与数据结构
2、规则三维形体的表示
形体表示的分类 线框模型
缺点 多边形表，拓扑信息： 显示和隐式表示
表面模型
显示表示：在数据结构中显式的存储拓扑结构。例如，翼边结构 表示（Winged Edges Structure） 隐式表示：即根据数据 之间的关系在运行时实
时的解算。 平面方程 多边形网格 分解表示、构造表示、边界表示
Bresenham算法绘制圆弧
基本原理 从（0，R）点，顺时针开始； 上一个确定像素点为p（x, y），则下一个像素点只 能是p1和p2中的一个；
P(x, y) P1(x＋1, y)
p2 (x＋1, y－1)
误差判据：像素点到圆心的距离平方与半径平方之 差； 一般关系式取值对应的几何意义，即和下一个像素 的对应关系；
3、椭圆的光栅化方法
【中南大学】计算机图形学习题及答案
计算机图形学作业答案第一章序论第二章图形系统1．什么是图像的分辨率？解答：在水平和垂直方向上每单位长度（如英寸）所包含的像素点的数目。
2．计算在240像素/英寸下640×480图像的大小。
解答：（640/240）×(480/240)或者（8/3）×2英寸。
3．计算有512×512像素的2×2英寸图像的分辨率。
解答：512/2或256像素/英寸。
第三章二维图形生成技术1．一条直线的两个端点是（0，0）和（6，18），计算x从0变到6时y所对应的值，并画出结果。
解答：由于直线的方程没有给出，所以必须找到直线的方程。
下面是寻找直线方程（y ＝mx＋b）的过程。
首先寻找斜率：m ＝⊿y/⊿x ＝（y2－y1）/（x2－x1）＝（18－0）/(6－0) ＝ 3 接着b在y轴的截距可以代入方程y＝3x＋b求出 0＝3（0）＋b。
因此b＝0，所以直线方程为y＝3x。
2．使用斜截式方程画斜率介于0°和45°之间的直线的步骤是什么？解答：（1）计算dx：dx＝x2－x1。
（2）计算dy：dy＝y2－y1。
（3）计算m：m＝dy/dx。
（4）计算b: b＝y1－m×x1（5）设置左下方的端点坐标为（x，y），同时将x end设为x的最大值。
如果dx < 0，则x＝x2、y＝y2和x end＝x1。
如果dx > 0,那么x＝x1、y＝y1和x end＝x2。
（6）测试整条线是否已经画完，如果x > x end就停止。
（7）在当前的（x，y）坐标画一个点。
（8）增加x：x＝x＋1。
（9）根据方程y＝mx＋b计算下一个y值。
（10）转到步骤（6）。
3．请用伪代码程序描述使用斜截式方程画一条斜率介于45°和－45°（即|m|>1）之间的直线所需的步骤。
假设线段的两个端点为（x1，y1）和（x2，y2），且y1<y2int x = x1, y = y1;float x f, m = （y2－y1）/（x2－x1）, b = y1－mx1;setPixel( x, y );/*画一个像素点*/while( y < y2 ) {y++;x f = ( y－b)/m;x = Floor( x f +0.5 );setPixel( x, y );}4．请用伪代码程序描述使用DDA算法扫描转换一条斜率介于－45°和45°（即|m| ≤1）之间的直线所需的步骤。
计算机图形学基础教程课件
i 0
n
n! Bi ,n (t ) t i (1 t ) n i i!(n i)!
Bernstein基函数有如下性质： 1 非负性 Bi ,n (t ) 0 2 权性
n B ( t ) ((1 t ) t ) 1 i ,n i 0 n
3 对称性 B (t ) B i ,n ni ,n (1 t ), i 1, 2,
7.4 BEZIER曲线
法国雷诺汽车公司的工程师Bezier 和法国雪铁龙汽车公司的de Casteljiau分别提出了一种新的参数曲 线表示方法，称为Bezier曲线。
Bezier的想法从一开始就面向几何而不是面 向代数。Bezier曲线由控制多边形惟一定义， Bezier曲线只有第一个顶点和最后一个顶点落在 控制多边形上，且多边形的第一条和最后一条边 表示了曲线在起点和终点的切矢量方向，其它顶 点则用于定义曲线的导数、阶次和形状，曲线的 形状趋近于控制多边形的形状，改变控制多边形 的顶点位置就会改变曲线的形状。绘制Bezier曲 线的直观交互性使得对设计对象的控制达到了直 接的几何化程度，使用起来非常方便。几种典型 的三次Bezier曲线如图7-7所示。
张力参数在Cardinal样条曲线中的作用
记s (1 u ) / 2, 用类似Hermite曲线样条中的方法， 将Cardinal边界条件代入式7-7可以得到： s 2 s s 2 s Pi 1 2s s 3 3 2s s P i 3 2 P(t ) [t t t 1] s 0 s 0 Pi 1 1 0 0 Pi 2 0 s 2 s s 2 s 2s s 3 3 2s s 称为Cardinal矩阵。 Mc s 0 s 0 1 0 0 0
n
n! Bi ,n (t ) t i (1 t ) n i i!(n i)!
Bernstein基函数有如下性质： 1 非负性 Bi ,n (t ) 0 2 权性
n B ( t ) ((1 t ) t ) 1 i ,n i 0 n
3 对称性 B (t ) B i ,n ni ,n (1 t ), i 1, 2,
7.4 BEZIER曲线
法国雷诺汽车公司的工程师Bezier 和法国雪铁龙汽车公司的de Casteljiau分别提出了一种新的参数曲 线表示方法，称为Bezier曲线。
Bezier的想法从一开始就面向几何而不是面 向代数。Bezier曲线由控制多边形惟一定义， Bezier曲线只有第一个顶点和最后一个顶点落在 控制多边形上，且多边形的第一条和最后一条边 表示了曲线在起点和终点的切矢量方向，其它顶 点则用于定义曲线的导数、阶次和形状，曲线的 形状趋近于控制多边形的形状，改变控制多边形 的顶点位置就会改变曲线的形状。绘制Bezier曲 线的直观交互性使得对设计对象的控制达到了直 接的几何化程度，使用起来非常方便。几种典型 的三次Bezier曲线如图7-7所示。
张力参数在Cardinal样条曲线中的作用
记s (1 u ) / 2, 用类似Hermite曲线样条中的方法， 将Cardinal边界条件代入式7-7可以得到： s 2 s s 2 s Pi 1 2s s 3 3 2s s P i 3 2 P(t ) [t t t 1] s 0 s 0 Pi 1 1 0 0 Pi 2 0 s 2 s s 2 s 2s s 3 3 2s s 称为Cardinal矩阵。 Mc s 0 s 0 1 0 0 0
第七章 图形的表示
数学中的点、线、面是其所代表的真实世界中的 对象中的一种抽象，它们之间存在着一定的差距。例 如，数学中的平面是二维的，它没有厚度，体积为0； 而在真实世界中，一张纸无论多么薄，它也是一个三 维体具有一定的体积。这种差距造成了在计算机中以 数学方法描述的形体可能是无效的，即在真实世界中 可能不存在。尽管在有的情况下要构造无效形体，但 用于计算机辅助设计与制造系统设计生产的形体必须 是有效的，所以在实体造型中必须保证实体的有效性 ，原则上的标准是要求“客观存在”。
第7章 图形的表示
图形的表示方法一直是计算机图形学关注的主要问 题。在计算机图形学发展的旱期，计算机图形系统的性 能较差，线框模型是表示三维物体的主要方法。线框模 型仅仅通过定义物体边界的直线和曲线来表示三维物体 ，其特点是模型简单目运算速度较快，但由于每一条直 线或四线都是单独构造出来的，不存在面的信息，因此 三维物体信息的表示不全面，在许多场合不能满足要求 。事实上，研究表示复杂形体的模型与数据结构是计算 机造型等技术的关键。经过近20年的发展，买体的边界 表示法、扫描表示法、构造的实体几何法及八叉树表示 法等已经发展成熟。
7.2 实体表示的三种模型
形体在计算机中常用线框模型、表面模型和实体 模型三种模型来表示。线框模型是在计算机图形学和 CAD、CAM领域中最早用来表示形体的模型，并且至 今仍在广泛应用。线框模型是用顶点和棱边表示形体 ，其特点是结构简单，易于理解，并是表面和实体模 型的基础。如前所述，用线框模型表示形体时曲面的 轮廓线无法随视角的变化而改变；线框模型无法给出 全部连续的几何信息，只有顶点和棱边，不能明确地 定义给定的点与形体之间的关系，以致不能用线框模 型处理计算机图形学和CAD、CAM领域中的多数问题 ，如图7.8所示。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第七章
光栅图形的扫描转换与区域填色
可编辑ppt
1
多边形的两种表示方法
可编辑ppt
2
两种表示方法的优缺点
可编辑ppt
3
什么是多边形的扫描转换
可编辑ppt
4
逐点判断算法
算法思想：逐个像素判别，检测其是否 在多边形内部，从而给出位于多边形内 部的像素集合。
可编辑ppt
5
逐点判断算法的具体实现
假设P=P0P1P2…PnP0为一个给定多边形， P0,P1,P2…Pn为其顶点表示。 假设inside(P,x,y)是验证点(x,y)是否在多 边形P内的布尔函数。
可编辑ppt
20
出现奇点的两种情况的讨论
极值点就是附近的点都比其小或都比其 大，满足数学表达式为(yi-1-yi)(yi+1-yi)>0 不是极值点的顶点称为非极值点。
可编辑ppt
21
对于奇点的两种情况的处理
可编辑ppt
22
扫描线算法的数据结构
可编辑ppt
23
边的分类表ET
边的分类表ET是按边下端点的纵坐标y 对非水平边进行分类的链表数组。
可编辑ppt
24
边的活化表AEL
边的活化表AEL由与当前扫描线相交的
所有多边形的边组成，它记录了多边形
边沿扫描线的交点序列，并根据递推式：
xe,ir
xd, jr
1 mr
不断刷新交点序列。
可编辑ppt
25
扫描线算法的描述
步骤1：(y初始化)建立ET表，并且取扫 描线纵坐标y的初始值为ET中非空元素的 最小序列。
可编辑ppt
27
子算法步骤
2)若相对于当前扫描线，边的活化链表 AEL非空，则将AEL中边两两依次配对 (位置位于1,2的配对；位置位于3,4的配 对)，依次配对的边的内部点(像素)按多 边形的颜色属性进行着色。
可编辑ppt
28
子算法步骤
3)将边的活化链表AEL中ymax＝y的边删去 4)将边的活化链表AEL剩下的每一条边的 x域累加Δx，即x:=x+Δx 5)将当前扫描线的纵坐标值y累加1，即 y:=y+1
xerxdrxxdrm 1r
可编辑ppt
17
怎样得到y=e上的交点序列
通过递推式可以算出与y=e和y=d都相交 的点 若再求出与扫描线y=d不相交但与下一扫 描线y=e相交的所有边PqPq+1上的交点xeq 然后把这些点按底层的顺序排列，就能 得到了y=e上的交点序列
可编辑ppt
18
边的连贯性
当取某一整数k，0<=k<=n-1，使
可编辑ppt
6
Inside函数的实现原理
计算从(x,y)到(+∞,y)的射线与多边形的交 点个数。 若交点个数是奇数的话，就表明该点在 多边形内部，否则该点在多边形外部。
可编辑ppt
7
逐点判断算法的具体实现
假设framebuffer(x,y)是与(x,y)对应的帧 缓冲器中的元素，用以存放对应像素的 颜色值。设polygon_color为多边形内的 颜色值，background_color为背景颜色。可编辑pLeabharlann t13分割后区域的分类
这些梯形分为两类：在多边形P内部和在 多边形P外部。 两类梯形交替地排列在长方形区域内。 如果知道了某点q所在区域在多边形内 (或外)，就能知道整个长方形区域内的 梯形排列情况。 此性质称为区域的连贯性。
可编辑ppt
14
扫描线的连贯性
假设e为一整数满足 yineyi0若扫描 线y=e与多边形P的边Pi-1Pi相交，则记 其交点的横坐标xei。 现在假设xei1,xei2,…,xeil为扫描线与P的 边界各交点的横坐标的递增序列，称为 交点序列。
步骤2：(AEL初始化)将边的活化链表 AEL设置为空。
步骤3：按从下到上的顺序对纵坐标值为 y的扫描线(当前扫描线)执行子算法，直 到ET和AEL都变为空为止。
可编辑ppt
26
子算法步骤
1)如果边分类表ET中第y类元素为非空， 则将属于该类的所有边从ET中取出并插 入边的活化链表AEL中，AEL中各边按x的 值(当x的值相等时，按Δx值)递增方式 排序。
可编辑ppt
15
交点序列的性质
l是偶数。 在该扫描线上只有区段(xeik,xei,k+1)， (k=1,3,5…l-1)位于多边形P内，其余均在 多边形P外，两种区段沿扫描线相间排列。 此性质称为扫描线的连贯性。
可编辑ppt
16
交点序列
若d=e-1，则位于扫描线y=d上的交点序 列为xdj1,xdj2,…,xdjk。 若多边形P的边Pr-1Pr与扫描线y=e和 y=d都相交，则xer和xdr满足：
可编辑ppt
8
逐点判断算法的伪代码程序
for y:=screen_ymin to screen_ymax do for x:=screen_xmin to screen_xmax do if inside(P,x+0.5,y+0.5) then
setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_co
yi,k1e,dyi,k
1)两序列元素数个数相等
2)点(xeir,e)与(xdjr,d)位于多边形同一条边
上，即ir=jr，得到
xe,ir xd, jr
1 mr
由上式就可递推出xeir。
可编辑ppt
19
奇点的处理
当扫描线与多边形P的边界的交点是P的 顶点时，该交点称为奇点。 由于连贯性，每一条扫描线与多边形P的 边界交点个数都是偶数。但是过奇点的 扫描线可能出现奇数。
lor)
可编辑ppt
9
逐点判断算法的优缺点
优点：简单，易于理解。 缺点：忽略了像素与像素之间的联系， 如果整个平面有几千万个像素，也要一 一进行判别，要做大量的计算工作，效 率太低。
可编辑ppt
10
扫描线算法
扫描线算法利用了相邻像素之间的连贯 性，避免了反复求交的运算。 扫描线算法综合利用了区域的连贯性， 扫描线的连贯性和边的连贯性。
可编辑ppt
11
区域的连贯性
假设多边形P的顶点Pi(xi,yi),i=0,1,2…n
各个顶点Pi的纵坐标按yi递减排序：
yi0, yi1, yi2… yin
其中yi,k>= yi,k+1
可编辑ppt
12
区域的分割
现在作两条扫描线y=yi,k和y=yi,k+1，这 两条扫描线之间的区域被多边形分割成 若干个梯形。 梯形上下两底分别为两条扫描线，腰在 多边形P的边上或在显示屏幕的边界上。
光栅图形的扫描转换与区域填色
可编辑ppt
1
多边形的两种表示方法
可编辑ppt
2
两种表示方法的优缺点
可编辑ppt
3
什么是多边形的扫描转换
可编辑ppt
4
逐点判断算法
算法思想：逐个像素判别，检测其是否 在多边形内部，从而给出位于多边形内 部的像素集合。
可编辑ppt
5
逐点判断算法的具体实现
假设P=P0P1P2…PnP0为一个给定多边形， P0,P1,P2…Pn为其顶点表示。 假设inside(P,x,y)是验证点(x,y)是否在多 边形P内的布尔函数。
可编辑ppt
20
出现奇点的两种情况的讨论
极值点就是附近的点都比其小或都比其 大，满足数学表达式为(yi-1-yi)(yi+1-yi)>0 不是极值点的顶点称为非极值点。
可编辑ppt
21
对于奇点的两种情况的处理
可编辑ppt
22
扫描线算法的数据结构
可编辑ppt
23
边的分类表ET
边的分类表ET是按边下端点的纵坐标y 对非水平边进行分类的链表数组。
可编辑ppt
24
边的活化表AEL
边的活化表AEL由与当前扫描线相交的
所有多边形的边组成，它记录了多边形
边沿扫描线的交点序列，并根据递推式：
xe,ir
xd, jr
1 mr
不断刷新交点序列。
可编辑ppt
25
扫描线算法的描述
步骤1：(y初始化)建立ET表，并且取扫 描线纵坐标y的初始值为ET中非空元素的 最小序列。
可编辑ppt
27
子算法步骤
2)若相对于当前扫描线，边的活化链表 AEL非空，则将AEL中边两两依次配对 (位置位于1,2的配对；位置位于3,4的配 对)，依次配对的边的内部点(像素)按多 边形的颜色属性进行着色。
可编辑ppt
28
子算法步骤
3)将边的活化链表AEL中ymax＝y的边删去 4)将边的活化链表AEL剩下的每一条边的 x域累加Δx，即x:=x+Δx 5)将当前扫描线的纵坐标值y累加1，即 y:=y+1
xerxdrxxdrm 1r
可编辑ppt
17
怎样得到y=e上的交点序列
通过递推式可以算出与y=e和y=d都相交 的点 若再求出与扫描线y=d不相交但与下一扫 描线y=e相交的所有边PqPq+1上的交点xeq 然后把这些点按底层的顺序排列，就能 得到了y=e上的交点序列
可编辑ppt
18
边的连贯性
当取某一整数k，0<=k<=n-1，使
可编辑ppt
6
Inside函数的实现原理
计算从(x,y)到(+∞,y)的射线与多边形的交 点个数。 若交点个数是奇数的话，就表明该点在 多边形内部，否则该点在多边形外部。
可编辑ppt
7
逐点判断算法的具体实现
假设framebuffer(x,y)是与(x,y)对应的帧 缓冲器中的元素，用以存放对应像素的 颜色值。设polygon_color为多边形内的 颜色值，background_color为背景颜色。可编辑pLeabharlann t13分割后区域的分类
这些梯形分为两类：在多边形P内部和在 多边形P外部。 两类梯形交替地排列在长方形区域内。 如果知道了某点q所在区域在多边形内 (或外)，就能知道整个长方形区域内的 梯形排列情况。 此性质称为区域的连贯性。
可编辑ppt
14
扫描线的连贯性
假设e为一整数满足 yineyi0若扫描 线y=e与多边形P的边Pi-1Pi相交，则记 其交点的横坐标xei。 现在假设xei1,xei2,…,xeil为扫描线与P的 边界各交点的横坐标的递增序列，称为 交点序列。
步骤2：(AEL初始化)将边的活化链表 AEL设置为空。
步骤3：按从下到上的顺序对纵坐标值为 y的扫描线(当前扫描线)执行子算法，直 到ET和AEL都变为空为止。
可编辑ppt
26
子算法步骤
1)如果边分类表ET中第y类元素为非空， 则将属于该类的所有边从ET中取出并插 入边的活化链表AEL中，AEL中各边按x的 值(当x的值相等时，按Δx值)递增方式 排序。
可编辑ppt
15
交点序列的性质
l是偶数。 在该扫描线上只有区段(xeik,xei,k+1)， (k=1,3,5…l-1)位于多边形P内，其余均在 多边形P外，两种区段沿扫描线相间排列。 此性质称为扫描线的连贯性。
可编辑ppt
16
交点序列
若d=e-1，则位于扫描线y=d上的交点序 列为xdj1,xdj2,…,xdjk。 若多边形P的边Pr-1Pr与扫描线y=e和 y=d都相交，则xer和xdr满足：
可编辑ppt
8
逐点判断算法的伪代码程序
for y:=screen_ymin to screen_ymax do for x:=screen_xmin to screen_xmax do if inside(P,x+0.5,y+0.5) then
setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_co
yi,k1e,dyi,k
1)两序列元素数个数相等
2)点(xeir,e)与(xdjr,d)位于多边形同一条边
上，即ir=jr，得到
xe,ir xd, jr
1 mr
由上式就可递推出xeir。
可编辑ppt
19
奇点的处理
当扫描线与多边形P的边界的交点是P的 顶点时，该交点称为奇点。 由于连贯性，每一条扫描线与多边形P的 边界交点个数都是偶数。但是过奇点的 扫描线可能出现奇数。
lor)
可编辑ppt
9
逐点判断算法的优缺点
优点：简单，易于理解。 缺点：忽略了像素与像素之间的联系， 如果整个平面有几千万个像素，也要一 一进行判别，要做大量的计算工作，效 率太低。
可编辑ppt
10
扫描线算法
扫描线算法利用了相邻像素之间的连贯 性，避免了反复求交的运算。 扫描线算法综合利用了区域的连贯性， 扫描线的连贯性和边的连贯性。
可编辑ppt
11
区域的连贯性
假设多边形P的顶点Pi(xi,yi),i=0,1,2…n
各个顶点Pi的纵坐标按yi递减排序：
yi0, yi1, yi2… yin
其中yi,k>= yi,k+1
可编辑ppt
12
区域的分割
现在作两条扫描线y=yi,k和y=yi,k+1，这 两条扫描线之间的区域被多边形分割成 若干个梯形。 梯形上下两底分别为两条扫描线，腰在 多边形P的边上或在显示屏幕的边界上。