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 14388144 : inline sal_Int64 toFractional( sal_Int32 v ) { return sal_Int64(sal_uInt64(v) << 32); }
43 : /// convert double to 32:32 fixed point
44 7253724 : 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 175399028 : 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 175399028 : 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 7253724 : Vertex( basegfx::B2DPoint const& rPt1,
71 : basegfx::B2DPoint const& rPt2,
72 : bool bDownwards ) :
73 14507448 : mnYCounter( basegfx::fround(rPt2.getY()) -
74 7253724 : basegfx::fround(rPt1.getY()) ),
75 7253724 : mnX( toFractional( basegfx::fround(rPt1.getX()) )),
76 : mnXDelta( toFractional(
77 7253724 : ((rPt2.getX() - rPt1.getX()) /
78 7253724 : (double)mnYCounter) )),
79 21761172 : mbDownwards(bDownwards)
80 7253724 : {}
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 6320817 : RasterConvertVertexComparator() {}
98 :
99 110827176 : bool operator()( const Vertex& rLHS,
100 : const Vertex& rRHS ) const
101 : {
102 110827176 : return rLHS.mnX < rRHS.mnX;
103 : }
104 :
105 4044669 : bool operator()( const Vertex* pLHS,
106 : const Vertex* pRHS ) const
107 : {
108 4044669 : 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 3567210 : 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 3567210 : const sal_Int32 nClipX1( std::max((sal_Int32)0,rClipRect.getMinX()) );
146 3567210 : const sal_Int32 nClipX2( rClipRect.getMaxX() );
147 3567210 : const sal_Int32 nClipY1( std::max((sal_Int32)0,rClipRect.getMinY()) );
148 3567210 : const sal_Int32 nClipY2( rClipRect.getMaxY() );
149 3567210 : const sal_Int64 nClipX1_frac( detail::toFractional(nClipX1) );
150 3567210 : const sal_Int64 nClipX2_frac( detail::toFractional(nClipX2) );
151 :
152 3567210 : basegfx::B2DRange const aPolyBounds( basegfx::tools::getRange(rPoly) );
153 :
154 3567210 : const sal_Int32 nMinY( basegfx::fround(aPolyBounds.getMinY()) );
155 : const sal_Int32 nMaxY(
156 : std::min(
157 : nClipY2-1,
158 3567210 : basegfx::fround(aPolyBounds.getMaxY())));
159 :
160 3567210 : if( nMinY > nMaxY )
161 813610 : return; // really, nothing to do then.
162 :
163 3160405 : detail::VectorOfVectorOfVertices aGET; // the Global Edge Table
164 3160405 : aGET.resize( nMaxY - nMinY + 1 );
165 :
166 : sal_uInt32 const nVertexCount(
167 3160405 : detail::setupGlobalEdgeTable( aGET, rPoly, nMinY ) );
168 :
169 :
170 : // Perform actual scan conversion
171 :
172 :
173 3160405 : if( aGET.empty() )
174 0 : return;
175 :
176 6320810 : detail::VectorOfVertexPtr aAET1; // the Active Edge Table
177 6320810 : detail::VectorOfVertexPtr aAET2;
178 3160405 : detail::VectorOfVertexPtr* pAET = &aAET1;
179 3160405 : detail::VectorOfVertexPtr* pAETOther = &aAET2;
180 3160405 : aAET1.reserve( nVertexCount );
181 3160405 : 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 6222120 : DestIterator aScanline( begin +
187 : vigra::Diff2D(
188 : 0,
189 : std::max(nMinY,
190 6320810 : nClipY1)) );
191 3160405 : detail::RasterConvertVertexComparator aComp;
192 :
193 :
194 : // now process each of the nMaxY - nMinY + 1 scanlines
195 :
196 :
197 111466304 : for( sal_Int32 y=nMinY; y <= nMaxY; ++y )
198 : {
199 108305899 : if( !aGET[y-nMinY].empty() )
200 : {
201 : // merge AET with current scanline's new vertices (both
202 : // are already correctly sorted)
203 3796367 : detail::VectorOfVectorOfVertices::value_type::iterator vertex=aGET[y-nMinY].begin();
204 3796367 : detail::VectorOfVectorOfVertices::value_type::iterator const end=aGET[y-nMinY].end();
205 14846458 : while( vertex != end )
206 : {
207 : // find insertion pos by binary search, and put ptr
208 : // into active edge vector
209 7253724 : pAET->insert( std::lower_bound( pAET->begin(),
210 : pAET->end(),
211 : &(*vertex),
212 7253724 : aComp ),
213 21761172 : &(*vertex) );
214 :
215 7253724 : ++vertex;
216 : }
217 : }
218 :
219 : // with less than two active edges, no fill visible
220 108305899 : if( pAET->size() >= 2 )
221 : {
222 : typename vigra::IteratorTraits<DestIterator>::row_iterator
223 105865126 : rowIter( aScanline.rowIterator() );
224 :
225 : // process each span in current scanline, with
226 : // even-odd fill rule
227 105865126 : detail::VectorOfVertexPtr::iterator currVertex( pAET->begin() );
228 105865126 : detail::VectorOfVertexPtr::iterator const lastVertex( pAET->end()-1 );
229 105865126 : sal_uInt32 nCrossedEdges(0);
230 318564090 : while( currVertex != lastVertex )
231 : {
232 : // TODO(P1): might be worth a try to extend the
233 : // size()==2 case also to the actual filling
234 : // here. YMMV.
235 106833838 : detail::Vertex& rV1( **currVertex );
236 106833838 : detail::Vertex const& rV2( **++currVertex );
237 :
238 : // calc fill status for both rules. might save a
239 : // few percent runtime to specialize here...
240 : const bool bEvenOddFill(
241 106833838 : eFillRule == basegfx::FillRule::EvenOdd && !(nCrossedEdges & 0x01) );
242 :
243 : // is span visible?
244 106833838 : if( bEvenOddFill &&
245 : y >= nClipY1 &&
246 : rV1.mnX < nClipX2_frac &&
247 : rV2.mnX > nClipX1_frac )
248 : {
249 : // clip span to horizontal bounds
250 : sal_Int32 const nStartX(
251 : std::max( nClipX1,
252 : std::min( nClipX2-1,
253 87699514 : detail::toRoundedInteger(rV1.mnX) )));
254 : sal_Int32 const nEndX(
255 : std::max( nClipX1,
256 : std::min( nClipX2,
257 87699514 : detail::toRoundedInteger(rV2.mnX) )));
258 :
259 : typename vigra::IteratorTraits<DestIterator>::row_iterator
260 87699514 : currPix( rowIter + nStartX);
261 : typename vigra::IteratorTraits<DestIterator>::row_iterator
262 92874989 : rowEnd( rowIter + nEndX );
263 :
264 : // TODO(P2): Provide specialized span fill methods on the
265 : // iterator/accessor
266 9964132758 : while( currPix != rowEnd )
267 9793909205 : ad.set(fillColor, currPix++);
268 : }
269 :
270 : // step vertices
271 106833838 : rV1.mnX += rV1.mnXDelta;
272 106833838 : --rV1.mnYCounter;
273 :
274 106833838 : ++nCrossedEdges;
275 : }
276 :
277 : // step vertex also for the last one
278 105865126 : detail::Vertex& rLastV( **currVertex );
279 105865126 : rLastV.mnX += rLastV.mnXDelta;
280 105865126 : --rLastV.mnYCounter;
281 :
282 :
283 : // prune AET from ended edges, and keep it sorted
284 :
285 :
286 105865126 : pAETOther->clear();
287 105865126 : if( pAET->size() == 2 )
288 : {
289 : // the case of exactly two active edges is both
290 : // sufficiently common (all 'simple' polygons have
291 : // it), and further more would complicate the
292 : // generic case below (which works with a sliding
293 : // triple of vertices).
294 105583910 : if( !aComp(*(*pAET)[0], *(*pAET)[1]) )
295 129888 : std::swap(*(*pAET)[0], *(*pAET)[1]);
296 :
297 105583910 : if( (*pAET)[0]->mnYCounter > 0 )
298 102193791 : pAETOther->push_back( (*pAET)[0] );
299 105583910 : if( (*pAET)[1]->mnYCounter > 0 )
300 102205490 : pAETOther->push_back( (*pAET)[1] );
301 : }
302 : else
303 : {
304 281216 : bool bFallbackTaken(false);
305 281216 : currVertex = pAET->begin();
306 281216 : detail::VectorOfVertexPtr::iterator prevVertex( currVertex );
307 1812233 : while( currVertex != lastVertex )
308 : {
309 : // try to get away with one linear swoop and
310 : // simple neighbor swapping. this is an
311 : // overwhelmingly common case - polygons with
312 : // excessively crisscrossing edges (which on
313 : // top of that cross more than one other edge
314 : // per scanline) are seldom. And even if we
315 : // get such a beast here, this extra loop has
316 : // still only linear cost
317 1249867 : if( aComp(**(currVertex+1),**currVertex) )
318 : {
319 4610 : std::swap(*currVertex, *(currVertex+1));
320 :
321 4610 : if( aComp(**currVertex,**prevVertex) )
322 : {
323 : // one swap was not sufficient -
324 : // fallback to generic sort algo, then
325 66 : detail::sortAET(*pAET, *pAETOther);
326 66 : bFallbackTaken = true;
327 66 : break;
328 : }
329 : }
330 :
331 1249801 : if( (*currVertex)->mnYCounter > 0 )
332 1144212 : pAETOther->push_back( *currVertex );
333 :
334 1249801 : prevVertex = currVertex++;
335 : }
336 :
337 : // don't forget to add last vertex (loop above
338 : // only deals with n-1 vertices)
339 281216 : if( !bFallbackTaken && (*currVertex)->mnYCounter > 0 )
340 260500 : pAETOther->push_back( *currVertex );
341 : }
342 :
343 105865126 : std::swap( pAET, pAETOther );
344 : }
345 :
346 108305899 : if( y >= nClipY1 )
347 94901942 : ++aScanline.y;
348 3160405 : }
349 : }
350 :
351 : } // namespace basebmp
352 :
353 : #endif /* INCLUDED_BASEBMP_POLYPOLYGONRENDERER_HXX */
354 :
355 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
