mikrocontroller.net

Forum: Compiler & IDEs Verzichten auf Float, aber wie?


Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Huhu,

Ich hab mir aufm Computer ne Funktion geschrieben, wo ich aus einem 
2dimensionalen Array eine Grafik auslesen kann, sie "virtuell" in einem 
bestimmten Displayspeicher platzieren kann, sie anschließend noch drehen 
und dann richtig anzeigen lassen kann.
Das ganze hab ich dann mit der sin und cos Funktion aus der math lib 
(header math.h) realisiert.
Blöderweise ist zur Zeit aber noch alles in Float realisiert. Wenn ich 
sowas jetzt auf den Mikrocontroller portieren will, wollte ich 
eigentlich darum herum kommen.
Also dachte ich an eine Sinus/Cosinus Tabelle mit einer Auflösung von 
8Bit.
Allerdings bekomme ich dermaßige Ungenauigkeiten darein, dass die 
gedrehten (und seien die Bilder nur um 90, 180 oder 270° gedreht) ne 
verdammt miese Qualität bekommen. (Unter anderem durch den 
Rundungsfehler bei xnew und ynew)

Achja, jedes Pixel stellt ein Byte im Grafikspeicher dar.

Hier mal die Float-variante
void CDisplay::CopyRotated(unsigned char** pBuf,int Left, int Top, int Width, int Height, int XOrigin, int YOrigin, int Angle)
{
  int x = Left - XOrigin;
  int y = Top - YOrigin;
  float cosine = cos(Angle*3.14F/180); 
  float sine = sin(Angle*3.14F/180);
  int i, j;
  int xnew, ynew;

  for (i=0; i<Width; i++)
  {
    for (j=0; j<Height; j++)
    {
      xnew = (((x+i) * cosine) - ((y+j) * sine)) + XOrigin + .5;
      ynew = (((x+i) * sine) + ((y+j) * cosine)) + YOrigin + .5;
      m_DisplayBuffer[xnew][ynew] = pBuf[i][j];
    }
  }
}

Und hier die int-Variante
void CDisplay::CopyRotated(unsigned char** pBuf,int Left, int Top, int Width, int Height, int XOrigin, int YOrigin, int Angle)
{
  int x = Left - XOrigin;
  int y = Top - YOrigin;
  int cosine = COS(Angle); 
  int sine = SIN(Angle);
  int i, j;
  int xnew, ynew;

  for (i=0; i<Width; i++)
  {
    for (j=0; j<Height; j++)
    {
      xnew = (((x+i) * cosine) / COS_RES - ((y+j) * sine) / SIN_RES) + XOrigin;
      ynew = (((x+i) * sine) / SIN_RES + ((y+j) * cosine) / COS_RES) + YOrigin;
      m_DisplayBuffer[xnew][ynew] = pBuf[i][j];
    }
  }
}

Die Makros sind wie folgt definiert:
#define SIN(deg) sin_lut[deg]
#define COS(deg) cos_lut[deg]

#define SIN_RES 127
#define COS_RES 127

Wobei die LUT(Lookup Tables) aus 360 Einträgen bestehen, die zwischen 
-126 und +127 liegen.


Nun meine Frage an die C-Experten hier. Wie komme ich besser um Float 
herum? Muss ich mit den argen Rundungsfehlern leben? Sieht schon nicht 
allzutoll aus, auf meinem emulierten Display.

PS: Bilder folgen

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Beispiel als Float-Variante

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Beispiel als Int-Variante

Autor: Marc S. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nun, es gibt einen Trick, um mit Integer-zahlen eine höhere 
Divisionsgenauigkeit zu erreichen:

du multiplizierst die zahl erst hoch, zum beispiel um den faktor 10 oder 
100 (auf bereichsüberschreitung achten) und dividierst dann. Nacher 
kannst das ganze dann ja wieder runterrechnen!

Nutze ich sehr gern für Grafikroutinen. Nimmt nicht viel Code ein und 
frisst weit weniger Rechenzeit als ein Float :) Man muss halt nur 
aufpassen, das einem die Variablen nicht zu groß werden, man ne 
Bereichsüberschreitung hat uns somit nur noch mist rauskommt.

P.S.:
du musst keinesfalls sinus UND cosinus tabelle implementieren, wenn du 
darauf zurückgreifst, das sinus und cosinus im Prinzip das gleiche ist, 
nur um ein paar Grad Phasenverschoben ;)

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nunja, gewissermaßen hab ich das ja oben auch gemacht. Die Sinustabelle 
habe ich zwischen +127 und -126 angelegt. Bei der Formel wird dann durch 
127 wieder geteilt. Blöderweise entstehen dabei aber Rundungsfehler.

Oder ich hab was falsch gemacht ;)

PS: Jou, das dachte ich mir auch schon. Habs aber noch nicht 
verwirklicht, da ich jetzt erstmal auf die reine Funktion aus bin. 
Optimieren kommt später.

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Oder ich hab was falsch gemacht ;)
Du machst es genau falsch herum, Du versuchst vom Originalbild aus zu 
drehen.
Damit riskierst du das aufgrund von Rundungsfehlern "Löcher" im Bild 
entstehen. Gehe vom Zielbild (rotiertes Bild) aus. Seinen Bereich kennst 
du.
(Rotation der Eckpunkte) Nun Rechnest du für jeden Punkt im Zielbild 
zurück welcher Punkt im Originalbild dazugehört. Dabei kommst du auf 
"Kommawerte" für den Originalpunkt. Dir steht es frei entsprechend der 
"Kommawerte" die umliegenden Originalbildpunkte zu mischen und daraus 
den neuen Farbwert zu bilden. Nennt sich bilineare Filterung.
Zurück zu den rotierten Eckpunkten:
Die Eckpunkte verbindest du durch Linien (Bresenham) und rasterst für 
jede Zeile im Display.

Autor: Roland Praml (pram)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich denke mal Marc S meint sowas:

xnew = (((x+i) * cosine) / COS_RES - ((y+j) * sine) / SIN_RES) + 
XOrigin;

wird zu:

xnew = (((x+i) * cosine) * SIN_RES - ((y+j) * sine) * COS_RES) / 
(SIN_RES*COS_RES) + XOrigin;

bei so vielen Multiplikationen kommt man aber gern in den Bereich, in 
dem der Int überläuft.
Das Problem mit den "Löchern" ist aber dann trotzdem nicht gelöst.

Gruß
Roland

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> xnew = (((x+i) * cosine) * SIN_RES - ((y+j) * sine) * COS_RES) /
> (SIN_RES*COS_RES) + XOrigin;

und wenn SIN_RES identisch ist zu COS_RES (was ja eigentlich
zu erwarten ist), dann wird daraus

xnew = (((x+i) * cosine) - ((y+j) * sine) ) / SIN_RES) + XOrigin;

Tip: Du willst Divisionen in der Berechnungskette soweit wie
möglich nach rechts schieben. Mal abgesehen von Overflows
entstehen bei Int-Rechnung keine Rundungsfehler bei:
Addition, Subtraktion, Multiplikation. Erst bei Division
muss man sich Gedanken um Rundungsfehler machen. Ergo möchte
man Divisionen erst ganz zum Schluss (und so wenige
wie möglich) machen, damit mit dem Rundungsfehler nicht
auch noch weiter gerechnet wird.

Aber Wolfram hat schon recht: Du zaeumst das Pferd von
der falschen Seite auf.


Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mit der Verwendung des Bresenham-Algorithmus sowohl zum Zeichnen des 
Bildes ,als auch zum Abtasten des Originals läßt sich eine ganze Menge 
an Multiplikationen vermeiden. Steht sehr gut beschrieben in:
Boris Bertelsons, Mathias Rasch: PC Underground. Data Becker, 1994, ISBN 
3815811171
Gute Einführung zu schnellen Grafikalgorithmen aus der Vor-3D-Kartenära
Die rechnen auch ohne float.
Sonst unter:
http://de.wikipedia.org/wiki/Demoszene
findest du genügend Einstiegslinks für die Suche


Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die vielen Antworten schonmal.

