Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.
Спасибо за статью. Я не Ваш студент. Но мне она помогла написать функцию для Канторова множества на Python для черепашки: import turtle def kanter(x, y, d):     if d > 1:         turtle...
Как реализовать в данном примере границы расчёта?

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

Важными характеристиками изображения являются:

  • - количество пикселей. Может указываться отдельно количество пикселей по ширине и высоте (1024*768, 640*480,...) или же, редко, общее количество пикселей (обычно измеряется в мегапикселях);
  • - количество используемых цветов (или глубина цвета);
  • - цветовое пространство RGB, CMYK, XYZ, YCbCr и др.

Алгоритм Брезенхема (англ. Bresenham's line algorithm) — это алгоритм, определяющий, какие точки двумерного растра нужно закрасить, чтобы получить близкое приближение прямой линии между двумя заданными точками. Это один из старейших алгоритмов в машинной графике — он был разработан Джеком Е. Брезенхемом (Jack E. Bresenham) в компании IBM в 1962 году. Алгоритм широко используется, в частности, для рисования линий на экране компьютера.

В алгоритме используется управляющая переменная di, которая на каждом шаге пропорциональна разности между s и t (см. рис.1). На рисунке 1 приведен i-ый шаг, когда пиксель Pi-1 уже найден как ближайший к реальному изображаемому отрезку, и теперь требуется определить, какой из пикселей должен быть установлен следующим: Ti или Si.


Рис.1

Если s < t, то Si ближе к отрезку и необходимо выбрать его; в противном случае ближе находится Ti. Другими словами, если s -t < 0, то выбирается Si; иначе выбирается Ti.

Отрезок в примере (на рис.1) проводится из точки (x1, y1) в точку (x2, y2). Пусть первая точка находится ближе к началу координат, тогда вычтем из соответствующих координат x1 и y1 тем самым перенеся первую точку в начало координат, тогда конечная окажется в (Δx, Δy), где Δx = x2 - x1, Δy = y2 - y1. Уравнение прямой теперь имеет вид y = x(Δy / Δx). В рассматриваемом примере предполагается, что Δx >= Δy и Δy >= 0.

Из рисунка 1 следует, что

s = (Δy / Δx)(x + 1) - y,

t = y + 1 - (Δy / Δx)(x + 1)

поэтому

s - t = 2( Δy / Δx)(x + 1) - 2y - 1.

Домножим обе части равенства на Δx:

Δx(s - t) = 2(Δy•x - y•Δx) + 2Δy - Δx.

Так как Δx > 0, то величину Δx(s-t) можно использовать в качестве критерия для выбора пикселя. Обозначим эту величину di:

di = 2(Δy•xi-1 - yi-1•Δx) + 2Δy - Δx.

Так как di надо считать на каждом шаге, рассчитаем величину Δi — приращения di:

Δi = di - di-1 = 2Δy(xi - xi-1) - 2Δx(yi - yi-1).

Известно, что xi – xi-1 = 1.

Если di >= 0, то выбираем Ti, т.е. yi — yi-1 = 1 (перемещаем точку по y), а Δi тогда равно

Δi = 2(Δy - Δx).

Если di < 0, то выбираем Si, т.е. yi — yi-1 = 0 (у не меняется), тогда Δi = 2Δy.

Таким образом, мы получили итеративную формулу для вычисления критерия di.

Начальное значение d1 = 2Δy - Δx.

Важно учитывать, что такой алгоритм требует определения ещё одного параметра — значения, определяющего изменение yi. В примере мы предполагали Δy >= 0, а потому при перемещении точки изменяли значение на +1. Если значение Δy < 0, то изменение происходит на -1.

Аналогично рассматривается случай, когда Δx < Δy. Алгоритм Брезенхэма в своей реализации требует учёт всех возможных ситуаций взаимного расположения точек.

Procedure line (x1, y1, x2, y2: Integer);
var dx, dy, d, d1, d2, x, y, stp: Integer;
begin
  dx := x2 - x1;
  dy := y2 - y1;
  if ((abs(dx) > abs(dy)) and (x2 < x1))
    or ((abs(dx) <= abs(dy)) and (y2 < y1)) then begin
      x := x1;
      x1 := x2;
      x2 := x;
      y := y1;
      y1 := y2;
      y2 := y;
  end;
  dx := x2 - x1;
  dy := y2 - y1;
  stp := 1;
  putpixel(x1, y1, clblack);
  if (abs(dx) > abs(dy)) then begin
    if (dy < 0) then begin
      stp := -1;
      dy := -dy;
    end;
    d := (dy * 2) - dx;
    d1 := dy * 2;
    d2 := (dy - dx) * 2;
    y := y1;
    for x := x1 + 1 to x2 do begin
      if (d > 0) then begin
        y := y + stp;
        d := d + d2;
      end else
        d := d + d1;
      putpixel(x, y, clblack);
    end;
  end else begin
    if (dx < 0) then begin
      stp := -1;
      dx := -dx;
    end;
    d := (dx * 2) - dy;
    d1 := dx * 2;
    d2 := (dx - dy) * 2;
    x := x1;
    for y := y1 + 1 to y2 do begin
      if (d > 0) then begin
        x := x + stp;
        d := d + d2;
      end else
        d:=d+d1;
      putpixel(x, y, clblack);
    end;
  end;
end;   

Демонстрационные примеры по теме