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

**PheeL** · 02.03.2005, 16:50

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

**Advertiser** · 02.03.2005, 16:50

**Lion17** · 02.03.2005, 17:32

Есть метод Брезенхема, он использует только сложение и сравнение.
Ща попытаюсь вспомнить.
Во-первых сразу отсекаешь часные случаи - вертикальные и горизонтальные линии.
Вычисляешь приращения по 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) //выводим текущую точку
}

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

**Aprisobal** · 02.03.2005, 18:05

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

Код:

;в 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

**PheeL** · 02.03.2005, 18:19

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

**lvd** · 02.03.2005, 20:45

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

**lvd** · 02.03.2005, 21:02

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

**PheeL** · 02.03.2005, 21:25

Сообщение от 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, а он никак не синхронизирован с внутренним циклом программы и поэтому не могу четко выставить кол-во шагов вычислений. Может в начале их окажется больше чем к концу.

**fk0** · 03.03.2005, 14:46

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

**fk0** · 03.03.2005, 14:58

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

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

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

**PheeL** · 03.03.2005, 16:19

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

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

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

User Tag List

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

Опции темы

Отображение

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

Информация о теме

Пользователи, просматривающие эту тему

Похожие темы

Tutorial по технике рисования на ZX

Процедура опроса клавиатуры

Ваши права