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 27 #include <basegfx/polygon/b3dpolygonclipper.hxx> 28 #include <osl/diagnose.h> 29 #include <basegfx/polygon/b3dpolygontools.hxx> 30 #include <basegfx/numeric/ftools.hxx> 31 #include <basegfx/matrix/b3dhommatrix.hxx> 32 #include <basegfx/polygon/b3dpolygontools.hxx> 33 #include <basegfx/range/b3drange.hxx> 34 #include <basegfx/point/b2dpoint.hxx> 35 #include <basegfx/range/b2drange.hxx> 36 #include <basegfx/color/bcolor.hxx> 37 38 ////////////////////////////////////////////////////////////////////////////// 39 40 namespace basegfx 41 { 42 namespace 43 { impIsInside(const B3DPoint & rCandidate,double fPlaneOffset,tools::B3DOrientation ePlaneOrthogonal)44 inline bool impIsInside(const B3DPoint& rCandidate, double fPlaneOffset, tools::B3DOrientation ePlaneOrthogonal) 45 { 46 if(tools::B3DORIENTATION_X == ePlaneOrthogonal) 47 { 48 return fTools::moreOrEqual(rCandidate.getX(), fPlaneOffset); 49 } 50 else if(tools::B3DORIENTATION_Y == ePlaneOrthogonal) 51 { 52 return fTools::moreOrEqual(rCandidate.getY(), fPlaneOffset); 53 } 54 else 55 { 56 return fTools::moreOrEqual(rCandidate.getZ(), fPlaneOffset); 57 } 58 } 59 impGetCut(const B3DPoint & rCurrent,const B3DPoint & rNext,double fPlaneOffset,tools::B3DOrientation ePlaneOrthogonal)60 inline double impGetCut(const B3DPoint& rCurrent, const B3DPoint& rNext, double fPlaneOffset, tools::B3DOrientation ePlaneOrthogonal) 61 { 62 if(tools::B3DORIENTATION_X == ePlaneOrthogonal) 63 { 64 return ((fPlaneOffset - rCurrent.getX())/(rNext.getX() - rCurrent.getX())); 65 } 66 else if(tools::B3DORIENTATION_Y == ePlaneOrthogonal) 67 { 68 return ((fPlaneOffset - rCurrent.getY())/(rNext.getY() - rCurrent.getY())); 69 } 70 else 71 { 72 return ((fPlaneOffset - rCurrent.getZ())/(rNext.getZ() - rCurrent.getZ())); 73 } 74 } 75 impAppendCopy(B3DPolygon & rDest,const B3DPolygon & rSource,sal_uInt32 nIndex)76 void impAppendCopy(B3DPolygon& rDest, const B3DPolygon& rSource, sal_uInt32 nIndex) 77 { 78 rDest.append(rSource.getB3DPoint(nIndex)); 79 80 if(rSource.areBColorsUsed()) 81 { 82 rDest.setBColor(rDest.count() - 1L, rSource.getBColor(nIndex)); 83 } 84 85 if(rSource.areNormalsUsed()) 86 { 87 rDest.setNormal(rDest.count() - 1L, rSource.getNormal(nIndex)); 88 } 89 90 if(rSource.areTextureCoordinatesUsed()) 91 { 92 rDest.setTextureCoordinate(rDest.count() - 1L, rSource.getTextureCoordinate(nIndex)); 93 } 94 } 95 impAppendInterpolate(B3DPolygon & rDest,const B3DPolygon & rSource,sal_uInt32 nIndA,sal_uInt32 nIndB,double fCut)96 void impAppendInterpolate(B3DPolygon& rDest, const B3DPolygon& rSource, sal_uInt32 nIndA, sal_uInt32 nIndB, double fCut) 97 { 98 const B3DPoint aCurrPoint(rSource.getB3DPoint(nIndA)); 99 const B3DPoint aNextPoint(rSource.getB3DPoint(nIndB)); 100 rDest.append(interpolate(aCurrPoint, aNextPoint, fCut)); 101 102 if(rSource.areBColorsUsed()) 103 { 104 const BColor aCurrBColor(rSource.getBColor(nIndA)); 105 const BColor aNextBColor(rSource.getBColor(nIndB)); 106 rDest.setBColor(rDest.count() - 1L, interpolate(aCurrBColor, aNextBColor, fCut)); 107 } 108 109 if(rSource.areNormalsUsed()) 110 { 111 const B3DVector aCurrVector(rSource.getNormal(nIndA)); 112 const B3DVector aNextVector(rSource.getNormal(nIndB)); 113 rDest.setNormal(rDest.count() - 1L, interpolate(aCurrVector, aNextVector, fCut)); 114 } 115 116 if(rSource.areTextureCoordinatesUsed()) 117 { 118 const B2DPoint aCurrTxCo(rSource.getTextureCoordinate(nIndA)); 119 const B2DPoint aNextTxCo(rSource.getTextureCoordinate(nIndB)); 120 rDest.setTextureCoordinate(rDest.count() - 1L, interpolate(aCurrTxCo, aNextTxCo, fCut)); 121 } 122 } 123 } 124 } // end of namespace basegfx 125 126 ////////////////////////////////////////////////////////////////////////////// 127 128 namespace basegfx 129 { 130 namespace tools 131 { clipPolygonOnOrthogonalPlane(const B3DPolygon & rCandidate,B3DOrientation ePlaneOrthogonal,bool bClipPositive,double fPlaneOffset,bool bStroke)132 B3DPolyPolygon clipPolygonOnOrthogonalPlane(const B3DPolygon& rCandidate, B3DOrientation ePlaneOrthogonal, bool bClipPositive, double fPlaneOffset, bool bStroke) 133 { 134 B3DPolyPolygon aRetval; 135 136 if(rCandidate.count()) 137 { 138 const B3DRange aCandidateRange(getRange(rCandidate)); 139 140 if(B3DORIENTATION_X == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinX(), fPlaneOffset)) 141 { 142 // completely above and on the clip plane. 143 if(bClipPositive) 144 { 145 // add completely 146 aRetval.append(rCandidate); 147 } 148 } 149 else if(B3DORIENTATION_X == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxX(), fPlaneOffset)) 150 { 151 // completely below and on the clip plane. 152 if(!bClipPositive) 153 { 154 // add completely 155 aRetval.append(rCandidate); 156 } 157 } 158 else if(B3DORIENTATION_Y == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinY(), fPlaneOffset)) 159 { 160 // completely above and on the clip plane. 161 if(bClipPositive) 162 { 163 // add completely 164 aRetval.append(rCandidate); 165 } 166 } 167 else if(B3DORIENTATION_Y == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxY(), fPlaneOffset)) 168 { 169 // completely below and on the clip plane. 170 if(!bClipPositive) 171 { 172 // add completely 173 aRetval.append(rCandidate); 174 } 175 } 176 else if(B3DORIENTATION_Z == ePlaneOrthogonal && fTools::moreOrEqual(aCandidateRange.getMinZ(), fPlaneOffset)) 177 { 178 // completely above and on the clip plane. 179 if(bClipPositive) 180 { 181 // add completely 182 aRetval.append(rCandidate); 183 } 184 } 185 else if(B3DORIENTATION_Z == ePlaneOrthogonal && fTools::lessOrEqual(aCandidateRange.getMaxZ(), fPlaneOffset)) 186 { 187 // completely below and on the clip plane. 188 if(!bClipPositive) 189 { 190 // add completely 191 aRetval.append(rCandidate); 192 } 193 } 194 else 195 { 196 // prepare loop(s) 197 B3DPolygon aNewPolygon; 198 B3DPoint aCurrent(rCandidate.getB3DPoint(0L)); 199 const sal_uInt32 nPointCount(rCandidate.count()); 200 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 201 bool bCurrentInside(impIsInside(aCurrent, fPlaneOffset, ePlaneOrthogonal) == bClipPositive); 202 203 if(bCurrentInside) 204 { 205 impAppendCopy(aNewPolygon, rCandidate, 0L); 206 } 207 208 if(bStroke) 209 { 210 // open polygon, create clipped line snippets. 211 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 212 { 213 // get next point data 214 const sal_uInt32 nNextIndex((a + 1L == nPointCount) ? 0L : a + 1L); 215 const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex)); 216 const bool bNextInside(impIsInside(aNext, fPlaneOffset, ePlaneOrthogonal) == bClipPositive); 217 218 if(bCurrentInside != bNextInside) 219 { 220 // change inside/outside 221 if(bNextInside) 222 { 223 // entering, finish existing and start new line polygon 224 if(aNewPolygon.count() > 1L) 225 { 226 aRetval.append(aNewPolygon); 227 } 228 229 aNewPolygon.clear(); 230 } 231 232 // calculate and add cut point 233 const double fCut(impGetCut(aCurrent, aNext, fPlaneOffset, ePlaneOrthogonal)); 234 impAppendInterpolate(aNewPolygon, rCandidate, a, nNextIndex, fCut); 235 236 // pepare next step 237 bCurrentInside = bNextInside; 238 } 239 240 if(bNextInside) 241 { 242 impAppendCopy(aNewPolygon, rCandidate, nNextIndex); 243 } 244 245 // pepare next step 246 aCurrent = aNext; 247 } 248 249 if(aNewPolygon.count() > 1L) 250 { 251 aRetval.append(aNewPolygon); 252 } 253 } 254 else 255 { 256 // closed polygon, create single clipped closed polygon 257 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 258 { 259 // get next point data, use offset 260 const sal_uInt32 nNextIndex((a + 1L == nPointCount) ? 0L : a + 1L); 261 const B3DPoint aNext(rCandidate.getB3DPoint(nNextIndex)); 262 const bool bNextInside(impIsInside(aNext, fPlaneOffset, ePlaneOrthogonal) == bClipPositive); 263 264 if(bCurrentInside != bNextInside) 265 { 266 // calculate and add cut point 267 const double fCut(impGetCut(aCurrent, aNext, fPlaneOffset, ePlaneOrthogonal)); 268 impAppendInterpolate(aNewPolygon, rCandidate, a, nNextIndex, fCut); 269 270 // pepare next step 271 bCurrentInside = bNextInside; 272 } 273 274 if(bNextInside && nNextIndex) 275 { 276 impAppendCopy(aNewPolygon, rCandidate, nNextIndex); 277 } 278 279 // pepare next step 280 aCurrent = aNext; 281 } 282 283 if(aNewPolygon.count() > 2L) 284 { 285 aNewPolygon.setClosed(true); 286 aRetval.append(aNewPolygon); 287 } 288 } 289 } 290 } 291 292 return aRetval; 293 } 294 clipPolyPolygonOnOrthogonalPlane(const B3DPolyPolygon & rCandidate,B3DOrientation ePlaneOrthogonal,bool bClipPositive,double fPlaneOffset,bool bStroke)295 B3DPolyPolygon clipPolyPolygonOnOrthogonalPlane(const B3DPolyPolygon& rCandidate, B3DOrientation ePlaneOrthogonal, bool bClipPositive, double fPlaneOffset, bool bStroke) 296 { 297 B3DPolyPolygon aRetval; 298 299 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 300 { 301 aRetval.append(clipPolygonOnOrthogonalPlane(rCandidate.getB3DPolygon(a), ePlaneOrthogonal, bClipPositive, fPlaneOffset, bStroke)); 302 } 303 304 return aRetval; 305 } 306 clipPolyPolygonOnRange(const B3DPolyPolygon & rCandidate,const B2DRange & rRange,bool bInside,bool bStroke)307 B3DPolyPolygon clipPolyPolygonOnRange(const B3DPolyPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke) 308 { 309 B3DPolyPolygon aRetval; 310 311 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 312 { 313 aRetval.append(clipPolygonOnRange(rCandidate.getB3DPolygon(a), rRange, bInside, bStroke)); 314 } 315 316 return aRetval; 317 } 318 clipPolygonOnRange(const B3DPolygon & rCandidate,const B2DRange & rRange,bool bInside,bool bStroke)319 B3DPolyPolygon clipPolygonOnRange(const B3DPolygon& rCandidate, const B2DRange& rRange, bool bInside, bool bStroke) 320 { 321 B3DPolyPolygon aRetval; 322 323 if(rRange.isEmpty()) 324 { 325 // clipping against an empty range. Nothing is inside an empty range, so the polygon 326 // is outside the range. So only return if not inside is wanted 327 if(!bInside && rCandidate.count()) 328 { 329 aRetval.append(rCandidate); 330 } 331 } 332 else if(rCandidate.count()) 333 { 334 const B3DRange aCandidateRange3D(getRange(rCandidate)); 335 const B2DRange aCandidateRange( 336 aCandidateRange3D.getMinX(), aCandidateRange3D.getMinY(), 337 aCandidateRange3D.getMaxX(), aCandidateRange3D.getMaxY()); 338 339 if(rRange.isInside(aCandidateRange)) 340 { 341 // candidate is completely inside given range, nothing to do. Is also true with curves. 342 if(bInside) 343 { 344 aRetval.append(rCandidate); 345 } 346 } 347 else if(!rRange.overlaps(aCandidateRange)) 348 { 349 // candidate is completely outside given range, nothing to do. Is also true with curves. 350 if(!bInside) 351 { 352 aRetval.append(rCandidate); 353 } 354 } 355 else 356 { 357 // clip against the six planes of the range 358 // against lower X 359 aRetval = clipPolygonOnOrthogonalPlane(rCandidate, tools::B3DORIENTATION_X, bInside, rRange.getMinX(), bStroke); 360 361 if(aRetval.count()) 362 { 363 // against lower Y 364 if(1L == aRetval.count()) 365 { 366 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Y, bInside, rRange.getMinY(), bStroke); 367 } 368 else 369 { 370 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Y, bInside, rRange.getMinY(), bStroke); 371 } 372 373 if(aRetval.count()) 374 { 375 // against higher X 376 if(1L == aRetval.count()) 377 { 378 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_X, !bInside, rRange.getMaxX(), bStroke); 379 } 380 else 381 { 382 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_X, !bInside, rRange.getMaxX(), bStroke); 383 } 384 385 if(aRetval.count()) 386 { 387 // against higher Y 388 if(1L == aRetval.count()) 389 { 390 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Y, !bInside, rRange.getMaxY(), bStroke); 391 } 392 else 393 { 394 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Y, !bInside, rRange.getMaxY(), bStroke); 395 } 396 } 397 } 398 } 399 } 400 } 401 402 return aRetval; 403 } 404 clipPolyPolygonOnRange(const B3DPolyPolygon & rCandidate,const B3DRange & rRange,bool bInside,bool bStroke)405 B3DPolyPolygon clipPolyPolygonOnRange(const B3DPolyPolygon& rCandidate, const B3DRange& rRange, bool bInside, bool bStroke) 406 { 407 B3DPolyPolygon aRetval; 408 409 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 410 { 411 aRetval.append(clipPolygonOnRange(rCandidate.getB3DPolygon(a), rRange, bInside, bStroke)); 412 } 413 414 return aRetval; 415 } 416 clipPolygonOnRange(const B3DPolygon & rCandidate,const B3DRange & rRange,bool bInside,bool bStroke)417 B3DPolyPolygon clipPolygonOnRange(const B3DPolygon& rCandidate, const B3DRange& rRange, bool bInside, bool bStroke) 418 { 419 B3DPolyPolygon aRetval; 420 421 if(rRange.isEmpty()) 422 { 423 // clipping against an empty range. Nothing is inside an empty range, so the polygon 424 // is outside the range. So only return if not inside is wanted 425 if(!bInside && rCandidate.count()) 426 { 427 aRetval.append(rCandidate); 428 } 429 } 430 else if(rCandidate.count()) 431 { 432 const B3DRange aCandidateRange(getRange(rCandidate)); 433 434 if(rRange.isInside(aCandidateRange)) 435 { 436 // candidate is completely inside given range, nothing to do. Is also true with curves. 437 if(bInside) 438 { 439 aRetval.append(rCandidate); 440 } 441 } 442 else if(!rRange.overlaps(aCandidateRange)) 443 { 444 // candidate is completely outside given range, nothing to do. Is also true with curves. 445 if(!bInside) 446 { 447 aRetval.append(rCandidate); 448 } 449 } 450 else 451 { 452 // clip against X,Y first and see if there's something left 453 const B2DRange aCandidateRange2D(rRange.getMinX(), rRange.getMinY(), rRange.getMaxX(), rRange.getMaxY()); 454 aRetval = clipPolygonOnRange(rCandidate, aCandidateRange2D, bInside, bStroke); 455 456 if(aRetval.count()) 457 { 458 // against lower Z 459 if(1L == aRetval.count()) 460 { 461 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Z, bInside, rRange.getMinZ(), bStroke); 462 } 463 else 464 { 465 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Z, bInside, rRange.getMinZ(), bStroke); 466 } 467 468 if(aRetval.count()) 469 { 470 // against higher Z 471 if(1L == aRetval.count()) 472 { 473 aRetval = clipPolygonOnOrthogonalPlane(aRetval.getB3DPolygon(0L), tools::B3DORIENTATION_Z, !bInside, rRange.getMaxZ(), bStroke); 474 } 475 else 476 { 477 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_Z, !bInside, rRange.getMaxZ(), bStroke); 478 } 479 } 480 } 481 } 482 } 483 484 return aRetval; 485 } 486 clipPolygonOnPlane(const B3DPolygon & rCandidate,const B3DPoint & rPointOnPlane,const B3DVector & rPlaneNormal,bool bClipPositive,bool bStroke)487 B3DPolyPolygon clipPolygonOnPlane(const B3DPolygon& rCandidate, const B3DPoint& rPointOnPlane, const B3DVector& rPlaneNormal, bool bClipPositive, bool bStroke) 488 { 489 B3DPolyPolygon aRetval; 490 491 if(rPlaneNormal.equalZero()) 492 { 493 // not really a plane definition, return polygon 494 aRetval.append(rCandidate); 495 } 496 else if(rCandidate.count()) 497 { 498 // build transform to project planeNormal on X-Axis and pointOnPlane to null point 499 B3DHomMatrix aMatrixTransform; 500 aMatrixTransform.translate(-rPointOnPlane.getX(), -rPointOnPlane.getY(), -rPointOnPlane.getZ()); 501 const double fRotInXY(atan2(rPlaneNormal.getY(), rPlaneNormal.getX())); 502 const double fRotInXZ(atan2(-rPlaneNormal.getZ(), rPlaneNormal.getXYLength())); 503 if(!fTools::equalZero(fRotInXY) || !fTools::equalZero(fRotInXZ)) 504 { 505 aMatrixTransform.rotate(0.0, fRotInXZ, fRotInXY); 506 } 507 508 // transform polygon to clip scenario 509 B3DPolygon aCandidate(rCandidate); 510 aCandidate.transform(aMatrixTransform); 511 512 // clip on YZ plane 513 aRetval = clipPolygonOnOrthogonalPlane(aCandidate, tools::B3DORIENTATION_X, bClipPositive, 0.0, bStroke); 514 515 if(aRetval.count()) 516 { 517 // if there is a result, it needs to be transformed back 518 aMatrixTransform.invert(); 519 aRetval.transform(aMatrixTransform); 520 } 521 } 522 523 return aRetval; 524 } 525 clipPolyPolygonOnPlane(const B3DPolyPolygon & rCandidate,const B3DPoint & rPointOnPlane,const B3DVector & rPlaneNormal,bool bClipPositive,bool bStroke)526 B3DPolyPolygon clipPolyPolygonOnPlane(const B3DPolyPolygon& rCandidate, const B3DPoint& rPointOnPlane, const B3DVector& rPlaneNormal, bool bClipPositive, bool bStroke) 527 { 528 B3DPolyPolygon aRetval; 529 530 if(rPlaneNormal.equalZero()) 531 { 532 // not really a plane definition, return polygon 533 aRetval = rCandidate; 534 } 535 else if(rCandidate.count()) 536 { 537 // build transform to project planeNormal on X-Axis and pointOnPlane to null point 538 B3DHomMatrix aMatrixTransform; 539 aMatrixTransform.translate(-rPointOnPlane.getX(), -rPointOnPlane.getY(), -rPointOnPlane.getZ()); 540 const double fRotInXY(atan2(rPlaneNormal.getY(), rPlaneNormal.getX())); 541 const double fRotInXZ(atan2(-rPlaneNormal.getZ(), rPlaneNormal.getXYLength())); 542 if(!fTools::equalZero(fRotInXY) || !fTools::equalZero(fRotInXZ)) 543 { 544 aMatrixTransform.rotate(0.0, fRotInXZ, fRotInXY); 545 } 546 547 // transform polygon to clip scenario 548 aRetval = rCandidate; 549 aRetval.transform(aMatrixTransform); 550 551 // clip on YZ plane 552 aRetval = clipPolyPolygonOnOrthogonalPlane(aRetval, tools::B3DORIENTATION_X, bClipPositive, 0.0, bStroke); 553 554 if(aRetval.count()) 555 { 556 // if there is a result, it needs to be transformed back 557 aMatrixTransform.invert(); 558 aRetval.transform(aMatrixTransform); 559 } 560 } 561 562 return aRetval; 563 } 564 565 } // end of namespace tools 566 } // end of namespace basegfx 567 568 ////////////////////////////////////////////////////////////////////////////// 569 570 // eof 571