4. Linien, Bresenham

Linien, Bresenham

  • A

    hallo
    ich bin gerade dabei eine art 'ascii-engine' zu schreiben. d.h. ich habe ein
    int [80][25] array dessen werte geändert werden und dann der reihe nach angezeigt werden, so dass ein bild entsteht.
    beispiel:ein x an postion (4,5):
    screen[4][5]='x';

    jetzt gibt es aber probleme mit linien.dank google weiss ich von einem Bresenham-algo. ich bin mir nicht ganz sicher ob ich den wirklich verstanden habe, hier mal meine version(nach einer seite):

    int screen::draw_line(int x1,int y1  ,int x2,int y2,  char symbol)
{
int m= (y2 - y1) / (x2 - x1); //steigung
int d=0;
int x = x1; 
int y = y1;

while (x != x2)
{
    sign[x][y]=symbol;
    x++;
    d=d+m;
    if (d > 0.5){
        y++;
        d--;
        }
   }
return 0;
}

    aufgerufen wird z.B. mit testbild.draw_line(10,10 ,20,8, 'x');
    richtig gut funktioniert es aber nur wenn der steigunswinkel 45° beträgt also z.B. eine linie von (10,10) nach (20,20).
    ehrlich gesagt wundert mich schon das.

    hat jemand vielleicht irgendeine idee oder kennt eine _gute_ seite wo der algo. erklärt wird? die links die ich bei google dunkelblau gefärbt habe waren irgendwie nicht wirklich verständlich...

    0
  • R

    Also ich hab den Algorithmus benutzt um Pixel in einer Linie zu zeichnen und das hat geklappt.

    Ich verschied das mal in das Grafik Forum

    0
  • G

    Zumindest kann man mit dem Algorithmus da oben keine senkrechten Linien zeichnen, da du dann durch 0 teilen würdest.

    EDIT : Außerdem bestimmst du m mit einer Integer-Division. Deshalb klappt das wohl nur bei 0° und 45° wirklich gut.

    EDIT 2 : m und d sollten floats sein und keine ints.

    [ Dieser Beitrag wurde am 29.01.2003 um 22:03 Uhr von Gregor editiert. ]

    0
  • T

    Ja, es ist Unsinn, zu prüfen, ob ein int-Wert größer als 0.5 ist!
    Außerdem sieht das nicht nach dem Bresenham-Algorithmus aus, der funktioniert nämlich ohne floats oder doubles und kommt mit allen Arten von Linien zurecht.

    0
  • R
    Mod

    was den bresenham ausmacht ist, dass er ohne division auskommt, das war früher mit das kostspieligste und deswegen war der gut.

    MfG
    micki

    0
  • A

    erstmal sorry dass der post im falschen forum war, aber bei "rund um die.."
    steht:
    Rund um die Programmierung
    Alles zum Thema programmieren: verschiedene Programmiersprachen, Librarys, [b] Algorithmen und Dinge zum Studium und Ausbildung.
    ---
    das mein zeug nicht wirklich sinn macht ist mir auch aufgefallen, keine ahnung was ich da gebastelt habe 🙄
    so wie ich den bresenham verstanden habe, funktioniert er nur von 0° - 45°, aber dass kann man doch durch spiegel beheben.
    waagrechte/senkrechten linien kann man ja als sonderfall behandeln.

    frage:
    kennt jemand eine gute erklärung für bresenham oder einen ähnlichen algo.?
    mfg
    abn

    0
  • ?

    Hier ist der Code aus Zerbies ersten Bands (hoffe, er hat nichts dagegen):

    BOOL Male_Linie(int sx, int sy, int ex, int ey, UCHAR Farbe,LPDIRECTDRAWSURFACE7 lpDDSurf)
   {
   int            Zeilenbreite;     // Zeilenbreite
   int            DDS_Breite;       // Breite der Surface
   int            DDS_Hoehe;        // Höhe der Surface
   int            x_wert, y_wert;   // Änderungen in x und y
   int            x_diff, y_diff;   // Differenzen x und y
   int            offset;           
   int            Fehler;
   int            Laenge;
   UCHAR          *Vram;            // Speicheradresse der Surface
   DDSURFACEDESC2 ddsd;             // SurfaceDesv Struktur

   ZeroMemory(&ddsd, sizeof(ddsd));
   ddsd.dwSize = sizeof(ddsd);

   lpDDSurf->Lock(NULL, &ddsd, DDLOCK_SURFACEMEMORYPTR |
                  DDLOCK_WAIT, NULL);
      Zeilenbreite = ddsd.lPitch;
      DDS_Breite   = ddsd.dwWidth;
      DDS_Hoehe    = ddsd.dwHeight;
      Vram = (UCHAR *)ddsd.lpSurface;

      // I N I T I A L I S I E R U N G E N /////////////////////////
      offset = sy*Zeilenbreite+sx;  // Startadresse im Video RAM
      y_diff = ey - sy;             // Höhe der Linie
      x_diff = ex - sx;             // Breite der Linie
      Fehler = 0;                   // Bresenhams Fehlervariable

      if (y_diff<0) {
         y_diff = -y_diff;          // Absolutbetrag der Höhe
         y_wert = -Zeilenbreite;    // y läuft von unten nach oben
         }
      else y_wert = Zeilenbreite;   // y läuft von oben nach unten

      if (x_diff<0) {
         x_diff = -x_diff;          // Absolutbetrag der Breite
         x_wert = -1;               // x läfut von rechts nach links
         }
      else x_wert = 1;              // x läfut von links nach rechts

      // B R E S E N H A M ' S   L I N I E  ////////////////////////
      if (x_diff > y_diff) {        // Steigung < 1
         Laenge = x_diff + 1;       // Schleife über x Koordinate
         for (int i=0; i < Laenge; i++) {
            Vram[offset] = Farbe;   // Pixel malen
            offset += x_wert;       // x Koordinate verschieben
            Fehler += y_diff;       // Bresenham Fehler anpassen
            if (Fehler > x_diff) {
               Fehler -= x_diff;    // Fehler neu ansetzen
               offset += y_wert;    // y Koordinate verschieben
               } // if
            } // for
         } // if
      else {                        // Steigung < 1
         Laenge = y_diff + 1;       // Schleife über y Koordinate
         for (int i=0; i<Laenge; i++) {
            Vram[offset] = Farbe;   // Pixel malen
            offset += y_wert;       // y Koordinate verschieben
            Fehler += x_diff;       // Bresenham Fehler anpassen
            if (Fehler > 0) {
               Fehler -= y_diff;    // Fehler neu ansetzen
               offset += x_wert;    // x Koordinate verschieben
               } // if
            } // for
         } // else

   lpDDSurf->Unlock(NULL);
   return TRUE;
   } // Male_Linie
    0
  • A

    @<Florianx>
    danke! ich hatte zwar mehr noch einer erklärung und keinem code gefragt aber ich
    werds mir mal ansehen.

    0
  • S

    Hi,
    http://www.uni-paderborn.de/fachbereich/AG/agdomik/computergrafik/cg_skript/html/node34.htm

    Ciao,
    Stefan

    0
Anmelden zum Antworten