每周一点图形学暂停。
  最新:Bresenham算法代码
  

帧缓冲器及分辨率

帧缓冲器每一个存储单元的位长决定了一幅画面上能同时显示的不同灰度的数目或颜色的种类。
如果是单色,则每个像素只需要1Bit表示;
如果是16色,则每个像素需要4Bit(2^4=16)表示;
如果是256色,则每个需要1个字节(8位,2^8=256)表示;
如果是65536(64K)色,则每个像素需要2个字节(16位,2^16=64K)表示;
如果是16777216(16.7M)色,则每个需要3个字节(24位,2^24=16.7M)表示(24位真彩色)。

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

题目:显示颜色64K,分辨率为1024*1024的显示器,至少需要的帧缓存容量为(C)
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为常数

映射关系
映射关系

公式
公式

公式
公式

三维图形几何变换

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

三维变换矩阵
三维变换矩阵

T3D
T3D

基本变换

平移变换

三维平移
三维平移

比例变换

局部比例变换

局部比例变换
局部比例变换

整体比例变换

整体比例变换
整体比例变换

旋转变换

绕z轴旋转θ

三维绕z旋转
三维绕z旋转

绕x轴旋转

三维绕x旋转
三维绕x旋转

绕y轴旋转

三维绕y旋转
三维绕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方向平移一段距离-z0,有一个平移矩阵。
所以,最终俯视图投影变换矩阵:
[x’ y’ z’ 1] = [x y -(y+z0) 1]

侧视图

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

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

正轴测图

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

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

透视投影

T3D
T3D

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

透视

一点透视

灭点:聚焦的那个点

多点透视

多个灭点

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

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

光栅图形学算法

研究内容

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

直线段的扫描转换算法

P0(x0,y0) P1(x1,y1)
y=kx+b
k=(y1-yo)/(x1-x0) (x1≠x0)
假设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不判断大小,是判断符号。