@Wolfram: Bei quadratischen Figuren habe ich ja die Eckpunkte (kann ich 
mir ja aus den Parametern Top, Left, Width, Height errechnen). Aber was 
ist, wenn (wie im Beispiel) Dreiecke gezeichnet werden sollen?
Dann kann ich aus den übergebenen Informationen keine Linien mehr 
ziehen.

Das Umstellen der Formel nach Bucheggsche Art ruft allerdings auch kein 
anderes Ergebnis hervor. Selbst bei Drehungen von 180°/270° rufen eine 
Verzerrung des Bildes hervor, was ja eigentlich nicht sein muss.

PS: Noch eine Frage bzgl. Der Lookup-Tabelle:
Ich hab mittlerweile herausgefunden, dass die Tabelle etwas 
unsymmetrisch ist. Daher sehen die Pfeile auf 180° und 270° etwas 
kleiner aus, als das Original. Nach welcher Formel soll ich denn nun die 
Tabellen erstellen? Bzw in welchen Wertebereichen? +126/-126 ?
Bisher hab ich dort folgende verwendet:
(signed char) (cos(Angle*3.14/180)*127+.5) //cos
(signed char) (sin(Angle*3.14/180)*127+.5) //sin

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Simon Küppers wrote:
> Danke für die vielen Antworten schonmal.
>
> @Wolfram: Bei quadratischen Figuren habe ich ja die Eckpunkte (kann ich
> mir ja aus den Parametern Top, Left, Width, Height errechnen). Aber was
> ist, wenn (wie im Beispiel) Dreiecke gezeichnet werden sollen?
> Dann kann ich aus den übergebenen Informationen keine Linien mehr
> ziehen.

Wieso nicht?
Auch eine gedrehte Linie ist immer noch eine Linie.

> Das Umstellen der Formel nach Bucheggsche Art ruft allerdings auch kein
> anderes Ergebnis hervor. Selbst bei Drehungen von 180°/270° rufen eine
> Verzerrung des Bildes hervor, was ja eigentlich nicht sein muss.

Dann ist irgendwas faul.
Bei 90°/180°/270° läuft eine Drehung auf einen Koordinatentausch
bzw. Multiplikation mit -1 hinaus.

Da sin(90°) bei dir gleich SIN_RES sein muesste und cos(90°)
eine satte 0 ergibt, ergibt die Formel

xnew = (((x+i) * cosine) - ((y+j) * sine)) / SIN_RES) + XOrigin;
ynew = (((x+i) * sine) + ((y+j) * cosine)) / COS_RES) + YOrigin;


xnew = (((x+i) * 0) - ((y+j) * SIN_RES)) / SIN_RES + XOrigin
ynew = (((x+i) * SIN_RES) + ((y+j)*0)) / COS_RES + YOrigin;

Multiplikationen mit 0 sind in int unkritisch, ergeben also
eine sichere 0:

xnew = (-((y+j) * SIN_RES)) / SIN_RES + XOrigin
ynew = (((x+i) * SIN_RES)) / COS_RES + YOrigin;

(da SIN_RES gleich COS_RES)

xnew = (-((y+j) * SIN_RES)) / SIN_RES + XOrigin
ynew = (((x+i) * SIN_RES)) / SIN_RES + YOrigin;

dadurch bleibt aber eine Multiplikation mit SIN_RES gefolgt
von einer Division durch SIN_RES und das sollte eigentlich
in int ein sauberes Ergebnis liefern.

Da das bei dir offensichtlich nicht so ist, schlage ich vor
du lässt dir mal bei einer Drehung um 90° ein paar Werte
ausgeben und analysierst womit da eigentlich multipliziert
wird.

>
> PS: Noch eine Frage bzgl. Der Lookup-Tabelle:
> Ich hab mittlerweile herausgefunden, dass die Tabelle etwas
> unsymmetrisch ist. Daher sehen die Pfeile auf 180° und 270° etwas
> kleiner aus, als das Original. Nach welcher Formel soll ich denn nun die
> Tabellen erstellen? Bzw in welchen Wertebereichen? +126/-126 ?
> Bisher hab ich dort folgende verwendet:
>
> (signed char) (cos(Angle*3.14/180)*127+.5) //cos
> (signed char) (sin(Angle*3.14/180)*127+.5) //sin
> 

Deine Asymetrie rührt daher, dass die Rundungskorrektur
bei negativen Zahlen anders rum laufen muss:

  0.7 gerundet auf die nächste ganze Zahl
      (signed char)( 0.7 + 0.5 ) = (signed char)( 1.2 ) = 1

 -0.7 gerundet auf die nächste ganze Zahl
      (signed char)( -0.7 + 0.5 ) = (signed char)( 0.2 ) = 0

0 ist aber nicht die nächste ganze Zahl zu -0.7
richtig wäre
 -0.7 gerundet auf die nächste ganze Zahl
      (signed char)( -0.7 - 0.5 ) = (signed char)( -1.2 ) = -1

Beim wegcasten von Kommastellen, werden diese einfach abgeschnitten!

Schreib dir mal eine round Funktion
signed char Round( float number )
{
  if( Numer > 0.0f )
    return (signed char)( number + 0.5f );
  else if( Number < 0.0f )
    return (signed char)( number - 0.5f );
  else
    return 0;
}


Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Karl Heinz Buchegger: Aha! Vielen Dank. Sowas hab ich mir doch glatt 
schon gedacht...

Ich werd erstmal wieder etwas herumprobieren ;)

PS: Puh, das ganze ist doch ziemlich kompliziert. Angenommen ich drehe 
wirklich nur die Eckpunkte erstmal und bestimme dann die Punkte, die im 
"Zielviereck" liegen, rechne zurück und bestimme so die Ursprungspixel:
Wie bestimme ich denn bei einem "verschobenen" Rechteck (quasi wie eine 
Raute) die Zielpunkte innerhalb des "verschobenen" Rechtecks? Irgendein 
Algorithmus?

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ich hab mir aufm Computer ne Funktion geschrieben, wo ich aus einem
>2dimensionalen Array eine Grafik auslesen kann, sie "virtuell" in einem
>bestimmten Displayspeicher platzieren kann, sie anschließend noch drehen
>und dann richtig anzeigen lassen kann.
Also bei einem 2dimensionalen Array kommt immer ein Rechteck raus, 
welches du
rotierst. Ob du darin ein Dreieck als Grafik ablegst ist nicht relevant, 
die anderen Punkte sind halt durchscheinend. Die Berechnungzeit ist aber 
dann immer proportional deiner arraygröße.
Was willst du nun EIN Bitmap darstellen und drehen oder sind es eher 
einfache Figuren. Diese könntest du auch als Linien codieren. Dies ist 
bei geringer Komplexität schneller. Kodierung ala (Wie hieß doch gleich 
die Programmiersprache mit der Schildkröte? richtig LOGO):
Anfangsdrehung von 0 Grad Linie 50 Pixel länge, Drehe dich um 20 grad 
nach links, nächste Linie 20 Pixel Länge, Drehe dich um 30 Grad nächste 
Linie 30 ... Figure ende
Du kannst dir vorstellen irgendwo gibt es einen Übergang, wo ein Bitmap 
drehen effizienter ist. Aber mit diesem Verfahren kannst du Figuren 
beliebig verdreht zeichnen , deine Anfangsdrehung ist dein Drehwinkel um 
den die Figur gedreht erscheint.
Was ist dein Problem mit der Lookuptabelle?
Zeichne dir einen Sinus auf und nutze die Symetrien. Du brauchst nur die 
Werte von 0..89,x Grad alles andere ist symetrisch, dies beachtest du 
beim Zugriff auf die Tabelle.
Beispiel:
Du hast eine Tabelle mit 16 Einträgen 0..15 z.B. 8 Bit
Wenn du mit 8 Bit weiterechnen willst kannst du nur 7 Bit codieren da 
die Symetrie auch ein - erfordert.
Dies ist aber sinnlos, du machst nachfolgend sowieso eine Multiplikation 
und kommst in den Bereich von short oder long also überlege es dir ob du 
nicht lieber mit 8Bit 0..255 codierst und den funktionswert von sin als 
short rausgibst. (höhere Genauigkeit)
256 entspricht dann 1 und ist dein skalierungsfaktor. (shift geht 
schneller) 1 wird in deiner Tabelle nie erreicht du codierst 0..89,x
für 90 Grad gilt Symetrie 1- (0 Grad Tabelle=0)=1
cosinus erschägst du mit um 90 Grad verschoben zum Sinus.
Wenn deine Tabelle genauer werden soll dann mache eine Interpolation 
zwischen 2 Werten.
Ok. 2 Seiten das reicht erst mal





Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Wolfram: Nein nein. Ich war irritiert. Du fingst an mit "Linien 
zeichnen"

