[imager.git] / hlines.c

#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 <tonyc@cpan.org>

=head1 REVISION

$Revision$

=cut
*/
Commit	Line	Data
92bda632	1	#include "imageri.h"
39f94030 TC	2	#include <stdlib.h>
	3
	4	#define OVERLAPPED(start1, end1, start2, end2) \
	5	(im_max((start1), (start2)) <= im_min((end1), (end2)))
	6
	7	/*
	8	=head1 NAME
	9
	10	hlines.c - implements a "class" for managing sets of horizontal line segments
	11
	12	=head1 SYNOPSIS
	13
	14	i_int_hlines hlines;
	15	// just for the specified range of y
	16	i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x);
	17	// to cover a whole image
	18	i_int_init_hlines_img(&hlines, img);
	19	// add a hline segment, merging into existing
	20	i_int_hlines_add(&hlines, y, x, width);
	21
	22	// work over the lines
	23	for (y = hlines.start; y < hlines.limit; ++y) {
	24	i_int_hline_entry *entry = hlines.entries[i];
	25	if (entry) {
	26	for (i = 0; i < entry->count; ++i) {
	27	i_int_hline_seg *seg = entry->segs+i;
	28	// do something on line y for seg->minx to x_limit
	29	}
	30	}
	31	}
	32
	33	// free it all up
	34	i_int_hlines_destroy(&hlines);
	35
	36	=head1 DESCRIPTION
	37
	38	Provides a class to manage sets of horizontal line segments. The
	39	intent is that when drawing shapes where the algorithm used might
	40	cause overlaps we can use this class to resolve the overlaps.
	41
	42	Note that segment lists are intended to remain small, if we end up
	43	with a need for longer lists we should use different structure for the
	44	segment lists.
	45
	46	=over
	47
	48	=item i_int_init_hlines
	49
	50	i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x)
	51
	52	Initializes the structure based on drawing an object within the given
	53	range. Any x or y values outside the given ranges will be ignored.
	54
	55	=cut
	56
	57	*/
	58
	59	void
	60	i_int_init_hlines(
	61	i_int_hlines *hlines,
	62	int start_y,
	63	int count_y,
	64	int start_x,
	65	int width_x
66	)
67	{
68	int bytes = count_y * sizeof(i_int_hline_entry *);
69
70	if (bytes / count_y != sizeof(i_int_hline_entry *)) {
b1e96952	71	i_fatal(3, "integer overflow calculating memory allocation\n");
39f94030 TC	72	}
	73
	74	hlines->start_y = start_y;
	75	hlines->limit_y = start_y + count_y;
	76	hlines->start_x = start_x;
	77	hlines->limit_x = start_x + width_x;
	78	hlines->entries = mymalloc(bytes);
	79	memset(hlines->entries, 0, bytes);
	80	}
	81
	82	/*
	83	=item i_int_init_hlines_img
	84
	85	i_int_init_hlines_img(img);
	86
	87	Initialize a hlines object as if we could potentially draw anywhere on
	88	the image.
	89
	90	=cut
	91	*/
	92
	93	void
	94	i_int_init_hlines_img(i_int_hlines hlines, i_img img)
	95	{
	96	i_int_init_hlines(hlines, 0, img->ysize, 0, img->xsize);
	97	}
	98
	99	/*
	100	=item i_int_hlines_add
	101
	102	i_int_hlines_add(hlines, y, x, width)
	103
	104	Add to the list, merging with existing entries.
	105
	106	=cut
	107	*/
	108
	109	void
	110	i_int_hlines_add(i_int_hlines *hlines, int y, int x, int width) {
	111	int x_limit = x + width;
	112
	113	if (width < 0) {
b1e96952	114	i_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
39f94030 TC	115	}
	116
	117	/* just return if out of range */
	118	if (y < hlines->start_y \|\| y >= hlines->limit_y)
	119	return;
	120
	121	if (x >= hlines->limit_x \|\| x_limit < hlines->start_x)
	122	return;
	123
	124	/* adjust x to our range */
	125	if (x < hlines->start_x)
	126	x = hlines->start_x;
	127	if (x_limit > hlines->limit_x)
	128	x_limit = hlines->limit_x;
	129
	130	if (x == x_limit)
	131	return;
	132
	133	if (hlines->entries[y - hlines->start_y]) {
	134	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	135	int i, found = -1;
	136
	137	for (i = 0; i < entry->count; ++i) {
	138	i_int_hline_seg *seg = entry->segs + i;
	139	if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
	140	found = i;
	141	break;
	142	}
	143	}
	144	if (found >= 0) {
	145	/* ok, we found an overlapping segment, any other overlapping
	146	segments need to be merged into the one we found */
	147	i_int_hline_seg *merge_seg = entry->segs + found;
	148
	149	/* merge in the segment we found */
	150	x = im_min(x, merge_seg->minx);
	151	x_limit = im_max(x_limit, merge_seg->x_limit);
	152
	153	/* look for other overlapping segments */
	154	/* this could be a for(), but I'm using continue */
	155	i = found + 1;
	156	while (i < entry->count) {
	157	i_int_hline_seg *seg = entry->segs + i;
	158	if (OVERLAPPED(x, x_limit, seg->minx, seg->x_limit)) {
	159	/* merge this into the current working segment, then
	160	delete it by moving the last segment (if this isn't it)
	161	into it's place */
	162	x = im_min(x, seg->minx);
	163	x_limit = im_max(x_limit, seg->x_limit);
	164	if (i < entry->count-1) {
	165	*seg = entry->segs[entry->count-1];
	166	--entry->count;
	167	continue;
	168	}
	169	else {
	170	--entry->count;
	171	break;
	172	}
	173	}
	174	++i;
	175	}
	176
	177	/* store it back */
	178	merge_seg->minx = x;
179	merge_seg->x_limit = x_limit;
180	}
181	else {
182	i_int_hline_seg *seg;
183	/* add a new segment */
184	if (entry->count == entry->alloc) {
185	/* expand it */
186	int alloc = entry->alloc * 3 / 2;
187	entry = myrealloc(entry, sizeof(i_int_hline_entry) +
188	sizeof(i_int_hline_seg) * (alloc - 1));
189	entry->alloc = alloc;
190	hlines->entries[y - hlines->start_y] = entry;
191	}
192	seg = entry->segs + entry->count++;
193	seg->minx = x;
194	seg->x_limit = x_limit;
195	}
196	}
197	else {
198	/* make a new one - start with space for 10 */
199	i_int_hline_entry *entry = mymalloc(sizeof(i_int_hline_entry) +
200	sizeof(i_int_hline_seg) * 9);
201	entry->alloc = 10;
202	entry->count = 1;
203	entry->segs[0].minx = x;
204	entry->segs[0].x_limit = x_limit;
205	hlines->entries[y - hlines->start_y] = entry;
206	}
207	}
208
209	/*
210	=item i_int_hlines_destroy
211
212	i_int_hlines_destroy(&hlines)
213
214	Releases all memory associated with the structure.
215
216	=cut
217	*/
218
219	void
220	i_int_hlines_destroy(i_int_hlines *hlines) {
221	int entry_count = hlines->limit_y - hlines->start_y;
222	int i;
223
224	for (i = 0; i < entry_count; ++i) {
225	if (hlines->entries[i])
226	myfree(hlines->entries[i]);
227	}
228	myfree(hlines->entries);
229	}
230
231	/*
232	=item i_int_hlines_fill_color
233
234	i_int_hlines_fill(im, hlines, color)
235
236	Fill the areas given by hlines with color.
237
238	=cut
239	*/
240
241	void
97ac0a96	242	i_int_hlines_fill_color(i_img im, i_int_hlines hlines, const i_color *col) {
39f94030 TC	243	int y, i, x;
	244
	245	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	246	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	247	if (entry) {
	248	for (i = 0; i < entry->count; ++i) {
	249	i_int_hline_seg *seg = entry->segs + i;
	250	for (x = seg->minx; x < seg->x_limit; ++x) {
	251	i_ppix(im, x, y, col);
	252	}
	253	}
	254	}
	255	}
	256	}
	257
	258	/*
	259	=item i_int_hlines_fill_fill
	260
	261	i_int_hlines_fill_fill(im, hlines, fill)
	262
	263	*/
	264	void
	265	i_int_hlines_fill_fill(i_img im, i_int_hlines hlines, i_fill_t *fill) {
9b1ec2b8	266	i_render r;
af070d99	267	int y, i;
39f94030	268
9b1ec2b8 TC	269	i_render_init(&r, im, im->xsize);
	270
	271	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	272	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	273	if (entry) {
	274	for (i = 0; i < entry->count; ++i) {
	275	i_int_hline_seg *seg = entry->segs + i;
	276	int width = seg->x_limit-seg->minx;
	277
	278	i_render_fill(&r, seg->minx, y, width, NULL, fill);
	279	}
	280	}
	281	}
	282	i_render_done(&r);
	283
	284	#if 1
	285	#else
