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