Двумерное параметрическое отсечение. Отсечение средней точкой

В алгоритме Сазерленда-Коэна требовалось вычислить пересечение отрезка со стороной окна. Можно избежать непосредственного вычисления, если реализовать двоичный поиск такого пересечения путем деления отрезка его средней точкой. Программная реализация этого алгоритма медленнее, чем реализация алгоритма Сазерленда-Коэна. Аппаратная же реализация быстрее и эффективнее, поскольку аппаратные умножения и деления на 2 очень быстры. Деление на 2 аппаратно эквивалентно сдвигу каждого бита вправо.

В алгоритме используются коды концевых точек отрезка и проверки, выявляющие полную видимость и тривиальную невидимость отрезков. Те отрезки, которые только с помощью таких простых проверок нельзя отнести к одной из двух категорий, разбиваются на две равные части. Затем те же проверки применяются к каждой из половин до тех пор, пока не будет обнаружено пересечение со стороной окна или длина разделяемого отрезка не станет пренебрежимо малой, т. е. пока он не выродится в точку. После вырождения определяется видимость полученной точки. В результате процесс обнаружения пересечения сводится к двоичному поиску. Максимальное число разбиений пропорционально точности задания координат концевых точек отрезка.

Данный алгоритм можно формально разбить на три этапа: Для каждой концевой точки отрезка: 1. Если концевая точка видима, то она будет наиболее удаленной видимой точкой. Процесс завершен. Иначе - продолжить. 2. Если отрезок тривиально характеризуется как невидимый, то выходная информация не формируется. Процесс завершен. Иначе - продолжить. 3. Грубо оценить наиболее удаленную видимую точку путем деления отрезка Р₁Р₂ средней точкой Р_m. Применить вышеизложенные тесты к двум кускам Р₁Р_m и Р_mР₂. Если Р_mР₂ тривиально отвергается как невидимый, то средняя точка дает верхнюю оценку для наиболее удаленной видимой точки. Продолжить процедуру с отрезком P₁Р_m. Иначе - средняя точка дает оценку снизу для наиболее удаленной видимой точки. Продолжить процедуру с куском Р₂Р_m. Если отрезок становится настолько мал, что его средняя точка совпадает с его концами с машинной или наперед заданной точностью, то надо оценить ее видимость и закончить процесс. Конкретный пример лучше проиллюстрирует этот алгоритм.

Двумерный алгоритм Лианга-Барски

В 1982 г. Лианг и Барски предложили алгоритмы отсечения прямоугольным окном с использованием параметрического представления для двух, трех и четырехмерного отсечения.

Продолжим каждую из четырех границ окна до бесконечных прямых. Каждая из таких прямых делит плоскость на 2 области. Назовем "видимой частью" ту, в которой находится окно отсечения.Пусть конечные точки отрезка есть V₀ и V₁ с координатами (x0,y0) и (x1,y1), соответственно. Тогда параметрическое представление линии может быть задано следующим образом:

Или в общем виде для отрезка, заданного точками V₀ и V₁: V(t)    =   V₀   +  (V₁   -  V₀)   ·  t

Для точек V₀ и V₁ параметр t равен 0 и 1, соответственно. Меняя t от 0 до 1 перемещаемся по отрезку V₀V₁ от точки V₀ к точке V₁. Изменяя t в интервале от -∞ до +∞, получаем бесконечную (далее удлиненную) прямую, ориентация которой - от точки V₀ к точке V₁.

Подставляя параметрическое представление, заданное уравнениями, в неравенства, получим следующие соотношения для частей удлиненной линии, которая находится в окне отсечения:

-dx·t ≤ x0   -  Xлев и dx·t ≤ Xправ   -  x0,

-dy·t ≤ y0   -  Yниз и dy·t ≤ Yверх   -  y0.

Заметим, что в этих соотношениях - неравенства, описывающие внутреннюю часть окна отсечения, в то время как равенства определяют его границы. Рассматривая неравенства, они имеют одинаковую форму вида: P_i·t    ≤   Q_i       для   i   = 1,2,3,4.

Тогда каждое неравенство задает диапазон значений параметра t, для которых эта удлиненная линия находится на видимой стороне соответствующей линии границы. Более того, конкретное значение параметра t для точки пересечения есть t = Q_i/P_i. Причем знак Q_i показывает на какой стороне соответствующей линии границы находится точка V₀. А именно, если Qi ≥ 0, тогда V₀ находится на видимой стороне линии границы, включая и ее. Если же Q_i    <   0, тогда V₀ находится на невидимой стороне. Ясно, что любое P_i может быть меньше 0, больше 0 и равно 0.