/* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */

/* cairo - a vector graphics library with display and print output

 *

 * Copyright 2009 Andrea Canciani

 *

 * 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., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, 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 Andrea Canciani.

 *

 * Contributor(s):

 *	Andrea Canciani <ranma42@gmail.com>

 */

#include "cairoint.h"

#include "cairo-array-private.h"

#include "cairo-pattern-private.h"

/*

 * Rasterizer for mesh patterns.

 *

 * This implementation is based on techniques derived from several

 * papers (available from ACM):

 *

 * - Lien, Shantz and Pratt "Adaptive Forward Differencing for

 *   Rendering Curves and Surfaces" (discussion of the AFD technique,

 *   bound of 1/sqrt(2) on step length without proof)

 *

 * - Popescu and Rosen, "Forward rasterization" (description of

 *   forward rasterization, proof of the previous bound)

 *

 * - Klassen, "Integer Forward Differencing of Cubic Polynomials:

 *   Analysis and Algorithms"

 *

 * - Klassen, "Exact Integer Hybrid Subdivision and Forward

 *   Differencing of Cubics" (improving the bound on the minimum

 *   number of steps)

 *

 * - Chang, Shantz and Rocchetti, "Rendering Cubic Curves and Surfaces

 *   with Integer Adaptive Forward Differencing" (analysis of forward

 *   differencing applied to Bezier patches)

 *

 * Notes:

 * - Poor performance expected in degenerate cases

 *

 * - Patches mostly outside the drawing area are drawn completely (and

 *   clipped), wasting time

 *

 * - Both previous problems are greatly reduced by splitting until a

 *   reasonably small size and clipping the new tiles: execution time

 *   is quadratic in the convex-hull diameter instead than linear to

 *   the painted area. Splitting the tiles doesn't change the painted

 *   area but (usually) reduces the bounding box area (bbox area can

 *   remain the same after splitting, but cannot grow)

 *

 * - The initial implementation used adaptive forward differencing,

 *   but simple forward differencing scored better in benchmarks

 *

 * Idea:

 *

 * We do a sampling over the cubic patch with step du and dv (in the

 * two parameters) that guarantees that any point of our sampling will

 * be at most at 1/sqrt(2) from its adjacent points. In formulae

 * (assuming B is the patch):

 *

 *   |B(u,v) - B(u+du,v)| < 1/sqrt(2)

 *   |B(u,v) - B(u,v+dv)| < 1/sqrt(2)

 *

 * This means that every pixel covered by the patch will contain at

 * least one of the samples, thus forward rasterization can be

 * performed. Sketch of proof (from Popescu and Rosen):

 *

 * Let's take the P pixel we're interested into. If we assume it to be

 * square, its boundaries define 9 regions on the plane:

 *

 * 1|2|3

 * -+-+-

 * 8|P|4

 * -+-+-

 * 7|6|5

 *

 * Let's check that the pixel P will contain at least one point

 * assuming that it is covered by the patch.

 *

 * Since the pixel is covered by the patch, its center will belong to

 * (at least) one of the quads:

 *

 *   {(B(u,v), B(u+du,v), B(u,v+dv), B(u+du,v+dv)) for u,v in [0,1]}

 *

 * If P doesn't contain any of the corners of the quad:

 *

 * - if one of the corners is in 1,3,5 or 7, other two of them have to

 *   be in 2,4,6 or 8, thus if the last corner is not in P, the length

 *   of one of the edges will be > 1/sqrt(2)

 *

 * - if none of the corners is in 1,3,5 or 7, all of them are in 2,4,6

 *   and/or 8. If they are all in different regions, they can't

 *   satisfy the distance constraint. If two of them are in the same

 *   region (let's say 2), no point is in 6 and again it is impossible

 *   to have the center of P in the quad respecting the distance

 *   constraint (both these assertions can be checked by continuity

 *   considering the length of the edges of a quad with the vertices

 *   on the edges of P)

 *

 * Each of the cases led to a contradiction, so P contains at least

 * one of the corners of the quad.

 */

