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
|
Edges come in different type:
*horizontal*
which are ignored. This is when dy is 0
*vertical*
which is when the edge is vertical
*short* which is when
dy and dx are both shorter than say 8 pixels.
and also dx / dy < 4 <=> dx < 4 * dy
Probably further split into *short forward/backward*
to avoid the extra test. Or even
short NORTH_WEST
short NORTH_EAST
short SOUTH_WEST
short SOUTH_EAST
since we do need to keep track of up/down for winding
rule purposes.
*long* otherwise
*uninitialized*
which is before the edge has been added to the aet
An edge can be stepped an arbitrary amount, or it can be stepped one step.
A *long* edge uses runslice (with a division). It is stored as a
pointer to allocated memory, since we assume these will be rare.
A *short* edge uses bresenham. It also does internal book keeping in
32 bit integers.
All edges
Potential optimizations:
- Polygons could store the edges as a kind of BSP tree to allow quick
access to arbitrary sub-rectangles.
- Rectilinear polygons could be recognized
- Rectilinear integer-aligned polygons could be recognized.
Write it top-down.
rasterize (polygon, int x, int y, int width, int height)
{
sample_t yi;
get = get_global_edges (polygon);
yi = next_sample_y (y); // yi = y << 8;
aet = update_aet (aet, yi, scanline=true);
/* For each scanline */
while (fixed_to_int (yi) < height)
{
/* later:
switch (aet->state)
case VERTICALS/NON_OVERLAP/etc.
*/
for (i = 0; i < N_GRID_Y - 1; ++i)
{
for_each (aet)
small step edge (emit);
yi = small_step_y (yi);
aet = update_aet (aet, scanline=false);
}
for_each (aet)
big_step edge (emit);
yi = big_step_y (yi); // yi = fixed_floor (yi + fixed_1);
aet = update_aet (yi, scanline=true);
}
}
update_aet (yi)
for each global edge
if y0 <= yi
add to aet
initialize
long_step (yi - y0)
else
break; /* global edges are sorted in YX order */
sort aet
Later on, update_aet() should keep track of various properties:
- All edges vertical for one or more scanlines
- The edges are longer than one scanline, and they don't cross
each other.
basically, if the next slope is bigger than or equal
to the current one's:
if (next dx/dy >= current dx dy)
which is equivlaent to
next dx * current dy >= current dx * next dy
Since dy's are always positive.
If this is the case, we can track it for a full range
of scanlines.
- How many active edges there are. If there aren't many, then
we can use a simpler sort such as insertion sort.
Note this means update_aet() should do two different things
depending on whether it's moving between subrows and scanlines.
Testing:
- Generate a ton of polygons in a naive way. Make sure they never
change.
- Rasterize polygons that completely cover a rectangle. Make sure
there are no seams.
- Rasterize on polygon that consists of many pieces that together
cover an entire rectangle.
|
