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
|
/* Author: Keith Packard, MIT X Consortium */
/* definitions related to filling of convex polygons, used in code for
* drawing of wide lines (with caps/joins) via span merging
*/
/* Structure used for moving along left and right edges of polygons via the
midpoint line algorithm. The algorithm: increment y, (height-1) times.
At each step, increment e by dx. If this makes e positive, also
subtract dy. Corresponding change to x: add stepx to x, and (if dy
needed to be subtracted from e), also add signdx to x. */
typedef struct
{
unsigned int height; /* number of scanlines in edge */
int x; /* starting x coordinate of edge */
int stepx; /* fixed integer dx (usually 0) */
int signdx; /* additional (optional) integer dx */
int e; /* initial value for decision variable */
int dy; /* dy/dx is (rational) slope of edge */
int dx;
} PolyEdge;
/*
* types for general polygon routines
*/
typedef struct
{
double x, y;
} PolyVertex;
typedef struct
{
int dx, dy; /* dy/dx is (rational) slope */
double k; /* x0 * dy - y0 * dx */
} PolySlope;
/*
* Line face, used in constructing additional cap/join polygons
*/
typedef struct
{
double xa, ya; /* endpoint of line face (rel. to (x,y)) */
int dx, dy; /* (dx,dy) points into line (a convention) */
int x, y; /* line end, i.e. center of face */
double k; /* xa * dy - ya * dx */
} LineFace;
/* Macros for stepping around a convex polygon (i.e. downward from top,
along the sequence of `left edges' and `right edges') */
/* load fields from next left edge in list */
#define MIPOLYRELOADLEFT if (!left_height && left_count) { \
left_height = left->height; \
left_x = left->x; \
left_stepx = left->stepx; \
left_signdx = left->signdx; \
left_e = left->e; \
left_dy = left->dy; \
left_dx = left->dx; \
--left_count; \
++left; \
}
/* load fields from next right edge in list */
#define MIPOLYRELOADRIGHT if (!right_height && right_count) { \
right_height = right->height; \
right_x = right->x; \
right_stepx = right->stepx; \
right_signdx = right->signdx; \
right_e = right->e; \
right_dy = right->dy; \
right_dx = right->dx; \
--right_count; \
++right; \
}
/* Update steps in edge traversal via midpoint line algorithm */
/* step along left edge (modify x appropriately as y is incremented by 1) */
#define MIPOLYSTEPLEFT left_x += left_stepx; \
left_e += left_dx; \
if (left_e > 0) \
{ \
left_x += left_signdx; \
left_e -= left_dy; \
}
/* step along right edge (modify x appropriately as y is incremented by 1) */
#define MIPOLYSTEPRIGHT right_x += right_stepx; \
right_e += right_dx; \
if (right_e > 0) \
{ \
right_x += right_signdx; \
right_e -= right_dy; \
}
|
