1 /*
2 Copyright (c) 1991 - 1994 Heinz W. Werntges. All rights reserved.
3 Distributed by Free Software Foundation, Inc.
4
5 This file is part of HP2xx.
6
7 HP2xx is distributed in the hope that it will be useful, but
8 WITHOUT ANY WARRANTY. No author or distributor accepts responsibility
9 to anyone for the consequences of using it or for whether it serves any
10 particular purpose or works at all, unless he says so in writing. Refer
11 to the GNU General Public License, Version 2 or later, for full details.
12
13 Everyone is granted permission to copy, modify and redistribute
14 HP2xx, but only under the conditions described in the GNU General Public
15 License. A copy of this license is supposed to have been
16 given to you along with HP2xx so you can know your rights and
17 responsibilities. It should be in a file named COPYING. Among other
18 things, the copyright notice and this notice must be preserved on all
19 copies.
20
21 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
22 */
23
24 /** bresnham.c: Implementation of Bresenham's algorithm
25 **
26 ** 1991/01/04 V 1.00 HWW Due to pseudocode in D.F. Rogers (1986) McGraw Hill
27 ** 1991/10/15 V 1.01 HWW ANSI_C
28 ** 2002/04/28 V 1.02 AJB Move static vars into struct
29 **/
30
31 #define TEST 0
32
33
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include "bresnham.h"
38
39 static struct {
40 DevPt p_act;
41 int dx, dy, s1, s2, swapdir, err, count;
42 } bres;
43
bresenham_init(DevPt * pp1,DevPt * pp2)44 DevPt *bresenham_init(DevPt * pp1, DevPt * pp2)
45 /**
46 ** Init. generation of a straight line between *pp1 & *pp2
47 **
48 ** Returns pointer to internally generated actual point of line.
49 ** Use this ptr for further reference! Example of use:
50 **
51 ** ..
52 ** #include <share/bresnham.h>
53 ** ...
54 ** DevPt p1, p2, *pp;
55 ** ...
56 ** pp = bresenham_init (&p1, &p2);
57 ** do {
58 ** plot (pp);
59 ** } while (bresenham_next() != BRESENHAM_ERR);
60 **/
61 {
62 bres.p_act = *pp1;
63
64 if ((bres.dx = pp2->x - pp1->x) != 0) {
65 if (bres.dx < 0) {
66 bres.dx = -bres.dx;
67 bres.s1 = -1;
68 } else
69 bres.s1 = 1;
70 } else
71 bres.s1 = 0; /* dx = abs(x2-x1), s1 = sign(x2-x1) */
72
73 if ((bres.dy = pp2->y - pp1->y) != 0) {
74 if (bres.dy < 0) {
75 bres.dy = -bres.dy;
76 bres.s2 = -1;
77 } else
78 bres.s2 = 1;
79 } else
80 bres.s2 = 0; /* dy = abs(y2-y1), s2 = sign(y2-y1) */
81
82 if (bres.dy > bres.dx) {
83 bres.swapdir = bres.dx; /* use swapdir as temp. var. */
84 bres.dx = bres.dy;
85 bres.dy = bres.swapdir;
86 bres.swapdir = 1;
87 } else
88 bres.swapdir = 0;
89
90 bres.count = bres.dx; /* Init. of loop cnt */
91 bres.dy <<= 1;
92 bres.err = bres.dy - bres.dx; /* Init. of error term */
93 bres.dx <<= 1;
94
95 return &bres.p_act;
96 }
97
98
99
bresenham_next(void)100 int bresenham_next(void)
101 /**
102 ** Move actual point to next position (if possible)
103 **
104 ** Returns 0 if ok,
105 ** BRESENHAM_EOL if last point reached (p_act == *pp2),
106 ** BRESENHAM_ERR else (e.g. if moving past EOL attempted)
107 **/
108 {
109 if (bres.count <= 0)
110 return (BRESENHAM_ERR); /* Beyond last point! */
111
112 while (bres.err >= 0) {
113 if (bres.swapdir)
114 bres.p_act.x += bres.s1;
115 else
116 bres.p_act.y += bres.s2;
117 bres.err -= bres.dx;
118 }
119 if (bres.swapdir)
120 bres.p_act.y += bres.s2;
121 else
122 bres.p_act.x += bres.s1;
123 bres.err += bres.dy;
124
125 bres.count--; /* i==0 indicates "last point reached" */
126 return ((bres.count) ? 0 : BRESENHAM_EOL);
127 }
128
129 /* Test module */
130 #if TEST
131 #ifdef __TURBOC__ && __MSDOS__
132
133
134 #include <graphics.h>
135
136
b_line(DevPt * pp1,DevPt * pp2,int col)137 void b_line(DevPt * pp1, DevPt * pp2, int col)
138 {
139 DevPt *pp;
140
141 pp = bresenham_init(pp1, pp2);
142 do {
143 putpixel(pp->x, pp->y, col);
144 } while (bresenham_next() != BRESENHAM_ERR);
145 }
146
147
main(void)148 void main(void)
149 {
150 int gdriver = DETECT, gmode, MaxX, MaxY;
151 DevPt pa, pc;
152
153 initgraph(&gdriver, &gmode, "");
154
155 MaxX = getmaxx();
156 MaxY = getmaxy();
157
158 pc.x = (MaxX + 1) >> 1;
159 pc.y = (MaxY + 1) >> 1;
160
161 for (pa.x = 0, pa.y = 0; pa.x < MaxX; pa.x += 4)
162 b_line(&pc, &pa, RED);
163 for (pa.x = MaxX, pa.y = 0; pa.y < MaxY; pa.y += 3)
164 b_line(&pc, &pa, GREEN);
165
166 for (pa.x = MaxX, pa.y = MaxY; pa.x >= 0; pa.x -= 4)
167 b_line(&pc, &pa, LIGHTRED);
168 for (pa.x = 0, pa.y = MaxY; pa.y >= 0; pa.y -= 3)
169 b_line(&pc, &pa, LIGHTGREEN);
170
171 getchar();
172 }
173
174 #endif
175 #endif
176