code cleanup: quiet warnings for gcc's -Wundef, -Wmissing-declarations
[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
28 /** \file raskter.c
29  *  \ingroup RASKTER
30  */
31
32 #include <stdlib.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 #define ABS(a)                   ( (a) < 0 ? (-(a)) : (a) )
39
40 struct PolyVert {
41         int x;
42         int y;
43 };
44
45 struct e_Status {
46         int x;
47         int ybeg;
48         int xshift;
49         int xdir;
50         int drift;
51         int drift_inc;
52         int drift_dec;
53         int num;
54         struct e_Status *e_next;
55 };
56
57 struct r_BufferStats {
58         float *buf;
59         int sizex;
60         int sizey;
61         int ymin;
62         int ymax;
63         int xmin;
64         int xmax;
65 };
66
67 struct r_FillContext {
68         struct e_Status *all_edges, *possible_edges;
69         struct r_BufferStats rb;
70 };
71
72 /*
73  * Sort all the edges of the input polygon by Y, then by X, of the "first" vertex encountered.
74  * This will ensure we can scan convert the entire poly in one pass.
75  *
76  * Really the poly should be clipped to the frame buffer's dimensions here for speed of drawing
77  * just the poly. Since the DEM code could end up being coupled with this, we'll keep it separate
78  * for now.
79  */
80 static void preprocess_all_edges(struct r_FillContext *ctx,
81                                  struct PolyVert *verts, int num_verts, struct e_Status *open_edge)
82 {
83         int i;
84         int xbeg;
85         int ybeg;
86         int xend;
87         int yend;
88         int dx;
89         int dy;
90         int temp_pos;
91         int xdist;
92         struct e_Status *e_new;
93         struct e_Status *next_edge;
94         struct e_Status **next_edge_ref;
95         struct PolyVert *v;
96         /* set up pointers */
97         v = verts;
98         ctx->all_edges = NULL;
99         /* initialize some boundaries */
100         ctx->rb.xmax = v[0].x;
101         ctx->rb.xmin = v[0].x;
102         ctx->rb.ymax = v[0].y;
103         ctx->rb.ymin = v[0].y;
104         /* loop all verts */
105         for (i = 0; i < num_verts; i++) {
106                 /* determine beginnings and endings of edges, linking last vertex to first vertex */
107                 xbeg = v[i].x;
108                 ybeg = v[i].y;
109                 /* keep track of our x and y bounds */
110                 if (xbeg >= ctx->rb.xmax) {
111                         ctx->rb.xmax = xbeg;
112                 }
113                 else if (xbeg <= ctx->rb.xmin) {
114                         ctx->rb.xmin = xbeg;
115                 }
116                 if (ybeg >= ctx->rb.ymax) {
117                         ctx->rb.ymax= ybeg;
118                 }
119                 else if (ybeg <= ctx->rb.ymin) {
120                         ctx->rb.ymin=ybeg;
121                 }
122                 if (i) {
123                         /* we're not at the last vert, so end of the edge is the previous vertex */
124                         xend = v[i - 1].x;
125                         yend = v[i - 1].y;
126                 }
127                 else {
128                         /* we're at the first vertex, so the "end" of this edge is the last vertex */
129                         xend = v[num_verts - 1].x;
130                         yend = v[num_verts - 1].y;
131                 }
132                 /* make sure our edges are facing the correct direction */
133                 if (ybeg > yend) {
134                         /* flip the Xs */
135                         temp_pos = xbeg;
136                         xbeg = xend;
137                         xend = temp_pos;
138                         /* flip the Ys */
139                         temp_pos = ybeg;
140                         ybeg = yend;
141                         yend = temp_pos;
142                 }
143
144                 /* calculate y delta */
145                 dy = yend - ybeg;
146                 /* dont draw horizontal lines directly, they are scanned as part of the edges they connect, so skip em. :) */
147                 if (dy) {
148                         /* create the edge and determine it's slope (for incremental line drawing) */
149                         e_new = open_edge++;
150
151                         /* calculate x delta */
152                         dx = xend - xbeg;
153                         if (dx > 0) {
154                                 e_new->xdir = 1;
155                                 xdist = dx;
156                         }
157                         else {
158                                 e_new->xdir = -1;
159                                 xdist = -dx;
160                         }
161
162                         e_new->x = xbeg;
163                         e_new->ybeg = ybeg;
164                         e_new->num = dy;
165                         e_new->drift_dec = dy;
166
167                         /* calculate deltas for incremental drawing */
168                         if (dx >= 0) {
169                                 e_new->drift = 0;
170                         }
171                         else {
172                                 e_new->drift = -dy + 1;
173                         }
174                         if (dy >= xdist) {
175                                 e_new->drift_inc = xdist;
176                                 e_new->xshift = 0;
177                         }
178                         else {
179                                 e_new->drift_inc = xdist % dy;
180                                 e_new->xshift = (xdist / dy) * e_new->xdir;
181                         }
182                         next_edge_ref = &ctx->all_edges;
183                         /* link in all the edges, in sorted order */
184                         for (;;) {
185                                 next_edge = *next_edge_ref;
186                                 if (!next_edge || (next_edge->ybeg > ybeg) || ((next_edge->ybeg == ybeg) && (next_edge->x >= xbeg))) {
187                                         e_new->e_next = next_edge;
188                                         *next_edge_ref = e_new;
189                                         break;
190                                 }
191                                 next_edge_ref = &next_edge->e_next;
192                         }
193                 }
194         }
195 }
196
197 /*
198  * This function clips drawing to the frame buffer. That clipping will likely be moved into the preprocessor
199  * for speed, but waiting on final design choices for curve-data before eliminating data the DEM code will need
200  * if it ends up being coupled with this function.
201  */
202 static int rast_scan_fill(struct r_FillContext *ctx, struct PolyVert *verts, int num_verts, float intensity)
203 {
204         int x_curr;                 /* current pixel position in X */
205         int y_curr;                 /* current scan line being drawn */
206         int yp;                     /* y-pixel's position in frame buffer */
207         int swixd = 0;              /* whether or not edges switched position in X */
208         float *cpxl;                /* pixel pointers... */
209         float *mpxl;
210         float *spxl;
211         struct e_Status *e_curr;    /* edge pointers... */
212         struct e_Status *e_temp;
213         struct e_Status *edgbuf;
214         struct e_Status **edgec;
215
216
217         /*
218          * If the number of verts specified to render as a polygon is less than 3,
219          * return immediately. Obviously we cant render a poly with sides < 3. The
220          * return for this we set to 1, simply so it can be distinguished from the
221          * next place we could return, /home/guest/blender-svn/soc-2011-tomato/intern/raskter/raskter.
222          * which is a failure to allocate memory.
223          */
224         if (num_verts < 3) {
225                 return(1);
226         }
227
228         /*
229          * Try to allocate an edge buffer in memory. needs to be the size of the edge tracking data
230          * multiplied by the number of edges, which is always equal to the number of verts in
231          * a 2D polygon. Here we return 0 to indicate a memory allocation failure, as opposed to a 1 for
232          * the preceeding error, which was a rasterization request on a 2D poly with less than
233          * 3 sides.
234          */
235         if ((edgbuf = (struct e_Status *)(malloc(sizeof(struct e_Status) * num_verts))) == NULL) {
236                 return(0);
237         }
238
239         /*
240          * Do some preprocessing on all edges. This constructs a table structure in memory of all
241          * the edge properties and can "flip" some edges so sorting works correctly.
242          */
243         preprocess_all_edges(ctx, verts, num_verts, edgbuf);
244
245         /* can happen with a zero area mask */
246         if (ctx->all_edges == NULL) {
247                 free(edgbuf);
248                 return(1);
249         }
250         /*
251          * Set the pointer for tracking the edges currently in processing to NULL to make sure
252          * we don't get some crazy value after initialization.
253          */
254         ctx->possible_edges = NULL;
255
256         /*
257          * Loop through all scan lines to be drawn. Since we sorted by Y values during
258          * preprocess_all_edges(), we can already exact values for the lowest and
259          * highest Y values we could possibly need by induction. The preprocessing sorted
260          * out edges by Y position, we can cycle the current edge being processed once
261          * it runs out of Y pixels. When we have no more edges, meaning the current edge
262          * is NULL after setting the "current" edge to be the previous current edge's
263          * "next" edge in the Y sorted edge connection chain, we can stop looping Y values,
264          * since we can't possibly have more scan lines if we ran out of edges. :)
265          *
266          * TODO: This clips Y to the frame buffer, which should be done in the preprocessor, but for now is done here.
267          *       Will get changed once DEM code gets in.
268          */
269         for (y_curr = ctx->all_edges->ybeg; (ctx->all_edges || ctx->possible_edges); y_curr++) {
270
271                 /*
272                  * Link any edges that start on the current scan line into the list of
273                  * edges currently needed to draw at least this, if not several, scan lines.
274                  */
275
276                 /*
277                  * Set the current edge to the beginning of the list of edges to be rasterized
278                  * into this scan line.
279                  *
280                  * We could have lots of edge here, so iterate over all the edges needed. The
281                  * preprocess_all_edges() function sorted edges by X within each chunk of Y sorting
282                  * so we safely cycle edges to thier own "next" edges in order.
283                  *
284                  * At each iteration, make sure we still have a non-NULL edge.
285                  */
286                 for (edgec = &ctx->possible_edges; ctx->all_edges && (ctx->all_edges->ybeg == y_curr);) {
287                         x_curr = ctx->all_edges->x;                  /* Set current X position. */
288                         for (;;) {                                   /* Start looping edges. Will break when edges run out. */
289                                 e_curr = *edgec;                         /* Set up a current edge pointer. */
290                                 if (!e_curr || (e_curr->x >= x_curr)) {  /* If we have an no edge, or we need to skip some X-span, */
291                                         e_temp = ctx->all_edges->e_next;     /* set a temp "next" edge to test. */
292                                         *edgec = ctx->all_edges;             /* Add this edge to the list to be scanned. */
293                                         ctx->all_edges->e_next = e_curr;     /* Set up the next edge. */
294                                         edgec = &ctx->all_edges->e_next;     /* Set our list to the next edge's location in memory. */
295                                         ctx->all_edges = e_temp;             /* Skip the NULL or bad X edge, set pointer to next edge. */
296                                         break;                               /* Stop looping edges (since we ran out or hit empty X span. */
297                                 }
298                                 else {
299                                         edgec = &e_curr->e_next;             /* Set the pointer to the edge list the "next" edge. */
300                                 }
301                         }
302                 }
303
304                 /*
305                  * Determine the current scan line's offset in the pixel buffer based on its Y position.
306                  * Basically we just multiply the current scan line's Y value by the number of pixels in each line.
307                  */
308                 yp = y_curr * ctx->rb.sizex;
309                 /*
310                  * Set a "scan line pointer" in memory. The location of the buffer plus the row offset.
311                  */
312                 spxl = ctx->rb.buf + (yp);
313                 /*
314                  * Set up the current edge to the first (in X) edge. The edges which could possibly be in this
315                  * list were determined in the preceeding edge loop above. They were already sorted in X by the
316                  * initial processing function.
317                  *
318                  * At each iteration, test for a NULL edge. Since we'll keep cycling edge's to their own "next" edge
319                  * we will eventually hit a NULL when the list runs out.
320                  */
321                 for (e_curr = ctx->possible_edges; e_curr; e_curr = e_curr->e_next) {
322                         /*
323                          * Calculate a span of pixels to fill on the current scan line.
324                          *
325                          * Set the current pixel pointer by adding the X offset to the scan line's start offset.
326                          * Cycle the current edge the next edge.
327                          * Set the max X value to draw to be one less than the next edge's first pixel. This way we are
328                          * sure not to ever get into a situation where we have overdraw. (drawing the same pixel more than
329                          * one time because it's on a vertex connecting two edges)
330                          *
331                          * Then blast through all the pixels in the span, advancing the pointer and setting the color to white.
332                          *
333                          * TODO: Here we clip to the scan line, this is not efficient, and should be done in the preprocessor,
334                          *       but for now it is done here until the DEM code comes in.
335                          */
336
337                         /* set up xmin and xmax bounds on this scan line */
338                         cpxl = spxl + MAX2(e_curr->x, 0);
339                         e_curr = e_curr->e_next;
340                         mpxl = spxl + MIN2(e_curr->x, ctx->rb.sizex) - 1;
341
342                         if ((y_curr >= 0) && (y_curr < ctx->rb.sizey)) {
343                                 /* draw the pixels. */
344                                 for (; cpxl <= mpxl; *cpxl++ += intensity) {}
345                         }
346                 }
347
348                 /*
349                  * Loop through all edges of polygon that could be hit by this scan line,
350                  * and figure out their x-intersections with the next scan line.
351                  *
352                  * Either A.) we wont have any more edges to test, or B.) we just add on the
353                  * slope delta computed in preprocessing step. Since this draws non-antialiased
354                  * polygons, we dont have fractional positions, so we only move in x-direction
355                  * when needed to get all the way to the next pixel over...
356                  */
357                 for (edgec = &ctx->possible_edges; (e_curr = *edgec);) {
358                         if (!(--(e_curr->num))) {
359                                 *edgec = e_curr->e_next;
360                         }
361                         else {
362                                 e_curr->x += e_curr->xshift;
363                                 if ((e_curr->drift += e_curr->drift_inc) > 0) {
364                                         e_curr->x += e_curr->xdir;
365                                         e_curr->drift -= e_curr->drift_dec;
366                                 }
367                                 edgec = &e_curr->e_next;
368                         }
369                 }
370                 /*
371                  * It's possible that some edges may have crossed during the last step, so we'll be sure
372                  * that we ALWAYS intersect scan lines in order by shuffling if needed to make all edges
373                  * sorted by x-intersection coordinate. We'll always scan through at least once to see if
374                  * edges crossed, and if so, we set the 'swixd' flag. If 'swixd' gets set on the initial
375                  * pass, then we know we need to sort by x, so then cycle through edges again and perform
376                  * the sort.-
377                  */
378                 if (ctx->possible_edges) {
379                         for (edgec = &ctx->possible_edges; (e_curr = *edgec)->e_next; edgec = &(*edgec)->e_next) {
380                                 /* if the current edge hits scan line at greater X than the next edge, we need to exchange the edges */
381                                 if (e_curr->x > e_curr->e_next->x) {
382                                         *edgec = e_curr->e_next;
383                                         /* exchange the pointers */
384                                         e_temp = e_curr->e_next->e_next;
385                                         e_curr->e_next->e_next = e_curr;
386                                         e_curr->e_next = e_temp;
387                                         /* set flag that we had at least one switch */
388                                         swixd = 1;
389                                 }
390                         }
391                         /* if we did have a switch, look for more (there will more if there was one) */
392                         for (;;) {
393                                 /* reset exchange flag so it's only set if we encounter another one */
394                                 swixd = 0;
395                                 for (edgec = &ctx->possible_edges; (e_curr = *edgec)->e_next; edgec = &(*edgec)->e_next) {
396                                         /* again, if current edge hits scan line at higher X than next edge, exchange the edges and set flag */
397                                         if (e_curr->x > e_curr->e_next->x) {
398                                                 *edgec = e_curr->e_next;
399                                                 /* exchange the pointers */
400                                                 e_temp = e_curr->e_next->e_next;
401                                                 e_curr->e_next->e_next = e_curr;
402                                                 e_curr->e_next = e_temp;
403                                                 /* flip the exchanged flag */
404                                                 swixd = 1;
405                                         }
406                                 }
407                                 /* if we had no exchanges, we're done reshuffling the pointers */
408                                 if (!swixd) {
409                                         break;
410                                 }
411                         }
412                 }
413         }
414
415         free(edgbuf);
416         return 1;
417 }
418
419 int PLX_raskterize(float(*base_verts)[2], int num_base_verts,
420                    float *buf, int buf_x, int buf_y)
421 {
422         int i;                                   /* i: Loop counter. */
423         struct PolyVert *ply;                   /* ply: Pointer to a list of integer buffer-space vertex coordinates. */
424         struct r_FillContext ctx = {0};
425         const float buf_x_f = (float)(buf_x);
426         const float buf_y_f = (float)(buf_y);
427         /*
428          * Allocate enough memory for our PolyVert list. It'll be the size of the PolyVert
429          * data structure multiplied by the number of base_verts.
430          *
431          * In the event of a failure to allocate the memory, return 0, so this error can
432          * be distinguished as a memory allocation error.
433          */
434         if ((ply = (struct PolyVert *)(malloc(sizeof(struct PolyVert) * num_base_verts))) == NULL) {
435                 return(0);
436         }
437
438         ctx.rb.buf = buf;                            /* Set the output buffer pointer. */
439         ctx.rb.sizex = buf_x;                        /* Set the output buffer size in X. (width) */
440         ctx.rb.sizey = buf_y;                        /* Set the output buffer size in Y. (height) */
441         /*
442          * Loop over all verts passed in to be rasterized. Each vertex's X and Y coordinates are
443          * then converted from normalized screen space (0.0 <= POS <= 1.0) to integer coordinates
444          * in the buffer-space coordinates passed in inside buf_x and buf_y.
445          *
446          * It's worth noting that this function ONLY outputs fully white pixels in a mask. Every pixel
447          * drawn will be 1.0f in value, there is no anti-aliasing.
448          */
449
450         for (i = 0; i < num_base_verts; i++) {                      /* Loop over all base_verts. */
451                 ply[i].x = (int)((base_verts[i][0] * buf_x_f) + 0.5f);  /* Range expand normalized X to integer buffer-space X. */
452                 ply[i].y = (int)((base_verts[i][1] * buf_y_f) + 0.5f);  /* Range expand normalized Y to integer buffer-space Y. */
453         }
454
455         i = rast_scan_fill(&ctx, ply, num_base_verts,1.0f);  /* Call our rasterizer, passing in the integer coords for each vert. */
456
457         free(ply);                                      /* Free the memory allocated for the integer coordinate table. */
458         return(i);                                      /* Return the value returned by the rasterizer. */
459 }