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