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