Новосибирский Государственный Технический Университет. Факультет автоматики и вычислительной техники Кафедра вычислительной техники (специальность 220100).

МАШИННАЯ ГРАФИКА
(Учебное пособие в 3-х книгах)
Книга 2

П.В.Вельтмандер

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

• разработчики программно-технических средств машинной графики,
• разработчики прикладных пакетов, приближенные к техническим средствам.

Курс разбит на три части, выпущенные в виде отдельных книг:

1. Вводный курс.
2. Алгоритмы компьютерной графики.
3. Архитектуры графических систем.

ISBN  ISBN 5-230-13606-5
© Новосибирский государственный университет, 1997

Оглавление

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

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

В разделе 2 рассматриваются три алгоритма генерации векторов - обычного и несимметричного ЦДА и Брезенхема. Там же рассмотрены способы борьбы с лестничным эффектом, вызванным различимыми размерами пикселов на экране. Один из способов основан на модификации алгоритма Брезенхема. Другой, общий способ базируется на использовании низкочастотной фильтрации. Этот способ, естественно, применим для произвольных изображений.

В разделе 3 приводится алгоритм генерации окружностей.

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

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

Раздел 6 посвящен различным алгоритмам отсечения отрезка (Коэна-Сазерленда, Собкова-Поспишила-Янга, Лианга-Барски и Кируса-Бека) применительно к двух, трех и четырехмерным координатам.

В разделе 7 рассмотрены алгоритмы отсечения многоугольника.

В разделе 8 рассмотрены различные варианты организации данных.

В разделе 9 рассматривается геометрическое моделирование объектов и сцен.

Раздел 10 посвящен рассмотрению алгоритмов удаления скрытых линий и поверхностей.

В разделе 11 рассмотрены методы и алгоритмы реалистичного представления сцен.

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

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

Далее большими буквами X,   Y,   Z будут обозначаться обычные декартовые координаты, а маленькие буквы x,   y,   z будут использоваться для обозначения т.н. однородных координат.

Преобразование сдвига в плоском случае имеет вид:

Преобразование масштабирования относительно начала координат имеет вид:

Преобразование поворота относительно начала координат имеет вид:

Столбцы и строки матрицы поворота представляют собой взаимно ортогональные единичные векторы. В самом деле квадраты длин векторов-строк равны единице:

Так как скалярное произведение векторов A ·B = |A| ·|B| ·cosy, где |A| - длина вектора A, |B| - длина вектора B, а y - наименьший положительный угол между ними, то из равенства 0 скалярного произведения двух векторов-строк длины 1 следует, что угол между ними равен 90^°.

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

т.е. это единичный вектор вдоль оси X. Аналогично, произведение второго столбца на матрицу даст вектор [ 0 1 ]. Это позволяет сформировать матрицу, если известны результаты преобразования (см. пример в п. ).

Как видно из (2), (4) и (6) двумерные преобразования имеют различный вид. Сдвиг реализуется сложением, а масштабирование и поворот - умножением. Это различие затрудняет формирование суммарного преобразования и устраняется использованием двумерных однородных координат точки, имеющих вид:

Двумерные декартовые координаты точки получаются из однородных делением на множитель w:

Однородные координаты можно представить как промасштабированные с коэффициентом w значения двумерных координат, расположенные в плоскости с Z = w.

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

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

Для сдвига

Для масштабирования

Для поворота

Как видно из (9) - (11), wn = w, а матрица преобразования для двумерных однородных координат в общем случае имеет вид:

Рассмотрим вначале для этого преобразование

Легко видеть, что xn = x,   yn = y,   h = S. Таким образом двумерные декартовые координаты преобразованной точки

Для уяснения смысла третьего столбца матрицы преобразований (12) выполним преобразование

Получим результирующие двумерные декартовые координаты Xn, Yn для преобразованной точки

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

Рассмотрим в декартовой системе линию, проходящую через начало координат и точку (X,Y). Однородные координаты этой точки - (x,y,h) = (hX, hY, h), где h имеет произвольное значение. Предел отношения x/y при h стремящимся к 0 равен X/Y, но при этом декартовые координаты стремятся к бесконечности. Таким образом, точка с однородными координатами

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

Пусть две пересекающиеся прямые в декартовой системе координат заданы системой уравнений:

Решая эту систему относительно X и Y, найдем координаты точки пересечения

Запишем результат в однородных координатах

В силу произвольности масштабного множителя, умножим значения координат на (A₁ ·B₂ - A₂ ·B₁)

При этом точка пересечения лежит на прямой -y₀ ·x + x₀ ·y = 0 на бесконечности.

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

Рассмотрим сдвиг точки P₀ на расстояние (Tx₁, Ty₁) в точку P₁, а затем сдвинем точку P₁ на расстояние (Tx₂, Ty₂) в точку P₂. Обозначая через T₁ и T₂ матрицы сдвига, в соответствии с (9) получим:

Рассмотрим теперь последовательное выполнение масштабирований, первое с коэффициентами (Sx₁, Sy₁), второе с коэффициентами (Sx₂, Sy₂). Следует ожидать, что суммарное масштабирование будет мультипликативным. Обозначая через S₁ и S₂ матрицы масштабирования, в соответствии с (10) получим

Итак, получили, что результирующее масштабирование есть (Sx₁ ·Sx₂,  Sy₁ ·Sy₂), т.е. суммарное масштабирование, вычисленное как произведение матриц, как и ожидалось, мультипликативно.

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

Рассмотрим выполнение часто используемого поворота изображения на угол f относительно заданной точки P(X,Y). Это преобразование можно представить как перенос начала координат в точку (X,Y), поворот на угол f относительно начала координат и обратный перенос начала координат:

Суммарная матрица двумерных преобразований в однородных координатах имеет вид:

Вычисление преобразованных однородных координат точки P с непосредственным использованием T в выражении P ·T требует 9 операций умножения и 6 операций сложения. Но так как третья однородная координата может быть выбрана равной 1, а третий столбец T содержит единственный ненулевой элемент, равный 1, то преобразование декартовых координат может быть представлено в виде:

Далее при рассмотрении трехмерных преобразований, в основном, используется общепринятая в векторной алгебре правая система координат (рис. а). При этом, если смотреть со стороны положительной полуоси в центр координат, то поворот на +90^° (против часовой стрелке) переводит одну положительную ось в другую (направление движения расположенного вдоль оси и поворачивающегося против часовой стрелки правого винта и положительной полуоси совпадают). В некоторых, специально оговариваемых случаях, используется левая система координат (см. рис. б). В левой системе координат положительными будут повороты по часовой стрелке, если смотреть с положительного конца полуоси. В трехмерной машинной графике более удобной является левая система координат. Тогда если, например, поверхность экрана совмещена с плоскостью XY, то большим удалениям от наблюдателя соответствую точки с большим значением Z (см. рис. б).

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

Подобно тому как в двумерном случае точка в однородных координатах представляется трехмерным вектором [ x y w ], а матрицы преобразований имеют размер 3×3, для трехмерного случая точка представляется четырехмерным вектором [ x y z w ], где w не равно 0, а матрицы преобразований имеют размер 4×4. Если w не равно 1, то декартовые координаты точки (X,Y,Z) получаются из соотношения:

В частности, матрица сдвига имеет вид:

Матрица масштабирования относительно центра координат имеет вид:

Ранее рассмотренная для двумерного случая матрица поворота (11) является в то же время трехмерным поворотом вокруг оси Z. Так как при трехмерном повороте вокруг оси Z (поворот в плоскости XY) размеры вдоль оси Z неизменны, то все элементы третьей строки и третьего столбца равны 0, кроме диагонального, равного 1:

При повороте вокруг оси X (в плоскости YZ) размеры вдоль оси X не меняются, поэтому все элементы первой строки и первого столбца равны 0, за исключением диагонального, равного 1:

При повороте вокруг оси Y (в плоскости XZ) размеры вдоль оси Y не меняются, поэтому все элементы второй строки и второго столбца равны 0, за исключением диагонального, равного 1:

Столбцы и строки подматриц 3×3 матриц поворота Rx,   Ry,   Rz, аналогично двумерному случаю, представляют собой взаимно ортогональные единичные векторы. Легко убедиться, что суммарная матрица преобразования для произвольной последовательности поворотов вокруг осей X,   Y и Z имеет вид:

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

Пример формирования матрицы преобразования (из [])

