计算机图形学 - 计算机与软件学院

Report
计算机图形学
傅向华
深圳大学信息工程学院
Email: [email protected]
电话: 26534380
办公楼339
1
课程性质:综合选修课
学分:2.5
上课时间地点:
每周四1,2节 A209教室,双周周五3,4节 D506机房
教材:
倪明田、吴良芝,计算机图形学,北京大学出版社,1999.11
主要参考书:
1. 孙家广、胡事民,计算机图形学基础教程,清华大学出版社,2005.2
2. David F. Rogers,Procedural Elements for computer Graphics,机械工业出版社,
2004.8 (计算机图形学的算法基础)
3. Zhigang Xiang, Roy Plastock著,陈泽琳,陈展文,陈屹等译. 计算机图形学习题与解答.
机械工业出版社.
2
考试(成绩分布):
平时成绩 30-40%,期末考试成绩60-70%
3
第一章 计算机图形学概述
•
•
•
•
•
•
计算机图形学的研究内容
计算机图形学应用举例
计算机图形学发展历史
图形显示设备
交互式图形系统的逻辑结构
当前的研究动态
4
计算机图形学的研究内容(1/2)
• 图形:计算机图形学的研究对象
– 能在人的视觉系统中产生视觉印象的客观对象
– 包括自然景物、拍摄到的图片、用数学方法描述的图形等等
• 构成图形的要素
– 几何要素:刻画对象的轮廓、形状等
– 非几何要素:刻画对象的颜色、材质等
• 计算机中表示图形的方法
– 点阵表示
• 枚举出图形中所有的点
• 简称为图像(数字图像)
– 参数表示
• 形状参数+属性参数
• 简称为图形
5
计算机图形学的研究内容(2/2)
• 计算机图形学的研究内容
• 图形的输入
• 图形的处理
• 图形的输出
• 与相关学科的关系
图像变换
(图像处理)
数
字
图
像
图像生成(计算机图形学)
数
据
模
型
模型变换
(计算几何)
模型(特征)提取
(计算机视觉,模式识别)
6
计算机图形学应用举例(1/8)
• 图形用户界面
– 发展历程
命令行界面CLI
人
机 图形用户界面GUI
界
面 多通道用户界面(MMI)
– 操作系统
• Macintosh,OS/2,Windows,Unix/X-Window
7
计算机图形学应用举例(2/8)
• 计算机辅助设计
– Computer-Aided Design
– 应用领域:飞机、轮船、汽车外形,大规模集成电路,建筑,服装,
玩具
– 优点:设计周期短,成本低,质量高
8
计算机图形学应用举例(3/8)
• 科学计算可视化
–
–
–
–
Scientific Visualization
必要性:直接分析大量的测量数据或统计数据有困难
目标:用图形表现抽象的数据
应用领域:医学,遥感,流场等等
波在单向环氧石墨中传播的可视化演示
9
计算机图形学应用举例(4/8)
• 科技、教育、商业领域的交互式绘图
股票趋势分析
10
计算机图形学应用举例(5/8)
• 计算机艺术
–
–
–
–
–
书法、艺术图片
输入工具:键盘、鼠标、手写笔等等
软件工具:PhotoShop、CorelDraw、PaintBrush等等
优点:功能多、创作轻松、调色方便等等
缺点:目前难以容入人的灵感(未来的研究课题)
11
计算机图形学应用举例(6/8)
• 地理信息系统
– Geographical Information System
– 建立在地理图形之上的关于各种资源的综合信息管理系统
– 例如百度地图搜索 (http://map.baidu.com/)
• 计算机动画及广告影视创作
– 传统动画:费时费力,质量差,
– 例子:《大闹天宫》,90*60*24=129,600张胶片,几十位动画
工作者近4年的时间 (1960 – 1964年),近7万张画作
– 计算机动画(Computer Animation):效率高,质量高
– 例子:《侏罗纪公园》
– 计算机动画创作工具:3D MAX, MAYA等等
12
计算机图形学应用举例(7/8)
• 电脑游戏
– 实时性
– 逼实性
– 蕴含了先进的图形处理技术
DirectX演示
• 多媒体系统
– 在计算机控制下,对多种媒体信息进行生成、操作、
表现、存储、通信、或集成的信息系统,其中媒体
至少应包括一种“连续媒体”及一种“离散媒体”。
– 计算机处理的常见媒体:文本、图形、图像、语音、
音频、视频、动画,与图形处理相关的是关键。
– 特点:媒体的多样性、操作的交互性、系统的集成性
13
计算机图形学应用举例(8/8)
• 虚拟现实系统
– Virtual Reality 或称虚拟环境(Virtual Environment)
– 是用计算机技术来生成一个逼真的三维视觉、听觉、触觉或嗅觉等
感觉世界,让用户可以从自己的视点出发,利用自然的技能和某些
设备对这一生成的虚拟世界客体进行浏览和交互考察。
– 主要研究用计算机模拟(构造)三维图形空间,并使用户能够自然
地与该空间进行交互。对三维图形处理技术的要求特别高。
– 20世纪80年代初,美国的DARPA为坦克编队作战训练开发了一个实
用的虚拟战场系统SIMNET。
– 1997年7月,地球上的工程师通过虚拟现实系统操纵距地1.9亿公里
的火星上的火星车。
– 输入输出设备,如头盔式显示器、立体耳机、头部跟踪系统以及数
据手套等。
14
计算机图形学应用举例(9/9)
• 网上虚拟现实:虚拟现实建模语言VRML (1994年3月在
日内瓦召开的第一届WWW大会上,首次正式提出了VRML这个
名字。)
VRML例子 (http://www.web3dchina.com/product.html)
校园漫游
15
计算机图形学发展历史
• 50年代,阴极射线管显示器出现,用于显示输出,不具交互
功能。
• 随后, 林肯实验室 战术防空系统SAGE 交互图形技术
诞生
• 1963 Ivan Sutherland研制SKETCH-PAD系统,第一台光
笔交互式CRT显示器, 奠基人
• 60年代中后期,计算机辅助设计系统在航空、汽车等领域
开展起来
• 80年代后,廉价图形输入输出和大容量存储介质的出现,
图形处理芯片的出现,使得交互式图形学广泛应用。
16
计算机图形学发展历史(1/7)
• 图形显示设备的发展
画线显示器(矢量显示器/随机扫描显示器)
存储管式显示器
刷新式光栅扫描显示器
60年代中后期出现,
只能绘制线条,任意
方向连续扫描
60年代末期, 具有内在的存储部件,
靶像,静态图像
70年代初, 以点阵形式表示图形.
点阵存放在专用缓冲区中,由视频
控制器负责扫描,显示图形.
平板显示器 (液晶显示器, 等离子显示器)
17
计算机图形学发展历史(2/7)
• 刷新式
电子束轰击荧光屏产生的亮点只能持续极短的时间,为了产生静
态的不闪烁的图像,电子束必须周期性地反复扫描所要绘制
的图形,这个过程称为刷新.
• 存储管式
内置金属网受到电子束轰击之后形成靶像,它可以持续发出电子,
在荧光屏上产生静态图像
• 画线显示器
– 只能显示线条
– 价格昂贵
• 存储管式显示器
– 无需刷新,价格较低
– 没有动态修改图形的能力
18
计算机图形学发展历史(3/7)
• 刷新式光栅扫描显示器
– 价格低
– 性能高
– 成为当前的主流显示器
等离子显示器
依靠高电压来激活显像单元中的特殊气体,使它产生紫外线来激发磷光物质发光。
用于比较大的屏幕,如等离子电视,大于40寸
液晶显示器
通过电流来改变液晶面板上的薄膜型晶体管内晶体的结构,使它显像。
用于比较小的屏幕,如30寸一下,电脑的显示器,液晶电视
19
计算机图形学发展历史(4/7)
• 图形输入设备的发展
– 第一阶段:控制开关、穿孔纸等等
– 第二阶段:键盘
– 第三阶段:二维定位设备,如鼠标、光笔、图形输入板、触
摸屏等等,
– 第四阶段:三维输入设备(如空间球、数据手套、数据衣),
用户的手势、表情等等
– 第五阶段:用户的思维?
发展方向是使人能够更自然、更方便地与计算机进行交互
20
计算机图形学发展历史(5/7)
21
计算机图形学发展历史(6/7)
22
计算机图形学发展历史(7/7)
• 图形软件的发展及软件标准的形成
– 发展历程
早期
70年代
1979年后
诸侯割据
标准讨论
标准形成
– 两类标准
• 官方标准(标准组织制定的标准):
核心图形系统CGS(Core Graphics System),1977年美国计算机协会公布
计算机图形接口CGI(Computer Graphics Interface), ISO公布;
计算机图形元标准CGM(Computer Graphics Metafile);
计算机图形核心系统GKS(Graphics Kernel System); 1984年 ISO和ANSI
程序员层次交互式图形系统PHIGS(Programmer’s Herarchical Interactive
Graphics System); 1986年ISO和ANSI
初始图形交换规范IGES(Initial Graphics Exchange Specification),1983年,
美国国家标准局;
• 工业标准(事实上的标准):SGI等公司的OpenGL,微软公司的
DirectX,X财团的Xlib(X-Windows),Adobe公司的PostScript等等
23
计算机图形学发展历史(7/7)
• 图形软件标准是指系统的各界面之间进行数据传递和通信的接口
标准,称为图形界面标准;供各种应用程序调用子程序功能及格
式标准,称为子程序界面标准。
•
•
•
•
•
交互式图形系统需要在四个层次上实现界面标准化
(1) 应用程序与它所处理的数据之间的数据接口
(2) 应用程序与图形软件包之间的接口
(3) 图形软件包与图形硬件之间的接口
(4) 数据文件接口
24
图形显示设备(1/21)
(阴极射线管显示器)
• 阴极射线管(CRT, cathode-ray tube)
– 组成:包括电子枪、聚焦系统、加速电极、偏转系统、荧光
屏
– 工作原理:电子枪发射电子束,经过聚焦系统、加速电极、
偏转系统,轰击到荧光屏的不同部位,被其内表面的荧光物
质吸收,发光产生可见的图形。
– 结构
25
图形显示设备(2/21)
– 荧光屏
(显示图形)
• 荧光物质:吸收电子束而发光
• 持续发光时间:电子束离开某点后,该点的亮度值衰减到初始值
1/10所需的时间
• 刷新(Refresh):为了让荧光物质保持一个稳定的亮度值,不断重
复绘制图形.
• 刷新频率:每秒钟重绘屏幕的次数
某种CRT产生稳定图像所需要的最小刷新频率
=1秒/荧光物质的持续发光时间
(例如)=1000ms/40ms=25Hz
• 像素(Pixel:Picture Cell):构成屏幕(图像)的最小元素
• 分辨率(Resolution):CRT在水平或竖直方向单位长度上能识别
的最大像素个数,单位通常为dpi(dots per inch)。在假定屏幕
尺寸一定的情况下,也可用整个屏幕所能容纳的像素个数描述,
如640*480,800*600,1024*768,1280*1024等等
26
图形显示设备(3/21)
• 彩色阴极射线管
– 产生彩色的常用方法:射线穿透法、影孔板法
– 射线穿透法
• 原理
荧光涂层
产生颜色
低速电子束
电子束
较低速电子束
较高速电子束
高速电子束
• 应用:画线显示器
• 优点:成本低
• 缺点:只等产生有限几种颜色
27
图形显示设备(4/21)
– 影孔板法
• 原理:影孔板被安装在荧光屏的内表面,用于精确定位像素的位
置
外层玻璃
影孔板
荧光涂层
28
图形显示设备(5/21)
– 影孔板的类型
• 点状影孔板
代表:大多数球面与柱面显像管
• 栅格式影孔板
代表:Sony的Trinitron (单枪三束)与Mitsubishi的
Diamondtron
显像管 (三枪三束)
两大好处:一是把相互平行的垂直铁线阵形安装在一个铁框
里,垂直部分没有任何东西阻挡,增强了电子流通量,也增
强了纵向方向的透光度,透出的光线比荫罩式显像管多一倍,
因而特丽珑显像管的明亮度和颜色饱和度要比其他的显像管
都要好;二是间条式栅罩的阻碍光率十分少,长时间使用后
也不会膨胀或变形,避免发生颜色突变或亮度变弱的情况。
• 沟槽式影孔板
代表:LG的Flatron显像管 (未来窗)
可以得到更大的电子流通量,也使荫罩网面的受力即稳定情
况比较好。
29
图形显示设备(6/21)
– 点状影孔板工作原理
• 红、绿、兰三基色
• 三色荧光点
• 三个电子枪
30
图形显示设备(7/21)
• 显示器能同时显示的颜色个数
如果每个电子枪有256个等级,则显示器能同时显
示256*256*256=16M种颜色,称为真彩系统
31
图形显示设备(8/21)
• 点距
32
图形显示设备(9/21)
• *纯平显示器*
– 走向平面的显像管
• 球面显象管:
– 表面:球面的一部分
– 时间:~90年代初
• 柱面显象管:
– 表面:柱面的一部分,垂直方向上平直,水平方向上有弯曲
– 时间:90年代中期
– 代表:Sony公司的Trinitron,Mitsubishi公司的Diamondtron
• 平面直角显象管
– 表面:球面的一部分,类似于平面
– 时间:90年代中后期
– 现在市场上的主流显象管
• 纯平显象管
– 表面:纯平面
– 时间:90年代后期
– 代表:Sony公司的FD Trinitron,Mitsubishi公司的Diamondtron,Samsung
公司的DanyFlat,LG公司的Flatron
– 今后的主流显象管
33
图形显示设备(11/21)
• 随机扫描显示系统
– 特点:电子束在任意方向上自由移动
– 逻辑部件:刷新存储器(Refreshing Buffer),显示处理器
(DPU:Display Processing Unit),CRT
– 系统结构
34
图形显示设备(12/21)
– 显示文件(Display File)
刷新存储器中所有绘图命令组成的文件
– 工作原理:
应用程序发出绘图命令,被解释成显示处理器可接受的命令格式,存放
在刷新存储器之中.组成一个显示文件,驱动电子枪在屏幕上绘图.
• 光栅扫描显示系统
–
–
–
–
–
特点:光栅扫描 (按固定的扫描线从左到右,从上到下进行扫描)
扫描线
帧 (一次扫描所产生的图像)
水平回扫期
垂直回扫期
35
图形显示设备(13/21)
36
– 绘图过程
图形显示设备(14/21)
37
图形显示设备(15/21)
– 逻辑部件:帧缓冲存储器(Frame Buffer),视频控制器
(Video Controller),显示处理器(Display Processor),
CRT
– 帧缓冲存储器
• 作用:存储屏幕上像素的颜色值
• 简称帧缓冲器,俗称显存
• 工作原理
帧缓冲器中的单元数目与显示器上的像素数相同,单元与象素一一对
应,各单元的数值决定了其对应的像素的颜色.
38
图形显示设备(16/21)
• 分辨率M*N、颜色个数K与显存大小V的关系
V  M  N  log2 K 
• 可以同时显示16兆种颜色的显示系统称为真彩显示系统
• 带宽T与分辨率、帧频F的关系
T  M NF
• 两个问题:显存问题和带宽问题
• 显存问题
– 高分辨率和真彩要求有大的显存;
1024*768真彩模式需要3M字节显存
– 曾经是个问题!
– 解决方法:采用查色表(Lookup Table)或称彩色表(Color Table)
– 查色表工作原理
帧缓冲器保存查色表各项的索引值.
39
图形显示设备(17/21)
• 带宽问题
– 高分辨率和高的刷新频率要求有高带宽
1024*768/85模式需要85M带宽
– 依然是个问题!
– 解决方法:隔行扫描(现在已经基本不用,主流地显示器都采用逐
行扫描方式)
– 隔行扫描的工作原理:把一帧分两场,即奇数场与偶数场
– 场频:==2*帧频
40
图形显示设备(18/21)
• 简单的光栅扫描图形显示系统的结构
• 较为典型的光栅扫描图形显示系统的结构
41
图形显示设备(19/21)
– 视频控制器
• 作用:负责刷新,建立缓冲单元与像素之间的一一对应
• 结构
Y
屏幕坐标
X
• 工作原理
• 双缓冲机制(Double Buffer)
可以同时进行读写
普通显卡=视频控制器+显存
42
图形显示设备(20/21)
– 显示处理器
• 作用:代替CPU完成部分图形处理功能,扫描转换、几何变换、
裁剪、光栅操作、纹理映射等等
• 具有专用显示处理器的光栅显示系统的结构
图形加速卡=视频控制器+显存+显示处理器
43
图形显示设备(21/21)
– 光栅显示系统的特点
• 优点:
–
–
–
–
–
成本低
易于绘制填充图形
色彩丰富
刷新频率一定,与图形的复杂程度无关
易于修改图形
优点使其占据了市场主流
• 缺点:
– 需要扫描转换
– 会产生混淆
缺点正在被克服
44
交互式系统的逻辑结构(1/5)
• 多数交互式图形系统的逻辑结构
–应用程序 用户通过其创建、修改、编辑应用模型
–应用模型 用户设计图形的数据表示
–图形软件包
由一系列输入输出汗水祖传,负责图形的最终显示
例子
Bmp
图像
PaintBrush
Windows
API
输入输
出设备
45
交互式系统的逻辑结构(2/5)
• 图形软件包
介于硬件设备和应用程序之间,起到桥梁作用
– 内容
•
•
•
•
图形系统管理程序
显示输出图元的程序
图形变换
交互处理程序
– 对图形软件包的一般要求
•
•
•
•
风格好,概念明确一致
易于使用,便于扩充和移植
具有良好的层次结构和模块结构
一般分为三层
最低层 设备驱动程序
中间层
最高层
完成基本图元生成,设备管理等
建立图形数据结构,定义,修改和输出图形
– 例子:Windows API, OpenGL, DirectX, X/Lib等等
46
交互式系统的逻辑结构(3/5)
• 应用模型
– 描述图形对象及他们之间的关系
例如空间中两个立方体的应用模型
包括描述图元的几何数据,属性数据以及相互关系的数据
– 与应用程序相关
– 数据模型:完全由数据刻画的应用模型
47
交互式系统的逻辑结构(4/5)
– 过程模型:有数据和一些过程共同刻画的应用模型
48
交互式系统的逻辑结构(5/5)
49
当前的研究动态(1/7)
• 造型技术(研究如何在计算机中构造二维、三维物体的模型,并合适表示)
– 规则形体:欧氏几何方法
(Bezier曲线、曲面、
非均匀有理B样条 NURBS)
– 不规则形体:
(不能用欧氏几何描述,如山,水,草,云,烟等)
• 分形几何方法
• 粒子系统
• 纹理映射
(表面纹理,几何纹理)
50
当前的研究动态(2/7)
– 实体造型 (特征造型,将物体表示成一组特征的集合)
– 基于物理的造型 (根据物体本身的物理特性及其所遵循的物理规律,自
动产生它在各种状态下的模型)
– 基于图像的造型
• 真实感图形绘制技术
–
–
–
–
光照明模型 (局部光照模型、整体光照模型)
绘制算法
快速算法,并行算法
基于图像的绘制 (通过图像分析从真实世界获取对象的几何信息和表面
纹理信息)
– 例子
51
当前的研究动态(3/7)
52
当前的研究动态(4/7)
53
当前的研究动态(5/7)
54
当前的研究动态(6/7)
55
当前的研究动态(7/7)
• 人机交互技术
三维空间的交互、多通道技术、交互的非精确性
• 与计算机网络技术的紧密结合
–
–
–
–
远程医疗与诊断
远程导航与维修
远程教育
VRML使用户在三维虚拟场景中漫游网络空间成为可能。
56
网络资源(7/7)
• 中国计算机图形学研究会
http://www.chinagraph.org/chinese/chinese.htm
57
第二章 一个简单的二维光栅图形软件包
Windows API简介
• 用图形软件包绘图
• 基本的交互处理
• 光栅操作
58
用图形软件包绘图(1/6)
• 图元的声明
– 绘图纸,屏幕,坐标系
– 扫描转换:将转换为(像素)点阵表示的图形
顶点(参数)
表示的图形
用户
扫描转换
点阵表示
的图形
显示系统
59
用图形软件包绘图(2/6)
SRGP支持的基本图元包括直线段,折线,多边形,圆弧,字符等.
– 点
COLORREF GetPixel( int x, int y ) const
COLORREF SetPixel( int x, int y, COLORREF crColor );
– 直线段
CPoint MoveTo( int x, int y );
BOOL LineTo( int x, int y );
– 折线
BOOL Polyline( LPPOINT lpPoints, int nCount );
60
用图形软件包绘图(3/6)
– 多变形和矩形
Polygon(LPPOINT lpPoints, int nCount)
Rectangle (int x1, int y1, int x2, int y2)
– 圆弧
BOOL AngleArc( int x, int y, int nRadius, float
fStartAngle, float fSweepAngle );
– 椭圆弧
BOOL Arc( int x1, int y1, int x2, int y2, int x3, int
y3, int x4, int y4 );x1,y1,x2,y2 左上,右下;X3,Y3起
始角射线上,X4,Y4终止角射线上
(x3,y3)
(x4,y4)
61
用图形软件包绘图(4/6)
• 图元的属性
– 线型、线宽
CPen ( int nPenStyle, int nWidth, COLORREF
crColor );
BOOL CreatePen (int nPenStyle,int nWidth,
COLORREF crColor);
– 颜色
• 三种指定颜色的方式
– 通过查色表索引值
– 通过颜色名称
– 通过红、绿、兰三分量
COLORREF
COLORREF
COLORREF
COLORREF
GetBkColor( ) const;
SetBkColor( COLORREF crColor );
GetTextColor( ) const;
SetTextColor( COLORREF crColor );
62
用图形软件包绘图(5/6)
• 填充图元及其属性
(封闭图元的两种绘制方式:只画出边框, 填充内部)
– 椭圆
BOOL Ellipse( int x1, int y1, int x2, int y2 );
BOOL Pie( int x1, int y1, int x2, int y2, int x3, int
y3, int x4, int y4 );
– 多边形
BOOL Polygon( LPPOINT lpPoints, int nCount );
– 矩形
BOOL Rectangle( int x1, int y1, int x2, int y2 );
– 填充模式
• 均匀填色
BOOL CreateSolidBrush( COLORREF crColor );
• 以图像填充
BOOL CreatePatternBrush( CBitmap* pBitmap );
63
用图形软件包绘图(6/6)
• 保存和恢复图元的属性: 提高程序的模块化程度
void InquireAttributes(AttributeGroup *group)
void SetAttributes(AttributeGroup *group)
在整个模块开始保存各种属性值,而在退出该模块时恢复原有属性值.
• 字符
(有大量属性:如字体,字形,字型,字间距,行间距等)
BOOL TextOut( int x, int y, LPCTSTR lpszString, int
nCount );
点阵字符的含义
64
基本的交互处理(1/3)
• 设计交互程序的几条原则
–
–
–
–
–
简单一致的交互操作序列
在交互的每一阶段,清晰地显示可选项
不能有过多的选项和繁杂的式样
给用户适当的反馈
Undo功能,允许用户取消操作
解决方法:菜单、按钮、加亮、变灰、光标变化等等
• 逻辑输入设备
–
–
–
–
目标:屏蔽物理设备的差异,获得系统的设备无关性
二维定位设备
键盘设备
设备驱动程序完成从物理设备到逻辑设备的映射
65
基本的交互处理(2/3)
• 输入方式
取样(轮询)方式
不管输入设备有没有
变化,都按固定频率
去查询它的值.
中断驱动方式
设备发出中断请求
事件驱动方式
输入事件存放在事件队
列中,系统按先后顺序处
理事件队列中的事件.
66
基本的交互处理(3/3)
• 事件驱动方式
– 简单的程序结构
初始化输入设备;
Do{
waitEvent(event);
Switch(event)
{
Case EVENT1: precedure1;
break;
Case EVENT2: procedure2;
break;
…
}
} while(TRUE);
67
光栅操作
光栅操作是光栅系统的特有操作,
这些光栅操作被大量应用于各种窗口
系统及相关的图形应用程序中 .
在基于窗口的系统中,选定菜单命
令”Edit”,然后按ESC键,菜单出现
后又消失,此过程中系统做了什么
呢?
(1) 把菜单将要覆盖的屏幕区域保存在像
素图中;
(2) 把系统保存的菜单拷贝到屏幕商;
(3) 恢复屏幕区域,把保存的像素图重新
拷贝到屏幕上
68
光栅操作
• 画布(Canvas)
–
–
–
–
–
抽象的数据类型,用户可以在其中画图;
包括一个用于绘图的像素图和一些控制信息(如像素大小,当前线型);
具有独立的坐标系,应用程序可以在其中绘图;
系统可以同时有多个画布,只有一个处于激活状态;
屏幕是一个特殊的画布,是唯一被显示的画布. 为使内存中的画布可
见,需将其拷贝到屏幕上;
– 绘图命令的作用对象是处于激活状态的画布;
– Windows中对应的概念:DC
69
光栅操作
• 裁剪窗口
– 为什么裁剪?(有时希望将整个画布划分成若干个区域,相互不影响)
– 内裁剪:保留窗口之内的图形
– 外裁剪:保留窗口之外的图形
UINT SetBoundsRect( LPCRECT lpRectBounds, UINT flags );
UINT GetBoundsRect( LPRECT lpRectBounds, UINT flags );
70
光栅操作
• 位块拷贝
将源画布中的矩形区域内的像素块拷贝到目标区域中,目标
区域位于当前激活的画布内.
– BitBlt (Bit Block Transfer)
BOOL BitBlt( int x, int y, int nWidth, int nHeight,
CDC* pSrcDC, int xSrc, int ySrc, DWORD dwRop );
dwRop参数指定光栅操作代码。这些代码将定义源矩形区域的颜色
数据,如何与目标矩形区域的颜色数据组合以完成最后的颜色。
(x,y)
(xSrs,ySrc)
71
光栅操作
位块拷贝和裁剪
72
光栅操作
• 显示模式
在光栅系统中,往屏幕上显示图形的过程就是向帧缓存里写数据的
过程,该过程由位拷贝函数完成.
- 位拷贝可以在内存与内存之间,内存与帧缓存之间移动位块,
- 拷贝的同时对源区域和目标区域的相应元素(像素)间进行指定
的逻辑运算.
– 4中简单的显示模式
• 覆盖/Replace
• 或/Or
• 异或/Xor
• 与/And
73
光栅操作
– Windows中的显示模式
int GetROP2( ) const; 获取绘图模式
int SetROP2( int nDrawMode ); 设置绘图模式
• R2_BLACK
只用黑色绘图
• R2_WHITE
• R2_NOP
用无色绘图
• R2_NOT
与背景颜色相反的颜色
• R2_COPYPEN 用画笔颜色绘图
• R2_NOTCOPYPEN 用与画笔颜色相反的颜色绘图
• R2_MERGEPENNOT
• R2_MASKPENNOT
• R2_MERGENOTPEN
• R2_MASKNOTPEN
• R2_MERGEPEN
• R2_NOTMERGEPEN
• R2_MASKPEN
• R2_NOTMASKPEN
• R2_XORPEN 用把画笔色与背景色进行异或运算后的颜色绘图
74
• R2_NOTXORPEN
光栅操作
– 多值图像的光栅运算
一个像素需要多个二进制位,相应单元间的按位逻辑运算.
11001001
Xor 11111111
------------------00110110
Xor 11111111
------------------11001001
–
–
–
–
覆盖模式: 用源图像块覆盖屏幕(或其他画布)上的一块区域.
或模式: 保留屏幕上已存在图像的同时再叠加源图像
与模式: 用于擦除屏幕上某块区域内的图像(清零)
异或的用途:光标的显示
75
第三章 二维线画图元的生成
•
•
•
•
•
简单的二维图形显示流程图
扫描转换直线段
扫描转换圆弧
生成圆弧的正负法
线画图元的属性控制
76
简单的二维图形显示流程图(1/2)
• 扫描转换
顶点(参数)
表示的图形
用户
扫描转换
点阵表示
的图形
光栅显示系统
• 简单流程图
77
简单的二维图形显示流程图(2/2)
– 裁剪的顺序
• 先裁剪
• 先扫描转换
78
扫描转换直线段(1/7)
• 扫描转换直线段
– 求与直线段充分接近的像素集
• 两点假设
– 直线段的宽度为1
– 直线段的斜率: m [1,1]
79
扫描转换直线段(2/7)
• DDA算法
– 条件:
P0 ( x0, y0) P1 ( x1, y1)
• 待扫描转换的直线段:
m  y / x
• 斜率:
x  x1  x0, y  y1  y0
• 直线方程: y  m  x  B
– 直接求交算法:x0 , x1 ,, xn , 其中xi 1  xi  1
yi  m  xi  B
• 划分区间[x0,x1]:
{( xi , yi )}in0
• 计算纵坐标:
• 取整:
{( xi , yi ,r )}in0
yi,r  round( yi )  (int)(yi  0.5)
80
扫描转换直线段(3/7)
• 复杂度:乘法+加法+取整
yi 1  m  xi 1  B  m  ( xi  1)  B
– DDA算法(增量算法)
 m  xi  B  m  yi  m
• 复杂度:加法+取整
81
• 例:画直线段P0(0,0)--P1(5,2)
k=2/5=0.4
int(y+0.5)
0
x
0
y
0
1
0.4
0
3
2
0.8
1
2
3
1.2
1
4
1.6
2.0
2
5
2
Line: P0(0, 0)-- P1(5, 2)
1
0
1
2
3
4
5
82
直线DDA算法核心代码
for (x=xa;x<=xb;x++)
{
pDC->SetPixel (x,int(y+0.5),c);
y=y+k;
}
83
直线DDA算法的VC代码
void CMyView:: OnDdaline()
{
CDC* pDC=GetDC(); //获得设备指针
int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);
//定义直线的两端点,直线颜色
int x,y;
float dx, dy, k;
dx=(float)(xb-xa), dy=(float)(yb-ya);
k=dy/dx, y=ya;
84
直线DDA算法VC代码
if (abs(k)<1)
{
for (x=xa; x<=xb; x++)
{ pDC->SetPixel (x,int(y+0.5),c);
y=y+k; }
}
if(abs(k)>=1) //当k1的情形
{
for (y=ya; y<=yb; y++)
{ pDC->SetPixel (int(x+0.5),y,c);
x=x+1/k; }
}
ReleaseDC(pDC);
}
85
扫描转换直线段(4/7)
• 中点算法
– 目标:消除DDA算法中的浮点运算
– 条件:
• 同DDA算法
m  [0,1]
• 斜率:
– 直线段的隐式方程
y
y  m x  B  y 
xB
x
 x  y  y  x  x  B
 F ( x, y )  x  y  y  x  x  B  0
86
扫描转换直线段(5/7)
– 直线的正负划分性
– 中点算法:
( xi , yi,r )  ( xi 1, yi 1,r )
87
扫描转换直线段(6/7)
1
1
( xi , yi ,r )  yi  ( yi ,r  , yi ,r  ]
2
2
1
1
[ 0 ,1]
m
 yi 1  ( yi ,r  , yi ,r  1  ]
2
2
1
1

y
(
E
)
,当
y

(
y

,
y

]
i 1
i ,r
i ,r
 i ,r
2
2
 yi 1,r  
1
3
 yi ,r  1( NE ),当yi 1  ( yi ,r  , yi ,r  ]
2
2

 yi ,r,当( xi 1 , yi 1 )在M的下方
 yi 1,r  
 yi ,r  1,当( xi 1 , yi 1 )在M的上方
 yi 1,r
 yi ,r,当F ( M )  0

 yi ,r  1,当F ( M )  0
88
扫描转换直线段(7/7)
– 判别式
1
• 取判别式 d i  2 F ( M )  2 F ( xi  1, yi ,r  2 )
• 递推计算 
di  2y,当di  0
di 1    
di  2(y  x),当di  0
– 初值条件
( x0 , y0,r )  ( x0, y 0)
d 0  2 F ( x0  1, y0,r
1
 )  2y  x
2
– 程序:
89
中点画线法
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=a+a+b; //即d0
d1=a+a, d2=a+a+b+b; // d1为右上方点判断式增量 d2为右方点判断
式增量,
x=x0, y=y0;
setpixel(x, y, color);
while (x<x1)
{
if (d<0)
{x++, y++, d+=d2; }
else
{x++, d+=d1;}
setpixel (x, y, color);
90
Bresenham画线算法
在直线生成的算法中Bresenham算法是最有效
的算法之一。
使用最广泛,最初的数字绘图仪设计。
About Bresenham
E.Jack Bresenham
Professor of Computer Science
Ph.D., Stanford University, 1964
MSIE, Stanford University, 1960
BSEE, University of New Mexico, 1959
Retired from 27 years service at IBM as a Senior Technical
Staff Member in 1987. Have taught 10 years at Winthrop.
Holder of five patents.
91
Bresenham画线算法
采用增量计算,对于每一列,只要检查一个误差项的符号。
原理: 直线与垂直网格线求交点,交点最近的象素。
d0=0,
d=d+k (k为直线斜率)
(假设k<1,当d≥1时,减1) 保证d在0、1之间。
d>0.5, (X0,Y0)→ (X0+1,Y0+1)
d<0.5, (X0,Y0)→ (X0+1,Y0)
d
d
d
d
92
为方便计算,令e=d-0.5, e的初值为-0.5,
增量为k。 e=e+k
当e≥0时,取当前象素(xi,yi)的右上方象素(xi+1,
yi+1);
而当e<0时,更接近于右方象素(xi+1,yi)。
一旦e≥0, 就把它减去1,这样保证e在 [
] 之间?
-1、0
93
例:Line: P0(0, 0), P1(5,2)
k=dy/dx=0.4
x y
e
0 0 -0.5 +0.4
1 0 -0.1 +0.4=0.3-1
3
2 1 -0.7
2
3 1 -0.3
1
4 2 -0.9
0
1
5 2 -0.5
2
3
4
5
94
Bresenham画线算法
void Bresenhamline (int x0,int y0,int x1, int y1,int
color)
{ int x, y, dx, dy;
float k, e;
dx = x1-x0, dy = y1- y0, k=dy/dx;
e=-0.5, x=x0, y=y0;
for (i=0; i<=dx; i++)
{
drawpixel (x, y, color);
x=x+1,e=e+k;
if (e0)
{ y++, e=e-1;}
95
}
Bresenham画线算法
可以改用整数以避免除法。由于算法中只用
到误差项的符号,因此可作如下替换:
e'  2 * e * dx
e0’=-0.5*2*dx= -dx
ei+1’ = ei’ +2*dy+2*dx ei’>=0
ei+1’ = ei’ +2*dy
ei’<0
96
Bresenham画线算法
Int- Bresenhamline (int x0,int y0,int x1, int y1,int color)
{ int x, y, dx, dy , e;
dx = x1-x0; dy = y1- y0;
e=- dx , x=x0, y=y0;
for (i=0; idx; i++)
{ drawpixel (x, y, color);
x=x+1,e=e+2*dy;
if (e0)
{ y++, e=e-2*dx;}
}
}
97
Bresenham算法的优点是:
1、不必计算直线之斜率,因此不做除法;
2、不用浮点数,只用整数;
3、只做整数加减法和乘2运算,而乘2运算可
以用硬件移位实现。
Bresenham 算法速度很快,并适于用硬件实现。
98
Bresenham 画线例
直线端点为(20,10)和(30,18), 用 Bresenham 法画线
解: x = 10, y = 8, k = y / x = 0.8,
2 y =16, 2 y-2x =-4
e0 = - x =-10,
ei<0
ei+1=ei+2*y
则有e1= e0+2*8 =-10+16=6
ei>=0
ei+1 = ei +2*dy+2*dx = ei-4
99
Bresenham 画线例
直线端点为(20,10)和(30,18)
画初始点(20, 10), 并根据判别式确定沿线段路径的后
续像素位置如下表:
i
0
1
2
3
4
5
6
7
8
9
e’ i
6
2
-2
14
10
6
2
-2
14
10
(x i+1,yi+1)
(21,11)
(22,12)
(23,12)
(24,13)
(25,14)
(26,15)
(27,16)
(28,16)
(29,17)
(20,18)
19
18
17
16
15
14
13
12
11
10
20 21 22 23 24 25 26 27 28 29 30
100
生成直线算法的进一步改进
1987年有人提出二步法,即每循环一次不是绘制一
个象素,而是绘制二个象素,这样无疑可以把生成直
线的速度提高一倍。
同样,我们先考虑当直线的斜率m属于区间[0,1]时,
在x方向每增加两个单元,只可能出现以下的四种情况。
A
B
C
D
101
生成直线算法的进一步改进
我们利用前述方法来讨论这个问题。令
ε(xi+2)=yi+2-yir-0.5
假定
当yi+2-yir≤0.5时绘制图A。
当0.5 ≤ yi+2-yir≤1时绘制图B。
当1 ≤ yi+2-yir≤1.5时绘制图C。
当yi+2-yir≥1.5时绘制图D。
A
B
C
D
102
ε(xi+4)=yi+4 - yi+2,r - 0.5
=yi+2 + 2m - yi+2,r - 0.5
=
=
{
{
yi+2 - yir + 2m - 0.5,
yi+2 - yir + 2m - 0.5 - 1,
yi+2 - yir + 2m - 0.5 - 2,
ε(xi+2) + 2m,
ε(xi+2) + 2m - 1,
ε(xi+2) + 2m - 2,
当ε(xi+2) ≤ 0
当1≥ε(xi+2)>0
当ε(xi+2)>1
当ε(xi+2) ≤ 0
当1≥ε(xi+2)>0
当ε(xi+2)>1
可取
ε(x3)=y3 - y1 - 0.5 = 2m - 0.5
相应的程序略
103
扫描转换圆弧(1/8)
• 处理对象:圆心在原点的圆弧
• 圆的八对称性
• 生成圆弧的隐函数方法
利用隐函数方程x 2  y 2  R 2
( xi , yi  R 2  xi2 ) 取整

(xi,yi ,r )
104
扫描转换圆弧(2/8)
• 生成圆弧的参数方程方法
 x  R cos
利用参数方程
 y  R sin 
(round( R cos i ), round( R sin  i ))
• 圆弧的正负划分性
F ( x, y)  x 2  y 2  R2  0
105
扫描转换圆弧
– 生成P点上方的弧段的弧段
• X递增一个像素,y递增多少?
10
9
8
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9 10
106
扫描转换圆弧
– 生成P点下方的弧段
• Y递增一个像素,x递增多少?
10
9
8
7
6
5
4
3
2
1
0
1
2
3
4
5
6
7
8
9 10
107
扫描转换圆弧(3/8)
• 生成圆弧的中点算法
– 考虑对象:
x [0, R / 2 ]
•
的1/8圆弧段
m [1,0]
• 在此圆弧段内,圆弧上各点的变化率
108
生成圆弧的中点算法
与直线情形类似
F(x,y)=x2+y2-R2=0, 切线斜率m in [-1,0]
中点 M=(xp+1,yp-0.5),
当F(M)<0时,M在圆内,说明P1距离圆
弧更近,取P1,当F(M)>0时,P取P2
P=(xp,yp)
d  F ( M )  F ( x p  1, y p  0.5)
 ( x p  1) 2  ( y p  0.5) 2  R 2
P1
M
P2
109
若 d<0, 则取P2为下一象素,而且再下一象素的判
别式为
d '  F ( x p  2, y p  0.5)  ( x p  2)2  ( y p  0.5)2  R 2  d  2 x p  3
若d>=0, 则应取P1为下一象素,而且下一象素的判别式为
d '  F ( x p  2, y p 1.5)  ( x p  2)2  ( y p 1.5)2  R 2  d  2( x p  y p )  5
第 一个象素是(0,R),判别式d的初始值为
d0  F (0  1, R  0.5)  5 / 4  R
110
算法过程
点
MidPointCircle(int r int color)
{ int x,y;
float d;
x=0; y=r; d=1.25-r;
circlepoints (x,y,color); //显示圆弧上的八个对称
while(x<=y)
{if(d<0)
d+=2*x+3;
else
{ d+=2*(x-y)+5; y--; }
x++;
circlepoints (x,y,color);
111
为了进一步提高算法的效率,可以将上面的算
法中的浮点数改写成整数,将乘法运算改成加法
运算,即仅用整数实现中点画圆法。
使用e =d - 0.25代替d
e0=1-R
112
生成圆弧的中点算法
若 e<0, 则取右方为下一象素,而且再下一象素的判别式为
e'  F ( x p  2, y p  0.5)  ei  2 x p  3  ei  Ei
若e >=0, 则应取右下方为下一象素,而且下一象素的判别式为
e'  F ( x p  2, y p  1.5)  ei  2( x p  y p )  5  ei  SEi
E的递推公式:
Ei+1=2(xi+1 )+3 = Ei+2
第 一个象素是(0,R),
E的初始值为: 3
SE的递推公式:
SE=
SEi+1的初始值为:
=2[(xi+1)-(y5-2*R
i -1)]+5 = SEi+4
113
椭圆的扫描转换
椭圆方程 x2/a2 + y2/b2 = 1
隐函数形式:F(x,y)= b2x2+a2y2-a2b2=0
椭圆的4对称性,只考虑第一象限椭圆弧生成,
分上下两部分,以弧上斜率为-1
的点(法向两个分量相等的点)作
为分界点。
椭圆上一点处的法向:

F ( x, y ) F ( x, y )
  (2b 2 x,2a 2 y)
,
x
y
114
F(x,y)= b2x2+a2y2-a2b2=0
弧上一点(x,y) 处的法向量

F ( x, y ) F ( x, y )
,
x
y
  (2b 2 x,2a 2 y)
从而弧上斜率为-1的点满足:
2b2x = 2a2y
可求得斜率为-1的点坐标:
(
a2
a 2  b2
,
b2
a 2  b2
)
115
椭圆的中点画法
与圆弧中点算法类似:确定一个象素后,接着在
两个候选象素的中点计算一个判别式的值,由判别
式的符号确定更近的点
考虑P点上方的椭圆弧段:斜率满足-1≤m≤0,下一
像素可能是中点的上方或下方
(Xp,Yp) 中点(Xp+1,Xp-0.5)
d1=F(Xp+1,Yp-0.5)= b2(Xp+1)2+a2(Yp-0.5)2-a2b2
116
若d1<0,中心在椭圆内,取正右方象素,判别式更
新为
d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)
d1的增量为
b2(2Xp+3)
当d1≥0,中点在椭圆外,取右下方象素,更新判别式:
d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)
沿右下方,判别式d1的增量为
d1 ≥ 0
d1<0
b2(2Xp+3)+a2(-2Yp+2)
117
椭圆的扫描转换
F(x,y)= b2x2+a2y2-a2b2=0
椭圆弧起点为(0,b),d1判别式的初始条
件:
转入P点下方的椭圆弧,斜率-1≤
1/m≤0, y递减一个像素,
d10=F(1, b-0.5)=b2+a2(-b+0.25)
x至多递增一个像素. 下一象素可能是一正下方或右下
方,x和y角色互换,此时判别式要初始化。
下部分也可以:从 x轴的
x=a, y=0
点逆时钟方向开始计算
118
生成圆弧的多边形逼近法
原理: lim(n边正内接多边形)  圆
n 
当圆的内接多边形边数足够多时,该多边形可
以和圆接近到任意程度,因此在允许的范围内,
可以用显示多边形代替显示圆。显示多边形的边
(直线)可用中点或Bresenham算法来实现。
用正多边形近似代替圆:
正内接多边形,等面积和正多边形
119
生成圆弧的多边形逼近法
设要绘的圆的圆心为c(xc,yc),半径为R。设内
接多边形的一个顶点为Pi(xi,yi),cPi的幅角为θi,
Pi+1
则:
Pi
xi = xc + Rcosθi
α
cos(θi+α)=cosθi cosα-sinθi sinα
yi = sinθ
yc + sinα+cosθ
Rsinθi cosα
sin(θi+α)=
i
i
设多边形每条边所对的圆心角为α,
则下一个顶点Pi+1的坐标为
c
θi
用正多边形迫近圆弧法
xi+1 = xc + Rcos(θi+α)
= xc + (xi - xc)cosα- (yi - yc)sinα
yi+1 = yc + Rsin(θi+ α)
= xc + (xi - xc)sinα- (yi - yc)cosα
120
生成圆弧的多边形逼近法
若c为原点,则用矩阵表示为
Pi+1
 xi 1  cos
 y    sin 
 i 1  
 sin    xi 
cos   y i 
一个顶点只需4次乘法,共4n次乘法,
外加直线段的中点算法的计算量。
α
c
Pi
θi
用正多边形迫近圆弧法
121
生成圆弧的多边形逼近法
误差分析
用递推公式要注意误差积累问题
(P58-59)
多边形直线点,带误差, 误差
A的特征值λ
||  || C ||  1,λ
|| 2
i 1
0
对初始误差稳定。
用矢量运算可以简化计算,
推出求顶点的逆推公式(p60)
122
生成圆弧的多边形逼近法
• 误差分析
用递推公式要注意误差积累问题(P58-59)
 iT
多边形直线点,带误差, 误差
cos  sin  
A
cos  sin   T
T

 i 1  

sin

cos

 i


sin

cos



A的特征值|λ1|=| λ2 |=1
||  i 1 || C ||  0 ||
对初始误差稳定。
123
扫描转换圆弧
生成圆弧的多边形逼近法
问题: 给定最大逼近误差delta, 确定多边形的
边数n .
2
n

R-Rcos(α/2)<=delta

cos (α/2)>=(R-delta)/R
α <=2arccos (R-delta)/R
边数 n=360/ α
124
圆的等面积多边形逼近法
| OP0 |
(1) 首先利用等面积,求多边形径长
 xi 1  cos
 y    sin 
 i 1  
从而求所有顶点坐标值
 sin    xi 
cos   y i 
(2) 由逼近误差值,确定边所对应的圆心角
α。
125
圆的等面积多边形逼近法
Pi+1
C
P1
B
E
D
O

1
R 
Pi Pi 1 . O B 
2
2
1
 
 1
2 o Pi sin 
o Pi cos  
o Pi

2
2 
2 2
从而得到
2

则有:
OPi
2
2
sin 
扇形面积等于三角形面积
R



 OPi 
R
sin 
sin 
2
126
生成圆弧的正负法(1/4)
• 正负法简介
由隐函数形式F(X,Y)=0,作判断点与曲线之间
关系.
– 基本原理
127
生成圆弧的正负法
好处:只需判断F(Pi)的符号,不会有累计误
差,计算方便,但需要满足一定条件:
如: Y=sin(1/x),
会在x点附近,震荡。
易画曲线:
(1)F(X,Y)具有正负划分性,
(2)F(X,Y)二阶连续
(3)曲线上各点的曲率半径大于步长△,
即在△的度量下,曲线较平坦。
128
生成圆弧的正负法(2/4)
– 初始定向 (从起始点P0(x0,y0)出发,向哪个方向前进)
• 确定x, y 的符号 (根据曲线所处的局部坐标系
象限确定)
对于单调曲线,符号一经确定,就不再改变
129
生成圆弧的正负法(3/4)
– 前进规则
起始点P0 ( x0 , y0 )
第1步前进x, P1 ( x0  x, y0 )
第2步前进y, P2 ( x0  x, y0  y )
(1)当Pi与P1在同侧时,前进y
(2)当Pi与P1在异侧时,前进x
D( Pi )  F ( Pi )  F ( P1 )  F ( xi , yi )  F ( x0  x, y0 )
• 取判别式
(1)当D( Pi )  0时,前进y
(2)当D( Pi )  0时,前进x
130
生成圆弧的正负法(4/4)
• 正负法生成圆弧
– 考虑第一像限圆弧段
– 圆弧是易画曲线
P ( x– ,程序:
y )  (0, R )
见63页
0
0
0
初始定向D  4,
x  1,y  1
P1坐标为( x0  1, y0 )  (1, R )
131
正负法生成圆弧:
Bresenham法生成圆弧:
132
线画图元的属性控制
线宽、线型、颜
色
线宽控制
刷子:刷子形状(圆,方)朝向,对线型的
影响
133
线画图元的属性控制(1/5)
• 线宽控制
– 像素复制方法 (在扫描转换的同时显示k个像素)
• 优点:
– 实现简单
• 缺点:
– 线段两端要么为水平的,要么是竖直的
– 折线顶点处有缺口
134
线画图元的属性控制(2/5)
– 图元的宽度不均匀
– 产生宽度为偶数像素的图元效果不好
135
2.移动刷子产生宽图元
1
线宽与线段的斜率有关
切线斜率向
宽度变大
用方刷比用像素复制得到的线条粗
变化时,
136
3.用填充图形表示宽图元
用等距线方法:
线宽均匀
端口处与边垂直
生成的图形质量高
缺点:
- 计算量大
- 有些图形的等距线
难以获得
137
线型控制
• 用位屏蔽器实现
111100111100111100
• 缺陷: 位屏蔽器中每一位对应的是一个像素,
而不是单位长度,会使笔画的长度与图元的斜率
有关.对于工程图来说不能满足要求
• 工程图,笔画作单独的扫描转换
138
本章要点
• 直线段与圆弧的扫描转换中点算法
• DDA算法, Bresenham算法
• 圆弧的各种算法
139
习题
1. 将中点画线方法推广,使之能画出任意斜率的直线
2. 用中点画线法或 Bresenham 算法,指出从(0,0)到
(6,18)间的直线段的象素位置。
3.
编写按逆时针方向生成中心在原点的第一个8分圆
的中点画圆算法,导出递推公式
4. 利用抛物线f(x,y)=x-y2=0的正负划分性和对称性,设
140
第四章 填充图元的生成
•
•
•
•
•
•
扫描转换矩形
扫描转换多边形
扫描转换扇形区域
区域填充
以图像填充区域
字符的表示与输出
141
一般步骤
1. 确定哪些像素位于填充图元的内部
2. 确定以什么颜色填充这些像素
142
扫描转换矩形(1/2)
• 方法:
void FillRectangle(Rectangle *rect,int color)
{ int x,y;
for(y = rect->ymin; y <= rect->ymax; y++)
for(x = rect->xmin;x <= rect->xmax;x++)
PutPixel(x,y,color);
}/*end of FillRectangle() */
143
扫描转换矩形(2/ 2)
• 问题:
– 矩形是简单的多边形,那么为什么要单独处
理矩形?
– 共享边界如何处理?
• 原则:左闭右开,下闭上开
属于谁?
144
扫描转换多边形(1/ 19)
• 多边形的表示方法
– 顶点表示
几何意义强,占空间少,易于几何变换
– 点阵表示
无几何信息,光栅系统显示时采用
– 扫描转换多边形:将顶点表示形式转换成点
阵表示形式
145
扫描转换多边形(2/ 19)
• 逐点判断算法
– 方法
void FillPolygonPbyP(Polygon *P, int polygonColor)
{ int x,y;
for(y = ymin;y <= ymax;y++)
for(x = xmin;x <= xmax;x++)
if(IsInside(P,x,y))
PutPixel(x,y,polygonColor);
else
PutPixel(x,y,backgroundColor);
}/*end of FillPolygonPbyP() */
146
扫描转换多边形(3/ 19)
–
–
问题:如何判别点(x,y)关于多边形区域P
的内外关系?
射线法
•
步骤:
1. 从待判别点v发出射线
2. 求交点个数k
3. K的奇偶性决定了点与多边形的内外关系
•
奇异情况处理
通过多边形顶点的情况,
如果本该是一个交点的
被算做了两个交点,或
反过来,就会使判断结果
错误.
(一般可使射线不交
于多边形的顶点,
如通过某边的中点)
147
扫描转换多边形(4/ 19)
–
累计角度法
•
步骤
•
 0,v位于P之外
i  

i 0
 2 , v位于P之内
奇异情况处理 | i | 
1. 从v点向多边形P顶点发出射线,形成有向角 i
2. 计算有相交的和,得出结论
n
即边在pipi+1上,预处理阶段进行处理
离散计算方法:编码方法
148
扫描转换多边形(4/ 19)
–
编码方法
• 步骤
1. 预处理:测试v是否在多边形P的边上;
2. 以v为原点建立局部坐标系vxy,对其各象限
按逆时针顺序编码,分别记为0,1,2,3,
3. 对多边形各顶点编码,Pi落在哪个象限,其
编码即为该象限的编码,记为IPi;
4. 对多边形的各边编码,边PiPi+1的编码记为 Pi Pi 1
n
5. 计算
Pi Pi 1  I pi1  I pi
 P P
i 0
i i 1
,若=0,则位于P之外,若
=±4,则v位于P之内.
注意:
1. 保证 Pi Pi 1 的绝对
值不大于2;
2.当 Pi Pi 1 的绝对值等
于2的情况
149
扫描转换多边形(5/ 19)
– 逐点判断算法优点:简单
– 算法缺点:计算量太大,速度慢
• 扫描线算法
– 目标:充分利用像素之间的连贯性,提高算
法效率,避免逐点判断和反复求交
– 处理对象:非自交多边形( 边与边除顶点外无其他交点)
150
扫描转换多边形(6/ 19)
–
基本原理
演示:MorphInk
一条扫描线与多边形的边有偶数个交点
扫描线的连贯性
–
步骤:
1. 求交
2. 排序
3. 填充
151
扫描转换多边形(7/ 19)
– 边的连贯性
为减少求交的计算量,要利用一条边与相继的两条扫描线的交点
间的连贯性.
• 第一类交点:位于同一条边上的后继交点
若x为该边与y=e的交点的横坐标,边的斜率为m,则此边与y=d的交
点的横坐标为x’=x+1/m.
• 第二类交点:新出现的边与扫描线的交点
152
扫描转换多边形(8/ 19)
– 交点的取整规则
• 要求:使生成的像素全部位于多边形之内
– 用于线画图元扫描转换的四舍五入原则导致部分像素
位于多边形之外,从而不可用
• 假定非水平边与扫描线y=e
相交,交点的横坐标为x,
规则如下
153
扫描转换多边形(9/ 19)
1. X为小数
•
•
(a)交点位于左边之上,向右取整
(b)交点位于右边之上,向左取整
154
扫描转换多边形(10/ 19))
2. (x,e)交点落在像素之上
– (a) (x,e)位于左边之上,属于多边形
– (b) (x,e)位于右边之上,不属于多边形
155
扫描转换多边形(11/ 19)
3. 交点为多边形的顶点
–
–
–
–
每条边视为下端闭,上端开
(a) 算作1个交点
(b) 算作1个交点
(c) 算作2个交点
(d) 算作0个交点
156
扫描转换多边形(12/ 19)
– 特殊情况处理
• 水平边:扔掉!
• 尖角:反混淆
157
扫描转换多边形(13/ 19)
– 数据结构
•边
typedef struct {int ymax;
float x, deltax;
Edge *nextEdge;
}Edge;
• 边的分类表E( Edge *edges[ ])
按照边的下端点y坐标对非水平边进行分类的指针数组
• 活化边表AEL(Edge *active)
纪录与当前扫描线相交的边(交点)
158
扫描转换多边形(14/ 19)
159
扫描转换多边形(15/ 19)
– 算法
1、建立ET;
2、将扫描线纵坐标y的初值置为ET中非空元素的最小序号,如在上图中,
y=1;
3、置AEL为空;
4、执行下列步骤直至ET和AEL都为空.
4.1、如ET中的第y类非空,则将其中的所有边取出并插入AEL中;
4.2、如果有新边插入AEL,则对AEL中各边排序;
4.3、对AEL中的边两两配对,(1和2为一对,3和4为一对,…),将每
对边中x坐标按规则取整,获得有效的填充区段,再填充.
4.4、将当前扫描线纵坐标y值递值1;
4.5、将AEL中满足y=ymax边删去(因为每条边被看作下闭上开的);
4.6、对AEL中剩下的每一条边的x递增deltax,即x = x+deltax.
160
扫描转换多边形(16/ 19)
• 边缘填充算法
(扫描线算法需要对AEL中的各边排序,排序工
作可以利用求余运算代替)
– 原理:以求余运算代替扫描线算法中的排序
运算
– 求余(A=0xFFFFFFFF)
M  A M  M
Xor
A
– 算法1:(以扫描线为中心的边缘填充算法)
1、将当前扫描线上的所有象素着上值为 M 的颜色;
2、求余:
for(i = 0;i <= m; i++)
在当前扫描线上,从x坐标为交点向右求余;
161
扫描转换多边形(17/ 19)
162
扫描转换多边形(18/ 19)
1、将绘图窗口的背景色置为 M ;
– 算法2:(以边为中心的
2、对多边形的每一条非水平边做:
边缘填充算法)
从该边上的每个象素开始向右求余;
163
扫描转换多边形(19/ 19)
164
扫描转换扇形区域(1/5)
• 扇形区域的描述
• 原理:同扫描转换多边形
• 问题:如何确定扫描线与直线段和圆弧
段的相交顺序
• 方法:分类
按点p1 和 p2点所处象限的不同,需要将扇形区域分成
4×4=16种情况
165
扫描转换扇形区域(2/5)
• 假设 p1 点落在第一象限 ,扇形区域的扫描
转换 分四种情况
1、p2 落在第一象限
166
扫描转换扇形区域(3/5)
2、p2 落在第二象限,此时又分为两种情况
•当
y1  y2 时
•当
y1  y2 时
167
扫描转换扇形区域(4/5)
3、p2 落在第三象限
4、p2 落在第四象限
168
扫描转换扇形区域(5/5)
• 遗留问题:当 p1 落在其它区域时?
• 其它方法:
多边形迫近方法
169
区域填充(1/10)
• 区域:点阵表示的图形,像素集合
• 表示方法:内点表示、边界表示
• 内点表示
– 枚举出区域内部的所有像素
– 内部的所有像素着同一个颜色
– 边界像素像素着与内部像素不同的颜色
• 边界表示
– 枚举出边界上所有的像素
– 边界上的所有像素着同一颜色
– 内部像素着与边界像素不同的颜色
170
区域填充(2/10)
区域的内点表示与边界表示
• 区域填充
– 将指定的颜色从种子点扩展到整个区域的过程,对区
域重新着色.
171
区域填充(3/10)
• 要求区域是连通的
连通性:4连通、8连通
• 4连通:
• 8连通
172
区域填充(4/10)
• 4连通与8连通区域的区别
– 连通性 4连通区域也是8连通区域
– 对边界的要求 4连通区域的边界只需8连通,而8连
通区域的边界必须是4连通的
173
区域填充(5/10)
• 递归填充算法
– 内点表示的4连通区域
void FloodFill4(int x, int y, int oldColor, int newColor)
{ if(GetPixel(x,y) == oldColor)
{ PutPixel(x,y,newColor);
FloodFill4(x,y+1,oldColor,newColor);
FloodFill4(x,y-1,oldColor,newColor);
FloodFill4(x-1,y,oldColor,newColor);
FloodFill4(x+1,y,oldColor,newColor);
}
}/*end of FloodFill4()
*/
174
区域填充(6/10)
175
• 种子填充算法(四向算法):允许从四个方向寻找下
一象素,利用栈结构实现。
• 算法:种子象素入栈,当栈非空时,重复执行:
(1)栈顶象素出栈;
(2)将出栈象素置成多边形色;
(3)四向检查象素,若其中某个象素不在边界对未置成
多边形色,该象素入栈。
• 可用于填充带内孔的平面区域。
176
• 缺点:
(1) 有些象素会入栈多次,降低算法效率;栈结构占
空间。
(2) 递归执行,算法简单,但效率不高,区域内每一
象素都引起一次递归,进/出栈,费时费内存。
改进算法,减少递归次数。
解决方法是用扫描线填充算法;
177
A. 简单的种子填充算法
例:下图情况堆栈内容看黑板
1. 初始化:种子像素入栈,当栈非空
时,重复2~4的步骤
4
2. 栈顶像素出栈
3
3. 将出栈像素置为多边形颜色
2
4. 按右、上、左、下顺序依次检查与
S1
1
出栈像素相邻的四个像素,若其中
某个像素不在边界上且未置成多边
0
0
1
2
3
4
5
形色,则该像素入栈
5. 当堆栈为空时,算法终止
178
区域填充(7/10)
– 边界表示的4连通区域
void BoundaryFill4(int x,int y,int oldColor,int newColor)
{
int color;
color = GetPixel(x,y);
if((color != boundaryColor) && (color != newColor))
{
PutPixel(x,y,newColor);
BoundaryFill4(x,y+1,oldColor,newColor);
BoundaryFill4(x,y-1,oldColor,newColor);
BoundaryFill4(x-1,y,oldColor,newColor);
BoundaryFill4(x+1,y,oldColor,newColor);
}
}/*end of BoundaryFill4()
*/
179
区域填充(9/10)
• 扫描线算法
– 目标:减少递归层次
– 算法思路
Step1:栈顶象素出栈,
Step2:沿扫描线对出栈象素的左右象素进行填充,直到遇
到边界象素为止,即填充区间。
Step3:检查上下扫描线,选相应区间的最右象素作种子象
素入栈。
特点:由区域算法定区间(区段),再定上、下相邻区间
180
区域填充(9/10)
• 步骤
1、填充并确定种子区段;
2、初始化:将种子区段压入堆栈;
3、出栈:如果堆栈为空,则算法结束;否则取栈顶元素
(y,xLeft,xRight),以纵坐标为y的扫描线为
当前扫描线,[xLeft,xRight]为搜索区间;
4、填充并确定新的区段.确定当前扫描线上、下相邻的两条
扫描线上与区段(y,xleft,xRight)连通的位于给定区域
内的区段。
181
区域填充(10/10)
182
B. 扫描线种子填充算法
为减少像素重复入栈,限定任一扫描线与多边形相交区间,
只取一个种子像素
例:
1. 初始化:种子像素入栈,当栈非空时,重
xL
xR
复2~6的步骤
11
2. 栈顶像素出栈
10
3. 沿扫描线对种子像素的左右像素进行填充, 9
8
直至边界,从而填满该区间
7
4. 区间内最左和最右像素分别记为 xL 和 xR
6
5. 在区间[xL, xR]中检查与当前扫描线相邻的
5
上下两条扫描线是否全为边界或已经填充, 4
3
若存在非边界、未填充的像素,将检查区
2
间的最右像素作种子入栈
1
0
6. 当堆栈为空时,算法终止
s
0 1 2 3 4 5
分析堆栈内容
6 7 8 9 10 11 12
183
多边形扫描转换与区域填充方法比较
都是光栅图形面着色,用于真实感图形显示。
可相互转换。
不同点:
1.基本思想不同;前者用于将顶点表示转换成点阵表示;
后者只改变区域内填充颜色,没有改变表示方法。
2.对边界的要求不同
前者:只要求扫描线与多边形边界交点个数为偶数。
后者:区域封闭,防止递归填充跨界。
3.基本的条件不同
前者:从边界顶点信息出发。
后者:区域内种子点。
184
以图像填充区域(1/3)
• 四种填充方法:
(1)均匀着色方法;(2)位图不透明;(3)位图透明;(4)像素图填充。
• 基本问题
– 建立绘图空间与纹理(图像)空间的1-1映射
• 方法1:建立整个绘图空间与图像空间的1-1映射
图像(纹理)
185
以图像填充区域(2/3)
假定图像是M*N大小,
若用于填充的图像较
小,将其周期性排列.
像素(x, y)的颜色值为
pattern[x%M][y%N]
186
方法1:建立整个
绘图空间与图像空
间的1-1映射
187
以图像填充区域(3/3)
• 方法2:建立区域局部坐标空间与图像空间的1-1映射
像素(x,y)的颜色值,先求得它在局部坐标系O’x’y’中的坐标(x’,y’),然后才能
确定对应的颜色值为pattern[x’%M][y’%N]
188
方法1:建立整个绘图
空间与图像空间的1-1
映射
方法2:建立区域局部
坐标空间与图像空间
的1-1映射
189
字符的表示与输出
•
•
•
•
字符集
点阵字体
矢量字体
矢量字体的变换,显示,存储
190
上机作业
1、实现已知顶点的多边形有序边扫描线转换算法。
2、实现已知区域的四连通种子填充算法和扫描线种子
填充算法。要求种子点(x,y)可交互输入
实验报告要求:
1. 描述各个作业使用的算法和数据结构,并说明理
由。如果有个人的创新工作,则应该详细说明。
2
简要说明实现的步骤,并总结实现的质量,如哪
些方面实现的较好、哪些方面尚需完善、哪些方面未
实现等(如有动态演示的闪烁问题等)。
191
C的代码如下
//用TURBO C实现
#include "stdio.h"
#include "graphics.h"
#include "process.h"
#define MAX 100
#define HEIGHT 480
typedef struct
{
int x;
int y;
} dcPt;
//点结构
192
多边形结构体
• typedef struct
• {
• int polygonnum;
•
// 多边形顶点个数,scanfill函数中的cnt参数
• dcPt verteces[MAX];
•
// 多边形顶点数组,scanfill函数中的*pts参数
•
//以下程序多次用到。
• }Polygon; //多边形结构
193
边结构(单链)
• typedef struct tEdge
• {
• int yUpper;
• float xIntersect, dxPerScan;
• struct tEdge *next;
• }Edge; //边结构(单链)
yUpper
xIntersect
dxPerScan △X
next
//程序中用到的边表edges数组和活性边
Edge *edges[HEIGHT], *active;
194
怎样构造边结构?
//用函数makeEdgeRec实现,
//该函数调用了插入边记录的insertEdge函数
//将构成的边指针edge插入边表edges[]
//参数lower, upper,表示一条边的高低两点,
• void makeEdgeRec( dcPt lower, dcPt upper, int yComp, Edge *edge,
Edge *edges[] )
195
• {
• edge->xIntersect=lower.x;
• edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);
• if(upper.y<yComp) //是否单调
•
edge->yUpper=upper.y-1; //算一个点
• else
•
edge->yUpper=upper.y;
• insertEdge(edges[lower.y],edge);
• }
p0
p1
p4
p2
p3
196
• 初始化边表edges数组代码
• for(i=0;i<HEIGHT;i++) //初始化NET表
• {
•
edges[i]=(Edge *)malloc(sizeof(Edge));
•
edges[i]->next=NULL;
• }
^
…..
^
^
^
^
^
197
利用多边形的非水平边建立边表数组edges
• buildEdgelist(int cnt, dcPt *pts, Edge *edges[])
• // buildEdgelist函数的功能是:建立新边表edges
• //该函数调用了构造边记录函数makeEdgeRec
198
buildEdgelist函数(1)
• void buildEdgelist(int cnt,dcPt *pts,Edge *edges[])
• {
• Edge *edge;
• dcPt v1,v2;
• int i, yPrev=pts[cnt-2].y;
• v1.x=pts[cnt-1].x;
• v1.y=pts[cnt-1].y;
• //第1条边由点pts[cnt-1]和pts[0]组成。
p0
p1
p4
第1条边由点p4和p0组成。
P3为Prev点,p2为next点
p2
p3
199
buildEdgelist函数(2)
• for(i=0;i<cnt;i++)
• {
•
v2.x=pts[i].x;
v2.y=pts[i].y;
•
if(v1.y!=v2.y)
•
{
dge=(Edge *)malloc(sizeof(Edge));
•
if(v1.y<v2.y)
•
makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);
•
else
•
makeEdgeRec(v2,v1,yPrev,edge,edges);
•
}
p0
•
yPrev=v1.y;
•
v1=v2;
p4
• }
• }
p1
p2
p3
200
• /* insertEdge函数的功能是:
• 将多边形的边 edge插入边表list(相当于edges表或NET表)
• 用edge的xIntersect与list->next->xIntersect逐一比较,进行插入*/
• void insertEdge(Edge *list, Edge *edge)
• {
•
Edge *p,*q=list;
•
p=q->next;
•
201
• while(p!=NULL)
•
{
•
if( edge->xIntersect < p->xIntersect )
•
p=NULL; //
•
else
•
{
•
q=p;
•
p=p->next;
•
}
•
}
•
edge->next=q->next;
•
q->next=edge;
• }
202
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
//函数yNext的功能是:跳过水平边找下一个点的Y值
int yNext (int k,int cnt,dcPt *pts)
{
int j;
if((k+1)>(cnt-1)) //若当前为最后一个点
j=0;
else
j=k+1;
while(pts[k].y==pts[j].y)//若当前点与下一点为水平边
if((j+1)>(cnt-1))
j=0;
else
j++;
return(pts[j].y);
}
203
//建立当前扫描线的活性边
• void buildActivelist(int scan,Edge *active,Edge *edges[])
• {
• Edge *p,*q;
• p=edges[scan]->next;
• while(p)
• {
•
q=(Edge *)malloc(sizeof(Edge));
•
q->yUpper=p->yUpper;
•
q->xIntersect=p->xIntersect;
•
q->dxPerScan=p->dxPerScan;
•
insertEdge(active,q);//将edges[scan]的边链表插入活性边表
•
p=p->next;
• }
• }
204
//对当前扫描线scan填充
• void fillscan(int scan,Edge *active)
• {
• Edge *p1,*p2;
• int i;
• p1=active->next;
• while(p1)
• {
•
p2=p1->next;
•
for(i=p1->xIntersect;i<p2->xIntersect;i++) putpixel(i,scan,15);
•
p1=p2->next; //跳过偶->奇区间
• }
• }
205
• void deleteAfter(Edge *q)
• {
• Edge *p=q->next;
• q->next=p->next;
• free(p);
• }
//删除*q的下一个边
206
//更新活性边表
• void updateActivelist(int scan,Edge *active)
• {
• Edge *q=active,*p=active->next;
• while(p)
•
if(scan>=p->yUpper) //删除高点为当前扫描线的边
•
{
•
p=p->next;
•
deleteAfter(q);
•
}
•
else
•
{
//更新交点值
•
p->xIntersect=p->xIntersect + p->dxPerScan;
•
q=p;
•
p=p->next;
•
}
• }
207
//活性边重排序
• void resortActivelist(Edge *active)
• {
• Edge *q,*p=active->next;
• active->next=NULL;
• while(p)
• {
•
q=p->next;
•
insertEdge(active,p);
•
p=q;
• }
• }
208
// 扫描线转换(1)
void scanFill(int cnt,dcPt *pts)
{
Edge *edges[HEIGHT],*active; /* ? */
Edge *p;
int i,scan;
for(i=0;i<HEIGHT;i++)//初始化NET表
{
edges[i]=(Edge *)malloc(sizeof(Edge));
edges[i]->next=NULL;
}
buildEdgelist(cnt,pts,edges); //将多边形各边插入NET表
209
//扫描线转换(2)
active=(Edge *)malloc(sizeof(Edge));//申请活性边表空间
active->next=NULL;// 活性边表初始化
for(scan=0;scan<HEIGHT;scan++) //对每一条扫描线
{
buildActivelist(scan,active,edges); //建立当前扫描线的活性边
if(active->next!=NULL)
{
fillscan(scan,active); // 填充
updateActivelist(scan,active);//更新
resortActivelist(active); //重排序
}
}
210
//扫描线转换(3)
// 以下释放活性边和边表的动态存储空间
p=active;
while(p!=NULL)
{
active=active->next;
free(p);
p=active;
}
211
//扫描线转换(4)
for(i=0;i<HEIGHT;i++)
{
p=edges[i];
while(p!=NULL)
{
edges[i]=p->next;
free(p);
p=edges[i];
}
}
}
212
主函数(1)
main()
{
int n,i,x,y,gdriver=DETECT,gmode;
dcPt *pts;
initgraph(&gdriver,&gmode,"");
printf("Input The Vertex's Number Of PolyGon:");
scanf(“%d”,&n); //输入多边形顶点个数
pts=(dcPt *)malloc(n*sizeof(dcPt));
for(i=0;i<n;i++) //输入多边形顶点坐标
{
printf("\n Input (X,Y) Of The %dth Vertex's: ",i);
scanf("%d%d",&x,&y);
pts[i].x=x;
pts[i].y=y;
}
213
主函数(2)
system("cls");
/*
for(i=0;i<n-1;i++)
line(pts[i].x,pts[i].y,pts[i+1].x,pts[i+1].y);
line(pts[n-1].x,pts[n-1].y,pts[0].x,pts[0].y);
*/
scanFill(n,pts);
printf("Press any key to return...\n");
getch();
closegraph();
}
214
第五章 二维光栅图形的混淆与反
混淆
• 混淆现象
• 反混淆方法
215
混淆(antialiasing)
在光栅显示器上显示图形时,直线段或图形边
界呈锯齿状:图形信号连续,光栅显示系统中,
离散表示。
用离散量(像素)表示连续的量(图形)而引起的失
真,叫混淆或叫走样(aliasing)
• 光栅图形混淆:
阶梯状边界;
图形细节失真;
216
混淆现象(1/3)
• 不光滑(阶梯状)的图形边界
例子:PaintBrush
217
混淆现象(2/3)
• 图形细节失真
218
混淆现象(3/3)
• 狭小图形的遗失与动态图形的闪烁
219
反混淆方法(1/10)
• 什么是反混淆
– 在图形显示过程中,用于减少或消除混淆现
象的方法
• 提高分辨率的反混淆方法
220
• 显示器提高分辩率,显示器距减少一倍,帧
缓存容量增加到原来的4倍,传输带宽提高四
倍,扫描转换花4倍时间。
另一种方法:
• 在较高分辨率的显示模式下计算,(对各自
像素计算,再求(非)加权平均的颜色值),
在较低的分辨率模式下显示。
只能减轻,不能消除。
221
反混淆方法(2/10)
• 非加权区域采样方法
– 两点假设
1、象素是数学上抽象的点,它的面积为0,它的
亮度由覆盖该点的图形的亮度所决定;
2、直线段是数学上抽象直线段,它的宽度为0。
– 现实
• 像素的面积不为0;
• 直线段的宽度至少为1个像素;
– 假设与现实的矛盾是导致混淆出现的原因之
一
222
反混淆方法(3/10)
– 解决方法:改变直线段模型
– 实现步骤:
1、将直线段看作具有一定宽度的狭长矩形;
2、当直线段与某象素有交时,求出两者相交区域的面积;
3、根据相交区域的面积,确定该象素的亮度值
223
反混淆方法(4/10)
非加权区域采样方法具有下面三条性质:
(1)像素宽度与相交区域面积成正比,和直线段与像素中心点
的距离成反比。
(2)直线与像素不相交,对象素的宽度没有影响。
(3)相交区域面积相同,像素的亮度相同,与相交区域的几何
位置无关。
计算相交区域的面积
224
反混淆方法(5/10)
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成m个更小的子象素;
2、计算中心点落在直线段内的子象素的个数,记为k,
3、k/m为线段与象素相交区域面积的近似值
225
反混淆方法(6/10)
• 加权区域采样方法
– 非加权区域采样方法的性质
1、直线段对一个象素亮度的贡献与两者相交区域的面积成
正比;
2、当直线段和一个象素不相交时,它对该象素的亮度没有
影响;
3、相同面积的相交区域对象素的亮度贡献相同,而与这个
相交区域落在象素内什么位置无关.
– 改进第3条性质
• 相交区域对象素亮度的贡献依赖于该区域与象素中心的距
离
226
反混淆方法(7/10)
– 权函数W(x,y)
• 以象素A的中心为原点建立二维坐标系
• w(x,y)反应了微面积元dA对整个象素亮度的贡献大小
• 权性
1
w( x, y ) 
d
• 权函数:W(X,Y), 高斯函数
W ( x, y) 
1
x2  y 2
exp(
)
2
2
2
 w( x, y)dA  1
A
227
反混淆方法(8/10)
– 相交区域 A  对该象素的亮度贡献 
A
特例:
w( x, y)dA
时,  w( x, y )dA  A的面积

A
加权区域采样方法退化为非加权区域采样方法
228
反混淆方法(9/10)
– 实现步骤
1.求直线段与象素的相交区域 A  ;
2.计算的值 A w( x, y)dA ;
3.上面所得到的值介于0、1之间,用它乘象素的
最大灰度值,即设该象素的显示灰度。
– 问题:计算量大
229
反混淆方法(10/10)
– 离散计算方法
1.将屏幕象素均匀分割成m个子象素  Ai  i 1,则每个子象素的面
积为 AdA  1 / m , 计算每个子象素对原象素亮度的贡献,记为 wi ,
m
将
wi  i 1 保存在一张加权表中;
2.求出所有中心落于直线段内的子象素,记为  Ai :i ,
wi
3.计算所有这些子象素对原象素亮度贡献之和 
该值乘以
i
象素的最大灰度值即为象素的显示灰度值.
m
i
– 加权表的取法
 w1
w
 4
w7
w2
w5
w8
w3 
 1 2 1
1 


w6   2 4 2
16
1 2 1
w9 
230
第六章 二维裁剪
• 直线段裁剪
• 多边形裁剪
• 字符裁剪
231
裁剪Clipping
裁剪的含义
裁剪是从数据集合中抽取信息的过程,是许多图形操
作的基础。
裁剪的目的
从大的画面中抽取所需的具体信息,判断图形元素是否
位于裁剪窗口之内。
裁剪的处理的基础
(1)图元关于窗口内外关系的判别
(2)图元与窗口的求交
232
线段裁剪
• 假定条件
P0 ( x0 , y0 ) P1 ( x1 , y1 )
– 矩形裁剪窗口:[xmin,xmax] X [ymin,ymax]
– 待裁剪线段:
待裁剪线段和窗口的关系:
(1)线段完全可见;
(2)线段完全不可见;
(3)线段至少有一个端点在裁
剪窗口之外,但非显然不可见
233
线段裁剪
• 点裁剪
– 点(x, y)在窗口内的充分必要条件是:
x min  x  x max
y min  y  y max
• 直接求交算法
234
线段裁剪
235
线段裁剪
Sutherland-Cohen算法
思路:
首先简化问题,排除无需操作的对象;
然后对需要处理的对象设法简化算法;
D
y
C
I
yT
A
K
F
yB
B
L
J
E
xL
xB
二维窗口
236
x
为了实现算法的第一部分,用窗口的四条边把整个平面
分成九个区域,每个区域中的点采用同一编码,这一编码
的特点是对于窗口的某一条边外侧的三个区域的四位编码
中有一位全为1。
y
1001
1000
1010
0001
0000
0010
0101
0100
0110
yT
yB
xL
xB
x
区域编码
237
Cohen-SutherLand算法(编码算法)
– 特点:对显然不可见线段的快速判别
– 编码方法:由窗口四条边所在直线把二维平面分成9个区
域,每个区域赋予一个四位编码,CtCbCrCl,上下右左;
1
Ct  
0
1
Cb  
0
1
Cr  
0
当y  y max
1
Cl  
0
当x  x min
else
当y  y min
else
当x  x max
else
else
238
Cohen-SutherLand算法(编码算法)
如果两个编码都是0,则线段完
全在区内,不用裁剪
1001
1000
1010
0000
0010
完全接受;否则
0001
如果两个编码的逻辑乘不为0000,
这时可断定两个编码的某一位都为
1,这条直线段的两个端点位于窗
口的一条边的外侧,因而是完全不
可见的,完全拒绝。
0101
0100
0110
239
通过区域编码进行判别:
1. 定义区域编码:
 Bit 0:左
 Bit 1:右
 Bit 2:下
 Bit 3:上
1001
1000
1010
2. 将线段两端点逐位求“与”,
若结果非零,该线段完全不可见
0001
0000
0010
3. 对求“与”结果为零线段,
如均为0,判别得完全可见线段
0101
0100
0110
4. 对剩下的其它线段,作线段与窗口边
求交处理确定可见部分
* 特殊线段的处理:斜率无穷大或为零,一个端点编码为零等
240
P1’’
例题:
P’’’1
P2
P1 ’
P1
P1:(-3/2, 1/6);编码 (0001)
P2:(1/2, 3/2);编码 (1000)
(1) 求左边交点,得P’1P2;
P’1:(-1,1/2); 编码(0000)
判别知非完全可见,且P’1在窗口内,
因此交换P’1P2得新线段P1P2;
P1:(1/2, 3/2);编码 (1000)
P2:(-1, 1/2); 编码 (0000)
(2) 求右边交点,得 P’’1(1, 11/6) P2(-1, 1/2);
并编码, 判别之不可见
x=x1+(y-y1)*(x2-x1)/(y2-y1)
y=y1+(x-x1)*(y2-y1)/(x2-x1)
(3) 求上边交点,得 P’’’1(-1/4, 1) P2(-1, 1/2);
并编码,
两端点编码全部为0,
线段完全可见,程序结束
241
Cohen-Sutherland 算法 (编码算法)
算法步骤:
第一步 判别线段两端点是否都落在窗口内,如果是,
则线段完全可见;否则进入第二步;
第二步 判别线段是否为显然不可见,如果是,则裁
剪结束;否则进行第三步 ;
第三步 求线段与窗口边延长线的交点,这个交点将
线段分为两段,其中一段显然不可见,丢弃。
对余下的另一段重新进行第一步,第二步判断,
直至结束
裁剪过程是递归的。
242
Cohen-Sutherland裁剪算法 1
#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
int encode(float x,float y) //端点编码
{ int c=0;
if(x<XL) c|=LEFT;
else if(x>XR) c|=RIGHT;
if(x<YB) c|=BOTTOM;
else if(x<YT) c|=TOP;
retrun c;
}
243
Cohen-Sutherland裁剪算法
2
void CS_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
/*(x1,y1)(x2,y2)为线段的端点坐标,其他四个参数定义窗口
的边界 */
{ int code1,code2,code;
code1=encode(x1,y1);
code2=encode(x2,y2);
while(code1!=0 ||code2!=0)
{ if(code1&code2 !=0) return; //放弃
code = code1;
if(code1==0) code = code2;
244
Cohen-Sutherland裁剪算法 3
if(code)
if(LEFT&code !=0) //左边界交点
{ x=XL;
y=y1+(y2-y1)*(XL-x1)/(x2-x1); }
else if(RIGHT&code !=0) //右边界交点
{ x=XR;
y=y1+(y2-y1)*(XR-x1)/(x2-x1); }
else if (BOTTOM&code !=0) //底边界交点
{ y=YB;
x=x1+(x2-x1)*(YB-y1)/(y2-y1); }
else if(TOP & code !=0) //顶边界交点
{ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1); }
245
Cohen-Sutherland裁剪算法 4
if(code ==code1)
{ x1=x;y1=y; code1 =encode(x,y);}
else
{ x2=x;y2=y; code2 =encode(x,y);}
}
displayline(x1,y1,x2,y2); //裁剪后直线显示
}
246
Cohen-SutherLand算法(编码算法)
对于那些非完全可见、又非显然不可见的线段,需要
求交(如,线段AD),求交前先测试与窗口哪条边所在
直线有交?(按序判断端点编码中各位的值ClCtCrCb)
不可见但非显然
• 求交测试顺序固定(左
上右下)
• 最坏情形,线段求交四
次。
求交四次
247
Cohen-SutherLand算法(编码算法)
1)特点:用编码方法可快速判断线段-完全可见和显然不可见。
2)特别适用二种场合:
大窗口场合;
窗口特别小的场合(如, 光标拾取图形时,
光标看作小的裁剪窗口。)
248
中点分割法
•基本思想:
与前一种Cohen-Sutherland算法一样首先对
线段端点进行编码,并把线段与窗口的关系分
为三种情况:
–全在、完全不在和线段和窗口有交。
– 对前两种情况,进行一样的处理。
–对于第三种情况,用中点分割的方法求出
线段与窗口的交点。
P0
A
Pm
B
P1
249
图4.21 中点分割算法
中点分割法
设要裁剪的线段是P0P1。中点分割算法可分成两个平行
的过程进行,即从P0点出发找出离P0最近的可见点(图中
的A点),和从P1点出发找出离P1最近的可见点(图中的B
点)。
P0
A
Pm
B
P1
中点分割算法
250
中点分割法
这两个可见点的连线就是原线段的可见部分。从P0出发找最近
可见点的方法是先求P0P1的中点Pm,若P0Pm不能定为显然不可见,
则取P0Pm代替P0P1,否则取PmP1代替P0P1,再对新的P0P1求中点Pm。
重复上述过程,直到P1Pm长度小于给定的小数ε为止。
P0
A
Pm
B
P1
251
Y
P0可见否?
否
P = P0
Y
exit
P0P1显然不可见
原线完全不可见
否
exit
Pm = (p0+p1)/2
Y
|Pm - P1|<ε?
否
P0 = Pm
P0Pm显然不可见?
是
Pm在裁剪框外
Y
P0 = Pm
否
exit
Pm在裁剪框内
P1 = Pm
中点分割算法框图
252
梁友栋-Barsky算法
设要裁剪的线段是P0P1。 P0P1和窗口边界交
于A,B,C,D四点,见图。
y
P1
yT
算法的基本思想是从A,B和P0
三点中找出最靠近P1的点,
图中,显然是点P0。
D
C
P0
yB
B
A
xL
xB
x
从C,D和P1中找出最靠近
P0的点。应该是点C。
那么P0C就是P0P1线段上
的可见部分。
P0C可见部分
253
梁友栋-Barsky算法
具体计算时,把P0P1写成参数方程
x = x0 + Δx · t
y = y0 + Δy · t
其中Δx=x1 - x0,Δy=y1 - y0。
把窗口边界的四条边分成两类,一类称为
始边,另一类称为终边。
254
梁友栋-Barsky算法
•当Δx≥0(或Δy≥0)时,
称x=xL(y=yB)为始边, x=xR(y=yT)为终边。
•当Δx<0(Δy<0)时,
称x=xL(y=yB)为终边, x=xR(y=yT)为始边。
P1
y
yT
D
C
P0
yB
A
p1 B
p0
xL
xB
x
255
梁友栋-Barsky算法
•求出P0P1和两条始边的交点的参数t0’和t0’’,令
t0 = max(t0’,t0’’,0 )
则t0 就是图中A、B和P0三点中最靠近P1的点的参数。
求出P0P1和两条终边的交点的参数 t1’,t1’’ ,令
t1 = min(t1’,t1’’,1)
则t1就是图中C、D和P1三点中最靠近
P0的点的参数。
t1
P1
y
yT
D
C
B
A
yB
P0
t0
xL
256 xB
x
x = x0 + Δx · t
y = y0 + Δy · t
当t1>t0时,
参数t∈[t0, t1]的线段就是P0P1的可见部分。
当t0>t1时,
整个直线段
为不可见。
t1’’
lP1
y
yT
t0’ yB
t0’’
P1
D
t 1’
lP0
C
B
A
P0
xL
xB
257
x
为了确定始边和终边,和求P0P1与它们的交点,令
QL = - Δx
D L = x0 - x L
QR = Δx
D R = x R - x0
QB = - Δy
D B = y 0 - yB
QT = Δx
D T = y T - y0
易知边界交点的参数为
ti = Di/Qi,
x = x0 + Δx · t
y = y0 + Δy · t
i= L,R,B,T
当Qi<0时,
求得的ti必是P0P1和始边的交点的参数。
当Qi>0时,ti必是P0P1和终边的交点的参数。258
y
F
B
C
A
E
xL
QL
QR
QB
QT
D
xB
=
=
=
=
- Δx
Δx
- Δy
Δx
DL
DR
DB
DT
=
=
=
=
x0
xR
y0
yT
–
-
xL
x0
yB
y0
x
Qi=0的情况
当Qi=0时,
若Di<0,则P0P1是完全不可见的(如图中AB,有QR=0,DR<0).
当Qi=0 而相应的 Di ≥0 时 则是另一种情况,图中的EF就
是这种情况,它使QL=0,DL>0和QR=0,DR>0。这时由于EF和
x=xL及x=xR平行,故不必去求出EF和x=xL及x=xR的交点,而让
EF和y=yT及y=yB的交点决定直线段上的可见部分。
259
梁友栋-Barskey参数化裁剪算法 1
void LB_LineClip(x1,y1,x2,y2,XL,XR,YB,YT)
float x1,y1,x2,y2,XL,XR,YB,YT;
{ float dx,dy,u1,u2;
tl=0;tu=1;
dx =x2-x1;
dy =y2-y1;
if(ClipT(-dx,x1-Xl,&u1,&u2))
if(ClipT(dx,XR-x1, &u1,&u2))
if(ClipT(-dy,y1-YB, &u1,&u2))
if(ClipT(dy,YT-y1, &u1,&u2))
{ displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy);
return; }
}
260
梁友栋-Barskey参数化裁剪算法 2
bool ClipT(p,q,u1,u2)
float p,q,*u1,*u2;
{
float r;
if(p<0)
{ r=q/p;
if(r>*u2) return FALSE;
else if(r>*u1)
{ *u1=r;
return TRUE;
}
}
else if(p>0)
{ r=p/q;
if(r<*u1) return FALSE;
else if(r<*u2)
{ *u2=r;
return TRUE;
}
}
else if(q<0) return FALSE;
return TRUE;
}
261
多边形的裁剪
262
多边形的裁剪
• 对多边形的裁剪不等于把多边形的每一条边进行裁剪。
• 因为在图形学中,多边形被认为是一个封闭的区域,它把
平面分为多边形内和多边形外,
• 对一个多边形的裁剪结果仍要求是多边形,且原来是多边
形内的点也在裁剪后的多边形内。
•
一部分窗口的边界可能成为裁剪后的多边形的边界,一个
凹多边形裁剪后可能成为几个多边形。
263
对多边形裁剪的Sutherland-Hodgman算法是一
种简便的方法,只要对多边形用窗口的四条边依次
裁剪四次,便可得到裁剪后的多边形。
Sutherland-Hodgman算法
264
Sutherland-Hodgman基本思想
• 基本思想是一次用窗口的一条边裁剪多
边形。
• 考虑窗口的一条边以及延长线构成的裁
可
可
可
可
剪线该线把平面分成两个部分:可见一
见
见
见
见
一
一
一
p
一 p
p
S
侧
侧;不可见一侧
侧
侧
侧
p
• 多边形的各条边的两端点S、P。它们与
S
S
S
(1)
(4)
(2)
(3)
裁剪线的位置关系只有四种
265
Sutherland-Hodgman基本思想
• 假设当前处理的边为SP,顶点S在上一轮中
已经处理.
• 对于情况(1)仅输出顶点P;
• 情况(2)输出0个顶点;
• 情况(3)输出线段SP与裁剪线的交点I;
可
可
可
可
见
见
见
见
• 情况(4)输出线段SP与裁剪线的交点I和
一 p
一
一
一 p
p
S
侧
侧
侧
侧
终点P
S
(1)
p
S
(2)
(3)
S
(4)
266
Sutherland-Hodgman算法的框图
取点P
否
是否第一点?
是
SP和e相交?
是
F
计算SP和
e的交点I
输出I
否
P
(a)
S
P
是
设封闭多边形的顶点为
P1,P2,…Pn,框图中e是表示窗口
的四条边中正在裁剪的一条边,
每次裁剪时第一个点存放在F中,
以便对最后一条边裁剪时使用。
用图(a)中的算法对边P1P2,
P2P3, …Pn-1Pn作裁剪。
S在e的可见侧
输出S
否
退出
图(a)
267
取点F为P
是
SP和e相交?
计算SP和
e的交点I
输出I
否
退出
(b)
图(b)
用图(b)中的算法对最后一条边PnP1作裁剪。裁剪好一条
边便输出一条边。
268
–上述算法仅用一条裁剪边对多边形进行裁剪,
得到一个顶点序列,作为下一条裁剪边处理
过程的输入。
• 裁剪结果的顶点构成:裁剪边内侧的原
顶点;多边形的边与裁剪边的交点。顺
序连接。
流水线过
程(左上右
下):
亦称逐边裁
剪算法
269
多边形裁剪
一个凹多边形可能被裁剪成几个小的多边形,如何确定这
些小多边形的边界?
270
Weiler-Athenton多边形裁剪算法
裁剪窗口为任意多边形(凸、凹、带内环)的
情况:
– 主多边形:被裁剪多边形,记为A
– 裁剪多边形:裁剪窗口,记为B
271
Weiler-Athenton多边形裁剪算法
• 主多边形和裁剪多边形把二维平面分成
两部分。
• 内裁剪:A∩B
• 外裁剪:A - B
裁剪结果区域的边界由A的部
分边界和B的部分边界两部分
构成,并且在交点处边界发生
交替,即由A的边界转至B的边
界,或由B的边界转至A的边界
272
Weiler-Athenton多边形裁剪算法
– 如果主多边形与裁剪多边形有交点,则交点成
对出现,它们被分为如下两类:
• 进点:主多边形边界由此进入裁剪多边形内
如,I1, I3, I5, I7, I9, I11
• 出点:主多边形边界由此离开裁剪多边形区
域.
如, I0, I2, I4, I6, I8, I10
273
Weiler-Athenton多边形裁剪算法
Weiler_Athenton裁剪算法(内裁剪)步骤:
1)建顶点表;
1、建立主多边形和裁剪多边的顶点表.
2)求交点;
3)裁剪… …
2、求主多边形和裁剪多边形的交点,并将这些交点按
顺序插入两多边形的顶点表中。在两多边形顶点表中的
相同交点间建立双向指针 。
3、裁剪
274
Weiler-Athenton多边形裁剪算法
3、裁剪
• 如果存在没有被跟踪过的交点,执行以下步骤:
•
(1)建立裁剪结果多边形的顶点表.
•
(2)选取任一没有被跟踪过的交点为始点,将其
输出到结果多边形顶点表中.
•
(3)如果该交点为进点,跟踪主多边形边边界;
否则跟踪裁剪多边形边界.
•
(4) 跟踪多边形边界,每遇到多边形顶点,将其
输出到结果多边形顶点表中,直至遇到新的交点.
•
(5)将该交点输出到结果多边形顶点表中,并通
过连接该交点的双向指针改变跟踪方向(如果上一步
275
跟踪的是主多边形边界,现在改为跟踪裁剪多边形边
Weiler-Athenton多边形裁剪算法
276
Weiler-Athenton多边形裁剪算法
从目标多边形A开始,逆时针扫描边界:
•如果进入裁剪窗口多边形,记录交点,然后继续扫描目标多
边形
•如果离开裁剪窗口多边形,记录交点,并右转,然后以同样
方式继续跟踪裁剪窗口多边形(即将裁剪窗口多边形作为目
标多边形,将目标多边形作为裁剪窗口多边形,继续前面操
作。)
当遍历路径产生子多边形时,将子多边形作为结果的一部分
输出,然后从标记为没有遍历的边的起点或部分边的交点处
开始,继续对原目标多边形进行遍历。当原目标多边形所有
边都遍历后,算法结束。
277
Weiler-Athenton多边形裁剪算法
10
13
11
9
1
12
5
6
7
8
2
4
3
•上图从1-2求交,2-3,3-4,4-5右转,5-6,6-7,7-8第二次
右转,输出子多边形;
•从第一次变换窗口处的交点开始遍历A,从9到10再到11,没有
输出。跳过已经遍历的6和7后,继续遍历12和13直到结束。
278
三维图形的裁剪
•
在规范化坐标系定义了两种视域
•平行投影时视域如图4.31(a)所示,它是由方程
x=0, x=1,y=0,y=1,z=0,z=1代表的六个平面围成的立方体。
• 透视时的视域如图4.31(b)的棱台,它是由方程
x=z, x=-z, y=z, y=-z, z=zmin和z=1代表的六个平面围成。
• 图形对三维的裁剪就是把视域内的图形保留下来,把视域
外的部分裁剪掉。
y
y
z
z
(a)
x
图4.31 两种视域
(b)
x
279
前面讲的各种裁剪方法均可以推广至三维。例如
Sutherland-Cohen算法中的编码应为六位。括号中的
条件适用于透视的情况,平行投影时用括号外的条件。
点在视域上面,第一位为1,y>1, (y>z)
点在视域下面,第二位为1,y<0, (y<-z)
点在视域右面,第三位为1,x>1, (x>z)
点在视域左面,第四位为1,x<0, (x<-z)
点在视域后面,第五位为1,z>1, (z>1)
点在视域前面,第六位为1,z<0, (z<zmin)
280
设线段的起点和终点分别为P0(x0,y0,z0)和P1(x1,y1,z1),直
线方程可表示成参数形式
x = x0 + (x1-x0)t,
y = y0 + (x1-x0)t,
x = x0 + (x1-x0)t
(4.39)
和视域的边界面,例如y=1求交时,可由
1=(y1 - y0)t’ + y0,
t’=(1-y0)/(y1-y0)
求得交点的参数t’,再把t’代入(4.39),即可得交点的坐标。
求P0P1和平面x=z的交点时,可把(4.39)代入x=z中求得交点处
的参数
t’=(z0-x0)/[(x1-x0)-(z1-z0)]
(4.40)
把t’代入式(4.39)即可得到交点的坐标。
281
梁友栋-Barsky算法也很容易推广到三维。
•当视域为立方体时,这种推广是直接的。
•当视域为棱台时,对x=z,x=-z,y=z,y=-z四个平面来说,对应于二维裁
剪时的Q和D值可取
QL = -(Δx + Δz), DL = z0 + x0
QR = (Δx - Δz),
D R = z 0 - x0
QB = -(Δy + Δz), DB = z0 + y0
QT = (Δy - Δz),
D T = z 0 - y0
对z=zmin和z=1两个平面,相应的Q和D值可取为
QF = -Δz), DF = z0 - zmin
QRA = Δz, DRA = 1 - z0
易知相应平面和P0P1交点的参数值为ti=Di/Qi,i=L,R,B,T,F,BA。
282
三维图形的显示流程图
• 显示流程图
– 观察变换:从世界坐标系到观察坐标系的变
换
283
三维图形的显示流程图
• 模型变换
–模型坐标系
• Modeling Coordinate
• 物体的局部坐标系
• 在模型坐标系中物体的表示简单
284
三维图形的显示流程图
– 模型变换
• Modeling Transformation
• 将物体从本身的模型坐标系变换到上层物体的模
型坐标系(或世界坐标系)的几何变换
• 模型变换是构造复杂物体的方法
• 例子:
模型变换1
285
三维图形的显示流程图
• 何时裁剪
– 投影之前裁剪----三维裁剪
• 优点
– 只对可见的物体进行投影变换
• 缺点
– 三维裁剪相对复杂
– 投影之后裁剪----二维裁剪
• 优点
– 二维裁剪相对容易
• 缺点
– 需要对所有的物体进行投影变换
286
三维图形的显示流程图
–采用二维裁剪的三维图形显示流程图
–在投影之前裁剪的理由
• 三维物体的表面通常被离散表示成多边形或折线,
而对这类简单图元,三维裁剪同样比较简单。
• 三维图形在显示过程中需要被消隐,做这个工作
要有图形的深度信息,所以必须在投影之前完
成 。 消隐很费时,如果在此之前裁剪(或部分
裁剪)掉不可见的图形,可使
需要消隐的图形减至最小。
287
三维图形的显示流程图
• 规范视见体
– 平行投影的规范视见体
• 半立方体
 u  1, u  1

 v  1, v  1
n  0, n  1

– 透视投影的规范时间体
• 四棱台
 u  n, u   n

 v  n, v   n
 n   n , n  1
min

288
三维图形的显示流程图
– 为什么引入规范视见体
• 简化投影
• 简化裁剪
–规范化变换
• 将任意视见体变换成规范视见体的变换
–规范投影坐标(三维屏幕坐标 )
• 经规范化的观察坐标系
289
三维图形的显示流程图
– 采用规范视见体的三维图形显示流程图
290
三维图形的显示流程图
• 平行投影视见体的规范化
– 将任意的平行投影视见体变换为规范平
行投影视见体
– 方法:变换的分解与合成
–N步骤
par  S par  Tpar 2  SH par  Tpar1
– 结果
291
三维图形的显示流程图
292
三维图形的显示流程图
• 透视投影视见体的规范化
– 将任意的透视投影视见体变换为规范透视投
影视见体
– 方法:变换的分解与合成
– 步骤
– 结果
N per  S per  SH per  Tper
293
三维图形的显示流程图
294
三维图形的显示流程图
0
0
• 规范视见体之间的变换
1 0
–

0 1

0
0
将透视投影的规范视见体变换为平行投

1
nmin 
M

0 0

影的规范视见体
1  nmin 1  nmin 

0 0
1
0 
– 为什么
• 关于长方体的裁剪较关于正四棱台的裁剪
简单。
• 平行投影较透视投影简单。
295
三维图形的显示流程图
– 将视见体变换结合到透视投影的规范化变换
矩阵中
N per  M  N per  M  S per  SHper  Tper
– 采用视见体变换的三维图形显示流程图
296
三维裁剪
• 三维裁剪的两种方法
–将齐次坐标转换为三维坐标,在三维
空间关于视见体裁剪
• 优点:三维裁剪相对容易
• 缺点:需要将齐次坐标转换为三维坐标
–直接在四维齐次坐标空间中进行裁剪
• 优点:
– 不需要将齐次坐标转换为三维坐标
–有理曲线曲面可能直接用齐次坐标来表示,对
它们的裁剪只能在齐次坐标空间中进行
• 缺点:四维裁剪相对复杂
297
三维裁剪
• 关于规范视见体的裁剪
– 直线段裁剪的Cohen_Sutherland算法、*梁_Barskey
算法的直接推广
– 多边形裁剪的Sutherland_Hodgman算法的直接推广
• 齐次坐标空间中的裁剪
– 四维裁剪体的定义
298
*图形显示过程小结
• 对应于三维裁剪的实现过程
1、将三维坐标扩展为齐项坐标,(x,y,z)(x,y,z,1);
2、进行模型变换;
3、进行观察变换;
4、进行视见体的规范化变换Npar或Nper;
5、除以h返回三维空间(有些情况下,h保持为1,所
以不必做除法运算);
6、关于规范视见体进行裁剪;
7、将三维坐标扩展为齐项坐标;
8、进行投影变换Mort或Mper;
9、进行窗口至视区的变换;
10、除以h返回二维设备坐标系 ;
11、扫描转换(显示)。
299
*图形显示过程小结
• 对应齐次坐标空间裁剪的实现过程
1、将三维坐标扩展为齐次坐标(对于直接用齐次坐标
表示的图形不需要进行这一步);
2、进行模型变换;
3、进行观察变换;
4、进行视见体的规范化变换Npar或
N per

