0.84 release
[imager.git] / hlines.c
CommitLineData
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
10hlines.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
38Provides a class to manage sets of horizontal line segments. The
39intent is that when drawing shapes where the algorithm used might
40cause overlaps we can use this class to resolve the overlaps.
41
42Note that segment lists are intended to remain small, if we end up
43with a need for longer lists we should use different structure for the
44segment lists.
45
46=over
47
48=item i_int_init_hlines
49
50i_int_init_hlines(&hlines, start_y, count_y, start_x, width_x)
51
52Initializes the structure based on drawing an object within the given
53range. Any x or y values outside the given ranges will be ignored.
54
55=cut
56
57*/
58
59void
60i_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
85i_int_init_hlines_img(img);
86
87Initialize a hlines object as if we could potentially draw anywhere on
88the image.
89
90=cut
91*/
92
93void
94i_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
102i_int_hlines_add(hlines, y, x, width)
103
104Add to the list, merging with existing entries.
105
106=cut
107*/
108
109void
110i_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
212i_int_hlines_destroy(&hlines)
213
214Releases all memory associated with the structure.
215
216=cut
217*/
218
219void
220i_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
234i_int_hlines_fill(im, hlines, color)
235
236Fill the areas given by hlines with color.
237
238=cut
239*/
240
241void
97ac0a96 242i_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
261i_int_hlines_fill_fill(im, hlines, fill)
262
263*/
264void
265i_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 356Tony Cook <tonyc@cpan.org>
39f94030
TC
357
358=head1 REVISION
359
360$Revision$
361
362=cut
363*/