Wasserwelle durch Kreis mit Bresenham animieren

[Basti (Gast)]

Hallo Forum,

wie im Betreff schon erwähnt möchte ich zur Animation auf meinem 
Farbdisplay eine Welle "lostreten". Das ist mir auch schon gelungen, 
indem ich Kreise mit aufeinanderfolgenden Radien zeichne. Diese bekommen 
durch eine Sinus LUT die Farbe zwischen dunkel und blau zugewiesen.

Das Problem: Der Bresenham Algo hat anscheinend den Nachteil das Pixel 
ausgelassen werden und damit immer dunkel bleiben. Also z.B. zwischen 
Radius 3 und 4 gibt es Pixellücken...

Was ich nun Suche ist ein neuer Ansatz. Das ganze sollte aber mit 25 FPS 
auf einem 8 Bit µC mit 24 MHz laufen... :-/
Hat jemand eine Idee? Tante google landet meist bei Direkt X oder OpenGL 
Spieleprogrammierung. Das ist eindeutig zu heavy...

Danke

Basti

[Falk B. (falk)]

@  Basti (Gast)

>ausgelassen werden und damit immer dunkel bleiben. Also z.B. zwischen
>Radius 3 und 4 gibt es Pixellücken...

Logisch, da ist die Auflösung einfach sehr gering.

>Was ich nun Suche ist ein neuer Ansatz. Das ganze sollte aber mit 25 FPS
>auf einem 8 Bit µC mit 24 MHz laufen... :-/

Eine Mölichkeit ist, derartig kleine Grafiken schlicht als fertige 
Bitmap reinzukopieren. Damit kann man sie vorher optimal mit einem 
Grafikprogramm zeichnen.

[Basti (Gast)]

Hm, war auch schon meine Idee, aber ist halt nicht so schick wie ichs 
erwartet habe.

Möglich wäre vielleicht noch sich die toten pixel zu merken (bzw die 
beschriebenen abzuhaken) und diesen Pixeln später eine Mittelwert aus 
den Nachbarpixeln zu berechnen...

Na vielleicht kommt ja noch ne bessere Lösung...

Grüße

Basti

[Oliver (Gast)]

Eventuell würde hier der "Wu circle draw algorithmus" weiterhelfen:

http://landkey.net/d/L/J/RF/WUCircle/Intro.txt.legacy.htm

Grüße,
Oliver

[Florian T. (florian_t)]

kann die Zeichenfunktion für den Kreis auch eine Liniendicke?
Wenn ja, probier doch mal die banalen Dinge zuerst: Liniendicke 
variieren.
Bsp. könntest Du bei Kreis 3/4 einem der beiden eine dickere linie 
verpassen. Dadurch müssten auch die Pixellücken verschwinden.

[Johann L. (gjlayde)]

Mach doch einfach fette Pixel, d.h. anstatt 1x1 Pixel zeichne sowas:

## 
##

oder so:

 # 
###
 #

oder so:

 ## 
####
####
 ##

Dadurch werden zwar Grafik-Pixel mehrfach überpinselt, aber stört das 
denn?

[Heinz (Gast)]

Beim Bresenham sollten eigentlich keine Lücken entstehen - zeig mal 
deinen Quellcode

Ich vermute mal - Du zeichnest den Q1 und spiegelst dann?

[Basti (Gast)]

@Oliver da ist floating point und sqrt gefragt... nich so schön... :-/

@Florian ne das geht net

@Johann, ja das ja wie das Prinzip mit dem fertigem Bild...

Also ich hab mir jetzt selbst was überlegt und will euch das mal nicht 
vorenthalten... sieht eigentlich ziemlich schick aus...
Ich brauch nur noch ein Effekt das die Welle ausklingt...
Ich glaub ich muss mir nochmal ne Welle anschauen... gerade keine Idee 
:D

