Алгоритм Коена — Сазерленда

Алгоритм Коена — Сазерленда (англ. Cohen-Sutherland algorithm) — алгоритм відсікання відрізків, тобто алгоритм, який дозволяє визначити частину відрізка, яка перетинає прямокутник. Був розроблений Деном Коеном^[en] і Айвеном Сазерлендом у Гарварді в 1966–1968 рр., І опублікований на конференції AFIPS в 1968 .^[1]^[2]

Опис алгоритму

Алгоритм поділяє площину на 9 частин прямими, які утворюють сторони прямокутника. Кожній з 9 частин присвоюється чотирьохбітний код. Біти (від молодшого до старшого) означають «лівіше», «правіше», «нижче», «вище». Іншими словами, у тих трьох частин площини, які зліва від прямокутника, молодший біт дорівнює 1, і так далі.

Алгоритм визначає код кінців відрізка. Якщо обидва коди дорівнюють нулю, то відрізок повністю знаходиться в прямокутнику. Якщо бітове "І" кодів не дорівнює нулю, то відрізок не перетинає прямокутник (так як це означає, що обидві кінців відрізка знаходяться з однієї сторони прямокутника). В інших випадках, алгоритм вибирає кінець, що знаходиться поза прямокутником, знаходить найближчу до неї точку перетину відрізка з однієї з ліній, що утворює сторони прямокутника, і використовує цю точку перетину як новий кінець відрізка. Укорочений відрізок знову пропускається через алгоритм.

Реалізації

Реалізація на мові С для двовимірної моделі.

#define LEFT 1 / * двійкове 0001 * /
#define RIGHT 2 / * двійкове 0010 * /
#define BOT 4 / * двійкове 0100 * /
#define TOP 8 / * двійкове 1000 * /

/ * Точка * /
struct point {
double x, y;
};

/ * Прямокутник * /
struct rect {
double x_min, y_min, x_max, y_max;
};

/ * Обчислення коду точки
    r: покажчик на struct rect; p: покажчик на struct point * /
