Bresenham-Algorithmus mit Zeit als x-Achse

[Alexander Willer (Gast)]

Hallo zusammen,

für einen RGB-Controller möchte ich eine Funktion schreiben, welche es 
ermöglicht die LEDs vom aktuellen Wert yAlt (uint16_t, 0 - 1023) zu 
einem anderen, beliebigen Wert yNeu im gleichen Bereich zu faden.

Dies soll in einem bestimmten Zeitraum passieren.

Damit das Fading unabhängig von der Hauptschleife funktioniert, habe ich 
einen Timer so eingestellt, dass eine ISR alle 1 ms aufgerufen wird.

Im nächsten Schritt habe ich versucht, die C-Implementierung des 
Bresenham-Algorithmus so umzubauen, dass die Funktion der Schleife von 
der ISR übernommen wird.

Die x-Achse ist dabei die Zeit, bzw. die Zahl der ISR-Aufrufe.

Dabei ist allerdings ein Problem aufgetaucht, aufgrund der Vertauschung 
von x- und y-Achse bei Steigungen größer 1 ist nicht gewährleistet, dass 
jeder ISR-Aufruf die y-Achse um 1 inkrementiert (mehrere "Pixel"/y-Werte 
auf einem x-Wert), so dass die Zeit nicht eingehalten wird.