>(Rotation der Eckpunkte) Nun Rechnest du für jeden Punkt im Zielbild
>zurück welcher Punkt im Originalbild dazugehört. Dabei kommst du auf
>"Kommawerte" für den Originalpunkt. Dir steht es frei entsprechend der
>"Kommawerte" die umliegenden Originalbildpunkte zu mischen und daraus
>den neuen Farbwert zu bilden. Nennt sich bilineare Filterung.
>Zurück zu den rotierten Eckpunkten:
>Die Eckpunkte verbindest du durch Linien (Bresenham) und rasterst für
>jede Zeile im Display.

Deswegen das ganze... Dass ich ein Dreieck oder Kreis in einem 
"rechteckigen" Array ablegen kann, ist mir schon klar.
Ich glaube du hast dich aber etwas missverständlich ausgedrückt. Ich 
denke, du meinst ich soll mir "virtuell" durch dieses 
Bresenham-Linienziehen die Pixel innerhalb des Ziel-Vierecks 
herausrechnen und diese dann auf die Quellkoordinaten zurückrechnen. 
Oder?

Bzgl. der Lookuptabelle: Ehrlichgesagt habe ich auch kein Problem damit, 
die Tabellen jetzt so zu belassen. Denn mal ehrlich, wie groß ist die 
Tabelle? Richtig, 360*1Byte = 360 Byte. Wenn ich das auf einem 
Mikrocontroller im Flash ablege, sind das mglw. nichtmal 1% des 
Gesamtspeichers. Da lohnt sich meiner Meinung nach kein 
Symetrie-ausgenutze, da das auch wieder etwas Rechenleistung brauchen 
würde (Wenn auch nicht viel).

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Oder?
Du rechnest für deine Eckpunkte die rotierten Koordinaten aus.
Zwischen den rotierten Eckpunkten denkst du dir Linien gespannt. Der 
umspannte Bereich ist deine zu füllende Fläche. Jeder Pixel darin wird 
auf das Originalbild zurückgerechnet. Das ist das wesentliche.
Wenn du das Füllen machst ist es vernünftig dies auf dem Bildschirm 
Zeilenweise (in einer Zeile nacheinander jeweils die Spalten im 
umspannten Bereich) von oben nach unten zu machen. Dazu brauchst du die 
Startspalte und die Endspalte für des umspannten Bereichs in der 
jeweiligen Zeile. Da das alles zusammenhängt benutzt du den 
Bresenhamalgorithmus um dich auf den (gedachten Linien) Zeile für Zeile 
abwärts zu bewegen. Ich glaube diese Art von Rasterung mit Bresenham 
geht auch im Originalbildarray womit das Rückrechnen entfällt. Deshalb 
der Buchhinweis, da habe ich es her.
jetzt klarer oder noch mehr verwirrt?

>Bzgl. der Lookuptabelle: Ehrlichgesagt habe ich auch kein Problem damit,
>die Tabellen jetzt so zu belassen.
Siehe Anmerkungen, auf deine Weise hast du immer den Skalierungsfaktor 
255 drin den du irgendwo evt. rausrechnen mußt, das zwingt dich zu einer 
Division durch 255 während ich mit einem shift auskomme, wenn ich mich 
jetzt nicht irre .(Kurz im Kopf durchgespielt) Das menschliche Auge ist 
sehr empfindlich auf geringe Abweichungen von 90 grad, deshalb sollte 
man da möglichst keine Fehler machen.

Autor: Jörg (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zum Thema rotieren habe ich mir vor langer Zeit gemerkt, daß man das 
auch mit komplexen Zahlen machen kann, ist viel effizienter als sin/cos.
Eine Rotation von einer Koordinate (=komplexe Zahl) um einen bestimmten 
Winkel ist eine Multiplikation mit einer bestimmten, konstanten 
komplexen Zahl. Diese hat den Betrag 1, denn sonst würde sie die erste 
skalieren.
Die Multiplikation kann man bestimmt in Festkomma mit geeignet langen 
Integers machen.

Mit so einem Algorithmus kann man auch fix Kreise zeichnen, das war 
glaubich die Anwendung damals.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Wolfram: Jou. So ists klar.

@Jörg: Tjo, sorry, aber das ist wohl nichts für mich ;) Keine Ahnung was 
eine komplexe Zahl ist, und da das Thema sicherlich umfangreicher ist, 
werd ich da erstmal Halt machen. Es kommt ja auf jeden Fall noch in der 
Schule dran. (So alt bin ich nu auch noch nicht, wie ihr vielleicht 
denkt)...

Also, ich bin mittlerweile soweit und hab die 4 Eckpunkte rotiert.
void CDisplay::CopyRotated(unsigned char** pBuf,int Left, int Top, int Width, int Height, int XOrigin, int YOrigin, int Angle)
{
  int x = Left - XOrigin;
  int y = Top - YOrigin;
  int cosine = COS(Angle); 
  int sine = SIN(Angle);
  struct point_t TopLeft, TopRight, BotLeft, BotRight;


  TopLeft.x = ( ( (x) * cosine) - ( (y) * sine) ) / 126 + XOrigin;
  TopLeft.y = ( ( (x) * sine) + ( (y) * cosine) ) / 126 + YOrigin;

  TopRight.x = ( ( (x+Width) * cosine) - ( (y) * sine) ) / 126 + XOrigin;
  TopRight.y = ( ( (x+Width) * sine) + ( (y) * cosine) ) / 126 + YOrigin;

  BotLeft.x = ( ( (x) * cosine) - ( (y+Height) * sine) ) / 126 + XOrigin;
  BotLeft.y = ( ( (x) * sine) + ( (y+Height) * cosine) ) / 126 + YOrigin;

  BotRight.x = ( ( (x+Width) * cosine) - ( (y+Height) * sine) ) / 126 + XOrigin;
  BotRight.y = ( ( (x+Width) * sine) + ( (y+Height) * cosine) ) / 126 + YOrigin;

  m_DisplayBuffer[TopLeft.x][TopLeft.y] = pBuf[0][0]; 
  m_DisplayBuffer[TopRight.x][TopRight.y] = pBuf[Width-1][0];
  m_DisplayBuffer[BotLeft.x][BotLeft.y] = pBuf[0][Height-1]; 
  m_DisplayBuffer[BotRight.x][BotRight.y] = pBuf[Width-1][Height-1]; 

}

Das Zielrechteck sieht dann so aus: (wieder in die horizontale Lage 
gedreht)
TopLeft          b             TopRight
        +--------------------+
        |                    |
       a|                    |c
        +--------------------+
BotLeft           d            BotRight

Nun dachte ich mir, dass ich erstmal die Linien a und c auflösen muss, 
und dann mehrere Horizontale Linien dazwischen Spanne, die mir dann die 
Koordinaten geben, zur Rückrechnung.

Spricht da was gegen? Andere Methode?



