**每周一点图形学重启，不弃坑。。。。。。** 　　几年之后的最新：多边形图像转换补完 　　

举例：显卡有2MB显存，当分辨率是1024x768时，可支持的色彩数又是多少？
2MB=2x1024x1024=2097152(字节)
1024x768=786432(个像素)
每个像素如果需要3个字节表示，将超过2MB显存，最多只需要2个字节表示，故只能支持64K色彩数。

题目：显示颜色64K，分辨率为1024*1024的显示器，至少需要的帧缓存容量为©
A.1MB B.3MB C.2MB D.512KB

• 解：显示颜色64K，故每个像素需要2个字节表示。1024x1024=1048576(个像素)，1048576x2=2097152(字节)
  2097152/1024/1024=2MB

二维图形变换

两大基本工具：向量分析 图形变换

向量分析

向量线性组合
w=a1v1+a2v2+…+anvn

1. 仿射组合
   a1+a2+…+am=1
2. 凸组合
   a1+a2+…+am=1
   i=1,2,…,m ai≥0

• 点积
  a=(a1,a2) b=(b1,b2)
  a·b=a1b1+a2b2
  点积最重要的应用是计算两个向量的夹角或者两条直线的夹角。
  b·c=|b||c|cosθ
  cosθ=(b·c)/(|b||c|)=b的单位向量·c的单位向量
  b·c > 0 θ < 90°
  b·c = 0 θ = 90°
  b·c < 0 θ > 90°

如何设计一个算法描述任意两篇新闻的相似性？
用一个向量来描述一篇新闻。当夹角的余弦接近1时，相似，归为一类。夹角余弦越小，两条新闻越不相关。

• 叉积
  

1. axb和a、b两个向量都正交
2. axb的长度等于由a和b决定的平行四边形面积
   axb=|a||b|sinθ
   利用叉积求平面的法向量

图形变换

将程序中用于描述对象几何信息的数值和那些用于表示对象中大小和位置的数值区分开来。前者通常被看作一个建模（modeling）的任务，后者是一个观察（viewing）的任务。
图形显示的过程是几何（对象）模型在不同坐标系之间的映射变换。

分类

世界坐标系
用最适合手中问题的坐标系来描述对象，并且可以自动的缩放和平移图形，使得其能正确地在屏幕窗口中显示。
建模坐标系（局部坐标系）
建模坐标系独立于世界坐标系来定义物体的几何特性
观察坐标系
观察坐标系主要用于从观察者的角度对整个世界坐标系内的对象进行重新定位和描述。依据观察窗口的方向和形状在世界坐标系中定义的坐标系成为观察坐标系。观察坐标系用于指定图形的输出范围。
二维观察变换的一般方法是在世界坐标系中指定一个观察坐标系统，以该系统为参考通过选定方向和位置来指定矩形剪裁窗口。
设备坐标系
适合特定输出设备输出对象的坐标系。比如屏幕坐标系。
在多数情况下，对于每一个具体的显示设备，都有一个单独的坐标系统。设备坐标是整数。
规范化坐标系
规范化坐标系独立于设备，能容易地转变为设备坐标系，是一个中间坐标系。
为使图形软件能在不同的设备之间移植，采用规范化坐标，坐标轴取值范围是0-1。

二维变换

变换图形就是要变换图形的几何关系，即改变顶点的坐标；同时，保持图形的原拓扑关系不变。
仿射变换（Affine Transformation或Affine Map）是一种二维坐标到二维坐标之间的线性变换。
（1）“平直性”。即：直线经过变换之后依然是直线
（2）“平行性”。即：平行线依然是平行线，且直线上
点的位置顺序不变）

齐次坐标
如n维向量（p1,p2,…,pn）表示为（hp1,hp2,…,hpn,h），其中h称为哑坐标。
普通坐标与齐次坐标的关系为“一对多”：
普通坐标×h→齐次坐标
齐次坐标÷h→普通坐标
当h = 1时产生的齐次坐标称为“规格化坐标”，因为前n个
坐标就是普通坐标系下的n维坐标

