1/* 2 3LinePathBuilder 4 5Copyright (c) 2002 OpenBeOS. 6 7Author: 8 Michael Pfeiffer 9 10Permission is hereby granted, free of charge, to any person obtaining a copy of 11this software and associated documentation files (the "Software"), to deal in 12the Software without restriction, including without limitation the rights to 13use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies 14of the Software, and to permit persons to whom the Software is furnished to do 15so, subject to the following conditions: 16 17The above copyright notice and this permission notice shall be included in all 18copies or substantial portions of the Software. 19 20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 21IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 22FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 23AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 24LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 25OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 26THE SOFTWARE. 27 28*/ 29 30#include <math.h> 31#include "LinePathBuilder.h" 32 33#include <math.h> 34 35static const float kNearZero = 0.000000000001; 36static const float kMinPenSize = 0.0001; 37 38LinePathBuilder::LinePathBuilder(SubPath *subPath, float penSize, cap_mode capMode, join_mode joinMode, float miterLimit) 39 : fSubPath(subPath) 40 , fPenSize(penSize) 41 , fCapMode(capMode) 42 , fJoinMode(joinMode) 43 , fMiterLimit(miterLimit) 44 , fFirst(true) 45{ 46} 47 48 49// vector of length w/2 in direction of line [a, b] 50bool 51LinePathBuilder::Vector(BPoint a, BPoint b, float w, BPoint &v) 52{ 53 v = b - a; 54 float l = 2.0 * sqrt(v.x * v.x + v.y * v.y); 55 if (fabs(l) <= kNearZero) return false; 56 w /= l; 57 v.x *= w; 58 v.y *= w; 59 return true; 60} 61 62 63// calculate line [pa, pb] parallel to line [a, b] in distance of w/2 64bool 65LinePathBuilder::Parallel(BPoint a, BPoint b, float w, BPoint &pa, BPoint &pb) 66{ 67 BPoint d; 68 if (!Vector(a, b, w, d)) return false; 69 BPoint r(-d.y, d.x); 70 71 pa = a - r; 72 pb = b - r; 73 return true; 74} 75 76 77// calculate intercept point e of lines [a, b] and [c, d] 78bool 79LinePathBuilder::Cut(BPoint a, BPoint b, BPoint c, BPoint d, BPoint &e) 80{ 81 BPoint r = b - a; 82 BPoint s = d - c; 83 BPoint v = c - a; 84 float div = r.x * s.y - r.y * s.x; 85 if (fabs(div) <= kNearZero) return false; 86 float u = (r.y * v.x - r.x * v.y) / div; 87 e.x = c.x + s.x * u; 88 e.y = c.y + s.y * u; 89 return true; 90} 91 92 93void 94LinePathBuilder::RoundCap(BPoint a, BPoint b, BPoint ra, BPoint rb, bool start) 95{ 96 BPoint bezier[3]; 97 BPoint v; 98 if (start) { // first quarter circle 99 Vector(b, a, PenSize(), v); 100 BPoint v055(0.55*v.x, 0.55*v.y); 101 BPoint vr055(-v.y, v.x); 102 bezier[0] = a + v + vr055; 103 bezier[1] = ra + v055; 104 bezier[2] = ra; 105 AddPoint(a+v); 106 BezierTo(bezier); 107 } else { // second quarter circle 108 Vector(a, b, PenSize(), v); 109 BPoint v055(0.55*v.x, 0.55*v.y); 110 BPoint vr055(v.y, -v.x); 111 bezier[0] = rb + v055; 112 bezier[1] = b + v + vr055; 113 bezier[2] = b + v; 114 AddPoint(rb); 115 BezierTo(bezier); 116 } 117} 118 119 120void 121LinePathBuilder::Corner(BPoint a, BPoint b, bool start) 122{ 123 BPoint ra, rb, r; 124 if (Parallel(a, b, PenSize(), ra, rb)) { 125 BPoint v; 126 switch (LineCapMode()) { 127 case B_ROUND_CAP: 128 RoundCap(a, b, ra, rb, start); 129 return; 130 case B_BUTT_CAP: // nothing to do 131 break; 132 case B_SQUARE_CAP: 133 Vector(a, b, PenSize(), v); 134 ra -= v; 135 rb += v; 136 break; 137 } 138 if (start) r = ra; else r = rb; 139 AddPoint(r); 140 } 141} 142 143 144bool 145LinePathBuilder::Inside(BPoint a, BPoint b, BPoint r) 146{ 147 BPoint v; 148 Vector(a, b, 2.0, v); 149 150 if (kNearZero <= fabs(v.x)) return (r.x - b.x) / v.x <= 0.0; 151 else if (kNearZero <= fabs(v.y)) return (r.y - b.y) / v.y <= 0.0; 152 else return false; // should not reach here (length of v > 0.0!) 153} 154 155 156bool 157LinePathBuilder::InMiterLimit(BPoint a, BPoint b) 158{ 159 BPoint d = a - b; 160 return 2.0*sqrt(d.x*d.x + d.y*d.y)/PenSize() <= LineMiterLimit(); 161} 162 163 164void 165LinePathBuilder::RoundJoin(BPoint p[4]) 166{ 167 BPoint v[2]; 168 Vector(p[0], p[1], PenSize() * 0.63, v[0]); 169 Vector(p[3], p[2], PenSize() * 0.63, v[1]); 170 AddPoint(p[1]); 171 BPoint bezier[3] = {p[1]+v[0], p[2]+v[1], p[2] }; 172 BezierTo(bezier); 173} 174 175 176void 177LinePathBuilder::Connect(BPoint a, BPoint b, BPoint c) 178{ 179 BPoint p[4], r, v; 180 if (Parallel(a, b, PenSize(), p[0], p[1]) && 181 Parallel(b, c, PenSize(), p[2], p[3]) && 182 Cut(p[0], p[1], p[2], p[3], r)) { 183 184 185 186 if (LineJoinMode() != B_BUTT_JOIN && 187 LineJoinMode() != B_SQUARE_JOIN && 188 Inside(p[0], p[1], r)) { 189 if (!Inside(p[1], p[0], r) || !Inside(p[2], p[3], r)) { 190 AddPoint(p[1]); AddPoint(p[2]); 191 } else { 192 AddPoint(r); 193 } 194 return; 195 } 196 197 switch (LineJoinMode()) { 198 case B_ROUND_JOIN: 199 RoundJoin(p); 200 break; 201 case B_MITER_JOIN: 202 if (InMiterLimit(b, r)) { 203 AddPoint(r); 204 break; 205 } 206 // fall through 207 case B_BEVEL_JOIN: 208 AddPoint(p[1]); AddPoint(p[2]); 209 break; 210 case B_BUTT_JOIN: // ??? 211 AddPoint(p[1]); AddPoint(b); AddPoint(p[2]); 212 break; 213 case B_SQUARE_JOIN: // ??? 214 Vector(a, b, PenSize(), v); 215 AddPoint(p[1] + v); AddPoint(b + v); 216 Vector(b, c, PenSize(), v); 217 AddPoint(b - v); AddPoint(p[2] - v); 218 break; 219 } 220 } 221} 222 223 224bool 225LinePathBuilder::IdenticalPoints(int i, int j) 226{ 227 BPoint d = fSubPath->PointAt(i) - fSubPath->PointAt(j); 228 return d.x * d.x + d.y * d.y < kNearZero; 229} 230 231 232// remove identical points 233void 234LinePathBuilder::OptimizeSubPath() 235{ 236 int i, j = 0; 237 const int n = fSubPath->CountPoints(); 238 for (i = 1; i < n; i++) { 239 if (!IdenticalPoints(i, j)) { 240 fSubPath->AtPut(++j, fSubPath->PointAt(i)); 241 } 242 } 243 fSubPath->Truncate(i-j-1); 244 245 // check also first point == last point if path is closed 246 if (fSubPath->IsClosed() && fSubPath->CountPoints() >= 2) { 247 const int n = fSubPath->CountPoints()-1; 248 if (IdenticalPoints(0, n)) fSubPath->Truncate(1); 249 } 250} 251 252 253BPoint 254LinePathBuilder::PointAt(int i) 255{ 256 const int n = fSubPath->CountPoints(); 257 return fSubPath->PointAt((i+n) % n); 258} 259 260 261void 262LinePathBuilder::AddPoint(BPoint p) 263{ 264 if (fFirst) { 265 fFirst = false; 266 MoveTo(p); 267 } else { 268 LineTo(p); 269 } 270} 271 272 273void 274LinePathBuilder::CreateLinePath() 275{ 276 OptimizeSubPath(); 277 if (fPenSize < kMinPenSize) fPenSize = kMinPenSize; 278 279 const bool start = true; 280 const bool end = false; 281 const int n = fSubPath->CountPoints(); 282 283 if (n < 2) return; 284 285 bool is_closed = fSubPath->IsClosed() && n != 2; 286 287 if (fSubPath->IsClosed() && n == 2) { 288 switch (LineJoinMode()) { 289 case B_ROUND_JOIN: 290 fCapMode = B_ROUND_CAP; 291 break; 292 case B_MITER_JOIN: // fall through 293 case B_BEVEL_JOIN: // fall through 294 case B_BUTT_JOIN: 295 fCapMode = B_BUTT_CAP; 296 break; 297 case B_SQUARE_JOIN: 298 fCapMode = B_SQUARE_CAP; 299 break; 300 } 301 } 302 303 // ahead 304 if (is_closed) { 305 Connect(PointAt(n-1), PointAt(0), PointAt(1)); 306 } else { 307 Corner(PointAt(0), PointAt(1), start); 308 } 309 310 for (int i = 1; i < n-1; i++) { 311 Connect(PointAt(i-1), PointAt(i), PointAt(i+1)); 312 } 313 314 if (is_closed) { 315 Connect(PointAt(n-2), PointAt(n-1), PointAt(n)); 316 Connect(PointAt(n-1), PointAt(n), PointAt(n+1)); 317 } else { 318 Corner(PointAt(n-2), PointAt(n-1), end); 319 } 320 321 // and back 322 if (is_closed) { 323 ClosePath(); fFirst = true; 324 Connect(PointAt(n+1), PointAt(n), PointAt(n-1)); 325 Connect(PointAt(n), PointAt(n-1), PointAt(n-2)); 326 } else { 327 Corner(PointAt(n-1), PointAt(n-2), start); 328 } 329 330 for (int i = n-2; i >= 1; i--) { 331 Connect(PointAt(i+1), PointAt(i), PointAt(i-1)); 332 } 333 334 if (is_closed) { 335 Connect(PointAt(1), PointAt(0), PointAt(n-1)); 336 } else { 337 Corner(PointAt(1), PointAt(0), end); 338 } 339 ClosePath(); 340} 341 342