git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/mi/miscanfill.h

   1 /* $XConsortium: miscanfill.h,v 1.5 94/04/17 20:27:50 dpw Exp $ */
   2 /*
   3
   4 Copyright (c) 1987  X Consortium
   5
   6 Permission is hereby granted, free of charge, to any person obtaining
   7 a copy of this software and associated documentation files (the
   8 "Software"), to deal in the Software without restriction, including
   9 without limitation the rights to use, copy, modify, merge, publish,
  10 distribute, sublicense, and/or sell copies of the Software, and to
  11 permit persons to whom the Software is furnished to do so, subject to
  12 the following conditions:
  13
  14 The above copyright notice and this permission notice shall be included
  15 in all copies or substantial portions of the Software.
  16
  17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
  21 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  22 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  23 OTHER DEALINGS IN THE SOFTWARE.
  24
  25 Except as contained in this notice, the name of the X Consortium shall
  26 not be used in advertising or otherwise to promote the sale, use or
  27 other dealings in this Software without prior written authorization
  28 from the X Consortium.
  29
  30 */
  31
  32
  33 #ifndef SCANFILLINCLUDED
  34 #define SCANFILLINCLUDED
  35 /*
  36  *     scanfill.h
  37  *
  38  *     Written by Brian Kelleher; Jan 1985
  39  *
  40  *     This file contains a few macros to help track
  41  *     the edge of a filled object.  The object is assumed
  42  *     to be filled in scanline order, and thus the
  43  *     algorithm used is an extension of Bresenham's line
  44  *     drawing algorithm which assumes that y is always the
  45  *     major axis.
  46  *     Since these pieces of code are the same for any filled shape,
  47  *     it is more convenient to gather the library in one
  48  *     place, but since these pieces of code are also in
  49  *     the inner loops of output primitives, procedure call
  50  *     overhead is out of the question.
  51  *     See the author for a derivation if needed.
  52  */
  53 \f
  54
  55 /*
  56  *  In scan converting polygons, we want to choose those pixels
  57  *  which are inside the polygon.  Thus, we add .5 to the starting
  58  *  x coordinate for both left and right edges.  Now we choose the
  59  *  first pixel which is inside the pgon for the left edge and the
  60  *  first pixel which is outside the pgon for the right edge.
  61  *  Draw the left pixel, but not the right.
  62  *
  63  *  How to add .5 to the starting x coordinate:
  64  *      If the edge is moving to the right, then subtract dy from the
  65  *  error term from the general form of the algorithm.
  66  *      If the edge is moving to the left, then add dy to the error term.
  67  *
  68  *  The reason for the difference between edges moving to the left
  69  *  and edges moving to the right is simple:  If an edge is moving
  70  *  to the right, then we want the algorithm to flip immediately.
  71  *  If it is moving to the left, then we don't want it to flip until
  72  *  we traverse an entire pixel.
  73  */
  74 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
  75     int dx;      /* local storage */ \
  76 \
  77     /* \
  78      *  if the edge is horizontal, then it is ignored \
  79      *  and assumed not to be processed.  Otherwise, do this stuff. \
  80      */ \
  81     if ((dy) != 0) { \
  82         xStart = (x1); \
  83         dx = (x2) - xStart; \
  84         if (dx < 0) { \
  85             m = dx / (dy); \
  86             m1 = m - 1; \
  87             incr1 = -2 * dx + 2 * (dy) * m1; \
  88             incr2 = -2 * dx + 2 * (dy) * m; \
  89             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
  90         } else { \
  91             m = dx / (dy); \
  92             m1 = m + 1; \
  93             incr1 = 2 * dx - 2 * (dy) * m1; \
  94             incr2 = 2 * dx - 2 * (dy) * m; \
  95             d = -2 * m * (dy) + 2 * dx; \
  96         } \
  97     } \
  98 }
  99 \f
 100 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
 101     if (m1 > 0) { \
 102         if (d > 0) { \
 103             minval += m1; \
 104             d += incr1; \
 105         } \
 106         else { \
 107             minval += m; \
 108             d += incr2; \
 109         } \
 110     } else {\
 111         if (d >= 0) { \
 112             minval += m1; \
 113             d += incr1; \
 114         } \
 115         else { \
 116             minval += m; \
 117             d += incr2; \
 118         } \
 119     } \
 120 }
 121
 122 \f
 123 /*
 124  *     This structure contains all of the information needed
 125  *     to run the bresenham algorithm.
 126  *     The variables may be hardcoded into the declarations
 127  *     instead of using this structure to make use of
 128  *     register declarations.
 129  */
 130 typedef struct {
 131     int minor;         /* minor axis        */
 132     int d;           /* decision variable */
 133     int m, m1;       /* slope and slope+1 */
 134     int incr1, incr2; /* error increments */
 135 } BRESINFO;
 136
 137
 138 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
 139         BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \
 140                      bres.m, bres.m1, bres.incr1, bres.incr2)
 141
 142 #define BRESINCRPGONSTRUCT(bres) \
 143         BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2)
 144
 145
 146 #endif