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

Вход на сайт

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

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

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

Скажите пожалуйста, подскажите алгоритм по которому по заданным точкам можно определить тип многогранника, скажем это куб или прямоугольный параллелепипед. Нашел теорию по этим фигурам: https://www.mat... https://www.mat... Акцентировать внимание...
Всем у кого не работает. файл wizard.script Ещё одно упоминание Glut32 в строке "if (!VerifyLibFile(dir_nomacro_lib, _T("glut32"), _T("GLUT's"))) return false;" меняем на "if (!VerifyLibFile(dir_nomacro_lib, _T("freeglut"), _T("GLUT's"))) return...
Не получается, емаё
огромное спасибо за подробное объяснение про 3д графику на питоне, в интернете очень мало подобной информации
dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?

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

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

Алгоритм Брезенхема смотрите на странице https://cgraph.ru/node/181

Алгоритм Брезенхема (англ. 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;   

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