void start_wave(uint8_t _x,uint8_t _y,uint8_t sx,uint8_t sy,type_rgb *buffer)
{
  
  static uint8_t counter = 0;
      
  
  //set all pixel to 1... find later the death pixel
  
  for (uint8_t x = 0; x < _x; x++)
  {
    for (uint8_t y = 0; y < _y; y++)
    {
      buffer[mapper(x,y)].b = 1;
    }
  }
  
  counter-=10;

  
  for(uint8_t i = 0;i<15;i++) {
    
    uint16_t temp = (sin_lut((uint8_t)(counter + FACTOR*(i+1)))>>2) //load sinus from lut
    *(256-i*16); //waves get darker with higher r
    temp>>=8;
    if(temp==1) temp=2;  //same color because of gamme table
    gfx_generic_draw_circle(sx,sy, i,0,0,(uint8_t)temp); //draw wave with radius i and color temp (blue)
  }    
  
  //look for death pixels and there neighbor, approx. the color
  for (uint8_t x = 0; x < _x; x++)
  {
    for (uint8_t y = 0; y < _y; y++)
    {
      if(buffer[mapper(x,y)].b == 1) {
        uint16_t temp_pixel=0;
        uint8_t div=0;
        if(x>0) {
          temp_pixel += buffer[mapper(x-1,y)].b;
          div++;
        }
        if(x<(_x-1)) {
          temp_pixel += buffer[mapper(x+1,y)].b;
          div++;
        }
        if(y>0) {
          temp_pixel += buffer[mapper(x,y-1)].b;
          div++;
        }
        if(y<(_y-1)) {
          temp_pixel += buffer[mapper(x,y+1)].b;
          div++;
        }
        
        buffer[mapper(x,y)].b = temp_pixel/div;
      }
    }
  }
}

[Adib (Gast)]

du kannst ein fertiges bitmap nehmen und die Farbwerte als index in eine 
farbtabelle nehmen. Den Index rotierst du dann und so ändern sich di 
Farben.

So wurde die Startbildschirm Animation bei win95 gemacht.

Adib.

[Basti (Gast)]

Hier die Kreisfunktion aus der ASF lib von Atmel... ich hab die etwas 
modifiziert... wozu die Bitmaske da ist, hat sich mir noch nicht 
erschlossen...

void gfx_generic_draw_circle(uint8_t x, uint8_t y,uint8_t radius, uint8_t red,uint8_t green,uint8_t blue)
{
  uint8_t offset_x;
  uint8_t offset_y;
  int16_t error;
  uint8_t octant_mask = 0xFF;

  /* Draw only a pixel if radius is zero. */
  if (radius == 0) {
    Set_Pixel(x, y,red,green,blue);
    return;
  }

  /* Set up start iterators. */
  offset_x = 0;
  offset_y = radius;
  error = 3 - 2 * radius;

  /* Iterate offsetX from 0 to radius. */
  while (offset_x <= offset_y) {
    /* Draw one pixel for each octant enabled in octant_mask. */
    if (octant_mask & (1 << 0)) {
      Set_Pixel(x + offset_y, y - offset_x,red,green,blue);
    }

    if (octant_mask & (1 << 1)) {
      Set_Pixel(x + offset_x, y - offset_y,red,green,blue);
    }

    if (octant_mask & (1 << 2)) {
      Set_Pixel(x - offset_x, y - offset_y,red,green,blue);
    }

    if (octant_mask & (1 << 3)) {
      Set_Pixel(x - offset_y, y - offset_x,red,green,blue);
    }

    if (octant_mask & (1 << 4)) {
      Set_Pixel(x - offset_y, y + offset_x,red,green,blue);
    }

    if (octant_mask & (1 << 5)) {
      Set_Pixel(x - offset_x, y + offset_y,red,green,blue);
    }

    if (octant_mask & (1 << 6)) {
      Set_Pixel(x + offset_x, y + offset_y,red,green,blue);
    }

    if (octant_mask & (1 << 7)) {
      Set_Pixel(x + offset_y, y + offset_x,red,green,blue);
    }

    /* Update error value and step offset_y when required. */
    if (error < 0) {
      error += ((offset_x << 2) + 6);
    } else {
      error += (((offset_x - offset_y) << 2) + 10);
      --offset_y;
    }

    /* Next X. */
    ++offset_x;
  }
}

[Heinz (Gast)]

Ich kann Dir einen in X86 zeigen ?
wie funktioniert das hier mit Codetags?

[Johann L. (gjlayde)]

Basti schrieb:

> buffer[mapper(x,y)].b = temp_pixel/div;

Aha.  Du machst dir Sorgen um die Performance und baust daher Divisionen 
ein :o)

Basti schrieb:

