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