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