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"
26 * Return if the given edge is 'live' at the specified y coordinate.
27 * That means the edge spans the y value. Horizontal lines are never
31 ao_edge_live(const struct ao_coord *coords,
36 int next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
37 float y1 = coords[edge].y;
38 float y2 = coords[next_edge].y;
41 return y2 <= y && y < y1;
43 return y1 <= y && y < y2;
47 * Compute the X coordinate for a given edge at a specified y value
50 ao_edge_x(const struct ao_coord *coords,
55 int next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
56 float x1 = coords[edge].x;
57 float x2 = coords[next_edge].x;
58 float y1 = coords[edge].y;
59 float y2 = coords[next_edge].y;
64 return x1 + (off_y * dx) / dy;
73 * Find the next X/edge pair along the given scanline. If two edges
74 * have the same X value, return them in edge index order. Returns false
75 * if there are no more edges.
78 ao_next_x(const struct ao_coord *coords,
80 struct next_x *this_x,
84 float next_x = FLT_MAX;
85 uint16_t next_edge = UINT16_MAX;
88 for (edge = 0; edge < ncoords; edge++) {
89 if (ao_edge_live(coords, ncoords, edge, y)) {
90 float nx = ao_edge_x(coords, ncoords, edge, y);
91 if (this_x->x < nx || (this_x->x == nx && this_x->edge < edge)) {
101 this_x->edge = next_edge;
106 * Fill a span at the specified y coordinate from x1 to x2
109 ao_span(const struct ao_bitmap *dst,
116 int16_t ix1 = floorf(x1 + 0.5f);
117 int16_t ix2 = floorf(x2 + 0.5f);
118 int16_t iy = (int16_t) y;
119 ao_rect(dst, ix1, iy, ix2 - ix1, 1, fill, rop);
123 * Compute the 'winding' for the specified edge. Winding is simply an
124 * indication of whether the edge goes upwards or downwards
127 ao_wind(const struct ao_coord *coords,
131 uint16_t next_edge = (edge == ncoords - 1) ? 0 : edge + 1;
132 return coords[edge].y > coords[next_edge].y ? 1 : -1;
136 * Fill the specified polygon with non-zero winding rule
139 ao_poly(const struct ao_bitmap *dst,
140 const struct ao_coord *coords,
149 struct next_x next_x;
153 * Find the y limits of the polygon
155 y_min = y_max = coords[0].y;
156 for (edge = 1; edge < ncoords; edge++) {
164 y_min = floorf(y_min);
165 y_max = ceilf(y_max);
168 * Walk each scanline in the range and fill included spans
170 for (y = y_min; y < y_max; y++) {
172 next_x.x = INT16_MIN;
175 while (ao_next_x(coords, ncoords, &next_x, y)) {
178 * Fill the previous span if winding is
182 ao_span(dst, x, next_x.x, y, fill, rop);
184 /* Adjust winding for the current span */
185 wind += ao_wind(coords, ncoords, next_x.edge);
187 /* Step to next span start x value */