Пусть заданы три точки P₁,   P₂,   P₃. Найти матрицу преобразования такого, что после преобразования вектор P₁P₂ будет направлен вдоль оси Z, а вектор P₁P₃ будет лежать в плоскости YZ.

1. Вначале надо сместить начало координат в точку P₁ с помощью преобразования

   T(-x1, -y1, -z1).

2. Единичный вектор, который должен лечь вдоль оси Z

   Rz = [r1z  r2z  r3z] = P1P2 / |P1P2|.

   Здесь |P₁P₂| - длина вектора P₁P₂.
3. Вектор, перпендикулярный плоскости, построенной на векторах P₁P₂ и P₁P₃, должен быть направлен вдоль оси X, так как вектор P₁P₂ лежит вдоль оси Z, а вектор P₁P₃ лежит в плоскости YZ. Этот вектор задается векторным произведением

   Rx = [r1x  r2x  r3x] = P1P2 ×P1P3 |P1P2| ·|P1P3| .

4. Наконец, вдоль оси Y должен быть направлен вектор, перпендикулярный к векторам R_x и R_z:

   Ry = [ r1y r2y r3y  ] = Rz ×Rx.

5. Искомая матрица есть

   M = T(-x1,-y1,-z1) · щ ъ ъ ъ ъ ъ ы r1x r1y r1z 0 r2x r2y r2z 0 r3x r3y r3z 0 0 0 0 1 щ ъ ъ ъ ъ ъ ы .

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

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

Как уже отмечалось, проецирование в общем случае - отображение точек, заданных в системе координат размерностью N, в точки в системе с меньшей размерностью. При отображении трехмерных изображений на дисплей три измерения отображаются в два.

Проецирование выполняется с помощью прямолинейных проекторов (проецирующих лучей), идущих из центра проекции через каждую точку объекта до пересечения с картинной поверхностью (поверхностью проекции). Далее рассматриваются только плоские проекции, при которых поверхность проекции - плоскость в трехмерном пространстве.

По расположению центра проекции относительно плоскости проекции различаются центральная и параллельные проекции.

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

При ортогональной проекции проекторы перпендикулярны плоскости проекции, а плоскость проекции перпендикулярна главной оси. Т.е. проекторы параллельны главной оси.

При аксонометрической проекции имеется одна из двух перпендикулярностей:

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

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

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

На рис.  приведена классификация описанных выше плоских проекций.

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

Использование проекций в техническом черчении регламентируется стандартом ГОСТ 2.317-69. Наиболее широко, особенно, в САПР используются ортогональные проекции (виды). Вид - ортогональная проекция обращенной к наблюдателю видимой части поверхности предмета, расположенного между наблюдателем и плоскостью чертежа.

В техническом черчении за основные плоскости проекций принимают шесть граней куба (рис. ).

1. Вид спереди, главный вид, фронтальная проекция, (на заднюю грань V),
2. Вид сверху, план, горизонтальная проекция, (на нижнюю грань H),
3. Вид слева, профильная проекция, (на правую грань W),
4. Вид справа (на левую грань),
5. Вид снизу (на верхнюю грань),
6. Вид сзади (на переднюю грань).

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

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

При изометрических проекциях укорачивания вдоль всех координатных осей одинаковы, поэтому можно производить измерения вдоль направлений осей с одним и тем же масштабом (отсюда и название изометрия). На рис.  приведена (аксонометрическая прямоугольная) изометрическая проекция куба со стороной A. При этой проекции плоскость проецирования наклонена ко всем главным координатным осям под одинаковым углом. Стандартом регламентируется коэффициент сжатия, равный 0.82, а также расположение и взаимные углы главных координатных осей, равные 120^° как это показано в левом верхнем углу рис. . Обычно сжатие не делается.

При диметрической проекции две из трех осей сокращены одинаково, т.е. из трех углов между нормалью к плоскости проекции и главными координатными осями два угла одинаковы. На рис.  приведена (аксонометрическая прямоугольная) диметрическая проекция куба со стороной A. Там же показаны регламентируемые расположение осей и коэффициенты сжатия. Обычно вместо коэффициента сжатия 0.94 используется 1, а вместо 0.47 - 0.5.

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

Наиболее употребимы два вида косоугольной проекции - фронтальная (косоугольная) диметрия (проекция Kabinett - кабине) и горизонтальная (косоугольная) изометрия (проекция Kavalier - кавалье) или военная перспектива.

В случае фронтальной (косоугольной) диметрии при использовании правосторонней системы координат экрана плоскость проецирования перпендикулярна оси Z. Ось X направлена горизонтально вправо. Ось Z изображается по углом в 45^° относительно горизонтального направления. Допускается угол наклона в 30 и 60^°. При этом отрезки, перпендикулярные плоскости проекции, при проецирования сокращаются до 1/2 их истинной длины. На рис.  приведена (аксонометрическая косоугольная) фронтальная диметрическая проекция куба со стороной A, там же показаны регламентируемые коэффициент сжатия, равный 0.5 и расположение осей.

В случае же (аксонометрической косоугольной) горизонтальной изометрии, как следует из названия, плоскость проецирования перпендикулярна оси Y а укорачивания по всем осям одинаковы и равны 1. Угол поворота изображения оси X относительно горизонтального направления составляет 30^°. Допускается 45 и 60^° при сохранении угла 90^° между изображениями осей X и Z. Иллюстрация этого приведена на рис. .

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

Простейшее параллельное проецирование - ортогональное выполняется на плоскость, перпендикулярную какой-либо оси, т.е. при направлении проецирования вдоль этой оси. В частности, проецирование в XY-плоскость, заданную соотношением Z = Z₀, выполняется следующим образом:

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

Из рисунка видно, что проектором, идущим из точки P₀ в P₁, точка P₀(0,0,1) проецируется в P₁(L·cosa, L·sina, 0).

Теперь проектором, параллельным рассмотренному (рис. ), спроецируем некоторую точку (X,Y,Z) в точку (X_p,Y_p,Z_p).

Из подобия треугольников получаем:

• вначале плоскости с заданной координатой Z₀ переносятся вдоль оси X на Z₀·L·cosa и вдоль оси Y на Z₀·L·sina,
• затем производится проецирование в плоскость Z = 0.

Различные варианты параллельных проекций формируются из полученной подстановкой значений L и углов a и b (см. рис. 0.10). В частности, для фронтальной косоугольной диметрии L = 1/2, следовательно, угол b между проекторами и плоскостью проецирования равен arctan2 = 63.4^°. Угол же a, равен 45^° и допускается 30 и 60^°, как это сказано выше. (Обратите внимание, что в этой системе координат плоскость фронтальной проекции - плоскость XY, в отличие от системы координат технического черчения, где фронтальная проекция, как это показано на рис. 0.5, формируется в плоскости XZ).

Наиболее реалистично трехмерные объекты выглядят в центральной проекции из-за перспективных искажений сцены. Центральные проекции параллельных прямых, не параллельных плоскости проекции будут сходиться в точке схода. В зависимости от числа точек схода, т.е. от числа координатных осей, которые пересекает плоскость проекции, различаются одно, двух и трехточечные центральные проекции. Иллюстрация одно-, двух- и трехточечной центральных проекций куба приведена на рис. .

Наиболее широко используется двухточечная центральная проекция.

Выведем матрицу, определяющую центральное проецирование для простого случая одноточечной проекции (рис. ), когда плоскость проекции перпендикулярна оси Z и расположена на расстоянии d от начала координат. (Здесь используется удобная для машинной графики левосторонняя система координат).

Начало отсчета находится в точке просмотра. Ясно, что изображения объектов, находящиеся между началом координат и плоскостью проекции увеличиваются, а изображения объектов, расположенных дальше от начала координат, чем плоскость проекции уменьшаются.

Из рис. 0.13 видно, что для координат (X1,Y1) точки P₁, полученной проецированием точки P₀(X,Y,Z) в плоскость Z = d (плоскость экрана) выполняются следующие соотношения:

Для перехода к декартовым координатам делим все на z/d и получаем:

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

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

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

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

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

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

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

Преобразование сдвига реализуется наиболее просто и заключается в переписывании части изображения (bitblt - операции Bit Block Transfer). При этом возможно исполнение некоторых операций над старым и новым пикселами с одинаковыми координатами.

Наиболее употребимыми являются:

