Графика машинная

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

$y(x)\; =\; (y2-y1)/(x2-x1)*(x-x1)\; +\; y1$

Представляем это уравнение, как функцию ошибки. В начальной точке y(x=x1) = y1, ошибка - отклонение от линии по Eps(x=x1) = 0. Отклонение накапливается с каждым шагом вдоль оси Х.

$Eps(x+1)\; :=\; Eps(x)\; +\; (y(x+1)\; -\; y(x))$
$Eps(x+1)\; :=\; Eps(x)\; +\; (y2-y1)/(x2-x1)$

На каждом шаге вдоль оси X надо прибавлять дробь. Если ошибка становится больше Eps>=0.5, то прибавляем, делаем шаг вдоль оси Y. На каждом шаге мы стремимся уменьшить ошибку, выполняем округление к ближайщему целому числу. Надо понимать, что мы вместо вещественных чисел работаем с дробными. С нормальными дробями, вещественные числа представляем в виде A/D = Q(R/D), где Q - целая часть от деления, R- остаток от деления, D- делитель.

X ++;
Y += Q;
Eps += R/D;
if (Eps >= 0.5) {
    Eps -= 1.0;
    Y ++;
}

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

От вещественных чисел можно перейти к целым, домножив Eps на 2D

X ++;
Y += Q;
Eps += 2*R;
if (Eps >= D) {
    Eps -= 2*D;
    Y ++;
}

До меня этот алгоритм предложил Бразенхейм. Однако, простое человеческое осмысление способа синтезирования подобных алгоритмов я подсмотрел в своей голове.

Парабола

$y(x)\; =\; A*x^2\; +\; B*x\; +\; C$
$Eps(x+1)\; :=\; Eps(x)\; +\; 2A*x\; +\; 1\; +\; B$

x ++;
Eps += 2A*x + (1 + B);
if (Eps >= 0.5) {
    Eps -= 1.0;
    y ++;
}

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

$Eps(x,y)\; =\; A*x^2\; +\; B*x\; +\; C\; -\; y$
$Eps(x,y+1)\; :=\; Eps(x,y)\; -\; 1$
$Eps(x+1,y+1)\; :=\; Eps(x,y)\; +\; 2A*x\; +\; B$

На каждом шаге мы сравниваем две величины Eps(x,y+1) и Eps(x+1,y+1)

y ++;
Eps --;
Eps1 = Eps + 2A*x + (1 + B);
if (-Eps > Eps1) {
    Eps = Eps1;
    x ++;
}

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

Дуга окружности

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

$Eps(x,y)\; =\; x^2\; +\; y^2\; -\; R^2$
$Eps(x+1,y)\; :=\; Eps(x,y)\; +\; 2x+1$
$Eps(x+1,y-1)\; :=\; Eps(x+1,y)\; -\; 2y\; +\; 1$

x ++;
Eps += 2*x + 1;
Eps1 = Eps - 2*y + 1;
if (Eps > -Eps1) {
    Eps = Eps1;
    y --;
}

Экспонента и логарифм

Как мы ранее показали на примере параболы, нам ничего не стоит перейти от вычисления прямой функции к обратной. Но вот если прямая функция определена "криво", что делать? А что такое экспонента, как она вообще в математику попала. Её определяют через .. никак не определяют, и через разложение в ряд - криво и приближенно, бесконечно- не возможно, и через дробь - бесконечно и не возможно, через предел - бесконечно криво. Все, что связано с бесконечно малыми или бесконечно большими не применимо для вычислений. Нормально экспоненту можно определить только через дифференциальное уравнение, решением которого является искомая функция. Движение вдоль экспоненты - это решение дифференциального уравнения. Функцию ошибки введем из диф.ура.

$dy/dx\; =\; -y/T$
$Tdy\; =\; -ydx$
$Eps(x,y)\; =\; y*dx\; +\; T*dy$
$Eps(x+1,y)\; :=\; Eps(x,y)\; +\; y$
$Eps(x+1,y-1)\; :=\; Eps(x+1,y)\; -\; T$

x ++;
Eps += y;
Eps1 = Eps - T;
if (Eps > -Eps1) {
    Eps = Eps1;
    y --;
}

Тут мы сравниваем две ошибки, Eps(x+1,y) и Eps(x+1,y-1), стараемся уменьшить ошибку. Ранее мы сравнивали ошибку с 0.5, и округляли к ближайшему целому. В общем виде можно представить как минимизация ошибки (отклонения от уравнения).

Логарифм - обратная функция. Значит и вычислят ее нужно относительно оси Y

$Eps(x,y)\; =\; y*dx\; -\; T*dy$
$Eps(x,y+1)\; :=\; Eps(x,y)\; -\; T$
$Eps(x+1,y+1)\; :=\; Eps(x,y+1)\; +\; y$

y ++;
Eps -= T;
Eps1 = Eps + y;
if (-Eps > Eps1) {
    Eps = Eps1;
    x ++;
}

Синус и косинус

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

$dy/dt\; =\; x/T$
dx/dt = -y/T
$Tdy\; =\; xdt,\; Tdx\; =\; -ydt$
$C(x,dy,dt)\; =\; x*dt\; -\; T*dy,\; шаг\; алгоритма\; dt=1$
$S(dx,y,dt)\; =\; y*dt\; +\; T*dx,\; шаг\; алгоритма\; dt=1$

На каждом шаге dt=1

$C(x,0,+1)\; :=\; C(x,0,0)\; +\; x$
$S(0,y,+1)\; :=\; S(0,y,0)\; +\; y$
$C(x,+1,0)\; :=\; C(x,0,0)\; -\; T$
$S(+1,y,0)\; :=\; S(0,y,0)\; +\; T$

Предлагаю синтезировать алгоритм самостоятельно...

Полагаю возможным синтезировать алгоритм из любой системы линейных дифференциальных уравнений.