ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

graphics/primitives.cpp

Go to the documentation of this file.
00001 /* ScummVM - Graphic Adventure Engine
00002  *
00003  * ScummVM is the legal property of its developers, whose names
00004  * are too numerous to list here. Please refer to the COPYRIGHT
00005  * file distributed with this source distribution.
00006  *
00007  * This program is free software; you can redistribute it and/or
00008  * modify it under the terms of the GNU General Public License
00009  * as published by the Free Software Foundation; either version 2
00010  * of the License, or (at your option) any later version.
00011  *
00012  * This program is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00020  *
00021  */
00022 
00023 #include "common/algorithm.h"
00024 #include "common/util.h"
00025 #include "graphics/primitives.h"
00026 
00027 namespace Graphics {
00028 
00029 void drawLine(int x0, int y0, int x1, int y1, int color, void (*plotProc)(int, int, int, void *), void *data) {
00030     // Bresenham's line algorithm, as described by Wikipedia
00031     const bool steep = ABS(y1 - y0) > ABS(x1 - x0);
00032 
00033     if (steep) {
00034         SWAP(x0, y0);
00035         SWAP(x1, y1);
00036     }
00037 
00038     const int delta_x = ABS(x1 - x0);
00039     const int delta_y = ABS(y1 - y0);
00040     const int delta_err = delta_y;
00041     int x = x0;
00042     int y = y0;
00043     int err = 0;
00044 
00045     const int x_step = (x0 < x1) ? 1 : -1;
00046     const int y_step = (y0 < y1) ? 1 : -1;
00047 
00048     if (steep)
00049         (*plotProc)(y, x, color, data);
00050     else
00051         (*plotProc)(x, y, color, data);
00052 
00053     while (x != x1) {
00054         x += x_step;
00055         err += delta_err;
00056         if (2 * err > delta_x) {
00057             y += y_step;
00058             err -= delta_x;
00059         }
00060         if (steep)
00061             (*plotProc)(y, x, color, data);
00062         else
00063             (*plotProc)(x, y, color, data);
00064     }
00065 }
00066 
00067 void drawHLine(int x1, int x2, int y, int color, void (*plotProc)(int, int, int, void *), void *data) {
00068     if (x1 > x2)
00069         SWAP(x1, x2);
00070 
00071     for (int x = x1; x <= x2; x++)
00072         (*plotProc)(x, y, color, data);
00073 }
00074 
00075 void drawVLine(int x, int y1, int y2, int color, void (*plotProc)(int, int, int, void *), void *data) {
00076     if (y1 > y2)
00077         SWAP(y1, y2);
00078 
00079     for (int y = y1; y <= y2; y++)
00080         (*plotProc)(x, y, color, data);
00081 }
00082 
00083 void drawThickLine(int x0, int y0, int x1, int y1, int penX, int penY, int color, void (*plotProc)(int, int, int, void *), void *data) {
00084     assert(penX > 0 && penY > 0);
00085 
00086     // Shortcut
00087     if (penX == 1 && penY == 1) {
00088         drawLine(x0, y0, x1, y1, color, plotProc, data);
00089         return;
00090     }
00091 
00092     // TODO: Optimize this. It currently is a very naive way of handling
00093     // thick lines since quite often it will be drawing to the same pixel
00094     // multiple times.
00095     for (int x = 0; x < penX; x++)
00096         for (int y = 0; y < penY; y++)
00097             drawLine(x0 + x, y0 + y, x1 + x, y1 + y, color, plotProc, data);
00098 }
00099 
00100 /* Bresenham as presented in Foley & Van Dam */
00101 /* Code is based on GD lib http://libgd.github.io/ */
00102 void drawThickLine2(int x1, int y1, int x2, int y2, int thick, int color, void (*plotProc)(int, int, int, void *), void *data) {
00103     int incr1, incr2, d, x, y, xend, yend, xdirflag, ydirflag;
00104     int wid;
00105     int w, wstart;
00106 
00107     int dx = abs(x2 - x1);
00108     int dy = abs(y2 - y1);
00109 
00110     if (dx == 0) {
00111         int xn = x1 - thick / 2;
00112         Common::Rect r(xn, MIN(y1, y2), xn + thick - 1, MAX(y1, y2));
00113         drawFilledRect(r, color, plotProc, data);
00114         return;
00115     } else if (dy == 0) {
00116         int yn = y1 - thick / 2;
00117         Common::Rect r(MIN(x1, x2), yn, MAX(x1, x2), yn + thick - 1);
00118         drawFilledRect(r, color, plotProc, data);
00119         return;
00120     }
00121 
00122     if (dy <= dx) {
00123         /* More-or-less horizontal. use wid for vertical stroke */
00124 
00125         /* 2.0.12: Michael Schwartz: divide rather than multiply;
00126               TBB: but watch out for /0! */
00127         if (dx != 0 && thick != 0) {
00128             double ac_recip = 1/dx * sqrt(dx * dx + dy * dy); // 1 / cos(atan2((double)dy, (double)dx));
00129             wid = thick * ac_recip;
00130         } else {
00131             wid = 1;
00132         }
00133 
00134         d = 2 * dy - dx;
00135         incr1 = 2 * dy;
00136         incr2 = 2 * (dy - dx);
00137         if (x1 > x2) {
00138             x = x2;
00139             y = y2;
00140             ydirflag = (-1);
00141             xend = x1;
00142         } else {
00143             x = x1;
00144             y = y1;
00145             ydirflag = 1;
00146             xend = x2;
00147         }
00148 
00149         /* Set up line thickness */
00150         wstart = y - wid / 2;
00151         for (w = wstart; w < wstart + wid; w++)
00152             (*plotProc)(x, y, color, data);
00153 
00154         if (((y2 - y1) * ydirflag) > 0) {
00155             while (x < xend) {
00156                 x++;
00157                 if (d < 0) {
00158                     d += incr1;
00159                 } else {
00160                     y++;
00161                     d += incr2;
00162                 }
00163                 wstart = y - wid / 2;
00164                 for (w = wstart; w < wstart + wid; w++)
00165                     (*plotProc)(x, w, color, data);
00166             }
00167         } else {
00168             while (x < xend) {
00169                 x++;
00170                 if (d < 0) {
00171                     d += incr1;
00172                 } else {
00173                     y--;
00174                     d += incr2;
00175                 }
00176                 wstart = y - wid / 2;
00177                 for (w = wstart; w < wstart + wid; w++)
00178                     (*plotProc)(x, w, color, data);
00179             }
00180         }
00181     } else {
00182         /* More-or-less vertical. use wid for horizontal stroke */
00183         /* 2.0.12: Michael Schwartz: divide rather than multiply;
00184            TBB: but watch out for /0! */
00185         if (dy != 0 && thick != 0) {
00186             double as_recip = 1/dy * sqrt(dx * dx + dy * dy); // 1 / sin(atan2((double)dy, (double)dx));
00187             wid = thick * as_recip;
00188         } else {
00189             wid = 1;
00190         }
00191 
00192         d = 2 * dx - dy;
00193         incr1 = 2 * dx;
00194         incr2 = 2 * (dx - dy);
00195         if (y1 > y2) {
00196             y = y2;
00197             x = x2;
00198             yend = y1;
00199             xdirflag = (-1);
00200         } else {
00201             y = y1;
00202             x = x1;
00203             yend = y2;
00204             xdirflag = 1;
00205         }
00206 
00207         /* Set up line thickness */
00208         wstart = x - wid / 2;
00209         for (w = wstart; w < wstart + wid; w++)
00210             (*plotProc)(w, y, color, data);
00211 
00212         if (((x2 - x1) * xdirflag) > 0) {
00213             while (y < yend) {
00214                 y++;
00215                 if (d < 0) {
00216                     d += incr1;
00217                 } else {
00218                     x++;
00219                     d += incr2;
00220                 }
00221                 wstart = x - wid / 2;
00222                 for (w = wstart; w < wstart + wid; w++)
00223                     (*plotProc)(w, y, color, data);
00224             }
00225         } else {
00226             while (y < yend) {
00227                 y++;
00228                 if (d < 0) {
00229                     d += incr1;
00230                 } else {
00231                     x--;
00232                     d += incr2;
00233                 }
00234                 wstart = x - wid / 2;
00235                 for (w = wstart; w < wstart + wid; w++)
00236                     (*plotProc)(w, y, color, data);
00237             }
00238         }
00239     }
00240 }
00241 
00242 void drawFilledRect(Common::Rect &rect, int color, void (*plotProc)(int, int, int, void *), void *data) {
00243     for (int y = rect.top; y <= rect.bottom; y++)
00244         drawHLine(rect.left, rect.right, y, color, plotProc, data);
00245 }
00246 
00247 // http://members.chello.at/easyfilter/bresenham.html
00248 void drawRoundRect(Common::Rect &rect, int arc, int color, bool filled, void (*plotProc)(int, int, int, void *), void *data) {
00249     if (rect.height() < rect.width()) {
00250         int x = -arc, y = 0, err = 2-2*arc; /* II. Quadrant */
00251         int dy = rect.height() - arc * 2;
00252         int r = arc;
00253         int stop = 0;
00254         int lastx = 0, lasty = 0;
00255         if (dy < 0)
00256             stop = -dy / 2;
00257 
00258         do {
00259             if (filled) {
00260                 drawHLine(rect.left + x + r, rect.right - x - r, rect.top    - y + r - stop, color, plotProc, data);
00261                 drawHLine(rect.left + x + r, rect.right - x - r, rect.bottom + y - r + stop, color, plotProc, data);
00262             } else {
00263                 (*plotProc)(rect.left  + x + r, rect.top    - y + r - stop, color, data);
00264                 (*plotProc)(rect.right - x - r, rect.top    - y + r - stop, color, data);
00265                 (*plotProc)(rect.left  + x + r, rect.bottom + y - r + stop, color, data);
00266                 (*plotProc)(rect.right - x - r, rect.bottom + y - r + stop, color, data);
00267 
00268                 lastx = x;
00269                 lasty = y;
00270             }
00271             arc = err;
00272             if (arc <= y) err += ++y*2+1;           /* e_xy+e_y < 0 */
00273             if (arc > x || err > y) err += ++x*2+1; /* e_xy+e_x > 0 or no 2nd y-step */
00274             if (stop && y > stop)
00275                 break;
00276         } while (x < 0);
00277 
00278         if (!filled) {
00279             x = lastx;
00280             y = lasty;
00281 
00282             drawHLine(rect.left + x + r, rect.right - x - r, rect.top    - y + r - stop, color, plotProc, data);
00283             drawHLine(rect.left + x + r, rect.right - x - r, rect.bottom + y - r + stop, color, plotProc, data);
00284         }
00285 
00286         for (int i = 0; i < dy; i++) {
00287             if (filled) {
00288                 drawHLine(rect.left, rect.right, rect.top + r + i, color, plotProc, data);
00289             } else {
00290                 (*plotProc)(rect.left,  rect.top + r + i, color, data);
00291                 (*plotProc)(rect.right, rect.top + r + i, color, data);
00292             }
00293         }
00294     } else {
00295         int y = -arc, x = 0, err = 2-2*arc; /* II. Quadrant */
00296         int dx = rect.width() - arc * 2;
00297         int r = arc;
00298         int stop = 0;
00299         int lastx = 0, lasty = 0;
00300         if (dx < 0)
00301             stop = -dx / 2;
00302 
00303         do {
00304             if (filled) {
00305                 drawVLine(rect.left  - x + r - stop, rect.top + y + r, rect.bottom - y - r, color, plotProc, data);
00306                 drawVLine(rect.right + x - r + stop, rect.top + y + r, rect.bottom - y - r, color, plotProc, data);
00307             } else {
00308                 (*plotProc)(rect.left  - x + r - stop, rect.top    + y + r, color, data);
00309                 (*plotProc)(rect.left  - x + r - stop, rect.bottom - y - r, color, data);
00310                 (*plotProc)(rect.right + x - r + stop, rect.top    + y + r, color, data);
00311                 (*plotProc)(rect.right + x - r + stop, rect.bottom - y - r, color, data);
00312 
00313                 lastx = x;
00314                 lasty = y;
00315             }
00316 
00317             arc = err;
00318             if (arc <= x) err += ++x*2+1;           /* e_xy+e_y < 0 */
00319             if (arc > y || err > x) err += ++y*2+1; /* e_xy+e_x > 0 or no 2nd y-step */
00320             if (stop && x > stop)
00321                 break;
00322         } while (y < 0);
00323 
00324         if (!filled) {
00325             x = lastx;
00326             y = lasty;
00327             drawVLine(rect.left  - x + r - stop, rect.top + y + r, rect.bottom - y - r, color, plotProc, data);
00328             drawVLine(rect.right + x - r + stop, rect.top + y + r, rect.bottom - y - r, color, plotProc, data);
00329         }
00330 
00331         for (int i = 0; i < dx; i++) {
00332             if (filled) {
00333                 drawVLine(rect.left + r + i, rect.top, rect.bottom, color, plotProc, data);
00334             } else {
00335                 (*plotProc)(rect.left + r + i, rect.top,    color, data);
00336                 (*plotProc)(rect.left + r + i, rect.bottom, color, data);
00337             }
00338         }
00339     }
00340 }
00341 
00342 // Based on public-domain code by Darel Rex Finley, 2007
00343 // http://alienryderflex.com/polygon_fill/
00344 void drawPolygonScan(int *polyX, int *polyY, int npoints, Common::Rect &bbox, int color, void (*plotProc)(int, int, int, void *), void *data) {
00345     int *nodeX = (int *)calloc(npoints, sizeof(int));
00346     int i, j;
00347 
00348     //  Loop through the rows of the image.
00349     for (int pixelY = bbox.top; pixelY < bbox.bottom; pixelY++) {
00350         //  Build a list of nodes.
00351         int nodes = 0;
00352         j = npoints - 1;
00353 
00354         for (i = 0; i < npoints; i++) {
00355             if ((polyY[i] < pixelY && polyY[j] >= pixelY) || (polyY[j] < pixelY && polyY[i] >= pixelY)) {
00356                 nodeX[nodes++] = (int)(polyX[i] + (double)(pixelY - polyY[i]) / (double)(polyY[j]-polyY[i]) *
00357                                                         (double)(polyX[j] - polyX[i]) + 0.5);
00358             }
00359             j = i;
00360         }
00361 
00362         //  Sort the nodes
00363         Common::sort(nodeX, &nodeX[nodes]);
00364 
00365         //  Fill the pixels between node pairs.
00366         for (i = 0; i < nodes; i += 2) {
00367             if (nodeX[i  ] >= bbox.right)
00368                 break;
00369             if (nodeX[i + 1] > bbox.left) {
00370                 nodeX[i] = MAX<int16>(nodeX[i], bbox.left);
00371                 nodeX[i + 1] = MIN<int16>(nodeX[i + 1], bbox.right);
00372 
00373                 drawHLine(nodeX[i], nodeX[i + 1], pixelY, color, plotProc, data);
00374             }
00375         }
00376     }
00377 
00378     free(nodeX);
00379 }
00380 
00381 // http://members.chello.at/easyfilter/bresenham.html
00382 void drawEllipse(int x0, int y0, int x1, int y1, int color, bool filled, void (*plotProc)(int, int, int, void *), void *data) {
00383     int a = abs(x1 - x0), b = abs(y1 - y0), b1 = b & 1; /* values of diameter */
00384     long dx = 4 * (1 - a) * b * b, dy = 4 * (b1 + 1) * a * a; /* error increment */
00385     long err = dx + dy + b1 * a * a, e2; /* error of 1.step */
00386 
00387     if (x0 > x1) { x0 = x1; x1 += a; } /* if called with swapped points */
00388     if (y0 > y1) y0 = y1; /* .. exchange them */
00389     y0 += (b + 1) / 2; y1 = y0 - b1;   /* starting pixel */
00390     a *= 8 * a; b1 = 8 * b * b;
00391 
00392     do {
00393         if (filled) {
00394             drawHLine(x0, x1, y0, color, plotProc, data);
00395             drawHLine(x0, x1, y1, color, plotProc, data);
00396         } else {
00397             (*plotProc)(x1, y0, color, data); /*   I. Quadrant */
00398             (*plotProc)(x0, y0, color, data); /*  II. Quadrant */
00399             (*plotProc)(x0, y1, color, data); /* III. Quadrant */
00400             (*plotProc)(x1, y1, color, data); /*  IV. Quadrant */
00401         }
00402         e2 = 2*err;
00403         if (e2 <= dy) { y0++; y1--; err += dy += a; }  /* y step */
00404         if (e2 >= dx || 2*err > dy) { x0++; x1--; err += dx += b1; } /* x step */
00405     } while (x0 <= x1);
00406 
00407     while (y0-y1 < b) {  /* too early stop of flat ellipses a=1 */
00408         if (filled) {
00409             drawHLine(x0 - 1, x0 - 1, y0, color, plotProc, data); /* -> finish tip of ellipse */
00410             drawHLine(x1 + 1, x1 + 1, y0, color, plotProc, data);
00411             drawHLine(x0 - 1, x0 - 1, y1, color, plotProc, data);
00412             drawHLine(x1 + 1, x1 + 1, y1, color, plotProc, data);
00413         } else {
00414             (*plotProc)(x0 - 1, y0, color, data); /* -> finish tip of ellipse */
00415             (*plotProc)(x1 + 1, y0, color, data);
00416             (*plotProc)(x0 - 1, y1, color, data);
00417             (*plotProc)(x1 + 1, y1, color, data);
00418         }
00419         y0++;
00420         y1--;
00421     }
00422 }
00423 
00424 } // End of namespace Graphics


Generated on Sat Mar 16 2019 05:01:50 for ResidualVM by doxygen 1.7.1
curved edge   curved edge