[imager.git] / hlines.c

#include "imagei.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 *)) {
    m_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) {
    m_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, 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) {
  int y, i, x;

  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);
  }
}

/*
=back

=head1 AUTHOR

Tony Cook <tony@imager.perl.org>

=head1 REVISION

$Revision$

=cut
*/
Commit	Line	Data
39f94030 TC	1	#include "imagei.h"
	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 *)) {
71	m_fatal(3, "integer overflow calculating memory allocation\n");
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) {
114	m_fatal(3, "negative width %d passed to i_int_hlines_add\n", width);
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
242	i_int_hlines_fill_color(i_img im, i_int_hlines hlines, i_color *col) {
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) {
266	int y, i, x;
267
268	if (im->bits == i_8_bits && fill->fill_with_color) {
269	i_color line = mymalloc(sizeof(i_color) im->xsize);
270	i_color *work = NULL;
271	if (fill->combine)
272	work = mymalloc(sizeof(i_color) * im->xsize);
273	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
274	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
275	if (entry) {
276	for (i = 0; i < entry->count; ++i) {
277	i_int_hline_seg *seg = entry->segs + i;
278	int width = seg->x_limit-seg->minx;
279
280	if (fill->combine) {
281	i_glin(im, seg->minx, seg->x_limit, y, line);
282	(fill->fill_with_color)(fill, seg->minx, y, width,
283	im->channels, work);
284	(fill->combine)(line, work, im->channels, width);
285	}
286	else {
287	(fill->fill_with_color)(fill, seg->minx, y, width,
288	im->channels, line);
289	}
290	i_plin(im, seg->minx, seg->x_limit, y, line);
291	}
292	}
293	}
294
295	myfree(line);
296	if (work)
297	myfree(work);
298	}
299	else {
300	i_fcolor line = mymalloc(sizeof(i_fcolor) im->xsize);
301	i_fcolor *work = NULL;
302	if (fill->combinef)
303	work = mymalloc(sizeof(i_fcolor) * im->xsize);
304	for (y = hlines->start_y; y < hlines->limit_y; ++y) {
305	i_int_hline_entry *entry = hlines->entries[y - hlines->start_y];
306	if (entry) {
307	for (i = 0; i < entry->count; ++i) {
308	i_int_hline_seg *seg = entry->segs + i;
309	int width = seg->x_limit-seg->minx;
310
311	if (fill->combinef) {
312	i_glinf(im, seg->minx, seg->x_limit, y, line);
313	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
314	im->channels, work);
315	(fill->combinef)(line, work, im->channels, width);
316	}
317	else {
318	(fill->fill_with_fcolor)(fill, seg->minx, y, width,
319	im->channels, line);
320	}
321	i_plinf(im, seg->minx, seg->x_limit, y, line);
322	}
323	}
324	}
325
326	myfree(line);
327	if (work)
328	myfree(work);
329	}
330	}
331
332	/*
333	=back
334
335	=head1 AUTHOR
336
337	Tony Cook <tony@imager.perl.org>
338
339	=head1 REVISION
340
341	$Revision$
342
343	=cut
344	*/