1 #define IMAGER_NO_CONTEXT
5 #define OVERLAPPED(start1, end1, start2, end2) \
6 (im_max((start1), (start2)) <= im_min((end1), (end2)))
11 hlines.c - implements a "class" for managing sets of horizontal line segments
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);
23 // work over the lines
24 for (y = hlines.start; y < hlines.limit; ++y) {
25 i_int_hline_entry *entry = hlines.entries[i];
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
35 i_int_hlines_destroy(&hlines);
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.
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
49 =item i_int_init_hlines
51 i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x)
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.
69 size_t bytes = count_y * sizeof(i_int_hline_entry *);
71 if (bytes / count_y != sizeof(i_int_hline_entry *)) {
73 im_fatal(aIMCTX, 3, "integer overflow calculating memory allocation\n");
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);
85 =item i_int_init_hlines_img
87 i_int_init_hlines_img(img);
89 Initialize a hlines object as if we could potentially draw anywhere on
96 i_int_init_hlines_img(i_int_hlines *hlines, i_img *img)
98 i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
102 =item i_int_hlines_add
104 i_int_hlines_add(hlines, y, x, width)
106 Add to the list, merging with existing entries.
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;
117 im_fatal(aIMCTX, 3, "negative width %d passed to i_int_hlines_add\n", width);
120 /* just return if out of range */
121 if (y < hlines->start_y || y >= hlines->limit_y)
124 if (x >= hlines->limit_x || x_limit < hlines->start_x)
127 /* adjust x to our range */
128 if (x < hlines->start_x)
130 if (x_limit > hlines->limit_x)
131 x_limit = hlines->limit_x;
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;
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)) {
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;
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);
156 /* look for other overlapping segments */
157 /* this could be a for(), but I'm using continue */
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)
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];
182 merge_seg->x_limit = x_limit;
185 i_int_hline_seg *seg;
186 /* add a new segment */
187 if (entry->count == entry->alloc) {
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;
195 seg = entry->segs + entry->count++;
197 seg->x_limit = x_limit;
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);
206 entry->segs[0].minx = x;
207 entry->segs[0].x_limit = x_limit;
208 hlines->entries[y - hlines->start_y] = entry;
213 =item i_int_hlines_destroy
215 i_int_hlines_destroy(&hlines)
217 Releases all memory associated with the structure.
223 i_int_hlines_destroy(i_int_hlines *hlines) {
224 size_t entry_count = hlines->limit_y - hlines->start_y;
227 for (i = 0; i < entry_count; ++i) {
228 if (hlines->entries[i])
229 myfree(hlines->entries[i]);
231 myfree(hlines->entries);
235 =item i_int_hlines_fill_color
237 i_int_hlines_fill(im, hlines, color)
239 Fill the areas given by hlines with color.
245 i_int_hlines_fill_color(i_img *im, i_int_hlines *hlines, const i_color *col) {
248 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
249 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
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);
262 =item i_int_hlines_fill_fill
264 i_int_hlines_fill_fill(im, hlines, fill)
269 i_int_hlines_fill_fill(i_img *im, i_int_hlines *hlines, i_fill_t *fill) {
273 i_render_init(&r, im, im->xsize);
275 for (y = hlines->start_y; y < hlines->limit_y; ++y) {
276 i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
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;
282 i_render_fill(&r, seg->minx, y, width, NULL, fill);
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;
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];
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;
303 i_glin(im, seg->minx, seg->x_limit, y, line);
304 (fill->fill_with_color)(fill, seg->minx, y, width,
306 (fill->combine)(line, work, im->channels, width);
309 (fill->fill_with_color)(fill, seg->minx, y, width,
312 i_plin(im, seg->minx, seg->x_limit, y, line);
322 i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
323 i_fcolor *work = NULL;
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];
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;
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,
337 (fill->combinef)(line, work, im->channels, width);
340 (fill->fill_with_fcolor)(fill, seg->minx, y, width,
343 i_plinf(im, seg->minx, seg->x_limit, y, line);
360 Tony Cook <tonyc@cpan.org>