[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)

=cut
*/
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
12db268a	266	=cut
39f94030 TC	267	*/
	268	void
	269	i_int_hlines_fill_fill(i_img im, i_int_hlines hlines, i_fill_t *fill) {
9b1ec2b8	270	i_render r;
8d14daab	271	i_img_dim y, i;
39f94030	272
9b1ec2b8 TC	273	i_render_init(&r, im, im->xsize);
	274
	275	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	276	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	277	if (entry) {
	278	for (i = 0; i < entry->count; ++i) {
	279	i_int_hline_seg *seg = entry->segs + i;
8d14daab	280	i_img_dim width = seg->x_limit-seg->minx;
9b1ec2b8 TC	281
	282	i_render_fill(&r, seg->minx, y, width, NULL, fill);
	283	}
	284	}
	285	}
	286	i_render_done(&r);
	287
	288	#if 1
	289	#else
39f94030 TC	290	if (im->bits == i_8_bits && fill->fill_with_color) {
	291	i_color line = mymalloc(sizeof(i_color) im->xsize);
	292	i_color *work = NULL;
	293	if (fill->combine)
	294	work = mymalloc(sizeof(i_color) * im->xsize);
	295	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	296	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	297	if (entry) {
	298	for (i = 0; i < entry->count; ++i) {
	299	i_int_hline_seg *seg = entry->segs + i;
8d14daab	300	i_img_dim width = seg->x_limit-seg->minx;
39f94030 TC	301
	302	if (fill->combine) {
	303	i_glin(im, seg->minx, seg->x_limit, y, line);
	304	(fill->fill_with_color)(fill, seg->minx, y, width,
	305	im->channels, work);
	306	(fill->combine)(line, work, im->channels, width);
	307	}
	308	else {
	309	(fill->fill_with_color)(fill, seg->minx, y, width,
	310	im->channels, line);
	311	}
	312	i_plin(im, seg->minx, seg->x_limit, y, line);
	313	}
	314	}
	315	}
	316
	317	myfree(line);
	318	if (work)
	319	myfree(work);
	320	}
	321	else {
	322	i_fcolor line = mymalloc(sizeof(i_fcolor) im->xsize);
	323	i_fcolor *work = NULL;
	324	if (fill->combinef)
	325	work = mymalloc(sizeof(i_fcolor) * im->xsize);
	326	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	327	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	328	if (entry) {
	329	for (i = 0; i < entry->count; ++i) {
	330	i_int_hline_seg *seg = entry->segs + i;
8d14daab	331	i_img_dim width = seg->x_limit-seg->minx;
39f94030 TC	332
	333	if (fill->combinef) {
	334	i_glinf(im, seg->minx, seg->x_limit, y, line);
	335	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	336	im->channels, work);
	337	(fill->combinef)(line, work, im->channels, width);
	338	}
	339	else {
	340	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	341	im->channels, line);
	342	}
	343	i_plinf(im, seg->minx, seg->x_limit, y, line);
	344	}
	345	}
	346	}
	347
	348	myfree(line);
	349	if (work)
	350	myfree(work);
	351	}
9b1ec2b8	352	#endif
39f94030 TC	353	}
	354
	355	/*
	356	=back
	357
	358	=head1 AUTHOR
	359
5b480b14	360	Tony Cook <tonyc@cpan.org>
39f94030 TC	361
	362	=head1 REVISION
	363
	364	$Revision$
	365
	366	=cut
	367	*/