libs/gfx/algo/CircleSeg.algo.h

   1 /*****************************************************************************
   2  * This file is part of gfxprim library.                                     *
   3  *                                                                           *
   4  * Gfxprim is free software; you can redistribute it and/or                  *
   5  * modify it under the terms of the GNU Lesser General Public                *
   6  * License as published by the Free Software Foundation; either              *
   7  * version 2.1 of the License, or (at your option) any later version.        *
   8  *                                                                           *
   9  * Gfxprim is distributed in the hope that it will be useful,                *
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  12  * Lesser General Public License for more details.                           *
  13  *                                                                           *
  14  * You should have received a copy of the GNU Lesser General Public          *
  15  * License along with gfxprim; if not, write to the Free Software            *
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor,                        *
  17  * Boston, MA  02110-1301  USA                                               *
  18  *                                                                           *
  19  * Copyright (C) 2009-2011 Jiri "BlueBear" Dluhos                            *
  20  *                         <jiri.bluebear.dluhos@gmail.com>                  *
  21  *                                                                           *
  22  * Copyright (C) 2009-2012 Cyril Hrubis <metan@ucw.cz>                       *
  23  *                                                                           *
  24  *****************************************************************************/
  25
  26 /*
  27  * Circle drawing algorithm.
  28  *
  29  * The circle is drawn in a top-down manner. We start from the top, and
  30  * at each line, we iterate X until we accumulate enough changes to Y
  31  * to pass to the next line. In each step, 4 pixels are drawn:
  32  * (X, Y), (-X, Y), (X, -Y) and (-X, -Y).
  33  *
  34  * The math:
  35  * From the circle equation, for every point applies:
  36  *
  37  * x^2 + y^2 = r^2      ->       x^2 + y^2 - r^2 = 0
  38  *
  39  * which has an exact solution for a non-integer x.
  40  * For an integer approximation, we want to find x
  41  * for which
  42  *
  43  * x^2 + y^2 - r^2 = error
  44  *
  45  * where error should be as close to 0 as possible.
  46  * We find the x by incrementing its value until
  47  * we cross the zero error boundary.
  48  *
  49  * Optimization:
  50  * Significant amount of multiplications can be
  51  * saved when calculating error by re-using previous
  52  * error values. For error(x+1) we have:
  53  *
  54  * error(x+1) = (x+1)^2 + y^2 - r^2
  55  *
  56  * which can be expanded to (expanding (x+1)^2):
  57  *
  58  * error(x+1) = x^2 + 2*x + 1 + y^2 - r^2
  59  *
  60  * and after substituting the error(x) we already know:
  61  *
  62  * error(x+1) = error(x) + 2*x + 1
  63  *
  64  * The same can be done for calculating
  65  * error(y-1) from error(y).
  66  */
  67
  68 /*
  69  * This macro defines a circle drawing function.
  70  * Arguments:
  71  *     PIXMAP_T - user-defined type of drawing pixmap (passed to PUTPIXEL)
  72  *     PIXVAL_T  - user-defined pixel value type (passed to PUTPIXEL)
  73  *     PUTPIXEL  - a pixel drawing function f(pixmap, x, y, pixval)
  74  *     FN_NAME   - name of the function to be defined
  75  */
  76 #define DEF_CIRCLE_SEG_FN(FN_NAME, PIXMAP_T, PIXVAL_T, PUTPIXEL) \
  77 static void FN_NAME(PIXMAP_T pixmap, int xcenter, int ycenter, int r, \
  78         uint8_t seg_flags, PIXVAL_T pixval) \
  79 { \
  80         int x, y, error; \
  81 \
  82         /* Special case for r == 0 */ \
  83         if (r == 0) { \
  84                 if (seg_flags) \
  85                         PUTPIXEL(pixmap, xcenter, ycenter, pixval); \
  86                 return; \
  87         } \
  88 \
  89         /* Clip negative r */ \
  90         r = r < 0 ? -r : r; \
  91 \
  92         for (x = 0, error = -r, y = r; y >= 0; y--) { \
  93 \
  94                 /* Iterate X until we can pass to the next line. */ \
  95                 while (error < 0) { \
  96                         error += 2*x + 1; \
  97                         x++; \
  98                         if (seg_flags & GP_CIRCLE_SEG2) \
  99                                 PUTPIXEL(pixmap, xcenter-x+1, ycenter-y, pixval); \
 100                         if (seg_flags & GP_CIRCLE_SEG1) \
 101                                 PUTPIXEL(pixmap, xcenter+x-1, ycenter-y, pixval); \
 102                         if (seg_flags & GP_CIRCLE_SEG3) \
 103                                 PUTPIXEL(pixmap, xcenter-x+1, ycenter+y, pixval); \
 104                         if (seg_flags & GP_CIRCLE_SEG4) \
 105                                 PUTPIXEL(pixmap, xcenter+x-1, ycenter+y, pixval); \
 106                 } \
 107 \
 108                 /* Enough changes accumulated, go to next line. */ \
 109                 error += -2*y + 1; \
 110                 if (seg_flags & GP_CIRCLE_SEG2) \
 111                         PUTPIXEL(pixmap, xcenter-x+1, ycenter-y, pixval); \
 112                 if (seg_flags & GP_CIRCLE_SEG1) \
 113                         PUTPIXEL(pixmap, xcenter+x-1, ycenter-y, pixval); \
 114                 if (seg_flags & GP_CIRCLE_SEG3) \
 115                         PUTPIXEL(pixmap, xcenter-x+1, ycenter+y, pixval); \
 116                 if (seg_flags & GP_CIRCLE_SEG4) \
 117                         PUTPIXEL(pixmap, xcenter+x-1, ycenter+y, pixval); \
 118         } \
 119 }