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

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

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

Алгоритм

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

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

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

оставилицентральныйверно
верх100110001010
центральный000100000010
Нижний010101000110

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

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

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

typedef int OutCode;const int ВНУТРИ = 0; // 0000const int ОСТАВИЛИ = 1;   // 0001const int ВЕРНО = 2;  // 0010const int НИЖНИЙ = 4; // 0100const int ВЕРХ = 8;    // 1000// Вычислить битовый код для точки (x, y) с помощью клипа// по диагонали ограничены (xmin, ymin) и (xmax, ymax)// ПРИНЯТЬ, ЧТО xmax, xmin, ymax и ymin - глобальные константы.OutCode ComputeOutCode(двойной Икс, двойной у){	OutCode код;	код = ВНУТРИ;          // инициализируется как находящийся внутри [[окна клипа]]	если (Икс < xmin)           // слева от окна клипа		код |= ОСТАВИЛИ;	еще если (Икс > xmax)      // справа от окна клипа		код |= ВЕРНО;	если (у < ymin)           // под окном клипа		код |= НИЖНИЙ;	еще если (у > ymax)      // над окном клипа		код |= ВЕРХ;	возвращаться код;}// Алгоритм отсечения Коэна – Сазерленда отсекает строку из// P0 = (x0, y0) to P1 = (x1, y1) против прямоугольника с // диагональ от (xmin, ymin) до (xmax, ymax).пустота КоэнСазерлендLineClipAndDraw(двойной x0, двойной y0, двойной x1, двойной y1){	// вычисляем исходящие коды для P0, P1 и любой точки, лежащей за пределами прямоугольника отсечения	OutCode outcode0 = ComputeOutCode(x0, y0);	OutCode outcode1 = ComputeOutCode(x1, y1);	bool принимать = ложный;	пока (истинный) {		если (!(outcode0 | outcode1)) {			// побитовое ИЛИ равно 0: обе точки внутри окна; тривиально принять и выйти из цикла			принимать = истинный;			перемена;		} еще если (outcode0 & outcode1) {			// побитовое И не равно 0: обе точки разделяют внешнюю зону (LEFT, RIGHT, TOP,			// или ВНИЗ), поэтому оба должны находиться за пределами окна; цикл выхода (accept - false)			перемена;		} еще {			// провалили оба теста, поэтому рассчитываем отрезок линии для обрезки			// от внешней точки до пересечения с краем обрезки			двойной Икс, у;			// По крайней мере одна конечная точка находится за пределами прямоугольника отсечения; возьми.			OutCode outcodeOut = outcode1 > outcode0 ? outcode1 : outcode0;			// Теперь находим точку пересечения;			// используем формулы:			// наклон = (y1 - y0) / (x1 - x0)			// x = x0 + (1 / slope) * (ym - y0), где ym - это ymin или ymax			// y = y0 + slope * (xm - x0), где xm - это xmin или xmax			// Не нужно беспокоиться о делении на ноль, потому что в каждом случае			// проверяемый бит outcode гарантирует, что знаменатель ненулевой			если (outcodeOut & ВЕРХ) {           // точка находится над окном клипа				Икс = x0 + (x1 - x0) * (ymax - y0) / (y1 - y0);				у = ymax;			} еще если (outcodeOut & НИЖНИЙ) { // точка ниже окна клипа				Икс = x0 + (x1 - x0) * (ymin - y0) / (y1 - y0);				у = ymin;			} еще если (outcodeOut & ВЕРНО) {  // точка находится справа от окна клипа				у = y0 + (y1 - y0) * (xmax - x0) / (x1 - x0);				Икс = xmax;			} еще если (outcodeOut & ОСТАВИЛИ) {   // точка находится слева от окна клипа				у = y0 + (y1 - y0) * (xmin - x0) / (x1 - x0);				Икс = xmin;			}			// Теперь перемещаем внешнюю точку в точку пересечения для обрезки			// и готовимся к следующему проходу.			если (outcodeOut == outcode0) {				x0 = Икс;				y0 = у;				outcode0 = ComputeOutCode(x0, y0);			} еще {				x1 = Икс;				y1 = у;				outcode1 = ComputeOutCode(x1, y1);			}		}	}}

Примечания

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

Смотрите также

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

Рекомендации

внешняя ссылка