Autor: Wolfram (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ich verstehe deine Frage nicht ganz deshalb nochmal zur Sicherheit ein 
Bild.
Viel Spaß noch heute Abend beim programmieren.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ah, sorum würdest du das machen. Dachte jetzt, dass ich im gedrehten 
Bild nicht parallel zur unteren Bildkante auslese, sondern parallel zu 
den Seitenkanten des Rechtecks.

Nunja, das ist wohl die Lösung der ganzen Sache. Allerdings ist das 
Problem jetzt für mich, das umzusetzen.

Irgendwie muss ich jetzt die Kanten vom neuen Bild herauskriegen. Das 
sollte ja kein Problem sein, mit dem Bresenham Algorithmus. Jetzt muss 
ich aber die Array-Zeilen "abtasten" und feststellen, ob der i.te Punkt 
wirklich in diesem (gedrehten) Rechteck liegt. Allerdings hab ich hier 
schon meine Schwierigkeit.

Lege ich ein neues Array ein, wo alle Koordinaten der Umrandung 
enthalten sind, weiß ich a) nicht wie groß das ist und b) ist das 
irgendwie sehr (zu?) speicherintensiv.

Zeichne ich die Linien in den Bildschirmspeicher ein, wird das ja 
möglicherweise schon auf dem Display ausgegeben, was auch nicht 
erwünscht wäre.

Problem ist also jetzt, wie realisiere ich programmatisch die 
Speicherung der "Grenzen" der Region. Das Zurückrechnen ist ja dann im 
Nachhinein das geringe re Übel (hier wüsste ich auch wieder weiter).

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Jetzt muss ich aber die Array-Zeilen "abtasten" und feststellen, ob
> der i.te Punkt wirklich in diesem (gedrehten) Rechteck liegt.
nicht ob sondern wo!
Du bewegts dich mit dem Bresenhamalgorithmus im gedrehten Bild auf den 
gedachten Kanten Zeile für Zeile abwärts. Alles zwischen den beiden 
Kanten ist für die jeweilige Zeile im Bild. Für die beiden 
Begrenzungspunkte in der jeweiligen Zeile Rechnest du zurück wo die 
Punkte im originalbildarray liegen.
Zwischen diesen bestimmten Punkten im Originalbild ziehst du eine 
gedachte Gerade. Du bestimmst im gedrehten Bild wieviele Punkte zwischen 
deinen Begrenzungspunkten liegen. Genauso viele Punkte hast du im 
Originalbild auf deiner gedachten Gerade in konstantem Abstand.
Mach dir das am besten auf einem karierten Papier mit Zeichnungen klar. 
Das ist einfache Geometrie.

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Jörg wrote:

> Zum Thema rotieren habe ich mir vor langer Zeit gemerkt, daß man das
> auch mit komplexen Zahlen machen kann, ist viel effizienter als sin/cos.

Ach, und womit wird die komplexe Rechnung dann implementiert?

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ach, und womit wird die komplexe Rechnung dann implementiert?
mit einer zweispaltigen Lookuptabelle, die sich ehochj nennt. ;-)

Autor: Simon K. (simon) Benutzerseite
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
@Wolfram: Ich habs jetzt folgendermaßen gemacht:

Ich habe die linke Seite und die Rechte seite des (ungedrehten) 
Rechtecks umdrehen lassen. Anschließend bilde ich zwischen jedem (neuen) 
linke-Seite Punkt und rechte-Seite Punkt die Bresenham-Linie (Erstmal 
nur gezeichnet auf dem Display, um zu testen wie das aussieht).
Dabei herausgekommen ist der Anhang.

Die hellweißen Punkte sind die Kanten, die transformiert wurden. Die 
dunklen wurden per Bresenham gezeichnet. Jetzt seh ich aber immernoch 
Löcher dazwischen.

PS: Wenn ich das nochmal mit deinen Posts vergleiche, wolltest du ja, 
dass ich die Linien horizontal zur x-Achse abtaste. Ich hab ja jetzt 
quasi die "Abtastlinie" (sprich die hier vorerst gezeichnete 
Bresenham-Linie) immer um den Winkel verschoben. Aber ich finde keinen 
Lösungsansatz, die Abtast-Linie immer parallel zur x-Achse zu bilden.

Der aktuelle Code, wobei GetRotatedPoint den ausgelagerten Sin/Cos 
Drehalgorithmus beinhaltet.
void CDisplay::CopyRotated(unsigned char** pBuf,int Left, int Top, int Width, int Height, int xOrigin, int yOrigin, int Angle)
{
  struct point_t LeftPoint, RightPoint;
  int i;

  for (i=0; i<Height; i++)
  {
    LeftPoint = GetRotatedPoint(Left, Top+i, xOrigin, yOrigin, Angle);
    RightPoint = GetRotatedPoint(Left+Width-1, Top+i, xOrigin, yOrigin, Angle);

    Line(LeftPoint.x, LeftPoint.y, RightPoint.x, RightPoint.y, 0x55);

    m_DisplayBuffer[LeftPoint.x][LeftPoint.y] = pBuf[0][i];
    m_DisplayBuffer[RightPoint.x][RightPoint.y] = pBuf[Width-1][i];
  }
}

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Simon, anscheinend hast du immer noch ein Verständnisproblem.
Niemand hast gesagt das du mit Bresenham Linien zeichnen sollst.
Du gehst immer noch vom Originalbild aus, das ist FALSCH!
Geh vom gedrehten Bild AUF DEM BILDSCHIRM aus. Das ist ein Rechteck. 
JEDER PUNKT in diesem RECHTECK hat einen PUNKT im ORIGINALBILD. Du mußt 
vom PUNKT im RECHTECK auf dem BILDSCHIRM zurückrechnen welchem PUNKT im 
ORIGINALBILD er entspricht.
Nun ist die Frage wie du die PUNKTE im RECHTECK auf dem BILDSCHIRM 
durchrasterst. Empfehlung ist zeilenweise. Bresenham brauchst du um für 
eine Zeile zu bestimmen welche Punkte in dieser Zeile auf dem Bildschirm 
in deinem Rechteck liegen.
Da du bei diesem Algorithmus für jeden Punkt im Rechteck auf dem 
Bildschirm die Berechnung des Farbwertes machst, bin ich mir sicher das 
da keine Löcher sein können.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Wolfram: OH mann, lies doch mal was ich schreibe, und guck dir nicht 
nur den Code an!

MIR ist schon KLAR, dass ich mit dem Algorithmus nichts zeichnen soll, 
sondern damit die Punkte ermittle. Ich habe es TESTWEISE aber mal 
gezeichnet um zu sehen, welche Punkte im Zielbield ersetzt werden 
würden.

Die Rückrechnung einzubauen ist doch der letzte Schritt, den ich zu 
machen habe bei dem ganzen Zeug, und zugegebenermaßen auch der 
einfachste.

Und wenn ich die Zeile PARALLEL zur x-Achse abscanne, dann brauche ich 
DEFINITIV kein Bresenham-Algorithmus, weil alle Pixel in einer Reihe 
liegen, und ich nur irgendwie an Start-x und End-x Punkt dieser Linie 
kommen muss. Wie aber schon gesagt, fehlt mir hierfür der Ansatz!

Deswegen habe ich erstmal probiert, die "Scanline" quasi "mitzudrehen", 
was aber nicht das gewünschte Ergebnis ist.

Deswegen wollte ich indirekt fragen, wie ich vorgehen muss, um die 
Scanline zu finden im neuen Bild, da ich mir nicht vorstellen kann, wie 
ich Start und Endpunkt einer jeden Scanline berechnen soll.

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok. Schritt für Schritt
>Und wenn ich die Zeile PARALLEL zur x-Achse abscanne, dann brauche ich
>DEFINITIV kein Bresenham-Algorithmus, weil alle Pixel in einer Reihe
>liegen.
richtig, alle liegen nebeneinander (zwangsweise bei einer Zeile)
Frage: Woher weist du WO du in der Zeile Anfangen und WO du aufhören 
mußt?
(also welche Punkte in dieser Zeile im Rechteck liegen)

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Frage: Woher weist du WO du in der Zeile Anfangen und WO du aufhören
>mußt?

