Алгоритм Коэна-Сазерленда является компьютерная графика- алгоритм , используемый для линии отсечения . Алгоритм делит двумерное пространство на 9 областей, а затем эффективно определяет линии и части линий, которые видны в центральной области интереса (области просмотра).
Алгоритм был разработан в 1967 году во время работы на авиасимуляторе Дэнни Коэном и Иваном Сазерлендом . [1]
Алгоритм [ править ]
Алгоритм включает, исключает или частично включает строку в зависимости от того,:
- Обе конечные точки находятся в области области просмотра (поразрядное ИЛИ конечных точек = 00): тривиальное принятие .
- Обе конечные точки имеют по крайней мере одну невидимую область, что означает, что линия не пересекает видимую область. (побитовое И конечных точек ≠ 0): тривиальный отказ .
- Обе конечные точки находятся в разных регионах: в случае этой нетривиальной ситуации алгоритм находит одну из двух точек, которая находится за пределами области просмотра (снаружи будет хотя бы одна точка). Затем вычисляется пересечение внешней точки и границы расширенного окна просмотра (т.е. с параметрическим уравнением для линии), и эта новая точка заменяет конечную точку. Алгоритм повторяется до тех пор, пока не произойдет банальное принятие или отклонение.
Цифры на рисунке ниже называются исходящими кодами . Исходящий код вычисляется для каждой из двух точек в строке. В исходящем коде будет 4 бита для двумерного отсечения или 6 бит в трехмерном случае. Первый бит устанавливается в 1, если точка находится над окном просмотра. Биты в двухмерном исходящем коде представляют: верх, низ, правый, левый. Например, выходной код 1010 представляет точку в правом верхнем углу окна просмотра.
оставил центральный верно вершина 1001 1000 1010 центральный 0001 0000 0010 Нижний 0101 0100 0110
Обратите внимание, что исходящие коды для конечных точек должны пересчитываться на каждой итерации после того, как происходит отсечение.
Алгоритм Коэна – Сазерленда можно использовать только для прямоугольного окна отсечения .
Пример реализации C / C ++ [ править ]
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// Вычислить битовый код для точки (x, y) с использованием клипа, // ограниченного по диагонали (xmin, ymin) и (xmax, ymax)// ПРИНЯТЬ, ЧТО xmax, xmin, ymax и ymin - глобальные константы.OutCode ComputeOutCode ( двойной x , двойной y ) { код OutCode ;код = ВНУТРИ ; // инициализируется как находящийся внутри [[окна клипа]]if ( x < xmin ) // слева от кода окна клипа | = LEFT ; else if ( x > xmax ) // справа от кода окна клипа | = RIGHT ; if ( y < ymin ) // код ниже окна клипа | = BOTTOM ; else if ( y > ymax ) // над кодом окна клипа | = TOP ; код возврата ; }// Алгоритм отсечения Коэна – Сазерленда обрезает линию от // P0 = (x0, y0) до P1 = (x1, y1) по прямоугольнику с диагональю // от (xmin, ymin) до (xmax, ymax). void CohenSutherlandLineClipAndDraw ( double x0 , double y0 , double x1 , double y1 ) { // вычисляем исходящие коды для P0, P1 и любой точки, лежащей за пределами прямоугольника клипа OutCode outcode0 = ComputeOutCode ( x0 , y0 ); OutCode outcode1 = ComputeOutCode ( x1 , y1 ); bool accept = false ;while ( true ) { if ( ! ( outcode0 | outcode1 )) { // побитовое ИЛИ равно 0: обе точки внутри окна; тривиально принять и выйти из цикла accept = true ; перерыв ; } else if ( outcode0 & outcode1 ) { // побитовое И не равно 0: обе точки разделяют внешнюю зону ( ЛЕВАЯ, ПРАВАЯ, ВЕРХНЯЯ , // или НИЖНЯЯ), поэтому обе должны находиться за пределами окна; цикл выхода (accept - ложь) break ; } else {// провалили оба теста, поэтому вычисляем отрезок линии для обрезки // от внешней точки до пересечения с краем обрезки double x , y ;// По крайней мере одна конечная точка находится за пределами прямоугольника отсечения; возьми это. OutCode outcodeOut = outcode1 > outcode0 ? outcode1 : outcode0 ;// Теперь находим точку пересечения; // использовать формулы: // slope = (y1 - y0) / (x1 - x0) // x = x0 + (1 / slope) * (ym - y0), где ym равно ymin или ymax // y = y0 + slope * (xm - x0), где xm равно xmin или xmax // Не нужно беспокоиться о делении на ноль, потому что в каждом случае проверяемый // бит исходящего кода гарантирует, что знаменатель не равен нулю if ( outcodeOut & TOP ) { // точка находится над окном отсечения x = x0 + ( x1 - x0 ) * ( ymax - y0 ) / ( y1 - y0 ); y = ymax ; } else if ( outcodeOut & BOTTOM ) { // точка находится ниже окна клипа x = x0 + ( x1 - x0 ) * ( ymin - y0 ) / ( y1 - y0 ); y = ymin ; } else if ( outcodeOut & RIGHT ) { // точка находится справа от окна клипа y = y0 + ( y1 - y0 ) * ( xmax - x0 ) / ( x1 - x0 ); х = хмакс ; } else if ( outcodeOut & LEFT ) { // точка находится слева от окна клипа y = y0 + ( y1 - y0 ) * ( xmin - x0 ) / ( x1 - x0 ); Икс = xmin ; }// Теперь мы перемещаем внешнюю точку в точку пересечения, // чтобы обрезать и готовимся к следующему проходу. если ( outcodeOut == outcode0 ) { x0 = x ; y0 = y ; outcode0 = ComputeOutCode ( x0 , y0 ); } иначе { x1 = x ; y1 = y ; outcode1 = ComputeOutCode ( x1 , y1 ); } } } }Заметки [ править ]
- ^ Принципы интерактивной компьютерной графики , стр. 124, 252, Боб Спроул и Уильям М. Ньюман, 1973, McGraw – Hill Education, международное издание, ISBN 0-07-085535-8 .
См. Также [ править ]
Алгоритмы, используемые с той же целью:
Ссылки [ править ]
- Джеймс Д. Фоули. Компьютерная графика: принципы и практика . Addison-Wesley Professional, 1996. стр. 113.
Внешние ссылки [ править ]
