1 #include "mupdf/fitz.h"
2
3 #include <string.h>
4 #include <math.h>
5
6 typedef struct
7 {
8 fz_shade *shade;
9 fz_shade_prepare_fn *prepare;
10 fz_shade_process_fn *process;
11 void *process_arg;
12 int ncomp;
13 } fz_mesh_processor;
14
15 #define SWAP(a,b) {fz_vertex *t = (a); (a) = (b); (b) = t;}
16
17 static inline void
paint_tri(fz_context * ctx,fz_mesh_processor * painter,fz_vertex * v0,fz_vertex * v1,fz_vertex * v2)18 paint_tri(fz_context *ctx, fz_mesh_processor *painter, fz_vertex *v0, fz_vertex *v1, fz_vertex *v2)
19 {
20 if (painter->process)
21 {
22 painter->process(ctx, painter->process_arg, v0, v1, v2);
23 }
24 }
25
26 static inline void
paint_quad(fz_context * ctx,fz_mesh_processor * painter,fz_vertex * v0,fz_vertex * v1,fz_vertex * v2,fz_vertex * v3)27 paint_quad(fz_context *ctx, fz_mesh_processor *painter, fz_vertex *v0, fz_vertex *v1, fz_vertex *v2, fz_vertex *v3)
28 {
29 /* For a quad with corners (in clockwise or anticlockwise order) are
30 * v0, v1, v2, v3. We can choose to split in in various different ways.
31 * Arbitrarily we can pick v0, v1, v3 for the first triangle. We then
32 * have to choose between v1, v2, v3 or v3, v2, v1 (or their equivalent
33 * rotations) for the second triangle.
34 *
35 * v1, v2, v3 has the property that both triangles share the same
36 * winding (useful if we were ever doing simple back face culling).
37 *
38 * v3, v2, v1 has the property that all the 'shared' edges (both
39 * within this quad, and with adjacent quads) are walked in the same
40 * direction every time. This can be useful in that depending on the
41 * implementation/rounding etc walking from A -> B can hit different
42 * pixels than walking from B->A.
43 *
44 * In the event neither of these things matter at the moment, as all
45 * the process functions where it matters order the edges from top to
46 * bottom before walking them.
47 */
48 if (painter->process)
49 {
50 painter->process(ctx, painter->process_arg, v0, v1, v3);
51 painter->process(ctx, painter->process_arg, v3, v2, v1);
52 }
53 }
54
55 static inline void
fz_prepare_color(fz_context * ctx,fz_mesh_processor * painter,fz_vertex * v,float * c)56 fz_prepare_color(fz_context *ctx, fz_mesh_processor *painter, fz_vertex *v, float *c)
57 {
58 if (painter->prepare)
59 {
60 painter->prepare(ctx, painter->process_arg, v, c);
61 }
62 }
63
64 static inline void
fz_prepare_vertex(fz_context * ctx,fz_mesh_processor * painter,fz_vertex * v,fz_matrix ctm,float x,float y,float * c)65 fz_prepare_vertex(fz_context *ctx, fz_mesh_processor *painter, fz_vertex *v, fz_matrix ctm, float x, float y, float *c)
66 {
67 v->p = fz_transform_point_xy(x, y, ctm);
68 if (painter->prepare)
69 {
70 painter->prepare(ctx, painter->process_arg, v, c);
71 }
72 }
73
74 static void
fz_process_shade_type1(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter)75 fz_process_shade_type1(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter)
76 {
77 float *p = shade->u.f.fn_vals;
78 int xdivs = shade->u.f.xdivs;
79 int ydivs = shade->u.f.ydivs;
80 float x0 = shade->u.f.domain[0][0];
81 float y0 = shade->u.f.domain[0][1];
82 float x1 = shade->u.f.domain[1][0];
83 float y1 = shade->u.f.domain[1][1];
84 int xx, yy;
85 float y, yn, x;
86 fz_vertex vs[2][2];
87 fz_vertex *v = vs[0];
88 fz_vertex *vn = vs[1];
89 int n = fz_colorspace_n(ctx, shade->colorspace);
90
91 ctm = fz_concat(shade->u.f.matrix, ctm);
92
93 y = y0;
94 for (yy = 0; yy < ydivs; yy++)
95 {
96 yn = y0 + (y1 - y0) * (yy + 1) / ydivs;
97
98 x = x0;
99
100 fz_prepare_vertex(ctx, painter, &v[0], ctm, x, y, p);
101 p += n;
102 fz_prepare_vertex(ctx, painter, &v[1], ctm, x, yn, p + xdivs * n);
103
104 for (xx = 0; xx < xdivs; xx++)
105 {
106 x = x0 + (x1 - x0) * (xx + 1) / xdivs;
107
108 fz_prepare_vertex(ctx, painter, &vn[0], ctm, x, y, p);
109 p += n;
110 fz_prepare_vertex(ctx, painter, &vn[1], ctm, x, yn, p + xdivs * n);
111
112 paint_quad(ctx, painter, &v[0], &vn[0], &vn[1], &v[1]);
113 SWAP(v,vn);
114 }
115 y = yn;
116 }
117 }
118
119 #define HUGENUM 32000 /* how far to extend linear/radial shadings */
120
121 static fz_point
fz_point_on_circle(fz_point p,float r,float theta)122 fz_point_on_circle(fz_point p, float r, float theta)
123 {
124 p.x = p.x + cosf(theta) * r;
125 p.y = p.y + sinf(theta) * r;
126 return p;
127 }
128
129 static void
fz_process_shade_type2(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter,fz_rect scissor)130 fz_process_shade_type2(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter, fz_rect scissor)
131 {
132 fz_point p0, p1, dir;
133 fz_vertex v0, v1, v2, v3;
134 fz_vertex e0, e1;
135 float theta;
136 float zero = 0;
137 float one = 1;
138 float r;
139
140 p0.x = shade->u.l_or_r.coords[0][0];
141 p0.y = shade->u.l_or_r.coords[0][1];
142 p1.x = shade->u.l_or_r.coords[1][0];
143 p1.y = shade->u.l_or_r.coords[1][1];
144 dir.x = p0.y - p1.y;
145 dir.y = p1.x - p0.x;
146 p0 = fz_transform_point(p0, ctm);
147 p1 = fz_transform_point(p1, ctm);
148 dir = fz_transform_vector(dir, ctm);
149 theta = atan2f(dir.y, dir.x);
150
151 if (fz_is_infinite_rect(scissor)) {
152 r = HUGENUM; /* Not ideal, but it'll do for now */
153 } else {
154 float x = p0.x - scissor.x0;
155 float y = p0.y - scissor.y0;
156 if (x < scissor.x1 - p0.x)
157 x = scissor.x1 - p0.x;
158 if (x < p0.x - scissor.x1)
159 x = p0.x - scissor.x1;
160 if (x < scissor.x1 - p1.x)
161 x = scissor.x1 - p1.x;
162 if (y < scissor.y1 - p0.y)
163 y = scissor.y1 - p0.y;
164 if (y < p0.y - scissor.y1)
165 y = p0.y - scissor.y1;
166 if (y < scissor.y1 - p1.y)
167 y = scissor.y1 - p1.y;
168 r = x+y;
169 }
170 v0.p = fz_point_on_circle(p0, r, theta);
171 v1.p = fz_point_on_circle(p1, r, theta);
172 v2.p.x = 2*p0.x - v0.p.x;
173 v2.p.y = 2*p0.y - v0.p.y;
174 v3.p.x = 2*p1.x - v1.p.x;
175 v3.p.y = 2*p1.y - v1.p.y;
176
177 fz_prepare_color(ctx, painter, &v0, &zero);
178 fz_prepare_color(ctx, painter, &v1, &one);
179 fz_prepare_color(ctx, painter, &v2, &zero);
180 fz_prepare_color(ctx, painter, &v3, &one);
181
182 paint_quad(ctx, painter, &v0, &v2, &v3, &v1);
183
184 if (shade->u.l_or_r.extend[0] || shade->u.l_or_r.extend[1]) {
185 float d = fabsf(p1.x - p0.x);
186 float e = fabsf(p1.y - p0.y);
187 if (d < e)
188 d = e;
189 if (d != 0)
190 r /= d;
191 }
192 if (shade->u.l_or_r.extend[0])
193 {
194 e0.p.x = v0.p.x - (p1.x - p0.x) * r;
195 e0.p.y = v0.p.y - (p1.y - p0.y) * r;
196 fz_prepare_color(ctx, painter, &e0, &zero);
197
198 e1.p.x = v2.p.x - (p1.x - p0.x) * r;
199 e1.p.y = v2.p.y - (p1.y - p0.y) * r;
200 fz_prepare_color(ctx, painter, &e1, &zero);
201
202 paint_quad(ctx, painter, &e0, &v0, &v2, &e1);
203 }
204
205 if (shade->u.l_or_r.extend[1])
206 {
207 e0.p.x = v1.p.x + (p1.x - p0.x) * r;
208 e0.p.y = v1.p.y + (p1.y - p0.y) * r;
209 fz_prepare_color(ctx, painter, &e0, &one);
210
211 e1.p.x = v3.p.x + (p1.x - p0.x) * r;
212 e1.p.y = v3.p.y + (p1.y - p0.y) * r;
213 fz_prepare_color(ctx, painter, &e1, &one);
214
215 paint_quad(ctx, painter, &e0, &v1, &v3, &e1);
216 }
217 }
218
219 static void
fz_paint_annulus(fz_context * ctx,fz_matrix ctm,fz_point p0,float r0,float c0,fz_point p1,float r1,float c1,int count,fz_mesh_processor * painter)220 fz_paint_annulus(fz_context *ctx, fz_matrix ctm,
221 fz_point p0, float r0, float c0,
222 fz_point p1, float r1, float c1,
223 int count,
224 fz_mesh_processor *painter)
225 {
226 fz_vertex t0, t1, t2, t3, b0, b1, b2, b3;
227 float theta, step, a, b;
228 int i;
229
230 theta = atan2f(p1.y - p0.y, p1.x - p0.x);
231 step = FZ_PI / count;
232
233 a = 0;
234 for (i = 1; i <= count; i++)
235 {
236 b = i * step;
237
238 t0.p = fz_transform_point(fz_point_on_circle(p0, r0, theta + a), ctm);
239 t1.p = fz_transform_point(fz_point_on_circle(p0, r0, theta + b), ctm);
240 t2.p = fz_transform_point(fz_point_on_circle(p1, r1, theta + a), ctm);
241 t3.p = fz_transform_point(fz_point_on_circle(p1, r1, theta + b), ctm);
242 b0.p = fz_transform_point(fz_point_on_circle(p0, r0, theta - a), ctm);
243 b1.p = fz_transform_point(fz_point_on_circle(p0, r0, theta - b), ctm);
244 b2.p = fz_transform_point(fz_point_on_circle(p1, r1, theta - a), ctm);
245 b3.p = fz_transform_point(fz_point_on_circle(p1, r1, theta - b), ctm);
246
247 fz_prepare_color(ctx, painter, &t0, &c0);
248 fz_prepare_color(ctx, painter, &t1, &c0);
249 fz_prepare_color(ctx, painter, &t2, &c1);
250 fz_prepare_color(ctx, painter, &t3, &c1);
251 fz_prepare_color(ctx, painter, &b0, &c0);
252 fz_prepare_color(ctx, painter, &b1, &c0);
253 fz_prepare_color(ctx, painter, &b2, &c1);
254 fz_prepare_color(ctx, painter, &b3, &c1);
255
256 paint_quad(ctx, painter, &t0, &t2, &t3, &t1);
257 paint_quad(ctx, painter, &b0, &b2, &b3, &b1);
258
259 a = b;
260 }
261 }
262
263 static void
fz_process_shade_type3(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter)264 fz_process_shade_type3(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter)
265 {
266 fz_point p0, p1;
267 float r0, r1;
268 fz_point e;
269 float er, rs;
270 int count;
271
272 p0.x = shade->u.l_or_r.coords[0][0];
273 p0.y = shade->u.l_or_r.coords[0][1];
274 r0 = shade->u.l_or_r.coords[0][2];
275
276 p1.x = shade->u.l_or_r.coords[1][0];
277 p1.y = shade->u.l_or_r.coords[1][1];
278 r1 = shade->u.l_or_r.coords[1][2];
279
280 /* number of segments for a half-circle */
281 count = 4 * sqrtf(fz_matrix_expansion(ctm) * fz_max(r0, r1));
282 if (count < 3)
283 count = 3;
284 if (count > 1024)
285 count = 1024;
286
287 if (shade->u.l_or_r.extend[0])
288 {
289 if (r0 < r1)
290 rs = r0 / (r0 - r1);
291 else
292 rs = -HUGENUM;
293
294 e.x = p0.x + (p1.x - p0.x) * rs;
295 e.y = p0.y + (p1.y - p0.y) * rs;
296 er = r0 + (r1 - r0) * rs;
297
298 fz_paint_annulus(ctx, ctm, e, er, 0, p0, r0, 0, count, painter);
299 }
300
301 fz_paint_annulus(ctx, ctm, p0, r0, 0, p1, r1, 1, count, painter);
302
303 if (shade->u.l_or_r.extend[1])
304 {
305 if (r0 > r1)
306 rs = r1 / (r1 - r0);
307 else
308 rs = -HUGENUM;
309
310 e.x = p1.x + (p0.x - p1.x) * rs;
311 e.y = p1.y + (p0.y - p1.y) * rs;
312 er = r1 + (r0 - r1) * rs;
313
314 fz_paint_annulus(ctx, ctm, p1, r1, 1, e, er, 1, count, painter);
315 }
316 }
317
read_sample(fz_context * ctx,fz_stream * stream,int bits,float min,float max)318 static inline float read_sample(fz_context *ctx, fz_stream *stream, int bits, float min, float max)
319 {
320 /* we use pow(2,x) because (1<<x) would overflow the math on 32-bit samples */
321 float bitscale = 1 / (powf(2, bits) - 1);
322 return min + fz_read_bits(ctx, stream, bits) * (max - min) * bitscale;
323 }
324
325 static void
fz_process_shade_type4(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter)326 fz_process_shade_type4(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter)
327 {
328 fz_stream *stream = fz_open_compressed_buffer(ctx, shade->buffer);
329 fz_vertex v[4];
330 fz_vertex *va = &v[0];
331 fz_vertex *vb = &v[1];
332 fz_vertex *vc = &v[2];
333 fz_vertex *vd = &v[3];
334 int flag, i, ncomp = painter->ncomp;
335 int bpflag = shade->u.m.bpflag;
336 int bpcoord = shade->u.m.bpcoord;
337 int bpcomp = shade->u.m.bpcomp;
338 float x0 = shade->u.m.x0;
339 float x1 = shade->u.m.x1;
340 float y0 = shade->u.m.y0;
341 float y1 = shade->u.m.y1;
342 const float *c0 = shade->u.m.c0;
343 const float *c1 = shade->u.m.c1;
344 float x, y, c[FZ_MAX_COLORS];
345 int first_triangle = 1;
346
347 fz_try(ctx)
348 {
349 while (!fz_is_eof_bits(ctx, stream))
350 {
351 flag = fz_read_bits(ctx, stream, bpflag);
352 x = read_sample(ctx, stream, bpcoord, x0, x1);
353 y = read_sample(ctx, stream, bpcoord, y0, y1);
354 for (i = 0; i < ncomp; i++)
355 c[i] = read_sample(ctx, stream, bpcomp, c0[i], c1[i]);
356 fz_prepare_vertex(ctx, painter, vd, ctm, x, y, c);
357
358 if (first_triangle)
359 {
360 if (flag != 0)
361 {
362 fz_warn(ctx, "ignoring non-zero edge flags for first vertex in mesh");
363 flag = 0;
364 }
365 first_triangle = 0;
366 }
367
368 switch (flag)
369 {
370 default:
371 fz_warn(ctx, "ignoring out of range edge flag in mesh");
372 /* fallthrough */
373
374 case 0: /* start new triangle */
375 SWAP(va, vd);
376
377 fz_read_bits(ctx, stream, bpflag);
378 x = read_sample(ctx, stream, bpcoord, x0, x1);
379 y = read_sample(ctx, stream, bpcoord, y0, y1);
380 for (i = 0; i < ncomp; i++)
381 c[i] = read_sample(ctx, stream, bpcomp, c0[i], c1[i]);
382 fz_prepare_vertex(ctx, painter, vb, ctm, x, y, c);
383
384 fz_read_bits(ctx, stream, bpflag);
385 x = read_sample(ctx, stream, bpcoord, x0, x1);
386 y = read_sample(ctx, stream, bpcoord, y0, y1);
387 for (i = 0; i < ncomp; i++)
388 c[i] = read_sample(ctx, stream, bpcomp, c0[i], c1[i]);
389 fz_prepare_vertex(ctx, painter, vc, ctm, x, y, c);
390
391 paint_tri(ctx, painter, va, vb, vc);
392 break;
393
394 case 1: /* Vb, Vc, Vd */
395 SWAP(va, vb);
396 SWAP(vb, vc);
397 SWAP(vc, vd);
398 paint_tri(ctx, painter, va, vb, vc);
399 break;
400
401 case 2: /* Va, Vc, Vd */
402 SWAP(vb, vc);
403 SWAP(vc, vd);
404 paint_tri(ctx, painter, va, vb, vc);
405 break;
406 }
407 }
408 }
409 fz_always(ctx)
410 {
411 fz_drop_stream(ctx, stream);
412 }
413 fz_catch(ctx)
414 {
415 fz_rethrow(ctx);
416 }
417 }
418
419 static void
fz_process_shade_type5(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter)420 fz_process_shade_type5(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter)
421 {
422 fz_stream *stream = fz_open_compressed_buffer(ctx, shade->buffer);
423 fz_vertex *buf = NULL;
424 fz_vertex *ref = NULL;
425 int first;
426 int ncomp = painter->ncomp;
427 int i, k;
428 int vprow = shade->u.m.vprow;
429 int bpcoord = shade->u.m.bpcoord;
430 int bpcomp = shade->u.m.bpcomp;
431 float x0 = shade->u.m.x0;
432 float x1 = shade->u.m.x1;
433 float y0 = shade->u.m.y0;
434 float y1 = shade->u.m.y1;
435 const float *c0 = shade->u.m.c0;
436 const float *c1 = shade->u.m.c1;
437 float x, y, c[FZ_MAX_COLORS];
438
439 fz_var(buf);
440 fz_var(ref);
441
442 fz_try(ctx)
443 {
444 ref = fz_malloc_array(ctx, vprow, fz_vertex);
445 buf = fz_malloc_array(ctx, vprow, fz_vertex);
446 first = 1;
447
448 while (!fz_is_eof_bits(ctx, stream))
449 {
450 for (i = 0; i < vprow; i++)
451 {
452 x = read_sample(ctx, stream, bpcoord, x0, x1);
453 y = read_sample(ctx, stream, bpcoord, y0, y1);
454 for (k = 0; k < ncomp; k++)
455 c[k] = read_sample(ctx, stream, bpcomp, c0[k], c1[k]);
456 fz_prepare_vertex(ctx, painter, &buf[i], ctm, x, y, c);
457 }
458
459 if (!first)
460 for (i = 0; i < vprow - 1; i++)
461 paint_quad(ctx, painter, &ref[i], &ref[i+1], &buf[i+1], &buf[i]);
462
463 SWAP(ref,buf);
464 first = 0;
465 }
466 }
467 fz_always(ctx)
468 {
469 fz_free(ctx, ref);
470 fz_free(ctx, buf);
471 fz_drop_stream(ctx, stream);
472 }
473 fz_catch(ctx)
474 {
475 fz_rethrow(ctx);
476 }
477 }
478
479 /* Subdivide and tessellate tensor-patches */
480
481 typedef struct
482 {
483 fz_point pole[4][4];
484 float color[4][FZ_MAX_COLORS];
485 } tensor_patch;
486
487 static void
triangulate_patch(fz_context * ctx,fz_mesh_processor * painter,tensor_patch * p)488 triangulate_patch(fz_context *ctx, fz_mesh_processor *painter, tensor_patch *p)
489 {
490 fz_vertex v0, v1, v2, v3;
491
492 v0.p = p->pole[0][0];
493 v1.p = p->pole[0][3];
494 v2.p = p->pole[3][3];
495 v3.p = p->pole[3][0];
496
497 fz_prepare_color(ctx, painter, &v0, p->color[0]);
498 fz_prepare_color(ctx, painter, &v1, p->color[1]);
499 fz_prepare_color(ctx, painter, &v2, p->color[2]);
500 fz_prepare_color(ctx, painter, &v3, p->color[3]);
501
502 paint_quad(ctx, painter, &v0, &v1, &v2, &v3);
503 }
504
midcolor(float * c,float * c1,float * c2,int n)505 static inline void midcolor(float *c, float *c1, float *c2, int n)
506 {
507 int i;
508 for (i = 0; i < n; i++)
509 c[i] = (c1[i] + c2[i]) * 0.5f;
510 }
511
512 static void
split_curve(fz_point * pole,fz_point * q0,fz_point * q1,int polestep)513 split_curve(fz_point *pole, fz_point *q0, fz_point *q1, int polestep)
514 {
515 /*
516 split bezier curve given by control points pole[0]..pole[3]
517 using de casteljau algo at midpoint and build two new
518 bezier curves q0[0]..q0[3] and q1[0]..q1[3]. all indices
519 should be multiplies by polestep == 1 for vertical bezier
520 curves in patch and == 4 for horizontal bezier curves due
521 to C's multi-dimensional matrix memory layout.
522 */
523
524 float x12 = (pole[1 * polestep].x + pole[2 * polestep].x) * 0.5f;
525 float y12 = (pole[1 * polestep].y + pole[2 * polestep].y) * 0.5f;
526
527 q0[1 * polestep].x = (pole[0 * polestep].x + pole[1 * polestep].x) * 0.5f;
528 q0[1 * polestep].y = (pole[0 * polestep].y + pole[1 * polestep].y) * 0.5f;
529 q1[2 * polestep].x = (pole[2 * polestep].x + pole[3 * polestep].x) * 0.5f;
530 q1[2 * polestep].y = (pole[2 * polestep].y + pole[3 * polestep].y) * 0.5f;
531
532 q0[2 * polestep].x = (q0[1 * polestep].x + x12) * 0.5f;
533 q0[2 * polestep].y = (q0[1 * polestep].y + y12) * 0.5f;
534 q1[1 * polestep].x = (x12 + q1[2 * polestep].x) * 0.5f;
535 q1[1 * polestep].y = (y12 + q1[2 * polestep].y) * 0.5f;
536
537 q0[3 * polestep].x = (q0[2 * polestep].x + q1[1 * polestep].x) * 0.5f;
538 q0[3 * polestep].y = (q0[2 * polestep].y + q1[1 * polestep].y) * 0.5f;
539 q1[0 * polestep].x = (q0[2 * polestep].x + q1[1 * polestep].x) * 0.5f;
540 q1[0 * polestep].y = (q0[2 * polestep].y + q1[1 * polestep].y) * 0.5f;
541
542 q0[0 * polestep].x = pole[0 * polestep].x;
543 q0[0 * polestep].y = pole[0 * polestep].y;
544 q1[3 * polestep].x = pole[3 * polestep].x;
545 q1[3 * polestep].y = pole[3 * polestep].y;
546 }
547
548 static void
split_stripe(tensor_patch * p,tensor_patch * s0,tensor_patch * s1,int n)549 split_stripe(tensor_patch *p, tensor_patch *s0, tensor_patch *s1, int n)
550 {
551 /*
552 split all horizontal bezier curves in patch,
553 creating two new patches with half the width.
554 */
555 split_curve(&p->pole[0][0], &s0->pole[0][0], &s1->pole[0][0], 4);
556 split_curve(&p->pole[0][1], &s0->pole[0][1], &s1->pole[0][1], 4);
557 split_curve(&p->pole[0][2], &s0->pole[0][2], &s1->pole[0][2], 4);
558 split_curve(&p->pole[0][3], &s0->pole[0][3], &s1->pole[0][3], 4);
559
560 /* interpolate the colors for the two new patches. */
561 memcpy(s0->color[0], p->color[0], n * sizeof(s0->color[0][0]));
562 memcpy(s0->color[1], p->color[1], n * sizeof(s0->color[1][0]));
563 midcolor(s0->color[2], p->color[1], p->color[2], n);
564 midcolor(s0->color[3], p->color[0], p->color[3], n);
565
566 memcpy(s1->color[0], s0->color[3], n * sizeof(s1->color[0][0]));
567 memcpy(s1->color[1], s0->color[2], n * sizeof(s1->color[1][0]));
568 memcpy(s1->color[2], p->color[2], n * sizeof(s1->color[2][0]));
569 memcpy(s1->color[3], p->color[3], n * sizeof(s1->color[3][0]));
570 }
571
572 static void
draw_stripe(fz_context * ctx,fz_mesh_processor * painter,tensor_patch * p,int depth)573 draw_stripe(fz_context *ctx, fz_mesh_processor *painter, tensor_patch *p, int depth)
574 {
575 tensor_patch s0, s1;
576
577 /* split patch into two half-height patches */
578 split_stripe(p, &s0, &s1, painter->ncomp);
579
580 depth--;
581 if (depth == 0)
582 {
583 /* if no more subdividing, draw two new patches... */
584 triangulate_patch(ctx, painter, &s1);
585 triangulate_patch(ctx, painter, &s0);
586 }
587 else
588 {
589 /* ...otherwise, continue subdividing. */
590 draw_stripe(ctx, painter, &s1, depth);
591 draw_stripe(ctx, painter, &s0, depth);
592 }
593 }
594
595 static void
split_patch(tensor_patch * p,tensor_patch * s0,tensor_patch * s1,int n)596 split_patch(tensor_patch *p, tensor_patch *s0, tensor_patch *s1, int n)
597 {
598 /*
599 split all vertical bezier curves in patch,
600 creating two new patches with half the height.
601 */
602 split_curve(p->pole[0], s0->pole[0], s1->pole[0], 1);
603 split_curve(p->pole[1], s0->pole[1], s1->pole[1], 1);
604 split_curve(p->pole[2], s0->pole[2], s1->pole[2], 1);
605 split_curve(p->pole[3], s0->pole[3], s1->pole[3], 1);
606
607 /* interpolate the colors for the two new patches. */
608 memcpy(s0->color[0], p->color[0], n * sizeof(s0->color[0][0]));
609 midcolor(s0->color[1], p->color[0], p->color[1], n);
610 midcolor(s0->color[2], p->color[2], p->color[3], n);
611 memcpy(s0->color[3], p->color[3], n * sizeof(s0->color[3][0]));
612
613 memcpy(s1->color[0], s0->color[1], n * sizeof(s1->color[0][0]));
614 memcpy(s1->color[1], p->color[1], n * sizeof(s1->color[1][0]));
615 memcpy(s1->color[2], p->color[2], n * sizeof(s1->color[2][0]));
616 memcpy(s1->color[3], s0->color[2], n * sizeof(s1->color[3][0]));
617 }
618
619 static void
draw_patch(fz_context * ctx,fz_mesh_processor * painter,tensor_patch * p,int depth,int origdepth)620 draw_patch(fz_context *ctx, fz_mesh_processor *painter, tensor_patch *p, int depth, int origdepth)
621 {
622 tensor_patch s0, s1;
623
624 /* split patch into two half-width patches */
625 split_patch(p, &s0, &s1, painter->ncomp);
626
627 depth--;
628 if (depth == 0)
629 {
630 /* if no more subdividing, draw two new patches... */
631 draw_stripe(ctx, painter, &s0, origdepth);
632 draw_stripe(ctx, painter, &s1, origdepth);
633 }
634 else
635 {
636 /* ...otherwise, continue subdividing. */
637 draw_patch(ctx, painter, &s0, depth, origdepth);
638 draw_patch(ctx, painter, &s1, depth, origdepth);
639 }
640 }
641
642 static fz_point
compute_tensor_interior(fz_point a,fz_point b,fz_point c,fz_point d,fz_point e,fz_point f,fz_point g,fz_point h)643 compute_tensor_interior(
644 fz_point a, fz_point b, fz_point c, fz_point d,
645 fz_point e, fz_point f, fz_point g, fz_point h)
646 {
647 fz_point pt;
648
649 /* see equations at page 330 in pdf 1.7 */
650
651 pt.x = -4 * a.x;
652 pt.x += 6 * (b.x + c.x);
653 pt.x += -2 * (d.x + e.x);
654 pt.x += 3 * (f.x + g.x);
655 pt.x += -1 * h.x;
656 pt.x /= 9;
657
658 pt.y = -4 * a.y;
659 pt.y += 6 * (b.y + c.y);
660 pt.y += -2 * (d.y + e.y);
661 pt.y += 3 * (f.y + g.y);
662 pt.y += -1 * h.y;
663 pt.y /= 9;
664
665 return pt;
666 }
667
668 static void
make_tensor_patch(tensor_patch * p,int type,fz_point * pt)669 make_tensor_patch(tensor_patch *p, int type, fz_point *pt)
670 {
671 if (type == 6)
672 {
673 /* see control point stream order at page 325 in pdf 1.7 */
674
675 p->pole[0][0] = pt[0];
676 p->pole[0][1] = pt[1];
677 p->pole[0][2] = pt[2];
678 p->pole[0][3] = pt[3];
679 p->pole[1][3] = pt[4];
680 p->pole[2][3] = pt[5];
681 p->pole[3][3] = pt[6];
682 p->pole[3][2] = pt[7];
683 p->pole[3][1] = pt[8];
684 p->pole[3][0] = pt[9];
685 p->pole[2][0] = pt[10];
686 p->pole[1][0] = pt[11];
687
688 /* see equations at page 330 in pdf 1.7 */
689
690 p->pole[1][1] = compute_tensor_interior(
691 p->pole[0][0], p->pole[0][1], p->pole[1][0], p->pole[0][3],
692 p->pole[3][0], p->pole[3][1], p->pole[1][3], p->pole[3][3]);
693
694 p->pole[1][2] = compute_tensor_interior(
695 p->pole[0][3], p->pole[0][2], p->pole[1][3], p->pole[0][0],
696 p->pole[3][3], p->pole[3][2], p->pole[1][0], p->pole[3][0]);
697
698 p->pole[2][1] = compute_tensor_interior(
699 p->pole[3][0], p->pole[3][1], p->pole[2][0], p->pole[3][3],
700 p->pole[0][0], p->pole[0][1], p->pole[2][3], p->pole[0][3]);
701
702 p->pole[2][2] = compute_tensor_interior(
703 p->pole[3][3], p->pole[3][2], p->pole[2][3], p->pole[3][0],
704 p->pole[0][3], p->pole[0][2], p->pole[2][0], p->pole[0][0]);
705 }
706 else if (type == 7)
707 {
708 /* see control point stream order at page 330 in pdf 1.7 */
709
710 p->pole[0][0] = pt[0];
711 p->pole[0][1] = pt[1];
712 p->pole[0][2] = pt[2];
713 p->pole[0][3] = pt[3];
714 p->pole[1][3] = pt[4];
715 p->pole[2][3] = pt[5];
716 p->pole[3][3] = pt[6];
717 p->pole[3][2] = pt[7];
718 p->pole[3][1] = pt[8];
719 p->pole[3][0] = pt[9];
720 p->pole[2][0] = pt[10];
721 p->pole[1][0] = pt[11];
722 p->pole[1][1] = pt[12];
723 p->pole[1][2] = pt[13];
724 p->pole[2][2] = pt[14];
725 p->pole[2][1] = pt[15];
726 }
727 }
728
729 /* FIXME: Nasty */
730 #define SUBDIV 3 /* how many levels to subdivide patches */
731
732 static void
fz_process_shade_type6(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter)733 fz_process_shade_type6(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter)
734 {
735 fz_stream *stream = fz_open_compressed_buffer(ctx, shade->buffer);
736 float color_storage[2][4][FZ_MAX_COLORS];
737 fz_point point_storage[2][12];
738 int store = 0;
739 int ncomp = painter->ncomp;
740 int i, k;
741 int bpflag = shade->u.m.bpflag;
742 int bpcoord = shade->u.m.bpcoord;
743 int bpcomp = shade->u.m.bpcomp;
744 float x0 = shade->u.m.x0;
745 float x1 = shade->u.m.x1;
746 float y0 = shade->u.m.y0;
747 float y1 = shade->u.m.y1;
748 const float *c0 = shade->u.m.c0;
749 const float *c1 = shade->u.m.c1;
750
751 fz_try(ctx)
752 {
753 float (*prevc)[FZ_MAX_COLORS] = NULL;
754 fz_point *prevp = NULL;
755 while (!fz_is_eof_bits(ctx, stream))
756 {
757 float (*c)[FZ_MAX_COLORS] = color_storage[store];
758 fz_point *v = point_storage[store];
759 int startcolor;
760 int startpt;
761 int flag;
762 tensor_patch patch;
763
764 flag = fz_read_bits(ctx, stream, bpflag);
765
766 if (flag == 0)
767 {
768 startpt = 0;
769 startcolor = 0;
770 }
771 else
772 {
773 startpt = 4;
774 startcolor = 2;
775 }
776
777 for (i = startpt; i < 12; i++)
778 {
779 v[i].x = read_sample(ctx, stream, bpcoord, x0, x1);
780 v[i].y = read_sample(ctx, stream, bpcoord, y0, y1);
781 v[i] = fz_transform_point(v[i], ctm);
782 }
783
784 for (i = startcolor; i < 4; i++)
785 {
786 for (k = 0; k < ncomp; k++)
787 c[i][k] = read_sample(ctx, stream, bpcomp, c0[k], c1[k]);
788 }
789
790 if (flag == 0)
791 {
792 /* No patch data to copy forwards */
793 }
794 else if (flag == 1 && prevc)
795 {
796 v[0] = prevp[3];
797 v[1] = prevp[4];
798 v[2] = prevp[5];
799 v[3] = prevp[6];
800 memcpy(c[0], prevc[1], ncomp * sizeof(float));
801 memcpy(c[1], prevc[2], ncomp * sizeof(float));
802 }
803 else if (flag == 2 && prevc)
804 {
805 v[0] = prevp[6];
806 v[1] = prevp[7];
807 v[2] = prevp[8];
808 v[3] = prevp[9];
809 memcpy(c[0], prevc[2], ncomp * sizeof(float));
810 memcpy(c[1], prevc[3], ncomp * sizeof(float));
811 }
812 else if (flag == 3 && prevc)
813 {
814 v[0] = prevp[ 9];
815 v[1] = prevp[10];
816 v[2] = prevp[11];
817 v[3] = prevp[ 0];
818 memcpy(c[0], prevc[3], ncomp * sizeof(float));
819 memcpy(c[1], prevc[0], ncomp * sizeof(float));
820 }
821 else
822 continue;
823
824 make_tensor_patch(&patch, 6, v);
825
826 for (i = 0; i < 4; i++)
827 memcpy(patch.color[i], c[i], ncomp * sizeof(float));
828
829 draw_patch(ctx, painter, &patch, SUBDIV, SUBDIV);
830
831 prevp = v;
832 prevc = c;
833 store ^= 1;
834 }
835 }
836 fz_always(ctx)
837 {
838 fz_drop_stream(ctx, stream);
839 }
840 fz_catch(ctx)
841 {
842 fz_rethrow(ctx);
843 }
844 }
845
846 static void
fz_process_shade_type7(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_mesh_processor * painter)847 fz_process_shade_type7(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_mesh_processor *painter)
848 {
849 fz_stream *stream = fz_open_compressed_buffer(ctx, shade->buffer);
850 int bpflag = shade->u.m.bpflag;
851 int bpcoord = shade->u.m.bpcoord;
852 int bpcomp = shade->u.m.bpcomp;
853 float x0 = shade->u.m.x0;
854 float x1 = shade->u.m.x1;
855 float y0 = shade->u.m.y0;
856 float y1 = shade->u.m.y1;
857 const float *c0 = shade->u.m.c0;
858 const float *c1 = shade->u.m.c1;
859 float color_storage[2][4][FZ_MAX_COLORS];
860 fz_point point_storage[2][16];
861 int store = 0;
862 int ncomp = painter->ncomp;
863 int i, k;
864 float (*prevc)[FZ_MAX_COLORS] = NULL;
865 fz_point (*prevp) = NULL;
866
867 fz_try(ctx)
868 {
869 while (!fz_is_eof_bits(ctx, stream))
870 {
871 float (*c)[FZ_MAX_COLORS] = color_storage[store];
872 fz_point *v = point_storage[store];
873 int startcolor;
874 int startpt;
875 int flag;
876 tensor_patch patch;
877
878 flag = fz_read_bits(ctx, stream, bpflag);
879
880 if (flag == 0)
881 {
882 startpt = 0;
883 startcolor = 0;
884 }
885 else
886 {
887 startpt = 4;
888 startcolor = 2;
889 }
890
891 for (i = startpt; i < 16; i++)
892 {
893 v[i].x = read_sample(ctx, stream, bpcoord, x0, x1);
894 v[i].y = read_sample(ctx, stream, bpcoord, y0, y1);
895 v[i] = fz_transform_point(v[i], ctm);
896 }
897
898 for (i = startcolor; i < 4; i++)
899 {
900 for (k = 0; k < ncomp; k++)
901 c[i][k] = read_sample(ctx, stream, bpcomp, c0[k], c1[k]);
902 }
903
904 if (flag == 0)
905 {
906 /* No patch data to copy forward */
907 }
908 else if (flag == 1 && prevc)
909 {
910 v[0] = prevp[3];
911 v[1] = prevp[4];
912 v[2] = prevp[5];
913 v[3] = prevp[6];
914 memcpy(c[0], prevc[1], ncomp * sizeof(float));
915 memcpy(c[1], prevc[2], ncomp * sizeof(float));
916 }
917 else if (flag == 2 && prevc)
918 {
919 v[0] = prevp[6];
920 v[1] = prevp[7];
921 v[2] = prevp[8];
922 v[3] = prevp[9];
923 memcpy(c[0], prevc[2], ncomp * sizeof(float));
924 memcpy(c[1], prevc[3], ncomp * sizeof(float));
925 }
926 else if (flag == 3 && prevc)
927 {
928 v[0] = prevp[ 9];
929 v[1] = prevp[10];
930 v[2] = prevp[11];
931 v[3] = prevp[ 0];
932 memcpy(c[0], prevc[3], ncomp * sizeof(float));
933 memcpy(c[1], prevc[0], ncomp * sizeof(float));
934 }
935 else
936 continue; /* We have no patch! */
937
938 make_tensor_patch(&patch, 7, v);
939
940 for (i = 0; i < 4; i++)
941 memcpy(patch.color[i], c[i], ncomp * sizeof(float));
942
943 draw_patch(ctx, painter, &patch, SUBDIV, SUBDIV);
944
945 prevp = v;
946 prevc = c;
947 store ^= 1;
948 }
949 }
950 fz_always(ctx)
951 {
952 fz_drop_stream(ctx, stream);
953 }
954 fz_catch(ctx)
955 {
956 fz_rethrow(ctx);
957 }
958 }
959
960 void
fz_process_shade(fz_context * ctx,fz_shade * shade,fz_matrix ctm,fz_rect scissor,fz_shade_prepare_fn * prepare,fz_shade_process_fn * process,void * process_arg)961 fz_process_shade(fz_context *ctx, fz_shade *shade, fz_matrix ctm, fz_rect scissor,
962 fz_shade_prepare_fn *prepare, fz_shade_process_fn *process, void *process_arg)
963 {
964 fz_mesh_processor painter;
965
966 painter.shade = shade;
967 painter.prepare = prepare;
968 painter.process = process;
969 painter.process_arg = process_arg;
970 painter.ncomp = (shade->use_function > 0 ? 1 : fz_colorspace_n(ctx, shade->colorspace));
971
972 if (shade->type == FZ_FUNCTION_BASED)
973 fz_process_shade_type1(ctx, shade, ctm, &painter);
974 else if (shade->type == FZ_LINEAR)
975 fz_process_shade_type2(ctx, shade, ctm, &painter, scissor);
976 else if (shade->type == FZ_RADIAL)
977 fz_process_shade_type3(ctx, shade, ctm, &painter);
978 else if (shade->type == FZ_MESH_TYPE4)
979 fz_process_shade_type4(ctx, shade, ctm, &painter);
980 else if (shade->type == FZ_MESH_TYPE5)
981 fz_process_shade_type5(ctx, shade, ctm, &painter);
982 else if (shade->type == FZ_MESH_TYPE6)
983 fz_process_shade_type6(ctx, shade, ctm, &painter);
984 else if (shade->type == FZ_MESH_TYPE7)
985 fz_process_shade_type7(ctx, shade, ctm, &painter);
986 else
987 fz_throw(ctx, FZ_ERROR_GENERIC, "Unexpected mesh type %d\n", shade->type);
988 }
989
990 static fz_rect
fz_bound_mesh_type1(fz_context * ctx,fz_shade * shade)991 fz_bound_mesh_type1(fz_context *ctx, fz_shade *shade)
992 {
993 fz_rect bbox;
994 bbox.x0 = shade->u.f.domain[0][0];
995 bbox.y0 = shade->u.f.domain[0][1];
996 bbox.x1 = shade->u.f.domain[1][0];
997 bbox.y1 = shade->u.f.domain[1][1];
998 return fz_transform_rect(bbox, shade->u.f.matrix);
999 }
1000
1001 static fz_rect
fz_bound_mesh_type2(fz_context * ctx,fz_shade * shade)1002 fz_bound_mesh_type2(fz_context *ctx, fz_shade *shade)
1003 {
1004 /* FIXME: If axis aligned and not extended, the bbox may only be
1005 * infinite in one direction */
1006 return fz_infinite_rect;
1007 }
1008
1009 static fz_rect
fz_bound_mesh_type3(fz_context * ctx,fz_shade * shade)1010 fz_bound_mesh_type3(fz_context *ctx, fz_shade *shade)
1011 {
1012 fz_rect bbox;
1013 fz_point p0, p1;
1014 float r0, r1;
1015
1016 r0 = shade->u.l_or_r.coords[0][2];
1017 r1 = shade->u.l_or_r.coords[1][2];
1018
1019 if (shade->u.l_or_r.extend[0])
1020 {
1021 if (r0 >= r1)
1022 return fz_infinite_rect;
1023 }
1024
1025 if (shade->u.l_or_r.extend[1])
1026 {
1027 if (r0 <= r1)
1028 return fz_infinite_rect;
1029 }
1030
1031 p0.x = shade->u.l_or_r.coords[0][0];
1032 p0.y = shade->u.l_or_r.coords[0][1];
1033 p1.x = shade->u.l_or_r.coords[1][0];
1034 p1.y = shade->u.l_or_r.coords[1][1];
1035
1036 bbox.x0 = p0.x - r0; bbox.y0 = p0.y - r0;
1037 bbox.x1 = p0.x + r0; bbox.y1 = p0.x + r0;
1038 if (bbox.x0 > p1.x - r1)
1039 bbox.x0 = p1.x - r1;
1040 if (bbox.x1 < p1.x + r1)
1041 bbox.x1 = p1.x + r1;
1042 if (bbox.y0 > p1.y - r1)
1043 bbox.y0 = p1.y - r1;
1044 if (bbox.y1 < p1.y + r1)
1045 bbox.y1 = p1.y + r1;
1046 return bbox;
1047 }
1048
1049 static fz_rect
fz_bound_mesh_type4567(fz_context * ctx,fz_shade * shade)1050 fz_bound_mesh_type4567(fz_context *ctx, fz_shade *shade)
1051 {
1052 fz_rect bbox;
1053 bbox.x0 = shade->u.m.x0;
1054 bbox.y0 = shade->u.m.y0;
1055 bbox.x1 = shade->u.m.x1;
1056 bbox.y1 = shade->u.m.y1;
1057 return bbox;
1058 }
1059
1060 static fz_rect
fz_bound_mesh(fz_context * ctx,fz_shade * shade)1061 fz_bound_mesh(fz_context *ctx, fz_shade *shade)
1062 {
1063 if (shade->type == FZ_FUNCTION_BASED)
1064 return fz_bound_mesh_type1(ctx, shade);
1065 else if (shade->type == FZ_LINEAR)
1066 return fz_bound_mesh_type2(ctx, shade);
1067 else if (shade->type == FZ_RADIAL)
1068 return fz_bound_mesh_type3(ctx, shade);
1069 else if (shade->type == FZ_MESH_TYPE4 ||
1070 shade->type == FZ_MESH_TYPE5 ||
1071 shade->type == FZ_MESH_TYPE6 ||
1072 shade->type == FZ_MESH_TYPE7)
1073 return fz_bound_mesh_type4567(ctx, shade);
1074 else
1075 fz_throw(ctx, FZ_ERROR_GENERIC, "Unexpected mesh type %d\n", shade->type);
1076 }
1077
1078 fz_shade *
fz_keep_shade(fz_context * ctx,fz_shade * shade)1079 fz_keep_shade(fz_context *ctx, fz_shade *shade)
1080 {
1081 return fz_keep_storable(ctx, &shade->storable);
1082 }
1083
1084 void
fz_drop_shade_imp(fz_context * ctx,fz_storable * shade_)1085 fz_drop_shade_imp(fz_context *ctx, fz_storable *shade_)
1086 {
1087 fz_shade *shade = (fz_shade *)shade_;
1088
1089 fz_drop_colorspace(ctx, shade->colorspace);
1090 if (shade->type == FZ_FUNCTION_BASED)
1091 fz_free(ctx, shade->u.f.fn_vals);
1092 fz_drop_compressed_buffer(ctx, shade->buffer);
1093 fz_free(ctx, shade);
1094 }
1095
1096 void
fz_drop_shade(fz_context * ctx,fz_shade * shade)1097 fz_drop_shade(fz_context *ctx, fz_shade *shade)
1098 {
1099 fz_drop_storable(ctx, &shade->storable);
1100 }
1101
1102 fz_rect
fz_bound_shade(fz_context * ctx,fz_shade * shade,fz_matrix ctm)1103 fz_bound_shade(fz_context *ctx, fz_shade *shade, fz_matrix ctm)
1104 {
1105 ctm = fz_concat(shade->matrix, ctm);
1106 if (shade->type != FZ_LINEAR && shade->type != FZ_RADIAL)
1107 {
1108 fz_rect rect = fz_bound_mesh(ctx, shade);
1109 rect = fz_intersect_rect(rect, shade->bbox);
1110 return fz_transform_rect(rect, ctm);
1111 }
1112 return fz_transform_rect(shade->bbox, ctm);
1113 }
1114