Im Anhang ist der bisherige Stand zu finden (Zu Testzwecken erstmal in 
C#, so kann ich es auf dem Rechner testen + plotten).
Habt Ihr eine Idee, wie ich einen Wert yAlt zu yNeu in einer 
festgelegten Schrittzahl inkrementieren/dekrementieren kann?

Viele Grüße,
Alex

[Karl H. (kbuchegg)]

Zu viel Aufwand.
Nimm einfach ein paar Bits mehr und implementiere dir eine 
Festkommaarithmetik.

   Neuer_Wert = Alter_Wert + Inkrement

Den Aufsummierfehler vermeidest du, indem du bei der letzten Summierung 
den Zielwert setzt.
Solange man keine Vergleichsmöglichkeiten hat (wie zb bei einer Linie am 
Schirm, wo man immer auch das Pixel 'davor' sieht), merkt kein Mensch 
wenn sich dein Farbwert mal um einen klitzekleinen Sprung zuviel ändert.

[Alexander W. (alexander_w)]

Ich hab gerade noch einmal gezielt gesucht und noch das hier gefunden:

Beitrag "Lineare Pulsweitenänderung PWM von a nach b in vorgegebener Zeit (wie?)"

Im Prinzip das gleiche Problem, aber auch ohne konkretere Lösung.

Mit der Geradengleichung möchte ich nur ungerne arbeiten, da bei den 
angestrebten Auflösungen die Werte recht groß werden und die Berechnung 
halbwegs zeitkritisch ist.

Der Bresenham-Algorithmus müsste ja auch nur für den ersten Quadranten 
implementiert werden, ich denke, dass man dieses Beispiel dafür 
verwenden kann:

http://de.wikipedia.org/wiki/Bresenham-Algorithmus#C-Implementierung

Lediglich die Umschaltung für den Fall, dass dy > dx ist, bereitet bei 
der Verwendung Probleme.

[Karl H. (kbuchegg)]

Alexander W. schrieb:

> Mit der Geradengleichung möchte ich nur ungerne arbeiten, da bei den
> angestrebten Auflösungen die Werte recht groß werden und die Berechnung
> halbwegs zeitkritisch ist.

Jetzt hast du mich neugierig gemacht.
Was bitte ist an einem LED Fading zeitkritisch?

[Falk B. (falk)]

@  Alexander Willer (Gast)

>ermöglicht die LEDs vom aktuellen Wert yAlt (uint16_t, 0 - 1023) zu
>einem anderen, beliebigen Wert yNeu im gleichen Bereich zu faden.

Das sollte eher einfach sein.

du willst N PWM-Schritte in M 1ms Takten machen. Mr Bresenham machte das 
so.

N = pwm_max-pmw_min;
M = 100;

void(1mstimer) {
  static fehler=0;

  fehler += N;
  if (fehler >=M) {
    fehler -= M; 
    pwm++;
  }
}

Ähhh vola, oder so ähnlich.

MFG
Falk

http://de.wikipedia.org/wiki/Bresenham-Algorithmus

[Falk B. (falk)]

Hmm, stimmt nicht ganz, ist nur ein Fragment aus dem Hippothalamus.

[Falk B. (falk)]

Eher so, dann passen auch steile Rampen mit N>M und beide Richtungen.

  M = 100;   // Zeitschritte für Übergang
  if (pwm_max>=pwm_min) {
    dir = 1;
    N = pwm_max-pmw_min;
  } else {
    dir = -1;
    N = pwm_min-pmw_max;
  }

void(1mstimer) {
  static fehler=0;

  fehler += N;
  while (fehler >=M) {
    fehler -= M; 
    pwm += dir;
  }
}

[Alexander W. (alexander_w)]

Zeitkritisch ist das ganze, weil ich auch bei niedrigen Helligkeiten 
einen stufenlosen Farbwechsel und gleichzeitige Bedienung von diversen 
anderen Funktionen sicherstellen möchte. Da ich nicht einschätzen kann, 
was 32-Bit-Divisionen und Multiplikationen für RGB+W an Zeit benötigen, 
verzichte ich lieber drauf.

@Falk: Danke, das werde ich gleich mal ausprobieren, ich müsste bitte 
noch wissen, was ich mit pwm/pmw_min/max machen soll? Zwei der Werte 
sind vermutlich Start und Ziel des Fadings, aber so ganz klar ist mir 
das noch nicht.

[Simon K. (simon)]

Also wenns um Programmkonzepte geht: Ich würde einfach eine Istwert- und 
Zielwert-Variable für jede LED einbauen.

Dann zyklisch aufrufen:

if (Zielwert > Istwert) {
    Istwert++;
    /* Ausgabe von Istwert */
} else if (Zielwert < Istwert) {
    Istwert--;
    /* Ausgabe von Istwert */
}

Das als Basic. Um das ganze Zeitvariabel zu machen würde ich einfach 
etwas DDS-ähnliches benutzen:

if (Zielwert > Istwert) {
    Istwert += Inkrement;
    /* Ausgabe von Istwert */
} else if (Zielwert < Istwert) {
    Istwert -= Inkrement;
    /* Ausgabe von Istwert */
}

Um dabei hohe Zeitauflösungen zu garantieren, verweise ich auf Karl 
Heinz Post: Festkommaarithmetik.
Verwendet man bspw. eine PWM mit 16 Bit, so legt man für Istwert und 
Zielwert einfach 32 Bit Werte an. Die PWM wird dann aus den oberen 16 
Bit davon gebildet.
Völlig analog zum DDS Prinzip.

EDIT: Das ganze ist jetzt übrigens eine I-Strecke. Also es wird linear 
angefahren, und der Zielwert erreicht.
Man könnte auch andere Strecken implementieren.

[Falk B. (falk)]

@  Alexander W. (alexander_w)

>Zeitkritisch ist das ganze, weil ich auch bei niedrigen Helligkeiten
>einen stufenlosen Farbwechsel und gleichzeitige Bedienung von diversen
>anderen Funktionen sicherstellen möchte.

Bei 1ms Zeitauflösung langeweilt sich der AVR.

> Da ich nicht einschätzen kann,
>was 32-Bit-Divisionen und Multiplikationen für RGB+W an Zeit benötigen,
>verzichte ich lieber drauf.

Bresenham braucht sowas nicht, nur Addition und Substraktion, der 
Vergleich ist effektiv eine Subtraktion.

>noch wissen, was ich mit pwm/pmw_min/max machen soll? Zwei der Werte
>sind vermutlich Start und Ziel des Fadings,

sicher.

> aber so ganz klar ist mir das noch nicht.

Hmmmm . . .

[Simon K. (simon)]

Einfach mal ein wenig drüber nachdenken. Mach den Monitor aus, nimm dir 
ein Blatt Papier und überlege wie du nur mit einem konstanten Takt das 
von dir gewünschte Verhalten hinkriegst. Anregungen sind hier ja genug.

Das Problem ist fast zu trivial, als dass man da irgendwo eine fertige 
Lösung für findet.