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 */
 267 void
 268 i_int_hlines_fill_fill(i_img *im, i_int_hlines *hlines, i_fill_t *fill) {
 269   i_render r;
 270   i_img_dim y, i;
 271
 272   i_render_init(&r, im, im->xsize);
 273
 274   for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 275     i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 276     if (entry) {
 277       for (i = 0; i < entry->count; ++i) {
 278         i_int_hline_seg *seg = entry->segs + i;
 279         i_img_dim width = seg->x_limit-seg->minx;
 280
 281         i_render_fill(&r, seg->minx, y, width, NULL, fill);
 282       }
 283     }
 284   }
 285   i_render_done(&r);
 286
 287 #if 1
 288 #else
 289   if (im->bits == i_8_bits && fill->fill_with_color) {
 290     i_color *line = mymalloc(sizeof(i_color) * im->xsize);
 291     i_color *work = NULL;
 292     if (fill->combine)
 293       work = mymalloc(sizeof(i_color) * im->xsize);
 294     for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 295       i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 296       if (entry) {
 297         for (i = 0; i < entry->count; ++i) {
 298           i_int_hline_seg *seg = entry->segs + i;
 299           i_img_dim width = seg->x_limit-seg->minx;
 300
 301           if (fill->combine) {
 302             i_glin(im, seg->minx, seg->x_limit, y, line);
 303             (fill->fill_with_color)(fill, seg->minx, y, width,
 304                                     im->channels, work);
 305             (fill->combine)(line, work, im->channels, width);
 306           }
 307           else {
 308             (fill->fill_with_color)(fill, seg->minx, y, width,
 309                                     im->channels, line);
 310           }
 311           i_plin(im, seg->minx, seg->x_limit, y, line);
 312         }
 313       }
 314     }
 315
 316     myfree(line);
 317     if (work)
 318       myfree(work);
 319   }
 320   else {
 321     i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
 322     i_fcolor *work = NULL;
 323     if (fill->combinef)
 324       work = mymalloc(sizeof(i_fcolor) * im->xsize);
 325     for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 326       i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 327       if (entry) {
 328         for (i = 0; i < entry->count; ++i) {
 329           i_int_hline_seg *seg = entry->segs + i;
 330           i_img_dim width = seg->x_limit-seg->minx;
 331
 332           if (fill->combinef) {
 333             i_glinf(im, seg->minx, seg->x_limit, y, line);
 334             (fill->fill_with_fcolor)(fill, seg->minx, y, width,
 335                                      im->channels, work);
 336             (fill->combinef)(line, work, im->channels, width);
 337           }
 338           else {
 339             (fill->fill_with_fcolor)(fill, seg->minx, y, width,
 340                                      im->channels, line);
 341           }
 342           i_plinf(im, seg->minx, seg->x_limit, y, line);
 343         }
 344       }
 345     }
 346
 347     myfree(line);
 348     if (work)
 349       myfree(work);
 350   }
 351 #endif
 352 }
 353
 354 /*
 355 =back
 356
 357 =head1 AUTHOR
 358
 359 Tony Cook <tonyc@cpan.org>
 360
 361 =head1 REVISION
 362
 363 $Revision$
 364
 365 =cut
 366 */