Важная информация

User Tag List

Страница 1 из 2 12 ПоследняяПоследняя
Показано с 1 по 10 из 15

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

  1. #1
    Activist Аватар для PheeL
    Регистрация
    19.01.2005
    Адрес
    Москва
    Сообщений
    329
    Благодарностей: 94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

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

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

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Master
    Регистрация
    18.01.2005
    Адрес
    Ростов-на-Дону
    Сообщений
    577
    Благодарностей: 202
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

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

  4. #3
    Activist
    Регистрация
    17.01.2005
    Адрес
    Belarus, Minsk
    Сообщений
    402
    Благодарностей: 36
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Вот процедура. Вроде бы брал из какого-то журнала...
    Код:
    ;в 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
    ATW4GS / BIN2SNA / SquareMania <ТИ-3> / Ужасм+
    ATM-Turbo 512 v4.50, Commodore 64G + TAC-2, Retro-Bit Super Retro TRIO

  5. #4
    Activist Аватар для PheeL
    Регистрация
    19.01.2005
    Адрес
    Москва
    Сообщений
    329
    Благодарностей: 94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  6. #5

    По умолчанию

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

  7. #6

    По умолчанию

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

  8. #7
    Activist Аватар для PheeL
    Регистрация
    19.01.2005
    Адрес
    Москва
    Сообщений
    329
    Благодарностей: 94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от 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; 02.03.2005 в 21:34.

  9. #8
    Activist Аватар для fk0
    Регистрация
    18.02.2005
    Адрес
    St. Petersburg
    Сообщений
    415
    Благодарностей: 2
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

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

  10. #9
    Activist Аватар для fk0
    Регистрация
    18.02.2005
    Адрес
    St. Petersburg
    Сообщений
    415
    Благодарностей: 2
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от PheeL
    Именно первое.
    P.S. Да, я тут подумал и понял, что число итераций между X0 и X1 у меня непредсказуемо. Я могу в любое время считать значение Timer0, а он никак не синхронизирован с внутренним циклом программы и поэтому не могу четко выставить кол-во шагов вычислений. Может в начале их окажется больше чем к концу.
    U tebq имеет место быть классическая задача линейной интерполяции.
    http://algolist.manual.ru/maths/approx.php, и с построением прямой оно
    никак не связано.

  11. #10
    Activist Аватар для PheeL
    Регистрация
    19.01.2005
    Адрес
    Москва
    Сообщений
    329
    Благодарностей: 94
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от fk0
    U tebq имеет место быть классическая задача линейной интерполяции.
    http://algolist.manual.ru/maths/approx.php, и с построением прямой оно
    никак не связано.
    Да, скорее всего я ошибся в определении. Спасибо за ссылку!

Страница 1 из 2 12 ПоследняяПоследняя

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

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

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Tutorial по технике рисования на ZX
    от diver в разделе Графика
    Ответов: 114
    Последнее: 16.03.2015, 14:33
  2. Процедура опроса клавиатуры
    от Aprisobal в разделе Программирование
    Ответов: 8
    Последнее: 19.02.2005, 18:12

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •