Quelle  pixman-trap.c   Sprache: C

/*
 * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
 * Copyright © 2004 Keith Packard
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Keith Packard not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  Keith Packard makes no
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

#ifdef HAVE_CONFIG_H
#include <pixman-config.h>
#endif

#include <stdio.h>
#include <stdlib.h>
#include "pixman-private.h"

/*
 * Compute the smallest value greater than or equal to y which is on a
 * grid row.
 */

PIXMAN_EXPORT pixman_fixed_t
pixman_sample_ceil_y (pixman_fixed_t y, int n)
{
    pixman_fixed_t f = pixman_fixed_frac (y);
    pixman_fixed_t i = pixman_fixed_floor (y);

    f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
 Y_FRAC_FIRST (n);
    
    if (f > Y_FRAC_LAST (n))
    {
 if (pixman_fixed_to_int (i) == 0x7fff)
 {
     f = 0xffff; /* saturate */
 }
 else
 {
     f = Y_FRAC_FIRST (n);
     i += pixman_fixed_1;
 }
    }
    return (i | f);
}

/*
 * Compute the largest value strictly less than y which is on a
 * grid row.
 */
PIXMAN_EXPORT pixman_fixed_t
pixman_sample_floor_y (pixman_fixed_t y,
                       int            n)
{
    pixman_fixed_t f = pixman_fixed_frac (y);
    pixman_fixed_t i = pixman_fixed_floor (y);

    f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
 Y_FRAC_FIRST (n);

    if (f < Y_FRAC_FIRST (n))
    {
 if (pixman_fixed_to_int (i) == 0xffff8000)
 {
     f = 0; /* saturate */
 }
 else
 {
     f = Y_FRAC_LAST (n);
     i -= pixman_fixed_1;
 }
    }
    return (i | f);
}

/*
 * Step an edge by any amount (including negative values)
 */
PIXMAN_EXPORT void
pixman_edge_step (pixman_edge_t *e,
                  int            n)
{
    pixman_fixed_48_16_t ne;

    e->x += n * e->stepx;

    ne = e->e + n * (pixman_fixed_48_16_t) e->dx;

    if (n >= 0)
    {
 if (ne > 0)
 {
     int nx = (ne + e->dy - 1) / e->dy;
     e->e = ne - nx * (pixman_fixed_48_16_t) e->dy;
     e->x += nx * e->signdx;
 }
    }
    else
    {
 if (ne <= -e->dy)
 {
     int nx = (-ne) / e->dy;
     e->e = ne + nx * (pixman_fixed_48_16_t) e->dy;
     e->x -= nx * e->signdx;
 }
    }
}

/*
 * A private routine to initialize the multi-step
 * elements of an edge structure
 */
static void
_pixman_edge_multi_init (pixman_edge_t * e,
                         int             n,
                         pixman_fixed_t *stepx_p,
                         pixman_fixed_t *dx_p)
{
    pixman_fixed_t stepx;
    pixman_fixed_48_16_t ne;

    ne = n * (pixman_fixed_48_16_t) e->dx;
    stepx = n * e->stepx;

    if (ne > 0)
    {
 int nx = ne / e->dy;
 ne -= nx * (pixman_fixed_48_16_t)e->dy;
 stepx += nx * e->signdx;
    }

    *dx_p = ne;
    *stepx_p = stepx;
}

/*
 * Initialize one edge structure given the line endpoints and a
 * starting y value
 */
PIXMAN_EXPORT void
pixman_edge_init (pixman_edge_t *e,
                  int            n,
                  pixman_fixed_t y_start,
                  pixman_fixed_t x_top,
                  pixman_fixed_t y_top,
                  pixman_fixed_t x_bot,
                  pixman_fixed_t y_bot)
{
    pixman_fixed_t dx, dy;

    e->x = x_top;
    e->e = 0;
    dx = x_bot - x_top;
    dy = y_bot - y_top;
    e->dy = dy;
    e->dx = 0;

    if (dy)
    {
 if (dx >= 0)
 {
     e->signdx = 1;
     e->stepx = dx / dy;
     e->dx = dx % dy;
     e->e = -dy;
 }
 else
 {
     e->signdx = -1;
     e->stepx = -(-dx / dy);
     e->dx = -dx % dy;
     e->e = 0;
 }

 _pixman_edge_multi_init (e, STEP_Y_SMALL (n),
     &e->stepx_small, &e->dx_small);

 _pixman_edge_multi_init (e, STEP_Y_BIG (n),
     &e->stepx_big, &e->dx_big);
    }
    pixman_edge_step (e, y_start - y_top);
}

