hlines.c

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