· замена - новый пиксел просто заменяет старый,

· исключающее ИЛИ - в видеопамять заносится результат операции XOR над старым и новым кодами пикселов. Эта операция обычно используется дважды - вначале для занесения некоторого изображения, например, перекрестия и повторного его занесения для восстановления исходной картины.

Кроме этого, для реализации техники "акварель", т.е. техники работы с прозрачными цветами, в видеопамять заносится результат цветовой интерполяции между старым и новым оттенками пикселов. Эта операция всегда точно реализуема в полноцветных дисплеях, хранящих значения R, G и B в каждом пикселе. В дисплеях с таблицей цветности возможно получение не совсем правильных результатов.

Принято различать два типа масштабирования:
· целочисленное - zoom,

· произвольное, когда коэффициент масштабирования не обязательно целое число, - transfocation.

Наиболее просто реализуется целочисленное масштабирование. При увеличении в K раз каждый пиксел в строке дублируется К раз и полученная строка дублируется К раз. При уменьшении в K раз из каждой группы в K строк выбирается одна строка и в ней из каждой группы в K пикселов берется один пиксел в качестве результата. Не целочисленное масштабирование требует нерегулярного дублирования при увеличении и выбрасывания при уменьшении. Для отсутствия "дырок" в результирующем изображении при любых преобразованиях растровых картин следует для очередного пиксела результирующего изображения определить соответствующий (соответствующие) пикселы исходного изображения, вычислить значение пиксела и занести его.

Рассмотрим нецелочисленное уменьшение, т.е. перепись из большего массива в меньший (увеличение строится похожим образом).

Алгоритм ясен из следующей программы:

#define Max 13  // размер исходного массива
#define Min 7   // размер результирующего массива

int   ist;      // целая часть приращения индекса большего
                // массива при смещении на 1 по меньшему
float rst;      // дробная часть приращения индекса большего
                // массива при смещении на 1 по меньшему
int   iwr;      // индекс записи
int   ird;      // целая часть индекса чтения
float rrd;      // дробная часть индекса чтения
char  isx[Max]; // исходный массив пикселов
char  rez[Min]; // результирующий массив пикселов

void main (void) {
   ist= (int)(Max / Min);
   rst= (float)(Max - ist*Min)/(float)Min;
   ird= 0;  rrd= 0.0;
   for (iwr=0; iwr < Min; iwr++) {
      ird= ird + ist;   // накопление целой части индекса;
      rrd= rrd + rst;   // накопление дробной части индекса;
      if (rrd >= 1.0) {rrd= rrd - 1.0;  ird= ird + 1; }
      rez[iwr]= rez[ird-1];
   }
}

Понятно, что такой алгоритм требует точной вещественной арифметики, версия алгоритма с целочисленной арифметикой имеет вид:

#define Max 13  // размер исходного массива
#define Min 7   // размер результирующего массива

int   ist;      // целая часть приращения индекса большего
                // массива при смещении на 1 по меньшему
int   rst;      // остаток от приращения индекса
                // меньшего массива
int   iwr;      // индекс записи
int   ird;      // целая часть индекса чтения
int   rrd;      // остаток индекса чтения
char  isx[Max]; // исходный массив пикселов
char  rez[Min]; // результирующий массив пикселов

void main (void) {
   ist= (int)(Max / Min);
   rst= Max - ist*Min;
   ird= 0;  rrd= 0.0;
   for (iwr=0; iwr < Min; iwr++) {
      ird= ird + ist;   // накопление целой части индекса;
      rrd= rrd + rst;   // накопление дробной части индекса;
      if (rrd >= Min) {rrd= rrd - Min;  ird= ird + 1; }
      rez[iwr]= rez[ird-1];
   }
}

Внутренняя часть цикла при записи на ассемблере существенно упрощается, если использовать то, что для обычных 16-ти разрядных ЭВМ при переполнении происходит смена знака.

Определенные проблемы, связанные с дискретных характером изображения, возникают и при повороте растровой картины на угол не кратный 90^°. Здесь возможны два подхода:

1. Сканируются строки исходной картины при этом вычисляются новые значения координат пикселов для результирующей картины. Ясно что отсутствие дырок на результирующем изображении может быть обеспечено только при использовании вещественной арифметики, кроме этого возможно повторное занесение пикселов.
2. Сканируются строки результирующей картины и по координатам очередного пиксела определяются координаты пиксела из исходного изображения. Этот подход гарантирует отсутствие дырок, кроме того исключает повторное занесение пикселов.

Назначение генератора векторов - соединение двух точек изображения отрезком прямой.

Далее будут рассмотрены четыре алгоритма:

· два алгоритма ЦДА - цифрового дифференциального анализатора (DDA - Digital Differential Analyzer) для генерации векторов - обычный и несимметричный;

· алгоритм Брезенхема для генерации векторов[];

· алгоритм Брезенхема для генерации ребер заполненного многоугольника с уменьшением ступенчатости.

Перед рассмотрением конкретных алгоритмов сформулируем общие требования к изображению отрезка:

· концы отрезка должны находиться в заданных точках;

· отрезки должны выглядеть прямыми,

· яркость вдоль отрезка должна быть постоянной и не зависеть от длины и наклона.

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

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

· отрезок аппроксимируется набором пикселов и лишь в частных случаях вертикальных, горизонтальных и отрезков под 45^° они будут выглядеть прямыми, причем гладкими прямыми, без ступенек только для вертикальных и горизонтальных отрезков (рис. );

· яркость для различных отрезков и даже вдоль отрезка в общем случае различна, так как, например, расстояние между центрами пикселов для вертикального отрезка и отрезка под 45^° различно (см. рис. ).

Объективное улучшение аппроксимации достигается увеличением разрешения дисплея, но в силу существенных технологических проблем разрешение для растровых систем приемлемой скорости разрешение составляет порядка 1280×1024.

Субъективное улучшение аппроксимации основано на психофизиологических особенностях зрения и, в частности, может достигаться просто уменьшением размеров экрана. Другие способы субъективного улучшения качества аппроксимации основаны на различных программных ухищрениях по "размыванию" резких границ изображения.

Далее в этом разделе рассмотрены три алгоритма генерации отрезка.

С помощью ЦДА решается дифференциальное уравнение отрезка, имеющее вид:

где Py = Yk - Yn - приращение координат отрезка по оси Y, а Px = Xk - Xn - приращение координат отрезка по оси X.

При этом ЦДА формирует дискретную аппроксимацию непрерывного решения этого дифференциального уравнения.

В обычном ЦДА, используемом, как правило, в векторных устройствах, тем или иным образом определяется количество узлов N, используемых для аппроксимации отрезка. Затем за N циклов вычисляются координаты очередных узлов:

Получаемые значения X_i, Y_i преобразуются в целочисленные значения координаты очередного подсвечиваемого пиксела либо округлением, либо отбрасыванием дробной части.

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

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

Аппаратная реализация этого алгоритма изложена в пункте 8.1 первой части курса.

Субъективно лучше смотрятся вектора с единичным шагом по большей относительной координате (несимметричный ЦДА). Для Px > Py (при Px, Py > 0) это означает, что координата по X направлению должна увеличиться на 1 Px раз, а координата по Y-направлению должна также Px раз увеличиться, но на Py/Px.

Т.е. количество узлов аппроксимации берется равным числу пикселов вдоль наибольшего приращения.

Для генерации отрезка из точки (x1,y1) в точку (x2,y2) в первом октанте (Px і Py і 0) алгоритм несимметричного ЦДА имеет вид:

1. Вычислить приращения координат:
   Px= x2 - x1;
   Py= y2 - y1;
2. Занести начальную точку отрезка
   PutPixel (x1, y1);
3. Сгенерировать отрезок
   while (x1 < x2) {
   x1:= x1 + 1.0;
   y1:= y1 + Py/Px;
   PutPixel (x1, y1);
   }

Пример генерации отрезка по алгоритму несимметричного ЦДА приведен на рис. .

В Приложении 2 приведена программа V_DDA, реализующая данный алгоритм.

Так как приращения координат, как правило, не являются целой степенью двойки, то в ЦДА-алгоритме (см. предыдущий пункт) требуется выполнение деления, что не всегда желательно, особенно при аппаратной реализации.

