1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 // MARKER(update_precomp.py): autogen include statement, do not remove 25 #include "precompiled_basegfx.hxx" 26 #include <basegfx/polygon/b2dpolygonclipper.hxx> 27 #include <osl/diagnose.h> 28 #include <basegfx/polygon/b2dpolygontools.hxx> 29 #include <basegfx/numeric/ftools.hxx> 30 #include <basegfx/matrix/b2dhommatrix.hxx> 31 #include <basegfx/polygon/b2dpolypolygoncutter.hxx> 32 #include <basegfx/polygon/b2dpolygoncutandtouch.hxx> 33 #include <basegfx/polygon/b2dpolypolygontools.hxx> 34 #include <basegfx/curve/b2dcubicbezier.hxx> 35 #include <basegfx/tools/rectcliptools.hxx> 36 #include <basegfx/matrix/b2dhommatrixtools.hxx> 37 38 ////////////////////////////////////////////////////////////////////////////// 39 40 namespace basegfx 41 { 42 namespace tools 43 { clipPolygonOnParallelAxis(const B2DPolygon & rCandidate,bool bParallelToXAxis,bool bAboveAxis,double fValueOnOtherAxis,bool bStroke)44 B2DPolyPolygon clipPolygonOnParallelAxis(const B2DPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke) 45 { 46 B2DPolyPolygon aRetval; 47 48 if(rCandidate.count()) 49 { 50 const B2DRange aCandidateRange(getRange(rCandidate)); 51 52 if(bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinY(), fValueOnOtherAxis)) 53 { 54 // completely above and on the clip line. also true for curves. 55 if(bAboveAxis) 56 { 57 // add completely 58 aRetval.append(rCandidate); 59 } 60 } 61 else if(bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxY(), fValueOnOtherAxis)) 62 { 63 // completely below and on the clip line. also true for curves. 64 if(!bAboveAxis) 65 { 66 // add completely 67 aRetval.append(rCandidate); 68 } 69 } 70 else if(!bParallelToXAxis && fTools::moreOrEqual(aCandidateRange.getMinX(), fValueOnOtherAxis)) 71 { 72 // completely right of and on the clip line. also true for curves. 73 if(bAboveAxis) 74 { 75 // add completely 76 aRetval.append(rCandidate); 77 } 78 } 79 else if(!bParallelToXAxis && fTools::lessOrEqual(aCandidateRange.getMaxX(), fValueOnOtherAxis)) 80 { 81 // completely left of and on the clip line. also true for curves. 82 if(!bAboveAxis) 83 { 84 // add completely 85 aRetval.append(rCandidate); 86 } 87 } 88 else 89 { 90 // add cuts with axis to polygon, including bezier segments 91 // Build edge to cut with. Make it a little big longer than needed for 92 // numerical stability. We want to cut against the edge seen as endless 93 // ray here, but addPointsAtCuts() will limit itself to the 94 // edge's range ]0.0 .. 1.0[. 95 const double fSmallExtension((aCandidateRange.getWidth() + aCandidateRange.getHeight()) * (0.5 * 0.1)); 96 const B2DPoint aStart( 97 bParallelToXAxis ? aCandidateRange.getMinX() - fSmallExtension : fValueOnOtherAxis, 98 bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMinY() - fSmallExtension); 99 const B2DPoint aEnd( 100 bParallelToXAxis ? aCandidateRange.getMaxX() + fSmallExtension : fValueOnOtherAxis, 101 bParallelToXAxis ? fValueOnOtherAxis : aCandidateRange.getMaxY() + fSmallExtension); 102 const B2DPolygon aCandidate(addPointsAtCuts(rCandidate, aStart, aEnd)); 103 const sal_uInt32 nPointCount(aCandidate.count()); 104 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 105 B2DCubicBezier aEdge; 106 B2DPolygon aRun; 107 108 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 109 { 110 aCandidate.getBezierSegment(a, aEdge); 111 const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5)); 112 const bool bInside(bParallelToXAxis ? 113 fTools::moreOrEqual(aTestPoint.getY(), fValueOnOtherAxis) == bAboveAxis : 114 fTools::moreOrEqual(aTestPoint.getX(), fValueOnOtherAxis) == bAboveAxis); 115 116 if(bInside) 117 { 118 if(!aRun.count() || !aRun.getB2DPoint(aRun.count() - 1).equal(aEdge.getStartPoint())) 119 { 120 aRun.append(aEdge.getStartPoint()); 121 } 122 123 if(aEdge.isBezier()) 124 { 125 aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint()); 126 } 127 else 128 { 129 aRun.append(aEdge.getEndPoint()); 130 } 131 } 132 else 133 { 134 if(bStroke && aRun.count()) 135 { 136 aRetval.append(aRun); 137 aRun.clear(); 138 } 139 } 140 } 141 142 if(aRun.count()) 143 { 144 if(bStroke) 145 { 146 // try to merge this last and first polygon; they may have been 147 // the former polygon's start/end point 148 if(aRetval.count()) 149 { 150 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0)); 151 152 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1))) 153 { 154 // append start polygon to aRun, remove from result set 155 aRun.append(aStartPolygon); aRun.removeDoublePoints(); 156 aRetval.remove(0); 157 } 158 } 159 160 aRetval.append(aRun); 161 } 162 else 163 { 164 // set closed flag and correct last point (which is added double now). 165 closeWithGeometryChange(aRun); 166 aRetval.append(aRun); 167 } 168 } 169 } 170 } 171 172 return aRetval; 173 } 174 clipPolyPolygonOnParallelAxis(const B2DPolyPolygon & rCandidate,bool bParallelToXAxis,bool bAboveAxis,double fValueOnOtherAxis,bool bStroke)175 B2DPolyPolygon clipPolyPolygonOnParallelAxis(const B2DPolyPolygon& rCandidate, bool bParallelToXAxis, bool bAboveAxis, double fValueOnOtherAxis, bool bStroke) 176 { 177 const sal_uInt32 nPolygonCount(rCandidate.count()); 178 B2DPolyPolygon aRetval; 179 180 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 181 { 182 const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnParallelAxis(rCandidate.getB2DPolygon(a), bParallelToXAxis, bAboveAxis, fValueOnOtherAxis, bStroke)); 183 184 if(aClippedPolyPolygon.count()) 185 { 186 aRetval.append(aClippedPolyPolygon); 187 } 188 } 189 190 return aRetval; 191 } 192 clipPolygonOnRange(const B2DPolygon & rCandidate,const B2DRange & rRange,bool bInside,bool bStroke)193 B2DPolyPolygon clipPolygonOnRange(const B2DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke) 194 { 195 const sal_uInt32 nCount(rCandidate.count()); 196 B2DPolyPolygon aRetval; 197 198 if(!nCount) 199 { 200 // source is empty 201 return aRetval; 202 } 203 204 if(rRange.isEmpty()) 205 { 206 if(bInside) 207 { 208 // nothing is inside an empty range 209 return aRetval; 210 } 211 else 212 { 213 // everything is outside an empty range 214 return B2DPolyPolygon(rCandidate); 215 } 216 } 217 218 const B2DRange aCandidateRange(getRange(rCandidate)); 219 220 if(rRange.isInside(aCandidateRange)) 221 { 222 // candidate is completely inside given range 223 if(bInside) 224 { 225 // nothing to do 226 return B2DPolyPolygon(rCandidate); 227 } 228 else 229 { 230 // nothing is outside, then 231 return aRetval; 232 } 233 } 234 235 if(!bInside) 236 { 237 // cutting off the outer parts of filled polygons at parallel 238 // lines to the axes is only possible for the inner part, not for 239 // the outer part which means cutting a hole into the original polygon. 240 // This is because the inner part is a logical AND-operation of 241 // the four implied half-planes, but the outer part is not. 242 // It is possible for strokes, but with creating unnecessary extra 243 // cuts, so using clipPolygonOnPolyPolygon is better there, too. 244 // This needs to be done with the topology knowlegde and is unfurtunately 245 // more expensive, too. 246 const B2DPolygon aClip(createPolygonFromRect(rRange)); 247 248 return clipPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke); 249 } 250 251 // clip against the four axes of the range 252 // against X-Axis, lower value 253 aRetval = clipPolygonOnParallelAxis(rCandidate, true, bInside, rRange.getMinY(), bStroke); 254 255 if(aRetval.count()) 256 { 257 // against Y-Axis, lower value 258 if(1L == aRetval.count()) 259 { 260 aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, bInside, rRange.getMinX(), bStroke); 261 } 262 else 263 { 264 aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, bInside, rRange.getMinX(), bStroke); 265 } 266 267 if(aRetval.count()) 268 { 269 // against X-Axis, higher value 270 if(1L == aRetval.count()) 271 { 272 aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), true, !bInside, rRange.getMaxY(), bStroke); 273 } 274 else 275 { 276 aRetval = clipPolyPolygonOnParallelAxis(aRetval, true, !bInside, rRange.getMaxY(), bStroke); 277 } 278 279 if(aRetval.count()) 280 { 281 // against Y-Axis, higher value 282 if(1L == aRetval.count()) 283 { 284 aRetval = clipPolygonOnParallelAxis(aRetval.getB2DPolygon(0L), false, !bInside, rRange.getMaxX(), bStroke); 285 } 286 else 287 { 288 aRetval = clipPolyPolygonOnParallelAxis(aRetval, false, !bInside, rRange.getMaxX(), bStroke); 289 } 290 } 291 } 292 } 293 294 return aRetval; 295 } 296 clipPolyPolygonOnRange(const B2DPolyPolygon & rCandidate,const B2DRange & rRange,bool bInside,bool bStroke)297 B2DPolyPolygon clipPolyPolygonOnRange(const B2DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke) 298 { 299 const sal_uInt32 nPolygonCount(rCandidate.count()); 300 B2DPolyPolygon aRetval; 301 302 if(!nPolygonCount) 303 { 304 // source is empty 305 return aRetval; 306 } 307 308 if(rRange.isEmpty()) 309 { 310 if(bInside) 311 { 312 // nothing is inside an empty range 313 return aRetval; 314 } 315 else 316 { 317 // everything is outside an empty range 318 return rCandidate; 319 } 320 } 321 322 if(bInside) 323 { 324 for(sal_uInt32 a(0L); a < nPolygonCount; a++) 325 { 326 const B2DPolyPolygon aClippedPolyPolygon(clipPolygonOnRange(rCandidate.getB2DPolygon(a), rRange, bInside, bStroke)); 327 328 if(aClippedPolyPolygon.count()) 329 { 330 aRetval.append(aClippedPolyPolygon); 331 } 332 } 333 } 334 else 335 { 336 // for details, see comment in clipPolygonOnRange for the "cutting off 337 // the outer parts of filled polygons at parallel lines" explanations 338 const B2DPolygon aClip(createPolygonFromRect(rRange)); 339 340 return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke); 341 } 342 343 return aRetval; 344 } 345 clipPolygonOnEdge(const B2DPolygon & rCandidate,const B2DPoint & rPointA,const B2DPoint & rPointB,bool bAbove,bool bStroke)346 B2DPolyPolygon clipPolygonOnEdge(const B2DPolygon& rCandidate, const B2DPoint& rPointA, const B2DPoint& rPointB, bool bAbove, bool bStroke) 347 { 348 B2DPolyPolygon aRetval; 349 350 if(rPointA.equal(rPointB)) 351 { 352 // edge has no length, return polygon 353 aRetval.append(rCandidate); 354 } 355 else if(rCandidate.count()) 356 { 357 const B2DVector aEdge(rPointB - rPointA); 358 B2DPolygon aCandidate(rCandidate); 359 360 // translate and rotate polygon so that given edge is on x axis 361 B2DHomMatrix aMatrixTransform(basegfx::tools::createTranslateB2DHomMatrix(-rPointA.getX(), -rPointA.getY())); 362 aMatrixTransform.rotate(-atan2(aEdge.getY(), aEdge.getX())); 363 aCandidate.transform(aMatrixTransform); 364 365 // call clip method on X-Axis 366 aRetval = clipPolygonOnParallelAxis(aCandidate, true, bAbove, 0.0, bStroke); 367 368 if(aRetval.count()) 369 { 370 // if there is a result, it needs to be transformed back 371 aMatrixTransform.invert(); 372 aRetval.transform(aMatrixTransform); 373 } 374 } 375 376 return aRetval; 377 } 378 clipPolyPolygonOnEdge(const B2DPolyPolygon & rCandidate,const B2DPoint & rPointA,const B2DPoint & rPointB,bool bAbove,bool bStroke)379 B2DPolyPolygon clipPolyPolygonOnEdge(const B2DPolyPolygon& rCandidate, const B2DPoint& rPointA, const B2DPoint& rPointB, bool bAbove, bool bStroke) 380 { 381 B2DPolyPolygon aRetval; 382 383 if(rPointA.equal(rPointB)) 384 { 385 // edge has no length, return polygon 386 aRetval = rCandidate; 387 } 388 else if(rCandidate.count()) 389 { 390 const B2DVector aEdge(rPointB - rPointA); 391 B2DPolyPolygon aCandidate(rCandidate); 392 393 // translate and rotate polygon so that given edge is on x axis 394 B2DHomMatrix aMatrixTransform(basegfx::tools::createTranslateB2DHomMatrix(-rPointA.getX(), -rPointA.getY())); 395 aMatrixTransform.rotate(-atan2(aEdge.getY(), aEdge.getX())); 396 aCandidate.transform(aMatrixTransform); 397 398 // call clip method on X-Axis 399 aRetval = clipPolyPolygonOnParallelAxis(aCandidate, true, bAbove, 0.0, bStroke); 400 401 if(aRetval.count()) 402 { 403 // if there is a result, it needs to be transformed back 404 aMatrixTransform.invert(); 405 aRetval.transform(aMatrixTransform); 406 } 407 } 408 409 return aRetval; 410 } 411 412 ////////////////////////////////////////////////////////////////////////////// 413 clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon & rCandidate,const B2DPolyPolygon & rClip,bool bInside,bool bStroke)414 B2DPolyPolygon clipPolyPolygonOnPolyPolygon(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke) 415 { 416 B2DPolyPolygon aRetval; 417 418 if(rCandidate.count() && rClip.count()) 419 { 420 // one or both are no rectangle - go the hard way and clip PolyPolygon 421 // against PolyPolygon... 422 if(bStroke) 423 { 424 // line clipping, create line snippets by first adding all cut points and 425 // then marching along the edges and detecting if they are inside or outside 426 // the clip polygon 427 for(sal_uInt32 a(0); a < rCandidate.count(); a++) 428 { 429 // add cuts with clip to polygon, including bezier segments 430 const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip)); 431 const sal_uInt32 nPointCount(aCandidate.count()); 432 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 433 B2DCubicBezier aEdge; 434 B2DPolygon aRun; 435 436 for(sal_uInt32 b(0); b < nEdgeCount; b++) 437 { 438 aCandidate.getBezierSegment(b, aEdge); 439 const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5)); 440 const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside); 441 442 if(bIsInside) 443 { 444 if(!aRun.count()) 445 { 446 aRun.append(aEdge.getStartPoint()); 447 } 448 449 if(aEdge.isBezier()) 450 { 451 aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint()); 452 } 453 else 454 { 455 aRun.append(aEdge.getEndPoint()); 456 } 457 } 458 else 459 { 460 if(aRun.count()) 461 { 462 aRetval.append(aRun); 463 aRun.clear(); 464 } 465 } 466 } 467 468 if(aRun.count()) 469 { 470 // try to merge this last and first polygon; they may have been 471 // the former polygon's start/end point 472 if(aRetval.count()) 473 { 474 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0)); 475 476 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1))) 477 { 478 // append start polygon to aRun, remove from result set 479 aRun.append(aStartPolygon); aRun.removeDoublePoints(); 480 aRetval.remove(0); 481 } 482 } 483 484 aRetval.append(aRun); 485 } 486 } 487 } 488 else 489 { 490 // check for simplification with ranges if !bStroke (handling as stroke is more simple), 491 // but also only when bInside, else the simplification may lead to recursive calls (see 492 // calls to clipPolyPolygonOnPolyPolygon in clipPolyPolygonOnRange and clipPolygonOnRange) 493 if(bInside) 494 { 495 // #125349# detect if both given PolyPolygons are indeed ranges 496 bool bBothRectangle(false); 497 498 if(basegfx::tools::isRectangle(rCandidate)) 499 { 500 if(basegfx::tools::isRectangle(rClip)) 501 { 502 // both are ranges 503 bBothRectangle = true; 504 } 505 else 506 { 507 // rCandidate is rectangle -> clip rClip on rRectangle, use the much 508 // cheaper and numerically more stable clipping against a range 509 // This simplification (exchanging content and clip) is valid 510 // since we do a logical AND operation 511 return clipPolyPolygonOnRange(rClip, rCandidate.getB2DRange(), bInside, bStroke); 512 } 513 } 514 else if(basegfx::tools::isRectangle(rClip)) 515 { 516 if(basegfx::tools::isRectangle(rCandidate)) 517 { 518 // both are ranges 519 bBothRectangle = true; 520 } 521 else 522 { 523 // rClip is rectangle -> clip rCandidate on rRectangle, use the much 524 // cheaper and numerically more stable clipping against a range 525 return clipPolyPolygonOnRange(rCandidate, rClip.getB2DRange(), bInside, bStroke); 526 } 527 } 528 529 if(bBothRectangle) 530 { 531 // both are rectangle 532 if(rCandidate.getB2DRange().equal(rClip.getB2DRange())) 533 { 534 // if both are equal -> no change 535 return rCandidate; 536 } 537 else 538 { 539 // not equal -> create new intersection from both ranges, 540 // but much cheaper based on the ranges 541 basegfx::B2DRange aIntersectionRange(rCandidate.getB2DRange()); 542 543 aIntersectionRange.intersect(rClip.getB2DRange()); 544 545 if(aIntersectionRange.isEmpty()) 546 { 547 // no common IntersectionRange -> the clip will be empty 548 return B2DPolyPolygon(); 549 } 550 else 551 { 552 // use common aIntersectionRange as result, convert 553 // to expected PolyPolygon form 554 return basegfx::B2DPolyPolygon( 555 basegfx::tools::createPolygonFromRect(aIntersectionRange)); 556 } 557 } 558 } 559 } 560 561 // area clipping 562 B2DPolyPolygon aMergePolyPolygonA(rClip); 563 564 // First solve all polygon-self and polygon-polygon intersections. 565 // Also get rid of some not-needed polygons (neutral, no area -> when 566 // no intersections, these are tubes). 567 // Now it is possible to correct the orientations in the cut-free 568 // polygons to values corresponding to painting the PolyPolygon with 569 // a XOR-WindingRule. 570 aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA); 571 aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA); 572 aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA); 573 574 if(!bInside) 575 { 576 // if we want to get the outside of the clip polygon, make 577 // it a 'Hole' in topological sense 578 aMergePolyPolygonA.flip(); 579 } 580 581 B2DPolyPolygon aMergePolyPolygonB(rCandidate); 582 583 // prepare 2nd source polygon in same way 584 aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB); 585 aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB); 586 aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB); 587 588 // to clip against each other, concatenate and solve all 589 // polygon-polygon crossovers. polygon-self do not need to 590 // be solved again, they were solved in the preparation. 591 aRetval.append(aMergePolyPolygonA); 592 aRetval.append(aMergePolyPolygonB); 593 aRetval = solveCrossovers(aRetval); 594 595 // now remove neutral polygons (closed, but no area). In a last 596 // step throw away all polygons which have a depth of less than 1 597 // which means there was no logical AND at their position. For the 598 // not-inside solution, the clip was flipped to define it as 'Hole', 599 // so the removal rule is different here; remove all with a depth 600 // of less than 0 (aka holes). 601 aRetval = stripNeutralPolygons(aRetval); 602 aRetval = stripDispensablePolygons(aRetval, bInside); 603 } 604 } 605 606 return aRetval; 607 } 608 609 ////////////////////////////////////////////////////////////////////////////// 610 clipPolygonOnPolyPolygon(const B2DPolygon & rCandidate,const B2DPolyPolygon & rClip,bool bInside,bool bStroke)611 B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke) 612 { 613 B2DPolyPolygon aRetval; 614 615 if(rCandidate.count() && rClip.count()) 616 { 617 aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke); 618 } 619 620 return aRetval; 621 } 622 623 ////////////////////////////////////////////////////////////////////////////// 624 625 /* 626 * let a plane be defined as 627 * 628 * v.n+d=0 629 * 630 * and a ray be defined as 631 * 632 * a+(b-a)*t=0 633 * 634 * substitute and rearranging yields 635 * 636 * t = -(a.n+d)/(n.(b-a)) 637 * 638 * if the denominator is zero, the line is either 639 * contained in the plane or parallel to the plane. 640 * in either case, there is no intersection. 641 * if numerator and denominator are both zero, the 642 * ray is contained in the plane. 643 * 644 */ 645 struct scissor_plane { 646 double nx,ny; // plane normal 647 double d; // [-] minimum distance from origin 648 sal_uInt32 clipmask; // clipping mask, e.g. 1000 1000 649 }; 650 651 /* 652 * 653 * polygon clipping rules (straight out of Foley and Van Dam) 654 * =========================================================== 655 * current |next |emit 656 * ____________________________________ 657 * inside |inside |next 658 * inside |outside |intersect with clip plane 659 * outside |outside |nothing 660 * outside |inside |intersect with clip plane follwed by next 661 * 662 */ scissorLineSegment(::basegfx::B2DPoint * in_vertex,sal_uInt32 in_count,::basegfx::B2DPoint * out_vertex,scissor_plane * pPlane,const::basegfx::B2DRectangle & rR)663 sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint *in_vertex, // input buffer 664 sal_uInt32 in_count, // number of verts in input buffer 665 ::basegfx::B2DPoint *out_vertex, // output buffer 666 scissor_plane *pPlane, // scissoring plane 667 const ::basegfx::B2DRectangle &rR ) // clipping rectangle 668 { 669 ::basegfx::B2DPoint *curr; 670 ::basegfx::B2DPoint *next; 671 672 sal_uInt32 out_count=0; 673 674 // process all the verts 675 for(sal_uInt32 i=0; i<in_count; i++) { 676 677 // vertices are relative to the coordinate 678 // system defined by the rectangle. 679 curr = &in_vertex[i]; 680 next = &in_vertex[(i+1)%in_count]; 681 682 // perform clipping judgement & mask against current plane. 683 sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR)); 684 685 if(clip==0) { // both verts are inside 686 out_vertex[out_count++] = *next; 687 } 688 else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside 689 } 690 else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside 691 692 // direction vector from 'current' to 'next', *not* normalized 693 // to bring 't' into the [0<=x<=1] intervall. 694 ::basegfx::B2DPoint dir((*next)-(*curr)); 695 696 double denominator = ( pPlane->nx*dir.getX() + 697 pPlane->ny*dir.getY() ); 698 double numerator = ( pPlane->nx*curr->getX() + 699 pPlane->ny*curr->getY() + 700 pPlane->d ); 701 double t = -numerator/denominator; 702 703 // calculate the actual point of intersection 704 ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(), 705 curr->getY()+t*dir.getY() ); 706 707 out_vertex[out_count++] = intersection; 708 } 709 else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside 710 711 // direction vector from 'current' to 'next', *not* normalized 712 // to bring 't' into the [0<=x<=1] intervall. 713 ::basegfx::B2DPoint dir((*next)-(*curr)); 714 715 double denominator = ( pPlane->nx*dir.getX() + 716 pPlane->ny*dir.getY() ); 717 double numerator = ( pPlane->nx*curr->getX() + 718 pPlane->ny*curr->getY() + 719 pPlane->d ); 720 double t = -numerator/denominator; 721 722 // calculate the actual point of intersection 723 ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(), 724 curr->getY()+t*dir.getY() ); 725 726 out_vertex[out_count++] = intersection; 727 out_vertex[out_count++] = *next; 728 } 729 } 730 731 return out_count; 732 } 733 clipTriangleListOnRange(const B2DPolygon & rCandidate,const B2DRange & rRange)734 B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate, 735 const B2DRange& rRange ) 736 { 737 B2DPolygon aResult; 738 739 if( !(rCandidate.count()%3) ) 740 { 741 const int scissor_plane_count = 4; 742 743 scissor_plane sp[scissor_plane_count]; 744 745 sp[0].nx = +1.0; 746 sp[0].ny = +0.0; 747 sp[0].d = -(rRange.getMinX()); 748 sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001 749 sp[1].nx = -1.0; 750 sp[1].ny = +0.0; 751 sp[1].d = +(rRange.getMaxX()); 752 sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010 753 sp[2].nx = +0.0; 754 sp[2].ny = +1.0; 755 sp[2].d = -(rRange.getMinY()); 756 sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100 757 sp[3].nx = +0.0; 758 sp[3].ny = -1.0; 759 sp[3].d = +(rRange.getMaxY()); 760 sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000 761 762 // retrieve the number of vertices of the triangulated polygon 763 const sal_uInt32 nVertexCount = rCandidate.count(); 764 765 if(nVertexCount) 766 { 767 //////////////////////////////////////////////////////////////////////// 768 //////////////////////////////////////////////////////////////////////// 769 //////////////////////////////////////////////////////////////////////// 770 // 771 // Upper bound for the maximal number of vertices when intersecting an 772 // axis-aligned rectangle with a triangle in E2 773 // 774 // The rectangle and the triangle are in general position, and have 4 and 3 775 // vertices, respectively. 776 // 777 // Lemma: Since the rectangle is a convex polygon ( see 778 // http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and 779 // has no holes, it follows that any straight line will intersect the 780 // rectangle's border line at utmost two times (with the usual 781 // tie-breaking rule, if the intersection exactly hits an already existing 782 // rectangle vertex, that this intersection is only attributed to one of 783 // the adjoining edges). Thus, having a rectangle intersected with 784 // a half-plane (one side of a straight line denotes 'inside', the 785 // other 'outside') will at utmost add _one_ vertex to the resulting 786 // intersection polygon (adding two intersection vertices, and removing at 787 // least one rectangle vertex): 788 // 789 // * 790 // +--+-----------------+ 791 // | * | 792 // |* | 793 // + | 794 // *| | 795 // * | | 796 // +--------------------+ 797 // 798 // Proof: If the straight line intersects the rectangle two 799 // times, it does so for distinct edges, i.e. the intersection has 800 // minimally one of the rectangle's vertices on either side of the straight 801 // line (but maybe more). Thus, the intersection with a half-plane has 802 // minimally _one_ rectangle vertex removed from the resulting clip 803 // polygon, and therefore, a clip against a half-plane has the net effect 804 // of adding at utmost _one_ vertex to the resulting clip polygon. 805 // 806 // Theorem: The intersection of a rectangle and a triangle results in a 807 // polygon with at utmost 7 vertices. 808 // 809 // Proof: The inside of the triangle can be described as the consecutive 810 // intersection with three half-planes. Together with the lemma above, this 811 // results in at utmost 3 additional vertices added to the already existing 4 812 // rectangle vertices. 813 // 814 // This upper bound is attained with the following example configuration: 815 // 816 // * 817 // *** 818 // ** * 819 // ** * 820 // ** * 821 // ** * 822 // ** * 823 // ** * 824 // ** * 825 // ** * 826 // ** * 827 // ----*2--------3 * 828 // | ** |* 829 // 1* 4 830 // **| *| 831 // ** | * | 832 // **| * | 833 // 7* * | 834 // --*6-----5----- 835 // ** * 836 // ** 837 // 838 // As we need to scissor all triangles against the 839 // output rectangle we employ an output buffer for the 840 // resulting vertices. the question is how large this 841 // buffer needs to be compared to the number of 842 // incoming vertices. this buffer needs to hold at 843 // most the number of original vertices times '7'. see 844 // figure above for an example. scissoring triangles 845 // with the cohen-sutherland line clipping algorithm 846 // as implemented here will result in a triangle fan 847 // which will be rendered as separate triangles to 848 // avoid pipeline stalls for each scissored 849 // triangle. creating separate triangles from a 850 // triangle fan produces (n-2)*3 vertices where n is 851 // the number of vertices of the original triangle 852 // fan. for the maximum number of 7 vertices of 853 // resulting triangle fans we therefore need 15 times 854 // the number of original vertices. 855 // 856 //////////////////////////////////////////////////////////////////////// 857 //////////////////////////////////////////////////////////////////////// 858 //////////////////////////////////////////////////////////////////////// 859 860 //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16); 861 //vertex *pVertices = (vertex*)alloca(nBufferSize); 862 //sal_uInt32 nNumOutput = 0; 863 864 // we need to clip this triangle against the output rectangle 865 // to ensure that the resulting texture coordinates are in 866 // the valid range from [0<=st<=1]. under normal circustances 867 // we could use the BORDERCOLOR renderstate but some cards 868 // seem to ignore this feature. 869 ::basegfx::B2DPoint stack[3]; 870 unsigned int clipflag = 0; 871 872 for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex) 873 { 874 // rotate stack 875 stack[0] = stack[1]; 876 stack[1] = stack[2]; 877 stack[2] = rCandidate.getB2DPoint(nIndex); 878 879 // clipping judgement 880 clipflag |= !(rRange.isInside(stack[2])); 881 882 if(nIndex > 1) 883 { 884 // consume vertices until a single separate triangle has been visited. 885 if(!((nIndex+1)%3)) 886 { 887 // if any of the last three vertices was outside 888 // we need to scissor against the destination rectangle 889 if(clipflag & 7) 890 { 891 ::basegfx::B2DPoint buf0[16]; 892 ::basegfx::B2DPoint buf1[16]; 893 894 sal_uInt32 vertex_count = 3; 895 896 // clip against all 4 planes passing the result of 897 // each plane as the input to the next using a double buffer 898 vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange); 899 vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange); 900 vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange); 901 vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange); 902 903 if(vertex_count >= 3) 904 { 905 // convert triangle fan back to triangle list. 906 ::basegfx::B2DPoint v0(buf0[0]); 907 ::basegfx::B2DPoint v1(buf0[1]); 908 for(sal_uInt32 i=2; i<vertex_count; ++i) 909 { 910 ::basegfx::B2DPoint v2(buf0[i]); 911 aResult.append(v0); 912 aResult.append(v1); 913 aResult.append(v2); 914 v1 = v2; 915 } 916 } 917 } 918 else 919 { 920 // the last triangle has not been altered, simply copy to result 921 for(sal_uInt32 i=0; i<3; ++i) 922 aResult.append(stack[i]); 923 } 924 } 925 } 926 927 clipflag <<= 1; 928 } 929 } 930 } 931 932 return aResult; 933 } 934 935 ////////////////////////////////////////////////////////////////////////////// 936 937 } // end of namespace tools 938 } // end of namespace basegfx 939 940 ////////////////////////////////////////////////////////////////////////////// 941 942 // eof 943