/*

 * Make sure that errors are less than 1 in fixed point math if you

 * change these values.

 *

 * The error is amplified by about steps^3/4 times.

 * The rasterizer always uses a number of steps that is a power of 2.

 *

 * 256 is the maximum allowed number of steps (to have error < 1)

 * using 8.24 for the differences.

 */

#define STEPS_MAX_V 256.0

#define STEPS_MAX_U 256.0

/*

 * If the patch/curve is only partially visible, split it to a finer

 * resolution to get higher chances to clip (part of) it.

 *

 * These values have not been computed, but simply obtained

 * empirically (by benchmarking some patches). They should never be

 * greater than STEPS_MAX_V (or STEPS_MAX_U), but they can be as small

 * as 1 (depending on how much you want to spend time in splitting the

 * patch/curve when trying to save some rasterization time).

 */

#define STEPS_CLIP_V 64.0

#define STEPS_CLIP_U 64.0

/* Utils */

static inline double

{

    cairo_point_double_t delta;

}

static inline int16_t

{

    /* We need to round toward zero, because otherwise adding the

     * delta 2^shift times can overflow */

    else

}

/*

 * Convert a number of steps to the equivalent shift.

 *

 * Input: the square of the minimum number of steps

 *

 * Output: the smallest integer x such that 2^x > steps

 */

static inline int

{

    int r;

}

/*

 * FD functions

 *

 * A Bezier curve is defined (with respect to a parameter t in

 * [0,1]) from its nodes (x,y,z,w) like this:

 *

 *   B(t) = x(1-t)^3 + 3yt(1-t)^2 + 3zt^2(1-t) + wt^3

 *

 * To efficiently evaluate a Bezier curve, the rasterizer uses forward

 * differences. Given x, y, z, w (the 4 nodes of the Bezier curve), it

 * is possible to convert them to forward differences form and walk

 * over the curve using fd_init (), fd_down () and fd_fwd ().

 *

 * f[0] is always the value of the Bezier curve for "current" t.

 */

/*

 * Initialize the coefficient for forward differences.

 *

 * Input: x,y,z,w are the 4 nodes of the Bezier curve

 *

 * Output: f[i] is the i-th difference of the curve

 *

 * f[0] is the value of the curve for t==0, i.e. f[0]==x.

 *

 * The initial step is 1; this means that each step increases t by 1

 * (so fd_init () immediately followed by fd_fwd (f) n times makes

 * f[0] be the value of the curve for t==n).

 */

static inline void

