1 /* This file is part of the GNU libxmi package. 2 3 Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an 4 associated permission notice, see the accompanying file README-X. 5 6 GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software 7 Foundation, Inc. 8 9 The GNU libxmi package is free software. You may redistribute it 10 and/or modify it under the terms of the GNU General Public License as 11 published by the Free Software foundation; either version 2, or (at your 12 option) any later version. 13 14 The GNU libxmi package is distributed in the hope that it will be 15 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 17 General Public License for more details. 18 19 You should have received a copy of the GNU General Public License along 20 with the GNU plotutils package; see the file COPYING. If not, write to 21 the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor, 22 Boston, MA 02110-1301, USA. */ 23 24 /* Author: Keith Packard, MIT X Consortium */ 25 26 /* definitions related to filling of convex polygons, used in code for 27 * drawing of wide lines (with caps/joins) via span merging 28 */ 29 30 /* Structure used for moving along left and right edges of polygons via the 31 midpoint line algorithm. The algorithm: increment y, (height-1) times. 32 At each step, increment e by dx. If this makes e positive, also 33 subtract dy. Corresponding change to x: add stepx to x, and (if dy 34 needed to be subtracted from e), also add signdx to x. */ 35 36 typedef struct 37 { 38 unsigned int height; /* number of scanlines in edge */ 39 int x; /* starting x coordinate of edge */ 40 int stepx; /* fixed integer dx (usually 0) */ 41 int signdx; /* additional (optional) integer dx */ 42 int e; /* initial value for decision variable */ 43 int dy; /* dy/dx is (rational) slope of edge */ 44 int dx; 45 } PolyEdge; 46 47 /* 48 * types for general polygon routines 49 */ 50 51 typedef struct 52 { 53 double x, y; 54 } PolyVertex; 55 56 typedef struct 57 { 58 int dx, dy; /* dy/dx is (rational) slope */ 59 double k; /* x0 * dy - y0 * dx */ 60 } PolySlope; 61 62 /* 63 * Line face, used in constructing additional cap/join polygons 64 */ 65 66 typedef struct 67 { 68 double xa, ya; /* endpoint of line face (rel. to (x,y)) */ 69 int dx, dy; /* (dx,dy) points into line (a convention) */ 70 int x, y; /* line end, i.e. center of face */ 71 double k; /* xa * dy - ya * dx */ 72 } LineFace; 73 74 75 /* Macros for stepping around a convex polygon (i.e. downward from top, 76 along the sequence of `left edges' and `right edges') */ 77 78 /* load fields from next left edge in list */ 79 #define MIPOLYRELOADLEFT if (!left_height && left_count) { \ 80 left_height = left->height; \ 81 left_x = left->x; \ 82 left_stepx = left->stepx; \ 83 left_signdx = left->signdx; \ 84 left_e = left->e; \ 85 left_dy = left->dy; \ 86 left_dx = left->dx; \ 87 --left_count; \ 88 ++left; \ 89 } 90 91 /* load fields from next right edge in list */ 92 #define MIPOLYRELOADRIGHT if (!right_height && right_count) { \ 93 right_height = right->height; \ 94 right_x = right->x; \ 95 right_stepx = right->stepx; \ 96 right_signdx = right->signdx; \ 97 right_e = right->e; \ 98 right_dy = right->dy; \ 99 right_dx = right->dx; \ 100 --right_count; \ 101 ++right; \ 102 } 103 104 /* Update steps in edge traversal via midpoint line algorithm */ 105 106 /* step along left edge (modify x appropriately as y is incremented by 1) */ 107 #define MIPOLYSTEPLEFT left_x += left_stepx; \ 108 left_e += left_dx; \ 109 if (left_e > 0) \ 110 { \ 111 left_x += left_signdx; \ 112 left_e -= left_dy; \ 113 } 114 115 /* step along right edge (modify x appropriately as y is incremented by 1) */ 116 #define MIPOLYSTEPRIGHT right_x += right_stepx; \ 117 right_e += right_dx; \ 118 if (right_e > 0) \ 119 { \ 120 right_x += right_signdx; \ 121 right_e -= right_dy; \ 122 } 123