Когерентность сканирующих строк

В самом простом случае, чтобы определить , которые надо закрасить, нужна проверка каждого на принадлежность многоугольнику (все экрана).

Но такой подход очень трудоемок, приходится проделывать много лишних операций.

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

На этом и основан принцип пространственной когерентности:

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

Используя этот принцип, можно предположить следующий алгоритм:

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

· Сортировать т. пересечения по увеличению x – координаты.

· Попарно закрасить.

Рассмотрим строку 2: строка 6:

1) т. пересечения: 3,6 1) 8,6,3,1

2) сортировка: 3,6 2) 1,3,6,8

3) закраска: 3-6 3) 1,-3,6,-8

строка 3: строка 5:

1) 2,8,8 1) 8,4,4,1

2) 2,8,8 не верно! 2) 1,4,4,8 верно!

3) 2,-8,8 – правая граница буфера 3) 1,-4,4,-8

Чтобы алгоритм работал верно, во всех случаях поступают следующим образом:

Все вершины разбивают на 2 типа:

1) промежуточные (1,3)

2) локальные и глобальные экстремумы (2,5,6,4).

Если вершина является промежуточной, то одно из ребер, ее составляющих, уменьшается на 1 по y.

Тогда для строки 3: (ребро е₃ укоротили на 1, появилась вершина 3¹)

1) 2,8

2) 2,8 3) 2,-8

Растровая развёртка многоуг-в (метод использования когерентности рёбер).

Принцип когерентности ребер: если ребро пересекается строкой i, то велика вероятность, что оно будет пересекаться и (i+1) – ой строкой.

,

,

Алгоритм: Создается таблица ребер (ТР), в которой все ребра сортируются по увеличению y – координаты. В ней содержатся все ребра и каждое ребро представлено в виде:

На основе ТР создается ТАР (таблица активных ребер), которая содержит только текущие ребра для каждой сканирующей строки. Они сортируются по увеличению x – координаты.

Каждое ребро представлено в виде:

Алгоритм создания ТАР:

1) Установить y=min – ому значению координаты y среди элементов ТР.

2) Инициализировать ТАР, сделать ее пустой.

3) Повторять шаг 3 до тех пор, пока ТАР и ТР не станут пустыми.

· Слить информацию из группы у таблицы ребер (ТР) с информацией в ТАР, сохраняя упорядочивание по x – координате.

· Занести желаемые значения в на сканирующей строке, определяемой текущим значением y, используя пары x – координат из ТАР.

· Удалить из ТАР те элементы, которые .

· Для всех элементов, содержащихся в ТАР, заменить x на (x+1/m).

· Т.к. на предыдущем шаге могла нарушиться упорядоченность ТАР по x, провести пересортировку ТАР.

· Увеличить y на 1 и т.о. перейти к следующей сканирующей строке.

10. Алгоритм отсечения отрезков Козна и Сазерленда. Алгоритм разбиения средней точкой.

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

Рассмотрим прямоугольник АВСD, который является окном (областью вывода). Все видимые отрезки прямых линий должны лежать внутри окна. Процесс отсечения должен выполнятся автоматически. Команды на вычерчивание треугольника PRQ интерпретируются как команды на вычерчивание отрезков .

Координаты точек и неизвестны. Их надо вычислить, зная координаты точек P, Q и R. Наклон отрезка PR вычисляется следующим образом:

Мы рассмотрели ситуацию, когда Р находится внутри окна, а R — удовлетворяет неравенствам:

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

где может быть либо 0 либо 1. Этот код содержит информацию о положении точки Р относительно окна.

			=0,	если
			=1,	если
			=0,	если
			=1,	если
			=0,	если
			=1,	если
			=0,	если
			=1,	если

Возможны 9 из 16 битовые комбинации показаны на рисунке.

Пусть для отрезка получены коды: .

· Если коды содержат только 0, то целиком лежит внутри окна и должен быть начерчен полностью.

· Если коды содержат единичный бит в одной и той же позиции, то отрезок целиком лежит за границами окна и не вычерчивается.

Остальные случаи рассмотрим подробнее. Если хотя бы 1 из кодов содержит единичный бит, то либо , либо перемещаются из области вне окна к одной их границ окна или к ее продолжению (точка перемещается в точку R, точка — в точку U). В последнем случае точка по-прежнему будет находится вне окна и понадобится еще одно перемещение (точка R переместиться в точку S, точка U — в точку Т). Таким образом, процесс отсечения может быть многоступенчатым, на каждом шаге расстояние между точками и

Алгоритм разбиения средней точкой.

В предыдущем алгоритме надо было вычислить пересечение отрезка со стороной окна. Этого можно избежать, если реализовать двоичный поиск такого пересечения путем деления отрезка его средней точкой. Алгоритм был предложен Спруллом и Сазерлендом. Программная реализация его медленнее, но аппаратная быстрее и эффективнее, так как аппаратно сложение и деление на 2 очень быстры (деление на 2 эквивалентно сдвигу побитовому вправо: 6=0110, 3=0011).

Рассмотрим отрезок с. Хотя он невидим, он пересекает диагональную прямую окна и не может быть тривиально отвергнут. Разбиение его средней точкой 3 позволяет тривиально исключать половину 3-2, а половина 1-3 тоже пересекает диагональ окна. Делим 1-3 пополам точкой 4 и отвергаем невидимый отрезок 1-4. разбиение отрезка 3-4 продолжается до тех пор, пока не будет найдено пересечение этого отрезка с правой стороной окна. Затем исследуется обнаруженная точка и она оказывается невидимой, следовательно весь отрезок невидим.

Рассмотрим отрезок d. Он также не определяется тривиально. Разбиение его средней точкой 3 приводит к одинаковым результатам для обоих половин. Разобьем отрезок 3-2 пополам точкой 4. Отрезок 3-4 полностью видим, а отрезок 4-2 видим частично. Отрезок 3-4 можно было бы начертить, но это привело бы к неэффективному изображению видимой части отрезка (серия коротких кусков). Поэтому точка 4 запоминается как текущая видимая точка, которая наиболее удалена от точки 1. А разбиение отрезка 4-2 продолжается. Как только обнаружится видимая средняя точка, она объявляется текущей наиболее удаленной от точки 1, до тех про, пока не будет обнаружено пересечение с нижней стороной окна с заранее заданной точностью. Это пересечение и будет объявлено самой удаленной от точки 1 видимой точкой. Затем точно также обрабатывается отрезок 1-3. Наиболее удаленной от точки 2 видимой точкой будет его пересечение с левой стороной окна.

Таким образом, для отрезков, подобных d, реализуется 2 двоичных поиска двух видимых точек, наиболее удаленных от концов отрезка. Это точка пересечения отрезка со сторонами окна. Для отрезков типа е один из двух поисков не нужен.

Дата добавления: 2015-07-14