1 /* -*- Mode: c; tab-width: 8; c-basic-offset: 4; indent-tabs-mode: t; -*- */
2 /* cairo - a vector graphics library with display and print output
4 * Copyright 2009 Andrea Canciani
6 * This library is free software; you can redistribute it and/or
7 * modify it either under the terms of the GNU Lesser General Public
8 * License version 2.1 as published by the Free Software Foundation
9 * (the "LGPL") or, at your option, under the terms of the Mozilla
10 * Public License Version 1.1 (the "MPL"). If you do not alter this
11 * notice, a recipient may use your version of this file under either
12 * the MPL or the LGPL.
14 * You should have received a copy of the LGPL along with this library
15 * in the file COPYING-LGPL-2.1; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
17 * You should have received a copy of the MPL along with this library
18 * in the file COPYING-MPL-1.1
20 * The contents of this file are subject to the Mozilla Public License
21 * Version 1.1 (the "License"); you may not use this file except in
22 * compliance with the License. You may obtain a copy of the License at
23 * http://www.mozilla.org/MPL/
25 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
26 * OF ANY KIND, either express or implied. See the LGPL or the MPL for
27 * the specific language governing rights and limitations.
29 * The Original Code is the cairo graphics library.
31 * The Initial Developer of the Original Code is Andrea Canciani.
34 * Andrea Canciani <ranma42@gmail.com>
39 #include "cairo-array-private.h"
40 #include "cairo-pattern-private.h"
43 * Rasterizer for mesh patterns.
45 * This implementation is based on techniques derived from several
46 * papers (available from ACM):
48 * - Lien, Shantz and Pratt "Adaptive Forward Differencing for
49 * Rendering Curves and Surfaces" (discussion of the AFD technique,
50 * bound of 1/sqrt(2) on step length without proof)
52 * - Popescu and Rosen, "Forward rasterization" (description of
53 * forward rasterization, proof of the previous bound)
55 * - Klassen, "Integer Forward Differencing of Cubic Polynomials:
56 * Analysis and Algorithms"
58 * - Klassen, "Exact Integer Hybrid Subdivision and Forward
59 * Differencing of Cubics" (improving the bound on the minimum
62 * - Chang, Shantz and Rocchetti, "Rendering Cubic Curves and Surfaces
63 * with Integer Adaptive Forward Differencing" (analysis of forward
64 * differencing applied to Bezier patches)
67 * - Poor performance expected in degenerate cases
69 * - Patches mostly outside the drawing area are drawn completely (and
70 * clipped), wasting time
72 * - Both previous problems are greatly reduced by splitting until a
73 * reasonably small size and clipping the new tiles: execution time
74 * is quadratic in the convex-hull diameter instead than linear to
75 * the painted area. Splitting the tiles doesn't change the painted
76 * area but (usually) reduces the bounding box area (bbox area can
77 * remain the same after splitting, but cannot grow)
79 * - The initial implementation used adaptive forward differencing,
80 * but simple forward differencing scored better in benchmarks
84 * We do a sampling over the cubic patch with step du and dv (in the
85 * two parameters) that guarantees that any point of our sampling will
86 * be at most at 1/sqrt(2) from its adjacent points. In formulae
87 * (assuming B is the patch):
89 * |B(u,v) - B(u+du,v)| < 1/sqrt(2)
90 * |B(u,v) - B(u,v+dv)| < 1/sqrt(2)
92 * This means that every pixel covered by the patch will contain at
93 * least one of the samples, thus forward rasterization can be
94 * performed. Sketch of proof (from Popescu and Rosen):
96 * Let's take the P pixel we're interested into. If we assume it to be
97 * square, its boundaries define 9 regions on the plane:
105 * Let's check that the pixel P will contain at least one point
106 * assuming that it is covered by the patch.
108 * Since the pixel is covered by the patch, its center will belong to
109 * (at least) one of the quads:
111 * {(B(u,v), B(u+du,v), B(u,v+dv), B(u+du,v+dv)) for u,v in [0,1]}
113 * If P doesn't contain any of the corners of the quad:
115 * - if one of the corners is in 1,3,5 or 7, other two of them have to
116 * be in 2,4,6 or 8, thus if the last corner is not in P, the length
117 * of one of the edges will be > 1/sqrt(2)
119 * - if none of the corners is in 1,3,5 or 7, all of them are in 2,4,6
120 * and/or 8. If they are all in different regions, they can't
121 * satisfy the distance constraint. If two of them are in the same
122 * region (let's say 2), no point is in 6 and again it is impossible
123 * to have the center of P in the quad respecting the distance
124 * constraint (both these assertions can be checked by continuity
125 * considering the length of the edges of a quad with the vertices
128 * Each of the cases led to a contradiction, so P contains at least
129 * one of the corners of the quad.
133 * Make sure that errors are less than 1 in fixed point math if you
134 * change these values.
136 * The error is amplified by about steps^3/4 times.
137 * The rasterizer always uses a number of steps that is a power of 2.
139 * 256 is the maximum allowed number of steps (to have error < 1)
140 * using 8.24 for the differences.
142 #define STEPS_MAX_V 256.0
143 #define STEPS_MAX_U 256.0
146 * If the patch/curve is only partially visible, split it to a finer
147 * resolution to get higher chances to clip (part of) it.
149 * These values have not been computed, but simply obtained
150 * empirically (by benchmarking some patches). They should never be
151 * greater than STEPS_MAX_V (or STEPS_MAX_U), but they can be as small
152 * as 1 (depending on how much you want to spend time in splitting the
153 * patch/curve when trying to save some rasterization time).
155 #define STEPS_CLIP_V 64.0
156 #define STEPS_CLIP_U 64.0
161 sqlen (cairo_point_double_t p0
, cairo_point_double_t p1
)
163 cairo_point_double_t delta
;
165 delta
.x
= p0
.x
- p1
.x
;
166 delta
.y
= p0
.y
- p1
.y
;
168 return delta
.x
* delta
.x
+ delta
.y
* delta
.y
;
171 static inline int16_t
172 _color_delta_to_shifted_short (int32_t from
, int32_t to
, int shift
)
174 int32_t delta
= to
- from
;
176 /* We need to round toward zero, because otherwise adding the
177 * delta 2^shift times can overflow */
179 return delta
>> shift
;
181 return -((-delta
) >> shift
);
185 * Convert a number of steps to the equivalent shift.
187 * Input: the square of the minimum number of steps
189 * Output: the smallest integer x such that 2^x > steps
192 sqsteps2shift (double steps_sq
)
195 frexp (MAX (1.0, steps_sq
), &r
);
202 * A Bezier curve is defined (with respect to a parameter t in
203 * [0,1]) from its nodes (x,y,z,w) like this:
205 * B(t) = x(1-t)^3 + 3yt(1-t)^2 + 3zt^2(1-t) + wt^3
207 * To efficiently evaluate a Bezier curve, the rasterizer uses forward
208 * differences. Given x, y, z, w (the 4 nodes of the Bezier curve), it
209 * is possible to convert them to forward differences form and walk
210 * over the curve using fd_init (), fd_down () and fd_fwd ().
212 * f[0] is always the value of the Bezier curve for "current" t.
216 * Initialize the coefficient for forward differences.
218 * Input: x,y,z,w are the 4 nodes of the Bezier curve
220 * Output: f[i] is the i-th difference of the curve
222 * f[0] is the value of the curve for t==0, i.e. f[0]==x.
224 * The initial step is 1; this means that each step increases t by 1
225 * (so fd_init () immediately followed by fd_fwd (f) n times makes
226 * f[0] be the value of the curve for t==n).
229 fd_init (double x
, double y
, double z
, double w
, double f
[4])
233 f
[2] = 6. * (w
- 2. * z
+ y
);
234 f
[3] = 6. * (w
- 3. * z
+ 3. * y
- x
);
238 * Halve the step of the coefficients for forward differences.
240 * Input: f[i] is the i-th difference of the curve
242 * Output: f[i] is the i-th difference of the curve with half the
245 * f[0] is not affected, so the current t is not changed.
247 * The other coefficients are changed so that the step is half the
248 * original step. This means that doing fd_fwd (f) n times with the
249 * input f results in the same f[0] as doing fd_fwd (f) 2n times with
253 fd_down (double f
[4])
256 f
[2] = f
[2] * 0.25 - f
[3];
257 f
[1] = (f
[1] - f
[2]) * 0.5;
261 * Perform one step of forward differences along the curve.
263 * Input: f[i] is the i-th difference of the curve
265 * Output: f[i] is the i-th difference of the curve after one step
276 * Transform to integer forward differences.
278 * Input: d[n] is the n-th difference (in double precision)
280 * Output: i[n] is the n-th difference (in fixed point precision)
282 * i[0] is 9.23 fixed point, other differences are 4.28 fixed point.
285 fd_fixed (double d
[4], int32_t i
[4])
287 i
[0] = _cairo_fixed_16_16_from_double (256 * 2 * d
[0]);
288 i
[1] = _cairo_fixed_16_16_from_double (256 * 16 * d
[1]);
289 i
[2] = _cairo_fixed_16_16_from_double (256 * 16 * d
[2]);
290 i
[3] = _cairo_fixed_16_16_from_double (256 * 16 * d
[3]);
294 * Perform one step of integer forward differences along the curve.
296 * Input: f[n] is the n-th difference
298 * Output: f[n] is the n-th difference
300 * f[0] is 9.23 fixed point, other differences are 4.28 fixed point.
303 fd_fixed_fwd (int32_t f
[4])
305 f
[0] += (f
[1] >> 5) + ((f
[1] >> 4) & 1);
311 * Compute the minimum number of steps that guarantee that walking
312 * over a curve will leave no holes.
314 * Input: p[0..3] the nodes of the Bezier curve
316 * Returns: the square of the number of steps
320 * We want to make sure that at every step we move by less than
323 * The derivative of the cubic Bezier with nodes (p0, p1, p2, p3) is
324 * the quadratic Bezier with nodes (p1-p0, p2-p1, p3-p2) scaled by 3,
325 * so (since a Bezier curve is always bounded by its convex hull), we
328 * max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p1|, |p3-p2|)
330 * We can improve this by noticing that a quadratic Bezier (a,b,c) is
331 * bounded by the quad (a,lerp(a,b,t),lerp(b,c,t),c) for any t, so
332 * (substituting the previous values, using t=0.5 and simplifying):
334 * max(|B'(t)|) <= 3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|)
336 * So, to guarantee a maximum step length of 1/sqrt(2) we must do:
338 * 3 max (|p1-p0|, |p2-p0|/2, |p3-p1|/2, |p3-p2|) sqrt(2) steps
341 bezier_steps_sq (cairo_point_double_t p
[4])
343 double tmp
= sqlen (p
[0], p
[1]);
344 tmp
= MAX (tmp
, sqlen (p
[2], p
[3]));
345 tmp
= MAX (tmp
, sqlen (p
[0], p
[2]) * .25);
346 tmp
= MAX (tmp
, sqlen (p
[1], p
[3]) * .25);
351 * Split a 1D Bezier cubic using de Casteljau's algorithm.
353 * Input: x,y,z,w the nodes of the Bezier curve
355 * Output: x0,y0,z0,w0 and x1,y1,z1,w1 are respectively the nodes of
356 * the first half and of the second half of the curve
358 * The output control nodes have to be distinct.
361 split_bezier_1D (double x
, double y
, double z
, double w
,
362 double *x0
, double *y0
, double *z0
, double *w0
,
363 double *x1
, double *y1
, double *z1
, double *w1
)
374 *z0
= 0.5 * (*y0
+ tmp
);
375 *y1
= 0.5 * (tmp
+ *z1
);
377 *w0
= *x1
= 0.5 * (*z0
+ *y1
);
381 * Split a Bezier curve using de Casteljau's algorithm.
383 * Input: p[0..3] the nodes of the Bezier curve
385 * Output: fst_half[0..3] and snd_half[0..3] are respectively the
386 * nodes of the first and of the second half of the curve
388 * fst_half and snd_half must be different, but they can be the same as
392 split_bezier (cairo_point_double_t p
[4],
393 cairo_point_double_t fst_half
[4],
394 cairo_point_double_t snd_half
[4])
396 split_bezier_1D (p
[0].x
, p
[1].x
, p
[2].x
, p
[3].x
,
397 &fst_half
[0].x
, &fst_half
[1].x
, &fst_half
[2].x
, &fst_half
[3].x
,
398 &snd_half
[0].x
, &snd_half
[1].x
, &snd_half
[2].x
, &snd_half
[3].x
);
400 split_bezier_1D (p
[0].y
, p
[1].y
, p
[2].y
, p
[3].y
,
401 &fst_half
[0].y
, &fst_half
[1].y
, &fst_half
[2].y
, &fst_half
[3].y
,
402 &snd_half
[0].y
, &snd_half
[1].y
, &snd_half
[2].y
, &snd_half
[3].y
);
406 typedef enum _intersection
{
407 INSIDE
= -1, /* the interval is entirely contained in the reference interval */
408 OUTSIDE
= 0, /* the interval has no intersection with the reference interval */
409 PARTIAL
= 1 /* the interval intersects the reference interval (but is not fully inside it) */
413 * Check if an interval if inside another.
415 * Input: a,b are the extrema of the first interval
416 * c,d are the extrema of the second interval
418 * Returns: INSIDE iff [a,b) intersection [c,d) = [a,b)
419 * OUTSIDE iff [a,b) intersection [c,d) = {}
422 * The function assumes a < b and c < d
424 * Note: Bitwise-anding the results along each component gives the
425 * expected result for [a,b) x [A,B) intersection [c,d) x [C,D).
428 intersect_interval (double a
, double b
, double c
, double d
)
430 if (c
<= a
&& b
<= d
)
432 else if (a
>= d
|| b
<= c
)
439 * Set the color of a pixel.
441 * Input: data is the base pointer of the image
442 * width, height are the dimensions of the image
443 * stride is the stride in bytes between adjacent rows
444 * x, y are the coordinates of the pixel to be colored
445 * r,g,b,a are the color components of the color to be set
447 * Output: the (x,y) pixel in data has the (r,g,b,a) color
449 * The input color components are not premultiplied, but the data
450 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
453 * If the pixel to be set is outside the image, this function does
457 draw_pixel (unsigned char *data
, int width
, int height
, int stride
,
458 int x
, int y
, uint16_t r
, uint16_t g
, uint16_t b
, uint16_t a
)
460 if (likely (0 <= x
&& 0 <= y
&& x
< width
&& y
< height
)) {
461 uint32_t tr
, tg
, tb
, ta
;
463 /* Premultiply and round */
465 tr
= r
* ta
+ 0x8000;
466 tg
= g
* ta
+ 0x8000;
467 tb
= b
* ta
+ 0x8000;
473 *((uint32_t*) (data
+ y
*stride
+ 4*x
)) = ((ta
<< 16) & 0xff000000) |
474 ((tr
>> 8) & 0xff0000) | ((tg
>> 16) & 0xff00) | (tb
>> 24);
479 * Forward-rasterize a cubic curve using forward differences.
481 * Input: data is the base pointer of the image
482 * width, height are the dimensions of the image
483 * stride is the stride in bytes between adjacent rows
484 * ushift is log2(n) if n is the number of desired steps
485 * dxu[i], dyu[i] are the x,y forward differences of the curve
486 * r0,g0,b0,a0 are the color components of the start point
487 * r3,g3,b3,a3 are the color components of the end point
489 * Output: data will be changed to have the requested curve drawn in
490 * the specified colors
492 * The input color components are not premultiplied, but the data
493 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
496 * The function draws n+1 pixels, that is from the point at step 0 to
497 * the point at step n, both included. This is the discrete equivalent
498 * to drawing the curve for values of the interpolation parameter in
499 * [0,1] (including both extremes).
502 rasterize_bezier_curve (unsigned char *data
, int width
, int height
, int stride
,
503 int ushift
, double dxu
[4], double dyu
[4],
504 uint16_t r0
, uint16_t g0
, uint16_t b0
, uint16_t a0
,
505 uint16_t r3
, uint16_t g3
, uint16_t b3
, uint16_t a3
)
507 int32_t xu
[4], yu
[4];
508 int x0
, y0
, u
, usteps
= 1 << ushift
;
510 uint16_t r
= r0
, g
= g0
, b
= b0
, a
= a0
;
511 int16_t dr
= _color_delta_to_shifted_short (r0
, r3
, ushift
);
512 int16_t dg
= _color_delta_to_shifted_short (g0
, g3
, ushift
);
513 int16_t db
= _color_delta_to_shifted_short (b0
, b3
, ushift
);
514 int16_t da
= _color_delta_to_shifted_short (a0
, a3
, ushift
);
520 * Use (dxu[0],dyu[0]) as origin for the forward differences.
522 * This makes it possible to handle much larger coordinates (the
523 * ones that can be represented as cairo_fixed_t)
525 x0
= _cairo_fixed_from_double (dxu
[0]);
526 y0
= _cairo_fixed_from_double (dyu
[0]);
530 for (u
= 0; u
<= usteps
; ++u
) {
532 * This rasterizer assumes that pixels are integer aligned
533 * squares, so a generic (x,y) point belongs to the pixel with
534 * top-left coordinates (floor(x), floor(y))
537 int x
= _cairo_fixed_integer_floor (x0
+ (xu
[0] >> 15) + ((xu
[0] >> 14) & 1));
538 int y
= _cairo_fixed_integer_floor (y0
+ (yu
[0] >> 15) + ((yu
[0] >> 14) & 1));
540 draw_pixel (data
, width
, height
, stride
, x
, y
, r
, g
, b
, a
);
552 * Clip, split and rasterize a Bezier curve.
554 * Input: data is the base pointer of the image
555 * width, height are the dimensions of the image
556 * stride is the stride in bytes between adjacent rows
557 * p[i] is the i-th node of the Bezier curve
558 * c0[i] is the i-th color component at the start point
559 * c3[i] is the i-th color component at the end point
561 * Output: data will be changed to have the requested curve drawn in
562 * the specified colors
564 * The input color components are not premultiplied, but the data
565 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
568 * The color components are red, green, blue and alpha, in this order.
570 * The function guarantees that it will draw the curve with a step
571 * small enough to never have a distance above 1/sqrt(2) between two
572 * consecutive points (which is needed to ensure that no hole can
573 * appear when using this function to rasterize a patch).
576 draw_bezier_curve (unsigned char *data
, int width
, int height
, int stride
,
577 cairo_point_double_t p
[4], double c0
[4], double c3
[4])
579 double top
, bottom
, left
, right
, steps_sq
;
582 top
= bottom
= p
[0].y
;
583 for (i
= 1; i
< 4; ++i
) {
584 top
= MIN (top
, p
[i
].y
);
585 bottom
= MAX (bottom
, p
[i
].y
);
588 /* Check visibility */
589 v
= intersect_interval (top
, bottom
, 0, height
);
593 left
= right
= p
[0].x
;
594 for (i
= 1; i
< 4; ++i
) {
595 left
= MIN (left
, p
[i
].x
);
596 right
= MAX (right
, p
[i
].x
);
599 v
&= intersect_interval (left
, right
, 0, width
);
603 steps_sq
= bezier_steps_sq (p
);
604 if (steps_sq
>= (v
== INSIDE
? STEPS_MAX_U
* STEPS_MAX_U
: STEPS_CLIP_U
* STEPS_CLIP_U
)) {
606 * The number of steps is greater than the threshold. This
607 * means that either the error would become too big if we
608 * directly rasterized it or that we can probably save some
609 * time by splitting the curve and clipping part of it
611 cairo_point_double_t first
[4], second
[4];
613 split_bezier (p
, first
, second
);
614 midc
[0] = (c0
[0] + c3
[0]) * 0.5;
615 midc
[1] = (c0
[1] + c3
[1]) * 0.5;
616 midc
[2] = (c0
[2] + c3
[2]) * 0.5;
617 midc
[3] = (c0
[3] + c3
[3]) * 0.5;
618 draw_bezier_curve (data
, width
, height
, stride
, first
, c0
, midc
);
619 draw_bezier_curve (data
, width
, height
, stride
, second
, midc
, c3
);
622 int ushift
= sqsteps2shift (steps_sq
), k
;
624 fd_init (p
[0].x
, p
[1].x
, p
[2].x
, p
[3].x
, xu
);
625 fd_init (p
[0].y
, p
[1].y
, p
[2].y
, p
[3].y
, yu
);
627 for (k
= 0; k
< ushift
; ++k
) {
632 rasterize_bezier_curve (data
, width
, height
, stride
, ushift
,
634 _cairo_color_double_to_short (c0
[0]),
635 _cairo_color_double_to_short (c0
[1]),
636 _cairo_color_double_to_short (c0
[2]),
637 _cairo_color_double_to_short (c0
[3]),
638 _cairo_color_double_to_short (c3
[0]),
639 _cairo_color_double_to_short (c3
[1]),
640 _cairo_color_double_to_short (c3
[2]),
641 _cairo_color_double_to_short (c3
[3]));
643 /* Draw the end point, to make sure that we didn't leave it
644 * out because of rounding */
645 draw_pixel (data
, width
, height
, stride
,
646 _cairo_fixed_integer_floor (_cairo_fixed_from_double (p
[3].x
)),
647 _cairo_fixed_integer_floor (_cairo_fixed_from_double (p
[3].y
)),
648 _cairo_color_double_to_short (c3
[0]),
649 _cairo_color_double_to_short (c3
[1]),
650 _cairo_color_double_to_short (c3
[2]),
651 _cairo_color_double_to_short (c3
[3]));
656 * Forward-rasterize a cubic Bezier patch using forward differences.
658 * Input: data is the base pointer of the image
659 * width, height are the dimensions of the image
660 * stride is the stride in bytes between adjacent rows
661 * vshift is log2(n) if n is the number of desired steps
662 * p[i][j], p[i][j] are the the nodes of the Bezier patch
663 * col[i][j] is the j-th color component of the i-th corner
665 * Output: data will be changed to have the requested patch drawn in
666 * the specified colors
668 * The nodes of the patch are as follows:
676 * i.e. u varies along the first component (rows), v varies along the
677 * second one (columns).
679 * The color components are red, green, blue and alpha, in this order.
680 * c[0..3] are the colors in p00, p30, p03, p33 respectively
682 * The input color components are not premultiplied, but the data
683 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
686 * If the patch folds over itself, the part with the highest v
687 * parameter is considered above. If both have the same v, the one
688 * with the highest u parameter is above.
690 * The function draws n+1 curves, that is from the curve at step 0 to
691 * the curve at step n, both included. This is the discrete equivalent
692 * to drawing the patch for values of the interpolation parameter in
693 * [0,1] (including both extremes).
696 rasterize_bezier_patch (unsigned char *data
, int width
, int height
, int stride
, int vshift
,
697 cairo_point_double_t p
[4][4], double col
[4][4])
699 double pv
[4][2][4], cstart
[4], cend
[4], dcstart
[4], dcend
[4];
705 * pv[i][0] is the function (represented using forward
706 * differences) mapping v to the x coordinate of the i-th node of
707 * the Bezier curve with parameter u.
708 * (Likewise p[i][0] gives the y coordinate).
710 * This means that (pv[0][0][0],pv[0][1][0]),
711 * (pv[1][0][0],pv[1][1][0]), (pv[2][0][0],pv[2][1][0]) and
712 * (pv[3][0][0],pv[3][1][0]) are the nodes of the Bezier curve for
713 * the "current" v value (see the FD comments for more details).
715 for (i
= 0; i
< 4; ++i
) {
716 fd_init (p
[i
][0].x
, p
[i
][1].x
, p
[i
][2].x
, p
[i
][3].x
, pv
[i
][0]);
717 fd_init (p
[i
][0].y
, p
[i
][1].y
, p
[i
][2].y
, p
[i
][3].y
, pv
[i
][1]);
718 for (k
= 0; k
< vshift
; ++k
) {
724 for (i
= 0; i
< 4; ++i
) {
725 cstart
[i
] = col
[0][i
];
727 dcstart
[i
] = (col
[2][i
] - col
[0][i
]) / v
;
728 dcend
[i
] = (col
[3][i
] - col
[1][i
]) / v
;
733 cairo_point_double_t nodes
[4];
734 for (i
= 0; i
< 4; ++i
) {
735 nodes
[i
].x
= pv
[i
][0][0];
736 nodes
[i
].y
= pv
[i
][1][0];
739 draw_bezier_curve (data
, width
, height
, stride
, nodes
, cstart
, cend
);
741 for (i
= 0; i
< 4; ++i
) {
744 cstart
[i
] += dcstart
[i
];
751 * Clip, split and rasterize a Bezier cubic patch.
753 * Input: data is the base pointer of the image
754 * width, height are the dimensions of the image
755 * stride is the stride in bytes between adjacent rows
756 * p[i][j], p[i][j] are the nodes of the patch
757 * col[i][j] is the j-th color component of the i-th corner
759 * Output: data will be changed to have the requested patch drawn in
760 * the specified colors
762 * The nodes of the patch are as follows:
770 * i.e. u varies along the first component (rows), v varies along the
771 * second one (columns).
773 * The color components are red, green, blue and alpha, in this order.
774 * c[0..3] are the colors in p00, p30, p03, p33 respectively
776 * The input color components are not premultiplied, but the data
777 * stored in the image is assumed to be in CAIRO_FORMAT_ARGB32 (8 bpc,
780 * If the patch folds over itself, the part with the highest v
781 * parameter is considered above. If both have the same v, the one
782 * with the highest u parameter is above.
784 * The function guarantees that it will draw the patch with a step
785 * small enough to never have a distance above 1/sqrt(2) between two
786 * adjacent points (which guarantees that no hole can appear).
788 * This function can be used to rasterize a tile of PDF type 7
789 * shadings (see http://www.adobe.com/devnet/pdf/pdf_reference.html).
792 draw_bezier_patch (unsigned char *data
, int width
, int height
, int stride
,
793 cairo_point_double_t p
[4][4], double c
[4][4])
795 double top
, bottom
, left
, right
, steps_sq
;
798 top
= bottom
= p
[0][0].y
;
799 for (i
= 0; i
< 4; ++i
) {
800 for (j
= 0; j
< 4; ++j
) {
801 top
= MIN (top
, p
[i
][j
].y
);
802 bottom
= MAX (bottom
, p
[i
][j
].y
);
806 v
= intersect_interval (top
, bottom
, 0, height
);
810 left
= right
= p
[0][0].x
;
811 for (i
= 0; i
< 4; ++i
) {
812 for (j
= 0; j
< 4; ++j
) {
813 left
= MIN (left
, p
[i
][j
].x
);
814 right
= MAX (right
, p
[i
][j
].x
);
818 v
&= intersect_interval (left
, right
, 0, width
);
823 for (i
= 0; i
< 4; ++i
)
824 steps_sq
= MAX (steps_sq
, bezier_steps_sq (p
[i
]));
826 if (steps_sq
>= (v
== INSIDE
? STEPS_MAX_V
* STEPS_MAX_V
: STEPS_CLIP_V
* STEPS_CLIP_V
)) {
827 /* The number of steps is greater than the threshold. This
828 * means that either the error would become too big if we
829 * directly rasterized it or that we can probably save some
830 * time by splitting the curve and clipping part of it. The
831 * patch is only split in the v direction to guarantee that
832 * rasterizing each part will overwrite parts with low v with
833 * overlapping parts with higher v. */
835 cairo_point_double_t first
[4][4], second
[4][4];
838 for (i
= 0; i
< 4; ++i
)
839 split_bezier (p
[i
], first
[i
], second
[i
]);
841 for (i
= 0; i
< 4; ++i
) {
842 subc
[0][i
] = c
[0][i
];
843 subc
[1][i
] = c
[1][i
];
844 subc
[2][i
] = 0.5 * (c
[0][i
] + c
[2][i
]);
845 subc
[3][i
] = 0.5 * (c
[1][i
] + c
[3][i
]);
848 draw_bezier_patch (data
, width
, height
, stride
, first
, subc
);
850 for (i
= 0; i
< 4; ++i
) {
851 subc
[0][i
] = subc
[2][i
];
852 subc
[1][i
] = subc
[3][i
];
853 subc
[2][i
] = c
[2][i
];
854 subc
[3][i
] = c
[3][i
];
856 draw_bezier_patch (data
, width
, height
, stride
, second
, subc
);
858 rasterize_bezier_patch (data
, width
, height
, stride
, sqsteps2shift (steps_sq
), p
, c
);
863 * Draw a tensor product shading pattern.
865 * Input: mesh is the mesh pattern
866 * data is the base pointer of the image
867 * width, height are the dimensions of the image
868 * stride is the stride in bytes between adjacent rows
870 * Output: data will be changed to have the pattern drawn on it
872 * data is assumed to be clear and its content is assumed to be in
873 * CAIRO_FORMAT_ARGB32 (8 bpc, premultiplied).
875 * This function can be used to rasterize a PDF type 7 shading (see
876 * http://www.adobe.com/devnet/pdf/pdf_reference.html).
879 _cairo_mesh_pattern_rasterize (const cairo_mesh_pattern_t
*mesh
,
887 cairo_point_double_t nodes
[4][4];
890 unsigned int i
, j
, k
, n
;
891 cairo_status_t status
;
892 const cairo_mesh_patch_t
*patch
;
893 const cairo_color_t
*c
;
895 assert (mesh
->base
.status
== CAIRO_STATUS_SUCCESS
);
896 assert (mesh
->current_patch
== NULL
);
898 p2u
= mesh
->base
.matrix
;
899 status
= cairo_matrix_invert (&p2u
);
900 assert (status
== CAIRO_STATUS_SUCCESS
);
902 n
= _cairo_array_num_elements (&mesh
->patches
);
903 patch
= _cairo_array_index_const (&mesh
->patches
, 0);
904 for (i
= 0; i
< n
; i
++) {
905 for (j
= 0; j
< 4; j
++) {
906 for (k
= 0; k
< 4; k
++) {
907 nodes
[j
][k
] = patch
->points
[j
][k
];
908 cairo_matrix_transform_point (&p2u
, &nodes
[j
][k
].x
, &nodes
[j
][k
].y
);
909 nodes
[j
][k
].x
+= x_offset
;
910 nodes
[j
][k
].y
+= y_offset
;
914 c
= &patch
->colors
[0];
915 colors
[0][0] = c
->red
;
916 colors
[0][1] = c
->green
;
917 colors
[0][2] = c
->blue
;
918 colors
[0][3] = c
->alpha
;
920 c
= &patch
->colors
[3];
921 colors
[1][0] = c
->red
;
922 colors
[1][1] = c
->green
;
923 colors
[1][2] = c
->blue
;
924 colors
[1][3] = c
->alpha
;
926 c
= &patch
->colors
[1];
927 colors
[2][0] = c
->red
;
928 colors
[2][1] = c
->green
;
929 colors
[2][2] = c
->blue
;
930 colors
[2][3] = c
->alpha
;
932 c
= &patch
->colors
[2];
933 colors
[3][0] = c
->red
;
934 colors
[3][1] = c
->green
;
935 colors
[3][2] = c
->blue
;
936 colors
[3][3] = c
->alpha
;
938 draw_bezier_patch (data
, width
, height
, stride
, nodes
, colors
);