Брезенхем в работе [] предложил алгоритм, не требующий деления, как и в алгоритме несимметричного ЦДА, но обеспечивающий минимизацию отклонения сгенерированного образа от истинного отрезка, как в алгоритме обычного ЦДА. Основная идея алгоритма состоит в том, что если угловой коэффициент прямой < 1/2, то естественно точку, следующую за точкой (0,0), поставить в позицию (1,0) (рис. а), а если угловой коэффициент > 1/2, то - в позицию (1,1) (рис. б). Для принятия решения куда заносить очередной пиксел вводится величина отклонения Е точной позиции от середины между двумя возможными растровыми точками в направлении наименьшей относительной координаты. Знак Е используется как критерий для выбора ближайшей растровой точки.

Если Е < 0, то точное Y-значение округляется до последнего меньшего целочисленного значения Y, т.е. Y-координата не меняется по сравнению с предыдущей точкой. В противном случае Y увеличивается на 1.

Для вычисления Е без ограничения общности упрощающе положим, что рассматриваемый вектор начинается в точке (0,0) и проходит через точку (4, 1.5) (см. рис. 0.3в), т.е. имеет положительный наклон меньший 1.

Из рис. 0.3в видно, отклонение для первого шага:

поэтому для занесения пиксела выбирается точка (1,0).

Отклонение для второго шага вычисляется добавлением приращения Y-координаты для следующей X-позиции (см. рис. 0.3в):

поэтому для занесения пиксела выбирается точка (2,1). Так как отклонение считается от Y-координаты, которая теперь увеличилась на 1, то из накопленного отклонения для вычисления последующих отклонений надо вычесть 1:

Отклонение для третьего шага:

поэтому для занесения пиксела выбирается точка (3,1).

Суммируя и обозначая большими буквами растровые точки, а маленькими - точки вектора, получаем:

Возможны случаи:

Е1 > 0	E1 Ј 0
ближайшая точка есть:
X1 = X0 + 1;    Y1 = Y0 + 1;	X1 = X0 + 1;     Y1 = Y0;
E2 = Е1 + Py/Px - 1;	E2 = E1 + Py/Px.

Так как интересует только знак Е, то можно избавиться от неудобные частных умножением E на 2×Px:

	E1 = 2×Py - Px
E1 > 0:	E2 = E1 + 2×(Py - Px)
E1 Ј 0:	E2 = E1 + 2×Py

Таким образом получается алгоритм, в котором используются только целые числа, сложение, вычитание и сдвиг:
X= x1;
Y= y1;
Px= x2 - x1;
Py= y2 - y1;
E= 2*Py - Px;
i= Px;
PutPixel(X, Y); /* Первая точка вектора */
while (i= i- 1 і 0) {
if (E і 0) {
X= X + 1;
Y= Y + 1;
E= E + 2*(Py - Px);
} else
X= X + 1;
E= E + 2*Py;
PutPixel(X, Y); /* Очередная точка вектора */
}

Этот алгоритм пригоден для случая 0    Ј   dY    Ј   dX. Для других случаев алгоритм строится аналогичным образом.

На рис.  приведен пример генерации по алгоритму Брезенхема того же самого отрезка, что и показанного на рис. 0.2 для генерации по алгоритму несимметричного ЦДА. Из сравнения рисунков видно, что результаты различны.

В Приложении 2 приведена программа V_BRE, реализующая описанный выше алгоритм.

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

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

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

Наиболее заметно ухудшает качество изображения ступенчатость. Имеется следующие способы борьбы со ступенчатостью :

· увеличение пространственного разрешения за счет усовершенствования аппаратуры,

· трактовка пиксела не как точки, а как площадки конечного размера, яркость которой зависит от размера площади пиксела, занятой изображением отрезка,

· "размывание" резкой границы, за счет частичной подсветки пикселов, примыкающих к формируемому отрезку. Понятно, что при этом ухудшается пространственное разрешение изображения.

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

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

На рис.  приведена иллюстрация построения ребра многоугольника с тангенсом угла наклона 11/21.

На рис. а) показан результат генерации многоугольника с использованием ранее рассмотренного алгоритма Брезенхема при двухуровневом изображении (пиксел или закрашен или не закрашен).

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

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

Как видно из рис.  при построении ребра многоугольника с тангенсом угла наклона t  (0 Ј t Ј 1) могут захватываться либо один пиксел (пикселы (0,0), (2,1), (4,2), (6,8)) либо два пиксела (пикселы (1,0) и (1,1), (3,1) и (3,2), (5,2) и (5,3)). Если захватывается один пиксел, то часть его площади, попавшая внутрь многоугольника, равна dy + t/2 (рис. a).

Если же захватывается два пиксела, то часть площади нижнего пиксела, попавшая внутрь многоугольника равна 1 - [((1 - dy)²)/ 2t], а верхнего - [((dy - 1 + 2)²)/ 2t] (см. рис. б). Суммарная площадь частей для двух пикселов, попавшая внутрь многоугольника, равна dy + t/2.

Если теперь в исходном алгоритме Брезенхема (см. 0.2.2) заменить отклонение E на E' = E + (1-t), то 0 Ј E' Ј 1) и значение E' будет давать значение той части площади пиксела, которая находится внутри многоугольника.

Выполняя преобразование над значением отклонения для первого шага (см. 0.2.2) получим, что начальное значение станет равным 1/2. Максимальное значение отклонения E'_max, при превышении которого производится увеличение Y-координаты занесения пикселов, станет равным (1 - t).

Для того, чтобы оперировать не дробной частью максимальной интенсивности, а непосредственно ее значениями достаточно домножить на полное число уровней интенсивности I тангенс угла наклона (t), начальное (E') и максимальное (E'_max) значения отклонения.

В результате получается следующий алгоритм, пригодный для случая 0    Ј   dY    Ј   dX:
X= x1;
Y= y1;
Px= x2 - x1;
Py= y2 - y1;
t= I*Py / Px;
E'= I/2;
E'_max= I - I*Py / Px;
i= Px;
PutPixel(X, Y, t/2); /* Первая точка вектора */
while (i = i - 1 і 0) {
if (E' і E'_max) {
X= X + 1;
Y= Y + 1;
E' = E'- E'_max;
} else
X= X + 1;
E' = E'+ t;
PutPixel(X, Y, E'); /* Очередная точка вектора */
}

Для избавления от вещественной арифметики при манипулировании с E' можно домножить уже упомянутые величины на 2*Px. Но в этом случае при занесении пикселов потребуется деление E' на 2*Px.

В Приложении 2 приведена процедура V_BreM, реализующая модифицированный алгоритм Брезенхема для генерации ребра заполненного многоугольника и пригодная для любого октанта.

Мы здесь рассмотрим методы, основанные на "размывании" границы.

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

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

Очевидно, что первый метод должен давать более качественное изображение, но при больших затратах ресурсов. Для усреднения предложены различные маски ([,]).

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

Эти массивы должны быть пронормированы для получения единичного коэффициента передачи, чтобы не вызывать неправильного смещения средней яркости изображения. Нормирующий коэффициент равен 1 / (сумму членов массива).

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

В Приложении 3 приведено несколько процедур фильтрации, реализующих оба рассмотренных метода - с понижением и без понижения разрешения.

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

Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).

Окружность с центром в начале координат описывается уравнением:

Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра P_i(X_i,  Y_i), ближайшую к истинной окружности, так чтобы ошибка:

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

Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.

Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.

При генерации окружности по часовой стрелке после занесения точки (X_i, Y_i) следующая точка может быть (см. рис. 0.1а) либо Pg = (X_i+1, Y_i) - перемещение по горизонтали, либо Pd = (X_i+1, Y_i-1) - перемещение по диагонали, либо Pv = (X_i, Y_i-1) - перемещение по вертикали.

Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:

Выбирается и заносится та точка, для которой это значение минимально.

Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.

Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.

Для определения того, какой пиксел выбрать Pg или Pd составим разность:

И будем выбирать точку Pg при di Ј 0, в противном случае выберем Pd.

Рассмотрим вычисление di для разных вариантов.

Для вариантов 2 и 3:

Dg і 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.

Добавив и вычтя (Y-1)² получим:

В квадратных скобках стоит Dd, так что

Для варианта 1:

Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.

Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.

Для определения того, какую пиксел выбрать Pd или Pv составим разность:

Если si Ј 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пиксел Pv.

Рассмотрим вычисление si для разных вариантов.

Для вариантов 5 и 6:

Dd > 0 и Dv Ј 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.