/*
 * Initialize one edge structure given a line, starting y value
 * and a pixel offset for the line
 */
PIXMAN_EXPORT void
pixman_line_fixed_edge_init (pixman_edge_t *            e,
                             int                        n,
                             pixman_fixed_t             y,
                             const pixman_line_fixed_t *line,
                             int                        x_off,
                             int                        y_off)
{
    pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off);
    pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off);
    const pixman_point_fixed_t *top, *bot;

    if (line->p1.y <= line->p2.y)
    {
 top = &line->p1;
 bot = &line->p2;
    }
    else
    {
 top = &line->p2;
 bot = &line->p1;
    }
    
    pixman_edge_init (e, n, y,
                      top->x + x_off_fixed,
                      top->y + y_off_fixed,
                      bot->x + x_off_fixed,
                      bot->y + y_off_fixed);
}

PIXMAN_EXPORT void
pixman_add_traps (pixman_image_t *     image,
                  int16_t              x_off,
                  int16_t              y_off,
                  int                  ntrap,
                  const pixman_trap_t *traps)
{
    int bpp;
    int height;

    pixman_fixed_t x_off_fixed;
    pixman_fixed_t y_off_fixed;
    pixman_edge_t l, r;
    pixman_fixed_t t, b;

    _pixman_image_validate (image);
    
    height = image->bits.height;
    bpp = PIXMAN_FORMAT_BPP (image->bits.format);

    x_off_fixed = pixman_int_to_fixed (x_off);
    y_off_fixed = pixman_int_to_fixed (y_off);

    while (ntrap--)
    {
 t = traps->top.y + y_off_fixed;
 if (t < 0)
     t = 0;
 t = pixman_sample_ceil_y (t, bpp);

 b = traps->bot.y + y_off_fixed;
 if (pixman_fixed_to_int (b) >= height)
     b = pixman_int_to_fixed (height) - 1;
 b = pixman_sample_floor_y (b, bpp);

 if (b >= t)
 {
     /* initialize edge walkers */
     pixman_edge_init (&l, bpp, t,
                       traps->top.l + x_off_fixed,
                       traps->top.y + y_off_fixed,
                       traps->bot.l + x_off_fixed,
                       traps->bot.y + y_off_fixed);

     pixman_edge_init (&r, bpp, t,
                       traps->top.r + x_off_fixed,
                       traps->top.y + y_off_fixed,
                       traps->bot.r + x_off_fixed,
                       traps->bot.y + y_off_fixed);

     pixman_rasterize_edges (image, &l, &r, t, b);
 }

 traps++;
    }
}

#if 0
static void
dump_image (pixman_image_t *image,
            const char *    title)
{
    int i, j;

    if (!image->type == BITS)
 printf ("%s is not a regular image\n", title);

    if (!image->bits.format == PIXMAN_a8)
 printf ("%s is not an alpha mask\n", title);

    printf ("\n\n\n%s: \n", title);

    for (i = 0; i < image->bits.height; ++i)
    {
 uint8_t *line =
     (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]);

 for (j = 0; j < image->bits.width; ++j)
     printf ("%c", line[j] ? '#' : ' ');

 printf ("\n");
    }
}
#endif

PIXMAN_EXPORT void
pixman_add_trapezoids (pixman_image_t *          image,
                       int16_t                   x_off,
                       int                       y_off,
                       int                       ntraps,
                       const pixman_trapezoid_t *traps)
{
    int i;

#if 0
    dump_image (image, "before");
#endif

    for (i = 0; i < ntraps; ++i)
    {
 const pixman_trapezoid_t *trap = &(traps[i]);

 if (!pixman_trapezoid_valid (trap))
     continue;

 pixman_rasterize_trapezoid (image, trap, x_off, y_off);
    }

#if 0
    dump_image (image, "after");
#endif
}

