vcl/source/gdi/impvect.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: impvect.cxx,v $
  10  * $Revision: 1.10 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_vcl.hxx"
  33
  34 #include <stdlib.h>
  35 #include <vcl/bmpacc.hxx>
  36 #include <tools/poly.hxx>
  37 #include <vcl/gdimtf.hxx>
  38 #include <vcl/metaact.hxx>
  39 #include <vcl/svapp.hxx>
  40 #include <vcl/wrkwin.hxx>
  41 #include <vcl/virdev.hxx>
  42 #ifndef _SV_VECTORIZ_HXX
  43 #include <impvect.hxx>
  44 #endif
  45
  46 // -----------
  47 // - Defines -
  48 // -----------
  49
  50 #define VECT_POLY_MAX 8192
  51
  52 // -----------------------------------------------------------------------------
  53
  54 #define VECT_FREE_INDEX 0
  55 #define VECT_CONT_INDEX 1
  56 #define VECT_DONE_INDEX 2
  57
  58 // -----------------------------------------------------------------------------
  59
  60 #define VECT_POLY_INLINE_INNER  1UL
  61 #define VECT_POLY_INLINE_OUTER  2UL
  62 #define VECT_POLY_OUTLINE_INNER 4UL
  63 #define VECT_POLY_OUTLINE_OUTER 8UL
  64
  65 // -----------------------------------------------------------------------------
  66
  67 #define VECT_MAP( _def_pIn, _def_pOut, _def_nVal )      _def_pOut[_def_nVal]=(_def_pIn[_def_nVal]=((_def_nVal)*4L)+1L)+5L;
  68 #define BACK_MAP( _def_nVal )                                           ((((_def_nVal)+2)>>2)-1)
  69 #define VECT_PROGRESS( _def_pProgress, _def_nVal )      if(_def_pProgress&&_def_pProgress->IsSet())(_def_pProgress->Call((void*)_def_nVal));
  70
  71 // -----------
  72 // - statics -
  73 // -----------
  74
  75 struct ChainMove { long nDX; long nDY; };
  76
  77 static ChainMove aImplMove[ 8 ] =       {
  78                                         { 1L, 0L },
  79                                         { 0L, -1L },
  80                                         { -1L, 0L },
  81                                         { 0L, 1L },
  82                                         { 1L, -1L },
  83                                         { -1, -1L },
  84                                         { -1L, 1L },
  85                                         { 1L, 1L }
  86                                     };
  87
  88 static ChainMove aImplMoveInner[ 8 ] =  {
  89                                             { 0L, 1L },
  90                                             { 1L, 0L },
  91                                             { 0L, -1L },
  92                                             { -1L, 0L },
  93                                             { 0L, 1L },
  94                                             { 1L, 0L },
  95                                             { 0L, -1L },
  96                                             { -1L, 0L }
  97                                         };
  98
  99 static ChainMove aImplMoveOuter[ 8 ] =  {
 100                                             { 0L, -1L },
 101                                             { -1L, 0L },
 102                                             { 0L, 1L },
 103                                             { 1L, 0L },
 104                                             { -1L, 0L },
 105                                             { 0L, 1L },
 106                                             { 1L, 0L },
 107                                             { 0L, -1L }
 108                                         };
 109
 110 // ----------------
 111 // - ImplColorSet -
 112 // ----------------
 113
 114 struct ImplColorSet
 115 {
 116     BitmapColor maColor;
 117     USHORT              mnIndex;
 118     BOOL                mbSet;
 119
 120     BOOL                operator<( const ImplColorSet& rSet ) const;
 121     BOOL                operator>( const ImplColorSet& rSet ) const;
 122 };
 123
 124 // ----------------------------------------------------------------------------
 125
 126 inline BOOL ImplColorSet::operator<( const ImplColorSet& rSet ) const
 127 {
 128     return( mbSet && ( !rSet.mbSet || ( maColor.GetLuminance() > rSet.maColor.GetLuminance() ) ) );
 129 }
 130
 131 // ----------------------------------------------------------------------------
 132
 133 inline BOOL ImplColorSet::operator>( const ImplColorSet& rSet ) const
 134 {
 135     return( !mbSet || ( rSet.mbSet && maColor.GetLuminance() < rSet.maColor.GetLuminance() ) );
 136 }
 137
 138 // ----------------------------------------------------------------------------
 139
 140 extern "C" int __LOADONCALLAPI ImplColorSetCmpFnc( const void* p1, const void* p2 )
 141 {
 142     ImplColorSet*       pSet1 = (ImplColorSet*) p1;
 143     ImplColorSet*       pSet2 = (ImplColorSet*) p2;
 144     int                         nRet;
 145
 146     if( pSet1->mbSet && pSet2->mbSet )
 147     {
 148         const BYTE cLum1 = pSet1->maColor.GetLuminance();
 149         const BYTE cLum2 = pSet2->maColor.GetLuminance();
 150         nRet = ( ( cLum1 > cLum2 ) ? -1 : ( ( cLum1 == cLum2 ) ? 0 : 1 ) );
 151     }
 152     else if( pSet1->mbSet )
 153         nRet = -1;
 154     else if( pSet2->mbSet )
 155         nRet = 1;
 156     else
 157         nRet = 0;
 158
 159     return nRet;
 160 }
 161
 162 // ------------------
 163 // - ImplPointArray -
 164 // ------------------
 165
 166 class ImplPointArray
 167 {
 168     Point*                              mpArray;
 169     ULONG                               mnSize;
 170     ULONG                               mnRealSize;
 171
 172 public:
 173
 174                         ImplPointArray();
 175                         ~ImplPointArray();
 176
 177     void                                ImplSetSize( ULONG nSize );
 178
 179     ULONG                               ImplGetRealSize() const { return mnRealSize; }
 180     void                                ImplSetRealSize( ULONG nRealSize ) { mnRealSize = nRealSize; }
 181
 182     inline Point&               operator[]( ULONG nPos );
 183     inline const Point& operator[]( ULONG nPos ) const;
 184
 185     void                                ImplCreatePoly( Polygon& rPoly ) const;
 186 };
 187
 188 // -----------------------------------------------------------------------------
 189
 190 ImplPointArray::ImplPointArray() :
 191     mpArray             ( NULL ),
 192     mnSize              ( 0UL ),
 193     mnRealSize  ( 0UL )
 194
 195 {
 196 }
 197
 198 // -----------------------------------------------------------------------------
 199
 200 ImplPointArray::~ImplPointArray()
 201 {
 202     if( mpArray )
 203         rtl_freeMemory( mpArray );
 204 }
 205
 206 // -----------------------------------------------------------------------------
 207
 208 void ImplPointArray::ImplSetSize( ULONG nSize )
 209 {
 210     const ULONG nTotal = nSize * sizeof( Point );
 211
 212     mnSize = nSize;
 213     mnRealSize = 0UL;
 214
 215     if( mpArray )
 216         rtl_freeMemory( mpArray );
 217
 218     mpArray = (Point*) rtl_allocateMemory( nTotal );
 219     memset( (HPBYTE) mpArray, 0, nTotal );
 220 }
 221
 222 // -----------------------------------------------------------------------------
 223
 224 inline Point& ImplPointArray::operator[]( ULONG nPos )
 225 {
 226     DBG_ASSERT( nPos < mnSize, "ImplPointArray::operator[]: nPos out of range!" );
 227     return mpArray[ nPos ];
 228 }
 229
 230 // -----------------------------------------------------------------------------
 231
 232 inline const Point& ImplPointArray::operator[]( ULONG nPos ) const
 233 {
 234     DBG_ASSERT( nPos < mnSize, "ImplPointArray::operator[]: nPos out of range!" );
 235     return mpArray[ nPos ];
 236 }
 237
 238 // -----------------------------------------------------------------------------
 239
 240 void ImplPointArray::ImplCreatePoly( Polygon& rPoly ) const
 241 {
 242     rPoly = Polygon( sal::static_int_cast<USHORT>(mnRealSize), mpArray );
 243 }
 244
 245 // ---------------
 246 // - ImplVectMap -
 247 // ---------------
 248
 249 class ImplVectMap
 250 {
 251 private:
 252
 253     Scanline            mpBuf;
 254     Scanline*           mpScan;
 255     long                        mnWidth;
 256     long                        mnHeight;
 257
 258                     ImplVectMap() {};
 259
 260 public:
 261
 262                     ImplVectMap( long nWidth, long nHeight );
 263                     ~ImplVectMap();
 264
 265     inline long         Width() const { return mnWidth; }
 266     inline long         Height() const { return mnHeight; }
 267
 268     inline void         Set( long nY, long nX, BYTE cVal );
 269     inline BYTE         Get( long nY, long nX ) const;
 270
 271     inline BOOL         IsFree( long nY, long nX ) const;
 272     inline BOOL         IsCont( long nY, long nX ) const;
 273     inline BOOL         IsDone( long nY, long nX ) const;
 274
 275 };
 276
 277 // -----------------------------------------------------------------------------
 278
 279 ImplVectMap::ImplVectMap( long nWidth, long nHeight ) :
 280     mnWidth     ( nWidth ),
 281     mnHeight( nHeight )
 282 {
 283     const long  nWidthAl = ( nWidth >> 2L ) + 1L;
 284     const long  nSize = nWidthAl * nHeight;
 285     Scanline    pTmp = mpBuf = (Scanline) rtl_allocateMemory( nSize );
 286
 287     memset( mpBuf, 0, nSize );
 288     mpScan = (Scanline*) rtl_allocateMemory( nHeight * sizeof( Scanline ) );
 289
 290     for( long nY = 0L; nY < nHeight; pTmp += nWidthAl )
 291         mpScan[ nY++ ] = pTmp;
 292 }
 293
 294 // -----------------------------------------------------------------------------
 295
 296
 297 ImplVectMap::~ImplVectMap()
 298 {
 299     rtl_freeMemory( mpBuf );
 300     rtl_freeMemory( mpScan );
 301 }
 302
 303 // -----------------------------------------------------------------------------
 304
 305 inline void     ImplVectMap::Set( long nY, long nX, BYTE cVal )
 306 {
 307     const BYTE cShift = sal::static_int_cast<BYTE>(6 - ( ( nX & 3 ) << 1 ));
 308     ( ( mpScan[ nY ][ nX >> 2 ] ) &= ~( 3 << cShift ) ) |= ( cVal << cShift );
 309 }
 310
 311 // -----------------------------------------------------------------------------
 312
 313 inline BYTE     ImplVectMap::Get( long nY, long nX ) const
 314 {
 315     return sal::static_int_cast<BYTE>( ( ( mpScan[ nY ][ nX >> 2 ] ) >> ( 6 - ( ( nX & 3 ) << 1 ) ) ) & 3 );
 316 }
 317
 318 // -----------------------------------------------------------------------------
 319
 320 inline BOOL ImplVectMap::IsFree( long nY, long nX ) const
 321 {
 322     return( VECT_FREE_INDEX == Get( nY, nX ) );
 323 }
 324
 325 // -----------------------------------------------------------------------------
 326
 327 inline BOOL ImplVectMap::IsCont( long nY, long nX ) const
 328 {
 329     return( VECT_CONT_INDEX == Get( nY, nX ) );
 330 }
 331
 332 // -----------------------------------------------------------------------------
 333
 334 inline BOOL ImplVectMap::IsDone( long nY, long nX ) const
 335 {
 336     return( VECT_DONE_INDEX == Get( nY, nX ) );
 337 }
 338
 339 // -------------
 340 // - ImplChain -
 341 // -------------
 342
 343 class ImplChain
 344 {
 345 private:
 346
 347     Polygon                     maPoly;
 348     Point                       maStartPt;
 349     ULONG                       mnArraySize;
 350     ULONG                       mnCount;
 351     long                        mnResize;
 352     BYTE*                       mpCodes;
 353
 354     void                        ImplGetSpace();
 355
 356     void                        ImplCreate();
 357     void                        ImplCreateInner();
 358     void                        ImplCreateOuter();
 359     void                        ImplPostProcess( const ImplPointArray& rArr );
 360
 361 public:
 362
 363                     ImplChain( ULONG nInitCount = 1024UL, long nResize = -1L );
 364                     ~ImplChain();
 365
 366     void                        ImplBeginAdd( const Point& rStartPt );
 367     inline void         ImplAdd( BYTE nCode );
 368     void                        ImplEndAdd( ULONG nTypeFlag );
 369
 370     const Polygon&      ImplGetPoly() { return maPoly; }
 371 };
 372
 373 // -----------------------------------------------------------------------------
 374
 375 ImplChain::ImplChain( ULONG nInitCount, long nResize ) :
 376     mnArraySize ( nInitCount ),
 377     mnCount             ( 0UL ),
 378     mnResize    ( nResize )
 379 {
 380     DBG_ASSERT( nInitCount && nResize, "ImplChain::ImplChain(): invalid parameters!" );
 381     mpCodes = new BYTE[ mnArraySize ];
 382 }
 383
 384 // -----------------------------------------------------------------------------
 385
 386 ImplChain::~ImplChain()
 387 {
 388     delete[] mpCodes;
 389 }
 390
 391 // -----------------------------------------------------------------------------
 392
 393 void ImplChain::ImplGetSpace()
 394 {
 395     const ULONG nOldArraySize = mnArraySize;
 396     BYTE*               pNewCodes;
 397
 398     mnArraySize = ( mnResize < 0L ) ? ( mnArraySize << 1UL ) : ( mnArraySize + (ULONG) mnResize );
 399     pNewCodes = new BYTE[ mnArraySize ];
 400     memcpy( pNewCodes, mpCodes, nOldArraySize );
 401     delete[] mpCodes;
 402     mpCodes = pNewCodes;
 403 }
 404
 405 // -----------------------------------------------------------------------------
 406
 407 void ImplChain::ImplBeginAdd( const Point& rStartPt )
 408 {
 409     maPoly = Polygon();
 410     maStartPt = rStartPt;
 411     mnCount = 0UL;
 412 }
 413
 414 // -----------------------------------------------------------------------------
 415
 416 inline void     ImplChain::ImplAdd( BYTE nCode )
 417 {
 418     if( mnCount == mnArraySize )
 419         ImplGetSpace();
 420
 421     mpCodes[ mnCount++ ] = nCode;
 422 }
 423
 424 // -----------------------------------------------------------------------------
 425
 426 void ImplChain::ImplEndAdd( ULONG nFlag )
 427 {
 428     if( mnCount )
 429     {
 430         ImplPointArray aArr;
 431
 432         if( nFlag & VECT_POLY_INLINE_INNER )
 433         {
 434             long nFirstX, nFirstY;
 435             long nLastX, nLastY;
 436
 437             nFirstX = nLastX = maStartPt.X();
 438             nFirstY = nLastY = maStartPt.Y();
 439             aArr.ImplSetSize( mnCount << 1 );
 440
 441             USHORT i, nPolyPos;
 442             for( i = 0, nPolyPos = 0; i < ( mnCount - 1 ); i++ )
 443             {
 444                 const BYTE                              cMove = mpCodes[ i ];
 445                 const BYTE                              cNextMove = mpCodes[ i + 1 ];
 446                 const ChainMove&                rMove = aImplMove[ cMove ];
 447                 const ChainMove&                rMoveInner = aImplMoveInner[ cMove ];
 448 //                              Point&                                  rPt = aArr[ nPolyPos ];
 449                 BOOL                                    bDone = TRUE;
 450
 451                 nLastX += rMove.nDX;
 452                 nLastY += rMove.nDY;
 453
 454                 if( cMove < 4 )
 455                 {
 456                     if( ( cMove == 0 && cNextMove == 3 ) ||
 457                         ( cMove == 3 && cNextMove == 2 ) ||
 458                         ( cMove == 2 && cNextMove == 1 ) ||
 459                         ( cMove == 1 && cNextMove == 0 ) )
 460                     {
 461                     }
 462                     else if( cMove == 2 && cNextMove == 3 )
 463                     {
 464                         aArr[ nPolyPos ].X() = nLastX;
 465                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 466
 467                         aArr[ nPolyPos ].X() = nLastX - 1;
 468                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 469
 470                         aArr[ nPolyPos ].X() = nLastX - 1;
 471                         aArr[ nPolyPos++ ].Y() = nLastY;
 472                     }
 473                     else if( cMove == 3 && cNextMove == 0 )
 474                     {
 475                         aArr[ nPolyPos ].X() = nLastX - 1;
 476                         aArr[ nPolyPos++ ].Y() = nLastY;
 477
 478                         aArr[ nPolyPos ].X() = nLastX - 1;
 479                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 480
 481                         aArr[ nPolyPos ].X() = nLastX;
 482                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 483                     }
 484                     else if( cMove == 0 && cNextMove == 1 )
 485                     {
 486                         aArr[ nPolyPos ].X() = nLastX;
 487                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 488
 489                         aArr[ nPolyPos ].X() = nLastX + 1;
 490                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 491
 492                         aArr[ nPolyPos ].X() = nLastX + 1;
 493                         aArr[ nPolyPos++ ].Y() = nLastY;
 494                     }
 495                     else if( cMove == 1 && cNextMove == 2 )
 496                     {
 497                         aArr[ nPolyPos ].X() = nLastX + 1;
 498                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 499
 500                         aArr[ nPolyPos ].X() = nLastX + 1;
 501                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 502
 503                         aArr[ nPolyPos ].X() = nLastX;
 504                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 505                     }
 506                     else
 507                         bDone = FALSE;
 508                 }
 509                 else if( cMove == 7 && cNextMove == 0 )
 510                 {
 511                     aArr[ nPolyPos ].X() = nLastX - 1;
 512                     aArr[ nPolyPos++ ].Y() = nLastY;
 513
 514                     aArr[ nPolyPos ].X() = nLastX;
 515                     aArr[ nPolyPos++ ].Y() = nLastY + 1;
 516                 }
 517                 else if( cMove == 4 && cNextMove == 1 )
 518                 {
 519                     aArr[ nPolyPos ].X() = nLastX;
 520                     aArr[ nPolyPos++ ].Y() = nLastY + 1;
 521
 522                     aArr[ nPolyPos ].X() = nLastX + 1;
 523                     aArr[ nPolyPos++ ].Y() = nLastY;
 524                 }
 525                 else
 526                     bDone = FALSE;
 527
 528                 if( !bDone )
 529                 {
 530                     aArr[ nPolyPos ].X() = nLastX + rMoveInner.nDX;
 531                     aArr[ nPolyPos++ ].Y() = nLastY + rMoveInner.nDY;
 532                 }
 533             }
 534
 535             aArr[ nPolyPos ].X() = nFirstX + 1L;
 536             aArr[ nPolyPos++ ].Y() = nFirstY + 1L;
 537             aArr.ImplSetRealSize( nPolyPos );
 538         }
 539         else if( nFlag & VECT_POLY_INLINE_OUTER )
 540         {
 541             long nFirstX, nFirstY;
 542             long nLastX, nLastY;
 543
 544             nFirstX = nLastX = maStartPt.X();
 545             nFirstY = nLastY = maStartPt.Y();
 546             aArr.ImplSetSize( mnCount << 1 );
 547
 548             USHORT i, nPolyPos;
 549             for( i = 0, nPolyPos = 0; i < ( mnCount - 1 ); i++ )
 550             {
 551                 const BYTE                              cMove = mpCodes[ i ];
 552                 const BYTE                              cNextMove = mpCodes[ i + 1 ];
 553                 const ChainMove&                rMove = aImplMove[ cMove ];
 554                 const ChainMove&                rMoveOuter = aImplMoveOuter[ cMove ];
 555 //                              Point&                                  rPt = aArr[ nPolyPos ];
 556                 BOOL                                    bDone = TRUE;
 557
 558                 nLastX += rMove.nDX;
 559                 nLastY += rMove.nDY;
 560
 561                 if( cMove < 4 )
 562                 {
 563                     if( ( cMove == 0 && cNextMove == 1 ) ||
 564                         ( cMove == 1 && cNextMove == 2 ) ||
 565                         ( cMove == 2 && cNextMove == 3 ) ||
 566                         ( cMove == 3 && cNextMove == 0 ) )
 567                     {
 568                     }
 569                     else if( cMove == 0 && cNextMove == 3 )
 570                     {
 571                         aArr[ nPolyPos ].X() = nLastX;
 572                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 573
 574                         aArr[ nPolyPos ].X() = nLastX + 1;
 575                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 576
 577                         aArr[ nPolyPos ].X() = nLastX + 1;
 578                         aArr[ nPolyPos++ ].Y() = nLastY;
 579                     }
 580                     else if( cMove == 3 && cNextMove == 2 )
 581                     {
 582                         aArr[ nPolyPos ].X() = nLastX + 1;
 583                         aArr[ nPolyPos++ ].Y() = nLastY;
 584
 585                         aArr[ nPolyPos ].X() = nLastX + 1;
 586                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 587
 588                         aArr[ nPolyPos ].X() = nLastX;
 589                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 590                     }
 591                     else if( cMove == 2 && cNextMove == 1 )
 592                     {
 593                         aArr[ nPolyPos ].X() = nLastX;
 594                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 595
 596                         aArr[ nPolyPos ].X() = nLastX - 1;
 597                         aArr[ nPolyPos++ ].Y() = nLastY + 1;
 598
 599                         aArr[ nPolyPos ].X() = nLastX - 1;
 600                         aArr[ nPolyPos++ ].Y() = nLastY;
 601                     }
 602                     else if( cMove == 1 && cNextMove == 0 )
 603                     {
 604                         aArr[ nPolyPos ].X() = nLastX - 1;
 605                         aArr[ nPolyPos++ ].Y() = nLastY;
 606
 607                         aArr[ nPolyPos ].X() = nLastX - 1;
 608                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 609
 610                         aArr[ nPolyPos ].X() = nLastX;
 611                         aArr[ nPolyPos++ ].Y() = nLastY - 1;
 612                     }
 613                     else
 614                         bDone = FALSE;
 615                 }
 616                 else if( cMove == 7 && cNextMove == 3 )
 617                 {
 618                     aArr[ nPolyPos ].X() = nLastX;
 619                     aArr[ nPolyPos++ ].Y() = nLastY - 1;
 620
 621                     aArr[ nPolyPos ].X() = nLastX + 1;
 622                     aArr[ nPolyPos++ ].Y() = nLastY;
 623                 }
 624                 else if( cMove == 6 && cNextMove == 2 )
 625                 {
 626                     aArr[ nPolyPos ].X() = nLastX + 1;
 627                     aArr[ nPolyPos++ ].Y() = nLastY;
 628
 629                     aArr[ nPolyPos ].X() = nLastX;
 630                     aArr[ nPolyPos++ ].Y() = nLastY + 1;
 631                 }
 632                 else
 633                     bDone = FALSE;
 634
 635                 if( !bDone )
 636                 {
 637                     aArr[ nPolyPos ].X() = nLastX + rMoveOuter.nDX;
 638                     aArr[ nPolyPos++ ].Y() = nLastY + rMoveOuter.nDY;
 639                 }
 640             }
 641
 642             aArr[ nPolyPos ].X() = nFirstX - 1L;
 643             aArr[ nPolyPos++ ].Y() = nFirstY - 1L;
 644             aArr.ImplSetRealSize( nPolyPos );
 645         }
 646         else
 647         {
 648             long nLastX = maStartPt.X(), nLastY = maStartPt.Y();
 649
 650             aArr.ImplSetSize( mnCount + 1 );
 651             aArr[ 0 ] = Point( nLastX, nLastY );
 652
 653             for( ULONG i = 0; i < mnCount; )
 654             {
 655                 const ChainMove& rMove = aImplMove[ mpCodes[ i ] ];
 656                 aArr[ ++i ] = Point( nLastX += rMove.nDX, nLastY += rMove.nDY );
 657             }
 658
 659             aArr.ImplSetRealSize( mnCount + 1 );
 660         }
 661
 662         ImplPostProcess( aArr );
 663     }
 664     else
 665         maPoly.SetSize( 0 );
 666 }
 667
 668 // -----------------------------------------------------------------------------
 669
 670 void ImplChain::ImplPostProcess( const ImplPointArray& rArr )
 671 {
 672     ImplPointArray      aNewArr1;
 673     ImplPointArray      aNewArr2;
 674     Point*                      pLast;
 675     Point*                      pLeast;
 676     ULONG                       nNewPos;
 677     ULONG                       nCount = rArr.ImplGetRealSize();
 678     ULONG                       n;
 679
 680     // pass 1
 681     aNewArr1.ImplSetSize( nCount );
 682     pLast = &( aNewArr1[ 0 ] );
 683     pLast->X() = BACK_MAP( rArr[ 0 ].X() );
 684     pLast->Y() = BACK_MAP( rArr[ 0 ].Y() );
 685
 686     for( n = nNewPos = 1; n < nCount; )
 687     {
 688         const Point& rPt = rArr[ n++ ];
 689         const long       nX = BACK_MAP( rPt.X() );
 690         const long       nY = BACK_MAP( rPt.Y() );
 691
 692         if( nX != pLast->X() || nY != pLast->Y() )
 693         {
 694             pLast = pLeast = &( aNewArr1[ nNewPos++ ] );
 695             pLeast->X() = nX;
 696             pLeast->Y() = nY;
 697         }
 698     }
 699
 700     aNewArr1.ImplSetRealSize( nCount = nNewPos );
 701
 702     // pass 2
 703     aNewArr2.ImplSetSize( nCount );
 704     pLast = &( aNewArr2[ 0 ] );
 705     *pLast = aNewArr1[ 0 ];
 706
 707     for( n = nNewPos = 1; n < nCount; )
 708     {
 709         pLeast = &( aNewArr1[ n++ ] );
 710
 711         if( pLeast->X() == pLast->X() )
 712         {
 713             while( n < nCount && aNewArr1[ n ].X() == pLast->X() )
 714                 pLeast = &( aNewArr1[ n++ ] );
 715         }
 716         else if( pLeast->Y() == pLast->Y() )
 717         {
 718             while( n < nCount && aNewArr1[ n ].Y() == pLast->Y() )
 719                 pLeast = &( aNewArr1[ n++ ] );
 720         }
 721
 722         aNewArr2[ nNewPos++ ] = *( pLast = pLeast );
 723     }
 724
 725     aNewArr2.ImplSetRealSize( nNewPos );
 726     aNewArr2.ImplCreatePoly( maPoly );
 727 }
 728
 729 // ------------------
 730 // - ImplVectorizer -
 731 // ------------------
 732
 733 ImplVectorizer::ImplVectorizer()
 734 {
 735 }
 736
 737 // -----------------------------------------------------------------------------
 738
 739 ImplVectorizer::~ImplVectorizer()
 740 {
 741 }
 742
 743 // -----------------------------------------------------------------------------
 744
 745 BOOL ImplVectorizer::ImplVectorize( const Bitmap& rColorBmp, GDIMetaFile& rMtf,
 746                                     BYTE cReduce, ULONG nFlags, const Link* pProgress )
 747 {
 748     BOOL bRet = FALSE;
 749
 750     VECT_PROGRESS( pProgress, 0 );
 751
 752     Bitmap*                             pBmp = new Bitmap( rColorBmp );
 753     BitmapReadAccess*   pRAcc = pBmp->AcquireReadAccess();
 754
 755     if( pRAcc )
 756     {
 757         PolyPolygon                     aPolyPoly;
 758         double                          fPercent = 0.0;
 759         double                          fPercentStep_2 = 0.0;
 760         const long                      nWidth = pRAcc->Width();
 761         const long                      nHeight = pRAcc->Height();
 762         const USHORT            nColorCount = pRAcc->GetPaletteEntryCount();
 763         USHORT                          n;
 764         ImplColorSet*           pColorSet = (ImplColorSet*) new BYTE[ 256 * sizeof( ImplColorSet ) ];
 765
 766         memset( pColorSet, 0, 256 * sizeof( ImplColorSet ) );
 767         rMtf.Clear();
 768
 769         // get used palette colors and sort them from light to dark colors
 770         for( n = 0; n < nColorCount; n++ )
 771         {
 772             pColorSet[ n ].mnIndex = n;
 773             pColorSet[ n ].maColor = pRAcc->GetPaletteColor( n );
 774         }
 775
 776         for( long nY = 0L; nY < nHeight; nY++ )
 777             for( long nX = 0L; nX < nWidth; nX++ )
 778                 pColorSet[ pRAcc->GetPixel( nY, nX ).GetIndex() ].mbSet = 1;
 779
 780         qsort( pColorSet, 256, sizeof( ImplColorSet ), ImplColorSetCmpFnc );
 781
 782         for( n = 0; n < 256; n++ )
 783             if( !pColorSet[ n ].mbSet )
 784                 break;
 785
 786         if( n )
 787             fPercentStep_2 = 45.0 / n;
 788
 789         VECT_PROGRESS( pProgress, FRound( fPercent += 10.0 ) );
 790
 791         for( USHORT i = 0; i < n; i++ )
 792         {
 793             const BitmapColor   aBmpCol( pRAcc->GetPaletteColor( pColorSet[ i ].mnIndex ) );
 794             const Color                 aFindColor( aBmpCol.GetRed(), aBmpCol.GetGreen(), aBmpCol.GetBlue() );
 795 //                      const BYTE                      cLum = aFindColor.GetLuminance();
 796             ImplVectMap*                pMap = ImplExpand( pRAcc, aFindColor );
 797
 798             VECT_PROGRESS( pProgress, FRound( fPercent += fPercentStep_2 ) );
 799
 800             if( pMap )
 801             {
 802                 aPolyPoly.Clear();
 803                 ImplCalculate( pMap, aPolyPoly, cReduce, nFlags );
 804                 delete pMap;
 805
 806                 if( aPolyPoly.Count() )
 807                 {
 808                     ImplLimitPolyPoly( aPolyPoly );
 809
 810                     if( nFlags & BMP_VECTORIZE_REDUCE_EDGES )
 811                         aPolyPoly.Optimize( POLY_OPTIMIZE_EDGES );
 812
 813                     if( aPolyPoly.Count() )
 814                     {
 815                         rMtf.AddAction( new MetaLineColorAction( aFindColor, TRUE ) );
 816                         rMtf.AddAction( new MetaFillColorAction( aFindColor, TRUE ) );
 817                         rMtf.AddAction( new MetaPolyPolygonAction( aPolyPoly ) );
 818                     }
 819                 }
 820             }
 821
 822             VECT_PROGRESS( pProgress, FRound( fPercent += fPercentStep_2 ) );
 823         }
 824
 825         delete[] (BYTE*) pColorSet;
 826
 827         if( rMtf.GetActionCount() )
 828         {
 829             MapMode                     aMap( MAP_100TH_MM );
 830             VirtualDevice       aVDev;
 831             const Size          aLogSize1( aVDev.PixelToLogic( Size( 1, 1 ), aMap ) );
 832
 833             rMtf.SetPrefMapMode( aMap );
 834             rMtf.SetPrefSize( Size( nWidth + 2, nHeight + 2 ) );
 835             rMtf.Move( 1, 1 );
 836             rMtf.Scale( aLogSize1.Width(), aLogSize1.Height() );
 837             bRet = TRUE;
 838         }
 839     }
 840
 841     pBmp->ReleaseAccess( pRAcc );
 842     delete pBmp;
 843     VECT_PROGRESS( pProgress, 100 );
 844
 845     return bRet;
 846 }
 847
 848 // -----------------------------------------------------------------------------
 849
 850 BOOL ImplVectorizer::ImplVectorize( const Bitmap& rMonoBmp,
 851                                     PolyPolygon& rPolyPoly,
 852                                     ULONG nFlags, const Link* pProgress )
 853 {
 854     Bitmap*                             pBmp = new Bitmap( rMonoBmp );
 855     BitmapReadAccess*   pRAcc;
 856     ImplVectMap*                pMap;
 857     BOOL                                bRet = FALSE;
 858
 859     VECT_PROGRESS( pProgress, 10 );
 860
 861     if( pBmp->GetBitCount() > 1 )
 862         pBmp->Convert( BMP_CONVERSION_1BIT_THRESHOLD );
 863
 864     VECT_PROGRESS( pProgress, 30 );
 865
 866     pRAcc = pBmp->AcquireReadAccess();
 867     pMap = ImplExpand( pRAcc, COL_BLACK );
 868     pBmp->ReleaseAccess( pRAcc );
 869     delete pBmp;
 870
 871     VECT_PROGRESS( pProgress, 60 );
 872
 873     if( pMap )
 874     {
 875         rPolyPoly.Clear();
 876         ImplCalculate( pMap, rPolyPoly, 0, nFlags );
 877         delete pMap;
 878         ImplLimitPolyPoly( rPolyPoly );
 879
 880         if( nFlags & BMP_VECTORIZE_REDUCE_EDGES )
 881             rPolyPoly.Optimize( POLY_OPTIMIZE_EDGES );
 882
 883         // #i14895#:setting the correct direction for polygons
 884         // that represent holes and non-holes; non-hole polygons
 885         // need to have a right orientation, holes need to have a
 886         // left orientation in order to be treated correctly by
 887         // several external tools like Flash viewers
 888         sal_Int32   nFirstPoly = -1;
 889         sal_uInt16  nCurPoly( 0 ), nCount( rPolyPoly.Count() );
 890
 891         for( ; nCurPoly < nCount; ++nCurPoly )
 892         {
 893             const Polygon&      rPoly = rPolyPoly.GetObject( nCurPoly );
 894             const sal_uInt16    nSize( rPoly.GetSize() );
 895             sal_uInt16                  nDepth( 0 ), i( 0 );
 896             const bool              bRight( rPoly.IsRightOrientated() );
 897
 898             for( ; i < nCount; ++i )
 899                 if( ( i != nCurPoly ) && rPolyPoly.GetObject( i ).IsInside( rPoly[ 0 ] ) )
 900                     ++nDepth;
 901
 902             const bool bHole( ( nDepth & 0x0001 ) == 1 );
 903
 904             if( nSize && ( ( !bRight && !bHole ) || ( bRight && bHole ) ) )
 905             {
 906                 Polygon     aNewPoly( nSize );
 907                 sal_uInt16  nPrim( 0 ), nSec( nSize - 1 );
 908
 909                 if( rPoly.HasFlags() )
 910                 {
 911                     while( nPrim < nSize )
 912                     {
 913                         aNewPoly.SetPoint( rPoly.GetPoint( nSec ), nPrim );
 914                         aNewPoly.SetFlags( nPrim++, rPoly.GetFlags( nSec-- ) );
 915                     }
 916                 }
 917                 else
 918                     while( nPrim < nSize )
 919                         aNewPoly.SetPoint( rPoly.GetPoint( nSec-- ), nPrim++ );
 920
 921                 rPolyPoly.Replace( aNewPoly, nCurPoly );
 922             }
 923
 924             if( ( 0 == nDepth ) && ( -1 == nFirstPoly ) )
 925                 nFirstPoly = nCurPoly;
 926         }
 927
 928         // put outmost polygon to the front
 929         if( nFirstPoly > 0 )
 930         {
 931             const Polygon aFirst( rPolyPoly.GetObject( static_cast< USHORT >( nFirstPoly ) ) );
 932
 933             rPolyPoly.Remove( static_cast< USHORT >( nFirstPoly ) );
 934             rPolyPoly.Insert( aFirst, 0 );
 935         }
 936
 937         bRet = TRUE;
 938     }
 939
 940     VECT_PROGRESS( pProgress, 100 );
 941
 942     return bRet;
 943 }
 944
 945 // -----------------------------------------------------------------------------
 946
 947 void ImplVectorizer::ImplLimitPolyPoly( PolyPolygon& rPolyPoly )
 948 {
 949     if( rPolyPoly.Count() > VECT_POLY_MAX )
 950     {
 951         PolyPolygon aNewPolyPoly;
 952         long            nReduce = 0;
 953         USHORT          nNewCount;
 954
 955         do
 956         {
 957             aNewPolyPoly.Clear();
 958             nReduce++;
 959
 960             for( USHORT i = 0, nCount = rPolyPoly.Count(); i < nCount; i++ )
 961             {
 962                 const Rectangle aBound( rPolyPoly[ i ].GetBoundRect() );
 963
 964                 if( aBound.GetWidth() > nReduce && aBound.GetHeight() > nReduce )
 965                 {
 966                     if( rPolyPoly[ i ].GetSize() )
 967                         aNewPolyPoly.Insert( rPolyPoly[ i ] );
 968                 }
 969             }
 970
 971             nNewCount = aNewPolyPoly.Count();
 972         }
 973         while( nNewCount > VECT_POLY_MAX );
 974
 975         rPolyPoly = aNewPolyPoly;
 976     }
 977 }
 978
 979 // -----------------------------------------------------------------------------
 980
 981 ImplVectMap* ImplVectorizer::ImplExpand( BitmapReadAccess* pRAcc, const Color& rColor )
 982 {
 983     ImplVectMap* pMap = NULL;
 984
 985        if( pRAcc && pRAcc->Width() && pRAcc->Height() )
 986     {
 987         const long                      nOldWidth = pRAcc->Width();
 988         const long                      nOldHeight = pRAcc->Height();
 989         const long                      nNewWidth = ( nOldWidth << 2L ) + 4L;
 990         const long                      nNewHeight = ( nOldHeight << 2L ) + 4L;
 991         const BitmapColor       aTest( pRAcc->GetBestMatchingColor( rColor ) );
 992         long*                           pMapIn = new long[ Max( nOldWidth, nOldHeight ) ];
 993         long*                           pMapOut = new long[ Max( nOldWidth, nOldHeight ) ];
 994         long                            nX, nY, nTmpX, nTmpY;
 995
 996         pMap = new ImplVectMap( nNewWidth, nNewHeight );
 997
 998         for( nX = 0L; nX < nOldWidth; nX++ )
 999             VECT_MAP( pMapIn, pMapOut, nX );
1000
1001         for( nY = 0L, nTmpY = 5L; nY < nOldHeight; nY++, nTmpY += 4L )
1002         {
1003             for( nX = 0L; nX < nOldWidth; )
1004             {
1005                 if( pRAcc->GetPixel( nY, nX ) == aTest )
1006                 {
1007                     nTmpX = pMapIn[ nX++ ];
1008                     nTmpY -= 3L;
1009
1010                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
1011                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
1012                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
1013                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
1014
1015                     while( nX < nOldWidth && pRAcc->GetPixel( nY, nX ) == aTest )
1016                          nX++;
1017
1018                     nTmpX = pMapOut[ nX - 1L ];
1019                     nTmpY -= 3L;
1020
1021                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
1022                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
1023                     pMap->Set( nTmpY++, nTmpX, VECT_CONT_INDEX );
1024                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
1025                 }
1026                 else
1027                     nX++;
1028             }
1029         }
1030
1031         for( nY = 0L; nY < nOldHeight; nY++ )
1032             VECT_MAP( pMapIn, pMapOut, nY );
1033
1034         for( nX = 0L, nTmpX = 5L; nX < nOldWidth; nX++, nTmpX += 4L )
1035         {
1036             for( nY = 0L; nY < nOldHeight; )
1037             {
1038                 if( pRAcc->GetPixel( nY, nX ) == aTest )
1039                 {
1040                     nTmpX -= 3L;
1041                     nTmpY = pMapIn[ nY++ ];
1042
1043                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
1044                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
1045                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
1046                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
1047
1048                     while( nY < nOldHeight && pRAcc->GetPixel( nY, nX ) == aTest )
1049                         nY++;
1050
1051                     nTmpX -= 3L;
1052                     nTmpY = pMapOut[ nY - 1L ];
1053
1054                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
1055                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
1056                     pMap->Set( nTmpY, nTmpX++, VECT_CONT_INDEX );
1057                     pMap->Set( nTmpY, nTmpX, VECT_CONT_INDEX );
1058                 }
1059                 else
1060                     nY++;
1061             }
1062         }
1063
1064         // cleanup
1065         delete[] pMapIn;
1066         delete[] pMapOut;
1067     }
1068
1069     return pMap;
1070 }
1071
1072 // -----------------------------------------------------------------------------
1073
1074 void ImplVectorizer::ImplCalculate( ImplVectMap* pMap, PolyPolygon& rPolyPoly, BYTE cReduce, ULONG nFlags )
1075 {
1076     const long nWidth = pMap->Width(), nHeight= pMap->Height();
1077
1078     for( long nY = 0L; nY < nHeight; nY++ )
1079     {
1080         long    nX = 0L;
1081         BOOL    bInner = TRUE;
1082
1083         while( nX < nWidth )
1084         {
1085             // skip free
1086             while( ( nX < nWidth ) && pMap->IsFree( nY, nX ) )
1087                 nX++;
1088
1089             if( nX == nWidth )
1090                 break;
1091
1092             if( pMap->IsCont( nY, nX ) )
1093             {
1094                 // new contour
1095                 ImplChain       aChain;
1096                 const Point     aStartPt( nX++, nY );
1097
1098                 // get chain code
1099                 aChain.ImplBeginAdd( aStartPt );
1100                 ImplGetChain( pMap, aStartPt, aChain );
1101
1102                 if( nFlags & BMP_VECTORIZE_INNER )
1103                     aChain.ImplEndAdd( bInner ? VECT_POLY_INLINE_INNER : VECT_POLY_INLINE_OUTER );
1104                 else
1105                     aChain.ImplEndAdd( bInner ? VECT_POLY_OUTLINE_INNER : VECT_POLY_OUTLINE_OUTER );
1106
1107                 const Polygon& rPoly = aChain.ImplGetPoly();
1108
1109                 if( rPoly.GetSize() > 2 )
1110                 {
1111                     if( cReduce )
1112                     {
1113                         const Rectangle aBound( rPoly.GetBoundRect() );
1114
1115                         if( aBound.GetWidth() > cReduce && aBound.GetHeight() > cReduce )
1116                             rPolyPoly.Insert( rPoly );
1117                     }
1118                     else
1119                         rPolyPoly.Insert( rPoly  );
1120                 }
1121
1122                 // skip rest of detected contour
1123                 while( pMap->IsCont( nY, nX ) )
1124                     nX++;
1125             }
1126             else
1127             {
1128                 // process done segment
1129                 const long nStartSegX = nX++;
1130
1131                 while( pMap->IsDone( nY, nX ) )
1132                     nX++;
1133
1134                 if( ( ( nX - nStartSegX ) == 1L ) || ( ImplIsUp( pMap, nY, nStartSegX ) != ImplIsUp( pMap, nY, nX - 1L ) ) )
1135                     bInner = !bInner;
1136             }
1137         }
1138     }
1139 }
1140
1141 // -----------------------------------------------------------------------------
1142
1143 BOOL ImplVectorizer::ImplGetChain(      ImplVectMap* pMap, const Point& rStartPt, ImplChain& rChain )
1144 {
1145     long                                nActX = rStartPt.X();
1146     long                                nActY = rStartPt.Y();
1147     long                                nTryX;
1148     long                                nTryY;
1149     ULONG                               nFound;
1150     ULONG                               nLastDir = 0UL;
1151     ULONG                               nDir;
1152
1153     do
1154     {
1155         nFound = 0UL;
1156
1157         // first try last direction
1158         nTryX = nActX + aImplMove[ nLastDir ].nDX;
1159         nTryY = nActY + aImplMove[ nLastDir ].nDY;
1160
1161         if( pMap->IsCont( nTryY, nTryX ) )
1162         {
1163             rChain.ImplAdd( (BYTE) nLastDir );
1164             pMap->Set( nActY = nTryY, nActX = nTryX, VECT_DONE_INDEX );
1165             nFound = 1UL;
1166         }
1167         else
1168         {
1169             // try other directions
1170             for( nDir = 0UL; nDir < 8UL; nDir++ )
1171             {
1172                 // we already tried nLastDir
1173                 if( nDir != nLastDir )
1174                 {
1175                     nTryX = nActX + aImplMove[ nDir ].nDX;
1176                     nTryY = nActY + aImplMove[ nDir ].nDY;
1177
1178                     if( pMap->IsCont( nTryY, nTryX ) )
1179                     {
1180                         rChain.ImplAdd( (BYTE) nDir );
1181                         pMap->Set( nActY = nTryY, nActX = nTryX, VECT_DONE_INDEX );
1182                         nFound = 1UL;
1183                         nLastDir = nDir;
1184                         break;
1185                     }
1186                 }
1187             }
1188         }
1189     }
1190     while( nFound );
1191
1192     return TRUE;
1193 }
1194
1195 // -----------------------------------------------------------------------------
1196
1197 BOOL ImplVectorizer::ImplIsUp( ImplVectMap* pMap, long nY, long nX ) const
1198 {
1199     if( pMap->IsDone( nY - 1L, nX ) )
1200         return TRUE;
1201     else if( pMap->IsDone( nY + 1L, nX ) )
1202         return FALSE;
1203     else if( pMap->IsDone( nY - 1L, nX - 1L ) || pMap->IsDone( nY - 1L, nX + 1L ) )
1204         return TRUE;
1205     else
1206         return FALSE;
1207 }