{

/*

 * Halve the step of the coefficients for forward differences.

 *

 * Input: f[i] is the i-th difference of the curve

 *

 * Output: f[i] is the i-th difference of the curve with half the

 *         original step

 *

 * f[0] is not affected, so the current t is not changed.

 *

 * The other coefficients are changed so that the step is half the

 * original step. This means that doing fd_fwd (f) n times with the

 * input f results in the same f[0] as doing fd_fwd (f) 2n times with

 * the output f.

 */

static inline void

{

/*

 * Perform one step of forward differences along the curve.

 *

 * Input: f[i] is the i-th difference of the curve

 *

 * Output: f[i] is the i-th difference of the curve after one step

 */

static inline void

{

/*

 * Transform to integer forward differences.

 *

 * Input: d[n] is the n-th difference (in double precision)

 *

 * Output: i[n] is the n-th difference (in fixed point precision)

 *

 * i[0] is 9.23 fixed point, other differences are 4.28 fixed point.

 */

static inline void

{

/*

 * Perform one step of integer forward differences along the curve.

 *

 * Input: f[n] is the n-th difference

 *

 * Output: f[n] is the n-th difference

 *

 * f[0] is 9.23 fixed point, other differences are 4.28 fixed point.

 */

static inline void

{

/*

 * Compute the minimum number of steps that guarantee that walking

 * over a curve will leave no holes.

 *

 * Input: p[0..3] the nodes of the Bezier curve

 *

 * Returns: the square of the number of steps

 *

 * Idea:

 *

 * We want to make sure that at every step we move by less than

 * 1/sqrt(2).

 *

 * The derivative of the cubic Bezier with nodes (p0, p1, p2, p3) is

 * the quadratic Bezier with nodes (p1-p0, p2-p1, p3-p2) scaled by 3,

 * so (since a Bezier curve is always bounded by its convex hull), we

 * can say that:

 *

 *  max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p1|, |p3-p2|)

 *

 * We can improve this by noticing that a quadratic Bezier (a,b,c) is

 * bounded by the quad (a,lerp(a,b,t),lerp(b,c,t),c) for any t, so

 * (substituting the previous values, using t=0.5 and simplifying):

 *

 *  max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|)

 *

 * So, to guarantee a maximum step length of 1/sqrt(2) we must do:

 *

 *   3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|) sqrt(2) steps

 */

static inline double

{

}

/*

 * Split a 1D Bezier cubic using de Casteljau's algorithm.

 *

 * Input: x,y,z,w the nodes of the Bezier curve

 *

 * Output: x0,y0,z0,w0 and x1,y1,z1,w1 are respectively the nodes of

 *         the first half and of the second half of the curve

 *

 * The output control nodes have to be distinct.

 */

static inline void

		 double *x0, double *y0, double *z0, double *w0,

		 double *x1, double *y1, double *z1, double *w1)

{

    double tmp;

/*

 * Split a Bezier curve using de Casteljau's algorithm.

 *

 * Input: p[0..3] the nodes of the Bezier curve

 *

 * Output: fst_half[0..3] and snd_half[0..3] are respectively the

 *         nodes of the first and of the second half of the curve

 *

 * fst_half and snd_half must be different, but they can be the same as

 * nodes.

 */

static void

	      cairo_point_double_t fst_half[4],

	      cairo_point_double_t snd_half[4])

{

typedef enum _intersection {

    INSIDE = -1, /* the interval is entirely contained in the reference interval */

    OUTSIDE = 0, /* the interval has no intersection with the reference interval */

    PARTIAL = 1  /* the interval intersects the reference interval (but is not fully inside it) */

} intersection_t;

/*

 * Check if an interval if inside another.

 *

 * Input: a,b are the extrema of the first interval

 *        c,d are the extrema of the second interval

 *

 * Returns: INSIDE  iff [a,b) intersection [c,d) = [a,b)

 *          OUTSIDE iff [a,b) intersection [c,d) = {}

 *          PARTIAL otherwise

 *

 * The function assumes a < b and c < d

 *

 * Note: Bitwise-anding the results along each component gives the

 *       expected result for [a,b) x [A,B) intersection [c,d) x [C,D).

 */

static inline int

{

    else

}

/*

 * Set the color of a pixel.

 *

 * Input: data is the base pointer of the image

 *        width, height are the dimensions of the image

 *        stride is the stride in bytes between adjacent rows

 *        x, y are the coordinates of the pixel to be colored

 *        r,g,b,a are the color components of the color to be set

 *

 * Output: the (x,y) pixel in data has the (r,g,b,a) color

 *

 * The input color components are not premultiplied, but the data

 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,

 * premultiplied).

 *

 * If the pixel to be set is outside the image, this function does

 * nothing.

 */

static inline void

	    int x, int y, uint16_t r, uint16_t g, uint16_t b, uint16_t a)

{

	uint32_t tr, tg, tb, ta;

	/* Premultiply and round */

    }

/*

 * Forward-rasterize a cubic curve using forward differences.

 *

 * Input: data is the base pointer of the image

 *        width, height are the dimensions of the image

 *        stride is the stride in bytes between adjacent rows

 *        ushift is log2(n) if n is the number of desired steps

 *        dxu[i], dyu[i] are the x,y forward differences of the curve

 *        r0,g0,b0,a0 are the color components of the start point

 *        r3,g3,b3,a3 are the color components of the end point

 *

 * Output: data will be changed to have the requested curve drawn in

 *         the specified colors

 *

 * The input color components are not premultiplied, but the data

 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,

 * premultiplied).

 *

 * The function draws n+1 pixels, that is from the point at step 0 to

 * the point at step n, both included. This is the discrete equivalent

 * to drawing the curve for values of the interpolation parameter in

 * [0,1] (including both extremes).

 */

static inline void

			int ushift, double dxu[4], double dyu[4],

			uint16_t r0, uint16_t g0, uint16_t b0, uint16_t a0,

			uint16_t r3, uint16_t g3, uint16_t b3, uint16_t a3)

{

    int32_t xu[4], yu[4];

    /*

     * Use (dxu[0],dyu[0]) as origin for the forward differences.

     *

     * This makes it possible to handle much larger coordinates (the

     * ones that can be represented as cairo_fixed_t)

     */

	/*

	 * This rasterizer assumes that pixels are integer aligned

	 * squares, so a generic (x,y) point belongs to the pixel with

	 * top-left coordinates (floor(x), floor(y))

	 */

    }

/*

 * Clip, split and rasterize a Bezier curve.

 *

 * Input: data is the base pointer of the image

 *        width, height are the dimensions of the image

 *        stride is the stride in bytes between adjacent rows

 *        p[i] is the i-th node of the Bezier curve

 *        c0[i] is the i-th color component at the start point

 *        c3[i] is the i-th color component at the end point

 *

 * Output: data will be changed to have the requested curve drawn in

 *         the specified colors

 *

 * The input color components are not premultiplied, but the data

 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,

 * premultiplied).

 *

 * The color components are red, green, blue and alpha, in this order.

 *

 * The function guarantees that it will draw the curve with a step

 * small enough to never have a distance above 1/sqrt(2) between two

 * consecutive points (which is needed to ensure that no hole can

 * appear when using this function to rasterize a patch).

 */

static void

		   cairo_point_double_t p[4], double c0[4], double c3[4])

{

    double top, bottom, left, right, steps_sq;

    int i, v;

    }

    /* Check visibility */

    }

	/*

	 * The number of steps is greater than the threshold. This

	 * means that either the error would become too big if we

	 * directly rasterized it or that we can probably save some

	 * time by splitting the curve and clipping part of it

	 */

	cairo_point_double_t first[4], second[4];

	double midc[4];

    } else {

	double xu[4], yu[4];

	}

				xu, yu,

	/* Draw the end point, to make sure that we didn't leave it

	 * out because of rounding */

    }

}

/*

 * Forward-rasterize a cubic Bezier patch using forward differences.

 *

 * Input: data is the base pointer of the image

 *        width, height are the dimensions of the image

 *        stride is the stride in bytes between adjacent rows

 *        vshift is log2(n) if n is the number of desired steps

 *        p[i][j], p[i][j] are the nodes of the Bezier patch

 *        col[i][j] is the j-th color component of the i-th corner

 *

 * Output: data will be changed to have the requested patch drawn in

 *         the specified colors

 *

 * The nodes of the patch are as follows:

 *

 * u\v 0    - >    1

 * 0  p00 p01 p02 p03

 * |  p10 p11 p12 p13

 * v  p20 p21 p22 p23

 * 1  p30 p31 p32 p33

 *

 * i.e. u varies along the first component (rows), v varies along the

 * second one (columns).

 *

 * The color components are red, green, blue and alpha, in this order.

 * c[0..3] are the colors in p00, p30, p03, p33 respectively

 *

 * The input color components are not premultiplied, but the data

 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,

 * premultiplied).

 *

 * If the patch folds over itself, the part with the highest v

 * parameter is considered above. If both have the same v, the one

 * with the highest u parameter is above.

 *

 * The function draws n+1 curves, that is from the curve at step 0 to

 * the curve at step n, both included. This is the discrete equivalent

 * to drawing the patch for values of the interpolation parameter in

 * [0,1] (including both extremes).

 */

