Koen-Saderlandov algoritam

Koen-Saderlandov algoritam (engl. Cohen–Sutherland algorithm) je algoritam računarske grafike koji se koristi za seckanje linija (енгл. Line clipping). Ovaj algoritam deli ravan na 9 delova (ili prostor na 27 delova) i zatim efikasno određuje koji delovi kojih linija su vidljivi u centralnom regionu - u okviru za prikaz (енгл. viewport).

Algoritam je razvijen tokom rada na simulatoru leta od strane Denija Koena i Ivana Saderlanda.^[1]

Algoritam[уреди | уреди извор]

Algoritam uključuje, isključuje ili delimično uključuje duži bazirano na sledećem:

Ako su oba kraja duži u okviru za prikaz (bitovska disjuncija krajnjih tačaka == 0) : trivijalno prihvatamo celu duž.
Ako su oba kraja duži manja od x_min, onda se ta duž trivijalno odbacuje. Analogno važi za x_max, y_min i y_max. Ovo se lako proverava sa bitovskom konjukcijom krajnjih tačaka duži ( == 0).
Ako su krajnje tačke duži u različitim regionima: Algoritam prvo pronalazi kraj duži koji se nalazi van okvira za prikaz (mora da postoji bar jedan takav). Zatim se izračuna presek sa proširenim okvirom za prikaz (okvir za prikaz čije su stranice produžene tako da budu prave a ne duži) i na taj način se dobija nova tačka. Ovaj postupak se ponavlja sve dok se ne dodje do jedne od prethodno navedenih trivijalnih situacija.

Kodovi koji se pridružuju tačkama su sledeći:

1001	1000	1010
0001	0000	0010
0101	0100	0110

Prvi bit (najmanje težine) označava da je tačka iznad gornje granice (veća od y_max).

Drugi bit (najmanje težine) označava da je tačka ispod donje granice (manja od y_min).

Treći bit (najmanje težine) označava da je tačka desno od desne stranice (veća od x_max).

Četvrti bit (najmanje težine) označava da je tačka levo od leve stranice (manja od x_min).

Kohen Saterlendov algoritam može da se koristi samo u slučaju kada je kliping površina pravougaonik. Za kliping u slučaju konveksnog poligona, može se koristiti Sajrus-Bekov algoritam.

Primer C/C++ implementacije[уреди | уреди извор]

typedef int OutCode;

const int INSIDE = 0; // 0000
const int LEFT = 1; // 0001
const int RIGHT = 2; // 0010
const int BOTTOM = 4; // 0100
const int TOP = 8; // 1000

// Compute the bit code for a point (x, y) using the clip rectangle
// bounded diagonally by (xmin, ymin), and (xmax, ymax)

// ASSUME THAT xmax, xmin, ymax and ymin are global constants.

OutCode ComputeOutCode(double x, double y)
{
	OutCode code;

	code = INSIDE; // initialised as being inside of clip window

	if (x < xmin) // to the left of clip window
		code |= LEFT;
	else if (x > xmax) // to the right of clip window
		code |= RIGHT;
	if (y < ymin) // below the clip window
		code |= BOTTOM;
	else if (y > ymax) // above the clip window
		code |= TOP;

	return code;
}

// Cohen–Sutherland clipping algorithm clips a line from
// P0 = (x0, y0) to P1 = (x1, y1) against a rectangle with 
// diagonal from (xmin, ymin) to (xmax, ymax).

void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1)
{
	// compute outcodes for P0, P1, and whatever point lies outside the clip rectangle
	OutCode outcode0 = ComputeOutCode(x0, y0);
	OutCode outcode1 = ComputeOutCode(x1, y1);
	bool accept = false;

	while (true) {
		if (!(outcode0 | outcode1)) { // Bitwise OR is 0. Trivially accept and get out of loop
			accept = true;
			break;
		} else if (outcode0 & outcode1) { // Bitwise AND is not 0. Trivially reject and get out of loop
			break;
                } else {
			// failed both tests, so calculate the line segment to clip
			// from an outside point to an intersection with clip edge
			double x, y;

			// At least one endpoint is outside the clip rectangle; pick it.
			OutCode outcodeOut = outcode0 ? outcode0 : outcode1;

			// Now find the intersection point;
			// use formulas y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
			if (outcodeOut & TOP) { // point is above the clip rectangle
				x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
				y = ymax;
			} else if (outcodeOut & BOTTOM) { // point is below the clip rectangle
				x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
				y = ymin;
			} else if (outcodeOut & RIGHT) { // point is to the right of clip rectangle
				y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
				x = xmax;
			} else if (outcodeOut & LEFT) { // point is to the left of clip rectangle
				y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
				x = xmin;
			}

			// Now we move outside point to intersection point to clip
			// and get ready for next pass.
			if (outcodeOut == outcode0) {
				x0 = x;
				y0 = y;
				outcode0 = ComputeOutCode(x0, y0);
			} else {
				x1 = x;
				y1 = y;
				outcode1 = ComputeOutCode(x1, y1);
			}
		}
	}
	if (accept) {
               // Following functions are left for implementation by user based on
               // their platform (OpenGL/graphics.h etc.)
               DrawRectangle(xmin, ymin, xmax, ymax);
               LineSegment(x0, y0, x1, y1);
	}
}

Vidi još[уреди | уреди извор]

Algoritmi koji se koriste u istu svrhu:

Reference[уреди | уреди извор]

^ Sproull, Bob; Newman, William M. (1973). Principles of Interactive Computer Graphics (International изд.). McGraw–Hill Education. стр. 124,252. ISBN 978-0-07-085535-9.

Literatura[уреди | уреди извор]

Foley, James D. (1996). Computer Graphics: Principles and Practice. Addison-Wesley Professional. ISBN 978-0-201-84840-3.
Predrag Janičić. [1]. Matematički fakultet, Beograd

Spoljašnje veze[уреди | уреди извор]

[Sproull-1] Sproull, Bob; Newman, William M. (1973). Principles of Interactive Computer Graphics (International изд.). McGraw–Hill Education. стр. 124,252. ISBN 978-0-07-085535-9.

[1]