§ Как рисовать линию?

Допустим, начало линии находится в (x_1,y_1) а конец ее находится в (x_2,y_2) , причем, x_2 \ge x_1, y_2 \ge y_1 .
Ясное дело, что если x_1 = x_2 или y_1 = y_2 , то это будут просто прямые линии, такие мы не будем рассматривать, потому что это слишком было бы просто. Нужно нагрузиться материалом так, чтобы мама не горевала.
Я должен вспомнить уравнение прямой, заданной параметрически:

x = x_1 + t(x_2 - x_1)




y = y_1 + t(y_2 - y_1)


То есть тут параметр t указывает на то, где именно мы берем точку, и если t = 0 , то точка будет тут (x,y) = (x_1,y_1) , если t = 1 , то правая точка будет находиться в (x,y) = (x_2,y_2)
Еще один важный момент, который нельзя упускать из виду: дело в том, что когда мы работаем с дисплеем, то любой, абы какой t брать нельзя, потому что пиксели там, а не непрерывное что-то, и потому t можно брать равным так, чтобы y попадал в пиксели ровно.
Задача такая: найти t по y . Все просто, берем уравнение y = y_1 + t(y_2 - y_1)
и начинаем находить t по y , перенося и деля:
t = \frac{y - y_1}{y_2 - y_1}
Отлично. Теперь надо подставить полученный t в уравнение x = x_1 + t(x_2 - x_1) .
x = x_1 + \frac{y - y_1}{y_2 - y_1}(x_2 - x_1)
То есть, вуаля - и все работает через магический вхуж.
А теперь давайте просто рассмотрим по шагам весь этот странный процесс. Допустим на секунду, что y = y1 , что тогда будет? Из верхней формулы ясно и четко видно, что будет y_1 - y_1 = 0 , и все справа обнулится, кроме x_1 :
x = x_1 + \frac{y_1 - y_1}{y_2 - y_1}(x_2 - x_1) = x_1
Но! Поскольку у нас все попиксельно (да?), то тогда следующий x должен быть равен y = y + 1 .

§ Инкрементальное вычисление

Конечно, можно брать и вычислять x , основываясь на y , по той формуле, что сверху написана. Но такие вычисления ужасно затратны, ясное дело. Намного легче вычислять приращение. Почему? Потому что y - не дробное число, и поэтому будет принимать значения от y_1 до y_2 , например, если y_1=10 а y_2=15 , то тогда y будет принимать только такие значения 10, 11, 12, 13, 14 и 15. Это значит, что если мы знаем x , который получается после вычисления y , то тогда можно узнать x_{n+1} , который получится путем определения разности между y_{n+1} - y_n . Тяжело... короче, легче на примере показать
Пример:
(x_1,y_1) = (5,12) , (x_2,y_2) = (10,16)
Теперь построю таблицу, понимая, что y может принимать значения только от 12 до 16, и только целочисленные.
y x_1 + \frac{y - y_1}{y_2 - y_1}(x_2 - x_1) x \Delta x
12 5 + \frac{12 - 12}{16 - 12}(10 - 5) = 5 + \frac{12 - 12}{4}5 51,25
13 5 + \frac{13 - 12}{4}5 6,251,25
14 5 + \frac{2}{4}5 7,51,25
15 5 + \frac{3}{4}5 8,751,25
16 5 + \frac{4}{4}5 10
Нетрудно заметить, что приращение \Delta x никак не увеличивается. И это валидно, ибо дело имеем мы с "линейной функцией", а то есть, линией. А линия, как известно, является прямой, без загогулин, и потому в любой точке ее приращение будет тем же самым.
Почему так получается? Элементарно же! Я сделаю расчет, который покажет, что все так. Надо взять любой y , добавить к нему +1 и рассчитать формулу, и потом из этой формулы числить формулу, которая просто с y , чтобы узнать, что все действительно в порядке.
x_{y+1} = x_1 + \frac{(y + 1) - y_1}{y_2 - y_1}(x_2 - x_1)
x_y = x_1 + \frac{y - y_1}{y_2 - y_1}(x_2 - x_1)
Так вычтем же!
\Delta{x} = x_{y+1} - x_y = x_1 + \frac{(y + 1) - y_1}{y_2 - y_1}(x_2 - x_1) - (x_1 + \frac{y - y_1}{y_2 - y_1}(x_2 - x_1))
Начинается магия разложения. Сначала я удалю отсюда лишние иксы
\Delta{x} = \frac{(y + 1) - y_1}{y_2 - y_1}(x_2 - x_1) - \frac{y - y_1}{y_2 - y_1}(x_2 - x_1)
А потом разложу числители
\Delta{x} = \frac{x_2 - x_1}{y_2 - y_1} + \frac{y(x_2 - x_1)}{y_2 - y_1} - \frac{y(x_2 - x_1)}{y_2 - y_1} + \frac{y_1(x_2 - x_1)}{y_2 - y_1} - \frac{y_1(x_2 - x_1)}{y_2 - y_1}
Осталось удалить не нужное (сократить)
\Delta{x} = x_{y+1} - x_y = \frac{x_2 - x_1}{y_2 - y_1}
Опупеть можно! Почему так сложно делается то, что можно было в уме легко сделать? В математике простых путей не ищут, потому надо нагородить формул, чтобы умнее выглядеть. Вот и ответ. А это еще даже до сути особо не добрались.
На самом деле, тут показано, что можно с помощью обычного приращения построить линию. Единственное, что никак не построишь никакую линию для случая, когда линия прямая, то есть когда y_1 = y_2 .

