cairo-traps.c

按照官方的说法：Cairo is a vector graphics library with cross-device output support. 翻译过来

/*
 * Copyright © 2002 Keith Packard
 *
 * This library is free software; you can redistribute it and/or
 * modify it either under the terms of the GNU Lesser General Public
 * License version 2.1 as published by the Free Software Foundation
 * (the "LGPL") or, at your option, under the terms of the Mozilla
 * Public License Version 1.1 (the "MPL"). If you do not alter this
 * notice, a recipient may use your version of this file under either
 * the MPL or the LGPL.
 *
 * You should have received a copy of the LGPL along with this library
 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 * You should have received a copy of the MPL along with this library
 * in the file COPYING-MPL-1.1
 *
 * The contents of this file are subject to the Mozilla Public License
 * Version 1.1 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
 * the specific language governing rights and limitations.
 *
 * The Original Code is the cairo graphics library.
 *
 * The Initial Developer of the Original Code is Keith Packard
 *
 * Contributor(s):
 *	Keith R. Packard <[e-mail]>
 *	Carl D. Worth <[e-mail]>
 *
 * 2002-07-15: Converted from XRenderCompositeDoublePoly to cairo_trap. Carl D. Worth
 */

#include "cairoint.h"

/* private functions */

static cairo_status_t
_cairo_traps_grow_by (cairo_traps_t *traps, int additional);

static cairo_status_t
_cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
		       cairo_line_t *left, cairo_line_t *right);

static cairo_status_t
_cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
				   cairo_point_t left_p1, cairo_point_t left_p2,
				   cairo_point_t right_p1, cairo_point_t right_p2);

static int
_compare_point_fixed_by_y (const void *av, const void *bv);

static int
_compare_cairo_edge_by_top (const void *av, const void *bv);

static int
_compare_cairo_edge_by_slope (const void *av, const void *bv);

static cairo_fixed_16_16_t
_compute_x (cairo_line_t *line, cairo_fixed_t y);

static int
_line_segs_intersect_ceil (cairo_line_t *left, cairo_line_t *right, cairo_fixed_t *y_ret);

void
_cairo_traps_init (cairo_traps_t *traps)
{
    traps->num_traps = 0;

    traps->traps_size = 0;
    traps->traps = NULL;
    traps->extents.p1.x = traps->extents.p1.y = INT16_MAX << 16;
    traps->extents.p2.x = traps->extents.p2.y = INT16_MIN << 16;
}

void
_cairo_traps_fini (cairo_traps_t *traps)
{
    if (traps->traps_size) {
	free (traps->traps);
	traps->traps = NULL;
	traps->traps_size = 0;
	traps->num_traps = 0;
    }
}

/**
 * _cairo_traps_init_box:
 * @traps: a #cairo_traps_t
 * @box: a box that will be converted to a single trapezoid
 *       to store in @traps.
 *
 * Initializes a cairo_traps_t to contain a single rectangular
 * trapezoid.
 **/
cairo_status_t
_cairo_traps_init_box (cairo_traps_t *traps,
		       cairo_box_t   *box)
{
  cairo_status_t status;

  _cairo_traps_init (traps);

  status = _cairo_traps_grow_by (traps, 1);
  if (status)
    return status;

  traps->num_traps = 1;

  traps->traps[0].top = box->p1.y;
  traps->traps[0].bottom = box->p2.y;
  traps->traps[0].left.p1 = box->p1;
  traps->traps[0].left.p2.x = box->p1.x;
  traps->traps[0].left.p2.y = box->p2.y;
  traps->traps[0].right.p1.x = box->p2.x;
  traps->traps[0].right.p1.y = box->p1.y;
  traps->traps[0].right.p2 = box->p2;

  traps->extents = *box;

  return CAIRO_STATUS_SUCCESS;
}