Nein, und ich weiß nicht, wie ich es herausfinden könnte. Und genau das 
ist mein Problem.

Schrieb ich ja auch schon:

>Deswegen wollte ich indirekt fragen, wie ich vorgehen muss, um die
>Scanline zu finden im neuen Bild, da ich mir nicht vorstellen kann, wie
>ich Start und Endpunkt einer jeden Scanline berechnen soll.

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok.
nimm am besten ein Blatt Papier und zeichne es dir auf
Wir haben das gedrehte Rechteck, das hat 4 Eckpunkte diese verbindest du 
mit Linien so daß ein Rechteck entsteht(das sind die gedachten Linien)
Jetzt willst du Zeile für Zeile das Rechteck horizontal Rastern, der 
Start und der Endpunkt liegen jeweils auf einer Linie. Kommst du so weit 
mit?
Auf den beiden Linien die den Start und  Endpunkt bilden mußt du dich 
zeilenweise abwärts bewegen, das geht mit dem Bresenham algorithmus.
Immer noch klar?
Die Feinheiten kommen noch...


Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Simon Küppers wrote:
>>Frage: Woher weist du WO du in der Zeile Anfangen und WO du aufhören
>>mußt?
>
> Nein, und ich weiß nicht, wie ich es herausfinden könnte. Und genau das
> ist mein Problem.

Du hast die 4 Originalen Eckpunkte.

Wenn du die über die Drehung drehst, dann erhältst du 4
Punkte die verdreht sind:


                              * 1



                                       * 2
                 * 3


                           * 4

Um jetzt die Scanlines (die waagrechten) Linien zu bestimmen,
musst du eine Linie von 1 nach 3 und eine Linie von 1 nach 2
ziehen.
Für jede Linie gibt es daher einen Punkt links (5) und rechts(6)
wo deine Pixel im gedrehten Bild anfangen und wo sie aufhören:

                              * 1

                         + 5        + 6

                                       * 2
                 * 3


                           * 4

und woher kriegst du die koordinaten von Punkt 5 und 6. Na zb.
indem du einen Bresenham zwischen 1 und 3 aufsetzt (der liefert
dann alle Koordinaten für 5) und einen weiteren Bresenham
zwischen 1 und 2 (der die Koordinaten für Punkt 6 liefert ).

Wenn dir das mit dem Bresenham zu aufwändig ist:
Man kann auch fürs erste mittels double oder float linear
zwischen den Punkten Interpolieren.
Nach dem Muster:
  Linie von 1 nach 3  also von P1x/P1y nach P3x/P3y
  dx = P3x - P1x
  dy = P3y - P1y

  wenn sich bei einer Änderung von dy in X Richtung eine
  Änderung von dx ergibt, dann ist diese Änderung beim
  Übergang von einer Zeile zur nächsten: dx/dy
  Für die n-te Scanline (Wenn P1 in der 0-ten Scanline
  liegt gilt daher:  P5x = P1x + n * dx / dy
                     P5y = P1y + n

Sinngemäss dasselbe noch mal für P6 und du hast deine
beiden Punkte.

Aber bitte: Stufenweise implementieren und auch stufenweise
testen. Du hast nichts davon, wenn du das bis zur Urbitmap
durchziehst. Das wird nicht auf Anhieb funktionireen und alles
was du am Display siehst ist: geht nicht. Sowas kann man
nur stufenweise debuggen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wolfram wrote:
> Ok.
> nimm am besten ein Blatt Papier und zeichne es dir auf

Das kann ich nur unterstützen.

Aufzeichnen ist bei Graphikprogrammierung immer gut.

Das andere was auch immer gut ist:
In der Zeichnung nach rechtwinkeligen Dreiecken suchen.
Die gibt es fast immer und sie vereinfachen die
Überlegungen zur Arithmetik ungemein.
Das andere was auch immer gut ist: Strahlensatz


                              *  1






                 * 3

Da kann ich sofort ein rechtwinkeliges Dreieck zeichnen:


                              *  1
                              |
                              |
                              |  dy
                              |
                              |
                              |
                3 *-----------+
                        dx

und nachdem ich das kann, gilt der Strahlensatz und ich
kann für jede Position P entlang der Hypothenuse


                              *  1
                              |
                              | py
                       P *    |--    dy
                              |
                              |
                              |
                3 *-----------+
                         | px

                        dx

sagen:  dx / dy = px / py
oder auch.   dy / dx = py / px

da ich py kenne (Ich weiss ja wieviele Zeilen ich von 1 nach
unten gegangen bin) folgt daraus sofort

          px = dx * py / dy

unter Berücksichtigung das alles von P1 aus gerechnet wurde und
dass py ganzzahlig ist, folgt dann die behauptete Formel vom
vorigen Posting.

Autor: Wolfram (Gast)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Verdammt @Karl Heinz, jetz hab ich so ein schönes Bild gemalt, das poste 
ich jetzt auch!!!
:-)))

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hmm, ich glaube das Problem liegt noch etwas weiter weg.
Das, was ihr bisher geschrieben habt, war mir eigentlich schon bekannt.
An die Punkte komm ich, indem ich Bresenham zwischen den Eckpunkten 
ansetze, ok.
Das Problem ist, wie ich das programmtechnisch umsetze, irgendwie muss 
ich ja feststellen, zwischen welchen (Randlinien) ich mich befinde, denn 
ab der x. Scanline liegt ja diese Scanline nicht mehr zwischen den 
oberen Beiden Randlinien, sondern unterhalb. Und wenn das Rechteck dann 
nicht um 45° sondern um 33° gedreht ist, wird das ganze noch etwas 
komplizierter. Irgendwie muss ich also ne Schleife konstruieren, die - 
keine Ahnung wie - lange laufen muss. Dann muss ich bei jeder Scanline 
zweimal Bresenham ausführen um an den y-Punkt im Rechteck zu kommen.

Und das ist meiner Meinung nach das, was irgendwie nicht sein kann. Der 
Aufwand ist doch viel zu riesig, als dass ich das so umsetzen würde. 
Deswegen würd ich gerne (schon etwas länger) von Euch wissen, wie ihr 
das programmtechnisch umsetzen würdet.

Versteht ihr? Dass ne Linie ne steigung von dy/dx hat, ist nicht das 
Problem, das ich habe.

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>um 45° sondern um 33° gedreht ist, wird das ganze noch etwas
>komplizierter. Irgendwie muss ich also ne Schleife konstruieren, die -
>keine Ahnung wie - lange laufen muss.
Das ganze muß Laufen bis du mit beiden Linien bei Punkt P4 angekommen 
bist.

>Dann muss ich bei jeder Scanline zweimal Bresenham ausführen um an den >y-Punkt 
im Rechteck zu kommen.
absolut richtig erfaßt.

erster Ansatz:
Implementiere den Bresenhamalgorithmus
ändere ihn in diese Form ab
Es geht um die Linie von PunktA nach PunktB, das ist mein aktueller 
Punkt
Was ist mein nächster Punkt?
also
void Bresenham(int* nächster PunktX,int* nächster PunktY,
int aktueller PunktX,int aktuellerPunktY,
/*Linie*/
int X1,int Y1,int X2,int Y2);

dem gibst du deine Linie auf der du dich bewegen willst deine aktuelle 
Zeile (die Spalte merkst du dir von letzten Punkt)
und bekommst den nächsten Punkt auf der Linie, beachte diese Punkt 
könnte noch in der selben Zeile liegen (du willst aber die nächste 
Zeile) dann Aufruf wiederholen bis nächte Zeile kommt (das kannst du 
später optimieren)
Verwende es zur Umsetzung des gemalten Algorithmus (bild.gif).
Probiere ertmal nur das Rechteck zu füllen, noch keine Rückrechnung.


Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wolfram wrote:

> Probiere ertmal nur das Rechteck zu füllen, noch keine Rückrechnung.

Das ist ein guter Vorschlag.

