Линейная интерполяция или процедура рисования линни

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

Есть метод Брезенхема, он использует только сложение и сравнение.
Ща попытаюсь вспомнить.
Во-первых сразу отсекаешь часные случаи - вертикальные и горизонтальные линии.
Вычисляешь приращения по X и по Y (оно или +1 или -1)
if(Crd.End>Crd.Start) Crd.Pri=1 else Crd.Pri=-1
теперь вычисляешь расстояния по X и Y
берешь Crd.Len=Abs(Crd.End-Crd.Start) те по модулю
выбираем дельту - меньшее растояние Delta=Min(X.Len,Y.Len)
теперь чертим линию
Point(X,Y) //первая точка (не обязательно)
YPos=0; XPos=0 //инициализация итерации
while(X!=X.End && Y!=Y.End){ // пока не дошли до конечной точки
YPos+=Delta; XPos+=Delta; //приращения
if(YPos>Delta) {Y+=X.Pri; Ypos-=Delta;} //шагаем по Y
if(XPos>Delta) {X+=Y.Pri; XPos-=Delta;} //шагаем по X
Point(X,Y) //выводим текущую точку
}

Вот и весь алгоритм, очень быстрый

Вот процедура. Вроде бы брал из какого-то журнала...

Код:

;в HL - YX начала ;в DE - YX конца LINE LD A,H SUB D JR NC,LINE1 EX DE,HL NEG LINE1 LD H,A LD A,L SUB E LD BC,#141C JR NC,LINE2 INC C NEG LINE2 CP H LD L,A JR C,LINE3 LD L,H LD H,A LD A,B LD B,C LD C,A LINE3 LD A,B LD (LINE5),A LD A,C LD (LINE6),A LD B,H LD A,H INC L INC B LINE4 CALL PLOT ;здесь печать точки - в DE координаты YX LINE5 NOP SUB L JR NC,LINE7 LINE6 NOP ADD A,H LINE7 DJNZ LINE4 RET

Всем ответившим - большое спасибо!
Попробую разобраться и применить. Программист из меня слабенький, а дипломы по рисункам в институте не принимают :)

Цитата:

Сообщение от aprisobal

Вот процедура. Вроде бы брал из какого-то журнала...
[skip]

Тихий ужас... :) :) :) Вот как выглядит более-менее приличная по скорости линия: =)

Код:

; LINE DRAWING/ETC. ;buffer: H - y, L - x LNBUF EQU #B000 ;strt of lin buffer LINDRAW ;draw line ;HL - BEGIN COORDS ;DE - END COORDS ; ;H,D - Y ;L,E - X ; ; deltaX and deltaY < 128 !!! ;brezenham algorithm ;idea of SET N,(HL) taken from SPAZM LD A,D SUB H JR NC,NOSWAP NEG EX DE,HL NOSWAP ;HL - UPPER THAN DE (H<=D) LD D,A ; DELTA Y LD A,E SUB L JP NC,LNRT ; LINE TO RIGHT ;LINE TO LEFT LNLF NEG LD E,A ; DELTA X LD A,D SUB E JR C,LFHZ ; HORIZONTAL ;VERTICAL LEFT LFVR LD A,L ; CALC ENTRY POINT CPL AND 7 LD C,A ADD A,A ADD A,A ADD A,A ADD A,C LD (VRLF_J+1),A LD A,L ; X BUFFER POS RRA RRA RRA AND #1F LD L,A LD A,'LNBUF; Y BUFFER POS ADD A,H LD H,A LD B,D ; LOOP COUNTER LD A,D SLA D SLA E ;MIDDLE CORRECTION VRLF_J JR $ MACRO VRLF SET \0,(HL) INC H DEC B RET M SUB E JR NC,$-6 ADD A,D ENDM VRLF_L VRLF 0 VRLF 1 VRLF 2 VRLF 3 VRLF 4 VRLF 5 VRLF 6 VRLF 7 DEC L JR VRLF_L ;HORIZONTAL LEFT LFHZ LD A,L ; CALC ENTRY POINT CPL AND 7 LD C,A ADD A,A ADD A,A ADD A,A ADD A,C LD (HZLF_J+1),A LD A,L ; X BUFFER POS RRA RRA RRA AND #1F LD L,A LD A,'LNBUF; Y BUFFER POS ADD A,H LD H,A LD B,E ; LOOP COUNTER LD A,E SLA E ;MIDDLE CORRECTION SLA D HZLF_J JR $ MACRO HZLF SET \0,(HL) DEC B RET M SUB D JR NC,$+4 ADD A,E INC H ENDM HZLF_L HZLF 0 HZLF 1 HZLF 2 HZLF 3 HZLF 4 HZLF 5 HZLF 6 HZLF 7 DEC L JR HZLF_L LNRT LD E,A ; DELTA X LD A,D SUB E JR C,RTHZ ; HORIZONTAL ;VERTICAL RIGHT RTVR LD A,L ; CALC ENTRY POINT AND 7 LD C,A ADD A,A ADD A,A ADD A,A ADD A,C LD (VRRT_J+1),A LD A,L ; X BUFFER POS RRA RRA RRA AND #1F LD L,A LD A,'LNBUF; Y BUFFER POS ADD A,H LD H,A LD B,D ; LOOP COUNTER LD A,D SLA D SLA E ;MIDDLE CORRECTION VRRT_J JR $ MACRO VRRT SET \0,(HL) INC H DEC B RET M SUB E JR NC,$-6 ADD A,D ENDM VRRT_L VRRT 7 VRRT 6 VRRT 5 VRRT 4 VRRT 3 VRRT 2 VRRT 1 VRRT 0 INC L JR VRRT_L ;HORIZONTAL RIGHT RTHZ LD A,L ; CALC ENTRY POINT AND 7 LD C,A ADD A,A ADD A,A ADD A,A ADD A,C LD (HZRT_J+1),A LD A,L ; X BUFFER POS RRA RRA RRA AND #1F LD L,A LD A,'LNBUF; Y BUFFER POS ADD A,H LD H,A LD B,E ; LOOP COUNTER LD A,E SLA E ;MIDDLE CORRECTION SLA D HZRT_J JR $ MACRO HZRT SET \0,(HL) DEC B RET M SUB D JR NC,$+4 ADD A,E INC H ENDM HZRT_L HZRT 7 HZRT 6 HZRT 5 HZRT 4 HZRT 3 HZRT 2 HZRT 1 HZRT 0 INC L JR HZRT_L

