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