miscanfill.h (4928B)
1 /* 2 3 Copyright 1987, 1998 The Open Group 4 5 Permission to use, copy, modify, distribute, and sell this software and its 6 documentation for any purpose is hereby granted without fee, provided that 7 the above copyright notice appear in all copies and that both that 8 copyright notice and this permission notice appear in supporting 9 documentation. 10 11 The above copyright notice and this permission notice shall be included 12 in all copies or substantial portions of the Software. 13 14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 15 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 16 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 17 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR 18 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 19 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 20 OTHER DEALINGS IN THE SOFTWARE. 21 22 Except as contained in this notice, the name of The Open Group shall 23 not be used in advertising or otherwise to promote the sale, use or 24 other dealings in this Software without prior written authorization 25 from The Open Group. 26 27 */ 28 29 #ifdef HAVE_DIX_CONFIG_H 30 #include <dix-config.h> 31 #endif 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 54 /* 55 * In scan converting polygons, we want to choose those pixels 56 * which are inside the polygon. Thus, we add .5 to the starting 57 * x coordinate for both left and right edges. Now we choose the 58 * first pixel which is inside the pgon for the left edge and the 59 * first pixel which is outside the pgon for the right edge. 60 * Draw the left pixel, but not the right. 61 * 62 * How to add .5 to the starting x coordinate: 63 * If the edge is moving to the right, then subtract dy from the 64 * error term from the general form of the algorithm. 65 * If the edge is moving to the left, then add dy to the error term. 66 * 67 * The reason for the difference between edges moving to the left 68 * and edges moving to the right is simple: If an edge is moving 69 * to the right, then we want the algorithm to flip immediately. 70 * If it is moving to the left, then we don't want it to flip until 71 * we traverse an entire pixel. 72 */ 73 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ 74 int dx; /* local storage */ \ 75 \ 76 /* \ 77 * if the edge is horizontal, then it is ignored \ 78 * and assumed not to be processed. Otherwise, do this stuff. \ 79 */ \ 80 if ((dy) != 0) { \ 81 xStart = (x1); \ 82 dx = (x2) - xStart; \ 83 if (dx < 0) { \ 84 m = dx / (dy); \ 85 m1 = m - 1; \ 86 incr1 = -2 * dx + 2 * (dy) * m1; \ 87 incr2 = -2 * dx + 2 * (dy) * m; \ 88 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ 89 } else { \ 90 m = dx / (dy); \ 91 m1 = m + 1; \ 92 incr1 = 2 * dx - 2 * (dy) * m1; \ 93 incr2 = 2 * dx - 2 * (dy) * m; \ 94 d = -2 * m * (dy) + 2 * dx; \ 95 } \ 96 } \ 97 } 98 99 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ 100 if (m1 > 0) { \ 101 if (d > 0) { \ 102 minval += m1; \ 103 d += incr1; \ 104 } \ 105 else { \ 106 minval += m; \ 107 d += incr2; \ 108 } \ 109 } else {\ 110 if (d >= 0) { \ 111 minval += m1; \ 112 d += incr1; \ 113 } \ 114 else { \ 115 minval += m; \ 116 d += incr2; \ 117 } \ 118 } \ 119 } 120 121 /* 122 * This structure contains all of the information needed 123 * to run the bresenham algorithm. 124 * The variables may be hardcoded into the declarations 125 * instead of using this structure to make use of 126 * register declarations. 127 */ 128 typedef struct { 129 int minor; /* minor axis */ 130 int d; /* decision variable */ 131 int m, m1; /* slope and slope+1 */ 132 int incr1, incr2; /* error increments */ 133 } BRESINFO; 134 135 #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \ 136 BRESINITPGON(dmaj, min1, min2, bres.minor, bres.d, \ 137 bres.m, bres.m1, bres.incr1, bres.incr2) 138 139 #define BRESINCRPGONSTRUCT(bres) \ 140 BRESINCRPGON(bres.d, bres.minor, bres.m, bres.m1, bres.incr1, bres.incr2) 141 142 #endif