Lines
0 %
Functions
Branches
/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
/* glitter-paths - polygon scan converter
*
* Copyright (c) 2008 M Joonas Pihlaja
* Copyright (c) 2007 David Turner
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
/* This is the Glitter paths scan converter incorporated into cairo.
* The source is from commit 734c53237a867a773640bd5b64816249fa1730f8
* of
* https://gitweb.freedesktop.org/?p=users/joonas/glitter-paths
/* Glitter-paths is a stand alone polygon rasteriser derived from
* David Turner's reimplementation of Tor Anderssons's 15x17
* supersampling rasteriser from the Apparition graphics library. The
* main new feature here is cheaply choosing per-scan line between
* doing fully analytical coverage computation for an entire row at a
* time vs. using a supersampling approach.
* David Turner's code can be found at
* http://david.freetype.org/rasterizer-shootout/raster-comparison-20070813.tar.bz2
* In particular this file incorporates large parts of ftgrays_tor10.h
* from raster-comparison-20070813.tar.bz2
/* Overview
* A scan converter's basic purpose to take polygon edges and convert
* them into an RLE compressed A8 mask. This one works in two phases:
* gathering edges and generating spans.
* 1) As the user feeds the scan converter edges they are vertically
* clipped and bucketted into a _polygon_ data structure. The edges
* are also snapped from the user's coordinates to the subpixel grid
* coordinates used during scan conversion.
* user
* |
* | edges
* V
* polygon buckets
* 2) Generating spans works by performing a vertical sweep of pixel
* rows from top to bottom and maintaining an _active_list_ of edges
* that intersect the row. From the active list the fill rule
* determines which edges are the left and right edges of the start of
* each span, and their contribution is then accumulated into a pixel
* coverage list (_cell_list_) as coverage deltas. Once the coverage
* deltas of all edges are known we can form spans of constant pixel
* coverage by summing the deltas during a traversal of the cell list.
* At the end of a pixel row the cell list is sent to a coverage
* blitter for rendering to some target surface.
* The pixel coverages are computed by either supersampling the row
* and box filtering a mono rasterisation, or by computing the exact
* coverages of edges in the active list. The supersampling method is
* used whenever some edge starts or stops within the row or there are
* edge intersections in the row.
* polygon bucket for \
* current pixel row |
* | |
* | activate new edges | Repeat GRID_Y times if we
* V \ are supersampling this row,
* active list / or just once if we're computing
* | | analytical coverage.
* | coverage deltas |
* V |
* pixel coverage list /
* coverage blitter
#include "cairoint.h"
#include "cairo-spans-private.h"
#include "cairo-error-private.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <setjmp.h>
/* The input coordinate scale and the rasterisation grid scales. */
#define GLITTER_INPUT_BITS CAIRO_FIXED_FRAC_BITS
#define GRID_X_BITS CAIRO_FIXED_FRAC_BITS
#define GRID_Y 15
/* Set glitter up to use a cairo span renderer to do the coverage
* blitting. */
struct pool;
struct cell_list;
/*-------------------------------------------------------------------------
* glitter-paths.h
/* "Input scaled" numbers are fixed precision reals with multiplier
* 2**GLITTER_INPUT_BITS. Input coordinates are given to glitter as
* pixel scaled numbers. These get converted to the internal grid
* scaled numbers as soon as possible. Internal overflow is possible
* if GRID_X/Y inside glitter-paths.c is larger than
* 1<<GLITTER_INPUT_BITS. */
#ifndef GLITTER_INPUT_BITS
# define GLITTER_INPUT_BITS 8
#endif
#define GLITTER_INPUT_SCALE (1<<GLITTER_INPUT_BITS)
typedef int glitter_input_scaled_t;
/* Opaque type for scan converting. */
typedef struct glitter_scan_converter glitter_scan_converter_t;
* glitter-paths.c: Implementation internal types
/* All polygon coordinates are snapped onto a subsample grid. "Grid
* scaled" numbers are fixed precision reals with multiplier GRID_X or
* GRID_Y. */
typedef int grid_scaled_t;
typedef int grid_scaled_x_t;
typedef int grid_scaled_y_t;
/* Default x/y scale factors.
* You can either define GRID_X/Y_BITS to get a power-of-two scale
* or define GRID_X/Y separately. */
#if !defined(GRID_X) && !defined(GRID_X_BITS)
# define GRID_X_BITS 8
#if !defined(GRID_Y) && !defined(GRID_Y_BITS)
# define GRID_Y 15
/* Use GRID_X/Y_BITS to define GRID_X/Y if they're available. */
#ifdef GRID_X_BITS
# define GRID_X (1 << GRID_X_BITS)
#ifdef GRID_Y_BITS
# define GRID_Y (1 << GRID_Y_BITS)
/* The GRID_X_TO_INT_FRAC macro splits a grid scaled coordinate into
* integer and fractional parts. The integer part is floored. */
#if defined(GRID_X_TO_INT_FRAC)
/* do nothing */
#elif defined(GRID_X_BITS)
# define GRID_X_TO_INT_FRAC(x, i, f) \
_GRID_TO_INT_FRAC_shift(x, i, f, GRID_X_BITS)
#else
_GRID_TO_INT_FRAC_general(x, i, f, GRID_X)
#define _GRID_TO_INT_FRAC_general(t, i, f, m) do { \
(i) = (t) / (m); \
(f) = (t) % (m); \
if ((f) < 0) { \
--(i); \
(f) += (m); \
} \
} while (0)
#define _GRID_TO_INT_FRAC_shift(t, i, f, b) do { \
(f) = (t) & ((1 << (b)) - 1); \
(i) = (t) >> (b); \
/* A grid area is a real in [0,1] scaled by 2*GRID_X*GRID_Y. We want
* to be able to represent exactly areas of subpixel trapezoids whose
* vertices are given in grid scaled coordinates. The scale factor
* comes from needing to accurately represent the area 0.5*dx*dy of a
* triangle with base dx and height dy in grid scaled numbers. */
typedef int grid_area_t;
#define GRID_XY (2*GRID_X*GRID_Y) /* Unit area on the grid. */
/* GRID_AREA_TO_ALPHA(area): map [0,GRID_XY] to [0,255]. */
#if GRID_XY == 510
# define GRID_AREA_TO_ALPHA(c) (((c)+1) >> 1)
#elif GRID_XY == 255
# define GRID_AREA_TO_ALPHA(c) (c)
#elif GRID_XY == 64
# define GRID_AREA_TO_ALPHA(c) (((c) << 2) | -(((c) & 0x40) >> 6))
#elif GRID_XY == 128
# define GRID_AREA_TO_ALPHA(c) ((((c) << 1) | -((c) >> 7)) & 255)
#elif GRID_XY == 256
# define GRID_AREA_TO_ALPHA(c) (((c) | -((c) >> 8)) & 255)
#elif GRID_XY == 15
# define GRID_AREA_TO_ALPHA(c) (((c) << 4) + (c))
#elif GRID_XY == 2*256*15
# define GRID_AREA_TO_ALPHA(c) (((c) + ((c)<<4) + 256) >> 9)
# define GRID_AREA_TO_ALPHA(c) (((c)*255 + GRID_XY/2) / GRID_XY)
#define UNROLL3(x) x x x
struct quorem {
int32_t quo;
int32_t rem;
};
/* Header for a chunk of memory in a memory pool. */
struct _pool_chunk {
/* # bytes used in this chunk. */
size_t size;
/* # bytes total in this chunk */
size_t capacity;
/* Pointer to the previous chunk or %NULL if this is the sentinel
* chunk in the pool header. */
struct _pool_chunk *prev_chunk;
/* Actual data starts here. Well aligned for pointers. */
/* A memory pool. This is supposed to be embedded on the stack or
* within some other structure. It may optionally be followed by an
* embedded array from which requests are fulfilled until
* malloc needs to be called to allocate a first real chunk. */
struct pool {
/* Chunk we're allocating from. */
struct _pool_chunk *current;
jmp_buf *jmp;
/* Free list of previously allocated chunks. All have >= default
* capacity. */
struct _pool_chunk *first_free;
/* The default capacity of a chunk. */
size_t default_capacity;
/* Header for the sentinel chunk. Directly following the pool
* struct should be some space for embedded elements from which
* the sentinel chunk allocates from. */
struct _pool_chunk sentinel[1];
/* A polygon edge. */
struct edge {
/* Next in y-bucket or active list. */
struct edge *next;
/* Current x coordinate while the edge is on the active
* list. Initialised to the x coordinate of the top of the
* edge. The quotient is in grid_scaled_x_t units and the
* remainder is mod dy in grid_scaled_y_t units.*/
struct quorem x;
/* Advance of the current x when moving down a subsample line. */
struct quorem dxdy;
/* Advance of the current x when moving down a full pixel
* row. Only initialised when the height of the edge is large
* enough that there's a chance the edge could be stepped by a
* full row's worth of subsample rows at a time. */
struct quorem dxdy_full;
/* The clipped y of the top of the edge. */
grid_scaled_y_t ytop;
/* y2-y1 after orienting the edge downwards. */
grid_scaled_y_t dy;
/* Number of subsample rows remaining to scan convert of this
* edge. */
grid_scaled_y_t height_left;
/* Original sign of the edge: +1 for downwards, -1 for upwards
* edges. */
int dir;
int vertical;
int clip;
/* Number of subsample rows per y-bucket. Must be GRID_Y. */
#define EDGE_Y_BUCKET_HEIGHT GRID_Y
#define EDGE_Y_BUCKET_INDEX(y, ymin) (((y) - (ymin))/EDGE_Y_BUCKET_HEIGHT)
/* A collection of sorted and vertically clipped edges of the polygon.
* Edges are moved from the polygon to an active list while scan
* converting. */
struct polygon {
/* The vertical clip extents. */
grid_scaled_y_t ymin, ymax;
/* Array of edges all starting in the same bucket. An edge is put
* into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
* it is added to the polygon. */
struct edge **y_buckets;
struct edge *y_buckets_embedded[64];
struct {
struct pool base[1];
struct edge embedded[32];
} edge_pool;
/* A cell records the effect on pixel coverage of polygon edges
* passing through a pixel. It contains two accumulators of pixel
* coverage.
* Consider the effects of a polygon edge on the coverage of a pixel
* it intersects and that of the following one. The coverage of the
* following pixel is the height of the edge multiplied by the width
* of the pixel, and the coverage of the pixel itself is the area of
* the trapezoid formed by the edge and the right side of the pixel.
* +-----------------------+-----------------------+
* | | |
* |_______________________|_______________________|
* | \...................|.......................|\
* | \..................|.......................| |
* | \.................|.......................| |
* | \....covered.....|.......................| |
* | \....area.......|.......................| } covered height
* | \..............|.......................| |
* |uncovered\.............|.......................| |
* | area \............|.......................| |
* |___________\...........|.......................|/
* Since the coverage of the following pixel will always be a multiple
* of the width of the pixel, we can store the height of the covered
* area instead. The coverage of the pixel itself is the total
* coverage minus the area of the uncovered area to the left of the
* edge. As it's faster to compute the uncovered area we only store
* that and subtract it from the total coverage later when forming
* spans to blit.
* The heights and areas are signed, with left edges of the polygon
* having positive sign and right edges having negative sign. When
* two edges intersect they swap their left/rightness so their
* contribution above and below the intersection point must be
* computed separately. */
struct cell {
struct cell *next;
int x;
grid_area_t uncovered_area;
grid_scaled_y_t covered_height;
grid_scaled_y_t clipped_height;
/* A cell list represents the scan line sparsely as cells ordered by
* ascending x. It is geared towards scanning the cells in order
* using an internal cursor. */
struct cell_list {
/* Sentinel nodes */
struct cell head, tail;
/* Cursor state for iterating through the cell list. */
struct cell *cursor;
/* Cells in the cell list are owned by the cell list and are
* allocated from this pool. */
struct cell embedded[32];
} cell_pool;
struct cell_pair {
struct cell *cell1;
struct cell *cell2;
/* The active list contains edges in the current scan line ordered by
* the x-coordinate of the intercept of the edge and the scan line. */
struct active_list {
/* Leftmost edge on the current scan line. */
struct edge *head;
/* A lower bound on the height of the active edges is used to
* estimate how soon some active edge ends. We can't advance the
* scan conversion by a full pixel row if an edge ends somewhere
* within it. */
grid_scaled_y_t min_height;
struct glitter_scan_converter {
struct polygon polygon[1];
struct active_list active[1];
struct cell_list coverages[1];
/* Clip box. */
/* Compute the floored division a/b. Assumes / and % perform symmetric
* division. */
inline static struct quorem
floored_divrem(int a, int b)
{
struct quorem qr;
qr.quo = a/b;
qr.rem = a%b;
if ((a^b)<0 && qr.rem) {
qr.quo -= 1;
qr.rem += b;
}
return qr;
/* Compute the floored division (x*a)/b. Assumes / and % perform symmetric
static struct quorem
floored_muldivrem(int x, int a, int b)
long long xa = (long long)x*a;
qr.quo = xa/b;
qr.rem = xa%b;
if ((xa>=0) != (b>=0) && qr.rem) {
static struct _pool_chunk *
_pool_chunk_init(
struct _pool_chunk *p,
struct _pool_chunk *prev_chunk,
size_t capacity)
p->prev_chunk = prev_chunk;
p->size = 0;
p->capacity = capacity;
return p;
_pool_chunk_create(struct pool *pool, size_t size)
struct _pool_chunk *p;
p = _cairo_malloc (size + sizeof(struct _pool_chunk));
if (unlikely (NULL == p))
longjmp (*pool->jmp, _cairo_error (CAIRO_STATUS_NO_MEMORY));
return _pool_chunk_init(p, pool->current, size);
static void
pool_init(struct pool *pool,
jmp_buf *jmp,
size_t default_capacity,
size_t embedded_capacity)
pool->jmp = jmp;
pool->current = pool->sentinel;
pool->first_free = NULL;
pool->default_capacity = default_capacity;
_pool_chunk_init(pool->sentinel, NULL, embedded_capacity);
pool_fini(struct pool *pool)
struct _pool_chunk *p = pool->current;
do {
while (NULL != p) {
struct _pool_chunk *prev = p->prev_chunk;
if (p != pool->sentinel)
free(p);
p = prev;
p = pool->first_free;
} while (NULL != p);
/* Satisfy an allocation by first allocating a new large enough chunk
* and adding it to the head of the pool's chunk list. This function
* is called as a fallback if pool_alloc() couldn't do a quick
* allocation from the current chunk in the pool. */
static void *
_pool_alloc_from_new_chunk(
struct pool *pool,
size_t size)
struct _pool_chunk *chunk;
void *obj;
/* If the allocation is smaller than the default chunk size then
* try getting a chunk off the free list. Force alloc of a new
* chunk for large requests. */
capacity = size;
chunk = NULL;
if (size < pool->default_capacity) {
capacity = pool->default_capacity;
chunk = pool->first_free;
if (chunk) {
pool->first_free = chunk->prev_chunk;
_pool_chunk_init(chunk, pool->current, chunk->capacity);
if (NULL == chunk)
chunk = _pool_chunk_create (pool, capacity);
pool->current = chunk;
obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
chunk->size += size;
return obj;
/* Allocate size bytes from the pool. The first allocated address
* returned from a pool is aligned to sizeof(void*). Subsequent
* addresses will maintain alignment as long as multiples of void* are
* allocated. Returns the address of a new memory area or %NULL on
* allocation failures. The pool retains ownership of the returned
* memory. */
inline static void *
pool_alloc (struct pool *pool, size_t size)
struct _pool_chunk *chunk = pool->current;
if (size <= chunk->capacity - chunk->size) {
void *obj = ((unsigned char*)chunk + sizeof(*chunk) + chunk->size);
} else {
return _pool_alloc_from_new_chunk(pool, size);
/* Relinquish all pool_alloced memory back to the pool. */
pool_reset (struct pool *pool)
/* Transfer all used chunks to the chunk free list. */
if (chunk != pool->sentinel) {
while (chunk->prev_chunk != pool->sentinel) {
chunk = chunk->prev_chunk;
chunk->prev_chunk = pool->first_free;
pool->first_free = pool->current;
/* Reset the sentinel as the current chunk. */
pool->sentinel->size = 0;
/* Rewinds the cell list's cursor to the beginning. After rewinding
* we're good to cell_list_find() the cell any x coordinate. */
inline static void
cell_list_rewind (struct cell_list *cells)
cells->cursor = &cells->head;
/* Rewind the cell list if its cursor has been advanced past x. */
cell_list_maybe_rewind (struct cell_list *cells, int x)
struct cell *tail = cells->cursor;
if (tail->x > x)
cell_list_rewind (cells);
cell_list_init(struct cell_list *cells, jmp_buf *jmp)
pool_init(cells->cell_pool.base, jmp,
256*sizeof(struct cell),
sizeof(cells->cell_pool.embedded));
cells->tail.next = NULL;
cells->tail.x = INT_MAX;
cells->head.x = INT_MIN;
cells->head.next = &cells->tail;
cell_list_fini(struct cell_list *cells)
pool_fini (cells->cell_pool.base);
/* Empty the cell list. This is called at the start of every pixel
* row. */
cell_list_reset (struct cell_list *cells)
pool_reset (cells->cell_pool.base);
static struct cell *
cell_list_alloc (struct cell_list *cells,
struct cell *tail,
int x)
struct cell *cell;
cell = pool_alloc (cells->cell_pool.base, sizeof (struct cell));
cell->next = tail->next;
tail->next = cell;
cell->x = x;
cell->uncovered_area = 0;
cell->covered_height = 0;
cell->clipped_height = 0;
return cell;
/* Find a cell at the given x-coordinate. Returns %NULL if a new cell
* needed to be allocated but couldn't be. Cells must be found with
* non-decreasing x-coordinate until the cell list is rewound using
* cell_list_rewind(). Ownership of the returned cell is retained by
* the cell list. */
inline static struct cell *
cell_list_find (struct cell_list *cells, int x)
while (1) {
UNROLL3({
if (tail->next->x > x)
break;
tail = tail->next;
});
if (tail->x != x)
tail = cell_list_alloc (cells, tail, x);
return cells->cursor = tail;
/* Find two cells at x1 and x2. This is exactly equivalent
* to
* pair.cell1 = cell_list_find(cells, x1);
* pair.cell2 = cell_list_find(cells, x2);
* except with less function call overhead. */
inline static struct cell_pair
cell_list_find_pair(struct cell_list *cells, int x1, int x2)
struct cell_pair pair;
pair.cell1 = cells->cursor;
if (pair.cell1->next->x > x1)
pair.cell1 = pair.cell1->next;
if (pair.cell1->x != x1) {
struct cell *cell = pool_alloc (cells->cell_pool.base,
sizeof (struct cell));
cell->x = x1;
cell->next = pair.cell1->next;
pair.cell1->next = cell;
pair.cell1 = cell;
pair.cell2 = pair.cell1;
if (pair.cell2->next->x > x2)
pair.cell2 = pair.cell2->next;
if (pair.cell2->x != x2) {
cell->x = x2;
cell->next = pair.cell2->next;
pair.cell2->next = cell;
pair.cell2 = cell;
cells->cursor = pair.cell2;
return pair;
/* Add a subpixel span covering [x1, x2) to the coverage cells. */
cell_list_add_subspan(struct cell_list *cells,
grid_scaled_x_t x1,
grid_scaled_x_t x2)
int ix1, fx1;
int ix2, fx2;
GRID_X_TO_INT_FRAC(x1, ix1, fx1);
GRID_X_TO_INT_FRAC(x2, ix2, fx2);
if (ix1 != ix2) {
struct cell_pair p;
p = cell_list_find_pair(cells, ix1, ix2);
p.cell1->uncovered_area += 2*fx1;
++p.cell1->covered_height;
p.cell2->uncovered_area -= 2*fx2;
--p.cell2->covered_height;
struct cell *cell = cell_list_find(cells, ix1);
cell->uncovered_area += 2*(fx1-fx2);
/* Adds the analytical coverage of an edge crossing the current pixel
* row to the coverage cells and advances the edge's x position to the
* following row.
* This function is only called when we know that during this pixel row:
* 1) The relative order of all edges on the active list doesn't
* change. In particular, no edges intersect within this row to pixel
* precision.
* 2) No new edges start in this row.
* 3) No existing edges end mid-row.
* This function depends on being called with all edges from the
* active list in the order they appear on the list (i.e. with
* non-decreasing x-coordinate.) */
cell_list_render_edge(
struct cell_list *cells,
struct edge *edge,
int sign)
grid_scaled_y_t y1, y2, dy;
grid_scaled_x_t dx;
int ix1, ix2;
grid_scaled_x_t fx1, fx2;
struct quorem x1 = edge->x;
struct quorem x2 = x1;
if (! edge->vertical) {
x2.quo += edge->dxdy_full.quo;
x2.rem += edge->dxdy_full.rem;
if (x2.rem >= 0) {
++x2.quo;
x2.rem -= edge->dy;
edge->x = x2;
GRID_X_TO_INT_FRAC(x1.quo, ix1, fx1);
GRID_X_TO_INT_FRAC(x2.quo, ix2, fx2);
/* Edge is entirely within a column? */
if (ix1 == ix2) {
/* We always know that ix1 is >= the cell list cursor in this
* case due to the no-intersections precondition. */
cell->covered_height += sign*GRID_Y;
cell->uncovered_area += sign*(fx1 + fx2)*GRID_Y;
return;
/* Orient the edge left-to-right. */
dx = x2.quo - x1.quo;
if (dx >= 0) {
y1 = 0;
y2 = GRID_Y;
int tmp;
tmp = ix1; ix1 = ix2; ix2 = tmp;
tmp = fx1; fx1 = fx2; fx2 = tmp;
dx = -dx;
sign = -sign;
y1 = GRID_Y;
y2 = 0;
dy = y2 - y1;
/* Add coverage for all pixels [ix1,ix2] on this row crossed
* by the edge. */
struct quorem y = floored_divrem((GRID_X - fx1)*dy, dx);
/* When rendering a previous edge on the active list we may
* advance the cell list cursor past the leftmost pixel of the
* current edge even though the two edges don't intersect.
* e.g. consider two edges going down and rightwards:
* --\_+---\_+-----+-----+----
* \_ \_ | |
* | \_ | \_ | |
* | \_| \_| |
* | \_ \_ |
* ----+-----+-\---+-\---+----
* The left edge touches cells past the starting cell of the
* right edge. Fortunately such cases are rare.
* The rewinding is never necessary if the current edge stays
* within a single column because we've checked before calling
* this function that the active list order won't change. */
cell_list_maybe_rewind(cells, ix1);
pair = cell_list_find_pair(cells, ix1, ix1+1);
pair.cell1->uncovered_area += sign*y.quo*(GRID_X + fx1);
pair.cell1->covered_height += sign*y.quo;
y.quo += y1;
if (ix1+1 < ix2) {
struct quorem dydx_full = floored_divrem(GRID_X*dy, dx);
struct cell *cell = pair.cell2;
++ix1;
grid_scaled_y_t y_skip = dydx_full.quo;
y.rem += dydx_full.rem;
if (y.rem >= dx) {
++y_skip;
y.rem -= dx;
y.quo += y_skip;
y_skip *= sign;
cell->uncovered_area += y_skip*GRID_X;
cell->covered_height += y_skip;
cell = cell_list_find(cells, ix1);
} while (ix1 != ix2);
pair.cell2->uncovered_area += sign*(y2 - y.quo)*fx2;
pair.cell2->covered_height += sign*(y2 - y.quo);
polygon_init (struct polygon *polygon, jmp_buf *jmp)
polygon->ymin = polygon->ymax = 0;
polygon->y_buckets = polygon->y_buckets_embedded;
pool_init (polygon->edge_pool.base, jmp,
8192 - sizeof (struct _pool_chunk),
sizeof (polygon->edge_pool.embedded));
polygon_fini (struct polygon *polygon)
if (polygon->y_buckets != polygon->y_buckets_embedded)
free (polygon->y_buckets);
pool_fini (polygon->edge_pool.base);
/* Empties the polygon of all edges. The polygon is then prepared to
* receive new edges and clip them to the vertical range
* [ymin,ymax). */
static cairo_status_t
polygon_reset (struct polygon *polygon,
grid_scaled_y_t ymin,
grid_scaled_y_t ymax)
unsigned h = ymax - ymin;
unsigned num_buckets = EDGE_Y_BUCKET_INDEX(ymax + EDGE_Y_BUCKET_HEIGHT-1,
ymin);
pool_reset(polygon->edge_pool.base);
if (unlikely (h > 0x7FFFFFFFU - EDGE_Y_BUCKET_HEIGHT))
goto bail_no_mem; /* even if you could, you wouldn't want to. */
if (num_buckets > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
polygon->y_buckets = _cairo_malloc_ab (num_buckets,
sizeof (struct edge *));
if (unlikely (NULL == polygon->y_buckets))
goto bail_no_mem;
memset (polygon->y_buckets, 0, num_buckets * sizeof (struct edge *));
polygon->ymin = ymin;
polygon->ymax = ymax;
return CAIRO_STATUS_SUCCESS;
bail_no_mem:
polygon->ymin = 0;
polygon->ymax = 0;
return CAIRO_STATUS_NO_MEMORY;
_polygon_insert_edge_into_its_y_bucket(
struct polygon *polygon,
struct edge *e)
unsigned ix = EDGE_Y_BUCKET_INDEX(e->ytop, polygon->ymin);
struct edge **ptail = &polygon->y_buckets[ix];
e->next = *ptail;
*ptail = e;
polygon_add_edge (struct polygon *polygon,
const cairo_edge_t *edge,
int clip)
struct edge *e;
grid_scaled_y_t ytop, ybot;
grid_scaled_y_t ymin = polygon->ymin;
grid_scaled_y_t ymax = polygon->ymax;
assert (edge->bottom > edge->top);
if (unlikely (edge->top >= ymax || edge->bottom <= ymin))
e = pool_alloc (polygon->edge_pool.base, sizeof (struct edge));
dx = edge->line.p2.x - edge->line.p1.x;
dy = edge->line.p2.y - edge->line.p1.y;
e->dy = dy;
e->dir = edge->dir;
e->clip = clip;
ytop = edge->top >= ymin ? edge->top : ymin;
ybot = edge->bottom <= ymax ? edge->bottom : ymax;
e->ytop = ytop;
e->height_left = ybot - ytop;
if (dx == 0) {
e->vertical = TRUE;
e->x.quo = edge->line.p1.x;
e->x.rem = 0;
e->dxdy.quo = 0;
e->dxdy.rem = 0;
e->dxdy_full.quo = 0;
e->dxdy_full.rem = 0;
e->vertical = FALSE;
e->dxdy = floored_divrem (dx, dy);
if (ytop == edge->line.p1.y) {
e->x = floored_muldivrem (ytop - edge->line.p1.y, dx, dy);
e->x.quo += edge->line.p1.x;
if (e->height_left >= GRID_Y) {
e->dxdy_full = floored_muldivrem (GRID_Y, dx, dy);
_polygon_insert_edge_into_its_y_bucket (polygon, e);
e->x.rem -= dy; /* Bias the remainder for faster
* edge advancement. */
active_list_reset (struct active_list *active)
active->head = NULL;
active->min_height = 0;
active_list_init(struct active_list *active)
active_list_reset(active);
/*
* Merge two sorted edge lists.
* Input:
* - head_a: The head of the first list.
* - head_b: The head of the second list; head_b cannot be NULL.
* Output:
* Returns the head of the merged list.
* Implementation notes:
* To make it fast (in particular, to reduce to an insertion sort whenever
* one of the two input lists only has a single element) we iterate through
* a list until its head becomes greater than the head of the other list,
* then we switch their roles. As soon as one of the two lists is empty, we
* just attach the other one to the current list and exit.
* Writes to memory are only needed to "switch" lists (as it also requires
* attaching to the output list the list which we will be iterating next) and
* to attach the last non-empty list.
static struct edge *
merge_sorted_edges (struct edge *head_a, struct edge *head_b)
struct edge *head, **next;
int32_t x;
if (head_a == NULL)
return head_b;
next = &head;
if (head_a->x.quo <= head_b->x.quo) {
head = head_a;
head = head_b;
goto start_with_b;
x = head_b->x.quo;
while (head_a != NULL && head_a->x.quo <= x) {
next = &head_a->next;
head_a = head_a->next;
*next = head_b;
return head;
start_with_b:
x = head_a->x.quo;
while (head_b != NULL && head_b->x.quo <= x) {
next = &head_b->next;
head_b = head_b->next;
*next = head_a;
if (head_b == NULL)
} while (1);
* Sort (part of) a list.
* - list: The list to be sorted; list cannot be NULL.
* - limit: Recursion limit.
* - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
* input list; if the input list has fewer elements, head_out be a sorted list
* containing all the elements of the input list.
* Returns the head of the list of unprocessed elements (NULL if the sorted list contains
* all the elements of the input list).
* Special case single element list, unroll/inline the sorting of the first two elements.
* Some tail recursion is used since we iterate on the bottom-up solution of the problem
* (we start with a small sorted list and keep merging other lists of the same size to it).
sort_edges (struct edge *list,
unsigned int level,
struct edge **head_out)
struct edge *head_other, *remaining;
unsigned int i;
head_other = list->next;
/* Single element list -> return */
if (head_other == NULL) {
*head_out = list;
return NULL;
/* Unroll the first iteration of the following loop (halves the number of calls to merge_sorted_edges):
* - Initialize remaining to be the list containing the elements after the second in the input list.
* - Initialize *head_out to be the sorted list containing the first two element.
remaining = head_other->next;
if (list->x.quo <= head_other->x.quo) {
/* list->next = head_other; */ /* The input list is already like this. */
head_other->next = NULL;
*head_out = head_other;
head_other->next = list;
list->next = NULL;
for (i = 0; i < level && remaining; i++) {
/* Extract a sorted list of the same size as *head_out
* (2^(i+1) elements) from the list of remaining elements. */
remaining = sort_edges (remaining, i, &head_other);
*head_out = merge_sorted_edges (*head_out, head_other);
/* *head_out now contains (at most) 2^(level+1) elements. */
return remaining;
/* Test if the edges on the active list can be safely advanced by a
* full row without intersections or any edges ending. */
inline static int
active_list_can_step_full_row (struct active_list *active)
const struct edge *e;
int prev_x = INT_MIN;
/* Recomputes the minimum height of all edges on the active
* list if we have been dropping edges. */
if (active->min_height <= 0) {
int min_height = INT_MAX;
e = active->head;
while (NULL != e) {
if (e->height_left < min_height)
min_height = e->height_left;
e = e->next;
active->min_height = min_height;
if (active->min_height < GRID_Y)
return 0;
/* Check for intersections as no edges end during the next row. */
struct quorem x = e->x;
if (! e->vertical) {
x.quo += e->dxdy_full.quo;
x.rem += e->dxdy_full.rem;
if (x.rem >= 0)
++x.quo;
if (x.quo <= prev_x)
prev_x = x.quo;
return 1;
/* Merges edges on the given subpixel row from the polygon to the
* active_list. */
active_list_merge_edges_from_polygon(struct active_list *active,
struct edge **ptail,
grid_scaled_y_t y,
struct polygon *polygon)
/* Split off the edges on the current subrow and merge them into
* the active list. */
int min_height = active->min_height;
struct edge *subrow_edges = NULL;
struct edge *tail = *ptail;
struct edge *next = tail->next;
if (y == tail->ytop) {
tail->next = subrow_edges;
subrow_edges = tail;
if (tail->height_left < min_height)
min_height = tail->height_left;
*ptail = next;
} else
ptail = &tail->next;
tail = next;
} while (tail);
if (subrow_edges) {
sort_edges (subrow_edges, UINT_MAX, &subrow_edges);
active->head = merge_sorted_edges (active->head, subrow_edges);
/* Advance the edges on the active list by one subsample row by
* updating their x positions. Drop edges from the list that end. */
active_list_substep_edges(struct active_list *active)
struct edge **cursor = &active->head;
grid_scaled_x_t prev_x = INT_MIN;
struct edge *unsorted = NULL;
struct edge *edge = *cursor;
if (NULL == edge)
next = edge->next;
if (--edge->height_left) {
edge->x.quo += edge->dxdy.quo;
edge->x.rem += edge->dxdy.rem;
if (edge->x.rem >= 0) {
++edge->x.quo;
edge->x.rem -= edge->dy;
if (edge->x.quo < prev_x) {
*cursor = next;
edge->next = unsorted;
unsorted = edge;
prev_x = edge->x.quo;
cursor = &edge->next;
edge = next;
})
if (unsorted) {
sort_edges (unsorted, UINT_MAX, &unsorted);
active->head = merge_sorted_edges (active->head, unsorted);
apply_nonzero_fill_rule_for_subrow (struct active_list *active,
struct cell_list *coverages)
struct edge *edge = active->head;
int winding = 0;
int xstart;
int xend;
cell_list_rewind (coverages);
while (NULL != edge) {
xstart = edge->x.quo;
winding = edge->dir;
edge = edge->next;
if (NULL == edge) {
ASSERT_NOT_REACHED;
winding += edge->dir;
if (0 == winding) {
if (edge->next == NULL || edge->next->x.quo != edge->x.quo)
xend = edge->x.quo;
cell_list_add_subspan (coverages, xstart, xend);
apply_evenodd_fill_rule_for_subrow (struct active_list *active,
apply_nonzero_fill_rule_and_step_edges (struct active_list *active,
struct edge *left_edge;
left_edge = *cursor;
while (NULL != left_edge) {
struct edge *right_edge;
int winding = left_edge->dir;
left_edge->height_left -= GRID_Y;
if (left_edge->height_left)
cursor = &left_edge->next;
else
*cursor = left_edge->next;
right_edge = *cursor;
if (NULL == right_edge) {
cell_list_render_edge (coverages, left_edge, +1);
right_edge->height_left -= GRID_Y;
if (right_edge->height_left)
cursor = &right_edge->next;
*cursor = right_edge->next;
winding += right_edge->dir;
if (right_edge->next == NULL ||
right_edge->next->x.quo != right_edge->x.quo)
if (! right_edge->vertical) {
right_edge->x.quo += right_edge->dxdy_full.quo;
right_edge->x.rem += right_edge->dxdy_full.rem;
if (right_edge->x.rem >= 0) {
++right_edge->x.quo;
right_edge->x.rem -= right_edge->dy;
cell_list_render_edge (coverages, right_edge, -1);
apply_evenodd_fill_rule_and_step_edges (struct active_list *active,
_glitter_scan_converter_init(glitter_scan_converter_t *converter, jmp_buf *jmp)
polygon_init(converter->polygon, jmp);
active_list_init(converter->active);
cell_list_init(converter->coverages, jmp);
converter->ymin=0;
converter->ymax=0;
_glitter_scan_converter_fini(glitter_scan_converter_t *converter)
polygon_fini(converter->polygon);
cell_list_fini(converter->coverages);
static grid_scaled_t
int_to_grid_scaled(int i, int scale)
/* Clamp to max/min representable scaled number. */
if (i >= 0) {
if (i >= INT_MAX/scale)
i = INT_MAX/scale;
else {
if (i <= INT_MIN/scale)
i = INT_MIN/scale;
return i*scale;
#define int_to_grid_scaled_x(x) int_to_grid_scaled((x), GRID_X)
#define int_to_grid_scaled_y(x) int_to_grid_scaled((x), GRID_Y)
glitter_scan_converter_reset(glitter_scan_converter_t *converter,
int ymin, int ymax)
cairo_status_t status;
converter->ymin = 0;
converter->ymax = 0;
ymin = int_to_grid_scaled_y(ymin);
ymax = int_to_grid_scaled_y(ymax);
active_list_reset(converter->active);
cell_list_reset(converter->coverages);
status = polygon_reset(converter->polygon, ymin, ymax);
if (status)
return status;
converter->ymin = ymin;
converter->ymax = ymax;
/* INPUT_TO_GRID_X/Y (in_coord, out_grid_scaled, grid_scale)
* These macros convert an input coordinate in the client's
* device space to the rasterisation grid.
/* Gah.. this bit of ugly defines INPUT_TO_GRID_X/Y so as to use
* shifts if possible, and something saneish if not.
#if !defined(INPUT_TO_GRID_Y) && defined(GRID_Y_BITS) && GRID_Y_BITS <= GLITTER_INPUT_BITS
# define INPUT_TO_GRID_Y(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_Y_BITS)
# define INPUT_TO_GRID_Y(in, out) INPUT_TO_GRID_general(in, out, GRID_Y)
#if !defined(INPUT_TO_GRID_X) && defined(GRID_X_BITS) && GRID_X_BITS <= GLITTER_INPUT_BITS
# define INPUT_TO_GRID_X(in, out) (out) = (in) >> (GLITTER_INPUT_BITS - GRID_X_BITS)
# define INPUT_TO_GRID_X(in, out) INPUT_TO_GRID_general(in, out, GRID_X)
#define INPUT_TO_GRID_general(in, out, grid_scale) do { \
long long tmp__ = (long long)(grid_scale) * (in); \
tmp__ >>= GLITTER_INPUT_BITS; \
(out) = tmp__; \
glitter_scan_converter_add_edge (glitter_scan_converter_t *converter,
cairo_edge_t e;
INPUT_TO_GRID_Y (edge->top, e.top);
INPUT_TO_GRID_Y (edge->bottom, e.bottom);
if (e.top >= e.bottom)
/* XXX: possible overflows if GRID_X/Y > 2**GLITTER_INPUT_BITS */
INPUT_TO_GRID_Y (edge->line.p1.y, e.line.p1.y);
INPUT_TO_GRID_Y (edge->line.p2.y, e.line.p2.y);
if (e.line.p1.y == e.line.p2.y)
INPUT_TO_GRID_X (edge->line.p1.x, e.line.p1.x);
INPUT_TO_GRID_X (edge->line.p2.x, e.line.p2.x);
e.dir = edge->dir;
polygon_add_edge (converter->polygon, &e, clip);
static cairo_bool_t
active_list_is_vertical (struct active_list *active)
for (e = active->head; e != NULL; e = e->next) {
if (! e->vertical)
return FALSE;
return TRUE;
step_edges (struct active_list *active, int count)
struct edge *edge;
for (edge = *cursor; edge != NULL; edge = *cursor) {
edge->height_left -= GRID_Y * count;
if (edge->height_left)
*cursor = edge->next;
blit_coverages (struct cell_list *cells,
cairo_span_renderer_t *renderer,
struct pool *span_pool,
int y, int height)
struct cell *cell = cells->head.next;
int prev_x = -1;
int cover = 0, last_cover = 0;
int clip = 0;
cairo_half_open_span_t *spans;
unsigned num_spans;
assert (cell != &cells->tail);
/* Count number of cells remaining. */
struct cell *next = cell;
num_spans = 2;
while (next->next) {
next = next->next;
++num_spans;
num_spans = 2*num_spans;
/* Allocate enough spans for the row. */
pool_reset (span_pool);
spans = pool_alloc (span_pool, sizeof(spans[0])*num_spans);
num_spans = 0;
/* Form the spans from the coverages and areas. */
for (; cell->next; cell = cell->next) {
int x = cell->x;
int area;
if (x > prev_x && cover != last_cover) {
spans[num_spans].x = prev_x;
spans[num_spans].coverage = GRID_AREA_TO_ALPHA (cover);
spans[num_spans].inverse = 0;
last_cover = cover;
cover += cell->covered_height*GRID_X*2;
clip += cell->covered_height*GRID_X*2;
area = cover - cell->uncovered_area;
if (area != last_cover) {
spans[num_spans].x = x;
spans[num_spans].coverage = GRID_AREA_TO_ALPHA (area);
last_cover = area;
prev_x = x+1;
/* Dump them into the renderer. */
return renderer->render_rows (renderer, y, height, spans, num_spans);
glitter_scan_converter_render(glitter_scan_converter_t *converter,
int nonzero_fill,
cairo_span_renderer_t *span_renderer,
struct pool *span_pool)
int i, j;
int ymax_i = converter->ymax / GRID_Y;
int ymin_i = converter->ymin / GRID_Y;
int h = ymax_i - ymin_i;
struct polygon *polygon = converter->polygon;
struct cell_list *coverages = converter->coverages;
struct active_list *active = converter->active;
/* Render each pixel row. */
for (i = 0; i < h; i = j) {
int do_full_step = 0;
j = i + 1;
/* Determine if we can ignore this row or use the full pixel
* stepper. */
if (GRID_Y == EDGE_Y_BUCKET_HEIGHT && ! polygon->y_buckets[i]) {
if (! active->head) {
for (; j < h && ! polygon->y_buckets[j]; j++)
;
continue;
do_full_step = active_list_can_step_full_row (active);
if (do_full_step) {
/* Step by a full pixel row's worth. */
if (nonzero_fill)
apply_nonzero_fill_rule_and_step_edges (active, coverages);
apply_evenodd_fill_rule_and_step_edges (active, coverages);
if (active_list_is_vertical (active)) {
while (j < h &&
polygon->y_buckets[j] == NULL &&
active->min_height >= 2*GRID_Y)
active->min_height -= GRID_Y;
j++;
if (j != i + 1)
step_edges (active, j - (i + 1));
grid_scaled_y_t suby;
/* Subsample this row. */
for (suby = 0; suby < GRID_Y; suby++) {
grid_scaled_y_t y = (i+ymin_i)*GRID_Y + suby;
if (polygon->y_buckets[i]) {
active_list_merge_edges_from_polygon (active,
&polygon->y_buckets[i], y,
polygon);
apply_nonzero_fill_rule_for_subrow (active, coverages);
apply_evenodd_fill_rule_for_subrow (active, coverages);
active_list_substep_edges(active);
blit_coverages (coverages, span_renderer, span_pool, i+ymin_i, j -i);
cell_list_reset (coverages);
if (! active->head)
active->min_height = INT_MAX;
struct _cairo_clip_tor_scan_converter {
cairo_scan_converter_t base;
glitter_scan_converter_t converter[1];
cairo_fill_rule_t fill_rule;
cairo_antialias_t antialias;
cairo_fill_rule_t clip_fill_rule;
cairo_antialias_t clip_antialias;
jmp_buf jmp;
cairo_half_open_span_t embedded[32];
} span_pool;
typedef struct _cairo_clip_tor_scan_converter cairo_clip_tor_scan_converter_t;
_cairo_clip_tor_scan_converter_destroy (void *converter)
cairo_clip_tor_scan_converter_t *self = converter;
if (self == NULL) {
_glitter_scan_converter_fini (self->converter);
pool_fini (self->span_pool.base);
free(self);
_cairo_clip_tor_scan_converter_generate (void *converter,
cairo_span_renderer_t *renderer)
if ((status = setjmp (self->jmp)))
return _cairo_scan_converter_set_error (self, _cairo_error (status));
glitter_scan_converter_render (self->converter,
self->fill_rule == CAIRO_FILL_RULE_WINDING,
renderer,
self->span_pool.base);
cairo_scan_converter_t *
_cairo_clip_tor_scan_converter_create (cairo_clip_t *clip,
cairo_polygon_t *polygon,
cairo_fill_rule_t fill_rule,
cairo_antialias_t antialias)
cairo_clip_tor_scan_converter_t *self;
cairo_polygon_t clipper;
int i;
self = _cairo_calloc (sizeof(struct _cairo_clip_tor_scan_converter));
if (unlikely (self == NULL)) {
status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
goto bail_nomem;
self->base.destroy = _cairo_clip_tor_scan_converter_destroy;
self->base.generate = _cairo_clip_tor_scan_converter_generate;
pool_init (self->span_pool.base, &self->jmp,
250 * sizeof(self->span_pool.embedded[0]),
sizeof(self->span_pool.embedded));
_glitter_scan_converter_init (self->converter, &self->jmp);
status = glitter_scan_converter_reset (self->converter,
clip->extents.y,
clip->extents.y + clip->extents.height);
if (unlikely (status))
goto bail;
self->fill_rule = fill_rule;
self->antialias = antialias;
for (i = 0; i < polygon->num_edges; i++)
glitter_scan_converter_add_edge (self->converter,
&polygon->edges[i],
FALSE);
status = _cairo_clip_get_polygon (clip,
&clipper,
&self->clip_fill_rule,
&self->clip_antialias);
for (i = 0; i < clipper.num_edges; i++)
&clipper.edges[i],
TRUE);
_cairo_polygon_fini (&clipper);
return &self->base;
bail:
self->base.destroy(&self->base);
bail_nomem:
return _cairo_scan_converter_create_in_error (status);