Френсис Хилл

Рис. 3.14. Отсечение прямых границами окна Существует много возможных расположений отрезка прямой по отношению к окну. Этот отрезок может находиться слева, справа, над и под окном; он может пересекать любую границу окна (или две) и т. д. Поэтому нам необходим систематизированный и эффективный метод, который идентифицировал бы существующую ситуацию и вычислял бы новые концевые точки для отсеченного отрезка. Эффективность здесь важна, поскольку в типичном изображении содержатся тысячи отрезков прямой, каждый из которых необходимо отсекать границами окна. Алгоритм Кохена-Сазерленда применяет к задаче быстрый метод «разделения» («divide-and-conquer» - разделяй и властвуй). Другие методы отсечения будут обсуждаться в главе 4.

3.3.2. Алгоритм отсечения Кохена-Сазерленда Алгоритм Кохена-Сазерленда быстро выявляет и отбрасывает два распространенных случая, называемых «тривиальный прием» («trivial accept*) и «тривиальное отклонение» («trivial reject*). Как показано на рис. 3.15, обе концевые точки отрезка АВ расположены внутри окна W, и поэтому весь отрезок АВ должен располагаться внутри W. Следовательно, отрезок АВ может быть тривиально принят: он не нуждается в отсечении. Такая ситуация часто возникает при использовании большого окна, охватывающего большинство отрезков прямых. С другой стороны, обе концевые точки С и D лежат целиком по одну сторону от окна W, поэтому отрезок CD должен располагаться целиком вне W. Следовательно, CD тривиально отклоняется и не рисуется ничего. Такая ситуация часто возникает, когда маленькое окно используется для плотного изображения, многие из отрезков которого находятся вне этого окна.

Френсис Хилл

Рис. 3.15. Тривиальные прием или отклонение отрезка прямой Проверка на тривиальный прием и тривиальное отклонение Мы хотим быстро выявлять такие случаи, когда отрезок прямой может быть тривиально принят или тривиально отклонен. С целью облегчения этой задачи для каждой концевой точки отрезка вычисляется «кодовое слово внутри/вне» («inside-outside code word»). Рисунок 3.16 показывает, как происходит


⇐ Предыдущая| |Следующая ⇒