光栅图形学(6)-直线裁剪算法

文章目录[x]
  1. 1:Cohen-Sutherland 裁剪算法
  2. 1.1:简介
  3. 1.2:代码
  4. 1.3:效果
  5. 1.4:参考
  6. 2:Liang-Barsky裁剪算法
  7. 2.1:思想介绍
  8. 2.2:裁剪一次的代码步骤
  9. 2.3:C++代码
  10. 2.4:参考

 

FBI WARNING:本文含有数学公式,如显示异常请刷新页面

 

直线段裁剪


直线裁剪算法是计算机光栅图形学中非常底层的算法,复杂的曲线也可以通过折线段来来裁剪。常用的裁剪方法有三种,即Cohen-Sutherland法、中点分割法和梁友栋-Barsky裁剪算法。

Cohen-Sutherland 裁剪算法


简介


  1. 若P1P2完全在窗口内,则显示该线段P1P2,即,取之
  2. 若P1P2明显在窗口外,则丢弃该线段P1P2,即,弃之
  3. 若既不满足取之,也不满足弃之,则在线段与边界的交点处把线段分为两段,其中一段完成在窗口外

为了快速的表示一条直线段与窗口是何种关系,采用如下编码的方法:延长窗口的边,将二维平面分成9个区域,每个区域赋予4位编码D4D3D2D1,如下图

(图片来自《计算机图形学》赵明-中国农业大学 3.1.2)

由上图可知:

  1. 先求出P1,P2所在区号code1和code2,若(code1 | code2) == 0,则对直线段应取之,(两点都在窗口内),否则
  2. 若(code1 & code2) != 0,对直线段弃之,(两点同在窗口的上方、下方、左方、右方),否则
  3. 求出线段与窗口某边的交点,在交点处把线段一分为二,其中必有一条在窗口外,可弃之,再对另一端重复上述处理。

代码


const int LINE_INSIDE   = 0; // 0000
const int LINE_LEFT     = 1; // 0001
const int LINE_RIGHT    = 2; // 0010
const int LINE_BOTTOM   = 4; // 0100
const int LINE_TOP      = 8; // 1000

const int XL = 200;
const int XR = 800;
const int YB = 200;
const int YT = 600;

int line_encode(int x, int y)
{
    int c = LINE_INSIDE;
    if (x < XL) c |= LINE_LEFT; 
    if (x > XR) c |= LINE_RIGHT;
    if (y < YB) c |= LINE_BOTTOM; 
    if (y > YT) c |= LINE_TOP;
    return c;
}


void LineClip_CohenSutherland(int x1, int y1, int x2, int y2, Color& color)
{
    int code1, code2, code, x, y;
    code1 = line_encode(x1, y1);
    code2 = line_encode(x2, y2);

    while (code1 || code2)    
    {
        if (code1 & code2) return; // 两个端点在窗口外,弃之

        if (code1)
            code = code1;
        else
            code = code2;

        if (LINE_LEFT & code)
        {
            x = XL;
            y = y1 + (XL - x1) * (y2 - y1) / (x2 - x1);  // 直线方程 点斜式
        }
        else if (LINE_RIGHT & code)
        {
            x = XR;
            y = y1 + (XR - x1) * (y2 - y1) / (x2 - x1);
        }
        else if (LINE_BOTTOM & code)
        {
            y = YB;
            x = x1 + (YB - y1) * (x2 - x1) / (y2 - y1);
        }
        else if (LINE_TOP & code)
        {
            y = YT;
            x = x1 + (YT - y1) * (x2 - x1) / (y2 - y1);
        }

        if (code == code1)
        {
            x1 = x;
            y1 = y;
            code1 = line_encode(x, y);
        }
        else
        {
            x2 = x;
            y2 = y;
            code2 = line_encode(x, y);
        }
    }

    RenderSystem::current->GetRasterizer()->DrawLineByDDA(Vector2(x1, y1), Vector2(x2, y2), color);
    
}

Usage

// 随机画100条线
void LineDrawing::LineClip()
{
    int xl = 200, xr = 800, yb = 200, yt = 600;
    int pointsArray[] = { xl, yb, xr, yb, xr, yt, xl, yt, xl, yb };
    DrawPoly(5, pointsArray, Color::black, true);  // 绘制窗口

    if (!points)
    {
        int xc = (xl + xr) / 2;
        int yc = (yt + yb) / 2;
        int xoffset1 = xl - 200;
        int xoffset2 = xr + 200;
        int yoffset1 = yb - 100;
        int yoffset2 = yt + 100;
        int x1, y1, x2, y2;
        points = new std::vector();
        for (int i = 0; i < 100; i++) 
        { 
            x1 = Random::Range(xoffset1, xoffset2); 
            x2 = Random::Range(xoffset1, xoffset2);
            y1 = Random::Range(yoffset1, yoffset2); 
            y2 = Random::Range(yoffset1, yoffset2); 
            points->push_back(Vector2(x1, y1));
            points->push_back(Vector2(x2, y2));
        }
    }

    int size = points->size();
    for (int i = 0; i < size; i += 2) 
    { 
        Vector2 v1 = points->at(i);
        Vector2 v2 = points->at(i + 1);
        RenderSystem::current->GetRasterizer()->DrawLineByDDA(v1, v2, Color::green); // 画出未经裁剪的线,用做对比
        LineClip_CohenSutherland(v1.x, v1.y, v2.x, v2.y, Color::blue);  // 裁剪画线
    }
}

