Blender V5.3
bmesh_polygon.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
11
12#include <algorithm>
13#include <array>
14#include <cmath>
15
16#include "DNA_modifier_types.h"
17
18#include "BLI_array.hh"
19#include "BLI_linklist.hh"
20#include "BLI_math_base.hh"
21#include "BLI_math_geom_c.hh"
22#include "BLI_math_matrix_c.hh"
23#include "BLI_math_vector.hh"
24#include "BLI_math_vector_c.hh"
25#include "BLI_memarena.hh"
26#include "BLI_polyfill_2d.hh"
28
29#include "bmesh.hh"
30#include "bmesh_tools.hh"
31
32#include "BKE_customdata.hh"
33
35
36namespace blender {
37
41static float angle_signed_v2v2_pos(const float v1[2], const float v2[2])
42{
43 const float angle = angle_signed_v2v2(v1, v2);
44 if (angle < 0.0f) {
45 return angle + (M_PI * 2);
46 }
47 return angle;
48}
49
55static float bm_face_calc_poly_normal(const BMFace *f, float n[3])
56{
57 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
58 BMLoop *l_iter = l_first;
59 const float *v_prev = l_first->prev->v->co;
60 const float *v_curr = l_first->v->co;
61
62 zero_v3(n);
63
64 /* Newell's Method */
65 do {
66 add_newell_cross_v3_v3v3(n, v_prev, v_curr);
67
68 l_iter = l_iter->next;
69 v_prev = v_curr;
70 v_curr = l_iter->v->co;
71
72 } while (l_iter != l_first);
73
74 return normalize_v3(n);
75}
76
84 float r_no[3],
85 const Span<float3> vertexCos)
86{
87 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
88 BMLoop *l_iter = l_first;
89 const float *v_prev = vertexCos[BM_elem_index_get(l_first->prev->v)];
90 const float *v_curr = vertexCos[BM_elem_index_get(l_first->v)];
91
92 zero_v3(r_no);
93
94 /* Newell's Method */
95 do {
96 add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
97
98 l_iter = l_iter->next;
99 v_prev = v_curr;
100 v_curr = vertexCos[BM_elem_index_get(l_iter->v)];
101 } while (l_iter != l_first);
102
103 return normalize_v3(r_no);
104}
105
110 float r_cent[3],
111 const Span<float3> vert_positions)
112{
113 const BMLoop *l_first, *l_iter;
114
115 zero_v3(r_cent);
116
117 /* Newell's Method */
118 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
119 do {
120 add_v3_v3(r_cent, vert_positions[BM_elem_index_get(l_iter->v)]);
121 } while ((l_iter = l_iter->next) != l_first);
122 mul_v3_fl(r_cent, 1.0f / f->len);
123}
124
126 const bool use_fixed_quad,
127 BMLoop **r_loops,
128 uint (*r_index)[3])
129{
130 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
131 BMLoop *l_iter;
132
133 if (f->len == 3) {
134 *r_loops++ = (l_iter = l_first);
135 *r_loops++ = (l_iter = l_iter->next);
136 *r_loops++ = (l_iter->next);
137
138 r_index[0][0] = 0;
139 r_index[0][1] = 1;
140 r_index[0][2] = 2;
141 }
142 else if (f->len == 4 && use_fixed_quad) {
143 *r_loops++ = (l_iter = l_first);
144 *r_loops++ = (l_iter = l_iter->next);
145 *r_loops++ = (l_iter = l_iter->next);
146 *r_loops++ = (l_iter->next);
147
148 r_index[0][0] = 0;
149 r_index[0][1] = 1;
150 r_index[0][2] = 2;
151
152 r_index[1][0] = 0;
153 r_index[1][1] = 2;
154 r_index[1][2] = 3;
155 }
156 else {
157 float axis_mat[3][3];
159 int j;
160
161 axis_dominant_v3_to_m3_negate(axis_mat, f->no);
162
163 j = 0;
164 l_iter = l_first;
165 do {
166 mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
167 r_loops[j] = l_iter;
168 j++;
169 } while ((l_iter = l_iter->next) != l_first);
170
171 /* complete the loop */
172 BLI_polyfill_calc(reinterpret_cast<float (*)[2]>(projverts.data()), f->len, 1, r_index);
173 }
174}
175
176void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
177{
178 const BMLoop *ltri[3];
179
180 if (f->len == 3) {
181 const BMLoop *l = BM_FACE_FIRST_LOOP(f);
182 ARRAY_SET_ITEMS(ltri, l, l->next, l->prev);
183 }
184 else {
185 /* tessellation here seems overkill when in many cases this will be the center,
186 * but without this we can't be sure the point is inside a concave face. */
187 const int tottri = f->len - 2;
190 int j;
191 int j_best = 0; /* use as fallback when unset */
192 float area_best = -1.0f;
193
194 BM_face_calc_tessellation(f, false, loops.data(), reinterpret_cast<uint(*)[3]>(index.data()));
195
196 for (j = 0; j < tottri; j++) {
197 const float *p1 = loops[index[j][0]]->v->co;
198 const float *p2 = loops[index[j][1]]->v->co;
199 const float *p3 = loops[index[j][2]]->v->co;
200 const float area = area_squared_tri_v3(p1, p2, p3);
201 if (area > area_best) {
202 j_best = j;
203 area_best = area;
204 }
205 }
206
208 ltri, loops[index[j_best][0]], loops[index[j_best][1]], loops[index[j_best][2]]);
209 }
210
211 mid_v3_v3v3v3(r_co, ltri[0]->v->co, ltri[1]->v->co, ltri[2]->v->co);
212}
213
215{
216 /* inline 'area_poly_v3' logic, avoid creating a temp array */
217 const BMLoop *l_iter, *l_first;
218 float n[3];
219
220 zero_v3(n);
221 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
222 do {
223 add_newell_cross_v3_v3v3(n, l_iter->v->co, l_iter->next->v->co);
224 } while ((l_iter = l_iter->next) != l_first);
225 return len_v3(n) * 0.5f;
226}
227
228float BM_face_calc_area_with_mat3(const BMFace *f, const float mat3[3][3])
229{
230 /* inline 'area_poly_v3' logic, avoid creating a temp array */
231 const BMLoop *l_iter, *l_first;
232 float co[3];
233 float n[3];
234
235 zero_v3(n);
236 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
237 mul_v3_m3v3(co, mat3, l_iter->v->co);
238 do {
239 float co_next[3];
240 mul_v3_m3v3(co_next, mat3, l_iter->next->v->co);
241 add_newell_cross_v3_v3v3(n, co, co_next);
242 copy_v3_v3(co, co_next);
243 } while ((l_iter = l_iter->next) != l_first);
244 return len_v3(n) * 0.5f;
245}
246
247float BM_face_calc_area_uv_signed(const BMFace *f, int cd_loop_uv_offset)
248{
249 /* inline 'area_poly_v2' logic, avoid creating a temp array */
250 const BMLoop *l_iter, *l_first;
251
252 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
253 /* Green's theorem applied to area of a polygon.
254 * TODO: `cross` should be of type `double` to reduce rounding error. */
255 float cross = 0.0f;
256 do {
257 const float *luv = BM_ELEM_CD_GET_FLOAT_P(l_iter, cd_loop_uv_offset);
258 const float *luv_next = BM_ELEM_CD_GET_FLOAT_P(l_iter->next, cd_loop_uv_offset);
259 cross += (luv_next[0] - luv[0]) * (luv_next[1] + luv[1]);
260 } while ((l_iter = l_iter->next) != l_first);
261 return cross * 0.5f;
262}
263
264float BM_face_calc_area_uv(const BMFace *f, int cd_loop_uv_offset)
265{
266 return fabsf(BM_face_calc_area_uv_signed(f, cd_loop_uv_offset));
267}
268
270{
271 const BMLoop *l_iter, *l_first;
272 float perimeter = 0.0f;
273
274 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
275 do {
276 perimeter += len_v3v3(l_iter->v->co, l_iter->next->v->co);
277 } while ((l_iter = l_iter->next) != l_first);
278
279 return perimeter;
280}
281
282float BM_face_calc_perimeter_with_mat3(const BMFace *f, const float mat3[3][3])
283{
284 const BMLoop *l_iter, *l_first;
285 float co[3];
286 float perimeter = 0.0f;
287
288 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
289 mul_v3_m3v3(co, mat3, l_iter->v->co);
290 do {
291 float co_next[3];
292 mul_v3_m3v3(co_next, mat3, l_iter->next->v->co);
293 perimeter += len_v3v3(co, co_next);
294 copy_v3_v3(co, co_next);
295 } while ((l_iter = l_iter->next) != l_first);
296
297 return perimeter;
298}
299
306{
307/* find the most 'unique' loop, (greatest difference to others) */
308#if 1
309 /* Optimized version that avoids `sqrt`. */
310 float difs[3];
311 for (int i_prev = 1, i_curr = 2, i_next = 0; i_next < 3; i_prev = i_curr, i_curr = i_next++) {
312 const float *co = verts[i_curr]->co;
313 const float *co_other[2] = {verts[i_prev]->co, verts[i_next]->co};
314 float proj_dir[3];
315 mid_v3_v3v3(proj_dir, co_other[0], co_other[1]);
316 sub_v3_v3(proj_dir, co);
317
318 float proj_pair[2][3];
319 project_v3_v3v3(proj_pair[0], co_other[0], proj_dir);
320 project_v3_v3v3(proj_pair[1], co_other[1], proj_dir);
321 difs[i_next] = len_squared_v3v3(proj_pair[0], proj_pair[1]);
322 }
323#else
324 const float lens[3] = {
325 len_v3v3(verts[0]->co, verts[1]->co),
326 len_v3v3(verts[1]->co, verts[2]->co),
327 len_v3v3(verts[2]->co, verts[0]->co),
328 };
329 const float difs[3] = {
330 fabsf(lens[1] - lens[2]),
331 fabsf(lens[2] - lens[0]),
332 fabsf(lens[0] - lens[1]),
333 };
334#endif
335
336 int order[3] = {0, 1, 2};
337 axis_sort_v3(difs, order);
338
339 return order[0];
340}
341
342void BM_vert_tri_calc_tangent_from_edge(BMVert *verts[3], float r_tangent[3])
343{
344 const int index = bm_vert_tri_find_unique_edge(verts);
345 const int index_next = (index + 1) % 3;
346
347 sub_v3_v3v3(r_tangent, verts[index]->co, verts[index_next]->co);
348 normalize_v3(r_tangent);
349}
350
352 float r_tangent_a[3],
353 float r_tangent_b[3])
354{
355 const int index = bm_vert_tri_find_unique_edge(verts);
356 const int index_next = (index + 1) % 3;
357 const int index_prev = (index_next + 1) % 3;
358
359 sub_v3_v3v3(r_tangent_a, verts[index]->co, verts[index_next]->co);
360 normalize_v3(r_tangent_a);
361
362 /* Pick the adjacent loop that is least co-linear. */
363 float vec_prev[3], vec_next[3];
364 float tmp_prev[3], tmp_next[3];
365
366 sub_v3_v3v3(vec_prev, verts[index_prev]->co, verts[index]->co);
367 sub_v3_v3v3(vec_next, verts[index_next]->co, verts[index_prev]->co);
368
369 cross_v3_v3v3(tmp_prev, r_tangent_a, vec_prev);
370 cross_v3_v3v3(tmp_next, r_tangent_a, vec_next);
371
372 normalize_v3_v3(r_tangent_b,
373 len_squared_v3(tmp_next) > len_squared_v3(tmp_prev) ? vec_next : vec_prev);
374}
375
376void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3])
377{
378 const int index = bm_vert_tri_find_unique_edge(verts);
379
380 const float *v_a = verts[index]->co;
381 const float *v_b = verts[(index + 1) % 3]->co;
382 const float *v_other = verts[(index + 2) % 3]->co;
383
384 mid_v3_v3v3(r_tangent, v_a, v_b);
385 sub_v3_v3v3(r_tangent, v_other, r_tangent);
386
387 normalize_v3(r_tangent);
388}
389
390void BM_face_calc_tangent_from_edge(const BMFace *f, float r_tangent[3])
391{
392 const BMLoop *l_long = BM_face_find_longest_loop(const_cast<BMFace *>(f));
393
394 sub_v3_v3v3(r_tangent, l_long->v->co, l_long->next->v->co);
395
396 normalize_v3(r_tangent);
397}
398
399static void bm_face_calc_tangent_from_quad_edge_pair(const BMFace *f, float r_tangent[3])
400{
401 BMVert *verts[4];
402 float vec[3], vec_a[3], vec_b[3];
403
404 BM_face_as_array_vert_quad(const_cast<BMFace *>(f), verts);
405
406 sub_v3_v3v3(vec_a, verts[3]->co, verts[2]->co);
407 sub_v3_v3v3(vec_b, verts[0]->co, verts[1]->co);
408 add_v3_v3v3(r_tangent, vec_a, vec_b);
409
410 sub_v3_v3v3(vec_a, verts[0]->co, verts[3]->co);
411 sub_v3_v3v3(vec_b, verts[1]->co, verts[2]->co);
412 add_v3_v3v3(vec, vec_a, vec_b);
413 /* use the longest edge length */
414 if (len_squared_v3(r_tangent) < len_squared_v3(vec)) {
415 copy_v3_v3(r_tangent, vec);
416 }
417 normalize_v3(r_tangent);
418}
419
421 float r_tangent_a[3],
422 float r_tangent_b[3])
423{
424 BLI_assert(f->len == 4);
425 BMVert *verts[4];
426 float vec_a[3], vec_b[3];
427
428 BM_face_as_array_vert_quad(const_cast<BMFace *>(f), verts);
429
430 sub_v3_v3v3(vec_a, verts[3]->co, verts[2]->co);
431 sub_v3_v3v3(vec_b, verts[0]->co, verts[1]->co);
432 add_v3_v3v3(r_tangent_a, vec_a, vec_b);
433
434 sub_v3_v3v3(vec_a, verts[0]->co, verts[3]->co);
435 sub_v3_v3v3(vec_b, verts[1]->co, verts[2]->co);
436 add_v3_v3v3(r_tangent_b, vec_a, vec_b);
437
438 /* `r_tangent_a` always gets the longest edge. */
439 if (normalize_v3(r_tangent_a) < normalize_v3(r_tangent_b)) {
440 swap_v3_v3(r_tangent_a, r_tangent_b);
441 }
442}
443
445 float r_tangent_a[3],
446 float r_tangent_b[3])
447{
448 const BMLoop *l_long = BM_face_find_longest_loop(const_cast<BMFace *>(f));
449
450 sub_v3_v3v3(r_tangent_a, l_long->v->co, l_long->next->v->co);
451 normalize_v3(r_tangent_a);
452
453 /* Pick the adjacent loop that is least co-linear. */
454 float vec_prev[3], vec_next[3];
455 float tmp_prev[3], tmp_next[3];
456
457 sub_v3_v3v3(vec_prev, l_long->prev->v->co, l_long->v->co);
458 sub_v3_v3v3(vec_next, l_long->next->v->co, l_long->next->next->v->co);
459
460 cross_v3_v3v3(tmp_prev, r_tangent_a, vec_prev);
461 cross_v3_v3v3(tmp_next, r_tangent_a, vec_next);
462
463 normalize_v3_v3(r_tangent_b,
464 len_squared_v3(tmp_next) > len_squared_v3(tmp_prev) ? vec_next : vec_prev);
465}
466
467void BM_face_calc_tangent_from_edge_pair(const BMFace *f, float r_tangent[3])
468{
469 if (f->len == 3) {
470 BMVert *verts[3];
471
472 BM_face_as_array_vert_tri(const_cast<BMFace *>(f), verts);
473
474 BM_vert_tri_calc_tangent_edge_pair(verts, r_tangent);
475 }
476 else if (f->len == 4) {
477 /* Use longest edge pair */
478 float r_tangent_dummy[3];
479 bm_face_calc_tangent_pair_from_quad_edge_pair(f, r_tangent, r_tangent_dummy);
480 }
481 else {
482 /* For ngons use two longest disconnected edges */
483 BMLoop *l_long = BM_face_find_longest_loop(const_cast<BMFace *>(f));
484 BMLoop *l_long_other = nullptr;
485
486 float len_max_sq = 0.0f;
487 float vec_a[3], vec_b[3];
488
489 BMLoop *l_iter = l_long->prev->prev;
490 BMLoop *l_last = l_long->next;
491
492 do {
493 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
494 if (len_sq >= len_max_sq) {
495 l_long_other = l_iter;
496 len_max_sq = len_sq;
497 }
498 } while ((l_iter = l_iter->prev) != l_last);
499
500 sub_v3_v3v3(vec_a, l_long->next->v->co, l_long->v->co);
501 sub_v3_v3v3(vec_b, l_long_other->v->co, l_long_other->next->v->co);
502 add_v3_v3v3(r_tangent, vec_a, vec_b);
503
504 /* Edges may not be opposite side of the ngon,
505 * this could cause problems for ngons with multiple-aligned edges of the same length.
506 * Fall back to longest edge. */
507 if (normalize_v3(r_tangent) == 0.0f) [[unlikely]] {
508 normalize_v3_v3(r_tangent, vec_a);
509 }
510 }
511}
512
513void BM_face_calc_tangent_from_edge_diagonal(const BMFace *f, float r_tangent[3])
514{
515 BMLoop *l_iter, *l_first;
516
517 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
518
519 /* In case of degenerate faces. */
520 zero_v3(r_tangent);
521
522 /* WARNING: O(n^2) loop here, take care! */
523 float dist_max_sq = 0.0f;
524 do {
525 BMLoop *l_iter_other = l_iter->next;
526 BMLoop *l_iter_last = l_iter->prev;
527 do {
528 BLI_assert(!ELEM(l_iter->v, l_iter_other->v, l_iter_other->next->v));
529 float co_other[3], vec[3];
531 co_other, l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co);
532 sub_v3_v3v3(vec, l_iter->v->co, co_other);
533
534 const float dist_sq = len_squared_v3(vec);
535 if (dist_sq > dist_max_sq) {
536 dist_max_sq = dist_sq;
537 copy_v3_v3(r_tangent, vec);
538 }
539 } while ((l_iter_other = l_iter_other->next) != l_iter_last);
540 } while ((l_iter = l_iter->next) != l_first);
541
542 normalize_v3(r_tangent);
543}
544
545void BM_face_calc_tangent_from_vert_diagonal(const BMFace *f, float r_tangent[3])
546{
547 BMLoop *l_iter, *l_first;
548
549 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
550
551 /* In case of degenerate faces. */
552 zero_v3(r_tangent);
553
554 /* WARNING: O(n^2) loop here, take care! */
555 float dist_max_sq = 0.0f;
556 do {
557 BMLoop *l_iter_other = l_iter->next;
558 do {
559 float vec[3];
560 sub_v3_v3v3(vec, l_iter->v->co, l_iter_other->v->co);
561
562 const float dist_sq = len_squared_v3(vec);
563 if (dist_sq > dist_max_sq) {
564 dist_max_sq = dist_sq;
565 copy_v3_v3(r_tangent, vec);
566 }
567 } while ((l_iter_other = l_iter_other->next) != l_iter);
568 } while ((l_iter = l_iter->next) != l_first);
569
570 normalize_v3(r_tangent);
571}
572
573void BM_face_calc_tangent_auto(const BMFace *f, float r_tangent[3])
574{
575 if (f->len == 3) {
576 /* most 'unique' edge of a triangle */
577 BMVert *verts[3];
578 BM_face_as_array_vert_tri(const_cast<BMFace *>(f), verts);
579 BM_vert_tri_calc_tangent_from_edge(verts, r_tangent);
580 }
581 else if (f->len == 4) {
582 /* longest edge pair of a quad */
584 }
585 else {
586 /* longest edge of an ngon */
587 BM_face_calc_tangent_from_edge(f, r_tangent);
588 }
589}
590
591void BM_face_calc_tangent_pair_auto(const BMFace *f, float r_tangent_a[3], float r_tangent_b[3])
592{
593 if (f->len == 3) {
594 /* most 'unique' edge of a triangle */
595 BMVert *verts[3];
596 BM_face_as_array_vert_tri(const_cast<BMFace *>(f), verts);
597 BM_vert_tri_calc_tangent_pair_from_edge(verts, r_tangent_a, r_tangent_b);
598 }
599 else if (f->len == 4) {
600 /* longest edge pair of a quad */
601 bm_face_calc_tangent_pair_from_quad_edge_pair(f, r_tangent_a, r_tangent_b);
602 }
603 else {
604 /* longest edge of an ngon */
605 BM_face_calc_tangent_pair_from_edge(f, r_tangent_a, r_tangent_b);
606 }
607}
608
609void BM_face_calc_bounds_expand(const BMFace *f, float min[3], float max[3])
610{
611 const BMLoop *l_iter, *l_first;
612 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
613 do {
614 minmax_v3v3_v3(min, max, l_iter->v->co);
615 } while ((l_iter = l_iter->next) != l_first);
616}
617
618void BM_face_calc_center_bounds(const BMFace *f, float r_cent[3])
619{
620 const BMLoop *l_iter, *l_first;
621 float min[3], max[3];
622
624
625 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
626 do {
627 minmax_v3v3_v3(min, max, l_iter->v->co);
628 } while ((l_iter = l_iter->next) != l_first);
629
630 mid_v3_v3v3(r_cent, min, max);
631}
632
634 const BMFace *f,
635 float r_cent[3],
636 const Span<float3> vert_positions)
637{
638 /* must have valid index data */
640 (void)bm;
641
642 const BMLoop *l_iter, *l_first;
643 float min[3], max[3];
644
646
647 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
648 do {
649 minmax_v3v3_v3(min, max, vert_positions[BM_elem_index_get(l_iter->v)]);
650 } while ((l_iter = l_iter->next) != l_first);
651
652 mid_v3_v3v3(r_cent, min, max);
653}
654
655void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
656{
657 const BMLoop *l_iter, *l_first;
658
659 zero_v3(r_cent);
660
661 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
662 do {
663 add_v3_v3(r_cent, l_iter->v->co);
664 } while ((l_iter = l_iter->next) != l_first);
665 mul_v3_fl(r_cent, 1.0f / float(f->len));
666}
667
668void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
669{
670 const BMLoop *l_iter;
671 const BMLoop *l_first;
672 float totw = 0.0f;
673 float w_prev;
674
675 zero_v3(r_cent);
676
677 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
678 w_prev = BM_edge_calc_length(l_iter->prev->e);
679 do {
680 const float w_curr = BM_edge_calc_length(l_iter->e);
681 const float w = (w_curr + w_prev);
682 madd_v3_v3fl(r_cent, l_iter->v->co, w);
683 totw += w;
684 w_prev = w_curr;
685 } while ((l_iter = l_iter->next) != l_first);
686
687 if (totw != 0.0f) {
688 mul_v3_fl(r_cent, 1.0f / totw);
689 }
690}
691
692void poly_rotate_plane(const float normal[3], float (*verts)[3], const uint nverts)
693{
694 float mat[3][3];
695 float co[3];
696 uint i;
697
698 co[2] = 0.0f;
699
700 axis_dominant_v3_to_m3(mat, normal);
701 for (i = 0; i < nverts; i++) {
702 mul_v2_m3v3(co, mat, verts[i]);
703 copy_v3_v3(verts[i], co);
704 }
705}
706
708{
709 BMIter iter;
710 BMFace *f;
711
712 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
714 }
715
718}
719
720static void bm_loop_normal_accum(const BMLoop *l, float no[3])
721{
722 float vec1[3], vec2[3], fac;
723
724 /* Same calculation used in BM_mesh_normals_update */
725 sub_v3_v3v3(vec1, l->v->co, l->prev->v->co);
726 sub_v3_v3v3(vec2, l->next->v->co, l->v->co);
727 normalize_v3(vec1);
728 normalize_v3(vec2);
729
730 fac = math::safe_acos_approx(-dot_v3v3(vec1, vec2));
731
732 madd_v3_v3fl(no, l->f->no, fac);
733}
734
735bool BM_vert_calc_normal_ex(const BMVert *v, const char hflag, float r_no[3])
736{
737 int len = 0;
738
739 zero_v3(r_no);
740
741 if (v->e) {
742 const BMEdge *e = v->e;
743 do {
744 if (e->l) {
745 const BMLoop *l = e->l;
746 do {
747 if (l->v == v) {
748 if (BM_elem_flag_test(l->f, hflag)) {
749 bm_loop_normal_accum(l, r_no);
750 len++;
751 }
752 }
753 } while ((l = l->radial_next) != e->l);
754 }
755 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
756 }
757
758 if (len) {
759 normalize_v3(r_no);
760 return true;
761 }
762 return false;
763}
764
765bool BM_vert_calc_normal(const BMVert *v, float r_no[3])
766{
767 int len = 0;
768
769 zero_v3(r_no);
770
771 if (v->e) {
772 const BMEdge *e = v->e;
773 do {
774 if (e->l) {
775 const BMLoop *l = e->l;
776 do {
777 if (l->v == v) {
778 bm_loop_normal_accum(l, r_no);
779 len++;
780 }
781 } while ((l = l->radial_next) != e->l);
782 }
783 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
784 }
785
786 if (len) {
787 normalize_v3(r_no);
788 return true;
789 }
790 return false;
791}
792
794{
795 int len = 0;
796
797 zero_v3(v->no);
798
799 if (v->e) {
800 const BMEdge *e = v->e;
801 do {
802 if (e->l) {
803 const BMLoop *l = e->l;
804 do {
805 if (l->v == v) {
808 len++;
809 }
810 } while ((l = l->radial_next) != e->l);
811 }
812 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
813 }
814
815 if (len) {
816 normalize_v3(v->no);
817 }
818}
819
824
825float BM_face_calc_normal(const BMFace *f, float r_no[3])
826{
827 BMLoop *l;
828
829 /* common cases first */
830 switch (f->len) {
831 case 4: {
832 const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
833 const float *co2 = (l = l->next)->v->co;
834 const float *co3 = (l = l->next)->v->co;
835 const float *co4 = (l->next)->v->co;
836
837 return normal_quad_v3(r_no, co1, co2, co3, co4);
838 }
839 case 3: {
840 const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
841 const float *co2 = (l = l->next)->v->co;
842 const float *co3 = (l->next)->v->co;
843
844 return normal_tri_v3(r_no, co1, co2, co3);
845 }
846 default: {
847 return bm_face_calc_poly_normal(f, r_no);
848 }
849 }
850}
852{
853 BM_face_calc_normal(f, f->no);
854}
855
857 const BMFace *f,
858 float r_no[3],
859 const Span<float3> vertexCos)
860{
861 BMLoop *l;
862
863 /* must have valid index data */
865 (void)bm;
866
867 /* common cases first */
868 switch (f->len) {
869 case 4: {
870 const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
871 const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
872 const float *co3 = vertexCos[BM_elem_index_get((l = l->next)->v)];
873 const float *co4 = vertexCos[BM_elem_index_get((l->next)->v)];
874
875 return normal_quad_v3(r_no, co1, co2, co3, co4);
876 }
877 case 3: {
878 const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
879 const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
880 const float *co3 = vertexCos[BM_elem_index_get((l->next)->v)];
881
882 return normal_tri_v3(r_no, co1, co2, co3);
883 }
884 default: {
885 return bm_face_calc_poly_normal_vertex_cos(f, r_no, vertexCos);
886 }
887 }
888}
889
891 BMVert **varr, int varr_len, float r_normal[3], float r_center[3], int *r_index_tangent)
892{
893 const float varr_len_inv = 1.0f / float(varr_len);
894
895 /* Get the center point and collect vector array since we loop over these a lot. */
896 float center[3] = {0.0f, 0.0f, 0.0f};
897 for (int i = 0; i < varr_len; i++) {
898 madd_v3_v3fl(center, varr[i]->co, varr_len_inv);
899 }
900
901 /* Find the 'co_a' point from center. */
902 int co_a_index = 0;
903 const float *co_a = nullptr;
904 {
905 float dist_sq_max = -1.0f;
906 for (int i = 0; i < varr_len; i++) {
907 const float dist_sq_test = len_squared_v3v3(varr[i]->co, center);
908 if (!(dist_sq_test <= dist_sq_max)) {
909 co_a = varr[i]->co;
910 co_a_index = i;
911 dist_sq_max = dist_sq_test;
912 }
913 }
914 }
915
916 float dir_a[3];
917 sub_v3_v3v3(dir_a, co_a, center);
918 normalize_v3(dir_a);
919
920 const float *co_b = nullptr;
921 float dir_b[3] = {0.0f, 0.0f, 0.0f};
922 {
923 float dist_sq_max = -1.0f;
924 for (int i = 0; i < varr_len; i++) {
925 if (varr[i]->co == co_a) {
926 continue;
927 }
928 float dir_test[3];
929 sub_v3_v3v3(dir_test, varr[i]->co, center);
930 project_plane_normalized_v3_v3v3(dir_test, dir_test, dir_a);
931 const float dist_sq_test = len_squared_v3(dir_test);
932 if (!(dist_sq_test <= dist_sq_max)) {
933 co_b = varr[i]->co;
934 dist_sq_max = dist_sq_test;
935 copy_v3_v3(dir_b, dir_test);
936 }
937 }
938 }
939
940 if (varr_len <= 3) {
941 normal_tri_v3(r_normal, center, co_a, co_b);
942 goto finally;
943 }
944
945 {
946 normalize_v3(dir_b);
947
948 const float *co_a_opposite = nullptr;
949 const float *co_b_opposite = nullptr;
950
951 {
952 float dot_a_min = FLT_MAX;
953 float dot_b_min = FLT_MAX;
954 for (int i = 0; i < varr_len; i++) {
955 const float *co_test = varr[i]->co;
956 float dot_test;
957
958 if (co_test != co_a) {
959 dot_test = dot_v3v3(dir_a, co_test);
960 if (dot_test < dot_a_min || co_a_opposite == nullptr) {
961 dot_a_min = dot_test;
962 co_a_opposite = co_test;
963 }
964 }
965
966 if (co_test != co_b) {
967 dot_test = dot_v3v3(dir_b, co_test);
968 if (dot_test < dot_b_min || co_b_opposite == nullptr) {
969 dot_b_min = dot_test;
970 co_b_opposite = co_test;
971 }
972 }
973 }
974 }
975
976 if (normal_quad_v3(r_normal, co_a, co_b, co_a_opposite, co_b_opposite) != 0.0f) {
977 /* Refine by accumulating a normal over all vertices
978 * in radial order around the initial normal - so all vertices contribute to the result. */
979
980 blender::Array<int> order(varr_len);
981 blender::Array<float> angles(varr_len);
982 for (int i = 0; i < varr_len; i++) {
983 order[i] = i;
984 float dir_test[3];
985 sub_v3_v3v3(dir_test, varr[i]->co, center);
986 const float angle = angle_signed_on_axis_v3v3_v3(dir_a, dir_test, r_normal);
987 angles[i] = std::isfinite(angle) ? angle : 0.0f;
988 }
989 std::ranges::sort(order, [&](int a, int b) {
990 /* This order ensures the normal doesn't "flip" when refining. */
991 return angles[a] > angles[b];
992 });
993 float normal_refine[3] = {0.0f, 0.0f, 0.0f};
994 const float *v_prev = varr[order[varr_len - 1]]->co;
995 for (int i = 0; i < varr_len; i++) {
996 const float *v_curr = varr[order[i]]->co;
997 add_newell_cross_v3_v3v3(normal_refine, v_prev, v_curr);
998 v_prev = v_curr;
999 }
1000
1001 if (normalize_v3(normal_refine) != 0.0f) {
1002 if (r_index_tangent) {
1003 /* Re-compute the tangent, because it's *possible* the original
1004 * tangent is aligned with the new normal. */
1005 float dist_sq_max = -1.0f;
1006 for (int i = 0; i < varr_len; i++) {
1007 float dir_test[3];
1008 sub_v3_v3v3(dir_test, varr[i]->co, center);
1009 project_plane_normalized_v3_v3v3(dir_test, dir_test, normal_refine);
1010 const float dist_sq_test = len_squared_v3(dir_test);
1011 if (!(dist_sq_test <= dist_sq_max)) {
1012 co_a_index = i;
1013 dist_sq_max = dist_sq_test;
1014 }
1015 }
1016 }
1017 copy_v3_v3(r_normal, normal_refine);
1018 }
1019 }
1020 }
1021
1022finally:
1023 if (r_center != nullptr) {
1024 copy_v3_v3(r_center, center);
1025 }
1026 if (r_index_tangent != nullptr) {
1027 *r_index_tangent = co_a_index;
1028 }
1029}
1030
1031void BM_verts_calc_normal_from_cloud(BMVert **varr, int varr_len, float r_normal[3])
1032{
1033 BM_verts_calc_normal_from_cloud_ex(varr, varr_len, r_normal, nullptr, nullptr);
1034}
1035
1036float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
1037{
1038 const float *v_prev, *v_curr;
1039
1040 /* Newell's Method */
1041 const BMLoop *l_iter = l_first;
1042 const BMLoop *l_term = l_last->next;
1043
1044 zero_v3(r_no);
1045
1046 v_prev = l_last->v->co;
1047 do {
1048 v_curr = l_iter->v->co;
1049 add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
1050 v_prev = v_curr;
1051 } while ((l_iter = l_iter->next) != l_term);
1052
1053 return normalize_v3(r_no);
1054}
1055
1057 const BMFace *f,
1058 float r_cent[3],
1059 const Span<float3> vert_positions)
1060{
1061 /* must have valid index data */
1063 (void)bm;
1064
1065 bm_face_calc_poly_center_median_vertex_cos(f, r_cent, vert_positions);
1066}
1067
1069 BMFace *f,
1070 const int cd_loop_mdisp_offset,
1071 const bool use_loop_mdisp_flip)
1072{
1073 bmesh_kernel_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
1074 negate_v3(f->no);
1075}
1076
1078{
1079 const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
1080 BM_face_normal_flip_ex(bm, f, cd_loop_mdisp_offset, true);
1081}
1082
1083bool BM_face_point_inside_test(const BMFace *f, const float co[3])
1084{
1085 float axis_mat[3][3];
1087
1088 float co_2d[2];
1089 BMLoop *l_iter;
1090 int i;
1091
1093
1094 axis_dominant_v3_to_m3(axis_mat, f->no);
1095
1096 mul_v2_m3v3(co_2d, axis_mat, co);
1097
1098 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
1099 mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
1100 }
1101
1102 return isect_point_poly_v2(co_2d, reinterpret_cast<float (*)[2]>(projverts.data()), f->len);
1103}
1104
1106 BMFace *f,
1107 BMFace **r_faces_new,
1108 int *r_faces_new_tot,
1109 BMEdge **r_edges_new,
1110 int *r_edges_new_tot,
1111 LinkNode **r_faces_double,
1112 const int quad_method,
1113 const int ngon_method,
1114 const bool use_tag,
1115 /* use for ngons only! */
1116 MemArena *pf_arena,
1117
1118 /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
1119 Heap *pf_heap)
1120{
1121 const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
1122 const bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
1123 BMLoop *l_first, *l_new;
1124 BMFace *f_new;
1125 int nf_i = 0;
1126 int ne_i = 0;
1127
1129
1130 /* ensure both are valid or nullptr */
1131 BLI_assert((r_faces_new == nullptr) == (r_faces_new_tot == nullptr));
1132
1133 BLI_assert(f->len > 3);
1134
1135 {
1138 uint(*tris)[3] = reinterpret_cast<uint(*)[3]>(tris_buf.data());
1139 const int totfilltri = f->len - 2;
1140 const int last_tri = f->len - 3;
1141 int i;
1142 /* for mdisps */
1143 float f_center[3];
1144
1145 if (f->len == 4) {
1146 /* even though we're not using BLI_polyfill, fill in 'tris' and 'loops'
1147 * so we can share code to handle face creation afterwards. */
1148 BMLoop *l_v1, *l_v2;
1149
1150 l_first = BM_FACE_FIRST_LOOP(f);
1151
1152 switch (quad_method) {
1153 case MOD_TRIANGULATE_QUAD_FIXED: {
1154 l_v1 = l_first;
1155 l_v2 = l_first->next->next;
1156 break;
1157 }
1158 case MOD_TRIANGULATE_QUAD_ALTERNATE: {
1159 l_v1 = l_first->next;
1160 l_v2 = l_first->prev;
1161 break;
1162 }
1163 case MOD_TRIANGULATE_QUAD_SHORTEDGE:
1164 case MOD_TRIANGULATE_QUAD_LONGEDGE:
1165 case MOD_TRIANGULATE_QUAD_BEAUTY:
1166 default: {
1167 BMLoop *l_v3, *l_v4;
1168 bool split_24;
1169
1170 l_v1 = l_first->next;
1171 l_v2 = l_first->next->next;
1172 l_v3 = l_first->prev;
1173 l_v4 = l_first;
1174
1175 if (quad_method == MOD_TRIANGULATE_QUAD_SHORTEDGE) {
1176 float d1, d2;
1177 d1 = len_squared_v3v3(l_v4->v->co, l_v2->v->co);
1178 d2 = len_squared_v3v3(l_v1->v->co, l_v3->v->co);
1179 split_24 = ((d2 - d1) > 0.0f);
1180 }
1181 else if (quad_method == MOD_TRIANGULATE_QUAD_LONGEDGE) {
1182 float d1, d2;
1183 d1 = len_squared_v3v3(l_v4->v->co, l_v2->v->co);
1184 d2 = len_squared_v3v3(l_v1->v->co, l_v3->v->co);
1185 split_24 = ((d2 - d1) < 0.0f);
1186 }
1187 else {
1188 /* first check if the quad is concave on either diagonal */
1189 const int flip_flag = is_quad_flip_v3(
1190 l_v1->v->co, l_v2->v->co, l_v3->v->co, l_v4->v->co);
1191 if (flip_flag & (1 << 0)) [[unlikely]] {
1192 split_24 = true;
1193 }
1194 else if (flip_flag & (1 << 1)) [[unlikely]] {
1195 split_24 = false;
1196 }
1197 else {
1198 split_24 = (BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) >
1199 0.0f);
1200 }
1201 }
1202
1203 /* named confusingly, l_v1 is in fact the second vertex */
1204 if (split_24) {
1205 l_v1 = l_v4;
1206 // l_v2 = l_v2;
1207 }
1208 else {
1209 // l_v1 = l_v1;
1210 l_v2 = l_v3;
1211 }
1212 break;
1213 }
1214 }
1215
1216 loops[0] = l_v1;
1217 loops[1] = l_v1->next;
1218 loops[2] = l_v2;
1219 loops[3] = l_v2->next;
1220
1221 ARRAY_SET_ITEMS(tris[0], 0, 1, 2);
1222 ARRAY_SET_ITEMS(tris[1], 0, 2, 3);
1223 }
1224 else {
1225 BMLoop *l_iter;
1226 float axis_mat[3][3];
1228
1229 axis_dominant_v3_to_m3_negate(axis_mat, f->no);
1230
1231 for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
1232 loops[i] = l_iter;
1233 mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
1234 }
1235
1237 reinterpret_cast<float (*)[2]>(projverts.data()), f->len, 1, tris, pf_arena);
1238
1239 if (use_beauty) {
1241 reinterpret_cast<float (*)[2]>(projverts.data()), f->len, tris, pf_arena, pf_heap);
1242 }
1243
1244 BLI_memarena_clear(pf_arena);
1245 }
1246
1247 if (cd_loop_mdisp_offset != -1) {
1248 BM_face_calc_center_median(f, f_center);
1249 }
1250
1251 /* loop over calculated triangles and create new geometry */
1252 for (i = 0; i < totfilltri; i++) {
1253 BMLoop *ltri[3] = {loops[tris[i][0]], loops[tris[i][1]], loops[tris[i][2]]};
1254
1255 BMVert *v_tri[3] = {ltri[0]->v, ltri[1]->v, ltri[2]->v};
1256
1257 f_new = BM_face_create_verts(bm, v_tri, 3, f, BM_CREATE_NOP, true);
1258 l_new = BM_FACE_FIRST_LOOP(f_new);
1259
1260 BLI_assert(v_tri[0] == l_new->v);
1261
1262 /* check for duplicate */
1263 if (l_new->radial_next != l_new) {
1264 BMLoop *l_iter = l_new->radial_next;
1265 do {
1266 if ((l_iter->f->len == 3) && (l_new->prev->v == l_iter->prev->v)) [[unlikely]] {
1267 /* Check the last tri because we swap last f_new with f at the end... */
1268 BLI_linklist_prepend(r_faces_double, (i != last_tri) ? f_new : f);
1269 break;
1270 }
1271 } while ((l_iter = l_iter->radial_next) != l_new);
1272 }
1273
1274 /* copy CD data */
1275 BM_elem_attrs_copy(bm, ltri[0], l_new);
1276 BM_elem_attrs_copy(bm, ltri[1], l_new->next);
1277 BM_elem_attrs_copy(bm, ltri[2], l_new->prev);
1278
1279 /* add all but the last face which is swapped and removed (below) */
1280 if (i != last_tri) {
1281 if (use_tag) {
1283 }
1284 if (r_faces_new) {
1285 r_faces_new[nf_i++] = f_new;
1286 }
1287 }
1288
1289 if (use_tag || r_edges_new) {
1290 /* new faces loops */
1291 BMLoop *l_iter;
1292
1293 l_iter = l_first = l_new;
1294 do {
1295 BMEdge *e = l_iter->e;
1296 /* Confusing! if its not a boundary now, we know it will be later since this will be an
1297 * edge of one of the new faces which we're in the middle of creating. */
1298 bool is_new_edge = (l_iter == l_iter->radial_next);
1299
1300 if (is_new_edge) {
1301 if (use_tag) {
1303 }
1304 if (r_edges_new) {
1305 r_edges_new[ne_i++] = e;
1306 }
1307 }
1308 /* NOTE: never disable tag's. */
1309 } while ((l_iter = l_iter->next) != l_first);
1310 }
1311
1312 if (cd_loop_mdisp_offset != -1) {
1313 float f_new_center[3];
1314 BM_face_calc_center_median(f_new, f_new_center);
1315 BM_face_interp_multires_ex(bm, f_new, f, f_new_center, f_center, cd_loop_mdisp_offset);
1316 }
1317 }
1318
1319 {
1320 /* we can't delete the real face, because some of the callers expect it to remain valid.
1321 * so swap data and delete the last created tri */
1322 bmesh_face_swap_data(f, f_new);
1323 BM_face_kill(bm, f_new);
1324 }
1325 }
1327
1328 if (r_faces_new_tot) {
1329 *r_faces_new_tot = nf_i;
1330 }
1331
1332 if (r_edges_new_tot) {
1333 *r_edges_new_tot = ne_i;
1334 }
1335}
1336
1338{
1339 float center[2] = {0.0f, 0.0f};
1340 float axis_mat[3][3];
1343 BMLoop *l;
1344 int i, i_prev, j;
1345
1347
1348 axis_dominant_v3_to_m3(axis_mat, f->no);
1349
1350 for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1351 mul_v2_m3v3(projverts[i], axis_mat, l->v->co);
1352 add_v2_v2(center, projverts[i]);
1353 }
1354
1355 /* first test for completely convex face */
1356 if (is_poly_convex_v2(reinterpret_cast<float (*)[2]>(projverts.data()), f->len)) {
1357 return;
1358 }
1359
1360 mul_v2_fl(center, 1.0f / f->len);
1361
1362 for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1363 BM_elem_index_set(l, i); /* set_dirty */
1364
1365 /* center the projection for maximum accuracy */
1366 sub_v2_v2(projverts[i], center);
1367 }
1369
1370 for (i = 0; i < len; i++) {
1371 edgeverts[i][0] = projverts[BM_elem_index_get(loops[i][0])];
1372 edgeverts[i][1] = projverts[BM_elem_index_get(loops[i][1])];
1373 }
1374 /* Check the split is inside the face, otherwise clear it.
1375 *
1376 * Ensure the edge between the two corners of the face defines a line that lies within the face.
1377 * Consider an edge that connects both tips of a crescent-moon shaped face.
1378 * In this case the edge would span the empty region and must not be considered "legal". */
1379 for (i = 0; i < len; i++) {
1380 /* Compare the angles at the loops. */
1381 BMLoop **l_pair = loops[i];
1382 const float *co_pair[2] = {
1383 projverts[BM_elem_index_get(l_pair[0])],
1384 projverts[BM_elem_index_get(l_pair[1])],
1385 };
1386
1387 /* Always allow cuts that overlap (unlikely but not an error). */
1388 if (equals_v2v2(co_pair[0], co_pair[1])) [[unlikely]] {
1389 continue;
1390 }
1391
1392 const float2 pair_dir = math::normalize(float2(co_pair[1]) - float2(co_pair[0]));
1393 for (const int side : IndexRange(2)) {
1394 const float2 co = float2(co_pair[side]);
1395 BMLoop *l_prev = l_pair[side]->prev;
1396 BMLoop *l_next = l_pair[side]->next;
1397
1398 /* Account for zero length edges, not essential but they shouldn't break the calculation. */
1399 {
1400 const int limit_init = f->len - 3;
1401 int limit;
1402 limit = limit_init;
1403 while (UNLIKELY(equals_v2v2(co, projverts[BM_elem_index_get(l_prev)])) && limit-- > 0) {
1404 l_prev = l_prev->prev;
1405 }
1406 limit = limit_init;
1407 while (UNLIKELY(equals_v2v2(co, projverts[BM_elem_index_get(l_next)])) && limit-- > 0) {
1408 l_next = l_next->next;
1409 }
1410 }
1411
1412 const float2 co_prev = float2(projverts[BM_elem_index_get(l_prev)]);
1413 const float2 co_next = float2(projverts[BM_elem_index_get(l_next)]);
1414
1415 const float2 dir_other = side == 0 ? pair_dir : -pair_dir;
1416 const float2 dir_prev = math::normalize(co_prev - co);
1417 const float2 dir_next = math::normalize(co_next - co);
1418
1419 if (angle_signed_v2v2_pos(dir_prev, dir_other) > angle_signed_v2v2_pos(dir_prev, dir_next)) {
1420 loops[i][0] = nullptr;
1421 break;
1422 }
1423 }
1424 }
1425
1426#define EDGE_SHARE_VERT(e1, e2) \
1427 (ELEM((e1)[0], (e2)[0], (e2)[1]) || ELEM((e1)[1], (e2)[0], (e2)[1]))
1428
1429 /* do line crossing tests */
1430 for (i = 0, i_prev = f->len - 1; i < f->len; i_prev = i++) {
1431 const float *f_edge[2] = {projverts[i_prev], projverts[i]};
1432 for (j = 0; j < len; j++) {
1433 if ((loops[j][0] != nullptr) && !EDGE_SHARE_VERT(f_edge, edgeverts[j])) {
1434 if (isect_seg_seg_v2(UNPACK2(f_edge), UNPACK2(edgeverts[j])) == ISECT_LINE_LINE_CROSS) {
1435 loops[j][0] = nullptr;
1436 }
1437 }
1438 }
1439 }
1440
1441 /* self intersect tests */
1442 for (i = 0; i < len; i++) {
1443 if (loops[i][0]) {
1444 for (j = i + 1; j < len; j++) {
1445 if ((loops[j][0] != nullptr) && !EDGE_SHARE_VERT(edgeverts[i], edgeverts[j])) {
1446 if (isect_seg_seg_v2(UNPACK2(edgeverts[i]), UNPACK2(edgeverts[j])) ==
1448 {
1449 loops[i][0] = nullptr;
1450 break;
1451 }
1452 }
1453 }
1454 }
1455 }
1456
1457#undef EDGE_SHARE_VERT
1458}
1459
1461{
1462 int i;
1463
1464 for (i = 0; i < len; i++) {
1465 BMLoop *l_a_dummy, *l_b_dummy;
1467 loops[i][0]->v, loops[i][1]->v, &l_a_dummy, &l_b_dummy, false))
1468 {
1469 loops[i][0] = nullptr;
1470 }
1471 }
1472}
1473
1475{
1477
1478 BLI_assert(f->len == 3);
1479
1480 r_verts[0] = l->v;
1481 l = l->next;
1482 r_verts[1] = l->v;
1483 l = l->next;
1484 r_verts[2] = l->v;
1485}
1486
1488{
1490
1491 BLI_assert(f->len == 4);
1492
1493 r_verts[0] = l->v;
1494 l = l->next;
1495 r_verts[1] = l->v;
1496 l = l->next;
1497 r_verts[2] = l->v;
1498 l = l->next;
1499 r_verts[3] = l->v;
1500}
1501
1503{
1505
1506 BLI_assert(f->len == 3);
1507
1508 r_loops[0] = l;
1509 l = l->next;
1510 r_loops[1] = l;
1511 l = l->next;
1512 r_loops[2] = l;
1513}
1514
1516{
1518
1519 BLI_assert(f->len == 4);
1520
1521 r_loops[0] = l;
1522 l = l->next;
1523 r_loops[1] = l;
1524 l = l->next;
1525 r_loops[2] = l;
1526 l = l->next;
1527 r_loops[3] = l;
1528}
1529
1530} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
#define M_PI
#define ISECT_LINE_LINE_CROSS
#define UNPACK2(a)
#define INIT_MINMAX(min, max)
#define ARRAY_SET_ITEMS(...)
#define UNLIKELY(x)
#define ELEM(...)
#define BM_DEFAULT_NGON_STACK_SIZE
#define BM_FACE_FIRST_LOOP(p)
#define BM_ELEM_CD_GET_FLOAT_P(ele, offset)
#define BM_DEFAULT_TOPOLOGY_STACK_SIZE
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_FACE
#define EDGE_SHARE_VERT(e1, e2)
btScalar max
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
SIMD_FORCE_INLINE btScalar angle(const btVector3 &v) const
Return the angle between this and another vector.
Definition btVector3.h:356
const T * data() const
Definition BLI_array.hh:323
#define FLT_MAX
VecBase< float, 3 > cross(VecOp< float, 3 >, VecOp< float, 3 >) RET
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
float safe_acos_approx(float x)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
BMesh Iterators.
void BM_face_calc_tessellation(const BMFace *f, const bool use_fixed_quad, BMLoop **r_loops, uint(*r_index)[3])
void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
int CustomData_get_offset(const CustomData *data, eCustomDataType type)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
BMFace * BM_face_create_verts(BMesh *bm, BMVert **vert_arr, const int len, const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges)
float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
void bmesh_kernel_loop_reverse(BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
Loop Reverse.
void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])
static void bm_face_calc_poly_center_median_vertex_cos(const BMFace *f, float r_cent[3], const Span< float3 > vert_positions)
COMPUTE POLY CENTER (BMFace).
void BM_face_normal_flip(BMesh *bm, BMFace *f)
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
float BM_face_calc_perimeter_with_mat3(const BMFace *f, const float mat3[3][3])
void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
void minmax_v3v3_v3(float min[3], float max[3], const float vec[3])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
MINLINE void mul_v2_fl(float r[2], float f)
float BM_face_calc_area_uv(const BMFace *f, int cd_loop_uv_offset)
void BM_face_calc_tangent_auto(const BMFace *f, float r_tangent[3])
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
void BM_face_calc_tangent_from_edge_diagonal(const BMFace *f, float r_tangent[3])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **r_faces_new, int *r_faces_new_tot, BMEdge **r_edges_new, int *r_edges_new_tot, LinkNode **r_faces_double, const int quad_method, const int ngon_method, const bool use_tag, MemArena *pf_arena, Heap *pf_heap)
BMESH TRIANGULATE FACE.
float angle_signed_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
float closest_to_line_segment_v3(float r_close[3], const float p[3], const float l1[3], const float l2[3])
Definition math_geom.cc:403
static float bm_face_calc_poly_normal_vertex_cos(const BMFace *f, float r_no[3], const Span< float3 > vertexCos)
COMPUTE POLY NORMAL (BMFace).
static float bm_face_calc_poly_normal(const BMFace *f, float n[3])
COMPUTE POLY NORMAL (BMFace).
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
void BM_verts_calc_normal_from_cloud_ex(BMVert **varr, int varr_len, float r_normal[3], float r_center[3], int *r_index_tangent)
ATTR_WARN_UNUSED_RESULT const BMVert * v
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:45
void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3])
static void bm_face_calc_tangent_pair_from_quad_edge_pair(const BMFace *f, float r_tangent_a[3], float r_tangent_b[3])
static int bm_vert_tri_find_unique_edge(BMVert *verts[3])
float BM_edge_calc_length(const BMEdge *e)
float angle_signed_on_axis_v3v3_v3(const float v1[3], const float v2[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
void BM_verts_calc_normal_from_cloud(BMVert **varr, int varr_len, float r_normal[3])
BMLoop * BM_face_find_longest_loop(BMFace *f)
MINLINE void mul_v3_fl(float r[3], float f)
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
void BM_face_calc_center_bounds(const BMFace *f, float r_cent[3])
bool BM_face_point_inside_test(const BMFace *f, const float co[3])
void BM_vert_normal_update(BMVert *v)
BMFace * BM_vert_pair_share_face_by_angle(BMVert *v_a, BMVert *v_b, BMLoop **r_l_a, BMLoop **r_l_b, const bool allow_adjacent)
void project_v3_v3v3(float out[3], const float p[3], const float v_proj[3])
MINLINE void sub_v3_v3(float r[3], const float a[3])
void BM_face_calc_center_median_vcos(const BMesh *bm, const BMFace *f, float r_cent[3], const Span< float3 > vert_positions)
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
void BM_face_splits_check_optimal(BMFace *f, BMLoop *(*loops)[2], int len)
void BM_vert_tri_calc_tangent_pair_from_edge(BMVert *verts[3], float r_tangent_a[3], float r_tangent_b[3])
VecBase< float, 2 > float2
bool BM_vert_calc_normal_ex(const BMVert *v, const char hflag, float r_no[3])
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
float BM_face_calc_area(const BMFace *f)
MINLINE void add_v2_v2(float r[2], const float a[2])
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_normal_update(BMFace *f)
MINLINE void swap_v3_v3(float a[3], float b[3])
float normal_quad_v3(float n[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition math_geom.cc:62
void BM_face_calc_tangent_pair_from_edge(const BMFace *f, float r_tangent_a[3], float r_tangent_b[3])
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
void BM_face_calc_center_bounds_vcos(const BMesh *bm, const BMFace *f, float r_cent[3], const Span< float3 > vert_positions)
void BM_vert_tri_calc_tangent_from_edge(BMVert *verts[3], float r_tangent[3])
void BM_vert_normal_update_all(BMVert *v)
void BM_face_calc_tangent_pair_auto(const BMFace *f, float r_tangent_a[3], float r_tangent_b[3])
static void bm_loop_normal_accum(const BMLoop *l, float no[3])
bool isect_point_poly_v2(const float pt[2], const float verts[][2], unsigned int nr)
float BM_face_calc_normal_vcos(const BMesh *bm, const BMFace *f, float r_no[3], const Span< float3 > vertexCos)
MINLINE void negate_v3(float r[3])
void BM_face_calc_tangent_from_vert_diagonal(const BMFace *f, float r_tangent[3])
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
void BM_edge_normals_update(BMEdge *e)
MINLINE void zero_v3(float r[3])
void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
float BM_face_calc_perimeter(const BMFace *f)
float BM_face_calc_area_uv_signed(const BMFace *f, int cd_loop_uv_offset)
MINLINE float normalize_v3_v3(float r[3], const float a[3])
void BM_face_calc_bounds_expand(const BMFace *f, float min[3], float max[3])
MINLINE float normalize_v3(float n[3])
void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
bool BM_vert_calc_normal(const BMVert *v, float r_no[3])
bool is_poly_convex_v2(const float verts[][2], unsigned int nr)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void BM_face_kill(BMesh *bm, BMFace *f)
static void bm_face_calc_tangent_from_quad_edge_pair(const BMFace *f, float r_tangent[3])
void BM_face_normal_flip_ex(BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
Face Flip Normal.
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
void axis_sort_v3(const float axis_values[3], int r_axis_order[3])
float BM_face_calc_normal(const BMFace *f, float r_no[3])
BMESH UPDATE FACE NORMAL.
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
float area_squared_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition math_geom.cc:111
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
MINLINE void sub_v2_v2(float r[2], const float a[2])
void BM_face_calc_tangent_from_edge_pair(const BMFace *f, float r_tangent[3])
void BM_face_interp_multires_ex(BMesh *bm, BMFace *f_dst, const BMFace *f_src, const float f_dst_center[3], const float f_src_center[3], const int cd_loop_mdisp_offset)
void BM_elem_attrs_copy(BMesh *bm, const BMCustomDataCopyMap &map, const BMVert *src, BMVert *dst)
void BM_face_as_array_loop_tri(BMFace *f, BMLoop *r_loops[3])
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool BM_face_is_normal_valid(const BMFace *f)
void poly_rotate_plane(const float normal[3], float(*verts)[3], const uint nverts)
POLY ROTATE PLANE.
void mul_v3_m3v3(float r[3], const float M[3][3], const float a[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
static float angle_signed_v2v2_pos(const float v1[2], const float v2[2])
void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BM_face_calc_tangent_from_edge(const BMFace *f, float r_tangent[3])
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
float BM_face_calc_area_with_mat3(const BMFace *f, const float mat3[3][3])
#define fabsf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMLoop * radial_next