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