;
5、在齐项坐标空间中关于裁剪窗口裁剪;
6、进行平行投影变换Mort。
7、进行窗口至视区的变换。
8、除以h返回二维设备坐标系。
9、扫描转换(显示)。
300
作业
1
编程实现直线段裁剪的Cohen_Sutherland算法、中
点算法、梁_Barskey算法中任意两种(演示)。
2 编程实现多边形裁剪的Sutherland_Hodgman算法
(逐边演示)。
301
第7章 图形变换
•
•
•
•
•
•
•
•
•
变换的数学基础
二维基本变换
齐次坐标与二维变换的矩阵表示
复合变换与变换的模式
其它变换
二维图形的显示流程图
窗口到视区的变换
三维几何变换
坐标系之间的变换
302
变换的数学基础
• 矢量
(n元组,对应n维空间中的一个点)
u x 
U  u y 
u z 
vx 
V  v y 
 v z 
– 矢量和
u x  vx 
U  V  u y  v y 
 u z  v z 
303
变换的数学基础
– 矢量的数乘
 kux 
k  U  ku y 
 kuz 
– 矢量的点积
U V  uxvx  u y vy  uz vz
• 性质
U V  V U
U V  0  U  V
U U  0  U  0
304
变换的数学基础
– 矢量的长度
U  U  U  u x  u y2  u z2
• 单位矢量 || U||=1
• 点积运算的几何解释
• 矢量的夹角
U V
cos 
U V
2
– 矢量的叉积
i
j
U V  ux
uy
vx
vy
u y v x  v y u z 


