科恩-蘇澤蘭演算法
外觀
此條目需要補充更多來源。 (2018年8月22日) |
科恩-蘇澤蘭演算法(英語:Cohen–Sutherland algorithm),是電腦圖學直線段裁剪演算法的一種,由丹尼·科恩和伊凡·蘇澤蘭兩人提出。
演算法描述
[編輯]科恩-蘇澤蘭演算法主要分三步進行:
第一步
[編輯]將矩形窗口四條邊界延長,則整個被平面分成九個區域。
每個區域內的點都對應著一個四位二進制區位碼。
任何位賦值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端點重新進行第二步。
線段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);
}
參考文獻
[編輯]- ^ 張義寬. 计算机图形学. 西安: 西安電子科技大學出版社. 2004.