Bresenham Algorithmus
-
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