[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 *)) {
    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, i_img_dim y, i_img_dim x, i_img_dim width) {
  i_img_dim 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];
    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 *)) {
d03fd5a4	72	i_fatal(3, "integer overflow calculating memory allocation\n");
39f94030 TC	73	}
	74
	75	hlines->start_y = start_y;
	76	hlines->limit_y = start_y + count_y;
	77	hlines->start_x = start_x;
	78	hlines->limit_x = start_x + width_x;
	79	hlines->entries = mymalloc(bytes);
	80	memset(hlines->entries, 0, bytes);
	81	}
	82
	83	/*
	84	=item i_int_init_hlines_img
	85
	86	i_int_init_hlines_img(img);
	87
	88	Initialize a hlines object as if we could potentially draw anywhere on
	89	the image.
	90
	91	=cut
	92	*/
	93
	94	void
	95	i_int_init_hlines_img(i_int_hlines hlines, i_img img)
	96	{
	97	i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
	98	}
	99
	100	/*
	101	=item i_int_hlines_add
	102
	103	i_int_hlines_add(hlines, y, x, width)
	104
	105	Add to the list, merging with existing entries.
	106
	107	=cut
	108	*/
	109
	110	void
8d14daab TC	111	i_int_hlines_add(i_int_hlines *hlines, i_img_dim y, i_img_dim x, i_img_dim width) {
8d14daab TC	112	i_img_dim x_limit = x + width;
39f94030 TC	113
39f94030 TC	114	if (width < 0) {
d03fd5a4	115	i_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
39f94030 TC	116	}
	117
	118	/* just return if out of range */
	119	if (y < hlines->start_y \|\| y >= hlines->limit_y)
	120	return;
	121
	122	if (x >= hlines->limit_x \|\| x_limit < hlines->start_x)
	123	return;
	124
	125	/* adjust x to our range */
	126	if (x < hlines->start_x)
	127	x = hlines->start_x;
	128	if (x_limit > hlines->limit_x)
	129	x_limit = hlines->limit_x;
	130
	131	if (x == x_limit)
	132	return;
	133
	134	if (hlines->entries[y - hlines->start_y]) {
	135	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
8d14daab	136	i_img_dim i, found = -1;
39f94030 TC	137
	138	for (i = 0; i < entry->count; ++i) {
	139	i_int_hline_seg *seg = entry->segs + i;
	140	if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
	141	found = i;
	142	break;
	143	}
	144	}
	145	if (found >= 0) {
	146	/* ok, we found an overlapping segment, any other overlapping
	147	segments need to be merged into the one we found */
	148	i_int_hline_seg *merge_seg = entry->segs + found;
	149
	150	/* merge in the segment we found */
	151	x = im_min(x, merge_seg->minx);
	152	x_limit = im_max(x_limit, merge_seg->x_limit);
	153
	154	/* look for other overlapping segments */
	155	/* this could be a for(), but I'm using continue */
	156	i = found + 1;
	157	while (i < entry->count) {
	158	i_int_hline_seg *seg = entry->segs + i;
	159	if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
	160	/* merge this into the current working segment, then
	161	delete it by moving the last segment (if this isn't it)
	162	into it's place */
	163	x = im_min(x, seg->minx);
	164	x_limit = im_max(x_limit, seg->x_limit);
	165	if (i < entry->count-1) {
	166	*seg = entry->segs[entry->count-1];
	167	--entry->count;
	168	continue;
	169	}
	170	else {
	171	--entry->count;
	172	break;
	173	}
	174	}
	175	++i;
	176	}
	177
	178	/* store it back */
	179	merge_seg->minx = x;
	180	merge_seg->x_limit = x_limit;
	181	}
	182	else {
	183	i_int_hline_seg *seg;
	184	/* add a new segment */
	185	if (entry->count == entry->alloc) {
	186	/* expand it */
8d14daab	187	size_t alloc = entry->alloc * 3 / 2;
39f94030 TC	188	entry = myrealloc(entry, sizeof(i_int_hline_entry) +
	189	sizeof(i_int_hline_seg) * (alloc - 1));
	190	entry->alloc = alloc;
	191	hlines->entries[y - hlines->start_y] = entry;
	192	}
	193	seg = entry->segs + entry->count++;
	194	seg->minx = x;
	195	seg->x_limit = x_limit;
	196	}
	197	}
	198	else {
	199	/* make a new one - start with space for 10 */
	200	i_int_hline_entry *entry = mymalloc(sizeof(i_int_hline_entry) +
	201	sizeof(i_int_hline_seg) * 9);
	202	entry->alloc = 10;
	203	entry->count = 1;
	204	entry->segs[0].minx = x;
	205	entry->segs[0].x_limit = x_limit;
	206	hlines->entries[y - hlines->start_y] = entry;
	207	}
	208	}
	209
	210	/*
	211	=item i_int_hlines_destroy
	212
	213	i_int_hlines_destroy(&hlines)
	214
	215	Releases all memory associated with the structure.
	216
	217	=cut
	218	*/
	219
	220	void
	221	i_int_hlines_destroy(i_int_hlines *hlines) {
8d14daab TC	222	size_t entry_count = hlines->limit_y - hlines->start_y;
8d14daab TC	223	size_t i;
39f94030 TC	224
	225	for (i = 0; i < entry_count; ++i) {
	226	if (hlines->entries[i])
	227	myfree(hlines->entries[i]);
	228	}
	229	myfree(hlines->entries);
	230	}
	231
	232	/*
	233	=item i_int_hlines_fill_color
	234
	235	i_int_hlines_fill(im, hlines, color)
	236
	237	Fill the areas given by hlines with color.
	238
	239	=cut
	240	*/
	241
	242	void
