Лабораторная работа № 7. Отсечение отрезков

Отсечение отрезков

Ц е л ь р а б о т ы: освоение алгоритмов отсечения отрезков.

Задание для подготовки к работе

1. Изучить алгоритмы двумерного отсечения.

2. Описать подпрограмму для отсечения отрезка, используя один из изученных алгоритмов.

3. Разработать алгоритм и составить программу для получения изображения в пределах заданного окна для соответствующего варианта.

Содержание отчета

1. Постановка задачи.

2. Спецификация подпрограмм.

3. Описание основных алгоритмов.

4. Тексты программ.

Методические указания

Отсечение отрезков

Если изображение выходит за пределы экрана, то на части дисплеев увеличивается время построения за счет того, что изображение строится в "уме". В некоторых дисплеях выход за пределы экрана приводит к искажению картины, так как координаты просто ограничиваются при достижении ими граничных значений, а не выполняется точный расчет координат пересечения (эффект "стягивания" изображения). Некоторые, в основном, простые дисплеи просто не допускают выхода за пределы экрана. Все это, особенно в связи с широким использованием технологии просмотра окнами, требует выполнения отсечения сцены по границам окна видимости.

В простых графических системах достаточно двумерного отсечения.

Отсекаемые отрезки могут быть трех классов – целиком видимые, целиком невидимые и пересекающие окно.

По способу выбора простого решения об отбрасывании невидимого отрезка целиком или принятия его существует два основных типа алгоритмов отсечения – алгоритмы, использующие кодирование концов отрезка или всего отрезка и алгоритмы, использующие параметрическое представление отсекаемых отрезков и окна отсечения. Представители первого типа алгоритмов – алгоритм Коэна-Сазерленда (Cohen-Sutherland, CS-алгоритм) и FC-алгоритм (Fast Clipping-алгоритм). Представители алгоритмов второго типа – алгоритм Кируса-Бека (Curus-Beck, CB-алгоритм) и более поздний алгоритм Лианга-Барски (Liang-Barsky, LB-алгоритм).

Алгоритмы с кодированием применимы для прямоугольного окна, стороны которого параллельны осям координат, в то время как алгоритмы с параметрическим представлением применимы для произвольного окна.

Рассмотрим двумерный алгоритм Коэна-Сазерленда.

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

· большинство примитивов содержится целиком в большом окне;

· большинство примитивов лежит целиком вне относительно маленького окна.

Идея алгоритма состоит в следующем:

В этом алгоритме для проверки принадлежности точки окну используются четырехбитовые коды Сазерленда-Коэна. Плоскость разбивается прямыми, содержащими стороны окна на 9 областей. Каждой области присваивается код по следующему правилу (разряды нумеруются слева направо):

1-й бит – точка слева от окна, x < x _min

2-й бит – точка справа от окна, x > x _max

3-й бит – точка ниже окна, y < y _min

4-й бит – точка выше окна, y < y _max

Турбо Паскаль позволяет эффективно вычислить код точки с помощью операции приведения типов и побитовых операций:

byte (x < x_min) shl 3 or byte (x > x_max) shl 2 or byte(y<y_min) shl 2 or byte (y> y_max).

Пусть С₁ и С₂ – коды концов отрезка. Если С₁=0 и С₂=0, то отрезок видимый. Если С₁ и С₂¹0, то отрезок лежит по одну сторону окна, т.е. он невидим. В остальных случаях отрезок может быть частично видимым или невидимым.

При определении точки пересечения прямой с отрезком деление заменяем целочисленным делением.

При расчете пересечения используется горизонтальность либо вертикальность сторон окна, что позволяет определить координату X или Y точки пересечения без вычислений.

Рис. 7.1. Отсечение по методу Коэна-Сазерленда

При непосредственном использовании описанного выше способа отбора целиком видимого или целиком невидимого отрезка после расчета пересечения потребовалось бы вычисление кода расположения точки пересечения. Для примера рассмотрим отрезок CD. Точка пересечения обозначена как P (Рис.7.1). В силу того, что граница окна считается принадлежащей окну, то можно просто принять только часть отрезка PD, попавшую в окно. Часть же отрезка CP, на самом деле оказавшаяся вне окна, потребует дальнейшего рассмотрения, так как логическое И кодов точек C и P даст 0, т.е. отрезок CP нельзя просто отбросить. Для решения этой проблемы Коэн и Сазерленд предложили заменять конечную точку с ненулевым кодом конца на точку, лежащую на стороне окна, либо на ее продолжении.

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

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

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

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

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

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

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

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

Поиск по сайту: