/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
/*
* Copyright (c) 2011 Intel Corporation
*
* 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.
*/
#include "cairoint.h"
#include "cairo-spans-private.h"
#include "cairo-error-private.h"
#include <stdlib.h>
#include <string.h>
#include <limits.h>
struct quorem {
int32_t quo;
int32_t rem;
};
struct edge {
struct edge *next, *prev;
int32_t height_left;
int32_t dir;
int32_t vertical;
int32_t dy;
struct quorem x;
struct quorem dxdy;
};
/* 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. */
int32_t ymin, ymax;
int num_edges;
struct edge *edges;
/* 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 edge edges_embedded[32];
};
struct mono_scan_converter {
struct polygon polygon[1];
/* Leftmost edge on the current scan line. */
struct edge head, tail;
int is_vertical;
cairo_half_open_span_t *spans;
cairo_half_open_span_t spans_embedded[64];
int num_spans;
/* Clip box. */
int32_t xmin, xmax;
int32_t ymin, ymax;
};
#define I(x) _cairo_fixed_integer_round_down(x)
/* 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
* division. */
static struct quorem
floored_muldivrem(int x, int a, int b)
{
struct quorem qr;
long long xa = (long long)x*a;
qr.quo = xa/b;
qr.rem = xa%b;
if ((xa>=0) != (b>=0) && qr.rem) {
qr.quo -= 1;
qr.rem += b;
}
return qr;
}
static cairo_status_t
polygon_init (struct polygon *polygon, int ymin, int ymax)
{
unsigned h = ymax - ymin + 1;
polygon->y_buckets = polygon->y_buckets_embedded;
if (h > ARRAY_LENGTH (polygon->y_buckets_embedded)) {
polygon->y_buckets = _cairo_malloc_ab (h, sizeof (struct edge *));
if (unlikely (NULL == polygon->y_buckets))
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
}
memset (polygon
->y_buckets
, 0, h
* sizeof (struct edge
*)); polygon->y_buckets[h-1] = (void *)-1;
polygon->ymin = ymin;
polygon->ymax = ymax;
return CAIRO_STATUS_SUCCESS;
}
static void
polygon_fini (struct polygon *polygon)
{
if (polygon->y_buckets != polygon->y_buckets_embedded)
free (polygon
->y_buckets
);
if (polygon->edges != polygon->edges_embedded)
}
static void
_polygon_insert_edge_into_its_y_bucket(struct polygon *polygon,
struct edge *e,
int y)
{
struct edge **ptail = &polygon->y_buckets[y - polygon->ymin];
if (*ptail)
(*ptail)->prev = e;
e->next = *ptail;
e->prev = NULL;
*ptail = e;
}
inline static void
polygon_add_edge (struct polygon *polygon,
const cairo_edge_t *edge)
{
struct edge *e;
cairo_fixed_t dx;
cairo_fixed_t dy;
int y, ytop, ybot;
int ymin = polygon->ymin;
int ymax = polygon->ymax;
y = I(edge->top);
ytop = MAX(y, ymin);
y = I(edge->bottom);
ybot = MIN(y, ymax);
if (ybot <= ytop)
return;
e = polygon->edges + polygon->num_edges++;
e->height_left = ybot - ytop;
e->dir = edge->dir;
dx = edge->line.p2.x - edge->line.p1.x;
dy = edge->line.p2.y - edge->line.p1.y;
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->dy = 0;
} else {
e->vertical = FALSE;
e->dxdy = floored_muldivrem (dx, CAIRO_FIXED_ONE, dy);
e->dy = dy;
e->x = floored_muldivrem (ytop * CAIRO_FIXED_ONE + CAIRO_FIXED_FRAC_MASK/2 - edge->line.p1.y,
dx, dy);
e->x.quo += edge->line.p1.x;
}
e->x.rem -= dy;
_polygon_insert_edge_into_its_y_bucket (polygon, e, ytop);
}
static struct edge *
merge_sorted_edges (struct edge *head_a, struct edge *head_b)
{
struct edge *head, **next, *prev;
int32_t x;
prev = head_a->prev;
next = &head;
if (head_a->x.quo <= head_b->x.quo) {
head = head_a;
} else {
head = head_b;
head_b->prev = prev;
goto start_with_b;
}
do {
x = head_b->x.quo;
while (head_a != NULL && head_a->x.quo <= x) {
prev = head_a;
next = &head_a->next;
head_a = head_a->next;
}
head_b->prev = prev;
*next = head_b;
if (head_a == NULL)
return head;
start_with_b:
x = head_a->x.quo;
while (head_b != NULL && head_b->x.quo <= x) {
prev = head_b;
next = &head_b->next;
head_b = head_b->next;
}
head_a->prev = prev;
*next = head_a;
if (head_b == NULL)
return head;
} while (1);
}
static struct edge *
sort_edges (struct edge *list,
unsigned int level,
struct edge **head_out)
{
struct edge *head_other, *remaining;
unsigned int i;
head_other = list->next;
if (head_other == NULL) {
*head_out = list;
return NULL;
}
remaining = head_other->next;
if (list->x.quo <= head_other->x.quo) {
*head_out = list;
head_other->next = NULL;
} else {
*head_out = head_other;
head_other->prev = list->prev;
head_other->next = list;
list->prev = head_other;
list->next = NULL;
}
for (i = 0; i < level && remaining; i++) {
remaining = sort_edges (remaining, i, &head_other);
*head_out = merge_sorted_edges (*head_out, head_other);
}
return remaining;
}
static struct edge *
merge_unsorted_edges (struct edge *head, struct edge *unsorted)
{
sort_edges (unsorted, UINT_MAX, &unsorted);
return merge_sorted_edges (head, unsorted);
}
inline static void
active_list_merge_edges (struct mono_scan_converter *c, struct edge *edges)
{
struct edge *e;
for (e = edges; c->is_vertical && e; e = e->next)
c->is_vertical = e->vertical;
c->head.next = merge_unsorted_edges (c->head.next, edges);
}
inline static void
add_span (struct mono_scan_converter *c, int x1, int x2)
{
int n;
if (x1 < c->xmin)
x1 = c->xmin;
if (x2 > c->xmax)
x2 = c->xmax;
if (x2 <= x1)
return;
n = c->num_spans++;
c->spans[n].x = x1;
c->spans[n].coverage = 255;
n = c->num_spans++;
c->spans[n].x = x2;
c->spans[n].coverage = 0;
}
inline static void
row (struct mono_scan_converter *c, unsigned int mask)
{
struct edge *edge = c->head.next;
int xstart = INT_MIN, prev_x = INT_MIN;
int winding = 0;
c->num_spans = 0;
while (&c->tail != edge) {
struct edge *next = edge->next;
int xend = I(edge->x.quo);
if (--edge->height_left) {
if (!edge->vertical) {
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) {
struct edge *pos = edge->prev;
pos->next = next;
next->prev = pos;
do {
pos = pos->prev;
} while (edge->x.quo < pos->x.quo);
pos->next->prev = edge;
edge->next = pos->next;
edge->prev = pos;
pos->next = edge;
} else
prev_x = edge->x.quo;
} else {
edge->prev->next = next;
next->prev = edge->prev;
}
winding += edge->dir;
if ((winding & mask) == 0) {
if (I(next->x.quo) > xend + 1) {
add_span (c, xstart, xend);
xstart = INT_MIN;
}
} else if (xstart == INT_MIN)
xstart = xend;
edge = next;
}
}
inline static void dec (struct edge *e, int h)
{
e->height_left -= h;
if (e->height_left == 0) {
e->prev->next = e->next;
e->next->prev = e->prev;
}
}
static cairo_status_t
_mono_scan_converter_init(struct mono_scan_converter *c,
int xmin, int ymin,
int xmax, int ymax)
{
cairo_status_t status;
int max_num_spans;
status = polygon_init (c->polygon, ymin, ymax);
if (unlikely (status))
return status;
max_num_spans = xmax - xmin + 1;
if (max_num_spans > ARRAY_LENGTH(c->spans_embedded)) {
c->spans = _cairo_malloc_ab (max_num_spans,
sizeof (cairo_half_open_span_t));
if (unlikely (c->spans == NULL)) {
polygon_fini (c->polygon);
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
}
} else
c->spans = c->spans_embedded;
c->xmin = xmin;
c->xmax = xmax;
c->ymin = ymin;
c->ymax = ymax;
c->head.vertical = 1;
c->head.height_left = INT_MAX;
c->head.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MIN));
c->head.prev = NULL;
c->head.next = &c->tail;
c->tail.prev = &c->head;
c->tail.next = NULL;
c->tail.x.quo = _cairo_fixed_from_int (_cairo_fixed_integer_part (INT_MAX));
c->tail.height_left = INT_MAX;
c->tail.vertical = 1;
c->is_vertical = 1;
return CAIRO_STATUS_SUCCESS;
}
static void
_mono_scan_converter_fini(struct mono_scan_converter *self)
{
if (self->spans != self->spans_embedded)
polygon_fini(self->polygon);
}
static cairo_status_t
mono_scan_converter_allocate_edges(struct mono_scan_converter *c,
int num_edges)
{
c->polygon->num_edges = 0;
c->polygon->edges = c->polygon->edges_embedded;
if (num_edges > ARRAY_LENGTH (c->polygon->edges_embedded)) {
c->polygon->edges = _cairo_malloc_ab (num_edges, sizeof (struct edge));
if (unlikely (c->polygon->edges == NULL))
return _cairo_error (CAIRO_STATUS_NO_MEMORY);
}
return CAIRO_STATUS_SUCCESS;
}
static void
mono_scan_converter_add_edge (struct mono_scan_converter *c,
const cairo_edge_t *edge)
{
polygon_add_edge (c->polygon, edge);
}
static void
step_edges (struct mono_scan_converter *c, int count)
{
struct edge *edge;
for (edge = c->head.next; edge != &c->tail; edge = edge->next) {
edge->height_left -= count;
if (! edge->height_left) {
edge->prev->next = edge->next;
edge->next->prev = edge->prev;
}
}
}
static cairo_status_t
mono_scan_converter_render(struct mono_scan_converter *c,
unsigned int winding_mask,
cairo_span_renderer_t *renderer)
{
struct polygon *polygon = c->polygon;
int i, j, h = c->ymax - c->ymin;
cairo_status_t status;
for (i = 0; i < h; i = j) {
j = i + 1;
if (polygon->y_buckets[i])
active_list_merge_edges (c, polygon->y_buckets[i]);
if (c->is_vertical) {
int min_height;
struct edge *e;
e = c->head.next;
min_height = e->height_left;
while (e != &c->tail) {
if (e->height_left < min_height)
min_height = e->height_left;
e = e->next;
}
while (--min_height >= 1 && polygon->y_buckets[j] == NULL)
j++;
if (j != i + 1)
step_edges (c, j - (i + 1));
}
row (c, winding_mask);
if (c->num_spans) {
status = renderer->render_rows (renderer, c->ymin+i, j-i,
c->spans, c->num_spans);
if (unlikely (status))
return status;
}
/* XXX recompute after dropping edges? */
if (c->head.next == &c->tail)
c->is_vertical = 1;
}
return CAIRO_STATUS_SUCCESS;
}
struct _cairo_mono_scan_converter {
cairo_scan_converter_t base;
struct mono_scan_converter converter[1];
cairo_fill_rule_t fill_rule;
};
typedef struct _cairo_mono_scan_converter cairo_mono_scan_converter_t;
static void
_cairo_mono_scan_converter_destroy (void *converter)
{
cairo_mono_scan_converter_t *self = converter;
_mono_scan_converter_fini (self->converter);
}
cairo_status_t
_cairo_mono_scan_converter_add_polygon (void *converter,
const cairo_polygon_t *polygon)
{
cairo_mono_scan_converter_t *self = converter;
cairo_status_t status;
int i;
#if 0
FILE
*file
= fopen ("polygon.txt", "w"); _cairo_debug_print_polygon (file, polygon);
#endif
status = mono_scan_converter_allocate_edges (self->converter,
polygon->num_edges);
if (unlikely (status))
return status;
for (i = 0; i < polygon->num_edges; i++)
mono_scan_converter_add_edge (self->converter, &polygon->edges[i]);
return CAIRO_STATUS_SUCCESS;
}
static cairo_status_t
_cairo_mono_scan_converter_generate (void *converter,
cairo_span_renderer_t *renderer)
{
cairo_mono_scan_converter_t *self = converter;
return mono_scan_converter_render (self->converter,
self->fill_rule == CAIRO_FILL_RULE_WINDING ? ~0 : 1,
renderer);
}
cairo_scan_converter_t *
_cairo_mono_scan_converter_create (int xmin,
int ymin,
int xmax,
int ymax,
cairo_fill_rule_t fill_rule)
{
cairo_mono_scan_converter_t *self;
cairo_status_t status;
self
= malloc (sizeof(struct _cairo_mono_scan_converter
)); if (unlikely (self == NULL)) {
status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
goto bail_nomem;
}
self->base.destroy = _cairo_mono_scan_converter_destroy;
self->base.generate = _cairo_mono_scan_converter_generate;
status = _mono_scan_converter_init (self->converter,
xmin, ymin, xmax, ymax);
if (unlikely (status))
goto bail;
self->fill_rule = fill_rule;
return &self->base;
bail:
self->base.destroy(&self->base);
bail_nomem:
return _cairo_scan_converter_create_in_error (status);
}