diff options
Diffstat (limited to 'basegfx/source/polygon/b2dpolypolygonrasterconverter.cxx')
-rw-r--r-- | basegfx/source/polygon/b2dpolypolygonrasterconverter.cxx | 702 |
1 files changed, 702 insertions, 0 deletions
diff --git a/basegfx/source/polygon/b2dpolypolygonrasterconverter.cxx b/basegfx/source/polygon/b2dpolypolygonrasterconverter.cxx new file mode 100644 index 000000000000..b795c04e158e --- /dev/null +++ b/basegfx/source/polygon/b2dpolypolygonrasterconverter.cxx @@ -0,0 +1,702 @@ +/************************************************************************* + * + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * Copyright 2000, 2010 Oracle and/or its affiliates. + * + * OpenOffice.org - a multi-platform office productivity suite + * + * This file is part of OpenOffice.org. + * + * OpenOffice.org is free software: you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License version 3 + * only, as published by the Free Software Foundation. + * + * OpenOffice.org is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Lesser General Public License version 3 for more details + * (a copy is included in the LICENSE file that accompanied this code). + * + * You should have received a copy of the GNU Lesser General Public License + * version 3 along with OpenOffice.org. If not, see + * <http://www.openoffice.org/license.html> + * for a copy of the LGPLv3 License. + * + ************************************************************************/ + +// MARKER(update_precomp.py): autogen include statement, do not remove +#include "precompiled_basegfx.hxx" + +#include <basegfx/polygon/b2dpolypolygonrasterconverter.hxx> + +#include <basegfx/numeric/ftools.hxx> +#include <basegfx/polygon/b2dpolygon.hxx> +#include <basegfx/polygon/b2dpolygontools.hxx> +#include <basegfx/polygon/b2dpolypolygontools.hxx> + +#include <boost/mem_fn.hpp> + +#include <algorithm> + +namespace basegfx +{ + class radixSort { + + //! public interface + public: + + //! default constructor + radixSort( void ); + + //! destructor + ~radixSort( void ); + + bool sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ); + + inline sal_uInt32 *indices( void ) const { return m_indices1; } + + //! private attributes + private: + + // current size of index list + sal_uInt32 m_current_size; + + // last known size of index list + sal_uInt32 m_previous_size; + + // index lists + sal_uInt32 *m_indices1; + sal_uInt32 *m_indices2; + + sal_uInt32 m_counter[256*4]; + sal_uInt32 m_offset[256]; + + //! private methods + private: + + bool resize( sal_uInt32 nNumElements ); + inline void reset_indices( void ); + bool prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ); + }; + + inline radixSort::radixSort( void ) { + + m_indices1 = NULL; + m_indices2 = NULL; + m_current_size = 0; + m_previous_size = 0; + + reset_indices(); + } + + inline radixSort::~radixSort( void ) { + + delete [] m_indices2; + delete [] m_indices1; + } + + bool radixSort::resize( sal_uInt32 nNumElements ) { + + if(nNumElements==m_previous_size) + return true; + + if(nNumElements > m_current_size) { + + // release index lists + if(m_indices2) + delete [] m_indices2; + if(m_indices1) + delete [] m_indices1; + + // allocate new index lists + m_indices1 = new sal_uInt32[nNumElements]; + m_indices2 = new sal_uInt32[nNumElements]; + + // check for out of memory situation + if(!m_indices1 || !m_indices2) { + delete [] m_indices1; + delete [] m_indices2; + m_indices1 = NULL; + m_indices2 = NULL; + m_current_size = 0; + return false; + } + + m_current_size = nNumElements; + } + + m_previous_size = nNumElements; + + // initialize indices + reset_indices(); + + return true; + } + + inline void radixSort::reset_indices( void ) { + + for(sal_uInt32 i=0;i<m_current_size;i++) + m_indices1[i] = i; + } + + bool radixSort::prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) { + + // clear counters + sal_uInt32 *ptr = m_counter; + for(int i=0; i<64; ++i) + { + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + *ptr++ = 0; + } + + // prepare pointers to relevant memory addresses + sal_uInt8 *p = (sal_uInt8*)pInput; + sal_uInt8 *pe = p+(nNumElements*dwStride); + sal_uInt32 *h0= &m_counter[0]; + sal_uInt32 *h1= &m_counter[256]; + sal_uInt32 *h2= &m_counter[512]; + sal_uInt32 *h3= &m_counter[768]; + + sal_uInt32 *Indices = m_indices1; + float previous_value = *(float *)(((sal_uInt8 *)pInput)+(m_indices1[0]*dwStride)); + bool bSorted = true; + while(p!=pe) { + float value = *(float *)(((sal_uInt8 *)pInput)+((*Indices++)*dwStride)); + if(value<previous_value) { + bSorted = false; + break; + } + previous_value = value; + h0[*p++]++; + h1[*p++]++; + h2[*p++]++; + h3[*p++]++; + p += dwStride-4; + } + if(bSorted) + return true; + while(p!=pe) { + h0[*p++]++; + h1[*p++]++; + h2[*p++]++; + h3[*p++]++; + p += dwStride-4; + } + return false; + } + + bool radixSort::sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) { + + if(!(pInput)) + return false; + if(!(nNumElements)) + return false; + if(!(resize(nNumElements))) + return false; + + // prepare radix counters, return if already sorted + if(prepareCounters(pInput,nNumElements,dwStride)) + return true; + + // count number of negative values + sal_uInt32 num_negatives = 0; + sal_uInt32 *h3= &m_counter[768]; + for(sal_uInt32 i=128;i<256;i++) + num_negatives += h3[i]; + + // perform passes, one for each byte + for(sal_uInt32 j=0;j<4;j++) { + + // ignore this pass if all values have the same byte + bool bRun = true; + sal_uInt32 *current_counter = &m_counter[j<<8]; + sal_uInt8 unique_value = *(((sal_uInt8*)pInput)+j); + if(current_counter[unique_value]==nNumElements) + bRun=false; + + // does the incoming byte contain the sign bit? + sal_uInt32 i; + if(j!=3) { + if(bRun) { + m_offset[0] = 0; + for(i=1;i<256;i++) + m_offset[i] = m_offset[i-1] + current_counter[i-1]; + sal_uInt8 *InputBytes = (sal_uInt8 *)pInput; + sal_uInt32 *Indices = m_indices1; + sal_uInt32 *IndicesEnd = &m_indices1[nNumElements]; + InputBytes += j; + while(Indices!=IndicesEnd) { + sal_uInt32 id = *Indices++; + m_indices2[m_offset[InputBytes[id*dwStride]]++] = id; + } + sal_uInt32 *Tmp = m_indices1; + m_indices1 = m_indices2; + m_indices2 = Tmp; + } + } + else { + if(bRun) { + m_offset[0] = num_negatives; + for(i=1;i<128;i++) + m_offset[i] = m_offset[i-1] + current_counter[i-1]; + m_offset[255] = 0; + for(i=0;i<127;i++) + m_offset[254-i] = m_offset[255-i] + current_counter[255-i]; + for(i=128;i<256;i++) + m_offset[i] += current_counter[i]; + for(i=0;i<nNumElements;i++) { + sal_uInt32 Radix = (*(sal_uInt32 *)(((sal_uInt8 *)pInput)+(m_indices1[i]*dwStride)))>>24; + if(Radix<128) m_indices2[m_offset[Radix]++] = m_indices1[i]; + else m_indices2[--m_offset[Radix]] = m_indices1[i]; + } + sal_uInt32 *Tmp = m_indices1; + m_indices1 = m_indices2; + m_indices2 = Tmp; + } + else { + if(unique_value>=128) { + for(i=0;i<nNumElements;i++) + m_indices2[i] = m_indices1[nNumElements-i-1]; + sal_uInt32 *Tmp = m_indices1; + m_indices1 = m_indices2; + m_indices2 = Tmp; + } + } + } + } + + return true; + } + + //************************************************************ + // Internal vertex storage of B2DPolyPolygonRasterConverter + //************************************************************ + + inline B2DPolyPolygonRasterConverter::Vertex::Vertex() : + aP1(), + aP2(), + bDownwards( true ) + { + } + + inline B2DPolyPolygonRasterConverter::Vertex::Vertex( const B2DPoint& rP1, const B2DPoint& rP2, bool bDown ) : + aP1( rP1 ), + aP2( rP2 ), + bDownwards( bDown ) + { + } + + + //************************************************************ + // Helper class for holding horizontal line segments during raster + // conversion + //************************************************************ + + namespace + { + class ImplLineNode + { + public: + sal_Int32 mnYCounter; + float mfXPos; + float mfXDelta; + bool mbDownwards; + + public: + /**rP1 and rP2 must not have equal y values, when rounded + to integer! + */ + ImplLineNode(const B2DPoint& rP1, const B2DPoint& rP2, bool bDown) : + mnYCounter( fround(rP2.getY()) - fround(rP1.getY()) ), + mfXPos( (float)(rP1.getX()) ), + mfXDelta((float) ((rP2.getX() - rP1.getX()) / mnYCounter) ), + mbDownwards( bDown ) + { + } + + /// get current x position + const float& getXPos() const + { + return mfXPos; + } + + /// returns true, if line ends on this Y value + float nextLine() + { + if(mnYCounter>=0) + { + // go one step in Y + mfXPos += mfXDelta; + --mnYCounter; + return mfXDelta; + } + + return 0.0f; + } + + bool isEnded() + { + return mnYCounter<=0; + } + + bool isDownwards() + { + return mbDownwards; + } + }; + } + + typedef ::std::vector<ImplLineNode> VectorOfLineNodes; + + + //************************************************************ + // Base2D PolyPolygon Raster Converter (Rasterizer) + //************************************************************ + + namespace + { + struct VertexComparator + { + bool operator()( const B2DPolyPolygonRasterConverter::Vertex& rLHS, + const B2DPolyPolygonRasterConverter::Vertex& rRHS ) + { + return rLHS.aP1.getX() < rRHS.aP1.getX(); + } + }; + } + + void B2DPolyPolygonRasterConverter::init() + { + if(!maPolyPolyRectangle.isEmpty()) + { + const sal_Int32 nMinY( fround(maPolyPolyRectangle.getMinY()) ); + const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY); + + maScanlines.resize( nScanlines+1 ); + + // add all polygons + for( sal_uInt32 i(0), nCount(maPolyPolygon.count()); + i < nCount; + ++i ) + { + // add all vertices + const B2DPolygon& rPoly( maPolyPolygon.getB2DPolygon(i) ); + for( sal_uInt32 k(0), nVertices(rPoly.count()); + k<nVertices; + ++k ) + { + const B2DPoint& rP1( rPoly.getB2DPoint(k) ); + const B2DPoint& rP2( rPoly.getB2DPoint( (k + 1) % nVertices ) ); + + const sal_Int32 nVertexYP1( fround(rP1.getY()) ); + const sal_Int32 nVertexYP2( fround(rP2.getY()) ); + + // insert only vertices which are not strictly + // horizontal. Note that the ImplLineNode relies on + // this. + if(nVertexYP1 != nVertexYP2) + { + if( nVertexYP2 < nVertexYP1 ) + { + const sal_Int32 nStartScanline(nVertexYP2 - nMinY); + + // swap edges + maScanlines[ nStartScanline ].push_back( Vertex(rP2, rP1, false) ); + } + else + { + const sal_Int32 nStartScanline(nVertexYP1 - nMinY); + + maScanlines[ nStartScanline ].push_back( Vertex(rP1, rP2, true) ); + } + } + } + } + + // now sort all scanlines, with increasing x coordinates + VectorOfVertexVectors::iterator aIter( maScanlines.begin() ); + VectorOfVertexVectors::iterator aEnd( maScanlines.end() ); + while( aIter != aEnd ) + { + ::std::sort( aIter->begin(), + aIter->end(), + VertexComparator() ); + ++aIter; + } + } + } + + B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPoly ) : + maPolyPolygon( rPolyPoly ), + maPolyPolyRectangle( tools::getRange( rPolyPoly ) ), + maScanlines() + { + init(); + } + + namespace + { + B2DRectangle getCombinedBounds( const B2DPolyPolygon& rPolyPolyRaster, + const B2DRectangle& rRasterArea ) + { + B2DRectangle aRect( tools::getRange( rPolyPolyRaster ) ); + aRect.expand( rRasterArea ); + + return aRect; + } + } + + B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPolyRaster, + const B2DRectangle& rRasterArea ) : + maPolyPolygon( rPolyPolyRaster ), + maPolyPolyRectangle( + getCombinedBounds( rPolyPolyRaster, + rRasterArea ) ), + maScanlines() + { + init(); + } + + B2DPolyPolygonRasterConverter::~B2DPolyPolygonRasterConverter() + { + } + + namespace + { + class LineNodeGenerator + { + public: + LineNodeGenerator( VectorOfLineNodes& rActiveVertices ) : + mrActiveVertices( rActiveVertices ) + { + } + + void operator()( const B2DPolyPolygonRasterConverter::Vertex& rVertex ) + { + mrActiveVertices.push_back( ImplLineNode(rVertex.aP1, + rVertex.aP2, + rVertex.bDownwards) ); + } + + private: + VectorOfLineNodes& mrActiveVertices; + }; + + struct LineNodeComparator + { + bool operator()( const ImplLineNode& rLHS, const ImplLineNode& rRHS ) + { + return rLHS.getXPos() < rRHS.getXPos(); + } + }; + } + + void B2DPolyPolygonRasterConverter::rasterConvert( FillRule eFillRule ) + { + if( maScanlines.empty() ) + return; // no scanlines at all -> bail out + + const sal_Int32 nMinY( fround(maPolyPolyRectangle.getMinY()) ); + const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY); + + // Vector of currently active vertices. A vertex is active, if + // it crosses or touches the current scanline. + VectorOfLineNodes aActiveVertices; + + // mickey's optimized version... + radixSort rs; + std::size_t nb(0); + std::size_t nb_previous(0); + bool bSort(false); + + // process each scanline + for( sal_Int32 y(0); y <= nScanlines; ++y ) + { + // add vertices which start at current scanline into + // active vertex vector + ::std::for_each( maScanlines[y].begin(), + maScanlines[y].end(), + LineNodeGenerator( aActiveVertices ) ); + nb = aActiveVertices.size(); + if(nb != nb_previous) + { + nb_previous = nb; + bSort = true; + } + + // sort with increasing X + if(bSort) + { + bSort = false; + + if( nb ) + { + rs.sort(&aActiveVertices[0].mfXPos, + nb, + sizeof(ImplLineNode)); + } + } + + const std::size_t nLen( nb ); + if( !nLen ) + { + // empty scanline - call derived with an 'off' span + // for the full width + span( maPolyPolyRectangle.getMinX(), + maPolyPolyRectangle.getMaxX(), + nMinY + y, + false ); + } + else + { + const sal_Int32 nCurrY( nMinY + y ); + + // scanline not empty - forward all scans to derived, + // according to selected fill rule + + // TODO(P1): Maybe allow these 'off' span calls to be + // switched off (or all 'on' span calls, depending on + // use case scenario) + + // sorting didn't change the order of the elements + // in memory but prepared a list of indices in sorted order. + // thus we now process the nodes with an additional indirection. + sal_uInt32 *sorted = rs.indices(); + + // call derived with 'off' span for everything left of first active span + if( aActiveVertices[sorted[0]].getXPos() > maPolyPolyRectangle.getMinX() ) + { + span( maPolyPolyRectangle.getMinX(), + aActiveVertices[sorted[0]].getXPos(), + nCurrY, + false ); + } + + switch( eFillRule ) + { + default: + OSL_ENSURE(false, + "B2DPolyPolygonRasterConverter::rasterConvert(): Unexpected fill rule"); + return; + + case FillRule_EVEN_ODD: + // process each span in current scanline, with + // even-odd fill rule + for( ::std::size_t i(0), nLength(aActiveVertices.size()); + i+1 < nLength; + ++i ) + { + sal_uInt32 nIndex = sorted[i]; + sal_uInt32 nNextIndex = sorted[i+1]; + span( aActiveVertices[nIndex].getXPos(), + aActiveVertices[nNextIndex].getXPos(), + nCurrY, + i % 2 == 0 ); + + float delta = aActiveVertices[nIndex].nextLine(); + if(delta > 0.0f) + { + if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos()) + bSort = true; + } + else if(delta < 0.0f) + { + if(i) + { + sal_uInt32 nPrevIndex = sorted[i-1]; + if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos()) + bSort = true; + } + } + } + break; + + case FillRule_NONZERO_WINDING_NUMBER: + // process each span in current scanline, with + // non-zero winding numbe fill rule + sal_Int32 nWindingNumber(0); + for( ::std::size_t i(0), nLength(aActiveVertices.size()); + i+1 < nLength; + ++i ) + { + sal_uInt32 nIndex = sorted[i]; + sal_uInt32 nNextIndex = sorted[i+1]; + nWindingNumber += -1 + 2*aActiveVertices[nIndex].isDownwards(); + + span( aActiveVertices[nIndex].getXPos(), + aActiveVertices[nNextIndex].getXPos(), + nCurrY, + nWindingNumber != 0 ); + + float delta = aActiveVertices[nIndex].nextLine(); + if(delta > 0.0f) + { + if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos()) + bSort = true; + } + else if(delta < 0.0f) + { + if(i) + { + sal_uInt32 nPrevIndex = sorted[i-1]; + if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos()) + bSort = true; + } + } + } + break; + } + + // call derived with 'off' span for everything right of last active span + if( aActiveVertices[sorted[nb-1]].getXPos()+1.0 < maPolyPolyRectangle.getMaxX() ) + { + span( aActiveVertices[sorted[nb-1]].getXPos()+1.0, + maPolyPolyRectangle.getMaxX(), + nCurrY, + false ); + } + + // also call nextLine on very last line node + sal_uInt32 nIndex = sorted[nb-1]; + float delta = aActiveVertices[nIndex].nextLine(); + if(delta < 0.0f) + { + if(nb) + { + sal_uInt32 nPrevIndex = sorted[nb-2]; + if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos()) + bSort = true; + } + } + } + + // remove line nodes which have ended on the current scanline + aActiveVertices.erase( ::std::remove_if( aActiveVertices.begin(), + aActiveVertices.end(), + ::boost::mem_fn( &ImplLineNode::isEnded ) ), + aActiveVertices.end() ); + nb = aActiveVertices.size(); + if(nb != nb_previous) + { + nb_previous = nb; + bSort = true; + } + } + } +} +// eof |