Blame

Date:
Message:
Initial import.
Actions:
History | Blob | Raw File
  1 ed7c8e8d 2003-09-30 devnull #include <u.h>

  2 ed7c8e8d 2003-09-30 devnull #include <libc.h>

  3 ed7c8e8d 2003-09-30 devnull #include <draw.h>

  4 ed7c8e8d 2003-09-30 devnull 

  5 ed7c8e8d 2003-09-30 devnull #define	PINC	32		/* realloc granularity */

  6 ed7c8e8d 2003-09-30 devnull 

  7 ed7c8e8d 2003-09-30 devnull typedef struct Plist Plist;

  8 ed7c8e8d 2003-09-30 devnull struct Plist

  9 ed7c8e8d 2003-09-30 devnull {

 10 ed7c8e8d 2003-09-30 devnull 	Point *p;

 11 ed7c8e8d 2003-09-30 devnull 	int np;			/* -1 if malloc/realloc failed */

 12 ed7c8e8d 2003-09-30 devnull };

 13 ed7c8e8d 2003-09-30 devnull 

 14 ed7c8e8d 2003-09-30 devnull static void

 15 ed7c8e8d 2003-09-30 devnull appendpt(Plist *l, Point p)

 16 ed7c8e8d 2003-09-30 devnull {

 17 ed7c8e8d 2003-09-30 devnull 	if(l->np == -1)

 18 ed7c8e8d 2003-09-30 devnull 		return;

 19 ed7c8e8d 2003-09-30 devnull 	if(l->np == 0)

 20 ed7c8e8d 2003-09-30 devnull 		l->p = malloc(PINC*sizeof(Point));

 21 ed7c8e8d 2003-09-30 devnull 	else if(l->np%PINC == 0)

 22 ed7c8e8d 2003-09-30 devnull 		l->p = realloc(l->p, (l->np+PINC)*sizeof(Point));

 23 ed7c8e8d 2003-09-30 devnull 	if(l->p == 0){

 24 ed7c8e8d 2003-09-30 devnull 		l->np = -1;

 25 ed7c8e8d 2003-09-30 devnull 		return;

 26 ed7c8e8d 2003-09-30 devnull 	}

 27 ed7c8e8d 2003-09-30 devnull 	l->p[l->np++] = p;

 28 ed7c8e8d 2003-09-30 devnull }

 29 ed7c8e8d 2003-09-30 devnull 

 30 ed7c8e8d 2003-09-30 devnull static int

 31 ed7c8e8d 2003-09-30 devnull normsq(Point p)

 32 ed7c8e8d 2003-09-30 devnull {

 33 ed7c8e8d 2003-09-30 devnull 	return p.x*p.x+p.y*p.y;

 34 ed7c8e8d 2003-09-30 devnull }

 35 ed7c8e8d 2003-09-30 devnull 

 36 ed7c8e8d 2003-09-30 devnull static int

 37 ed7c8e8d 2003-09-30 devnull psdist(Point p, Point a, Point b)

 38 ed7c8e8d 2003-09-30 devnull {

 39 ed7c8e8d 2003-09-30 devnull 	int num, den;

 40 ed7c8e8d 2003-09-30 devnull 

 41 ed7c8e8d 2003-09-30 devnull 	p = subpt(p, a);

 42 ed7c8e8d 2003-09-30 devnull 	b = subpt(b, a);

 43 ed7c8e8d 2003-09-30 devnull 	num = p.x*b.x + p.y*b.y;

 44 ed7c8e8d 2003-09-30 devnull 	if(num <= 0)

 45 ed7c8e8d 2003-09-30 devnull 		return normsq(p);

 46 ed7c8e8d 2003-09-30 devnull 	den = normsq(b);

 47 ed7c8e8d 2003-09-30 devnull 	if(num >= den)

 48 ed7c8e8d 2003-09-30 devnull 		return normsq(subpt(b, p));

 49 ed7c8e8d 2003-09-30 devnull 	return normsq(subpt(divpt(mulpt(b, num), den), p));

 50 ed7c8e8d 2003-09-30 devnull }

 51 ed7c8e8d 2003-09-30 devnull 

 52 ed7c8e8d 2003-09-30 devnull /*

 53 ed7c8e8d 2003-09-30 devnull  * Convert cubic Bezier curve control points to polyline

 54 ed7c8e8d 2003-09-30 devnull  * vertices.  Leaves the last vertex off, so you can continue

 55 ed7c8e8d 2003-09-30 devnull  * with another curve.

 56 ed7c8e8d 2003-09-30 devnull  */

 57 ed7c8e8d 2003-09-30 devnull static void

 58 ed7c8e8d 2003-09-30 devnull bpts1(Plist *l, Point p0, Point p1, Point p2, Point p3, int scale)

 59 ed7c8e8d 2003-09-30 devnull {

 60 ed7c8e8d 2003-09-30 devnull 	Point p01, p12, p23, p012, p123, p0123;

 61 ed7c8e8d 2003-09-30 devnull 	Point tp0, tp1, tp2, tp3;

 62 ed7c8e8d 2003-09-30 devnull 	tp0=divpt(p0, scale);

 63 ed7c8e8d 2003-09-30 devnull 	tp1=divpt(p1, scale);

 64 ed7c8e8d 2003-09-30 devnull 	tp2=divpt(p2, scale);

 65 ed7c8e8d 2003-09-30 devnull 	tp3=divpt(p3, scale);

 66 ed7c8e8d 2003-09-30 devnull 	if(psdist(tp1, tp0, tp3)<=1 && psdist(tp2, tp0, tp3)<=1){

 67 ed7c8e8d 2003-09-30 devnull 		appendpt(l, tp0);

 68 ed7c8e8d 2003-09-30 devnull 		appendpt(l, tp1);

 69 ed7c8e8d 2003-09-30 devnull 		appendpt(l, tp2);

 70 ed7c8e8d 2003-09-30 devnull 	}

 71 ed7c8e8d 2003-09-30 devnull 	else{

 72 ed7c8e8d 2003-09-30 devnull 		/*

 73 ed7c8e8d 2003-09-30 devnull 		 * if scale factor is getting too big for comfort,

 74 ed7c8e8d 2003-09-30 devnull 		 * rescale now & concede the rounding error

 75 ed7c8e8d 2003-09-30 devnull 		 */

 76 ed7c8e8d 2003-09-30 devnull 		if(scale>(1<<12)){

 77 ed7c8e8d 2003-09-30 devnull 			p0=tp0;

 78 ed7c8e8d 2003-09-30 devnull 			p1=tp1;

 79 ed7c8e8d 2003-09-30 devnull 			p2=tp2;

 80 ed7c8e8d 2003-09-30 devnull 			p3=tp3;

 81 ed7c8e8d 2003-09-30 devnull 			scale=1;

 82 ed7c8e8d 2003-09-30 devnull 		}

 83 ed7c8e8d 2003-09-30 devnull 		p01=addpt(p0, p1);

 84 ed7c8e8d 2003-09-30 devnull 		p12=addpt(p1, p2);

 85 ed7c8e8d 2003-09-30 devnull 		p23=addpt(p2, p3);

 86 ed7c8e8d 2003-09-30 devnull 		p012=addpt(p01, p12);

 87 ed7c8e8d 2003-09-30 devnull 		p123=addpt(p12, p23);

 88 ed7c8e8d 2003-09-30 devnull 		p0123=addpt(p012, p123);

 89 ed7c8e8d 2003-09-30 devnull 		bpts1(l, mulpt(p0, 8), mulpt(p01, 4), mulpt(p012, 2), p0123, scale*8);

 90 ed7c8e8d 2003-09-30 devnull 		bpts1(l, p0123, mulpt(p123, 2), mulpt(p23, 4), mulpt(p3, 8), scale*8);

 91 ed7c8e8d 2003-09-30 devnull 	}

 92 ed7c8e8d 2003-09-30 devnull }

 93 ed7c8e8d 2003-09-30 devnull 

 94 ed7c8e8d 2003-09-30 devnull static void

 95 ed7c8e8d 2003-09-30 devnull bpts(Plist *l, Point p0, Point p1, Point p2, Point p3)

 96 ed7c8e8d 2003-09-30 devnull {

 97 ed7c8e8d 2003-09-30 devnull 	bpts1(l, p0, p1, p2, p3, 1);

 98 ed7c8e8d 2003-09-30 devnull }

 99 ed7c8e8d 2003-09-30 devnull 

