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 { 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 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 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 parallell 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 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 parallell lines" explanations 338 const B2DPolygon aClip(createPolygonFromRect(rRange)); 339 340 return clipPolyPolygonOnPolyPolygon(rCandidate, B2DPolyPolygon(aClip), bInside, bStroke); 341 } 342 343 return aRetval; 344 } 345 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 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 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 // #125349# detect if both given PolyPolygons are indeed ranges 421 bool bBothRectangle(false); 422 423 if(basegfx::tools::isRectangle(rCandidate)) 424 { 425 if(basegfx::tools::isRectangle(rClip)) 426 { 427 // both are ranges 428 bBothRectangle = true; 429 } 430 else 431 { 432 // rCandidate is rectangle -> clip rClip on rRectangle, use the much 433 // cheaper and numerically more stable clipping against a range 434 // This simplification (exchanging content and clip) is valid 435 // since we do a logical AND operation 436 return clipPolyPolygonOnRange(rClip, rCandidate.getB2DRange(), bInside, bStroke); 437 } 438 } 439 else if(basegfx::tools::isRectangle(rClip)) 440 { 441 if(basegfx::tools::isRectangle(rCandidate)) 442 { 443 // both are ranges 444 bBothRectangle = true; 445 } 446 else 447 { 448 // rClip is rectangle -> clip rCandidate on rRectangle, use the much 449 // cheaper and numerically more stable clipping against a range 450 return clipPolyPolygonOnRange(rCandidate, rClip.getB2DRange(), bInside, bStroke); 451 } 452 } 453 454 if(bBothRectangle) 455 { 456 // both are rectangle 457 if(rCandidate.getB2DRange().equal(rClip.getB2DRange())) 458 { 459 // if both are equal -> no change 460 return rCandidate; 461 } 462 else 463 { 464 // not equal -> create new intersection from both ranges, 465 // but much cheaper based on the ranges 466 basegfx::B2DRange aIntersectionRange(rCandidate.getB2DRange()); 467 468 aIntersectionRange.intersect(rClip.getB2DRange()); 469 470 if(aIntersectionRange.isEmpty()) 471 { 472 // no common IntersectionRange -> the clip will be empty 473 return B2DPolyPolygon(); 474 } 475 else 476 { 477 // use common aIntersectionRange as result, convert 478 // to expected PolyPolygon form 479 return basegfx::B2DPolyPolygon( 480 basegfx::tools::createPolygonFromRect(aIntersectionRange)); 481 } 482 } 483 } 484 485 // one or both are no rectangle - go the hard way and clip PolyPolygon 486 // against PolyPolygon... 487 if(bStroke) 488 { 489 // line clipping, create line snippets by first adding all cut points and 490 // then marching along the edges and detecting if they are inside or outside 491 // the clip polygon 492 for(sal_uInt32 a(0); a < rCandidate.count(); a++) 493 { 494 // add cuts with clip to polygon, including bezier segments 495 const B2DPolygon aCandidate(addPointsAtCuts(rCandidate.getB2DPolygon(a), rClip)); 496 const sal_uInt32 nPointCount(aCandidate.count()); 497 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); 498 B2DCubicBezier aEdge; 499 B2DPolygon aRun; 500 501 for(sal_uInt32 b(0); b < nEdgeCount; b++) 502 { 503 aCandidate.getBezierSegment(b, aEdge); 504 const B2DPoint aTestPoint(aEdge.interpolatePoint(0.5)); 505 const bool bIsInside(tools::isInside(rClip, aTestPoint) == bInside); 506 507 if(bIsInside) 508 { 509 if(!aRun.count()) 510 { 511 aRun.append(aEdge.getStartPoint()); 512 } 513 514 if(aEdge.isBezier()) 515 { 516 aRun.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint()); 517 } 518 else 519 { 520 aRun.append(aEdge.getEndPoint()); 521 } 522 } 523 else 524 { 525 if(aRun.count()) 526 { 527 aRetval.append(aRun); 528 aRun.clear(); 529 } 530 } 531 } 532 533 if(aRun.count()) 534 { 535 // try to merge this last and first polygon; they may have been 536 // the former polygon's start/end point 537 if(aRetval.count()) 538 { 539 const B2DPolygon aStartPolygon(aRetval.getB2DPolygon(0)); 540 541 if(aStartPolygon.count() && aStartPolygon.getB2DPoint(0).equal(aRun.getB2DPoint(aRun.count() - 1))) 542 { 543 // append start polygon to aRun, remove from result set 544 aRun.append(aStartPolygon); aRun.removeDoublePoints(); 545 aRetval.remove(0); 546 } 547 } 548 549 aRetval.append(aRun); 550 } 551 } 552 } 553 else 554 { 555 // area clipping 556 B2DPolyPolygon aMergePolyPolygonA(rClip); 557 558 // First solve all polygon-self and polygon-polygon intersections. 559 // Also get rid of some not-needed polygons (neutral, no area -> when 560 // no intersections, these are tubes). 561 // Now it is possible to correct the orientations in the cut-free 562 // polygons to values corresponding to painting the PolyPolygon with 563 // a XOR-WindingRule. 564 aMergePolyPolygonA = solveCrossovers(aMergePolyPolygonA); 565 aMergePolyPolygonA = stripNeutralPolygons(aMergePolyPolygonA); 566 aMergePolyPolygonA = correctOrientations(aMergePolyPolygonA); 567 568 if(!bInside) 569 { 570 // if we want to get the outside of the clip polygon, make 571 // it a 'Hole' in topological sense 572 aMergePolyPolygonA.flip(); 573 } 574 575 B2DPolyPolygon aMergePolyPolygonB(rCandidate); 576 577 // prepare 2nd source polygon in same way 578 aMergePolyPolygonB = solveCrossovers(aMergePolyPolygonB); 579 aMergePolyPolygonB = stripNeutralPolygons(aMergePolyPolygonB); 580 aMergePolyPolygonB = correctOrientations(aMergePolyPolygonB); 581 582 // to clip against each other, concatenate and solve all 583 // polygon-polygon crossovers. polygon-self do not need to 584 // be solved again, they were solved in the preparation. 585 aRetval.append(aMergePolyPolygonA); 586 aRetval.append(aMergePolyPolygonB); 587 aRetval = solveCrossovers(aRetval); 588 589 // now remove neutral polygons (closed, but no area). In a last 590 // step throw away all polygons which have a depth of less than 1 591 // which means there was no logical AND at their position. For the 592 // not-inside solution, the clip was flipped to define it as 'Hole', 593 // so the removal rule is different here; remove all with a depth 594 // of less than 0 (aka holes). 595 aRetval = stripNeutralPolygons(aRetval); 596 aRetval = stripDispensablePolygons(aRetval, bInside); 597 } 598 } 599 600 return aRetval; 601 } 602 603 ////////////////////////////////////////////////////////////////////////////// 604 605 B2DPolyPolygon clipPolygonOnPolyPolygon(const B2DPolygon& rCandidate, const B2DPolyPolygon& rClip, bool bInside, bool bStroke) 606 { 607 B2DPolyPolygon aRetval; 608 609 if(rCandidate.count() && rClip.count()) 610 { 611 aRetval = clipPolyPolygonOnPolyPolygon(B2DPolyPolygon(rCandidate), rClip, bInside, bStroke); 612 } 613 614 return aRetval; 615 } 616 617 ////////////////////////////////////////////////////////////////////////////// 618 619 /* 620 * let a plane be defined as 621 * 622 * v.n+d=0 623 * 624 * and a ray be defined as 625 * 626 * a+(b-a)*t=0 627 * 628 * substitute and rearranging yields 629 * 630 * t = -(a.n+d)/(n.(b-a)) 631 * 632 * if the denominator is zero, the line is either 633 * contained in the plane or parallel to the plane. 634 * in either case, there is no intersection. 635 * if numerator and denominator are both zero, the 636 * ray is contained in the plane. 637 * 638 */ 639 struct scissor_plane { 640 double nx,ny; // plane normal 641 double d; // [-] minimum distance from origin 642 sal_uInt32 clipmask; // clipping mask, e.g. 1000 1000 643 }; 644 645 /* 646 * 647 * polygon clipping rules (straight out of Foley and Van Dam) 648 * =========================================================== 649 * current |next |emit 650 * ____________________________________ 651 * inside |inside |next 652 * inside |outside |intersect with clip plane 653 * outside |outside |nothing 654 * outside |inside |intersect with clip plane follwed by next 655 * 656 */ 657 sal_uInt32 scissorLineSegment( ::basegfx::B2DPoint *in_vertex, // input buffer 658 sal_uInt32 in_count, // number of verts in input buffer 659 ::basegfx::B2DPoint *out_vertex, // output buffer 660 scissor_plane *pPlane, // scissoring plane 661 const ::basegfx::B2DRectangle &rR ) // clipping rectangle 662 { 663 ::basegfx::B2DPoint *curr; 664 ::basegfx::B2DPoint *next; 665 666 sal_uInt32 out_count=0; 667 668 // process all the verts 669 for(sal_uInt32 i=0; i<in_count; i++) { 670 671 // vertices are relative to the coordinate 672 // system defined by the rectangle. 673 curr = &in_vertex[i]; 674 next = &in_vertex[(i+1)%in_count]; 675 676 // perform clipping judgement & mask against current plane. 677 sal_uInt32 clip = pPlane->clipmask & ((getCohenSutherlandClipFlags(*curr,rR)<<4)|getCohenSutherlandClipFlags(*next,rR)); 678 679 if(clip==0) { // both verts are inside 680 out_vertex[out_count++] = *next; 681 } 682 else if((clip&0x0f) && (clip&0xf0)) { // both verts are outside 683 } 684 else if((clip&0x0f) && (clip&0xf0)==0) { // curr is inside, next is outside 685 686 // direction vector from 'current' to 'next', *not* normalized 687 // to bring 't' into the [0<=x<=1] intervall. 688 ::basegfx::B2DPoint dir((*next)-(*curr)); 689 690 double denominator = ( pPlane->nx*dir.getX() + 691 pPlane->ny*dir.getY() ); 692 double numerator = ( pPlane->nx*curr->getX() + 693 pPlane->ny*curr->getY() + 694 pPlane->d ); 695 double t = -numerator/denominator; 696 697 // calculate the actual point of intersection 698 ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(), 699 curr->getY()+t*dir.getY() ); 700 701 out_vertex[out_count++] = intersection; 702 } 703 else if((clip&0x0f)==0 && (clip&0xf0)) { // curr is outside, next is inside 704 705 // direction vector from 'current' to 'next', *not* normalized 706 // to bring 't' into the [0<=x<=1] intervall. 707 ::basegfx::B2DPoint dir((*next)-(*curr)); 708 709 double denominator = ( pPlane->nx*dir.getX() + 710 pPlane->ny*dir.getY() ); 711 double numerator = ( pPlane->nx*curr->getX() + 712 pPlane->ny*curr->getY() + 713 pPlane->d ); 714 double t = -numerator/denominator; 715 716 // calculate the actual point of intersection 717 ::basegfx::B2DPoint intersection( curr->getX()+t*dir.getX(), 718 curr->getY()+t*dir.getY() ); 719 720 out_vertex[out_count++] = intersection; 721 out_vertex[out_count++] = *next; 722 } 723 } 724 725 return out_count; 726 } 727 728 B2DPolygon clipTriangleListOnRange( const B2DPolygon& rCandidate, 729 const B2DRange& rRange ) 730 { 731 B2DPolygon aResult; 732 733 if( !(rCandidate.count()%3) ) 734 { 735 const int scissor_plane_count = 4; 736 737 scissor_plane sp[scissor_plane_count]; 738 739 sp[0].nx = +1.0; 740 sp[0].ny = +0.0; 741 sp[0].d = -(rRange.getMinX()); 742 sp[0].clipmask = (RectClipFlags::LEFT << 4) | RectClipFlags::LEFT; // 0001 0001 743 sp[1].nx = -1.0; 744 sp[1].ny = +0.0; 745 sp[1].d = +(rRange.getMaxX()); 746 sp[1].clipmask = (RectClipFlags::RIGHT << 4) | RectClipFlags::RIGHT; // 0010 0010 747 sp[2].nx = +0.0; 748 sp[2].ny = +1.0; 749 sp[2].d = -(rRange.getMinY()); 750 sp[2].clipmask = (RectClipFlags::TOP << 4) | RectClipFlags::TOP; // 0100 0100 751 sp[3].nx = +0.0; 752 sp[3].ny = -1.0; 753 sp[3].d = +(rRange.getMaxY()); 754 sp[3].clipmask = (RectClipFlags::BOTTOM << 4) | RectClipFlags::BOTTOM; // 1000 1000 755 756 // retrieve the number of vertices of the triangulated polygon 757 const sal_uInt32 nVertexCount = rCandidate.count(); 758 759 if(nVertexCount) 760 { 761 //////////////////////////////////////////////////////////////////////// 762 //////////////////////////////////////////////////////////////////////// 763 //////////////////////////////////////////////////////////////////////// 764 // 765 // Upper bound for the maximal number of vertices when intersecting an 766 // axis-aligned rectangle with a triangle in E2 767 // 768 // The rectangle and the triangle are in general position, and have 4 and 3 769 // vertices, respectively. 770 // 771 // Lemma: Since the rectangle is a convex polygon ( see 772 // http://mathworld.wolfram.com/ConvexPolygon.html for a definition), and 773 // has no holes, it follows that any straight line will intersect the 774 // rectangle's border line at utmost two times (with the usual 775 // tie-breaking rule, if the intersection exactly hits an already existing 776 // rectangle vertex, that this intersection is only attributed to one of 777 // the adjoining edges). Thus, having a rectangle intersected with 778 // a half-plane (one side of a straight line denotes 'inside', the 779 // other 'outside') will at utmost add _one_ vertex to the resulting 780 // intersection polygon (adding two intersection vertices, and removing at 781 // least one rectangle vertex): 782 // 783 // * 784 // +--+-----------------+ 785 // | * | 786 // |* | 787 // + | 788 // *| | 789 // * | | 790 // +--------------------+ 791 // 792 // Proof: If the straight line intersects the rectangle two 793 // times, it does so for distinct edges, i.e. the intersection has 794 // minimally one of the rectangle's vertices on either side of the straight 795 // line (but maybe more). Thus, the intersection with a half-plane has 796 // minimally _one_ rectangle vertex removed from the resulting clip 797 // polygon, and therefore, a clip against a half-plane has the net effect 798 // of adding at utmost _one_ vertex to the resulting clip polygon. 799 // 800 // Theorem: The intersection of a rectangle and a triangle results in a 801 // polygon with at utmost 7 vertices. 802 // 803 // Proof: The inside of the triangle can be described as the consecutive 804 // intersection with three half-planes. Together with the lemma above, this 805 // results in at utmost 3 additional vertices added to the already existing 4 806 // rectangle vertices. 807 // 808 // This upper bound is attained with the following example configuration: 809 // 810 // * 811 // *** 812 // ** * 813 // ** * 814 // ** * 815 // ** * 816 // ** * 817 // ** * 818 // ** * 819 // ** * 820 // ** * 821 // ----*2--------3 * 822 // | ** |* 823 // 1* 4 824 // **| *| 825 // ** | * | 826 // **| * | 827 // 7* * | 828 // --*6-----5----- 829 // ** * 830 // ** 831 // 832 // As we need to scissor all triangles against the 833 // output rectangle we employ an output buffer for the 834 // resulting vertices. the question is how large this 835 // buffer needs to be compared to the number of 836 // incoming vertices. this buffer needs to hold at 837 // most the number of original vertices times '7'. see 838 // figure above for an example. scissoring triangles 839 // with the cohen-sutherland line clipping algorithm 840 // as implemented here will result in a triangle fan 841 // which will be rendered as separate triangles to 842 // avoid pipeline stalls for each scissored 843 // triangle. creating separate triangles from a 844 // triangle fan produces (n-2)*3 vertices where n is 845 // the number of vertices of the original triangle 846 // fan. for the maximum number of 7 vertices of 847 // resulting triangle fans we therefore need 15 times 848 // the number of original vertices. 849 // 850 //////////////////////////////////////////////////////////////////////// 851 //////////////////////////////////////////////////////////////////////// 852 //////////////////////////////////////////////////////////////////////// 853 854 //const size_t nBufferSize = sizeof(vertex)*(nVertexCount*16); 855 //vertex *pVertices = (vertex*)alloca(nBufferSize); 856 //sal_uInt32 nNumOutput = 0; 857 858 // we need to clip this triangle against the output rectangle 859 // to ensure that the resulting texture coordinates are in 860 // the valid range from [0<=st<=1]. under normal circustances 861 // we could use the BORDERCOLOR renderstate but some cards 862 // seem to ignore this feature. 863 ::basegfx::B2DPoint stack[3]; 864 unsigned int clipflag = 0; 865 866 for(sal_uInt32 nIndex=0; nIndex<nVertexCount; ++nIndex) 867 { 868 // rotate stack 869 stack[0] = stack[1]; 870 stack[1] = stack[2]; 871 stack[2] = rCandidate.getB2DPoint(nIndex); 872 873 // clipping judgement 874 clipflag |= !(rRange.isInside(stack[2])); 875 876 if(nIndex > 1) 877 { 878 // consume vertices until a single separate triangle has been visited. 879 if(!((nIndex+1)%3)) 880 { 881 // if any of the last three vertices was outside 882 // we need to scissor against the destination rectangle 883 if(clipflag & 7) 884 { 885 ::basegfx::B2DPoint buf0[16]; 886 ::basegfx::B2DPoint buf1[16]; 887 888 sal_uInt32 vertex_count = 3; 889 890 // clip against all 4 planes passing the result of 891 // each plane as the input to the next using a double buffer 892 vertex_count = scissorLineSegment(stack,vertex_count,buf1,&sp[0],rRange); 893 vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[1],rRange); 894 vertex_count = scissorLineSegment(buf0,vertex_count,buf1,&sp[2],rRange); 895 vertex_count = scissorLineSegment(buf1,vertex_count,buf0,&sp[3],rRange); 896 897 if(vertex_count >= 3) 898 { 899 // convert triangle fan back to triangle list. 900 ::basegfx::B2DPoint v0(buf0[0]); 901 ::basegfx::B2DPoint v1(buf0[1]); 902 for(sal_uInt32 i=2; i<vertex_count; ++i) 903 { 904 ::basegfx::B2DPoint v2(buf0[i]); 905 aResult.append(v0); 906 aResult.append(v1); 907 aResult.append(v2); 908 v1 = v2; 909 } 910 } 911 } 912 else 913 { 914 // the last triangle has not been altered, simply copy to result 915 for(sal_uInt32 i=0; i<3; ++i) 916 aResult.append(stack[i]); 917 } 918 } 919 } 920 921 clipflag <<= 1; 922 } 923 } 924 } 925 926 return aResult; 927 } 928 929 ////////////////////////////////////////////////////////////////////////////// 930 931 } // end of namespace tools 932 } // end of namespace basegfx 933 934 ////////////////////////////////////////////////////////////////////////////// 935 936 // eof 937