1*48cdb363SAndrew Rist /************************************************************** 2cdf0e10cSrcweir * 3*48cdb363SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one 4*48cdb363SAndrew Rist * or more contributor license agreements. See the NOTICE file 5*48cdb363SAndrew Rist * distributed with this work for additional information 6*48cdb363SAndrew Rist * regarding copyright ownership. The ASF licenses this file 7*48cdb363SAndrew Rist * to you under the Apache License, Version 2.0 (the 8*48cdb363SAndrew Rist * "License"); you may not use this file except in compliance 9*48cdb363SAndrew Rist * with the License. You may obtain a copy of the License at 10*48cdb363SAndrew Rist * 11*48cdb363SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0 12*48cdb363SAndrew Rist * 13*48cdb363SAndrew Rist * Unless required by applicable law or agreed to in writing, 14*48cdb363SAndrew Rist * software distributed under the License is distributed on an 15*48cdb363SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16*48cdb363SAndrew Rist * KIND, either express or implied. See the License for the 17*48cdb363SAndrew Rist * specific language governing permissions and limitations 18*48cdb363SAndrew Rist * under the License. 19*48cdb363SAndrew Rist * 20*48cdb363SAndrew Rist *************************************************************/ 21*48cdb363SAndrew Rist 22*48cdb363SAndrew Rist 23cdf0e10cSrcweir 24cdf0e10cSrcweir #ifndef INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX 25cdf0e10cSrcweir #define INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX 26cdf0e10cSrcweir 27cdf0e10cSrcweir #include <basegfx/point/b2dpoint.hxx> 28cdf0e10cSrcweir #include <basegfx/range/b2drange.hxx> 29cdf0e10cSrcweir #include <basegfx/range/b2irange.hxx> 30cdf0e10cSrcweir #include <basegfx/polygon/b2dpolypolygon.hxx> 31cdf0e10cSrcweir #include <basegfx/polygon/b2dpolypolygontools.hxx> 32cdf0e10cSrcweir #include <basegfx/polygon/b2dpolypolygonfillrule.hxx> 33cdf0e10cSrcweir #include <basegfx/numeric/ftools.hxx> 34cdf0e10cSrcweir 35cdf0e10cSrcweir #include <vigra/diff2d.hxx> 36cdf0e10cSrcweir #include <vigra/iteratortraits.hxx> 37cdf0e10cSrcweir 38cdf0e10cSrcweir #include <vector> 39cdf0e10cSrcweir 40cdf0e10cSrcweir 41cdf0e10cSrcweir namespace basebmp 42cdf0e10cSrcweir { 43cdf0e10cSrcweir namespace detail 44cdf0e10cSrcweir { 45cdf0e10cSrcweir /// convert int32 to 32:32 fixed point toFractional(sal_Int32 v)46cdf0e10cSrcweir inline sal_Int64 toFractional( sal_Int32 v ) { return (sal_Int64)v << 32; } 47cdf0e10cSrcweir /// convert double to 32:32 fixed point toFractional(double v)48cdf0e10cSrcweir inline sal_Int64 toFractional( double v ) { return (sal_Int64)(v*SAL_MAX_UINT32 + (v < 0.0 ? -0.5 : 0.5 )); } 49cdf0e10cSrcweir /// convert 32:32 fixed point to int32 (truncate) toInteger(sal_Int64 v)50cdf0e10cSrcweir inline sal_Int32 toInteger( sal_Int64 v ) { return (sal_Int32)(v < 0 ? ~((~v) >> 32) : v >> 32); } 51cdf0e10cSrcweir /// convert 32:32 fixed point to int32 (properly rounded) toRoundedInteger(sal_Int64 v)52cdf0e10cSrcweir inline sal_Int32 toRoundedInteger( sal_Int64 v ) { return toInteger(v) + (sal_Int32)((v&0x80000000) >> 31); } 53cdf0e10cSrcweir 54cdf0e10cSrcweir /** internal vertex store - 55cdf0e10cSrcweir 56cdf0e10cSrcweir Different from B2DPoint, since we don't need floating 57cdf0e10cSrcweir point coords, but orientation of vertex and y counter 58cdf0e10cSrcweir */ 59cdf0e10cSrcweir struct Vertex 60cdf0e10cSrcweir { 61cdf0e10cSrcweir sal_Int32 mnYCounter; 62cdf0e10cSrcweir sal_Int64 mnX; 63cdf0e10cSrcweir sal_Int64 mnXDelta; 64cdf0e10cSrcweir 65cdf0e10cSrcweir bool mbDownwards; // needed for nonzero winding rule 66cdf0e10cSrcweir // fills 67cdf0e10cSrcweir Vertexbasebmp::detail::Vertex68cdf0e10cSrcweir Vertex() : 69cdf0e10cSrcweir mnYCounter(0), 70cdf0e10cSrcweir mnX(0), 71cdf0e10cSrcweir mnXDelta(0), 72cdf0e10cSrcweir mbDownwards(true) 73cdf0e10cSrcweir {} Vertexbasebmp::detail::Vertex74cdf0e10cSrcweir Vertex( basegfx::B2DPoint const& rPt1, 75cdf0e10cSrcweir basegfx::B2DPoint const& rPt2, 76cdf0e10cSrcweir bool bDownwards ) : 77cdf0e10cSrcweir mnYCounter( basegfx::fround(rPt2.getY()) - 78cdf0e10cSrcweir basegfx::fround(rPt1.getY()) ), 79cdf0e10cSrcweir mnX( toFractional( basegfx::fround(rPt1.getX()) )), 80cdf0e10cSrcweir mnXDelta( toFractional( 81cdf0e10cSrcweir ((rPt2.getX() - rPt1.getX()) / 82cdf0e10cSrcweir (double)mnYCounter) )), 83cdf0e10cSrcweir mbDownwards(bDownwards) 84cdf0e10cSrcweir {} 85cdf0e10cSrcweir }; 86cdf0e10cSrcweir 87cdf0e10cSrcweir typedef std::vector< std::vector<Vertex> > VectorOfVectorOfVertices; 88cdf0e10cSrcweir typedef std::vector< Vertex* > VectorOfVertexPtr; 89cdf0e10cSrcweir 90cdf0e10cSrcweir /// non-templated setup of GET 91cdf0e10cSrcweir sal_uInt32 setupGlobalEdgeTable( VectorOfVectorOfVertices& rGET, 92cdf0e10cSrcweir basegfx::B2DPolyPolygon const& rPoly, 93cdf0e10cSrcweir sal_Int32 nMinY ); 94cdf0e10cSrcweir /// sort rAETSrc, copy not-yet-ended edges over to rAETDest 95cdf0e10cSrcweir void sortAET( VectorOfVertexPtr& rAETSrc, 96cdf0e10cSrcweir VectorOfVertexPtr& rAETDest ); 97cdf0e10cSrcweir 98cdf0e10cSrcweir /// For the STL algorithms 99cdf0e10cSrcweir struct RasterConvertVertexComparator 100cdf0e10cSrcweir { RasterConvertVertexComparatorbasebmp::detail::RasterConvertVertexComparator101cdf0e10cSrcweir RasterConvertVertexComparator() {} 102cdf0e10cSrcweir operator ()basebmp::detail::RasterConvertVertexComparator103cdf0e10cSrcweir bool operator()( const Vertex& rLHS, 104cdf0e10cSrcweir const Vertex& rRHS ) const 105cdf0e10cSrcweir { 106cdf0e10cSrcweir return rLHS.mnX < rRHS.mnX; 107cdf0e10cSrcweir } 108cdf0e10cSrcweir operator ()basebmp::detail::RasterConvertVertexComparator109cdf0e10cSrcweir bool operator()( const Vertex* pLHS, 110cdf0e10cSrcweir const Vertex* pRHS ) const 111cdf0e10cSrcweir { 112cdf0e10cSrcweir return pLHS->mnX < pRHS->mnX; 113cdf0e10cSrcweir } 114cdf0e10cSrcweir }; 115cdf0e10cSrcweir 116cdf0e10cSrcweir } // namespace detail 117cdf0e10cSrcweir 118cdf0e10cSrcweir 119cdf0e10cSrcweir /** Raster-convert a poly-polygon. 120cdf0e10cSrcweir 121cdf0e10cSrcweir This algorithm does not perform antialiasing, and thus 122cdf0e10cSrcweir internally works with integer vertex coordinates. 123cdf0e10cSrcweir 124cdf0e10cSrcweir @param begin 125cdf0e10cSrcweir Left, top edge of the destination bitmap. This position is 126cdf0e10cSrcweir considered (0,0) relative to all polygon vertices 127cdf0e10cSrcweir 128cdf0e10cSrcweir @param ad 129cdf0e10cSrcweir Accessor to set pixel values 130cdf0e10cSrcweir 131cdf0e10cSrcweir @param fillColor 132cdf0e10cSrcweir Color to use for filling 133cdf0e10cSrcweir 134cdf0e10cSrcweir @param rClipRect 135cdf0e10cSrcweir Clipping rectangle, relative to the begin iterator. No pixel outside 136cdf0e10cSrcweir this clip rect will be modified. 137cdf0e10cSrcweir 138cdf0e10cSrcweir @param rPoly 139cdf0e10cSrcweir Polygon to fill 140cdf0e10cSrcweir */ 141cdf0e10cSrcweir template< class DestIterator, class DestAccessor, typename T > renderClippedPolyPolygon(DestIterator begin,DestAccessor ad,T fillColor,const basegfx::B2IRange & rClipRect,basegfx::B2DPolyPolygon const & rPoly,basegfx::FillRule eFillRule)142cdf0e10cSrcweir void renderClippedPolyPolygon( DestIterator begin, 143cdf0e10cSrcweir DestAccessor ad, 144cdf0e10cSrcweir T fillColor, 145cdf0e10cSrcweir const basegfx::B2IRange& rClipRect, 146cdf0e10cSrcweir basegfx::B2DPolyPolygon const& rPoly, 147cdf0e10cSrcweir basegfx::FillRule eFillRule ) 148cdf0e10cSrcweir { 149cdf0e10cSrcweir const sal_Int32 nClipX1( std::max((sal_Int32)0,rClipRect.getMinX()) ); 150cdf0e10cSrcweir const sal_Int32 nClipX2( rClipRect.getMaxX() ); 151cdf0e10cSrcweir const sal_Int32 nClipY1( std::max((sal_Int32)0,rClipRect.getMinY()) ); 152cdf0e10cSrcweir const sal_Int32 nClipY2( rClipRect.getMaxY() ); 153cdf0e10cSrcweir const sal_Int64 nClipX1_frac( detail::toFractional(nClipX1) ); 154cdf0e10cSrcweir const sal_Int64 nClipX2_frac( detail::toFractional(nClipX2) ); 155cdf0e10cSrcweir 156cdf0e10cSrcweir basegfx::B2DRange const aPolyBounds( basegfx::tools::getRange(rPoly) ); 157cdf0e10cSrcweir 158cdf0e10cSrcweir const sal_Int32 nMinY( basegfx::fround(aPolyBounds.getMinY()) ); 159cdf0e10cSrcweir const sal_Int32 nMaxY( 160cdf0e10cSrcweir std::min( 161cdf0e10cSrcweir nClipY2-1, 162cdf0e10cSrcweir basegfx::fround(aPolyBounds.getMaxY()))); 163cdf0e10cSrcweir 164cdf0e10cSrcweir if( nMinY > nMaxY ) 165cdf0e10cSrcweir return; // really, nothing to do then. 166cdf0e10cSrcweir 167cdf0e10cSrcweir detail::VectorOfVectorOfVertices aGET; // the Global Edge Table 168cdf0e10cSrcweir aGET.resize( nMaxY - nMinY + 1 ); 169cdf0e10cSrcweir 170cdf0e10cSrcweir sal_uInt32 const nVertexCount( 171cdf0e10cSrcweir detail::setupGlobalEdgeTable( aGET, rPoly, nMinY ) ); 172cdf0e10cSrcweir 173cdf0e10cSrcweir 174cdf0e10cSrcweir // Perform actual scan conversion 175cdf0e10cSrcweir //---------------------------------------------------------------------- 176cdf0e10cSrcweir 177cdf0e10cSrcweir if( aGET.empty() ) 178cdf0e10cSrcweir return; 179cdf0e10cSrcweir 180cdf0e10cSrcweir detail::VectorOfVertexPtr aAET1; // the Active Edge Table 181cdf0e10cSrcweir detail::VectorOfVertexPtr aAET2; 182cdf0e10cSrcweir detail::VectorOfVertexPtr* pAET = &aAET1; 183cdf0e10cSrcweir detail::VectorOfVertexPtr* pAETOther = &aAET2; 184cdf0e10cSrcweir aAET1.reserve( nVertexCount ); 185cdf0e10cSrcweir aAET2.reserve( nVertexCount ); 186cdf0e10cSrcweir 187cdf0e10cSrcweir // current scanline - initially, points to first scanline 188cdf0e10cSrcweir // within the clip rect, or to the polygon's first scanline 189cdf0e10cSrcweir // (whichever is greater) 190cdf0e10cSrcweir DestIterator aScanline( begin + 191cdf0e10cSrcweir vigra::Diff2D( 192cdf0e10cSrcweir 0, 193cdf0e10cSrcweir std::max(nMinY, 194cdf0e10cSrcweir nClipY1)) ); 195cdf0e10cSrcweir detail::RasterConvertVertexComparator aComp; 196cdf0e10cSrcweir 197cdf0e10cSrcweir 198cdf0e10cSrcweir // now process each of the nMaxY - nMinY + 1 scanlines 199cdf0e10cSrcweir // ------------------------------------------------------------ 200cdf0e10cSrcweir 201cdf0e10cSrcweir for( sal_Int32 y=nMinY; y <= nMaxY; ++y ) 202cdf0e10cSrcweir { 203cdf0e10cSrcweir if( !aGET[y-nMinY].empty() ) 204cdf0e10cSrcweir { 205cdf0e10cSrcweir // merge AET with current scanline's new vertices (both 206cdf0e10cSrcweir // are already correctly sorted) 207cdf0e10cSrcweir detail::VectorOfVectorOfVertices::value_type::iterator vertex=aGET[y-nMinY].begin(); 208cdf0e10cSrcweir detail::VectorOfVectorOfVertices::value_type::iterator const end=aGET[y-nMinY].end(); 209cdf0e10cSrcweir while( vertex != end ) 210cdf0e10cSrcweir { 211cdf0e10cSrcweir // find insertion pos by binary search, and put ptr 212cdf0e10cSrcweir // into active edge vector 213cdf0e10cSrcweir pAET->insert( std::lower_bound( pAET->begin(), 214cdf0e10cSrcweir pAET->end(), 215cdf0e10cSrcweir &(*vertex), 216cdf0e10cSrcweir aComp ), 217cdf0e10cSrcweir &(*vertex) ); 218cdf0e10cSrcweir 219cdf0e10cSrcweir ++vertex; 220cdf0e10cSrcweir } 221cdf0e10cSrcweir } 222cdf0e10cSrcweir 223cdf0e10cSrcweir // with less than two active edges, no fill visible 224cdf0e10cSrcweir if( pAET->size() >= 2 ) 225cdf0e10cSrcweir { 226cdf0e10cSrcweir typename vigra::IteratorTraits<DestIterator>::row_iterator 227cdf0e10cSrcweir rowIter( aScanline.rowIterator() ); 228cdf0e10cSrcweir 229cdf0e10cSrcweir // process each span in current scanline, with 230cdf0e10cSrcweir // even-odd fill rule 231cdf0e10cSrcweir detail::VectorOfVertexPtr::iterator currVertex( pAET->begin() ); 232cdf0e10cSrcweir detail::VectorOfVertexPtr::iterator const lastVertex( pAET->end()-1 ); 233cdf0e10cSrcweir sal_uInt32 nCrossedEdges(0); 234cdf0e10cSrcweir sal_Int32 nWindingNumber(0); 235cdf0e10cSrcweir while( currVertex != lastVertex ) 236cdf0e10cSrcweir { 237cdf0e10cSrcweir // TODO(P1): might be worth a try to extend the 238cdf0e10cSrcweir // size()==2 case also to the actual filling 239cdf0e10cSrcweir // here. YMMV. 240cdf0e10cSrcweir detail::Vertex& rV1( **currVertex ); 241cdf0e10cSrcweir detail::Vertex const& rV2( **++currVertex ); 242cdf0e10cSrcweir 243cdf0e10cSrcweir nWindingNumber += -1 + 2*rV1.mbDownwards; 244cdf0e10cSrcweir 245cdf0e10cSrcweir // calc fill status for both rules. might save a 246cdf0e10cSrcweir // few percent runtime to specialize here... 247cdf0e10cSrcweir const bool bEvenOddFill( 248cdf0e10cSrcweir eFillRule == basegfx::FillRule_EVEN_ODD && !(nCrossedEdges & 0x01) ); 249cdf0e10cSrcweir const bool bNonZeroWindingFill( 250cdf0e10cSrcweir eFillRule == basegfx::FillRule_NONZERO_WINDING_NUMBER && nWindingNumber != 0 ); 251cdf0e10cSrcweir 252cdf0e10cSrcweir // is span visible? 253cdf0e10cSrcweir if( (bEvenOddFill || bNonZeroWindingFill) && 254cdf0e10cSrcweir y >= nClipY1 && 255cdf0e10cSrcweir rV1.mnX < nClipX2_frac && 256cdf0e10cSrcweir rV2.mnX > nClipX1_frac ) 257cdf0e10cSrcweir { 258cdf0e10cSrcweir // clip span to horizontal bounds 259cdf0e10cSrcweir sal_Int32 const nStartX( 260cdf0e10cSrcweir std::max( nClipX1, 261cdf0e10cSrcweir std::min( nClipX2-1, 262cdf0e10cSrcweir detail::toRoundedInteger(rV1.mnX) ))); 263cdf0e10cSrcweir sal_Int32 const nEndX( 264cdf0e10cSrcweir std::max( nClipX1, 265cdf0e10cSrcweir std::min( nClipX2, 266cdf0e10cSrcweir detail::toRoundedInteger(rV2.mnX) ))); 267cdf0e10cSrcweir 268cdf0e10cSrcweir typename vigra::IteratorTraits<DestIterator>::row_iterator 269cdf0e10cSrcweir currPix( rowIter + nStartX); 270cdf0e10cSrcweir typename vigra::IteratorTraits<DestIterator>::row_iterator 271cdf0e10cSrcweir rowEnd( rowIter + nEndX ); 272cdf0e10cSrcweir 273cdf0e10cSrcweir // TODO(P2): Provide specialized span fill methods on the 274cdf0e10cSrcweir // iterator/accessor 275cdf0e10cSrcweir while( currPix != rowEnd ) 276cdf0e10cSrcweir ad.set(fillColor, currPix++); 277cdf0e10cSrcweir } 278cdf0e10cSrcweir 279cdf0e10cSrcweir // step vertices 280cdf0e10cSrcweir rV1.mnX += rV1.mnXDelta; 281cdf0e10cSrcweir --rV1.mnYCounter; 282cdf0e10cSrcweir 283cdf0e10cSrcweir ++nCrossedEdges; 284cdf0e10cSrcweir } 285cdf0e10cSrcweir 286cdf0e10cSrcweir // step vertex also for the last one 287cdf0e10cSrcweir detail::Vertex& rLastV( **currVertex ); 288cdf0e10cSrcweir rLastV.mnX += rLastV.mnXDelta; 289cdf0e10cSrcweir --rLastV.mnYCounter; 290cdf0e10cSrcweir 291cdf0e10cSrcweir 292cdf0e10cSrcweir // prune AET from ended edges, and keep it sorted 293cdf0e10cSrcweir // --------------------------------------------------------- 294cdf0e10cSrcweir 295cdf0e10cSrcweir pAETOther->clear(); 296cdf0e10cSrcweir if( pAET->size() == 2 ) 297cdf0e10cSrcweir { 298cdf0e10cSrcweir // the case of exactly two active edges is both 299cdf0e10cSrcweir // sufficiently common (all 'simple' polygons have 300cdf0e10cSrcweir // it), and further more would complicate the 301cdf0e10cSrcweir // generic case below (which works with a sliding 302cdf0e10cSrcweir // triple of vertices). 303cdf0e10cSrcweir if( !aComp(*(*pAET)[0], *(*pAET)[1]) ) 304cdf0e10cSrcweir std::swap(*(*pAET)[0], *(*pAET)[1]); 305cdf0e10cSrcweir 306cdf0e10cSrcweir if( (*pAET)[0]->mnYCounter > 0 ) 307cdf0e10cSrcweir pAETOther->push_back( (*pAET)[0] ); 308cdf0e10cSrcweir if( (*pAET)[1]->mnYCounter > 0 ) 309cdf0e10cSrcweir pAETOther->push_back( (*pAET)[1] ); 310cdf0e10cSrcweir } 311cdf0e10cSrcweir else 312cdf0e10cSrcweir { 313cdf0e10cSrcweir bool bFallbackTaken(false); 314cdf0e10cSrcweir currVertex = pAET->begin(); 315cdf0e10cSrcweir detail::VectorOfVertexPtr::iterator prevVertex( currVertex ); 316cdf0e10cSrcweir while( currVertex != lastVertex ) 317cdf0e10cSrcweir { 318cdf0e10cSrcweir // try to get away with one linear swoop and 319cdf0e10cSrcweir // simple neighbor swapping. this is an 320cdf0e10cSrcweir // overwhelmingly common case - polygons with 321cdf0e10cSrcweir // excessively crisscrossing edges (which on 322cdf0e10cSrcweir // top of that cross more than one other edge 323cdf0e10cSrcweir // per scanline) are seldom. And even if we 324cdf0e10cSrcweir // get such a beast here, this extra loop has 325cdf0e10cSrcweir // still only linear cost 326cdf0e10cSrcweir if( aComp(**(currVertex+1),**currVertex) ) 327cdf0e10cSrcweir { 328cdf0e10cSrcweir std::swap(*currVertex, *(currVertex+1)); 329cdf0e10cSrcweir 330cdf0e10cSrcweir if( aComp(**currVertex,**prevVertex) ) 331cdf0e10cSrcweir { 332cdf0e10cSrcweir // one swap was not sufficient - 333cdf0e10cSrcweir // fallback to generic sort algo, then 334cdf0e10cSrcweir detail::sortAET(*pAET, *pAETOther); 335cdf0e10cSrcweir bFallbackTaken = true; 336cdf0e10cSrcweir break; 337cdf0e10cSrcweir } 338cdf0e10cSrcweir } 339cdf0e10cSrcweir 340cdf0e10cSrcweir if( (*currVertex)->mnYCounter > 0 ) 341cdf0e10cSrcweir pAETOther->push_back( *currVertex ); 342cdf0e10cSrcweir 343cdf0e10cSrcweir prevVertex = currVertex++; 344cdf0e10cSrcweir } 345cdf0e10cSrcweir 346cdf0e10cSrcweir // don't forget to add last vertex (loop above 347cdf0e10cSrcweir // only deals with n-1 vertices) 348cdf0e10cSrcweir if( !bFallbackTaken && (*currVertex)->mnYCounter > 0 ) 349cdf0e10cSrcweir pAETOther->push_back( *currVertex ); 350cdf0e10cSrcweir } 351cdf0e10cSrcweir 352cdf0e10cSrcweir std::swap( pAET, pAETOther ); 353cdf0e10cSrcweir } 354cdf0e10cSrcweir 355cdf0e10cSrcweir if( y >= nClipY1 ) 356cdf0e10cSrcweir ++aScanline.y; 357cdf0e10cSrcweir } 358cdf0e10cSrcweir } 359cdf0e10cSrcweir 360cdf0e10cSrcweir } // namespace basebmp 361cdf0e10cSrcweir 362cdf0e10cSrcweir #endif /* INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX */ 363