1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
/* This file is part of the GNU libxmi package.
Copyright (C) 1985, 1986, 1987, 1988, 1989, X Consortium. For an
associated permission notice, see the accompanying file README-X.
GNU enhancements Copyright (C) 1998, 1999, 2000, 2005, Free Software
Foundation, Inc.
The GNU libxmi package is free software. You may redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software foundation; either version 2, or (at your
option) any later version.
The GNU libxmi package is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License along
with the GNU plotutils package; see the file COPYING. If not, write to
the Free Software Foundation, Inc., 51 Franklin St., Fifth Floor,
Boston, MA 02110-1301, USA. */
#ifndef SCANFILLINCLUDED
#define SCANFILLINCLUDED
/*
* miscanfill.h
*
* Written by Brian Kelleher; Jan 1985
*
* This file contains a few macros to help track
* the edge of a filled object. The object is assumed
* to be filled in scanline order, and thus the
* algorithm used is an extension of Bresenham's line
* drawing algorithm which assumes that y is always the
* major axis.
* Since these pieces of code are the same for any filled shape,
* it is more convenient to gather the library in one
* place, but since these pieces of code are also in
* the inner loops of output primitives, procedure call
* overhead is out of the question.
* See the author for a derivation if needed.
*/
/*
* In scan converting polygons, we want to choose those pixels
* which are inside the polygon. Thus, we add .5 to the starting
* x coordinate for both left and right edges. Now we choose the
* first pixel which is inside the polygon for the left edge and the
* first pixel which is outside the polygon for the right edge.
* Draw the left pixel, but not the right.
*
* How to add .5 to the starting x coordinate:
* If the edge is moving to the right, then subtract dy from the
* error term from the general form of the algorithm.
* If the edge is moving to the left, then add dy to the error term.
*
* The reason for the difference between edges moving to the left
* and edges moving to the right is simple: If an edge is moving
* to the right, then we want the algorithm to flip immediately.
* If it is moving to the left, then we don't want it to flip until
* we traverse an entire pixel.
*/
#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
int dx; /* local storage */ \
\
/* \
* if the edge is horizontal, then it is ignored \
* and assumed not to be processed. Otherwise, do this stuff. \
*/ \
if ((dy) != 0) { \
xStart = (x1); \
dx = (x2) - xStart; \
if (dx < 0) { \
m = dx / (dy); \
m1 = m - 1; \
incr1 = -2 * dx + 2 * (dy) * m1; \
incr2 = -2 * dx + 2 * (dy) * m; \
d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
} else { \
m = dx / (dy); \
m1 = m + 1; \
incr1 = 2 * dx - 2 * (dy) * m1; \
incr2 = 2 * dx - 2 * (dy) * m; \
d = -2 * m * (dy) + 2 * dx; \
} \
} \
}
#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
if (m1 > 0) { \
if (d > 0) { \
minval += m1; \
d += incr1; \
} \
else { \
minval += m; \
d += incr2; \
} \
} else {\
if (d >= 0) { \
minval += m1; \
d += incr1; \
} \
else { \
minval += m; \
d += incr2; \
} \
} \
}
/*
* This structure contains all of the information needed
* to run the bresenham algorithm.
* The variables may be hardcoded into the declarations
* instead of using this structure to make use of
* register declarations.
*/
typedef struct
{
int minor_axis; /* minor axis */
int d; /* decision variable */
int m, m1; /* slope and slope+1 */
int incr1, incr2; /* error increments */
} BRESINFO;
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
bres.m, bres.m1, bres.incr1, bres.incr2)
#define BRESINCRPGONSTRUCT(bres) \
BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
#endif
|
