Просмотр полной версии : Линейная интерполяция или процедура рисования линни
Пишу тут дипломчик (софт для кардиостимулятора) и возникла проблема написания процедуры линии для соединения двух точек табличного графика. Немного оффтопично, но внутри микроконтроллера стоит ядро 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) //выводим текущую точку
}
Вот и весь алгоритм, очень быстрый
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
Всем ответившим - большое спасибо!
Попробую разобраться и применить. Программист из меня слабенький, а дипломы по рисункам в институте не принимают :)
Вот процедура. Вроде бы брал из какого-то журнала...
[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 ....
Пишу тут дипломчик (софт для кардиостимулятора) и возникла проблема написания процедуры линии для соединения двух точек табличного графика. Немного оффтопично, но внутри микроконтроллера стоит ядро 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.
Вопрос - тебе именно линию надо, т.е. например надо рассчитать 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, а он никак не синхронизирован с внутренним циклом программы и поэтому не могу четко выставить кол-во шагов вычислений. Может в начале их окажется больше чем к концу.
Пишу тут дипломчик (софт для кардиостимулятора) и возникла проблема написания процедуры линии для соединения двух точек табличного графика. Немного оффтопично, но внутри микроконтроллера стоит ядро 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
Именно первое.
P.S. Да, я тут подумал и понял, что число итераций между X0 и X1 у меня непредсказуемо. Я могу в любое время считать значение Timer0, а он никак не синхронизирован с внутренним циклом программы и поэтому не могу четко выставить кол-во шагов вычислений. Может в начале их окажется больше чем к концу.
U tebq имеет место быть классическая задача линейной интерполяции.
http://algolist.manual.ru/maths/approx.php, и с построением прямой оно
никак не связано.
U tebq имеет место быть классическая задача линейной интерполяции.
http://algolist.manual.ru/maths/approx.php, и с построением прямой оно
никак не связано.
Да, скорее всего я ошибся в определении. Спасибо за ссылку!
x51 имеет аппаратный умножитель! Какие, нафиг, таблицы?
В даташит глянь!
Один хрен возня будет, когда 16x16 при помощи A и B будет компайлер считать.
Да и с делением засада.
Один хрен возня будет, когда 16x16 при помощи A и B будет компайлер считать.
Да и с делением засада.
Совершенно верно. Абсолютно бесполезные команды для решения моей задачи (в процедуре деления команда div вообще не используется ни разу). Этот момент я хорошо понял когда посмотрел на сайте www.8052.com набор арифметических процедур для контроллера. Данные команды подходят только для 8-ми битных операций. Даташитсы я ессно от начала и до конца изучил.
Да, и ещё - я все-таки не понял, подходит ли метод Брезенхема для решения моей задачи или он работает только для заранее известного кол-ва вычислений? Или я останавливаюсь на своей реализации классической формулы для такого типа задачи (благо она уже работает)?
Совершенно верно. Абсолютно бесполезные команды для решения моей задачи (в процедуре деления команда div вообще не используется ни разу). Этот момент я хорошо понял когда посмотрел на сайте www.8052.com набор арифметических процедур для контроллера. Данные команды подходят только для 8-ми битных операций. Даташитсы я ессно от начала и до конца изучил.
Ну да - деление в топку, но вот таки умножение полезно. 16x16->32 можно делать столбиком из четырёх 8x8->16 и большой возни =)
Да, и ещё - я все-таки не понял, подходит ли метод Брезенхема для решения моей задачи или он работает только для заранее известного кол-ва вычислений? Или я останавливаюсь на своей реализации классической формулы для такого типа задачи (благо она уже работает)?
Брезенхем применим, когда у тебя шаг по одной координате всегда 1, и надо посчитать вторую. У тебя видимо это не так, так что брезенхем не подойдёт.
Кстати, ты на сях пишешь? Работать и успешно выполнять свою задачу код успевает? Ну так и забей =) Лучше на forever 1к-интру накодь =)
Брезенхем применим, когда у тебя шаг по одной координате всегда 1, и надо посчитать вторую. У тебя видимо это не так, так что брезенхем не подойдёт.
Кстати, ты на сях пишешь? Работать и успешно выполнять свою задачу код успевает? Ну так и забей =)
Да, значит все-таки Брезенхем не подойдет. А жаль, он бы здорово убыстрил вычисления.
Сам импульсный табличный генератор я пишу на голом асме. Процедура небольшая да и низкоуровневое программирование мне ближе. Также будет написана "связка" в виде редактора табличек с последующим заливанием их в память контроллера. Эту часть я реализую на Delphi, так как мне нужна лёгкость и гибкость в программировании именно интерфейсной части.
Там вся байда по скорости в том, что моя процедура будет входить в состав многозадачного ядра (мой препод по диплому мощный персонаж - переделал ядро QNX под I8052) и будет высокий приоритет по исполнению, но отнюдь не наивысший. Поэтому кол-во итераций будет прямо пропорционально кол-ву вызовов моей процедуры этим ядром. В этом моменте и отпадает метод Брезенхема. Но поскольку контроллер работает на частоте ~20 МГц (на самом деле используется ADuC842, поэтому и такие частоты ядра), и команды исполняются за 1 такт, то вроде бы скорости хватает. Реальной железки у меня нет, но на эмуляторе по выходным значениям напряжения от времени с DAC вроде бы все в порядке (я даже граф. анализатор на Дельфях для этого накатал :) ).
ну как успехи, давно не слышно :)
или уже полностью ld de,Кипр? ;)
Да какой тут Кипр... На кафедре разборки между преподами и я как раз нечаянно меж двух огней попадаю.
Насчет процедуры. Твой метод верный и он будет работать. Но! При больших задержках между вызовами процедуры интерполяции, соответственно возрастает и кол-во вызовов процедуры рисующей отрезок по методу Брезенхема. Ну понятно, да? Чтобы высчитать следующую точку ему надо построить отрезок до неё и если расстояние между точками в следствие задержки возрастает, то пропорционально возрастает и кол-во вызовов процедуры и также пропорционально снижается скорость. И может наступить такой момент, что из-за возросшего числа вызовов вся прелесть метода по части отсутствия умножения и деления уйдет в нуль, а то и в минус. Моя же реализация классической формулы будет тормозить всегда одинаково в любой вычисляемой точке :)
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot