Алгоритмы отсечения отрезков

метод Д. Коэна и А. Сазерленда. В этом методе для определения той из девяти областей, которой принадлежит конец ребра, вводится четырехразрядный (битовый) код. Коды этих областей показаны на рис.

Крайний правый бит кода считается первым. В соответствующий бит заносится 1 при выполнении следующих условий:

· для первого бита - если точка левее окна

· для второго бита - если точка правее окна

· для третьего бита - если точка ниже окна

· для четвертого бита -если точка выше окна

В противном случае в бит заносится нуль. Отсюда, очевидно, следует, что если коды обоих концов ребра равны нулю, то обе эти точки лежат внутри окна, и отрезок видимый. Коды концевых точек можно использовать также и для тривиального отбрасывания полностью невидимых отрезков. Если побитовое логическое произведение кодов концевых точек отрезка не равно нулю, то отрезок полностью невидим и его можно отбросить тривиально. Однако если логическое произведение равно нулю, то отрезок может оказаться целиком или частично видимым или даже целиком невидимым. Для решения этой проблемы Коэн и Сазерленд предложили заменять конечную точку с ненулевым кодом конца на точку, лежащую на стороне окна, либо на ее продолжении.

В целом схема алгоритма Коэна-Сазерленда следующая:

1. Рассчитать коды конечных точек отсекаемого отрезка.

В цикле повторять пункты 2-6:

2. Если логическое И кодов конечных точек не равно 0, то отрезок целиком вне окна. Он отбрасывается и отсечение закончено.

3. Если оба кода равны 0, то отрезок целиком видим. Он принимается и отсечение закончено.

4. Если начальная точка внутри окна, то она меняется местами с конечной точкой.

5. Анализируется код начальной точки для определения стороны окна с которой есть пересечение и выполняется расчет пересечения. При этом вычисленная точка пересечения заменяет начальную точку.

6. Определение нового кода начальной точки.

В приведенном алгоритме требуется вычислить пересечение отрезка со стороной окна. Алгоритм разбиения средней точкой позволяет избежать непосредственного вычисления. Этот алгоритм отсечения реализует двоичный поиск пересечения путем деления отрезка его средней точкой. Идея этого алгоритма была предложена Спруллом и Сазерлендом в 1968г. для аппаратной реализации. Программная реализация этого алгоритма медленнее, чем реализация предыдущего алгоритма, аппаратная - быстрее и эффективнее, поскольку можно использовать параллельную архитектуру. Кроме того, аппаратные сложения и деления на 2 очень быстры (деление на 2 аппаратно эквивалентно сдвигу каждого бита вправо). Затем те же проверки применяются к каждой из половин до тех пор, пока не будет обнаружено пересечение со стороной окна или длина разделяемого отрезка не станет пренебрежимо малой, т.е. пока он не выродится в точку. После вырождения определяется видимость полученной точки. Максимальное число разбиений пропорционально точности задания координат концевых точек отрезка.