static cairo_status_t
_cairo_traps_add_trap (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
		       cairo_line_t *left, cairo_line_t *right)
{
    cairo_status_t status;
    cairo_trapezoid_t *trap;

    if (top == bottom) {
	return CAIRO_STATUS_SUCCESS;
    }

    if (traps->num_traps >= traps->traps_size) {
	int inc = traps->traps_size ? traps->traps_size : 32;
	status = _cairo_traps_grow_by (traps, inc);
	if (status)
	    return status;
    }

    trap = &traps->traps[traps->num_traps];
    trap->top = top;
    trap->bottom = bottom;
    trap->left = *left;
    trap->right = *right;

    if (top < traps->extents.p1.y)
	traps->extents.p1.y = top;
    if (bottom > traps->extents.p2.y)
	traps->extents.p2.y = bottom;
    /*
     * This isn't generally accurate, but it is close enough for
     * this purpose.  Assuming that the left and right segments always
     * contain the trapezoid vertical extents, these compares will
     * yield a containing box.  Assuming that the points all come from
     * the same figure which will eventually be completely drawn, then
     * the compares will yield the correct overall extents
     */
    if (left->p1.x < traps->extents.p1.x)
	traps->extents.p1.x = left->p1.x;
    if (left->p2.x < traps->extents.p1.x)
	traps->extents.p1.x = left->p2.x;

    if (right->p1.x > traps->extents.p2.x)
	traps->extents.p2.x = right->p1.x;
    if (right->p2.x > traps->extents.p2.x)
	traps->extents.p2.x = right->p2.x;

    traps->num_traps++;

    return CAIRO_STATUS_SUCCESS;
}

static cairo_status_t
_cairo_traps_add_trap_from_points (cairo_traps_t *traps, cairo_fixed_t top, cairo_fixed_t bottom,
				   cairo_point_t left_p1, cairo_point_t left_p2,
				   cairo_point_t right_p1, cairo_point_t right_p2)
{
    cairo_line_t left;
    cairo_line_t right;

    left.p1 = left_p1;
    left.p2 = left_p2;

    right.p1 = right_p1;
    right.p2 = right_p2;

    return _cairo_traps_add_trap (traps, top, bottom, &left, &right);
}

static cairo_status_t
_cairo_traps_grow_by (cairo_traps_t *traps, int additional)
{
    cairo_trapezoid_t *new_traps;
    int old_size = traps->traps_size;
    int new_size = traps->num_traps + additional;

    if (new_size <= traps->traps_size) {
	return CAIRO_STATUS_SUCCESS;
    }

    traps->traps_size = new_size;
    new_traps = realloc (traps->traps, traps->traps_size * sizeof (cairo_trapezoid_t));

    if (new_traps == NULL) {
	traps->traps_size = old_size;
	return CAIRO_STATUS_NO_MEMORY;
    }

    traps->traps = new_traps;

    return CAIRO_STATUS_SUCCESS;
}

static int
_compare_point_fixed_by_y (const void *av, const void *bv)
{
    const cairo_point_t	*a = av, *b = bv;

    int ret = a->y - b->y;
    if (ret == 0) {
	ret = a->x - b->x;
    }
    return ret;
}

void
_cairo_traps_translate (cairo_traps_t *traps, int x, int y)
{
    cairo_fixed_t xoff, yoff;
    cairo_trapezoid_t *t;
    int i;

    /* Ugh. The cairo_composite/(Render) interface doesn't allow
       an offset for the trapezoids. Need to manually shift all
       the coordinates to align with the offset origin of the
       intermediate surface. */

    xoff = _cairo_fixed_from_int (x);
    yoff = _cairo_fixed_from_int (y);

    for (i = 0, t = traps->traps; i < traps->num_traps; i++, t++) {
	t->top += yoff;
	t->bottom += yoff;
	t->left.p1.x += xoff;
	t->left.p1.y += yoff;
	t->left.p2.x += xoff;
	t->left.p2.y += yoff;
	t->right.p1.x += xoff;
	t->right.p1.y += yoff;
	t->right.p2.x += xoff;
	t->right.p2.y += yoff;
    }
}

