From b9337e22ce1dbf2eba0e8c8db294ae99f4111f91 Mon Sep 17 00:00:00 2001 From: Bjoern Michaelsen Date: Thu, 18 Apr 2013 18:26:28 +0200 Subject: execute move of global headers see https://gerrit.libreoffice.org/#/c/3367/ and Change-Id: I00c96fa77d04b33a6f8c8cd3490dfcd9bdc9e84a for details Change-Id: I199a75bc4042af20817265d5ef85b1134a96ff5a --- include/basebmp/polypolygonrenderer.hxx | 360 ++++++++++++++++++++++++++++++++ 1 file changed, 360 insertions(+) create mode 100644 include/basebmp/polypolygonrenderer.hxx (limited to 'include/basebmp/polypolygonrenderer.hxx') diff --git a/include/basebmp/polypolygonrenderer.hxx b/include/basebmp/polypolygonrenderer.hxx new file mode 100644 index 000000000000..80f73ac01279 --- /dev/null +++ b/include/basebmp/polypolygonrenderer.hxx @@ -0,0 +1,360 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * This file incorporates work covered by the following license notice: + * + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed + * with this work for additional information regarding copyright + * ownership. The ASF licenses this file to you under the Apache + * License, Version 2.0 (the "License"); you may not use this file + * except in compliance with the License. You may obtain a copy of + * the License at http://www.apache.org/licenses/LICENSE-2.0 . + */ + +#ifndef INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX +#define INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX + +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +#include + + +namespace basebmp +{ + namespace detail + { + /// convert int32 to 32:32 fixed point + inline sal_Int64 toFractional( sal_Int32 v ) { return (sal_Int64)v << 32; } + /// convert double to 32:32 fixed point + inline sal_Int64 toFractional( double v ) { return (sal_Int64)(v*SAL_MAX_UINT32 + (v < 0.0 ? -0.5 : 0.5 )); } + /// convert 32:32 fixed point to int32 (truncate) + inline sal_Int32 toInteger( sal_Int64 v ) { return (sal_Int32)(v < 0 ? ~((~v) >> 32) : v >> 32); } + /// convert 32:32 fixed point to int32 (properly rounded) + inline sal_Int32 toRoundedInteger( sal_Int64 v ) { return toInteger(v) + (sal_Int32)((v&0x80000000) >> 31); } + + /** internal vertex store - + + Different from B2DPoint, since we don't need floating + point coords, but orientation of vertex and y counter + */ + struct Vertex + { + sal_Int32 mnYCounter; + sal_Int64 mnX; + sal_Int64 mnXDelta; + + bool mbDownwards; // needed for nonzero winding rule + // fills + + Vertex() : + mnYCounter(0), + mnX(0), + mnXDelta(0), + mbDownwards(true) + {} + Vertex( basegfx::B2DPoint const& rPt1, + basegfx::B2DPoint const& rPt2, + bool bDownwards ) : + mnYCounter( basegfx::fround(rPt2.getY()) - + basegfx::fround(rPt1.getY()) ), + mnX( toFractional( basegfx::fround(rPt1.getX()) )), + mnXDelta( toFractional( + ((rPt2.getX() - rPt1.getX()) / + (double)mnYCounter) )), + mbDownwards(bDownwards) + {} + }; + + typedef std::vector< std::vector > VectorOfVectorOfVertices; + typedef std::vector< Vertex* > VectorOfVertexPtr; + + /// non-templated setup of GET + sal_uInt32 setupGlobalEdgeTable( VectorOfVectorOfVertices& rGET, + basegfx::B2DPolyPolygon const& rPoly, + sal_Int32 nMinY ); + /// sort rAETSrc, copy not-yet-ended edges over to rAETDest + void sortAET( VectorOfVertexPtr& rAETSrc, + VectorOfVertexPtr& rAETDest ); + + /// For the STL algorithms + struct RasterConvertVertexComparator + { + RasterConvertVertexComparator() {} + + bool operator()( const Vertex& rLHS, + const Vertex& rRHS ) const + { + return rLHS.mnX < rRHS.mnX; + } + + bool operator()( const Vertex* pLHS, + const Vertex* pRHS ) const + { + return pLHS->mnX < pRHS->mnX; + } + }; + + } // namespace detail + + + /** Raster-convert a poly-polygon. + + This algorithm does not perform antialiasing, and thus + internally works with integer vertex coordinates. + + @param begin + Left, top edge of the destination bitmap. This position is + considered (0,0) relative to all polygon vertices + + @param ad + Accessor to set pixel values + + @param fillColor + Color to use for filling + + @param rClipRect + Clipping rectangle, relative to the begin iterator. No pixel outside + this clip rect will be modified. + + @param rPoly + Polygon to fill + */ + template< class DestIterator, class DestAccessor, typename T > + void renderClippedPolyPolygon( DestIterator begin, + DestAccessor ad, + T fillColor, + const basegfx::B2IBox& rClipRect, + basegfx::B2DPolyPolygon const& rPoly, + basegfx::FillRule eFillRule ) + { + const sal_Int32 nClipX1( std::max((sal_Int32)0,rClipRect.getMinX()) ); + const sal_Int32 nClipX2( rClipRect.getMaxX() ); + const sal_Int32 nClipY1( std::max((sal_Int32)0,rClipRect.getMinY()) ); + const sal_Int32 nClipY2( rClipRect.getMaxY() ); + const sal_Int64 nClipX1_frac( detail::toFractional(nClipX1) ); + const sal_Int64 nClipX2_frac( detail::toFractional(nClipX2) ); + + basegfx::B2DRange const aPolyBounds( basegfx::tools::getRange(rPoly) ); + + const sal_Int32 nMinY( basegfx::fround(aPolyBounds.getMinY()) ); + const sal_Int32 nMaxY( + std::min( + nClipY2-1, + basegfx::fround(aPolyBounds.getMaxY()))); + + if( nMinY > nMaxY ) + return; // really, nothing to do then. + + detail::VectorOfVectorOfVertices aGET; // the Global Edge Table + aGET.resize( nMaxY - nMinY + 1 ); + + sal_uInt32 const nVertexCount( + detail::setupGlobalEdgeTable( aGET, rPoly, nMinY ) ); + + + // Perform actual scan conversion + //---------------------------------------------------------------------- + + if( aGET.empty() ) + return; + + detail::VectorOfVertexPtr aAET1; // the Active Edge Table + detail::VectorOfVertexPtr aAET2; + detail::VectorOfVertexPtr* pAET = &aAET1; + detail::VectorOfVertexPtr* pAETOther = &aAET2; + aAET1.reserve( nVertexCount ); + aAET2.reserve( nVertexCount ); + + // current scanline - initially, points to first scanline + // within the clip rect, or to the polygon's first scanline + // (whichever is greater) + DestIterator aScanline( begin + + vigra::Diff2D( + 0, + std::max(nMinY, + nClipY1)) ); + detail::RasterConvertVertexComparator aComp; + + + // now process each of the nMaxY - nMinY + 1 scanlines + // ------------------------------------------------------------ + + for( sal_Int32 y=nMinY; y <= nMaxY; ++y ) + { + if( !aGET[y-nMinY].empty() ) + { + // merge AET with current scanline's new vertices (both + // are already correctly sorted) + detail::VectorOfVectorOfVertices::value_type::iterator vertex=aGET[y-nMinY].begin(); + detail::VectorOfVectorOfVertices::value_type::iterator const end=aGET[y-nMinY].end(); + while( vertex != end ) + { + // find insertion pos by binary search, and put ptr + // into active edge vector + pAET->insert( std::lower_bound( pAET->begin(), + pAET->end(), + &(*vertex), + aComp ), + &(*vertex) ); + + ++vertex; + } + } + + // with less than two active edges, no fill visible + if( pAET->size() >= 2 ) + { + typename vigra::IteratorTraits::row_iterator + rowIter( aScanline.rowIterator() ); + + // process each span in current scanline, with + // even-odd fill rule + detail::VectorOfVertexPtr::iterator currVertex( pAET->begin() ); + detail::VectorOfVertexPtr::iterator const lastVertex( pAET->end()-1 ); + sal_uInt32 nCrossedEdges(0); + sal_Int32 nWindingNumber(0); + while( currVertex != lastVertex ) + { + // TODO(P1): might be worth a try to extend the + // size()==2 case also to the actual filling + // here. YMMV. + detail::Vertex& rV1( **currVertex ); + detail::Vertex const& rV2( **++currVertex ); + + nWindingNumber += -1 + 2*rV1.mbDownwards; + + // calc fill status for both rules. might save a + // few percent runtime to specialize here... + const bool bEvenOddFill( + eFillRule == basegfx::FillRule_EVEN_ODD && !(nCrossedEdges & 0x01) ); + const bool bNonZeroWindingFill( + eFillRule == basegfx::FillRule_NONZERO_WINDING_NUMBER && nWindingNumber != 0 ); + + // is span visible? + if( (bEvenOddFill || bNonZeroWindingFill) && + y >= nClipY1 && + rV1.mnX < nClipX2_frac && + rV2.mnX > nClipX1_frac ) + { + // clip span to horizontal bounds + sal_Int32 const nStartX( + std::max( nClipX1, + std::min( nClipX2-1, + detail::toRoundedInteger(rV1.mnX) ))); + sal_Int32 const nEndX( + std::max( nClipX1, + std::min( nClipX2, + detail::toRoundedInteger(rV2.mnX) ))); + + typename vigra::IteratorTraits::row_iterator + currPix( rowIter + nStartX); + typename vigra::IteratorTraits::row_iterator + rowEnd( rowIter + nEndX ); + + // TODO(P2): Provide specialized span fill methods on the + // iterator/accessor + while( currPix != rowEnd ) + ad.set(fillColor, currPix++); + } + + // step vertices + rV1.mnX += rV1.mnXDelta; + --rV1.mnYCounter; + + ++nCrossedEdges; + } + + // step vertex also for the last one + detail::Vertex& rLastV( **currVertex ); + rLastV.mnX += rLastV.mnXDelta; + --rLastV.mnYCounter; + + + // prune AET from ended edges, and keep it sorted + // --------------------------------------------------------- + + pAETOther->clear(); + if( pAET->size() == 2 ) + { + // the case of exactly two active edges is both + // sufficiently common (all 'simple' polygons have + // it), and further more would complicate the + // generic case below (which works with a sliding + // triple of vertices). + if( !aComp(*(*pAET)[0], *(*pAET)[1]) ) + std::swap(*(*pAET)[0], *(*pAET)[1]); + + if( (*pAET)[0]->mnYCounter > 0 ) + pAETOther->push_back( (*pAET)[0] ); + if( (*pAET)[1]->mnYCounter > 0 ) + pAETOther->push_back( (*pAET)[1] ); + } + else + { + bool bFallbackTaken(false); + currVertex = pAET->begin(); + detail::VectorOfVertexPtr::iterator prevVertex( currVertex ); + while( currVertex != lastVertex ) + { + // try to get away with one linear swoop and + // simple neighbor swapping. this is an + // overwhelmingly common case - polygons with + // excessively crisscrossing edges (which on + // top of that cross more than one other edge + // per scanline) are seldom. And even if we + // get such a beast here, this extra loop has + // still only linear cost + if( aComp(**(currVertex+1),**currVertex) ) + { + std::swap(*currVertex, *(currVertex+1)); + + if( aComp(**currVertex,**prevVertex) ) + { + // one swap was not sufficient - + // fallback to generic sort algo, then + detail::sortAET(*pAET, *pAETOther); + bFallbackTaken = true; + break; + } + } + + if( (*currVertex)->mnYCounter > 0 ) + pAETOther->push_back( *currVertex ); + + prevVertex = currVertex++; + } + + // don't forget to add last vertex (loop above + // only deals with n-1 vertices) + if( !bFallbackTaken && (*currVertex)->mnYCounter > 0 ) + pAETOther->push_back( *currVertex ); + } + + std::swap( pAET, pAETOther ); + } + + if( y >= nClipY1 ) + ++aScanline.y; + } + } + +} // namespace basebmp + +#endif /* INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX */ + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ -- cgit