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 */