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