Subversion Repositories planix.SVN

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 1 
#include <u.h>
2 
#include <libc.h>
3 
#include <draw.h>
4 
 
5 
#define	PINC	32		/* realloc granularity */
6 
 
7 
typedef struct Plist Plist;
8 
struct Plist
9 
{
10 
	Point *p;
11 
	int np;			/* -1 if malloc/realloc failed */
12 
};
13 
 
14 
static void
15 
appendpt(Plist *l, Point p)
16 
{
17 
	if(l->np == -1)
18 
		return;
19 
	if(l->np == 0)
20 
		l->p = malloc(PINC*sizeof(Point));
21 
	else if(l->np%PINC == 0)
22 
		l->p = realloc(l->p, (l->np+PINC)*sizeof(Point));
23 
	if(l->p == 0){
24 
		l->np = -1;
25 
		return;
26 
	}
27 
	l->p[l->np++] = p;
28 
}
29 
 
30 
static int
31 
normsq(Point p)
32 
{
33 
	return p.x*p.x+p.y*p.y;
34 
}
35 
 
36 
static int
37 
psdist(Point p, Point a, Point b)
38 
{
39 
	int num, den;
40 
 
41 
	p = subpt(p, a);
42 
	b = subpt(b, a);
43 
	num = p.x*b.x + p.y*b.y;
44 
	if(num <= 0)
45 
		return normsq(p);
46 
	den = normsq(b);
47 
	if(num >= den)
48 
		return normsq(subpt(b, p));
49 
	return normsq(subpt(divpt(mulpt(b, num), den), p));
50 
}
51 
 
52 
/*
53 
 * Convert cubic Bezier curve control points to polyline
54 
 * vertices.  Leaves the last vertex off, so you can continue
55 
 * with another curve.
56 
 */
57 
static void
58 
bpts1(Plist *l, Point p0, Point p1, Point p2, Point p3, int scale)
59 
{
60 
	Point p01, p12, p23, p012, p123, p0123;
61 
	Point tp0, tp1, tp2, tp3;
62 
	tp0=divpt(p0, scale);
63 
	tp1=divpt(p1, scale);
64 
	tp2=divpt(p2, scale);
65 
	tp3=divpt(p3, scale);
66 
	if(psdist(tp1, tp0, tp3)<=1 && psdist(tp2, tp0, tp3)<=1){
67 
		appendpt(l, tp0);
68 
		appendpt(l, tp1);
69 
		appendpt(l, tp2);
70 
	}
71 
	else{
72 
		/*
73 
		 * if scale factor is getting too big for comfort,
74 
		 * rescale now & concede the rounding error
75 
		 */
76 
		if(scale>(1<<12)){
77 
			p0=tp0;
78 
			p1=tp1;
79 
			p2=tp2;
80 
			p3=tp3;
81 
			scale=1;
82 
		}
83 
		p01=addpt(p0, p1);
84 
		p12=addpt(p1, p2);
85 
		p23=addpt(p2, p3);
86 
		p012=addpt(p01, p12);
87 
		p123=addpt(p12, p23);
88 
		p0123=addpt(p012, p123);
89 
		bpts1(l, mulpt(p0, 8), mulpt(p01, 4), mulpt(p012, 2), p0123, scale*8);
90 
		bpts1(l, p0123, mulpt(p123, 2), mulpt(p23, 4), mulpt(p3, 8), scale*8);
91 
	}
92 
}
93 
 
94 
static void
95 
bpts(Plist *l, Point p0, Point p1, Point p2, Point p3)
96 
{
97 
	bpts1(l, p0, p1, p2, p3, 1);
98 
}
99 
 
100 
static void
101 
bezierpts(Plist *l, Point p0, Point p1, Point p2, Point p3)
102 
{
103 
	bpts(l, p0, p1, p2, p3);
104 
	appendpt(l, p3);
105 
}
106 
 
