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 for pointers. */
283 /* A memory pool. This is supposed to be embedded on the stack or
284 * within some other structure. It may optionally be followed by an
285 * embedded array from which requests are fulfilled until
286 * malloc needs to be called to allocate a first real chunk. */
288 /* Chunk we're allocating from. */
289 struct _pool_chunk *current;
293 /* Free list of previously allocated chunks. All have >= default
295 struct _pool_chunk *first_free;
297 /* The default capacity of a chunk. */
298 size_t default_capacity;
300 /* Header for the sentinel chunk. Directly following the pool
301 * struct should be some space for embedded elements from which
302 * the sentinel chunk allocates from. */
303 struct _pool_chunk sentinel[1];
306 /* A polygon edge. */
308 /* Next in y-bucket or active list. */
309 struct edge *next, *prev;
311 /* Number of subsample rows remaining to scan convert of this
313 grid_scaled_y_t height_left;
315 /* Original sign of the edge: +1 for downwards, -1 for upwards
320 /* Current x coordinate while the edge is on the active
321 * list. Initialised to the x coordinate of the top of the
322 * edge. The quotient is in grid_scaled_x_t units and the
323 * remainder is mod dy in grid_scaled_y_t units.*/
326 /* Advance of the current x when moving down a subsample line. */
329 /* Advance of the current x when moving down a full pixel
330 * row. Only initialised when the height of the edge is large
331 * enough that there's a chance the edge could be stepped by a
332 * full row's worth of subsample rows at a time. */
333 struct quorem dxdy_full;
335 /* The clipped y of the top of the edge. */
336 grid_scaled_y_t ytop;
338 /* y2-y1 after orienting the edge downwards. */
342 #define EDGE_Y_BUCKET_INDEX(y, ymin) (((y) - (ymin))/GRID_Y)
344 /* A collection of sorted and vertically clipped edges of the polygon.
345 * Edges are moved from the polygon to an active list while scan
348 /* The vertical clip extents. */
349 grid_scaled_y_t ymin, ymax;
351 /* Array of edges all starting in the same bucket. An edge is put
352 * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
353 * it is added to the polygon. */
354 struct edge **y_buckets;
355 struct edge *y_buckets_embedded[64];
359 struct edge embedded[32];
363 /* A cell records the effect on pixel coverage of polygon edges
364 * passing through a pixel. It contains two accumulators of pixel
367 * Consider the effects of a polygon edge on the coverage of a pixel
368 * it intersects and that of the following one. The coverage of the
369 * following pixel is the height of the edge multiplied by the width
370 * of the pixel, and the coverage of the pixel itself is the area of
371 * the trapezoid formed by the edge and the right side of the pixel.
373 * +-----------------------+-----------------------+
376 * |_______________________|_______________________|
377 * | \...................|.......................|\
378 * | \..................|.......................| |
379 * | \.................|.......................| |
380 * | \....covered.....|.......................| |
381 * | \....area.......|.......................| } covered height
382 * | \..............|.......................| |
383 * |uncovered\.............|.......................| |
384 * | area \............|.......................| |
385 * |___________\...........|.......................|/
389 * +-----------------------+-----------------------+
391 * Since the coverage of the following pixel will always be a multiple
392 * of the width of the pixel, we can store the height of the covered
393 * area instead. The coverage of the pixel itself is the total
394 * coverage minus the area of the uncovered area to the left of the
395 * edge. As it's faster to compute the uncovered area we only store
396 * that and subtract it from the total coverage later when forming
399 * The heights and areas are signed, with left edges of the polygon
400 * having positive sign and right edges having negative sign. When
401 * two edges intersect they swap their left/rightness so their
402 * contribution above and below the intersection point must be
403 * computed separately. */
407 int16_t uncovered_area;
408 int16_t covered_height;
411 /* A cell list represents the scan line sparsely as cells ordered by
412 * ascending x. It is geared towards scanning the cells in order
413 * using an internal cursor. */
416 struct cell head, tail;
418 /* Cursor state for iterating through the cell list. */
419 struct cell *cursor, *rewind;
421 /* Cells in the cell list are owned by the cell list and are
422 * allocated from this pool. */
425 struct cell embedded[32];
434 /* The active list contains edges in the current scan line ordered by
435 * the x-coordinate of the intercept of the edge and the scan line. */
437 /* Leftmost edge on the current scan line. */
438 struct edge head, tail;
440 /* A lower bound on the height of the active edges is used to
441 * estimate how soon some active edge ends. We can't advance the
442 * scan conversion by a full pixel row if an edge ends somewhere
444 grid_scaled_y_t min_height;
448 struct glitter_scan_converter {
449 struct polygon polygon[1];
450 struct active_list active[1];
451 struct cell_list coverages[1];
453 cairo_half_open_span_t *spans;
454 cairo_half_open_span_t spans_embedded[64];
457 grid_scaled_x_t xmin, xmax;
458 grid_scaled_y_t ymin, ymax;
461 /* Compute the floored division a/b. Assumes / and % perform symmetric
463 inline static struct quorem
464 floored_divrem(int a, int b)
469 if ((a^b)<0 && qr.rem) {
476 /* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
479 floored_muldivrem(int x, int a, int b)
482 long long xa = (long long)x*a;
485 if ((xa>=0) != (b>=0) && qr.rem) {
492 static struct _pool_chunk *
494 struct _pool_chunk *p,
495 struct _pool_chunk *prev_chunk,
498 p->prev_chunk = prev_chunk;
500 p->capacity = capacity;
504 static struct _pool_chunk *
505 _pool_chunk_create(struct pool *pool, size_t size)
507 struct _pool_chunk *p;
509 p = malloc(size + sizeof(struct _pool_chunk));
510 if (unlikely (NULL == p))
511 longjmp (*pool->jmp, _cairo_error (CAIRO_STATUS_NO_MEMORY));
513 return _pool_chunk_init(p, pool->current, size);
517 pool_init(struct pool *pool,
519 size_t default_capacity,
520 size_t embedded_capacity)
523 pool->current = pool->sentinel;
524 pool->first_free = NULL;
525 pool->default_capacity = default_capacity;
526 _pool_chunk_init(pool->sentinel, NULL, embedded_capacity);
530 pool_fini(struct pool *pool)
532 struct _pool_chunk *p = pool->current;
535 struct _pool_chunk *prev = p->prev_chunk;
536 if (p != pool->sentinel)
540 p = pool->first_free;
541 pool->first_free = NULL;
545 /* Satisfy an allocation by first allocating a new large enough chunk
546 * and adding it to the head of the pool's chunk list. This function
547 * is called as a fallback if pool_alloc() couldn't do a quick
548 * allocation from the current chunk in the pool. */
550 _pool_alloc_from_new_chunk(
554 struct _pool_chunk *chunk;
558 /* If the allocation is smaller than the default chunk size then
559 * try getting a chunk off the free list. Force alloc of a new
560 * chunk for large requests. */
563 if (size < pool->default_capacity) {
564 capacity = pool->default_capacity;
565 chunk = pool->first_free;
567 pool->first_free = chunk->prev_chunk;
568 _pool_chunk_init(chunk, pool->current, chunk->capacity);
573 chunk = _pool_chunk_create (pool, capacity);
574 pool->current = chunk;
576 obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
581 /* Allocate size bytes from the pool. The first allocated address
582 * returned from a pool is aligned to sizeof(void*). Subsequent
583 * addresses will maintain alignment as long as multiples of void* are
584 * allocated. Returns the address of a new memory area or %NULL on
585 * allocation failures. The pool retains ownership of the returned
588 pool_alloc (struct pool *pool, size_t size)
590 struct _pool_chunk *chunk = pool->current;
592 if (size <= chunk->capacity - chunk->size) {
593 void *obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
597 return _pool_alloc_from_new_chunk(pool, size);
601 /* Relinquish all pool_alloced memory back to the pool. */
603 pool_reset (struct pool *pool)
605 /* Transfer all used chunks to the chunk free list. */
606 struct _pool_chunk *chunk = pool->current;
607 if (chunk != pool->sentinel) {
608 while (chunk->prev_chunk != pool->sentinel) {
609 chunk = chunk->prev_chunk;
611 chunk->prev_chunk = pool->first_free;
612 pool->first_free = pool->current;
614 /* Reset the sentinel as the current chunk. */
615 pool->current = pool->sentinel;
616 pool->sentinel->size = 0;
619 /* Rewinds the cell list's cursor to the beginning. After rewinding
620 * we're good to cell_list_find() the cell any x coordinate. */
622 cell_list_rewind (struct cell_list *cells)
624 cells->cursor = &cells->head;
628 cell_list_maybe_rewind (struct cell_list *cells, int x)
630 if (x < cells->cursor->x) {
631 cells->cursor = cells->rewind;
632 if (x < cells->cursor->x)
633 cells->cursor = &cells->head;
638 cell_list_set_rewind (struct cell_list *cells)
640 cells->rewind = cells->cursor;
644 cell_list_init(struct cell_list *cells, jmp_buf *jmp)
646 pool_init(cells->cell_pool.base, jmp,
647 256*sizeof(struct cell),
648 sizeof(cells->cell_pool.embedded));
649 cells->tail.next = NULL;
650 cells->tail.x = INT_MAX;
651 cells->head.x = INT_MIN;
652 cells->head.next = &cells->tail;
653 cell_list_rewind (cells);
657 cell_list_fini(struct cell_list *cells)
659 pool_fini (cells->cell_pool.base);
662 /* Empty the cell list. This is called at the start of every pixel
665 cell_list_reset (struct cell_list *cells)
667 cell_list_rewind (cells);
668 cells->head.next = &cells->tail;
669 pool_reset (cells->cell_pool.base);
672 inline static struct cell *
673 cell_list_alloc (struct cell_list *cells,
679 cell = pool_alloc (cells->cell_pool.base, sizeof (struct cell));
680 cell->next = tail->next;
683 *(uint32_t *)&cell->uncovered_area = 0;
688 /* Find a cell at the given x-coordinate. Returns %NULL if a new cell
689 * needed to be allocated but couldn't be. Cells must be found with
690 * non-decreasing x-coordinate until the cell list is rewound using
691 * cell_list_rewind(). Ownership of the returned cell is retained by
693 inline static struct cell *
694 cell_list_find (struct cell_list *cells, int x)
696 struct cell *tail = cells->cursor;
703 if (tail->next->x > x)
710 tail = cell_list_alloc (cells, tail, x);
711 return cells->cursor = tail;
715 /* Find two cells at x1 and x2. This is exactly equivalent
718 * pair.cell1 = cell_list_find(cells, x1);
719 * pair.cell2 = cell_list_find(cells, x2);
721 * except with less function call overhead. */
722 inline static struct cell_pair
723 cell_list_find_pair(struct cell_list *cells, int x1, int x2)
725 struct cell_pair pair;
727 pair.cell1 = cells->cursor;
730 if (pair.cell1->next->x > x1)
732 pair.cell1 = pair.cell1->next;
735 if (pair.cell1->x != x1)
736 pair.cell1 = cell_list_alloc (cells, pair.cell1, x1);
738 pair.cell2 = pair.cell1;
741 if (pair.cell2->next->x > x2)
743 pair.cell2 = pair.cell2->next;
746 if (pair.cell2->x != x2)
747 pair.cell2 = cell_list_alloc (cells, pair.cell2, x2);
749 cells->cursor = pair.cell2;
753 /* Add a subpixel span covering [x1, x2) to the coverage cells. */
755 cell_list_add_subspan(struct cell_list *cells,
765 GRID_X_TO_INT_FRAC(x1, ix1, fx1);
766 GRID_X_TO_INT_FRAC(x2, ix2, fx2);
770 p = cell_list_find_pair(cells, ix1, ix2);
771 p.cell1->uncovered_area += 2*fx1;
772 ++p.cell1->covered_height;
773 p.cell2->uncovered_area -= 2*fx2;
774 --p.cell2->covered_height;
776 struct cell *cell = cell_list_find(cells, ix1);
777 cell->uncovered_area += 2*(fx1-fx2);
781 /* Adds the analytical coverage of an edge crossing the current pixel
782 * row to the coverage cells and advances the edge's x position to the
785 * This function is only called when we know that during this pixel row:
787 * 1) The relative order of all edges on the active list doesn't
788 * change. In particular, no edges intersect within this row to pixel
791 * 2) No new edges start in this row.
793 * 3) No existing edges end mid-row.
795 * This function depends on being called with all edges from the
796 * active list in the order they appear on the list (i.e. with
797 * non-decreasing x-coordinate.) */
799 cell_list_render_edge(struct cell_list *cells,
803 grid_scaled_y_t y1, y2, dy;
806 grid_scaled_x_t fx1, fx2;
808 struct quorem x1 = edge->x;
809 struct quorem x2 = x1;
811 if (! edge->vertical) {
812 x2.quo += edge->dxdy_full.quo;
813 x2.rem += edge->dxdy_full.rem;
822 GRID_X_TO_INT_FRAC(x1.quo, ix1, fx1);
823 GRID_X_TO_INT_FRAC(x2.quo, ix2, fx2);
825 /* Edge is entirely within a column? */
827 /* We always know that ix1 is >= the cell list cursor in this
828 * case due to the no-intersections precondition. */
829 struct cell *cell = cell_list_find(cells, ix1);
830 cell->covered_height += sign*GRID_Y;
831 cell->uncovered_area += sign*(fx1 + fx2)*GRID_Y;
835 /* Orient the edge left-to-right. */
836 dx = x2.quo - x1.quo;
842 tmp = ix1; ix1 = ix2; ix2 = tmp;
843 tmp = fx1; fx1 = fx2; fx2 = tmp;
851 /* Add coverage for all pixels [ix1,ix2] on this row crossed
854 struct cell_pair pair;
855 struct quorem y = floored_divrem((GRID_X - fx1)*dy, dx);
857 /* When rendering a previous edge on the active list we may
858 * advance the cell list cursor past the leftmost pixel of the
859 * current edge even though the two edges don't intersect.
860 * e.g. consider two edges going down and rightwards:
862 * --\_+---\_+-----+-----+----
867 * ----+-----+-\---+-\---+----
869 * The left edge touches cells past the starting cell of the
870 * right edge. Fortunately such cases are rare.
872 * The rewinding is never necessary if the current edge stays
873 * within a single column because we've checked before calling
874 * this function that the active list order won't change. */
875 cell_list_maybe_rewind(cells, ix1);
877 pair = cell_list_find_pair(cells, ix1, ix1+1);
878 pair.cell1->uncovered_area += sign*y.quo*(GRID_X + fx1);
879 pair.cell1->covered_height += sign*y.quo;
883 struct quorem dydx_full = floored_divrem(GRID_X*dy, dx);
884 struct cell *cell = pair.cell2;
888 grid_scaled_y_t y_skip = dydx_full.quo;
889 y.rem += dydx_full.rem;
898 cell->uncovered_area += y_skip*GRID_X;
899 cell->covered_height += y_skip;
902 cell = cell_list_find(cells, ix1);
903 } while (ix1 != ix2);
907 pair.cell2->uncovered_area += sign*(y2 - y.quo)*fx2;
908 pair.cell2->covered_height += sign*(y2 - y.quo);
913 polygon_init (struct polygon *polygon, jmp_buf *jmp)
915 polygon->ymin = polygon->ymax = 0;
916 polygon->y_buckets = polygon->y_buckets_embedded;
917 pool_init (polygon->edge_pool.base, jmp,
918 8192 - sizeof (struct _pool_chunk),
919 sizeof (polygon->edge_pool.embedded));
923 polygon_fini (struct polygon *polygon)
925 if (polygon->y_buckets != polygon->y_buckets_embedded)
926 free (polygon->y_buckets);
928 pool_fini (polygon->edge_pool.base);
931 /* Empties the polygon of all edges. The polygon is then prepared to
932 * receive new edges and clip them to the vertical range
934 static glitter_status_t
935 polygon_reset (struct polygon *polygon,
936 grid_scaled_y_t ymin,
937 grid_scaled_y_t ymax)
939 unsigned h = ymax - ymin;
940 unsigned num_buckets = EDGE_Y_BUCKET_INDEX(ymax + GRID_Y-1, ymin);
942 pool_reset(polygon->edge_pool.base);
944 if (unlikely (h > 0x7FFFFFFFU - GRID_Y))
945 goto bail_no_mem; /* even if you could, you wouldn't want to. */
947 if (polygon->y_buckets != polygon->y_buckets_embedded)
948 free (polygon->y_buckets);
950 polygon->y_buckets = polygon->y_buckets_embedded;
951 if (num_buckets > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
952 polygon->y_buckets = _cairo_malloc_ab (num_buckets,
953 sizeof (struct edge *));
954 if (unlikely (NULL == polygon->y_buckets))
957 memset (polygon->y_buckets, 0, num_buckets * sizeof (struct edge *));
959 polygon->ymin = ymin;
960 polygon->ymax = ymax;
961 return GLITTER_STATUS_SUCCESS;
966 return GLITTER_STATUS_NO_MEMORY;
970 _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
973 unsigned ix = EDGE_Y_BUCKET_INDEX(e->ytop, polygon->ymin);
974 struct edge **ptail = &polygon->y_buckets[ix];
980 polygon_add_edge (struct polygon *polygon,
981 const cairo_edge_t *edge)
986 grid_scaled_y_t ytop, ybot;
987 grid_scaled_y_t ymin = polygon->ymin;
988 grid_scaled_y_t ymax = polygon->ymax;
990 if (unlikely (edge->top >= ymax || edge->bottom <= ymin))
993 e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge));
995 dx = edge->line.p2.x - edge->line.p1.x;
996 dy = edge->line.p2.y - edge->line.p1.y;
1000 ytop = edge->top >= ymin ? edge->top : ymin;
1001 ybot = edge->bottom <= ymax ? edge->bottom : ymax;
1003 e->height_left = ybot - ytop;
1007 e->x.quo = edge->line.p1.x;
1011 e->dxdy_full.quo = 0;
1012 e->dxdy_full.rem = 0;
1014 e->vertical = FALSE;
1015 e->dxdy = floored_divrem (dx, dy);
1016 if (ytop == edge->line.p1.y) {
1017 e->x.quo = edge->line.p1.x;
1020 e->x = floored_muldivrem (ytop - edge->line.p1.y, dx, dy);
1021 e->x.quo += edge->line.p1.x;
1024 if (e->height_left >= GRID_Y) {
1025 e->dxdy_full = floored_muldivrem (GRID_Y, dx, dy);
1027 e->dxdy_full.quo = 0;
1028 e->dxdy_full.rem = 0;
1032 _polygon_insert_edge_into_its_y_bucket (polygon, e);
1034 e->x.rem -= dy; /* Bias the remainder for faster
1035 * edge advancement. */
1039 active_list_reset (struct active_list *active)
1041 active->head.vertical = 1;
1042 active->head.height_left = INT_MAX;
1043 active->head.x.quo = INT_MIN;
1044 active->head.prev = NULL;
1045 active->head.next = &active->tail;
1046 active->tail.prev = &active->head;
1047 active->tail.next = NULL;
1048 active->tail.x.quo = INT_MAX;
1049 active->tail.height_left = INT_MAX;
1050 active->tail.vertical = 1;
1051 active->min_height = 0;
1052 active->is_vertical = 1;
1056 active_list_init(struct active_list *active)
1058 active_list_reset(active);
1062 * Merge two sorted edge lists.
1064 * - head_a: The head of the first list.
1065 * - head_b: The head of the second list; head_b cannot be NULL.
1067 * Returns the head of the merged list.
1069 * Implementation notes:
1070 * To make it fast (in particular, to reduce to an insertion sort whenever
1071 * one of the two input lists only has a single element) we iterate through
1072 * a list until its head becomes greater than the head of the other list,
1073 * then we switch their roles. As soon as one of the two lists is empty, we
1074 * just attach the other one to the current list and exit.
1075 * Writes to memory are only needed to "switch" lists (as it also requires
1076 * attaching to the output list the list which we will be iterating next) and
1077 * to attach the last non-empty list.
1079 static struct edge *
1080 merge_sorted_edges (struct edge *head_a, struct edge *head_b)
1082 struct edge *head, **next, *prev;
1085 prev = head_a->prev;
1087 if (head_a->x.quo <= head_b->x.quo) {
1091 head_b->prev = prev;
1097 while (head_a != NULL && head_a->x.quo <= x) {
1099 next = &head_a->next;
1100 head_a = head_a->next;
1103 head_b->prev = prev;
1110 while (head_b != NULL && head_b->x.quo <= x) {
1112 next = &head_b->next;
1113 head_b = head_b->next;
1116 head_a->prev = prev;
1124 * Sort (part of) a list.
1126 * - list: The list to be sorted; list cannot be NULL.
1127 * - limit: Recursion limit.
1129 * - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
1130 * input list; if the input list has fewer elements, head_out be a sorted list
1131 * containing all the elements of the input list.
1132 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
1133 * all the elements of the input list).
1135 * Implementation notes:
1136 * Special case single element list, unroll/inline the sorting of the first two elements.
1137 * Some tail recursion is used since we iterate on the bottom-up solution of the problem
1138 * (we start with a small sorted list and keep merging other lists of the same size to it).
1140 static struct edge *
1141 sort_edges (struct edge *list,
1143 struct edge **head_out)
1145 struct edge *head_other, *remaining;
1148 head_other = list->next;
1150 if (head_other == NULL) {
1155 remaining = head_other->next;
1156 if (list->x.quo <= head_other->x.quo) {
1158 head_other->next = NULL;
1160 *head_out = head_other;
1161 head_other->prev = list->prev;
1162 head_other->next = list;
1163 list->prev = head_other;
1167 for (i = 0; i < level && remaining; i++) {
1168 remaining = sort_edges (remaining, i, &head_other);
1169 *head_out = merge_sorted_edges (*head_out, head_other);
1175 static struct edge *
1176 merge_unsorted_edges (struct edge *head, struct edge *unsorted)
1178 sort_edges (unsorted, UINT_MAX, &unsorted);
1179 return merge_sorted_edges (head, unsorted);
1182 /* Test if the edges on the active list can be safely advanced by a
1183 * full row without intersections or any edges ending. */
1185 can_do_full_row (struct active_list *active)
1187 const struct edge *e;
1188 int prev_x = INT_MIN;
1190 /* Recomputes the minimum height of all edges on the active
1191 * list if we have been dropping edges. */
1192 if (active->min_height <= 0) {
1193 int min_height = INT_MAX;
1194 int is_vertical = 1;
1196 e = active->head.next;
1198 if (e->height_left < min_height)
1199 min_height = e->height_left;
1200 is_vertical &= e->vertical;
1204 active->is_vertical = is_vertical;
1205 active->min_height = min_height;
1208 if (active->min_height < GRID_Y)
1211 /* Check for intersections as no edges end during the next row. */
1212 for (e = active->head.next; e != &active->tail; e = e->next) {
1213 struct quorem x = e->x;
1215 if (! e->vertical) {
1216 x.quo += e->dxdy_full.quo;
1217 x.rem += e->dxdy_full.rem;
1231 /* Merges edges on the given subpixel row from the polygon to the
1234 active_list_merge_edges_from_bucket(struct active_list *active,
1237 active->head.next = merge_unsorted_edges (active->head.next, edges);
1241 polygon_fill_buckets (struct active_list *active,
1244 struct edge **buckets)
1246 grid_scaled_y_t min_height = active->min_height;
1247 int is_vertical = active->is_vertical;
1250 struct edge *next = edge->next;
1251 int suby = edge->ytop - y;
1253 buckets[suby]->prev = edge;
1254 edge->next = buckets[suby];
1256 buckets[suby] = edge;
1257 if (edge->height_left < min_height)
1258 min_height = edge->height_left;
1259 is_vertical &= edge->vertical;
1263 active->is_vertical = is_vertical;
1264 active->min_height = min_height;
1268 sub_row (struct active_list *active,
1269 struct cell_list *coverages,
1272 struct edge *edge = active->head.next;
1273 int xstart = INT_MIN, prev_x = INT_MIN;
1276 cell_list_rewind (coverages);
1278 while (&active->tail != edge) {
1279 struct edge *next = edge->next;
1280 int xend = edge->x.quo;
1282 if (--edge->height_left) {
1283 edge->x.quo += edge->dxdy.quo;
1284 edge->x.rem += edge->dxdy.rem;
1285 if (edge->x.rem >= 0) {
1287 edge->x.rem -= edge->dy;
1290 if (edge->x.quo < prev_x) {
1291 struct edge *pos = edge->prev;
1296 } while (edge->x.quo < pos->x.quo);
1297 pos->next->prev = edge;
1298 edge->next = pos->next;
1302 prev_x = edge->x.quo;
1304 edge->prev->next = next;
1305 next->prev = edge->prev;
1308 winding += edge->dir;
1309 if ((winding & mask) == 0) {
1310 if (next->x.quo != xend) {
1311 cell_list_add_subspan (coverages, xstart, xend);
1314 } else if (xstart == INT_MIN)
1321 inline static void dec (struct edge *e, int h)
1323 e->height_left -= h;
1324 if (e->height_left == 0) {
1325 e->prev->next = e->next;
1326 e->next->prev = e->prev;
1330 inline static void full_step (struct edge *e)
1332 if (! e->vertical) {
1333 e->x.quo += e->dxdy_full.quo;
1334 e->x.rem += e->dxdy_full.rem;
1335 if (e->x.rem >= 0) {
1343 full_row (struct active_list *active,
1344 struct cell_list *coverages,
1347 struct edge *left = active->head.next;
1349 while (&active->tail != left) {
1355 winding = left->dir;
1358 dec (right, GRID_Y);
1360 winding += right->dir;
1361 if ((winding & mask) == 0 && right->next->x.quo != right->x.quo)
1366 right = right->next;
1369 cell_list_set_rewind (coverages);
1370 cell_list_render_edge (coverages, left, +1);
1371 cell_list_render_edge (coverages, right, -1);
1378 _glitter_scan_converter_init(glitter_scan_converter_t *converter, jmp_buf *jmp)
1380 polygon_init(converter->polygon, jmp);
1381 active_list_init(converter->active);
1382 cell_list_init(converter->coverages, jmp);
1390 _glitter_scan_converter_fini(glitter_scan_converter_t *self)
1392 if (self->spans != self->spans_embedded)
1395 polygon_fini(self->polygon);
1396 cell_list_fini(self->coverages);
1404 static grid_scaled_t
1405 int_to_grid_scaled(int i, int scale)
1407 /* Clamp to max/min representable scaled number. */
1409 if (i >= INT_MAX/scale)
1413 if (i <= INT_MIN/scale)
1419 #define int_to_grid_scaled_x(x) int_to_grid_scaled((x), GRID_X)
1420 #define int_to_grid_scaled_y(x) int_to_grid_scaled((x), GRID_Y)
1423 glitter_scan_converter_reset(
1424 glitter_scan_converter_t *converter,
1428 glitter_status_t status;
1431 converter->xmin = 0; converter->xmax = 0;
1432 converter->ymin = 0; converter->ymax = 0;
1434 max_num_spans = xmax - xmin + 1;
1436 if (max_num_spans > ARRAY_LENGTH(converter->spans_embedded)) {
1437 converter->spans = _cairo_malloc_ab (max_num_spans,
1438 sizeof (cairo_half_open_span_t));
1439 if (unlikely (converter->spans == NULL))
1440 return _cairo_error (CAIRO_STATUS_NO_MEMORY);
1442 converter->spans = converter->spans_embedded;
1444 xmin = int_to_grid_scaled_x(xmin);
1445 ymin = int_to_grid_scaled_y(ymin);
1446 xmax = int_to_grid_scaled_x(xmax);
1447 ymax = int_to_grid_scaled_y(ymax);
1449 active_list_reset(converter->active);
1450 cell_list_reset(converter->coverages);
1451 status = polygon_reset(converter->polygon, ymin, ymax);
1455 converter->xmin = xmin;
1456 converter->xmax = xmax;
1457 converter->ymin = ymin;
1458 converter->ymax = ymax;
1459 return GLITTER_STATUS_SUCCESS;
1462 /* INPUT_TO_GRID_X/Y (in_coord, out_grid_scaled, grid_scale)
1463 * These macros convert an input coordinate in the client's
1464 * device space to the rasterisation grid.
1466 /* Gah.. this bit of ugly defines INPUT_TO_GRID_X/Y so as to use
1467 * shifts if possible, and something saneish if not.
1469 #if !defined(INPUT_TO_GRID_Y) && defined(GRID_Y_BITS) && GRID_Y_BITS <= GLITTER_INPUT_BITS
1470 # define INPUT_TO_GRID_Y(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
1472 # define INPUT_TO_GRID_Y(in, out) INPUT_TO_GRID_general(in, out, GRID_Y)
1475 #if !defined(INPUT_TO_GRID_X) && defined(GRID_X_BITS) && GRID_X_BITS <= GLITTER_INPUT_BITS
1476 # define INPUT_TO_GRID_X(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
1478 # define INPUT_TO_GRID_X(in, out) INPUT_TO_GRID_general(in, out, GRID_X)
1481 #define INPUT_TO_GRID_general(in, out, grid_scale) do { \
1482 long long tmp__ = (long long)(grid_scale) * (in); \
1483 tmp__ >>= GLITTER_INPUT_BITS; \
1487 /* Add a new polygon edge from pixel (x1,y1) to (x2,y2) to the scan
1488 * converter. The coordinates represent pixel positions scaled by
1489 * 2**GLITTER_PIXEL_BITS. If this function fails then the scan
1490 * converter should be reset or destroyed. Dir must be +1 or -1,
1491 * with the latter reversing the orientation of the edge. */
1493 glitter_scan_converter_add_edge (glitter_scan_converter_t *converter,
1494 const cairo_edge_t *edge)
1498 INPUT_TO_GRID_Y (edge->top, e.top);
1499 INPUT_TO_GRID_Y (edge->bottom, e.bottom);
1500 if (e.top >= e.bottom)
1503 /* XXX: possible overflows if GRID_X/Y > 2**GLITTER_INPUT_BITS */
1504 INPUT_TO_GRID_Y (edge->line.p1.y, e.line.p1.y);
1505 INPUT_TO_GRID_Y (edge->line.p2.y, e.line.p2.y);
1506 if (e.line.p1.y == e.line.p2.y)
1509 INPUT_TO_GRID_X (edge->line.p1.x, e.line.p1.x);
1510 INPUT_TO_GRID_X (edge->line.p2.x, e.line.p2.x);
1514 polygon_add_edge (converter->polygon, &e);
1518 step_edges (struct active_list *active, int count)
1523 for (edge = active->head.next; edge != &active->tail; edge = edge->next) {
1524 edge->height_left -= count;
1525 if (! edge->height_left) {
1526 edge->prev->next = edge->next;
1527 edge->next->prev = edge->prev;
1532 static glitter_status_t
1533 blit_a8 (struct cell_list *cells,
1534 cairo_span_renderer_t *renderer,
1535 cairo_half_open_span_t *spans,
1539 struct cell *cell = cells->head.next;
1540 int prev_x = xmin, last_x = -1;
1541 int16_t cover = 0, last_cover = 0;
1544 if (cell == &cells->tail)
1545 return CAIRO_STATUS_SUCCESS;
1547 /* Skip cells to the left of the clip region. */
1548 while (cell->x < xmin) {
1549 cover += cell->covered_height;
1554 /* Form the spans from the coverages and areas. */
1556 for (; cell->x < xmax; cell = cell->next) {
1560 if (x > prev_x && cover != last_cover) {
1561 spans[num_spans].x = prev_x;
1562 spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
1568 cover += cell->covered_height*GRID_X*2;
1569 area = cover - cell->uncovered_area;
1571 if (area != last_cover) {
1572 spans[num_spans].x = x;
1573 spans[num_spans].coverage = GRID_AREA_TO_ALPHA (area);
1582 if (prev_x <= xmax && cover != last_cover) {
1583 spans[num_spans].x = prev_x;
1584 spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
1590 if (last_x < xmax && last_cover) {
1591 spans[num_spans].x = xmax;
1592 spans[num_spans].coverage = 0;
1596 /* Dump them into the renderer. */
1597 return renderer->render_rows (renderer, y, height, spans, num_spans);
1600 #define GRID_AREA_TO_A1(A) ((GRID_AREA_TO_ALPHA (A) > 127) ? 255 : 0)
1601 static glitter_status_t
1602 blit_a1 (struct cell_list *cells,
1603 cairo_span_renderer_t *renderer,
1604 cairo_half_open_span_t *spans,
1608 struct cell *cell = cells->head.next;
1609 int prev_x = xmin, last_x = -1;
1611 uint8_t coverage, last_cover = 0;
1614 if (cell == &cells->tail)
1615 return CAIRO_STATUS_SUCCESS;
1617 /* Skip cells to the left of the clip region. */
1618 while (cell->x < xmin) {
1619 cover += cell->covered_height;
1624 /* Form the spans from the coverages and areas. */
1626 for (; cell->x < xmax; cell = cell->next) {
1630 coverage = GRID_AREA_TO_A1 (cover);
1631 if (x > prev_x && coverage != last_cover) {
1632 last_x = spans[num_spans].x = prev_x;
1633 last_cover = spans[num_spans].coverage = coverage;
1637 cover += cell->covered_height*GRID_X*2;
1638 area = cover - cell->uncovered_area;
1640 coverage = GRID_AREA_TO_A1 (area);
1641 if (coverage != last_cover) {
1642 last_x = spans[num_spans].x = x;
1643 last_cover = spans[num_spans].coverage = coverage;
1650 coverage = GRID_AREA_TO_A1 (cover);
1651 if (prev_x <= xmax && coverage != last_cover) {
1652 last_x = spans[num_spans].x = prev_x;
1653 last_cover = spans[num_spans].coverage = coverage;
1657 if (last_x < xmax && last_cover) {
1658 spans[num_spans].x = xmax;
1659 spans[num_spans].coverage = 0;
1663 return CAIRO_STATUS_SUCCESS;
1665 /* Dump them into the renderer. */
1666 return renderer->render_rows (renderer, y, height, spans, num_spans);
1671 glitter_scan_converter_render(glitter_scan_converter_t *converter,
1672 unsigned int winding_mask,
1674 cairo_span_renderer_t *renderer)
1677 int ymax_i = converter->ymax / GRID_Y;
1678 int ymin_i = converter->ymin / GRID_Y;
1680 int h = ymax_i - ymin_i;
1681 struct polygon *polygon = converter->polygon;
1682 struct cell_list *coverages = converter->coverages;
1683 struct active_list *active = converter->active;
1684 struct edge *buckets[GRID_Y] = { 0 };
1686 xmin_i = converter->xmin / GRID_X;
1687 xmax_i = converter->xmax / GRID_X;
1688 if (xmin_i >= xmax_i)
1691 /* Render each pixel row. */
1692 for (i = 0; i < h; i = j) {
1693 int do_full_row = 0;
1697 /* Determine if we can ignore this row or use the full pixel
1699 if (! polygon->y_buckets[i]) {
1700 if (active->head.next == &active->tail) {
1701 active->min_height = INT_MAX;
1702 active->is_vertical = 1;
1703 for (; j < h && ! polygon->y_buckets[j]; j++)
1708 do_full_row = can_do_full_row (active);
1712 /* Step by a full pixel row's worth. */
1713 full_row (active, coverages, winding_mask);
1715 if (active->is_vertical) {
1717 polygon->y_buckets[j] == NULL &&
1718 active->min_height >= 2*GRID_Y)
1720 active->min_height -= GRID_Y;
1724 step_edges (active, j - (i + 1));
1729 polygon_fill_buckets (active,
1730 polygon->y_buckets[i],
1734 /* Subsample this row. */
1735 for (sub = 0; sub < GRID_Y; sub++) {
1737 active_list_merge_edges_from_bucket (active, buckets[sub]);
1738 buckets[sub] = NULL;
1741 sub_row (active, coverages, winding_mask);
1746 blit_a8 (coverages, renderer, converter->spans,
1747 i+ymin_i, j-i, xmin_i, xmax_i);
1749 blit_a1 (coverages, renderer, converter->spans,
1750 i+ymin_i, j-i, xmin_i, xmax_i);
1751 cell_list_reset (coverages);
1753 active->min_height -= GRID_Y;
1757 struct _cairo_tor_scan_converter {
1758 cairo_scan_converter_t base;
1760 glitter_scan_converter_t converter[1];
1761 cairo_fill_rule_t fill_rule;
1762 cairo_antialias_t antialias;
1767 typedef struct _cairo_tor_scan_converter cairo_tor_scan_converter_t;
1770 _cairo_tor_scan_converter_destroy (void *converter)
1772 cairo_tor_scan_converter_t *self = converter;
1776 _glitter_scan_converter_fini (self->converter);
1781 _cairo_tor_scan_converter_add_polygon (void *converter,
1782 const cairo_polygon_t *polygon)
1784 cairo_tor_scan_converter_t *self = converter;
1788 FILE *file = fopen ("polygon.txt", "w");
1789 _cairo_debug_print_polygon (file, polygon);
1793 for (i = 0; i < polygon->num_edges; i++)
1794 glitter_scan_converter_add_edge (self->converter, &polygon->edges[i]);
1796 return CAIRO_STATUS_SUCCESS;
1799 static cairo_status_t
1800 _cairo_tor_scan_converter_generate (void *converter,
1801 cairo_span_renderer_t *renderer)
1803 cairo_tor_scan_converter_t *self = converter;
1804 cairo_status_t status;
1806 if ((status = setjmp (self->jmp)))
1807 return _cairo_scan_converter_set_error (self, _cairo_error (status));
1809 glitter_scan_converter_render (self->converter,
1810 self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
1811 self->antialias != CAIRO_ANTIALIAS_NONE,
1813 return CAIRO_STATUS_SUCCESS;
1816 cairo_scan_converter_t *
1817 _cairo_tor_scan_converter_create (int xmin,
1821 cairo_fill_rule_t fill_rule,
1822 cairo_antialias_t antialias)
1824 cairo_tor_scan_converter_t *self;
1825 cairo_status_t status;
1827 self = malloc (sizeof(struct _cairo_tor_scan_converter));
1828 if (unlikely (self == NULL)) {
1829 status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
1833 self->base.destroy = _cairo_tor_scan_converter_destroy;
1834 self->base.generate = _cairo_tor_scan_converter_generate;
1836 _glitter_scan_converter_init (self->converter, &self->jmp);
1837 status = glitter_scan_converter_reset (self->converter,
1838 xmin, ymin, xmax, ymax);
1839 if (unlikely (status))
1842 self->fill_rule = fill_rule;
1843 self->antialias = antialias;
1848 self->base.destroy(&self->base);
1850 return _cairo_scan_converter_create_in_error (status);