3 Various utility functions for dealing with gfxdevices.
5 Part of the swftools package.
7 Copyright (c) 2005 Matthias Kramm <kramm@quiss.org>
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 2 of the License, or
12 (at your option) any later version.
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
32 typedef struct _linedraw_internal
36 } linedraw_internal_t;
38 static void linedraw_moveTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
40 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
41 gfxline_t*l = (gfxline_t*)rfx_alloc(sizeof(gfxline_t));
43 if((int)((d->x * 5120) == (int)(x * 5120)) &&
44 (int)((d->y * 5120) == (int)(y * 5120))) {
45 /* never mind- we're already there */
59 static void linedraw_lineTo(gfxdrawer_t*d, gfxcoord_t x, gfxcoord_t y)
61 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
62 gfxline_t*l = (gfxline_t*)rfx_alloc(sizeof(gfxline_t));
65 /* starts with a line, not with a moveto. That needs we first
66 need an explicit moveto to (0,0) */
67 linedraw_moveTo(d, 0, 0);
81 static void linedraw_splineTo(gfxdrawer_t*d, gfxcoord_t sx, gfxcoord_t sy, gfxcoord_t x, gfxcoord_t y)
83 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
84 gfxline_t*l = (gfxline_t*)rfx_alloc(sizeof(gfxline_t));
87 /* starts with a line, not with a moveto. That needs we first
88 need an explicit moveto to (0,0) */
89 linedraw_moveTo(d, 0, 0);
92 l->type = gfx_splineTo;
104 static void* linedraw_result(gfxdrawer_t*d)
106 linedraw_internal_t*i = (linedraw_internal_t*)d->internal;
107 void*result = (void*)i->start;
109 memset(d, 0, sizeof(gfxdrawer_t));
113 void gfxdrawer_target_gfxline(gfxdrawer_t*d)
115 linedraw_internal_t*i = (linedraw_internal_t*)rfx_calloc(sizeof(linedraw_internal_t));
119 d->moveTo = linedraw_moveTo;
120 d->lineTo = linedraw_lineTo;
121 d->splineTo = linedraw_splineTo;
122 d->result = linedraw_result;
125 typedef struct _qspline_abc
131 typedef struct qspline_t
138 typedef struct cspline_t
146 static void mkspline(qspline_abc_t*s, double x, double y, gfxline_t*l)
149 Form 1: x = t*t*l->x + 2*t*(1-t)*l->sx + (1-t)*(1-t)*x;
150 Form 2: x = a*t*t + b*t + c
152 s->cx = x; s->bx = 2*l->sx - 2*x; s->ax = l->x - 2*l->sx + x;
153 s->cy = y; s->by = 2*l->sy - 2*y; s->ay = l->y - 2*l->sy + y;
156 static void spline_get_controlpoint(qspline_abc_t*q, double t1, double t2, double*dx, double*dy)
159 double nax = q->ax*dt*dt;
160 double nay = q->ay*dt*dt;
161 double nbx = 2*q->ax*dt*t1 + q->bx*dt;
162 double nby = 2*q->ay*dt*t1 + q->by*dt;
163 double ncx = q->ax*t1*t1 + q->bx*t1 + q->cx;
164 double ncy = q->ay*t1*t1 + q->by*t1 + q->cy;
169 static double get_spline_len(qspline_abc_t*s)
171 int parts = (int)(sqrt(fabs(s->ax) + fabs(s->ay))*3);
176 if(parts < 3) parts = 3;
178 r2 = 1.0/(parts*parts);
181 double dx = s->ax*(2*i+1)*r2 + s->bx*r;
182 double dy = s->ay*(2*i+1)*r2 + s->by*r;
183 len += sqrt(dx*dx+dy*dy);
185 /*printf("Spline from %f,%f to %f,%f has len %f (%f)\n", s->cx, s->cy,
186 s->cx + s->bx + s->ax,
187 s->cy + s->by + s->ay, len,
188 sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay))
190 assert(len+0.5 >= sqrt((s->bx + s->ax)*(s->bx + s->ax) + (s->by + s->ay)*(s->by + s->ay)));
195 void gfxtool_draw_dashed_line(gfxdrawer_t*d, gfxline_t*line, float*r, float phase)
198 double linepos,nextpos;
202 if(line && line->type != gfx_moveTo) {
203 fprintf(stderr, "gfxtool: outline doesn't start with a moveTo");
206 if(!r || (r[0]<=0 && r[0]>-0.01)) {
207 // no dashing. just draw the thing
209 if(line->type == gfx_moveTo) {
210 d->moveTo(d, line->x, line->y);
211 } else if(line->type == gfx_lineTo) {
212 d->lineTo(d, line->x, line->y);
213 } else if(line->type == gfx_splineTo) {
214 d->splineTo(d, line->sx, line->sy, line->x, line->y);
220 if(r[0]<0 || phase<0) {
221 fprintf(stderr, "gfxtool: invalid (negative) dashes: %f, phase=%f", r[0], phase);
226 for(;line;line=line->next) {
227 if(line->type == gfx_moveTo) {
228 d->moveTo(d, line->x, line->y);
229 on = 1; nextpos = r[0]; apos = 0; linepos = 0;
230 x = line->x; y = line->y;
231 while(linepos < phase) {
232 //printf("[+] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f\n", linepos, phase, on, apos, nextpos);
234 if(linepos < phase) {
242 //printf("[k] linepos: %f, phase: %f, on:%d, apos:%d nextpos:%f \n", linepos, phase, on, apos, nextpos);
243 } else if(line->type == gfx_lineTo) {
244 double dx = line->x - x;
245 double dy = line->y - y;
246 double len = sqrt(dx*dx+dy*dy);
249 double lineend = linepos+len;
254 assert(nextpos>=linepos);
255 //printf("(line) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
256 while(nextpos<lineend) {
257 double nx = x + vx*(nextpos-linepos);
258 double ny = y + vy*(nextpos-linepos);
259 if(on) {d->lineTo(d, nx,ny);/*printf("lineTo %f\n", nextpos);*/}
260 else {d->moveTo(d, nx,ny);/*printf("moveTo %f\n", nextpos);*/}
268 //printf("lineTo %f\n", 1.0);
269 d->lineTo(d, line->x,line->y);
271 x = line->x; y = line->y;
272 } else if(line->type == gfx_splineTo) {
274 double len, lineend,lastt;
275 mkspline(&q, x, y, line);
277 len = get_spline_len(&q);
278 //printf("%f %f -> %f %f, len: %f\n", x, y, line->x, line->y, len);
281 lineend = linepos+len;
284 printf("%f !< %f\n", nextpos, linepos);
285 assert(nextpos>=linepos);
286 //printf("(spline) on:%d apos: %d nextpos: %f, line pos: %f, line end: %f\n", on, apos, nextpos, linepos, linepos+len);
287 while(nextpos<lineend) {
288 double t = (nextpos-linepos)/len;
289 //printf("%f (%f-%f) apos=%d r[apos]=%f\n", t, nextpos, linepos, apos, r[apos]);
290 double nx = q.ax*t*t+q.bx*t+q.cx;
291 double ny = q.ay*t*t+q.by*t+q.cy;
294 spline_get_controlpoint(&q, lastt, t, &sx, &sy);
295 d->splineTo(d, sx, sy, nx,ny);
296 //printf("splineTo %f\n", nextpos);
299 //printf("moveTo %f\n", nextpos);
310 spline_get_controlpoint(&q, lastt, 1, &sx, &sy);
311 d->splineTo(d, sx, sy, line->x,line->y);
312 //printf("splineTo %f\n", 1.0);
314 x = line->x; y = line->y;
319 gfxline_t * gfxline_clone(gfxline_t*line)
324 gfxline_t*n = (gfxline_t*)rfx_calloc(sizeof(gfxline_t));
337 void gfxline_optimize(gfxline_t*line)
340 /* step 1: convert splines to lines, where possible */
343 if(l->type == gfx_splineTo) {
348 if(fabs(dx*sy - dy*sx) < 0.000001 && (dx*sx + dy*sy) >= 0) {
349 l->type = gfx_lineTo;
356 /* step 2: combine adjacent lines and splines, where possible */
358 while(l && l->next) {
359 gfxline_t*next = l->next;
362 if(l->type == gfx_lineTo && next->type == gfx_lineTo) {
365 double nx = next->x-l->x;
366 double ny = next->y-l->y;
367 if(fabs(dx*ny - dy*nx) < 0.000001 && (dx*nx + dy*ny) >= 0) {
370 } else if(l->type == gfx_splineTo && next->type == gfx_splineTo) {
374 l->next = next->next;
389 gfxline_t* gfxtool_dash_line(gfxline_t*line, float*dashes, float phase)
393 gfxdrawer_target_gfxline(&d);
394 gfxtool_draw_dashed_line(&d, line, dashes, phase);
395 result= (gfxline_t*)d.result(&d);
399 void gfxline_show(gfxline_t*l, FILE*fi)
402 if(l->type == gfx_moveTo) {
403 fprintf(fi, "moveTo %.2f,%.2f\n", l->x, l->y);
405 if(l->type == gfx_lineTo) {
406 fprintf(fi, "lineTo %.2f,%.2f\n", l->x, l->y);
408 if(l->type == gfx_splineTo) {
409 fprintf(fi, "splineTo %.2f,%.2f %.2f,%.2f\n", l->sx, l->sy, l->x, l->y);
415 void gfxline_free(gfxline_t*l)
417 if(l && (l+1) == l->next) {
431 static inline gfxpoint_t cspline_getpoint(const struct cspline_t*s, double t)
437 double mtmt = mt*(1-t);
438 double mtmtmt = mtmt*(1-t);
439 p.x= s->end.x*ttt + 3*s->control2.x*tt*mt
440 + 3*s->control1.x*t*mtmt + s->start.x*mtmtmt;
441 p.y= s->end.y*ttt + 3*s->control2.y*tt*mt
442 + 3*s->control1.y*t*mtmt + s->start.y*mtmtmt;
445 static gfxpoint_t qspline_getpoint(const qspline_t*s, double t)
448 p.x= s->end.x*t*t + 2*s->control.x*t*(1-t) + s->start.x*(1-t)*(1-t);
449 p.y= s->end.y*t*t + 2*s->control.y*t*(1-t) + s->start.y*(1-t)*(1-t);
453 static int approximate3(const cspline_t*s, qspline_t*q, int size, double quality2)
455 unsigned int gran = 0;
456 unsigned int istep = 0x80000000;
457 unsigned int istart = 0;
461 while(istart<0x80000000)
463 unsigned int iend = istart + istep;
464 double start = istart/(double)0x80000000;
465 double end = iend/(double)0x80000000;
468 char left = 0,recurse=0;
473 /* create simple approximation: a qspline_t which run's through the
474 qspline_t point at 0.5 */
475 test.start = cspline_getpoint(s, start);
476 test.control = cspline_getpoint(s, (start+end)/2);
477 test.end = cspline_getpoint(s, end);
478 /* fix the control point:
479 move it so that the new spline does runs through it */
480 test.control.x = -(test.end.x + test.start.x)/2 + 2*(test.control.x);
481 test.control.y = -(test.end.y + test.start.y)/2 + 2*(test.control.y);
483 /* depending on where we are in the spline, we either try to match
484 the left or right tangent */
488 pos = left?start:end;
490 test.control.x = s->end.x*(3*qpos) + 3*s->control2.x*(2*pos-3*qpos) +
491 3*s->control1.x*(1-4*pos+3*qpos) + s->start.x*(-3+6*pos-3*qpos);
492 test.control.y = s->end.y*(3*qpos) + 3*s->control2.y*(2*pos-3*qpos) +
493 3*s->control1.y*(1-4*pos+3*qpos) + s->start.y*(-3+6*pos-3*qpos);
495 test.control.x *= (end-start)/2;
496 test.control.y *= (end-start)/2;
497 test.control.x += test.start.x;
498 test.control.y += test.start.y;
500 test.control.x *= -(end-start)/2;
501 test.control.y *= -(end-start)/2;
502 test.control.x += test.end.x;
503 test.control.y += test.end.y;
508 /* measure the spline's accurancy, by taking a number of probes */
509 for(t=0;t<probes;t++) {
510 gfxpoint_t qr1,qr2,cr1,cr2;
511 double pos = 0.5/(probes*2)*(t*2+1);
514 qr1 = qspline_getpoint(&test, pos);
515 cr1 = cspline_getpoint(s, start+pos*(end-start));
524 qr2 = qspline_getpoint(&test, (1-pos));
525 cr2 = cspline_getpoint(s, start+(1-pos)*(end-start));
535 #else // quadratic error: *much* faster!
537 /* convert control point representation to
538 d*x^3 + c*x^2 + b*x + a */
539 dx= s->end.x - s->control2.x*3 + s->control1.x*3 - s->start.x;
540 dy= s->end.y - s->control2.y*3 + s->control1.y*3 - s->start.y;
542 /* we need to do this for the subspline between [start,end], not [0,1]
543 as a transformation of t->a*t+b does nothing to highest coefficient
544 of the spline except multiply it with a^3, we just need to modify
546 {double m = end-start;
551 /* use the integral over (f(x)-g(x))^2 between 0 and 1
552 to measure the approximation quality.
553 (it boils down to const*d^2) */
554 recurse = (dx*dx + dy*dy > quality2);
557 if(recurse && istep>1 && size-level > num) {
564 while(!(istart & istep)) {
573 void gfxdraw_conicTo(gfxdrawer_t*draw, double cx, double cy, double tox, double toy, double quality)
575 double c1x = (draw->x + 2 * cx) / 3;
576 double c1y = (draw->y + 2 * cy) / 3;
577 double c2x = (2 * cx + tox) / 3;
578 double c2y = (2 * cy + toy) / 3;
579 gfxdraw_cubicTo(draw, c1x, c1y, c2x, c2y, tox, toy, quality);
583 void gfxdraw_cubicTo(gfxdrawer_t*draw, double c1x, double c1y, double c2x, double c2y, double x, double y, double quality)
587 double maxerror = quality>0 ? quality : 1.0;
599 num = approximate3(&c, q, 128, maxerror);
604 mid.x = q[t].control.x;
605 mid.y = q[t].control.y;
608 draw->splineTo(draw, mid.x, mid.y, to.x, to.y);
612 gfxbbox_t gfxbbox_expand_to_point(gfxbbox_t box, gfxcoord_t x, gfxcoord_t y)
614 if(box.xmin==0 && box.ymin==0 && box.xmax==0 && box.ymax==0) {
619 if(x==0 && y==0) box.xmax = 0.0000001;
633 void gfxbbox_intersect(gfxbbox_t*box1, gfxbbox_t*box2)
635 if(box2->xmin > box1->xmin)
636 box1->xmin = box2->xmin;
637 if(box2->ymin > box1->ymin)
638 box1->ymin = box2->ymin;
639 if(box2->xmax < box1->xmax)
640 box1->xmax = box2->xmax;
641 if(box2->ymax > box1->ymax)
642 box1->ymax = box2->ymax;
643 if(box1->xmin > box1->xmax)
644 box1->xmax = box1->xmin;
645 if(box1->ymin > box1->ymax)
646 box1->ymax = box1->ymin;
649 gfxbbox_t gfxline_getbbox(gfxline_t*line)
652 gfxbbox_t bbox = {0,0,0,0};
655 if(line->type == gfx_moveTo) {
657 } else if(line->type == gfx_lineTo) {
658 if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
659 bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
661 } else if(line->type == gfx_splineTo) {
662 if(last) bbox = gfxbbox_expand_to_point(bbox, x, y);
663 bbox = gfxbbox_expand_to_point(bbox, line->sx, line->sy);
664 bbox = gfxbbox_expand_to_point(bbox, line->x, line->y);
674 void gfxline_dump(gfxline_t*line, FILE*fi, char*prefix)
677 if(line->type == gfx_moveTo) {
678 fprintf(fi, "%smoveTo %.2f %.2f\n", prefix, line->x, line->y);
679 } else if(line->type == gfx_lineTo) {
680 fprintf(fi, "%slineTo %.2f %.2f\n", prefix, line->x, line->y);
681 } else if(line->type == gfx_splineTo) {
682 fprintf(fi, "%ssplineTo (%.2f %.2f) %.2f %.2f\n", prefix, line->sx, line->sy, line->x, line->y);
688 gfxline_t* gfxline_append(gfxline_t*line1, gfxline_t*line2)
690 gfxline_t*l = line1;;
700 void gfxline_transform(gfxline_t*line, gfxmatrix_t*matrix)
703 double x = matrix->m00*line->x + matrix->m10*line->y + matrix->tx;
704 double y = matrix->m01*line->x + matrix->m11*line->y + matrix->ty;
707 if(line->type == gfx_splineTo) {
708 double sx = matrix->m00*line->sx + matrix->m10*line->sy + matrix->tx;
709 double sy = matrix->m01*line->sx + matrix->m11*line->sy + matrix->ty;
717 void gfxmatrix_dump(gfxmatrix_t*m, FILE*fi, char*prefix)
719 fprintf(fi, "%f %f | %f\n", m->m00, m->m10, m->tx);
720 fprintf(fi, "%f %f | %f\n", m->m01, m->m11, m->ty);
723 void gfxmatrix_transform(gfxmatrix_t*m, double* v, double*dest)
725 dest[0] = m->m00*v[0] + m->m10*v[1] + m->tx;
726 dest[1] = m->m01*v[0] + m->m11*v[1] + m->ty;
728 void gfxmatrix_invert(gfxmatrix_t*m, gfxmatrix_t*dest)
730 double det = m->m00 * m->m11 - m->m10 * m->m01;
732 memset(dest, 0, sizeof(gfxmatrix_t));
736 dest->m00 = m->m11 * det;
737 dest->m01 = -m->m01 * det;
738 dest->m10 = -m->m10 * det;
739 dest->m11 = m->m00 * det;
740 dest->tx = -(dest->m00 * m->tx + dest->m10 * m->ty);
741 dest->ty = -(dest->m01 * m->tx + dest->m11 * m->ty);
743 void gfxmatrix_unit(gfxmatrix_t*m)
745 memset(m, 0, sizeof(gfxmatrix_t));
749 void gfxmatrix_multiply(gfxmatrix_t*m1, gfxmatrix_t*m2, gfxmatrix_t*dest)
751 dest->m00 = m1->m00*m2->m00 + m1->m10*m2->m01;
752 dest->m01 = m1->m01*m2->m00 + m1->m11*m2->m01;
753 dest->m10 = m1->m00*m2->m10 + m1->m10*m2->m11;
754 dest->m11 = m1->m01*m2->m10 + m1->m11*m2->m11;
755 dest->tx = m1->m00*m2->tx + m1->m10*m2->ty + m1->tx;
756 dest->ty = m1->m01*m2->tx + m1->m11*m2->ty + m1->ty;
759 gfxfontlist_t* gfxfontlist_create()
761 /* Initial list ist empty */
765 gfxfont_t*gfxfontlist_findfont(gfxfontlist_t*list, char*id)
767 gfxfontlist_t*l = list;
769 if(!strcmp((char*)l->font->id, id)) {
776 char gfxfontlist_hasfont(gfxfontlist_t*list, gfxfont_t*font)
778 gfxfontlist_t*l = list;
780 if(!strcmp((char*)l->font->id, font->id)) {
787 gfxfontlist_t*gfxfontlist_addfont(gfxfontlist_t*list, gfxfont_t*font)
789 gfxfontlist_t*last=0,*l = list;
792 if(l->font == font) {
793 return list; // we already know this font
798 fprintf(stderr, "Tried to add zero font\n");
800 l = (gfxfontlist_t*)rfx_calloc(sizeof(gfxfontlist_t));
810 void gfxfontlist_free(gfxfontlist_t*list, char deletefonts)
812 gfxfontlist_t*l = list;
814 gfxfontlist_t*next = l->next;
815 if(deletefonts && l->font) {
816 gfxfont_free(l->font);l->font=0;
824 gfxline_t*gfxline_makerectangle(int x1,int y1,int x2, int y2)
826 gfxline_t* line = (gfxline_t*)rfx_calloc(sizeof(gfxline_t)*5);
827 line[0].x = x1;line[0].y = y1;line[0].type = gfx_moveTo;line[0].next = &line[1];
828 line[1].x = x2;line[1].y = y1;line[1].type = gfx_lineTo;line[1].next = &line[2];
829 line[2].x = x2;line[2].y = y2;line[2].type = gfx_lineTo;line[2].next = &line[3];
830 line[3].x = x1;line[3].y = y2;line[3].type = gfx_lineTo;line[3].next = &line[4];
831 line[4].x = x1;line[4].y = y1;line[4].type = gfx_lineTo;
835 void gfximage_transform(gfximage_t*img, gfxcxform_t*cxform)
838 int size = img->width*img->height;
844 rr = (int)(cxform->rr*256);gr = (int)(cxform->gr*256);
845 rg = (int)(cxform->rg*256);gg = (int)(cxform->gg*256);
846 rb = (int)(cxform->rb*256);gb = (int)(cxform->gb*256);
847 ra = (int)(cxform->ra*256);ga = (int)(cxform->ga*256);
848 br = (int)(cxform->br*256);ar = (int)(cxform->ar*256);tr = (int)(cxform->tr*256);
849 bg = (int)(cxform->bg*256);ag = (int)(cxform->ag*256);tg = (int)(cxform->tg*256);
850 bb = (int)(cxform->bb*256);ab = (int)(cxform->ab*256);tb = (int)(cxform->tb*256);
851 ba = (int)(cxform->ba*256);aa = (int)(cxform->aa*256);ta = (int)(cxform->ta*256);
853 for(t=0;t<size;t++) {
854 gfxcolor_t*pixel = &img->data[t];
855 unsigned char r = (pixel->r * rr + pixel->g * rg + pixel->b * rb + pixel->a * ra + tr) / 256;
856 unsigned char g = (pixel->r * gr + pixel->g * gg + pixel->b * gb + pixel->a * ga + tg) / 256;
857 unsigned char b = (pixel->r * br + pixel->g * bg + pixel->b * bb + pixel->a * ba + tb) / 256;
858 unsigned char a = (pixel->r * ar + pixel->g * ag + pixel->b * ab + pixel->a * aa + ta) / 256;