#include "imageri.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 *)) {
i_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) {
i_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, const 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) {
i_render r;
int y, i;
i_render_init(&r, im, 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;
i_render_fill(&r, seg->minx, y, width, NULL, fill);
}
}
}
i_render_done(&r);
#if 1
#else
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);
}
#endif
}
/*
=back
=head1 AUTHOR
Tony Cook <tony@imager.perl.org>
=head1 REVISION
$Revision: 1431 $
=cut
*/