• 基本几何变换

1. 平移变换

1
2

x*=x+Tx
y*=y+Ty

2. 比例变换

1
2

x*=x·Sx
y*=y·Sy

3. 对称变换（反射变换/镜像变换）
4. 旋转变换

1
2
3
4

x*=rcos(α+θ)=rcosαcosθ-rsinαsinθ
y*=rsin(α+θ)=rcosasinθ+rsinαcosθ
x*=xcosθ-ysinθ
y*=xsinθ+ycosθ

5. 错切变换

1
2

x*=x+cy
y*=bx+y

坐标系变换
1.平移变换
2.旋转变换
相对任意参考点的二维几何变换
比例、旋转变换等均与参考点相关。如要对某个参考点（xf，yf）作二维几何变换，其变换过程如下：
a、将固定点移至坐标原点，此时进行平移变换
b、针对原点进行二维几何变换
c、进行反平移，将固定点又移回到原来的位置
二维变换矩阵

窗口视区变换

窗口：世界坐标系中药显示的区域成为窗口。
视区：窗口映射到显示器（设备）上的区域称为视区。
观察变换（Viewing Transformation），将窗口到视区的变换处理。

窗口到视区的映射是基于一个等式，即对每一个在世界坐标下的点（x,y），产生屏幕坐标系中的一个点（sx,sy）。

1
2

sx=A*x+C
sy=B*y+D

A、B、C、D为常数

三维图形几何变换

三维空间中某点的变换可以表示成点的齐次坐标与四阶的三维变换矩阵相乘：

基本变换

平移变换

比例变换

局部比例变换

整体比例变换

旋转变换

绕z轴旋转θ

绕x轴旋转

绕y轴旋转

对称变换

关于坐标平面的对称

xoy:
[x’ y’ z’ 1] = [x y -z 1]
yoz:
[x’ y’ z’ 1] = [-x y z 1]
zox:
[x’ y’ z’ 1] = [x -y z 1]

关于坐标轴对称

x:
[x’ y’ z’ 1] = [x -y -z 1]
y:
[x’ y’ z’ 1] = [-x y -z 1]
z:
[x’ y’ z’ 1] = [-x -y z 1]

投影变换

在二维平面上显示三维物体的解决方法：投影变换。

正投影根据投影面与坐标轴的夹角又可分为两类：三视图和
正轴侧图。
当投影面与某一坐标轴垂直时，得到的投影为三视图，这时
投影方向与这个坐标轴的方向一致；否则，得到的投影为正
轴侧图。

三视图的计算

具体计算步骤如下：
a、确定三维物体上各点的位置坐标；
b、引入齐次坐标，求出所作变换相应的变换矩阵；
c、将所作变换用矩阵表示，通过运算求得三维物
体上各点经变换后的点坐标值；
d、由变换后得到的二维点绘出三维物体投影后的三视图

主视图

投影变换矩阵：[x’ y’ z’ 1] = [x 0 z 1]

俯视图

