1/**
2 * Draws a line between two points p1(p1x,p1y) and p2(p2x,p2y).
3 * This function is based on the Bresenham's line algorithm and is highly 
4 * optimized to be able to draw lines very quickly. There is no floating point 
5 * arithmetic nor multiplications and divisions involved. Only addition, 
6 * subtraction and bit shifting are used. 
7 *
8 * Note that you have to define your own customized setPixel(x,y) function, 
9 * which essentially lights a pixel on the screen.
10 */
11void lineBresenham(int p1x, int p1y, int p2x, int p2y)
12{
13    int F, x, y;
14
15    if (p1x > p2x)  // Swap points if p1 is on the right of p2
16    {
17        swap(p1x, p2x);
18        swap(p1y, p2y);
19    }
20
21    // Handle trivial cases separately for algorithm speed up.
22    // Trivial case 1: m = +/-INF (Vertical line)
23    if (p1x == p2x)
24    {
25        if (p1y > p2y)  // Swap y-coordinates if p1 is above p2
26        {
27            swap(p1y, p2y);
28        }
29
30        x = p1x;
31        y = p1y;
32        while (y <= p2y)
33        {
34            setPixel(x, y);
35            y++;
36        }
37        return;
38    }
39    // Trivial case 2: m = 0 (Horizontal line)
40    else if (p1y == p2y)
41    {
42        x = p1x;
43        y = p1y;
44
45        while (x <= p2x)
46        {
47            setPixel(x, y);
48            x++;
49        }
50        return;
51    }
52
53
54    int dy            = p2y - p1y;  // y-increment from p1 to p2
55    int dx            = p2x - p1x;  // x-increment from p1 to p2
56    int dy2           = (dy << 1);  // dy << 1 == 2*dy
57    int dx2           = (dx << 1);
58    int dy2_minus_dx2 = dy2 - dx2;  // precompute constant for speed up
59    int dy2_plus_dx2  = dy2 + dx2;
60
61
62    if (dy >= 0)    // m >= 0
63    {
64        // Case 1: 0 <= m <= 1 (Original case)
65        if (dy <= dx)   
66        {
67            F = dy2 - dx;    // initial F
68
69            x = p1x;
70            y = p1y;
71            while (x <= p2x)
72            {
73                setPixel(x, y);
74                if (F <= 0)
75                {
76                    F += dy2;
77                }
78                else
79                {
80                    y++;
81                    F += dy2_minus_dx2;
82                }
83                x++;
84            }
85        }
86        // Case 2: 1 < m < INF (Mirror about y=x line
87        // replace all dy by dx and dx by dy)
88        else
89        {
90            F = dx2 - dy;    // initial F
91
92            y = p1y;
93            x = p1x;
94            while (y <= p2y)
95            {
96                setPixel(x, y);
97                if (F <= 0)
98                {
99                    F += dx2;
100                }
101                else
102                {
103                    x++;
104                    F -= dy2_minus_dx2;
105                }
106                y++;
107            }
108        }
109    }
110    else    // m < 0
111    {
112        // Case 3: -1 <= m < 0 (Mirror about x-axis, replace all dy by -dy)
113        if (dx >= -dy)
114        {
115            F = -dy2 - dx;    // initial F
116
117            x = p1x;
118            y = p1y;
119            while (x <= p2x)
120            {
121                setPixel(x, y);
122                if (F <= 0)
123                {
124                    F -= dy2;
125                }
126                else
127                {
128                    y--;
129                    F -= dy2_plus_dx2;
130                }
131                x++;
132            }
133        }
134        // Case 4: -INF < m < -1 (Mirror about x-axis and mirror 
135        // about y=x line, replace all dx by -dy and dy by dx)
136        else    
137        {
138            F = dx2 + dy;    // initial F
139
140            y = p1y;
141            x = p1x;
142            while (y >= p2y)
143            {
144                setPixel(x, y);
145                if (F <= 0)
146                {
147                    F += dx2;
148                }
149                else
150                {
151                    x++;
152                    F += dy2_plus_dx2;
153                }
154                y--;
155            }
156        }
157    }
158}

// Snippet of a sample program in OpenGL

void setPixel(int px, int py)
{
    glBegin(GL_POINTS);
        glVertex2i(px, py);
    glEnd();
}

void display()
{
    glClear(GL_COLOR_BUFFER_BIT);

    // Draws a line from (100,100) to (400,300).
    lineBresenham(100, 100, 400, 300);

    glFlush();
}