include/basebmp/polypolygonrenderer.hxx

   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         inline sal_Int64 toFractional( sal_Int32 v ) { return sal_Int64(sal_uInt64(v) << 32); }
  43         /// convert double to 32:32 fixed point
  44         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         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         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             Vertex( basegfx::B2DPoint const& rPt1,
  71                     basegfx::B2DPoint const& rPt2,
  72                     bool                     bDownwards ) :
  73                 mnYCounter( basegfx::fround(rPt2.getY()) -
  74                             basegfx::fround(rPt1.getY()) ),
  75                 mnX( toFractional( basegfx::fround(rPt1.getX()) )),
  76                 mnXDelta( toFractional(
  77                               ((rPt2.getX() - rPt1.getX()) /
  78                                (double)mnYCounter) )),
  79                 mbDownwards(bDownwards)
  80             {}
  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             RasterConvertVertexComparator() {}
  98
  99             bool operator()( const Vertex& rLHS,
 100                              const Vertex& rRHS ) const
 101             {
 102                 return rLHS.mnX < rRHS.mnX;
 103             }
 104
 105             bool operator()( const Vertex* pLHS,
 106                              const Vertex* pRHS ) const
 107             {
 108                 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     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         const sal_Int32 nClipX1( std::max((sal_Int32)0,rClipRect.getMinX()) );
 146         const sal_Int32 nClipX2( rClipRect.getMaxX() );
 147         const sal_Int32 nClipY1( std::max((sal_Int32)0,rClipRect.getMinY()) );
 148         const sal_Int32 nClipY2( rClipRect.getMaxY() );
 149         const sal_Int64 nClipX1_frac( detail::toFractional(nClipX1) );
 150         const sal_Int64 nClipX2_frac( detail::toFractional(nClipX2) );
 151
 152         basegfx::B2DRange const aPolyBounds( basegfx::tools::getRange(rPoly) );
 153
 154         const sal_Int32 nMinY( basegfx::fround(aPolyBounds.getMinY()) );
 155         const sal_Int32 nMaxY(
 156             std::min(
 157                 nClipY2-1,
 158                 basegfx::fround(aPolyBounds.getMaxY())));
 159
 160         if( nMinY > nMaxY )
 161             return; // really, nothing to do then.
 162
 163         detail::VectorOfVectorOfVertices aGET; // the Global Edge Table
 164         aGET.resize( nMaxY - nMinY + 1 );
 165
 166         sal_uInt32 const nVertexCount(
 167             detail::setupGlobalEdgeTable( aGET, rPoly, nMinY ) );
 168
 169
 170         // Perform actual scan conversion
 171         //----------------------------------------------------------------------
 172
 173         if( aGET.empty() )
 174             return;
 175
 176         detail::VectorOfVertexPtr      aAET1; // the Active Edge Table
 177         detail::VectorOfVertexPtr      aAET2;
 178         detail::VectorOfVertexPtr*     pAET = &aAET1;
 179         detail::VectorOfVertexPtr*     pAETOther = &aAET2;
 180         aAET1.reserve( nVertexCount );
 181         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         DestIterator aScanline( begin +
 187                                 vigra::Diff2D(
 188                                     0,
 189                                     std::max(nMinY,
 190                                              nClipY1)) );
 191         detail::RasterConvertVertexComparator aComp;
 192
 193
 194         // now process each of the nMaxY - nMinY + 1 scanlines
 195         // ------------------------------------------------------------
 196
 197         for( sal_Int32 y=nMinY; y <= nMaxY; ++y )
 198         {
 199             if( !aGET[y-nMinY].empty() )
 200             {
 201                 // merge AET with current scanline's new vertices (both
 202                 // are already correctly sorted)
 203                 detail::VectorOfVectorOfVertices::value_type::iterator       vertex=aGET[y-nMinY].begin();
 204                 detail::VectorOfVectorOfVertices::value_type::iterator const end=aGET[y-nMinY].end();
 205                 while( vertex != end )
 206                 {
 207                     // find insertion pos by binary search, and put ptr
 208                     // into active edge vector
 209                     pAET->insert( std::lower_bound( pAET->begin(),
 210                                                     pAET->end(),
 211                                                     &(*vertex),
 212                                                     aComp ),
 213                                   &(*vertex) );
 214
 215                     ++vertex;
 216                 }
 217             }
 218
 219             // with less than two active edges, no fill visible
 220             if( pAET->size() >= 2 )
 221             {
 222                 typename vigra::IteratorTraits<DestIterator>::row_iterator
 223                     rowIter( aScanline.rowIterator() );
 224
 225                 // process each span in current scanline, with
 226                 // even-odd fill rule
 227                 detail::VectorOfVertexPtr::iterator       currVertex( pAET->begin() );
 228                 detail::VectorOfVertexPtr::iterator const lastVertex( pAET->end()-1 );
 229                 sal_uInt32                                nCrossedEdges(0);
 230                 sal_Int32                                 nWindingNumber(0);
 231                 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                     detail::Vertex&       rV1( **currVertex );
 237                     detail::Vertex const& rV2( **++currVertex );
 238
 239                     nWindingNumber += -1 + 2*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                         eFillRule == basegfx::FillRule_EVEN_ODD && !(nCrossedEdges & 0x01) );
 245                     const bool bNonZeroWindingFill(
 246                         eFillRule == basegfx::FillRule_NONZERO_WINDING_NUMBER && nWindingNumber != 0 );
 247
 248                     // is span visible?
 249                     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                                                 detail::toRoundedInteger(rV1.mnX) )));
 259                         sal_Int32 const nEndX(
 260                             std::max( nClipX1,
 261                                       std::min( nClipX2,
 262                                                 detail::toRoundedInteger(rV2.mnX) )));
 263
 264                         typename vigra::IteratorTraits<DestIterator>::row_iterator
 265                             currPix( rowIter + nStartX);
 266                         typename vigra::IteratorTraits<DestIterator>::row_iterator
 267                             rowEnd( rowIter + nEndX );
 268
 269                         // TODO(P2): Provide specialized span fill methods on the
 270                         // iterator/accessor
 271                         while( currPix != rowEnd )
 272                             ad.set(fillColor, currPix++);
 273                     }
 274
 275                     // step vertices
 276                     rV1.mnX += rV1.mnXDelta;
 277                     --rV1.mnYCounter;
 278
 279                     ++nCrossedEdges;
 280                 }
 281
 282                 // step vertex also for the last one
 283                 detail::Vertex& rLastV( **currVertex );
 284                 rLastV.mnX += rLastV.mnXDelta;
 285                 --rLastV.mnYCounter;
 286
 287
 288                 // prune AET from ended edges, and keep it sorted
 289                 // ---------------------------------------------------------
 290
 291                 pAETOther->clear();
 292                 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                     if( !aComp(*(*pAET)[0], *(*pAET)[1]) )
 300                         std::swap(*(*pAET)[0], *(*pAET)[1]);
 301
 302                     if( (*pAET)[0]->mnYCounter > 0 )
 303                         pAETOther->push_back( (*pAET)[0] );
 304                     if( (*pAET)[1]->mnYCounter > 0 )
 305                         pAETOther->push_back( (*pAET)[1] );
 306                 }
 307                 else
 308                 {
 309                     bool bFallbackTaken(false);
 310                     currVertex = pAET->begin();
 311                     detail::VectorOfVertexPtr::iterator prevVertex( currVertex );
 312                     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                         if( aComp(**(currVertex+1),**currVertex) )
 323                         {
 324                             std::swap(*currVertex, *(currVertex+1));
 325
 326                             if( aComp(**currVertex,**prevVertex) )
 327                             {
 328                                 // one swap was not sufficient -
 329                                 // fallback to generic sort algo, then
 330                                 detail::sortAET(*pAET, *pAETOther);
 331                                 bFallbackTaken = true;
 332                                 break;
 333                             }
 334                         }
 335
 336                         if( (*currVertex)->mnYCounter > 0 )
 337                             pAETOther->push_back( *currVertex );
 338
 339                         prevVertex = currVertex++;
 340                     }
 341
 342                     // don't forget to add last vertex (loop above
 343                     // only deals with n-1 vertices)
 344                     if( !bFallbackTaken && (*currVertex)->mnYCounter > 0 )
 345                         pAETOther->push_back( *currVertex );
 346                 }
 347
 348                 std::swap( pAET, pAETOther );
 349             }
 350
 351             if( y >= nClipY1 )
 352                 ++aScanline.y;
 353         }
 354     }
 355
 356 } // namespace basebmp
 357
 358 #endif /* INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX */
 359
 360 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */