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