PIXMAN_EXPORT void
pixman_rasterize_trapezoid (pixman_image_t *          image,
                            const pixman_trapezoid_t *trap,
                            int                       x_off,
                            int                       y_off)
{
    int bpp;
    int height;

    pixman_fixed_t y_off_fixed;
    pixman_edge_t l, r;
    pixman_fixed_t t, b;

    return_if_fail (image->type == BITS);

    _pixman_image_validate (image);
    
    if (!pixman_trapezoid_valid (trap))
 return;

    height = image->bits.height;
    bpp = PIXMAN_FORMAT_BPP (image->bits.format);

    y_off_fixed = pixman_int_to_fixed (y_off);

    t = trap->top + y_off_fixed;
    if (t < 0)
 t = 0;
    t = pixman_sample_ceil_y (t, bpp);

    b = trap->bottom + y_off_fixed;
    if (pixman_fixed_to_int (b) >= height)
 b = pixman_int_to_fixed (height) - 1;
    b = pixman_sample_floor_y (b, bpp);
    
    if (b >= t)
    {
 /* initialize edge walkers */
 pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off);
 pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off);

 pixman_rasterize_edges (image, &l, &r, t, b);
    }
}

static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] =
{
    FALSE, /* Clear 0 0    */
    FALSE, /* Src 1 0    */
    TRUE, /* Dst 0 1    */
    TRUE, /* Over 1 1-Aa */
    TRUE, /* OverReverse 1-Ab 1    */
    FALSE, /* In Ab 0    */
    FALSE, /* InReverse 0 Aa   */
    FALSE, /* Out 1-Ab 0    */
    TRUE, /* OutReverse 0 1-Aa */
    TRUE, /* Atop Ab 1-Aa */
    FALSE, /* AtopReverse 1-Ab Aa   */
    TRUE, /* Xor 1-Ab 1-Aa */
    TRUE, /* Add 1 1    */
};

static pixman_bool_t
get_trap_extents (pixman_op_t op, pixman_image_t *dest,
    const pixman_trapezoid_t *traps, int n_traps,
    pixman_box32_t *box)
{
    int i;

    /* When the operator is such that a zero source has an
     * effect on the underlying image, we have to
     * composite across the entire destination
     */
    if (!zero_src_has_no_effect [op])
    {
 box->x1 = 0;
 box->y1 = 0;
 box->x2 = dest->bits.width;
 box->y2 = dest->bits.height;
 return TRUE;
    }
    
    box->x1 = INT32_MAX;
    box->y1 = INT32_MAX;
    box->x2 = INT32_MIN;
    box->y2 = INT32_MIN;
 
    for (i = 0; i < n_traps; ++i)
    {
 const pixman_trapezoid_t *trap = &(traps[i]);
 int y1, y2;
     
 if (!pixman_trapezoid_valid (trap))
     continue;
     
 y1 = pixman_fixed_to_int (trap->top);
 if (y1 < box->y1)
     box->y1 = y1;
     
 y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));
 if (y2 > box->y2)
     box->y2 = y2;
     
#define EXTEND_MIN(x)       \
 if (pixman_fixed_to_int ((x)) < box->x1)   \
     box->x1 = pixman_fixed_to_int ((x));
#define EXTEND_MAX(x)       \
 if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2) \
     box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x)));
     
#define EXTEND(x)       \
 EXTEND_MIN(x);       \
 EXTEND_MAX(x);
     
 EXTEND(trap->left.p1.x);
 EXTEND(trap->left.p2.x);
 EXTEND(trap->right.p1.x);
 EXTEND(trap->right.p2.x);
    }
 
    if (box->x1 >= box->x2 || box->y1 >= box->y2)
 return FALSE;

    return TRUE;
}

/*
 * pixman_composite_trapezoids()
 *
 * All the trapezoids are conceptually rendered to an infinitely big image.
 * The (0, 0) coordinates of this image are then aligned with the (x, y)
 * coordinates of the source image, and then both images are aligned with
 * the (x, y) coordinates of the destination. Then these three images are
 * composited across the entire destination.
 */
PIXMAN_EXPORT void
pixman_composite_trapezoids (pixman_op_t  op,
        pixman_image_t *  src,
        pixman_image_t *  dst,
        pixman_format_code_t mask_format,
        int   x_src,
        int   y_src,
        int   x_dst,
        int   y_dst,
        int   n_traps,
        const pixman_trapezoid_t * traps)
{
    int i;

    return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A);
    
    if (n_traps <= 0)
 return;

    _pixman_image_validate (src);
    _pixman_image_validate (dst);

    if (op == PIXMAN_OP_ADD &&
 (src->common.flags & FAST_PATH_IS_OPAQUE)  &&
 (mask_format == dst->common.extended_format_code) &&
 !(dst->common.have_clip_region))
    {
 for (i = 0; i < n_traps; ++i)
 {
     const pixman_trapezoid_t *trap = &(traps[i]);
     
     if (!pixman_trapezoid_valid (trap))
  continue;
     
     pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst);
 }
    }
    else
    {
 pixman_image_t *tmp;
 pixman_box32_t box;
 int i;

 if (!get_trap_extents (op, dst, traps, n_traps, &box))
     return;
 
 if (!(tmp = pixman_image_create_bits (
    mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1)))
     return;
 
 for (i = 0; i < n_traps; ++i)
 {
     const pixman_trapezoid_t *trap = &(traps[i]);
     
     if (!pixman_trapezoid_valid (trap))
  continue;
     
     pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);
 }
 
 pixman_image_composite (op, src, tmp, dst,
    x_src + box.x1, y_src + box.y1,
    0, 0,
    x_dst + box.x1, y_dst + box.y1,
    box.x2 - box.x1, box.y2 - box.y1);
 
 pixman_image_unref (tmp);
    }
}