Небольшой комментарий: буфер имеет вид: H - y-координата, L - x-координата. Конечно зажор памяти афуенный, но окошко было маленькое, а вывод из такого буфера чуть быстрее, чем ld e,(hl):inc h:ld d,(hl):inc h : push de ....

Цитата:

Сообщение от 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.

Цитата:

Сообщение от lvd

Вопрос - тебе именно линию надо, т.е. например надо рассчитать Y-ки для всех (X1-X0) точек с шагом 1, или же просто по произвольным параметрам X0,X1,Y0,Y1,dX вычислить формулу? Если второе - то оставь как есть, линия тут не при чём.

Именно первое.

Попробую детально рассказать что надо. Есть некая таблица (синус, треугольник или др. произвольный вид). В ней содержатся значения Y (вывожу их на ЦАП - получаю напряжение) в 16-ти битном виде, т.е. таблица выглядит так :
...
DB #0DAh, #069h
DB #0DCh, #09Ah
DB ...
...
Далее. Есть 16-ти битный счетчик Timer0. Когда он обнуляется происходит прерывание. Значением этого счетчика я задаю задержку между считыванием последующих значений (Y) из таблицы. Т.е. беру первое значение из таблицы и второе. Это мои Y0 и Y1 . Потом ставлю Timer0 в исходное положение (допустим #0E1Ah) - это моё значение X0. Соответственно максимальное значение после которого происходит обнуление таймера и берется следующее значение из таблицы будет #FFFFh - это моё X1. Таймер крутится в своём внутреннем цикле независимо от программы (он связан с тактовым генератором). Программно считывая его значение по мере исполнения программы после нехитрых вычислений я получаю deltaX. Далее использую классическую формулу которую я приводил в начале темы. Вот собсно вся задача.

За разъяснение метода Брезенхема большое спасибо, потому как я по незнанию пытался придумать его сам %)))

P.S. Да, я тут подумал и понял, что число итераций между X0 и X1 у меня непредсказуемо. Я могу в любое время считать значение Timer0, а он никак не синхронизирован с внутренним циклом программы и поэтому не могу четко выставить кол-во шагов вычислений. Может в начале их окажется больше чем к концу.

Цитата:

Сообщение от PheeL

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

x51 имеет аппаратный умножитель! Какие, нафиг, таблицы?
В даташит глянь!

Цитата:

Как-нибудь с 16-ти битной арифметикой, но без извратов (т.е. без умножения\деления) ? Вычисления целочисленные, беззнаковые. Обе координаты соединяемых точек (X0,Y0 и X1,Y1) имеют 16-ти битные значения.

А это, алгоритм брезентхема: http://algolist.manual.ru/graphics/painting/line.php

Цитата:

Сообщение от PheeL

Именно первое.
P.S. Да, я тут подумал и понял, что число итераций между X0 и X1 у меня непредсказуемо. Я могу в любое время считать значение Timer0, а он никак не синхронизирован с внутренним циклом программы и поэтому не могу четко выставить кол-во шагов вычислений. Может в начале их окажется больше чем к концу.

U tebq имеет место быть классическая задача линейной интерполяции.
http://algolist.manual.ru/maths/approx.php, и с построением прямой оно
никак не связано.