static inline void

			cairo_point_double_t p[4][4], double col[4][4])

{

    double pv[4][2][4], cstart[4], cend[4], dcstart[4], dcend[4];

    int v, i, k;

    /*

     * pv[i][0] is the function (represented using forward

     * differences) mapping v to the x coordinate of the i-th node of

     * the Bezier curve with parameter u.

     * (Likewise p[i][0] gives the y coordinate).

     *

     * This means that (pv[0][0][0],pv[0][1][0]),

     * (pv[1][0][0],pv[1][1][0]), (pv[2][0][0],pv[2][1][0]) and

     * (pv[3][0][0],pv[3][1][0]) are the nodes of the Bezier curve for

     * the "current" v value (see the FD comments for more details).

     */

	}

    }

    }

	cairo_point_double_t nodes[4];

	}

	}

    }

/*

 * Clip, split and rasterize a Bezier cubic patch.

 *

 * Input: data is the base pointer of the image

 *        width, height are the dimensions of the image

 *        stride is the stride in bytes between adjacent rows

 *        p[i][j], p[i][j] are the nodes of the patch

 *        col[i][j] is the j-th color component of the i-th corner

 *

 * Output: data will be changed to have the requested patch drawn in

 *         the specified colors

 *

 * The nodes of the patch are as follows:

 *

 * u\v 0    - >    1

 * 0  p00 p01 p02 p03

 * |  p10 p11 p12 p13

 * v  p20 p21 p22 p23

 * 1  p30 p31 p32 p33

 *

 * i.e. u varies along the first component (rows), v varies along the

 * second one (columns).

 *

 * The color components are red, green, blue and alpha, in this order.

 * c[0..3] are the colors in p00, p30, p03, p33 respectively

 *

 * The input color components are not premultiplied, but the data

 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,

 * premultiplied).

 *

 * If the patch folds over itself, the part with the highest v

 * parameter is considered above. If both have the same v, the one

 * with the highest u parameter is above.

 *

 * The function guarantees that it will draw the patch with a step

 * small enough to never have a distance above 1/sqrt(2) between two

 * adjacent points (which guarantees that no hole can appear).

 *

 * This function can be used to rasterize a tile of PDF type 7

 * shadings (see http://www.adobe.com/devnet/pdf/pdf_reference.html).

 */

static void

		     cairo_point_double_t p[4][4], double c[4][4])

{

    double top, bottom, left, right, steps_sq;

    int i, j, v;

	}

    }

	}

    }

	/* The number of steps is greater than the threshold. This

	 * means that either the error would become too big if we

	 * directly rasterized it or that we can probably save some

	 * time by splitting the curve and clipping part of it. The

	 * patch is only split in the v direction to guarantee that

	 * rasterizing each part will overwrite parts with low v with

	 * overlapping parts with higher v. */

	cairo_point_double_t first[4][4], second[4][4];

	double subc[4][4];

	}

	}

    } else {

    }

}

/*

 * Draw a tensor product shading pattern.

 *

 * Input: mesh is the mesh pattern

 *        data is the base pointer of the image

 *        width, height are the dimensions of the image

 *        stride is the stride in bytes between adjacent rows

 *

 * Output: data will be changed to have the pattern drawn on it

 *

 * data is assumed to be clear and its content is assumed to be in

 * CAIRO_FORMAT_ARGB32 (8 bpc, premultiplied).

 *

 * This function can be used to rasterize a PDF type 7 shading (see

 * http://www.adobe.com/devnet/pdf/pdf_reference.html).

 */

void

			       void                       *data,

			       int                         width,

			       int                         height,

			       int                         stride,

			       double                      x_offset,

			       double                      y_offset)

{

    cairo_point_double_t nodes[4][4];

    double colors[4][4];

    cairo_matrix_t p2u;

    unsigned int i, j, k, n;

    cairo_status_t status;

    const cairo_mesh_patch_t *patch;

    const cairo_color_t *c;

	    }

	}

    }