u z  v x u z  u x v z 
vz u x v y  vx u y 
k
305
变换的数学基础
• 矩阵
m n
–
–
–
–
–
阶矩阵
A
 a11

 a21


 am1
a12
a1n
a22
a2 n
am 2
amn






n阶方阵
当m=n时
零矩阵
矩阵元素全为零
行向量与列向量 m=1 行矩阵, n=1 列矩阵
单位矩阵 n阶矩阵的主对角线元素均为1,其余元
素为0。
306
变换的数学基础
• 矩阵
–
–
–
–
–
矩阵的加法
矩阵的数乘
矩阵的乘法
矩阵的转置
矩阵的逆
307
二维基本变换
• 平移变换
P  P  T
 x 
P   
 y 
 x
P 
 y
t x 
T  
t y 
 x  x  t x
 
y  y  ty
308
二维基本变换
• 旋转变换
– 绕坐标原点旋转角度  (逆时针为正,顺时
针为负)
P  R  P
cos
R
 sin 
 sin  
cos 
 x '  x cos  y sin 

 y '  x sin   y cos 
309
二维基本变换
• 放缩变换
•  x '  sx x
在x轴方向和y轴方向分别放缩sx和sy倍


 y '  sy y
P  S  P
sx
S
0
0
s y 
– 以坐标原点为放缩参照点
– 不仅改变了物体的大小和形状,也改变了它
离原点的距离
310
齐次坐标与二维变换的矩阵表
示
• 为什么需要齐次坐标?
实际绘图中,常要对图形对象作连续的多个变换,例如先
平移,再旋转、放大等。
如果需要对图形进行旋转和放缩变换,可以先对两个变换
进行复合变换,将两次运算转换成一次性的矩阵与向量乘
法。
P ''  S  P  S  R  P  A  P
 sx
