include/basebmp/clippedlinerenderer.hxx

   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 #ifndef INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX
  21 #define INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX
  22
  23 #include <basegfx/tools/rectcliptools.hxx>
  24 #include <basegfx/point/b2ipoint.hxx>
  25 #include <basegfx/range/b2ibox.hxx>
  26
  27 #include <vigra/diff2d.hxx>
  28 #include <vigra/iteratortraits.hxx>
  29
  30 namespace basebmp
  31 {
  32
  33 // factored-out bresenham setup code, which is used from two different
  34 // places in renderClippedLine() below. Admittedly messy for the long
  35 // parameter list...
  36 inline bool prepareClip( sal_Int32  a1,
  37                          sal_Int32  a2,
  38                          sal_Int32  b1,
  39                          sal_Int32  da,
  40                          sal_Int32  db,
  41                          sal_Int32& o_as,
  42                          sal_Int32& o_bs,
  43                          int        sa,
  44                          int        sb,
  45                          sal_Int32& io_rem,
  46                          int&       o_n,
  47                          sal_uInt32 clipCode1,
  48                          sal_uInt32 clipCount1,
  49                          sal_uInt32 clipCode2,
  50                          sal_uInt32 clipCount2,
  51                          sal_Int32  aMin,
  52                          sal_uInt32 aMinFlag,
  53                          sal_Int32  aMax,
  54                          sal_uInt32 aMaxFlag,
  55                          sal_Int32  bMin,
  56                          sal_uInt32 bMinFlag,
  57                          sal_Int32  bMax,
  58                          sal_uInt32 bMaxFlag,
  59                          bool       bRoundTowardsPt2,
  60                          bool&      o_bUseAlternateBresenham )
  61 {
  62     int ca(0), cb(0);
  63     if( clipCode1 )
  64     {
  65         if( clipCode1 & aMinFlag )
  66         {
  67             ca = 2*db*(aMin - a1);
  68             o_as = aMin;
  69         }
  70         else if( clipCode1 & aMaxFlag )
  71         {
  72             ca = 2*db*(a1 - aMax);
  73             o_as = aMax;
  74         }
  75
  76         if( clipCode1 & bMinFlag )
  77         {
  78             cb = 2*da*(bMin - b1);
  79             o_bs = bMin;
  80         }
  81         else if( clipCode1 & bMaxFlag )
  82         {
  83             cb = 2*da*(b1 - bMax);
  84             o_bs = bMax;
  85         }
  86
  87         if( clipCount1 == 2 )
  88             clipCode1 &= (ca + da < cb + !bRoundTowardsPt2) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
  89
  90         if( clipCode1 & (aMinFlag|aMaxFlag) )
  91         {
  92             cb = (ca + da - !bRoundTowardsPt2) / (2*da);
  93
  94             if( sb >= 0 )
  95             {
  96                 o_bs = b1 + cb;
  97                 if( o_bs > bMax )
  98                     return false; // fully clipped
  99             }
 100             else
 101             {
 102                 o_bs = b1 - cb;
 103                 if( o_bs < bMin )
 104                     return false; // fully clipped
 105             }
 106
 107             io_rem += ca - 2*da*cb;
 108         }
 109         else
 110         {
 111             ca = (cb - da + 2*db - bRoundTowardsPt2) / (2*db);
 112             if( sa >= 0 )
 113             {
 114                 o_as = a1 + ca;
 115                 if( o_as > aMax )
 116                     return false; // fully clipped
 117             }
 118             else
 119             {
 120                 o_as = a1 - ca;
 121                 if( o_as < aMin )
 122                     return false; // fully clipped
 123             }
 124
 125             io_rem += 2*db*ca - cb;
 126         }
 127     }
 128     else
 129     {
 130         o_as = a1; o_bs = b1;
 131     }
 132
 133     if( clipCode2 )
 134     {
 135         if( clipCount2 == 2 )
 136         {
 137             ca = 2*db*((clipCode2 & aMinFlag) ? a1 - aMin : aMax - a1);
 138             cb = 2*da*((clipCode2 & bMinFlag) ? b1 - bMin : bMax - b1);
 139             clipCode2 &= (cb + da < ca + bRoundTowardsPt2) ? ~(aMinFlag|aMaxFlag) : ~(bMinFlag|bMaxFlag);
 140         }
 141
 142         if( clipCode2 & (aMinFlag|aMaxFlag) )
 143             o_n = (clipCode2 & aMinFlag) ? o_as - aMin : aMax - o_as;
 144         else
 145         {
 146             o_n = (clipCode2 & bMinFlag) ? o_bs - bMin : bMax - o_bs;
 147             o_bUseAlternateBresenham = true;
 148         }
 149     }
 150     else
 151         o_n = (a2 >= o_as) ? a2 - o_as : o_as - a2;
 152
 153     return true; // at least one pixel to render
 154 }
 155
 156
 157 /** Render line to image iterators, clip against given rectangle
 158
 159     This method renders a line from aPt1 to aPt2, clipped against
 160     rClipRect (the clipping will take place pixel-perfect, i.e. as if
 161     the original bresenham-rendered line would have been clipped each
 162     pixel individually. No slight shifts compared to unclipped lines).
 163
 164     @param aPt1
 165     Start point of the line
 166
 167     @param aPt2
 168     End point of the line
 169
 170     @param rClipRect
 171     Rectangle to clip against
 172
 173     @param color
 174     Color value to render the line with
 175
 176     @param begin
 177     left-top image iterator
 178
 179     @param end
 180     right-bottom image iterator
 181
 182     @param acc
 183     Image accessor
 184
 185     @param bRoundTowardsPt2
 186     Rounding mode to use. Giving false here results in line pixel tend
 187     towards pt1, i.e. when a pixel exactly hits the middle between two
 188     pixel, the pixel closer to pt1 will be chosen. Giving true here
 189     makes renderClippedLine() choose pt2 in those cases.
 190  */
 191 template< class Iterator, class Accessor >
 192 void renderClippedLine( basegfx::B2IPoint             aPt1,
 193                         basegfx::B2IPoint             aPt2,
 194                         const basegfx::B2IBox&        rClipRect,
 195                         typename Accessor::value_type color,
 196                         Iterator                      begin,
 197                         Accessor                      acc,
 198                         bool                          bRoundTowardsPt2=false )
 199 {
 200     // Algorithm according to Steven Eker's 'Pixel-perfect line clipping',
 201     // Graphics Gems V, pp. 314-322
 202     sal_uInt32 clipCode1 = basegfx::tools::getCohenSutherlandClipFlags(aPt1,
 203                                                                        rClipRect);
 204     sal_uInt32 clipCode2 = basegfx::tools::getCohenSutherlandClipFlags(aPt2,
 205                                                                        rClipRect);
 206
 207     if( clipCode1 & clipCode2 )
 208         return; // line fully clipped away, both endpoints share a half-plane
 209
 210     sal_uInt32 clipCount1 = basegfx::tools::getNumberOfClipPlanes(clipCode1);
 211     sal_uInt32 clipCount2 = basegfx::tools::getNumberOfClipPlanes(clipCode2);
 212
 213     if( (clipCode1 != 0 && clipCode2 == 0)
 214         || (clipCount1 == 2 && clipCount2 == 1) )
 215     {
 216         std::swap(clipCount2,clipCount1);
 217         std::swap(clipCode2,clipCode1);
 218         std::swap(aPt1,aPt2);
 219         bRoundTowardsPt2 = !bRoundTowardsPt2;
 220     }
 221
 222     const sal_Int32 x1 = aPt1.getX();
 223     const sal_Int32 x2 = aPt2.getX();
 224     const sal_Int32 y1 = aPt1.getY();
 225     const sal_Int32 y2 = aPt2.getY();
 226
 227     // TODO(E1): This might overflow
 228     sal_Int32 adx = x2 - x1;
 229     int sx = 1;
 230     if( adx < 0 )
 231     {
 232         adx *= -1;
 233         sx = -1;
 234     }
 235
 236     // TODO(E1): This might overflow
 237     sal_Int32 ady = y2 - y1;
 238     int sy = 1;
 239     if( ady < 0 )
 240     {
 241         ady *= -1;
 242         sy = -1;
 243     }
 244
 245     int n  = 0;
 246     sal_Int32 xs = x1;
 247     sal_Int32 ys = y1;
 248     bool bUseAlternateBresenham=false;
 249     if( adx >= ady )
 250     {
 251         // semi-horizontal line
 252         sal_Int32 rem = 2*ady - adx - !bRoundTowardsPt2;
 253
 254         if( !prepareClip(x1, x2, y1, adx, ady, xs, ys, sx, sy,
 255                          rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
 256                          rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
 257                          rClipRect.getMaxX()-1, basegfx::tools::RectClipFlags::RIGHT,
 258                          rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
 259                          rClipRect.getMaxY()-1, basegfx::tools::RectClipFlags::BOTTOM,
 260                          bRoundTowardsPt2, bUseAlternateBresenham ) )
 261             return; // line fully clipped away, no active pixel inside rect
 262
 263         Iterator currIter( begin + vigra::Diff2D(0,ys) );
 264         typename vigra::IteratorTraits<Iterator>::row_iterator
 265             rowIter( currIter.rowIterator() + xs );
 266
 267         adx *= 2;
 268         ady *= 2;
 269
 270         if( bUseAlternateBresenham )
 271         {
 272             while(true)
 273             {
 274                 acc.set(color, rowIter);
 275
 276                 if( rem >= 0 )
 277                 {
 278                     // this is intended - we clip endpoint against y
 279                     // plane, so n here denotes y range to render
 280                     if( --n < 0 )
 281                         break;
 282
 283                     ys += sy;
 284                     xs += sx;
 285                     rem -= adx;
 286
 287                     currIter.y += sy;
 288                     rowIter = currIter.rowIterator() + xs;
 289                 }
 290                 else
 291                 {
 292                     xs += sx;
 293                     rowIter += sx;
 294                 }
 295
 296                 rem += ady;
 297             }
 298         }
 299         else
 300         {
 301             while(true)
 302             {
 303                 acc.set(color, rowIter);
 304
 305                 if( --n < 0 )
 306                     break;
 307
 308                 if( rem >= 0 )
 309                 {
 310                     ys += sy;
 311                     xs += sx;
 312                     rem -= adx;
 313
 314                     currIter.y += sy;
 315                     rowIter = currIter.rowIterator() + xs;
 316                 }
 317                 else
 318                 {
 319                     xs += sx;
 320                     rowIter += sx;
 321                 }
 322
 323                 rem += ady;
 324             }
 325         }
 326     }
 327     else
 328     {
 329         // semi-vertical line
 330         sal_Int32 rem = 2*adx - ady - !bRoundTowardsPt2;
 331
 332         if( !prepareClip(y1, y2, x1, ady, adx, ys, xs, sy, sx,
 333                          rem, n, clipCode1, clipCount1, clipCode2, clipCount2,
 334                          rClipRect.getMinY(), basegfx::tools::RectClipFlags::TOP,
 335                          rClipRect.getMaxY()-1, basegfx::tools::RectClipFlags::BOTTOM,
 336                          rClipRect.getMinX(), basegfx::tools::RectClipFlags::LEFT,
 337                          rClipRect.getMaxX()-1, basegfx::tools::RectClipFlags::RIGHT,
 338                          bRoundTowardsPt2, bUseAlternateBresenham ) )
 339             return; // line fully clipped away, no active pixel inside rect
 340
 341         Iterator currIter( begin + vigra::Diff2D(xs,0) );
 342         typename vigra::IteratorTraits<Iterator>::column_iterator
 343             colIter( currIter.columnIterator() + ys );
 344
 345         adx *= 2;
 346         ady *= 2;
 347
 348         if( bUseAlternateBresenham )
 349         {
 350             while(true)
 351             {
 352                 acc.set(color, colIter);
 353
 354                 if( rem >= 0 )
 355                 {
 356                     // this is intended - we clip endpoint against x
 357                     // plane, so n here denotes x range to render
 358                     if( --n < 0 )
 359                         break;
 360
 361                     xs += sx;
 362                     ys += sy;
 363                     rem -= ady;
 364
 365                     currIter.x += sx;
 366                     colIter = currIter.columnIterator() + ys;
 367                 }
 368                 else
 369                 {
 370                     ys += sy;
 371                     colIter += sy;
 372                 }
 373
 374                 rem += adx;
 375             }
 376         }
 377         else
 378         {
 379             while(true)
 380             {
 381                 acc.set(color, colIter);
 382
 383                 if( --n < 0 )
 384                     break;
 385
 386                 if( rem >= 0 )
 387                 {
 388                     xs += sx;
 389                     ys += sy;
 390                     rem -= ady;
 391
 392                     currIter.x += sx;
 393                     colIter = currIter.columnIterator() + ys;
 394                 }
 395                 else
 396                 {
 397                     ys += sy;
 398                     colIter += sy;
 399                 }
 400
 401                 rem += adx;
 402             }
 403         }
 404     }
 405 }
 406
 407 } // namespace basebmp
 408
 409 #endif /* INCLUDED_BASEBMP_CLIPPEDLINERENDERER_HXX */
 410
 411 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */