Этот алгоритм позволяет быстро выявить отрезки, которые могут быть или приняты или отброшены целиком. Вычисление пересечений требуется когда отрезок не попадает ни в один из этих классов. Этот алгоритм особенно эффективен в двух крайних случаях: большинство примитивов содержится целиком в большом окне, большинство примитивов лежит целиком вне относительно маленького окна. Идея алгоритма состоит в следующем: Окно отсечения и прилегающие к нему части плоскости вместе образуют 9 областей (рис. 0.2.3). Каждой из областей присвоен 4-х разрядный код. Две конечные точки отрезка получают 4-х разрядные коды, соответствующие областям, в которые они попали. Смысл разрядов кода: 1 рр = 1 - точка над верхним краем окна; 2 рр = 1 - точка под нижним краем окна; 3 рр = 1 - точка справа от правого края окна; 4 рр = 1 - точка слева от левого края окна. Определение того лежит ли отрезок целиком внутри окна или целиком вне окна выполняется следующим образом: если коды обоих концов отрезка равны 0 то отрезок целиком внутри окна, отсечение не нужно, отрезок принимается как тривиально видимый (отрезок AB на рис. 0.2.3); если логическое & кодов обоих концов отрезка не равно нулю, то отрезок целиком вне окна, отсечение не нужно, отрезок отбрасывается как тривиально невидимый (отрезок KL на рис. 0.2.3); если логическое & кодов обоих концов отрезка равно нулю, то отрезок подозрительный, он может быть частично видимым (отрезки CD, EF, GH) или целиком невидимым (отрезок IJ); для него нужно определить координаты пересечений со сторонами окна и для каждой полученной части определить тривиальную видимость или невидимость. При этом для отрезков CD и IJ потребуется вычисление одного пересечения, для остальных (EF и GH) - двух. При расчете пересечения используется горизонтальность либо вертикальность сторон окна, что позволяет определить координату X или Y точки пересечения без вычислений. Рис. 0.2.3: Отсечение по методу Коэна-Сазерленда При непосредственном использовании описанного выше способа отбора целиком видимого или целиком невидимого отрезка после расчета пересечения потребовалось бы вычисление кода расположения точки пересечения. Для примера рассмотрим отрезок CD. Точка пересечения обозначена как P. В силу того, что граница окна считается принадлежащей окну, то можно просто принять только часть отрезка PD, попавшую в окно. Часть же отрезка CP, на самом деле оказавшаяся вне окна, потребует дальнейшего рассмотрения, так как логическое И кодов точек C и P даст 0, т.е. отрезок CP нельзя просто отбросить. Для решения этой проблемы Коэн и Сазерленд предложили заменять конечную точку с ненулевым кодом конца на точку, лежащую на стороне окна, либо на ее продолжении. В целом схема алгоритма Коэна-Сазерленда следующая: Рассчитать коды конечных точек отсекаемого отрезка. В цикле повторять пункты 2-6: Если логическое И кодов конечных точек не равно 0, то отрезок целиком вне окна. Он отбрасывается и отсечение закончено. Если оба кода равны 0, то отрезок целиком видим. Он принимается и отсечение закончено. Если начальная точка внутри окна, то она меняется местами с конечной точкой. Анализируется код начальной точки для определения стороны окна с которой есть пересечение и выполняется расчет пересечения. При этом вычисленная точка пересечения заменяет начальную точку. Определение нового кода начальной точки. Эта схема реализована в процедуре V_CSclip, приведенной в Приложении 7.  8  Комментарии к статье  8 8  Обсудить в чате