A SR  
0
0  cos 
s y   sin 
 sin    sx cos 


cos    s y sin 
 sx sin  
s y cos  
但如果再加入平移变换,就不易合并了。 平移变换和旋转、缩放变换的
表示形式不一样,平移是加法,旋转和缩放是乘法。为使变换合成容易,
引入齐次坐标的概念。
311
齐次坐标与二维变换的矩阵表
示
多个变换作用于多个目标
变换合成
变换合成的问题
引入齐次坐标
变换的表示法统一
312
齐次坐标与二维变换的矩阵表
示
• 齐次坐标
– 定义
• (x,y)点对应的齐次坐标为 ( xh , yh , h)
xh  hx, yh  hy, h  0
( xh1 , yh1 , h1 ) ( xh , yh , h2 )
2
2
– (x,y)点对应的齐次坐标为三维空间的一条直
线
 xh  hx

 y h  hy
 z h
 h
313
齐次坐标与二维变换的矩阵表
示
• 标准齐次坐标(x,y,1)
• 二维变换的矩阵表示
– 平移变换
 x   1 0 t x   x 
 x
记为
 y  0 1 t   y   T (t , t )  y 
y  
x y  
  
 1  0 0 1   1 
 1 
– 旋转变换
 x  cos
 y   sin 
  
 1   0
 sin 
