1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_basegfx.hxx"
26 
27 #include <basegfx/polygon/b2dpolypolygonrasterconverter.hxx>
28 
29 #include <basegfx/numeric/ftools.hxx>
30 #include <basegfx/polygon/b2dpolygon.hxx>
31 #include <basegfx/polygon/b2dpolygontools.hxx>
32 #include <basegfx/polygon/b2dpolypolygontools.hxx>
33 
34 #include <boost/mem_fn.hpp>
35 
36 #include <algorithm>
37 
38 namespace basegfx
39 {
40 	class radixSort {
41 
42 		//! public interface
43 		public:
44 
45 			//! default constructor
46 			radixSort( void );
47 
48 			//! destructor
49 			~radixSort( void );
50 
51 			bool sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride );
52 
indices(void) const53 			inline sal_uInt32 *indices( void ) const { return m_indices1; }
54 
55 		//! private attributes
56 		private:
57 
58 			// current size of index list
59 			sal_uInt32 m_current_size;
60 
61 			// last known size of index list
62 			sal_uInt32 m_previous_size;
63 
64 			// index lists
65 			sal_uInt32 *m_indices1;
66 			sal_uInt32 *m_indices2;
67 
68 			sal_uInt32 m_counter[256*4];
69 			sal_uInt32 m_offset[256];
70 
71 		//! private methods
72 		private:
73 
74 			bool resize( sal_uInt32 nNumElements );
75 			inline void reset_indices( void );
76 			bool prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride );
77 	};
78 
radixSort(void)79 	inline radixSort::radixSort( void ) {
80 
81 		m_indices1 = NULL;
82 		m_indices2 = NULL;
83 		m_current_size = 0;
84 		m_previous_size = 0;
85 
86 		reset_indices();
87 	}
88 
~radixSort(void)89 	inline radixSort::~radixSort( void ) {
90 
91 		delete [] m_indices2;
92 		delete [] m_indices1;
93 	}
94 
resize(sal_uInt32 nNumElements)95 	bool radixSort::resize( sal_uInt32 nNumElements ) {
96 
97 		if(nNumElements==m_previous_size)
98 			return true;
99 
100 		if(nNumElements > m_current_size) {
101 
102 			// release index lists
103 			if(m_indices2)
104 				delete [] m_indices2;
105 			if(m_indices1)
106 				delete [] m_indices1;
107 
108 			// allocate new index lists
109 			m_indices1 = new sal_uInt32[nNumElements];
110 			m_indices2 = new sal_uInt32[nNumElements];
111 
112 			// check for out of memory situation
113             if(!m_indices1 || !m_indices2) {
114 				delete [] m_indices1;
115 				delete [] m_indices2;
116 				m_indices1 = NULL;
117 				m_indices2 = NULL;
118 				m_current_size = 0;
119 				return false;
120 			}
121 
122 			m_current_size = nNumElements;
123 		}
124 
125 		m_previous_size = nNumElements;
126 
127 		// initialize indices
128 		reset_indices();
129 
130 		return true;
131 	}
132 
reset_indices(void)133 	inline void radixSort::reset_indices( void ) {
134 
135 		for(sal_uInt32 i=0;i<m_current_size;i++)
136 			m_indices1[i] = i;
137 	}
138 
prepareCounters(const float * pInput,sal_uInt32 nNumElements,sal_uInt32 dwStride)139 	bool radixSort::prepareCounters( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) {
140 
141 		// clear counters
142 		sal_uInt32 *ptr = m_counter;
143 		for(int i=0; i<64; ++i)
144         {
145 			*ptr++ = 0;
146 			*ptr++ = 0;
147 			*ptr++ = 0;
148 			*ptr++ = 0;
149 			*ptr++ = 0;
150 			*ptr++ = 0;
151 			*ptr++ = 0;
152 			*ptr++ = 0;
153 			*ptr++ = 0;
154 			*ptr++ = 0;
155 			*ptr++ = 0;
156 			*ptr++ = 0;
157 			*ptr++ = 0;
158 			*ptr++ = 0;
159 			*ptr++ = 0;
160 			*ptr++ = 0;
161 		}
162 
163 		// prepare pointers to relevant memory addresses
164 		sal_uInt8 *p = (sal_uInt8*)pInput;
165 		sal_uInt8 *pe = p+(nNumElements*dwStride);
166 		sal_uInt32 *h0= &m_counter[0];
167 		sal_uInt32 *h1= &m_counter[256];
168 		sal_uInt32 *h2= &m_counter[512];
169 		sal_uInt32 *h3= &m_counter[768];
170 
171 		sal_uInt32 *Indices = m_indices1;
172 		float previous_value = *(float *)(((sal_uInt8 *)pInput)+(m_indices1[0]*dwStride));
173 		bool bSorted = true;
174 		while(p!=pe) {
175 			float value = *(float *)(((sal_uInt8 *)pInput)+((*Indices++)*dwStride));
176 			if(value<previous_value)	{
177 				bSorted = false;
178 				break;
179 			}
180 			previous_value = value;
181 			h0[*p++]++;
182 			h1[*p++]++;
183 			h2[*p++]++;
184 			h3[*p++]++;
185 			p += dwStride-4;
186 		}
187 		if(bSorted)
188 			return true;
189 		while(p!=pe) {
190 			h0[*p++]++;
191 			h1[*p++]++;
192 			h2[*p++]++;
193 			h3[*p++]++;
194 			p += dwStride-4;
195 		}
196 		return false;
197 	}
198 
sort(const float * pInput,sal_uInt32 nNumElements,sal_uInt32 dwStride)199 	bool radixSort::sort( const float *pInput, sal_uInt32 nNumElements, sal_uInt32 dwStride ) {
200 
201 		if(!(pInput))
202 			return false;
203 		if(!(nNumElements))
204 			return false;
205 		if(!(resize(nNumElements)))
206 			return false;
207 
208 		// prepare radix counters, return if already sorted
209 		if(prepareCounters(pInput,nNumElements,dwStride))
210 			return true;
211 
212 		// count number of negative values
213 		sal_uInt32 num_negatives = 0;
214 		sal_uInt32 *h3= &m_counter[768];
215 		for(sal_uInt32 i=128;i<256;i++)
216 			num_negatives += h3[i];
217 
218 		// perform passes, one for each byte
219 		for(sal_uInt32 j=0;j<4;j++) {
220 
221 			// ignore this pass if all values have the same byte
222 			bool bRun = true;
223 			sal_uInt32 *current_counter = &m_counter[j<<8];
224 			sal_uInt8 unique_value = *(((sal_uInt8*)pInput)+j);
225 			if(current_counter[unique_value]==nNumElements)
226 				bRun=false;
227 
228 			// does the incoming byte contain the sign bit?
229 			sal_uInt32 i;
230 			if(j!=3) {
231 				if(bRun) {
232 					m_offset[0] = 0;
233 					for(i=1;i<256;i++)
234 						m_offset[i] = m_offset[i-1] + current_counter[i-1];
235 					sal_uInt8 *InputBytes = (sal_uInt8 *)pInput;
236 					sal_uInt32 *Indices = m_indices1;
237 					sal_uInt32 *IndicesEnd = &m_indices1[nNumElements];
238 					InputBytes += j;
239 					while(Indices!=IndicesEnd) {
240 						sal_uInt32 id = *Indices++;
241 						m_indices2[m_offset[InputBytes[id*dwStride]]++] = id;
242 					}
243 					sal_uInt32 *Tmp	= m_indices1;
244 					m_indices1 = m_indices2;
245 					m_indices2 = Tmp;
246 				}
247 			}
248 			else {
249 				if(bRun) {
250 					m_offset[0] = num_negatives;
251 					for(i=1;i<128;i++)
252 						m_offset[i] = m_offset[i-1] + current_counter[i-1];
253 					m_offset[255] = 0;
254 					for(i=0;i<127;i++)
255 						m_offset[254-i] = m_offset[255-i] + current_counter[255-i];
256 					for(i=128;i<256;i++)
257 						m_offset[i] += current_counter[i];
258 					for(i=0;i<nNumElements;i++) {
259 						sal_uInt32 Radix = (*(sal_uInt32 *)(((sal_uInt8 *)pInput)+(m_indices1[i]*dwStride)))>>24;
260 						if(Radix<128) m_indices2[m_offset[Radix]++] = m_indices1[i];
261 						else m_indices2[--m_offset[Radix]] = m_indices1[i];
262 					}
263 					sal_uInt32 *Tmp	= m_indices1;
264 					m_indices1 = m_indices2;
265 					m_indices2 = Tmp;
266 				}
267 				else {
268 					if(unique_value>=128) {
269 						for(i=0;i<nNumElements;i++)
270 							m_indices2[i] = m_indices1[nNumElements-i-1];
271 						sal_uInt32 *Tmp	= m_indices1;
272 						m_indices1 = m_indices2;
273 						m_indices2 = Tmp;
274 					}
275 				}
276 			}
277 		}
278 
279 		return true;
280 	}
281 
282 	//************************************************************
283 	// Internal vertex storage of B2DPolyPolygonRasterConverter
284 	//************************************************************
285 
Vertex()286     inline B2DPolyPolygonRasterConverter::Vertex::Vertex() :
287         aP1(),
288         aP2(),
289         bDownwards( true )
290     {
291     }
292 
Vertex(const B2DPoint & rP1,const B2DPoint & rP2,bool bDown)293     inline B2DPolyPolygonRasterConverter::Vertex::Vertex( const B2DPoint& rP1, const B2DPoint& rP2, bool bDown ) :
294         aP1( rP1 ),
295         aP2( rP2 ),
296         bDownwards( bDown )
297     {
298     }
299 
300 
301 	//************************************************************
302 	// Helper class for holding horizontal line segments during raster
303 	// conversion
304 	//************************************************************
305 
306 	namespace
307     {
308         class ImplLineNode
309         {
310 		public:
311             sal_Int32	mnYCounter;
312             float		mfXPos;
313             float		mfXDelta;
314             bool		mbDownwards;
315 
316         public:
317             /**rP1 and rP2 must not have equal y values, when rounded
318                to integer!
319             */
ImplLineNode(const B2DPoint & rP1,const B2DPoint & rP2,bool bDown)320             ImplLineNode(const B2DPoint& rP1, const B2DPoint& rP2, bool bDown) :
321                 mnYCounter( fround(rP2.getY()) - fround(rP1.getY()) ),
322                 mfXPos( (float)(rP1.getX()) ),
323                 mfXDelta((float) ((rP2.getX() - rP1.getX()) / mnYCounter) ),
324                 mbDownwards( bDown )
325             {
326             }
327 
328             /// get current x position
getXPos() const329             const float& getXPos() const
330             {
331                 return mfXPos;
332             }
333 
334             /// returns true, if line ends on this Y value
nextLine()335             float nextLine()
336             {
337                 if(mnYCounter>=0)
338                 {
339                     // go one step in Y
340                     mfXPos += mfXDelta;
341                     --mnYCounter;
342 					return mfXDelta;
343                 }
344 
345 				return 0.0f;
346             }
347 
isEnded()348             bool isEnded()
349             {
350                 return mnYCounter<=0;
351             }
352 
isDownwards()353             bool isDownwards()
354             {
355                 return mbDownwards;
356             }
357         };
358     }
359 
360     typedef ::std::vector<ImplLineNode> VectorOfLineNodes;
361 
362 
363 	//************************************************************
364 	//   Base2D PolyPolygon Raster Converter (Rasterizer)
365 	//************************************************************
366 
367     namespace
368     {
369         struct VertexComparator
370         {
operator ()basegfx::__anon62c76c420211::VertexComparator371             bool operator()( const B2DPolyPolygonRasterConverter::Vertex& rLHS,
372                              const B2DPolyPolygonRasterConverter::Vertex& rRHS )
373             {
374                 return rLHS.aP1.getX() < rRHS.aP1.getX();
375             }
376         };
377     }
378 
init()379     void B2DPolyPolygonRasterConverter::init()
380     {
381         if(!maPolyPolyRectangle.isEmpty())
382         {
383             const sal_Int32	nMinY( fround(maPolyPolyRectangle.getMinY()) );
384             const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY);
385 
386             maScanlines.resize( nScanlines+1 );
387 
388             // add all polygons
389             for( sal_uInt32 i(0), nCount(maPolyPolygon.count());
390                  i < nCount;
391                  ++i )
392             {
393                 // add all vertices
394                 const B2DPolygon& rPoly( maPolyPolygon.getB2DPolygon(i) );
395                 for( sal_uInt32 k(0), nVertices(rPoly.count());
396                      k<nVertices;
397                      ++k )
398                 {
399                     const B2DPoint& rP1( rPoly.getB2DPoint(k) );
400                     const B2DPoint& rP2( rPoly.getB2DPoint( (k + 1) % nVertices ) );
401 
402                     const sal_Int32 nVertexYP1( fround(rP1.getY()) );
403                     const sal_Int32 nVertexYP2( fround(rP2.getY()) );
404 
405                     // insert only vertices which are not strictly
406                     // horizontal. Note that the ImplLineNode relies on
407                     // this.
408                     if(nVertexYP1 != nVertexYP2)
409                     {
410                         if( nVertexYP2 < nVertexYP1 )
411                         {
412                             const sal_Int32 nStartScanline(nVertexYP2 - nMinY);
413 
414                             // swap edges
415                             maScanlines[ nStartScanline ].push_back( Vertex(rP2, rP1, false) );
416                         }
417                         else
418                         {
419                             const sal_Int32 nStartScanline(nVertexYP1 - nMinY);
420 
421                             maScanlines[ nStartScanline ].push_back( Vertex(rP1, rP2, true) );
422                         }
423                     }
424                 }
425             }
426 
427             // now sort all scanlines, with increasing x coordinates
428             VectorOfVertexVectors::iterator aIter( maScanlines.begin() );
429             VectorOfVertexVectors::iterator aEnd( maScanlines.end() );
430             while( aIter != aEnd )
431             {
432                 ::std::sort( aIter->begin(),
433                              aIter->end(),
434                              VertexComparator() );
435                 ++aIter;
436             }
437         }
438     }
439 
B2DPolyPolygonRasterConverter(const B2DPolyPolygon & rPolyPoly)440     B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPoly ) :
441         maPolyPolygon( rPolyPoly ),
442         maPolyPolyRectangle( tools::getRange( rPolyPoly ) ),
443         maScanlines()
444     {
445         init();
446     }
447 
448     namespace
449     {
getCombinedBounds(const B2DPolyPolygon & rPolyPolyRaster,const B2DRectangle & rRasterArea)450         B2DRectangle getCombinedBounds( const B2DPolyPolygon& rPolyPolyRaster,
451                                         const B2DRectangle&   rRasterArea )
452         {
453             B2DRectangle aRect( tools::getRange( rPolyPolyRaster ) );
454             aRect.expand( rRasterArea );
455 
456             return aRect;
457         }
458     }
459 
B2DPolyPolygonRasterConverter(const B2DPolyPolygon & rPolyPolyRaster,const B2DRectangle & rRasterArea)460     B2DPolyPolygonRasterConverter::B2DPolyPolygonRasterConverter( const B2DPolyPolygon& rPolyPolyRaster,
461                                                                   const B2DRectangle&   rRasterArea ) :
462         maPolyPolygon( rPolyPolyRaster ),
463         maPolyPolyRectangle(
464             getCombinedBounds( rPolyPolyRaster,
465                                rRasterArea ) ),
466         maScanlines()
467     {
468         init();
469     }
470 
~B2DPolyPolygonRasterConverter()471     B2DPolyPolygonRasterConverter::~B2DPolyPolygonRasterConverter()
472     {
473     }
474 
475     namespace
476     {
477         class LineNodeGenerator
478         {
479         public:
LineNodeGenerator(VectorOfLineNodes & rActiveVertices)480             LineNodeGenerator( VectorOfLineNodes& rActiveVertices ) :
481                 mrActiveVertices( rActiveVertices )
482             {
483             }
484 
operator ()(const B2DPolyPolygonRasterConverter::Vertex & rVertex)485             void operator()( const B2DPolyPolygonRasterConverter::Vertex& rVertex )
486             {
487                 mrActiveVertices.push_back( ImplLineNode(rVertex.aP1,
488                                                          rVertex.aP2,
489                                                          rVertex.bDownwards) );
490             }
491 
492         private:
493             VectorOfLineNodes& mrActiveVertices;
494         };
495 
496         struct LineNodeComparator
497         {
operator ()basegfx::__anon62c76c420411::LineNodeComparator498             bool operator()( const ImplLineNode& rLHS, const ImplLineNode& rRHS )
499             {
500                 return rLHS.getXPos() < rRHS.getXPos();
501             }
502         };
503     }
504 
rasterConvert(FillRule eFillRule)505     void B2DPolyPolygonRasterConverter::rasterConvert( FillRule eFillRule )
506     {
507         if( maScanlines.empty() )
508             return; // no scanlines at all -> bail out
509 
510         const sal_Int32	nMinY( fround(maPolyPolyRectangle.getMinY()) );
511         const sal_Int32 nScanlines(fround(maPolyPolyRectangle.getMaxY()) - nMinY);
512 
513         // Vector of currently active vertices. A vertex is active, if
514         // it crosses or touches the current scanline.
515         VectorOfLineNodes	aActiveVertices;
516 
517 		// mickey's optimized version...
518 		radixSort   rs;
519 		std::size_t nb(0);
520         std::size_t nb_previous(0);
521 		bool        bSort(false);
522 
523         // process each scanline
524         for( sal_Int32 y(0); y <= nScanlines; ++y )
525         {
526             // add vertices which start at current scanline into
527             // active vertex vector
528             ::std::for_each( maScanlines[y].begin(),
529                              maScanlines[y].end(),
530                              LineNodeGenerator( aActiveVertices ) );
531 			nb = aActiveVertices.size();
532 			if(nb != nb_previous)
533             {
534 				nb_previous = nb;
535 				bSort = true;
536 			}
537 
538             // sort with increasing X
539 			if(bSort)
540             {
541 				bSort = false;
542 
543                 if( nb )
544                 {
545                     rs.sort(&aActiveVertices[0].mfXPos,
546                             nb,
547                             sizeof(ImplLineNode));
548                 }
549 			}
550 
551             const std::size_t nLen( nb );
552             if( !nLen )
553             {
554                 // empty scanline - call derived with an 'off' span
555                 // for the full width
556                 span( maPolyPolyRectangle.getMinX(),
557                       maPolyPolyRectangle.getMaxX(),
558                       nMinY + y,
559                       false );
560             }
561             else
562             {
563                 const sal_Int32 nCurrY( nMinY + y );
564 
565                 // scanline not empty - forward all scans to derived,
566                 // according to selected fill rule
567 
568                 // TODO(P1): Maybe allow these 'off' span calls to be
569                 // switched off (or all 'on' span calls, depending on
570                 // use case scenario)
571 
572 				// sorting didn't change the order of the elements
573 				// in memory but prepared a list of indices in sorted order.
574 				// thus we now process the nodes with an additional indirection.
575 				sal_uInt32 *sorted = rs.indices();
576 
577                 // call derived with 'off' span for everything left of first active span
578                 if( aActiveVertices[sorted[0]].getXPos() > maPolyPolyRectangle.getMinX() )
579                 {
580                     span( maPolyPolyRectangle.getMinX(),
581                           aActiveVertices[sorted[0]].getXPos(),
582                           nCurrY,
583                           false );
584                 }
585 
586                 switch( eFillRule )
587                 {
588                     default:
589                         OSL_ENSURE(false,
590                                    "B2DPolyPolygonRasterConverter::rasterConvert(): Unexpected fill rule");
591                         return;
592 
593                     case FillRule_EVEN_ODD:
594                         // process each span in current scanline, with
595                         // even-odd fill rule
596                         for( ::std::size_t i(0), nLength(aActiveVertices.size());
597                              i+1 < nLength;
598                              ++i )
599                         {
600 							sal_uInt32 nIndex = sorted[i];
601 							sal_uInt32 nNextIndex = sorted[i+1];
602                             span( aActiveVertices[nIndex].getXPos(),
603                                   aActiveVertices[nNextIndex].getXPos(),
604                                   nCurrY,
605                                   i % 2 == 0 );
606 
607                             float delta = aActiveVertices[nIndex].nextLine();
608 							if(delta > 0.0f)
609                             {
610 								if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos())
611 									bSort = true;
612 							}
613 							else if(delta < 0.0f)
614                             {
615 								if(i)
616                                 {
617 									sal_uInt32 nPrevIndex = sorted[i-1];
618 									if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos())
619 										bSort = true;
620 								}
621 							}
622                         }
623                         break;
624 
625                     case FillRule_NONZERO_WINDING_NUMBER:
626                         // process each span in current scanline, with
627                         // non-zero winding numbe fill rule
628                         sal_Int32 nWindingNumber(0);
629                         for( ::std::size_t i(0), nLength(aActiveVertices.size());
630                              i+1 < nLength;
631                              ++i )
632                         {
633 							sal_uInt32 nIndex = sorted[i];
634 							sal_uInt32 nNextIndex = sorted[i+1];
635                             nWindingNumber += -1 + 2*aActiveVertices[nIndex].isDownwards();
636 
637                             span( aActiveVertices[nIndex].getXPos(),
638                                   aActiveVertices[nNextIndex].getXPos(),
639                                   nCurrY,
640                                   nWindingNumber != 0 );
641 
642                             float delta = aActiveVertices[nIndex].nextLine();
643 							if(delta > 0.0f)
644                             {
645 								if(aActiveVertices[nIndex].getXPos() > aActiveVertices[nNextIndex].getXPos())
646 									bSort = true;
647 							}
648 							else if(delta < 0.0f)
649                             {
650 								if(i)
651                                 {
652 									sal_uInt32 nPrevIndex = sorted[i-1];
653 									if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos())
654 										bSort = true;
655 								}
656 							}
657                         }
658                         break;
659                 }
660 
661                 // call derived with 'off' span for everything right of last active span
662                 if( aActiveVertices[sorted[nb-1]].getXPos()+1.0 < maPolyPolyRectangle.getMaxX() )
663                 {
664                     span( aActiveVertices[sorted[nb-1]].getXPos()+1.0,
665                           maPolyPolyRectangle.getMaxX(),
666                           nCurrY,
667                           false );
668                 }
669 
670                 // also call nextLine on very last line node
671 				sal_uInt32 nIndex = sorted[nb-1];
672                 float delta = aActiveVertices[nIndex].nextLine();
673 				if(delta < 0.0f)
674                 {
675 					if(nb)
676                     {
677 						sal_uInt32 nPrevIndex = sorted[nb-2];
678 						if(aActiveVertices[nIndex].getXPos() < aActiveVertices[nPrevIndex].getXPos())
679 							bSort = true;
680 					}
681 				}
682             }
683 
684             // remove line nodes which have ended on the current scanline
685             aActiveVertices.erase( ::std::remove_if( aActiveVertices.begin(),
686                                                      aActiveVertices.end(),
687                                                      ::boost::mem_fn( &ImplLineNode::isEnded ) ),
688                                    aActiveVertices.end() );
689 			nb = aActiveVertices.size();
690 			if(nb != nb_previous)
691             {
692 				nb_previous = nb;
693 				bSort = true;
694 			}
695         }
696 	}
697 }
698 // eof
699