void
_cairo_trapezoid_array_translate_and_scale (cairo_trapezoid_t *offset_traps,
                                            cairo_trapezoid_t *src_traps,
                                            int num_traps,
                                            double tx, double ty,
                                            double sx, double sy)
{
    int i;
    cairo_fixed_t xoff = _cairo_fixed_from_double (tx);
    cairo_fixed_t yoff = _cairo_fixed_from_double (ty);

    if (sx == 1.0 && sy == 1.0) {
        for (i = 0; i < num_traps; i++) {
            offset_traps[i].top = src_traps[i].top + yoff;
            offset_traps[i].bottom = src_traps[i].bottom + yoff;
            offset_traps[i].left.p1.x = src_traps[i].left.p1.x + xoff;
            offset_traps[i].left.p1.y = src_traps[i].left.p1.y + yoff;
            offset_traps[i].left.p2.x = src_traps[i].left.p2.x + xoff;
            offset_traps[i].left.p2.y = src_traps[i].left.p2.y + yoff;
            offset_traps[i].right.p1.x = src_traps[i].right.p1.x + xoff;
            offset_traps[i].right.p1.y = src_traps[i].right.p1.y + yoff;
            offset_traps[i].right.p2.x = src_traps[i].right.p2.x + xoff;
            offset_traps[i].right.p2.y = src_traps[i].right.p2.y + yoff;
        }
    } else {
        cairo_fixed_t xsc = _cairo_fixed_from_double (sx);
        cairo_fixed_t ysc = _cairo_fixed_from_double (sy);

        for (i = 0; i < num_traps; i++) {
#define FIXED_MUL(_a, _b) \
            (_cairo_int64_to_int32(_cairo_int64_rsl(_cairo_int32x32_64_mul((_a), (_b)), 16)))

            offset_traps[i].top = FIXED_MUL(src_traps[i].top + yoff, ysc);
            offset_traps[i].bottom = FIXED_MUL(src_traps[i].bottom + yoff, ysc);
            offset_traps[i].left.p1.x = FIXED_MUL(src_traps[i].left.p1.x + xoff, xsc);
            offset_traps[i].left.p1.y = FIXED_MUL(src_traps[i].left.p1.y + yoff, ysc);
            offset_traps[i].left.p2.x = FIXED_MUL(src_traps[i].left.p2.x + xoff, xsc);
            offset_traps[i].left.p2.y = FIXED_MUL(src_traps[i].left.p2.y + yoff, ysc);
            offset_traps[i].right.p1.x = FIXED_MUL(src_traps[i].right.p1.x + xoff, xsc);
            offset_traps[i].right.p1.y = FIXED_MUL(src_traps[i].right.p1.y + yoff, ysc);
            offset_traps[i].right.p2.x = FIXED_MUL(src_traps[i].right.p2.x + xoff, xsc);
            offset_traps[i].right.p2.y = FIXED_MUL(src_traps[i].right.p2.y + yoff, ysc);

#undef FIXED_MUL
        }
    }
}