#define vcode (r, p) \
	((((p)->x < (r)->x_min) ? LEFT : 0) + /* +1 якщо точка лівіше прямокутника * / \
(((p) -> x> (r) -> x_max)? RIGHT: 0) + / * +2 якщо точка правіше прямокутника * / \
(((p) -> y <(r) -> y_min)? BOT: 0) + / * +4 якщо точка нижче прямокутника * / \
(((p) -> y> (r) -> y_max)? TOP: 0)) / * +8 якщо точка вище прямокутника * /

/* якщо відрізок ab не перетинає прямокутник r, функція повертає -1;
    якщо відрізок ab перетинає прямокутник r, функція повертає 0 і відсікає
    ті частини відрізка, які знаходяться поза прямокутника */
int cohen_sutherland (const struct rect *r, struct point *a, struct point *b)
{
	int code_a, code_b, code; /* код кінців відрізка */
	struct point *c; /* одна з точок */

	code_a = vcode(r, a);
	code_b = vcode(r, b);
	
	/* поки одна з точок відрізка поза прямокутником */
	while (code_a | code_b) {
		/* якщо обидві точки з одного боку прямокутника, то відрізок не перетинає прямокутник */
		if (code_a & code_b)
			return -1;

		/* обираємо точку c з ненульовим кодом */
		if (code_a) {
			code = code_a;
			c = a;
		} else {
			code = code_b;
			c = b;
		}

		/* якщо c лівіше r, тоді переміщуємо c на пряму x = r->x_min
		 якщо c правіше r, тоді переміщуємо c на пряму x = r->x_max */
		if (code & LEFT) {
			c->y += (a->y - b->y) * (r->x_min - c->x) / (a->x - b->x);
			c->x = r->x_min;
		} else if (code & RIGHT) {
			c->y += (a->y - b->y) * (r->x_max - c->x) / (a->x - b->x);
			c->x = r->x_max;
		}/* якщо c нижче r, тоді переміщуємо c на пряму y = r->y_min
		 якщо c вище r, то переміщуємо c на пряму y = r->y_max */
		else if (code & TOP) {
			c->x += (a->x - b->x) * (r->y_min - c->y) / (a->y - b->y);
			c->y = r->y_min;
		} else if (code & BOT) {
			c->x += (a->x - b->x) * (r->y_max - c->y) / (a->y - b->y);
			c->y = r->y_max;
		}

		/* оновлюємо код */
		if (code == code_a) {
                        a = c;
			code_a = vcode(r,a);
		} else {
                        b = c;
			code_b = vcode(r,b);
                }
	}

	/* коди рівні 0, отже обидві точки в прямокутнику */
	return 0;
}

Реалізація мовою C++ для тривимірної моделі.

# define BOTTOM 1 // 00 000001
# define LEFT 2 // 00 000010
# define TOP 4 // 00 000100
# define RIGHT 8 // 00 001000
# define BACK 16 // 00 010000
# define FRONT 32 // 00 100000

typedef struct Area {
	float xlt, ylt, zlt; // Координати лівого верхнього кута ближньої грані
        float xrb, yrb, zrb; // Координати правого нижнього кута дальньої грані
} Area;

int GetCode ( const float point[1][4], const Area &anArea ) {
	int code = 0;
	if (point [0] [1]> anArea.ylt) // Точка вище області відсікання
               code | = TOP;
        else if (point [0] [1] <anArea.yrb) // Точка нижче області відсікання
               code | = BOTTOM;
        if (point [0] [0]> anArea.xrb) // Точка правіше області відсікання
               code | = RIGHT;
        else if (point [0] [0] <anArea.xlt) // Точка лівіше області відсікання
               code | = LEFT;
        if (point [0] [2] <anArea.zlt) // Точка перед областю відсікання
               code | = FRONT;
        else if (point [0] [2]> anArea.zrb) // Точка за областю відсікання
               code | = BACK;
        return code;
        }

// Тривимірне відсікання методом Коена-Сазерленда.
// Beg - координати початку відрізка [xn, yn, zn, 1]
// End - координати кінця відрізка [xk, yk, zk, 1]
// AnArea - координати області, яка відтинає
void CS_Clip (const float beg [1] [4], const float end [1] [4], const Area & anArea)
{
	// Коди кінців відрізка
	int outcode0 = 0, outcode1 = 0, outcodeOut = 0;
		
	char codes[2][7] = {"000000","000000"};
	float temp[2][1][4];

	// Прапор видимості і прапор завершення відсікання
        bool accept = false, done = false;

        outcode0 = GetCode (beg, codes [0], anArea); // Обчислюємо початкові коди кінців відрізка
	outcode1 = GetCode( end, codes[1],anArea );
	do
	{
 		float x, y, z;
        if (! (outcode0 | outcode1)) {// Відрізок повністю видимий
        accept = true;
        done = true;
        }
        else if (outcode0 & outcode1) // Відрізок повністю невидимий
        done = true;
        else {// Відрізок частково видимий. Обчислення точок перетину відрізка та області відсікання
			outcodeOut = outcode0 ? outcode0: outcode1;
			if( outcodeOut & TOP ) {
				x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.ylt-beg[0][1])/(end[0][1]-beg[0][1]);
				z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.ylt-beg[0][1])/(end[0][1]-beg[0][1]);
				y = anArea.ylt;
			}
			else if( outcodeOut & BOTTOM ) {
				x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.yrb-beg[0][1])/(end[0][1]-beg[0][1]);
				z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.yrb-beg[0][1])/(end[0][1]-beg[0][1]);
				y = anArea.yrb;
			}
			else if( outcodeOut & RIGHT ) {
				y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.xrb-beg[0][0])/(end[0][0]-beg[0][0]);
				z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.xrb-beg[0][0])/(end[0][0]-beg[0][0]);
				x = anArea.xrb;
			}
			else if( outcodeOut & LEFT ) {
				y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.xlt-beg[0][0])/(end[0][0]-beg[0][0]);
				z = beg[0][2]+(end[0][2]-beg[0][2])*(anArea.xlt-beg[0][0])/(end[0][0]-beg[0][0]);
				x = anArea.xlt;
			}
			else if( outcodeOut & FRONT ) {
				x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.zlt-beg[0][2])/(end[0][2]-beg[0][2]);
				y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.zlt-beg[0][2])/(end[0][2]-beg[0][2]);
				z = anArea.zrb;
			}
			else if( outcodeOut & BACK ) {
				x = beg[0][0]+(end[0][0]-beg[0][0])*(anArea.zrb-beg[0][2])/(end[0][2]-beg[0][2]);
				y = beg[0][1]+(end[0][1]-beg[0][1])*(anArea.zrb-beg[0][2])/(end[0][2]-beg[0][2]);
				z = anArea.zlt;
			}
			if ( outcodeOut == outcode0 ) {
				temp[0][0][0] = x;
				temp[0][0][1] = y;
				temp[0][0][2] = z;
				outcode0 = GetCode( temp[0],codes[0],anArea );
			}
			else {
				temp[1][0][0] = x;
				temp[1][0][1] = y;
				temp[1][0][2] = z;
				outcode1 = GetCode( temp[1], codes[1],anArea );
			}
		}
	}while ( !done );	
	if( accept ) { // Відрізок повністю видимий. Відрізок на екран.
		LINE(temp[0],temp[1]);
	}
}

Примітки

↑ A Critical History of Computer Graphics and Animation. Section 4: Basic and applied research moves the industry (англ.).
↑ Robert F. Sproull, Ivan E. Sutherland A clipping divider // AFIPS Joint Computer Conferences: Proceedings of the December 9-11, 1968, fall joint computer conference. — New York: ACM, 1968. — Т. I. — С. 765–775.