39f94030 TC	286	if (im->bits == i_8_bits && fill->fill_with_color) {
	287	i_color line = mymalloc(sizeof(i_color) im->xsize);
	288	i_color *work = NULL;
	289	if (fill->combine)
	290	work = mymalloc(sizeof(i_color) * im->xsize);
	291	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	292	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	293	if (entry) {
	294	for (i = 0; i < entry->count; ++i) {
	295	i_int_hline_seg *seg = entry->segs + i;
	296	int width = seg->x_limit-seg->minx;
	297
	298	if (fill->combine) {
	299	i_glin(im, seg->minx, seg->x_limit, y, line);
	300	(fill->fill_with_color)(fill, seg->minx, y, width,
	301	im->channels, work);
	302	(fill->combine)(line, work, im->channels, width);
	303	}
	304	else {
	305	(fill->fill_with_color)(fill, seg->minx, y, width,
	306	im->channels, line);
	307	}
	308	i_plin(im, seg->minx, seg->x_limit, y, line);
	309	}
	310	}
	311	}
	312
	313	myfree(line);
	314	if (work)
	315	myfree(work);
	316	}
	317	else {
	318	i_fcolor line = mymalloc(sizeof(i_fcolor) im->xsize);
	319	i_fcolor *work = NULL;
	320	if (fill->combinef)
	321	work = mymalloc(sizeof(i_fcolor) * im->xsize);
	322	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
	323	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
	324	if (entry) {
	325	for (i = 0; i < entry->count; ++i) {
	326	i_int_hline_seg *seg = entry->segs + i;
	327	int width = seg->x_limit-seg->minx;
	328
	329	if (fill->combinef) {
	330	i_glinf(im, seg->minx, seg->x_limit, y, line);
	331	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	332	im->channels, work);
	333	(fill->combinef)(line, work, im->channels, width);
	334	}
	335	else {
	336	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
	337	im->channels, line);
	338	}
	339	i_plinf(im, seg->minx, seg->x_limit, y, line);
	340	}
	341	}
	342	}
	343
	344	myfree(line);
	345	if (work)
	346	myfree(work);
	347	}
9b1ec2b8	348	#endif
39f94030 TC	349	}
	350
	351	/*
	352	=back
	353
	354	=head1 AUTHOR
	355
5b480b14	356	Tony Cook <tonyc@cpan.org>
39f94030 TC	357
	358	=head1 REVISION
	359
	360	$Revision$
	361
	362	=cut
	363	*/