100 ed7c8e8d 2003-09-30 devnull static void

101 ed7c8e8d 2003-09-30 devnull bezierpts(Plist *l, Point p0, Point p1, Point p2, Point p3)

102 ed7c8e8d 2003-09-30 devnull {

103 ed7c8e8d 2003-09-30 devnull 	bpts(l, p0, p1, p2, p3);

104 ed7c8e8d 2003-09-30 devnull 	appendpt(l, p3);

105 ed7c8e8d 2003-09-30 devnull }

106 ed7c8e8d 2003-09-30 devnull 

107 ed7c8e8d 2003-09-30 devnull static void

108 ed7c8e8d 2003-09-30 devnull _bezsplinepts(Plist *l, Point *pt, int npt)

109 ed7c8e8d 2003-09-30 devnull {

110 ed7c8e8d 2003-09-30 devnull 	Point *p, *ep;

111 ed7c8e8d 2003-09-30 devnull 	Point a, b, c, d;

112 ed7c8e8d 2003-09-30 devnull 	int periodic;

113 ed7c8e8d 2003-09-30 devnull 

114 ed7c8e8d 2003-09-30 devnull 	if(npt<3)

115 ed7c8e8d 2003-09-30 devnull 		return;

116 ed7c8e8d 2003-09-30 devnull 	ep = &pt[npt-3];

117 ed7c8e8d 2003-09-30 devnull 	periodic = eqpt(pt[0], ep[2]);

118 ed7c8e8d 2003-09-30 devnull 	if(periodic){

119 ed7c8e8d 2003-09-30 devnull 		a = divpt(addpt(ep[1], pt[0]), 2);

120 ed7c8e8d 2003-09-30 devnull 		b = divpt(addpt(ep[1], mulpt(pt[0], 5)), 6);

121 ed7c8e8d 2003-09-30 devnull 		c = divpt(addpt(mulpt(pt[0], 5), pt[1]), 6);

122 ed7c8e8d 2003-09-30 devnull 		d = divpt(addpt(pt[0], pt[1]), 2);

123 ed7c8e8d 2003-09-30 devnull 		bpts(l, a, b, c, d);

124 ed7c8e8d 2003-09-30 devnull 	}

125 ed7c8e8d 2003-09-30 devnull 	for(p=pt; p<=ep; p++){

126 ed7c8e8d 2003-09-30 devnull 		if(p==pt && !periodic){

127 ed7c8e8d 2003-09-30 devnull 			a = p[0];

128 ed7c8e8d 2003-09-30 devnull 			b = divpt(addpt(p[0], mulpt(p[1], 2)), 3);

129 ed7c8e8d 2003-09-30 devnull 		}

130 ed7c8e8d 2003-09-30 devnull 		else{

131 ed7c8e8d 2003-09-30 devnull 			a = divpt(addpt(p[0], p[1]), 2);

132 ed7c8e8d 2003-09-30 devnull 			b = divpt(addpt(p[0], mulpt(p[1], 5)), 6);

133 ed7c8e8d 2003-09-30 devnull 		}

134 ed7c8e8d 2003-09-30 devnull 		if(p==ep && !periodic){

135 ed7c8e8d 2003-09-30 devnull 			c = divpt(addpt(mulpt(p[1], 2), p[2]), 3);

136 ed7c8e8d 2003-09-30 devnull 			d = p[2];

137 ed7c8e8d 2003-09-30 devnull 		}

138 ed7c8e8d 2003-09-30 devnull 		else{

139 ed7c8e8d 2003-09-30 devnull 			c = divpt(addpt(mulpt(p[1], 5), p[2]), 6);

140 ed7c8e8d 2003-09-30 devnull 			d = divpt(addpt(p[1], p[2]), 2);

141 ed7c8e8d 2003-09-30 devnull 		}

142 ed7c8e8d 2003-09-30 devnull 		bpts(l, a, b, c, d);

143 ed7c8e8d 2003-09-30 devnull 	}

144 ed7c8e8d 2003-09-30 devnull 	appendpt(l, d);

145 ed7c8e8d 2003-09-30 devnull }

