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

В компьютерной графике алгоритм Коэна-Сазерленда представляет собой алгоритм, используемый для отсечения строк . Алгоритм делит двумерное пространство на 9 областей, а затем эффективно определяет линии и части линий, которые видны в центральной интересующей области (области просмотра ).

Алгоритм был разработан в 1967 году во время на авиасимуляторе работы Дэнни Коэном и Иваном Сазерлендом . ^{[ 1 ]}

Алгоритм

Алгоритм включает, исключает или частично включает строку в зависимости от того,:

Обе конечные точки находятся в области просмотра (побитовое ИЛИ конечных точек = 0000): тривиальный метод Accept .
Обе конечные точки имеют по крайней мере одну невидимую область, что означает, что линия не пересекает видимую область. (побитовое И конечных точек ≠ 0000): тривиальное отклонение .
Обе конечные точки находятся в разных регионах: в случае этой нетривиальной ситуации алгоритм находит одну из двух точек, находящуюся за пределами области просмотра (внешне будет хотя бы одна точка). Затем рассчитывается пересечение конечной точки и расширенной границы области просмотра (т. е. с помощью параметрического уравнения для линии), и эта новая точка заменяет конечную точку. Алгоритм повторяется до тех пор, пока не произойдет тривиальное принятие или отклонение.

Числа на рисунке ниже называются исходящими кодами . Выходной код вычисляется для каждой из двух точек линии. Выходной код будет иметь 4 бита для двумерного отсечения или 6 бит в трехмерном случае. Первый бит устанавливается в 1, если точка находится над областью просмотра. Биты в 2D-коде представляют: верх, низ, право, лево. Например, исходящий код 1010 представляет точку, которая находится в правом верхнем углу области просмотра.

	левый	центральный	верно
вершина	1001	1000	1010
центральный	0001	0000	0010
нижний	0101	0100	0110

Обратите внимание, что выходные коды для конечных точек необходимо пересчитывать на каждой итерации после обрезки.

Алгоритм Коэна-Сазерленда можно использовать только в прямоугольном окне клипа .

Пример реализации C/C++

typedef int OutCode;

const int INSIDE = 0b0000;
const int LEFT   = 0b0001;
const int RIGHT  = 0b0010;
const int BOTTOM = 0b0100;
const int TOP    = 0b1000;

// 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 = 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).
bool CohenSutherlandLineClip(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: both points inside window; trivially accept and exit loop
			accept = true;
			break;
		} else if (outcode0 & outcode1) {
			// bitwise AND is not 0: both points share an outside zone (LEFT, RIGHT, TOP,
			// or BOTTOM), so both must be outside window; exit loop (accept is false)
			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 = outcode1 > outcode0 ? outcode1 : outcode0;

			// Now find the intersection point;
			// use formulas:
			//   slope = (y1 - y0) / (x1 - x0)
			//   x = x0 + (1 / slope) * (ym - y0), where ym is ymin or ymax
			//   y = y0 + slope * (xm - x0), where xm is xmin or xmax
			// No need to worry about divide-by-zero because, in each case, the
			// outcode bit being tested guarantees the denominator is non-zero
			if (outcodeOut & TOP) {           // point is above the clip window
				x = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);
				y = ymax;
			} else if (outcodeOut & BOTTOM) { // point is below the clip window
				x = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);
				y = ymin;
			} else if (outcodeOut & RIGHT) {  // point is to the right of clip window
				y = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);
				x = xmax;
			} else if (outcodeOut & LEFT) {   // point is to the left of clip window
				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);
			}
		}
	}
	return accept;
}

Примечания

^ Принципы интерактивной компьютерной графики , с. 124, 252, Боб Спроулл и Уильям М. Ньюман, 1973, McGraw – Hill Education, международное издание, ISBN 0-07-085535-8 .

См. также

Алгоритмы, используемые для той же цели:

Ссылки

Джеймс Д. Фоли. Компьютерная графика: принципы и практика . Аддисон-Уэсли Профессионал, 1996. с. 113.

Внешние ссылки

[Sproull-1] Принципы интерактивной компьютерной графики , с. 124, 252, Боб Спроулл и Уильям М. Ньюман, 1973, McGraw – Hill Education, международное издание, ISBN 0-07-085535-8 .

[ 1 ]