cairo_status_t
_cairo_traps_tessellate_triangle (cairo_traps_t *traps, cairo_point_t t[3])
{
    cairo_status_t status;
    cairo_line_t line;
    cairo_fixed_16_16_t intersect;
    cairo_point_t tsort[3];

    memcpy (tsort, t, 3 * sizeof (cairo_point_t));
    qsort (tsort, 3, sizeof (cairo_point_t), _compare_point_fixed_by_y);

    /* horizontal top edge requires special handling */
    if (tsort[0].y == tsort[1].y) {
	if (tsort[0].x < tsort[1].x)
	    status = _cairo_traps_add_trap_from_points (traps,
							tsort[1].y, tsort[2].y,
							tsort[0], tsort[2],
							tsort[1], tsort[2]);
	else
	    status = _cairo_traps_add_trap_from_points (traps,
							tsort[1].y, tsort[2].y,
							tsort[1], tsort[2],
							tsort[0], tsort[2]);
	return status;
    }

    line.p1 = tsort[0];
    line.p2 = tsort[1];

    intersect = _compute_x (&line, tsort[2].y);

    if (intersect < tsort[2].x) {
	status = _cairo_traps_add_trap_from_points (traps,
						    tsort[0].y, tsort[1].y,
						    tsort[0], tsort[1],
						    tsort[0], tsort[2]);
	if (status)
	    return status;
	status = _cairo_traps_add_trap_from_points (traps,
						    tsort[1].y, tsort[2].y,
						    tsort[1], tsort[2],
						    tsort[0], tsort[2]);
	if (status)
	    return status;
    } else {
	status = _cairo_traps_add_trap_from_points (traps,
						    tsort[0].y, tsort[1].y,
						    tsort[0], tsort[2],
						    tsort[0], tsort[1]);
	if (status)
	    return status;
	status = _cairo_traps_add_trap_from_points (traps,
						    tsort[1].y, tsort[2].y,
						    tsort[0], tsort[2],
						    tsort[1], tsort[2]);
	if (status)
	    return status;
    }

    return CAIRO_STATUS_SUCCESS;
}

/* Warning: This function reorders the elements of the array provided. */
cairo_status_t
_cairo_traps_tessellate_rectangle (cairo_traps_t *traps, cairo_point_t q[4])
{
    cairo_status_t status;

    qsort (q, 4, sizeof (cairo_point_t), _compare_point_fixed_by_y);

    if (q[1].x > q[2].x) {
	status = _cairo_traps_add_trap_from_points (traps,
						    q[0].y, q[1].y, q[0], q[2], q[0], q[1]);
	if (status)
	    return status;
	status = _cairo_traps_add_trap_from_points (traps,
						    q[1].y, q[2].y, q[0], q[2], q[1], q[3]);
	if (status)
	    return status;
	status = _cairo_traps_add_trap_from_points (traps,
						    q[2].y, q[3].y, q[2], q[3], q[1], q[3]);
	if (status)
	    return status;
    } else {
	status = _cairo_traps_add_trap_from_points (traps,
						    q[0].y, q[1].y, q[0], q[1], q[0], q[2]);
	if (status)
	    return status;
	status = _cairo_traps_add_trap_from_points (traps,
						    q[1].y, q[2].y, q[1], q[3], q[0], q[2]);
	if (status)
	    return status;
	status = _cairo_traps_add_trap_from_points (traps,
						    q[2].y, q[3].y, q[1], q[3], q[2], q[3]);
	if (status)
	    return status;
    }

    return CAIRO_STATUS_SUCCESS;
}

static int
_compare_cairo_edge_by_top (const void *av, const void *bv)
{
    const cairo_edge_t *a = av, *b = bv;

    return a->edge.p1.y - b->edge.p1.y;
}

/* Return value is:
   > 0 if a is "clockwise" from b, (in a mathematical, not a graphical sense)
   == 0 if slope (a) == slope (b)
   < 0 if a is "counter-clockwise" from b
*/
static int
_compare_cairo_edge_by_slope (const void *av, const void *bv)
{
    const cairo_edge_t *a = av, *b = bv;
    cairo_fixed_32_32_t d;

    cairo_fixed_48_16_t a_dx = a->edge.p2.x - a->edge.p1.x;
    cairo_fixed_48_16_t a_dy = a->edge.p2.y - a->edge.p1.y;
    cairo_fixed_48_16_t b_dx = b->edge.p2.x - b->edge.p1.x;
    cairo_fixed_48_16_t b_dy = b->edge.p2.y - b->edge.p1.y;

    d = b_dy * a_dx - a_dy * b_dx;

    if (d > 0)
	return 1;
    else if (d == 0)
	return 0;
    else
	return -1;
}

static int
_compare_cairo_edge_by_current_x_slope (const void *av, const void *bv)
{
    const cairo_edge_t *a = av, *b = bv;
    int ret;

    ret = a->current_x - b->current_x;
    if (ret == 0)
	ret = _compare_cairo_edge_by_slope (a, b);
    return ret;
}