107 
static void
108 
_bezsplinepts(Plist *l, Point *pt, int npt)
109 
{
110 
	Point *p, *ep;
111 
	Point a, b, c, d;
112 
	int periodic;
113 
 
114 
	if(npt<3)
115 
		return;
116 
	ep = &pt[npt-3];
117 
	periodic = eqpt(pt[0], ep[2]);
118 
	if(periodic){
119 
		a = divpt(addpt(ep[1], pt[0]), 2);
120 
		b = divpt(addpt(ep[1], mulpt(pt[0], 5)), 6);
121 
		c = divpt(addpt(mulpt(pt[0], 5), pt[1]), 6);
122 
		d = divpt(addpt(pt[0], pt[1]), 2);
123 
		bpts(l, a, b, c, d);
124 
	}
125 
	for(p=pt; p<=ep; p++){
126 
		if(p==pt && !periodic){
127 
			a = p[0];
128 
			b = divpt(addpt(p[0], mulpt(p[1], 2)), 3);
129 
		}
130 
		else{
131 
			a = divpt(addpt(p[0], p[1]), 2);
132 
			b = divpt(addpt(p[0], mulpt(p[1], 5)), 6);
133 
		}
134 
		if(p==ep && !periodic){
135 
			c = divpt(addpt(mulpt(p[1], 2), p[2]), 3);
136 
			d = p[2];
137 
		}
138 
		else{
139 
			c = divpt(addpt(mulpt(p[1], 5), p[2]), 6);
140 
			d = divpt(addpt(p[1], p[2]), 2);
141 
		}
142 
		bpts(l, a, b, c, d);
143 
	}
144 
	appendpt(l, d);
145 
}
146 
 
147 
int
148 
bezsplinepts(Point *pt, int npt, Point **pp)
149 
{
150 
	Plist l;
151 
	l.np = 0;
152 
	l.p = nil;
153 
	_bezsplinepts(&l, pt, npt);
154 
	*pp  = l.p;
155 
	return l.np;
156 
}
157 
 
158 
int
159 
bezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp)
160 
{
161 
	return bezierop(dst, p0, p1, p2, p3, end0, end1, radius, src, sp, SoverD);
162 
}
163 
 
164 
int
165 
bezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp, Drawop op)
166 
{
167 
	Plist l;
168 
 
169 
	l.np = 0;
170 
	bezierpts(&l, p0, p1, p2, p3);
171 
	if(l.np == -1)
172 
		return 0;
173 
	if(l.np != 0){
174 
		polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, p0), l.p[0]), op);
175 
		free(l.p);
176 
	}
177 
	return 1;
178 
}
179 
 
180 
int
181 
bezspline(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp)
182 
{
183 
	return bezsplineop(dst, pt, npt, end0, end1, radius, src, sp, SoverD);
184 
}
185 
 
186 
int
187 
bezsplineop(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp, Drawop op)
188 
{
189 
	Plist l;
190 
 
191 
	l.np = 0;
192 
	_bezsplinepts(&l, pt, npt);
193 
	if(l.np==-1)
194 
		return 0;
195 
	if(l.np != 0){
196 
		polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, pt[0]), l.p[0]), op);
197 
		free(l.p);
198 
	}
199 
	return 1;
200 
}
201 
 
202 
int
203 
fillbezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp)
204 
{
205 
	return fillbezierop(dst, p0, p1, p2, p3, w, src, sp, SoverD);
206 
}
207 
 
208 
int
209 
fillbezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp, Drawop op)
210 
{
211 
	Plist l;
212 
 
213 
	l.np = 0;
214 
	bezierpts(&l, p0, p1, p2, p3);
215 
	if(l.np == -1)
216 
		return 0;
217 
	if(l.np != 0){
218 
		fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, p0), l.p[0]), op);
219 
		free(l.p);
220 
	}
221 
	return 1;
222 
}
223 
 
224 
int
225 
fillbezspline(Image *dst, Point *pt, int npt, int w, Image *src, Point sp)
226 
{
227 
	return fillbezsplineop(dst, pt, npt, w, src, sp, SoverD);
228 
}
229 
 
230 
int
231 
fillbezsplineop(Image *dst, Point *pt, int npt, int w, Image *src, Point sp, Drawop op)
232 
{
233 
	Plist l;
234 
 
235 
	l.np = 0;
236 
	_bezsplinepts(&l, pt, npt);
237 
	if(l.np == -1)
238 
		return 0;
239 
	if(l.np > 0){
240 
		fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, pt[0]), l.p[0]), op);
241 
		free(l.p);
242 
	}
243 
	return 1;
244 
}