效果


参考


计算机图形学 - 中国农业大学 3.1.1 编码算法
《计算机图形学基础教程》(第二版) 孙家广、胡事民 2.5.1.1 (此章节算法程序2.11有误,if (y<YT) 应为 if (y>YT))

 

Liang-Barsky裁剪算法


思想介绍


1.用参数方程表示一段直线

已知点 $ P_1 (x_1, y_1) $ 和 $ P_2 (x_2, y_2) $,那么该直线用参数方程表示为

\begin{equation}
\begin{cases}
x &= x_1 + u \cdot \Delta x \\
y &= y_1 + u \cdot \Delta y
\end{cases}
\quad (-\infty < u < +\infty)
\begin{cases}
0 \le u \le 1 & 直线段 P_1P_2 \\
u < 0 &射线(-\infty, P_1 ) \\
u > 1 & 射线(P_2, +\infty)
\end{cases}
\end{equation}

2.把直线段看成是一条有方向的线段

(图片来自 《计算机图形学》- 赵明 中国农业大学 3.3.1)

若线段与窗口不平行,则线段的延长线与窗口边界的延长线必有4个交点,如上图红点,再加上线段自身的两个端点共有6个点。

如上图所示,只需求得 $ u_1  u_2 $ 即可算出裁剪后的线段端点。

目前已知的裁剪条件为:

\begin{equation}
\begin{cases}
XL \le x_1 + u \cdot \Delta x \le XR \\
YB \le y_1 + u \cdot \Delta y \le YT
\end{cases}
\end{equation}
$$ XL = XLeft \quad XR = XRight \quad YB = YBottom \quad YT =  YTOP $$

求得上述不等式为:

\begin{equation}
\begin{cases}
u \cdot -\Delta x &\le x_1 - XL \\
u \cdot \Delta x &\le XR - x_1 \\
u \cdot -\Delta y &\le y_1 - YB \\
u \cdot \Delta y &\le  YT  - y_1
\end{cases}
\end{equation}

令:

$$ p_1 = -\Delta x \quad q_1 = x_1 - XL \\ p_2 = +\Delta x \quad q_2 = XR - x_1  \\ p_3 = -\Delta y \quad q_3 = y_1 - YB \\ p_4 = +\Delta y \quad q_4 = YT - y_1 $$

可得:

$$ u \cdot p_k = q_k $$

对于任何平行于裁剪边界之一的直线 $ p_k = 0 $,其中 $ k $ 对应于裁剪边界( $ k = 1, 2, 3, 4, 对应于左、右、下、上边界$);如果还满足 $ q_k < 0 $, 则线段完全在边界外,舍弃该线段;如果 $ q_k \ge 0 $,则该线段平行于裁剪边界并且在窗口内

当 $ p_k < 0 $ 时,线段从裁剪边界所在直线的外部指向内部。当 $ p_k > 0 $时,线段从裁剪边界所在直线的内部指向外部。当 $ p_k \neq 0 $ 时,可以计算出线段与边界 $ k $ 的延长线交点的 $ u $ 值: $ u = \frac{q_k}{p_k} $

 

裁剪一次的代码步骤


  1. 初始化 $ u_1 = 0\quad u_2 = 1 $
  2. 计算p值,q值, r = q / p;
  3. 若 p < 0,若r > u2,舍弃;否则u1 = max(r, u1)
  4. 若 p > 0,若r < u1,舍弃;否则u2 = min(r, u2)
  5. 若q < 0,舍弃

 

C++代码


bool LB_Clip(float p, float q, float* u1, float* u2)
{
    float r;
    if (p < 0)
    {
        r = q / p;
        if (r > *u2)
            return false;
        if (r > *u1)
            *u1 = r;
    }
    else if (p > 0)
    {
        r = q / p;
        if (r < *u1)
            return false;
        if (r < *u2)
            *u2 = r;
    }
    else
    {
        return q >= 0;
    }

    return true;
}

void LineClip_Liang_Barsky(int x1, int y1, int x2, int y2, Color& color)
{
    // x = x1 + u*Δx
    // y = y1 + u*Δy
    // p1=-Δx, q1=x1-XL; 
    // p2= Δx, q2=XR-x1; 
    // p3=-Δy, q3=y1-YB; 
    // p4= Δy, q4=YT-y1

    float dx = x2 - x1, dy = y2 - y1, u1 = 0, u2 = 1;
    if (LB_Clip(-dx, x1 - XL, &u1, &u2)
        && LB_Clip(+dx, XR - x1, &u1, &u2)
        && LB_Clip(-dy, y1 - YB, &u1, &u2)
        && LB_Clip(+dy, YT - y1, &u1, &u2))
    {
        RenderSystem::current->GetRasterizer()->DrawLineByDDA(
            Vector2(x1 + u1 * dx, y1 + u1 * dy),
            Vector2(x1 + u2 * dx, y1 + u2 * dy),
            color);
    }
}

效果:

参考


《计算机图形学基础教程》(第二版) 孙家广、胡事民 2.5.1.3
计算机图形学 - 中国农业大学 3.3 Liang-Barsky算法
【裁剪】线段的裁剪——Liang-Barskey算法以及代码实现

 

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像