投影变换矩阵：[x’ y’ z’ 1] = [x y 0 1]
为了使俯视图与主视图都画在一个平面内，就要使H面绕x轴
顺时针转90°，即应有一个旋转变换。为了使主视图和俯视图有一定的间距，还要使H面沿z方向平移一段距离-z₀，有一个平移矩阵。
所以，最终俯视图投影变换矩阵：
[x’ y’ z’ 1] = [x y -(y+z₀） 1]

侧视图

为了使侧视图与主视图也在一个平面内，就要使W面绕z轴正
转90°，有一个旋转矩阵。为使主视图和侧视图有一定的间距，还要使W面沿负x方向平移一段距离-x₀，有一个平移矩阵。
所以，最终侧视图投影变换矩阵：
[x’ y’ z’ 1] = [-(y+z₀) 0 z 1]

三个视图中的y’均为0，表明三个视图均落在xoz面上。

正轴测图

正轴测有等轴测、正二测和正三测三种：
当投影面与三个坐标轴之间的夹角都相等时为等轴测
当投影面与两个坐标轴之间的夹角相等时为正二测
当投影面与三个坐标轴之间的夹角都不相等时为正三测
变换矩阵为：

1
2
3

x*=xcosγ-ysinγ
y*=0
z*=-xsinγsinα-ycosγsina+zcosα

透视投影

其中的[p,q,r]能产生透视变换的效果

一点透视

灭点：聚焦的那个点

多点透视

多个灭点

构造二点透视的一般步骤如下：
（1）将物体平移到适当位置l、m、n
（2）将物体绕y轴旋转θ角
（3）进行透视变换
（4）最后向xoy面做正投影，即得二点透视图

构造三点透视的一般步骤如下：
（1）将物体平移到适当位置
（2）将物体绕y轴旋转θ角
（3）再绕x轴旋转α角
（4）进行透视变换
（5）最后向xoy面做正投影，即得三点透视图

光栅图形学算法

研究内容

• 直线段的扫描转换算法
• 多边形的扫描转换与区域填充算法
• 裁剪算法
• 反走样算法
• 消隐算法

直线段的扫描转换算法

P₀（x₀,y₀） P₁(x₁,y₁)
y=kx+b
k=(y₁-y_o)/(x₁-x₀) (x₁≠x₀)
假设x已知，即从x的起点xo开始，沿x方向前进一个像素（步长=1），可以计算出相应的y值。因为像素的坐标是整数，所以y值要进行取整处理。
如何把数学上的一个点扫描转换一个屏幕像素点？
如：P（1.7, 0.8）—(取整)—>P(1, 0)
P(1.7, 0.8) -(+0.5)-> p(2.2, 1.3)
P(2.2, 1.3) -(取整)-> p(2, 1)
为提高效率，减小计算量，要把乘法消掉。

直线绘制的三个著名的常用算法

1. 数值微分法（DDA）
2. 中点画线法
3. Bresenham算法

数值微分DDA（Digital Differential Analyzer）

引进图形学中一个重要思想——增量思想
直线斜率小于1：
x=x+1
y=y+k
(注意y+0.5化为整数)
直线斜率大于1：
x=x+1/k
y=y+1
（注意x+0.5化为整数）

DDA算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

void CDrawLinesDlg::DDALine(int iBeginX, int iBeginY, int iEndX, int iEndY, COLORREF col)
{
	CDC *pDC = GetDC();
	pDC->TextOut(450, 18, _T("DDA画线成功！"));

	float x, y, dx, dy, k, r;
	float xm, ym;
	dx = iEndX - iBeginX;
	dy = iEndY - iBeginY;
	k = dy / dx;
	r = dx / dy;//r为斜率倒数
	x = iEndX;
	y = iEndY;
	xm = iBeginX;
	ym = iBeginY;

	if (abs(dx) > abs(dy))//斜率小于1
	{
		if (iBeginX <= iEndX)
		{
			x = iBeginX;
			xm = iEndX;
			y = iBeginY;
			ym = iEndY;
		}
		while(x <= xm)
		{
			y = y + k;
			pDC->SetPixel(x, (int)(y + 0.5), col);
			++x;
		}
	}
	else//斜率大于1
	{
		if (iBeginY <= iEndY)
		{
			x = iBeginX;
			xm = iEndX;
			y = iBeginY;
			ym = iEndY;
		}
		while (y <= ym)
		{
			x = x + r;
			pDC->SetPixel((int)(x + 0.5), y, col);
			++y;
		}
	}
}

中点画线法

核心思想：考虑斜率小于1，若x每次+1，y值要么+1，要么不+1。
直线一般式方程；Ax+By+C=0
设y+1和y之间的中点M，把M带入方程。d=Ax+By+C
d < 0 M在直线下方 选上面那个点(y+1)
d > 0 M在直线上方 选下面那个点(y)

中点画线法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

void CDrawLinesDlg::MidLine(int iBeginX, int iBeginY, int iEndX, int iEndY, COLORREF col)
{
	CDC  *pDc = GetDC();
	pDc->TextOut(450, 18, _T("中点画线法成功！"));
	int  d1, d2, d;
	int num = 0;
	int p, p1, q, q1;

	int x = iBeginX;
	int y = iBeginY;
	int a = iBeginY - iEndY;
	int b = iEndX - iEndY;
	int dx = abs(iBeginX - iEndX);
	int dy = abs(iBeginY - iEndY);

	//第二、四象限
	if (((iEndX - iBeginX >= 0) && (iEndY - iBeginY<0)) || ((iEndX - iBeginX <= 0) && (iEndY - iBeginY>0)))
	{
		//从第四象限到第二象限
		if ((iEndX - iBeginX <= 0) && (iEndY - iBeginY > 0))
		{
			a = -a;
			b = -b;
			x = iEndX;
			y = iEndY;
		}
		//斜率小于1
		if (dx >= dy)
		{
			num = dx;//以x轴为基准
			p = 1;
			p1 = 0;
			q = 1;
			q1 = -1;
			d = 2 * a - b;//初始值
			d2 = 2 * a;//当大于0时的增量
			d1 = 2 * (a - b);//当小于0时的增量
		}
		else
		{
			num = dy;//以y轴为基准
			p = 1;
			p1 = -1;
			q = 0;
			q1 = -1;
			d = a - 2 * b;
			d1 = -(2 * b);
			d2 = 2 * (a - b);
		}
	}
	else//第一、三象限
	{
		if ((iEndX - iBeginX <= 0) && (iEndY - iBeginY < 0))
		{
			a = -a;
			b = -b;
			x = iEndX;
			y = iEndY;
		}
		if (dx >= dy)
		{
			num = dx;
			p = 1;
			p1 = 1;
			q = 1;
			q1 = 0;
			d = 2 * a + b;
			d1 = 2 * a;
			d2 = 2 * (a + b);
		}
		else
		{
			num = dy;
			p = 0;
			p1 = 1;
			q = 1;
			q1 = 1;
			d = a + 2 * b;
			d2 = 2 * b;
			d1 = 2 * (a + b);
		}
	}
	pDc->SetPixel(x, y, col);

	for (int i = 0; i <= num; ++i)
	{
		if (d < 0)//d(new)=d(old)+A+B	选Pu(上面一点)
		{
			x += p;
			y += p1;
			d += d2;
		}
		else//d(new)=d(old)+A 选Pd(下面一点)
		{
			x += q;
			y += q1;
			d += d1;
		}
		pDc->SetPixel(x, y, col);
	}
}

Bresenham算法

Bresenham算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

void CDrawLinesDlg::BresenhamLine(int iBeginX, int iBeginY, int iEndX, int iEndY, COLORREF col)
{
	CDC *pDC = GetDC();
	pDC->TextOut(450, 18, _T("Bresenham画线成功！"));

	int dx = abs(iEndX - iBeginX);
	int dy = abs(iEndY - iBeginY);
	int x = iBeginX;
	int y = iBeginY;
	int stepX = 1;
	int stepY = 1;
	if (iBeginX > iEndX)  //从右向左画  
	{
		stepX = -1;
	}
	if (iBeginY > iEndY)//从下往上画
	{
		stepY = -1;
	}

	if (dx > dy)  //斜率大于1
	{
		int e = dy * 2 - dx;
		for (int i = 0; i <= dx; i++)
		{
			pDC->SetPixel(x, y, col);
			x += stepX;
			e += dy;
			if (e >= 0)
			{
				y += stepY;
				e -= dx;
			}
		}
	}
	else//斜率小于1
	{
		int e = 2 * dx - dy;
		for (int i = 0; i <= dy; i++)
		{
			pDC->SetPixel(x, y, col);
			y += stepY;
			e += dx;
			if (e >= 0)
			{
				x += stepX;
				e -= dy;
			}
		}
	}
}

三者区别：DDA是浮点数加法，中点画线是整数加法，Bresenham不判断大小，是判断符号。

多边形扫描转换

多边形的扫描转换和区域填充这个问题是怎么样在离散的像素集上表示一个连续的二维图形
多边形有两种重要的表示方法：顶点表示和点阵表示

顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换
但由于它没有明确指出哪些像素在多边形内，故不能直接用于面着色

点阵表示是用位于多边形内的像素集合来刻画多边形。这种表示丢失了许多几何信息（如边界、顶点等），但它却是光栅显示系统显示时所需的表示形式。

涉及两个问题：
1、 如果知道边界，能否求出哪些像素在多边形内？
2、 如果知道多边形内部的像素，反过来如何求多边形的边界？——得不到，不是计算机图形学问题，属于图像识别领域

光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描转换。
多边形分为凸多边形、凹多边形、含内环的多边形等
凸多边形：任意两顶点间的连线均在多边形内
凹多边形：任意两顶点间的连线有不在多边形内
含内环的多边形：多边形内包含多边形

现在的问题：知道多边形的边界，如何找到多边形内部的点，即把多边形内部填上颜色

X-扫描线算法

基本思想：按照扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作
区间的端点可以通过计算扫描线与多边形边界线的交点获得
步骤：
1、 确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）
2、 从y = ymin到y = ymax，每次用一条扫描线进行填充
3、 对一条扫描线填充的过程分为四步：
a. 求交：计算扫描线与多边形各边的交点
b. 排序：把所有交点按递增顺序进行排序
c. 交点配对：第一个与第二个，第三个与第四个
d. 区间填色：把这些相交区间内的像素置成不同于背景色的填充色

当扫描线与多边形顶点相交时，交点的取舍问题（交点的个数应保证为偶数个）
解决方案：
1、 若共享顶点的两条边分别落在扫描线的两边，交点只算一个
2、 若共享顶点的两条边在扫描线的同一边，这时交点作为零个或两个
检查共享顶点的两条边的另外两个端点的y值，按这两个y值中大于交点y值的个数来决定交点数
为了计算每条扫描线与多边形各边的交点，最简单的方法是把多边形的所有边放在一个表中。在处理每条扫描线时，按顺序从表中取出所有的边，分别与扫描线求交。
该算法效率低。求交计算量很大。但排序、配对、填色总是要的。

改进的x扫描线算法

扫描转换算法重要意义是提出了图形学里两个重要的思想：
1、 扫描线
2、 增量思想

三方面改进：
1、 在处理一条扫描线时，仅对与它相交的多边形的边（有效边）进行求交运算
2、 考虑扫描线的连贯性，即当前扫描线与各边的交点顺序与下一条扫描线与各边的交点顺序很可能相同或非常相似
3、 最后考虑多边形的连贯性，即当某条边与当前扫描线相交时，它很可能也与下一条扫描线相交

为了避免求交运算，需引入一套特殊的数据结构：
1、 活性边表（AET）：把与当前扫描线相交的边称为活性边，并把他们按与扫描线交点x坐标递增的顺序存放在一个链表中。
2、结点内容：
x：当前扫描线与边的交点坐标
△x：从当前扫描线到下一条扫描线间x的增量
ymax：该边所交的最高扫描线的坐标值ymax
next：指向下一条边的指针

随着扫描线的移动，扫描线与多边形的交点和上一次交点相关：
设边的直线斜率为k
k = △y/△x = (yi+1 - yi) / (xi+1 - xi)
xi+1 - xi = 1/k
xi+1 = xi + 1/k
(1/k即为增量)
即△x = 1/k

另外需要知道一条边何时不再与下一条扫描线相交，以便及时把它从有效边表中删除出去，避免下一步无谓计算。

为了方便活性边表的建立与更新，需构造一个新边表（NET），用来存放多边形的边的信息，步骤：
1、构造一个纵向链表，链表长度为多边形所占有的最大扫描线数，链表的每个节点，称为一个吊桶，对应多边形覆盖的每一条扫描线
2、NET挂在与该边低端y值相同的扫描线桶中。即存放在该扫描线第一次出现的边
ymax：该边的ymax
xmin：该边较低点的x坐标值xmin
1/k：该边的斜率1/k
next：指向下一条具有相同较低端y坐标的边的指针
每做一次新的扫描线时，要对已有的边进行三个处理：
1、是否被去除掉
2、如果不被去除，第二就要对它的数据进行更新。即更新它的x值，x+ 1/k
3、看有没有新的边进来，新的边在NET里，可插入排序插进来
该算法避免了求交运算。
缺点：无法实现对未知边界的区域填充。

边缘填充算法

基本思想：按任意顺序处理多边形的每条边。在处理每条边时，首先求出该边与扫描线的交点，然后将每一条扫描线上交点右方的所有像素取补。多边形的所有边处理完毕后，填充即完成。
算法简单，但对复杂模型，每一像素可能被访问多次。输入和输出量比有效边算法大得多。

为了减少边缘填充法访问像素的次数，可采用栅栏填充算法。

栅栏填充算法

栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。在处理每条边与扫描线的交点时，将交点与栅栏之间的像素取补。

边界标志算法

帧缓冲器中对多边形的每条边进行直线扫描转换，即对多边形边界所经过的像素打上标志。
然后再采用和扫描线算法类似的方法将位于多边形内的各个区段着上所需颜色。
由于边界标志算法不必建立维护边表以及对它进行排序，所以边界标志算法更适合硬件实现，这时它的执行速度比有序边表算法快一至两个数量级。

区域填充算法

区域——指已经表示成点阵形式的填充图形，是像素的集合。
区域填充是指将区域内的一点（常称种子点）赋予给定颜色，然后将这种颜色扩展到整个区域内的过程。
区域可采用内点表示和边界表示两种表示形式。
区域填充算法要求区域是连通的。
区域可分为4向连通区域（上下左右）和8向连通区域（上下左右、左上、左下、右上、右下）。

简单四连通种子填充算法（区域填充递归算法）

原理：假设在多边形区域内部有一像素已知，由此出发找到区域内的所有像素，用一定的颜色或灰度来填充。
假设区域采用边界定义，即区域边界上所有像素均具有某个特定值，区域内部所有像素均不取这一特定值，而边界外的像素则可具有与边界相同的值。
使用栈结构来实现简单的种子填充算法：
种子像素入栈，当栈非空时重复以下操作：
1、 栈顶像素出栈
2、 将出栈像素置成要填充色
3、 按左、上、右、下顺序检查与栈像素相邻 的四个像素，若其中某个像素不在边界且未置成填充色，则把该像素入栈

不足：
1、 有些像素入栈多次，降低算法效率；栈结构占空间
2、 递归执行，算法简单，但效率不高。区域内每一像素都引进一次递归，进/出栈，费时费内存
3、 改进算法，减少递归次数，提高效率
可采用区域填充的扫描线算法

多边形的扫描转换与区域填充算法小结

• 基本思想不同
  多边形扫描转换是指将多边形的顶点表示转化为点阵表示
  区域填充只改变区域的填充颜色，不改变区域表示方法

• 基本条件不同
  在区域填充算法中，要求给定区域内一点作为种子点，然后从这一点根据连通性将新的颜色扩散到整个区域
  扫描转换多边形是从多边形的边界（顶点）信息出发，利用多种形式的连贯性进行填充的
  烧苗转换区域填充的核心是知道多边形的边界，要得到多边形内部的像素集，有多种方法。其中扫描线算法是利用一套特殊的数据结构，避免求交，然后一条条扫描线确定。
  区域填充条件更强一些，不但知道边界，而且还知道区域内的一点，可以利用四连通或八连通区域不断往外扩展。

填充一个定义的区域的选择包括：
选择实区域颜色或图案填充方式
选择某种颜色和图案

这些填充选择可应用于多边形区域或用曲线边界定义的区域；此外，区域可用多种画笔、颜色和透明度参数来绘制。

反走样

以上待填坑

裁剪算法

使用计算机处理图形信息时，计算机内部存储的图像往往比较大，而屏幕显示的只是图形的一部分。
因此需要确定图形哪些部分落在显示区之内，哪些落在显示区之外。这个选择的过程称为裁剪。
最简单的裁剪方法是把各种图形扫描转换为点之后，再判断点是否在窗口内。

点的裁剪

对于任意一点P(x, y)
若满足下列两个不等式：
x_left ≤ x ≤ x_right
y_bottom ≤ y ≤ y_top
则点P在矩形窗口内；否则在矩形窗口外
但判断图形中每个点是否在窗口内，太费时，一般不可取

直线段的裁剪

直线段裁剪算法是复杂图形裁剪的基础
直线段和剪裁窗口的可能关系：

• 完全落在窗口内
• 完全落在窗口外
• 与窗口边界相交
  要裁剪一条直线段，首先要判断：
  （1）它是否完全落在裁剪窗口内？
  （2）它是否完全在窗口外？
  （3）如果不满足以上两个条件，则计算它与一个或多个裁剪边界的交点
  常用的裁剪算法有三种：Cohen-Sutherland、中点分割法、Liang-Barsky裁剪算法

Cohen-Sutherland算法

本算法又称为编码裁剪算法，基本思想：

• 若点p1和p2完全在裁剪窗口内
  “简取”之
• 若点p1(x1, y1)和p2(x2, y2)均在窗口外，且满足下列四个条件之一：
  x₁ < x_left 且 x₂ < x_left
  x₁ > x_right 且 x₂ > x_right
  y₁ < y_bottom 且 y₂ < y_bottom
  y₁ < y_top 且 y₂ < y_top

这四种类型的直线，“简弃”之

• 既不满足“简取”也不满足“简弃”
  需要对直线段按交点进行分段，分段后判断直线是“简取”还是“简弃”
  每条线段的端点都赋以四位二进制码D3D2D1D0，编码规则如下：
  若x < x_left ，则D₀=1，否则为0
  若x > x_right ，则D₁=1，否则为0
  若y < y_bottom ，则D₂=1，否则为0
  若y < y_top ，则D₃=1，否则为0

窗口及其延长线构成了9个区域。根据编码规则：
D₀对应窗口左边界
D₁对应窗口右边界
D₂对应窗口下边界
D₃对应窗口上边界

裁剪一条线段时，先求出端点p1和p2的编码code1和code2，然后进行二进制“或”运算和“与”运算。
（1）若code1|code2=0，对直线段简取之
（2）若code1&code2≠0，对直线段简弃之
（3）若上述两条件均不成立
需求出直线段与窗口边界的交点在交点处把线段一分为二

比较适合两种情况：一是大部分线段完全可见；二是大部分线段完全不可见

存在的问题：

或：0001 | 0100 = 0101
与：0001 & 0100 = 0000
最坏情况下，被裁剪线段与窗口4条边计算交点，然后所得的裁剪结果却可能是全部舍弃。

中点分割算法

和Cohen-Sutherland算法一样，首先对直线段的端点进行编码。
把线段和窗口的关系分成三种情况：

1. 完全在窗口内
2. 完全在窗口外
3. 和窗口有交点

核心思想：通过二分逼近来确定直线段与窗口的交点。
注意：1. 若中点不在窗口内，则把中点和离窗口边界最远点构成的线段丢掉，以线段上的另一点和该中点再构成线段求其中点。

2. 如中点再窗口内，则又以中点和最远点构成线段，并求其中点，直到中点与窗口边界的坐标值在规定的误差范围内相等。

中点分割算法会不会无限循环二分下去？
不会。因为屏幕像素有限。

假如屏幕分辨率是1024*1024，请问被裁减线段最多被分割几次？
10次。

Liang-Barsky算法

主要思想：
（1）用参数方程表示一条直线

x = x1 + u · (x2 - x1) = x1 + △x · u
y = y1 + u · (y2 - y1) = y1 + △y · u
(0 ≤ u ≤ 1)

（2）把被裁剪的红色直线段看成是一条有方向的线段，把窗口的四条边分成两类：
入边和出边
裁剪结果的线段起点是直线和两条入边的交点以及始端点三个点里最前面的一个点，即参数u最大的那个点；
裁剪线段的终点是和两条出边的交点以及端点最后面的一个点，取参数u最小的那个点。

即取图中的绿点。

注意，当u从负无穷到正无穷遍历直线时，首先对裁剪窗口的两条边界直线（下边和左边）从外面向里面移动，再对裁剪窗口两条边界直线（上边和右边）从里面向外面移动。

如果用u1, u2分别表示线段（u1 ≤ u2）可见部分的开始和结束
u1 = max(0, u1, ub)
u2 = min(1, ut, ur)

若窗口如下

x_left ≤ x1 + u · △x ≤ x_right
y_bottom ≤ y1 + u · △y ≤ y_top

简单的推导变形后：

（1）分析Pk = 0的情况
若P1 = P2 = 0

平行于y轴

若P3 = P4 = 0

平行于x轴

任何平行于窗口某边界的直线，其Pk=0

如果还满足qk < 0

则线段完全在边界外，应舍弃

如果qk ≥ 0 ，则进一步判断

(2)当pk ≠ 0 时：
当pk < 0时
线段从裁剪边界延长线的外部延伸到内部，是入边交点
当pk > 0时
线段从裁剪边界延长线的内部延伸到外部，是出边交点

线段和窗口边界一共有四个交点，根据pk的符号，就知道哪两个是入交点，哪两个是出交点

当pk < 0时：对应入边交点
当pk > 0时：对应出边交点

一共四个u值，再叫上u=0、u=1两个端点值，总共六个值

把pk < 0的两个u值和0比较去找最大的，把pk > 0的两个u值和1比较去找最小的，这样得到两个端点的参数值。

uk = qk / pk (pk≠0， k = 1,2,3,4)
uk是窗口边界及其延长线的交点的对应参数值

umax =max(0, uk|pk < 0, uk|pk < 0)
umin =min(0, uk|pk > 0, uk|pk > 0, 1)

注意：pk < 0，代表入边；pk > 0代表出边

umax > umin，则直线段在窗口外，删除该直线
若umax≤umin，将umax和umin代回直线参数方程，即求出直线与窗口的两实交点坐标。
x = x1 + u·(x2 - x1)
y = y1 + u·(y2 - y1)

注意：因为对于实交点0≤u≤1，因此umax不能小于0，umin不能大于1

步骤

多边形裁剪

Sutherland-Hodgeman多边形裁剪

思想：将边界看作整体，每次用窗口的一条边对要裁剪的多边形和中间结果多边形进行裁剪。分而治之的思想。
缺点：只适合凸多边形

过程：

顶点处理四种情况：

文字裁剪

1. 串精度裁剪
   当字符串中的所有字符都在裁剪窗口内时，就全部保留它，否则舍弃整个字符串。
2. 字符精度裁剪
   裁剪时，任何与窗口有重叠或落在窗口边界以外的字符都被裁减掉。
3. 笔画/像素精度裁剪
   将笔划分解成直线段对窗口作裁剪。判断字符串中各字符的哪些像素、笔划的哪一部分在窗口内，保留窗口内部分，裁减掉窗口外的部分。

消隐算法

…未完待续