КГ Лекция 10. Отсечение отрезка. Алгоритмы Сазерленда Коэна и разбиения средней точкой
Алгоритм Сазерленда-Коэна, как и в предыдущем случае, предусматривает нахождение точек пересечения отрезка со сторонами окна прямоугольной формы. Однако здесь не производится проверка корректности найденных точек пересечения. Найденная точка пересечения разбивает отрезок на две части: полностью невидимую относительно очередной стороны отсекателя и видимую часть. Невидимой будет та часть отрезка, которая заключена от вершины отрезка, невидимой относительно текущей стороны окна, до точки пересечения. Этот факт используется в алгоритме для определения части отрезка, подлежащей отсечению. Это связано с тем, что точка, попадающая на ребро отсекателя, имеет нулевой код (она считается видимой), поэтому попарное логическое произведение кодов концов будет равно нулю.
В алгоритме предусматривается предварительный анализ сумм кодов концов отрезка и попарных логических произведений этих кодов с целью определения тривиально видимых и тривиально невидимых отрезков.
Если отрезок не является ни тривиально видимым, ни тривиально невидимым, то производится собственно его отсечение. При этом предполагается, что невидимой относительно каждого ребра должна быть первая вершина отрезка. Поэтому в случае необходимости вершины меняются местами. Следует отметить, что одновременно обе вершины не могут быть невидимыми относительно одного текущего ребра отсекателя, так как этот факт позволил бы на предварительном этапе отбросить отрезок как тривиально невидимый.
Для каждой стороны окна выполнить:
- Для каждого отрезка P1P2 определить, не является ли он полностью видимым или может быть тривиально отвергнут как невидимый.
- Если P1 вне окна, то продолжить выполнение, иначе поменять P1 и P2 местами.
- Заменить P1 на точку пересечения P1P2 со стороной окна.
Для удобства работы данные, задающие отсекатель, заносятся в массив "окно" O(4), в котором O1=Xл, O2=Xп, O3=Yн, O4=Yв. Отсечение производится в определенном порядке: левой, правой, нижней, верхней границами отсекателя. Поэтому для отыскания точек пересечения в выражения следует на i-ом шаге подставлять i-ые элементы массива O. Такое задание исходных данных позволяет для горизонтального отрезка не проводить третий и четвертый этапы, а для вертикального отрезка - первый и второй этапы.
В алгоритме используется признак (флаг) Fl, определяющий расположение отрезка:
- Fl =-1 - отрезок вертикальный,
- Fl = 0 - общего положения,
- Fl = 1 - горизонтальный.
1. Ввод координат отсекателя
Xл (O1), Xп (O2), Yн (O3), Yв (O4).
2. Ввод координат концов отрезка
P1(X1,Y1), P2(X 2,Y2).
3. Установка начального значения флага Fl = 0.
4. Проверка вертикальности отрезка:
если P2.x-P1.x=0 (вертикальный), то Fl = -1,
иначе вычислить тангенс угла наклона отрезка
m = (P2.y - P1.y)/(P2.x - P1.x).
5. Проверка горизонтальности отрезка: если m=0, то Fl=1.
6. Начало цикла по i от 1 до 4 отсечения отрезка по всем четырем сторонам отсекателя.
7. Обращение к алгоритму (подпрограмме) определения видимости отрезка P1P2 относительно заданного окна.
Подпрограмма возвращает признак pr, принимающий следующие значения:
pr = 1 - отрезок видимый;
pr = -1 - отрезок полностью невидимый;
pr = 0 - отрезок может быть частично видимым.
8. Анализ полученного признака видимости:
если pr= -1, то переход к п. 20;
если pr=1, то переход к п. 19.
9. Проверка видимости обеих вершин отрезка относительно текущей i-ой стороны окна:
если T1i=T2i, то переход к п.18.
10. Проверка видимости первой вершины:
если T1i=0 (вершина видима), то обмен местами вершин:
R = P1;
P1 = P2;
P2 = R.
11. Проверка вертикальности отрезка:
если Fl = -1, то переход к п. 14.
12. Анализ номера шага отсечения: если i >= 3, то переход к п. 14.
13. Вычисление координат точки пересечения с i-ым ребром отсекателя (левым или правым):
P1.y = m(Oi-P1.x) + P1.y;
P1.x = Oi.
Переход к п. 18.
14. Проверка горизонтальности отрезка:
если Fl=1, то переход к п. 18.
15. Проверка вертикальности отрезка:
если Fl=-1, то переход к п.17.
16. Вычисление абсциссы точки пересечения отрезка общего положения со стороной отсекателя
(верхней или нижней):
P1.x = (Oi-P1.y) / m + P1.x .
17. Присвоение ординате вершины отрезка ординаты стороны отсекателя:
P1.y = Oi .
18. Конец цикла по i (вычисление нового значения параметра цикла i=i+1,
анализ его значения и переход на повторное выполнение цикла или выход из цикла).
19. Вычерчивание отрезка P1P2.
20. Конец.
Алгоритм определения видимости отрезка относительно окна можно представить следующим образом:
1. Вычисление кодов первой вершины отрезка T1.
2. Вычисление кодов второй вершины отрезка T2.
3. Вычисление суммы кодов первой вершины S1.
4. Вычисление суммы кодов второй вершины S2.
5. Определение полной видимости отрезка: если (S1=0)&(S2=0)=истина, то pr =1 и переход к п. 8.
6. Вычисление попарного логического произведения кодов концов отрезка p.
7. Определение полной невидимости отрезка:
если p=1, то pr= -1,
иначе pr=0.
8. Конец.
Логическую сумму можно вычислить или как арифметическую или как логическую сумму.
Если одна из сумм кодов концов отрезка равна нулю, а вторая отлична от нуля, то отрезок частично видимый ((S1 == 0 и S2 <> 0) или (S1 <> 0 и S2 == 0)). Если обе суммы ненулевые, то отрезок в действительности может оказаться частично видимым или полностью невидимым. Для распознавания части полностью невидимых отрезков можно использовать логическое произведение кодов концов отрезка: P = T1(1) * T2(1) + T1(2) * T2(2) + T1(3) * T2(3) + T1(4) * T2(4)
Если P <> 0, то отрезок невидимый.
На очередном шаге выполнения алгоритма мы должны проверить i-ые разряды кодов для первой и второй вершины. Если они равны, то переход на следующий шаг выполнения цикла.
Логика здесь следующая: если одноименные биты коды концов отрезка равны, то мы считаем, что они могут равняться только нулю, т. е. обе вершины располагаются по видимую сторону по видимую сторону от текущей i-ой границы отсекателя, точки пересечения нет, нужно переходить на следующий шаг. Мы считаем, что они не могут одновременно равняться единице. Равенство одноименных разрядов кодов двух концов отрезка единице означает, что обе вершины лежат по невидимую сторону от текущей границы и означает тривиальную невидимость отрезка. До пункта if (T1[i] == T2[i]) continue; все подобные отрезки отбрасываются.
Почему в случае вертикального отрезка не проверяем if (flag != -1) номер шага, т.е. границу отсекателя, с которой ищем пересечение?
Вертикальный отрезок может быть полностью видимым, полностью невидимым, либо частично видимым.
Если он целиком видимый – это сразу обнаружится, уйдем сразу в визуализацию. Если полностью невидимый – уйдем в конец. Продолжится работа с вертикальным отрезком (частично видимым), но он в этом случае расположен по видимую сторону от левой и от правой границы. Значит, при выполнении пункта 3.3 (Если T1[i] =T2[i], то …) выяснится, что в первых двух разрядов обоих кодов для первой и второй вершин хранятся нули. По отношению к этим границам он является видимым и мы просто на первые два шага, где мы ищем пересечения с левой и правой границей не попадем. Мы будем переходить к следующей итерации. То есть, если мы дошли до пункта 3.5 (Если Fl <> -1, то …) и выяснили, что отрезок вертикальный, это будет означать, что мы ищем пересечения с верхней и нижней границей. Т. к. он вертикальный, x-координата изменяться не должна, измениться должна только y-координата.
Надо расставаться с той частью отрезка, которая расположена, начиная с невидимой вершины отрезка до найденной точки пересечения. Предлагается считать всегда невидимой по отношению к текущей границе отсекателя первую вершину. В алгоритме проводится проверка: если первая вершина невидима, значит находим точку пересечения и перемещаем первую вершину на найденную точку пересечения. Если же вторая вершина является невидимой, поменяем местами эти две вершины. Считаем (и не только считаем, а делаем так), что всегда первая вершина располагается по невидимую сторону от текущей границы отсекателя.
В простом алгоритме после нахождения точки пересечения отрезка с границей отсекателя проводится проверка на корректность найденного пересечения. Если пересечение корректно, то считается, что одна точка видимой части отрезка найдена и дальше надо находить вторую точку видимой части отрезка.
В алгоритме Сазерленда-Коэна, каждый раз находя точку пересечения отрезка со стороной отсекателя, мы никаких проверок на корректность не проводим, просто отбрасываем невидимую часть отрезка. Другими словам, мы невидимую вершину, P1, после нахождения точки пересечения, перемещаем в найденную точку пересечения (см. рисунок ниже).
В предыдущих алгоритмах координаты точки пересечения отрезка с ребром отсекателя определялись непосредственно путем решения соответствующих уравнений. В данном алгоритме непосредственное вычисление координат отсутствует, точка пересечения определяется с использованием двоичного поиска. Рассматриваемый алгоритм является частным случаем алгоритма отсечения Сазерленда-Коэна. Он был разработан Спруллом и Сазерлендом для аппаратной реализации, так как программная реализация данного алгоритма медленнее, чем алгоритма Сазерленда-Коэна; аппаратная же, за счет того, что сложение и деление на 2 очень быстры, намного эффективнее.
Алгоритм предусматривает вычисление кодов концевых точек отрезков объектов синтезируемой сцены и проверок, определяющих полную видимость отрезков (коды обоих концов отрезка равны 0 ), и полную невидимость отрезков ( побитное логическое произведение кодов концевых точек не равно нулю). Те же отрезки, о которых нельзя судить столь однозначно, разбивают на две равные части. К каждой из половин отрезков применяют те же проверки до тех пор, пока не будет обнаружено пересечение со стороной окна отсечения, либо пока он не выродится в точку. Затем определяется видимость вычисленной точки. Таким образом, процесс определения пересечения сводится к двоичному поиску, столь эффективно реализуемому аппаратно.
Для каждой концевой точки отрезка:
- Если концевая точка видима, то она будет наиболее удаленной видимой точкой. Процесс завершен. Иначе - продолжить.
- Если отрезок тривиально характеризуется как невидимый, то выходная информация не формируется. Процесс завершен. Иначе - продолжить.
- Грубо оценить наиболее удаленную видимую точку путем деления отрезка P1P2 средней точкой PmP2. Если PmP2 тривиально отвергается как невидимый, то средняя точка дает верхнюю оценку для наиболее удаленной видимой точки. Продолжить процедуру с куском P2Pm. Если отрезок становится настолько мал, что его средняя точка совпадает с его концами с машинной или наперед заданной точностью, то надо оценить ее видимость и закончить процесс.
1. Ввод координат отсекателя Xл, Xп, Yн, Yв.
2. Ввод координат концов отрезка P1(X1,Y1), P2(X 2,Y 2).
3. Ввод точности вычисления точки пересечения отрезка с границей отсекателя.
4. Установка номера шага отсечения i = 1.
5. Вычисление кодов концевых точек и запись их в соответствующие массивы
T1 и T2 размерностью 1х4,
вычисление сумм кодов концов S1, S2.
6. Проверка полной видимости отрезка. Если коды обоих концов отрезка равны нулю (полная видимость отрезка), то переход к п. 9.
7. Проверка полной невидимости отрезка.
Вычисление побитного логического произведения кодов концевых точек отрезка.
Если произведение отлично от нуля (отрезок невидим), то переход к п. 10.
8. Анализ частично видимого отрезка в том случае,
если побитовое логическое произведение кодов его концов равно нулю:
8.1. Поиск наиболее удаленной от P1 видимой точки S исследуемого отрезка.
Запоминание исходной точки P1 в промежуточной переменной R.
8.2. Проверка на окончание процесса решения:
Если i > 2, то определение логического произведения pr кодов концов отрезка.
Если pr != 0, то переход к п.10,
иначе переход к п.9.
8.3. Проверка точки P2 на наиболее удаленную от P1 видимую точку отрезка.
Если сумма всех элементов массива T2 равна нулю (S2), то переход к пункту 8.12.
8.4. Проверка нахождения точки пересечения отрезка с границами отсекателя.
Если |P1- P2| <= E (расстояние между концевыми точками исследуемого
отрезка меньше допустимой погрешности),
то переход к пункту 8.12.
8.5. Вычисление средней точки Pср. отрезка:
Pср. = (P1 + P2 )/2
(Pср.x = (P1.x + P2.x )/2;
Pср.y = (P1.y + P2.y )/2).
8.6. Запоминание текущей точки P1:
Pm = P1.
8.7. Замена точки P1 на среднюю точку:
P1 = Pср .
8.8. Вычисление нового кода T1 точки P1.
8.9. Вычисление произведения pr кодов концов нового отрезка P1P2.
8.10. Проверка полной невидимости отрезка P1P2.
Если побитовое логическое произведение pr кодов
концевых точек равно нулю, то переход к пункту 8.4.
В противном случае отрезок P1P2 невидим.
8.11. Возврат к предыдущему отрезку P1P2 :
P1 = Pm, = Pср , переход к пункту 8.4.
(Вычислена наиболее удаленная от точки P1 видимая точка отрезка).
8.12..Поиск наиболее удаленной от P2 видимой точки отрезка.
Замена мест точек P1 и P2:
P1 = P2,
P2 = R.
Увеличение шага выполнения отсечения i=i+1.
Переход к п.5.
9. Визуализация отрезка.
10.Конец.
При программной реализации алгоритма целесообразно для вычисления кодов концевых точек отрезков и их логических произведений использовать отдельные функции.
Как будут определяться полностью невидимые отрезки, которые не являются тривиально невидимыми?
Найдем Рср1, отрезок РсрР4 не будет распознан, как полностью невидимый, продолжим с ним работу, ищем опять Рср2, нижняя часть отрезка-тривиально невидимая, вершина Р4 переезжает в Рср2 и так далее. Подводя итог, в процессе разбиения отрезка, либо мы убеждаемся в том, что части отрезка становятся невидимыми, либо может сложиться ситуация, когда отрезок стянется в точку и тогда нужно будет определить видимость/невидимость этой точки.
