15.6. Алгоритмы построчного сканирования
Эти алгоритмы разработаны Уайли, Ромни, Эвансом и Эрдалом [516], Букнайтом [52, 53] и Уоткинсом [487]. Они функционируют в пространстве изображения, причем образ в них генерируется построчно. Ниже описан общий подход, который с некоторыми вариациями используется в названных выше алгоритмах.
Этот подход является расширением алгоритма преобразования многоугольника в растровую форму, описанного в разд. 11.7. Различие заключается в том, что в этом случае мы имеем дело не с одним многоугольником, а сразу со всеми многоугольниками, определяющими объект. На первом шаге создается таблица ребер (ТР), содержащая все негоризонтальные ребра многоугольников. Элементы ТР отсортированы по группам на основе меньшей у-координаты каждого ребра, а внутри групп — в зависимости от величины тангенса угла наклона. Эти элементы содержат:
1) х-координату крайней точки ребра с меньшей у-координатой;
2) «/-координату другой крайней точки ребра;
3) приращение Ал: координаты х, используемое для перехода от каждой сканирующей строки к следующей (Ах обратно тангенсу
угла наклона ребра);
4) идентификатор многоугольника, указывающий, какому многоугольнику принадлежит данное ребро.
На втором шаге создается таблица многоугольников (ТМ), в которой содержится по крайней мере следующая информация о каждом многоугольнике:
1) коэффициенты уравнения плоскости;
2) информация о закраске или цвете многоугольника;
3) булева переменная (флаг), определяющая положение внутри/ вне многоугольника. (Она используется при обработке сканирующей строки; вначале этой переменной присваивается значение false.)
На рис. 15.9 показаны проекции двух треугольников на плоскость ху; невидимые линии изображены пунктиром. В отсортированной ТР для этой фигуры содержатся элементы для АВ, AC, FD, FE, СВ и DE. В ТМ входят элементы для ABC и DEF.
На третьем шаге создается таблица активных ребер (ТАР), которая применялась в разд. 11.7; эта таблица всегда упорядочена по возрастанию координаты х. К тому времени, когда алгоритм дойдет до сканирующей строки у—а, ТАР будет содержать АВ и АС в указанном порядке. Ребра рассматриваются в направлении слева направо. Приступая к обработке АВ, инвертируем прежде всего флаг внутри/вне треугольника ABC. Тогда флаг примет значение true и, следовательно, мы окажемся «внутри» треугольника, который необходимо рассмотреть Теперь, поскольку мы находимся внутри только одного треугольника, последний должен быть видимым и, следовательно, на интервале от ребра А В до следующего ребра АС в ТАР будет вестись закраска, требуемая для треугольника ABC. При прохождении этого ребра флаг ABC меняет значение на false, и, следовательно, мы теперь не находимся «внутри» ни одного из треугольников. Поскольку АС является последним ребром в ТАР, обработка сканирующей строки завершается. В ТАР вносятся изменения из ТР, она снова упорядочивается по х и производится переход к обработке следующей строки.
Когда встретится сканирующая строка t/=p\ в отсортированной ТАР будут находиться АВ, AC, FD и F£. Обработка продолжается в основном так же, как прежде. Со сканирующей строкой пересекаются два треугольника, но мы в каждый момент будем находиться «внутри» только одного из них.
Больший интерес представляет сканирующая строка i/=V-При входе в ABC флаг треугольника становится равным true. На интервале от точки входа до следующего ребра DE ведется закраска, требуемая для ABC. В точке пересечения с DE флаг DEF также устанавливается в true, и, следовательно, мы будем находиться «внутри» сразу двух треугольников (полезно иметь отдельный список многоугольников, флаги внутри/вне которых принимают значение true, а также счетчик, показывающий сколько многоугольников находится в списке). Очевидно, что теперь нам надо решить, какой из треугольников расположен ближе к наблюдателю — ABC или DEF. Определение производится путем вычисления значений z из уравнений плоскости для обоих треугольников при у=у и при х, задаваемом пересечением строки у=7 с ребром DE. Эта величина х содержится в элементе для DE в ТАР. В нашем примере треуголь-ник DEF имеет меньшую координату z и поэтому мы его видим. Таким образом, правило закраски DEF действует на всем интервале : вплоть до пересечения с ребром ВС, где флаг ABC примет значение false, после чего интервал снова будет «внутри» только одного треугольника DEF. Поэтому правило закраски, установленное для DEF, продолжает действовать вплоть до пересечения с ребром FE. На рис. 15.10 показано соотношение между двумя треугольниками
и плоскостью у=у, двумя сплошными линиями обозначены пересечения треугольников с плоскостью.
Предположим, что за треугольниками ABC и DEF находится большой многоугольник GHIJ (рис. 15.11). Тогда, если при движении вдоль строки z/=Y, мы пересечем ребро СВ, будем все еще находиться «внутри» многоугольников DEF и GHIJ и,следовательно, вычисления, связанные с определением глубины, будут производиться снова. Этих затрат процессорного времени можно избежать, если предположить, что многоугольники не могут проникать друг в друга (при моделировании реальных объектов такое допущение вполне приемлемо). Из этого предположения вытекает, что соотношение глубин между DEF и GHIJ после выхода из ABC измениться не может, и, мы, следовательно, будем продолжать оставаться «внутри» DEF. Поэтому при выходе из закрываемого многоугольника глубину можно не вычислять, ее требуется определять только в том случае, если мы выходим из закрывающего многоугольника.
На рис. 15.12 показаны проникающие друг в друга треугольники. Чтобы правильно использовать алгоритм, введем в рассмотрение ложное ребро M'L' и тем самым разобьем треугольник KLM на KLL'M' и L'ММ'. Кроме того, можно модифицировать алгоритм и при обработке сканирующей строки на ней определять точку проникновения.
В другой модификации алгоритма используется когерентность по глубине. Если при обработке некоторой сканирующей строки в ТАР находятся те же ребра, что и при рассмотрении непосредственно предшествующей строки, причем в том же порядке, то соотношения глубин остаются прежними и их не надо вычислять. В этом случае видимые интервалы, найденные при обработке предыдущей строки (от АВ до DE и от DE до EF на рис. 15.9), сохраняются и на следующей сканирующей строке. Такая ситуация показана на рис.
рис. 15.9, где для обеих сканирующих строк у—^ и у=7+1 видимыми являются интервалы от АВ до DE и от DE до FE.
На рис. 15.9 когерентность по глубине теряется при переходе от (/=Y+1 к У=7+2, поскольку в ТАР меняется взаимная упорядоченность ребер DE и СВ (эта ситуация в алгоритме должна быть предусмотрена). Поэтому видимыми станут другие интервалы, в нашем случае от АВ до СВ и от DE до FE. Хзмлин и Джир [210] показали, как иногда может сохраняться когерентность по глубине, даже если меняется порядок хождения ребер в ТАР.
Мы еще не затрагивали вопросов, связанных с обработкой фона. В случае буфера регенерации простейшим способом является начальное присвоение пэлам некоторого заданного значения; следовательно, алгоритм должен обрабатывать лишь те сканирующие строки, которые пересекают ребра. Другой способ состоит в том, что в описание объекта включается большой квадрат, расположенный дальше от точки зрения, чем все остальные многоугольники. Этот квадрат параллелен картинной плоскости и имеет желаемую окраску. Наконец, еще один способ заключается в такой модификации алгоритма, при которой значения пэлов, соответствующие фону, можно непосредственно помещать в буфер регенерации в тех случаях, когда мы не находимся «внутри» многоугольника.
- 1. Векторные дисплеи.
- 2. Растровые дисплеи.
- Программистская модель интерактивной графики
- Лекция 2
- 640X480
- Лекция 4. Анимация
- Лекция 7. Алгоритмы растровой графики. Растровая графика.
- Лекция 9
- Перспективные проекции
- 15.1. Введение
- 15.2. Упрощение сравнений по глубине: перспективное преобразование
- 15.3. Исключение сравнений по глубине. Оболочки
- 15.4. Алгоритм сортировки по глубине
- 15.5. Алгоритм, использующий z-буфер
- 15.6. Алгоритмы построчного сканирования
- 15.7. Алгоритмы разбиения области
- 15.8. Эффективность алгоритма
- 15.9. Алгоритмы для криволинейных поверхностей
- Введение в OpenGl
- Void glVertex[2 3 4][s I f d] (type coords)
- Void glVertex[2 3 4][s I f d]V (type *coords)
- Gl_points каждая вершина задает координаты некоторой точки. Gl_lines каждая отдельная пара вершин определяет отрезок; ес-ли задано нечетное число вершин, то последняя вершина игнорируется.
- Gl_polygon последовательно задаются вершины выпуклог многоугольника.
- OpenGl в Delphi
- Событие. Сообщение. Контекст.