style cleanup
[blender.git] / intern / raskter / raskter.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2012 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Peter Larabell.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27 /** \file raskter.c
28  *  \ingroup RASKTER
29  */
30
31 #include <stdio.h>
32 #include <malloc.h>
33 #include "raskter.h"
34
35 /* from BLI_utildefines.h */
36 #define MIN2(x, y)               ( (x) < (y) ? (x) : (y) )
37 #define MAX2(x, y)               ( (x) > (y) ? (x) : (y) )
38
39
40 struct e_status {
41         int x;
42         int ybeg;
43         int xshift;
44         int xdir;
45         int drift;
46         int drift_inc;
47         int drift_dec;
48         int num;
49         struct e_status *e_next;
50 };
51
52 struct r_buffer_stats {
53         float *buf;
54         int sizex;
55         int sizey;
56 };
57
58 struct r_fill_context {
59         struct e_status *all_edges, *possible_edges;
60         struct r_buffer_stats rb;
61 };
62
63 /*
64  * Sort all the edges of the input polygon by Y, then by X, of the "first" vertex encountered.
65  * This will ensure we can scan convert the entire poly in one pass.
66  *
67  * Really the poly should be clipped to the frame buffer's dimensions here for speed of drawing
68  * just the poly. Since the DEM code could end up being coupled with this, we'll keep it separate
69  * for now.
70  */
71 static void preprocess_all_edges(struct r_fill_context *ctx, struct poly_vert *verts, int num_verts, struct e_status *open_edge)
72 {
73         int i;
74         int xbeg;
75         int ybeg;
76         int xend;
77         int yend;
78         int dx;
79         int dy;
80         int temp_pos;
81         int xdist;
82         struct e_status *e_new;
83         struct e_status *next_edge;
84         struct e_status **next_edge_ref;
85         struct poly_vert *v;
86         /* set up pointers */
87         v = verts;
88         ctx->all_edges = NULL;
89         /* loop all verts */
90         for (i = 0; i < num_verts; i++) {
91                 /* determine beginnings and endings of edges, linking last vertex to first vertex */
92                 xbeg = v[i].x;
93                 ybeg = v[i].y;
94                 if (i) {
95                         /* we're not at the last vert, so end of the edge is the previous vertex */
96                         xend = v[i - 1].x;
97                         yend = v[i - 1].y;
98                 }
99                 else {
100                         /* we're at the first vertex, so the "end" of this edge is the last vertex */
101                         xend = v[num_verts - 1].x;
102                         yend = v[num_verts - 1].y;
103                 }
104                 /* make sure our edges are facing the correct direction */
105                 if (ybeg > yend) {
106                         /* flip the Xs */
107                         temp_pos = xbeg;
108                         xbeg = xend;
109                         xend = temp_pos;
110                         /* flip the Ys */
111                         temp_pos = ybeg;
112                         ybeg = yend;
113                         yend = temp_pos;
114                 }
115
116                 /* calculate y delta */
117                 dy = yend - ybeg;
118                 /* dont draw horizontal lines directly, they are scanned as part of the edges they connect, so skip em. :) */
119                 if (dy) {
120                         /* create the edge and determine it's slope (for incremental line drawing) */
121                         e_new = open_edge++;
122
123                         /* calculate x delta */
124                         dx = xend - xbeg;
125                         if (dx > 0) {
126                                 e_new->xdir = 1;
127                                 xdist = dx;
128                         }
129                         else {
130                                 e_new->xdir = -1;
131                                 xdist = -dx;
132                         }
133
134                         e_new->x = xbeg;
135                         e_new->ybeg = ybeg;
136                         e_new->num = dy;
137                         e_new->drift_dec = dy;
138
139                         /* calculate deltas for incremental drawing */
140                         if (dx >= 0) {
141                                 e_new->drift = 0;
142                         }
143                         else {
144                                 e_new->drift = -dy + 1;
145                         }
146                         if (dy >= xdist) {
147                                 e_new->drift_inc = xdist;
148                                 e_new->xshift = 0;
149                         }
150                         else {
151                                 e_new->drift_inc = xdist % dy;
152                                 e_new->xshift = (xdist / dy) * e_new->xdir;
153                         }
154                         next_edge_ref = &ctx->all_edges;
155                         /* link in all the edges, in sorted order */
156                         for (;; ) {
157                                 next_edge = *next_edge_ref;
158                                 if (!next_edge || (next_edge->ybeg > ybeg) || ((next_edge->ybeg == ybeg) && (next_edge->x >= xbeg))) {
159                                         e_new->e_next = next_edge;
160                                         *next_edge_ref = e_new;
161                                         break;
162                                 }
163                                 next_edge_ref = &next_edge->e_next;
164                         }
165                 }
166         }
167 }
168
169 /*
170  * This function clips drawing to the frame buffer. That clipping will likely be moved into the preprocessor
171  * for speed, but waiting on final design choices for curve-data before eliminating data the DEM code will need
172  * if it ends up being coupled with this function.
173  */
174 int rast_scan_fill(struct r_fill_context *ctx, struct poly_vert *verts, int num_verts)
175 {
176         int x_curr;                 /* current pixel position in X */
177         int y_curr;                 /* current scan line being drawn */
178         int yp;                     /* y-pixel's position in frame buffer */
179         int swixd = 0;              /* whether or not edges switched position in X */
180         float *cpxl;                /* pixel pointers... */
181         float *mpxl;
182         float *spxl;
183         struct e_status *e_curr;    /* edge pointers... */
184         struct e_status *e_temp;
185         struct e_status *edgbuf;
186         struct e_status **edgec;
187
188
189         /*
190          * If the number of verts specified to render as a polygon is less than 3,
191          * return immediately. Obviously we cant render a poly with sides < 3. The
192          * return for this we set to 1, simply so it can be distinguished from the
193          * next place we could return, /home/guest/blender-svn/soc-2011-tomato/intern/raskter/raskter.cwhich is a failure to allocate memory.
194          */
195         if (num_verts < 3) {
196                 return(1);
197         }
198
199         /*
200          * Try to allocate an edge buffer in memory. needs to be the size of the edge tracking data
201          * multiplied by the number of edges, which is always equal to the number of verts in
202          * a 2D polygon. Here we return 0 to indicate a memory allocation failure, as opposed to a 1 for
203          * the preceeding error, which was a rasterization request on a 2D poly with less than
204          * 3 sides.
205          */
206         if ((edgbuf = (struct e_status *)(malloc(sizeof(struct e_status) * num_verts))) == NULL) {
207                 return(0);
208         }
209
210         /*
211          * Do some preprocessing on all edges. This constructs a table structure in memory of all
212          * the edge properties and can "flip" some edges so sorting works correctly.
213          */
214         preprocess_all_edges(ctx, verts, num_verts, edgbuf);
215
216         /*
217          * Set the pointer for tracking the edges currently in processing to NULL to make sure
218          * we don't get some crazy value after initialization.
219          */
220         ctx->possible_edges = NULL;
221
222         /*
223          * Loop through all scan lines to be drawn. Since we sorted by Y values during
224          * preprocess_all_edges(), we can already exact values for the lowest and
225          * highest Y values we could possibly need by induction. The preprocessing sorted
226          * out edges by Y position, we can cycle the current edge being processed once
227          * it runs out of Y pixels. When we have no more edges, meaning the current edge
228          * is NULL after setting the "current" edge to be the previous current edge's
229          * "next" edge in the Y sorted edge connection chain, we can stop looping Y values,
230          * since we can't possibly have more scan lines if we ran out of edges. :)
231          *
232          * TODO: This clips Y to the frame buffer, which should be done in the preprocessor, but for now is done here.
233          *       Will get changed once DEM code gets in.
234          */
235         for (y_curr = ctx->all_edges->ybeg; (ctx->all_edges || ctx->possible_edges); y_curr++) {
236
237                 /*
238                  * Link any edges that start on the current scan line into the list of
239                  * edges currently needed to draw at least this, if not several, scan lines.
240                  */
241
242                 /*
243                  * Set the current edge to the beginning of the list of edges to be rasterized
244                  * into this scan line.
245                  *
246                  * We could have lots of edge here, so iterate over all the edges needed. The
247                  * preprocess_all_edges() function sorted edges by X within each chunk of Y sorting
248                  * so we safely cycle edges to thier own "next" edges in order.
249                  *
250                  * At each iteration, make sure we still have a non-NULL edge.
251                  */
252                 for (edgec = &ctx->possible_edges; ctx->all_edges && (ctx->all_edges->ybeg == y_curr); ) {
253                         x_curr = ctx->all_edges->x;                  /* Set current X position. */
254                         for (;; ) {                                  /* Start looping edges. Will break when edges run out. */
255                                 e_curr = *edgec;                         /* Set up a current edge pointer. */
256                                 if (!e_curr || (e_curr->x >= x_curr)) {  /* If we have an no edge, or we need to skip some X-span, */
257                                         e_temp = ctx->all_edges->e_next;     /* set a temp "next" edge to test. */
258                                         *edgec = ctx->all_edges;             /* Add this edge to the list to be scanned. */
259                                         ctx->all_edges->e_next = e_curr;     /* Set up the next edge. */
260                                         edgec = &ctx->all_edges->e_next;     /* Set our list to the next edge's location in memory. */
261                                         ctx->all_edges = e_temp;             /* Skip the NULL or bad X edge, set pointer to next edge. */
262                                         break;                               /* Stop looping edges (since we ran out or hit empty X span. */
263                                 }
264                                 else {
265                                         edgec = &e_curr->e_next;             /* Set the pointer to the edge list the "next" edge. */
266                                 }
267                         }
268                 }
269
270                 /*
271                  * Determine the current scan line's offset in the pixel buffer based on its Y position.
272                  * Basically we just multiply the current scan line's Y value by the number of pixels in each line.
273                  */
274                 yp = y_curr * ctx->rb.sizex;
275                 /*
276                  * Set a "scan line pointer" in memory. The location of the buffer plus the row offset.
277                  */
278                 spxl = ctx->rb.buf + (yp);
279                 /*
280                  * Set up the current edge to the first (in X) edge. The edges which could possibly be in this
281                  * list were determined in the preceeding edge loop above. They were already sorted in X by the
282                  * initial processing function.
283                  *
284                  * At each iteration, test for a NULL edge. Since we'll keep cycling edge's to their own "next" edge
285                  * we will eventually hit a NULL when the list runs out.
286                  */
287                 for (e_curr = ctx->possible_edges; e_curr; e_curr = e_curr->e_next) {
288                         /*
289                          * Calculate a span of pixels to fill on the current scan line.
290                          *
291                          * Set the current pixel pointer by adding the X offset to the scan line's start offset.
292                          * Cycle the current edge the next edge.
293                          * Set the max X value to draw to be one less than the next edge's first pixel. This way we are
294                          * sure not to ever get into a situation where we have overdraw. (drawing the same pixel more than
295                          * one time because it's on a vertex connecting two edges)
296                          *
297                          * Then blast through all the pixels in the span, advancing the pointer and setting the color to white.
298                          *
299                          * TODO: Here we clip to the scan line, this is not efficient, and should be done in the preprocessor,
300                          *       but for now it is done here until the DEM code comes in.
301                          */
302
303                         /* set up xmin and xmax bounds on this scan line */
304                         cpxl = spxl + MAX2(e_curr->x, 0);
305                         e_curr = e_curr->e_next;
306                         mpxl = spxl + MIN2(e_curr->x, ctx->rb.sizex) - 1;
307
308                         if ((y_curr >= 0) && (y_curr < ctx->rb.sizey)) {
309                                 /* draw the pixels. */
310                                 for (; cpxl <= mpxl; cpxl++) {
311                                         if (*cpxl < 0.5f) {
312                                                 *cpxl = 1.0f;
313                                         }
314                                         else {
315                                                 *cpxl = 0.0f;
316                                         }
317                                 }
318                         }
319                 }
320
321                 /*
322                  * Loop through all edges of polygon that could be hit by this scan line,
323                  * and figure out their x-intersections with the next scan line.
324                  *
325                  * Either A.) we wont have any more edges to test, or B.) we just add on the
326                  * slope delta computed in preprocessing step. Since this draws non-antialiased
327                  * polygons, we dont have fractional positions, so we only move in x-direction
328                  * when needed to get all the way to the next pixel over...
329                  */
330                 for (edgec = &ctx->possible_edges; (e_curr = *edgec); ) {
331                         if (!(--(e_curr->num))) {
332                                 *edgec = e_curr->e_next;
333                         }
334                         else {
335                                 e_curr->x += e_curr->xshift;
336                                 if ((e_curr->drift += e_curr->drift_inc) > 0) {
337                                         e_curr->x += e_curr->xdir;
338                                         e_curr->drift -= e_curr->drift_dec;
339                                 }
340                                 edgec = &e_curr->e_next;
341                         }
342                 }
343                 /*
344                  * It's possible that some edges may have crossed during the last step, so we'll be sure
345                  * that we ALWAYS intersect scan lines in order by shuffling if needed to make all edges
346                  * sorted by x-intersection coordinate. We'll always scan through at least once to see if
347                  * edges crossed, and if so, we set the 'swixd' flag. If 'swixd' gets set on the initial
348                  * pass, then we know we need to sort by x, so then cycle through edges again and perform
349                  * the sort.-
350                  */
351                 if (ctx->possible_edges) {
352                         for (edgec = &ctx->possible_edges; (e_curr = *edgec)->e_next; edgec = &(*edgec)->e_next) {
353                                 /* if the current edge hits scan line at greater X than the next edge, we need to exchange the edges */
354                                 if (e_curr->x > e_curr->e_next->x) {
355                                         *edgec = e_curr->e_next;
356                                         /* exchange the pointers */
357                                         e_temp = e_curr->e_next->e_next;
358                                         e_curr->e_next->e_next = e_curr;
359                                         e_curr->e_next = e_temp;
360                                         /* set flag that we had at least one switch */
361                                         swixd = 1;
362                                 }
363                         }
364                         /* if we did have a switch, look for more (there will more if there was one) */
365                         for (;; ) {
366                                 /* reset exchange flag so it's only set if we encounter another one */
367                                 swixd = 0;
368                                 for (edgec = &ctx->possible_edges; (e_curr = *edgec)->e_next; edgec = &(*edgec)->e_next) {
369                                         /* again, if current edge hits scan line at higher X than next edge, exchange the edges and set flag */
370                                         if (e_curr->x > e_curr->e_next->x) {
371                                                 *edgec = e_curr->e_next;
372                                                 /* exchange the pointers */
373                                                 e_temp = e_curr->e_next->e_next;
374                                                 e_curr->e_next->e_next = e_curr;
375                                                 e_curr->e_next = e_temp;
376                                                 /* flip the exchanged flag */
377                                                 swixd = 1;
378                                         }
379                                 }
380                                 /* if we had no exchanges, we're done reshuffling the pointers */
381                                 if (!swixd) {
382                                         break;
383                                 }
384                         }
385                 }
386         }
387
388         free(edgbuf);
389         return 1;
390 }
391
392 int PLX_raskterize(float (*base_verts)[2], int num_base_verts,
393                    float *buf, int buf_x, int buf_y)
394 {
395         int i;                                       /* i: Loop counter. */
396         struct poly_vert *ply;                       /* ply: Pointer to a list of integer buffer-space vertex coordinates. */
397         struct r_fill_context ctx = {0};
398
399         /*
400          * Allocate enough memory for our poly_vert list. It'll be the size of the poly_vert
401          * data structure multiplied by the number of base_verts.
402          *
403          * In the event of a failure to allocate the memory, return 0, so this error can
404          * be distinguished as a memory allocation error.
405          */
406         if ((ply = (struct poly_vert *)(malloc(sizeof(struct poly_vert) * num_base_verts))) == NULL) {
407                 return(0);
408         }
409
410         /*
411          * Loop over all verts passed in to be rasterized. Each vertex's X and Y coordinates are
412          * then converted from normalized screen space (0.0 <= POS <= 1.0) to integer coordinates
413          * in the buffer-space coordinates passed in inside buf_x and buf_y.
414          *
415          * It's worth noting that this function ONLY outputs fully white pixels in a mask. Every pixel
416          * drawn will be 1.0f in value, there is no anti-aliasing.
417          */
418         for (i = 0; i < num_base_verts; i++) {                          /* Loop over all base_verts. */
419                 ply[i].x = (base_verts[i][0] * buf_x) + 0.5f;       /* Range expand normalized X to integer buffer-space X. */
420                 ply[i].y = (base_verts[i][1] * buf_y) + 0.5f; /* Range expand normalized Y to integer buffer-space Y. */
421         }
422
423         ctx.rb.buf = buf;                            /* Set the output buffer pointer. */
424         ctx.rb.sizex = buf_x;                        /* Set the output buffer size in X. (width) */
425         ctx.rb.sizey = buf_y;                        /* Set the output buffer size in Y. (height) */
426
427         i = rast_scan_fill(&ctx, ply, num_base_verts);  /* Call our rasterizer, passing in the integer coords for each vert. */
428         free(ply);                                      /* Free the memory allocated for the integer coordinate table. */
429         return(i);                                      /* Return the value returned by the rasterizer. */
430 }
431
432 /*
433  * This function clips drawing to the frame buffer. That clipping will likely be moved into the preprocessor
434  * for speed, but waiting on final design choices for curve-data before eliminating data the DEM code will need
435  * if it ends up being coupled with this function.
436  */
437 int rast_scan_feather(struct r_fill_context *ctx,
438                       float (*base_verts_f)[2], int num_base_verts,
439                       struct poly_vert *feather_verts, float (*feather_verts_f)[2], int num_feather_verts)
440 {
441         int x_curr;                 /* current pixel position in X */
442         int y_curr;                 /* current scan line being drawn */
443         int yp;                     /* y-pixel's position in frame buffer */
444         int swixd = 0;              /* whether or not edges switched position in X */
445         float *cpxl;                /* pixel pointers... */
446         float *mpxl;
447         float *spxl;
448         struct e_status *e_curr;    /* edge pointers... */
449         struct e_status *e_temp;
450         struct e_status *edgbuf;
451         struct e_status **edgec;
452
453         /* from dem */
454         int a;                          // a = temporary pixel index buffer loop counter
455         float fsz;                        // size of the frame
456         unsigned int rsl;               // long used for finding fast 1.0/sqrt
457         float rsf;                      // float used for finding fast 1.0/sqrt
458         const float rsopf = 1.5f;       // constant float used for finding fast 1.0/sqrt
459
460         //unsigned int gradientFillOffset;
461         float t;
462         float ud;                // ud = unscaled edge distance
463         float dmin;              // dmin = minimun edge distance
464         float odist;                    // odist = current outer edge distance
465         float idist;                    // idist = current inner edge distance
466         float dx;                         // dx = X-delta (used for distance proportion calculation)
467         float dy;                         // dy = Y-delta (used for distance proportion calculation)
468         float xpxw = (1.0f / (float)(ctx->rb.sizex));  // xpxw = normalized pixel width
469         float ypxh = (1.0f / (float)(ctx->rb.sizey));  // ypxh = normalized pixel height
470
471         /*
472          * If the number of verts specified to render as a polygon is less than 3,
473          * return immediately. Obviously we cant render a poly with sides < 3. The
474          * return for this we set to 1, simply so it can be distinguished from the
475          * next place we could return, /home/guest/blender-svn/soc-2011-tomato/intern/raskter/raskter
476          * which is a failure to allocate memory.
477          */
478         if (num_feather_verts < 3) {
479                 return(1);
480         }
481
482         /*
483          * Try to allocate an edge buffer in memory. needs to be the size of the edge tracking data
484          * multiplied by the number of edges, which is always equal to the number of verts in
485          * a 2D polygon. Here we return 0 to indicate a memory allocation failure, as opposed to a 1 for
486          * the preceeding error, which was a rasterization request on a 2D poly with less than
487          * 3 sides.
488          */
489         if ((edgbuf = (struct e_status *)(malloc(sizeof(struct e_status) * num_feather_verts))) == NULL) {
490                 return(0);
491         }
492
493         /*
494          * Do some preprocessing on all edges. This constructs a table structure in memory of all
495          * the edge properties and can "flip" some edges so sorting works correctly.
496          */
497         preprocess_all_edges(ctx, feather_verts, num_feather_verts, edgbuf);
498
499         /*
500          * Set the pointer for tracking the edges currently in processing to NULL to make sure
501          * we don't get some crazy value after initialization.
502          */
503         ctx->possible_edges = NULL;
504
505         /*
506          * Loop through all scan lines to be drawn. Since we sorted by Y values during
507          * preprocess_all_edges(), we can already exact values for the lowest and
508          * highest Y values we could possibly need by induction. The preprocessing sorted
509          * out edges by Y position, we can cycle the current edge being processed once
510          * it runs out of Y pixels. When we have no more edges, meaning the current edge
511          * is NULL after setting the "current" edge to be the previous current edge's
512          * "next" edge in the Y sorted edge connection chain, we can stop looping Y values,
513          * since we can't possibly have more scan lines if we ran out of edges. :)
514          *
515          * TODO: This clips Y to the frame buffer, which should be done in the preprocessor, but for now is done here.
516          *       Will get changed once DEM code gets in.
517          */
518         for (y_curr = ctx->all_edges->ybeg; (ctx->all_edges || ctx->possible_edges); y_curr++) {
519
520                 /*
521                  * Link any edges that start on the current scan line into the list of
522                  * edges currently needed to draw at least this, if not several, scan lines.
523                  */
524
525                 /*
526                  * Set the current edge to the beginning of the list of edges to be rasterized
527                  * into this scan line.
528                  *
529                  * We could have lots of edge here, so iterate over all the edges needed. The
530                  * preprocess_all_edges() function sorted edges by X within each chunk of Y sorting
531                  * so we safely cycle edges to thier own "next" edges in order.
532                  *
533                  * At each iteration, make sure we still have a non-NULL edge.
534                  */
535                 for (edgec = &ctx->possible_edges; ctx->all_edges && (ctx->all_edges->ybeg == y_curr); ) {
536                         x_curr = ctx->all_edges->x;                  /* Set current X position. */
537                         for (;; ) {                                  /* Start looping edges. Will break when edges run out. */
538                                 e_curr = *edgec;                         /* Set up a current edge pointer. */
539                                 if (!e_curr || (e_curr->x >= x_curr)) {  /* If we have an no edge, or we need to skip some X-span, */
540                                         e_temp = ctx->all_edges->e_next;     /* set a temp "next" edge to test. */
541                                         *edgec = ctx->all_edges;             /* Add this edge to the list to be scanned. */
542                                         ctx->all_edges->e_next = e_curr;     /* Set up the next edge. */
543                                         edgec = &ctx->all_edges->e_next;     /* Set our list to the next edge's location in memory. */
544                                         ctx->all_edges = e_temp;             /* Skip the NULL or bad X edge, set pointer to next edge. */
545                                         break;                               /* Stop looping edges (since we ran out or hit empty X span. */
546                                 }
547                                 else {
548                                         edgec = &e_curr->e_next;             /* Set the pointer to the edge list the "next" edge. */
549                                 }
550                         }
551                 }
552
553                 /*
554                  * Determine the current scan line's offset in the pixel buffer based on its Y position.
555                  * Basically we just multiply the current scan line's Y value by the number of pixels in each line.
556                  */
557                 yp = y_curr * ctx->rb.sizex;
558                 /*
559                  * Set a "scan line pointer" in memory. The location of the buffer plus the row offset.
560                  */
561                 spxl = ctx->rb.buf + (yp);
562                 /*
563                  * Set up the current edge to the first (in X) edge. The edges which could possibly be in this
564                  * list were determined in the preceeding edge loop above. They were already sorted in X by the
565                  * initial processing function.
566                  *
567                  * At each iteration, test for a NULL edge. Since we'll keep cycling edge's to their own "next" edge
568                  * we will eventually hit a NULL when the list runs out.
569                  */
570                 for (e_curr = ctx->possible_edges; e_curr; e_curr = e_curr->e_next) {
571                         /*
572                          * Calculate a span of pixels to fill on the current scan line.
573                          *
574                          * Set the current pixel pointer by adding the X offset to the scan line's start offset.
575                          * Cycle the current edge the next edge.
576                          * Set the max X value to draw to be one less than the next edge's first pixel. This way we are
577                          * sure not to ever get into a situation where we have overdraw. (drawing the same pixel more than
578                          * one time because it's on a vertex connecting two edges)
579                          *
580                          * Then blast through all the pixels in the span, advancing the pointer and setting the color to white.
581                          *
582                          * TODO: Here we clip to the scan line, this is not efficient, and should be done in the preprocessor,
583                          *       but for now it is done here until the DEM code comes in.
584                          */
585
586                         /* set up xmin and xmax bounds on this scan line */
587                         cpxl = spxl + MAX2(e_curr->x, 0);
588                         e_curr = e_curr->e_next;
589                         mpxl = spxl + MIN2(e_curr->x, ctx->rb.sizex) - 1;
590
591                         if ((y_curr >= 0) && (y_curr < ctx->rb.sizey)) {
592                                 t = ((float)((cpxl - spxl) % ctx->rb.sizex) + 0.5f) * xpxw;
593                                 fsz = ((float)(y_curr) + 0.5f) * ypxh;
594                                 /* draw the pixels. */
595                                 for (; cpxl <= mpxl; cpxl++, t += xpxw) {
596                                         //do feather check
597                                         // first check that pixel isn't already full, and only operate if it is not
598                                         if (*cpxl < 0.9999f) {
599
600                                                 dmin = 2.0f;                        // reset min distance to edge pixel
601                                                 for (a = 0; a < num_feather_verts; a++) { // loop through all outer edge buffer pixels
602                                                         dy = t - feather_verts_f[a][0];          // set dx to gradient pixel column - outer edge pixel row
603                                                         dx = fsz - feather_verts_f[a][1];        // set dy to gradient pixel row - outer edge pixel column
604                                                         ud = dx * dx + dy * dy;               // compute sum of squares
605                                                         if (ud < dmin) {                      // if our new sum of squares is less than the current minimum
606                                                                 dmin = ud;                        // set a new minimum equal to the new lower value
607                                                         }
608                                                 }
609                                                 odist = dmin;                    // cast outer min to a float
610                                                 rsf = odist * 0.5f;                       //
611                                                 rsl = *(unsigned int *)&odist;            // use some peculiar properties of the way bits are stored
612                                                 rsl = 0x5f3759df - (rsl >> 1);            // in floats vs. unsigned ints to compute an approximate
613                                                 odist = *(float *)&rsl;                   // reciprocal square root
614                                                 odist = odist * (rsopf - (rsf * odist * odist));  // -- ** this line can be iterated for more accuracy ** --
615                                                 odist = odist * (rsopf - (rsf * odist * odist));
616                                                 dmin = 2.0f;                        // reset min distance to edge pixel
617                                                 for (a = 0; a < num_base_verts; a++) {    // loop through all inside edge pixels
618                                                         dy = t - base_verts_f[a][0];             // compute delta in Y from gradient pixel to inside edge pixel
619                                                         dx = fsz - base_verts_f[a][1];           // compute delta in X from gradient pixel to inside edge pixel
620                                                         ud = dx * dx + dy * dy;   // compute sum of squares
621                                                         if (ud < dmin) {          // if our new sum of squares is less than the current minimum we've found
622                                                                 dmin = ud;            // set a new minimum equal to the new lower value
623                                                         }
624                                                 }
625                                                 idist = dmin;                    // cast inner min to a float
626                                                 rsf = idist * 0.5f;                       //
627                                                 rsl = *(unsigned int *)&idist;            //
628                                                 rsl = 0x5f3759df - (rsl >> 1);            // see notes above
629                                                 idist = *(float *)&rsl;                   //
630                                                 idist = idist * (rsopf - (rsf * idist * idist));  //
631                                                 idist = idist * (rsopf - (rsf * idist * idist));
632                                                 /*
633                                                  * Note once again that since we are using reciprocals of distance values our
634                                                  * proportion is already the correct intensity, and does not need to be
635                                                  * subracted from 1.0 like it would have if we used real distances.
636                                                  */
637
638                                                 /* set intensity, do the += so overlapping gradients are additive */
639                                                 *cpxl = (idist / (idist + odist));
640                                         }
641                                 }
642                         }
643                 }
644
645                 /*
646                  * Loop through all edges of polygon that could be hit by this scan line,
647                  * and figure out their x-intersections with the next scan line.
648                  *
649                  * Either A.) we wont have any more edges to test, or B.) we just add on the
650                  * slope delta computed in preprocessing step. Since this draws non-antialiased
651                  * polygons, we dont have fractional positions, so we only move in x-direction
652                  * when needed to get all the way to the next pixel over...
653                  */
654                 for (edgec = &ctx->possible_edges; (e_curr = *edgec); ) {
655                         if (!(--(e_curr->num))) {
656                                 *edgec = e_curr->e_next;
657                         }
658                         else {
659                                 e_curr->x += e_curr->xshift;
660                                 if ((e_curr->drift += e_curr->drift_inc) > 0) {
661                                         e_curr->x += e_curr->xdir;
662                                         e_curr->drift -= e_curr->drift_dec;
663                                 }
664                                 edgec = &e_curr->e_next;
665                         }
666                 }
667                 /*
668                  * It's possible that some edges may have crossed during the last step, so we'll be sure
669                  * that we ALWAYS intersect scan lines in order by shuffling if needed to make all edges
670                  * sorted by x-intersection coordinate. We'll always scan through at least once to see if
671                  * edges crossed, and if so, we set the 'swixd' flag. If 'swixd' gets set on the initial
672                  * pass, then we know we need to sort by x, so then cycle through edges again and perform
673                  * the sort.-
674                  */
675                 if (ctx->possible_edges) {
676                         for (edgec = &ctx->possible_edges; (e_curr = *edgec)->e_next; edgec = &(*edgec)->e_next) {
677                                 /* if the current edge hits scan line at greater X than the next edge, we need to exchange the edges */
678                                 if (e_curr->x > e_curr->e_next->x) {
679                                         *edgec = e_curr->e_next;
680                                         /* exchange the pointers */
681                                         e_temp = e_curr->e_next->e_next;
682                                         e_curr->e_next->e_next = e_curr;
683                                         e_curr->e_next = e_temp;
684                                         /* set flag that we had at least one switch */
685                                         swixd = 1;
686                                 }
687                         }
688                         /* if we did have a switch, look for more (there will more if there was one) */
689                         for (;; ) {
690                                 /* reset exchange flag so it's only set if we encounter another one */
691                                 swixd = 0;
692                                 for (edgec = &ctx->possible_edges; (e_curr = *edgec)->e_next; edgec = &(*edgec)->e_next) {
693                                         /* again, if current edge hits scan line at higher X than next edge,
694                                          * exchange the edges and set flag */
695                                         if (e_curr->x > e_curr->e_next->x) {
696                                                 *edgec = e_curr->e_next;
697                                                 /* exchange the pointers */
698                                                 e_temp = e_curr->e_next->e_next;
699                                                 e_curr->e_next->e_next = e_curr;
700                                                 e_curr->e_next = e_temp;
701                                                 /* flip the exchanged flag */
702                                                 swixd = 1;
703                                         }
704                                 }
705                                 /* if we had no exchanges, we're done reshuffling the pointers */
706                                 if (!swixd) {
707                                         break;
708                                 }
709                         }
710                 }
711         }
712
713         free(edgbuf);
714         return 1;
715 }
716
717 int PLX_raskterize_feather(float (*base_verts)[2], int num_base_verts, float (*feather_verts)[2], int num_feather_verts,
718                            float *buf, int buf_x, int buf_y)
719 {
720         int i;                            /* i: Loop counter. */
721         struct poly_vert *fe;             /* fe: Pointer to a list of integer buffer-space feather vertex coords. */
722         struct r_fill_context ctx = {0};
723
724         /* for faster multiply */
725         const float buf_x_f = (float)buf_x;
726         const float buf_y_f = (float)buf_y;
727
728         /*
729          * Allocate enough memory for our poly_vert list. It'll be the size of the poly_vert
730          * data structure multiplied by the number of verts.
731          *
732          * In the event of a failure to allocate the memory, return 0, so this error can
733          * be distinguished as a memory allocation error.
734          */
735         if ((fe = (struct poly_vert *)(malloc(sizeof(struct poly_vert) * num_feather_verts))) == NULL) {
736                 return(0);
737         }
738
739         /*
740          * Loop over all verts passed in to be rasterized. Each vertex's X and Y coordinates are
741          * then converted from normalized screen space (0.0 <= POS <= 1.0) to integer coordinates
742          * in the buffer-space coordinates passed in inside buf_x and buf_y.
743          *
744          * It's worth noting that this function ONLY outputs fully white pixels in a mask. Every pixel
745          * drawn will be 1.0f in value, there is no anti-aliasing.
746          */
747         for (i = 0; i < num_feather_verts; i++) {            /* Loop over all verts. */
748                 fe[i].x = (int)((feather_verts[i][0] * buf_x_f) + 0.5f);  /* Range expand normalized X to integer buffer-space X. */
749                 fe[i].y = (int)((feather_verts[i][1] * buf_y_f) + 0.5f);  /* Range expand normalized Y to integer buffer-space Y. */
750         }
751
752         ctx.rb.buf = buf;                            /* Set the output buffer pointer. */
753         ctx.rb.sizex = buf_x;                        /* Set the output buffer size in X. (width) */
754         ctx.rb.sizey = buf_y;                        /* Set the output buffer size in Y. (height) */
755
756         /* Call our rasterizer, passing in the integer coords for each vert. */
757         i = rast_scan_feather(&ctx, base_verts, num_base_verts, fe, feather_verts, num_feather_verts);
758         free(fe);
759         return i;                                   /* Return the value returned by the rasterizer. */
760 }