Добавив и вычтя (X+1)² получим:

В квадратных скобках стоит Dd, так что

Для варианта 7:

Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.

Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.

С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si Ј 0 также выбираем диагональный пиксел.

Итак:

Dd < 0

di Ј 0 - выбор горизонтального пиксела Pg

di > 0 - выбор диагонального пиксела Pd

Dd > 0

si Ј 0 - выбор диагонального пиксела Pd

si > 0 - выбор вертикального пиксела Pv

Dd = 0

выбор диагонального пиксела Pd.

Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.

1. Для горизонтального шага к X_i+1, Y_i

X_i+1 = X_i + 1
Y_i+1 = Y_i
Dd_i+1 = (X_i+1+1)² + (Y_i+1-1)² - R² =
X_i+1² + 2·X_i+1 + 1 + (Y_i+1-1)² - R² =
(X_i+1)² + (Y_i-1)² - R² + 2·X_i+1 + 1 =
Dd_i + 2·X_i+1 + 1

2. Для диагонального шага к X_i+1, Y_i-1

X_i+1 = X_i + 1
Y_i+1 = Y_i - 1
Dd_i+1 = Dd_i + 2 ·X_i+1 - 2 ·Y_i+1 + 2

3. Для вертикального шага к X_i, Y_i-1

X_i+1 = X_i
Y_i+1 = Y_i - 1
Dd_i+1 = Dd_i - 2 ·Y_i+1 + 1

В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:

X= 0

Y= R

Dd = (X+1)² + (Y-1)² - R² = 1 + (R-1)² - R² = 2*(1 - R)

Пикселы в остальных четвертях можно получить отражением. Кроме того достаточно сформировать дугу только во втором октанте, а остальные пикселы сформировать из соображений симметрии, например, с помощью подпрограммы Pixel_circle, приведенной в Приложении 5 и заносящей симметричные пикселы по часовой стрелке от исходного.

В Приложении 6 приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения 6. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.

В большинстве приложений используется одно из существенных достоинств растровых устройств - возможность заполнения областей экрана.

Существует две разновидности заполнения:

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

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

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

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

Определить принадлежность пиксела многоугольнику можно, например, подсчетом суммарного угла с вершиной на пикселе при обходе контура многоугольника. Если пиксел внутри, то угол будет равен 360^°, если вне - 0^° (рис. ).

Вычисление принадлежности должно производиться для всех пикселов экрана и так как большинство пикселов скорее всего вне многоугольников, то данный способ слишком расточителен. Объем лишних вычислений в некоторых случаях можно сократить использованием прямоугольной оболочки - минимального прямоугольника, объемлющего интересующий объект, но все равно вычислений будет много. Другой метод определения принадлежности точки внутренней части многоугольника будет рассмотрен ниже при изучении отсечения отрезков по алгоритму Кируса-Бека.

Реально используются алгоритмы построчного заполнения, основанные на том, что соседние пикселы в строке скорее всего одинаковы и меняются только там где строка пересекается с ребром многоугольника. Это называется когерентностью растровых строк (строки сканирования Y_i, Y_i+1, Y_i+2 на рис. ). При этом достаточно определить X-координаты пересечений строк сканирования с ребрами. Пары отсортированных точек пересечения задают интервалы заливки.

Кроме того, если какие-либо ребра пересекались i-й строкой, то они скорее всего будут пересекаться также и строкой i+1. (строки сканирования Y_i и Y_i+1 на рис. 0.2). Это называется когерентностью ребер. При переходе к новой строке легко вычислить новую X-координату точки пересечения ребра, используя X-координату старой точки пересечения и тангенс угла наклона ребра:

(тангенс угла наклона ребра - k = dy/dx, так как dy = 1, то 1/k = dx).

Смена же количества интервалов заливки происходит только тогда, когда в строке сканирования появляется вершина.

Учет когерентности строк и ребер позволяет построить для заполнения многоугольников различные высокоэффективные алгоритмы построчного сканирования. Для каждой строки сканирования рассматриваются только те ребра, которые пересекают строку. Они задаются списком активных ребер (САР). При переходе к следующей строке для пересекаемых ребер перевычисляются X-координаты пересечений. При появлении в строке сканирования вершин производится перестройка САР. Ребра, которые перестали пересекаться, удаляются из САР, а все новые ребра, пересекаемые строкой заносятся в него.

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

1. Подготовить служебные целочисленные массивы Y-координат вершин и номеров вершин.
2. Совместно отсортировать Y-координаты по возрастанию и массив номеров вершин для того, чтобы можно было определить исходный номер вершины.
3. Определить пределы заполнения по оси Y - Y_мin и Y_max. Стартуя с текущим значением Y_tek = Y_min, исполнять пункты 4-9 до завершения раскраски.
4. Определить число вершин, расположенных на строке Y_tek - текущей строке сканирования.
5. Если вершины есть, то для каждой из вершин дополнить список активных ребер, используя информацию о соседних вершинах.
   Для каждого ребра в список активных ребер заносятся:

   • максимальное значение Y-координаты ребра,
   • приращение X-координаты при увеличении Y на 1,
   • начальное значение X-координаты.

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

6. По списку активных ребер определяется Y_след - Y-координата ближайшей вершины. (Вплоть до Y_след можно не заботиться о модификации САР а только менять X-координаты пересечений строки сканирования с активными ребрами).
7. В цикле от Y_tek до Y_след:

   • выбрать из списка активных ребер и отсортировать X-координаты пересечений активных ребер со строкой сканирования;
   • определить интервалы и выполнить закраску;
   • перевычислить координаты пересечений для следующей строки сканирования.

8. Проверить не достигли ли максимальной Y-координаты. Если достигли, то заливка закончена, иначе выполнить пункт .
9. Очистить список активных ребер от ребер, закончившихся на строке Y_след и перейти к пункту 4.

В Приложении 5 приведены две подпрограммы заполнения многоугольника - V_FP0 и V_FP1. Первая реализует данный (простейший) алгоритм. Эта программа вполне работоспособна, но генерирует двух и трехкратное занесение части пикселов. Это мало приемлемо для устройств вывода типа матричных или струйных принтеров.

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

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

Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем "Исходный_массив"; количество сортируемых чисел задается скаляром "Кол-во_чисел"; сортируемые числа J удовлетворяют условию:

Для сортировки потребуются описания:

int  Max_число;        /* Верхняя граница значений */
int  *Повтор;          /* Длина этого массива = Max_число */
int  Кол_чисел;        /* Кол-во сортируемых чисел */
int  *Исходный_массив; /* Длина этого массива >= Кол_чисел */
int  *Результат;       /* Длина этого массива >= Кол_чисел */
int  ii,jj, kk;        /* Рабочие переменные */

1. Обнуляется служебный массив для подсчета числа повторений исходных кодов.

      for (ii=0; ii<Max_число; ++ii) Повтор[ii]= 0;
   

2. Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа:

      for (ii= 0; ii < Кол_чисел; ++ii) {
         jj= Исходный_массив[ii];
         Повтор[jj]= Повтор[jj] + 1;
      }
   

3. Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве:

      jj= 0;
      for (ii=0; ii<Max_число; ++ii) {
         jj= jj + Повтор[ii];
         Повтор[ii]= jj;
      }
   

4. Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1:

      for (ii= 0; ii < Кол_чисел; ++ii) {
         jj= Исходный_массив[ii];
         kk= Повтор[jj];
         Результат[kk]= jj;
         Повтор[jj]= Повтор[jj] - 1;
      }
   

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

При этом тем или иным образом задается заливаемая (перекрашиваемая) область, код пиксела, которым будет выполняться заливка и начальная точка в области, начиная с которой начнется заливка.

По способу задания области делятся на два типа:

· гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселы внутренней части области налагаются два условия - они должны быть отличны от кода пикселов границы и кода пиксела перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

· внутренне-определенные, нарисованные одним определенным кодом пиксела. При заливке этот код заменяется на новый код закраски.

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

Заливаемая область или ее граница - некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пикселы области.

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

В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так область на рис. а мы можем заполнить любым алгоритмом, а область на рис. б, состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом.

С использованием связности областей и стека можно построить простые алгоритмы закраски как внутренне, так и гранично-определенной области. В [] рассматриваются совсем короткие рекурсивные подпрограммы заливки. В [] - несколько более длинные итеративные подпрограммы.

