gfx/fillpoly.cpp

   1 /**
   2  * \file
   3  * <!--
   4  * Copyright 2005 Develer S.r.l. (http://www.develer.com/)
   5  * This file is part of DevLib - See README.devlib for information.
   6  * -->
   7  *
   8  * \version $Id$
   9  * \author Massimiliano Corsini <chad@develer.com>
  10  *
  11  *
  12  * \brief Low-level drawing routines.
  13  *
  14  * This file contains the implementation of the low-level drawing routines
  15  * to draw fill rectangle, fill triangle and so on.
  16  *
  17  */
  18
  19 /*#*
  20  *#* $Log$
  21  *#* Revision 1.1  2006/07/19 13:00:01  bernie
  22  *#* Import into DevLib.
  23  *#*
  24  *#* Revision 1.10  2005/10/15 15:03:43  rasky
  25  *#* Remove per-pixel clipping from line().
  26  *#* Use clipLine() also for a-scope.
  27  *#*
  28  *#* Revision 1.9  2005/10/14 15:21:32  eldes
  29  *#* Implement the cohen-sutherland clipping on the buffer
  30  *#*
  31  *#* Revision 1.8  2005/09/27 13:28:10  rasky
  32  *#* Add clipping capabilities to line()
  33  *#* Fix off-by-one computation of rectangles of drawing.
  34  *#*
  35  *#* Revision 1.7  2005/09/27 10:41:35  rasky
  36  *#* Import line-drawing routine from Devlib
  37  *#*
  38  *#* Revision 1.6  2005/09/19 16:36:05  chad
  39  *#* Fix doxygen autobrief
  40  *#*
  41  *#* Revision 1.5  2005/07/06 12:51:47  chad
  42  *#* Make the fillRectangle() independent of the order of the points of the rectangle
  43  *#*
  44  *#* Revision 1.4  2005/06/17 15:06:36  chad
  45  *#* Remove conversion warning
  46  *#*
  47  *#* Revision 1.3  2005/06/17 15:04:47  chad
  48  *#* Add line clipping capability
  49  *#*
  50  *#* Revision 1.2  2005/06/15 14:04:43  chad
  51  *#* Add line routine
  52  *#*
  53  *#* Revision 1.1  2005/06/15 13:34:34  chad
  54  *#* Low-level drawing routines
  55  *#*
  56  *#*/
  57
  58 // Qt-specific headers
  59 #include <qpoint.h>
  60
  61
  62 /**
  63  * Low-level routine to draw a line.
  64  *
  65  * This routine is based on the Bresenham Line-Drawing Algorithm.
  66  *
  67  * The \a stride represents the width of the image buffer.
  68  * (\a x1, \a y1) are the coordinates of the starting point.
  69  * (\a x2, \a y2) are the coordinates of the ending point.
  70  *
  71  * The line has no anti-alias, and clipping is not performed. The line
  72  * must be fully contained in the buffer (use clipLine() if you need
  73  * to clip it).
  74  */
  75 void line(unsigned char *buf,
  76                   unsigned long bufw, unsigned long bufh, unsigned long stride,
  77                   int x1, int y1, int x2, int y2, unsigned char color)
  78 {
  79         int x, y, e, len, adx, ady, signx, signy;
  80
  81         if (x2 > x1)
  82         {
  83                 /* left to right */
  84                 signx = +1;
  85                 adx = x2 - x1;
  86         }
  87         else
  88         {
  89                 /* right to left */
  90                 signx = -1;
  91                 adx = x1 - x2;
  92         }
  93
  94         if (y2 > y1)
  95         {
  96                 /* top to bottom */
  97                 signy = +1;
  98                 ady = y2 - y1;
  99         }
 100         else
 101         {
 102                 /* bottom to top */
 103                 signy = -1;
 104                 ady = y1 - y2;
 105         }
 106
 107         x = x1;
 108         y = y1;
 109
 110         if (adx > ady)
 111         {
 112                 /* X-major line (octants 1/4/5/8) */
 113                 len = adx;
 114                 e = -adx;
 115                 while (len--)
 116                 {
 117                         /* Sanity check */
 118                         assert(y >= 0 && y < static_cast<int>(bufh) &&
 119                                    x >= 0 && x < static_cast<int>(bufw));
 120                         buf[y * stride + x] = color;
 121                         x += signx;
 122                         e += ady;
 123                         if (e >= 0)
 124                         {
 125                                 y += signy;
 126                                 e -= adx;
 127                         }
 128                 }
 129         }
 130         else
 131         {
 132                 /* Y-major line (octants 2/3/6/7) */
 133                 len = ady;
 134                 e = -ady;
 135                 while (len--)
 136                 {
 137                         /* Sanity check */
 138                         assert(y >= 0 && y < static_cast<int>(bufh) &&
 139                                    x >= 0 && x < static_cast<int>(bufw));
 140                         buf[y * stride + x] = color;
 141                         y += signy;
 142                         e += adx;
 143                         if (e >= 0)
 144                         {
 145                                 x += signx;
 146                                 e -= ady;
 147                         }
 148                 }
 149         }
 150 }
 151
 152 /// Helper routine for clipLine().
 153 static int region(int x, int y, int w, int h)
 154 {
 155         int code = 0;
 156
 157         if (y >= h)
 158                 code |= 1; // top
 159         else if (y < 0)
 160                 code |= 2; // bottom
 161
 162         if (x >= w)
 163                 code |= 4; // right
 164         else if (x < 0)
 165                 code |= 8; // left
 166
 167         return code;
 168 }
 169
 170 /**
 171  * Low-level routine to draw a line, clipped to the buffer extents.
 172  *
 173  * This routine executes the clipping, and then invokes line().
 174  * Parameters are the same of line(). The clipping is performed
 175  * using the Cohen-Sutherland algorithm, which is very fast.
 176  */
 177 void clipLine(unsigned char *buf,
 178                   unsigned long w, unsigned long h, unsigned long stride,
 179                   int x1, int y1, int x2, int y2, unsigned char color)
 180 {
 181         int code1 = region(x1, y1, w, h);
 182         int code2 = region(x2, y2, w, h);
 183
 184         // Loop while there is at least one point outside
 185         while (code1 | code2)
 186         {
 187                 // Check for line totally outside
 188                 if (code1 & code2)
 189                         return;
 190
 191                 int c = code1 ? code1 : code2;
 192                 int x, y;
 193
 194                 if (c & 1) // top
 195                 {
 196                         x = x1 + (x2 - x1) * (h - y1) / (y2 - y1);
 197                         y = h - 1;
 198                 }
 199                 else if (c & 2) //bottom
 200                 {
 201                         x = x1 + (x2 - x1) * -y1 / (y2 - y1);
 202                         y = 0;
 203                 }
 204                 else if (c & 4) //right
 205                 {
 206                         y = y1 + (y2 - y1) * (w - x1) / (x2 - x1);
 207                         x = w - 1;
 208                 }
 209                 else //left
 210                 {
 211                         y = y1 + (y2 - y1) * -x1 / (x2 - x1);
 212                         x = 0;
 213                 }
 214
 215                 if (c == code1) // first endpoint was clipped
 216                 {
 217                         x1 = x; y1 = y;
 218                         code1 = region(x1, y1, w, h);
 219                 }
 220                 else //second endpoint was clipped
 221                 {
 222                         x2 = x; y2 = y;
 223                         code2 = region(x2, y2, w, h);
 224                 }
 225         }
 226
 227         line(buf, w, h, stride, x1, y1, x2, y2, color);
 228 }
 229
 230
 231 /**
 232  * Low-level routine to draw a filled rectangle.
 233  *
 234  * The triangle is filled with the given color.
 235  *
 236  * The \a stride represents the width of the image buffer.
 237  * The points \a p1 and \a p2 are two opposite corners of the
 238  * rectangle.
 239  */
 240 void fillRectangle(unsigned char *buf, unsigned long stride,
 241                                    QPoint p1, QPoint p2, unsigned char color)
 242 {
 243         QPoint ul;       // upper-left corner
 244         QPoint lr;       // lower-right corner
 245
 246         if (p2.x() > p1.x())
 247         {
 248                 ul.setX(p1.x());
 249                 lr.setX(p2.x());
 250         }
 251         else
 252         {
 253                 ul.setX(p2.x());
 254                 lr.setX(p1.x());
 255         }
 256
 257         if (p2.y() > p1.y())
 258         {
 259                 ul.setY(p1.y());
 260                 lr.setY(p2.y());
 261         }
 262         else
 263         {
 264                 ul.setY(p2.y());
 265                 lr.setY(p1.y());
 266         }
 267
 268         int width = lr.x() - ul.x();
 269         unsigned long offset = ul.x() + ul.y()*stride;
 270
 271         for (int h = ul.y(); h < lr.y(); h++)
 272         {
 273                 memset(buf+offset, color, width);
 274                 offset += stride;
 275         }
 276 }
 277
 278 /**
 279  * Low-level routines to draw a filled triangle.
 280  *
 281  * The triangle is filled with the given \a color.
 282  * The \a stride represents the width of the image buffer (\a buf).
 283  *
 284  * The routine use fixed-point arithmetic.
 285  */
 286 void fillTriangle(unsigned char* buf, unsigned long stride,
 287                                   QPoint v1, QPoint v2, QPoint v3, unsigned char color)
 288 {
 289         int altezza[3];
 290
 291         // Sort by vertical coordinate
 292         if (v1.y() > v2.y())
 293                 std::swap(v1, v2);
 294         if (v1.y() > v3.y())
 295                 std::swap(v1, v3);
 296         if (v2.y() > v3.y())
 297                 std::swap(v2, v3);
 298
 299         altezza[0] = v3.y() - v1.y();
 300         if (!altezza[0])
 301                 return;
 302
 303         int sezioni = 2;
 304         int sezione = 1;
 305
 306         buf += v1.y() * stride;
 307
 308         altezza[1] = v2.y() - v1.y();
 309         altezza[2] = v3.y() - v2.y();
 310
 311         int sinistra = v1.x();
 312         int destra = sinistra;
 313
 314         if (v1.y() == v2.y())
 315         {
 316                 if (v1.x() < v2.x())
 317                         destra = v2.x();
 318                 else
 319                         sinistra = v2.x();
 320         }
 321
 322         sinistra <<= 16;
 323         destra <<= 16;
 324
 325         int stmp1, stmp2, stmp3;
 326
 327         stmp1 = (altezza[1] << 16) / altezza[0];
 328         int lunghezza = stmp1 * (v3.x() - v1.x()) + ((v1.x() - v2.x()) << 16);
 329
 330         if (!lunghezza )
 331                 return;
 332
 333         int delta_sinistra[2];
 334         int delta_destra[2];
 335
 336         stmp1 = ((v3.x() - v1.x()) << 16) / altezza[0];
 337
 338         if (altezza[1])
 339                 stmp2 = ((v2.x() - v1.x()) << 16) / altezza[1];
 340         if (altezza[2])
 341                 stmp3 = ((v3.x() - v2.x()) << 16) / altezza[2];
 342
 343         if (lunghezza < 0) // Il secondo vertice ~J a destra
 344         {
 345                 delta_sinistra[0] = stmp1;
 346                 delta_sinistra[1] = stmp1;
 347                 delta_destra[0] = stmp2;
 348                 delta_destra[1] = stmp3;
 349         }
 350         else // Il secondo vertice ~J a sinistra
 351         {
 352                 delta_sinistra[0] = stmp2;
 353                 delta_sinistra[1] = stmp3;
 354                 delta_destra[0] = stmp1;
 355                 delta_destra[1] = stmp1;
 356         }
 357
 358         int len2 = lunghezza;
 359
 360         do
 361         {
 362                 while (altezza [sezione])
 363                 {
 364                         unsigned char* curpos = buf + ((sinistra )>> 16);
 365                         lunghezza = ((destra ) >> 16) - ((sinistra ) >> 16);
 366                         assert(lunghezza >= 0);
 367                         if (lunghezza)
 368                                 memset(curpos, color, lunghezza);
 369                         buf += stride;
 370                         destra += delta_destra[sezione - 1];
 371                         sinistra += delta_sinistra[sezione - 1];
 372                         altezza[sezione]--;
 373                 }
 374                 if (len2 < 0)
 375                         destra = v2.x() << 16;
 376                 else
 377                         sinistra = v2.x() << 16;
 378                 sezione++;
 379         } while (--sezioni);
 380 }