Forum: Mikrocontroller und Digitale Elektronik Problem mit Bresenham


von Sascha K. (Gast)


Lesenswert?

Hallo Leute,

ich habe ein Problem mit dem Bresenham.
Für eine 2D-Steuerung will ich eine gerasterte Linie mit 2 Motoren 
abfahren.

Hier mein Code:
1
#include "bresenham.h"
2
#include <math.h>
3
4
//Linen zeichnen nach dem Bresenham-Algorithmus
5
void Swap(uint16_t *i1, uint16_t *i2)
6
{
7
uint16_t dummy;
8
9
dummy = *i2;
10
*i2 = *i1;
11
*i1 = dummy;
12
}
13
14
inline void Bresenham(uint16_t x1, uint16_t y1, uint16_t x2, uint16_t y2)
15
{
16
int16_t d, dx, dy, aincr, bincr, xincr, yincr, x, y;
17
18
if ( labs(x2-x1) < labs(y2-y1) )
19
{
20
 if ( y1 > y2 )
21
 {
22
  Swap( &x1, &x2 );
23
  Swap( &y1, &y2 );
24
 }
25
 xincr = ( x2 > x1 ) ? 1 : -1;
26
 dy = y2 - y1;
27
 dx = labs( x2-x1 );
28
 d = 2 * dx - dy;
29
 aincr = 2 * (dx - dy);
30
 bincr = 2 * dx;
31
 x = x1;
32
 y = y1;
33
34
 putpixel( x, y );
35
 for (y=y1+1; y<= y2; ++y )
36
 {
37
  if ( d >= 0 )
38
  {
39
   x += xincr;
40
   d += aincr;
41
  }
42
  else d += bincr;
43
  putpixel( x, y );
44
 }
45
}
46
else
47
{
48
 if ( x1 > x2 )
49
 {
50
  Swap( &x1, &x2 );
51
  Swap( &y1, &y2 );
52
 }
53
 yincr = ( y2 > y1 ) ? 1 : -1;
54
 dx = x2 - x1;
55
 dy = labs( y2-y1 );
56
 d = 2 * dy - dx;
57
 aincr = 2 * (dy - dx);
58
 bincr = 2 * dy;
59
 x = x1;
60
 y = y1;
61
 
62
 putpixel( x, y );
63
 for (x=x1+1; x<=x2; ++x )
64
 {
65
  if ( d >= 0 )
66
  {
67
   y += yincr;
68
   d += aincr;
69
  }
70
  else d += bincr;
71
  putpixel( x, y );
72
 }
73
}
74
}

Läuft auch ganz gut, wenn ich die Funktion mit (0,0,50,15) aufrufe - die 
Funktion tut was sie soll. Wenn ich nun von 50,15 (=>x1,y1) aus in 
positive Richtung (=>Größere Werte) fahre, wird dies auch getan (z.B. 
(50,15,51,25)).

Sobald ich in negative Richtung fahren will - und selbst wenn's nur ein 
Schritt ist - wird zuerst zu 0,0 gefahren und dann von dort aus zu der 
Position - nur woran liegts?

In putpixel gebe ich die Parameter per RS232 aus. Daher konnte ich 
erkennen, dass die Funktion putpixel(0,0) aufgerufen wird.

Könnt ihr mir helfen? Ich habe inzwischen locker 5 
Bresenham-Implementationen ausprobiert - und alle haben andere Probleme 
:-(
Die Codebeispiele von Wikipedia (en) habe ich auch schon durch :(

Vielen Dank für eure Hilfe,
Sascha

von Kai G. (runtimeterror)


Lesenswert?

Hi Sascha,

bist du da noch dran?

Welche "Negative" Richtung geht denn nicht? Es gibt 6 verschiedene (A - 
F):
1
\         |         /
2
  \   C   |  B    /
3
    \     |     /
4
  D   \   |   /   A
5
        \ | /
6
----------+----------> +X
7
        / | \
8
  E   /   |   \   H
9
    /     |     \
10
  /   F   |   G   \
11
/         V         \
12
           +Y

Beispiele für die Bereiche:
A (50, 50)->(70, 40)
B (50, 50)->(60, 30)
C (50, 50)->(40, 30)
D (50, 50)->(30, 40)
E (50, 50)->(30, 60)
F (50, 50)->(40, 70)
G (50, 50)->(60, 70)
H (50, 50)->(70, 60)

Die funktionierenden Linie
(0,0,50,15) liegt in Bereich H
bzw.
(50,15,51,25) in Bereich G

Je nachdem welche Richtungen nicht gehen, kann man sehr leicht 
eingrenzen welche Bedingungen oder Vorzeichen nciht stimmen.

Gruß

Kai

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.