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