光栅图形学

光栅图形学主要研究如何使光栅图形最完美地逼近实际图形，本文主要介绍光栅图形学的几个基本算法。

直线段的扫描转换算法

一个像素宽直线绘制的三个常用算法：数值微分法、中点画线法、Bresenham算法

数值微分法（DDA）

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void DDALine(int x0, int y0, int x1, int y1, int color)
{
    int x;
    float dx, dy, y, k;
    dx = x1 - x0;
    dy = y1 - y0;
    k = dy / dx;
    y = y0;
    for (x = x0; x < x1; x++) {
        drawpixel(x, int(y + 0.5), color);
        y = y + k;
    }
}

// 该算法仅适用于|k| <= 1的情形，x每增加1，y最多增加1，当|k| > 1时，必须交换x和y，y和k必须用浮点数表示，每一步都要对y进行四舍五入后取整，不利于硬件实现

中点画线法

程序（斜率也是小于1）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void MidpointLine(int x0, int y0, int x1, int y1, int color)
{
    int a, b, d1, d2, x, y;
    a = y0 - y1;
    b = x1 - x0;
    d = 2 * a + b;
    d1 =  2 * a;
    d2 = 2 * (a + b);
    x = x0;
    y = y0;
    drawpixel(x, y, color);
    while(x < x1) 
    {
        if (d < 0) {x++; y++; d+=d2;}
        else  {x++; d+=d1;}
        drawpixel(x, y, color);
    }
}

Bresenham算法

使用最广泛的直线扫描转换算法，仍然假定直线斜率在0~1之间，类似于中点法，由误差项符号决定下一像素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 (int i = 0; i < dx; i++) 
    {
        drawpixel(x, y, color);
        x = x + 1;
        e = e + k;
        if (e >= 0.5) e = e - 1;
        if (e >= 0) y++;
    }
}

圆弧的扫描转换算法

圆的八对称性：若已知圆弧上一点（x, y），可以得到其关于四条对称轴的其它7个点的性质，因此只要扫描转换八分之一圆弧，就可以求出整个圆弧的像素集。

简单方程产生圆弧

利用其函数方程，直接离散计算

函数方程

极坐标

中点画圆法

程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void 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);
    }
}

圆的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
void circle(int xc, int yc, int radius, int c)
{
    int x = 0; int y = radius;
    int p = 3 - 2 * radius;
    while (x < y)
    {
        polt_circle(xc, yc, x, y, c);
        if (p < 0)
            p = p + 4*x + 6;
        else
        {
            p = p + 4*(x-y) + 10;
            y = 1;
        }
        
    }
    if(x == y) plot_circle_points(xc, yc, x, y, c);
}

void plot_circle_points(int xc, int yc, int x, int y, int c)
{
    set_pixel(xc+x, yc+y, c); set_pixel(xc+x, yc+y, c); set_pixel(xc+x, yc-y, c); 

    set_pixel(xc-x, yc-y, c); set_pixel(xc+y, yc+x, c); set_pixel(xc-y, yc+x, c);

    set_pixel(xc+y, yc-x, c); set_pixel(xc-y, yc-x, c); 
}

椭圆的扫描转换

椭圆的中点算法：和圆类似，确定一个像素后，接着在两个候选像素的中点计算一个判别式的值，根据判别式的符号确定哪个像素离椭圆更近。

多边形区域填充

表示方法

两种表示方法：

  • 顶点表示：直观，不能直接用于面填充
  • 点阵表示：可以用于面填充

多边形填充-扫描算法

步骤

  1. 求交：计算扫描线与多边形各边的交点
  2. 排序：把所有交点按x值递增顺序排序
  3. 配对：第一个与第二个，第三个与第四个等；每对交点代表扫描线与多边形一个相交区间
  4. 着色把相交区间内的象素置成多边形颜色，把相交区间外的象素置成背景色

活性边：与当前扫描线相交的边

活性边表AET：按与扫描线交点按x坐标递增顺序存放的活性边链表

活性边表节点保存的信息：

  • 当前扫描线与边的交点
  • 从当前扫描线到下一条扫描线之间的x增量
  • 边所交的最高扫描线号

例子

算法过程：

算法

多边形填充-边界标志算法

在帧缓冲器中对多边形边界所经过的像素打上标志，按扫描线将位于多边形内的各个区段着上所需颜色。

算法

多边形填充-种子填充算法

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

种子填充的递归算法原理简单，但效率不高，下面介绍种子填充的扫描线算法：

