summaryrefslogtreecommitdiff
path: root/draw/pathfill.c
blob: 62d4ac593a20edfbecd96a6168266101e5b941e4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include "fitz.h"

static void
line(fz_gel *gel, fz_matrix *ctm, float x0, float y0, float x1, float y1)
{
	float tx0 = ctm->a * x0 + ctm->c * y0 + ctm->e;
	float ty0 = ctm->b * x0 + ctm->d * y0 + ctm->f;
	float tx1 = ctm->a * x1 + ctm->c * y1 + ctm->e;
	float ty1 = ctm->b * x1 + ctm->d * y1 + ctm->f;
	fz_insertgel(gel, tx0, ty0, tx1, ty1);
}

static void
bezier(fz_gel *gel, fz_matrix *ctm, float flatness,
	float xa, float ya,
	float xb, float yb,
	float xc, float yc,
	float xd, float yd)
{
	float dmax;
	float xab, yab;
	float xbc, ybc;
	float xcd, ycd;
	float xabc, yabc;
	float xbcd, ybcd;
	float xabcd, yabcd;

	/* termination check */
	dmax = ABS(xa - xb);
	dmax = MAX(dmax, ABS(ya - yb));
	dmax = MAX(dmax, ABS(xd - xc));
	dmax = MAX(dmax, ABS(yd - yc));
	if (dmax < flatness) {
		line(gel, ctm, xa, ya, xd, yd);
		return;
	}

	xab = xa + xb;
	yab = ya + yb;
	xbc = xb + xc;
	ybc = yb + yc;
	xcd = xc + xd;
	ycd = yc + yd;

	xabc = xab + xbc;
	yabc = yab + ybc;
	xbcd = xbc + xcd;
	ybcd = ybc + ycd;

	xabcd = xabc + xbcd;
	yabcd = yabc + ybcd;

	xab *= 0.5f; yab *= 0.5f;
	xbc *= 0.5f; ybc *= 0.5f;
	xcd *= 0.5f; ycd *= 0.5f;

	xabc *= 0.25f; yabc *= 0.25f;
	xbcd *= 0.25f; ybcd *= 0.25f;

	xabcd *= 0.125f; yabcd *= 0.125f;

	bezier(gel, ctm, flatness, xa, ya, xab, yab, xabc, yabc, xabcd, yabcd);
	bezier(gel, ctm, flatness, xabcd, yabcd, xbcd, ybcd, xcd, ycd, xd, yd);
}

void
fz_fillpath(fz_gel *gel, fz_path *path, fz_matrix ctm, float flatness)
{
	float x1, y1, x2, y2, x3, y3;
	float cx = 0;
	float cy = 0;
	float bx = 0;
	float by = 0;
	int i = 0;

	while (i < path->len)
	{
		switch (path->els[i++].k)
		{
		case FZ_MOVETO:
			/* implicit closepath before moveto */
			if (i && (cx != bx || cy != by))
				line(gel, &ctm, cx, cy, bx, by);
			x1 = path->els[i++].v;
			y1 = path->els[i++].v;
			cx = bx = x1;
			cy = by = y1;
			break;

		case FZ_LINETO:
			x1 = path->els[i++].v;
			y1 = path->els[i++].v;
			line(gel, &ctm, cx, cy, x1, y1);
			cx = x1;
			cy = y1;
			break;

		case FZ_CURVETO:
			x1 = path->els[i++].v;
			y1 = path->els[i++].v;
			x2 = path->els[i++].v;
			y2 = path->els[i++].v;
			x3 = path->els[i++].v;
			y3 = path->els[i++].v;
			bezier(gel, &ctm, flatness, cx, cy, x1, y1, x2, y2, x3, y3);
			cx = x3;
			cy = y3;
			break;

		case FZ_CLOSEPATH:
			line(gel, &ctm, cx, cy, bx, by);
			cx = bx;
			cy = by;
			break;
		}
	}

	if (i && (cx != bx || cy != by))
		line(gel, &ctm, cx, cy, bx, by);
}