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     i_fatal(3, "integer overflow calculating memory allocation\n");
  73   }
  74
  75   hlines->start_y = start_y;
  76   hlines->limit_y = start_y + count_y;
  77   hlines->start_x = start_x;
  78   hlines->limit_x = start_x + width_x;
  79   hlines->entries = mymalloc(bytes);
  80   memset(hlines->entries, 0, bytes);
  81 }
  82
  83 /*
  84 =item i_int_init_hlines_img
  85
  86 i_int_init_hlines_img(img);
  87
  88 Initialize a hlines object as if we could potentially draw anywhere on
  89 the image.
  90
  91 =cut
  92 */
  93
  94 void
  95 i_int_init_hlines_img(i_int_hlines *hlines, i_img *img)
  96 {
  97   i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
  98 }
  99
 100 /*
 101 =item i_int_hlines_add
 102
 103 i_int_hlines_add(hlines, y, x, width)
 104
 105 Add to the list, merging with existing entries.
 106
 107 =cut
 108 */
 109
 110 void
 111 i_int_hlines_add(i_int_hlines *hlines, i_img_dim y, i_img_dim x, i_img_dim width) {
 112   i_img_dim x_limit = x + width;
 113
 114   if (width < 0) {
 115     i_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
 116   }
 117
 118   /* just return if out of range */
 119   if (y < hlines->start_y || y >= hlines->limit_y)
 120     return;
 121
 122   if (x >= hlines->limit_x || x_limit < hlines->start_x)
 123     return;
 124
 125   /* adjust x to our range */
 126   if (x < hlines->start_x)
 127     x = hlines->start_x;
 128   if (x_limit > hlines->limit_x)
 129     x_limit = hlines->limit_x;
 130
 131   if (x == x_limit)
 132     return;
 133
 134   if (hlines->entries[y - hlines->start_y]) {
 135     i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 136     i_img_dim i, found = -1;
 137
 138     for (i = 0; i < entry->count; ++i) {
 139       i_int_hline_seg *seg = entry->segs + i;
 140       if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
 141         found = i;
 142         break;
 143       }
 144     }
 145     if (found >= 0) {
 146       /* ok, we found an overlapping segment, any other overlapping
 147          segments need to be merged into the one we found */
 148       i_int_hline_seg *merge_seg = entry->segs + found;
 149
 150       /* merge in the segment we found */
 151       x = im_min(x, merge_seg->minx);
 152       x_limit = im_max(x_limit, merge_seg->x_limit);
 153
 154       /* look for other overlapping segments */
 155       /* this could be a for(), but I'm using continue */
 156       i = found + 1;
 157       while (i < entry->count) {
 158         i_int_hline_seg *seg = entry->segs + i;
 159         if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
 160           /* merge this into the current working segment, then
 161              delete it by moving the last segment (if this isn't it)
 162              into it's place */
 163           x = im_min(x, seg->minx);
 164           x_limit = im_max(x_limit, seg->x_limit);
 165           if (i < entry->count-1) {
 166             *seg = entry->segs[entry->count-1];
 167             --entry->count;
 168             continue;
 169           }
 170           else {
 171             --entry->count;
 172             break;
 173           }
 174         }
 175         ++i;
 176       }
 177
 178       /* store it back */
 179       merge_seg->minx = x;
 180       merge_seg->x_limit = x_limit;
 181     }
 182     else {
 183       i_int_hline_seg *seg;
 184       /* add a new segment */
 185       if (entry->count == entry->alloc) {
 186         /* expand it */
 187         size_t alloc = entry->alloc * 3 / 2;
 188         entry = myrealloc(entry, sizeof(i_int_hline_entry) +
 189                            sizeof(i_int_hline_seg) * (alloc - 1));
 190         entry->alloc = alloc;
 191         hlines->entries[y - hlines->start_y] = entry;
 192       }
 193       seg = entry->segs + entry->count++;
 194       seg->minx = x;
 195       seg->x_limit = x_limit;
 196     }
 197   }
 198   else {
 199     /* make a new one - start with space for 10 */
 200     i_int_hline_entry *entry = mymalloc(sizeof(i_int_hline_entry) +
 201                                         sizeof(i_int_hline_seg) * 9);
 202     entry->alloc = 10;
 203     entry->count = 1;
 204     entry->segs[0].minx = x;
 205     entry->segs[0].x_limit = x_limit;
 206     hlines->entries[y - hlines->start_y] = entry;
 207   }
 208 }
 209
 210 /*
 211 =item i_int_hlines_destroy
 212
 213 i_int_hlines_destroy(&hlines)
 214
 215 Releases all memory associated with the structure.
 216
 217 =cut
 218 */
 219
 220 void
 221 i_int_hlines_destroy(i_int_hlines *hlines) {
 222   size_t entry_count = hlines->limit_y - hlines->start_y;
 223   size_t i;
 224
 225   for (i = 0; i < entry_count; ++i) {
 226     if (hlines->entries[i])
 227       myfree(hlines->entries[i]);
 228   }
 229   myfree(hlines->entries);
 230 }
 231
 232 /*
 233 =item i_int_hlines_fill_color
 234
 235 i_int_hlines_fill(im, hlines, color)
 236
 237 Fill the areas given by hlines with color.
 238
 239 =cut
 240 */
 241
 242 void
 243 i_int_hlines_fill_color(i_img *im, i_int_hlines *hlines, const i_color *col) {
 244   i_img_dim y, i, x;
 245
 246   for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 247     i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 248     if (entry) {
 249       for (i = 0; i < entry->count; ++i) {
 250         i_int_hline_seg *seg = entry->segs + i;
 251         for (x = seg->minx; x < seg->x_limit; ++x) {
 252           i_ppix(im, x, y, col);
 253         }
 254       }
 255     }
 256   }
 257 }
 258
 259 /*
 260 =item i_int_hlines_fill_fill
 261
 262 i_int_hlines_fill_fill(im, hlines, fill)
 263
 264 */
 265 void
 266 i_int_hlines_fill_fill(i_img *im, i_int_hlines *hlines, i_fill_t *fill) {
 267   i_render r;
 268   i_img_dim y, i;
 269
 270   i_render_init(&r, im, im->xsize);
 271
 272   for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 273     i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 274     if (entry) {
 275       for (i = 0; i < entry->count; ++i) {
 276         i_int_hline_seg *seg = entry->segs + i;
 277         i_img_dim width = seg->x_limit-seg->minx;
 278
 279         i_render_fill(&r, seg->minx, y, width, NULL, fill);
 280       }
 281     }
 282   }
 283   i_render_done(&r);
 284
 285 #if 1
 286 #else
 287   if (im->bits == i_8_bits && fill->fill_with_color) {
 288     i_color *line = mymalloc(sizeof(i_color) * im->xsize);
 289     i_color *work = NULL;
 290     if (fill->combine)
 291       work = mymalloc(sizeof(i_color) * im->xsize);
 292     for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 293       i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 294       if (entry) {
 295         for (i = 0; i < entry->count; ++i) {
 296           i_int_hline_seg *seg = entry->segs + i;
 297           i_img_dim width = seg->x_limit-seg->minx;
 298
 299           if (fill->combine) {
 300             i_glin(im, seg->minx, seg->x_limit, y, line);
 301             (fill->fill_with_color)(fill, seg->minx, y, width,
 302                                     im->channels, work);
 303             (fill->combine)(line, work, im->channels, width);
 304           }
 305           else {
 306             (fill->fill_with_color)(fill, seg->minx, y, width,
 307                                     im->channels, line);
 308           }
 309           i_plin(im, seg->minx, seg->x_limit, y, line);
 310         }
 311       }
 312     }
 313
 314     myfree(line);
 315     if (work)
 316       myfree(work);
 317   }
 318   else {
 319     i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
 320     i_fcolor *work = NULL;
 321     if (fill->combinef)
 322       work = mymalloc(sizeof(i_fcolor) * im->xsize);
 323     for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 324       i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 325       if (entry) {
 326         for (i = 0; i < entry->count; ++i) {
 327           i_int_hline_seg *seg = entry->segs + i;
 328           i_img_dim width = seg->x_limit-seg->minx;
 329
 330           if (fill->combinef) {
 331             i_glinf(im, seg->minx, seg->x_limit, y, line);
 332             (fill->fill_with_fcolor)(fill, seg->minx, y, width,
 333                                      im->channels, work);
 334             (fill->combinef)(line, work, im->channels, width);
 335           }
 336           else {
 337             (fill->fill_with_fcolor)(fill, seg->minx, y, width,
 338                                      im->channels, line);
 339           }
 340           i_plinf(im, seg->minx, seg->x_limit, y, line);
 341         }
 342       }
 343     }
 344
 345     myfree(line);
 346     if (work)
 347       myfree(work);
 348   }
 349 #endif
 350 }
 351
 352 /*
 353 =back
 354
 355 =head1 AUTHOR
 356
 357 Tony Cook <tonyc@cpan.org>
 358
 359 =head1 REVISION
 360
 361 $Revision$
 362
 363 =cut
 364 */