summaryrefslogtreecommitdiff
path: root/src/cairo-mono-scan-converter.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cairo-mono-scan-converter.c')
-rw-r--r--src/cairo-mono-scan-converter.c612
1 files changed, 612 insertions, 0 deletions
diff --git a/src/cairo-mono-scan-converter.c b/src/cairo-mono-scan-converter.c
new file mode 100644
index 000000000..2a9546cf8
--- /dev/null
+++ b/src/cairo-mono-scan-converter.c
@@ -0,0 +1,612 @@
+/* -*- 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)
+ free (polygon->edges);
+}
+
+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)
+ free (self->spans);
+
+ 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);
+ free(self);
+}
+
+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);
+ fclose (file);
+#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);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-16 07:35:33 +0000