146 ed7c8e8d 2003-09-30 devnull 

147 ed7c8e8d 2003-09-30 devnull int

148 ed7c8e8d 2003-09-30 devnull bezsplinepts(Point *pt, int npt, Point **pp)

149 ed7c8e8d 2003-09-30 devnull {

150 ed7c8e8d 2003-09-30 devnull 	Plist l;

151 ed7c8e8d 2003-09-30 devnull 	l.np = 0;

152 ed7c8e8d 2003-09-30 devnull 	l.p = nil;

153 ed7c8e8d 2003-09-30 devnull 	_bezsplinepts(&l, pt, npt);

154 ed7c8e8d 2003-09-30 devnull 	*pp  = l.p;

155 ed7c8e8d 2003-09-30 devnull 	return l.np;

156 ed7c8e8d 2003-09-30 devnull }

157 ed7c8e8d 2003-09-30 devnull 

158 ed7c8e8d 2003-09-30 devnull int

159 ed7c8e8d 2003-09-30 devnull bezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp)

160 ed7c8e8d 2003-09-30 devnull {

161 ed7c8e8d 2003-09-30 devnull 	return bezierop(dst, p0, p1, p2, p3, end0, end1, radius, src, sp, SoverD);

162 ed7c8e8d 2003-09-30 devnull }

