Автоматизированное проектирование. Норенков И.П. - 94 стр.

 5@!"! 3                             %!#*%!#&F*:,$*     $I*:+*F*)&* !)!@&'! +($*,#)KH (*L*)&M

села) примем единицу. В алгоритме развертки номера строк и столбцов карты, на пересечении кото-
рых должны находиться точки отрезка, определяются следующим образом:
      1) ∆x := xb - xa; ∆y := yb - ya; x := xa; y := y);
      2) d = 2 ∆y - ∆x;
      3) если d ≥ 0, то {y := y+1; d := d + 2(∆y-∆x)}; иначе d := d + 2 ∆y;
      4) x := x + 1;
      5) переход к пункту 3, пока не достигнута точка (.
      Этот же алгоритм с небольшими модификациями используется и при других значениях
коэффициента a.
      Экономичность этого алгоритма обусловливается отсутствием длинных арифметических опера-
ций типа умножения.
      I.-$4$*'$ #%*) требуется при определении той части сцены, которая должна быть выведена на
экран дисплея.
      Пусть окно ограничено линиями x = x1, x = x2, y = y1, y = y2 (рис. 3.28).
Поочередно для каждого многоугольника проверяется расположение его вер-
шин и ребер относительно границ окна. Так, для многоугольника ABCD (см.
рис. 3.28) при отсечении по границе x = x2 просматривается множество вер-
шин в порядке обхода по часовой стрелке. Возможны четыре ситуации для
двух последовательных вершин P и R:
      1) если xp > x2 и xR > x2, то обе вершины и инцидентное им ребро нахо-
дятся вне окна и исключаются из дальнейшего анализа;                            %+,. 3.28. Выделение окна
      2) если xp ≤ x2 и xR ≤ x2, то обе вершины и инцидентное им ребро остаются для дальнейшего ана-
лиза;
      3) если xp ≤ x2 и xR > x2, то вершина % остается в списке вершин, а вершина R заменяется новой
вершиной с координатами x = x2, y = yp + (yR-yp)(x2-xP)/(xR-xP); в нашем примере такой новой верши-
ной будет &;
      4) если xp > x2 и xR ≤ x2, то вершина % заменяется новой вершиной с координатами x = x2,
y = yR + (yP-yR)(x2-xR)/(xP-xR), а вершина R остается в списке вершин; в нашем примере новой верши-
ной будет F.
      После окончания просмотра применительно ко всем границам в окне оказываются оставшиеся
в списке вершины.
      Применяя эти правила в нашем примере, получаем сначала многоугольник AEFD, а после отсе-
чения по верхней границе y = y2 — многоугольник AGFD (см. рис.3.28). Однако правильный резуль-
тат несколько иной, а именно многоугольник AGHFD. Этот правильный результат получается при
двойном обходе вершин сначала по часовой стрелке, затем против с включением в список новых вер-
шин, появляющихся при каждом обходе.
      Применяют ряд алгоритмов 7-)4$*'9 +%".&., 4'*';. Один из наиболее просто реализуемых ал-
горитмов — алгоритм z-буфера, где z-буфер — область памяти, число ячеек в которой равно числу
пикселов в окне вывода. Предполагается, что ось z направлена по нормали к видовой поверхности и
наблюдатель расположен в точке z = 0.
      В начале исполнения алгоритма все пикселы соответствуют максимальному значению z, т.е. мак-
симальному удалению от наблюдателя, что приводит к помещению во все ячейки z-буфера значений
пикселов фона картины (чертежа). Далее поочередно для всех точек граней рассчитываются значения
координаты z. Среди точек, относящихся к одному и тому же пикселу (одной и той же ячейке z-буфе-
ра S), выбирается точка с наименьшим значением z и ее код (т.е. цвет и яркость) помещается в S. В
итоге z-буфер будет содержать пикселы наиболее близких к наблюдателю граней.
      K48#"'&/. 0#+&"#$*'9 0"#$%='; преобразуют трехмерные изображения в двумерные. В случае
построения центральной проекции каждая точка трехмерного изображения отображается на картин-
ную поверхность путем пересчета координат x и y (рис. 3.29). Так, координату xa’ точки C’ вычисля-


 &.+.)$(*),$" . !"#$%!#&'&($"!))$*           +($*,#&($"!)&*                                        94