1 #define __NR_PATH_C__
3 /*
4 * Pixel buffer rendering library
5 *
6 * Authors:
7 * Lauris Kaplinski <lauris@kaplinski.com>
8 *
9 * This code is in public domain
10 */
12 #include <glib/gmem.h>
13 #include "n-art-bpath.h"
14 #include "nr-rect.h"
15 #include "nr-path.h"
17 static void nr_curve_bbox (NR::Coord x000, NR::Coord y000, NR::Coord x001, NR::Coord y001, NR::Coord x011, NR::Coord y011, NR::Coord x111, NR::Coord y111, NRRect *bbox);
19 static void nr_curve_bbox(NR::Point const p000, NR::Point const p001,
20 NR::Point const p011, NR::Point const p111,
21 NRRect *bbox);
23 NRBPath *nr_path_duplicate_transform(NRBPath *d, NRBPath *s, NR::Matrix const *transform)
24 {
25 int i;
27 if (!s->path) {
28 d->path = NULL;
29 return d;
30 }
32 i = 0;
33 while (s->path[i].code != NR_END) i += 1;
35 d->path = g_new (NArtBpath, i + 1);
37 i = 0;
38 while (s->path[i].code != NR_END) {
39 d->path[i].code = s->path[i].code;
40 if (s->path[i].code == NR_CURVETO) {
41 d->path[i].setC(1, s->path[i].c(1) * (*transform));
42 d->path[i].setC(2, s->path[i].c(2) * (*transform));
43 }
44 d->path[i].setC(3, s->path[i].c(3) * (*transform));
45 i += 1;
46 }
47 d->path[i].code = NR_END;
49 return d;
50 }
52 NRBPath *nr_path_duplicate_transform(NRBPath *d, NRBPath *s, NR::Matrix const transform) {
53 NR::Matrix tr = transform;
54 return nr_path_duplicate_transform(d, s, &tr);
55 }
57 NArtBpath* nr_artpath_affine(NArtBpath *s, NR::Matrix const &aff) {
58 NRBPath bp, abp;
59 bp.path = s;
60 nr_path_duplicate_transform(&abp, &bp, aff);
61 return abp.path;
62 }
64 static void
65 nr_line_wind_distance (NR::Coord x0, NR::Coord y0, NR::Coord x1, NR::Coord y1, NR::Point &pt, int *wind, NR::Coord *best)
66 {
67 NR::Coord Ax, Ay, Bx, By, Dx, Dy, s;
68 NR::Coord dist2;
70 /* Find distance */
71 Ax = x0;
72 Ay = y0;
73 Bx = x1;
74 By = y1;
75 Dx = x1 - x0;
76 Dy = y1 - y0;
77 const NR::Coord Px = pt[NR::X];
78 const NR::Coord Py = pt[NR::Y];
80 if (best) {
81 s = ((Px - Ax) * Dx + (Py - Ay) * Dy) / (Dx * Dx + Dy * Dy);
82 if (s <= 0.0) {
83 dist2 = (Px - Ax) * (Px - Ax) + (Py - Ay) * (Py - Ay);
84 } else if (s >= 1.0) {
85 dist2 = (Px - Bx) * (Px - Bx) + (Py - By) * (Py - By);
86 } else {
87 NR::Coord Qx, Qy;
88 Qx = Ax + s * Dx;
89 Qy = Ay + s * Dy;
90 dist2 = (Px - Qx) * (Px - Qx) + (Py - Qy) * (Py - Qy);
91 }
93 if (dist2 < (*best * *best)) *best = sqrt (dist2);
94 }
96 if (wind) {
97 /* Find wind */
98 if ((Ax >= Px) && (Bx >= Px)) return;
99 if ((Ay >= Py) && (By >= Py)) return;
100 if ((Ay < Py) && (By < Py)) return;
101 if (Ay == By) return;
102 /* Ctach upper y bound */
103 if (Ay == Py) {
104 if (Ax < Px) *wind -= 1;
105 return;
106 } else if (By == Py) {
107 if (Bx < Px) *wind += 1;
108 return;
109 } else {
110 NR::Coord Qx;
111 /* Have to calculate intersection */
112 Qx = Ax + Dx * (Py - Ay) / Dy;
113 if (Qx < Px) {
114 *wind += (Dy > 0.0) ? 1 : -1;
115 }
116 }
117 }
118 }
120 static void
121 nr_curve_bbox_wind_distance (NR::Coord x000, NR::Coord y000,
122 NR::Coord x001, NR::Coord y001,
123 NR::Coord x011, NR::Coord y011,
124 NR::Coord x111, NR::Coord y111,
125 NR::Point &pt,
126 NRRect *bbox, int *wind, NR::Coord *best,
127 NR::Coord tolerance)
128 {
129 NR::Coord x0, y0, x1, y1, len2;
130 int needdist, needwind, needline;
132 const NR::Coord Px = pt[NR::X];
133 const NR::Coord Py = pt[NR::Y];
135 needdist = 0;
136 needwind = 0;
137 needline = 0;
139 if (bbox) nr_curve_bbox (x000, y000, x001, y001, x011, y011, x111, y111, bbox);
141 x0 = MIN (x000, x001);
142 x0 = MIN (x0, x011);
143 x0 = MIN (x0, x111);
144 y0 = MIN (y000, y001);
145 y0 = MIN (y0, y011);
146 y0 = MIN (y0, y111);
147 x1 = MAX (x000, x001);
148 x1 = MAX (x1, x011);
149 x1 = MAX (x1, x111);
150 y1 = MAX (y000, y001);
151 y1 = MAX (y1, y011);
152 y1 = MAX (y1, y111);
154 if (best) {
155 /* Quicly adjust to endpoints */
156 len2 = (x000 - Px) * (x000 - Px) + (y000 - Py) * (y000 - Py);
157 if (len2 < (*best * *best)) *best = (NR::Coord) sqrt (len2);
158 len2 = (x111 - Px) * (x111 - Px) + (y111 - Py) * (y111 - Py);
159 if (len2 < (*best * *best)) *best = (NR::Coord) sqrt (len2);
161 if (((x0 - Px) < *best) && ((y0 - Py) < *best) && ((Px - x1) < *best) && ((Py - y1) < *best)) {
162 /* Point is inside sloppy bbox */
163 /* Now we have to decide, whether subdivide */
164 /* fixme: (Lauris) */
165 if (((y1 - y0) > 5.0) || ((x1 - x0) > 5.0)) {
166 needdist = 1;
167 } else {
168 needline = 1;
169 }
170 }
171 }
172 if (!needdist && wind) {
173 if ((y1 >= Py) && (y0 < Py) && (x0 < Px)) {
174 /* Possible intersection at the left */
175 /* Now we have to decide, whether subdivide */
176 /* fixme: (Lauris) */
177 if (((y1 - y0) > 5.0) || ((x1 - x0) > 5.0)) {
178 needwind = 1;
179 } else {
180 needline = 1;
181 }
182 }
183 }
185 if (needdist || needwind) {
186 NR::Coord x00t, x0tt, xttt, x1tt, x11t, x01t;
187 NR::Coord y00t, y0tt, yttt, y1tt, y11t, y01t;
188 NR::Coord s, t;
190 t = 0.5;
191 s = 1 - t;
193 x00t = s * x000 + t * x001;
194 x01t = s * x001 + t * x011;
195 x11t = s * x011 + t * x111;
196 x0tt = s * x00t + t * x01t;
197 x1tt = s * x01t + t * x11t;
198 xttt = s * x0tt + t * x1tt;
200 y00t = s * y000 + t * y001;
201 y01t = s * y001 + t * y011;
202 y11t = s * y011 + t * y111;
203 y0tt = s * y00t + t * y01t;
204 y1tt = s * y01t + t * y11t;
205 yttt = s * y0tt + t * y1tt;
207 nr_curve_bbox_wind_distance (x000, y000, x00t, y00t, x0tt, y0tt, xttt, yttt, pt, NULL, wind, best, tolerance);
208 nr_curve_bbox_wind_distance (xttt, yttt, x1tt, y1tt, x11t, y11t, x111, y111, pt, NULL, wind, best, tolerance);
209 } else if (1 || needline) {
210 nr_line_wind_distance (x000, y000, x111, y111, pt, wind, best);
211 }
212 }
214 void
215 nr_path_matrix_point_bbox_wind_distance (NRBPath *bpath, NR::Matrix const &m, NR::Point &pt,
216 NRRect *bbox, int *wind, NR::Coord *dist,
217 NR::Coord tolerance, NR::Rect *viewbox)
218 {
219 if (!bpath->path) {
220 if (wind) *wind = 0;
221 if (dist) *dist = NR_HUGE;
222 return;
223 }
225 NR::Coord x0 = 0;
226 NR::Coord y0 = 0;
227 NR::Coord x1 = 0;
228 NR::Coord y1 = 0;
229 NR::Coord x2 = 0;
230 NR::Coord y2 = 0;
231 NR::Coord x3 = 0;
232 NR::Coord y3 = 0;
234 // remembering the start of subpath
235 NR::Coord x_start = 0, y_start = 0; bool start_set = false;
236 NR::Rect swept;
238 for (const NArtBpath *p = bpath->path; p->code != NR_END; p+= 1) {
239 switch (p->code) {
240 case NR_MOVETO_OPEN:
241 case NR_MOVETO:
242 if (start_set) { // this is a new subpath
243 if (wind && (x0 != x_start || y0 != y_start)) // for correct fill picking, each subpath must be closed
244 nr_line_wind_distance (x0, y0, x_start, y_start, pt, wind, dist);
245 }
246 x0 = m[0] * p->x3 + m[2] * p->y3 + m[4];
247 y0 = m[1] * p->x3 + m[3] * p->y3 + m[5];
248 x_start = x0; y_start = y0; start_set = true;
249 if (bbox) {
250 bbox->x0 = (NR::Coord) MIN (bbox->x0, x0);
251 bbox->y0 = (NR::Coord) MIN (bbox->y0, y0);
252 bbox->x1 = (NR::Coord) MAX (bbox->x1, x0);
253 bbox->y1 = (NR::Coord) MAX (bbox->y1, y0);
254 }
255 break;
256 case NR_LINETO:
257 x3 = m[0] * p->x3 + m[2] * p->y3 + m[4];
258 y3 = m[1] * p->x3 + m[3] * p->y3 + m[5];
259 if (bbox) {
260 bbox->x0 = (NR::Coord) MIN (bbox->x0, x3);
261 bbox->y0 = (NR::Coord) MIN (bbox->y0, y3);
262 bbox->x1 = (NR::Coord) MAX (bbox->x1, x3);
263 bbox->y1 = (NR::Coord) MAX (bbox->y1, y3);
264 }
265 if (dist || wind) {
266 if (wind) { // we need to pick fill, so do what we're told
267 nr_line_wind_distance (x0, y0, x3, y3, pt, wind, dist);
268 } else { // only stroke is being picked; skip this segment if it's totally outside the viewbox
269 swept = NR::Rect(NR::Point(x0, y0), NR::Point(x3, y3));
270 //std::cout << "swept: " << swept;
271 //std::cout << "view: " << *viewbox;
272 //std::cout << "intersects? " << (swept.intersects(*viewbox)? "YES" : "NO") << "\n";
273 if (!viewbox || swept.intersects(*viewbox))
274 nr_line_wind_distance (x0, y0, x3, y3, pt, wind, dist);
275 }
276 }
277 x0 = x3;
278 y0 = y3;
279 break;
280 case NR_CURVETO:
281 {
282 x3 = m[0] * p->x3 + m[2] * p->y3 + m[4];
283 y3 = m[1] * p->x3 + m[3] * p->y3 + m[5];
284 x1 = m[0] * p->x1 + m[2] * p->y1 + m[4];
285 y1 = m[1] * p->x1 + m[3] * p->y1 + m[5];
286 x2 = m[0] * p->x2 + m[2] * p->y2 + m[4];
287 y2 = m[1] * p->x2 + m[3] * p->y2 + m[5];
289 swept = NR::Rect(NR::Point(x0, y0), NR::Point(x3, y3));
290 swept.expandTo(NR::Point(x1, y1));
291 swept.expandTo(NR::Point(x2, y2));
293 if (!viewbox || swept.intersects(*viewbox)) { // we see this segment, so do full processing
294 nr_curve_bbox_wind_distance (
295 x0, y0,
296 x1, y1,
297 x2, y2,
298 x3, y3,
299 pt,
300 bbox, wind, dist, tolerance);
301 } else {
302 if (wind) { // if we need fill, we can just pretend it's a straight line
303 nr_line_wind_distance (x0, y0, x3, y3, pt, wind, dist);
304 } else { // otherwise, skip it completely
305 }
306 }
307 x0 = x3;
308 y0 = y3;
309 }
310 break;
311 default:
312 break;
313 }
314 }
316 if (start_set) {
317 if (wind && (x0 != x_start || y0 != y_start)) // for correct picking, each subpath must be closed
318 nr_line_wind_distance (x0, y0, x_start, y_start, pt, wind, dist);
319 }
320 }
322 static void
323 nr_curve_bbox(NR::Point const p000, NR::Point const p001,
324 NR::Point const p011, NR::Point const p111,
325 NRRect *bbox)
326 {
327 using NR::X;
328 using NR::Y;
330 nr_curve_bbox(p000[X], p000[Y],
331 p001[X], p001[Y],
332 p011[X], p011[Y],
333 p111[X], p111[Y],
334 bbox);
335 }
337 /* Fast bbox calculation */
338 /* Thanks to Nathan Hurst for suggesting it */
340 static void
341 nr_curve_bbox (NR::Coord x000, NR::Coord y000, NR::Coord x001, NR::Coord y001, NR::Coord x011, NR::Coord y011, NR::Coord x111, NR::Coord y111, NRRect *bbox)
342 {
343 NR::Coord a, b, c, D;
345 bbox->x0 = (NR::Coord) MIN (bbox->x0, x111);
346 bbox->y0 = (NR::Coord) MIN (bbox->y0, y111);
347 bbox->x1 = (NR::Coord) MAX (bbox->x1, x111);
348 bbox->y1 = (NR::Coord) MAX (bbox->y1, y111);
350 /*
351 * xttt = s * (s * (s * x000 + t * x001) + t * (s * x001 + t * x011)) + t * (s * (s * x001 + t * x011) + t * (s * x011 + t * x111))
352 * xttt = s * (s2 * x000 + s * t * x001 + t * s * x001 + t2 * x011) + t * (s2 * x001 + s * t * x011 + t * s * x011 + t2 * x111)
353 * xttt = s * (s2 * x000 + 2 * st * x001 + t2 * x011) + t * (s2 * x001 + 2 * st * x011 + t2 * x111)
354 * xttt = s3 * x000 + 2 * s2t * x001 + st2 * x011 + s2t * x001 + 2st2 * x011 + t3 * x111
355 * xttt = s3 * x000 + 3s2t * x001 + 3st2 * x011 + t3 * x111
356 * xttt = s3 * x000 + (1 - s) 3s2 * x001 + (1 - s) * (1 - s) * 3s * x011 + (1 - s) * (1 - s) * (1 - s) * x111
357 * xttt = s3 * x000 + (3s2 - 3s3) * x001 + (3s - 6s2 + 3s3) * x011 + (1 - 2s + s2 - s + 2s2 - s3) * x111
358 * xttt = (x000 - 3 * x001 + 3 * x011 - x111) * s3 +
359 * ( 3 * x001 - 6 * x011 + 3 * x111) * s2 +
360 * ( 3 * x011 - 3 * x111) * s +
361 * ( x111)
362 * xttt' = (3 * x000 - 9 * x001 + 9 * x011 - 3 * x111) * s2 +
363 * ( 6 * x001 - 12 * x011 + 6 * x111) * s +
364 * ( 3 * x011 - 3 * x111)
365 */
367 a = 3 * x000 - 9 * x001 + 9 * x011 - 3 * x111;
368 b = 6 * x001 - 12 * x011 + 6 * x111;
369 c = 3 * x011 - 3 * x111;
371 /*
372 * s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a;
373 */
374 if (fabs (a) < NR_EPSILON) {
375 /* s = -c / b */
376 if (fabs (b) > NR_EPSILON) {
377 double s, t, xttt;
378 s = -c / b;
379 if ((s > 0.0) && (s < 1.0)) {
380 t = 1.0 - s;
381 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
382 bbox->x0 = (float) MIN (bbox->x0, xttt);
383 bbox->x1 = (float) MAX (bbox->x1, xttt);
384 }
385 }
386 } else {
387 /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
388 D = b * b - 4 * a * c;
389 if (D >= 0.0) {
390 NR::Coord d, s, t, xttt;
391 /* Have solution */
392 d = sqrt (D);
393 s = (-b + d) / (2 * a);
394 if ((s > 0.0) && (s < 1.0)) {
395 t = 1.0 - s;
396 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
397 bbox->x0 = (NR::Coord) MIN (bbox->x0, xttt);
398 bbox->x1 = (NR::Coord) MAX (bbox->x1, xttt);
399 }
400 s = (-b - d) / (2 * a);
401 if ((s > 0.0) && (s < 1.0)) {
402 t = 1.0 - s;
403 xttt = s * s * s * x000 + 3 * s * s * t * x001 + 3 * s * t * t * x011 + t * t * t * x111;
404 bbox->x0 = (NR::Coord) MIN (bbox->x0, xttt);
405 bbox->x1 = (NR::Coord) MAX (bbox->x1, xttt);
406 }
407 }
408 }
410 a = 3 * y000 - 9 * y001 + 9 * y011 - 3 * y111;
411 b = 6 * y001 - 12 * y011 + 6 * y111;
412 c = 3 * y011 - 3 * y111;
414 if (fabs (a) < NR_EPSILON) {
415 /* s = -c / b */
416 if (fabs (b) > NR_EPSILON) {
417 double s, t, yttt;
418 s = -c / b;
419 if ((s > 0.0) && (s < 1.0)) {
420 t = 1.0 - s;
421 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
422 bbox->y0 = (float) MIN (bbox->y0, yttt);
423 bbox->y1 = (float) MAX (bbox->y1, yttt);
424 }
425 }
426 } else {
427 /* s = (-b +/- sqrt (b * b - 4 * a * c)) / 2 * a; */
428 D = b * b - 4 * a * c;
429 if (D >= 0.0) {
430 NR::Coord d, s, t, yttt;
431 /* Have solution */
432 d = sqrt (D);
433 s = (-b + d) / (2 * a);
434 if ((s > 0.0) && (s < 1.0)) {
435 t = 1.0 - s;
436 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
437 bbox->y0 = (NR::Coord) MIN (bbox->y0, yttt);
438 bbox->y1 = (NR::Coord) MAX (bbox->y1, yttt);
439 }
440 s = (-b - d) / (2 * a);
441 if ((s > 0.0) && (s < 1.0)) {
442 t = 1.0 - s;
443 yttt = s * s * s * y000 + 3 * s * s * t * y001 + 3 * s * t * t * y011 + t * t * t * y111;
444 bbox->y0 = (NR::Coord) MIN (bbox->y0, yttt);
445 bbox->y1 = (NR::Coord) MAX (bbox->y1, yttt);
446 }
447 }
448 }
449 }
451 void
452 nr_path_matrix_bbox_union(NRBPath const *bpath, NR::Matrix const &m,
453 NRRect *bbox)
454 {
455 using NR::X;
456 using NR::Y;
458 if (!bpath->path) {
459 return;
460 }
462 NR::Point prev0(0, 0);
463 for (NArtBpath const *p = bpath->path; p->code != NR_END; ++p) {
464 switch (p->code) {
465 case NR_MOVETO_OPEN:
466 case NR_MOVETO: {
467 NR::Point const c3(p->x3,
468 p->y3);
469 prev0 = c3 * m;
470 nr_rect_union_pt(bbox, prev0);
471 break;
472 }
474 case NR_LINETO: {
475 NR::Point const c3(p->x3,
476 p->y3);
477 NR::Point const endPt( c3 * m );
478 nr_rect_union_pt(bbox, endPt);
479 prev0 = endPt;
480 break;
481 }
483 case NR_CURVETO: {
484 NR::Point const c1(p->x1, p->y1);
485 NR::Point const c2(p->x2, p->y2);
486 NR::Point const c3(p->x3, p->y3);
487 NR::Point const endPt( c3 * m );
488 nr_curve_bbox(prev0,
489 c1 * m,
490 c2 * m,
491 endPt,
492 bbox);
493 prev0 = endPt;
494 break;
495 }
497 default:
498 break;
499 }
500 }
501 }
503 NArtBpath *nr_path_from_rect(NRRect const &r)
504 {
505 NArtBpath *path = g_new (NArtBpath, 6);
507 path[0].code = NR_MOVETO;
508 path[0].setC(3, NR::Point(r.x0, r.y0));
509 path[1].code = NR_LINETO;
510 path[1].setC(3, NR::Point(r.x1, r.y0));
511 path[2].code = NR_LINETO;
512 path[2].setC(3, NR::Point(r.x1, r.y1));
513 path[3].code = NR_LINETO;
514 path[3].setC(3, NR::Point(r.x0, r.y1));
515 path[4].code = NR_LINETO;
516 path[4].setC(3, NR::Point(r.x0, r.y0));
517 path[5].code = NR_END;
519 return path;
520 }