1// This file is part of SmallBASIC
2//
3// PolyLineFill
4// See: "Zen of graphics programming", Chapter 24. L24-1.C.
5//
6// This program is distributed under the terms of the GPL v2.0 or later
7// Download the GNU Public License (GPL) from www.gnu.org
8//
9// Copyright(C) 2000 Nicholas Christopoulos
10
11#include "common/sys.h"
12#include "common/device.h"
13
14struct EdgeState {
15 struct EdgeState *NextEdge;
16 int X, StartY;
17 int WholePixelXMove;
18 int XDirection;
19 int ErrorTerm;
20 int ErrorTermAdjUp;
21 int ErrorTermAdjDown;
22 int Count;
23};
24// 18bytes
25
26void pf_build_GET(ipt_t *, int, struct EdgeState *);
27void pf_move_xsorted_AET(int);
28void pf_scan_out_AET(int);
29void pf_advance_AET(void);
30void pf_xsort_AET(void);
31
32/*
33 * Pointers to global edge table (GET) and active edge table (AET)
34 */
35static struct EdgeState *GETPtr;
36static struct EdgeState *AETPtr;
37
38/*
39 * FillPoly
40 *
41 * XOffset, YOffset Coordinates to draw the polygon.
42 * *VertexList The array of the points.
43 * ptNum The number of points.
44 * Color The color.
45 */
46void dev_pfill(ipt_t * pts, int ptNum) {
47 struct EdgeState *EdgeTableBuffer;
48 int CurrentY;
49
50 /*
51 * It takes a minimum of 3 vertices to cause any pixels to be
52 * drawn; reject polygons that are guaranteed to be invisible
53 */
54 if (ptNum < 3)
55 return;
56
57 EdgeTableBuffer = (struct EdgeState *) malloc(sizeof(struct EdgeState) * (ptNum + 1));
58
59 /*
60 * Build the global edge table.
61 */
62
63 pf_build_GET(pts, ptNum, EdgeTableBuffer);
64
65 /*
66 * Scan down through the polygon edges, one scan line at a time,
67 * so long as at least one edge remains in either the GET or AET
68 */
69 AETPtr = NULL; /* initialize the active edge table to empty */
70 if (GETPtr != NULL) {
71 CurrentY = GETPtr->StartY; /* start at the top polygon vertex */
72 } else {
73 CurrentY = 0;
74 }
75 while ((GETPtr != NULL) || (AETPtr != NULL)) {
76 pf_move_xsorted_AET(CurrentY); /* update AET for this scan line */
77 pf_scan_out_AET(CurrentY); /* draw this scan line from AET */
78 pf_advance_AET(); /* advance AET edges 1 scan line */
79 pf_xsort_AET(); /* resort on X */
80 CurrentY++; /* advance to the next scan line */
81 }
82
83 free(EdgeTableBuffer);
84}
85
86/*
87 * Creates a GET in the buffer pointed to by NextFreeEdgeStruc from
88 * the vertex list. Edge endpoints are flipped, if necessary, to
89 * guarantee all edges go top to bottom. The GET is sorted primarily
90 * by ascending Y start coordinate, and secondarily by ascending X
91 * start coordinate within edges with common Y coordinates
92 */
93void pf_build_GET(ipt_t * VertexPtr, int ptNum, struct EdgeState *NextFreeEdgeStruc) {
94 int i, StartX, StartY, EndX, EndY, DeltaY, DeltaX, Width, temp;
95 struct EdgeState *NewEdgePtr;
96 struct EdgeState *FollowingEdge;
97 struct EdgeState **FollowingEdgeLink;
98
99 /*
100 * Scan through the vertex list and put all non-0-height edges into
101 * the GET, sorted by increasing Y start coordinate
102 */
103 GETPtr = NULL; /* initialize the global edge table to empty */
104 for (i = 0; i < ptNum; i++) {
105 /*
106 * Calculate the edge height and width
107 */
108 StartX = VertexPtr[i].x;
109 StartY = VertexPtr[i].y;
110 /*
111 * The edge runs from the current point to the previous one
112 */
113 if (i == 0) {
114 /*
115 * Wrap back around to the end of the list
116 */
117 EndX = VertexPtr[ptNum - 1].x;
118 EndY = VertexPtr[ptNum - 1].y;
119 } else {
120 EndX = VertexPtr[i - 1].x;
121 EndY = VertexPtr[i - 1].y;
122 }
123 /*
124 * Make sure the edge runs top to bottom
125 */
126 if (StartY > EndY) {
127 SWAP(StartX, EndX, temp);
128 SWAP(StartY, EndY, temp);
129 }
130 /*
131 * Skip if this can't ever be an active edge (has 0 height)
132 */
133 if ((DeltaY = EndY - StartY) != 0) {
134 /*
135 * Allocate space for this edge's info, and fill in the structure
136 */
137 NewEdgePtr = NextFreeEdgeStruc++;
138 NewEdgePtr->XDirection = /* direction in which X moves */
139 ((DeltaX = EndX - StartX) > 0) ? 1 : -1;
140 Width = abs(DeltaX);
141 NewEdgePtr->X = StartX;
142 NewEdgePtr->StartY = StartY;
143 NewEdgePtr->Count = DeltaY;
144 NewEdgePtr->ErrorTermAdjDown = DeltaY;
145 if (DeltaX >= 0) /* initial error term going L->R */
146 NewEdgePtr->ErrorTerm = 0;
147 else
148 /* initial error term going R->L */
149 NewEdgePtr->ErrorTerm = -DeltaY + 1;
150 if (DeltaY >= Width) { /* Y-major edge */
151 NewEdgePtr->WholePixelXMove = 0;
152 NewEdgePtr->ErrorTermAdjUp = Width;
153 } else { /* X-major edge */
154 NewEdgePtr->WholePixelXMove = (Width / DeltaY) * NewEdgePtr->XDirection;
155 NewEdgePtr->ErrorTermAdjUp = Width % DeltaY;
156 }
157 /*
158 * Link the new edge into the GET so that the edge list is still sorted
159 * by Y coordinate, and by X coordinate for all edges with the same Y
160 * coordinate
161 */
162 FollowingEdgeLink = &GETPtr;
163 for (;;) {
164 FollowingEdge = *FollowingEdgeLink;
165 if ((FollowingEdge == NULL) || (FollowingEdge->StartY > StartY)
166 || ((FollowingEdge->StartY == StartY) && (FollowingEdge->X >= StartX))) {
167 NewEdgePtr->NextEdge = FollowingEdge;
168 *FollowingEdgeLink = NewEdgePtr;
169 break;
170 }
171 FollowingEdgeLink = &FollowingEdge->NextEdge;
172 }
173 }
174 }
175}
176
177/*
178 * Sorts all edges currently in the active edge table into ascending
179 * order of current X coordinates
180 */
181void pf_xsort_AET() {
182 struct EdgeState *CurrentEdge;
183 struct EdgeState **CurrentEdgePtr;
184 struct EdgeState *TempEdge;
185 int SwapOccurred;
186
187 /*
188 * Scan through the AET and swap any adjacent edges for which the * second
189 * edge is at a lower current X coord than the first edge. Repeat until no
190 * further swapping is needed
191 */
192 if (AETPtr != NULL) {
193 do {
194 SwapOccurred = 0;
195 CurrentEdgePtr = &AETPtr;
196 while ((CurrentEdge = *CurrentEdgePtr)->NextEdge != NULL) {
197 if (CurrentEdge->X > CurrentEdge->NextEdge->X) {
198 /*
199 * The second edge has a lower X than the first; swap them in the AET
200 */
201 TempEdge = CurrentEdge->NextEdge->NextEdge;
202 *CurrentEdgePtr = CurrentEdge->NextEdge;
203 CurrentEdge->NextEdge->NextEdge = CurrentEdge;
204 CurrentEdge->NextEdge = TempEdge;
205 SwapOccurred = 1;
206 }
207 CurrentEdgePtr = &(*CurrentEdgePtr)->NextEdge;
208 }
209 } while (SwapOccurred != 0);
210 }
211}
212
213/*
214 * Advances each edge in the AET by one scan line.
215 * Removes edges that have been fully scanned.
216 */
217void pf_advance_AET() {
218 struct EdgeState *CurrentEdge;
219 struct EdgeState **CurrentEdgePtr;
220
221 /*
222 * Count down and remove or advance each edge in the AET
223 */
224 CurrentEdgePtr = &AETPtr;
225 while ((CurrentEdge = *CurrentEdgePtr) != NULL) {
226 /*
227 * Count off one scan line for this edge
228 */
229 if ((--(CurrentEdge->Count)) == 0) {
230 /*
231 * This edge is finished, so remove it from the AET
232 */
233 *CurrentEdgePtr = CurrentEdge->NextEdge;
234 } else {
235 /*
236 * Advance the edge's X coordinate by minimum move
237 */
238 CurrentEdge->X += CurrentEdge->WholePixelXMove;
239 /*
240 * Determine whether it's time for X to advance one extra
241 */
242 if ((CurrentEdge->ErrorTerm += CurrentEdge->ErrorTermAdjUp) > 0) {
243 CurrentEdge->X += CurrentEdge->XDirection;
244 CurrentEdge->ErrorTerm -= CurrentEdge->ErrorTermAdjDown;
245 }
246 CurrentEdgePtr = &CurrentEdge->NextEdge;
247 }
248 }
249}
250
251/*
252 * Moves all edges that start at the specified Y coordinate from the
253 * GET to the AET, maintaining the X sorting of the AET.
254 */
255void pf_move_xsorted_AET(int YToMove) {
256 struct EdgeState *AETEdge;
257 struct EdgeState **AETEdgePtr;
258 struct EdgeState *TempEdge;
259 int CurrentX;
260
261 /*
262 * The GET is Y sorted. Any edges that start at the desired Y
263 * coordinate will be first in the GET, so we'll move edges from
264 * the GET to AET until the first edge left in the GET is no longer
265 * at the desired Y coordinate. Also, the GET is X sorted within
266 * each Y coordinate, so each successive edge we add to the AET is
267 * guaranteed to belong later in the AET than the one just added
268 */
269 AETEdgePtr = &AETPtr;
270 while ((GETPtr != NULL) && (GETPtr->StartY == YToMove)) {
271 CurrentX = GETPtr->X;
272 /*
273 * Link the new edge into the AET so that the AET is still sorted by X
274 * coordinate
275 */
276 while (1) {
277 AETEdge = *AETEdgePtr;
278 if ((AETEdge == NULL) || (AETEdge->X >= CurrentX)) {
279 TempEdge = GETPtr->NextEdge;
280 *AETEdgePtr = GETPtr; /* link the edge into the AET */
281 GETPtr->NextEdge = AETEdge;
282 AETEdgePtr = &GETPtr->NextEdge;
283 GETPtr = TempEdge; /* unlink the edge from the GET */
284 break;
285 } else {
286 AETEdgePtr = &AETEdge->NextEdge;
287 }
288 }
289 }
290}
291
292/*
293 * Fills the scan line described by the current AET at the specified Y
294 * coordinate in the specified color, using the odd/even fill rule.
295 */
296void pf_scan_out_AET(int YToScan) {
297 int LeftX;
298 struct EdgeState *CurrentEdge;
299
300 /*
301 * Scan through the AET, drawing line segments as each pair of edge
302 * crossings is encountered. The nearest pixel on or to the right
303 * of left edges is drawn, and the nearest pixel to the left of but
304 * not on right edges is drawn
305 */
306 CurrentEdge = AETPtr;
307 while (CurrentEdge != NULL) {
308 LeftX = CurrentEdge->X;
309 CurrentEdge = CurrentEdge->NextEdge;
310 /*
311 * 8/5/95, NDC: Zen's bug
312 */
313 if (CurrentEdge->X)
314 dev_line(LeftX, YToScan, CurrentEdge->X - 1, YToScan);
315 CurrentEdge = CurrentEdge->NextEdge;
316 }
317}
318