vcl/source/gdi/impvect.cxx

   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 #include <stdlib.h>
  21 #include <vcl/bitmapaccess.hxx>
  22 #include <tools/poly.hxx>
  23 #include <vcl/gdimtf.hxx>
  24 #include <vcl/metaact.hxx>
  25 #include <vcl/svapp.hxx>
  26 #include <vcl/wrkwin.hxx>
  27 #include <vcl/virdev.hxx>
  28 #include <impvect.hxx>
  29 #include <memory>
  30
  31 #define VECT_POLY_MAX 8192
  32
  33 #define VECT_FREE_INDEX 0
  34 #define VECT_CONT_INDEX 1
  35 #define VECT_DONE_INDEX 2
  36
  37 #define VECT_POLY_INLINE_INNER  1UL
  38 #define VECT_POLY_INLINE_OUTER  2UL
  39 #define VECT_POLY_OUTLINE_INNER 4UL
  40 #define VECT_POLY_OUTLINE_OUTER 8UL
  41
  42 #define VECT_MAP( _def_pIn, _def_pOut, _def_nVal )  _def_pOut[_def_nVal]=(_def_pIn[_def_nVal]=((_def_nVal)*4)+1)+5;
  43 #define BACK_MAP( _def_nVal )                       ((((_def_nVal)+2)>>2)-1)
  44 #define VECT_PROGRESS( _def_pProgress, _def_nVal ) \
  45   if(_def_pProgress)      \
  46       (_def_pProgress->Call(_def_nVal));
  47
  48 class ImplVectMap;
  49 class ImplChain;
  50
  51 namespace ImplVectorizer
  52 {
  53     ImplVectMap* ImplExpand( BitmapReadAccess* pRAcc, const Color& rColor );
  54     void     ImplCalculate( ImplVectMap* pMap, tools::PolyPolygon& rPolyPoly, sal_uInt8 cReduce );
  55     bool     ImplGetChain( ImplVectMap* pMap, const Point& rStartPt, ImplChain& rChain );
  56     bool     ImplIsUp( ImplVectMap* pMap, long nY, long nX );
  57     void     ImplLimitPolyPoly( tools::PolyPolygon& rPolyPoly );
  58 }
  59
  60 struct ChainMove { long nDX; long nDY; };
  61
  62 static const ChainMove aImplMove[ 8 ] =   {
  63                                         { 1, 0 },
  64                                         { 0, -1 },
  65                                         { -1, 0 },
  66                                         { 0, 1 },
  67                                         { 1, -1 },
  68                                         { -1, -1 },
  69                                         { -1, 1 },
  70                                         { 1, 1 }
  71                                     };
  72
  73 static const ChainMove aImplMoveInner[ 8 ] =  {
  74                                             { 0, 1 },
  75                                             { 1, 0 },
  76                                             { 0, -1 },
  77                                             { -1, 0 },
  78                                             { 0, 1 },
  79                                             { 1, 0 },
  80                                             { 0, -1 },
  81                                             { -1, 0 }
  82                                         };
  83
  84 static const ChainMove aImplMoveOuter[ 8 ] =  {
  85                                             { 0, -1 },
  86                                             { -1, 0 },
  87                                             { 0, 1 },
  88                                             { 1, 0 },
  89                                             { -1, 0 },
  90                                             { 0, 1 },
  91                                             { 1, 0 },
  92                                             { 0, -1 }
  93                                         };
  94
  95 struct ImplColorSet
  96 {
  97     BitmapColor maColor;
  98     sal_uInt16      mnIndex;
  99     bool        mbSet;
 100 };
 101
 102 extern "C" int SAL_CALL ImplColorSetCmpFnc( const void* p1, const void* p2 )
 103 {
 104     ImplColorSet const * pSet1 = static_cast<ImplColorSet const *>(p1);
 105     ImplColorSet const * pSet2 = static_cast<ImplColorSet const *>(p2);
 106     int             nRet;
 107
 108     if( pSet1->mbSet && pSet2->mbSet )
 109     {
 110         const sal_uInt8 cLum1 = pSet1->maColor.GetLuminance();
 111         const sal_uInt8 cLum2 = pSet2->maColor.GetLuminance();
 112         nRet = ( ( cLum1 > cLum2 ) ? -1 : ( ( cLum1 == cLum2 ) ? 0 : 1 ) );
 113     }
 114     else if( pSet1->mbSet )
 115         nRet = -1;
 116     else if( pSet2->mbSet )
 117         nRet = 1;
 118     else
 119         nRet = 0;
 120
 121     return nRet;
 122 }
 123
 124 class ImplPointArray
 125 {
 126     Point* mpArray;
 127     sal_uLong mnSize;
 128     sal_uLong mnRealSize;
 129
 130 public:
 131
 132     ImplPointArray();
 133    ~ImplPointArray();
 134
 135     void ImplSetSize( sal_uLong nSize );
 136     sal_uLong ImplGetRealSize() const { return mnRealSize; }
 137     void ImplSetRealSize( sal_uLong nRealSize ) { mnRealSize = nRealSize; }
 138     void ImplCreatePoly( tools::Polygon& rPoly ) const;
 139
 140     inline Point& operator[]( sal_uLong nPos );
 141     inline const Point& operator[]( sal_uLong nPos ) const;
 142
 143 };
 144
 145 ImplPointArray::ImplPointArray() :
 146     mpArray     ( nullptr ),
 147     mnSize      ( 0UL ),
 148     mnRealSize  ( 0UL )
 149
 150 {
 151 }
 152
 153 ImplPointArray::~ImplPointArray()
 154 {
 155     if( mpArray )
 156         rtl_freeMemory( mpArray );
 157 }
 158
 159 void ImplPointArray::ImplSetSize( sal_uLong nSize )
 160 {
 161     const sal_uLong nTotal = nSize * sizeof( Point );
 162
 163     mnSize = nSize;
 164     mnRealSize = 0UL;
 165
 166     if( mpArray )
 167         rtl_freeMemory( mpArray );
 168
 169     mpArray = static_cast<Point*>(rtl_allocateMemory( nTotal ));
 170     memset( mpArray, 0, nTotal );
 171 }
 172
 173 inline Point& ImplPointArray::operator[]( sal_uLong nPos )
 174 {
 175     SAL_WARN_IF( nPos >= mnSize, "vcl", "ImplPointArray::operator[]: nPos out of range!" );
 176     return mpArray[ nPos ];
 177 }
 178
 179 inline const Point& ImplPointArray::operator[]( sal_uLong nPos ) const
 180 {
 181     SAL_WARN_IF( nPos >= mnSize, "vcl", "ImplPointArray::operator[]: nPos out of range!" );
 182     return mpArray[ nPos ];
 183 }
 184
 185 void ImplPointArray::ImplCreatePoly( tools::Polygon& rPoly ) const
 186 {
 187     rPoly = tools::Polygon( sal::static_int_cast<sal_uInt16>(mnRealSize), mpArray );
 188 }
 189
 190 class ImplVectMap
 191 {
 192 private:
 193
 194     Scanline        mpBuf;
 195     Scanline*       mpScan;
 196     long            mnWidth;
 197     long            mnHeight;
 198
 199 public:
 200
 201                     ImplVectMap( long nWidth, long nHeight );
 202                     ~ImplVectMap();
 203
 204     long     Width() const { return mnWidth; }
 205     long     Height() const { return mnHeight; }
 206
 207     inline void     Set( long nY, long nX, sal_uInt8 cVal );
 208     inline sal_uInt8        Get( long nY, long nX ) const;
 209
 210     inline bool     IsFree( long nY, long nX ) const;
 211     inline bool     IsCont( long nY, long nX ) const;
 212     inline bool     IsDone( long nY, long nX ) const;
 213
 214 };
 215
 216 ImplVectMap::ImplVectMap( long nWidth, long nHeight ) :
 217     mnWidth ( nWidth ),
 218     mnHeight( nHeight )
 219 {
 220     const long  nWidthAl = ( nWidth >> 2 ) + 1;
 221     const long  nSize = nWidthAl * nHeight;
 222     Scanline    pTmp = mpBuf = static_cast<Scanline>(rtl_allocateMemory( nSize ));
 223
 224     memset( mpBuf, 0, nSize );
 225     mpScan = static_cast<Scanline*>(rtl_allocateMemory( nHeight * sizeof( Scanline ) ));
 226
 227     for( long nY = 0; nY < nHeight; pTmp += nWidthAl )
 228         mpScan[ nY++ ] = pTmp;
 229 }
 230
 231 ImplVectMap::~ImplVectMap()
 232 {
 233     rtl_freeMemory( mpBuf );
 234     rtl_freeMemory( mpScan );
 235 }
 236
 237 inline void ImplVectMap::Set( long nY, long nX, sal_uInt8 cVal )
 238 {
 239     const sal_uInt8 cShift = sal::static_int_cast<sal_uInt8>(6 - ( ( nX & 3 ) << 1 ));
 240     ( ( mpScan[ nY ][ nX >> 2 ] ) &= ~( 3 << cShift ) ) |= ( cVal << cShift );
 241 }
 242
 243 inline sal_uInt8    ImplVectMap::Get( long nY, long nX ) const
 244 {
 245     return sal::static_int_cast<sal_uInt8>( ( ( mpScan[ nY ][ nX >> 2 ] ) >> ( 6 - ( ( nX & 3 ) << 1 ) ) ) & 3 );
 246 }
 247
 248 inline bool ImplVectMap::IsFree( long nY, long nX ) const
 249 {
 250     return( VECT_FREE_INDEX == Get( nY, nX ) );
 251 }
 252
 253 inline bool ImplVectMap::IsCont( long nY, long nX ) const
 254 {
 255     return( VECT_CONT_INDEX == Get( nY, nX ) );
 256 }
 257
 258 inline bool ImplVectMap::IsDone( long nY, long nX ) const
 259 {
 260     return( VECT_DONE_INDEX == Get( nY, nX ) );
 261 }
 262
 263 class ImplChain
 264 {
 265 private:
 266
 267     tools::Polygon  maPoly;
 268     Point           maStartPt;
 269     sal_uLong       mnArraySize;
 270     sal_uLong       mnCount;
 271     std::unique_ptr<sal_uInt8[]>
 272                     mpCodes;
 273
 274     void            ImplGetSpace();
 275
 276     void            ImplPostProcess( const ImplPointArray& rArr );
 277
 278     ImplChain(const ImplChain&) = delete;
 279     ImplChain& operator=(const ImplChain&) = delete;
 280
 281 public:
 282
 283                     ImplChain();
 284
 285     void            ImplBeginAdd( const Point& rStartPt );
 286     inline void     ImplAdd( sal_uInt8 nCode );
 287     void            ImplEndAdd( sal_uLong nTypeFlag );
 288
 289     const tools::Polygon& ImplGetPoly() const { return maPoly; }
 290 };
 291
 292 ImplChain::ImplChain() :
 293     mnArraySize ( 1024UL ),
 294     mnCount     ( 0UL )
 295 {
 296     mpCodes.reset( new sal_uInt8[ mnArraySize ] );
 297 }
 298
 299 void ImplChain::ImplGetSpace()
 300 {
 301     const sal_uLong nOldArraySize = mnArraySize;
 302     sal_uInt8*      pNewCodes;
 303
 304     mnArraySize = mnArraySize << 1UL;
 305     pNewCodes = new sal_uInt8[ mnArraySize ];
 306     memcpy( pNewCodes, mpCodes.get(), nOldArraySize );
 307     mpCodes.reset( pNewCodes );
 308 }
 309
 310 void ImplChain::ImplBeginAdd( const Point& rStartPt )
 311 {
 312     maPoly = tools::Polygon();
 313     maStartPt = rStartPt;
 314     mnCount = 0UL;
 315 }
 316
 317 inline void ImplChain::ImplAdd( sal_uInt8 nCode )
 318 {
 319     if( mnCount == mnArraySize )
 320         ImplGetSpace();
 321
 322     mpCodes[ mnCount++ ] = nCode;
 323 }
 324
 325 void ImplChain::ImplEndAdd( sal_uLong nFlag )
 326 {
 327     if( mnCount )
 328     {
 329         ImplPointArray aArr;
 330
 331         if( nFlag & VECT_POLY_INLINE_INNER )
 332         {
 333             long nFirstX, nFirstY;
 334             long nLastX, nLastY;
 335
 336             nFirstX = nLastX = maStartPt.X();
 337             nFirstY = nLastY = maStartPt.Y();
 338             aArr.ImplSetSize( mnCount << 1 );
 339
 340             sal_uInt16 i, nPolyPos;
 341             for( i = 0, nPolyPos = 0; i < ( mnCount - 1 ); i++ )
 342             {
 343                 const sal_uInt8             cMove = mpCodes[ i ];
 344                 const sal_uInt8             cNextMove = mpCodes[ i + 1 ];
 345                 const ChainMove&        rMove = aImplMove[ cMove ];
 346                 const ChainMove&        rMoveInner = aImplMoveInner[ cMove ];
 347 //              Point&                  rPt = aArr[ nPolyPos ];
 348                 bool                    bDone = true;
 349
 350                 nLastX += rMove.nDX;
 351                 nLastY += rMove.nDY;
 352
 353                 if( cMove < 4 )
 354                 {
 355                     if( ( cMove == 0 && cNextMove == 3 ) ||
 356                         ( cMove == 3 && cNextMove == 2 ) ||
 357                         ( cMove == 2 && cNextMove == 1 ) ||
 358                         ( cMove == 1 && cNextMove == 0 ) )
 359                     {
 360                     }
 361                     else if( cMove == 2 && cNextMove == 3 )
 362                     {
 363                         aArr[ nPolyPos ].X() = nLastX;
 364                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 365
 366                         aArr[ nPolyPos ].X() = nLastX - 1;
 367                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 368
 369                         aArr[ nPolyPos ].X() = nLastX - 1;
 370                         aArr[ nPolyPos++ ].Y() = nLastY;
 371                     }
 372                     else if( cMove == 3 && cNextMove == 0 )
 373                     {
 374                         aArr[ nPolyPos ].X() = nLastX - 1;
 375                         aArr[ nPolyPos++ ].Y() = nLastY;
 376
 377                         aArr[ nPolyPos ].X() = nLastX - 1;
 378                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 379
 380                         aArr[ nPolyPos ].X() = nLastX;
 381                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 382                     }
 383                     else if( cMove == 0 && cNextMove == 1 )
 384                     {
 385                         aArr[ nPolyPos ].X() = nLastX;
 386                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 387
 388                         aArr[ nPolyPos ].X() = nLastX + 1;
 389                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 390
 391                         aArr[ nPolyPos ].X() = nLastX + 1;
 392                         aArr[ nPolyPos++ ].Y() = nLastY;
 393                     }
 394                     else if( cMove == 1 && cNextMove == 2 )
 395                     {
 396                         aArr[ nPolyPos ].X() = nLastX + 1;
 397                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 398
 399                         aArr[ nPolyPos ].X() = nLastX + 1;
 400                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 401
 402                         aArr[ nPolyPos ].X() = nLastX;
 403                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 404                     }
 405                     else
 406                         bDone = false;
 407                 }
 408                 else if( cMove == 7 && cNextMove == 0 )
 409                 {
 410                     aArr[ nPolyPos ].X() = nLastX - 1;
 411                     aArr[ nPolyPos++ ].Y() = nLastY;
 412
 413                     aArr[ nPolyPos ].X() = nLastX;
 414                     aArr[ nPolyPos++ ].Y() = nLastY + 1;
 415                 }
 416                 else if( cMove == 4 && cNextMove == 1 )
 417                 {
 418                     aArr[ nPolyPos ].X() = nLastX;
 419                     aArr[ nPolyPos++ ].Y() = nLastY + 1;
 420
 421                     aArr[ nPolyPos ].X() = nLastX + 1;
 422                     aArr[ nPolyPos++ ].Y() = nLastY;
 423                 }
 424                 else
 425                     bDone = false;
 426
 427                 if( !bDone )
 428                 {
 429                     aArr[ nPolyPos ].X() = nLastX + rMoveInner.nDX;
 430                     aArr[ nPolyPos++ ].Y() = nLastY + rMoveInner.nDY;
 431                 }
 432             }
 433
 434             aArr[ nPolyPos ].X() = nFirstX + 1;
 435             aArr[ nPolyPos++ ].Y() = nFirstY + 1;
 436             aArr.ImplSetRealSize( nPolyPos );
 437         }
 438         else if( nFlag & VECT_POLY_INLINE_OUTER )
 439         {
 440             long nFirstX, nFirstY;
 441             long nLastX, nLastY;
 442
 443             nFirstX = nLastX = maStartPt.X();
 444             nFirstY = nLastY = maStartPt.Y();
 445             aArr.ImplSetSize( mnCount << 1 );
 446
 447             sal_uInt16 i, nPolyPos;
 448             for( i = 0, nPolyPos = 0; i < ( mnCount - 1 ); i++ )
 449             {
 450                 const sal_uInt8             cMove = mpCodes[ i ];
 451                 const sal_uInt8             cNextMove = mpCodes[ i + 1 ];
 452                 const ChainMove&        rMove = aImplMove[ cMove ];
 453                 const ChainMove&        rMoveOuter = aImplMoveOuter[ cMove ];
 454 //              Point&                  rPt = aArr[ nPolyPos ];
 455                 bool                    bDone = true;
 456
 457                 nLastX += rMove.nDX;
 458                 nLastY += rMove.nDY;
 459
 460                 if( cMove < 4 )
 461                 {
 462                     if( ( cMove == 0 && cNextMove == 1 ) ||
 463                         ( cMove == 1 && cNextMove == 2 ) ||
 464                         ( cMove == 2 && cNextMove == 3 ) ||
 465                         ( cMove == 3 && cNextMove == 0 ) )
 466                     {
 467                     }
 468                     else if( cMove == 0 && cNextMove == 3 )
 469                     {
 470                         aArr[ nPolyPos ].X() = nLastX;
 471                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 472
 473                         aArr[ nPolyPos ].X() = nLastX + 1;
 474                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 475
 476                         aArr[ nPolyPos ].X() = nLastX + 1;
 477                         aArr[ nPolyPos++ ].Y() = nLastY;
 478                     }
 479                     else if( cMove == 3 && cNextMove == 2 )
 480                     {
 481                         aArr[ nPolyPos ].X() = nLastX + 1;
 482                         aArr[ nPolyPos++ ].Y() = nLastY;
 483
 484                         aArr[ nPolyPos ].X() = nLastX + 1;
 485                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 486
 487                         aArr[ nPolyPos ].X() = nLastX;
 488                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 489                     }
 490                     else if( cMove == 2 && cNextMove == 1 )
 491                     {
 492                         aArr[ nPolyPos ].X() = nLastX;
 493                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 494
 495                         aArr[ nPolyPos ].X() = nLastX - 1;
 496                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 497
 498                         aArr[ nPolyPos ].X() = nLastX - 1;
 499                         aArr[ nPolyPos++ ].Y() = nLastY;
 500                     }
 501                     else if( cMove == 1 && cNextMove == 0 )
 502                     {
 503                         aArr[ nPolyPos ].X() = nLastX - 1;
 504                         aArr[ nPolyPos++ ].Y() = nLastY;
 505
 506                         aArr[ nPolyPos ].X() = nLastX - 1;
 507                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 508
 509                         aArr[ nPolyPos ].X() = nLastX;
 510                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 511                     }
 512                     else
 513                         bDone = false;
 514                 }
 515                 else if( cMove == 7 && cNextMove == 3 )
 516                 {
 517                     aArr[ nPolyPos ].X() = nLastX;
 518                     aArr[ nPolyPos++ ].Y() = nLastY - 1;
 519
 520                     aArr[ nPolyPos ].X() = nLastX + 1;
 521                     aArr[ nPolyPos++ ].Y() = nLastY;
 522                 }
 523                 else if( cMove == 6 && cNextMove == 2 )
 524                 {
 525                     aArr[ nPolyPos ].X() = nLastX + 1;
 526                     aArr[ nPolyPos++ ].Y() = nLastY;
 527
 528                     aArr[ nPolyPos ].X() = nLastX;
 529                     aArr[ nPolyPos++ ].Y() = nLastY + 1;
 530                 }
 531                 else
 532                     bDone = false;
 533
 534                 if( !bDone )
 535                 {
 536                     aArr[ nPolyPos ].X() = nLastX + rMoveOuter.nDX;
 537                     aArr[ nPolyPos++ ].Y() = nLastY + rMoveOuter.nDY;
 538                 }
 539             }
 540
 541             aArr[ nPolyPos ].X() = nFirstX - 1;
 542             aArr[ nPolyPos++ ].Y() = nFirstY - 1;
 543             aArr.ImplSetRealSize( nPolyPos );
 544         }
 545         else
 546         {
 547             long nLastX = maStartPt.X(), nLastY = maStartPt.Y();
 548
 549             aArr.ImplSetSize( mnCount + 1 );
 550             aArr[ 0 ] = Point( nLastX, nLastY );
 551
 552             for( sal_uLong i = 0; i < mnCount; )
 553             {
 554                 const ChainMove& rMove = aImplMove[ mpCodes[ i ] ];
 555                 aArr[ ++i ] = Point( nLastX += rMove.nDX, nLastY += rMove.nDY );
 556             }
 557
 558             aArr.ImplSetRealSize( mnCount + 1 );
 559         }
 560
 561         ImplPostProcess( aArr );
 562     }
 563     else
 564         maPoly.SetSize( 0 );
 565 }
 566
 567 void ImplChain::ImplPostProcess( const ImplPointArray& rArr )
 568 {
 569     ImplPointArray  aNewArr1;
 570     ImplPointArray  aNewArr2;
 571     Point*          pLast;
 572     Point*          pLeast;
 573     sal_uLong           nNewPos;
 574     sal_uLong           nCount = rArr.ImplGetRealSize();
 575     sal_uLong           n;
 576
 577     // pass 1
 578     aNewArr1.ImplSetSize( nCount );
 579     pLast = &( aNewArr1[ 0 ] );
 580     pLast->X() = BACK_MAP( rArr[ 0 ].X() );
 581     pLast->Y() = BACK_MAP( rArr[ 0 ].Y() );
 582
 583     for( n = nNewPos = 1; n < nCount; )
 584     {
 585         const Point& rPt = rArr[ n++ ];
 586         const long   nX = BACK_MAP( rPt.X() );
 587         const long   nY = BACK_MAP( rPt.Y() );
 588
 589         if( nX != pLast->X() || nY != pLast->Y() )
 590         {
 591             pLast = pLeast = &( aNewArr1[ nNewPos++ ] );
 592             pLeast->X() = nX;
 593             pLeast->Y() = nY;
 594         }
 595     }
 596
 597     aNewArr1.ImplSetRealSize( nCount = nNewPos );
 598
 599     // pass 2
 600     aNewArr2.ImplSetSize( nCount );
 601     pLast = &( aNewArr2[ 0 ] );
 602     *pLast = aNewArr1[ 0 ];
 603
 604     for( n = nNewPos = 1; n < nCount; )
 605     {
 606         pLeast = &( aNewArr1[ n++ ] );
 607
 608         if( pLeast->X() == pLast->X() )
 609         {
 610             while( n < nCount && aNewArr1[ n ].X() == pLast->X() )
 611                 pLeast = &( aNewArr1[ n++ ] );
 612         }
 613         else if( pLeast->Y() == pLast->Y() )
 614         {
 615             while( n < nCount && aNewArr1[ n ].Y() == pLast->Y() )
 616                 pLeast = &( aNewArr1[ n++ ] );
 617         }
 618
 619         aNewArr2[ nNewPos++ ] = *( pLast = pLeast );
 620     }
 621
 622     aNewArr2.ImplSetRealSize( nNewPos );
 623     aNewArr2.ImplCreatePoly( maPoly );
 624 }
 625
 626 namespace ImplVectorizer {
 627
 628 bool ImplVectorize( const Bitmap& rColorBmp, GDIMetaFile& rMtf,
 629                     sal_uInt8 cReduce, const Link<long,void>* pProgress )
 630 {
 631     bool bRet = false;
 632
 633     VECT_PROGRESS( pProgress, 0 );
 634
 635     std::unique_ptr<Bitmap> xBmp(new Bitmap( rColorBmp ));
 636     Bitmap::ScopedReadAccess pRAcc(*xBmp);
 637
 638     if( pRAcc )
 639     {
 640         tools::PolyPolygon         aPolyPoly;
 641         double              fPercent = 0.0;
 642         double              fPercentStep_2 = 0.0;
 643         const long          nWidth = pRAcc->Width();
 644         const long          nHeight = pRAcc->Height();
 645         const sal_uInt16        nColorCount = pRAcc->GetPaletteEntryCount();
 646         sal_uInt16              n;
 647         ImplColorSet*       pColorSet = reinterpret_cast<ImplColorSet*>(new sal_uInt8[ 256 * sizeof( ImplColorSet ) ]);
 648
 649         memset( pColorSet, 0, 256 * sizeof( ImplColorSet ) );
 650         rMtf.Clear();
 651
 652         // get used palette colors and sort them from light to dark colors
 653         for( n = 0; n < nColorCount; n++ )
 654         {
 655             pColorSet[ n ].mnIndex = n;
 656             pColorSet[ n ].maColor = pRAcc->GetPaletteColor( n );
 657         }
 658
 659         for( long nY = 0; nY < nHeight; nY++ )
 660             for( long nX = 0; nX < nWidth; nX++ )
 661                 pColorSet[ pRAcc->GetPixel( nY, nX ).GetIndex() ].mbSet = true;
 662
 663         qsort( pColorSet, 256, sizeof( ImplColorSet ), ImplColorSetCmpFnc );
 664
 665         for( n = 0; n < 256; n++ )
 666             if( !pColorSet[ n ].mbSet )
 667                 break;
 668
 669         if( n )
 670             fPercentStep_2 = 45.0 / n;
 671
 672         VECT_PROGRESS( pProgress, FRound( fPercent += 10.0 ) );
 673
 674         for( sal_uInt16 i = 0; i < n; i++ )
 675         {
 676             const BitmapColor   aBmpCol( pRAcc->GetPaletteColor( pColorSet[ i ].mnIndex ) );
 677             const Color         aFindColor( aBmpCol.GetRed(), aBmpCol.GetGreen(), aBmpCol.GetBlue() );
 678             std::unique_ptr<ImplVectMap> xMap(ImplExpand( pRAcc.get(), aFindColor ));
 679
 680             VECT_PROGRESS( pProgress, FRound( fPercent += fPercentStep_2 ) );
 681
 682             if( xMap )
 683             {
 684                 aPolyPoly.Clear();
 685                 ImplCalculate( xMap.get(), aPolyPoly, cReduce );
 686                 xMap.reset();
 687
 688                 if( aPolyPoly.Count() )
 689                 {
 690                     ImplLimitPolyPoly( aPolyPoly );
 691
 692                     aPolyPoly.Optimize( PolyOptimizeFlags::EDGES );
 693
 694                     if( aPolyPoly.Count() )
 695                     {
 696                         rMtf.AddAction( new MetaLineColorAction( aFindColor, true ) );
 697                         rMtf.AddAction( new MetaFillColorAction( aFindColor, true ) );
 698                         rMtf.AddAction( new MetaPolyPolygonAction( aPolyPoly ) );
 699                     }
 700                 }
 701             }
 702
 703             VECT_PROGRESS( pProgress, FRound( fPercent += fPercentStep_2 ) );
 704         }
 705
 706         delete[] reinterpret_cast<sal_uInt8*>(pColorSet);
 707
 708         if( rMtf.GetActionSize() )
 709         {
 710             MapMode         aMap( MapUnit::Map100thMM );
 711             ScopedVclPtrInstance< VirtualDevice > aVDev;
 712             const Size      aLogSize1( aVDev->PixelToLogic( Size( 1, 1 ), aMap ) );
 713
 714             rMtf.SetPrefMapMode( aMap );
 715             rMtf.SetPrefSize( Size( nWidth + 2, nHeight + 2 ) );
 716             rMtf.Move( 1, 1 );
 717             rMtf.Scale( aLogSize1.Width(), aLogSize1.Height() );
 718             bRet = true;
 719         }
 720     }
 721
 722     pRAcc.reset();
 723     xBmp.reset();
 724     VECT_PROGRESS( pProgress, 100 );
 725
 726     return bRet;
 727 }
 728
 729 void ImplLimitPolyPoly( tools::PolyPolygon& rPolyPoly )
 730 {
 731     if( rPolyPoly.Count() > VECT_POLY_MAX )
 732     {
 733         tools::PolyPolygon aNewPolyPoly;
 734         long        nReduce = 0;
 735         sal_uInt16      nNewCount;
 736
 737         do
 738         {
 739             aNewPolyPoly.Clear();
 740             nReduce++;
 741
 742             for( sal_uInt16 i = 0, nCount = rPolyPoly.Count(); i < nCount; i++ )
 743             {
 744                 const tools::Rectangle aBound( rPolyPoly[ i ].GetBoundRect() );
 745
 746                 if( aBound.GetWidth() > nReduce && aBound.GetHeight() > nReduce )
 747                 {
 748                     if( rPolyPoly[ i ].GetSize() )
 749                         aNewPolyPoly.Insert( rPolyPoly[ i ] );
 750                 }
 751             }
 752
 753             nNewCount = aNewPolyPoly.Count();
 754         }
 755         while( nNewCount > VECT_POLY_MAX );
 756
 757         rPolyPoly = aNewPolyPoly;
 758     }
 759 }
 760
 761 ImplVectMap* ImplExpand( BitmapReadAccess* pRAcc, const Color& rColor )
 762 {
 763     ImplVectMap* pMap = nullptr;
 764
 765     if( pRAcc && pRAcc->Width() && pRAcc->Height() )
 766     {
 767         const long          nOldWidth = pRAcc->Width();
 768         const long          nOldHeight = pRAcc->Height();
 769         const long          nNewWidth = ( nOldWidth << 2 ) + 4;
 770         const long          nNewHeight = ( nOldHeight << 2 ) + 4;
 771         const BitmapColor   aTest( pRAcc->GetBestMatchingColor( rColor ) );
 772         std::unique_ptr<long[]> pMapIn(new long[ std::max( nOldWidth, nOldHeight ) ]);
 773         std::unique_ptr<long[]> pMapOut(new long[ std::max( nOldWidth, nOldHeight ) ]);
 774         long                nX, nY, nTmpX, nTmpY;
 775
 776         pMap = new ImplVectMap( nNewWidth, nNewHeight );
 777
 778         for( nX = 0; nX < nOldWidth; nX++ )
 779             VECT_MAP( pMapIn, pMapOut, nX );
 780
 781         for( nY = 0, nTmpY = 5; nY < nOldHeight; nY++, nTmpY += 4 )
 782         {
 783             for( nX = 0; nX < nOldWidth; )
 784             {
 785                 if( pRAcc->GetPixel( nY, nX ) == aTest )
 786                 {
 787                     nTmpX = pMapIn[ nX++ ];
 788                     nTmpY -= 3;
 789
 790                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
 791                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
 792                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
 793                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
 794
 795                     while( nX < nOldWidth && pRAcc->GetPixel( nY, nX ) == aTest )
 796                          nX++;
 797
 798                     nTmpX = pMapOut[ nX - 1 ];
 799                     nTmpY -= 3;
 800
 801                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
 802                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
 803                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
 804                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
 805                 }
 806                 else
 807                     nX++;
 808             }
 809         }
 810
 811         for( nY = 0; nY < nOldHeight; nY++ )
 812             VECT_MAP( pMapIn, pMapOut, nY );
 813
 814         for( nX = 0, nTmpX = 5; nX < nOldWidth; nX++, nTmpX += 4 )
 815         {
 816             for( nY = 0; nY < nOldHeight; )
 817             {
 818                 if( pRAcc->GetPixel( nY, nX ) == aTest )
 819                 {
 820                     nTmpX -= 3;
 821                     nTmpY = pMapIn[ nY++ ];
 822
 823                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
 824                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
 825                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
 826                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
 827
 828                     while( nY < nOldHeight && pRAcc->GetPixel( nY, nX ) == aTest )
 829                         nY++;
 830
 831                     nTmpX -= 3;
 832                     nTmpY = pMapOut[ nY - 1 ];
 833
 834                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
 835                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
 836                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
 837                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
 838                 }
 839                 else
 840                     nY++;
 841             }
 842         }
 843     }
 844
 845     return pMap;
 846 }
 847
 848 void ImplCalculate( ImplVectMap* pMap, tools::PolyPolygon& rPolyPoly, sal_uInt8 cReduce )
 849 {
 850     const long nWidth = pMap->Width(), nHeight= pMap->Height();
 851
 852     for( long nY = 0; nY < nHeight; nY++ )
 853     {
 854         long    nX = 0;
 855         bool    bInner = true;
 856
 857         while( nX < nWidth )
 858         {
 859             // skip free
 860             while( ( nX < nWidth ) && pMap->IsFree( nY, nX ) )
 861                 nX++;
 862
 863             if( nX == nWidth )
 864                 break;
 865
 866             if( pMap->IsCont( nY, nX ) )
 867             {
 868                 // new contour
 869                 ImplChain   aChain;
 870                 const Point aStartPt( nX++, nY );
 871
 872                 // get chain code
 873                 aChain.ImplBeginAdd( aStartPt );
 874                 ImplGetChain( pMap, aStartPt, aChain );
 875
 876                 aChain.ImplEndAdd( bInner ? VECT_POLY_OUTLINE_INNER : VECT_POLY_OUTLINE_OUTER );
 877
 878                 const tools::Polygon& rPoly = aChain.ImplGetPoly();
 879
 880                 if( rPoly.GetSize() > 2 )
 881                 {
 882                     if( cReduce )
 883                     {
 884                         const tools::Rectangle aBound( rPoly.GetBoundRect() );
 885
 886                         if( aBound.GetWidth() > cReduce && aBound.GetHeight() > cReduce )
 887                             rPolyPoly.Insert( rPoly );
 888                     }
 889                     else
 890                         rPolyPoly.Insert( rPoly  );
 891                 }
 892
 893                 // skip rest of detected contour
 894                 while( pMap->IsCont( nY, nX ) )
 895                     nX++;
 896             }
 897             else
 898             {
 899                 // process done segment
 900                 const long nStartSegX = nX++;
 901
 902                 while( pMap->IsDone( nY, nX ) )
 903                     nX++;
 904
 905                 if( ( ( nX - nStartSegX ) == 1 ) || ( ImplIsUp( pMap, nY, nStartSegX ) != ImplIsUp( pMap, nY, nX - 1 ) ) )
 906                     bInner = !bInner;
 907             }
 908         }
 909     }
 910 }
 911
 912 bool ImplGetChain(  ImplVectMap* pMap, const Point& rStartPt, ImplChain& rChain )
 913 {
 914     long                nActX = rStartPt.X();
 915     long                nActY = rStartPt.Y();
 916     sal_uLong               nFound;
 917     sal_uLong               nLastDir = 0UL;
 918     sal_uLong               nDir;
 919
 920     do
 921     {
 922         nFound = 0UL;
 923
 924         // first try last direction
 925         long nTryX = nActX + aImplMove[ nLastDir ].nDX;
 926         long nTryY = nActY + aImplMove[ nLastDir ].nDY;
 927
 928         if( pMap->IsCont( nTryY, nTryX ) )
 929         {
 930             rChain.ImplAdd( (sal_uInt8) nLastDir );
 931             pMap->Set( nActY = nTryY, nActX = nTryX, VECT_DONE_INDEX );
 932             nFound = 1UL;
 933         }
 934         else
 935         {
 936             // try other directions
 937             for( nDir = 0UL; nDir < 8UL; nDir++ )
 938             {
 939                 // we already tried nLastDir
 940                 if( nDir != nLastDir )
 941                 {
 942                     nTryX = nActX + aImplMove[ nDir ].nDX;
 943                     nTryY = nActY + aImplMove[ nDir ].nDY;
 944
 945                     if( pMap->IsCont( nTryY, nTryX ) )
 946                     {
 947                         rChain.ImplAdd( (sal_uInt8) nDir );
 948                         pMap->Set( nActY = nTryY, nActX = nTryX, VECT_DONE_INDEX );
 949                         nFound = 1UL;
 950                         nLastDir = nDir;
 951                         break;
 952                     }
 953                 }
 954             }
 955         }
 956     }
 957     while( nFound );
 958
 959     return true;
 960 }
 961
 962 bool ImplIsUp( ImplVectMap* pMap, long nY, long nX )
 963 {
 964     if( pMap->IsDone( nY - 1, nX ) )
 965         return true;
 966     else if( pMap->IsDone( nY + 1, nX ) )
 967         return false;
 968     else if( pMap->IsDone( nY - 1, nX - 1 ) || pMap->IsDone( nY - 1, nX + 1 ) )
 969         return true;
 970     else
 971         return false;
 972 }
 973
 974 }
 975
 976 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */