LCOV - code coverage report
Current view: top level - include/basebmp - polypolygonrenderer.hxx (source / functions) Hit Total Coverage
Test: commit 10e77ab3ff6f4314137acd6e2702a6e5c1ce1fae Lines: 103 104 99.0 %
Date: 2014-11-03 Functions: 19 40 47.5 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.10