Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 364 lines (295 sloc) 8.718 kb
92bda63 - start of external Imager API access:
Tony Cook authored
1 #include "imageri.h"
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
2 #include <stdlib.h>
3
4 #define OVERLAPPED(start1, end1, start2, end2) \
5 (im_max((start1), (start2)) <= im_min((end1), (end2)))
6
7 /*
8 =head1 NAME
9
10 hlines.c - implements a "class" for managing sets of horizontal line segments
11
12 =head1 SYNOPSIS
13
14 i_int_hlines hlines;
15 // just for the specified range of y
16 i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x);
17 // to cover a whole image
18 i_int_init_hlines_img(&hlines, img);
19 // add a hline segment, merging into existing
20 i_int_hlines_add(&hlines, y, x, width);
21
22 // work over the lines
23 for (y = hlines.start; y < hlines.limit; ++y) {
24 i_int_hline_entry *entry = hlines.entries[i];
25 if (entry) {
26 for (i = 0; i < entry->count; ++i) {
27 i_int_hline_seg *seg = entry->segs+i;
28 // do something on line y for seg->minx to x_limit
29 }
30 }
31 }
32
33 // free it all up
34 i_int_hlines_destroy(&hlines);
35
36 =head1 DESCRIPTION
37
38 Provides a class to manage sets of horizontal line segments. The
39 intent is that when drawing shapes where the algorithm used might
40 cause overlaps we can use this class to resolve the overlaps.
41
42 Note that segment lists are intended to remain small, if we end up
43 with a need for longer lists we should use different structure for the
44 segment lists.
45
46 =over
47
48 =item i_int_init_hlines
49
50 i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x)
51
52 Initializes the structure based on drawing an object within the given
53 range. Any x or y values outside the given ranges will be ignored.
54
55 =cut
56
57 */
58
59 void
60 i_int_init_hlines(
61 i_int_hlines *hlines,
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
62 i_img_dim start_y,
63 i_img_dim count_y,
64 i_img_dim start_x,
65 i_img_dim width_x
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
66 )
67 {
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
68 size_t bytes = count_y * sizeof(i_int_hline_entry *);
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
69
70 if (bytes / count_y != sizeof(i_int_hline_entry *)) {
d03fd5a @tonycoz revert threading changes, they aren't ready for the mainline yet
authored
71 i_fatal(3, "integer overflow calculating memory allocation\n");
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
72 }
73
74 hlines->start_y = start_y;
75 hlines->limit_y = start_y + count_y;
76 hlines->start_x = start_x;
77 hlines->limit_x = start_x + width_x;
78 hlines->entries = mymalloc(bytes);
79 memset(hlines->entries, 0, bytes);
80 }
81
82 /*
83 =item i_int_init_hlines_img
84
85 i_int_init_hlines_img(img);
86
87 Initialize a hlines object as if we could potentially draw anywhere on
88 the image.
89
90 =cut
91 */
92
93 void
94 i_int_init_hlines_img(i_int_hlines *hlines, i_img *img)
95 {
96 i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
97 }
98
99 /*
100 =item i_int_hlines_add
101
102 i_int_hlines_add(hlines, y, x, width)
103
104 Add to the list, merging with existing entries.
105
106 =cut
107 */
108
109 void
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
110 i_int_hlines_add(i_int_hlines *hlines, i_img_dim y, i_img_dim x, i_img_dim width) {
111 i_img_dim x_limit = x + width;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
112
113 if (width < 0) {
d03fd5a @tonycoz revert threading changes, they aren't ready for the mainline yet
authored
114 i_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
115 }
116
117 /* just return if out of range */
118 if (y < hlines->start_y || y >= hlines->limit_y)
119 return;
120
121 if (x >= hlines->limit_x || x_limit < hlines->start_x)
122 return;
123
124 /* adjust x to our range */
125 if (x < hlines->start_x)
126 x = hlines->start_x;
127 if (x_limit > hlines->limit_x)
128 x_limit = hlines->limit_x;
129
130 if (x == x_limit)
131 return;
132
133 if (hlines->entries[y - hlines->start_y]) {
134 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
135 i_img_dim i, found = -1;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
136
137 for (i = 0; i < entry->count; ++i) {
138 i_int_hline_seg *seg = entry->segs + i;
139 if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
140 found = i;
141 break;
142 }
143 }
144 if (found >= 0) {
145 /* ok, we found an overlapping segment, any other overlapping
146 segments need to be merged into the one we found */
147 i_int_hline_seg *merge_seg = entry->segs + found;
148
149 /* merge in the segment we found */
150 x = im_min(x, merge_seg->minx);
151 x_limit = im_max(x_limit, merge_seg->x_limit);
152
153 /* look for other overlapping segments */
154 /* this could be a for(), but I'm using continue */
155 i = found + 1;
156 while (i < entry->count) {
157 i_int_hline_seg *seg = entry->segs + i;
158 if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
159 /* merge this into the current working segment, then
160 delete it by moving the last segment (if this isn't it)
161 into it's place */
162 x = im_min(x, seg->minx);
163 x_limit = im_max(x_limit, seg->x_limit);
164 if (i < entry->count-1) {
165 *seg = entry->segs[entry->count-1];
166 --entry->count;
167 continue;
168 }
169 else {
170 --entry->count;
171 break;
172 }
173 }
174 ++i;
175 }
176
177 /* store it back */
178 merge_seg->minx = x;
179 merge_seg->x_limit = x_limit;
180 }
181 else {
182 i_int_hline_seg *seg;
183 /* add a new segment */
184 if (entry->count == entry->alloc) {
185 /* expand it */
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
186 size_t alloc = entry->alloc * 3 / 2;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
187 entry = myrealloc(entry, sizeof(i_int_hline_entry) +
188 sizeof(i_int_hline_seg) * (alloc - 1));
189 entry->alloc = alloc;
190 hlines->entries[y - hlines->start_y] = entry;
191 }
192 seg = entry->segs + entry->count++;
193 seg->minx = x;
194 seg->x_limit = x_limit;
195 }
196 }
197 else {
198 /* make a new one - start with space for 10 */
199 i_int_hline_entry *entry = mymalloc(sizeof(i_int_hline_entry) +
200 sizeof(i_int_hline_seg) * 9);
201 entry->alloc = 10;
202 entry->count = 1;
203 entry->segs[0].minx = x;
204 entry->segs[0].x_limit = x_limit;
205 hlines->entries[y - hlines->start_y] = entry;
206 }
207 }
208
209 /*
210 =item i_int_hlines_destroy
211
212 i_int_hlines_destroy(&hlines)
213
214 Releases all memory associated with the structure.
215
216 =cut
217 */
218
219 void
220 i_int_hlines_destroy(i_int_hlines *hlines) {
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
221 size_t entry_count = hlines->limit_y - hlines->start_y;
222 size_t i;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
223
224 for (i = 0; i < entry_count; ++i) {
225 if (hlines->entries[i])
226 myfree(hlines->entries[i]);
227 }
228 myfree(hlines->entries);
229 }
230
231 /*
232 =item i_int_hlines_fill_color
233
234 i_int_hlines_fill(im, hlines, color)
235
236 Fill the areas given by hlines with color.
237
238 =cut
239 */
240
241 void
97ac0a9 - constify the Imager API
Tony Cook authored
242 i_int_hlines_fill_color(i_img *im, i_int_hlines *hlines, const i_color *col) {
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
243 i_img_dim y, i, x;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
244
245 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
246 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
247 if (entry) {
248 for (i = 0; i < entry->count; ++i) {
249 i_int_hline_seg *seg = entry->segs + i;
250 for (x = seg->minx; x < seg->x_limit; ++x) {
251 i_ppix(im, x, y, col);
252 }
253 }
254 }
255 }
256 }
257
258 /*
259 =item i_int_hlines_fill_fill
260
261 i_int_hlines_fill_fill(im, hlines, fill)
262
263 */
264 void
265 i_int_hlines_fill_fill(i_img *im, i_int_hlines *hlines, i_fill_t *fill) {
9b1ec2b commit changes from draw branch
Tony Cook authored
266 i_render r;
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
267 i_img_dim y, i;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
268
9b1ec2b commit changes from draw branch
Tony Cook authored
269 i_render_init(&r, im, im->xsize);
270
271 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
272 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
273 if (entry) {
274 for (i = 0; i < entry->count; ++i) {
275 i_int_hline_seg *seg = entry->segs + i;
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
276 i_img_dim width = seg->x_limit-seg->minx;
9b1ec2b commit changes from draw branch
Tony Cook authored
277
278 i_render_fill(&r, seg->minx, y, width, NULL, fill);
279 }
280 }
281 }
282 i_render_done(&r);
283
284 #if 1
285 #else
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
286 if (im->bits == i_8_bits && fill->fill_with_color) {
287 i_color *line = mymalloc(sizeof(i_color) * im->xsize);
288 i_color *work = NULL;
289 if (fill->combine)
290 work = mymalloc(sizeof(i_color) * im->xsize);
291 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
292 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
293 if (entry) {
294 for (i = 0; i < entry->count; ++i) {
295 i_int_hline_seg *seg = entry->segs + i;
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
296 i_img_dim width = seg->x_limit-seg->minx;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
297
298 if (fill->combine) {
299 i_glin(im, seg->minx, seg->x_limit, y, line);
300 (fill->fill_with_color)(fill, seg->minx, y, width,
301 im->channels, work);
302 (fill->combine)(line, work, im->channels, width);
303 }
304 else {
305 (fill->fill_with_color)(fill, seg->minx, y, width,
306 im->channels, line);
307 }
308 i_plin(im, seg->minx, seg->x_limit, y, line);
309 }
310 }
311 }
312
313 myfree(line);
314 if (work)
315 myfree(work);
316 }
317 else {
318 i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
319 i_fcolor *work = NULL;
320 if (fill->combinef)
321 work = mymalloc(sizeof(i_fcolor) * im->xsize);
322 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
323 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
324 if (entry) {
325 for (i = 0; i < entry->count; ++i) {
326 i_int_hline_seg *seg = entry->segs + i;
8d14daa @tonycoz switch to using size_t and i_img_dim strictly
authored
327 i_img_dim width = seg->x_limit-seg->minx;
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
328
329 if (fill->combinef) {
330 i_glinf(im, seg->minx, seg->x_limit, y, line);
331 (fill->fill_with_fcolor)(fill, seg->minx, y, width,
332 im->channels, work);
333 (fill->combinef)(line, work, im->channels, width);
334 }
335 else {
336 (fill->fill_with_fcolor)(fill, seg->minx, y, width,
337 im->channels, line);
338 }
339 i_plinf(im, seg->minx, seg->x_limit, y, line);
340 }
341 }
342 }
343
344 myfree(line);
345 if (work)
346 myfree(work);
347 }
9b1ec2b commit changes from draw branch
Tony Cook authored
348 #endif
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
349 }
350
351 /*
352 =back
353
354 =head1 AUTHOR
355
5b480b1 @tonycoz replace (imager|tony)@imager.perl.org with tonyc@cpan.org
authored
356 Tony Cook <tonyc@cpan.org>
39f9403 - arc(..., fill=> ...) wasn't handling concave areas correctly
Tony Cook authored
357
358 =head1 REVISION
359
360 $Revision$
361
362 =cut
363 */
Something went wrong with that request. Please try again.