步骤：

  1. 初始化

    堆栈置空。将种子点(x, y)入栈

  2. 出栈

    若栈空则结束。否则取栈顶元素(x, y)，以y作为当前扫描线

  3. 填充并确定种子点所在区段

    从种子点(x, y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr

  4. 确定新的种子点

    在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第(2)步

字符的生成

点阵式字符

定义成一个成为掩膜的矩阵，由点阵中的不同值表达字符的形状。

变化：加租、旋转等，如下图

变化

矢量型字符

用点坐标的序列表示各个笔划

B

方向编码式字符

用若干种方向编码（如8方向编码）来表达一个字符

B

轮廓字型技术

一种点阵字符压缩技术，对字型数据压缩后再存储，使用时，将压缩的数据还原为字符位图点阵

原理：

  • 采用直线、或者二/三次Bezier(贝塞尔)曲线的集合来描述一个字符的轮廓线。轮廓线构成一个或若干个封闭的平面区域
  • 轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息，就构成了字符的压缩数据。这种控制信息用于保证字符变倍时引起的字符笔划原来的横宽/竖宽变大变小时，其宽度在任何点阵情况下永远一致
  • 采用适当的区域填充算法，可以从字符的轮廓线定义产生的字符位图点阵

裁剪

确定图形中哪些部分落在显示区内，以便只显示该部分图形的过程。

一般先裁剪再扫描转换

直线段裁剪-Cohen-Sutherland裁剪算法

延长窗口的边，将二维平面分成九个区域。

图示

裁剪一条线段时，先求出P1P2所在的区号code1,code2

  • 若code1=0 且 code2=0，则线段P1P2完全在窗口内，应取之
  • 若按位与运算code1 & code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。可判断线段完全在窗口外，可弃之
  • 否则，按第三种情况处理。求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。在对另一段重复上述处理

直线段裁剪-中点分割裁剪算法

首先采用前述方法对线段端点进行编码，把线段与窗口的关系分为三种情况: 全在、完全不在、线段和窗口有交

  • 对前两种情况，进行一样的处理(显示或抛弃)

  • 对第三种情况，用中点分割方法求出线段与窗口的交点

    • 从P0点出发找出距P0最近的可见点A(从P0往P1方向运动第一个进入窗口的点)
    • 从P1点出发找出距P1最近的可见点B (从P1往P0方向运动第一个进入窗口的点)
  • 两个可见点之间的连线即为线段P0P1的可见部分

中点分割方法

  • 先求出P0P1的中点Pm

  • 若P0Pm不是显然不可见的，并且P0P1在窗口中有可见部分，则距P0最近的可见点一定落在P0Pm上，所以用P0Pm代替P0P1

  • 否则若P0Pm是显然不可见的，则取PmP1代替P0P1

  • 再对新的P0P1求中点Pm。重复上述过程，直到PmP1长度小于给定的控制常数为止，此时Pm收敛于交点

由于该算法的主要计算过程只用到加法和除2运算，所以特别适合硬件实现，同时也适合于并行计算

直线段裁剪-梁友栋-Barskey算法

一种参数化裁剪算法，更快。

多边形裁剪

Sutherland-Hodgeman算法

基本思想是一次用窗口的一条边裁剪多边形。

算法的每一步，考虑窗口的一条边以及延长线构成的裁剪线。该线把平面分成两个部分：一部分包含窗口，称为可见一侧；另一部分称为不可见一侧。依序考虑多边形的各条边的两端点S、P。

它们与裁剪线的位置关系只有四种

  • S、P均在可见一侧=>仅输出顶点P
  • S、P均在不可见一侧=> 输出0个顶点
  • S可见,P不可见=>输出线段SP与裁剪线的交点I;
  • S不可见,P可见=>输出线段SP与裁剪线的交点I和终点P

记忆规则：交点(如果存在)+终点(如果可见)

位置关系

字符串裁剪

主要分为字符串精度剪裁、字符精度剪裁、像素精度剪裁

image-20211127210111156

反走样

提高分辨率

原理

显示器分辨率提高一倍，直线经过两倍的象素，锯齿也增加一倍，但同时每个阶梯的宽度也减小了一倍，显示出的直线段看起来就平直光滑了一些

缺点

这种反走样方法是以4倍的存储器代价和扫描转换时间获得的。因此，增加分辨率虽然简单，但是不经济的方法，而且它也只能减轻而不能消除锯齿问题

提高分辨率

区域采样

假定每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。

象素的显示灰度值=round(阴影面积*象素的最大灰度值) 。反走样效果较好。

加权区域采样

使相交区域对象素亮度的贡献依赖于该区域与象素中心的距离。当直线经过该象素时，该象素的亮度F是在两者相交区域A´上对滤波器(函数w)进行积分的积分值。

原理
计算机图形学

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！