#i65904# Dumped basegfx polygon raster converter in favor of a specialized solution; constructing all accessors with passed parameter now for the BitmapRenderer; significantly improved test coverage for polygon rasterizing

4 files changed, 393 insertions, 8 deletions

diff --git a/basebmp/inc/basebmp/clippedlinerenderer.hxx b/basebmp/inc/basebmp/clippedlinerenderer.hxx
index 72b768f66fef..0f26309c30d5 100644
--- a/basebmp/inc/basebmp/clippedlinerenderer.hxx
+++ b/basebmp/inc/basebmp/clippedlinerenderer.hxx
@@ -4,9 +4,9 @@
  *
  *  $RCSfile: clippedlinerenderer.hxx,v $
  *
- *  $Revision: 1.6 $
+ *  $Revision: 1.7 $
  *
- *  last change: $Author: thb $ $Date: 2006-07-11 11:38:54 $
+ *  last change: $Author: thb $ $Date: 2006-07-27 11:35:31 $
  *
  *  The Contents of this file are made available subject to
  *  the terms of GNU Lesser General Public License Version 2.1.
@@ -209,7 +209,7 @@ inline bool prepareClip( sal_Int32  a1,
     pixel, the pixel closer to pt1 will be chosen. Giving true here
     makes renderClippedLine() choose pt2 in those cases.
  */
-template< class Iterator, class Accessor >
+template< class Iterator, class Accessor > inline
 void renderClippedLine( basegfx::B2IPoint             aPt1,
                         basegfx::B2IPoint             aPt2,
                         const basegfx::B2IRange&      rClipRect,
diff --git a/basebmp/inc/basebmp/linerenderer.hxx b/basebmp/inc/basebmp/linerenderer.hxx
index c151c0d1010b..df58c6f56742 100644
--- a/basebmp/inc/basebmp/linerenderer.hxx
+++ b/basebmp/inc/basebmp/linerenderer.hxx
@@ -4,9 +4,9 @@
  *
  *  $RCSfile: linerenderer.hxx,v $
  *
- *  $Revision: 1.4 $
+ *  $Revision: 1.5 $
  *
- *  last change: $Author: thb $ $Date: 2006-07-11 11:38:55 $
+ *  last change: $Author: thb $ $Date: 2006-07-27 11:35:31 $
  *
  *  The Contents of this file are made available subject to
  *  the terms of GNU Lesser General Public License Version 2.1.
@@ -79,7 +79,7 @@ namespace basebmp
     pixel, the pixel closer to pt1 will be chosen. Giving true here
     makes renderClippedLine() choose pt2 in those cases.
  */
-template< class Iterator, class Accessor >
+template< class Iterator, class Accessor > inline
 void renderLine( const basegfx::B2IPoint&      rPt1,
                  const basegfx::B2IPoint&      rPt2,
                  typename Accessor::value_type color,
diff --git a/basebmp/inc/basebmp/polypolygonrenderer.hxx b/basebmp/inc/basebmp/polypolygonrenderer.hxx
new file mode 100644
index 000000000000..2a02c96ceca0
--- /dev/null
+++ b/basebmp/inc/basebmp/polypolygonrenderer.hxx
@@ -0,0 +1,360 @@
+/*************************************************************************
+ *
+ *  OpenOffice.org - a multi-platform office productivity suite
+ *
+ *  $RCSfile: polypolygonrenderer.hxx,v $
+ *
+ *  $Revision: 1.1 $
+ *
+ *  last change: $Author: thb $ $Date: 2006-07-27 11:35:31 $
+ *
+ *  The Contents of this file are made available subject to
+ *  the terms of GNU Lesser General Public License Version 2.1.
+ *
+ *
+ *    GNU Lesser General Public License Version 2.1
+ *    =============================================
+ *    Copyright 2005 by Sun Microsystems, Inc.
+ *    901 San Antonio Road, Palo Alto, CA 94303, USA
+ *
+ *    This library is free software; you can redistribute it and/or
+ *    modify it under the terms of the GNU Lesser General Public
+ *    License version 2.1, as published by the Free Software Foundation.
+ *
+ *    This library 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 for more details.
+ *
+ *    You should have received a copy of the GNU Lesser General Public
+ *    License along with this library; if not, write to the Free Software
+ *    Foundation, Inc., 59 Temple Place, Suite 330, Boston,
+ *    MA  02111-1307  USA
+ *
+ ************************************************************************/
+
+#ifndef INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX
+#define INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX
+
+#include <basegfx/point/b2dpoint.hxx>
+#include <basegfx/range/b2drange.hxx>
+#include <basegfx/range/b2irange.hxx>
+#include <basegfx/polygon/b2dpolypolygon.hxx>
+#include <basegfx/polygon/b2dpolypolygontools.hxx>
+#include <basegfx/numeric/ftools.hxx>
+
+#include <vigra/diff2d.hxx>
+#include <vigra/iteratortraits.hxx>
+
+#include <vector>
+
+
+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 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) + ((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<Vertex> > 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
+        {
+            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 > inline
+    void renderClippedPolyPolygon( DestIterator                   begin,
+                                   DestAccessor                   ad,
+                                   T                              fillColor,
+                                   const basegfx::B2IRange&       rClipRect,
+                                   basegfx::B2DPolyPolygon const& rPoly )
+    {
+        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<DestIterator>::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                                nVertexCount(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 );
+
+                    // even/odd fillrule
+                    if( !(nVertexCount & 0x01) &&
+                        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<DestIterator>::row_iterator
+                            currPix( rowIter + nStartX);
+                        typename vigra::IteratorTraits<DestIterator>::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;
+
+                    ++nVertexCount;
+                }
+
+                // 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 */
diff --git a/basebmp/inc/basebmp/scaleimage.hxx b/basebmp/inc/basebmp/scaleimage.hxx
index f3231dec2e9b..af8557175e04 100644
--- a/basebmp/inc/basebmp/scaleimage.hxx
+++ b/basebmp/inc/basebmp/scaleimage.hxx
@@ -4,9 +4,9 @@
  *
  *  $RCSfile: scaleimage.hxx,v $
  *
- *  $Revision: 1.1 $
+ *  $Revision: 1.2 $
  *
- *  last change: $Author: thb $ $Date: 2006-07-14 14:22:58 $
+ *  last change: $Author: thb $ $Date: 2006-07-27 11:35:31 $
  *
  *  The Contents of this file are made available subject to
  *  the terms of GNU Lesser General Public License Version 2.1.
@@ -97,6 +97,29 @@ inline void scaleLine( SourceIter      s_begin,
     }
 }
 
+/** Scale an image using zero order interpolation (pixel replication)
+
+    Source and destination range must be at least one pixel wide and
+    high.
+
+    @param s_begin
+    Start iterator for source image
+
+    @param s_end
+    End iterator for source image
+
+    @param s_acc
+    Source accessor
+
+    @param d_begin
+    Start iterator for destination image
+
+    @param d_end
+    End iterator for destination image
+
+    @param d_acc
+    Destination accessor
+ */
 template< class SourceIter, class SourceAcc,
           class DestIter, class DestAcc >
 inline void scaleImage( SourceIter      s_begin,
@@ -142,6 +165,8 @@ inline void scaleImage( SourceIter      s_begin,
     }
 }
 
+/** Scale an image, range tuple version
+ */
 template< class SourceIter, class SourceAcc,
           class DestIter, class DestAcc >
 inline void scaleImage( vigra::triple<SourceIter,SourceIter,SourceAcc> const& src,