cos
0
0  x 
 x
记为



0  y   R ( )  y 
 1 
1  1 
314
齐次坐标与二维变换的矩阵表
示
放缩变换
 x   s x
 y    0
  
 1   0
0
sy
0
0  x 
 x
记为



0  y   S ( s x , s y )  y 
 1 
1  1 
• 变换具有统一表示形式的优点
– 便于变换合成
– 便于硬件实现
315
齐次坐标与二维变换的矩阵表
示
平移和旋转变换具有可加性
T (t x2 , t y2 )  T (t x1 , t y1 )  T (t x2  t x1 , t y2  t y1 )
R( 2 )  R(1 )  R( 2  1 )
放缩变换具有可乘性
T (tx2 , t y2 )  T (tx1 , t y1 )  T (tx2  tx1 , t y2  t y1 )
316
复合变换及变换的模式
• 问题:如何实现复杂变换?
变换分解
• 关于任意参照点
变换合成
Pr ( xr , yr )
的旋转变换
R( xr , yr ; )  T ( xr , yr )  R( )  T ( xr , yr )
317
复合变换及变换的模式
R( xr , yr ; )  T ( xr , yr )  R( )  T ( xr , yr )
1 0
 0 1
0 0
xr  cos 
yr    sin 
1   0
cos 
  sin 
 0
 sin 
cos 
0
 sin 
cos 
0
0  1 0  xr 
0   0 1  yr 
1  0 0 1 
xr (1  cos  )  yr sin  
yr (1  cos  )  xr sin  