@Simon
Das ganze ist wirklich einfacher als es jetzt klingt.

WEnn du die Punkte transformiert hast, suchst du den
mit der größten y Koordinate raus. Danach den mit
der kleinsten.
Damit hast du schon mal Punkt 1 und Punkt 4.

Deine Schleife läuft für alle y Koordinaten von P1y bis
P4y.

Jetzt musst du nur noch die jeweilige linken (bzw. rechten)
X Koordinaten für die Zeile y bestimmen. Es gibt aber nur
2 Möglichkeiten pro Seite. Entweder die y Koordinate
befindet sich noch auf Linie P1/P3 oder aber wenn y
weit genug nach unten gewandert ist, wechselt die über
auf die Linie P3/P4. Du fängst also einfach mal
mit der Linie P1/P3 an und überprüfst bei jedem Schleifen-
durchlauf auf deine Schliefenvariable y identisch zu P3y
ist. Ist es dass, dann wird umgeschaltet auf die Linie P3/P4.
Das ganze natürlich identisch auf der rechten Seite mit P2

Ja so ist Computergraphik. Von der Ferne sieht alles ganz
einfach aus. Schaut man aber genauer hin, dann wirds ein
bischen komplizierter. Ist aber alles noch handhabbar.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Simon Küppers wrote:
> Das Problem ist, wie ich das programmtechnisch umsetze, irgendwie muss
> ich ja feststellen, zwischen welchen (Randlinien) ich mich befinde, denn
> ab der x. Scanline liegt ja diese Scanline nicht mehr zwischen den
> oberen Beiden Randlinien,

OK. Man kann das Ganze auch in der X Richtung machen. Traditionell
nimmt man die y Richtung.

Und wieder: Auf dem Papier aufmalen.
Die Scanlinie, die das Rechteck abtastet simulierst du
mit einem Lineal. Leg es oben bei P1 an und lass es zeilen-
weise runterlaufen (karriertes Papier simuliert dir die Pixel).
Und dann beobachte was passiert und ziehe deine Schluesse
daraus.
zb. Wie lang ziehst du das Lineal über das Rechteck?
Irgendwann hörst du ganz von alleine auf. Wann?
(Antwort: Ich fange beim obersten Punkt an und offensichtlich
ist die ganze Schose vorbei, wenn der unterste Punkt erreicht
ist. Woran erkennt man den obersten Punkt? Woran den untersten?)

> sondern unterhalb. Und wenn das Rechteck dann
> nicht um 45° sondern um 33° gedreht ist, wird das ganze noch etwas
> komplizierter.

Quatsch: Die Punkt verändern ihre Position. Mehr aber auch nicht.
Das Verfahren ist immer noch exakt das gleiche, nur die
Zahlenwerte sind andere.
Komplizierter wird das ganze, wenn aus dem Rechteck ein
beliebiges Polygon wird. Noch komplizierter wird das
Ganze, wenn dieses Polygon auch noch Löcher enthalten kann.

> Und das ist meiner Meinung nach das, was irgendwie nicht sein kann. Der
> Aufwand ist doch viel zu riesig, als dass ich das so umsetzen würde.

Falsche Frage.
Richtige Frage: Was ist dir lieber
* Eine simpel zu realisiernde Vorwärtstransformation, die im
  Endergebnis Löcher hinterlässt
* Eine etwas aufwändigere Rücktransformation, die allerdings
  ein sauberes Ergebnis hinterlässt.

Alte Regel:
Es ist leicht ein 'einfaches' oder auch ein 'schnelles'
Verfahren auf die Beine zu stellen, wenn die Ergebnisse
nicht korrekt sein müssen.

> Versteht ihr? Dass ne Linie ne steigung von dy/dx hat, ist nicht das
> Problem, das ich habe.

Ich kann dir nur immer wieder den Rat geben:
Mal dir die Situation auf Papier auf. Such dir Hilfsmittel:
In dem Fall simulierst du die Scanline mit einem Lineal oder
einem anderen Blatt Papier, dass du über die Zeichnung zíehst
und dann hältst du nach Zusammenhängen Ausschau.
Dann formulierst du einen Plan in Umgangssprache und wieder:
Du probierst deinen Plan mit der Zeichnung und mit den Hilfsmitteln
aus und suchst nach Fehlern im Plan, bzw. wo du Dinge präzisieren
musst. Zur Kontrolle probierst du das Ganze dann auch noch mit
anderen Eingangsdaten aus.
Du denkst mir zu früh in C Einheiten und in Form von Schleifen und
sitzt zu schnell vorm Editor um Code zu schreiben.

