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