跳转到内容

科恩-萨瑟兰算法

本页使用了标题或全文手工转换
维基百科,自由的百科全书
(重定向自科恩-苏泽兰算法

科恩-萨瑟兰算法(英語:Cohen–Sutherland algorithm),是计算机图形学直线段裁剪算法的一种,由丹尼·科恩英语Danny Cohen (computer scientist)伊万·萨瑟兰两人提出。

算法描述

科恩-萨瑟兰算法主要分三步进行:

第一步

将矩形窗口四条边界延长,则整个被平面分成九个区域。

区域划分及编码

每个区域内的点都对应着一个四位二进制区位码。

区位码各位含义

任何位赋值1,代表端点落在相应的位置上,否则该位置为0。例如,如果端点在裁剪窗口内,则区位码为0000,如果端点在矩形裁剪窗口的左下角,则区位码为0101。

根据要裁剪线段P1P2的端点坐标求出相应的编码值C1和C2。

第二步

判断P1、P2的位置。

若C1=C2=0,即P1、P2的编码全为零,线段P1P2在窗口内,保留线段P1P2,过程结束。

否则,若C1∧C2≠0,即作P1、P2编码的逻辑与,结果为非零时,表示P1、P2在窗口的同侧,弃之,过程结束。

否则,线段必有一端点在窗口外,令该点为P1,进行下一步。

第三步

根据P1点的编码值,确定其在哪条边界线之外,求线段与该边界线的交点P,交点把线段分成两段,舍去P1P段,把交点P作为剩余线段的P1端点重新进行第二步。

Cohen-Sutherland img3.png

线段a经第二步测试为窗口内线段(C1=C2=0),取之。线段b经第二步测试为窗口外同侧线段(C1∧C2≠0),弃之。线段c需在第三步求出与窗口边界的交点P3,舍去P1P3段,把P3作为新的P1再进行第二步测试,又到第三步求出与窗口边界的交点P4,舍去P4P2段,再把P4作为新的P2,经第二步测试为窗口内线段,取之。

示例代码

C语言

#define LEFT 1
#define TOP 8
#define RIGHT 2
#define BOTTOM 4
 
void encode (x, y, color)
float x,y;
int *code; {
	int c = 0;
	if ( x <XL)
		c = c|LEFT;
    else if ( x> XR)
		c = c|RIGHT;
    if (y < YB)
		c = c|BOTTOM;
    else if (y > YT)
		c = c|TOP;
    *code = c;
    return;
}

void Swappoint (x1, y1, x2, y2)
float *x1,*y1,*x2*,x2; {
    float t;
    t = *x1; *x1 = *x2; *x2 = t;
    t = *y1; *y1 = *y2; *y2 = t;
}
 
void SwapCode (code1, code2)
int *code1,*code2; {
    int t;
    t = *code1; *code1 = *code2; *code2 = t;
}
 
/*(x1,y1)与(x2,y2)是线段端点坐标,其他四个参数分别为窗口左、右、上、下四个边界*/
C_S_Line_Clip (x1, y1, x2, y2, XL, XR, YT, YB)
float x1,y1,x2,y2, XL, XR,YT, YB; {
    int code1, code2, code;
    encode (x1, y1, &code1);
    encode (x2, y2, &code2);
    while (code1 != 0 && code2 != 0) {
        if (code1 & code2 != 0)
            return;
        if (code1 == 0) {
            SwapPoint (&x1, &y1, &x2, &y2);
            SwapCode (&code1, &code2);
        }
        code = code1;
        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 (TOP & code !=0) { /*线段与上边界相交*/
            y = YT;
            x = x1+(x2-x1)*(YT-y1)/(y2-y1);
        }
        else if (BOTTOM & code != 0) { /*线段与下边界相交*/
            y = YB;
            x = x1+(x2-x1)*(YB-y1)/(y2-y1);
        }
        x1 = x;
        y1 = y;
        encode (x, y, code1);
    }
    line (x1, y1, x2, y2);
}

[1]

参考文献

  1. ^ 张义宽. 计算机图形学. 西安: 西安电子科技大学出版社. 2004.