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