Cohen-Sutherlands algoritme

Cohen–Sutherlands algoritme er en datagrafikk-algoritme som brukes for linjeklipping. Algoritmen deler et todimensjonalt område inn i ni regioner (eller et tredimensjonalt område inn i 27 regioner), og avgjør så på en effektiv måte hvilke linjer og linjesegmenter som er synlige i den midterste regionen (skjermporten).

Algoritmen ble utviklet i 1967, under arbeid med en flysimulator, av Danny Cohen og Ivan Sutherland.^[1]

Algoritmen rediger

Algoritmen inkluderer, ekskluderer, eller delvis inkluderer en linje basert på om:

Begge endepunktene er inne i skjermportregionen (bitvis OR av endepunktene == 0): trivielt akseptert.
Begge endepunktene er å finne i minst en ikke-synlig region, som tilsier at linja ikke krysser den synlige regionen. (bitvis AND av endepunktene != 0): trivielt forkastet.
Begge endepunktene er å finne i forskjellige regioner: I denne ikke-trivielle situasjonen finner algoritmen ett av endepunktene som er utenfor skjermporten (det vil gjelde minst ett av endepunktene). Krysningen mellom linjen fra dette punktet, og skjermportregionen regnes så ut (for eksempel med den parametriske likningen for en linje), og dette krysningspunktet erstatter nå det valgte punktet. Algoritmen gjentar denne prosedyren helt til linjen enten kan trivielt aksepteres, eller trivielt forkastes.

Tallene i figuren under kalles utkoder. En utkode regnes ut for hvert av de to endepunktene i en linje. Utkodene vil ha en størrelse på fire bit for todimensjonal klipping, eller seks bit for tredimensjonal klipping. Den første biten settes til 1 hvis punktet ligger over skjermporten. Bitene for 2D-utkoder representerer: Topp, bunn, høyre og venstre. For eksempel vil utkode 1010 representere et punkt som ligger i region over og til høyre for skjermporten.

1001	1000	1010
0001	0000	0010
0101	0100	0110

Cohen–Sutherlands algorithme kan kun brukes på rektangulære klippevinduer. For klippevinduer av andre konvekse polygoner, bruk Cyrus–Beck sin algoritme.

Eksempel på C/C++ implementasjon rediger

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

// Regn ut bitkode for et punkt (x, y) ved bruk av klipperektangelet
// avgrenset diagonalt av (xmin, ymin), og (xmax, ymax)

// REGN MED AT xmax, xmin, ymax og ymin er globale konstanter.

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

	code = INSIDE;          // settes som utgangspunkt inni klippevinduet

	if (x < xmin)           // til venstre for klippevinduet
		code |= LEFT;
	else if (x > xmax)      // til høyre for klippevinduet
		code |= RIGHT;
	if (y < ymin)           // under klippevinduet
		code |= BOTTOM;
	else if (y > ymax)      // over klippevinduet
		code |= TOP;

	return code;
}

// Cohen–Sutherland linjeklippingsalgoritme klipper linjer fra
// P0 = (x0, y0) til P1 = (x1, y1) mot et rektangel med 
// diagonal fra (xmin, ymin) til (xmax, ymax).
void CohenSutherlandLineClipAndDraw(double x0, double y0, double x1, double y1)
{
	// regn ut utkoder for P0, P1, og ev. punkter som ligger utenfor klipperektangelet
	OutCode outcode0 = ComputeOutCode(x0, y0);
	OutCode outcode1 = ComputeOutCode(x1, y1);
	bool accept = false;

	while (true) {
		if (!(outcode0 | outcode1)) { // Bitvis OR er 0. Trivielt akseptert, gå ut av løkken
			accept = true;
			break;
		} else if (outcode0 & outcode1) { // Bitvis AND er ulik 0. Trivielt forkastet, gå ut av løkken
			break;
		} else {
			// feilet begge tester, så regn ut nytt linjesegment
			// fra utsiden til krysningspunkt med kanten til klipprektangelet
			double x, y;

			// Minst ett endepunkt ligger utenfor klipperektangelet; velg det.
			OutCode outcodeOut = outcode0 ? outcode0 : outcode1;

			// Finn så krysningspunktet;
			// bruk formel y = y0 + slope * (x - x0), x = x0 + (1 / slope) * (y - y0)
			if (outcodeOut & TOP) {           // punktet er over klipperektangelet
				x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
				y = ymax;
			} else if (outcodeOut & BOTTOM) { // punktet er under klipperektangelet
				x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
				y = ymin;
			} else if (outcodeOut & RIGHT) {  // punktet er til høyre for klipperektangelet
				y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
				x = xmax;
			} else if (outcodeOut & LEFT) {   // punktet er til venstre for klipperektangelet
				y = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);
				x = xmin;
			}

			// Nå flyttes punktet på utsiden inn til krysningspunktet for å klippe
			// og klargjøre for neste utregning.
			if (outcodeOut == outcode0) {
				x0 = x;
				y0 = y;
				outcode0 = ComputeOutCode(x0, y0);
			} else {
				x1 = x;
				y1 = y;
				outcode1 = ComputeOutCode(x1, y1);
			}
		}
	}
	if (accept) {
               // Følgende funksjoner er utelatt, og må implementeres basert
               // på brukerens plattform (OpenGL/graphics.h osv.)
               DrawRectangle(xmin, ymin, xmax, ymax);
               LineSegment(x0, y0, x1, y1);
	}
}

Merknader rediger

^ Principles of Interactive Computer Graphics p.124 and p.252, by Bob Sproull and William M. Newman, 1973, McGraw–Hill Education, International edition, ISBN 0-07-085535-8

Se også rediger

Andre algoritmer som brukes til samme formål:

Referanser rediger

James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. s. 113.

Eksterne lenker rediger

[Sproull-1] Principles of Interactive Computer Graphics p.124 and p.252, by Bob Sproull and William M. Newman, 1973, McGraw–Hill Education, International edition, ISBN 0-07-085535-8

[1]