Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
gl3-6.doc
Скачиваний:
3
Добавлен:
01.07.2025
Размер:
232 Кб
Скачать
☆

3.6.2.3. Отсечение отрезка с помощью алгоритма разбиения средней точкой

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

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

Алгоритм предусматривает вычисление кодов концевых точек отрезков объектов синтезируемой сцены и проверок, определяющих полную видимость отрезков (коды обоих концов отрезка равны 0 ), и полную невидимость отрезков ( побитное логическое произведение кодов концевых точек не равно нулю). Те же отрезки, о которых нельзя судить столь однозначно, разбивают на две равные части. К каждой из половин отрезков применяют те же проверки до тех пор, пока не будет обнаружено пересечение со стороной окна отсечения, либо пока он не выродится в точку. Затем определяется видимость вычисленной точки. Таким образом, процесс определения пересечения сводится к двоичному поиску, столь эффективно реализуемому аппаратно.

Рассмотрим более подробно работу алгоритма на примере отрезка GK (рис.3.6.5). После анализа кодов точек G и K нельзя однозначно судить о его полной видимости или полной невидимости, поэтому разобьём его средней точкой S. Однако это разбиение приводит к одинаковым результатам для обеих половин. Далее разобьём отрезок SK средней точкой R. Теперь отрезок SR полностью видим, а отрезок RK видим частично. Запомним точку R как текущую видимую точку, наиболее удаленную от G и продолжим разбиение отрезка RK. При обнаружении следующей видимой средней точки, она запоминается как текущая, наиболее удаленная от G. Разбиения продолжаются до тех пор, пока не будет обнаружено пересечение с нижней стороной окна с заданной точностью. Это пересечение и будет являться самой удаленной от G видимой точкой. Далее аналогичным образом обрабатывается отрезок GS. Для отрезка GK наиболее удаленной от K видимой точкой будет точка пересечения с левой стороной окна отсечения.

При отсечении отрезков объектов синтезируемой сцены возможны также случаи расположения отрезков подобно отрезкам EF и NM рис.3.6.5. У отрезка NM полностью виден конец N, поэтому производится поиск точки пересечения только с одной (в данном случае левой) стороной окна отсечения. Отрезок же EF невидим, однако в отличие от отрезка CD, он пересекает диагональ окна и требует дополнительных проверок

Каждое разбиение средней точкой дает грубую оценку искомых пересечений, поэтому разбиения производятся до тех пор, пока не будет обнаружено пересечение с заранее заданной точностью.

Исходя из возможных вышеизложенных проверок частей отрезков на видимость и невидимость, полный анализ каждой концевой точки отрезка состоит из следующих трех этапов:

-проверка на видимость, в положительном случае она принимается за наиболее удаленную видимую точку и анализ завершен, в отрицательном - переход к следующему этапу;

-проверка на полную невидимость отрезка, в положительном случае отрезок не рисуется, следовательно, никакая информация о нем не запоминается и анализ завершен, в отрицательном - переход к следующему этапу;

-грубая оценка наиболее удаленной видимой точки путем деления исследуемого отрезка средней точкой. Применение вышеизложенных проверок и оценок к двум полученным частям отрезка. Если часть отрезка является полностью невидимой, то средняя точка даёт верхнюю оценку для наиболее удаленной видимой точки. Если же средняя точка видима, то она дает нижнюю оценку для наиболее удаленной видимой точки. Аналогично исследуется другая часть исходного отрезка. Процедуры с частями отрезков повторяются до тех пор, пока часть отрезка не становится так мала, что его средняя точка совпадает с его концами с заранее заданной точностью. Тогда полученная средняя точка проверяется на видимость и анализ завершается.

Более подробно алгоритм разбиения средней точкой можно представить следующим образом:

1. Ввод координат отсекателя Xл, Xп, Yн, Yв.

  1. Ввод координат концов отрезка P1(X1,Y1), P2(X 2,Y 2).

  2. Ввод точности  вычисления точки пересечения отрезка с границей отсекателя.

  3. Установка номера шага отсечения 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 (расстояние между концевыми точками исследуемого отрезка меньше допустимой погрешности), то переход к пункту 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.Конец.

При программной реализации алгоритма целесообразно для вычисления кодов концевых точек отрезков и их логических произведений использовать отдельные функции.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]