Рассмотрим простой алгоритм заливки гранично-определенной 4-х связной области. В [] приведена рекурсивная реализация подпрограммы заливки 4-х связной гранично-определенной области:

void V_FAB4R (grn_pix, new_pix, x_isx, y_isx)

int grn_pix, new_pix, x_isx, y_isx;

{

if (getpixel (x_isx, y_isx) № grn_pix &&

getpixel (x_isx, y_isx) № new_pix)

{

putpixel (x_isx, y_isx, new_pix);

V_FAB4R (grn_pix, new_pix, x_isx+1, y_isx);

V_FAB4R (grn_pix, new_pix, x_isx, y_isx+1);

V_FAB4R (grn_pix, new_pix, x_isx-1, y_isx);

V_FAB4R (grn_pix, new_pix, x_isx, y_isx-1);

}

} /* V_FAB4R */

Заливка выполняется следующим образом:

· определяется является ли пиксел граничным или уже закрашенным,

· если нет, то пиксел перекрашивается, затем проверяются и если надо перекрашиваются 4 соседних пиксела.

Полный текст тестовой программы V_FAB4R с использованием этой подпрограммы приведен в Приложении 6.

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

В [] приведен итеративный алгоритм закраски 4-х связной гранично-определенной области. Логика работы алгоритма следующая:

Поместить координаты затравки в стек

Пока стек не пуст

Извлечь координаты пиксела из стека.

Перекрасить пиксел.

Для всех четырех соседних пикселов проверить

является ли он граничным или уже перекрашен.

Если нет, то занести его координаты в стек.

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

a) Порядок перебора соседних пикселов

б) Порядок заливки области

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

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

Программа V_FAB4, реализующая данный алгоритм, приведена в Приложении 6.

Сравнительные прогоны тестовых программ V_FAB4R и V_FAB4 подтвердили соображения о неэкономности рекурсивного алгоритма: при стандартном окне стека в 64 K с помощью рекурсивной программы можно закрасить квадратик не более чем 57×57 пикселов. Итеративная же программа V_FAB4 при тех же условиях позволяет закрасить прямоугольник размером 110×110 истратив на массив координат 16382 байта.

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

Использует пространственную когерентность:

· пикселы в строке меняются только на границах;

· при перемещении к следующей строке размер заливаемой строки скорее всего или неизменен или меняется на 1 пиксел.

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

Последовательность работы алгоритма для гранично определенной области следующая:

1. Координата затравки помещается в стек, затем до исчерпания стека выполняются пункты 2-4.

2. Координата очередной затравки извлекается из стека и выполняется максимально возможное закрашивание вправо и влево по строке с затравкой, т.е. пока не попадется граничный пиксел. Пусть это Хлев и Хправ, соответственно.

3. Анализируется строка ниже закрашиваемой в пределах от Хлев до Хправ и в ней находятся крайние правые пикселы всех незакрашенных фрагментов. Их координаты заносятся в стек.

4. То же самое проделывается для строки выше закрашиваемой.

В Приложении 6 приведена процедура V_FAST, реализующая рассмотренный алгоритм. За счет несложной модификации служебных процедур запроса и записи строк изображения, данная процедура может заливать изображение, размещенное в файле.

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

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

Программное исполнение отсечения достаточно медленный процесс, поэтому, естественно, в мощные дисплеи встраивается соответствующая аппаратура. Первое сообщение об аппаратуре отсечения, использующей алгоритм отсечения делением отрезка пополам и реализованной в устройстве Clipping Divider, появилось в 1968 г. [38]. Этот алгоритм был рассмотрен при изучении технических средств. Здесь мы рассмотрим программные реализации алгоритма отсечения.

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

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

Вначале мы рассмотрим алгоритм Коэна-Сазерленда, являющийся стандартом де-факто алгоритма отсечения линий и обладающий одним из лучших быстродействий при компактной реализации. Затем рассмотрим наиболее быстрый, но и чрезвычайно громоздкий FC-алгоритм. Далее рассмотрим алгоритм Лианга-Барски для отсечения прямоугольным окном с использованием параметрического представления. Быстродействие этого алгоритма сравнимо с быстродействием алгоритма Коэна-Сазерленда при большей компактности и наличии 3D и 4D реализаций. Последним рассмотрим алгоритм Кируса-Бека, который использует параметрическое представление и позволяет отсекать произвольным выпуклым окном. В заключение сравним быстродействие различных алгоритмов.

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

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

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

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

Окно отсечения и прилегающие к нему части плоскости вместе образуют 9 областей (рис. 0.2.3). Каждой из областей присвоен 4-х разрядный код.

Две конечные точки отрезка получают 4-х разрядные коды, соответствующие областям, в которые они попали. Смысл разрядов кода:

1 рр = 1 - точка над верхним краем окна;

2 рр = 1 - точка под нижним краем окна;

3 рр = 1 - точка справа от правого края окна;

4 рр = 1 - точка слева от левого края окна.

Определение того лежит ли отрезок целиком внутри окна или целиком вне окна выполняется следующим образом:

· если коды обоих концов отрезка равны 0 то отрезок целиком внутри окна, отсечение не нужно, отрезок принимается как тривиально видимый (отрезок AB на рис. 0.2.3);

· если логическое & кодов обоих концов отрезка не равно нулю, то отрезок целиком вне окна, отсечение не нужно, отрезок отбрасывается как тривиально невидимый (отрезок KL на рис. 0.2.3);

· если логическое & кодов обоих концов отрезка равно нулю, то отрезок подозрительный, он может быть частично видимым (отрезки CD, EF, GH) или целиком невидимым (отрезок IJ); для него нужно определить координаты пересечений со сторонами окна и для каждой полученной части определить тривиальную видимость или невидимость. При этом для отрезков CD и IJ потребуется вычисление одного пересечения, для остальных (EF и GH) - двух.

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

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

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

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

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

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

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

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

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

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

Эта схема реализована в процедуре V_CSclip, приведенной в Приложении 7.

В 1987 г. Собков, Поспишил и Янг [37] предложили алгоритм, названный ими FC-алгоритмом (Fast Clipping), также использующий кодирование, но не конечных точек, а линий целиком. Приведенное далее изложение алгоритма следует статье [37].

Схема кодирования близка к используемой в алгоритме Коэна-Сазерленда (рис. 0.2.4). Пространство разбивается на 9 неперекрывающихся областей, пронумерованных арабскими цифрами от 1 до 9. Коды, назначаемые концам отрезков, попавших в ту или иную область, приведены в двоичном и шестнадцатиричном виде (запись вида 0xD).

Отрезок видим только в области 5, т.е. отрезок, координаты которого удовлетворяют условиям:

Каждая конечная точка отрезка V₀V₁ окажется с одной из этих областей. Комбинация кодов концов отрезка, называемая кодом линии, используется для определения возможных вариантов расположения отрезка и, следовательно, отсечения. Код линии формируется из кодов концов отрезка следующим образом:

здесь Code(V₁) обозначает код конечной точки V₁,
Code(V₀) × 16 означает сдвиг кода начальной точки V₀ влево на 4 разряда.

Так как каждый код может принимать одно из 9 значений, то всего имеется 81 возможный вариант расположения отрезка. Но, если Code(V₀) равен Code(V₁), то LineCode(V₀,V₁) равен LineCode(V₁,V₀). Имеется всего 9 таких случаев: 1-1, 2-2, ј 9-9. Следовательно, число различных случаев уменьшается до 72.

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

· начальная точка отрезка считается точкой номер 0 (V₀),

· конечная точка отрезка считается точкой номер 1 (V₁),

· ClipA_B обозначает алгоритм расчета перемещения конечной точки номер А на сторону окна B (расчет пересечения прямой линии, на которой расположен отсекаемый отрезок со стороной окна B).

Иллюстрации к случаям 1-7 приведены на рис. 0.2.5, для случая 8 - на рис. 0.2.6.

1. Начальная и конечная точки отрезка обе в области 5 (отрезок JK). Это простой случай принятия отрезка.

2. Начальная и конечная точки отрезка обе в области 4 (отрезок LA). Отрезок не пересекает видимую область, так что это простой случай отбрасывания.

3. Начальная точка в области 4, конечная - в области 1 (отрезок LB). Отрезок не пересекает видимую область, так что это простой случай отбрасывания.