Autor: Wolfram (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Guten Morgen,
@Simon: Du mußte es nicht mal aufzeichnen, du mußte eigentlich nur das 
letzte Bild von mir ausdrucken, da steht der Algorithmus den @Karl Heinz 
ganz ausführlich gemacht hat, auch nochmal daneben.

>Deswegen würd ich gerne (schon etwas länger) von Euch wissen, wie ihr
>das programmtechnisch umsetzen würdet.

>Du denkst mir zu früh in C Einheiten und in Form von Schleifen und
>sitzt zu schnell vorm Editor um Code zu schreiben.
Ich kann Karl Heinz nur zu stimmen, genau aus diesem Grund bekommst du 
Probleme.

ausführliche Schrittfolge:
1.groben Algorithmus ausdenken <- Den Algorithmus hast du bekommen
2.Algorithmus verstehen <- hast du wahrscheinlich
3.grob nachvollziehen um ihn in Schrittfolgen zu zerlegen und 
Abbruch/Umschaltkriterien festzustellen <- teilweise gemacht
4.Algorithmus in Deutsch formulieren <- teilweise gemacht
5.Algotrithmus in Deutsch Schritt für Schritt formulieren
6.aufmalen mit Abbruchkriterien
7.umformen in PAP
8. Typenbereiche festlegen
9.hinschreiben in Programmiersprache
10. Bewertung und Optimierung entweder nochmals ab. 8 oder 5. oder 1.

Schritt 1 bis 6 ist programmieren, der Rest reiner Formalismus
Viele "Programmierer" scheitern an der Lösung eines Problems, weil sie 
versuchen gleich den PAP aufzustellen oder gleich in der 
Programmiersprache losschreiben. Das wird nichts. Es führt zu Lösungen 
die sehr umständlich sind oder es geht gar nicht, weil versucht wird 
einen Algorithmus in den Formen(Schleifen,etc) der Programmiersprache zu 
entwerfen. Erst kommt der Algorithmus, dann werden die Formen der 
Programmiersprache daran angepaßt.

Dein aktuelles Problem ist hervorragend geeignet um von
for (???){äh, was tue ich jetzt eigentlich} wegzukommen.

>Und das ist meiner Meinung nach das, was irgendwie nicht sein kann. Der
>Aufwand ist doch viel zu riesig, als dass ich das so umsetzen würde.
Den Aufwand kannst du gar nicht einschätzen, solange du den Algorithmus 
nicht Schritt für Schritt vorliegen hast und auf 
Optimierungsmöglichkeiten überprüft hast. Optimierungsmöglichkeiten sind 
in diesem Fall nicht, wenn ich bei der Variable 8bit nehme spare ich 2 
Takte, sondern für diese Punkte muß ich keine Transformation mit sin/cos 
machen weil ich das durch die Nachbarpunkte schon weiß.
Der Algorithmus läßt übrigens auch ein Vergrößern und Verkleinern des 
Rechtecks zu.




Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wolfram wrote:

> Der Algorithmus läßt übrigens auch ein Vergrößern und Verkleinern des
> Rechtecks zu.

Nicht zu vergessen, dass solche Scanline Algorithmen quasi
Standardverfahren in der Computergraphik sind. Die komplett
zu verstehen und mal umgesetzt zu haben kann nie schaden.

zb. Benutze ich so ein Scanlineverfahren um ein geschlossenes
Polygon zu schraffieren. Das was Windows an 'Füllmustern' für
Flächen anbietet ist für CAD nicht zu gebrauchen. Auf einem
Plotter muss die 'Schraffur' dann nur noch dicht an dicht sitzen,
um gefüllte Polygone ausgeben zu können. Will man Flächen im 3D
mit Beleuchtung rendern, braucht man ein Scanline Verfahren um
bei Gouraud und/oder Phong Shading (oder vielleicht noch schlimmeren)
die Pixel einer Fläche abzurastern, etc. Es gibt viele Anwendungs-
fälle für Scanline Verfahren.



Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Soo, da ihr ja meintet, dass man so einen Scanline Algorithmus immer mal 
gebrauchen kann, und man ja schließlich immernoch ein bisschen Stolz in 
sich trägt und es einfach nicht ertragen kann diese Aufgabe nicht 
gemeistert zu haben:

Inzwischen habe ich folgendes gemacht:
1. Ich habe eine Klasse für eine Bresenham-Linie angelegt. Sprich: Ich 
initialisere mit dem Start- und Endpunkt und kann per Methode
BOOL CBresLine::GetNextPointOnLine(CMyPoint& Point)
 immer die Punkte der Reihe nach abfragen, wobei eine 0 zurückgegeben 
wird, falls der aktuelle Punkt den Endpunkt überschreiten würde, und die 
Linie somit am Ende ist.

2. Eine Funktion zum sortieren von 4 Punkten zuerst nach y-Koordinate 
und anschließend nach x-Koordinate (Damit wollte ich bezwecken, dass 
falls y-Koordinaten auf gleicher Höhe liegen, immer die mit dem 
niedrigeren Array-Index weiter rechts bzw. links liegt). Hierfür hab ich 
den Bubblesort-Algo gewählt (Was sagt ihr zu der Lösung. Gut oder eher 
nicht?)

3. Die Sin/Cos Rotation ausgelagert:
CMyPoint GetRotatedPoint(int xPos, int yPos, int xOrigin, int yOrigin, int Angle)
 Die Funktion sollte eigentlich auch mit negativen Drehungen umgehen 
können (bei negativ, dann 360-Angle).

4. Das ganze zusammenzufügen in einer CopyRotated Funktion. Und hier 
fehlt mir mal wieder ein wenig der Ansatz. Ich hab das ganze nun erstmal 
wie folgt gemacht:
CMyPoint Points[4];  //Array für Eckpunkte
CBresLine LeftBorder, RightBorder;  //Aktuelle Linke und Rechte Seite
CMyPoint LeftPoint, RightPoint;  //Aktueller Linker und Rechter Eckpunkt der Scanline
CMyPoint ScanPoint;  //Aktueller Scanpoint

//Gedrehte Eckpunkte holen
Points[0] = GetRotatedPoint(Left, Top, xOrigin, yOrigin, Angle);
Points[1] = GetRotatedPoint(Left+Width-1, Top, xOrigin, yOrigin, Angle);
Points[2] = GetRotatedPoint(Left+Width-1, Top+Height-1, xOrigin, yOrigin, Angle);
Points[3] = GetRotatedPoint(Left, Top+Height-1, xOrigin, yOrigin, Angle);

//Punkte nach y- und anschließend nach x-Koordinate sortieren
SortPoints(Points);

//Die Anfangs-Begrenzungsseiten der Scanlines bestimmen
LeftBorder.SetLine(CMyLine(Points[0], Points[1]));
RightBorder.SetLine(CMyLine(Points[0], Points[2]));

//Diese beiden Seiten vorerst sichtbar machen
Line(Points[0].x, Points[0].y, Points[1].x, Points[1].y, 0x33);  Line(Points[0].x, Points[0].y, Points[2].x, Points[2].y, 0x66);

So, ich komme jetzt ehrlichgesagt auf keinen grünen Ast um die 
While-Schleife zu bauen, sowie die Punktumschaltung. Obwohl die Punkte 
zwar schon geordnet sind, fehlt mir da irgendwie die Lösung. Ich dachte 
eventuell, dass man die Punkte anders organisiert, sodass die linke 
Begrenzungslinie immer zwischen Punkt 0|1 liegt usw... (Deswegen auch 
die Anmerkung beim Sortier-algorithmus. Ich glaub ich bin da auf dem 
Holzweg)
Irgendwie sind es zuviele Bedingungen die da eine Rolle spielen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Studier das mal:

Das ganze beruht darauf, dass ja die Punkte nicht einfach
irgendeine Reihenfolge haben, sondern die Outline des Rechtecks
von den Punkten 0, 1, 2, 3 (in dieser Reihenfolge) gebildet
wird. Nehmen wir mal an, dass das Rechteck etwas rotiert ist
(dann sieht man besser worauf ich hinaus will)

                   0
                   +
                  / \
                 /   \
                /     \
               /       + 3
                     
           1 +       /
              \     /
               \   /
                \ /
                 +
                 2


(annahme: Die Scanline geht von oben nach unten)
D.h. die linke Kante der Outline beginnt mit der Kante
von 0 nach 1, die rechte Kante von 0 nach 3.
Hat die y Koordinate der Scanline die y-Koordinate von
3 erreicht, dann wird die rechte Kante umgeschaltet auf
die Kante von 3 nach 2 und sinngemäß schaltet die linke
Kante um auf die Kante von 1 nach 2.

Alles was noch bleibt, ist die Reihenfolge so hinzudrehen,
dass sich bei beliebiger Rotation wieder dieses Schema ergibt.
Dazu schau ich einfach welches der oberste Punkt ist, und
rotiere das Puntkablaufschema

    0, 1, 2, 3


entsprechend oft nach links.

PS: Ich hab noch keinen Bresenham eingebaut. Die Berechnung
der Start-X und End-X Koordinaten in einer Zeile erfolgt
mittels normaler Geradengleichung (mir ging es in erster Linie
darum, dir mal eine Scanlineverfahren zu zeigen).

Wichtig: Unbedingt am PC mal kompilieren und damit rumspielen.
Sowas kann man nur entwickeln, wenn man Zahlenausgaben machen
kann, die man auch studieren kann! Es hat wenig bis gar keinen
Sinn die ersten Tests direkt auf der Graphikhardware zu machen.
Alles was du siehst ist: Es funktioniert nicht.
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

struct Point {
    int x;
    int y;
};

unsigned char Reihung[4];
struct Point Punkte[4];

void Rotate( double ang )
{
    int tmp;

    for( unsigned char i = 0; i < 4; ++i ) {
        tmp         = (int)( cos(ang)*Punkte[i].x - sin(ang)*Punkte[i].y );
        Punkte[i].y = (int)( sin(ang)*Punkte[i].x + cos(ang)*Punkte[i].y );
        Punkte[i].x = tmp;
    }
}

void Scan()
{
    // zunächst mal den Punkt oben finden
    int ymax = Punkte[0].y;
    unsigned char NrRol = 0;
    unsigned char i;

    for (i = 1; i < 4; i++)
    {
        if(Punkte[i].y > ymax) {
            NrRol = i;
            ymax = Punkte[i].y;
        }
    }

    // Dann die Reihung entsprechend oft nach links rotieren
    for( i = 0; i  < NrRol; ++i ) {
        unsigned char tmp = Reihung[0];
        Reihung[0] = Reihung[1];
        Reihung[1] = Reihung[2];
        Reihung[2] = Reihung[3];
        Reihung[3] = tmp;
    }

    // gestartet wird beim Punkt  mit dem Index Reihung[0]
    // die linke Kante wird gebildet von den Punkten Reihung[0] und Reihung[1]
    // die rechte Kante wird gebildet von den Punkten Reihung[0] und Reihung[3]
    //
    // wenn dies nicht klar ist, dann unbedingt eine Zeichnung machen!
    //
    // jetzt in y Richtung durchgehen. Ein Kantenwechsel erfolgt, wenn die
    // y Koordinate der Scanline die Endpunktskoordinate der Kante erreicht
    // hat. Dann wird auf die nächste Kante umgeschaltet.
    // Bei der linken Kante ist dies: Reihung[1] nach Reihung[2]
    // Bei der rechten Kante ist dies: Reihung[3] nach Reihung[2]
    //
    // der komplette Scan ist zuende, wenn y die y Koordinate von Reihung[2] erreicht hat

    int y = ymax;
    unsigned char StartLinks = Reihung[0];
    unsigned char StartRechts = Reihung[0];
    unsigned char EndeLinks = Reihung[1];
    unsigned char EndeRechts = Reihung[3];
    int dxLinks = Punkte[EndeLinks].x - Punkte[StartLinks].x;
    int dyLinks = Punkte[EndeLinks].y - Punkte[StartLinks].y;
    int dxRechts = Punkte[EndeRechts].x - Punkte[StartRechts].x;
    int dyRechts = Punkte[EndeRechts].y - Punkte[StartRechts].y;

    while( y > Punkte[Reihung[2]].y ) {
        if( y == Punkte[EndeLinks].y ) {
            printf( "Wechsle Kante links\n");
            StartLinks = EndeLinks;
            EndeLinks = Reihung[2];

            dxLinks = Punkte[EndeLinks].x - Punkte[StartLinks].x;
            dyLinks = Punkte[EndeLinks].y - Punkte[StartLinks].y;
        }

        if( y == Punkte[EndeRechts].y ) {
            printf( "Wechsle Kante rechts\n");
            StartRechts = EndeRechts;
            EndeRechts = Reihung[2];

            dxRechts = Punkte[EndeRechts].x - Punkte[StartRechts].x;
            dyRechts = Punkte[EndeRechts].y - Punkte[StartRechts].y;
        }

        //
        // An der Kante Reihung[0] nach Reihung[1]:
        // Wo beginnt die Zeile?
        //
        int xLinks = Punkte[StartLinks].x + ( y - Punkte[StartLinks].y ) * dxLinks / dyLinks;

        // und wo endet sie?
        int xRechts = Punkte[StartRechts].x + ( y - Punkte[StartRechts].y ) * dxRechts / dyRechts;

        printf( "Zeile %d: Kante von x:%d nach x:%d\n", y, xLinks, xRechts);

        y--;
    }
    printf( "Zeile %d: Kante von x:%d nach x:%d\n", y, Punkte[EndeLinks].x, Punkte[EndeRechts].x);
}

int main(int argc, char *argv[])
{
    Punkte[0].x = 0;
    Punkte[0].y = 0;
    Punkte[1].x = 10;
    Punkte[1].y = 0;
    Punkte[2].x = 10;
    Punkte[2].y = 5;
    Punkte[3].x = 0;
    Punkte[3].y = 5;

    Reihung[0] = 0;
    Reihung[1] = 1;
    Reihung[2] = 2;
    Reihung[3] = 3;

    printf( "Rechteck\n" );
    for( int i = 0; i < 4; ++i ) {
        printf( "%d: %d/%d\n", i, Punkte[i].x, Punkte[i].y );
    }
    printf( "\n" );

    Rotate( 120 * 3.141592654 / 180 );

    printf( "Rechteck gedreht\n" );
    for( int i = 0; i < 4; ++i ) {
        printf( "%d: %d/%d\n", i, Punkte[i].x, Punkte[i].y );
    }
    printf( "\n" );

    Scan();
}


PS: Ich hab das schnell in einer halben Stunde runtergetippt.
Mit dem Beispiel klappt es und ich hab auch den Winkel in der
Rotation mal verändert. Es ist aber durchaus möglich, dass ich
noch einen Sonderfall übersehen habe.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tja. Da hab ich ja einiges an Optimierungspotential liegen
gelassen :-)