> Was ich nun Suche ist ein neuer Ansatz. Das ganze sollte aber mit 25 FPS
> auf einem 8 Bit µC mit 24 MHz laufen... :-/

Das ganze ist Kaffesatz-Lesen solinge der µC oder zumindest die Familie 
nicht bekannt ist; vermutlich ein AVR.

Bei der Randdaten bleiben 960000 Ticks / Frame, bei 50 Ticks pro Pixel 
reicht das für ein 160 x 120 Display.

[Heinz (Gast)]

Hier mal in x86 assembler intel syntax


CIRCLE  PROC  NEAR
;
;          RA% = AX
;          XM% = BX
;          YM% = CX
;

  MOV  Y1,CX
  MOV  Y2,CX

  MOV  DX,CX
  ADD  DX,AX
  MOV  Y3,DX

  MOV  DX,CX
  SUB  DX,AX
  MOV  Y4,DX

  MOV  X1,BX
  MOV  X2,BX

  MOV  DX,BX
  ADD  DX,AX
  MOV  X3,DX

  MOV  DX,BX
  SUB  DX,AX
  MOV  X4,DX
;
;       AX = DA   BX = X   CX = Y
;
  MOV  CX,AX
  DEC  AX
  XOR  BX,BX

  PUSHA
  SETPOINT X1,Y3
  SETPOINT X2,Y4
  SETPOINT X3,Y1
  SETPOINT X4,Y2
  POPA
  JMP  CIRCLE_1

CIRCLE_LOOP:
  PUSHA
  SETPOINT X3,Y1
  SETPOINT X3,Y2
  SETPOINT X4,Y2
  SETPOINT X4,Y1
  POPA
  INC  Y1
  DEC  Y2
  INC  X1
  DEC  X2

  CMP  AX,0
  JGE  NO_Y_STEP

  ADD  AX,CX
  ADD  AX,CX
  DEC  CX

  DEC  Y3
  INC  Y4
  DEC  X3
  INC  X4
NO_Y_STEP:
  PUSHA
  SETPOINT X1,Y3
  SETPOINT X1,Y4
  SETPOINT X2,Y4
  SETPOINT X2,Y3
  POPA

CIRCLE_1:
  SUB  AX,BX
  SUB  AX,BX
  DEC  AX
  INC  BX
  CMP  BX,CX
  JGE  CIRCLE_EXIT

  JMP  CIRCLE_LOOP
CIRCLE_EXIT:
  RET
CIRCLE  ENDP

SETPOINT ist ein Macro

der code ist von 1986 und lief mit Sicherheit

[Johann L. (gjlayde)]

Heinz schrieb:
> der code ist von 1986 und lief mit Sicherheit

Löst das Problem der Pixel-Lücken aber auch nicht...  Es sei denn, ein 
Pixel ist wie bereits besprochen fett genug.

[Heinz (Gast)]

Und hier mal auf die schnelle in C übersetzt - keine Garantie dass das 
fehlerfrei ist

XM Kreismittelpunkt X Coo
YM Kreismittelpunkt Y Coo
RA Kreisradius


y1=XM;
y2=YM;
y3=YM+RA;
y4=YM-RA;
x1=XM;
x2=XM;
x3=XM+RA;
x4=XM-RA;

d = RA;
y=RA;
x=0;
d--;

punkt x3,y1
punkt x3,y2
punkt x4,y2
punkt x4,y1
goto c1;

cl:
  y1++;
  y2--;
  x1++;
  x2--;

  if (d<0){
    d+=y;
    d+=y;
    y--;
    y3--;
    y4++;
    x3--;
    x4++;
  }
  punkt x1,y3
  punkt x1,y4
  punkt x2,y3
  punkt x2,y4

c1:
  d-=x;
  d-=x;
  d--;
  x++;
  if (x<y) goto cl;

[Heinz (Gast)]

@Johann
Wieso sollte der Lücken haben?

[Markus M. (adrock)]

Hmmm... glaube auf dem C64 damals gab es auch so interessante Muster 
wenn man (mit Simons Basic oder was auch immer) Kreise in 1er Schritten 
gezeichnet hat ;-)

Wie wäre es, wenn Du die den Radius nicht in 1er Schritten, sondern in 
0.5er Schritten erhöhst?

Anstatt (mal in pseudo-code):

