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/b2dpolypolygonrasterconverter.hxx> 32 33 #include <basegfx/numeric/ftools.hxx> 34 #include <basegfx/polygon/b2dpolygon.hxx> 35 #include <basegfx/polygon/b2dpolygontools.hxx> 36 #include <basegfx/polygon/b2dpolypolygontools.hxx> 37 38 #include <boost/mem_fn.hpp> 39 40 #include <algorithm> 41 42 namespace basegfx 43 { 44 class radixSort { 45 46 //! public interface 47 public: 48 49 //! default constructor 50 radixSort( void ); 51 52 //! destructor 53 ~radixSort( void ); 54 55 bool sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ); 56 57 inline sal_uInt32 *indices( void ) const { return m_indices1; } 58 59 //! private attributes 60 private: 61 62 // current size of index list 63 sal_uInt32 m_current_size; 64 65 // last known size of index list 66 sal_uInt32 m_previous_size; 67 68 // index lists 69 sal_uInt32 *m_indices1; 70 sal_uInt32 *m_indices2; 71 72 sal_uInt32 m_counter[256*4]; 73 sal_uInt32 m_offset[256]; 74 75 //! private methods 76 private: 77 78 bool resize( sal_uInt32 nNumElements ); 79 inline void reset_indices( void ); 80 bool prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ); 81 }; 82 83 inline radixSort::radixSort( void ) { 84 85 m_indices1 = NULL; 86 m_indices2 = NULL; 87 m_current_size = 0; 88 m_previous_size = 0; 89 90 reset_indices(); 91 } 92 93 inline radixSort::~radixSort( void ) { 94 95 delete [] m_indices2; 96 delete [] m_indices1; 97 } 98 99 bool radixSort::resize( sal_uInt32 nNumElements ) { 100 101 if(nNumElements==m_previous_size) 102 return true; 103 104 if(nNumElements > m_current_size) { 105 106 // release index lists 107 if(m_indices2) 108 delete [] m_indices2; 109 if(m_indices1) 110 delete [] m_indices1; 111 112 // allocate new index lists 113 m_indices1 = new sal_uInt32[nNumElements]; 114 m_indices2 = new sal_uInt32[nNumElements]; 115 116 // check for out of memory situation 117 if(!m_indices1 || !m_indices2) { 118 delete [] m_indices1; 119 delete [] m_indices2; 120 m_indices1 = NULL; 121 m_indices2 = NULL; 122 m_current_size = 0; 123 return false; 124 } 125 126 m_current_size = nNumElements; 127 } 128 129 m_previous_size = nNumElements; 130 131 // initialize indices 132 reset_indices(); 133 134 return true; 135 } 136 137 inline void radixSort::reset_indices( void ) { 138 139 for(sal_uInt32 i=0;i<m_current_size;i++) 140 m_indices1[i] = i; 141 } 142 143 bool radixSort::prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) { 144 145 // clear counters 146 sal_uInt32 *ptr = m_counter; 147 for(int i=0; i<64; ++i) 148 { 149 *ptr++ = 0; 150 *ptr++ = 0; 151 *ptr++ = 0; 152 *ptr++ = 0; 153 *ptr++ = 0; 154 *ptr++ = 0; 155 *ptr++ = 0; 156 *ptr++ = 0; 157 *ptr++ = 0; 158 *ptr++ = 0; 159 *ptr++ = 0; 160 *ptr++ = 0; 161 *ptr++ = 0; 162 *ptr++ = 0; 163 *ptr++ = 0; 164 *ptr++ = 0; 165 } 166 167 // prepare pointers to relevant memory addresses 168 sal_uInt8 *p = (sal_uInt8*)pInput; 169 sal_uInt8 *pe = p+(nNumElements*dwStride); 170 sal_uInt32 *h0= &m_counter[0]; 171 sal_uInt32 *h1= &m_counter[256]; 172 sal_uInt32 *h2= &m_counter[512]; 173 sal_uInt32 *h3= &m_counter[768]; 174 175 sal_uInt32 *Indices = m_indices1; 176 float previous_value = *(float *)(((sal_uInt8 *)pInput)+(m_indices1[0]*dwStride)); 177 bool bSorted = true; 178 while(p!=pe) { 179 float value = *(float *)(((sal_uInt8 *)pInput)+((*Indices++)*dwStride)); 180 if(value<previous_value) { 181 bSorted = false; 182 break; 183 } 184 previous_value = value; 185 h0[*p++]++; 186 h1[*p++]++; 187 h2[*p++]++; 188 h3[*p++]++; 189 p += dwStride-4; 190 } 191 if(bSorted) 192 return true; 193 while(p!=pe) { 194 h0[*p++]++; 195 h1[*p++]++; 196 h2[*p++]++; 197 h3[*p++]++; 198 p += dwStride-4; 199 } 200 return false; 201 } 202 203 bool radixSort::sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) { 204 205 if(!(pInput)) 206 return false; 207 if(!(nNumElements)) 208 return false; 209 if(!(resize(nNumElements))) 210 return false; 211 212 // prepare radix counters, return if already sorted 213 if(prepareCounters(pInput,nNumElements,dwStride)) 214 return true; 215 216 // count number of negative values 217 sal_uInt32 num_negatives = 0; 218 sal_uInt32 *h3= &m_counter[768]; 219 for(sal_uInt32 i=128;i<256;i++) 220 num_negatives += h3[i]; 221 222 // perform passes, one for each byte 223 for(sal_uInt32 j=0;j<4;j++) { 224 225 // ignore this pass if all values have the same byte 226 bool bRun = true; 227 sal_uInt32 *current_counter = &m_counter[j<<8]; 228 sal_uInt8 unique_value = *(((sal_uInt8*)pInput)+j); 229 if(current_counter[unique_value]==nNumElements) 230 bRun=false; 231 232 // does the incoming byte contain the sign bit? 233 sal_uInt32 i; 234 if(j!=3) { 235 if(bRun) { 236 m_offset[0] = 0; 237 for(i=1;i<256;i++) 238 m_offset[i] = m_offset[i-1] + current_counter[i-1]; 239 sal_uInt8 *InputBytes = (sal_uInt8 *)pInput; 240 sal_uInt32 *Indices = m_indices1; 241 sal_uInt32 *IndicesEnd = &m_indices1[nNumElements]; 242 InputBytes += j; 243 while(Indices!=IndicesEnd) { 244 sal_uInt32 id = *Indices++; 245 m_indices2[m_offset[InputBytes[id*dwStride]]++] = id; 246 } 247 sal_uInt32 *Tmp = m_indices1; 248 m_indices1 = m_indices2; 249 m_indices2 = Tmp; 250 } 251 } 252 else { 253 if(bRun) { 254 m_offset[0] = num_negatives; 255 for(i=1;i<128;i++) 256 m_offset[i] = m_offset[i-1] + current_counter[i-1]; 257 m_offset[255] = 0; 258 for(i=0;i<127;i++) 259 m_offset[254-i] = m_offset[255-i] + current_counter[255-i]; 260 for(i=128;i<256;i++) 261 m_offset[i] += current_counter[i]; 262 for(i=0;i<nNumElements;i++) { 263 sal_uInt32 Radix = (*(sal_uInt32 *)(((sal_uInt8 *)pInput)+(m_indices1[i]*dwStride)))>>24; 264 if(Radix<128) m_indices2[m_offset[Radix]++] = m_indices1[i]; 265 else m_indices2[--m_offset[Radix]] = m_indices1[i]; 266 } 267 sal_uInt32 *Tmp = m_indices1; 268 m_indices1 = m_indices2; 269 m_indices2 = Tmp; 270 } 271 else { 272 if(unique_value>=128) { 273 for(i=0;i<nNumElements;i++) 274 m_indices2[i] = m_indices1[nNumElements-i-1]; 275 sal_uInt32 *Tmp = m_indices1; 276 m_indices1 = m_indices2; 277 m_indices2 = Tmp; 278 } 279 } 280 } 281 } 282 283 return true; 284 } 285 286 //************************************************************ 287 // Internal vertex storage of B2DPolyPolygonRasterConverter 288 //************************************************************ 289 290 inline B2DPolyPolygonRasterConverter::Vertex::Vertex() : 291 aP1(), 292 aP2(), 293 bDownwards( true ) 294 { 295 } 296 297 inline B2DPolyPolygonRasterConverter::Vertex::Vertex( const B2DPoint& rP1, const B2DPoint& rP2, bool bDown ) : 298 aP1( rP1 ), 299 aP2( rP2 ), 300 bDownwards( bDown ) 301 { 302 } 303 304 305 //************************************************************ 306 // Helper class for holding horizontal line segments during raster 307 // conversion 308 //************************************************************ 309 310 namespace 311 { 312 class ImplLineNode 313 { 314 public: 315 sal_Int32 mnYCounter; 316 float mfXPos; 317 float mfXDelta; 318 bool mbDownwards; 319 320 public: 321 /**rP1 and rP2 must not have equal y values, when rounded 322 to integer! 323 */ 324 ImplLineNode(const B2DPoint& rP1, const B2DPoint& rP2, bool bDown) : 325 mnYCounter( fround(rP2.getY()) - fround(rP1.getY()) ), 326 mfXPos( (float)(rP1.getX()) ), 327 mfXDelta((float) ((rP2.getX() - rP1.getX()) / mnYCounter) ), 328 mbDownwards( bDown ) 329 { 330 } 331 332 /// get current x position 333 const float& getXPos() const 334 { 335 return mfXPos; 336 } 337 338 /// returns true, if line ends on this Y value 339 float nextLine() 340 { 341 if(mnYCounter>=0) 342 { 343 // go one step in Y 344 mfXPos += mfXDelta; 345 --mnYCounter; 346 return mfXDelta; 347 } 348 349 return 0.0f; 350 } 351 352 bool isEnded() 353 { 354 return mnYCounter<=0; 355 } 356 357 bool isDownwards() 358 { 359 return mbDownwards; 360 } 361 }; 362 } 363 364 typedef ::std::vector<ImplLineNode> VectorOfLineNodes; 365 366 367 //************************************************************ 368 // Base2D PolyPolygon Raster Converter (Rasterizer) 369 //************************************************************ 370 371 namespace 372 { 373 struct VertexComparator 374 { 375 bool operator()( const B2DPolyPolygonRasterConverter::Vertex& rLHS, 376 const B2DPolyPolygonRasterConverter::Vertex& rRHS ) 377 { 378 return rLHS.aP1.getX() < rRHS.aP1.getX(); 379 } 380 }; 381 } 382 383 void B2DPolyPolygonRasterConverter::init() 384 { 385 if(!maPolyPolyRectangle.isEmpty()) 386 { 387 const sal_Int32 nMinY( fround(maPolyPolyRectangle.getMinY()) ); 388 const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY); 389 390 maScanlines.resize( nScanlines+1 ); 391 392 // add all polygons 393 for( sal_uInt32 i(0), nCount(maPolyPolygon.count()); 394 i < nCount; 395 ++i ) 396 { 397 // add all vertices 398 const B2DPolygon& rPoly( maPolyPolygon.getB2DPolygon(i) ); 399 for( sal_uInt32 k(0), nVertices(rPoly.count()); 400 k<nVertices; 401 ++k ) 402 { 403 const B2DPoint& rP1( rPoly.getB2DPoint(k) ); 404 const B2DPoint& rP2( rPoly.getB2DPoint( (k + 1) % nVertices ) ); 405 406 const sal_Int32 nVertexYP1( fround(rP1.getY()) ); 407 const sal_Int32 nVertexYP2( fround(rP2.getY()) ); 408 409 // insert only vertices which are not strictly 410 // horizontal. Note that the ImplLineNode relies on 411 // this. 412 if(nVertexYP1 != nVertexYP2) 413 { 414 if( nVertexYP2 < nVertexYP1 ) 415 { 416 const sal_Int32 nStartScanline(nVertexYP2 - nMinY); 417 418 // swap edges 419 maScanlines[ nStartScanline ].push_back( Vertex(rP2, rP1, false) ); 420 } 421 else 422 { 423 const sal_Int32 nStartScanline(nVertexYP1 - nMinY); 424 425 maScanlines[ nStartScanline ].push_back( Vertex(rP1, rP2, true) ); 426 } 427 } 428 } 429 } 430 431 // now sort all scanlines, with increasing x coordinates 432 VectorOfVertexVectors::iterator aIter( maScanlines.begin() ); 433 VectorOfVertexVectors::iterator aEnd( maScanlines.end() ); 434 while( aIter != aEnd ) 435 { 436 ::std::sort( aIter->begin(), 437 aIter->end(), 438 VertexComparator() ); 439 ++aIter; 440 } 441 } 442 } 443 444 B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPoly ) : 445 maPolyPolygon( rPolyPoly ), 446 maPolyPolyRectangle( tools::getRange( rPolyPoly ) ), 447 maScanlines() 448 { 449 init(); 450 } 451 452 namespace 453 { 454 B2DRectangle getCombinedBounds( const B2DPolyPolygon& rPolyPolyRaster, 455 const B2DRectangle& rRasterArea ) 456 { 457 B2DRectangle aRect( tools::getRange( rPolyPolyRaster ) ); 458 aRect.expand( rRasterArea ); 459 460 return aRect; 461 } 462 } 463 464 B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPolyRaster, 465 const B2DRectangle& rRasterArea ) : 466 maPolyPolygon( rPolyPolyRaster ), 467 maPolyPolyRectangle( 468 getCombinedBounds( rPolyPolyRaster, 469 rRasterArea ) ), 470 maScanlines() 471 { 472 init(); 473 } 474 475 B2DPolyPolygonRasterConverter::~B2DPolyPolygonRasterConverter() 476 { 477 } 478 479 namespace 480 { 481 class LineNodeGenerator 482 { 483 public: 484 LineNodeGenerator( VectorOfLineNodes& rActiveVertices ) : 485 mrActiveVertices( rActiveVertices ) 486 { 487 } 488 489 void operator()( const B2DPolyPolygonRasterConverter::Vertex& rVertex ) 490 { 491 mrActiveVertices.push_back( ImplLineNode(rVertex.aP1, 492 rVertex.aP2, 493 rVertex.bDownwards) ); 494 } 495 496 private: 497 VectorOfLineNodes& mrActiveVertices; 498 }; 499 500 struct LineNodeComparator 501 { 502 bool operator()( const ImplLineNode& rLHS, const ImplLineNode& rRHS ) 503 { 504 return rLHS.getXPos() < rRHS.getXPos(); 505 } 506 }; 507 } 508 509 void B2DPolyPolygonRasterConverter::rasterConvert( FillRule eFillRule ) 510 { 511 if( maScanlines.empty() ) 512 return; // no scanlines at all -> bail out 513 514 const sal_Int32 nMinY( fround(maPolyPolyRectangle.getMinY()) ); 515 const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY); 516 517 // Vector of currently active vertices. A vertex is active, if 518 // it crosses or touches the current scanline. 519 VectorOfLineNodes aActiveVertices; 520 521 // mickey's optimized version... 522 radixSort rs; 523 std::size_t nb(0); 524 std::size_t nb_previous(0); 525 bool bSort(false); 526 527 // process each scanline 528 for( sal_Int32 y(0); y <= nScanlines; ++y ) 529 { 530 // add vertices which start at current scanline into 531 // active vertex vector 532 ::std::for_each( maScanlines[y].begin(), 533 maScanlines[y].end(), 534 LineNodeGenerator( aActiveVertices ) ); 535 nb = aActiveVertices.size(); 536 if(nb != nb_previous) 537 { 538 nb_previous = nb; 539 bSort = true; 540 } 541 542 // sort with increasing X 543 if(bSort) 544 { 545 bSort = false; 546 547 if( nb ) 548 { 549 rs.sort(&aActiveVertices[0].mfXPos, 550 nb, 551 sizeof(ImplLineNode)); 552 } 553 } 554 555 const std::size_t nLen( nb ); 556 if( !nLen ) 557 { 558 // empty scanline - call derived with an 'off' span 559 // for the full width 560 span( maPolyPolyRectangle.getMinX(), 561 maPolyPolyRectangle.getMaxX(), 562 nMinY + y, 563 false ); 564 } 565 else 566 { 567 const sal_Int32 nCurrY( nMinY + y ); 568 569 // scanline not empty - forward all scans to derived, 570 // according to selected fill rule 571 572 // TODO(P1): Maybe allow these 'off' span calls to be 573 // switched off (or all 'on' span calls, depending on 574 // use case scenario) 575 576 // sorting didn't change the order of the elements 577 // in memory but prepared a list of indices in sorted order. 578 // thus we now process the nodes with an additional indirection. 579 sal_uInt32 *sorted = rs.indices(); 580 581 // call derived with 'off' span for everything left of first active span 582 if( aActiveVertices[sorted[0]].getXPos() > maPolyPolyRectangle.getMinX() ) 583 { 584 span( maPolyPolyRectangle.getMinX(), 585 aActiveVertices[sorted[0]].getXPos(), 586 nCurrY, 587 false ); 588 } 589 590 switch( eFillRule ) 591 { 592 default: 593 OSL_ENSURE(false, 594 "B2DPolyPolygonRasterConverter::rasterConvert(): Unexpected fill rule"); 595 return; 596 597 case FillRule_EVEN_ODD: 598 // process each span in current scanline, with 599 // even-odd fill rule 600 for( ::std::size_t i(0), nLength(aActiveVertices.size()); 601 i+1 < nLength; 602 ++i ) 603 { 604 sal_uInt32 nIndex = sorted[i]; 605 sal_uInt32 nNextIndex = sorted[i+1]; 606 span( aActiveVertices[nIndex].getXPos(), 607 aActiveVertices[nNextIndex].getXPos(), 608 nCurrY, 609 i % 2 == 0 ); 610 611 float delta = aActiveVertices[nIndex].nextLine(); 612 if(delta > 0.0f) 613 { 614 if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos()) 615 bSort = true; 616 } 617 else if(delta < 0.0f) 618 { 619 if(i) 620 { 621 sal_uInt32 nPrevIndex = sorted[i-1]; 622 if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos()) 623 bSort = true; 624 } 625 } 626 } 627 break; 628 629 case FillRule_NONZERO_WINDING_NUMBER: 630 // process each span in current scanline, with 631 // non-zero winding numbe fill rule 632 sal_Int32 nWindingNumber(0); 633 for( ::std::size_t i(0), nLength(aActiveVertices.size()); 634 i+1 < nLength; 635 ++i ) 636 { 637 sal_uInt32 nIndex = sorted[i]; 638 sal_uInt32 nNextIndex = sorted[i+1]; 639 nWindingNumber += -1 + 2*aActiveVertices[nIndex].isDownwards(); 640 641 span( aActiveVertices[nIndex].getXPos(), 642 aActiveVertices[nNextIndex].getXPos(), 643 nCurrY, 644 nWindingNumber != 0 ); 645 646 float delta = aActiveVertices[nIndex].nextLine(); 647 if(delta > 0.0f) 648 { 649 if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos()) 650 bSort = true; 651 } 652 else if(delta < 0.0f) 653 { 654 if(i) 655 { 656 sal_uInt32 nPrevIndex = sorted[i-1]; 657 if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos()) 658 bSort = true; 659 } 660 } 661 } 662 break; 663 } 664 665 // call derived with 'off' span for everything right of last active span 666 if( aActiveVertices[sorted[nb-1]].getXPos()+1.0 < maPolyPolyRectangle.getMaxX() ) 667 { 668 span( aActiveVertices[sorted[nb-1]].getXPos()+1.0, 669 maPolyPolyRectangle.getMaxX(), 670 nCurrY, 671 false ); 672 } 673 674 // also call nextLine on very last line node 675 sal_uInt32 nIndex = sorted[nb-1]; 676 float delta = aActiveVertices[nIndex].nextLine(); 677 if(delta < 0.0f) 678 { 679 if(nb) 680 { 681 sal_uInt32 nPrevIndex = sorted[nb-2]; 682 if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos()) 683 bSort = true; 684 } 685 } 686 } 687 688 // remove line nodes which have ended on the current scanline 689 aActiveVertices.erase( ::std::remove_if( aActiveVertices.begin(), 690 aActiveVertices.end(), 691 ::boost::mem_fn( &ImplLineNode::isEnded ) ), 692 aActiveVertices.end() ); 693 nb = aActiveVertices.size(); 694 if(nb != nb_previous) 695 { 696 nb_previous = nb; 697 bSort = true; 698 } 699 } 700 } 701 } 702 // eof 703