Bresenham Algorithmus
-
hi,
ich habe hier den Bresenham Algorithmus mit einer liste verbunden
jedoch funktionieren die Sonderfälle nicht richtig d.h. er zeichnet nicht von
oben nach unten und nicht von rechts nach links ich kann den Fehler einfach nicht finden.void polygon_zeichnen(Monitor *m, ELEMENT *liste){ int y,x,int_fehler, delta, schritt, dx, dy, inc_x, inc_y; ELEMENT *hz=liste; ELEMENT *hz2=liste->next; Punkt punkt; if(hz!=NULL && hz2!=NULL){ while(hz2!=NULL){ x = hz->inhalt.x; // Koordinaten retten y = hz->inhalt.y; dy= hz2->inhalt.y-hz->inhalt.y;// Hoehenzuwachs berechnen dx= hz2->inhalt.x-hz->inhalt.x;// Schrittweite if(dx > 0) // Linie nach rechts? inc_x = 1; // x inkrementieren else // Linie nach links inc_x = -1; // x dekrementieren if(dy > 0) // Linie nach unten? inc_y = 1; // y inkrementieren else // Linie nach oben inc_y = -1; // y dekrementieren if(dy < dx) { // flach nach oben oder unten int_fehler = -dx; // Fehler bestimmen delta = 2*dy; // Delta bestimmen schritt = 2*int_fehler; // Schwelle bestimmen while(x != hz2->inhalt.x) { // Fuer jede x-Koordinate punkt.x=x; punkt.y=y; punkt_setzen(punkt,m); // setze Pixel x=x + inc_x; // naechste x-Koordinate int_fehler = int_fehler + delta; // Fehler aktualisieren if (int_fehler > 0) { // neue Spalte erreicht? y=y+inc_y; // y-Koord. aktualisieren int_fehler=int_fehler + schritt; // Fehler aktualisieren } } } else { // steil nach oben oder unten int_fehler = -dy; // Fehler bestimmen delta = 2*dx; // Delta bestimmen schritt = 2*int_fehler; // Schwelle bestimmen while(y != hz2->inhalt.y) { // fuer jede y-Koordinate punkt.x=x; punkt.y=y; punkt_setzen(punkt,m); // setze Pixel y=y + inc_y; // naechste y-Koordinate int_fehler = int_fehler + delta; // Fehler aktualisieren if (int_fehler > 0) { // neue Zeile erreicht? x += inc_x; // x-Koord. aktualisieren int_fehler=int_fehler + schritt; // Fehler aktualisieren } } } punkt.x=hz2->inhalt.x; punkt.y=hz2->inhalt.y; punkt_setzen(punkt,m); // setze Pixel hz=hz->next; hz2=hz2->next; }}}
-
oO
-
indent hat geschrieben:
void polygon_zeichnen(Monitor * m, ELEMENT * liste) { int y, x, int_fehler, delta, schritt, dx, dy, inc_x, inc_y; ELEMENT *hz = liste; ELEMENT *hz2 = liste->next; Punkt punkt; if (hz != NULL && hz2 != NULL) { while (hz2 != NULL) { x = hz->inhalt.x; // Koordinaten retten y = hz->inhalt.y; dy = hz2->inhalt.y - hz->inhalt.y; // Hoehenzuwachs berechnen dx = hz2->inhalt.x - hz->inhalt.x; // Schrittweite if (dx > 0) // Linie nach rechts? inc_x = 1; // x inkrementieren else // Linie nach links inc_x = -1; // x dekrementieren if (dy > 0) // Linie nach unten? inc_y = 1; // y inkrementieren else // Linie nach oben inc_y = -1; // y dekrementieren if (dy < dx) { // flach nach oben oder unten int_fehler = -dx; // Fehler bestimmen delta = 2 * dy; // Delta bestimmen schritt = 2 * int_fehler; // Schwelle bestimmen while (x != hz2->inhalt.x) { // Fuer jede x-Koordinate punkt.x = x; punkt.y = y; punkt_setzen(punkt, m); // setze Pixel x = x + inc_x; // naechste x-Koordinate int_fehler = int_fehler + delta; // Fehler aktualisieren if (int_fehler > 0) { // neue Spalte erreicht? y = y + inc_y; // y-Koord. aktualisieren int_fehler = int_fehler + schritt; // Fehler aktualisieren } } } else { // steil nach oben oder unten int_fehler = -dy; // Fehler bestimmen delta = 2 * dx; // Delta bestimmen schritt = 2 * int_fehler; // Schwelle bestimmen while (y != hz2->inhalt.y) { // fuer jede y-Koordinate punkt.x = x; punkt.y = y; punkt_setzen(punkt, m); // setze Pixel y = y + inc_y; // naechste y-Koordinate int_fehler = int_fehler + delta; // Fehler aktualisieren if (int_fehler > 0) { // neue Zeile erreicht? x += inc_x; // x-Koord. aktualisieren int_fehler = int_fehler + schritt; // Fehler aktualisieren } } } punkt.x = hz2->inhalt.x; punkt.y = hz2->inhalt.y; punkt_setzen(punkt, m); // setze Pixel hz = hz->next; hz2 = hz2->next; } } }dein code mag schneller sein (wenn er liefe), aber ich wuerde die redundanzen entfernen. dann siehts wenigstens sauberer aus.
-
Hi. Wenn du willst, kannst du das mal mit meiner Realisierung dieses Algorithmus vergleichen. Vielleicht kannst du so den Fehler finden.
(Die ist allerdings auf n Dimensionen verallgemeinert, so dass ich nicht jeden Quadranten separat behandeln konnte. Im Prinzip sollte es aber das gleiche sein.)
public float castLine(final Vector startPoint, final Vector endPoint) { // Check parameters. if (startPoint.getDimension() != dimension) throw new IllegalArgumentException("startPoint has wrong dimension."); if (endPoint.getDimension() != dimension) throw new IllegalArgumentException("endPoint has wrong dimension."); // Clip line: // Resulting line is given by rasterStartPoint and rasterEndPoint. final int[] rasterStartPoint = new int[dimension]; final int[] rasterEndPoint = new int[dimension]; if(!setFirstPointInRaster(rasterStartPoint,startPoint,endPoint)) return 0.0f; if(!setFirstPointInRaster(rasterEndPoint,endPoint,startPoint)) return 0.0f; // Init helper variables. int maxDiffIndex = 0; final int[] intDifferences = new int[dimension]; final int[] relativePosition = new int[dimension]; final int[] position = new int[dimension]; final int[] increments = new int[dimension]; for(int i = 0 ; i < dimension ; ++i) { intDifferences[i] = rasterEndPoint[i] - rasterStartPoint[i]; increments[i] = (intDifferences[i] > 0) ? 1 : -1; intDifferences[i] = Math.abs(intDifferences[i]); if (intDifferences[i] > intDifferences[maxDiffIndex]) maxDiffIndex = i; relativePosition[i] = intDifferences[i] >> 1; position[i] = rasterStartPoint[i]; } final int maxDifference = intDifferences[maxDiffIndex]; final int maxIncrement = increments[maxDiffIndex]; // Process line: // 1. Reset pointProcessor. // 2. Process Bresenham-Line-Algorithm // 3. Return value of pointProcessor pointProcessor.reset(); for(;position[maxDiffIndex] != rasterEndPoint[maxDiffIndex] ; position[maxDiffIndex] += maxIncrement) { if (pointProcessor.addPoint(raster,position)) break; for(int i = 0 ; i < dimension ; ++i) { if (i == maxDiffIndex) continue; relativePosition[i] += intDifferences[i]; if (relativePosition[i] < maxDifference) continue; position[i] += increments[i]; relativePosition[i] -= maxDifference; } } pointProcessor.addPoint(raster,position); return pointProcessor.getValue(); }
-
Aber was ist denn das Problem ich habe meinen code genau nach dem Bresenham Code Aufgebaut und mit der Liste verbunden ich sehe jetzt keine logischen fehler darin
@gregor:ok danke werds versuchen
-
blizzarac: Naja, ich habe mich längere Zeit nicht mehr mit diesem Algorithmus befasst. Insofern weiß ich nicht, ob folgendes tatsächlich ein Fehler ist, aber überleg dir mal folgendes:
Du hast da:
if(dy < dx) { // flach nach oben oder unten
Der Kommentar passt da zumindest nicht zur Abfrage. Überleg dir mal, was passiert, wenn dx oder dy negativ sind, z.B. dy -10000 und dx = -5. Dann hat die Gerade nicht so eine Steigung, wie sie dein Kommentar wohl beschreiben soll. Du müßtest da wohl eher Absolutbeträge vergleichen.
-
was macht denn die funktion math.abs? und wie setze ich sie in c um?
-
Da gibt es sicherlich entsprechende Funktionen in der Standardbibliothek. Aber da ich mich da nicht auskenne...
int abs(int x)
{
if (x < 0) x = -x;
return x;
}...oder auch in einer einfacheren Variante.
-
jo danke das ist hilfreich da wir sowieso keine befehle benutzen dürfen die wir noch nicht in der vorlesung hatten
-
hmm jetzt bricht das programm bei sonderfällen ab..
void polygon_zeichnen(Monitor * m, ELEMENT * liste) { int y, x, int_fehler, delta, schritt, dx, dy, inc_x, inc_y; ELEMENT *hz = liste; ELEMENT *hz2 = liste->next; Punkt punkt; if (hz != NULL && hz2 != NULL) { while (hz2 != NULL) { x = hz->inhalt.x; // Koordinaten retten y = hz->inhalt.y; dy = hz2->inhalt.y - hz->inhalt.y; // Hoehenzuwachs berechnen dx = hz2->inhalt.x - hz->inhalt.x; // Schrittweite if (dx > 0) // Linie nach rechts? inc_x = 1; // x inkrementieren else // Linie nach links inc_x = -1; // x dekrementieren if (dy > 0) // Linie nach unten? inc_y = 1; // y inkrementieren else // Linie nach oben inc_y = -1; // y dekrementieren if (abs(dy) < abs(dx)) { // flach nach oben oder unten int_fehler = - abs(dx); // Fehler bestimmen delta = 2 * abs(dy); // Delta bestimmen schritt = 2 * int_fehler; // Schwelle bestimmen while (x != hz2->inhalt.x) { // Fuer jede x-Koordinate punkt.x = x; punkt.y = y; punkt_setzen(punkt, m); // setze Pixel x = x + inc_x; // naechste x-Koordinate int_fehler = int_fehler + delta; // Fehler aktualisieren if (int_fehler > 0) { // neue Spalte erreicht? y = y + inc_y; // y-Koord. aktualisieren int_fehler = int_fehler + schritt; // Fehler aktualisieren } } } else { // steil nach oben oder unten int_fehler = -abs(dy); // Fehler bestimmen delta = 2 * abs(dx); // Delta bestimmen schritt = 2 * int_fehler; // Schwelle bestimmen while (y != hz2->inhalt.y) { // fuer jede y-Koordinate punkt.x = x; punkt.y = y; punkt_setzen(punkt, m); // setze Pixel y = y + inc_y; // naechste y-Koordinate int_fehler = int_fehler + delta; // Fehler aktualisieren if (int_fehler > 0) { // neue Zeile erreicht? x += inc_x; // x-Koord. aktualisieren int_fehler = int_fehler + schritt; // Fehler aktualisieren } } } punkt.x = hz2->inhalt.x; punkt.y = hz2->inhalt.y; punkt_setzen(punkt, m); // setze Pixel hz = hz->next; hz2 = hz2->next; } } }
-
Nein hab mich geirrt es funktioniert jetzt danke für die hilfe
-
http://turing.fh-landshut.de/~jamann/Bresenham.pdf
http://turing.fh-landshut.de/~jamann/Bresenham die 2te.pdf