2 * Copyright © 2023 Keith Packard <keithp@keithp.com>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
14 * You should have received a copy of the GNU General Public License along
15 * with this program; if not, write to the Free Software Foundation, Inc.,
16 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
20 #include <ao_draw_int.h>
25 const struct ao_transform ao_identity = {
26 .x_scale = 1.0f, .x_off = 0.0f,
27 .y_scale = 1.0f, .y_off = 0.0f
31 _x(const struct ao_coord *coords,
32 const struct ao_transform *transform,
35 return ao_t_x_c(&coords[coord], transform);
39 _y(const struct ao_coord *coords,
40 const struct ao_transform *transform,
43 return ao_t_y_c(&coords[coord], transform);
47 _next(uint16_t ncoords, uint16_t edge)
49 return edge == ncoords - 1 ? 0 : edge + 1;
53 * Return if the given edge is 'live' at the specified y coordinate.
54 * That means the edge spans the y value. Horizontal lines are never
58 ao_edge_live(const struct ao_coord *coords,
60 const struct ao_transform *transform,
64 float y1 = _y(coords, transform, edge);
65 float y2 = _y(coords, transform, _next(ncoords, edge));
68 return y2 <= y && y < y1;
70 return y1 <= y && y < y2;
74 * Compute the X coordinate for a given edge at a specified y value
77 ao_edge_x(const struct ao_coord *coords,
79 const struct ao_transform *transform,
83 uint16_t next_edge = _next(ncoords, edge);
84 float x1 = _x(coords, transform, edge);
85 float x2 = _x(coords, transform, next_edge);
86 float y1 = _y(coords, transform, edge);
87 float y2 = _y(coords, transform, next_edge);
92 return (int16_t) (x1 + (off_y * dx) / dy + 0.5f);
101 * Find the next X/edge pair along the given scanline. If two edges
102 * have the same X value, return them in edge index order. Returns false
103 * if there are no more edges.
106 ao_next_x(const struct ao_coord *coords,
108 const struct ao_transform *transform,
109 struct next_x *this_x,
113 float next_x = FLT_MAX;
114 uint16_t next_edge = UINT16_MAX;
117 for (edge = 0; edge < ncoords; edge++) {
118 if (ao_edge_live(coords, ncoords, transform, edge, y)) {
119 float nx = ao_edge_x(coords, ncoords, transform, edge, y);
120 if (this_x->x < nx || (this_x->x == nx && this_x->edge < edge)) {
130 this_x->edge = next_edge;
135 * Fill a span at the specified y coordinate from x1 to x2
138 ao_span(const struct ao_bitmap *dst,
145 int16_t ix1 = (int16_t) floorf(x1 + 0.5f);
146 int16_t ix2 = (int16_t) floorf(x2 + 0.5f);
147 int16_t iy = (int16_t) y;
149 ao_clip(ix1, 0, dst->width);
150 ao_clip(ix2, 0, dst->width);
151 ao_solid(ao_and(rop, fill),
153 dst->base + iy * dst->stride,
161 * Compute the 'winding' for the specified edge. Winding is simply an
162 * indication of whether the edge goes upwards or downwards
165 ao_wind(const struct ao_coord *coords,
167 const struct ao_transform *transform,
170 uint16_t next_edge = _next(ncoords, edge);
171 return _y(coords, transform, edge) > _y(coords, transform, next_edge) ? 1 : -1;
175 * Fill the specified polygon with non-zero winding rule
178 ao_poly(struct ao_bitmap *dst,
179 const struct ao_coord *coords,
181 const struct ao_transform *transform,
190 struct next_x next_x;
194 transform = &ao_identity;
197 * Find the limits of the polygon
199 x_min = x_max = _x(coords, transform, 0);
200 y_min = y_max = _y(coords, transform, 0);
201 for (edge = 1; edge < ncoords; edge++) {
202 x = _x(coords, transform, edge);
207 y = _y(coords, transform, edge);
214 x_min = floorf(x_min);
215 x_max = ceilf(x_max);
216 ao_clip(x_min, 0, dst->width);
217 ao_clip(x_max, 0, dst->width);
219 y_min = floorf(y_min);
220 y_max = ceilf(y_max);
221 ao_clip(y_min, 0, dst->height);
222 ao_clip(y_max, 0, dst->height);
224 ao_damage(dst, (int16_t) x_min, (int16_t) y_min, (int16_t) x_max, (int16_t) y_max);
227 * Walk each scanline in the range and fill included spans
229 for (y = y_min; y < y_max; y++) {
231 next_x.x = INT16_MIN;
234 while (ao_next_x(coords, ncoords, transform, &next_x, y)) {
237 * Fill the previous span if winding is
241 ao_span(dst, x, next_x.x, y, fill, rop);
243 /* Adjust winding for the current span */
244 wind += ao_wind(coords, ncoords, transform, next_x.edge);
246 /* Step to next span start x value */