algo/Circle.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-2010 Jiri "BlueBear" Dluhos                            *
  20  *                         <jiri.bluebear.dluhos@gmail.com>                  *
  21  *                                                                           *
  22  * Copyright (C) 2009-2010 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  *     CONTEXT_T - user-defined type of drawing context (passed to PUTPIXEL)
  72  *     PIXVAL_T  - user-defined pixel value type (passed to PUTPIXEL)
  73  *     PUTPIXEL  - a pixel drawing function f(context, x, y, pixval)
  74  *     FN_NAME   - name of the function to be defined
  75  */
  76 #define DEF_CIRCLE_FN(FN_NAME, CONTEXT_T, PIXVAL_T, PUTPIXEL) \
  77 void FN_NAME(CONTEXT_T context, int xcenter, int ycenter, unsigned int r, \
  78         PIXVAL_T pixval) \
  79 { \
  80         int x, y, error; \
  81         for (x = 0, error = -r, y = r; y >= 0; y--) { \
  82 \
  83                 /* Iterate X until we can pass to the next line. */ \
  84                 while (error < 0) { \
  85                         error += 2*x + 1; \
  86                         x++; \
  87                         PUTPIXEL(context, xcenter-x+1, ycenter-y, pixval); \
  88                         PUTPIXEL(context, xcenter+x-1, ycenter-y, pixval); \
  89                         PUTPIXEL(context, xcenter-x+1, ycenter+y, pixval); \
  90                         PUTPIXEL(context, xcenter+x-1, ycenter+y, pixval); \
  91                 } \
  92 \
  93                 /* Enough changes accumulated, go to next line. */ \
  94                 error += -2*y + 1; \
  95                 PUTPIXEL(context, xcenter-x+1, ycenter-y, pixval); \
  96                 PUTPIXEL(context, xcenter+x-1, ycenter-y, pixval); \
  97                 PUTPIXEL(context, xcenter-x+1, ycenter+y, pixval); \
  98                 PUTPIXEL(context, xcenter+x-1, ycenter+y, pixval); \
  99         } \
 100 }