Für r=1..10
   zeichne_kreis(x,y,r)
done

Machst Du ein

Für r=1..20
   zeichne_kreis(x*2, y*2, r)
done

In der eigentlichen Routine die die Pixel setzt, musst Du natürlich 
alles wieder zurückskalieren (also /2, lsr).

Grüße
Markus

[Heinz (Gast)]

@Markus
Damit hast Du aber auch die doppelte Laufzeit (bei 0.5 schritten)

Du kannst beim Bresenham keine Pixel verlieren ausser Du brichst zu früh 
ab - dann hast Du 4 Lücken bei etwa 2:30 und die gespiegelten

[Markus M. (adrock)]

...es gehen ja auch keine Pixel innerhalb eines Kreises verloren, 
sondern zwischen Kreisen bei einer Radiusänderung von 1 (so habe ich 
zumindest den TE verstanden) bleiben Pixel übrig, die nicht angesprochen 
werden.

Ich gehe mal davon aus, dass eben durch Ungenauigkeiten diese Pixel 
nicht angesprochen werden. Deshalb meine Idee mit dem 0.5 Radiusschritt.

Klar ist es die doppelte Laufzeit, aber alle anderen Ansätze mit 
Zwischenpixel berechnen etc. halte ich für aufwändiger.

Grüße
Markus

[Basti (Gast)]

Hallo Markus,

du hast das schon richtig verstanden...

Wenn ich das so skaliere wie du vorschlägst, verliere ich aber mit 
Sicherheit die "rundlichkeit" des Kreises.

Das "Display/LED Matrix" hat nur 288 Pixel, höchstwahrscheinlich läuft 
sogar der Ansatz mit der Wurzel pro Pixel noch mit 25 FPS, aber dann 
habe ich auch bloß das Problem das die Aliesingpixel mir den Kreis von 
davor überschreiben.

Also eigentlich habe ich meine Lösung gefunden mit dem Pixelsuchen und 
mitteln, es sieht ziemlich gut aus. Kann euch ja morgen mal zwei 
Vergleichsbilder schießen und mal die Laufzeit der Funktion messe, wenn 
Interesse besteht.

Natürlich bin ich weiterhin offen für Kreisalgo's die "geschlossen 
auftreten"

@Heinz, so richtig werde ich aus deinem "C" Code nicht schlau, aber ich 
werde mir das morgen ausgeschlafen nochmal anschauen.

>Das ganze ist Kaffesatz-Lesen solinge der µC oder zumindest die Familie
nicht bekannt ist; vermutlich ein AVR.

Ja ein ein XMega um genau zu sein. Ich nehme an jetzt gehst du zum 
Schreibtisch greifst in das Fach AVR unter K wie Kreisalgorithmus und 
wirst mir dank der neuen Informationen eine Maßgeschneiderte Lösung 
präsentieren können =) ;)

Grüße

Basti

[MichaelH (Gast)]

Das Problem hatte ich auch mal, als ich auf einem LCD gefüllte Kreise 
darstellen wollte.

Sieht beim Bresenham (Wie hier implementiert: 
http://de.wikipedia.org/wiki/Bresenham-Algorithmus#Kreisvariante_des_Algorithmus 
) halt beim Rastern mit

            for (int i = 0; i < 100; i++) {
                rasterCircle(100, 100, i);
            }

wie das Bild im Anhang aus.

Ne Lösung hab ich aber auch nicht gefunden...

[Heinz (Gast)]

Guten Morgen

hab da oben Mist geschrieben 2:30 sollte 1:30 bzw. 45 Grad heisen

Sorry ich hatte das nicht wie MichaelH verstanden sondern so dass bei 
EINEM Kreis die entsprechenden 4 Punkte fehlen

Wenn ausgefüllter Kreis würde ich eher den Bresenham modifizieren

x1/y1 x2/y2 ....
berechnest Du sowie. Dann noch
for (x1; x1<x2 ;x1++)
  punkt x1,y1
  punkt x1,y3

[Basti (Gast)]

Hallo MichaelH,

die Lösung habe ich ja oben schon gepostet.
Man merkt sich die Pos der Toten Pixel und mittelt den Farbwert des 
Pixels aus dem rechten, linken, oben und unterem Pixel. Deine Grafik 
beweißt ganz gut, dass das super funktioniert! Kein totes Pixel hat bei 
den erwähnten Nachbarpixeln wieder ein Totes Pixel...

