bertos/gfx/fillpoly.cpp

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