おたくのスタジオ

Cohen-Sutherland算法

发表于 | 分类于

本文主要介绍Cohen-Sutherland算法。该算法没有用很多if语句来寻找直线的位置，而是把裁剪区域分成了许多部分，然后给每一段被裁剪的线段的两端分配一位代码。而后，只采用少量的if语句或一个case语句，就能判断出具体情况。下图给出了原理示意图。

2d-clipping-a

算法流程如下：

2d-clipping-b

伪代码如下：

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
int Clip_Line(int &x1, int &y1, int &x2, int &y2) {
    #define CLIP_CODE_C 0x0000
    #define CLIP_CODE_N 0x0008
    #define CLIP_CODE_S 0x0004
    #define CLIP_CODE_E 0x0002
    #define CLIP_CODE_W 0x0001

    #define CLIP_CODE_NE 0x000a
    #define CLIP_CODE_SE 0x0006
    #define CLIP_CODE_NW 0x0009
    #define CLIP_CODE_SW 0x0005

    int xc1=x1, yc1=y1, xc2=x2, yc2=y2;
    int p1_code=0, p2_code=0;

    // determine codes for p1 and p2
    if (y1 < min_clip_y)
        p1_code|=CLIP_CODE_N;
    else if (y1 > max_clip_y)
        p1_code|=CLIP_CODE_S;

    if (x1 < min_clip_x)
        p1_code|=CLIP_CODE_W;
    else if (x1 > max_clip_x)
        p1_code|=CLIP_CODE_E;

    if (y2 < min_clip_y)
        p2_code|=CLIP_CODE_N;
    else if (y2 > max_clip_y)
        p2_code|=CLIP_CODE_S;

    if (x2 < min_clip_x)
        p2_code|=CLIP_CODE_W;
    else if (x2 > max_clip_x)
        p2_code|=CLIP_CODE_E;

    // try and trivially reject
    if ((p1_code & p2_code))
        return 0;

    // test for totally visible, if so leave points untouched
    if (p1_code==0 && p2_code==0)
        return 1;
  
    // determine end clip point for p1
    switch(p1_code)
    {
        case CLIP_CODE_C: break;
        case CLIP_CODE_N:
        {
            yc1 = min_clip_y;
            xc1 = x1 + 0.5+(min_clip_y-y1)*(x2-x1)/(y2-y1);
        } break;
        case CLIP_CODE_S:
        {
            yc1 = max_clip_y;
            xc1 = x1 + 0.5+(max_clip_y-y1)*(x2-x1)/(y2-y1);
        } break;
        case CLIP_CODE_W:
        {
            xc1 = min_clip_x;
            yc1 = y1 + 0.5+(min_clip_x-x1)*(y2-y1)/(x2-x1);
        } break;
        case CLIP_CODE_E:
        {
            xc1 = max_clip_x;
            yc1 = y1 + 0.5+(max_clip_x-x1)*(y2-y1)/(x2-x1);
        } break;
        // these cases are more complex, must compute 2 intersections
        case CLIP_CODE_NE:
        {
            // north hline intersection
            yc1 = min_clip_y;
            xc1 = x1 + 0.5+(min_clip_y-y1)*(x2-x1)/(y2-y1);
            // test if intersection is valid,
            // if so then done, else compute next
            if (xc1 < min_clip_x || xc1 > max_clip_x)
            {
            	// east vline intersection
            	xc1 = max_clip_x;
            	yc1 = y1 + 0.5+(max_clip_x-x1)*(y2-y1)/(x2-x1);
            } // end if
        } break;
        case CLIP_CODE_SE:
        {
            // south hline intersection
            yc1 = max_clip_y;
            xc1 = x1 + 0.5+(max_clip_y-y1)*(x2-x1)/(y2-y1);
            // test if intersection is valid,
            // if so then done, else compute next
            if (xc1 < min_clip_x || xc1 > max_clip_x)
            {
              // east vline intersection
                xc1 = max_clip_x;
            	yc1 = y1 + 0.5+(max_clip_x-x1)*(y2-y1)/(x2-x1);
            } // end if
        } break;
        case CLIP_CODE_NW:
        {
            // north hline intersection
            yc1 = min_clip_y;
            xc1 = x1 + 0.5+(min_clip_y-y1)*(x2-x1)/(y2-y1);
            // test if intersection is valid,
            // if so then done, else compute next
            if (xc1 < min_clip_x || xc1 > max_clip_x)
            {
                xc1 = min_clip_x;
            	yc1 = y1 + 0.5+(min_clip_x-x1)*(y2-y1)/(x2-x1);
            } // end if
        } break;
        case CLIP_CODE_SW:
        {
            // south hline intersection
            yc1 = max_clip_y;
            xc1 = x1 + 0.5+(max_clip_y-y1)*(x2-x1)/(y2-y1);
            // test if intersection is valid,
            // if so then done, else compute next
            if (xc1 < min_clip_x || xc1 > max_clip_x)
            {
            	xc1 = min_clip_x;
            	yc1 = y1 + 0.5+(min_clip_x-x1)*(y2-y1)/(x2-x1);
            } // end if
        } break;
		  default:break;
    } // end switch
    // determine end clip point for p2
    switch(p2_code)
    {
    	...
    }
  
    // do bounds check
    if ((xc1 < min_clip_x) || (xc1 > max_clip_x) ||
    	(yc1 < min_clip_y) || (yc1 > max_clip_y) ||
    	(xc2 < min_clip_x) || (xc2 > max_clip_x) ||
    	(yc2 < min_clip_y) || (yc2 > max_clip_y) )
    {
    	return 0;
    } // end if
  
    // store vars back
    x1 = xc1;
    y1 = yc1;
    x2 = xc2;
    y2 = yc2;
    return 1;
}