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"
105 /*-------------------------------------------------------------------------
106 * cairo specific config
110 /* Prefer cairo's status type. */
111 #define GLITTER_HAVE_STATUS_T 1
112 #define GLITTER_STATUS_SUCCESS CAIRO_STATUS_SUCCESS
113 #define GLITTER_STATUS_NO_MEMORY CAIRO_STATUS_NO_MEMORY
114 typedef cairo_status_t glitter_status_t
;
116 /* The input coordinate scale and the rasterisation grid scales. */
117 #define GLITTER_INPUT_BITS CAIRO_FIXED_FRAC_BITS
118 #define GRID_X_BITS CAIRO_FIXED_FRAC_BITS
121 /* Set glitter up to use a cairo span renderer to do the coverage
126 /*-------------------------------------------------------------------------
130 /* "Input scaled" numbers are fixed precision reals with multiplier
131 * 2**GLITTER_INPUT_BITS. Input coordinates are given to glitter as
132 * pixel scaled numbers. These get converted to the internal grid
133 * scaled numbers as soon as possible. Internal overflow is possible
134 * if GRID_X/Y inside glitter-paths.c is larger than
135 * 1<<GLITTER_INPUT_BITS. */
136 #ifndef GLITTER_INPUT_BITS
137 # define GLITTER_INPUT_BITS 8
139 #define GLITTER_INPUT_SCALE (1<<GLITTER_INPUT_BITS)
140 typedef int glitter_input_scaled_t
;
142 #if !GLITTER_HAVE_STATUS_T
144 GLITTER_STATUS_SUCCESS
= 0,
145 GLITTER_STATUS_NO_MEMORY
150 # define I /*static*/
153 /* Opaque type for scan converting. */
154 typedef struct glitter_scan_converter glitter_scan_converter_t
;
156 /* Reset a scan converter to accept polygon edges and set the clip box
157 * in pixels. Allocates O(ymax-ymin) bytes of memory. The clip box
158 * is set to integer pixel coordinates xmin <= x < xmax, ymin <= y <
161 glitter_scan_converter_reset(
162 glitter_scan_converter_t
*converter
,
166 /* Render the polygon in the scan converter to the given A8 format
167 * image raster. Only the pixels accessible as pixels[y*stride+x] for
168 * x,y inside the clip box are written to, where xmin <= x < xmax,
169 * ymin <= y < ymax. The image is assumed to be clear on input.
171 * If nonzero_fill is true then the interior of the polygon is
172 * computed with the non-zero fill rule. Otherwise the even-odd fill
175 * The scan converter must be reset or destroyed after this call. */
177 /*-------------------------------------------------------------------------
178 * glitter-paths.c: Implementation internal types
184 /* All polygon coordinates are snapped onto a subsample grid. "Grid
185 * scaled" numbers are fixed precision reals with multiplier GRID_X or
187 typedef int grid_scaled_t
;
188 typedef int grid_scaled_x_t
;
189 typedef int grid_scaled_y_t
;
191 /* Default x/y scale factors.
192 * You can either define GRID_X/Y_BITS to get a power-of-two scale
193 * or define GRID_X/Y separately. */
194 #if !defined(GRID_X) && !defined(GRID_X_BITS)
195 # define GRID_X_BITS 8
197 #if !defined(GRID_Y) && !defined(GRID_Y_BITS)
201 /* Use GRID_X/Y_BITS to define GRID_X/Y if they're available. */
203 # define GRID_X (1 << GRID_X_BITS)
206 # define GRID_Y (1 << GRID_Y_BITS)
209 /* The GRID_X_TO_INT_FRAC macro splits a grid scaled coordinate into
210 * integer and fractional parts. The integer part is floored. */
211 #if defined(GRID_X_TO_INT_FRAC)
213 #elif defined(GRID_X_BITS)
214 # define GRID_X_TO_INT_FRAC(x, i, f) \
215 _GRID_TO_INT_FRAC_shift(x, i, f, GRID_X_BITS)
217 # define GRID_X_TO_INT_FRAC(x, i, f) \
218 _GRID_TO_INT_FRAC_general(x, i, f, GRID_X)
221 #define _GRID_TO_INT_FRAC_general(t, i, f, m) do { \
230 #define _GRID_TO_INT_FRAC_shift(t, i, f, b) do { \
231 (f) = (t) & ((1 << (b)) - 1); \
235 /* A grid area is a real in [0,1] scaled by 2*GRID_X*GRID_Y. We want
236 * to be able to represent exactly areas of subpixel trapezoids whose
237 * vertices are given in grid scaled coordinates. The scale factor
238 * comes from needing to accurately represent the area 0.5*dx*dy of a
239 * triangle with base dx and height dy in grid scaled numbers. */
240 #define GRID_XY (2*GRID_X*GRID_Y) /* Unit area on the grid. */
242 /* GRID_AREA_TO_ALPHA(area): map [0,GRID_XY] to [0,255]. */
244 # define GRID_AREA_TO_ALPHA(c) (((c)+1) >> 1)
246 # define GRID_AREA_TO_ALPHA(c) (c)
248 # define GRID_AREA_TO_ALPHA(c) (((c) << 2) | -(((c) & 0x40) >> 6))
250 # define GRID_AREA_TO_ALPHA(c) ((((c) << 1) | -((c) >> 7)) & 255)
252 # define GRID_AREA_TO_ALPHA(c) (((c) | -((c) >> 8)) & 255)
254 # define GRID_AREA_TO_ALPHA(c) (((c) << 4) + (c))
255 #elif GRID_XY == 2*256*15
256 # define GRID_AREA_TO_ALPHA(c) (((c) + ((c)<<4) + 256) >> 9)
258 # define GRID_AREA_TO_ALPHA(c) (((c)*255 + GRID_XY/2) / GRID_XY)
261 #define UNROLL3(x) x x x
268 /* Header for a chunk of memory in a memory pool. */
270 /* # bytes used in this chunk. */
273 /* # bytes total in this chunk */
276 /* Pointer to the previous chunk or %NULL if this is the sentinel
277 * chunk in the pool header. */
278 struct _pool_chunk
*prev_chunk
;
280 /* Actual data starts here. Well aligned even for 64 bit types. */
284 /* The int64_t data member of _pool_chunk just exists to enforce alignment,
285 * it shouldn't be included in the allocated size for the struct. */
286 #define SIZEOF_POOL_CHUNK (sizeof(struct _pool_chunk) - sizeof(int64_t))
288 /* A memory pool. This is supposed to be embedded on the stack or
289 * within some other structure. It may optionally be followed by an
290 * embedded array from which requests are fulfilled until
291 * malloc needs to be called to allocate a first real chunk. */
293 /* Chunk we're allocating from. */
294 struct _pool_chunk
*current
;
298 /* Free list of previously allocated chunks. All have >= default
300 struct _pool_chunk
*first_free
;
302 /* The default capacity of a chunk. */
303 size_t default_capacity
;
305 /* Header for the sentinel chunk. Directly following the pool
306 * struct should be some space for embedded elements from which
307 * the sentinel chunk allocates from. This is expressed as a char
308 * array so that the 'int64_t data' member of _pool_chunk isn't
309 * included. This way embedding struct pool in other structs works
310 * without wasting space. */
311 char sentinel
[SIZEOF_POOL_CHUNK
];
314 /* A polygon edge. */
316 /* Next in y-bucket or active list. */
317 struct edge
*next
, *prev
;
319 /* The clipped y of the top of the edge. */
320 grid_scaled_y_t ytop
;
322 /* Number of subsample rows remaining to scan convert of this
324 grid_scaled_y_t height_left
;
326 /* Original sign of the edge: +1 for downwards, -1 for upwards
331 /* Current x coordinate while the edge is on the active
332 * list. Initialised to the x coordinate of the top of the
333 * edge. The quotient is in grid_scaled_x_t units and the
334 * remainder is mod dy in grid_scaled_y_t units.*/
337 /* Advance of the current x when moving down a subsample line. */
340 /* Advance of the current x when moving down a full pixel
341 * row. Only initialised when the height of the edge is large
342 * enough that there's a chance the edge could be stepped by a
343 * full row's worth of subsample rows at a time. */
344 struct quorem dxdy_full
;
346 /* y2-y1 after orienting the edge downwards. */
350 #define EDGE_Y_BUCKET_INDEX(y, ymin) (((y) - (ymin))/GRID_Y)
352 /* A collection of sorted and vertically clipped edges of the polygon.
353 * Edges are moved from the polygon to an active list while scan
356 /* The vertical clip extents. */
357 grid_scaled_y_t ymin
, ymax
;
359 /* Array of edges all starting in the same bucket. An edge is put
360 * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
361 * it is added to the polygon. */
362 struct edge
**y_buckets
;
363 struct edge
*y_buckets_embedded
[64];
367 struct edge embedded
[32];
371 /* A cell records the effect on pixel coverage of polygon edges
372 * passing through a pixel. It contains two accumulators of pixel
375 * Consider the effects of a polygon edge on the coverage of a pixel
376 * it intersects and that of the following one. The coverage of the
377 * following pixel is the height of the edge multiplied by the width
378 * of the pixel, and the coverage of the pixel itself is the area of
379 * the trapezoid formed by the edge and the right side of the pixel.
381 * +-----------------------+-----------------------+
384 * |_______________________|_______________________|
385 * | \...................|.......................|\
386 * | \..................|.......................| |
387 * | \.................|.......................| |
388 * | \....covered.....|.......................| |
389 * | \....area.......|.......................| } covered height
390 * | \..............|.......................| |
391 * |uncovered\.............|.......................| |
392 * | area \............|.......................| |
393 * |___________\...........|.......................|/
397 * +-----------------------+-----------------------+
399 * Since the coverage of the following pixel will always be a multiple
400 * of the width of the pixel, we can store the height of the covered
401 * area instead. The coverage of the pixel itself is the total
402 * coverage minus the area of the uncovered area to the left of the
403 * edge. As it's faster to compute the uncovered area we only store
404 * that and subtract it from the total coverage later when forming
407 * The heights and areas are signed, with left edges of the polygon
408 * having positive sign and right edges having negative sign. When
409 * two edges intersect they swap their left/rightness so their
410 * contribution above and below the intersection point must be
411 * computed separately. */
415 int16_t uncovered_area
;
416 int16_t covered_height
;
419 /* A cell list represents the scan line sparsely as cells ordered by
420 * ascending x. It is geared towards scanning the cells in order
421 * using an internal cursor. */
424 struct cell head
, tail
;
426 /* Cursor state for iterating through the cell list. */
427 struct cell
*cursor
, *rewind
;
429 /* Cells in the cell list are owned by the cell list and are
430 * allocated from this pool. */
433 struct cell embedded
[32];
442 /* The active list contains edges in the current scan line ordered by
443 * the x-coordinate of the intercept of the edge and the scan line. */
445 /* Leftmost edge on the current scan line. */
446 struct edge head
, tail
;
448 /* A lower bound on the height of the active edges is used to
449 * estimate how soon some active edge ends. We can't advance the
450 * scan conversion by a full pixel row if an edge ends somewhere
452 grid_scaled_y_t min_height
;
456 struct glitter_scan_converter
{
457 struct polygon polygon
[1];
458 struct active_list active
[1];
459 struct cell_list coverages
[1];
461 cairo_half_open_span_t
*spans
;
462 cairo_half_open_span_t spans_embedded
[64];
465 grid_scaled_x_t xmin
, xmax
;
466 grid_scaled_y_t ymin
, ymax
;
469 static struct _pool_chunk
*
471 struct _pool_chunk
*p
,
472 struct _pool_chunk
*prev_chunk
,
475 p
->prev_chunk
= prev_chunk
;
477 p
->capacity
= capacity
;
481 static struct _pool_chunk
*
482 _pool_chunk_create(struct pool
*pool
, size_t size
)
484 struct _pool_chunk
*p
;
486 p
= malloc(SIZEOF_POOL_CHUNK
+ size
);
487 if (unlikely (NULL
== p
))
488 longjmp (*pool
->jmp
, _cairo_error (CAIRO_STATUS_NO_MEMORY
));
490 return _pool_chunk_init(p
, pool
->current
, size
);
494 pool_init(struct pool
*pool
,
496 size_t default_capacity
,
497 size_t embedded_capacity
)
500 pool
->current
= (void*) pool
->sentinel
;
501 pool
->first_free
= NULL
;
502 pool
->default_capacity
= default_capacity
;
503 _pool_chunk_init(pool
->current
, NULL
, embedded_capacity
);
507 pool_fini(struct pool
*pool
)
509 struct _pool_chunk
*p
= pool
->current
;
512 struct _pool_chunk
*prev
= p
->prev_chunk
;
513 if (p
!= (void *) pool
->sentinel
)
517 p
= pool
->first_free
;
518 pool
->first_free
= NULL
;
522 /* Satisfy an allocation by first allocating a new large enough chunk
523 * and adding it to the head of the pool's chunk list. This function
524 * is called as a fallback if pool_alloc() couldn't do a quick
525 * allocation from the current chunk in the pool. */
527 _pool_alloc_from_new_chunk(
531 struct _pool_chunk
*chunk
;
535 /* If the allocation is smaller than the default chunk size then
536 * try getting a chunk off the free list. Force alloc of a new
537 * chunk for large requests. */
540 if (size
< pool
->default_capacity
) {
541 capacity
= pool
->default_capacity
;
542 chunk
= pool
->first_free
;
544 pool
->first_free
= chunk
->prev_chunk
;
545 _pool_chunk_init(chunk
, pool
->current
, chunk
->capacity
);
550 chunk
= _pool_chunk_create (pool
, capacity
);
551 pool
->current
= chunk
;
553 obj
= ((unsigned char*)&chunk
->data
+ chunk
->size
);
558 /* Allocate size bytes from the pool. The first allocated address
559 * returned from a pool is aligned to 8 bytes. Subsequent
560 * addresses will maintain alignment as long as multiples of 8 are
561 * allocated. Returns the address of a new memory area or %NULL on
562 * allocation failures. The pool retains ownership of the returned
565 pool_alloc (struct pool
*pool
, size_t size
)
567 struct _pool_chunk
*chunk
= pool
->current
;
569 if (size
<= chunk
->capacity
- chunk
->size
) {
570 void *obj
= ((unsigned char*)&chunk
->data
+ chunk
->size
);
574 return _pool_alloc_from_new_chunk(pool
, size
);
578 /* Relinquish all pool_alloced memory back to the pool. */
580 pool_reset (struct pool
*pool
)
582 /* Transfer all used chunks to the chunk free list. */
583 struct _pool_chunk
*chunk
= pool
->current
;
584 if (chunk
!= (void *) pool
->sentinel
) {
585 while (chunk
->prev_chunk
!= (void *) pool
->sentinel
) {
586 chunk
= chunk
->prev_chunk
;
588 chunk
->prev_chunk
= pool
->first_free
;
589 pool
->first_free
= pool
->current
;
591 /* Reset the sentinel as the current chunk. */
592 pool
->current
= (void *) pool
->sentinel
;
593 pool
->current
->size
= 0;
596 /* Rewinds the cell list's cursor to the beginning. After rewinding
597 * we're good to cell_list_find() the cell any x coordinate. */
599 cell_list_rewind (struct cell_list
*cells
)
601 cells
->cursor
= &cells
->head
;
605 cell_list_maybe_rewind (struct cell_list
*cells
, int x
)
607 if (x
< cells
->cursor
->x
) {
608 cells
->cursor
= cells
->rewind
;
609 if (x
< cells
->cursor
->x
)
610 cells
->cursor
= &cells
->head
;
615 cell_list_set_rewind (struct cell_list
*cells
)
617 cells
->rewind
= cells
->cursor
;
621 cell_list_init(struct cell_list
*cells
, jmp_buf *jmp
)
623 pool_init(cells
->cell_pool
.base
, jmp
,
624 256*sizeof(struct cell
),
625 sizeof(cells
->cell_pool
.embedded
));
626 cells
->tail
.next
= NULL
;
627 cells
->tail
.x
= INT_MAX
;
628 cells
->head
.x
= INT_MIN
;
629 cells
->head
.next
= &cells
->tail
;
630 cell_list_rewind (cells
);
634 cell_list_fini(struct cell_list
*cells
)
636 pool_fini (cells
->cell_pool
.base
);
639 /* Empty the cell list. This is called at the start of every pixel
642 cell_list_reset (struct cell_list
*cells
)
644 cell_list_rewind (cells
);
645 cells
->head
.next
= &cells
->tail
;
646 pool_reset (cells
->cell_pool
.base
);
649 inline static struct cell
*
650 cell_list_alloc (struct cell_list
*cells
,
656 cell
= pool_alloc (cells
->cell_pool
.base
, sizeof (struct cell
));
657 cell
->next
= tail
->next
;
660 *(uint32_t *)&cell
->uncovered_area
= 0;
665 /* Find a cell at the given x-coordinate. Returns %NULL if a new cell
666 * needed to be allocated but couldn't be. Cells must be found with
667 * non-decreasing x-coordinate until the cell list is rewound using
668 * cell_list_rewind(). Ownership of the returned cell is retained by
670 inline static struct cell
*
671 cell_list_find (struct cell_list
*cells
, int x
)
673 struct cell
*tail
= cells
->cursor
;
680 if (tail
->next
->x
> x
)
687 tail
= cell_list_alloc (cells
, tail
, x
);
688 return cells
->cursor
= tail
;
692 /* Find two cells at x1 and x2. This is exactly equivalent
695 * pair.cell1 = cell_list_find(cells, x1);
696 * pair.cell2 = cell_list_find(cells, x2);
698 * except with less function call overhead. */
699 inline static struct cell_pair
700 cell_list_find_pair(struct cell_list
*cells
, int x1
, int x2
)
702 struct cell_pair pair
;
704 pair
.cell1
= cells
->cursor
;
707 if (pair
.cell1
->next
->x
> x1
)
709 pair
.cell1
= pair
.cell1
->next
;
712 if (pair
.cell1
->x
!= x1
)
713 pair
.cell1
= cell_list_alloc (cells
, pair
.cell1
, x1
);
715 pair
.cell2
= pair
.cell1
;
718 if (pair
.cell2
->next
->x
> x2
)
720 pair
.cell2
= pair
.cell2
->next
;
723 if (pair
.cell2
->x
!= x2
)
724 pair
.cell2
= cell_list_alloc (cells
, pair
.cell2
, x2
);
726 cells
->cursor
= pair
.cell2
;
730 /* Add a subpixel span covering [x1, x2) to the coverage cells. */
732 cell_list_add_subspan(struct cell_list
*cells
,
742 GRID_X_TO_INT_FRAC(x1
, ix1
, fx1
);
743 GRID_X_TO_INT_FRAC(x2
, ix2
, fx2
);
747 p
= cell_list_find_pair(cells
, ix1
, ix2
);
748 p
.cell1
->uncovered_area
+= 2*fx1
;
749 ++p
.cell1
->covered_height
;
750 p
.cell2
->uncovered_area
-= 2*fx2
;
751 --p
.cell2
->covered_height
;
753 struct cell
*cell
= cell_list_find(cells
, ix1
);
754 cell
->uncovered_area
+= 2*(fx1
-fx2
);
758 inline static void full_step (struct edge
*e
)
763 e
->x
.quo
+= e
->dxdy_full
.quo
;
764 e
->x
.rem
+= e
->dxdy_full
.rem
;
768 } else if (e
->x
.rem
>= e
->dy
) {
773 e
->cell
= e
->x
.quo
+ (e
->x
.rem
>= e
->dy
/2);
777 /* Adds the analytical coverage of an edge crossing the current pixel
778 * row to the coverage cells and advances the edge's x position to the
781 * This function is only called when we know that during this pixel row:
783 * 1) The relative order of all edges on the active list doesn't
784 * change. In particular, no edges intersect within this row to pixel
787 * 2) No new edges start in this row.
789 * 3) No existing edges end mid-row.
791 * This function depends on being called with all edges from the
792 * active list in the order they appear on the list (i.e. with
793 * non-decreasing x-coordinate.) */
795 cell_list_render_edge(struct cell_list
*cells
,
799 struct quorem x1
, x2
;
800 grid_scaled_x_t fx1
, fx2
;
807 /* Step back from the sample location (half-subrow) to the pixel origin */
809 x1
.quo
-= edge
->dxdy
.quo
/ 2;
810 x1
.rem
-= edge
->dxdy
.rem
/ 2;
814 } else if (x1
.rem
>= edge
->dy
) {
819 x2
.quo
-= edge
->dxdy
.quo
/ 2;
820 x2
.rem
-= edge
->dxdy
.rem
/ 2;
824 } else if (x2
.rem
>= edge
->dy
) {
830 GRID_X_TO_INT_FRAC(x1
.quo
, ix1
, fx1
);
831 GRID_X_TO_INT_FRAC(x2
.quo
, ix2
, fx2
);
833 cell_list_maybe_rewind(cells
, MIN(ix1
, ix2
));
835 /* Edge is entirely within a column? */
837 /* We always know that ix1 is >= the cell list cursor in this
838 * case due to the no-intersections precondition. */
839 struct cell
*cell
= cell_list_find(cells
, ix1
);
840 cell
->covered_height
+= sign
*GRID_Y
;
841 cell
->uncovered_area
+= sign
*(fx1
+ fx2
)*GRID_Y
;
845 /* Orient the edge left-to-right. */
863 /* Add coverage for all pixels [ix1,ix2] on this row crossed
866 struct cell_pair pair
;
871 dx
= (x2
.quo
- x1
.quo
) * edge
->dy
+ (x2
.rem
- x1
.rem
);
873 tmp
= (ix1
+ 1) * GRID_X
* edge
->dy
;
874 tmp
-= x1
.quo
* edge
->dy
+ x1
.rem
;
880 /* When rendering a previous edge on the active list we may
881 * advance the cell list cursor past the leftmost pixel of the
882 * current edge even though the two edges don't intersect.
883 * e.g. consider two edges going down and rightwards:
885 * --\_+---\_+-----+-----+----
890 * ----+-----+-\---+-\---+----
892 * The left edge touches cells past the starting cell of the
893 * right edge. Fortunately such cases are rare.
896 pair
= cell_list_find_pair(cells
, ix1
, ix1
+1);
897 pair
.cell1
->uncovered_area
+= sign
*y
.quo
*(GRID_X
+ fx1
);
898 pair
.cell1
->covered_height
+= sign
*y
.quo
;
902 struct cell
*cell
= pair
.cell2
;
903 struct quorem dydx_full
;
905 dydx_full
.quo
= GRID_Y
* GRID_X
* edge
->dy
/ dx
;
906 dydx_full
.rem
= GRID_Y
* GRID_X
* edge
->dy
% dx
;
910 y
.quo
+= dydx_full
.quo
;
911 y
.rem
+= dydx_full
.rem
;
917 cell
->uncovered_area
+= sign
*(y
.quo
- y_last
)*GRID_X
;
918 cell
->covered_height
+= sign
*(y
.quo
- y_last
);
922 cell
= cell_list_find(cells
, ix1
);
923 } while (ix1
!= ix2
);
927 pair
.cell2
->uncovered_area
+= sign
*(GRID_Y
- y_last
)*fx2
;
928 pair
.cell2
->covered_height
+= sign
*(GRID_Y
- y_last
);
933 polygon_init (struct polygon
*polygon
, jmp_buf *jmp
)
935 polygon
->ymin
= polygon
->ymax
= 0;
936 polygon
->y_buckets
= polygon
->y_buckets_embedded
;
937 pool_init (polygon
->edge_pool
.base
, jmp
,
938 8192 - sizeof (struct _pool_chunk
),
939 sizeof (polygon
->edge_pool
.embedded
));
943 polygon_fini (struct polygon
*polygon
)
945 if (polygon
->y_buckets
!= polygon
->y_buckets_embedded
)
946 free (polygon
->y_buckets
);
948 pool_fini (polygon
->edge_pool
.base
);
951 /* Empties the polygon of all edges. The polygon is then prepared to
952 * receive new edges and clip them to the vertical range
954 static glitter_status_t
955 polygon_reset (struct polygon
*polygon
,
956 grid_scaled_y_t ymin
,
957 grid_scaled_y_t ymax
)
959 unsigned h
= ymax
- ymin
;
960 unsigned num_buckets
= EDGE_Y_BUCKET_INDEX(ymax
+ GRID_Y
-1, ymin
);
962 pool_reset(polygon
->edge_pool
.base
);
964 if (unlikely (h
> 0x7FFFFFFFU
- GRID_Y
))
965 goto bail_no_mem
; /* even if you could, you wouldn't want to. */
967 if (polygon
->y_buckets
!= polygon
->y_buckets_embedded
)
968 free (polygon
->y_buckets
);
970 polygon
->y_buckets
= polygon
->y_buckets_embedded
;
971 if (num_buckets
> ARRAY_LENGTH (polygon
->y_buckets_embedded
)) {
972 polygon
->y_buckets
= _cairo_malloc_ab (num_buckets
,
973 sizeof (struct edge
*));
974 if (unlikely (NULL
== polygon
->y_buckets
))
977 memset (polygon
->y_buckets
, 0, num_buckets
* sizeof (struct edge
*));
979 polygon
->ymin
= ymin
;
980 polygon
->ymax
= ymax
;
981 return GLITTER_STATUS_SUCCESS
;
986 return GLITTER_STATUS_NO_MEMORY
;
990 _polygon_insert_edge_into_its_y_bucket(struct polygon
*polygon
,
993 unsigned ix
= EDGE_Y_BUCKET_INDEX(e
->ytop
, polygon
->ymin
);
994 struct edge
**ptail
= &polygon
->y_buckets
[ix
];
1000 active_list_reset (struct active_list
*active
)
1002 active
->head
.height_left
= INT_MAX
;
1003 active
->head
.dy
= 0;
1004 active
->head
.cell
= INT_MIN
;
1005 active
->head
.prev
= NULL
;
1006 active
->head
.next
= &active
->tail
;
1007 active
->tail
.prev
= &active
->head
;
1008 active
->tail
.next
= NULL
;
1009 active
->tail
.cell
= INT_MAX
;
1010 active
->tail
.height_left
= INT_MAX
;
1011 active
->tail
.dy
= 0;
1012 active
->min_height
= 0;
1013 active
->is_vertical
= 1;
1017 active_list_init(struct active_list
*active
)
1019 active_list_reset(active
);
1023 * Merge two sorted edge lists.
1025 * - head_a: The head of the first list.
1026 * - head_b: The head of the second list; head_b cannot be NULL.
1028 * Returns the head of the merged list.
1030 * Implementation notes:
1031 * To make it fast (in particular, to reduce to an insertion sort whenever
1032 * one of the two input lists only has a single element) we iterate through
1033 * a list until its head becomes greater than the head of the other list,
1034 * then we switch their roles. As soon as one of the two lists is empty, we
1035 * just attach the other one to the current list and exit.
1036 * Writes to memory are only needed to "switch" lists (as it also requires
1037 * attaching to the output list the list which we will be iterating next) and
1038 * to attach the last non-empty list.
1040 static struct edge
*
1041 merge_sorted_edges (struct edge
*head_a
, struct edge
*head_b
)
1043 struct edge
*head
, **next
, *prev
;
1046 prev
= head_a
->prev
;
1048 if (head_a
->cell
<= head_b
->cell
) {
1052 head_b
->prev
= prev
;
1058 while (head_a
!= NULL
&& head_a
->cell
<= x
) {
1060 next
= &head_a
->next
;
1061 head_a
= head_a
->next
;
1064 head_b
->prev
= prev
;
1071 while (head_b
!= NULL
&& head_b
->cell
<= x
) {
1073 next
= &head_b
->next
;
1074 head_b
= head_b
->next
;
1077 head_a
->prev
= prev
;
1085 * Sort (part of) a list.
1087 * - list: The list to be sorted; list cannot be NULL.
1088 * - limit: Recursion limit.
1090 * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
1091 * input list; if the input list has fewer elements, head_out be a sorted list
1092 * containing all the elements of the input list.
1093 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
1094 * all the elements of the input list).
1096 * Implementation notes:
1097 * Special case single element list, unroll/inline the sorting of the first two elements.
1098 * Some tail recursion is used since we iterate on the bottom-up solution of the problem
1099 * (we start with a small sorted list and keep merging other lists of the same size to it).
1101 static struct edge
*
1102 sort_edges (struct edge
*list
,
1104 struct edge
**head_out
)
1106 struct edge
*head_other
, *remaining
;
1109 head_other
= list
->next
;
1111 if (head_other
== NULL
) {
1116 remaining
= head_other
->next
;
1117 if (list
->cell
<= head_other
->cell
) {
1119 head_other
->next
= NULL
;
1121 *head_out
= head_other
;
1122 head_other
->prev
= list
->prev
;
1123 head_other
->next
= list
;
1124 list
->prev
= head_other
;
1128 for (i
= 0; i
< level
&& remaining
; i
++) {
1129 remaining
= sort_edges (remaining
, i
, &head_other
);
1130 *head_out
= merge_sorted_edges (*head_out
, head_other
);
1136 static struct edge
*
1137 merge_unsorted_edges (struct edge
*head
, struct edge
*unsorted
)
1139 sort_edges (unsorted
, UINT_MAX
, &unsorted
);
1140 return merge_sorted_edges (head
, unsorted
);
1143 /* Test if the edges on the active list can be safely advanced by a
1144 * full row without intersections or any edges ending. */
1146 can_do_full_row (struct active_list
*active
)
1148 const struct edge
*e
;
1149 int prev_x
= INT_MIN
;
1151 /* Recomputes the minimum height of all edges on the active
1152 * list if we have been dropping edges. */
1153 if (active
->min_height
<= 0) {
1154 int min_height
= INT_MAX
;
1155 int is_vertical
= 1;
1157 e
= active
->head
.next
;
1159 if (e
->height_left
< min_height
)
1160 min_height
= e
->height_left
;
1161 is_vertical
&= e
->dy
== 0;
1165 active
->is_vertical
= is_vertical
;
1166 active
->min_height
= min_height
;
1169 if (active
->min_height
< GRID_Y
)
1172 /* Check for intersections as no edges end during the next row. */
1173 for (e
= active
->head
.next
; e
!= &active
->tail
; e
= e
->next
) {
1177 struct quorem x
= e
->x
;
1178 x
.quo
+= e
->dxdy_full
.quo
;
1179 x
.rem
+= e
->dxdy_full
.rem
;
1183 } else if (x
.rem
>= e
->dy
) {
1187 cell
= x
.quo
+ (x
.rem
>= e
->dy
/2);
1200 /* Merges edges on the given subpixel row from the polygon to the
1203 active_list_merge_edges_from_bucket(struct active_list
*active
,
1206 active
->head
.next
= merge_unsorted_edges (active
->head
.next
, edges
);
1210 polygon_fill_buckets (struct active_list
*active
,
1213 struct edge
**buckets
)
1215 grid_scaled_y_t min_height
= active
->min_height
;
1216 int is_vertical
= active
->is_vertical
;
1220 struct edge
*next
= edge
->next
;
1221 int suby
= edge
->ytop
- y
;
1223 buckets
[suby
]->prev
= edge
;
1224 edge
->next
= buckets
[suby
];
1226 buckets
[suby
] = edge
;
1227 if (edge
->height_left
< min_height
)
1228 min_height
= edge
->height_left
;
1229 is_vertical
&= edge
->dy
== 0;
1231 if (suby
> max_suby
)
1235 active
->is_vertical
= is_vertical
;
1236 active
->min_height
= min_height
;
1241 static void step (struct edge
*edge
)
1246 edge
->x
.quo
+= edge
->dxdy
.quo
;
1247 edge
->x
.rem
+= edge
->dxdy
.rem
;
1248 if (edge
->x
.rem
< 0) {
1250 edge
->x
.rem
+= edge
->dy
;
1251 } else if (edge
->x
.rem
>= edge
->dy
) {
1253 edge
->x
.rem
-= edge
->dy
;
1256 edge
->cell
= edge
->x
.quo
+ (edge
->x
.rem
>= edge
->dy
/2);
1260 sub_row (struct active_list
*active
,
1261 struct cell_list
*coverages
,
1264 struct edge
*edge
= active
->head
.next
;
1265 int xstart
= INT_MIN
, prev_x
= INT_MIN
;
1268 cell_list_rewind (coverages
);
1270 while (&active
->tail
!= edge
) {
1271 struct edge
*next
= edge
->next
;
1272 int xend
= edge
->cell
;
1274 if (--edge
->height_left
) {
1277 if (edge
->cell
< prev_x
) {
1278 struct edge
*pos
= edge
->prev
;
1283 } while (edge
->cell
< pos
->cell
);
1284 pos
->next
->prev
= edge
;
1285 edge
->next
= pos
->next
;
1289 prev_x
= edge
->cell
;
1290 active
->min_height
= -1;
1292 edge
->prev
->next
= next
;
1293 next
->prev
= edge
->prev
;
1296 winding
+= edge
->dir
;
1297 if ((winding
& mask
) == 0) {
1298 if (next
->cell
!= xend
) {
1299 cell_list_add_subspan (coverages
, xstart
, xend
);
1302 } else if (xstart
== INT_MIN
)
1309 inline static void dec (struct active_list
*a
, struct edge
*e
, int h
)
1311 e
->height_left
-= h
;
1312 if (e
->height_left
== 0) {
1313 e
->prev
->next
= e
->next
;
1314 e
->next
->prev
= e
->prev
;
1320 full_row (struct active_list
*active
,
1321 struct cell_list
*coverages
,
1324 struct edge
*left
= active
->head
.next
;
1326 while (&active
->tail
!= left
) {
1330 dec (active
, left
, GRID_Y
);
1332 winding
= left
->dir
;
1335 dec (active
, right
, GRID_Y
);
1337 winding
+= right
->dir
;
1338 if ((winding
& mask
) == 0 && right
->next
->cell
!= right
->cell
)
1343 right
= right
->next
;
1346 cell_list_set_rewind (coverages
);
1347 cell_list_render_edge (coverages
, left
, +1);
1348 cell_list_render_edge (coverages
, right
, -1);
1355 _glitter_scan_converter_init(glitter_scan_converter_t
*converter
, jmp_buf *jmp
)
1357 polygon_init(converter
->polygon
, jmp
);
1358 active_list_init(converter
->active
);
1359 cell_list_init(converter
->coverages
, jmp
);
1367 _glitter_scan_converter_fini(glitter_scan_converter_t
*self
)
1369 if (self
->spans
!= self
->spans_embedded
)
1372 polygon_fini(self
->polygon
);
1373 cell_list_fini(self
->coverages
);
1381 static grid_scaled_t
1382 int_to_grid_scaled(int i
, int scale
)
1384 /* Clamp to max/min representable scaled number. */
1386 if (i
>= INT_MAX
/scale
)
1390 if (i
<= INT_MIN
/scale
)
1396 #define int_to_grid_scaled_x(x) int_to_grid_scaled((x), GRID_X)
1397 #define int_to_grid_scaled_y(x) int_to_grid_scaled((x), GRID_Y)
1400 glitter_scan_converter_reset(
1401 glitter_scan_converter_t
*converter
,
1405 glitter_status_t status
;
1408 converter
->xmin
= 0; converter
->xmax
= 0;
1409 converter
->ymin
= 0; converter
->ymax
= 0;
1411 max_num_spans
= xmax
- xmin
+ 1;
1413 if (max_num_spans
> ARRAY_LENGTH(converter
->spans_embedded
)) {
1414 converter
->spans
= _cairo_malloc_ab (max_num_spans
,
1415 sizeof (cairo_half_open_span_t
));
1416 if (unlikely (converter
->spans
== NULL
))
1417 return _cairo_error (CAIRO_STATUS_NO_MEMORY
);
1419 converter
->spans
= converter
->spans_embedded
;
1421 xmin
= int_to_grid_scaled_x(xmin
);
1422 ymin
= int_to_grid_scaled_y(ymin
);
1423 xmax
= int_to_grid_scaled_x(xmax
);
1424 ymax
= int_to_grid_scaled_y(ymax
);
1426 active_list_reset(converter
->active
);
1427 cell_list_reset(converter
->coverages
);
1428 status
= polygon_reset(converter
->polygon
, ymin
, ymax
);
1432 converter
->xmin
= xmin
;
1433 converter
->xmax
= xmax
;
1434 converter
->ymin
= ymin
;
1435 converter
->ymax
= ymax
;
1436 return GLITTER_STATUS_SUCCESS
;
1439 /* INPUT_TO_GRID_X/Y (in_coord, out_grid_scaled, grid_scale)
1440 * These macros convert an input coordinate in the client's
1441 * device space to the rasterisation grid.
1443 /* Gah.. this bit of ugly defines INPUT_TO_GRID_X/Y so as to use
1444 * shifts if possible, and something saneish if not.
1446 #if !defined(INPUT_TO_GRID_Y) && defined(GRID_Y_BITS) && GRID_Y_BITS <= GLITTER_INPUT_BITS
1447 # define INPUT_TO_GRID_Y(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
1449 # define INPUT_TO_GRID_Y(in, out) INPUT_TO_GRID_general(in, out, GRID_Y)
1452 #if !defined(INPUT_TO_GRID_X) && defined(GRID_X_BITS) && GRID_X_BITS <= GLITTER_INPUT_BITS
1453 # define INPUT_TO_GRID_X(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
1455 # define INPUT_TO_GRID_X(in, out) INPUT_TO_GRID_general(in, out, GRID_X)
1458 #define INPUT_TO_GRID_general(in, out, grid_scale) do { \
1459 long long tmp__ = (long long)(grid_scale) * (in); \
1460 tmp__ += 1 << (GLITTER_INPUT_BITS-1); \
1461 tmp__ >>= GLITTER_INPUT_BITS; \
1466 polygon_add_edge (struct polygon
*polygon
,
1467 const cairo_edge_t
*edge
)
1470 grid_scaled_y_t ytop
, ybot
;
1471 const cairo_point_t
*p1
, *p2
;
1473 INPUT_TO_GRID_Y (edge
->top
, ytop
);
1474 if (ytop
< polygon
->ymin
)
1475 ytop
= polygon
->ymin
;
1477 INPUT_TO_GRID_Y (edge
->bottom
, ybot
);
1478 if (ybot
> polygon
->ymax
)
1479 ybot
= polygon
->ymax
;
1484 e
= pool_alloc (polygon
->edge_pool
.base
, sizeof (struct edge
));
1487 e
->height_left
= ybot
- ytop
;
1488 if (edge
->line
.p2
.y
> edge
->line
.p1
.y
) {
1490 p1
= &edge
->line
.p1
;
1491 p2
= &edge
->line
.p2
;
1493 e
->dir
= -edge
->dir
;
1494 p1
= &edge
->line
.p2
;
1495 p2
= &edge
->line
.p1
;
1498 if (p2
->x
== p1
->x
) {
1502 e
->dxdy
.quo
= e
->dxdy
.rem
= 0;
1503 e
->dxdy_full
.quo
= e
->dxdy_full
.rem
= 0;
1506 int64_t Ex
, Ey
, tmp
;
1508 Ex
= (int64_t)(p2
->x
- p1
->x
) * GRID_X
;
1509 Ey
= (int64_t)(p2
->y
- p1
->y
) * GRID_Y
* (2 << GLITTER_INPUT_BITS
);
1511 e
->dxdy
.quo
= Ex
* (2 << GLITTER_INPUT_BITS
) / Ey
;
1512 e
->dxdy
.rem
= Ex
* (2 << GLITTER_INPUT_BITS
) % Ey
;
1514 tmp
= (int64_t)(2*ytop
+ 1) << GLITTER_INPUT_BITS
;
1515 tmp
-= (int64_t)p1
->y
* GRID_Y
* 2;
1517 e
->x
.quo
= tmp
/ Ey
;
1518 e
->x
.rem
= tmp
% Ey
;
1520 #if GRID_X_BITS == GLITTER_INPUT_BITS
1523 tmp
= (int64_t)p1
->x
* GRID_X
;
1524 e
->x
.quo
+= tmp
>> GLITTER_INPUT_BITS
;
1525 e
->x
.rem
+= ((tmp
& ((1 << GLITTER_INPUT_BITS
) - 1)) * Ey
) / (1 << GLITTER_INPUT_BITS
);
1531 } else if (e
->x
.rem
>= Ey
) {
1536 if (e
->height_left
>= GRID_Y
) {
1537 tmp
= Ex
* (2 * GRID_Y
<< GLITTER_INPUT_BITS
);
1538 e
->dxdy_full
.quo
= tmp
/ Ey
;
1539 e
->dxdy_full
.rem
= tmp
% Ey
;
1541 e
->dxdy_full
.quo
= e
->dxdy_full
.rem
= 0;
1543 e
->cell
= e
->x
.quo
+ (e
->x
.rem
>= Ey
/2);
1547 _polygon_insert_edge_into_its_y_bucket (polygon
, e
);
1550 /* Add a new polygon edge from pixel (x1,y1) to (x2,y2) to the scan
1551 * converter. The coordinates represent pixel positions scaled by
1552 * 2**GLITTER_PIXEL_BITS. If this function fails then the scan
1553 * converter should be reset or destroyed. Dir must be +1 or -1,
1554 * with the latter reversing the orientation of the edge. */
1556 glitter_scan_converter_add_edge (glitter_scan_converter_t
*converter
,
1557 const cairo_edge_t
*edge
)
1559 polygon_add_edge (converter
->polygon
, edge
);
1563 step_edges (struct active_list
*active
, int count
)
1568 for (edge
= active
->head
.next
; edge
!= &active
->tail
; edge
= edge
->next
) {
1569 edge
->height_left
-= count
;
1570 if (! edge
->height_left
) {
1571 edge
->prev
->next
= edge
->next
;
1572 edge
->next
->prev
= edge
->prev
;
1573 active
->min_height
= -1;
1578 static glitter_status_t
1579 blit_a8 (struct cell_list
*cells
,
1580 cairo_span_renderer_t
*renderer
,
1581 cairo_half_open_span_t
*spans
,
1585 struct cell
*cell
= cells
->head
.next
;
1586 int prev_x
= xmin
, last_x
= -1;
1587 int16_t cover
= 0, last_cover
= 0;
1590 if (cell
== &cells
->tail
)
1591 return CAIRO_STATUS_SUCCESS
;
1593 /* Skip cells to the left of the clip region. */
1594 while (cell
->x
< xmin
) {
1595 cover
+= cell
->covered_height
;
1600 /* Form the spans from the coverages and areas. */
1602 for (; cell
->x
< xmax
; cell
= cell
->next
) {
1606 if (x
> prev_x
&& cover
!= last_cover
) {
1607 spans
[num_spans
].x
= prev_x
;
1608 spans
[num_spans
].coverage
= GRID_AREA_TO_ALPHA (cover
);
1614 cover
+= cell
->covered_height
*GRID_X
*2;
1615 area
= cover
- cell
->uncovered_area
;
1617 if (area
!= last_cover
) {
1618 spans
[num_spans
].x
= x
;
1619 spans
[num_spans
].coverage
= GRID_AREA_TO_ALPHA (area
);
1628 if (prev_x
<= xmax
&& cover
!= last_cover
) {
1629 spans
[num_spans
].x
= prev_x
;
1630 spans
[num_spans
].coverage
= GRID_AREA_TO_ALPHA (cover
);
1636 if (last_x
< xmax
&& last_cover
) {
1637 spans
[num_spans
].x
= xmax
;
1638 spans
[num_spans
].coverage
= 0;
1642 /* Dump them into the renderer. */
1643 return renderer
->render_rows (renderer
, y
, height
, spans
, num_spans
);
1646 #define GRID_AREA_TO_A1(A) ((GRID_AREA_TO_ALPHA (A) > 127) ? 255 : 0)
1647 static glitter_status_t
1648 blit_a1 (struct cell_list
*cells
,
1649 cairo_span_renderer_t
*renderer
,
1650 cairo_half_open_span_t
*spans
,
1654 struct cell
*cell
= cells
->head
.next
;
1655 int prev_x
= xmin
, last_x
= -1;
1657 uint8_t coverage
, last_cover
= 0;
1660 if (cell
== &cells
->tail
)
1661 return CAIRO_STATUS_SUCCESS
;
1663 /* Skip cells to the left of the clip region. */
1664 while (cell
->x
< xmin
) {
1665 cover
+= cell
->covered_height
;
1670 /* Form the spans from the coverages and areas. */
1672 for (; cell
->x
< xmax
; cell
= cell
->next
) {
1676 coverage
= GRID_AREA_TO_A1 (cover
);
1677 if (x
> prev_x
&& coverage
!= last_cover
) {
1678 last_x
= spans
[num_spans
].x
= prev_x
;
1679 last_cover
= spans
[num_spans
].coverage
= coverage
;
1683 cover
+= cell
->covered_height
*GRID_X
*2;
1684 area
= cover
- cell
->uncovered_area
;
1686 coverage
= GRID_AREA_TO_A1 (area
);
1687 if (coverage
!= last_cover
) {
1688 last_x
= spans
[num_spans
].x
= x
;
1689 last_cover
= spans
[num_spans
].coverage
= coverage
;
1696 coverage
= GRID_AREA_TO_A1 (cover
);
1697 if (prev_x
<= xmax
&& coverage
!= last_cover
) {
1698 last_x
= spans
[num_spans
].x
= prev_x
;
1699 last_cover
= spans
[num_spans
].coverage
= coverage
;
1703 if (last_x
< xmax
&& last_cover
) {
1704 spans
[num_spans
].x
= xmax
;
1705 spans
[num_spans
].coverage
= 0;
1709 return CAIRO_STATUS_SUCCESS
;
1711 /* Dump them into the renderer. */
1712 return renderer
->render_rows (renderer
, y
, height
, spans
, num_spans
);
1717 glitter_scan_converter_render(glitter_scan_converter_t
*converter
,
1718 unsigned int winding_mask
,
1720 cairo_span_renderer_t
*renderer
)
1723 int ymax_i
= converter
->ymax
/ GRID_Y
;
1724 int ymin_i
= converter
->ymin
/ GRID_Y
;
1726 int h
= ymax_i
- ymin_i
;
1727 struct polygon
*polygon
= converter
->polygon
;
1728 struct cell_list
*coverages
= converter
->coverages
;
1729 struct active_list
*active
= converter
->active
;
1730 struct edge
*buckets
[GRID_Y
] = { 0 };
1732 xmin_i
= converter
->xmin
/ GRID_X
;
1733 xmax_i
= converter
->xmax
/ GRID_X
;
1734 if (xmin_i
>= xmax_i
)
1737 /* Render each pixel row. */
1738 for (i
= 0; i
< h
; i
= j
) {
1739 int do_full_row
= 0;
1743 /* Determine if we can ignore this row or use the full pixel
1745 if (polygon_fill_buckets (active
,
1746 polygon
->y_buckets
[i
],
1750 active_list_merge_edges_from_bucket (active
, buckets
[0]);
1754 if (active
->head
.next
== &active
->tail
) {
1755 active
->min_height
= INT_MAX
;
1756 active
->is_vertical
= 1;
1757 for (; j
< h
&& ! polygon
->y_buckets
[j
]; j
++)
1762 do_full_row
= can_do_full_row (active
);
1766 /* Step by a full pixel row's worth. */
1767 full_row (active
, coverages
, winding_mask
);
1769 if (active
->is_vertical
) {
1771 polygon
->y_buckets
[j
] == NULL
&&
1772 active
->min_height
>= 2*GRID_Y
)
1774 active
->min_height
-= GRID_Y
;
1778 step_edges (active
, j
- (i
+ 1));
1783 /* Subsample this row. */
1784 for (sub
= 0; sub
< GRID_Y
; sub
++) {
1786 active_list_merge_edges_from_bucket (active
, buckets
[sub
]);
1787 buckets
[sub
] = NULL
;
1789 sub_row (active
, coverages
, winding_mask
);
1794 blit_a8 (coverages
, renderer
, converter
->spans
,
1795 i
+ymin_i
, j
-i
, xmin_i
, xmax_i
);
1797 blit_a1 (coverages
, renderer
, converter
->spans
,
1798 i
+ymin_i
, j
-i
, xmin_i
, xmax_i
);
1799 cell_list_reset (coverages
);
1801 active
->min_height
-= GRID_Y
;
1805 struct _cairo_tor_scan_converter
{
1806 cairo_scan_converter_t base
;
1808 glitter_scan_converter_t converter
[1];
1809 cairo_fill_rule_t fill_rule
;
1810 cairo_antialias_t antialias
;
1815 typedef struct _cairo_tor_scan_converter cairo_tor_scan_converter_t
;
1818 _cairo_tor_scan_converter_destroy (void *converter
)
1820 cairo_tor_scan_converter_t
*self
= converter
;
1824 _glitter_scan_converter_fini (self
->converter
);
1829 _cairo_tor_scan_converter_add_polygon (void *converter
,
1830 const cairo_polygon_t
*polygon
)
1832 cairo_tor_scan_converter_t
*self
= converter
;
1836 FILE *file
= fopen ("polygon.txt", "w");
1837 _cairo_debug_print_polygon (file
, polygon
);
1841 for (i
= 0; i
< polygon
->num_edges
; i
++)
1842 glitter_scan_converter_add_edge (self
->converter
, &polygon
->edges
[i
]);
1844 return CAIRO_STATUS_SUCCESS
;
1847 static cairo_status_t
1848 _cairo_tor_scan_converter_generate (void *converter
,
1849 cairo_span_renderer_t
*renderer
)
1851 cairo_tor_scan_converter_t
*self
= converter
;
1852 cairo_status_t status
;
1854 if ((status
= setjmp (self
->jmp
)))
1855 return _cairo_scan_converter_set_error (self
, _cairo_error (status
));
1857 glitter_scan_converter_render (self
->converter
,
1858 self
->fill_rule
== CAIRO_FILL_RULE_WINDING
? ~0 : 1,
1859 self
->antialias
!= CAIRO_ANTIALIAS_NONE
,
1861 return CAIRO_STATUS_SUCCESS
;
1864 cairo_scan_converter_t
*
1865 _cairo_tor_scan_converter_create (int xmin
,
1869 cairo_fill_rule_t fill_rule
,
1870 cairo_antialias_t antialias
)
1872 cairo_tor_scan_converter_t
*self
;
1873 cairo_status_t status
;
1875 self
= malloc (sizeof(struct _cairo_tor_scan_converter
));
1876 if (unlikely (self
== NULL
)) {
1877 status
= _cairo_error (CAIRO_STATUS_NO_MEMORY
);
1881 self
->base
.destroy
= _cairo_tor_scan_converter_destroy
;
1882 self
->base
.generate
= _cairo_tor_scan_converter_generate
;
1884 _glitter_scan_converter_init (self
->converter
, &self
->jmp
);
1885 status
= glitter_scan_converter_reset (self
->converter
,
1886 xmin
, ymin
, xmax
, ymax
);
1887 if (unlikely (status
))
1890 self
->fill_rule
= fill_rule
;
1891 self
->antialias
= antialias
;
1896 self
->base
.destroy(&self
->base
);
1898 return _cairo_scan_converter_create_in_error (status
);