163 ed7c8e8d 2003-09-30 devnull 

164 ed7c8e8d 2003-09-30 devnull int

165 ed7c8e8d 2003-09-30 devnull bezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int end0, int end1, int radius, Image *src, Point sp, Drawop op)

166 ed7c8e8d 2003-09-30 devnull {

167 ed7c8e8d 2003-09-30 devnull 	Plist l;

168 ed7c8e8d 2003-09-30 devnull 

169 ed7c8e8d 2003-09-30 devnull 	l.np = 0;

170 ed7c8e8d 2003-09-30 devnull 	bezierpts(&l, p0, p1, p2, p3);

171 ed7c8e8d 2003-09-30 devnull 	if(l.np == -1)

172 ed7c8e8d 2003-09-30 devnull 		return 0;

173 ed7c8e8d 2003-09-30 devnull 	if(l.np != 0){

174 ed7c8e8d 2003-09-30 devnull 		polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, p0), l.p[0]), op);

175 ed7c8e8d 2003-09-30 devnull 		free(l.p);

176 ed7c8e8d 2003-09-30 devnull 	}

177 ed7c8e8d 2003-09-30 devnull 	return 1;

178 ed7c8e8d 2003-09-30 devnull }

179 ed7c8e8d 2003-09-30 devnull 

180 ed7c8e8d 2003-09-30 devnull int

181 ed7c8e8d 2003-09-30 devnull bezspline(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp)

182 ed7c8e8d 2003-09-30 devnull {

183 ed7c8e8d 2003-09-30 devnull 	return bezsplineop(dst, pt, npt, end0, end1, radius, src, sp, SoverD);

184 ed7c8e8d 2003-09-30 devnull }

185 ed7c8e8d 2003-09-30 devnull 

186 ed7c8e8d 2003-09-30 devnull int

187 ed7c8e8d 2003-09-30 devnull bezsplineop(Image *dst, Point *pt, int npt, int end0, int end1, int radius, Image *src, Point sp, Drawop op)

188 ed7c8e8d 2003-09-30 devnull {

189 ed7c8e8d 2003-09-30 devnull 	Plist l;

190 ed7c8e8d 2003-09-30 devnull 

191 ed7c8e8d 2003-09-30 devnull 	l.np = 0;

192 ed7c8e8d 2003-09-30 devnull 	_bezsplinepts(&l, pt, npt);

193 ed7c8e8d 2003-09-30 devnull 	if(l.np==-1)

194 ed7c8e8d 2003-09-30 devnull 		return 0;

195 ed7c8e8d 2003-09-30 devnull 	if(l.np != 0){

196 ed7c8e8d 2003-09-30 devnull 		polyop(dst, l.p, l.np, end0, end1, radius, src, addpt(subpt(sp, pt[0]), l.p[0]), op);

197 ed7c8e8d 2003-09-30 devnull 		free(l.p);

198 ed7c8e8d 2003-09-30 devnull 	}

199 ed7c8e8d 2003-09-30 devnull 	return 1;

200 ed7c8e8d 2003-09-30 devnull }