Also ich bin sehr zufrieden mit der Funktion, aber gegen ne andere Idee 
habe ich nix einzuwenden. :)

@Heinz auch kein ausgefüllter Kreis, das ist wieder ein anderes Thema...

Man könnte aber schon von außen nach innen ausgefüllte Kreise zeichnen.
Wäre eine Möglichkeit 2. Stell ich mir aber deutlich langsamer vor. Da 
die Grafikfläche sehr oft übermalt wird.

Grüße

Basti

[Basti (Gast)]

Achso, das meint Heinz....

@ MichaelH für gefüllte Kreise gibts auch schon gute Funktionen, die 
muss man nicht aus vielen Kreisen mit unterschiedlichen Radien zeichnen!

Mir gehts um einen Welleneffekt. Dazu brauch ich Kreise mit 
unterschiedlichen Helligkeitswerten...

[Heinz (Gast)]

Ja - das mit dem gefüllten Kreis ist bei Dir schwierig da nicht 
einfarbig, das war auch auf Michael bezogen

Basti - wenn das obige dein Source ist kannst Du dir das ganze 
octant_mask sparen - braucht nur Rechenzeit.

Ich hab anstelle 1 xy koordinate eben 4 - damit sparst Du dir das 
gerechne mit dem Offset in der Schleife. Das wird zu inc und dec. Auf 
einem 8088 war dec:add mal 1:4

[Adib (Gast)]

Basti warum willst du die Kreise nicht schon verher berechnen?

Wenn du in einem Bitmap für jedes Pixel den Radiuswert speicherst, dann 
kannst du für alle Pixel mit dem gleichen Radius durch eine Farbe aus 
deiner Farbtbelle ersetzen.

Wo ist das Problem?

adib.
--

[Basti (Gast)]

>Wo ist das Problem?

Naja, bei mir ist hier der Weg das Ziel ;)
Im Paint vormalen und nur die Farbpalette durchschieben find ich etwas 
langweilig :)

Bin jetzt nochmal nen ganzes Stück voran gekommen... jetzt sieht es so 
aus:

http://www.youtube.com/watch?v=ktB-R8ErZEg

Bin eigentlich schon ganz zufrieden. Ich werd jetzt nur noch nen 
bisschen mit den Parametern spielen, damit das perfekter wirkt....

Danke trotzdem für die Hilfe,

Grüße

Basti

[Markus M. (adrock)]

Basti: Das sieht sehr gut aus! Vielleicht ein bisschen langsamer laufen 
lassen...

Und es schreit geradezu danach, über ein Mikro und FFT passend zur Musik 
Effekte zu machen :-)

Man kann garnicht erkennen, das es einzelne LEDs sind. Was hast Du denn 
noch alles darüber gepackt, um ein schönes "Finish" zu erzielen?

Grüße
Markus

[Basti (Gast)]

Hallo Markus,

es ist ein Multi-Touchscreen geplant... also die Wasserwellen bekommen 
noch ihre Bedeutung ;)

Aber ich möchte da noch nicht so viel verraten...

Das Plexiglas ist echt scharf ne? War selbst überrascht =) Gibts im 
offiziellen Plexiglasshop und nennt sich TrueColor oder so und dann das 
schwarze wählen.

Multitouch wären mehrere Wellen von Vorteil: :)

http://www.youtube.com/watch?v=dkI_uyFWxXo

Achso... zwei Wellen brauchen ca. 9 ms mit allem drum und dran... Da 
kommt man schon noch auf gute Frameraten!

Grüße

Basti

[Markus M. (adrock)]

...und wie machst Du die Touch-Erkennung? DAS würde mich jetzt noch 
interessieren...

Viele Grüße
Markus (der jetzt gleich mal mit dem ATXmega experimentiert, weil die 
ATMegas haben einfach zu wenig SRAM :-)

[Rolf Magnus (Gast)]

Heinz schrieb:
> wie funktioniert das hier mit Codetags?

Man liest einfach, was direkt über dem Eingabefeld für deinen Text unter 
Wichtige Regeln - erst lesen, dann posten! steht, speziell unter 
dem Punkt Formatierung.