doxygen: add newline after \file
[blender.git] / source / blender / blenlib / intern / bitmap_draw_2d.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  *
19  * The Original Code is: some of this file.
20  *
21  * */
22
23 /** \file
24  * \ingroup bli
25  *
26  * Utility functions for primitive drawing operations.
27  */
28
29 #include <limits.h>
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_bitmap_draw_2d.h"
34
35 #include "BLI_math_base.h"
36 #include "BLI_sort.h"
37 #include "BLI_utildefines.h"
38
39 #include "BLI_strict_flags.h"
40
41 /* -------------------------------------------------------------------- */
42 /** \name Draw Line
43  * \{ */
44
45 /**
46  * Plot a line from \a p1 to \a p2 (inclusive).
47  *
48  * \note For clipped line drawing, see: http://stackoverflow.com/a/40902741/432509
49  */
50 void BLI_bitmap_draw_2d_line_v2v2i(
51         const int p1[2], const int p2[2],
52         bool (*callback)(int, int, void *), void *user_data)
53 {
54         /* Bresenham's line algorithm. */
55         int x1 = p1[0];
56         int y1 = p1[1];
57         int x2 = p2[0];
58         int y2 = p2[1];
59
60         if (callback(x1, y1, user_data) == 0) {
61                 return;
62         }
63
64         /* if x1 == x2 or y1 == y2, then it does not matter what we set here */
65         const int sign_x = (x2 > x1) ? 1 : -1;
66         const int sign_y = (y2 > y1) ? 1 : -1;
67
68         const int delta_x = (sign_x == 1) ? (x2 - x1) : (x1 - x2);
69         const int delta_y = (sign_y == 1) ? (y2 - y1) : (y1 - y2);
70
71         const int delta_x_step = delta_x * 2;
72         const int delta_y_step = delta_y * 2;
73
74         if (delta_x >= delta_y) {
75                 /* error may go below zero */
76                 int error = delta_y_step - delta_x;
77
78                 while (x1 != x2) {
79                         if (error >= 0) {
80                                 if (error || (sign_x == 1)) {
81                                         y1 += sign_y;
82                                         error -= delta_x_step;
83                                 }
84                                 /* else do nothing */
85                         }
86                         /* else do nothing */
87
88                         x1 += sign_x;
89                         error += delta_y_step;
90
91                         if (callback(x1, y1, user_data) == 0) {
92                                 return;
93                         }
94                 }
95         }
96         else {
97                 /* error may go below zero */
98                 int error = delta_x_step - delta_y;
99
100                 while (y1 != y2) {
101                         if (error >= 0) {
102                                 if (error || (sign_y == 1)) {
103                                         x1 += sign_x;
104                                         error -= delta_y_step;
105                                 }
106                                 /* else do nothing */
107                         }
108                         /* else do nothing */
109
110                         y1 += sign_y;
111                         error += delta_x_step;
112
113                         if (callback(x1, y1, user_data) == 0) {
114                                 return;
115                         }
116                 }
117         }
118 }
119
120 /** \} */
121
122 /* -------------------------------------------------------------------- */
123 /** \name Draw Filled Triangle
124  * \{ */
125
126 /**
127  * Fill a triangle
128  *
129  * Standard algorithm,
130  * See: http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html
131  *
132  * Changes to the basic implementation:
133  *
134  * - Reuse slope calculation when drawing the second triangle.
135  * - Don't calculate the 4th point at all for the triangle split.
136  * - Order line drawing from left to right (minor detail).
137  * - 1-pixel offsets are applied so adjacent triangles don't overlap.
138  *
139  * This is not clipped, a clipped version can be added if needed.
140  */
141
142 /* Macros could be moved to a shared location. */
143 #define ORDERED_SWAP(ty, a, b) \
144         if (a > b) { SWAP(ty, a, b); } ((void)0)
145
146 #define ORDERED_SWAP_BY(ty, a, b, by) \
147         if ((a by) > (b by)) { SWAP(ty, a, b); } ((void)0)
148
149 #define ORDER_VARS2(ty, a, b) \
150         { ORDERED_SWAP(ty, a, b); } ((void)0)
151
152 #define ORDER_VARS3_BY(ty, a, b, c, by) \
153         { \
154                 ORDERED_SWAP_BY(ty, b, c, by); \
155                 ORDERED_SWAP_BY(ty, a, c, by); \
156                 ORDERED_SWAP_BY(ty, a, b, by); \
157         } ((void)0)
158
159 static float inv_slope(const int a[2], const int b[2])
160 {
161         return ((float)(a[0] - b[0]) /
162                 (float)(a[1] - b[1]));
163 }
164
165 /**
166  * <pre>
167  * *---*
168  * \ /
169  *   *
170  * </pre>
171  */
172 static void draw_tri_flat_max(
173         const int p[2],
174         const int max_y,
175         const float inv_slope1,
176         const float inv_slope2,
177         void (*callback)(int x, int x_end, int y, void *),
178         void *user_data)
179 {
180         float cur_x1 = (float)p[0];
181         float cur_x2 = cur_x1;
182         /* start-end inclusive */
183         const int min_y = p[1];
184         const int max_y_end = max_y + 1;
185         for (int scanline_y = min_y; scanline_y != max_y_end; scanline_y += 1) {
186                 callback((int)cur_x1, 1 + (int)cur_x2, scanline_y, user_data);
187                 cur_x1 += inv_slope1;
188                 cur_x2 += inv_slope2;
189         }
190 }
191
192 /**
193  * <pre>
194  *   *
195  *  / \
196  * *---*
197  * </pre>
198  */
199 static void draw_tri_flat_min(
200         const int p[2],
201         const int min_y,
202         const float inv_slope1,
203         const float inv_slope2,
204         void (*callback)(int x, int x_end, int y, void *),
205         void *user_data)
206 {
207         float cur_x1 = (float)p[0];
208         float cur_x2 = cur_x1;
209         /* start-end inclusive */
210         const int max_y = p[1];
211         const int min_y_end = min_y - 1;
212         for (int scanline_y = max_y; scanline_y != min_y_end; scanline_y -= 1) {
213                 callback((int)cur_x1, 1 + (int)cur_x2, scanline_y, user_data);
214                 cur_x1 -= inv_slope1;
215                 cur_x2 -= inv_slope2;
216         }
217 }
218
219 /**
220  * \note Unclipped (clipped version can be added if needed).
221  */
222 void BLI_bitmap_draw_2d_tri_v2i(
223         /* all 2d */
224         const int p1[2],
225         const int p2[2],
226         const int p3[2],
227         void (*callback)(int x, int x_end, int y, void *),
228         void *user_data)
229 {
230         /* At first sort the three vertices by y-coordinate ascending so p1 is the top-most vertice */
231         ORDER_VARS3_BY(const int *, p1, p2, p3, [1]);
232
233         BLI_assert(p1[1] <= p2[1] && p2[1] <= p3[1]);
234
235         /* Check for trivial case of bottom-flat triangle. */
236         if (p2[1] == p3[1]) {
237                 float inv_slope1 = inv_slope(p2, p1);
238                 float inv_slope2 = inv_slope(p3, p1);
239                 ORDER_VARS2(float, inv_slope1, inv_slope2);
240                 BLI_assert(!(inv_slope1 > inv_slope2));
241                 draw_tri_flat_max(
242                         p1, p2[1],
243                         inv_slope1, inv_slope2,
244                         callback, user_data);
245         }
246         else if (p1[1] == p2[1]) {
247                 /* Check for trivial case of top-flat triangle. */
248                 float inv_slope1 = inv_slope(p3, p1);
249                 float inv_slope2 = inv_slope(p3, p2);
250                 ORDER_VARS2(float, inv_slope2, inv_slope1);
251                 BLI_assert(!(inv_slope1 < inv_slope2));
252                 draw_tri_flat_min(
253                         p3, p2[1] + 1, /* avoid overlap */
254                         inv_slope1, inv_slope2,
255                         callback, user_data);
256         }
257         else {
258                 /* General case - split the triangle in a top-flat and bottom-flat one. */
259                 const float inv_slope_p21 = inv_slope(p2, p1);
260                 const float inv_slope_p31 = inv_slope(p3, p1);
261                 const float inv_slope_p32 = inv_slope(p3, p2);
262
263                 float inv_slope1_max, inv_slope2_max;
264                 float inv_slope2_min, inv_slope1_min;
265
266                 if (inv_slope_p21 < inv_slope_p31) {
267                         inv_slope1_max = inv_slope_p21;
268                         inv_slope2_max = inv_slope_p31;
269                         inv_slope2_min = inv_slope_p31;
270                         inv_slope1_min = inv_slope_p32;
271                 }
272                 else {
273                         inv_slope1_max = inv_slope_p31;
274                         inv_slope2_max = inv_slope_p21;
275                         inv_slope2_min = inv_slope_p32;
276                         inv_slope1_min = inv_slope_p31;
277                 }
278
279                 draw_tri_flat_max(
280                         p1, p2[1],
281                         inv_slope1_max, inv_slope2_max,
282                         callback, user_data);
283                 draw_tri_flat_min(
284                         p3, p2[1] + 1, /* avoid overlap */
285                         inv_slope1_min, inv_slope2_min,
286                         callback, user_data);
287         }
288 }
289
290 #undef ORDERED_SWAP
291 #undef ORDERED_SWAP_BY
292 #undef ORDER_VARS2
293 #undef ORDER_VARS3_BY
294
295 /** \} */
296
297 /* -------------------------------------------------------------------- */
298 /** \name Draw Filled Polygon
299  * \{ */
300
301 /* sort edge-segments on y, then x axis */
302 static int draw_poly_v2i_n__span_y_sort(const void *a_p, const void *b_p, void *verts_p)
303 {
304         const int (*verts)[2] = verts_p;
305         const int *a = a_p;
306         const int *b = b_p;
307         const int *co_a = verts[a[0]];
308         const int *co_b = verts[b[0]];
309
310         if (co_a[1] < co_b[1]) {
311                 return -1;
312         }
313         else if (co_a[1] > co_b[1]) {
314                 return 1;
315         }
316         else if (co_a[0] < co_b[0]) {
317                 return -1;
318         }
319         else if (co_a[0] > co_b[0]) {
320                 return 1;
321         }
322         else {
323                 /* co_a & co_b are identical, use the line closest to the x-min */
324                 const int *co = co_a;
325                 co_a = verts[a[1]];
326                 co_b = verts[b[1]];
327                 int ord = (((co_b[0] - co[0]) * (co_a[1] - co[1])) -
328                            ((co_a[0] - co[0]) * (co_b[1] - co[1])));
329                 if (ord > 0) {
330                         return -1;
331                 }
332                 if (ord < 0) {
333                         return 1;
334                 }
335         }
336         return 0;
337 }
338
339 /**
340  * Draws a filled polygon with support for self intersections.
341  *
342  * \param callback: Takes the x, y coords and x-span (\a x_end is not inclusive),
343  * note that \a x_end will always be greater than \a x, so we can use:
344  *
345  * \code{.c}
346  * do {
347  *     func(x, y);
348  * } while (++x != x_end);
349  * \endcode
350  */
351 void BLI_bitmap_draw_2d_poly_v2i_n(
352         const int xmin, const int ymin, const int xmax, const int ymax,
353         const int verts[][2], const int verts_len,
354         void (*callback)(int x, int x_end, int y, void *), void *user_data)
355 {
356         /* Originally by Darel Rex Finley, 2007.
357          * Optimized by Campbell Barton, 2016 to track sorted intersections. */
358
359         int (*span_y)[2] = MEM_mallocN(sizeof(*span_y) * (size_t)verts_len, __func__);
360         int span_y_len = 0;
361
362         for (int i_curr = 0, i_prev = verts_len - 1; i_curr < verts_len; i_prev = i_curr++) {
363                 const int *co_prev = verts[i_prev];
364                 const int *co_curr = verts[i_curr];
365
366                 if (co_prev[1] != co_curr[1]) {
367                         /* Any segments entirely above or below the area of interest can be skipped. */
368                         if ((min_ii(co_prev[1], co_curr[1]) >= ymax) ||
369                             (max_ii(co_prev[1], co_curr[1]) <  ymin))
370                         {
371                                 continue;
372                         }
373
374                         int *s = span_y[span_y_len++];
375                         if (co_prev[1] < co_curr[1]) {
376                                 s[0] = i_prev;
377                                 s[1] = i_curr;
378                         }
379                         else {
380                                 s[0] = i_curr;
381                                 s[1] = i_prev;
382                         }
383                 }
384         }
385
386         BLI_qsort_r(span_y, (size_t)span_y_len, sizeof(*span_y), draw_poly_v2i_n__span_y_sort, (void *)verts);
387
388         struct NodeX {
389                 int span_y_index;
390                 int x;
391         } *node_x = MEM_mallocN(sizeof(*node_x) * (size_t)(verts_len + 1), __func__);
392         int node_x_len = 0;
393
394         int span_y_index = 0;
395         if (span_y_len != 0 && verts[span_y[0][0]][1] < ymin) {
396                 while ((span_y_index < span_y_len) &&
397                        (verts[span_y[span_y_index][0]][1] < ymin))
398                 {
399                         BLI_assert(verts[span_y[span_y_index][0]][1] <
400                                    verts[span_y[span_y_index][1]][1]);
401                         if (verts[span_y[span_y_index][1]][1] >= ymin) {
402                                 struct NodeX *n = &node_x[node_x_len++];
403                                 n->span_y_index = span_y_index;
404                         }
405                         span_y_index += 1;
406                 }
407         }
408
409         /* Loop through the rows of the image. */
410         for (int pixel_y = ymin; pixel_y < ymax; pixel_y++) {
411                 bool is_sorted = true;
412                 bool do_remove = false;
413
414                 for (int i = 0, x_ix_prev = INT_MIN; i < node_x_len; i++) {
415                         struct NodeX *n = &node_x[i];
416                         const int *s = span_y[n->span_y_index];
417                         const int *co_prev = verts[s[0]];
418                         const int *co_curr = verts[s[1]];
419
420                         BLI_assert(co_prev[1] < pixel_y && co_curr[1] >= pixel_y);
421
422                         const double x    = (co_prev[0] - co_curr[0]);
423                         const double y    = (co_prev[1] - co_curr[1]);
424                         const double y_px = (pixel_y    - co_curr[1]);
425                         const int    x_ix = (int)((double)co_curr[0] + ((y_px / y) * x));
426                         n->x = x_ix;
427
428                         if (is_sorted && (x_ix_prev > x_ix)) {
429                                 is_sorted = false;
430                         }
431                         if (do_remove == false && co_curr[1] == pixel_y) {
432                                 do_remove = true;
433                         }
434                         x_ix_prev = x_ix;
435                 }
436
437                 /* Sort the nodes, via a simple "Bubble" sort. */
438                 if (is_sorted == false) {
439                         int i = 0;
440                         const int node_x_end = node_x_len - 1;
441                         while (i < node_x_end) {
442                                 if (node_x[i].x > node_x[i + 1].x) {
443                                         SWAP(struct NodeX, node_x[i], node_x[i + 1]);
444                                         if (i != 0) {
445                                                 i -= 1;
446                                         }
447                                 }
448                                 else {
449                                         i += 1;
450                                 }
451                         }
452                 }
453
454                 /* Fill the pixels between node pairs. */
455                 for (int i = 0; i < node_x_len; i += 2) {
456                         int x_src = node_x[i].x;
457                         int x_dst = node_x[i + 1].x;
458
459                         if (x_src >= xmax) {
460                                 break;
461                         }
462
463                         if (x_dst > xmin) {
464                                 if (x_src < xmin) {
465                                         x_src = xmin;
466                                 }
467                                 if (x_dst > xmax) {
468                                         x_dst = xmax;
469                                 }
470                                 /* for single call per x-span */
471                                 if (x_src < x_dst) {
472                                         callback(x_src - xmin, x_dst - xmin, pixel_y - ymin, user_data);
473                                 }
474                         }
475                 }
476
477                 /* Clear finalized nodes in one pass, only when needed
478                  * (avoids excessive array-resizing). */
479                 if (do_remove == true) {
480                         int i_dst = 0;
481                         for (int i_src = 0; i_src < node_x_len; i_src += 1) {
482                                 const int *s = span_y[node_x[i_src].span_y_index];
483                                 const int *co = verts[s[1]];
484                                 if (co[1] != pixel_y) {
485                                         if (i_dst != i_src) {
486                                                 /* x is initialized for the next pixel_y (no need to adjust here) */
487                                                 node_x[i_dst].span_y_index = node_x[i_src].span_y_index;
488                                         }
489                                         i_dst += 1;
490                                 }
491                         }
492                         node_x_len = i_dst;
493                 }
494
495                 /* Scan for new x-nodes */
496                 while ((span_y_index < span_y_len) &&
497                        (verts[span_y[span_y_index][0]][1] == pixel_y))
498                 {
499                         /* note, node_x these are just added at the end,
500                          * not ideal but sorting once will resolve. */
501
502                         /* x is initialized for the next pixel_y */
503                         struct NodeX *n = &node_x[node_x_len++];
504                         n->span_y_index = span_y_index;
505                         span_y_index += 1;
506                 }
507         }
508
509         MEM_freeN(span_y);
510         MEM_freeN(node_x);
511 }
512
513 /** \} */