1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
2 /*
3 * Copyright (c) 2011 Intel Corporation
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 */
26 #include "cairoint.h"
27 #include "cairo-spans-private.h"
28 #include "cairo-error-private.h"
29
30 #include <stdlib.h>
31 #include <string.h>
32 #include <limits.h>
33
34 struct quorem {
35 int32_t quo;
36 int32_t rem;
37 };
38
39 struct edge {
40 struct edge *next, *prev;
41
42 int32_t height_left;
43 int32_t dir;
44 int32_t vertical;
45
46 int32_t dy;
47 struct quorem x;
48 struct quorem dxdy;
49 };
50
51 /* A collection of sorted and vertically clipped edges of the polygon.
52 * Edges are moved from the polygon to an active list while scan
53 * converting. */
54 struct polygon {
55 /* The vertical clip extents. */
56 int32_t ymin, ymax;
57
58 int num_edges;
59 struct edge *edges;
60
61 /* Array of edges all starting in the same bucket. An edge is put
62 * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
63 * it is added to the polygon. */
64 struct edge **y_buckets;
65
66 struct edge *y_buckets_embedded[64];
67 struct edge edges_embedded[32];
68 };
69
70 struct mono_scan_converter {
71 struct polygon polygon[1];
72
73 /* Leftmost edge on the current scan line. */
74 struct edge head, tail;
75 int is_vertical;
76
77 cairo_half_open_span_t *spans;
78 cairo_half_open_span_t spans_embedded[64];
79 int num_spans;
80
81 /* Clip box. */
82 int32_t xmin, xmax;
83 int32_t ymin, ymax;
84 };
85
86 #define I(x) _cairo_fixed_integer_round_down(x)
87
88 /* Compute the floored division a/b. Assumes / and % perform symmetric
89 * division. */
90 inline static struct quorem
floored_divrem(int a,int b)91 floored_divrem(int a, int b)
92 {
93 struct quorem qr;
94 qr.quo = a/b;
95 qr.rem = a%b;
96 if ((a^b)<0 && qr.rem) {
97 qr.quo -= 1;
98 qr.rem += b;
99 }
100 return qr;
101 }
102
103 /* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
104 * division. */
105 static struct quorem
floored_muldivrem(int x,int a,int b)106 floored_muldivrem(int x, int a, int b)
107 {
108 struct quorem qr;
109 long long xa = (long long)x*a;
110 qr.quo = xa/b;
111 qr.rem = xa%b;
112 if ((xa>=0) != (b>=0) && qr.rem) {
113 qr.quo -= 1;
114 qr.rem += b;
115 }
116 return qr;
117 }
118
119 static cairo_status_t
polygon_init(struct polygon * polygon,int ymin,int ymax)120 polygon_init (struct polygon *polygon, int ymin, int ymax)
121 {
122 unsigned h = ymax - ymin + 1;
123
124 polygon->y_buckets = polygon->y_buckets_embedded;
125 if (h > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
126 polygon->y_buckets = _cairo_malloc_ab (h, sizeof (struct edge *));
127 if (unlikely (NULL == polygon->y_buckets))
128 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
129 }
130 memset (polygon->y_buckets, 0, h * sizeof (struct edge *));
131 polygon->y_buckets[h-1] = (void *)-1;
132
133 polygon->ymin = ymin;
134 polygon->ymax = ymax;
135 return CAIRO_STATUS_SUCCESS;
136 }
137
138 static void
polygon_fini(struct polygon * polygon)139 polygon_fini (struct polygon *polygon)
140 {
141 if (polygon->y_buckets != polygon->y_buckets_embedded)
142 free (polygon->y_buckets);
143
144 if (polygon->edges != polygon->edges_embedded)
145 free (polygon->edges);
146 }
147
148 static void
_polygon_insert_edge_into_its_y_bucket(struct polygon * polygon,struct edge * e,int y)149 _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
150 struct edge *e,
151 int y)
152 {
153 struct edge **ptail = &polygon->y_buckets[y - polygon->ymin];
154 if (*ptail)
155 (*ptail)->prev = e;
156 e->next = *ptail;
157 e->prev = NULL;
158 *ptail = e;
159 }
160
161 inline static void
polygon_add_edge(struct polygon * polygon,const cairo_edge_t * edge)162 polygon_add_edge (struct polygon *polygon,
163 const cairo_edge_t *edge)
164 {
165 struct edge *e;
166 cairo_fixed_t dx;
167 cairo_fixed_t dy;
168 int y, ytop, ybot;
169 int ymin = polygon->ymin;
170 int ymax = polygon->ymax;
171
172 y = I(edge->top);
173 ytop = MAX(y, ymin);
174
175 y = I(edge->bottom);
176 ybot = MIN(y, ymax);
177
178 if (ybot <= ytop)
179 return;
180
181 e = polygon->edges + polygon->num_edges++;
182 e->height_left = ybot - ytop;
183 e->dir = edge->dir;
184
185 dx = edge->line.p2.x - edge->line.p1.x;
186 dy = edge->line.p2.y - edge->line.p1.y;
187
188 if (dx == 0) {
189 e->vertical = TRUE;
190 e->x.quo = edge->line.p1.x;
191 e->x.rem = 0;
192 e->dxdy.quo = 0;
193 e->dxdy.rem = 0;
194 e->dy = 0;
195 } else {
196 e->vertical = FALSE;
197 e->dxdy = floored_muldivrem (dx, CAIRO_FIXED_ONE, dy);
198 e->dy = dy;
199
200 e->x = floored_muldivrem (ytop * CAIRO_FIXED_ONE + CAIRO_FIXED_FRAC_MASK/2 - edge->line.p1.y,
201 dx, dy);
202 e->x.quo += edge->line.p1.x;
203 }
204 e->x.rem -= dy;
205
206 _polygon_insert_edge_into_its_y_bucket (polygon, e, ytop);
207 }
208
209 static struct edge *
merge_sorted_edges(struct edge * head_a,struct edge * head_b)210 merge_sorted_edges (struct edge *head_a, struct edge *head_b)
211 {
212 struct edge *head, **next, *prev;
213 int32_t x;
214
215 prev = head_a->prev;
216 next = &head;
217 if (head_a->x.quo <= head_b->x.quo) {
218 head = head_a;
219 } else {
220 head = head_b;
221 head_b->prev = prev;
222 goto start_with_b;
223 }
224
225 do {
226 x = head_b->x.quo;
227 while (head_a != NULL && head_a->x.quo <= x) {
228 prev = head_a;
229 next = &head_a->next;
230 head_a = head_a->next;
231 }
232
233 head_b->prev = prev;
234 *next = head_b;
235 if (head_a == NULL)
236 return head;
237
238 start_with_b:
239 x = head_a->x.quo;
240 while (head_b != NULL && head_b->x.quo <= x) {
241 prev = head_b;
242 next = &head_b->next;
243 head_b = head_b->next;
244 }
245
246 head_a->prev = prev;
247 *next = head_a;
248 if (head_b == NULL)
249 return head;
250 } while (1);
251 }
252
253 static struct edge *
sort_edges(struct edge * list,unsigned int level,struct edge ** head_out)254 sort_edges (struct edge *list,
255 unsigned int level,
256 struct edge **head_out)
257 {
258 struct edge *head_other, *remaining;
259 unsigned int i;
260
261 head_other = list->next;
262
263 if (head_other == NULL) {
264 *head_out = list;
265 return NULL;
266 }
267
268 remaining = head_other->next;
269 if (list->x.quo <= head_other->x.quo) {
270 *head_out = list;
271 head_other->next = NULL;
272 } else {
273 *head_out = head_other;
274 head_other->prev = list->prev;
275 head_other->next = list;
276 list->prev = head_other;
277 list->next = NULL;
278 }
279
280 for (i = 0; i < level && remaining; i++) {
281 remaining = sort_edges (remaining, i, &head_other);
282 *head_out = merge_sorted_edges (*head_out, head_other);
283 }
284
285 return remaining;
286 }
287
288 static struct edge *
merge_unsorted_edges(struct edge * head,struct edge * unsorted)289 merge_unsorted_edges (struct edge *head, struct edge *unsorted)
290 {
291 sort_edges (unsorted, UINT_MAX, &unsorted);
292 return merge_sorted_edges (head, unsorted);
293 }
294
295 inline static void
active_list_merge_edges(struct mono_scan_converter * c,struct edge * edges)296 active_list_merge_edges (struct mono_scan_converter *c, struct edge *edges)
297 {
298 struct edge *e;
299
300 for (e = edges; c->is_vertical && e; e = e->next)
301 c->is_vertical = e->vertical;
302
303 c->head.next = merge_unsorted_edges (c->head.next, edges);
304 }
305
306 inline static void
add_span(struct mono_scan_converter * c,int x1,int x2)307 add_span (struct mono_scan_converter *c, int x1, int x2)
308 {
309 int n;
310
311 if (x1 < c->xmin)
312 x1 = c->xmin;
313 if (x2 > c->xmax)
314 x2 = c->xmax;
315 if (x2 <= x1)
316 return;
317
318 n = c->num_spans++;
319 c->spans[n].x = x1;
320 c->spans[n].coverage = 255;
321
322 n = c->num_spans++;
323 c->spans[n].x = x2;
324 c->spans[n].coverage = 0;
325 }
326
327 inline static void
row(struct mono_scan_converter * c,unsigned int mask)328 row (struct mono_scan_converter *c, unsigned int mask)
329 {
330 struct edge *edge = c->head.next;
331 int xstart = INT_MIN, prev_x = INT_MIN;
332 int winding = 0;
333
334 c->num_spans = 0;
335 while (&c->tail != edge) {
336 struct edge *next = edge->next;
337 int xend = I(edge->x.quo);
338
339 if (--edge->height_left) {
340 if (!edge->vertical) {
341 edge->x.quo += edge->dxdy.quo;
342 edge->x.rem += edge->dxdy.rem;
343 if (edge->x.rem >= 0) {
344 ++edge->x.quo;
345 edge->x.rem -= edge->dy;
346 }
347 }
348
349 if (edge->x.quo < prev_x) {
350 struct edge *pos = edge->prev;
351 pos->next = next;
352 next->prev = pos;
353 do {
354 pos = pos->prev;
355 } while (edge->x.quo < pos->x.quo);
356 pos->next->prev = edge;
357 edge->next = pos->next;
358 edge->prev = pos;
359 pos->next = edge;
360 } else
361 prev_x = edge->x.quo;
362 } else {
363 edge->prev->next = next;
364 next->prev = edge->prev;
365 }
366
367 winding += edge->dir;
368 if ((winding & mask) == 0) {
369 if (I(next->x.quo) > xend + 1) {
370 add_span (c, xstart, xend);
371 xstart = INT_MIN;
372 }
373 } else if (xstart == INT_MIN)
374 xstart = xend;
375
376 edge = next;
377 }
378 }
379
dec(struct edge * e,int h)380 inline static void dec (struct edge *e, int h)
381 {
382 e->height_left -= h;
383 if (e->height_left == 0) {
384 e->prev->next = e->next;
385 e->next->prev = e->prev;
386 }
387 }
388
389 static cairo_status_t
_mono_scan_converter_init(struct mono_scan_converter * c,int xmin,int ymin,int xmax,int ymax)390 _mono_scan_converter_init(struct mono_scan_converter *c,
391 int xmin, int ymin,
392 int xmax, int ymax)
393 {
394 cairo_status_t status;
395 int max_num_spans;
396
397 status = polygon_init (c->polygon, ymin, ymax);
398 if (unlikely (status))
399 return status;
400
401 max_num_spans = xmax - xmin + 1;
402 if (max_num_spans > ARRAY_LENGTH(c->spans_embedded)) {
403 c->spans = _cairo_malloc_ab (max_num_spans,
404 sizeof (cairo_half_open_span_t));
405 if (unlikely (c->spans == NULL)) {
406 polygon_fini (c->polygon);
407 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
408 }
409 } else
410 c->spans = c->spans_embedded;
411
412 c->xmin = xmin;
413 c->xmax = xmax;
414 c->ymin = ymin;
415 c->ymax = ymax;
416
417 c->head.vertical = 1;
418 c->head.height_left = INT_MAX;
419 c->head.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MIN));
420 c->head.prev = NULL;
421 c->head.next = &c->tail;
422 c->tail.prev = &c->head;
423 c->tail.next = NULL;
424 c->tail.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MAX));
425 c->tail.height_left = INT_MAX;
426 c->tail.vertical = 1;
427
428 c->is_vertical = 1;
429 return CAIRO_STATUS_SUCCESS;
430 }
431
432 static void
_mono_scan_converter_fini(struct mono_scan_converter * self)433 _mono_scan_converter_fini(struct mono_scan_converter *self)
434 {
435 if (self->spans != self->spans_embedded)
436 free (self->spans);
437
438 polygon_fini(self->polygon);
439 }
440
441 static cairo_status_t
mono_scan_converter_allocate_edges(struct mono_scan_converter * c,int num_edges)442 mono_scan_converter_allocate_edges(struct mono_scan_converter *c,
443 int num_edges)
444
445 {
446 c->polygon->num_edges = 0;
447 c->polygon->edges = c->polygon->edges_embedded;
448 if (num_edges > ARRAY_LENGTH (c->polygon->edges_embedded)) {
449 c->polygon->edges = _cairo_malloc_ab (num_edges, sizeof (struct edge));
450 if (unlikely (c->polygon->edges == NULL))
451 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
452 }
453
454 return CAIRO_STATUS_SUCCESS;
455 }
456
457 static void
mono_scan_converter_add_edge(struct mono_scan_converter * c,const cairo_edge_t * edge)458 mono_scan_converter_add_edge (struct mono_scan_converter *c,
459 const cairo_edge_t *edge)
460 {
461 polygon_add_edge (c->polygon, edge);
462 }
463
464 static void
step_edges(struct mono_scan_converter * c,int count)465 step_edges (struct mono_scan_converter *c, int count)
466 {
467 struct edge *edge;
468
469 for (edge = c->head.next; edge != &c->tail; edge = edge->next) {
470 edge->height_left -= count;
471 if (! edge->height_left) {
472 edge->prev->next = edge->next;
473 edge->next->prev = edge->prev;
474 }
475 }
476 }
477
478 static cairo_status_t
mono_scan_converter_render(struct mono_scan_converter * c,unsigned int winding_mask,cairo_span_renderer_t * renderer)479 mono_scan_converter_render(struct mono_scan_converter *c,
480 unsigned int winding_mask,
481 cairo_span_renderer_t *renderer)
482 {
483 struct polygon *polygon = c->polygon;
484 int i, j, h = c->ymax - c->ymin;
485 cairo_status_t status;
486
487 for (i = 0; i < h; i = j) {
488 j = i + 1;
489
490 if (polygon->y_buckets[i])
491 active_list_merge_edges (c, polygon->y_buckets[i]);
492
493 if (c->is_vertical) {
494 int min_height;
495 struct edge *e;
496
497 e = c->head.next;
498 min_height = e->height_left;
499 while (e != &c->tail) {
500 if (e->height_left < min_height)
501 min_height = e->height_left;
502 e = e->next;
503 }
504
505 while (--min_height >= 1 && polygon->y_buckets[j] == NULL)
506 j++;
507 if (j != i + 1)
508 step_edges (c, j - (i + 1));
509 }
510
511 row (c, winding_mask);
512 if (c->num_spans) {
513 status = renderer->render_rows (renderer, c->ymin+i, j-i,
514 c->spans, c->num_spans);
515 if (unlikely (status))
516 return status;
517 }
518
519 /* XXX recompute after dropping edges? */
520 if (c->head.next == &c->tail)
521 c->is_vertical = 1;
522 }
523
524 return CAIRO_STATUS_SUCCESS;
525 }
526
527 struct _cairo_mono_scan_converter {
528 cairo_scan_converter_t base;
529
530 struct mono_scan_converter converter[1];
531 cairo_fill_rule_t fill_rule;
532 };
533
534 typedef struct _cairo_mono_scan_converter cairo_mono_scan_converter_t;
535
536 static void
_cairo_mono_scan_converter_destroy(void * converter)537 _cairo_mono_scan_converter_destroy (void *converter)
538 {
539 cairo_mono_scan_converter_t *self = converter;
540 _mono_scan_converter_fini (self->converter);
541 free(self);
542 }
543
544 cairo_status_t
_cairo_mono_scan_converter_add_polygon(void * converter,const cairo_polygon_t * polygon)545 _cairo_mono_scan_converter_add_polygon (void *converter,
546 const cairo_polygon_t *polygon)
547 {
548 cairo_mono_scan_converter_t *self = converter;
549 cairo_status_t status;
550 int i;
551
552 #if 0
553 FILE *file = fopen ("polygon.txt", "w");
554 _cairo_debug_print_polygon (file, polygon);
555 fclose (file);
556 #endif
557
558 status = mono_scan_converter_allocate_edges (self->converter,
559 polygon->num_edges);
560 if (unlikely (status))
561 return status;
562
563 for (i = 0; i < polygon->num_edges; i++)
564 mono_scan_converter_add_edge (self->converter, &polygon->edges[i]);
565
566 return CAIRO_STATUS_SUCCESS;
567 }
568
569 static cairo_status_t
_cairo_mono_scan_converter_generate(void * converter,cairo_span_renderer_t * renderer)570 _cairo_mono_scan_converter_generate (void *converter,
571 cairo_span_renderer_t *renderer)
572 {
573 cairo_mono_scan_converter_t *self = converter;
574
575 return mono_scan_converter_render (self->converter,
576 self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
577 renderer);
578 }
579
580 cairo_scan_converter_t *
_cairo_mono_scan_converter_create(int xmin,int ymin,int xmax,int ymax,cairo_fill_rule_t fill_rule)581 _cairo_mono_scan_converter_create (int xmin,
582 int ymin,
583 int xmax,
584 int ymax,
585 cairo_fill_rule_t fill_rule)
586 {
587 cairo_mono_scan_converter_t *self;
588 cairo_status_t status;
589
590 self = _cairo_malloc (sizeof(struct _cairo_mono_scan_converter));
591 if (unlikely (self == NULL)) {
592 status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
593 goto bail_nomem;
594 }
595
596 self->base.destroy = _cairo_mono_scan_converter_destroy;
597 self->base.generate = _cairo_mono_scan_converter_generate;
598
599 status = _mono_scan_converter_init (self->converter,
600 xmin, ymin, xmax, ymax);
601 if (unlikely (status))
602 goto bail;
603
604 self->fill_rule = fill_rule;
605
606 return &self->base;
607
608 bail:
609 self->base.destroy(&self->base);
610 bail_nomem:
611 return _cairo_scan_converter_create_in_error (status);
612 }
613