[imager.git] / hlines.c

#define IMAGER_NO_CONTEXT
#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, 
		  i_img_dim start_y, 
		  i_img_dim count_y,
		  i_img_dim start_x, 
		  i_img_dim width_x
		  )
{
  size_t bytes = count_y * sizeof(i_int_hline_entry *);

  if (bytes / count_y != sizeof(i_int_hline_entry *)) {
    dIMCTX;
    im_fatal(aIMCTX, 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, i_img_dim y, i_img_dim x, i_img_dim width) {
  i_img_dim x_limit = x + width;

  if (width < 0) {
    dIMCTX;
    im_fatal(aIMCTX, 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];
    i_img_dim 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 */
	size_t 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) {
  size_t entry_count = hlines->limit_y - hlines->start_y;
  size_t 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) {
  i_img_dim 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;
  i_img_dim 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;
	i_img_dim 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;
	  i_img_dim 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;
	  i_img_dim 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 <tonyc@cpan.org>

=head1 REVISION

$Revision$

=cut
*/
Commit	Line	Data
fc414e6a	1	#define IMAGER_NO_CONTEXT
92bda632	2	#include "imageri.h"
39f94030 TC	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,
8d14daab TC	63	i_img_dim start_y,
	64	i_img_dim count_y,
	65	i_img_dim start_x,
	66	i_img_dim width_x
39f94030 TC	67	)
39f94030 TC	68	{
8d14daab	69	size_t bytes = count_y * sizeof(i_int_hline_entry *);
39f94030 TC	70
39f94030 TC	71	if (bytes / count_y != sizeof(i_int_hline_entry *)) {
8ebac85f TC	72	dIMCTX;
8ebac85f TC	73	im_fatal(aIMCTX, 3, "integer overflow calculating memory allocation\n");
39f94030 TC	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
8d14daab TC	112	i_int_hlines_add(i_int_hlines *hlines, i_img_dim y, i_img_dim x, i_img_dim width) {
8d14daab TC	113	i_img_dim x_limit = x + width;
39f94030 TC	114
39f94030 TC	115	if (width < 0) {
8ebac85f TC	116	dIMCTX;
8ebac85f TC	117	im_fatal(aIMCTX, 3, "negative width %d passed to i_int_hlines_add\n", width);
39f94030 TC	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];
8d14daab	138	i_img_dim i, found = -1;
39f94030 TC	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 */
8d14daab	189	size_t alloc = entry->alloc * 3 / 2;
39f94030 TC	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) {
8d14daab TC	224	size_t entry_count = hlines->limit_y - hlines->start_y;
8d14daab TC	225	size_t i;
39f94030 TC	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
97ac0a96	245	i_int_hlines_fill_color(i_img im, i_int_hlines hlines, const i_color *col) {
8d14daab	246	i_img_dim y, i, x;
39f94030 TC	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	*/
	267	void
	268	i_int_hlines_fill_fill(i_img im, i_int_hlines hlines, i_fill_t *fill) {
9b1ec2b8	269	i_render r;
8d14daab	270	i_img_dim y, i;
39f94030	271
9b1ec2b8 TC	272	i_render_init(&r, im, im->xsize);
	273
	274	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	275	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	276	if (entry) {
	277	for (i = 0; i < entry->count; ++i) {
	278	i_int_hline_seg *seg = entry->segs + i;
8d14daab	279	i_img_dim width = seg->x_limit-seg->minx;
9b1ec2b8 TC	280
	281	i_render_fill(&r, seg->minx, y, width, NULL, fill);
	282	}
	283	}
	284	}
	285	i_render_done(&r);
	286
	287	#if 1
	288	#else
39f94030 TC	289	if (im->bits == i_8_bits && fill->fill_with_color) {
	290	i_color line = mymalloc(sizeof(i_color) im->xsize);
	291	i_color *work = NULL;
	292	if (fill->combine)
	293	work = mymalloc(sizeof(i_color) * im->xsize);
	294	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	295	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	296	if (entry) {
	297	for (i = 0; i < entry->count; ++i) {
	298	i_int_hline_seg *seg = entry->segs + i;
8d14daab	299	i_img_dim width = seg->x_limit-seg->minx;
39f94030 TC	300
	301	if (fill->combine) {
	302	i_glin(im, seg->minx, seg->x_limit, y, line);
	303	(fill->fill_with_color)(fill, seg->minx, y, width,
	304	im->channels, work);
	305	(fill->combine)(line, work, im->channels, width);
	306	}
	307	else {
	308	(fill->fill_with_color)(fill, seg->minx, y, width,
	309	im->channels, line);
	310	}
	311	i_plin(im, seg->minx, seg->x_limit, y, line);
	312	}
	313	}
	314	}
	315
	316	myfree(line);
	317	if (work)
	318	myfree(work);
	319	}
	320	else {
	321	i_fcolor line = mymalloc(sizeof(i_fcolor) im->xsize);
	322	i_fcolor *work = NULL;
	323	if (fill->combinef)
	324	work = mymalloc(sizeof(i_fcolor) * im->xsize);
	325	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	326	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	327	if (entry) {
	328	for (i = 0; i < entry->count; ++i) {
	329	i_int_hline_seg *seg = entry->segs + i;
8d14daab	330	i_img_dim width = seg->x_limit-seg->minx;
39f94030 TC	331
	332	if (fill->combinef) {
	333	i_glinf(im, seg->minx, seg->x_limit, y, line);
	334	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	335	im->channels, work);
	336	(fill->combinef)(line, work, im->channels, width);
	337	}
	338	else {
	339	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	340	im->channels, line);
	341	}
	342	i_plinf(im, seg->minx, seg->x_limit, y, line);
	343	}
	344	}
	345	}
	346
	347	myfree(line);
	348	if (work)
	349	myfree(work);
	350	}
9b1ec2b8	351	#endif
39f94030 TC	352	}
	353
	354	/*
	355	=back
	356
	357	=head1 AUTHOR
	358
5b480b14	359	Tony Cook <tonyc@cpan.org>
39f94030 TC	360
	361	=head1 REVISION
	362
	363	$Revision$
	364
	365	=cut
	366	*/