18294f51e9af3f475a76e5cd17ab9d3d9e3dc236
[gbajam22] / src / polyfill.c
1 /*
2 blender for the Gameboy Advance
3 Copyright (C) 2021  John Tsiombikas <nuclear@member.fsf.org>
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program.  If not, see <https://www.gnu.org/licenses/>.
17 */
18 #include <string.h>
19 #include "polyfill.h"
20 #include "debug.h"
21
22 static unsigned char *fb;
23 static int fbwidth, fbheight;
24 static short scantab[2][160] __attribute__((section(".iwram")));
25
26 void polyfill_framebuffer(unsigned char *ptr, int w, int h)
27 {
28         fb = ptr;
29         fbwidth = w;
30         fbheight = h;
31 }
32
33 #define VNEXT(p)        (((p) == vlast) ? varr : (p) + 1)
34 #define VPREV(p)        ((p) == varr ? vlast : (p) - 1)
35 #define VSUCC(p, side)  ((side) == 0 ? VNEXT(p) : VPREV(p))
36
37 void polyfill_flat(struct pvertex *varr, int vnum, unsigned char col)
38 {
39         int i, line, top, bot;
40         struct pvertex *vlast, *v, *vn;
41         int32_t x, y0, y1, dx, dy, slope, fx, fy;
42         short *tab, start, len;
43         unsigned char *fbptr;
44         uint16_t *pptr, pcol = ((uint16_t)col << 8) | (uint16_t)col;
45
46         vlast = varr + vnum - 1;
47         top = fbheight;
48         bot = 0;
49
50         for(i=0; i<vnum; i++) {
51                 v = varr + i;
52                 vn = VNEXT(v);
53
54                 if(vn->y == v->y) continue;
55
56                 if(vn->y > v->y) {
57                         tab = scantab[0];
58                 } else {
59                         tab = scantab[1];
60                         v = vn;
61                         vn = varr + i;
62                 }
63
64                 dx = vn->x - v->x;
65                 dy = vn->y - v->y;
66                 slope = (dx << 8) / dy;
67
68                 y0 = (v->y + 0x100) & 0xffffff00;       /* start from the next scanline */
69                 fy = y0 - v->y;                                         /* fractional part before the next scanline */
70                 fx = (fy * slope) >> 8;                         /* X adjust for the step to the next scanline */
71                 x = v->x + fx;                                          /* adjust X */
72                 y1 = vn->y & 0xffffff00;                        /* last scanline of the edge <= vn->y */
73
74                 line = y0 >> 8;
75                 if(line < top) top = line;
76                 if((y1 >> 8) > bot) bot = y1 >> 8;
77
78                 if(line > 0) tab += line;
79
80                 while(line <= (y1 >> 8) && line < fbheight) {
81                         if(line >= 0) {
82                                 int val = x < 0 ? 0 : x >> 8;
83                                 *tab++ = val < fbwidth ? val : fbwidth - 1;
84                         }
85                         x += slope;
86                         line++;
87                 }
88         }
89
90         fbptr = fb + top * fbwidth;
91         for(i=top; i<=bot; i++) {
92                 start = scantab[0][i];
93                 len = scantab[1][i] - start;
94
95                 if(len > 0) {
96                         if(start & 1) {
97                                 pptr = (uint16_t*)(fbptr + (start & 0xfffe));
98                                 *pptr = (*pptr & 0xff) | ((uint16_t)col << 8);
99                                 len--;
100                                 start++;
101                         }
102                         pptr = (uint16_t*)(fbptr + start);
103                         while(len > 1) {
104                                 *pptr++ = pcol;
105                                 len -= 2;
106                         }
107                         if(len) {
108                                 *pptr = (*pptr & 0xff00) | col;
109                         }
110                 }
111                 fbptr += fbwidth;
112         }
113 }
114
115
116 /* ----- line drawing and clipping ------ */
117 enum {
118         IN              = 0,
119         LEFT    = 1,
120         RIGHT   = 2,
121         TOP             = 4,
122         BOTTOM  = 8
123 };
124
125 static int outcode(int x, int y, int xmin, int ymin, int xmax, int ymax)
126 {
127         int code = 0;
128
129         if(x < xmin) {
130                 code |= LEFT;
131         } else if(x > xmax) {
132                 code |= RIGHT;
133         }
134         if(y < ymin) {
135                 code |= TOP;
136         } else if(y > ymax) {
137                 code |= BOTTOM;
138         }
139         return code;
140 }
141
142 #define FIXMUL(a, b)    (((a) * (b)) >> 8)
143 #define FIXDIV(a, b)    (((a) << 8) / (b))
144
145 #define LERP(a, b, t)   ((a) + FIXMUL((b) - (a), (t)))
146
147 int clip_line(int *x0, int *y0, int *x1, int *y1, int xmin, int ymin, int xmax, int ymax)
148 {
149         int oc_out;
150
151         int oc0 = outcode(*x0, *y0, xmin, ymin, xmax, ymax);
152         int oc1 = outcode(*x1, *y1, xmin, ymin, xmax, ymax);
153
154         long fx0, fy0, fx1, fy1, fxmin, fymin, fxmax, fymax;
155
156         if(!(oc0 | oc1)) return 1;      /* both points are inside */
157
158         fx0 = *x0 << 8;
159         fy0 = *y0 << 8;
160         fx1 = *x1 << 8;
161         fy1 = *y1 << 8;
162         fxmin = xmin << 8;
163         fymin = ymin << 8;
164         fxmax = xmax << 8;
165         fymax = ymax << 8;
166
167         for(;;) {
168                 long x, y, t;
169
170                 if(oc0 & oc1) return 0;         /* both have points with the same outbit, not visible */
171                 if(!(oc0 | oc1)) break;         /* both points are inside */
172
173                 oc_out = oc0 ? oc0 : oc1;
174
175                 if(oc_out & TOP) {
176                         t = FIXDIV(fymin - fy0, fy1 - fy0);
177                         x = LERP(fx0, fx1, t);
178                         y = fymin;
179                 } else if(oc_out & BOTTOM) {
180                         t = FIXDIV(fymax - fy0, fy1 - fy0);
181                         x = LERP(fx0, fx1, t);
182                         y = fymax;
183                 } else if(oc_out & LEFT) {
184                         t = FIXDIV(fxmin - fx0, fx1 - fx0);
185                         x = fxmin;
186                         y = LERP(fy0, fy1, t);
187                 } else {/*if(oc_out & RIGHT) {*/
188                         t = FIXDIV(fxmax - fx0, fx1 - fx0);
189                         x = fxmax;
190                         y = LERP(fy0, fy1, t);
191                 }
192
193                 if(oc_out == oc0) {
194                         fx0 = x;
195                         fy0 = y;
196                         oc0 = outcode(fx0 >> 8, fy0 >> 8, xmin, ymin, xmax, ymax);
197                 } else {
198                         fx1 = x;
199                         fy1 = y;
200                         oc1 = outcode(fx1 >> 8, fy1 >> 8, xmin, ymin, xmax, ymax);
201                 }
202         }
203
204         *x0 = fx0 >> 8;
205         *y0 = fy0 >> 8;
206         *x1 = fx1 >> 8;
207         *y1 = fy1 >> 8;
208         return 1;
209 }
210
211 #ifdef ALT_LCLIP
212 #define PUTPIXEL(ptr) \
213         do { \
214                 if(x0 >= 0 && x0 < fbwidth && y0 >= 0 && y0 < fbheight) { \
215                         uint16_t *pptr = (uint16_t*)((uint32_t)ptr & 0xfffffffe); \
216                         if((uint32_t)ptr & 1) { \
217                                 *pptr = (*pptr & 0xff) | (color << 8); \
218                         } else { \
219                                 *pptr = (*pptr & 0xff00) | color; \
220                         } \
221                 } \
222         } while(0)
223 #else   /* !ALT_LCLIP */
224 #define PUTPIXEL(ptr) \
225         do { \
226                 uint16_t *pptr = (uint16_t*)((uint32_t)ptr & 0xfffffffe); \
227                 if((uint32_t)ptr & 1) { \
228                         *pptr = (*pptr & 0xff) | (color << 8); \
229                 } else { \
230                         *pptr = (*pptr & 0xff00) | color; \
231                 } \
232         } while(0)
233 #endif
234
235 void draw_line(int x0, int y0, int x1, int y1, unsigned short color)
236 {
237         int i, dx, dy, x_inc, y_inc, error;
238 #ifdef ALT_LCLIP
239         int y0inc;
240 #endif
241         unsigned char *fbptr = fb;
242
243         fbptr += y0 * fbwidth + x0;
244
245         dx = x1 - x0;
246         dy = y1 - y0;
247
248         if(dx >= 0) {
249                 x_inc = 1;
250         } else {
251                 x_inc = -1;
252                 dx = -dx;
253         }
254         if(dy >= 0) {
255                 y_inc = fbwidth;
256 #ifdef ALT_LCLIP
257                 y0inc = 1;
258 #endif
259         } else {
260                 y_inc = -fbwidth;
261 #ifdef ALT_LCLIP
262                 y0inc = -1;
263 #endif
264                 dy = -dy;
265         }
266
267         if(dx > dy) {
268                 error = dy * 2 - dx;
269                 for(i=0; i<=dx; i++) {
270                         PUTPIXEL(fbptr);
271                         if(error >= 0) {
272                                 error -= dx * 2;
273                                 fbptr += y_inc;
274 #ifdef ALT_LCLIP
275                                 y0 += y0inc;
276 #endif
277                         }
278                         error += dy * 2;
279                         fbptr += x_inc;
280 #ifdef ALT_LCLIP
281                         x0 += x_inc;
282 #endif
283                 }
284         } else {
285                 error = dx * 2 - dy;
286                 for(i=0; i<=dy; i++) {
287                         PUTPIXEL(fbptr);
288                         if(error >= 0) {
289                                 error -= dy * 2;
290                                 fbptr += x_inc;
291 #ifdef ALT_LCLIP
292                                 x0 += x_inc;
293 #endif
294                         }
295                         error += dx * 2;
296                         fbptr += y_inc;
297 #ifdef ALT_LCLIP
298                         y0 += y0inc;
299 #endif
300                 }
301         }
302 }
303