Цитата:

Сообщение от fk0

U tebq имеет место быть классическая задача линейной интерполяции.
http://algolist.manual.ru/maths/approx.php, и с построением прямой оно
никак не связано.

Да, скорее всего я ошибся в определении. Спасибо за ссылку!

Цитата:

Сообщение от fk0

x51 имеет аппаратный умножитель! Какие, нафиг, таблицы?
В даташит глянь!

Один хрен возня будет, когда 16x16 при помощи A и B будет компайлер считать.

Да и с делением засада.

Цитата:

Сообщение от lvd

Один хрен возня будет, когда 16x16 при помощи A и B будет компайлер считать.

Да и с делением засада.

Совершенно верно. Абсолютно бесполезные команды для решения моей задачи (в процедуре деления команда div вообще не используется ни разу). Этот момент я хорошо понял когда посмотрел на сайте www.8052.com набор арифметических процедур для контроллера. Данные команды подходят только для 8-ми битных операций. Даташитсы я ессно от начала и до конца изучил.

Да, и ещё - я все-таки не понял, подходит ли метод Брезенхема для решения моей задачи или он работает только для заранее известного кол-ва вычислений? Или я останавливаюсь на своей реализации классической формулы для такого типа задачи (благо она уже работает)?

Цитата:

Сообщение от PheeL

Совершенно верно. Абсолютно бесполезные команды для решения моей задачи (в процедуре деления команда div вообще не используется ни разу). Этот момент я хорошо понял когда посмотрел на сайте www.8052.com набор арифметических процедур для контроллера. Данные команды подходят только для 8-ми битных операций. Даташитсы я ессно от начала и до конца изучил.

Ну да - деление в топку, но вот таки умножение полезно. 16x16->32 можно делать столбиком из четырёх 8x8->16 и большой возни =)

Цитата:

Да, и ещё - я все-таки не понял, подходит ли метод Брезенхема для решения моей задачи или он работает только для заранее известного кол-ва вычислений? Или я останавливаюсь на своей реализации классической формулы для такого типа задачи (благо она уже работает)?

Брезенхем применим, когда у тебя шаг по одной координате всегда 1, и надо посчитать вторую. У тебя видимо это не так, так что брезенхем не подойдёт.
Кстати, ты на сях пишешь? Работать и успешно выполнять свою задачу код успевает? Ну так и забей =) Лучше на forever 1к-интру накодь =)

Цитата:

Сообщение от lvd

Брезенхем применим, когда у тебя шаг по одной координате всегда 1, и надо посчитать вторую. У тебя видимо это не так, так что брезенхем не подойдёт.
Кстати, ты на сях пишешь? Работать и успешно выполнять свою задачу код успевает? Ну так и забей =)

Да, значит все-таки Брезенхем не подойдет. А жаль, он бы здорово убыстрил вычисления.

Сам импульсный табличный генератор я пишу на голом асме. Процедура небольшая да и низкоуровневое программирование мне ближе. Также будет написана "связка" в виде редактора табличек с последующим заливанием их в память контроллера. Эту часть я реализую на Delphi, так как мне нужна лёгкость и гибкость в программировании именно интерфейсной части.
Там вся байда по скорости в том, что моя процедура будет входить в состав многозадачного ядра (мой препод по диплому мощный персонаж - переделал ядро QNX под I8052) и будет высокий приоритет по исполнению, но отнюдь не наивысший. Поэтому кол-во итераций будет прямо пропорционально кол-ву вызовов моей процедуры этим ядром. В этом моменте и отпадает метод Брезенхема. Но поскольку контроллер работает на частоте ~20 МГц (на самом деле используется ADuC842, поэтому и такие частоты ядра), и команды исполняются за 1 такт, то вроде бы скорости хватает. Реальной железки у меня нет, но на эмуляторе по выходным значениям напряжения от времени с DAC вроде бы все в порядке (я даже граф. анализатор на Дельфях для этого накатал :) ).

Цитата:

Сообщение от char

ну как успехи, давно не слышно :)
или уже полностью ld de,Кипр? ;)

Да какой тут Кипр... На кафедре разборки между преподами и я как раз нечаянно меж двух огней попадаю.
Насчет процедуры. Твой метод верный и он будет работать. Но! При больших задержках между вызовами процедуры интерполяции, соответственно возрастает и кол-во вызовов процедуры рисующей отрезок по методу Брезенхема. Ну понятно, да? Чтобы высчитать следующую точку ему надо построить отрезок до неё и если расстояние между точками в следствие задержки возрастает, то пропорционально возрастает и кол-во вызовов процедуры и также пропорционально снижается скорость. И может наступить такой момент, что из-за возросшего числа вызовов вся прелесть метода по части отсутствия умножения и деления уйдет в нуль, а то и в минус. Моя же реализация классической формулы будет тормозить всегда одинаково в любой вычисляемой точке :)