4. Начальная точка в области 4, конечная - в области 2 (отрезки LC и LD). Отрезки явно пересекает Xлев, так что вначале надо определить соответствующую координату, используя алгоритм Clip0_Xleft. Для отрезка LC это дает V₀y > Yверх, так что отрезок должен быть отброшен без дальнейших вычислений. Отрезок LD входит в окно с левой стороны и может выходить через верх. Следовательно, следующее отсечение должно быть Clip1_Top, после которого отрезок принимается.

5. Начальная точка в области 4, конечная - в области 3 (отрезки LE, LF и LG). Отрезки явно пересекает Xлев. Так же как и для случая 4 вначале применяется Clip0_Xleft и отрезок LE отбрасывается если V₀y > Yверх. Если же получаем V₀y Ј Yверх, то отрезок должен выйти из области видимости через верхнее или правое ребро. Применяем отсечение Clip1_Top и сравниваем новое значение X-координаты конечной точки - V₁x c Xправ. Если V₁x Ј Xправ, то отрезок (LF) проходит через верхнюю сторону, отрезок принимается и дальнейшие вычисления не нужны. Иначе отрезок (LG) проходит через правую сторону и требуется отсечение Clip1_Right. Отсечение закончено, отрезок принимается.

6. Начальная точка в области 4, конечная - в области 6 (отрезок LH). Данный отрезок видим. Вначале используем Clip0_Xleft затем Clip1_Right и принимаем отрезок.

7. Начальная точка в области 4, конечная - в области 5 (отрезок LI). Данный отрезок видим. Просто используем Clip0_Xleft и принимаем отрезок.

8. Начальная точка V₀ (R, S, T или U) в области 7, конечная точка V₁ (W, X, Y или Z) - в области 3 (см. рис.0.2.6). В этом случае могут быть отброшены только два типа отрезков. Для минимизации вычислений используем Clip0_Xleft. Если V₀y > Yверх, то это первый случай отбрасывания (отрезок RW). Clip1_Xright и проверка V₁y < Yниз задают второй случай отбрасывания (отрезок UZ). Все другие отрезки должны быть видимы. Если V₀y < Yниз, тогда V₀ = T, иначе V₀ = S. Если V₀y < Yниз, то Clip1_Ybottom даст точку V₀ на ребре окна. Аналогично, если V₁y > Yверх, то V₁=X и здесь требуется Clip1_Ytop перед приемом отрезка. Если V₁y < Yверх, тогда V₁ = Y.

Из этих восьми случаев легко симметрично сгенерировать все остальные.

Главное отличие FC-алгоритма от алгоритма Коэна-Сазерленда состоит в упорядочивании действий по отсечению. Эффективность алгоритма Коэна-Сазерленда ограничивается последовательным характером и фиксированным порядком действий по отсечению. Как пример (см. рис. 0.2.6) отрезок RW будет отсекаться в порядке: сверху, снизу, справа и слева. Число же отсечений для определения видимости равно 2 - снизу и слева. В FC-алгоритме, напротив, для каждого значения LineCode имеется свой набор действий по отсечению. Для приведенного выше примера потребуется только одно отсечение для определения невидимости отрезка RW. Кроме этого, повышению эффективности FC-алгоритма по сравнению с CS-алгоритмом способствует отсутствие ненужных циклов и, следовательно, перевычислений кодов конечных точек.

