+#include "imagei.h"
+#include <stdlib.h>
+
+#define OVERLAPPED(start1, end1, start2, end2) \
+ (im_max((start1), (start2)) <= im_min((end1), (end2)))
+
+/*
+=head1 NAME
+
+hlines.c - implements a "class" for managing sets of horizontal line segments
+
+=head1 SYNOPSIS
+
+ i_int_hlines hlines;
+ // just for the specified range of y
+ i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x);
+ // to cover a whole image
+ i_int_init_hlines_img(&hlines, img);
+ // add a hline segment, merging into existing
+ i_int_hlines_add(&hlines, y, x, width);
+
+ // work over the lines
+ for (y = hlines.start; y < hlines.limit; ++y) {
+ i_int_hline_entry *entry = hlines.entries[i];
+ if (entry) {
+ for (i = 0; i < entry->count; ++i) {
+ i_int_hline_seg *seg = entry->segs+i;
+ // do something on line y for seg->minx to x_limit
+ }
+ }
+ }
+
+ // free it all up
+ i_int_hlines_destroy(&hlines);
+
+=head1 DESCRIPTION
+
+Provides a class to manage sets of horizontal line segments. The
+intent is that when drawing shapes where the algorithm used might
+cause overlaps we can use this class to resolve the overlaps.
+
+Note that segment lists are intended to remain small, if we end up
+with a need for longer lists we should use different structure for the
+segment lists.
+
+=over
+
+=item i_int_init_hlines
+
+i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x)
+
+Initializes the structure based on drawing an object within the given
+range. Any x or y values outside the given ranges will be ignored.
+
+=cut
+
+*/
+
+void
+i_int_init_hlines(
+ i_int_hlines *hlines,
+ int start_y,
+ int count_y,
+ int start_x,
+ int width_x
+ )
+{
+ int bytes = count_y * sizeof(i_int_hline_entry *);
+
+ if (bytes / count_y != sizeof(i_int_hline_entry *)) {
+ m_fatal(3, "integer overflow calculating memory allocation\n");
+ }
+
+ hlines->start_y = start_y;
+ hlines->limit_y = start_y + count_y;
+ hlines->start_x = start_x;
+ hlines->limit_x = start_x + width_x;
+ hlines->entries = mymalloc(bytes);
+ memset(hlines->entries, 0, bytes);
+}
+
+/*
+=item i_int_init_hlines_img
+
+i_int_init_hlines_img(img);
+
+Initialize a hlines object as if we could potentially draw anywhere on
+the image.
+
+=cut
+*/
+
+void
+i_int_init_hlines_img(i_int_hlines *hlines, i_img *img)
+{
+ i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
+}
+
+/*
+=item i_int_hlines_add
+
+i_int_hlines_add(hlines, y, x, width)
+
+Add to the list, merging with existing entries.
+
+=cut
+*/
+
+void
+i_int_hlines_add(i_int_hlines *hlines, int y, int x, int width) {
+ int x_limit = x + width;
+
+ if (width < 0) {
+ m_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
+ }
+
+ /* just return if out of range */
+ if (y < hlines->start_y || y >= hlines->limit_y)
+ return;
+
+ if (x >= hlines->limit_x || x_limit < hlines->start_x)
+ return;
+
+ /* adjust x to our range */
+ if (x < hlines->start_x)
+ x = hlines->start_x;
+ if (x_limit > hlines->limit_x)
+ x_limit = hlines->limit_x;
+
+ if (x == x_limit)
+ return;
+
+ if (hlines->entries[y - hlines->start_y]) {
+ i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
+ int i, found = -1;
+
+ for (i = 0; i < entry->count; ++i) {
+ i_int_hline_seg *seg = entry->segs + i;
+ if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
+ found = i;
+ break;
+ }
+ }
+ if (found >= 0) {
+ /* ok, we found an overlapping segment, any other overlapping
+ segments need to be merged into the one we found */
+ i_int_hline_seg *merge_seg = entry->segs + found;
+
+ /* merge in the segment we found */
+ x = im_min(x, merge_seg->minx);
+ x_limit = im_max(x_limit, merge_seg->x_limit);
+
+ /* look for other overlapping segments */
+ /* this could be a for(), but I'm using continue */
+ i = found + 1;
+ while (i < entry->count) {
+ i_int_hline_seg *seg = entry->segs + i;
+ if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
+ /* merge this into the current working segment, then
+ delete it by moving the last segment (if this isn't it)
+ into it's place */
+ x = im_min(x, seg->minx);
+ x_limit = im_max(x_limit, seg->x_limit);
+ if (i < entry->count-1) {
+ *seg = entry->segs[entry->count-1];
+ --entry->count;
+ continue;
+ }
+ else {
+ --entry->count;
+ break;
+ }
+ }
+ ++i;
+ }
+
+ /* store it back */
+ merge_seg->minx = x;
+ merge_seg->x_limit = x_limit;
+ }
+ else {
+ i_int_hline_seg *seg;
+ /* add a new segment */
+ if (entry->count == entry->alloc) {
+ /* expand it */
+ int alloc = entry->alloc * 3 / 2;
+ entry = myrealloc(entry, sizeof(i_int_hline_entry) +
+ sizeof(i_int_hline_seg) * (alloc - 1));
+ entry->alloc = alloc;
+ hlines->entries[y - hlines->start_y] = entry;
+ }
+ seg = entry->segs + entry->count++;
+ seg->minx = x;
+ seg->x_limit = x_limit;
+ }
+ }
+ else {
+ /* make a new one - start with space for 10 */
+ i_int_hline_entry *entry = mymalloc(sizeof(i_int_hline_entry) +
+ sizeof(i_int_hline_seg) * 9);
+ entry->alloc = 10;
+ entry->count = 1;
+ entry->segs[0].minx = x;
+ entry->segs[0].x_limit = x_limit;
+ hlines->entries[y - hlines->start_y] = entry;
+ }
+}
+
+/*
+=item i_int_hlines_destroy
+
+i_int_hlines_destroy(&hlines)
+
+Releases all memory associated with the structure.
+
+=cut
+*/
+
+void
+i_int_hlines_destroy(i_int_hlines *hlines) {
+ int entry_count = hlines->limit_y - hlines->start_y;
+ int i;
+
+ for (i = 0; i < entry_count; ++i) {
+ if (hlines->entries[i])
+ myfree(hlines->entries[i]);
+ }
+ myfree(hlines->entries);
+}
+
+/*
+=item i_int_hlines_fill_color
+
+i_int_hlines_fill(im, hlines, color)
+
+Fill the areas given by hlines with color.
+
+=cut
+*/
+
+void
+i_int_hlines_fill_color(i_img *im, i_int_hlines *hlines, i_color *col) {
+ int y, i, x;
+
+ for (y = hlines->start_y; y < hlines->limit_y; ++y) {
+ i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
+ if (entry) {
+ for (i = 0; i < entry->count; ++i) {
+ i_int_hline_seg *seg = entry->segs + i;
+ for (x = seg->minx; x < seg->x_limit; ++x) {
+ i_ppix(im, x, y, col);
+ }
+ }
+ }
+ }
+}
+
+/*
+=item i_int_hlines_fill_fill
+
+i_int_hlines_fill_fill(im, hlines, fill)
+
+*/
+void
+i_int_hlines_fill_fill(i_img *im, i_int_hlines *hlines, i_fill_t *fill) {
+ int y, i, x;
+
+ if (im->bits == i_8_bits && fill->fill_with_color) {
+ i_color *line = mymalloc(sizeof(i_color) * im->xsize);
+ i_color *work = NULL;
+ if (fill->combine)
+ work = mymalloc(sizeof(i_color) * im->xsize);
+ for (y = hlines->start_y; y < hlines->limit_y; ++y) {
+ i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
+ if (entry) {
+ for (i = 0; i < entry->count; ++i) {
+ i_int_hline_seg *seg = entry->segs + i;
+ int width = seg->x_limit-seg->minx;
+
+ if (fill->combine) {
+ i_glin(im, seg->minx, seg->x_limit, y, line);
+ (fill->fill_with_color)(fill, seg->minx, y, width,
+ im->channels, work);
+ (fill->combine)(line, work, im->channels, width);
+ }
+ else {
+ (fill->fill_with_color)(fill, seg->minx, y, width,
+ im->channels, line);
+ }
+ i_plin(im, seg->minx, seg->x_limit, y, line);
+ }
+ }
+ }
+
+ myfree(line);
+ if (work)
+ myfree(work);
+ }
+ else {
+ i_fcolor *line = mymalloc(sizeof(i_fcolor) * im->xsize);
+ i_fcolor *work = NULL;
+ if (fill->combinef)
+ work = mymalloc(sizeof(i_fcolor) * im->xsize);
+ for (y = hlines->start_y; y < hlines->limit_y; ++y) {
+ i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
+ if (entry) {
+ for (i = 0; i < entry->count; ++i) {
+ i_int_hline_seg *seg = entry->segs + i;
+ int width = seg->x_limit-seg->minx;
+
+ if (fill->combinef) {
+ i_glinf(im, seg->minx, seg->x_limit, y, line);
+ (fill->fill_with_fcolor)(fill, seg->minx, y, width,
+ im->channels, work);
+ (fill->combinef)(line, work, im->channels, width);
+ }
+ else {
+ (fill->fill_with_fcolor)(fill, seg->minx, y, width,
+ im->channels, line);
+ }
+ i_plinf(im, seg->minx, seg->x_limit, y, line);
+ }
+ }
+ }
+
+ myfree(line);
+ if (work)
+ myfree(work);
+ }
+}
+
+/*
+=back
+
+=head1 AUTHOR
+
+Tony Cook <tony@imager.perl.org>
+
+=head1 REVISION
+
+$Revision$
+
+=cut
+*/
projects / imager.git / commitdiff