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