Blender V5.3
bitmap_draw_2d.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2001-2002 NaN Holding BV. All rights reserved.
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include <algorithm>
12#include <climits>
13
14#include "MEM_guardedalloc.h"
15
16#include "BLI_bitmap_draw_2d.hh"
17
18#include "BLI_math_base_c.hh"
19#include "BLI_sort.hh"
20#include "BLI_utildefines.hh"
21
22#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
23
24namespace blender {
25
26/* -------------------------------------------------------------------- */
29
30void BLI_bitmap_draw_2d_line_v2v2i(const int p1[2],
31 const int p2[2],
32 bool (*callback)(int, int, void *),
33 void *user_data)
34{
35 /* Bresenham's line algorithm. */
36 int x1 = p1[0];
37 int y1 = p1[1];
38 int x2 = p2[0];
39 int y2 = p2[1];
40
41 if (callback(x1, y1, user_data) == 0) {
42 return;
43 }
44
45 /* if x1 == x2 or y1 == y2, then it does not matter what we set here */
46 const int sign_x = (x2 > x1) ? 1 : -1;
47 const int sign_y = (y2 > y1) ? 1 : -1;
48
49 const int delta_x = (sign_x == 1) ? (x2 - x1) : (x1 - x2);
50 const int delta_y = (sign_y == 1) ? (y2 - y1) : (y1 - y2);
51
52 const int delta_x_step = delta_x * 2;
53 const int delta_y_step = delta_y * 2;
54
55 if (delta_x >= delta_y) {
56 /* error may go below zero */
57 int error = delta_y_step - delta_x;
58
59 while (x1 != x2) {
60 if (error >= 0) {
61 if (error || (sign_x == 1)) {
62 y1 += sign_y;
63 error -= delta_x_step;
64 }
65 /* else do nothing */
66 }
67 /* else do nothing */
68
69 x1 += sign_x;
70 error += delta_y_step;
71
72 if (callback(x1, y1, user_data) == 0) {
73 return;
74 }
75 }
76 }
77 else {
78 /* error may go below zero */
79 int error = delta_x_step - delta_y;
80
81 while (y1 != y2) {
82 if (error >= 0) {
83 if (error || (sign_y == 1)) {
84 x1 += sign_x;
85 error -= delta_y_step;
86 }
87 /* else do nothing */
88 }
89 /* else do nothing */
90
91 y1 += sign_y;
92 error += delta_x_step;
93
94 if (callback(x1, y1, user_data) == 0) {
95 return;
96 }
97 }
98 }
99}
100
102
103/* -------------------------------------------------------------------- */
106
122
123/* Macros could be moved to a shared location. */
124#define ORDERED_SWAP(ty, a, b) \
125 if (a > b) { \
126 SWAP(ty, a, b); \
127 } \
128 ((void)0)
129
130#define ORDERED_SWAP_BY(ty, a, b, by) \
131 if ((a by) > (b by)) { \
132 SWAP(ty, a, b); \
133 } \
134 ((void)0)
135
136#define ORDER_VARS2(ty, a, b) \
137 { \
138 ORDERED_SWAP(ty, a, b); \
139 } \
140 ((void)0)
141
142#define ORDER_VARS3_BY(ty, a, b, c, by) \
143 { \
144 ORDERED_SWAP_BY(ty, b, c, by); \
145 ORDERED_SWAP_BY(ty, a, c, by); \
146 ORDERED_SWAP_BY(ty, a, b, by); \
147 } \
148 ((void)0)
149
150static float inv_slope(const int a[2], const int b[2])
151{
152 return float(a[0] - b[0]) / float(a[1] - b[1]);
153}
154
162static void draw_tri_flat_max(const int p[2],
163 const int max_y,
164 const float inv_slope1,
165 const float inv_slope2,
166 void (*callback)(int x, int x_end, int y, void *),
167 void *user_data)
168{
169 float cur_x1 = float(p[0]);
170 float cur_x2 = cur_x1;
171 /* start-end inclusive */
172 const int min_y = p[1];
173 const int max_y_end = max_y + 1;
174 for (int scanline_y = min_y; scanline_y != max_y_end; scanline_y += 1) {
175 callback(int(cur_x1), 1 + int(cur_x2), scanline_y, user_data);
176 cur_x1 += inv_slope1;
177 cur_x2 += inv_slope2;
178 }
179}
180
188static void draw_tri_flat_min(const int p[2],
189 const int min_y,
190 const float inv_slope1,
191 const float inv_slope2,
192 void (*callback)(int x, int x_end, int y, void *),
193 void *user_data)
194{
195 float cur_x1 = float(p[0]);
196 float cur_x2 = cur_x1;
197 /* start-end inclusive */
198 const int max_y = p[1];
199 const int min_y_end = min_y - 1;
200 for (int scanline_y = max_y; scanline_y != min_y_end; scanline_y -= 1) {
201 callback(int(cur_x1), 1 + int(cur_x2), scanline_y, user_data);
202 cur_x1 -= inv_slope1;
203 cur_x2 -= inv_slope2;
204 }
205}
206
208 /* all 2d */
209 const int p1[2],
210 const int p2[2],
211 const int p3[2],
212 void (*callback)(int x, int x_end, int y, void *),
213 void *user_data)
214{
215 /* At first sort the three vertices by y-coordinate ascending so p1 is the top-most vertex */
216 ORDER_VARS3_BY(const int *, p1, p2, p3, [1]);
217
218 BLI_assert(p1[1] <= p2[1] && p2[1] <= p3[1]);
219
220 /* Check for trivial case of bottom-flat triangle. */
221 if (p2[1] == p3[1]) {
222 float inv_slope1 = inv_slope(p2, p1);
223 float inv_slope2 = inv_slope(p3, p1);
224 ORDER_VARS2(float, inv_slope1, inv_slope2);
225 BLI_assert(!(inv_slope1 > inv_slope2));
226 draw_tri_flat_max(p1, p2[1], inv_slope1, inv_slope2, callback, user_data);
227 }
228 else if (p1[1] == p2[1]) {
229 /* Check for trivial case of top-flat triangle. */
230 float inv_slope1 = inv_slope(p3, p1);
231 float inv_slope2 = inv_slope(p3, p2);
232 ORDER_VARS2(float, inv_slope2, inv_slope1);
233 BLI_assert(!(inv_slope1 < inv_slope2));
235 p2[1] + 1, /* avoid overlap */
236 inv_slope1,
237 inv_slope2,
238 callback,
239 user_data);
240 }
241 else {
242 /* General case - split the triangle in a top-flat and bottom-flat one. */
243 const float inv_slope_p21 = inv_slope(p2, p1);
244 const float inv_slope_p31 = inv_slope(p3, p1);
245 const float inv_slope_p32 = inv_slope(p3, p2);
246
247 float inv_slope1_max, inv_slope2_max;
248 float inv_slope2_min, inv_slope1_min;
249
250 if (inv_slope_p21 < inv_slope_p31) {
251 inv_slope1_max = inv_slope_p21;
252 inv_slope2_max = inv_slope_p31;
253 inv_slope2_min = inv_slope_p31;
254 inv_slope1_min = inv_slope_p32;
255 }
256 else {
257 inv_slope1_max = inv_slope_p31;
258 inv_slope2_max = inv_slope_p21;
259 inv_slope2_min = inv_slope_p32;
260 inv_slope1_min = inv_slope_p31;
261 }
262
263 draw_tri_flat_max(p1, p2[1], inv_slope1_max, inv_slope2_max, callback, user_data);
265 p2[1] + 1, /* avoid overlap */
266 inv_slope1_min,
267 inv_slope2_min,
268 callback,
269 user_data);
270 }
271}
272
273#undef ORDERED_SWAP
274#undef ORDERED_SWAP_BY
275#undef ORDER_VARS2
276#undef ORDER_VARS3_BY
277
279
280/* -------------------------------------------------------------------- */
283
284/* sort edge-segments on y, then x axis */
285static int draw_poly_v2i_n__span_y_sort(const void *a_p, const void *b_p, void *verts_p)
286{
287 const int (*verts)[2] = static_cast<const int (*)[2]>(verts_p);
288 const int *a = static_cast<const int *>(a_p);
289 const int *b = static_cast<const int *>(b_p);
290 const int *co_a = verts[a[0]];
291 const int *co_b = verts[b[0]];
292
293 if (co_a[1] < co_b[1]) {
294 return -1;
295 }
296 if (co_a[1] > co_b[1]) {
297 return 1;
298 }
299 if (co_a[0] < co_b[0]) {
300 return -1;
301 }
302 if (co_a[0] > co_b[0]) {
303 return 1;
304 }
305 /* co_a & co_b are identical, use the line closest to the x-min */
306 const int *co = co_a;
307 co_a = verts[a[1]];
308 co_b = verts[b[1]];
309 int ord = (((co_b[0] - co[0]) * (co_a[1] - co[1])) - ((co_a[0] - co[0]) * (co_b[1] - co[1])));
310 if (ord > 0) {
311 return -1;
312 }
313 if (ord < 0) {
314 return 1;
315 }
316 return 0;
317}
318
320 const int ymin,
321 const int xmax,
322 const int ymax,
323 const Span<int2> verts,
324 void (*callback)(int x, int x_end, int y, void *),
325 void *user_data)
326{
327 /* Originally by Darel Rex Finley, 2007.
328 * Optimized by Campbell Barton, 2016 to track sorted intersections. */
329
330 int (*span_y)[2] = MEM_new_array_uninitialized<int[2]>(size_t(verts.size()), __func__);
331 int span_y_len = 0;
332
333 for (int i_curr = 0, i_prev = int(verts.size() - 1); i_curr < verts.size(); i_prev = i_curr++) {
334 const int *co_prev = verts[i_prev];
335 const int *co_curr = verts[i_curr];
336
337 if (co_prev[1] != co_curr[1]) {
338 /* Any segments entirely above or below the area of interest can be skipped. */
339 if ((min_ii(co_prev[1], co_curr[1]) >= ymax) || (max_ii(co_prev[1], co_curr[1]) < ymin)) {
340 continue;
341 }
342
343 int *s = span_y[span_y_len++];
344 if (co_prev[1] < co_curr[1]) {
345 s[0] = i_prev;
346 s[1] = i_curr;
347 }
348 else {
349 s[0] = i_curr;
350 s[1] = i_prev;
351 }
352 }
353 }
354
355 BLI_qsort_r(span_y,
356 size_t(span_y_len),
357 sizeof(*span_y),
359 (void *)verts.data());
360
361 struct NodeX {
362 int span_y_index;
363 int x;
364 } *node_x = MEM_new_array_uninitialized<NodeX>(size_t(verts.size() + 1), __func__);
365 int node_x_len = 0;
366
367 int span_y_index = 0;
368 if (span_y_len != 0 && verts[span_y[0][0]][1] < ymin) {
369 while ((span_y_index < span_y_len) && (verts[span_y[span_y_index][0]][1] < ymin)) {
370 BLI_assert(verts[span_y[span_y_index][0]][1] < verts[span_y[span_y_index][1]][1]);
371 if (verts[span_y[span_y_index][1]][1] >= ymin) {
372 NodeX *n = &node_x[node_x_len++];
373 n->span_y_index = span_y_index;
374 }
375 span_y_index += 1;
376 }
377 }
378
379 /* Loop through the rows of the image. */
380 for (int pixel_y = ymin; pixel_y < ymax; pixel_y++) {
381 bool is_sorted = true;
382 bool do_remove = false;
383
384 for (int i = 0, x_ix_prev = INT_MIN; i < node_x_len; i++) {
385 NodeX *n = &node_x[i];
386 const int *s = span_y[n->span_y_index];
387 const int *co_prev = verts[s[0]];
388 const int *co_curr = verts[s[1]];
389
390 BLI_assert(co_prev[1] < pixel_y && co_curr[1] >= pixel_y);
391
392 const double x = (co_prev[0] - co_curr[0]);
393 const double y = (co_prev[1] - co_curr[1]);
394 const double y_px = (pixel_y - co_curr[1]);
395 const int x_ix = int(double(co_curr[0]) + ((y_px / y) * x));
396 n->x = x_ix;
397
398 if (is_sorted && (x_ix_prev > x_ix)) {
399 is_sorted = false;
400 }
401 if (do_remove == false && co_curr[1] == pixel_y) {
402 do_remove = true;
403 }
404 x_ix_prev = x_ix;
405 }
406
407 /* Sort the nodes, via a simple "Bubble" sort. */
408 if (is_sorted == false) {
409 int i = 0;
410 const int node_x_end = node_x_len - 1;
411 while (i < node_x_end) {
412 if (node_x[i].x > node_x[i + 1].x) {
413 SWAP(NodeX, node_x[i], node_x[i + 1]);
414 if (i != 0) {
415 i -= 1;
416 }
417 }
418 else {
419 i += 1;
420 }
421 }
422 }
423
424 /* Fill the pixels between node pairs. */
425 for (int i = 0; i < node_x_len; i += 2) {
426 int x_src = node_x[i].x;
427 int x_dst = node_x[i + 1].x;
428
429 if (x_src >= xmax) {
430 break;
431 }
432
433 if (x_dst > xmin) {
434 x_src = std::max(x_src, xmin);
435 x_dst = std::min(x_dst, xmax);
436 /* for single call per x-span */
437 if (x_src < x_dst) {
438 callback(x_src - xmin, x_dst - xmin, pixel_y - ymin, user_data);
439 }
440 }
441 }
442
443 /* Clear finalized nodes in one pass, only when needed
444 * (avoids excessive array-resizing). */
445 if (do_remove == true) {
446 int i_dst = 0;
447 for (int i_src = 0; i_src < node_x_len; i_src += 1) {
448 const int *s = span_y[node_x[i_src].span_y_index];
449 const int *co = verts[s[1]];
450 if (co[1] != pixel_y) {
451 if (i_dst != i_src) {
452 /* x is initialized for the next pixel_y (no need to adjust here) */
453 node_x[i_dst].span_y_index = node_x[i_src].span_y_index;
454 }
455 i_dst += 1;
456 }
457 }
458 node_x_len = i_dst;
459 }
460
461 /* Scan for new x-nodes */
462 while ((span_y_index < span_y_len) && (verts[span_y[span_y_index][0]][1] == pixel_y)) {
463 /* NOTE: node_x these are just added at the end,
464 * not ideal but sorting once will resolve. */
465
466 /* x is initialized for the next pixel_y */
467 NodeX *n = &node_x[node_x_len++];
468 n->span_y_index = span_y_index;
469 span_y_index += 1;
470 }
471 }
472
473 MEM_delete(span_y);
474 MEM_delete(node_x);
475}
476
478
479} // namespace blender
Read Blender memory allocation and freeing.
#define ORDER_VARS3_BY(ty, a, b, c, by)
#define ORDER_VARS2(ty, a, b)
#define SWAP(type, a, b)
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BLI_bitmap_draw_2d_tri_v2i(const int p1[2], const int p2[2], const int p3[2], void(*callback)(int x, int x_end, int y, void *), void *user_data)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static int draw_poly_v2i_n__span_y_sort(const void *a_p, const void *b_p, void *verts_p)
MINLINE int max_ii(int a, int b)
void BLI_bitmap_draw_2d_poly_v2i_n(int xmin, int ymin, int xmax, int ymax, Span< int2 > verts, void(*callback)(int x, int x_end, int y, void *), void *user_data)
void BLI_bitmap_draw_2d_line_v2v2i(const int p1[2], const int p2[2], bool(*callback)(int, int, void *), void *user_data)
void BLI_qsort_r(void *a, size_t n, size_t es, BLI_sort_cmp_t cmp, void *thunk)
Definition sort.cc:79
static void draw_tri_flat_max(const int p[2], const int max_y, const float inv_slope1, const float inv_slope2, void(*callback)(int x, int x_end, int y, void *), void *user_data)
static float inv_slope(const int a[2], const int b[2])
MINLINE int min_ii(int a, int b)
static void draw_tri_flat_min(const int p[2], const int min_y, const float inv_slope1, const float inv_slope2, void(*callback)(int x, int x_end, int y, void *), void *user_data)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float