1
318
复合变换及变换的模式
• 关于任意参照点 Pr ( xr , yr ) 的放缩变换
S ( xr , yr ; sx , s y )  T ( xr , yr )  S (sx , s y )  T ( xr , yr )
319
复合变换及变换的模式
• 变换的结果与变换的顺序有关(矩阵乘法不可
交换,先作用的变换放在连乘式的右端,后作用的变换放在连乘
式的左端)
Translate2D(1,0);
Rotate2D(45);
House();
Rotate2D(45);
Translate2D(1,0);
House();
320
复合变换及变换的模式
• 变换的固定坐标系模式
– 相对于同一个固定坐标系
– 先调用的变换先执行,后调用的变换后执行
Rotate2D(45);
Translate2D(1,0);
House();
321
复合变换及变换的模式
• 人的思维方式
– 每次变换产生一个新的坐标系
• 变换的活动坐标系模式
– 先调用的变换后执行,后调用的变换先执行(图形
系统一般用堆栈实现)
322
复合变换及变换的模式
Rotate2D(45);
Translate2D(1,0);
House();
例子
323
其它变换
• 对称变换
– 关于x轴的对称变换
1 0 0
SYx  0  1 0
0 0 1
– 关于y轴的对称变换
  1 0 0
SYy   0 1 0
 0 0 1
324
其它变换
– 关于任意轴的对称变
换
总的变换:
T2  R2  SYx  R1  T1
325
其它变换
• 错切变换
(弹性物体有时会用到错切变换)
保持图形上各点的某一坐标值不变,而 另一坐标值关于该坐标
值呈线性变换。坐标不变的轴称为依赖轴,余下的坐标轴称为方
向轴。
– 以y轴为依赖轴的错切变换
• 以y=0为参考轴,切变程度由shx=tanα
 x  x  shx y

 y  y
1 shx
SH y ( shx )  0 1
0 0
0
0
1
326
其它变换
• 以平行x轴的任意直线y  yref 为参考轴
 x '  x  ( y  yref ) shx

y'  y
1 shx
SH y ( shx , yref )  0 1
0 0
 shx  yref 

0


1
327
其它变换
– 以x轴为依赖轴的错切变换
x  x

 
 y  sh y x  y
 1
SH x ( sh y )   sh y
 0
0 0
1 0
0 1
328
其它变换
• 仿射变换 (二维线性变换的一般形式,保持两条平行直线间
的平行关系)
 x  ax  by  e
表示为: 
 y  cx  dy  f
a b
变换矩阵为: A f   c d
 0 0
e
f 
1 
329
二维图形的显示流程图
• 图形以数字形式存储和处理,坐标系建立了图
形与数之间的对应联系
– 世界坐标系(world coordinate)
– 用户坐标系(user coordinate)
– 局部坐标系(local coordinate)
330
二维图形的显示流程图
– 屏幕坐标系(screen coordinate)
– 设备坐标系(device coordinate)
331
二维图形的显示流程图
• 窗口
– 在世界坐标系中指定的矩形区域
– 用来指定要显示的图形
• 视区
– 在设备坐标系(屏幕或绘图纸)上指定的矩
形区域
– 用来指定窗口内的图形在屏幕上显示的大小
及位置
• 窗口到视区的变换
332
二维图形的显示流程图
333
窗口到视区的变换
• 目标
– 将窗口之中的图形变换到视区中
• 变换的求法
– 变换的分解与合成
M wv  T (umin ,v min ) S (
Ex Ev
, )T ( xmin , y min )
Ex E y
334
M wv
复合变换及变换的模式
E E
 T (u ,v ) S ( , )T ( x , y )
x
min
min
v
Ex E y
1 0 umin   Eu / Ex
 0 1 vmin    0
0 0 1   0
 Eu / Ex
  sin 
 0
 sin 
Ev / E y
0
min
0
Ev / E y
0
min
0 1 0  xmin 
0  0 1  ymin 
1  0 0
1 
 xmin Eu / Ex  umin 
 ymin Ev / E y  vmin 

1
335
窗口到视区的变换(2/2)
当窗口的边与坐标轴不平行时
M wv
Ex Ev
 T (umin ,v min )S ( , ) R( )T ( xmin , y min )
Ex E y
336
三维几何变换
• 三维齐次坐标
• (x,y,z)点对应的齐次坐标为
( xh , yh , zh , h)
xh  hx, yh  hy, zh  hz, h  0
• 标准齐次坐标(x,y,z,1)
• 采用右手坐标系
旋转轴
x
y
z
正的旋转方向
yz
zx
x y
337
三维几何变换(2/5)
• 平移变换
1
0
T (t x , t y , t z )  
0

0
0
1
0
0
0 tx 
0 t y 
1 tz 

0 1
• 放缩变换
1
0
S (sx , s y , sz )  
0

0
0
1
0
0
0 sx 
0 s y 
1 sz 

0 1
338
三维几何变换(3/5)
• 旋转变换
– 绕x轴
0
1
0 cos
Rx ( )  
0 sin 

0
0
0
 sin 
cos
0
0
0
0

1
0 sin 
1
0
cos
0
0
0
0
0

1
– 绕y轴
 cos
 0
R y ( )  
 sin 

 0
339
三维几何变换(4/5)
– 绕z轴
cos
 sin 
Rz ( )  
 0

 0
 sin 
cos
0
0
0
0
1
0
0
0
0

1
0 shx
1 shy
0 1
0 0
0
0
0

1
• 错切变换
1
0
SH z ( shx , shy )  
0

0
340
三维几何变换(5/5)
• 对称变换
– 关于坐标平面xy的对称变换
1
0
SYxy  
0

0
• 三维变换的一般形式
 a11
a
A   21
a31

0
0 0
1 0
0 1
0 0
a12
a22
a32
0
a13
a23
a33
0
0
0
0

1
0
0
0

1
341
坐标系之间的变换
• 什么是?
– 建立坐标系之间的变换关系
– 将图形从一个坐标系中变换到另一个坐标系中,
同一图形在不同坐标系中的表示
• 怎样求?
342
习题
7、在坐标系oxyz中,求一个变换将
P(1,1,1)Q(2,2,2)变换到z轴上:P在坐标原
点,Q在z轴正半轴。
y
y
Q
P
o
z
M
x
Q
x
o(P)
z
343
第8章 投影
•
•
•
•
•
•
•
三维图形的基本问题
平面几何投影
观察坐标系中的投影变换
投影举例
三维图形的显示流程图
三维裁剪
图形显示过程小结
344
三维图形的基本问题(1/4)
在二维屏幕上如何显示三维物体?
– 显示器屏幕、绘图纸等是二维的
– 显示对象是三维的
– 解决方法----投影
– 三维显示设备
如何表示三维物体?
– 二维形体的表示----直线段、折线、曲线段、
多边形区域
– 二维形体的输入----简单(图形显示设备与
形体的维数一致)
345
三维图形的基本问题(2/4)
– 三维形体的表示----空间直线段、折线、曲线
段、多边形、曲面片
– 三维形体的输入、运算、有效性保证----困难
– 解决方法----各种用于形体表示的理论、模型、
方法 (线框模型、表面模型、实体模型)
如何反映遮挡关系?
– 物体之间或物体的不同部分之间存在相互遮
挡关系
– 遮挡关系是空间位置关系的重要组成部分
– 解决方法----消除隐藏面与隐藏线
346
三维图形的基本问题(3/4)
如何产生真实感图形
– 何谓真实感图形
• 逼真的
• 示意的
– 人们观察现实世界产生的真实感来源于
• 空间位置关系----近大远小的透视关系和遮挡关系
• 光线传播引起的物体表面颜色的自然分布
– 解决方法----建立光照明模型、开发真实感图
形绘制方法
347
三维图形的基本问题(4/4)
三维图形的基本研究内容
1.
2.
3.
4.
投影
三维形体的表示
消除隐藏面与隐藏线
建立光照明模型、开发真实感图形绘制方法
348
投影(projection)变换
由于显示器和绘图机只能用二维空间
来表示图形,要显示三维图形就要用投
影方式来降低其维数。
–投影
•将n维的点变换成小于n维的点
•将3维的点变换成2维的点
349
在三维坐标系统中,物体上的每一点都以三个分
量(x,y,z)描述,这样的物体称为三维物体。要想
将一个三维物体描画在一个二维的平面,如纸面,
荧光屏面上,必须对三维物体进行投影。投影
(project)是一种使三维对象映射为二维对象的变
换。它可描述为:
project(object(x,y,z))→object(x′,y′)
350
投影(projection)
• 平面几何投影及其分类
– 投影中心(COP:Center of Projection)
• 视觉系统—观察点、视点
• 电影放映机—光源
– 投影面
• 不经过投影中心
• 平面--照相机底片
• 曲面—球幕电影,视网膜
351
平面几何投影分类
投影的要素除投影对象,投影面外,还有投影线。
按照投影线角度的不同,有两种基本投影方法:
•
1 平行投影(parallel projection)。它使用一组平
行投影线将三维对象投影到投影平面上去(图
3.21(a))。
•
2 透视投影(perspective projection)。它使用一
组由投影中心产生的放射投影线,将三维对象投
影到投影平面上去。
352

投影分类
投影中心与投影平面之间的距离为无限
投影中心与投影平面之间的距离为有限
根据投影
方向与投
影平面的
夹角
根据投影
平面与坐
标轴的夹
角
353
一、 投影变换的分类:
正投影 (三视图)
正平行投影
正轴测投影
平行投影
斜平行投影
正等测投影
正二测投影
正三测投影
(三轴变形系数相等)
(两轴向变形相等)
(三轴变形系数各不相同)
斜等测投影
(三轴都不缩短,但一根轴倾斜)
斜二测投影
(一根轴倾斜,且缩短为1/2)
一点透视投影
透视投影
二点透视投影
三点透视投影
354
在计算机图形软件中所采用笛卡尔(cartesian)直角三
维坐标系统,按照z轴方向的不同有两种形式:
1 右手系统:当用右手握住z轴时,大姆指指向z轴
的正方向(图(a)),其余四个手指从x轴到y轴形成一个弧。
(Z值越大,越靠近视点)
2 左手系统:当用左手握住z轴时,大姆指指向z轴
的正方向(图(b));其余四个手指从x轴到y轴形成一个弧。
(Z值越大,越远离视点)
两种三维直角坐标系统
355
(a)右手系统
(b)左手系统
平面几何投影分类
356
F为投影平面;p1p2 为三维直线;p’1p′2 是p1p2 在F上的投影;
虚线显示投影线;o是投影中心。
•由平行投影方法表现三维对象的图,称为正视图和轴测图;
•由透视投影方法表现三维对象的图,称为透视图。
357
平行投影
按照标准线与投影面的交角不同,平行投影分
为两类:正交平行投影和斜交平行投影。
1、正交平行投影(orthographic P.P.)的投影线
与投影平面成90°角。将一个三维点(x,y,z)用正
交平行投影法投影平面xoy上,得到一个二维点
(xp,yp)。这种变换,可以由正交平行交换公式来
计算,它为
• xp=x;
• yp=y;
• zp=0
358
同样,也可以将三维物体正交平行投影
于xoz和yoz平面上,分别获平视与侧视图。
设计中常用正交平行投影来产生三视图称
为正视图。它们具有x,y方向易于测量的
特点,因此作为主要的工程施工图纸。

三视图:投影面与某一坐标轴垂直,即投影方
向与该坐标轴的方向一致。
分类(组成):主视图X、侧视图Y、俯视图Z
注意:此处, X指前, Y指右,Z指上
359
平面几何投影(12/12)
• 三视图:正视图、侧视图和俯视图
360
三视图的变换矩阵(3D用户坐标系进行)
特点:三视图常用于工程制图。但一种三视图上只有物体一个侧面的投影,
所以单独从某个方向的三视图上是很难想象出物体的三维形状的。只有将主、
侧、俯三个视图放在一起,才能综合出物体的空间形状。
以CRT作图纸,显示三视图
用户坐标系3D设备坐标系视区
选择视图,建立相应的视图区选好视图后,在CRT上为其建立视图区,每个
视图区代表一个坐标平面,操作一个视图。
根据3D物体的复杂程度,合理选择视图数目。原则:在能表示清楚物体的形
状和尺寸的前提下,视图数目越小越好。
361
1)主视图(y)
2)俯视图 z
3)侧视图x
三视图的生成就是把x、y、z坐标系的形体投影到z=0的平面,变换
到u、v、w坐标系。一般还需将三个视图在一个平面上画出,这时就
得到下面的变换公式,其中(a,b )为u、v坐标系下的值,tx、ty、tz
均如图中所示。 (注:这里以垂直Y轴为主视图)
362
平行正投影三视图
上
1.投影规律:
左
主、俯视图 “长对正”
主、左视图 “高平齐”
俯、左视图 “宽相等”
左
主xoy
高平齐
右
上
后 左 前
yoz
下
下
长对正
后
俯zox
右
宽相等
前
主视图  上下、左右;
2.各视图中的方位: 俯视图  前后、左右;
363
左视图  前后、上下。
例三棱柱及表面上各点的三视图。
S
A
B
a’
(b’)
a’
(b’)
a”
b”
(b)
a
364
轴测图的形成与分类
定义:用一个投影面来表达物体长、宽、高三个方
向形状的图样;
特点:直观性好,立体感强。但作图复杂且有变形;
用途:一般作为工程上的辅助图样。
正轴测图
按形成方法可分为二大类:
斜轴测图
365
轴测图的参数
Z
1. 轴间角:
相邻两轴测轴之间的夹角。
X
2. 轴向变形系数:
Y
沿轴测轴测量而得到的投影长度与实际长度之比。
X轴的轴向变形系数:
p
=
oa / OA
Y轴的轴向变形系数:
q
=
ob / OB
Z轴的轴向变形系数:
r
=
oc / OC
366
( 三)
平行性:
轴测图的投影特性
(1) 物体上相互平行的直线,
其轴测投影仍相互平行;
(2) 物体上与坐标轴平行的直线,
其轴测投影仍与该轴测轴平行。
367
( 四)
常见的几种轴测图
1. 正(斜)等轴测图:
常见轴测图
p = r = q
2. 正(斜)二等轴测图:p = r  q
3. 正(斜)三轴测图: p  r  q
368
正等轴测图 斜二等轴测图 正二等轴测图
变形
p=q=r
p=r=1
p=r1
系数
= 0.82  1
q = 0.5
q  0.5
轴
XZ:
间
XY:
角
YZ:
120
XZ:90
XZ:9710
XY:
XY:
135
YZ:
ZZ Z
13125
YZ:
ZZ
Z
9710
120
120
120
120 120 120
30
0 0 3030
30 300
30
X X
120
YY
X
120 120
Y
XX
90
90
0 0 135
135
45
45
135
135
8
1
X
Y
Y
0
13125 8
13125
7
369
Y
正 轴 测 图
(1) 以正投影面作为轴测投影面(P);
形成的方法: (2) 投影方向垂直于轴测投影面( S  P );
(3) 改变物体与投影面的相对位置。
S
P
P
(使其三方向的轴均倾斜于轴测投影面)
370
斜 轴 测 图
(1) 以正投影面作为轴测投影面(P);
形成的方法:
(2) 投影方向倾斜于轴测投影面( S ∠ P );
(3) 物体与投影面的相对位置不变。
S
P
P
(使其 X、Z 轴平行于轴测投影面)
371
轴 测 图
半圆弧变
成椭圆弧
圆形变
成椭圆
矩形变
成棱形
轴承座零件的轴测图
372
轴测图的平行性
Z
Z
X
Y
X
三视图
Y
Y
物体上平行的直线轴测投影仍平行
与轴平行的直线仍与该轴测轴平行
373
常见轴测图
374
Orthographic Projection
375
平行投影(Parallel )
设给定的投影方向为(xd,yd,zd)。假设P(xp,yp)
为任一点Q(x,y,z)在该投影方向上在z=0平面上的
投影。又设Q和P在oxz平面上的投影分别为Q’和P’。
α为Q’P’与x轴的夹角,易知
tgα=zd/xd。
y
P
x
Q
xP
P’α
x
β
z
P’
O
Q’
x
Q’
z
zc
z
376
平行投影计算公式
又从图中可以得出:
xp= x
=
=
=
+
x
x
x
ztgβ
+ z*tg(α-π/2)
– z*ctgα
– z*xd/zd
同理可得
yp = y – z*yd/zd
上两式即平行投影的计算公式。
y
x
P
Q
xP
P’α
β
z
P’
O
x
Q’
z
Q’
zc
z
377
x
透视投影 (Perspectiveprojection)
378
相机(Camera )模拟方式
实际上,从三维空间到二维平面,就如同用相机拍照一样,
通常都要经历以下几个步骤 :
•
第一步,将相机置于三角架上,让它对准三维景物
(视点变换,Viewing Transformation)。
•
第二步,将三维物体放在适当的位置(模型变换,
Modeling Transformation)。
•
第三步,选择相机镜头并调焦,使三维物体投影在二
维胶片上(投影变换,Projection Transformation)。
•
第四步,决定二维像片的大小(视口变换,Viewport
Transformation)。
•
这样,一个三维空间里的物体就可以用相应的二维平
面物体表示了,也就能在二维的电脑屏幕上正确显示了。
379
相机(Camera )模拟方式
透视投影(Perspectiveprojection)
380
透视投影(Perspective Projection)
透视投影符合人们心理习惯,即离视点近的
物体大,离视点远的物体小,远到极点即为消失,
成为灭点。它的视景体类似于一个顶部和底部都
被切除掉的棱椎,也就是棱台。这个投影通常用
于动画、视觉仿真以及其它许多具有真实性反映
的方面。
381
Ys
S
简单的一点透视投影变换
Y
Qw
Qs
P0
O
Z
Qw (Xw, Yw, Zw)
Xs
Qs (Xs, Ys)
Z2
P0 :
视点
S平面:投影面,屏幕画面
点Qw的透视:P0Qw与平面S的交点
Z1 X
当投影面与某轴垂直时为一点透视;
当投影面平行于某坐标轴,但与另
外两轴不垂直时为二点透视;否则
为三点透视
382
透视投影(Perspective projection)
y
xc x
P
Q
xP
x
C
z
P’
O
x
Q’
z
C’
P为Q的投影
zc
P’
Q’
C’
z
在oxz平面上的正投影
在坐标系oxyz中来讨论投影,假设投影平面就是z=0。
(一点透视)
设视点[PRP]C(xc,yc,zc),空间中任一点Q(x,y,z)在
z=0平面上的投影为 P(xp,yp,zp)。设Q、P、C在 oxz 平面
上的正投影为Q’,P’和C’,可得透视投影的计算公式
383
透视投影(Perspectiveprojection)计算公式。
xc x
(xp-xc)/ zc= (x-xc)/(zc-z)
z
整理后便有
xp=xc + (x-xc)zc/(zc-z)
同理可得
yp=yc + (y-yc)zc/(zc-z)
zc
P’
xP
x
Q’
C’
z
 xp  t  x