Zunächst mal braucht niemand das Zwischenarray 'Reihung'.

Wenn der Punkt i oben ist, dann ist (bei Anordnung entgegen
dem Uhrzeiger) der Punkt links immer der mit der Nummer
 Links = ( i + 1 ) % 4;
 Rechts = ( i - 1 + 4 ) % 3;
 Unten = ( i + 2 ) % 4;

Damit vereinfacht sich das ganze aber zu:
void Scan()
{
    // zunächst mal den Punkt oben finden
    int ymax = Punkte[0].y;
    unsigned char NrRol = 0;
    unsigned char i;
    unsigned char Oben, Unten, Links, Rechts;

    for (i = 1; i < 4; i++)
    {
        if(Punkte[i].y > ymax) {
            Oben = i;
            ymax = Punkte[i].y;
        }
    }

    Links = ( Oben + 1 ) % 4;
    Rechts = ( Oben - 1 + 4 ) % 4;
    Unten = ( Oben + 2 ) % 4;

    // gestartet wird beim Punkt  mit dem Index Oben
    // die linke Kante wird gebildet von den Punkten Oben und Links
    // die rechte Kante wird gebildet von den Punkten Oben und Rechts
    //
    // wenn dies nicht klar ist, dann unbedingt eine Zeichnung machen!
    //
    // jetzt in y Richtung durchgehen. Ein Kantenwechsel erfolgt, wenn die
    // y Koordinate der Scanline die Endpunktskoordinate der Kante erreicht
    // hat. Dann wird auf die nächste Kante umgeschaltet.
    // Bei der linken Kante ist dies: Links nach Unten
    // Bei der rechten Kante ist dies: Rechts nach Unten
    //
    // der komplette Scan ist zuende, wenn y die y Koordinate von Unten erreicht hat

    int y = ymax;
    unsigned char StartLinks = Oben;
    unsigned char StartRechts = Oben;
    unsigned char EndeLinks = Links;
    unsigned char EndeRechts = Rechts;
    int dxLinks = Punkte[EndeLinks].x - Punkte[StartLinks].x;
    int dyLinks = Punkte[EndeLinks].y - Punkte[StartLinks].y;
    int dxRechts = Punkte[EndeRechts].x - Punkte[StartRechts].x;
    int dyRechts = Punkte[EndeRechts].y - Punkte[StartRechts].y;

    while( y > Punkte[Unten].y ) {
        if( y == Punkte[EndeLinks].y ) {
            printf( "Wechsle Kante links\n");
            StartLinks = EndeLinks;
            EndeLinks = Unten;

            dxLinks = Punkte[EndeLinks].x - Punkte[StartLinks].x;
            dyLinks = Punkte[EndeLinks].y - Punkte[StartLinks].y;
        }

        if( y == Punkte[EndeRechts].y ) {
            printf( "Wechsle Kante rechts\n");
            StartRechts = EndeRechts;
            EndeRechts = Unten;

            dxRechts = Punkte[EndeRechts].x - Punkte[StartRechts].x;
            dyRechts = Punkte[EndeRechts].y - Punkte[StartRechts].y;
        }

        //
        // An der Kante Reihung[0] nach Reihung[1]:
        // Wo beginnt die Zeile?
        //
        int xLinks = Punkte[StartLinks].x + ( y - Punkte[StartLinks].y ) * dxLinks / dyLinks;

        // und wo endet sie?
        int xRechts = Punkte[StartRechts].x + ( y - Punkte[StartRechts].y ) * dxRechts / dyRechts;

        printf( "Zeile %d: Kante von x:%d nach x:%d\n", y, xLinks, xRechts);

        y--;
    }
    printf( "Zeile %d: Kante von x:%d nach x:%d\n", y, Punkte[EndeLinks].x, Punkte[EndeRechts].x);
}

  

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ah Dank dir! Das studier ich mal..

Man braucht ja garkeine Sortierfunktion meiner Art. Deine 
"Rotiermethode" ist auch ziemlich ausgefuchst.

Ich weiß aber jetzt wo ich weiter ansetzen muss: Erstmal die Punkte nach 
deinem Schema sortieren (hab ich ja schon in die richtige Richtung 
gedacht). Wenn ich weiß, wo die Punkte liegen, unabhängig vom Winkel, 
dann ergibt sich ja fast eine statische Figur nach der Drehung, die viel 
berechenbarer ist.

Danke nochmal ;)

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.