201 ed7c8e8d 2003-09-30 devnull 

202 ed7c8e8d 2003-09-30 devnull int

203 ed7c8e8d 2003-09-30 devnull fillbezier(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp)

204 ed7c8e8d 2003-09-30 devnull {

205 ed7c8e8d 2003-09-30 devnull 	return fillbezierop(dst, p0, p1, p2, p3, w, src, sp, SoverD);

206 ed7c8e8d 2003-09-30 devnull }

207 ed7c8e8d 2003-09-30 devnull 

208 ed7c8e8d 2003-09-30 devnull int

209 ed7c8e8d 2003-09-30 devnull fillbezierop(Image *dst, Point p0, Point p1, Point p2, Point p3, int w, Image *src, Point sp, Drawop op)

210 ed7c8e8d 2003-09-30 devnull {

211 ed7c8e8d 2003-09-30 devnull 	Plist l;

212 ed7c8e8d 2003-09-30 devnull 

213 ed7c8e8d 2003-09-30 devnull 	l.np = 0;

214 ed7c8e8d 2003-09-30 devnull 	bezierpts(&l, p0, p1, p2, p3);

215 ed7c8e8d 2003-09-30 devnull 	if(l.np == -1)

216 ed7c8e8d 2003-09-30 devnull 		return 0;

217 ed7c8e8d 2003-09-30 devnull 	if(l.np != 0){

218 ed7c8e8d 2003-09-30 devnull 		fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, p0), l.p[0]), op);

219 ed7c8e8d 2003-09-30 devnull 		free(l.p);

220 ed7c8e8d 2003-09-30 devnull 	}

221 ed7c8e8d 2003-09-30 devnull 	return 1;

222 ed7c8e8d 2003-09-30 devnull }

223 ed7c8e8d 2003-09-30 devnull 

224 ed7c8e8d 2003-09-30 devnull int

225 ed7c8e8d 2003-09-30 devnull fillbezspline(Image *dst, Point *pt, int npt, int w, Image *src, Point sp)

226 ed7c8e8d 2003-09-30 devnull {

227 ed7c8e8d 2003-09-30 devnull 	return fillbezsplineop(dst, pt, npt, w, src, sp, SoverD);

228 ed7c8e8d 2003-09-30 devnull }

229 ed7c8e8d 2003-09-30 devnull 

230 ed7c8e8d 2003-09-30 devnull int

231 ed7c8e8d 2003-09-30 devnull fillbezsplineop(Image *dst, Point *pt, int npt, int w, Image *src, Point sp, Drawop op)

232 ed7c8e8d 2003-09-30 devnull {

233 ed7c8e8d 2003-09-30 devnull 	Plist l;

234 ed7c8e8d 2003-09-30 devnull 

235 ed7c8e8d 2003-09-30 devnull 	l.np = 0;

236 ed7c8e8d 2003-09-30 devnull 	_bezsplinepts(&l, pt, npt);

237 ed7c8e8d 2003-09-30 devnull 	if(l.np == -1)

238 ed7c8e8d 2003-09-30 devnull 		return 0;

239 ed7c8e8d 2003-09-30 devnull 	if(l.np > 0){

240 ed7c8e8d 2003-09-30 devnull 		fillpolyop(dst, l.p, l.np, w, src, addpt(subpt(sp, pt[0]), l.p[0]), op);

241 ed7c8e8d 2003-09-30 devnull 		free(l.p);

242 ed7c8e8d 2003-09-30 devnull 	}

243 ed7c8e8d 2003-09-30 devnull 	return 1;

244 ed7c8e8d 2003-09-30 devnull }