1 /* edge.c: operations on edges in bitmaps.
2 *
3 * Copyright (C) 1992 Free Software Foundation, Inc.
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3, or (at your option)
8 * any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>.
17 */
18
19 #include "config.h"
20
21 #include <assert.h>
22
23 #include "types.h"
24 #include "selection-to-path.h"
25 #include "edge.h"
26
27 /* We can move in any of eight directions as we are traversing
28 the outline. These numbers are not arbitrary; TRY_PIXEL depends on
29 them. */
30
31 typedef enum
32 {
33 north = 0, northwest = 1, west = 2, southwest = 3, south = 4,
34 southeast = 5, east = 6, northeast = 7
35 } direction_type;
36
37
38 static boolean is_marked_edge (edge_type, unsigned, unsigned, bitmap_type);
39 static boolean is_outline_edge (edge_type, unsigned, unsigned);
40 static edge_type next_edge (edge_type);
41
42 /* The following macros are used (directly or indirectly) by the
43 `next_outline_edge' routine. */
44
45 /* Given the direction DIR of the pixel to test, decide which edge on
46 that pixel we are supposed to test. Because we've chosen the mapping
47 from directions to numbers carefully, we don't have to do much. */
48
49 #define FIND_TEST_EDGE(dir) ((dir) / 2)
50
51
52 /* Find how to move in direction DIR on the axis AXIS (either `ROW' or
53 `COL'). We are in the ``display'' coordinate system, with y
54 increasing downward and x increasing to the right. Therefore, we are
55 implementing the following table:
56
57 direction row delta col delta
58 north -1 0
59 south +1 0
60 east 0 +1
61 west 0 +1
62
63 with the other four directions (e.g., northwest) being the sum of
64 their components (e.g., north + west).
65
66 The first macro, `COMPUTE_DELTA', handles splitting up the latter
67 cases, all of which have been assigned odd numbers. */
68
69 #define COMPUTE_DELTA(axis, dir) \
70 ((dir) % 2 != 0 \
71 ? COMPUTE_##axis##_DELTA ((dir) - 1) \
72 + COMPUTE_##axis##_DELTA (((dir) + 1) % 8) \
73 : COMPUTE_##axis##_DELTA (dir) \
74 )
75
76 /* Now it is trivial to implement the four cardinal directions. */
77 #define COMPUTE_ROW_DELTA(dir) \
78 ((dir) == north ? -1 : (dir) == south ? +1 : 0)
79
80 #define COMPUTE_COL_DELTA(dir) \
81 ((dir) == west ? -1 : (dir) == east ? +1 : 0)
82
83
84 /* See if the appropriate edge on the pixel from (row,col) in direction
85 DIR is on the outline. If so, update `row', `col', and `edge', and
86 break. We also use the variable `character' as the bitmap in which
87 to look. */
88
89 #define TRY_PIXEL(dir) \
90 { \
91 int delta_r = COMPUTE_DELTA (ROW, dir); \
92 int delta_c = COMPUTE_DELTA (COL, dir); \
93 int test_row = *row + delta_r; \
94 int test_col = *col + delta_c; \
95 edge_type test_edge = FIND_TEST_EDGE (dir); \
96 \
97 if (sel_valid_pixel(test_row, test_col) \
98 && is_outline_edge (test_edge, test_row, test_col)) \
99 { \
100 *row = test_row; \
101 *col = test_col; \
102 *edge = test_edge; \
103 break; \
104 } \
105 }
106
107 /* Finally, we are ready to implement the routine that finds the next
108 edge on the outline. We look first for an adjacent edge that is not
109 on the current pixel. We want to go around outside outlines
110 counterclockwise, and inside outlines clockwise (because that is how
111 both Metafont and Adobe Type 1 format want their curves to be drawn).
112
113 The very first outline (an outside one) on each character starts on a
114 top edge (STARTING_EDGE in edge.h defines this); so, if we're at a
115 top edge, we want to go only to the left (on the pixel to the west)
116 or down (on the same pixel), to begin with. Then, when we're on a
117 left edge, we want to go to the top edge (on the southwest pixel) or
118 to the left edge (on the south pixel).
119
120 All well and good. But if you draw a rasterized circle (or whatever),
121 eventually we have to come back around to the beginning; at that
122 point, we'll be on a top edge, and we'll have to go to the right edge
123 on the northwest pixel. Draw pictures.
124
125 The upshot is, if we find an edge on another pixel, we return (in ROW
126 and COL) the position of the new pixel, and (in EDGE) the kind of
127 edge it is. If we don't find such an edge, we return (in EDGE) the
128 next (in a counterclockwise direction) edge on the current pixel. */
129
130 void
next_outline_edge(edge_type * edge,unsigned * row,unsigned * col)131 next_outline_edge (edge_type *edge,
132 unsigned *row, unsigned *col)
133 {
134 unsigned original_row = *row;
135 unsigned original_col = *col;
136
137 switch (*edge)
138 {
139 case right:
140 TRY_PIXEL (north);
141 TRY_PIXEL (northeast);
142 break;
143
144 case top:
145 TRY_PIXEL (west);
146 TRY_PIXEL (northwest);
147 break;
148
149 case left:
150 TRY_PIXEL (south);
151 TRY_PIXEL (southwest);
152 break;
153
154 case bottom:
155 TRY_PIXEL (east);
156 TRY_PIXEL (southeast);
157 break;
158
159 default:
160 printf ("next_outline_edge: Bad edge value (%d)", *edge);
161
162 }
163
164 /* If we didn't find an adjacent edge on another pixel, return the
165 next edge on the current pixel. */
166 if (*row == original_row && *col == original_col)
167 *edge = next_edge (*edge);
168 }
169
170 /* We return the next edge on the pixel at position ROW and COL which is
171 an unmarked outline edge. By ``next'' we mean either the one sent in
172 in STARTING_EDGE, if it qualifies, or the next such returned by
173 `next_edge'. */
174
175 edge_type
next_unmarked_outline_edge(unsigned row,unsigned col,edge_type starting_edge,bitmap_type marked)176 next_unmarked_outline_edge (unsigned row, unsigned col,
177 edge_type starting_edge,
178 bitmap_type marked)
179 {
180 edge_type edge = starting_edge;
181
182 assert (edge != no_edge);
183
184 while (is_marked_edge (edge, row, col, marked)
185 || !is_outline_edge (edge, row, col))
186 {
187 edge = next_edge (edge);
188 if (edge == starting_edge)
189 return no_edge;
190 }
191
192 return edge;
193 }
194
195
196 /* We check to see if the edge EDGE of the pixel at position ROW and COL
197 is an outline edge; i.e., that it is a black pixel which shares that
198 edge with a white pixel. The position ROW and COL should be inside
199 the bitmap CHARACTER. */
200
201 static boolean
is_outline_edge(edge_type edge,unsigned row,unsigned col)202 is_outline_edge (edge_type edge,
203 unsigned row, unsigned col)
204 {
205 /* If this pixel isn't black, it's not part of the outline. */
206 if (sel_pixel_is_white(row, col))
207 return false;
208
209 switch (edge)
210 {
211 case left:
212 return col == 0 || sel_pixel_is_white(row, col - 1);
213
214 case top:
215 return row == 0 || sel_pixel_is_white(row - 1, col);
216
217 case right:
218 return (col == sel_get_width() - 1)
219 || sel_pixel_is_white(row, col + 1);
220
221 case bottom:
222 return (row == sel_get_height() - 1)
223 || sel_pixel_is_white(row + 1, col);
224
225 case no_edge:
226 default:
227 printf ("is_outline_edge: Bad edge value(%d)", edge);
228 }
229
230 return 0; /* NOTREACHED */
231 }
232
233 /* If EDGE is not already marked, we mark it; otherwise, it's a fatal error.
234 The position ROW and COL should be inside the bitmap MARKED. EDGE can
235 be `no_edge'; we just return false. */
236
237 void
mark_edge(edge_type edge,unsigned row,unsigned col,bitmap_type * marked)238 mark_edge (edge_type edge, unsigned row, unsigned col, bitmap_type *marked)
239 {
240 /* printf("row = %d, col = %d \n",row,col); */
241 assert (!is_marked_edge (edge, row, col, *marked));
242
243 if (edge != no_edge)
244 BITMAP_PIXEL (*marked, row, col) |= 1 << edge;
245 }
246
247
248 /* Test if the edge EDGE at ROW/COL in MARKED is marked. */
249
250 static boolean
is_marked_edge(edge_type edge,unsigned row,unsigned col,bitmap_type marked)251 is_marked_edge (edge_type edge, unsigned row, unsigned col, bitmap_type marked)
252 {
253 return
254 edge == no_edge ? false : BITMAP_PIXEL (marked, row, col) & (1 << edge);
255 }
256
257
258 /* Return the edge which is counterclockwise-adjacent to EDGE. This
259 code makes use of the ``numericness'' of C enumeration constants;
260 sorry about that. */
261
262 #define NUM_EDGES no_edge
263
264 static edge_type
next_edge(edge_type edge)265 next_edge (edge_type edge)
266 {
267 return edge == no_edge ? edge : (edge + 1) % NUM_EDGES;
268 }
269