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                   int start_y,
  63                   int count_y,
  64                   int start_x,
  65                   int width_x
  66                   )
  67 {
  68   int 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, int y, int x, int width) {
 111   int 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     int 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         int 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   int entry_count = hlines->limit_y - hlines->start_y;
 222   int 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   int 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   int y, i;
 267
 268   if (im->bits == i_8_bits && fill->fill_with_color) {
 269     i_color *line = mymalloc(sizeof(i_color) * im->xsize);
 270     i_color *work = NULL;
 271     if (fill->combine)
 272       work = mymalloc(sizeof(i_color) * im->xsize);
 273     for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 274       i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 275       if (entry) {
 276         for (i = 0; i < entry->count; ++i) {
 277           i_int_hline_seg *seg = entry->segs + i;
 278           int width = seg->x_limit-seg->minx;
 279
 280           if (fill->combine) {
 281             i_glin(im, seg->minx, seg->x_limit, y, line);
 282             (fill->fill_with_color)(fill, seg->minx, y, width,
 283                                     im->channels, work);
 284             (fill->combine)(line, work, im->channels, width);
 285           }
 286           else {
 287             (fill->fill_with_color)(fill, seg->minx, y, width,
 288                                     im->channels, line);
 289           }
 290           i_plin(im, seg->minx, seg->x_limit, y, line);
 291         }
 292       }
 293     }
 294
 295     myfree(line);
 296     if (work)
 297       myfree(work);
 298   }
 299   else {
 300     i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
 301     i_fcolor *work = NULL;
 302     if (fill->combinef)
 303       work = mymalloc(sizeof(i_fcolor) * im->xsize);
 304     for (y = hlines->start_y; y < hlines->limit_y; ++y) {
 305       i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
 306       if (entry) {
 307         for (i = 0; i < entry->count; ++i) {
 308           i_int_hline_seg *seg = entry->segs + i;
 309           int width = seg->x_limit-seg->minx;
 310
 311           if (fill->combinef) {
 312             i_glinf(im, seg->minx, seg->x_limit, y, line);
 313             (fill->fill_with_fcolor)(fill, seg->minx, y, width,
 314                                      im->channels, work);
 315             (fill->combinef)(line, work, im->channels, width);
 316           }
 317           else {
 318             (fill->fill_with_fcolor)(fill, seg->minx, y, width,
 319                                      im->channels, line);
 320           }
 321           i_plinf(im, seg->minx, seg->x_limit, y, line);
 322         }
 323       }
 324     }
 325
 326     myfree(line);
 327     if (work)
 328       myfree(work);
 329   }
 330 }
 331
 332 /*
 333 =back
 334
 335 =head1 AUTHOR
 336
 337 Tony Cook <tony@imager.perl.org>
 338
 339 =head1 REVISION
 340
 341 $Revision$
 342
 343 =cut
 344 */