1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
2 /* glitter-paths - polygon scan converter
4 * Copyright (c) 2008 M Joonas Pihlaja
5 * Copyright (c) 2007 David Turner
7 * Permission is hereby granted, free of charge, to any person
8 * obtaining a copy of this software and associated documentation
9 * files (the "Software"), to deal in the Software without
10 * restriction, including without limitation the rights to use,
11 * copy, modify, merge, publish, distribute, sublicense, and/or sell
12 * copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
21 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
23 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
24 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
26 * OTHER DEALINGS IN THE SOFTWARE.
28 /* This is the Glitter paths scan converter incorporated into cairo.
29 * The source is from commit 734c53237a867a773640bd5b64816249fa1730f8
32 * http://gitweb.freedesktop.org/?p=users/joonas/glitter-paths
34 /* Glitter-paths is a stand alone polygon rasteriser derived from
35 * David Turner's reimplementation of Tor Anderssons's 15x17
36 * supersampling rasteriser from the Apparition graphics library. The
37 * main new feature here is cheaply choosing per-scan line between
38 * doing fully analytical coverage computation for an entire row at a
39 * time vs. using a supersampling approach.
41 * David Turner's code can be found at
43 * http://david.freetype.org/rasterizer-shootout/raster-comparison-20070813.tar.bz2
45 * In particular this file incorporates large parts of ftgrays_tor10.h
46 * from raster-comparison-20070813.tar.bz2
50 * A scan converter's basic purpose to take polygon edges and convert
51 * them into an RLE compressed A8 mask. This one works in two phases:
52 * gathering edges and generating spans.
54 * 1) As the user feeds the scan converter edges they are vertically
55 * clipped and bucketted into a _polygon_ data structure. The edges
56 * are also snapped from the user's coordinates to the subpixel grid
57 * coordinates used during scan conversion.
65 * 2) Generating spans works by performing a vertical sweep of pixel
66 * rows from top to bottom and maintaining an _active_list_ of edges
67 * that intersect the row. From the active list the fill rule
68 * determines which edges are the left and right edges of the start of
69 * each span, and their contribution is then accumulated into a pixel
70 * coverage list (_cell_list_) as coverage deltas. Once the coverage
71 * deltas of all edges are known we can form spans of constant pixel
72 * coverage by summing the deltas during a traversal of the cell list.
73 * At the end of a pixel row the cell list is sent to a coverage
74 * blitter for rendering to some target surface.
76 * The pixel coverages are computed by either supersampling the row
77 * and box filtering a mono rasterisation, or by computing the exact
78 * coverages of edges in the active list. The supersampling method is
79 * used whenever some edge starts or stops within the row or there are
80 * edge intersections in the row.
82 * polygon bucket for \
85 * | activate new edges | Repeat GRID_Y times if we
86 * V \ are supersampling this row,
87 * active list / or just once if we're computing
88 * | | analytical coverage.
91 * pixel coverage list /
97 #include "cairo-spans-private.h"
98 #include "cairo-error-private.h"
106 /* The input coordinate scale and the rasterisation grid scales. */
107 #define GLITTER_INPUT_BITS CAIRO_FIXED_FRAC_BITS
108 #define GRID_X_BITS CAIRO_FIXED_FRAC_BITS
111 /* Set glitter up to use a cairo span renderer to do the coverage
116 /*-------------------------------------------------------------------------
120 /* "Input scaled" numbers are fixed precision reals with multiplier
121 * 2**GLITTER_INPUT_BITS. Input coordinates are given to glitter as
122 * pixel scaled numbers. These get converted to the internal grid
123 * scaled numbers as soon as possible. Internal overflow is possible
124 * if GRID_X/Y inside glitter-paths.c is larger than
125 * 1<<GLITTER_INPUT_BITS. */
126 #ifndef GLITTER_INPUT_BITS
127 # define GLITTER_INPUT_BITS 8
129 #define GLITTER_INPUT_SCALE (1<<GLITTER_INPUT_BITS)
130 typedef int glitter_input_scaled_t
;
132 /* Opaque type for scan converting. */
133 typedef struct glitter_scan_converter glitter_scan_converter_t
;
135 /*-------------------------------------------------------------------------
136 * glitter-paths.c: Implementation internal types
142 /* All polygon coordinates are snapped onto a subsample grid. "Grid
143 * scaled" numbers are fixed precision reals with multiplier GRID_X or
145 typedef int grid_scaled_t
;
146 typedef int grid_scaled_x_t
;
147 typedef int grid_scaled_y_t
;
149 /* Default x/y scale factors.
150 * You can either define GRID_X/Y_BITS to get a power-of-two scale
151 * or define GRID_X/Y separately. */
152 #if !defined(GRID_X) && !defined(GRID_X_BITS)
153 # define GRID_X_BITS 8
155 #if !defined(GRID_Y) && !defined(GRID_Y_BITS)
159 /* Use GRID_X/Y_BITS to define GRID_X/Y if they're available. */
161 # define GRID_X (1 << GRID_X_BITS)
164 # define GRID_Y (1 << GRID_Y_BITS)
167 /* The GRID_X_TO_INT_FRAC macro splits a grid scaled coordinate into
168 * integer and fractional parts. The integer part is floored. */
169 #if defined(GRID_X_TO_INT_FRAC)
171 #elif defined(GRID_X_BITS)
172 # define GRID_X_TO_INT_FRAC(x, i, f) \
173 _GRID_TO_INT_FRAC_shift(x, i, f, GRID_X_BITS)
175 # define GRID_X_TO_INT_FRAC(x, i, f) \
176 _GRID_TO_INT_FRAC_general(x, i, f, GRID_X)
179 #define _GRID_TO_INT_FRAC_general(t, i, f, m) do { \
188 #define _GRID_TO_INT_FRAC_shift(t, i, f, b) do { \
189 (f) = (t) & ((1 << (b)) - 1); \
193 /* A grid area is a real in [0,1] scaled by 2*GRID_X*GRID_Y. We want
194 * to be able to represent exactly areas of subpixel trapezoids whose
195 * vertices are given in grid scaled coordinates. The scale factor
196 * comes from needing to accurately represent the area 0.5*dx*dy of a
197 * triangle with base dx and height dy in grid scaled numbers. */
198 typedef int grid_area_t
;
199 #define GRID_XY (2*GRID_X*GRID_Y) /* Unit area on the grid. */
201 /* GRID_AREA_TO_ALPHA(area): map [0,GRID_XY] to [0,255]. */
203 # define GRID_AREA_TO_ALPHA(c) (((c)+1) >> 1)
205 # define GRID_AREA_TO_ALPHA(c) (c)
207 # define GRID_AREA_TO_ALPHA(c) (((c) << 2) | -(((c) & 0x40) >> 6))
209 # define GRID_AREA_TO_ALPHA(c) ((((c) << 1) | -((c) >> 7)) & 255)
211 # define GRID_AREA_TO_ALPHA(c) (((c) | -((c) >> 8)) & 255)
213 # define GRID_AREA_TO_ALPHA(c) (((c) << 4) + (c))
214 #elif GRID_XY == 2*256*15
215 # define GRID_AREA_TO_ALPHA(c) (((c) + ((c)<<4) + 256) >> 9)
217 # define GRID_AREA_TO_ALPHA(c) (((c)*255 + GRID_XY/2) / GRID_XY)
220 #define UNROLL3(x) x x x
227 /* Header for a chunk of memory in a memory pool. */
229 /* # bytes used in this chunk. */
232 /* # bytes total in this chunk */
235 /* Pointer to the previous chunk or %NULL if this is the sentinel
236 * chunk in the pool header. */
237 struct _pool_chunk
*prev_chunk
;
239 /* Actual data starts here. Well aligned for pointers. */
242 /* A memory pool. This is supposed to be embedded on the stack or
243 * within some other structure. It may optionally be followed by an
244 * embedded array from which requests are fulfilled until
245 * malloc needs to be called to allocate a first real chunk. */
247 /* Chunk we're allocating from. */
248 struct _pool_chunk
*current
;
252 /* Free list of previously allocated chunks. All have >= default
254 struct _pool_chunk
*first_free
;
256 /* The default capacity of a chunk. */
257 size_t default_capacity
;
259 /* Header for the sentinel chunk. Directly following the pool
260 * struct should be some space for embedded elements from which
261 * the sentinel chunk allocates from. */
262 struct _pool_chunk sentinel
[1];
265 /* A polygon edge. */
267 /* Next in y-bucket or active list. */
270 /* Current x coordinate while the edge is on the active
271 * list. Initialised to the x coordinate of the top of the
272 * edge. The quotient is in grid_scaled_x_t units and the
273 * remainder is mod dy in grid_scaled_y_t units.*/
276 /* Advance of the current x when moving down a subsample line. */
279 /* Advance of the current x when moving down a full pixel
280 * row. Only initialised when the height of the edge is large
281 * enough that there's a chance the edge could be stepped by a
282 * full row's worth of subsample rows at a time. */
283 struct quorem dxdy_full
;
285 /* The clipped y of the top of the edge. */
286 grid_scaled_y_t ytop
;
288 /* y2-y1 after orienting the edge downwards. */
291 /* Number of subsample rows remaining to scan convert of this
293 grid_scaled_y_t height_left
;
295 /* Original sign of the edge: +1 for downwards, -1 for upwards
302 /* Number of subsample rows per y-bucket. Must be GRID_Y. */
303 #define EDGE_Y_BUCKET_HEIGHT GRID_Y
305 #define EDGE_Y_BUCKET_INDEX(y, ymin) (((y) - (ymin))/EDGE_Y_BUCKET_HEIGHT)
307 /* A collection of sorted and vertically clipped edges of the polygon.
308 * Edges are moved from the polygon to an active list while scan
311 /* The vertical clip extents. */
312 grid_scaled_y_t ymin
, ymax
;
314 /* Array of edges all starting in the same bucket. An edge is put
315 * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
316 * it is added to the polygon. */
317 struct edge
**y_buckets
;
318 struct edge
*y_buckets_embedded
[64];
322 struct edge embedded
[32];
326 /* A cell records the effect on pixel coverage of polygon edges
327 * passing through a pixel. It contains two accumulators of pixel
330 * Consider the effects of a polygon edge on the coverage of a pixel
331 * it intersects and that of the following one. The coverage of the
332 * following pixel is the height of the edge multiplied by the width
333 * of the pixel, and the coverage of the pixel itself is the area of
334 * the trapezoid formed by the edge and the right side of the pixel.
336 * +-----------------------+-----------------------+
339 * |_______________________|_______________________|
340 * | \...................|.......................|\
341 * | \..................|.......................| |
342 * | \.................|.......................| |
343 * | \....covered.....|.......................| |
344 * | \....area.......|.......................| } covered height
345 * | \..............|.......................| |
346 * |uncovered\.............|.......................| |
347 * | area \............|.......................| |
348 * |___________\...........|.......................|/
352 * +-----------------------+-----------------------+
354 * Since the coverage of the following pixel will always be a multiple
355 * of the width of the pixel, we can store the height of the covered
356 * area instead. The coverage of the pixel itself is the total
357 * coverage minus the area of the uncovered area to the left of the
358 * edge. As it's faster to compute the uncovered area we only store
359 * that and subtract it from the total coverage later when forming
362 * The heights and areas are signed, with left edges of the polygon
363 * having positive sign and right edges having negative sign. When
364 * two edges intersect they swap their left/rightness so their
365 * contribution above and below the intersection point must be
366 * computed separately. */
370 grid_area_t uncovered_area
;
371 grid_scaled_y_t covered_height
;
372 grid_scaled_y_t clipped_height
;
375 /* A cell list represents the scan line sparsely as cells ordered by
376 * ascending x. It is geared towards scanning the cells in order
377 * using an internal cursor. */
380 struct cell head
, tail
;
382 /* Cursor state for iterating through the cell list. */
385 /* Cells in the cell list are owned by the cell list and are
386 * allocated from this pool. */
389 struct cell embedded
[32];
398 /* The active list contains edges in the current scan line ordered by
399 * the x-coordinate of the intercept of the edge and the scan line. */
401 /* Leftmost edge on the current scan line. */
404 /* A lower bound on the height of the active edges is used to
405 * estimate how soon some active edge ends. We can't advance the
406 * scan conversion by a full pixel row if an edge ends somewhere
408 grid_scaled_y_t min_height
;
411 struct glitter_scan_converter
{
412 struct polygon polygon
[1];
413 struct active_list active
[1];
414 struct cell_list coverages
[1];
417 grid_scaled_y_t ymin
, ymax
;
420 /* Compute the floored division a/b. Assumes / and % perform symmetric
422 inline static struct quorem
423 floored_divrem(int a
, int b
)
428 if ((a
^b
)<0 && qr
.rem
) {
435 /* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
438 floored_muldivrem(int x
, int a
, int b
)
441 long long xa
= (long long)x
*a
;
444 if ((xa
>=0) != (b
>=0) && qr
.rem
) {
451 static struct _pool_chunk
*
453 struct _pool_chunk
*p
,
454 struct _pool_chunk
*prev_chunk
,
457 p
->prev_chunk
= prev_chunk
;
459 p
->capacity
= capacity
;
463 static struct _pool_chunk
*
464 _pool_chunk_create(struct pool
*pool
, size_t size
)
466 struct _pool_chunk
*p
;
468 p
= malloc(size
+ sizeof(struct _pool_chunk
));
469 if (unlikely (NULL
== p
))
470 longjmp (*pool
->jmp
, _cairo_error (CAIRO_STATUS_NO_MEMORY
));
472 return _pool_chunk_init(p
, pool
->current
, size
);
476 pool_init(struct pool
*pool
,
478 size_t default_capacity
,
479 size_t embedded_capacity
)
482 pool
->current
= pool
->sentinel
;
483 pool
->first_free
= NULL
;
484 pool
->default_capacity
= default_capacity
;
485 _pool_chunk_init(pool
->sentinel
, NULL
, embedded_capacity
);
489 pool_fini(struct pool
*pool
)
491 struct _pool_chunk
*p
= pool
->current
;
494 struct _pool_chunk
*prev
= p
->prev_chunk
;
495 if (p
!= pool
->sentinel
)
499 p
= pool
->first_free
;
500 pool
->first_free
= NULL
;
504 /* Satisfy an allocation by first allocating a new large enough chunk
505 * and adding it to the head of the pool's chunk list. This function
506 * is called as a fallback if pool_alloc() couldn't do a quick
507 * allocation from the current chunk in the pool. */
509 _pool_alloc_from_new_chunk(
513 struct _pool_chunk
*chunk
;
517 /* If the allocation is smaller than the default chunk size then
518 * try getting a chunk off the free list. Force alloc of a new
519 * chunk for large requests. */
522 if (size
< pool
->default_capacity
) {
523 capacity
= pool
->default_capacity
;
524 chunk
= pool
->first_free
;
526 pool
->first_free
= chunk
->prev_chunk
;
527 _pool_chunk_init(chunk
, pool
->current
, chunk
->capacity
);
532 chunk
= _pool_chunk_create (pool
, capacity
);
533 pool
->current
= chunk
;
535 obj
= ((unsigned char*)chunk
+ sizeof(*chunk
) + chunk
->size
);
540 /* Allocate size bytes from the pool. The first allocated address
541 * returned from a pool is aligned to sizeof(void*). Subsequent
542 * addresses will maintain alignment as long as multiples of void* are
543 * allocated. Returns the address of a new memory area or %NULL on
544 * allocation failures. The pool retains ownership of the returned
547 pool_alloc (struct pool
*pool
, size_t size
)
549 struct _pool_chunk
*chunk
= pool
->current
;
551 if (size
<= chunk
->capacity
- chunk
->size
) {
552 void *obj
= ((unsigned char*)chunk
+ sizeof(*chunk
) + chunk
->size
);
556 return _pool_alloc_from_new_chunk(pool
, size
);
560 /* Relinquish all pool_alloced memory back to the pool. */
562 pool_reset (struct pool
*pool
)
564 /* Transfer all used chunks to the chunk free list. */
565 struct _pool_chunk
*chunk
= pool
->current
;
566 if (chunk
!= pool
->sentinel
) {
567 while (chunk
->prev_chunk
!= pool
->sentinel
) {
568 chunk
= chunk
->prev_chunk
;
570 chunk
->prev_chunk
= pool
->first_free
;
571 pool
->first_free
= pool
->current
;
573 /* Reset the sentinel as the current chunk. */
574 pool
->current
= pool
->sentinel
;
575 pool
->sentinel
->size
= 0;
578 /* Rewinds the cell list's cursor to the beginning. After rewinding
579 * we're good to cell_list_find() the cell any x coordinate. */
581 cell_list_rewind (struct cell_list
*cells
)
583 cells
->cursor
= &cells
->head
;
586 /* Rewind the cell list if its cursor has been advanced past x. */
588 cell_list_maybe_rewind (struct cell_list
*cells
, int x
)
590 struct cell
*tail
= cells
->cursor
;
592 cell_list_rewind (cells
);
596 cell_list_init(struct cell_list
*cells
, jmp_buf *jmp
)
598 pool_init(cells
->cell_pool
.base
, jmp
,
599 256*sizeof(struct cell
),
600 sizeof(cells
->cell_pool
.embedded
));
601 cells
->tail
.next
= NULL
;
602 cells
->tail
.x
= INT_MAX
;
603 cells
->head
.x
= INT_MIN
;
604 cells
->head
.next
= &cells
->tail
;
605 cell_list_rewind (cells
);
609 cell_list_fini(struct cell_list
*cells
)
611 pool_fini (cells
->cell_pool
.base
);
614 /* Empty the cell list. This is called at the start of every pixel
617 cell_list_reset (struct cell_list
*cells
)
619 cell_list_rewind (cells
);
620 cells
->head
.next
= &cells
->tail
;
621 pool_reset (cells
->cell_pool
.base
);
625 cell_list_alloc (struct cell_list
*cells
,
631 cell
= pool_alloc (cells
->cell_pool
.base
, sizeof (struct cell
));
632 cell
->next
= tail
->next
;
635 cell
->uncovered_area
= 0;
636 cell
->covered_height
= 0;
637 cell
->clipped_height
= 0;
641 /* Find a cell at the given x-coordinate. Returns %NULL if a new cell
642 * needed to be allocated but couldn't be. Cells must be found with
643 * non-decreasing x-coordinate until the cell list is rewound using
644 * cell_list_rewind(). Ownership of the returned cell is retained by
646 inline static struct cell
*
647 cell_list_find (struct cell_list
*cells
, int x
)
649 struct cell
*tail
= cells
->cursor
;
653 if (tail
->next
->x
> x
)
660 tail
= cell_list_alloc (cells
, tail
, x
);
661 return cells
->cursor
= tail
;
665 /* Find two cells at x1 and x2. This is exactly equivalent
668 * pair.cell1 = cell_list_find(cells, x1);
669 * pair.cell2 = cell_list_find(cells, x2);
671 * except with less function call overhead. */
672 inline static struct cell_pair
673 cell_list_find_pair(struct cell_list
*cells
, int x1
, int x2
)
675 struct cell_pair pair
;
677 pair
.cell1
= cells
->cursor
;
680 if (pair
.cell1
->next
->x
> x1
)
682 pair
.cell1
= pair
.cell1
->next
;
685 if (pair
.cell1
->x
!= x1
) {
686 struct cell
*cell
= pool_alloc (cells
->cell_pool
.base
,
687 sizeof (struct cell
));
689 cell
->uncovered_area
= 0;
690 cell
->covered_height
= 0;
691 cell
->clipped_height
= 0;
692 cell
->next
= pair
.cell1
->next
;
693 pair
.cell1
->next
= cell
;
697 pair
.cell2
= pair
.cell1
;
700 if (pair
.cell2
->next
->x
> x2
)
702 pair
.cell2
= pair
.cell2
->next
;
705 if (pair
.cell2
->x
!= x2
) {
706 struct cell
*cell
= pool_alloc (cells
->cell_pool
.base
,
707 sizeof (struct cell
));
708 cell
->uncovered_area
= 0;
709 cell
->covered_height
= 0;
710 cell
->clipped_height
= 0;
712 cell
->next
= pair
.cell2
->next
;
713 pair
.cell2
->next
= cell
;
717 cells
->cursor
= pair
.cell2
;
721 /* Add a subpixel span covering [x1, x2) to the coverage cells. */
723 cell_list_add_subspan(struct cell_list
*cells
,
730 GRID_X_TO_INT_FRAC(x1
, ix1
, fx1
);
731 GRID_X_TO_INT_FRAC(x2
, ix2
, fx2
);
735 p
= cell_list_find_pair(cells
, ix1
, ix2
);
736 p
.cell1
->uncovered_area
+= 2*fx1
;
737 ++p
.cell1
->covered_height
;
738 p
.cell2
->uncovered_area
-= 2*fx2
;
739 --p
.cell2
->covered_height
;
741 struct cell
*cell
= cell_list_find(cells
, ix1
);
742 cell
->uncovered_area
+= 2*(fx1
-fx2
);
746 /* Adds the analytical coverage of an edge crossing the current pixel
747 * row to the coverage cells and advances the edge's x position to the
750 * This function is only called when we know that during this pixel row:
752 * 1) The relative order of all edges on the active list doesn't
753 * change. In particular, no edges intersect within this row to pixel
756 * 2) No new edges start in this row.
758 * 3) No existing edges end mid-row.
760 * This function depends on being called with all edges from the
761 * active list in the order they appear on the list (i.e. with
762 * non-decreasing x-coordinate.) */
764 cell_list_render_edge(
765 struct cell_list
*cells
,
769 grid_scaled_y_t y1
, y2
, dy
;
772 grid_scaled_x_t fx1
, fx2
;
774 struct quorem x1
= edge
->x
;
775 struct quorem x2
= x1
;
777 if (! edge
->vertical
) {
778 x2
.quo
+= edge
->dxdy_full
.quo
;
779 x2
.rem
+= edge
->dxdy_full
.rem
;
788 GRID_X_TO_INT_FRAC(x1
.quo
, ix1
, fx1
);
789 GRID_X_TO_INT_FRAC(x2
.quo
, ix2
, fx2
);
791 /* Edge is entirely within a column? */
793 /* We always know that ix1 is >= the cell list cursor in this
794 * case due to the no-intersections precondition. */
795 struct cell
*cell
= cell_list_find(cells
, ix1
);
796 cell
->covered_height
+= sign
*GRID_Y
;
797 cell
->uncovered_area
+= sign
*(fx1
+ fx2
)*GRID_Y
;
801 /* Orient the edge left-to-right. */
802 dx
= x2
.quo
- x1
.quo
;
808 tmp
= ix1
; ix1
= ix2
; ix2
= tmp
;
809 tmp
= fx1
; fx1
= fx2
; fx2
= tmp
;
817 /* Add coverage for all pixels [ix1,ix2] on this row crossed
820 struct cell_pair pair
;
821 struct quorem y
= floored_divrem((GRID_X
- fx1
)*dy
, dx
);
823 /* When rendering a previous edge on the active list we may
824 * advance the cell list cursor past the leftmost pixel of the
825 * current edge even though the two edges don't intersect.
826 * e.g. consider two edges going down and rightwards:
828 * --\_+---\_+-----+-----+----
833 * ----+-----+-\---+-\---+----
835 * The left edge touches cells past the starting cell of the
836 * right edge. Fortunately such cases are rare.
838 * The rewinding is never necessary if the current edge stays
839 * within a single column because we've checked before calling
840 * this function that the active list order won't change. */
841 cell_list_maybe_rewind(cells
, ix1
);
843 pair
= cell_list_find_pair(cells
, ix1
, ix1
+1);
844 pair
.cell1
->uncovered_area
+= sign
*y
.quo
*(GRID_X
+ fx1
);
845 pair
.cell1
->covered_height
+= sign
*y
.quo
;
849 struct quorem dydx_full
= floored_divrem(GRID_X
*dy
, dx
);
850 struct cell
*cell
= pair
.cell2
;
854 grid_scaled_y_t y_skip
= dydx_full
.quo
;
855 y
.rem
+= dydx_full
.rem
;
864 cell
->uncovered_area
+= y_skip
*GRID_X
;
865 cell
->covered_height
+= y_skip
;
868 cell
= cell_list_find(cells
, ix1
);
869 } while (ix1
!= ix2
);
873 pair
.cell2
->uncovered_area
+= sign
*(y2
- y
.quo
)*fx2
;
874 pair
.cell2
->covered_height
+= sign
*(y2
- y
.quo
);
879 polygon_init (struct polygon
*polygon
, jmp_buf *jmp
)
881 polygon
->ymin
= polygon
->ymax
= 0;
882 polygon
->y_buckets
= polygon
->y_buckets_embedded
;
883 pool_init (polygon
->edge_pool
.base
, jmp
,
884 8192 - sizeof (struct _pool_chunk
),
885 sizeof (polygon
->edge_pool
.embedded
));
889 polygon_fini (struct polygon
*polygon
)
891 if (polygon
->y_buckets
!= polygon
->y_buckets_embedded
)
892 free (polygon
->y_buckets
);
894 pool_fini (polygon
->edge_pool
.base
);
897 /* Empties the polygon of all edges. The polygon is then prepared to
898 * receive new edges and clip them to the vertical range
900 static cairo_status_t
901 polygon_reset (struct polygon
*polygon
,
902 grid_scaled_y_t ymin
,
903 grid_scaled_y_t ymax
)
905 unsigned h
= ymax
- ymin
;
906 unsigned num_buckets
= EDGE_Y_BUCKET_INDEX(ymax
+ EDGE_Y_BUCKET_HEIGHT
-1,
909 pool_reset(polygon
->edge_pool
.base
);
911 if (unlikely (h
> 0x7FFFFFFFU
- EDGE_Y_BUCKET_HEIGHT
))
912 goto bail_no_mem
; /* even if you could, you wouldn't want to. */
914 if (polygon
->y_buckets
!= polygon
->y_buckets_embedded
)
915 free (polygon
->y_buckets
);
917 polygon
->y_buckets
= polygon
->y_buckets_embedded
;
918 if (num_buckets
> ARRAY_LENGTH (polygon
->y_buckets_embedded
)) {
919 polygon
->y_buckets
= _cairo_malloc_ab (num_buckets
,
920 sizeof (struct edge
*));
921 if (unlikely (NULL
== polygon
->y_buckets
))
924 memset (polygon
->y_buckets
, 0, num_buckets
* sizeof (struct edge
*));
926 polygon
->ymin
= ymin
;
927 polygon
->ymax
= ymax
;
928 return CAIRO_STATUS_SUCCESS
;
933 return CAIRO_STATUS_NO_MEMORY
;
937 _polygon_insert_edge_into_its_y_bucket(
938 struct polygon
*polygon
,
941 unsigned ix
= EDGE_Y_BUCKET_INDEX(e
->ytop
, polygon
->ymin
);
942 struct edge
**ptail
= &polygon
->y_buckets
[ix
];
948 polygon_add_edge (struct polygon
*polygon
,
949 const cairo_edge_t
*edge
,
955 grid_scaled_y_t ytop
, ybot
;
956 grid_scaled_y_t ymin
= polygon
->ymin
;
957 grid_scaled_y_t ymax
= polygon
->ymax
;
959 assert (edge
->bottom
> edge
->top
);
961 if (unlikely (edge
->top
>= ymax
|| edge
->bottom
<= ymin
))
964 e
= pool_alloc (polygon
->edge_pool
.base
, sizeof (struct edge
));
966 dx
= edge
->line
.p2
.x
- edge
->line
.p1
.x
;
967 dy
= edge
->line
.p2
.y
- edge
->line
.p1
.y
;
972 ytop
= edge
->top
>= ymin
? edge
->top
: ymin
;
973 ybot
= edge
->bottom
<= ymax
? edge
->bottom
: ymax
;
975 e
->height_left
= ybot
- ytop
;
979 e
->x
.quo
= edge
->line
.p1
.x
;
983 e
->dxdy_full
.quo
= 0;
984 e
->dxdy_full
.rem
= 0;
987 e
->dxdy
= floored_divrem (dx
, dy
);
988 if (ytop
== edge
->line
.p1
.y
) {
989 e
->x
.quo
= edge
->line
.p1
.x
;
992 e
->x
= floored_muldivrem (ytop
- edge
->line
.p1
.y
, dx
, dy
);
993 e
->x
.quo
+= edge
->line
.p1
.x
;
996 if (e
->height_left
>= GRID_Y
) {
997 e
->dxdy_full
= floored_muldivrem (GRID_Y
, dx
, dy
);
999 e
->dxdy_full
.quo
= 0;
1000 e
->dxdy_full
.rem
= 0;
1004 _polygon_insert_edge_into_its_y_bucket (polygon
, e
);
1006 e
->x
.rem
-= dy
; /* Bias the remainder for faster
1007 * edge advancement. */
1011 active_list_reset (struct active_list
*active
)
1013 active
->head
= NULL
;
1014 active
->min_height
= 0;
1018 active_list_init(struct active_list
*active
)
1020 active_list_reset(active
);
1024 * Merge two sorted edge lists.
1026 * - head_a: The head of the first list.
1027 * - head_b: The head of the second list; head_b cannot be NULL.
1029 * Returns the head of the merged list.
1031 * Implementation notes:
1032 * To make it fast (in particular, to reduce to an insertion sort whenever
1033 * one of the two input lists only has a single element) we iterate through
1034 * a list until its head becomes greater than the head of the other list,
1035 * then we switch their roles. As soon as one of the two lists is empty, we
1036 * just attach the other one to the current list and exit.
1037 * Writes to memory are only needed to "switch" lists (as it also requires
1038 * attaching to the output list the list which we will be iterating next) and
1039 * to attach the last non-empty list.
1041 static struct edge
*
1042 merge_sorted_edges (struct edge
*head_a
, struct edge
*head_b
)
1044 struct edge
*head
, **next
;
1051 if (head_a
->x
.quo
<= head_b
->x
.quo
) {
1060 while (head_a
!= NULL
&& head_a
->x
.quo
<= x
) {
1061 next
= &head_a
->next
;
1062 head_a
= head_a
->next
;
1071 while (head_b
!= NULL
&& head_b
->x
.quo
<= x
) {
1072 next
= &head_b
->next
;
1073 head_b
= head_b
->next
;
1083 * Sort (part of) a list.
1085 * - list: The list to be sorted; list cannot be NULL.
1086 * - limit: Recursion limit.
1088 * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
1089 * input list; if the input list has fewer elements, head_out be a sorted list
1090 * containing all the elements of the input list.
1091 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
1092 * all the elements of the input list).
1094 * Implementation notes:
1095 * Special case single element list, unroll/inline the sorting of the first two elements.
1096 * Some tail recursion is used since we iterate on the bottom-up solution of the problem
1097 * (we start with a small sorted list and keep merging other lists of the same size to it).
1099 static struct edge
*
1100 sort_edges (struct edge
*list
,
1102 struct edge
**head_out
)
1104 struct edge
*head_other
, *remaining
;
1107 head_other
= list
->next
;
1109 /* Single element list -> return */
1110 if (head_other
== NULL
) {
1115 /* Unroll the first iteration of the following loop (halves the number of calls to merge_sorted_edges):
1116 * - Initialize remaining to be the list containing the elements after the second in the input list.
1117 * - Initialize *head_out to be the sorted list containing the first two element.
1119 remaining
= head_other
->next
;
1120 if (list
->x
.quo
<= head_other
->x
.quo
) {
1122 /* list->next = head_other; */ /* The input list is already like this. */
1123 head_other
->next
= NULL
;
1125 *head_out
= head_other
;
1126 head_other
->next
= list
;
1130 for (i
= 0; i
< level
&& remaining
; i
++) {
1131 /* Extract a sorted list of the same size as *head_out
1132 * (2^(i+1) elements) from the list of remaining elements. */
1133 remaining
= sort_edges (remaining
, i
, &head_other
);
1134 *head_out
= merge_sorted_edges (*head_out
, head_other
);
1137 /* *head_out now contains (at most) 2^(level+1) elements. */
1142 /* Test if the edges on the active list can be safely advanced by a
1143 * full row without intersections or any edges ending. */
1145 active_list_can_step_full_row (struct active_list
*active
)
1147 const struct edge
*e
;
1148 int prev_x
= INT_MIN
;
1150 /* Recomputes the minimum height of all edges on the active
1151 * list if we have been dropping edges. */
1152 if (active
->min_height
<= 0) {
1153 int min_height
= INT_MAX
;
1157 if (e
->height_left
< min_height
)
1158 min_height
= e
->height_left
;
1162 active
->min_height
= min_height
;
1165 if (active
->min_height
< GRID_Y
)
1168 /* Check for intersections as no edges end during the next row. */
1171 struct quorem x
= e
->x
;
1173 if (! e
->vertical
) {
1174 x
.quo
+= e
->dxdy_full
.quo
;
1175 x
.rem
+= e
->dxdy_full
.rem
;
1180 if (x
.quo
<= prev_x
)
1190 /* Merges edges on the given subpixel row from the polygon to the
1193 active_list_merge_edges_from_polygon(struct active_list
*active
,
1194 struct edge
**ptail
,
1196 struct polygon
*polygon
)
1198 /* Split off the edges on the current subrow and merge them into
1199 * the active list. */
1200 int min_height
= active
->min_height
;
1201 struct edge
*subrow_edges
= NULL
;
1202 struct edge
*tail
= *ptail
;
1205 struct edge
*next
= tail
->next
;
1207 if (y
== tail
->ytop
) {
1208 tail
->next
= subrow_edges
;
1209 subrow_edges
= tail
;
1211 if (tail
->height_left
< min_height
)
1212 min_height
= tail
->height_left
;
1216 ptail
= &tail
->next
;
1222 sort_edges (subrow_edges
, UINT_MAX
, &subrow_edges
);
1223 active
->head
= merge_sorted_edges (active
->head
, subrow_edges
);
1224 active
->min_height
= min_height
;
1228 /* Advance the edges on the active list by one subsample row by
1229 * updating their x positions. Drop edges from the list that end. */
1231 active_list_substep_edges(struct active_list
*active
)
1233 struct edge
**cursor
= &active
->head
;
1234 grid_scaled_x_t prev_x
= INT_MIN
;
1235 struct edge
*unsorted
= NULL
;
1236 struct edge
*edge
= *cursor
;
1246 if (--edge
->height_left
) {
1247 edge
->x
.quo
+= edge
->dxdy
.quo
;
1248 edge
->x
.rem
+= edge
->dxdy
.rem
;
1249 if (edge
->x
.rem
>= 0) {
1251 edge
->x
.rem
-= edge
->dy
;
1254 if (edge
->x
.quo
< prev_x
) {
1256 edge
->next
= unsorted
;
1259 prev_x
= edge
->x
.quo
;
1260 cursor
= &edge
->next
;
1270 sort_edges (unsorted
, UINT_MAX
, &unsorted
);
1271 active
->head
= merge_sorted_edges (active
->head
, unsorted
);
1276 apply_nonzero_fill_rule_for_subrow (struct active_list
*active
,
1277 struct cell_list
*coverages
)
1279 struct edge
*edge
= active
->head
;
1284 cell_list_rewind (coverages
);
1286 while (NULL
!= edge
) {
1287 xstart
= edge
->x
.quo
;
1288 winding
= edge
->dir
;
1296 winding
+= edge
->dir
;
1298 if (edge
->next
== NULL
|| edge
->next
->x
.quo
!= edge
->x
.quo
)
1304 cell_list_add_subspan (coverages
, xstart
, xend
);
1311 apply_evenodd_fill_rule_for_subrow (struct active_list
*active
,
1312 struct cell_list
*coverages
)
1314 struct edge
*edge
= active
->head
;
1318 cell_list_rewind (coverages
);
1320 while (NULL
!= edge
) {
1321 xstart
= edge
->x
.quo
;
1330 if (edge
->next
== NULL
|| edge
->next
->x
.quo
!= edge
->x
.quo
)
1337 cell_list_add_subspan (coverages
, xstart
, xend
);
1344 apply_nonzero_fill_rule_and_step_edges (struct active_list
*active
,
1345 struct cell_list
*coverages
)
1347 struct edge
**cursor
= &active
->head
;
1348 struct edge
*left_edge
;
1350 left_edge
= *cursor
;
1351 while (NULL
!= left_edge
) {
1352 struct edge
*right_edge
;
1353 int winding
= left_edge
->dir
;
1355 left_edge
->height_left
-= GRID_Y
;
1356 if (left_edge
->height_left
)
1357 cursor
= &left_edge
->next
;
1359 *cursor
= left_edge
->next
;
1362 right_edge
= *cursor
;
1363 if (NULL
== right_edge
) {
1364 cell_list_render_edge (coverages
, left_edge
, +1);
1368 right_edge
->height_left
-= GRID_Y
;
1369 if (right_edge
->height_left
)
1370 cursor
= &right_edge
->next
;
1372 *cursor
= right_edge
->next
;
1374 winding
+= right_edge
->dir
;
1376 if (right_edge
->next
== NULL
||
1377 right_edge
->next
->x
.quo
!= right_edge
->x
.quo
)
1383 if (! right_edge
->vertical
) {
1384 right_edge
->x
.quo
+= right_edge
->dxdy_full
.quo
;
1385 right_edge
->x
.rem
+= right_edge
->dxdy_full
.rem
;
1386 if (right_edge
->x
.rem
>= 0) {
1387 ++right_edge
->x
.quo
;
1388 right_edge
->x
.rem
-= right_edge
->dy
;
1393 cell_list_render_edge (coverages
, left_edge
, +1);
1394 cell_list_render_edge (coverages
, right_edge
, -1);
1396 left_edge
= *cursor
;
1401 apply_evenodd_fill_rule_and_step_edges (struct active_list
*active
,
1402 struct cell_list
*coverages
)
1404 struct edge
**cursor
= &active
->head
;
1405 struct edge
*left_edge
;
1407 left_edge
= *cursor
;
1408 while (NULL
!= left_edge
) {
1409 struct edge
*right_edge
;
1411 left_edge
->height_left
-= GRID_Y
;
1412 if (left_edge
->height_left
)
1413 cursor
= &left_edge
->next
;
1415 *cursor
= left_edge
->next
;
1418 right_edge
= *cursor
;
1419 if (NULL
== right_edge
) {
1420 cell_list_render_edge (coverages
, left_edge
, +1);
1424 right_edge
->height_left
-= GRID_Y
;
1425 if (right_edge
->height_left
)
1426 cursor
= &right_edge
->next
;
1428 *cursor
= right_edge
->next
;
1430 if (right_edge
->next
== NULL
||
1431 right_edge
->next
->x
.quo
!= right_edge
->x
.quo
)
1436 if (! right_edge
->vertical
) {
1437 right_edge
->x
.quo
+= right_edge
->dxdy_full
.quo
;
1438 right_edge
->x
.rem
+= right_edge
->dxdy_full
.rem
;
1439 if (right_edge
->x
.rem
>= 0) {
1440 ++right_edge
->x
.quo
;
1441 right_edge
->x
.rem
-= right_edge
->dy
;
1446 cell_list_render_edge (coverages
, left_edge
, +1);
1447 cell_list_render_edge (coverages
, right_edge
, -1);
1449 left_edge
= *cursor
;
1454 _glitter_scan_converter_init(glitter_scan_converter_t
*converter
, jmp_buf *jmp
)
1456 polygon_init(converter
->polygon
, jmp
);
1457 active_list_init(converter
->active
);
1458 cell_list_init(converter
->coverages
, jmp
);
1464 _glitter_scan_converter_fini(glitter_scan_converter_t
*converter
)
1466 polygon_fini(converter
->polygon
);
1467 cell_list_fini(converter
->coverages
);
1472 static grid_scaled_t
1473 int_to_grid_scaled(int i
, int scale
)
1475 /* Clamp to max/min representable scaled number. */
1477 if (i
>= INT_MAX
/scale
)
1481 if (i
<= INT_MIN
/scale
)
1487 #define int_to_grid_scaled_x(x) int_to_grid_scaled((x), GRID_X)
1488 #define int_to_grid_scaled_y(x) int_to_grid_scaled((x), GRID_Y)
1490 static cairo_status_t
1491 glitter_scan_converter_reset(glitter_scan_converter_t
*converter
,
1494 cairo_status_t status
;
1496 converter
->ymin
= 0;
1497 converter
->ymax
= 0;
1499 ymin
= int_to_grid_scaled_y(ymin
);
1500 ymax
= int_to_grid_scaled_y(ymax
);
1502 active_list_reset(converter
->active
);
1503 cell_list_reset(converter
->coverages
);
1504 status
= polygon_reset(converter
->polygon
, ymin
, ymax
);
1508 converter
->ymin
= ymin
;
1509 converter
->ymax
= ymax
;
1510 return CAIRO_STATUS_SUCCESS
;
1513 /* INPUT_TO_GRID_X/Y (in_coord, out_grid_scaled, grid_scale)
1514 * These macros convert an input coordinate in the client's
1515 * device space to the rasterisation grid.
1517 /* Gah.. this bit of ugly defines INPUT_TO_GRID_X/Y so as to use
1518 * shifts if possible, and something saneish if not.
1520 #if !defined(INPUT_TO_GRID_Y) && defined(GRID_Y_BITS) && GRID_Y_BITS <= GLITTER_INPUT_BITS
1521 # define INPUT_TO_GRID_Y(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
1523 # define INPUT_TO_GRID_Y(in, out) INPUT_TO_GRID_general(in, out, GRID_Y)
1526 #if !defined(INPUT_TO_GRID_X) && defined(GRID_X_BITS) && GRID_X_BITS <= GLITTER_INPUT_BITS
1527 # define INPUT_TO_GRID_X(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
1529 # define INPUT_TO_GRID_X(in, out) INPUT_TO_GRID_general(in, out, GRID_X)
1532 #define INPUT_TO_GRID_general(in, out, grid_scale) do { \
1533 long long tmp__ = (long long)(grid_scale) * (in); \
1534 tmp__ >>= GLITTER_INPUT_BITS; \
1539 glitter_scan_converter_add_edge (glitter_scan_converter_t
*converter
,
1540 const cairo_edge_t
*edge
,
1545 INPUT_TO_GRID_Y (edge
->top
, e
.top
);
1546 INPUT_TO_GRID_Y (edge
->bottom
, e
.bottom
);
1547 if (e
.top
>= e
.bottom
)
1550 /* XXX: possible overflows if GRID_X/Y > 2**GLITTER_INPUT_BITS */
1551 INPUT_TO_GRID_Y (edge
->line
.p1
.y
, e
.line
.p1
.y
);
1552 INPUT_TO_GRID_Y (edge
->line
.p2
.y
, e
.line
.p2
.y
);
1553 if (e
.line
.p1
.y
== e
.line
.p2
.y
)
1556 INPUT_TO_GRID_X (edge
->line
.p1
.x
, e
.line
.p1
.x
);
1557 INPUT_TO_GRID_X (edge
->line
.p2
.x
, e
.line
.p2
.x
);
1561 polygon_add_edge (converter
->polygon
, &e
, clip
);
1565 active_list_is_vertical (struct active_list
*active
)
1569 for (e
= active
->head
; e
!= NULL
; e
= e
->next
) {
1578 step_edges (struct active_list
*active
, int count
)
1580 struct edge
**cursor
= &active
->head
;
1583 for (edge
= *cursor
; edge
!= NULL
; edge
= *cursor
) {
1584 edge
->height_left
-= GRID_Y
* count
;
1585 if (edge
->height_left
)
1586 cursor
= &edge
->next
;
1588 *cursor
= edge
->next
;
1592 static cairo_status_t
1593 blit_coverages (struct cell_list
*cells
,
1594 cairo_span_renderer_t
*renderer
,
1595 struct pool
*span_pool
,
1598 struct cell
*cell
= cells
->head
.next
;
1600 int cover
= 0, last_cover
= 0;
1602 cairo_half_open_span_t
*spans
;
1605 assert (cell
!= &cells
->tail
);
1607 /* Count number of cells remaining. */
1609 struct cell
*next
= cell
;
1611 while (next
->next
) {
1615 num_spans
= 2*num_spans
;
1618 /* Allocate enough spans for the row. */
1619 pool_reset (span_pool
);
1620 spans
= pool_alloc (span_pool
, sizeof(spans
[0])*num_spans
);
1623 /* Form the spans from the coverages and areas. */
1624 for (; cell
->next
; cell
= cell
->next
) {
1628 if (x
> prev_x
&& cover
!= last_cover
) {
1629 spans
[num_spans
].x
= prev_x
;
1630 spans
[num_spans
].coverage
= GRID_AREA_TO_ALPHA (cover
);
1631 spans
[num_spans
].inverse
= 0;
1636 cover
+= cell
->covered_height
*GRID_X
*2;
1637 clip
+= cell
->covered_height
*GRID_X
*2;
1638 area
= cover
- cell
->uncovered_area
;
1640 if (area
!= last_cover
) {
1641 spans
[num_spans
].x
= x
;
1642 spans
[num_spans
].coverage
= GRID_AREA_TO_ALPHA (area
);
1643 spans
[num_spans
].inverse
= 0;
1651 /* Dump them into the renderer. */
1652 return renderer
->render_rows (renderer
, y
, height
, spans
, num_spans
);
1656 glitter_scan_converter_render(glitter_scan_converter_t
*converter
,
1658 cairo_span_renderer_t
*span_renderer
,
1659 struct pool
*span_pool
)
1662 int ymax_i
= converter
->ymax
/ GRID_Y
;
1663 int ymin_i
= converter
->ymin
/ GRID_Y
;
1664 int h
= ymax_i
- ymin_i
;
1665 struct polygon
*polygon
= converter
->polygon
;
1666 struct cell_list
*coverages
= converter
->coverages
;
1667 struct active_list
*active
= converter
->active
;
1669 /* Render each pixel row. */
1670 for (i
= 0; i
< h
; i
= j
) {
1671 int do_full_step
= 0;
1675 /* Determine if we can ignore this row or use the full pixel
1677 if (GRID_Y
== EDGE_Y_BUCKET_HEIGHT
&& ! polygon
->y_buckets
[i
]) {
1678 if (! active
->head
) {
1679 for (; j
< h
&& ! polygon
->y_buckets
[j
]; j
++)
1684 do_full_step
= active_list_can_step_full_row (active
);
1688 /* Step by a full pixel row's worth. */
1690 apply_nonzero_fill_rule_and_step_edges (active
, coverages
);
1692 apply_evenodd_fill_rule_and_step_edges (active
, coverages
);
1694 if (active_list_is_vertical (active
)) {
1696 polygon
->y_buckets
[j
] == NULL
&&
1697 active
->min_height
>= 2*GRID_Y
)
1699 active
->min_height
-= GRID_Y
;
1703 step_edges (active
, j
- (i
+ 1));
1706 grid_scaled_y_t suby
;
1708 /* Subsample this row. */
1709 for (suby
= 0; suby
< GRID_Y
; suby
++) {
1710 grid_scaled_y_t y
= (i
+ymin_i
)*GRID_Y
+ suby
;
1712 if (polygon
->y_buckets
[i
]) {
1713 active_list_merge_edges_from_polygon (active
,
1714 &polygon
->y_buckets
[i
], y
,
1719 apply_nonzero_fill_rule_for_subrow (active
, coverages
);
1721 apply_evenodd_fill_rule_for_subrow (active
, coverages
);
1723 active_list_substep_edges(active
);
1727 blit_coverages (coverages
, span_renderer
, span_pool
, i
+ymin_i
, j
-i
);
1728 cell_list_reset (coverages
);
1731 active
->min_height
= INT_MAX
;
1733 active
->min_height
-= GRID_Y
;
1737 struct _cairo_clip_tor_scan_converter
{
1738 cairo_scan_converter_t base
;
1740 glitter_scan_converter_t converter
[1];
1741 cairo_fill_rule_t fill_rule
;
1742 cairo_antialias_t antialias
;
1744 cairo_fill_rule_t clip_fill_rule
;
1745 cairo_antialias_t clip_antialias
;
1750 struct pool base
[1];
1751 cairo_half_open_span_t embedded
[32];
1755 typedef struct _cairo_clip_tor_scan_converter cairo_clip_tor_scan_converter_t
;
1758 _cairo_clip_tor_scan_converter_destroy (void *converter
)
1760 cairo_clip_tor_scan_converter_t
*self
= converter
;
1764 _glitter_scan_converter_fini (self
->converter
);
1765 pool_fini (self
->span_pool
.base
);
1769 static cairo_status_t
1770 _cairo_clip_tor_scan_converter_generate (void *converter
,
1771 cairo_span_renderer_t
*renderer
)
1773 cairo_clip_tor_scan_converter_t
*self
= converter
;
1774 cairo_status_t status
;
1776 if ((status
= setjmp (self
->jmp
)))
1777 return _cairo_scan_converter_set_error (self
, _cairo_error (status
));
1779 glitter_scan_converter_render (self
->converter
,
1780 self
->fill_rule
== CAIRO_FILL_RULE_WINDING
,
1782 self
->span_pool
.base
);
1783 return CAIRO_STATUS_SUCCESS
;
1786 cairo_scan_converter_t
*
1787 _cairo_clip_tor_scan_converter_create (cairo_clip_t
*clip
,
1788 cairo_polygon_t
*polygon
,
1789 cairo_fill_rule_t fill_rule
,
1790 cairo_antialias_t antialias
)
1792 cairo_clip_tor_scan_converter_t
*self
;
1793 cairo_polygon_t clipper
;
1794 cairo_status_t status
;
1797 self
= calloc (1, sizeof(struct _cairo_clip_tor_scan_converter
));
1798 if (unlikely (self
== NULL
)) {
1799 status
= _cairo_error (CAIRO_STATUS_NO_MEMORY
);
1803 self
->base
.destroy
= _cairo_clip_tor_scan_converter_destroy
;
1804 self
->base
.generate
= _cairo_clip_tor_scan_converter_generate
;
1806 pool_init (self
->span_pool
.base
, &self
->jmp
,
1807 250 * sizeof(self
->span_pool
.embedded
[0]),
1808 sizeof(self
->span_pool
.embedded
));
1810 _glitter_scan_converter_init (self
->converter
, &self
->jmp
);
1811 status
= glitter_scan_converter_reset (self
->converter
,
1813 clip
->extents
.y
+ clip
->extents
.height
);
1814 if (unlikely (status
))
1817 self
->fill_rule
= fill_rule
;
1818 self
->antialias
= antialias
;
1820 for (i
= 0; i
< polygon
->num_edges
; i
++)
1821 glitter_scan_converter_add_edge (self
->converter
,
1825 status
= _cairo_clip_get_polygon (clip
,
1827 &self
->clip_fill_rule
,
1828 &self
->clip_antialias
);
1829 if (unlikely (status
))
1832 for (i
= 0; i
< clipper
.num_edges
; i
++)
1833 glitter_scan_converter_add_edge (self
->converter
,
1836 _cairo_polygon_fini (&clipper
);
1841 self
->base
.destroy(&self
->base
);
1843 return _cairo_scan_converter_create_in_error (status
);