1 //---------------------------------------------------------------------------- 2 // Anti-Grain Geometry - Version 2.4 3 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com) 4 // 5 // Permission to copy, use, modify, sell and distribute this software 6 // is granted provided this copyright notice appears in all copies. 7 // This software is provided "as is" without express or implied 8 // warranty, and with no claim as to its suitability for any purpose. 9 // 10 //---------------------------------------------------------------------------- 11 // Contact: mcseem@antigrain.com 12 // mcseemagg@yahoo.com 13 // http://www.antigrain.com 14 //---------------------------------------------------------------------------- 15 // 16 // Stroke math 17 // 18 //---------------------------------------------------------------------------- 19 20 #ifndef AGG_STROKE_MATH_INCLUDED 21 #define AGG_STROKE_MATH_INCLUDED 22 23 #include "agg_math.h" 24 #include "agg_vertex_sequence.h" 25 26 namespace agg 27 { 28 //-------------------------------------------------------------line_cap_e 29 enum line_cap_e 30 { 31 butt_cap, 32 square_cap, 33 round_cap 34 }; 35 36 //------------------------------------------------------------line_join_e 37 enum line_join_e 38 { 39 miter_join = 0, 40 miter_join_revert = 1, 41 round_join = 2, 42 bevel_join = 3, 43 miter_join_round = 4 44 }; 45 46 47 //-----------------------------------------------------------inner_join_e 48 enum inner_join_e 49 { 50 inner_bevel, 51 inner_miter, 52 inner_jag, 53 inner_round 54 }; 55 56 //------------------------------------------------------------math_stroke 57 template<class VertexConsumer> class math_stroke 58 { 59 public: 60 typedef typename VertexConsumer::value_type coord_type; 61 62 math_stroke(); 63 line_cap(line_cap_e lc)64 void line_cap(line_cap_e lc) { m_line_cap = lc; } line_join(line_join_e lj)65 void line_join(line_join_e lj) { m_line_join = lj; } inner_join(inner_join_e ij)66 void inner_join(inner_join_e ij) { m_inner_join = ij; } 67 line_cap()68 line_cap_e line_cap() const { return m_line_cap; } line_join()69 line_join_e line_join() const { return m_line_join; } inner_join()70 inner_join_e inner_join() const { return m_inner_join; } 71 72 void width(double w); miter_limit(double ml)73 void miter_limit(double ml) { m_miter_limit = ml; } 74 void miter_limit_theta(double t); inner_miter_limit(double ml)75 void inner_miter_limit(double ml) { m_inner_miter_limit = ml; } approximation_scale(double as)76 void approximation_scale(double as) { m_approx_scale = as; } 77 width()78 double width() const { return m_width * 2.0; } miter_limit()79 double miter_limit() const { return m_miter_limit; } inner_miter_limit()80 double inner_miter_limit() const { return m_inner_miter_limit; } approximation_scale()81 double approximation_scale() const { return m_approx_scale; } 82 83 void calc_cap(VertexConsumer& vc, 84 const vertex_dist& v0, 85 const vertex_dist& v1, 86 double len); 87 88 void calc_join(VertexConsumer& vc, 89 const vertex_dist& v0, 90 const vertex_dist& v1, 91 const vertex_dist& v2, 92 double len1, 93 double len2); 94 95 private: add_vertex(VertexConsumer & vc,double x,double y)96 AGG_INLINE void add_vertex(VertexConsumer& vc, double x, double y) 97 { 98 vc.add(coord_type(x, y)); 99 } 100 101 void calc_arc(VertexConsumer& vc, 102 double x, double y, 103 double dx1, double dy1, 104 double dx2, double dy2); 105 106 void calc_miter(VertexConsumer& vc, 107 const vertex_dist& v0, 108 const vertex_dist& v1, 109 const vertex_dist& v2, 110 double dx1, double dy1, 111 double dx2, double dy2, 112 line_join_e lj, 113 double mlimit, 114 double dbevel); 115 116 double m_width; 117 double m_width_abs; 118 double m_width_eps; 119 int m_width_sign; 120 double m_miter_limit; 121 double m_inner_miter_limit; 122 double m_approx_scale; 123 line_cap_e m_line_cap; 124 line_join_e m_line_join; 125 inner_join_e m_inner_join; 126 }; 127 128 //----------------------------------------------------------------------- math_stroke()129 template<class VC> math_stroke<VC>::math_stroke() : 130 m_width(0.5), 131 m_width_abs(0.5), 132 m_width_eps(0.5/1024.0), 133 m_width_sign(1), 134 m_miter_limit(4.0), 135 m_inner_miter_limit(1.01), 136 m_approx_scale(1.0), 137 m_line_cap(butt_cap), 138 m_line_join(miter_join), 139 m_inner_join(inner_miter) 140 { 141 } 142 143 //----------------------------------------------------------------------- width(double w)144 template<class VC> void math_stroke<VC>::width(double w) 145 { 146 m_width = w * 0.5; 147 if(m_width < 0) 148 { 149 m_width_abs = -m_width; 150 m_width_sign = -1; 151 } 152 else 153 { 154 m_width_abs = m_width; 155 m_width_sign = 1; 156 } 157 m_width_eps = m_width / 1024.0; 158 } 159 160 //----------------------------------------------------------------------- miter_limit_theta(double t)161 template<class VC> void math_stroke<VC>::miter_limit_theta(double t) 162 { 163 m_miter_limit = 1.0 / sin(t * 0.5) ; 164 } 165 166 //----------------------------------------------------------------------- 167 template<class VC> calc_arc(VC & vc,double x,double y,double dx1,double dy1,double dx2,double dy2)168 void math_stroke<VC>::calc_arc(VC& vc, 169 double x, double y, 170 double dx1, double dy1, 171 double dx2, double dy2) 172 { 173 double a1 = atan2(dy1 * m_width_sign, dx1 * m_width_sign); 174 double a2 = atan2(dy2 * m_width_sign, dx2 * m_width_sign); 175 double da = a1 - a2; 176 int i, n; 177 178 da = acos(m_width_abs / (m_width_abs + 0.125 / m_approx_scale)) * 2; 179 180 add_vertex(vc, x + dx1, y + dy1); 181 if(m_width_sign > 0) 182 { 183 if(a1 > a2) a2 += 2 * pi; 184 n = int((a2 - a1) / da); 185 da = (a2 - a1) / (n + 1); 186 a1 += da; 187 for(i = 0; i < n; i++) 188 { 189 add_vertex(vc, x + cos(a1) * m_width, y + sin(a1) * m_width); 190 a1 += da; 191 } 192 } 193 else 194 { 195 if(a1 < a2) a2 -= 2 * pi; 196 n = int((a1 - a2) / da); 197 da = (a1 - a2) / (n + 1); 198 a1 -= da; 199 for(i = 0; i < n; i++) 200 { 201 add_vertex(vc, x + cos(a1) * m_width, y + sin(a1) * m_width); 202 a1 -= da; 203 } 204 } 205 add_vertex(vc, x + dx2, y + dy2); 206 } 207 208 //----------------------------------------------------------------------- 209 template<class VC> calc_miter(VC & vc,const vertex_dist & v0,const vertex_dist & v1,const vertex_dist & v2,double dx1,double dy1,double dx2,double dy2,line_join_e lj,double mlimit,double dbevel)210 void math_stroke<VC>::calc_miter(VC& vc, 211 const vertex_dist& v0, 212 const vertex_dist& v1, 213 const vertex_dist& v2, 214 double dx1, double dy1, 215 double dx2, double dy2, 216 line_join_e lj, 217 double mlimit, 218 double dbevel) 219 { 220 double xi = v1.x; 221 double yi = v1.y; 222 double di = 1; 223 double lim = m_width_abs * mlimit; 224 bool miter_limit_exceeded = true; // Assume the worst 225 bool intersection_failed = true; // Assume the worst 226 227 if(calc_intersection(v0.x + dx1, v0.y - dy1, 228 v1.x + dx1, v1.y - dy1, 229 v1.x + dx2, v1.y - dy2, 230 v2.x + dx2, v2.y - dy2, 231 &xi, &yi)) 232 { 233 // Calculation of the intersection succeeded 234 //--------------------- 235 di = calc_distance(v1.x, v1.y, xi, yi); 236 if(di <= lim) 237 { 238 // Inside the miter limit 239 //--------------------- 240 add_vertex(vc, xi, yi); 241 miter_limit_exceeded = false; 242 } 243 intersection_failed = false; 244 } 245 else 246 { 247 // Calculation of the intersection failed, most probably 248 // the three points lie one straight line. 249 // First check if v0 and v2 lie on the opposite sides of vector: 250 // (v1.x, v1.y) -> (v1.x+dx1, v1.y-dy1), that is, the perpendicular 251 // to the line determined by vertices v0 and v1. 252 // This condition determines whether the next line segments continues 253 // the previous one or goes back. 254 //---------------- 255 double x2 = v1.x + dx1; 256 double y2 = v1.y - dy1; 257 if((cross_product(v0.x, v0.y, v1.x, v1.y, x2, y2) < 0.0) == 258 (cross_product(v1.x, v1.y, v2.x, v2.y, x2, y2) < 0.0)) 259 { 260 // This case means that the next segment continues 261 // the previous one (straight line) 262 //----------------- 263 add_vertex(vc, v1.x + dx1, v1.y - dy1); 264 miter_limit_exceeded = false; 265 } 266 } 267 268 if(miter_limit_exceeded) 269 { 270 // Miter limit exceeded 271 //------------------------ 272 switch(lj) 273 { 274 case miter_join_revert: 275 // For the compatibility with SVG, PDF, etc, 276 // we use a simple bevel join instead of 277 // "smart" bevel 278 //------------------- 279 add_vertex(vc, v1.x + dx1, v1.y - dy1); 280 add_vertex(vc, v1.x + dx2, v1.y - dy2); 281 break; 282 283 case miter_join_round: 284 calc_arc(vc, v1.x, v1.y, dx1, -dy1, dx2, -dy2); 285 break; 286 287 default: 288 // If no miter-revert, calculate new dx1, dy1, dx2, dy2 289 //---------------- 290 if(intersection_failed) 291 { 292 mlimit *= m_width_sign; 293 add_vertex(vc, v1.x + dx1 + dy1 * mlimit, 294 v1.y - dy1 + dx1 * mlimit); 295 add_vertex(vc, v1.x + dx2 - dy2 * mlimit, 296 v1.y - dy2 - dx2 * mlimit); 297 } 298 else 299 { 300 double x1 = v1.x + dx1; 301 double y1 = v1.y - dy1; 302 double x2 = v1.x + dx2; 303 double y2 = v1.y - dy2; 304 di = (lim - dbevel) / (di - dbevel); 305 add_vertex(vc, x1 + (xi - x1) * di, 306 y1 + (yi - y1) * di); 307 add_vertex(vc, x2 + (xi - x2) * di, 308 y2 + (yi - y2) * di); 309 } 310 break; 311 } 312 } 313 } 314 315 //--------------------------------------------------------stroke_calc_cap 316 template<class VC> calc_cap(VC & vc,const vertex_dist & v0,const vertex_dist & v1,double len)317 void math_stroke<VC>::calc_cap(VC& vc, 318 const vertex_dist& v0, 319 const vertex_dist& v1, 320 double len) 321 { 322 vc.remove_all(); 323 324 double dx1 = (v1.y - v0.y) / len; 325 double dy1 = (v1.x - v0.x) / len; 326 double dx2 = 0; 327 double dy2 = 0; 328 329 dx1 *= m_width; 330 dy1 *= m_width; 331 332 if(m_line_cap != round_cap) 333 { 334 if(m_line_cap == square_cap) 335 { 336 dx2 = dy1 * m_width_sign; 337 dy2 = dx1 * m_width_sign; 338 } 339 add_vertex(vc, v0.x - dx1 - dx2, v0.y + dy1 - dy2); 340 add_vertex(vc, v0.x + dx1 - dx2, v0.y - dy1 - dy2); 341 } 342 else 343 { 344 double da = acos(m_width_abs / (m_width_abs + 0.125 / m_approx_scale)) * 2; 345 double a1; 346 int i; 347 int n = int(pi / da); 348 349 da = pi / (n + 1); 350 add_vertex(vc, v0.x - dx1, v0.y + dy1); 351 if(m_width_sign > 0) 352 { 353 a1 = atan2(dy1, -dx1); 354 a1 += da; 355 for(i = 0; i < n; i++) 356 { 357 add_vertex(vc, v0.x + cos(a1) * m_width, 358 v0.y + sin(a1) * m_width); 359 a1 += da; 360 } 361 } 362 else 363 { 364 a1 = atan2(-dy1, dx1); 365 a1 -= da; 366 for(i = 0; i < n; i++) 367 { 368 add_vertex(vc, v0.x + cos(a1) * m_width, 369 v0.y + sin(a1) * m_width); 370 a1 -= da; 371 } 372 } 373 add_vertex(vc, v0.x + dx1, v0.y - dy1); 374 } 375 } 376 377 //----------------------------------------------------------------------- 378 template<class VC> calc_join(VC & vc,const vertex_dist & v0,const vertex_dist & v1,const vertex_dist & v2,double len1,double len2)379 void math_stroke<VC>::calc_join(VC& vc, 380 const vertex_dist& v0, 381 const vertex_dist& v1, 382 const vertex_dist& v2, 383 double len1, 384 double len2) 385 { 386 double dx1 = m_width * (v1.y - v0.y) / len1; 387 double dy1 = m_width * (v1.x - v0.x) / len1; 388 double dx2 = m_width * (v2.y - v1.y) / len2; 389 double dy2 = m_width * (v2.x - v1.x) / len2; 390 391 vc.remove_all(); 392 393 double cp = cross_product(v0.x, v0.y, v1.x, v1.y, v2.x, v2.y); 394 if ((cp > agg::vertex_dist_epsilon && m_width > 0) || 395 (cp < -agg::vertex_dist_epsilon && m_width < 0)) 396 { 397 // Inner join 398 //--------------- 399 double limit = ((len1 < len2) ? len1 : len2) / m_width_abs; 400 if(limit < m_inner_miter_limit) 401 { 402 limit = m_inner_miter_limit; 403 } 404 405 switch(m_inner_join) 406 { 407 default: // inner_bevel 408 add_vertex(vc, v1.x + dx1, v1.y - dy1); 409 add_vertex(vc, v1.x + dx2, v1.y - dy2); 410 break; 411 412 case inner_miter: 413 calc_miter(vc, 414 v0, v1, v2, dx1, dy1, dx2, dy2, 415 miter_join_revert, 416 limit, 0); 417 break; 418 419 case inner_jag: 420 case inner_round: 421 cp = (dx1-dx2) * (dx1-dx2) + (dy1-dy2) * (dy1-dy2); 422 if(cp < len1 * len1 && cp < len2 * len2) 423 { 424 calc_miter(vc, 425 v0, v1, v2, dx1, dy1, dx2, dy2, 426 miter_join_revert, 427 limit, 0); 428 } 429 else 430 { 431 if(m_inner_join == inner_jag) 432 { 433 add_vertex(vc, v1.x + dx1, v1.y - dy1); 434 add_vertex(vc, v1.x, v1.y ); 435 add_vertex(vc, v1.x + dx2, v1.y - dy2); 436 } 437 else 438 { 439 add_vertex(vc, v1.x + dx1, v1.y - dy1); 440 add_vertex(vc, v1.x, v1.y ); 441 calc_arc(vc, v1.x, v1.y, dx2, -dy2, dx1, -dy1); 442 add_vertex(vc, v1.x, v1.y ); 443 add_vertex(vc, v1.x + dx2, v1.y - dy2); 444 } 445 } 446 break; 447 } 448 } 449 else 450 { 451 // Outer join 452 //--------------- 453 454 // Calculate the distance between v1 and 455 // the central point of the bevel line segment 456 //--------------- 457 double dx = (dx1 + dx2) / 2; 458 double dy = (dy1 + dy2) / 2; 459 double dbevel = sqrt(dx * dx + dy * dy); 460 461 if(m_line_join == round_join || m_line_join == bevel_join) 462 { 463 // This is an optimization that reduces the number of points 464 // in cases of almost collinear segments. If there's no 465 // visible difference between bevel and miter joins we'd rather 466 // use miter join because it adds only one point instead of two. 467 // 468 // Here we calculate the middle point between the bevel points 469 // and then, the distance between v1 and this middle point. 470 // At outer joins this distance always less than stroke width, 471 // because it's actually the height of an isosceles triangle of 472 // v1 and its two bevel points. If the difference between this 473 // width and this value is small (no visible bevel) we can 474 // add just one point. 475 // 476 // The constant in the expression makes the result approximately 477 // the same as in round joins and caps. You can safely comment 478 // out this entire "if". 479 //------------------- 480 if(m_approx_scale * (m_width_abs - dbevel) < m_width_eps) 481 { 482 if(calc_intersection(v0.x + dx1, v0.y - dy1, 483 v1.x + dx1, v1.y - dy1, 484 v1.x + dx2, v1.y - dy2, 485 v2.x + dx2, v2.y - dy2, 486 &dx, &dy)) 487 { 488 add_vertex(vc, dx, dy); 489 } 490 else 491 { 492 add_vertex(vc, v1.x + dx1, v1.y - dy1); 493 } 494 return; 495 } 496 } 497 498 switch(m_line_join) 499 { 500 case miter_join: 501 case miter_join_revert: 502 case miter_join_round: 503 calc_miter(vc, 504 v0, v1, v2, dx1, dy1, dx2, dy2, 505 m_line_join, 506 m_miter_limit, 507 dbevel); 508 break; 509 510 case round_join: 511 calc_arc(vc, v1.x, v1.y, dx1, -dy1, dx2, -dy2); 512 break; 513 514 default: // Bevel join 515 add_vertex(vc, v1.x + dx1, v1.y - dy1); 516 add_vertex(vc, v1.x + dx2, v1.y - dy2); 517 break; 518 } 519 } 520 } 521 522 523 524 525 } 526 527 #endif 528