§ Как переделать в целочисленность?

На самом деле тут так все элементарно, что не знаю, как бы еще доступнее объяснить! Возьму линию (2,4)-(3,8), вычислю \Delta x = 3-2 = 1 , \Delta y = 8-4 = 4 , а значит, приращение с каждым разом будет x_{y+1} = x_y + \frac{\Delta x}{\Delta y} , что совершенно естественно в данном случае.
Нетрудно заметить, что приращение получается дробным, а именно всегда рациональной дробью. То что это всегда рациональная дробь, и может спасти всех нас от замедления скорости.
Достану таблицу и расскажу что да как:
y x +dx [x] сумма
42,00+0,2520 : 4
52,25+0,2521 : 4
62,50+0,2522 : 4
72,75+0,2523 : 4
83,00+0,2524 : 4
В первой и второй колонке (где игрек и икс) находятся координаты следующей точки для построения. В третьей колонке - величина приращения при добавлении +1, а в четвертой как раз самое интересное - это общая сумма при постоянном приращении
Вот действительно, если встать на начальную точку, что x = x_1 , если добавить приращение, то тогда будет так
x = x_1 + \frac{\Delta x}{\Delta y}
Если добавить еще раз приращение, то будет так
x = x_1 + \frac{\Delta x}{\Delta y} + \frac{\Delta x}{\Delta y} = x_1 + \frac{2\Delta x}{\Delta y}
И так далее. Теперь как применить к случаю выше:
x = x_1 + \frac{1}{4} + .. + \frac{1}{4} = \frac{4}{4} = 1
Как можно заметить, числитель равномерно складывается, а знаменатель (снизу), остается тем же самым. Это на руку. То есть можно просто сделать так
Y = Y + 1
Числитель = Числитель + (x2-x1)
ПОКА Числитель >= Знаменатель
    Числитель = Числитель - Знаменатель
    X = X + 1
То есть суть такая, что пока числитель меньше знаменателя, то целочисленное значение X не увеличивается (а дробное не нужно), но как только числитель превышает знаменатель, то надо увеличивать X столько раз, пока числитель не станет меньше знаменателя (это вообще процедура деления, между прочим, из 5-го класса!)
Не, ну ты это видел? Это же элементарно и так круто! Вот так и работает рисование линии с помощью целочисленных операции. Ничего сложного, не считая статью сверху.

§ Но есть нюанс

Если внезапно глянуть наверх, то можно увидеть (свернув шею), что последовательность точек по X будет такой: 2, 2, 2, 2, 3. То есть это линия, которая выглядит очень некрасиво! Как исправить? Все просто - надо делать так, чтобы проверялся выход не за пределы полного знаменателя, а через его половину!
Другими словами:
Y = Y + 1
Числитель = Числитель + (x2-x1)
ПОКА Числитель >= (Знаменатель / 2)
    Числитель = Числитель - Знаменатель
    X = X + 1
Ну либо домножить на 2
ПОКА 2*Числитель >= Знаменатель
И будет всем счастье! И все равно Брезенхэм лучше!
21 окт, 2019
© 2007-2022 Джерри улетает в парке