1 /**
2 ** scanpoly.c ---- scan fill an arbitrary polygon
3 **
4 ** Copyright (c) 1995 Csaba Biegl, 820 Stirrup Dr, Nashville, TN 37221
5 ** [e-mail: csaba@vuse.vanderbilt.edu]
6 **
7 ** This file is part of the GRX graphics library.
8 **
9 ** The GRX graphics library is free software; you can redistribute it
10 ** and/or modify it under some conditions; see the "copying.grx" file
11 ** for details.
12 **
13 ** This library is distributed in the hope that it will be useful,
14 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
15 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 **
17 **/
18
19 #include "libgrx.h"
20 #include "shapes.h"
21 #include "allocate.h"
22 #include "clipping.h"
23 #include "arith.h"
24 #include "shape/polyedge.h"
25
26 typedef enum {
27 inactive, /* not reached yet */
28 active, /* currently contributes point */
29 passed /* above current scan line */
30 } edgestat;
31
32 typedef struct {
33 edgestat status; /* status of this edge */
34 polyedge e; /* the edge data */
35 } edge;
36
37 typedef struct _scan {
38 struct _scan *next; /* next segment/point in the list */
39 int x1,x2; /* endpoints of this filled segment */
40 } scan;
41
42 #define add_scanpoint(List,Scp,X1,X2) { \
43 scan *prev = NULL; \
44 scan *work = List; \
45 while(work != NULL) { \
46 if(work->x1 > X1) break; \
47 prev = work; \
48 work = work->next; \
49 } \
50 Scp->x1 = X1; \
51 Scp->x2 = X2; \
52 Scp->next = work; \
53 if(prev) prev->next = Scp; \
54 else List = Scp; \
55 }
56
57 #define add_scansegment(List,Scp,X1,X2) { \
58 scan *prev = NULL; \
59 scan *work = List; \
60 int overlap = FALSE; \
61 while(work != NULL) { \
62 if((work->x1 <= X2) && (X1 <= work->x2)) { \
63 overlap = TRUE; \
64 if(X1 < work->x1) work->x1 = X1; \
65 if(X2 > work->x2) { \
66 prev = work; \
67 while((work = work->next) != NULL) { \
68 if(work->x1 > X2) break; \
69 if(work->x2 > X2) X2 = work->x2; \
70 } \
71 prev->x2 = X2; \
72 prev->next = work; \
73 } \
74 break; \
75 } \
76 if(work->x1 > X2) break; \
77 prev = work; \
78 work = work->next; \
79 } \
80 if(!overlap) { \
81 Scp->x1 = X1; \
82 Scp->x2 = X2; \
83 Scp->next = work; \
84 if(prev) prev->next = Scp; \
85 else List = Scp; \
86 } \
87 }
88
_GrScanPolygon(int n,int pt[][2],GrFiller * f,GrFillArg c)89 void _GrScanPolygon(int n,int pt[][2],GrFiller *f,GrFillArg c)
90 {
91 edge *edges,*ep;
92 scan *scans,*sp,*points,*segments;
93 int xmin,xmax,ymin,ymax;
94 int ypos,nedges;
95 if((n > 1) &&
96 (pt[0][0] == pt[n-1][0]) &&
97 (pt[0][1] == pt[n-1][1])) {
98 n--;
99 }
100 if(n < 1) {
101 return;
102 }
103 setup_ALLOC();
104 edges = (edge *)ALLOC(sizeof(edge) * (n + 2));
105 scans = (scan *)ALLOC(sizeof(scan) * (n + 8));
106 if(edges && scans) {
107 /*
108 * Build the edge table. Store only those edges which are in the
109 * valid Y region. Clip them in Y if necessary. Store them with
110 * the endpoints ordered by Y in the edge table.
111 */
112 int prevx = xmin = xmax = pt[0][0];
113 int prevy = ymin = ymax = pt[0][1];
114 nedges = 0;
115 ep = edges;
116 while(--n >= 0) {
117 if(pt[n][1] >= prevy) {
118 ep->e.x = prevx;
119 ep->e.y = prevy;
120 ep->e.xlast = prevx = pt[n][0];
121 ep->e.ylast = prevy = pt[n][1];
122 }
123 else {
124 ep->e.xlast = prevx;
125 ep->e.ylast = prevy;
126 ep->e.x = prevx = pt[n][0];
127 ep->e.y = prevy = pt[n][1];
128 }
129 if((ep->e.y > GrHighY()) || (ep->e.ylast < GrLowY())) continue;
130 clip_line_ymin(CURC,ep->e.x,ep->e.y,ep->e.xlast,ep->e.ylast);
131 if(ymin > ep->e.y) ymin = ep->e.y;
132 if(ymax < ep->e.ylast) ymax = ep->e.ylast;
133 if(xmin > ep->e.x) xmin = ep->e.x;
134 if(xmax < ep->e.xlast) xmax = ep->e.xlast;
135 setup_edge(&ep->e);
136 ep->status = inactive;
137 nedges++;
138 ep++;
139 }
140 if((nedges > 0) && (xmin <= GrHighX()) && (xmax >= GrLowX())) {
141 if(xmin < GrLowX()) xmin = GrLowX();
142 if(ymin < GrLowY()) ymin = GrLowY();
143 if(xmax > GrHighX()) xmax = GrHighX();
144 if(ymax > GrHighY()) ymax = GrHighY();
145 mouse_block(CURC,xmin,ymin,xmax,ymax);
146 /*
147 * Scan for every row between ymin and ymax.
148 * Build a linked list of disjoint segments to fill. Rules:
149 * (1) a horizontal edge in the row contributes a segment
150 * (2) any other edge crossing the row contributes a point
151 * (3) every segment between even and odd points is filled
152 */
153 for(ypos = ymin; ypos <= ymax; ypos++) {
154 sp = scans;
155 points = NULL;
156 segments = NULL;
157 for(n = nedges,ep = edges; --n >= 0; ep++) {
158 switch(ep->status) {
159 case inactive:
160 if(ep->e.y != ypos) break;
161 if(ep->e.dy == 0) {
162 ep->status = passed;
163 xmin = ep->e.x;
164 xmax = ep->e.xlast;
165 isort(xmin,xmax);
166 add_scansegment(segments,sp,xmin,xmax);
167 sp++;
168 break;
169 }
170 ep->status = active;
171 case active:
172 xmin = xmax = ep->e.x;
173 if(ep->e.ylast == ypos) {
174 ep->status = passed;
175 xmax = ep->e.xlast;
176 isort(xmin,xmax);
177 add_scanpoint(points,sp,xmin,xmax);
178 sp++;
179 }
180 else if(ep->e.xmajor) {
181 xstep_edge(&ep->e);
182 xmax = ep->e.x - ep->e.xstep;
183 isort(xmin,xmax);
184 }
185 else {
186 ystep_edge(&ep->e);
187 }
188 add_scanpoint(points,sp,xmin,xmax);
189 sp++;
190 break;
191 default:
192 break;
193 }
194 }
195 while(points != NULL) {
196 scan *nextpt = points->next;
197 if(!nextpt) break;
198 xmin = points->x1;
199 xmax = nextpt->x2;
200 points = nextpt->next;
201 add_scansegment(segments,nextpt,xmin,xmax);
202 }
203 while(segments != NULL) {
204 xmin = segments->x1;
205 xmax = segments->x2;
206 segments = segments->next;
207 clip_ordxrange_(CURC,xmin,xmax,continue,CLIP_EMPTY_MACRO_ARG);
208 (*f->scan)(
209 (xmin + CURC->gc_xoffset),
210 (ypos + CURC->gc_yoffset),
211 (xmax - xmin + 1),
212 c
213 );
214 }
215 }
216 mouse_unblock();
217 }
218 }
219 if (edges) FREE(edges);
220 if (scans) FREE(scans);
221 reset_ALLOC();
222 }
223
224