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