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