Цитата Сообщение от PheeL
Пишу тут дипломчик (софт для кардиостимулятора) и возникла проблема написания процедуры линии для соединения двух точек табличного графика. Немного оффтопично, но внутри микроконтроллера стоит ядро Intel8052. В принципе, устроит и процедура под Z80 ибо меня интересует в конечном итоге сам алгоритм, потому как я сам не нашел ничего лучше чем в лоб запрограммировать формулу : (Y1 - Y0) \ (X1 - X0) * dX (доп. часть формулы я выкинул - она поднимает точку на заданную высоту. Я заменил сложением\вычитанием)
Но при таком раскладе мне приходится делать 16-ти битное (таблица 16-ти битная) деление и умножение, что есть сакс хоть ядро и работает на 12-20 МГц. Есть ли способ хитрее? Как-нибудь с 16-ти битной арифметикой, но без извратов (т.е. без умножения\деления) ? Вычисления целочисленные, беззнаковые. Обе координаты соединяемых точек (X0,Y0 и X1,Y1) имеют 16-ти битные значения.
Вопрос - тебе именно линию надо, т.е. например надо рассчитать Y-ки для всех (X1-X0) точек с шагом 1, или же просто по произвольным параметрам X0,X1,Y0,Y1,dX вычислить формулу? Если второе - то оставь как есть, линия тут не при чём.

Если первое - попробую объяснить доходчиво, что такое алгоритм брезенхема и откуда он получается:

Для ясности упростим формулу до вида y=x*(Y/X), где линия рисуется из точки 0,0 в точку X,Y, x - текущий, для которого хотим посчитать y. Также предположим, что Y<X (т.е. линия под углом менее 45% к горизонтальной оси) и что X>0, Y>0.

Подумаем, что происходит с формулой, когда x увеличивается от 0 до X c шагом 1. Сначала x=1 и (x*Y)/X=0, потому что x*Y=1*Y<X. Потом x=2,3,4... etc, пока x*Y не станет больше X. Аналогично y станет 2, когда x*Y станет больше 2*X.

Теперь прикинем - если x увеличивается с шагом 1, зачем умножение? Выкидываем, вводим переменную z, к которой прибавляем Y. z=z+Y; y=z/X.

Выкидываем и деление - заметив, что как только z станет больше X, можно инкрементировать y на 1. А что делать при этом с z? А очень просто - вычесть из него X! =) Таким образом z у нас всегда есть остаток от деления x*Y на X. И как только этот остаток становится больше X, мы понимаем, что результат деления увеличился на 1 и надо увеличить y. А остаток корректируем, вычитая X.

Вот собственно и образовался алгоритм брезенхема.

init: z=0; x=0; y=0;

loop: x=x+1;
z=z+Y;
if(z>X) {z=z-X; y=y+1;}
setpoint(x,y);
go to loop

Обрати внимание, что он в таком виде применим только когда X>Y.
При рисовании линии обычно делят всё множество направлений на 4 кусочка, в каждом из которых либо X>Y, либо Y>X.