hlines.c

   1 #include "imageri.h"
   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,
  62                   i_img_dim start_y,
  63                   i_img_dim count_y,
  64                   i_img_dim start_x,
  65                   i_img_dim width_x
  66                   )
  67 {
  68   size_t bytes = count_y * sizeof(i_int_hline_entry *);
  69
  70   if (bytes / count_y != sizeof(i_int_hline_entry *)) {
  71     i_fatal(3, "integer overflow calculating memory allocation\n");
  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
 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;
 112
 113   if (width < 0) {
 114     i_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
 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];
 135     i_img_dim i, found = -1;
 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 */
 186         size_t alloc = entry->alloc * 3 / 2;
 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) {
 221   size_t entry_count = hlines->limit_y - hlines->start_y;
 222   size_t i;
 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
 242 i_int_hlines_fill_color(i_img *im, i_int_hlines *hlines, const i_color *col) {
 243   i_img_dim y, i, x;
 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) {
 266   i_render r;
 267   i_img_dim y, i;
 268
 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;
 276         i_img_dim width = seg->x_limit-seg->minx;
 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
 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;
 296           i_img_dim width = seg->x_limit-seg->minx;
 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;
 327           i_img_dim width = seg->x_limit-seg->minx;
 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   }
 348 #endif
 349 }
 350
 351 /*
 352 =back
 353
 354 =head1 AUTHOR
 355
 356 Tony Cook <tonyc@cpan.org>
 357
 358 =head1 REVISION
 359
 360 $Revision$
 361
 362 =cut
 363 */