Optymalizacja algorytmu Bresenhama w ATmega128 do płynnego narastania prądu

Mon Oct 08, 2012 11:43 pm   

Witam,

Używam mikrokontrolera ATmega128. W moim programie użytkownik ustawia
wartość prądu (liczba całkowita od 0 do 1000) oraz czas (od 1 do 40 sekund).
Prąd ma narosnąć od 0 do wartości ustawionej w ustawionym czasie. Funkcja
służąca do obliczania aktualnej wartości prądu podczas jego narastania jest
wywoływana z pewną częstotliwością (od 10 do 60Hz, zależnie od ustawienia w
parametrach programu). Zatem narastanie prądu odbywa się w liczbie kroków
wyrażonej wzorem: K = czas[s] * częstotliwość[Hz].
Żeby uniknąć obliczeń zmiennoprzecinkowych, zastosowałem algorytm Bresenhama
do kreślenia odcinków. Zapowiada się, że będzie to działać bardzo szybko,
gdy K >= wartość prądu.
Gdy K < wartość prądu, to algorytm Bresenhama normalnie kreśli odcinek w
pętli "idąc po zmiennej Y". Tymczasem ja działam w osi odciętych, czyli X (u
mnie jest to liczba kroków, w których prąd ma narosnąć). Bez większych
problemów przerobiłem ten algorytm tak, aby dla K < wartość prądu, "szedł on
po zmiennej X". Przy czym po tej przeróbce uzyskałem podpętlę (while), która
niekiedy będzie wykonywać się wiele razy (dla pojedynczego kroku w osi X),
co spowolni algorytm. Inną metodą, zamiast tej podpętli, byłoby zastosowanie
dzielenia, co też nie jest rozwiązaniem, gdyż dzielenie realizowane jest
przez kompilator także w pętli.
Poniżej przedstawiłem algorytm, który stosuję -- na razie to jest wersja
kreśląca grafikę (tak łatwiej mi obserwować działanie tego algorytmu), a nie
funkcja wywoływana z pewną częstotliwością i sterująca prądem.
Algorytm działa prawidłowo. Przy czym może działać niekiedy wolno (pętla
while może wykonywać się wiele razy) dla K < wartość prądu -- no i to jest
mój problem.
Mam pytanie do Was, jak przyspieszyć ten algorytm?
A jeśli się nie da, to byłbym wdzięczny za naprowadzenie na jakiś inny
sposób zaprogramowania opisanego problemu (narastania wartości w pewnej
liczbie kroków).

Ilustracja graficzna działania poniżej zaprezentowanego algorytmu:
http://imageshack.us/a/img341/925/74439722.png

K = czas * czestotliwosc;

if (K >= wartoscPradu) {
for (t = 0; t <= K; t++) {
drawPixel(px, py);
y += wartoscPradu + 1;
if (y >= K + 1)
y -= K + 1, py++;
px++;
}
} else {
for (t = 0; t <= K; t++) {
while (1) {
x += K + 1;
if (x >= wartoscPradu + 1) {
drawPixel(px, py);
x -= wartoscPradu + 1, px++;
py++;
break;
}
py++;
}
}
}


Pozdrawiam i z góry dziękuję za pomoc,
Robbo

Tue Oct 09, 2012 4:12 am   

cyt:

"Algorytm może działać zarówno na liczbach zmiennoprzecinkowych jak i całkowitych, ale ze względów wydajnościowych wykorzystuje się najczęściej realizacje całkowitoliczbowe. Zatem jeżeli początkowa wartość zmiennej decyzyjnej d lub jej przyrosty wychodzą nam ułamkowe, to mnożymy zarówno zmienną decyzyjną d jak i jej przyrosty tak by uzyskać liczby całkowite. Możemy tak zrobić gdyż do decyzji bierzemy pod uwagę jedynie znak zmiennej decyzyjnej d."

źródło: http://www.algorytm.org/podstawy-grafiki/algorytm-bresenhama.html

Tue Oct 09, 2012 7:29 am   

On 09.10.2012 01:43, Robbo wrote:

I(s)=I(S0)+(I(Se)-I(S0))*((s-S0)/(Se-S0))
I(s)=I(S0)+(I(Se)-I(S0))/(Se-S0) * (s-S0)
gdzie s - czas, S0 - czas początkowy, Se - czas końcowy

Przekształcasz to sobie na:
I(t)=I(T0)+t*dI
I(t)=I(t-1)+dI

Raz wyliczasz iloraz różnicowy dI, potem masz w każdym cyklu jedno
dodawanie i jeden shift.


--
Pozdrawiam
Michoo

Tue Oct 09, 2012 8:06 am   

Użytkownik "Robbo" <niemam@gmail.com> napisał w wiadomości
news:5073652e$0$26682$65785112@news.neostrada.pl...


Może w przypadku KI, a potem
pętla już jak dla przypadku K>I, tylko py++ zastąpić py+=n.
"Schodki" wyjdą większe niż z twojej części else, ale jeśli dzielenie przed
pętlą nie byłoby problemem to może być n=2,3,4,5,.... i wtedy to chyba już
wyjdzie prawie to samo.
P.G.