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