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