这两式便是透视投影的计算公式。把空间上任一点(x,y,z)

当xc=0, yc=0时,则有
yp  t  y
t  [0,)

的坐标代入上式便可求出在z=0平面的投影点P(xp,yp)。
z  t( z  z )  z
c
c
 p
384
投影平面是任意平面的情况

透视投影的特征

投影中心与投影平面之间的距离为有限
参数:投影方向,投影面

灭点:不平行于投影平面的平行线,经过透视投影之

后收敛于一点,称为灭点.

在坐标轴上的灭点叫做主灭点。主灭点数和投影
平面切割坐标轴的数量相对应。按照主灭点的个
数,透视投影可分为

一点透视
两点透视
三点透视
由投影平面与主坐标轴
的交点个数决定
 特点:产生近大远小的视觉效果,由它产生的图形深度


感强,看起来更加真实。
主灭点的个数由什么决定?
385
投影平面是任意平面的情况
386
投影平面是任意平面的情况
y
U
z’
y’
o’
x’
N
R
o
x
投影平面的指定
Z
在实际应用时投影平面的位
置要允许改变。为了确定一
个投影平面,先给定一个参
考点R (xr,yr,zr)、投影平
面的法线方向N(xn,yn,zn)和
一个常数d。过点 R 沿N方
向作射线,与投影平面的交
点o’,并且使|o’R|=d。调
整R和N可以很方便的改变投
影平面的位置和方向。
387
首先在投影平面上建立一个坐标系
y
U
z’
o’x’y’z’.并且oz’的方向为投影平面
y’
o’
x’
的法线方向,同时给定一个向量
N
R
U(xu,yu,zu),此向量在投影平面上的
o
x
正投影所指的方向便是o’y’的方向。
这样,对于坐标系(o’x’y’z’)来说,投影平面正好是z’=0
平面,因此可以用透视计算公式或平行计算公式来计算这
两种投影。现在我们只须求出这两个坐标系的转换关系。
388
设(x0,y0,z0)是点o’在坐标系oxyz中的坐标,o’x’,
o’y’和o’z’轴的单位方向向量为(a11,a12,a13)、
(a21,a22,a23)和(a31,a32,a33),那么从坐标系oxyz 到
o’x’y’z’的变换是
x’
y’
z’
a11 a12 a13
a21 a22 a23
a31,a32,a33
[ ] =[
x - x0
y - y0
z - z0
][
]
下面给出计算x0,y0,z0和aij(i,j=1,2,3)的方法。由图可知
x0= xr + dxn/(xn2 + yn2 + zn2)1/2
y0= yr + dyn/(xn2 + yn2 + zn2)1/2
z0= zr + dzn/(xn2 + yn2 + zn2)1/2
389
o’z’轴和N方向一致,故有
(a31,a32,a33)=(xn,yn,zn)/(xn2 + yn2 + zn2)1/2
o’x’轴和向量U×N方向一致,设
i
j
k
U×N = xu
yu
zu = b1i + b2j +b3k
xn
yn
zn
其中i,j和k分别为ox,oy,oz轴的单位方向向量,则
(a11,a12,a13)=(b1,b2,b3)/(b12 + b22 + b32)1/2
390
o’y’轴的单位方向向量应是o’z’和o’x’轴的单位向量的向量积,
因此
(a21,a22,a23))=
(a13a32 - a12a33,a11a33 - a13a31,a12a31 - a11a32)
(4.30)
用式(4.25)至(4.30)可算出式(4.24)中全部常数,因
此在坐标系oxyz中给定的投影方向或视点的坐标都可用式
(4.24)变换到坐标系o’x’y’z’中的量(xd,yd,zd)和
(xc,yc,zc)。
391
观察坐标系中的投影变换(1/15)
• 如何进行投影变换?
观察坐标系
生活中的类比--移动舞台还是移动摄像机
移动舞台
投影(摄像)简单
移动难度大

移动摄像机
移动容易
投影复杂

采用观察坐标系,投影简单
392
观察坐标系中的投影变换(2/15)
– 什么是观察坐标系
• View Reference Coordinate或VRC
• 照相机所在的坐标系
– 如何建立观察坐标系
• 坐标原点----聚焦参考点在底片(投影平面)上
的投影,称为观察参考点VRP(View Reference
Point)
• n轴----照相机镜头方向(投影平面的法向)
• v轴----照相机向上的方向(观察正向)
• u轴----
u  v n
393
观察坐标系中的投影变换(3/15)
394
观察坐标系中的投影变换(4/15)
– 为什么需要观察坐标系
• 简化和加速投影变换
• 投影平面---- n=0
• 投影中心---- (0,0,d)
• 视见体
– 视见体是三维裁剪窗口
– 建立步骤
定义窗口
发出射线
形成观察空间
前后裁剪面
形成视见体
395
观察坐标系中的投影变换(5/15)
– 投影参考点
• PRP:Projection Reference Point
• 透视投影:COP==PRP
• 平行投影:投影方向DOP=窗口中心CW-PRP
396
观察坐标系中的投影变换(6/15)
397
观察坐标系中的投影变换(7/15)
投影参数
参数
作用
投影类型
定义投影是平行投影还是透视投影
观察参考点VRP
在世界坐标系中指定,为观察坐标系原点
观察平面法向VPN
在世界坐标系中指定,为观察坐标的n轴
观察正向UVP
在世界坐标系中指定,确定观察坐标系的v轴
投影参考点PRP
在观察坐标系中指定确定投影中心或投影方向
前裁剪面裁距F
在观察坐标系中指定,n=F为前裁剪面
后B裁剪面裁距
在观察坐标系中指定,n=B为后裁剪面
窗 口 umin 、 umax 、 在观察坐标系的uv平面上指定,确定窗口与视见体
vmin、vmax
398
观察坐标系中的投影变换(8/15)
• 透视投影变换
– 问题----在uvn中,投影平面为n=0,投影中
心为(0,0,d),待投影点为P,求投影点Q
399
观察坐标系中的投影变换(9/15)
– 投影线的参数方程
u  t  u p

v  t  v p
 n  t (n  d )  d
p

– 投影平面方程 n=0
•Q点的坐标
t  [0,)
d
t 
d  nP
uP

uQ  1  (n / d )
P

vP

vQ 
1  ( nP / d )

 nQ  0

400
观察坐标系中的投影变换(10/15)
–投影中心为(0,0,d)时的透视投影变换矩阵
M per
1
0

 0

0
0
0
1
0
0
0
1
0 
d
M per
0
0

0

1

Q  M per  P
401
观察坐标系中的投影变换(11/15)
• 平行投影变换
– 问题----在uvn中,投影平面为n=0,投影方
向为(0,0,-1),待投影点为P,求投影点
Q
402
观察坐标系中的投影变换(12/15)
– 投影线的参数方程
 u  up

 v  vp
n  d  t

t  [0,)
– 投影平面方程 n=0
– Q点的坐标
uQ  u P

 vQ  v P
n 0
 Q
403
观察坐标系中的投影变换(13/15)
– 平行投影变换矩阵
M ort
1
0

0

0
M ort
0 0 0
1 0 0

0 0 0

0 0 1
Q  M ort  P
• 透视投影与平行投影之间的关系
404
观察坐标系中的投影变换(14/15)
• 从世界坐标系到观察坐标系的变换
– 条件
• VRC的坐标原点(观察参考点)VRP
(VRPx ,VRPy,VRPz )
投影平面法向VPN
,,
观察正向VUP
n
u
VPN 记为

 n  VPN  [ n x , n y , n z ]

VUP  VPN 记为

 [u x , u y , u z ]
u 
VUP  VPN

记为

 v  n  u  [v x , v y , v z ]

405
观察坐标系中的投影变换(15/15)
– 结论
u x u y u z
v v v
x
y
z

M WC VRC 
nx n y nz

0 0 0
0 1


0  0

0  0
 
1  0
0
1
0
0
0  VRPx 

0  VRPy 
1  VRPz 

0
1 
406
投影举例(1/5)
• 待投影的单位立方体
缺省投影参数
参数
值
投影类型
平行投影
VRP(WC) (0,0,0)
VPN(WC) (0,0,1)
VUP(WC)
PRP(VRC)
窗口(VRC)
F(VRC)
B(VRC)
(0,1,0)
(0.5,0.5,1)
(0,1,0,1)
正无穷
负无穷
407
投影举例(2/5)
• 透视投影
– 一点透视
参数
值
投影类型
透视投影
VRP(WC) (0,0,0)
VPN(WC) (0,0,1)
VUP(WC) (0,1,0)
PRP(VRC)(0.5,0.5,4)
窗口(VRC)(-0.5,1.5,-0.5,1.5)
408
投影举例(2/5)

透视投影

一点透视
参数
值
投影类型
透视投影
VRP(WC) (0,0,0)
VPN(WC) (0,0,1)
VUP(WC) (0,1,0)
PRP(VRC)(2.0,2.0,4.0)
窗口(VRC)(-0.5,1.5,-0.5,1.5)
透视投影坐标值
顶点
1(-3/2,-3/2,0)
1(0,0,1)
2(2(1,0,1)
3/2,-3/2,0 )
3(3(1,1,1)
3/2,3/2,0 )
4(4(0,1,1)
-3/2,3/2,0 )
409
投影举例(3/5)
– 两点透视
参数
值
投影类型
透视投影
VRP(WC) (0,0,0)
VPN(WC) (1,0,1)
VUP(WC) (0,1,0)
PRP(VRC) (0.5,0.5,4)
窗口(VRC) (-1.5,1.5, -1.5, 1.5)
410
参数
值
投影类型
透视投影
VRP(WC) (0,0,0)
VPN(WC) (1,0,1)
VUP(WC) (1,1,0)
PRP(VRC) (0.5,0.5,4)
窗口(VRC) (-1.5,1.5, -1.5, 1.5)
411
投影举例(4/5)
• 平行投影
参数
投影类型
VRP(WC)
VPN(WC)
VUP(WC)
PRP(VRC)
窗口(VRC)
参数
投影类型
VRP(WC)
VPN(WC)
VUP(WC)
PRP(VRC)
窗口(VRC)
值
平行投影
(0,0,0)
(0,0,1)
(0,1,0)
(0.5,0.5,1)
(-0.5,1.5,0.5,1.5)
值
平行投影
(0,0,0)
(1,1,1)
(0,1,0)
(0.5,0.5,2)
(-0.5,1.5,0.5,1.5)
412
投影举例(5/5)
• 前、后裁剪面的影响
参数
值
投影类型
透视投影
VRP(WC) (0,0,0)
VPN(WC) (0,0,1)
VUP(WC) (0,1,0)
PRP(VRC) (0.5,0.5,2)
窗口(VRC) (-0.5,1.5,-0.5,1.5)
F(VRC)
1.2
B(VRC)
0.2
413
三维图形的显示流程图(1/14)
• 显示流程图
– 观察变换:从世界坐标系到观察坐标系的变
换
414
三维图形的显示流程图(2/14)
• 模型变换
–模型坐标系
• Modeling Coordinate
• 物体的局部坐标系
• 在模型坐标系中物体的表示简单
415
三维图形的显示流程图(3/14)
– 模型变换
• Modeling Transformation
• 将物体从本身的模型坐标系变换到上层物体的模
型坐标系(或世界坐标系)的几何变换
• 模型变换是构造复杂物体的方法
• 例子:
模型变换1
416
三维图形的显示流程图(4/14)
• 何时裁剪
– 投影之前裁剪----三维裁剪
• 优点
– 只对可见的物体进行投影变换
• 缺点
– 三维裁剪相对复杂
– 投影之后裁剪----二维裁剪
• 优点
– 二维裁剪相对容易
• 缺点
– 需要对所有的物体进行投影变换
417
三维图形的显示流程图(5/14)
–采用二维裁剪的三维图形显示流程图
–在投影之前裁剪的理由
• 三维物体的表面通常被离散表示成多边形或折线,而对这
类简单图元,三维裁剪同样比较简单。
• 三维图形在显示过程中需要被消隐,做这个工作要有图形
的深度信息,所以必须在投影之前完成
418
三维图形的显示流程图(6/14)
• 规范视见体
– 平行投影的规范视见体
• 半立方体
 u  1, u  1

 v  1, v  1
n  0, n  1

透视投影的规范视见体
四棱台
 u  n, u   n

 v  n, v   n
 n   n , n  1
min

419
三维图形的显示流程图(7/14)
– 为什么引入规范视见体
• 简化投影
• 简化裁剪
–规范化变换
• 将任意视见体变换成规范视见体的变换
–规范投影坐标(三维屏幕坐标 )
• 经规范化的观察坐标系
420
三维图形的显示流程图(8/14)
– 采用规范视见体的三维图形显示流程图
421
三维图形的显示流程图(9/14)
• 平行投影视见体的规范化
– 将任意的平行投影视见体变换为规范平行投
影视见体
– 方法:变换的分解与合成
– 步骤
– 结果
N par  S par  Tpar 2  SH par  Tpar1
422
三维图形的显示流程图(10/14)
423
三维图形的显示流程图(11/14)
• 透视投影视见体的规范化
– 将任意的透视投影视见体变换为规范透视投
影视见体
– 方法:变换的分解与合成
– 步骤
– 结果
N per  S per  SH per  Tper
424
三维图形的显示流程图(12/14)
425
三维图形的显示流程图(13/14)
• 规范视见体之间的变换
– 将透视投影的规范视见体变换为平行投影的
规范视见体
1
0

M 
0

0
0
1
0
0
1
0
1  nmin
0
1


nmin 

1  nmin 
0 
0
0
为什么
关于长方体的裁剪较关于正四棱台的裁剪简单。
平行投影较透视投影简单。
透视投影与平行投影都采用同一套裁剪与投影程序,处理一致,便
于用硬件实现。
426
三维图形的显示流程图(14/14)
– 将视见体变换结合到透视投影的规范化变换
矩阵中
N per  M  N per  M  S per  SHper  Tper
– 采用视见体变换的三维图形显示流程图
427
三维裁剪(1/2)
• 三维裁剪的两种方法
–将齐次坐标转换为三维坐标,在三维空间关
于视见体裁剪
• 优点:三维裁剪相对容易
• 缺点:需要将齐次坐标转换为三维坐标
–直接在四维齐次坐标空间中进行裁剪
• 优点:
– 不需要将齐次坐标转换为三维坐标
–有理曲线曲面可能直接用齐次坐标来表示,对它们的
裁剪只能在齐次坐标空间中进行
• 缺点:四维裁剪相对复杂
428
三维裁剪(2/2)
• 关于规范视见体的裁剪
– 直线段裁剪的Cohen_Sutherland算法、梁
_Barskey算法的直接推广
– 多边形裁剪的Sutherland_Hodgman算法的直
接推广
• 齐次坐标空间中的裁剪
– 四维裁剪体的定义
429
图形显示过程小结(1/2)
• 对应于三维裁剪的实现过程
1、将三维坐标扩展为齐项坐标,(x,y,z)(x,y,z,1);
2、进行模型变换;
3、进行观察变换;
4、进行视见体的规范化变换Npar或Nper;
5、除以h返回三维空间(有些情况下,h保持为1,所
以不必做除法运算);
6、关于规范视见体进行裁剪;
7、将三维坐标扩展为齐项坐标;
8、进行投影变换Mort或Mper;
9、进行窗口至视区的变换;
10、除以h返回二维设备坐标系 ;
11、扫描转换(显示)。
430
图形显示过程小结(2/2)
对应齐次坐标空间裁剪的实现过程
1、将三维坐标扩展为齐次坐标(对于直接用齐次坐标
表示的图形不需要进行这一步);
2、进行模型变换;
3、进行观察变换;
 ;
4、进行视见体的规范化变换Npar或 N per
5、在齐项坐标空间中关于裁剪窗口裁剪;
6、进行平行投影变换Mort。
7、进行窗口至视区的变换。
8、除以h返回二维设备坐标系。
9、扫描转换(显示)。
431
变换与投影题解
1. 在坐标系OXY中,求关于对称轴y=x+1的对称变换,并写出其在
齐次坐标下的矩阵表示。
步骤:
(1)
(2)
(3)
(4)
(5)
作平移变换T(0,–1), 是对称轴y=x+1变为y=x
作旋转变换R(-π/4),是对称轴y=x变为y=0
作关于对称轴 y=0的对称变换Ax;
作旋转变换R(π/4);
作平移变换T(0,1),恢复原对称轴位置;
432
变换与投影题解
•
•
总的变换为
M=T(0, 1)R(π/4) Ax R(-π/4)T(0,-1)=


1 0 0 
0 1 1  


0 0 1 


 2
2
2 

0

2
2
 1 0 0  2
2
2
2




0 0  1 0  

 2
2
2
0
0 1 0 0 1  0




2 
0
2
 1 0 0  0 1  1
2 
0 0 1  1  1 0 1 

2
0 1 0 0 1  0 0 1 


433
在观察坐标系oxyz中,选定投影平面为z=0,投影参考点为
D(0,0,d),待投影的三维空间的点为P(xp.yp,zp),试求出P点在投影
平面上的投影点Q(xq,yq,zq),并在齐次坐标系下,写出其透视投影
变换矩阵。
•
2.
•
解答: (1) 过P与投影中心的直线的参数方程为
x  t  xp

y  t  yp
 z  d  t (Z  d )
p

•
投影平面的方程为
(xp.0,zp)
X
t  [,)
(0,0,d)
Z=0
434
(2)联立两方程得
d
t
zp  d
代入直线方程,求得Q的坐标
xp
1  dp
yP
z
1
zp
d
0
(3)从而透视投影变换的矩阵为
1
0
0
1 0
0 1

0
0

M per  
0 0
0
0


1
0 0  d 1 
435
即:
 x '  1
 y ' 0
 
 z '  0
  
1  0
xp
1  dp
yP
z
1
0
0
1
0
0
0
0
 d1
0  x   x
 y  y
0
   
0   z  0
  
1  1  
z
d





 1
若本题采用左手坐标系,投影参考点为D(0,0,-d),则
投影矩阵如何?
Z
zp
d
(xp.0,zp)
0
1
0
X
(0,0-d)
436

similar documents