Когерентность ребер и алгоритм построчного сканирования.
Первый шаг процедуры, т. е. вычисление пересечений, может оказаться медленным. Каждое ребро многоугольника требуется сравнивать с каждой сканирующей строкой. Во многих случаях лишь небольшое число ребер будет представлять интерес. Более того, необходимо отметить, что многие из ребер, пересекаемых строкой i, будут пересекаться также строкой i+1. Такая когерентность ребер (аналогичная когерентности сканирующих строк, рассмотренной выше) проявляется всякий раз, когда сканирующие строки пересекают ребро. При переходе от одной строки к другой можно вычислить новую x-координату точки пересечения ребра, используя x-координату старой точки пересечения (аналогично случаю развертки отрезков):
где m — тангенс угла наклона ребра. Параметр m равен Dy/Dx, а Dy=1, так что 1/m=Dx;.
Можно воспользоваться когерентностью ребер и устранить лишние сравнения сканирующих строк и ребер путем построчного разложения многоугольника в растр снизу вверх (или сверху вниз), используя алгоритм построчного сканирования.
Для каждой сканирующей строки рассматриваются только те ребра, которые пересекают строку. Они задаются таблицей активных ребер (ТАР). При переходе к следующей строке новые значения х-координат точек пересечения вычисляются с помощью уравнения (11.14), все новые ребра, пересекаемые следующей сканирующей строкой, добавляются в ТАР, а те ребра, которые содержатся в ТАР, но не пересекаются со следующей строкой, удаляются. Ребра, содержащиеся в ТАР, упорядочиваются по значениям x-координат точек пересечения, поэтому можно легко находить последовательности пикселей, которые следует закрасить.
|
|
|
Для эффективной реализации включения ребер в ТАР вводится таблица ребер (ТР), которая содержит все ребра, упорядоченные по значениям их меньших y-координат. ТР обычно строят с помощью групповой сортировки, выделяя столько же групп, сколько имеется сканирующих строк. Внутри каждой группы ребра располагаются в порядке возрастания x-координат наиболее низких точек. Этот порядок устанавливается с помощью сортировки вставками. Каждый элемент ТР содержит большую y-координату ребра (y max), x-координату нижней точки (x min) и приращение х, используемое для перехода от одной сканирующей строки к следующей (1/m).
На рис. 11.27 показано, как были бы отсортированы шесть ребер, изображенные на рис. 11.25, в предположении, что соответствующие ребра были предварительно укорочены на одну строку каждое, чтобы избежать двойных пересечений.
На рис. 11.28 приведена ТАР в случае сканирующих строк 9 и 10 для многоугольника, показанного на рис. 11.25.
После того как ТР сформирована, алгоритм построчного сканирования складывается из следующих шагов:
|
|
|
1. Установить у, равным минимальному значению координаты у среди элементов ТР, т. е. совпадающей с у-координатой первой непустой группы.
2. Инициализировать ТАР, сделать ее пустой.
3. Повторять шаг 3 до тех пор, пока ТАР и ТР не станут пустыми:
3.1. Слить информацию из группы у в ТР с информацией в ТАР, сохраняя упорядочение по х-координате.
3.2. Занести желаемые значения в пиксели на сканирующей строке, определяемой текущим значением у, используя пары x-координат из ТАР.
3.3. Удалить из ТАР те элементы, в которых y=ymax
3.4. Для всех элементов, содержащихся в ТАР, заменить х на х+1/m. Тем самым пересечение со следующей сканирующей строкой заносится в каждый элемент ТАР.
3.5. Поскольку на предыдущем шаге могла нарушиться упорядоченность ТАР по х, провести пересортировку ТАР.
3.6. Увеличить у на 1 и, таким образом, перейти к следующей сканирующей строке.
В этом алгоритме для эффективности преобразования многоугольника в растровую форму используются когерентность ребер сканирующих строк, а также сортировка.
Наиболее просто осуществляется построчная закраска треугольника (в 3D графике треугольник – это основной элемент аппроксимации криволинейных поверхностей):
|
|
|
1.
|
‑ верхняя (X1,Y1)
‑ средняя (X3,Y3)
‑ нижняя (X2,Y2)
2. разбиваем на 2 треугольника:
‑ выше средней вершины (1,3,4)
‑ ниже средней вершины (4,3,2)
=> вводится новая псевдовершина (X4,Y4)
3. сортируем среднюю и новую вершины по горизонтали:
‑ левая (X4,Y4)
‑ правая (X3,Y3)
4. строим уравнения прямой для левого и правого ребер:
‑ от (X1,Y1) до (X4,Y4) - левая (идентично (X1,Y1)-(X2,Y2))
‑ от (X1,Y1) до (X3,Y3) - правая
по формуле X =( Y - Yn )*( Xk - Xn )/( Yk - Yn )+ Xn
5. построчная закраска треугольника горизонтальными прямыми:
внешний цикл for Y := Y 1 to Y 3
внутренний цикл for X := X л( Y ) to X п( Y )
6. повторяем 4)-5) для нижнего треугольника for Y := Y 3 to Y 2
X1,Y1
X4,Y4 X3,Y3
|
|
|
X2,Y2
Текст и шрифты
Растровые шрифты, устарело, т.е. ступенчатость:
Векторные (TrueType): из прямых (по двум точкам)
или кривых Безье (по 3+ точкам, где первая и последняя
задают начало и конец, а средние только изгиб)
Для расчёта каждой точки кривой используется формула:
P(t)=(1-t)2 P0+2t(1-t) P1+t2 P2 t in [0,1]
Дата добавления: 2020-11-15; просмотров: 122; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!