Extra ways of calling translate(), shear()
[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) {
af070d99 266 int y, i;
39f94030
TC
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
337Tony Cook <tony@imager.perl.org>
338
339=head1 REVISION
340
341$Revision$
342
343=cut
344*/