97ac0a96	243	i_int_hlines_fill_color(i_img im, i_int_hlines hlines, const i_color *col) {
8d14daab	244	i_img_dim y, i, x;
39f94030 TC	245
	246	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	247	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	248	if (entry) {
	249	for (i = 0; i < entry->count; ++i) {
	250	i_int_hline_seg *seg = entry->segs + i;
	251	for (x = seg->minx; x < seg->x_limit; ++x) {
	252	i_ppix(im, x, y, col);
	253	}
	254	}
	255	}
	256	}
	257	}
	258
	259	/*
	260	=item i_int_hlines_fill_fill
	261
	262	i_int_hlines_fill_fill(im, hlines, fill)
	263
	264	*/
	265	void
	266	i_int_hlines_fill_fill(i_img im, i_int_hlines hlines, i_fill_t *fill) {
9b1ec2b8	267	i_render r;
8d14daab	268	i_img_dim y, i;
39f94030	269
9b1ec2b8 TC	270	i_render_init(&r, im, im->xsize);
	271
	272	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	273	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	274	if (entry) {
	275	for (i = 0; i < entry->count; ++i) {
	276	i_int_hline_seg *seg = entry->segs + i;
8d14daab	277	i_img_dim width = seg->x_limit-seg->minx;
9b1ec2b8 TC	278
	279	i_render_fill(&r, seg->minx, y, width, NULL, fill);
	280	}
	281	}
	282	}
	283	i_render_done(&r);
	284
	285	#if 1
	286	#else
39f94030 TC	287	if (im->bits == i_8_bits && fill->fill_with_color) {
	288	i_color line = mymalloc(sizeof(i_color) im->xsize);
	289	i_color *work = NULL;
	290	if (fill->combine)
	291	work = mymalloc(sizeof(i_color) * im->xsize);
	292	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	293	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	294	if (entry) {
	295	for (i = 0; i < entry->count; ++i) {
	296	i_int_hline_seg *seg = entry->segs + i;
8d14daab	297	i_img_dim width = seg->x_limit-seg->minx;
39f94030 TC	298
	299	if (fill->combine) {
	300	i_glin(im, seg->minx, seg->x_limit, y, line);
	301	(fill->fill_with_color)(fill, seg->minx, y, width,
	302	im->channels, work);
	303	(fill->combine)(line, work, im->channels, width);
	304	}
	305	else {
	306	(fill->fill_with_color)(fill, seg->minx, y, width,
	307	im->channels, line);
	308	}
	309	i_plin(im, seg->minx, seg->x_limit, y, line);
	310	}
	311	}
	312	}
	313
	314	myfree(line);
	315	if (work)
	316	myfree(work);
	317	}
	318	else {
	319	i_fcolor line = mymalloc(sizeof(i_fcolor) im->xsize);
	320	i_fcolor *work = NULL;
	321	if (fill->combinef)
	322	work = mymalloc(sizeof(i_fcolor) * im->xsize);
	323	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	324	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	325	if (entry) {
	326	for (i = 0; i < entry->count; ++i) {
	327	i_int_hline_seg *seg = entry->segs + i;
8d14daab	328	i_img_dim width = seg->x_limit-seg->minx;
39f94030 TC	329
	330	if (fill->combinef) {
	331	i_glinf(im, seg->minx, seg->x_limit, y, line);
	332	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	333	im->channels, work);
	334	(fill->combinef)(line, work, im->channels, width);
	335	}
	336	else {
	337	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	338	im->channels, line);
	339	}
	340	i_plinf(im, seg->minx, seg->x_limit, y, line);
	341	}
	342	}
	343	}
	344
	345	myfree(line);
	346	if (work)
	347	myfree(work);
	348	}
9b1ec2b8	349	#endif
39f94030 TC	350	}
	351
	352	/*
	353	=back
	354
	355	=head1 AUTHOR
	356
5b480b14	357	Tony Cook <tonyc@cpan.org>
39f94030 TC	358
	359	=head1 REVISION
	360
	361	$Revision$
	362
	363	=cut
	364	*/