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