static int
greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b)
{
    if (a->y == b->y)
 return a->x > b->x;
    return a->y > b->y;
}

/*
 * Note that the definition of this function is a bit odd because
 * of the X coordinate space (y increasing downwards).
 */
static int
clockwise (const pixman_point_fixed_t *ref,
    const pixman_point_fixed_t *a,
    const pixman_point_fixed_t *b)
{
    pixman_point_fixed_t ad, bd;

    ad.x = a->x - ref->x;
    ad.y = a->y - ref->y;
    bd.x = b->x - ref->x;
    bd.y = b->y - ref->y;

    return ((pixman_fixed_32_32_t) bd.y * ad.x -
     (pixman_fixed_32_32_t) ad.y * bd.x) < 0;
}

static void
triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps)
{
    const pixman_point_fixed_t *top, *left, *right, *tmp;

    top = &tri->p1;
    left = &tri->p2;
    right = &tri->p3;

    if (greater_y (top, left))
    {
 tmp = left;
 left = top;
 top = tmp;
    }

    if (greater_y (top, right))
    {
 tmp = right;
 right = top;
 top = tmp;
    }

    if (clockwise (top, right, left))
    {
 tmp = right;
 right = left;
 left = tmp;
    }
    
    /*
     * Two cases:
     *
     * + +
     *        / \             / \
     *       /   \           /   \
     *      /     +         +    \
     *      /    --           --    \
     *     /   --               --   \
     *    / ---                   --- \
     *  +--                         --+
     */

    traps->top = top->y;
    traps->left.p1 = *top;
    traps->left.p2 = *left;
    traps->right.p1 = *top;
    traps->right.p2 = *right;

    if (right->y < left->y)
 traps->bottom = right->y;
    else
 traps->bottom = left->y;

    traps++;

    *traps = *(traps - 1);
    
    if (right->y < left->y)
    {
 traps->top = right->y;
 traps->bottom = left->y;
 traps->right.p1 = *right;
 traps->right.p2 = *left;
    }
    else
    {
 traps->top = left->y;
 traps->bottom = right->y;
 traps->left.p1 = *left;
 traps->left.p2 = *right;
    }
}

static pixman_trapezoid_t *
convert_triangles (int n_tris, const pixman_triangle_t *tris)
{
    pixman_trapezoid_t *traps;
    int i;

    if (n_tris <= 0)
 return NULL;
    
    traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));
    if (!traps)
 return NULL;

    for (i = 0; i < n_tris; ++i)
 triangle_to_trapezoids (&(tris[i]), traps + 2 * i);

    return traps;
}

PIXMAN_EXPORT void
pixman_composite_triangles (pixman_op_t   op,
       pixman_image_t *  src,
       pixman_image_t *  dst,
       pixman_format_code_t mask_format,
       int    x_src,
       int    y_src,
       int    x_dst,
       int    y_dst,
       int    n_tris,
       const pixman_triangle_t * tris)
{
    pixman_trapezoid_t *traps;

    if ((traps = convert_triangles (n_tris, tris)))
    {
 pixman_composite_trapezoids (op, src, dst, mask_format,
         x_src, y_src, x_dst, y_dst,
         n_tris * 2, traps);
 
 free (traps);
    }
}

PIXMAN_EXPORT void
pixman_add_triangles (pixman_image_t          *image,
        int32_t                x_off,
        int32_t                y_off,
        int                n_tris,
        const pixman_triangle_t *tris)
{
    pixman_trapezoid_t *traps;

    if ((traps = convert_triangles (n_tris, tris)))
    {
 pixman_add_trapezoids (image, x_off, y_off,
          n_tris * 2, traps);

 free (traps);
    }
}