В Приложении 7 приведена C-подпрограмма V_FCclip, реализующая FC-алгоритм и свободная от ошибок в подпрограмме, приведенной в [37]. Можно заметно сократить объем ее программного кода учтя симметрию и использовав указатели на данные либо переставляя данные. Например, в подпрограмме V_FCclip для отрезка LH (см. рис. 0.2.5, если он идет слева-направо вначале выполняется отсечение для начальной точки по левой стороне окна и затем для конечной - по правой. Если же отрезок идет справа-налево, то вначале вычисляется отсечение начальной точки по правой стороне и затем конечной - по левой. Очевидно, что эти два случая идентичны если поменять местами координаты начальной и конечной точек.

В 1982 г. Лианг и Барски [32] предложили алгоритмы отсечения прямоугольным окном с использованием параметрического представления для двух, трех и четырехмерного отсечения. По утверждению авторов, данный алгоритм в целом превосходит алгоритм Коэна-Сазерленда. Однако в работе [37] показывается, что это утверждение справедливо только для случая когда оба конца видимого отрезка вне окна и окно небольшое (до 50×50 при разрешении 1000×1000). Приведенное далее изложение двумерного варианта алгоритма следует, основном, работе [32].

Как уже говорилось, при 2D отсечении прямые отсекаются по 2D области, называемой окном отсечения. В частности, внутренняя часть окна отсечения может быть выражена с помощью следующих неравенств (рис. 0.2.7).

#tth_closerowВнутренняя часть окна отсечения

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

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

Отсекаемый отрезок прямой может быть преобразован в параметрическое представление следующим образом. Пусть конечные точки отрезка есть V₀ и V₁ с координатами (x0,y0) и (x1,y1), соответственно. Тогда параметрическое представление линии может быть задано следующим образом:

Или в общем виде для отрезка, заданного точками V₀ и V₁:

Для точек V₀ и V₁ параметр t равен 0 и 1, соответственно. Меняя t от 0 до 1 перемещаемся по отрезку V₀V₁ от точки V₀ к точке V₁. Изменяя t в интервале от -Ґ до +Ґ, получаем бесконечную (далее удлиненную) прямую, ориентация которой - от точки V₀ к точке V₁.

Однако вернемся к формальному рассмотрению алгоритма отсечения.

Подставляя параметрическое представление, заданное уравнениями (0.2.2) и (0.2.3), в неравенства (0.2.1), получим следующие соотношения для частей удлиненной линии, которая находится в окне отсечения:

Заметим, что соотношения (0.2.5) - неравенства, описывающие внутреннюю часть окна отсечения, в то время как равенства определяют его границы.

Рассматривая неравенства (0.2.5), видим, что они имеют одинаковую форму вида:

Здесь использованы следующие обозначения:

Вспоминая определения внутренней и внешней стороны линии границы (см. рис. 0.2.8), замечаем, что каждое из неравенств (0.2.6) соответствует одной из граничных линий (левой, правой, нижней и верхней, соответственно) и описывает ее видимую сторону. (Например, для i=1 имеем: P₁·t    Ј   Q₁ Ю -dx·t    Ј   x0 - XлевЮ x0   +  dx·t    і   Xлев). Удлиним V₀V₁ в бесконечную прямую. Тогда каждое неравенство задает диапазон значений параметра t, для которых эта удлиненная линия находится на видимой стороне соответствующей линии границы. Более того, конкретное значение параметра t для точки пересечения есть t = Q_i/P_i. Причем знак Q_i показывает на какой стороне соответствующей линии границы находится точка V₀. А именно, если Qi    і   0, тогда V₀ находится на видимой стороне линии границы, включая и ее. Если же Q_i    <   0, тогда V₀ находится на невидимой стороне.

Рассмотрим P_i в соотношениях (0.2.7). Ясно, что любое P_i может быть меньше 0, больше 0 и равно 0.

Если P_i    <   0, тогда соответствующее неравенство становится:

Для пояснения на рис. 0.2.10 показано пересечение с левой и правой границами при P_i    <   0.

Очевидно, что диапазон значений параметра t, для которых удлиненная линия находится на видимой стороне соответствующей граничной линии, имеет минимум в точке пересечения направленной удлиненной линии, заданной вектором V₀V₁ и идущей с невидимой на видимую сторону граничной линии (так как только на границе t равно Q_i   /  P_i, а в остальной части видимой стороны больше).

Аналогично, если P_i    >   0, тогда соответствующее неравенство становится:

Для пояснения на рис. 0.2.11 показано пересечение с левой и правой границами при P_i    >   0.

Так как значения параметра t только на границе равны Q_i/P_i, а в остальной видимой части меньше Q_i/P_i, то значение параметра t имеет максимум на границе.

Наконец, если P_i    =   0, тогда соответствующее неравенство превращается в:

Заметим, что здесь нет зависимости от t, т.е. неравенство выполняется для всех t, если Q_i    і   0 и не имеет решения при Q_i   <   0. Для пояснения на рис. 0.2.12 иллюстрируется случай P_i    =   0.

Геометрически, если P_i    =   0, то нет точек пересечения удлиненной линии, определяемой точками V₀V₁, с линиями границы. Более того, если Q_i    <   0, то удлиненная линия находится на внешней стороне линии границы, а при Q_i    і   0 находится на внутренней стороне (включая ее). В последнем случае отрезок V₀V₁ может быть видим или нет в зависимости от того где находятся точки V₀V₁ на удлиненной линии. В предыдущем же случае нет видимого сегмента, так как удлиненная линия вне окна, т.е. это случай тривиального отбрасывания.

Все эти случаи суммированы на блок-схеме, представленной на рис. 0.2.13.

Итак, рассмотрение четырех неравенств дает диапазон значений параметра t, для которого удлиненная линия находится внутри окна отсечения. Однако, отрезок V₀V₁ только часть удлиненной линии и он описывается значениями параметра t в диапазоне: 0    Ј   t   Ј   1. Таким образом, решение задачи двумерного отсечения эквивалентно решению неравенств (0.2.6) при условии 0    Ј   t    Ј   1. Решение этой задачи сводится к далее описанному отысканию максимумов и минимумов.

Вспомним, что для всех i таких, что P_i    <   0, условие видимости имеет вид: t    і   Q_i  /  P_i. Из условия принадлежности точек удлиненной линии отрезку V₀V₁ имеем t    і   0. Таким образом, нужно искать:

Аналогично, для всех i таких что P_i    >   0, условие видимости - t    Ј   Q_i  /  P_i и, следовательно, Ј 1.

Наконец, для всех i, таких что P_i    =   0 следует проверить знак Q_i. Если Q_i    <   0, то это случай тривиального отбрасывания, задача отсечения решена и дальнейшие вычисления не нужны. Если же Q_i    і   0, то информации, даваемой неравенством, недостаточно и это неравенство игнорируется.

Правая часть неравенств (0.2.11) и (0.2.12) - значения параметра t, соответствующие началу и концу видимого сегмента, соответственно. Обозначим эти значения как t₀ и t₁:

Если сегмент отрезка V₀V₁ видим, то ему соответствует интервал параметра:

Следовательно, необходимое условие видимости сегмента:

Но это недостаточное условие, так как оно игнорирует случай тривиального отбрасывания при P_i    =   0, если Q_i    <   0. Тем не менее это достаточное условие для отбрасывания, т.е. если t₀    >   t₁, то отрезок должен быть отброшен. Алгоритм проверяет, если P_i    =   0     c    Q_i    <   0, или t₀ > t₁ и в этом случае отрезок немедленно отбрасывается без дальнейших вычислений.

В алгоритме t₀ и t₁ инициализируются в 0 и 1, соответственно. Затем последовательно рассматривается каждое отношение Q_i/P_i.

Если P_i    <   0, то отношение вначале сравнивается с t₁ и, если оно больше t₁, то это случай отбрасывания. В противном случае оно сравнивается с t₀ и, если оно больше, то t₀ должно быть заменено на новое значение.

Если P_i > 0, то отношение вначале сравнивается с t₀ и, если оно меньше t₀, то это случай отбрасывания. В противном случае оно сравнивается с t₁ и, если оно меньше, то t₁ должно быть заменено на новое значение.

Наконец, если Pi    =   0   и  Q_i < 0, то это случай отбрасывания.

На последнем этапе алгоритма, если отрезок еще не отброшен, то t₀ и t₁ используются для вычисления соответствующих точек. Однако, если t₀ = 0, то конечная точка равна V₀ и не требуется вычислений. Аналогично, если t₁ = 1, то конечная точка - V₁ и вычисления также не нужны.

Геометрический смысл этого процесса состоит в том, что отрезок удлиняется для определения где эта удлиненная линия пересекает каждую линию границы. Более детально, каждая конечная точка заданного отрезка V₀V₁ используется как начальное значение для конечных точек отсеченного отрезка C₀C₁. Затем вычисляются точки пересечения удлиненной линии с каждой линией границы (эти вычисления соответствуют вызову процедуры LB_tclip в программе). Если для данной линии границы направление, определяемое V₀V₁, идет с невидимой на видимую сторону линии границы, то эта точка пересечения вначале сравнивается с С₁. Если точка находится далее вдоль линии, тогда C₁ (и таким образом, С₀С₁) должна быть на невидимой стороне линии, поэтому отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с С₀; если точка далее вдоль линии, тогда С₀ перемещается вперед к этой точке.

С другой стороны, если направление с видимой на невидимую сторону, тогда точка пересечения вначале сравнивается с С₀. Если С₀ далее вдоль линии, чем точка пересечения, тогда C₀ (и, следовательно C₀C₁) находится на невидимой стороне линии границы, т.е. отрезок должен быть отброшен. В противном случае точка пересечения сравнивается с С₁ и, если С₁ далее вдоль линии, тогда С₁ перемещается назад к точке пересечения.

Наконец, если удлиненная линия параллельна граничной линии и она на невидимой стороне, то отрезок отбрасывается. В конце алгоритма, если отрезок не отброшен, тогда C₀ и С₁ используются как конечные точки видимой части отрезка.

В Приложении 7 приведена C-подпрограмма V_LBclip, реализующая описанный выше алгоритм.

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

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

Для этих целей в алгоритме Кируса-Бека [29], реализующем отсечение произвольным выпуклым многоугольником, используется вектор внутренней нормали к ребру окна.

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

Рассмотрим основные идеи алгоритма Кируса-Бека.

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

Пусть N_i - внутренняя нормаль к i-й граничной линии окна, а P = V₁ - V₀ - вектор, определяющий ориентацию отсекаемого отрезка, тогда ориентация отрезка относительно i-й стороны окна определяется знаком скалярного произведения P_i    =   N_i ·V, равного произведению длин векторов на косинус наименьшего угла, требуемого для поворота вектора N_i до совпадения по направлению с вектором V:

a) Изнутри наружу

б) Параллельно границе

в) Снаружи внутрь

Для определения расположения точки относительно окна вспомним параметрическое представление отсекаемого отрезка:

Рассмотрим теперь скалярное произведение внутренней нормали N_i к i-й границе на вектор Q(t) = V(t) - F_i, начинающийся в начальной точке ребра окна и заканчивающийся в некоторой точке V(t) удлиненной линии.

Аналогично предыдущему имеем (рис. 0.2.15):

a) Точка V вне

б) Точка V на границе

в) Точка V внутри

Подставляя в (0.2.19) параметрическое представление (0.2.18), получим условие пересечения отрезка с границей окна:

Раскрывая скобки, получим:

Используя (0.2.16) и (0.2.19) перепишем (0.2.21):

Разрешая (0.2.22) относительно t, получим:

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

Как следует из (0.2.17), P_i равно нулю если отрезок либо вырожден в точку, либо параллелен границе. В этом случае следует проанализировать знак Q_i и принять или не принять решение об отбрасывании отрезка целиком в соответствии с условиями (0.2.17).

Если же P_i не равно 0, то уравнение (0.2.24) используется для вычисления значений параметров t, соответствующих точкам пересечений удлиненной линии с линиями границ.

Алгоритм построен следующим образом:

Искомые значения параметров t₀ и t₁ точек пересечения инициализируются значениями 0 и 1, соответствующими началу и концу отсекаемого отрезка.

Затем в цикле для каждой i-й стороны окна отсечения вычисляются значения скалярных произведений, входящих в (0.2.23).

Если очередное P_i равно 0, то отсекаемый отрезок либо вырожден в точку, либо параллелен i-й стороне окна. При этом достаточно проанализировать знак Q_i. Если Q_i < 0, то отрезок вне окна и отсечение закончено иначе рассматривается следующая сторона окна.

Если же P_i не равно 0, то по (0.2.24) можно вычислить значение параметра t для точки пересечения отсекаемого отрезка с i-й границей. Так как отрезок V₀V₁ соответствует диапазону 0 Ј t Ј 1, то все решения, выходящие за данный диапазон следует отбросить. Выбор оставшихся решений определяется знаком P_i.

Если P_i < 0, т.е. удлиненная линия направлена с внутренней на внешнюю стороны граничной линии, то ищутся значения параметра для конечной точки видимой части отрезка. В этом случае определяется минимальное значение из всех получаемых решений. Оно даст значение параметра t₁ для конечной точки отсеченного отрезка. Если текущее полученное значение t₁ окажется меньше, чем t₀, то отрезок отбрасывается, так как нарушено условие t₀    Ј   t₁.