Blender  V3.3
bmesh_polygon.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
10 #include "DNA_listBase.h"
11 #include "DNA_meshdata_types.h"
12 #include "DNA_modifier_types.h"
13 
14 #include "MEM_guardedalloc.h"
15 
16 #include "BLI_alloca.h"
17 #include "BLI_heap.h"
18 #include "BLI_linklist.h"
19 #include "BLI_math.h"
20 #include "BLI_memarena.h"
21 #include "BLI_polyfill_2d.h"
23 
24 #include "bmesh.h"
25 #include "bmesh_tools.h"
26 
27 #include "BKE_customdata.h"
28 
29 #include "intern/bmesh_private.h"
30 
36 static float bm_face_calc_poly_normal(const BMFace *f, float n[3])
37 {
38  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
39  BMLoop *l_iter = l_first;
40  const float *v_prev = l_first->prev->v->co;
41  const float *v_curr = l_first->v->co;
42 
43  zero_v3(n);
44 
45  /* Newell's Method */
46  do {
47  add_newell_cross_v3_v3v3(n, v_prev, v_curr);
48 
49  l_iter = l_iter->next;
50  v_prev = v_curr;
51  v_curr = l_iter->v->co;
52 
53  } while (l_iter != l_first);
54 
55  return normalize_v3(n);
56 }
57 
65  float r_no[3],
66  float const (*vertexCos)[3])
67 {
68  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
69  BMLoop *l_iter = l_first;
70  const float *v_prev = vertexCos[BM_elem_index_get(l_first->prev->v)];
71  const float *v_curr = vertexCos[BM_elem_index_get(l_first->v)];
72 
73  zero_v3(r_no);
74 
75  /* Newell's Method */
76  do {
77  add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
78 
79  l_iter = l_iter->next;
80  v_prev = v_curr;
81  v_curr = vertexCos[BM_elem_index_get(l_iter->v)];
82  } while (l_iter != l_first);
83 
84  return normalize_v3(r_no);
85 }
86 
91  float r_cent[3],
92  float const (*vertexCos)[3])
93 {
94  const BMLoop *l_first, *l_iter;
95 
96  zero_v3(r_cent);
97 
98  /* Newell's Method */
99  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
100  do {
101  add_v3_v3(r_cent, vertexCos[BM_elem_index_get(l_iter->v)]);
102  } while ((l_iter = l_iter->next) != l_first);
103  mul_v3_fl(r_cent, 1.0f / f->len);
104 }
105 
107  const bool use_fixed_quad,
108  BMLoop **r_loops,
109  uint (*r_index)[3])
110 {
111  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
112  BMLoop *l_iter;
113 
114  if (f->len == 3) {
115  *r_loops++ = (l_iter = l_first);
116  *r_loops++ = (l_iter = l_iter->next);
117  *r_loops++ = (l_iter->next);
118 
119  r_index[0][0] = 0;
120  r_index[0][1] = 1;
121  r_index[0][2] = 2;
122  }
123  else if (f->len == 4 && use_fixed_quad) {
124  *r_loops++ = (l_iter = l_first);
125  *r_loops++ = (l_iter = l_iter->next);
126  *r_loops++ = (l_iter = l_iter->next);
127  *r_loops++ = (l_iter->next);
128 
129  r_index[0][0] = 0;
130  r_index[0][1] = 1;
131  r_index[0][2] = 2;
132 
133  r_index[1][0] = 0;
134  r_index[1][1] = 2;
135  r_index[1][2] = 3;
136  }
137  else {
138  float axis_mat[3][3];
139  float(*projverts)[2] = BLI_array_alloca(projverts, f->len);
140  int j;
141 
142  axis_dominant_v3_to_m3_negate(axis_mat, f->no);
143 
144  j = 0;
145  l_iter = l_first;
146  do {
147  mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
148  r_loops[j] = l_iter;
149  j++;
150  } while ((l_iter = l_iter->next) != l_first);
151 
152  /* complete the loop */
153  BLI_polyfill_calc(projverts, f->len, 1, r_index);
154  }
155 }
156 
157 void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
158 {
159  const BMLoop *l_tri[3];
160 
161  if (f->len == 3) {
162  const BMLoop *l = BM_FACE_FIRST_LOOP(f);
163  ARRAY_SET_ITEMS(l_tri, l, l->next, l->prev);
164  }
165  else {
166  /* tessellation here seems overkill when in many cases this will be the center,
167  * but without this we can't be sure the point is inside a concave face. */
168  const int tottri = f->len - 2;
169  BMLoop **loops = BLI_array_alloca(loops, f->len);
170  uint(*index)[3] = BLI_array_alloca(index, tottri);
171  int j;
172  int j_best = 0; /* use as fallback when unset */
173  float area_best = -1.0f;
174 
175  BM_face_calc_tessellation(f, false, loops, index);
176 
177  for (j = 0; j < tottri; j++) {
178  const float *p1 = loops[index[j][0]]->v->co;
179  const float *p2 = loops[index[j][1]]->v->co;
180  const float *p3 = loops[index[j][2]]->v->co;
181  const float area = area_squared_tri_v3(p1, p2, p3);
182  if (area > area_best) {
183  j_best = j;
184  area_best = area;
185  }
186  }
187 
189  l_tri, loops[index[j_best][0]], loops[index[j_best][1]], loops[index[j_best][2]]);
190  }
191 
192  mid_v3_v3v3v3(r_co, l_tri[0]->v->co, l_tri[1]->v->co, l_tri[2]->v->co);
193 }
194 
195 float BM_face_calc_area(const BMFace *f)
196 {
197  /* inline 'area_poly_v3' logic, avoid creating a temp array */
198  const BMLoop *l_iter, *l_first;
199  float n[3];
200 
201  zero_v3(n);
202  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
203  do {
204  add_newell_cross_v3_v3v3(n, l_iter->v->co, l_iter->next->v->co);
205  } while ((l_iter = l_iter->next) != l_first);
206  return len_v3(n) * 0.5f;
207 }
208 
209 float BM_face_calc_area_with_mat3(const BMFace *f, const float mat3[3][3])
210 {
211  /* inline 'area_poly_v3' logic, avoid creating a temp array */
212  const BMLoop *l_iter, *l_first;
213  float co[3];
214  float n[3];
215 
216  zero_v3(n);
217  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
218  mul_v3_m3v3(co, mat3, l_iter->v->co);
219  do {
220  float co_next[3];
221  mul_v3_m3v3(co_next, mat3, l_iter->next->v->co);
222  add_newell_cross_v3_v3v3(n, co, co_next);
223  copy_v3_v3(co, co_next);
224  } while ((l_iter = l_iter->next) != l_first);
225  return len_v3(n) * 0.5f;
226 }
227 
228 float BM_face_calc_area_uv(const BMFace *f, int cd_loop_uv_offset)
229 {
230  /* inline 'area_poly_v2' logic, avoid creating a temp array */
231  const BMLoop *l_iter, *l_first;
232 
233  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
234  /* The Trapezium Area Rule */
235  float cross = 0.0f;
236  do {
237  const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_uv_offset);
238  const MLoopUV *luv_next = BM_ELEM_CD_GET_VOID_P(l_iter->next, cd_loop_uv_offset);
239  cross += (luv_next->uv[0] - luv->uv[0]) * (luv_next->uv[1] + luv->uv[1]);
240  } while ((l_iter = l_iter->next) != l_first);
241  return fabsf(cross * 0.5f);
242 }
243 
245 {
246  const BMLoop *l_iter, *l_first;
247  float perimeter = 0.0f;
248 
249  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
250  do {
251  perimeter += len_v3v3(l_iter->v->co, l_iter->next->v->co);
252  } while ((l_iter = l_iter->next) != l_first);
253 
254  return perimeter;
255 }
256 
257 float BM_face_calc_perimeter_with_mat3(const BMFace *f, const float mat3[3][3])
258 {
259  const BMLoop *l_iter, *l_first;
260  float co[3];
261  float perimeter = 0.0f;
262 
263  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
264  mul_v3_m3v3(co, mat3, l_iter->v->co);
265  do {
266  float co_next[3];
267  mul_v3_m3v3(co_next, mat3, l_iter->next->v->co);
268  perimeter += len_v3v3(co, co_next);
269  copy_v3_v3(co, co_next);
270  } while ((l_iter = l_iter->next) != l_first);
271 
272  return perimeter;
273 }
274 
281 {
282  /* find the most 'unique' loop, (greatest difference to others) */
283 #if 1
284  /* optimized version that avoids sqrt */
285  float difs[3];
286  for (int i_prev = 1, i_curr = 2, i_next = 0; i_next < 3; i_prev = i_curr, i_curr = i_next++) {
287  const float *co = verts[i_curr]->co;
288  const float *co_other[2] = {verts[i_prev]->co, verts[i_next]->co};
289  float proj_dir[3];
290  mid_v3_v3v3(proj_dir, co_other[0], co_other[1]);
291  sub_v3_v3(proj_dir, co);
292 
293  float proj_pair[2][3];
294  project_v3_v3v3(proj_pair[0], co_other[0], proj_dir);
295  project_v3_v3v3(proj_pair[1], co_other[1], proj_dir);
296  difs[i_next] = len_squared_v3v3(proj_pair[0], proj_pair[1]);
297  }
298 #else
299  const float lens[3] = {
300  len_v3v3(verts[0]->co, verts[1]->co),
301  len_v3v3(verts[1]->co, verts[2]->co),
302  len_v3v3(verts[2]->co, verts[0]->co),
303  };
304  const float difs[3] = {
305  fabsf(lens[1] - lens[2]),
306  fabsf(lens[2] - lens[0]),
307  fabsf(lens[0] - lens[1]),
308  };
309 #endif
310 
311  int order[3] = {0, 1, 2};
312  axis_sort_v3(difs, order);
313 
314  return order[0];
315 }
316 
317 void BM_vert_tri_calc_tangent_edge(BMVert *verts[3], float r_tangent[3])
318 {
319  const int index = bm_vert_tri_find_unique_edge(verts);
320 
321  sub_v3_v3v3(r_tangent, verts[index]->co, verts[(index + 1) % 3]->co);
322 
323  normalize_v3(r_tangent);
324 }
325 
326 void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3])
327 {
328  const int index = bm_vert_tri_find_unique_edge(verts);
329 
330  const float *v_a = verts[index]->co;
331  const float *v_b = verts[(index + 1) % 3]->co;
332  const float *v_other = verts[(index + 2) % 3]->co;
333 
334  mid_v3_v3v3(r_tangent, v_a, v_b);
335  sub_v3_v3v3(r_tangent, v_other, r_tangent);
336 
337  normalize_v3(r_tangent);
338 }
339 
340 void BM_face_calc_tangent_edge(const BMFace *f, float r_tangent[3])
341 {
342  const BMLoop *l_long = BM_face_find_longest_loop((BMFace *)f);
343 
344  sub_v3_v3v3(r_tangent, l_long->v->co, l_long->next->v->co);
345 
346  normalize_v3(r_tangent);
347 }
348 
349 void BM_face_calc_tangent_edge_pair(const BMFace *f, float r_tangent[3])
350 {
351  if (f->len == 3) {
352  BMVert *verts[3];
353 
355 
357  }
358  else if (f->len == 4) {
359  /* Use longest edge pair */
360  BMVert *verts[4];
361  float vec[3], vec_a[3], vec_b[3];
362 
364 
365  sub_v3_v3v3(vec_a, verts[3]->co, verts[2]->co);
366  sub_v3_v3v3(vec_b, verts[0]->co, verts[1]->co);
367  add_v3_v3v3(r_tangent, vec_a, vec_b);
368 
369  sub_v3_v3v3(vec_a, verts[0]->co, verts[3]->co);
370  sub_v3_v3v3(vec_b, verts[1]->co, verts[2]->co);
371  add_v3_v3v3(vec, vec_a, vec_b);
372  /* use the longest edge length */
373  if (len_squared_v3(r_tangent) < len_squared_v3(vec)) {
374  copy_v3_v3(r_tangent, vec);
375  }
376  }
377  else {
378  /* For ngons use two longest disconnected edges */
379  BMLoop *l_long = BM_face_find_longest_loop((BMFace *)f);
380  BMLoop *l_long_other = NULL;
381 
382  float len_max_sq = 0.0f;
383  float vec_a[3], vec_b[3];
384 
385  BMLoop *l_iter = l_long->prev->prev;
386  BMLoop *l_last = l_long->next;
387 
388  do {
389  const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
390  if (len_sq >= len_max_sq) {
391  l_long_other = l_iter;
392  len_max_sq = len_sq;
393  }
394  } while ((l_iter = l_iter->prev) != l_last);
395 
396  sub_v3_v3v3(vec_a, l_long->next->v->co, l_long->v->co);
397  sub_v3_v3v3(vec_b, l_long_other->v->co, l_long_other->next->v->co);
398  add_v3_v3v3(r_tangent, vec_a, vec_b);
399 
400  /* Edges may not be opposite side of the ngon,
401  * this could cause problems for ngons with multiple-aligned edges of the same length.
402  * Fallback to longest edge. */
403  if (UNLIKELY(normalize_v3(r_tangent) == 0.0f)) {
404  normalize_v3_v3(r_tangent, vec_a);
405  }
406  }
407 }
408 
409 void BM_face_calc_tangent_edge_diagonal(const BMFace *f, float r_tangent[3])
410 {
411  BMLoop *l_iter, *l_first;
412 
413  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
414 
415  /* In case of degenerate faces. */
416  zero_v3(r_tangent);
417 
418  /* WARNING: O(n^2) loop here, take care! */
419  float dist_max_sq = 0.0f;
420  do {
421  BMLoop *l_iter_other = l_iter->next;
422  BMLoop *l_iter_last = l_iter->prev;
423  do {
424  BLI_assert(!ELEM(l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co));
425  float co_other[3], vec[3];
427  co_other, l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co);
428  sub_v3_v3v3(vec, l_iter->v->co, co_other);
429 
430  const float dist_sq = len_squared_v3(vec);
431  if (dist_sq > dist_max_sq) {
432  dist_max_sq = dist_sq;
433  copy_v3_v3(r_tangent, vec);
434  }
435  } while ((l_iter_other = l_iter_other->next) != l_iter_last);
436  } while ((l_iter = l_iter->next) != l_first);
437 
438  normalize_v3(r_tangent);
439 }
440 
441 void BM_face_calc_tangent_vert_diagonal(const BMFace *f, float r_tangent[3])
442 {
443  BMLoop *l_iter, *l_first;
444 
445  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
446 
447  /* In case of degenerate faces. */
448  zero_v3(r_tangent);
449 
450  /* WARNING: O(n^2) loop here, take care! */
451  float dist_max_sq = 0.0f;
452  do {
453  BMLoop *l_iter_other = l_iter->next;
454  do {
455  float vec[3];
456  sub_v3_v3v3(vec, l_iter->v->co, l_iter_other->v->co);
457 
458  const float dist_sq = len_squared_v3(vec);
459  if (dist_sq > dist_max_sq) {
460  dist_max_sq = dist_sq;
461  copy_v3_v3(r_tangent, vec);
462  }
463  } while ((l_iter_other = l_iter_other->next) != l_iter);
464  } while ((l_iter = l_iter->next) != l_first);
465 
466  normalize_v3(r_tangent);
467 }
468 
469 void BM_face_calc_tangent_auto(const BMFace *f, float r_tangent[3])
470 {
471  if (f->len == 3) {
472  /* most 'unique' edge of a triangle */
473  BMVert *verts[3];
476  }
477  else if (f->len == 4) {
478  /* longest edge pair of a quad */
479  BM_face_calc_tangent_edge_pair((BMFace *)f, r_tangent);
480  }
481  else {
482  /* longest edge of an ngon */
483  BM_face_calc_tangent_edge((BMFace *)f, r_tangent);
484  }
485 }
486 
487 void BM_face_calc_bounds_expand(const BMFace *f, float min[3], float max[3])
488 {
489  const BMLoop *l_iter, *l_first;
490  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
491  do {
492  minmax_v3v3_v3(min, max, l_iter->v->co);
493  } while ((l_iter = l_iter->next) != l_first);
494 }
495 
496 void BM_face_calc_center_bounds(const BMFace *f, float r_cent[3])
497 {
498  const BMLoop *l_iter, *l_first;
499  float min[3], max[3];
500 
501  INIT_MINMAX(min, max);
502 
503  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
504  do {
505  minmax_v3v3_v3(min, max, l_iter->v->co);
506  } while ((l_iter = l_iter->next) != l_first);
507 
508  mid_v3_v3v3(r_cent, min, max);
509 }
510 
512  const BMFace *f,
513  float r_cent[3],
514  float const (*vertexCos)[3])
515 {
516  /* must have valid index data */
518  (void)bm;
519 
520  const BMLoop *l_iter, *l_first;
521  float min[3], max[3];
522 
523  INIT_MINMAX(min, max);
524 
525  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
526  do {
527  minmax_v3v3_v3(min, max, vertexCos[BM_elem_index_get(l_iter->v)]);
528  } while ((l_iter = l_iter->next) != l_first);
529 
530  mid_v3_v3v3(r_cent, min, max);
531 }
532 
533 void BM_face_calc_center_median(const BMFace *f, float r_cent[3])
534 {
535  const BMLoop *l_iter, *l_first;
536 
537  zero_v3(r_cent);
538 
539  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
540  do {
541  add_v3_v3(r_cent, l_iter->v->co);
542  } while ((l_iter = l_iter->next) != l_first);
543  mul_v3_fl(r_cent, 1.0f / (float)f->len);
544 }
545 
546 void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
547 {
548  const BMLoop *l_iter;
549  const BMLoop *l_first;
550  float totw = 0.0f;
551  float w_prev;
552 
553  zero_v3(r_cent);
554 
555  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
556  w_prev = BM_edge_calc_length(l_iter->prev->e);
557  do {
558  const float w_curr = BM_edge_calc_length(l_iter->e);
559  const float w = (w_curr + w_prev);
560  madd_v3_v3fl(r_cent, l_iter->v->co, w);
561  totw += w;
562  w_prev = w_curr;
563  } while ((l_iter = l_iter->next) != l_first);
564 
565  if (totw != 0.0f) {
566  mul_v3_fl(r_cent, 1.0f / (float)totw);
567  }
568 }
569 
570 void poly_rotate_plane(const float normal[3], float (*verts)[3], const uint nverts)
571 {
572  float mat[3][3];
573  float co[3];
574  uint i;
575 
576  co[2] = 0.0f;
577 
579  for (i = 0; i < nverts; i++) {
580  mul_v2_m3v3(co, mat, verts[i]);
581  copy_v3_v3(verts[i], co);
582  }
583 }
584 
586 {
587  BMIter iter;
588  BMFace *f;
589 
590  BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
592  }
593 
596 }
597 
598 static void bm_loop_normal_accum(const BMLoop *l, float no[3])
599 {
600  float vec1[3], vec2[3], fac;
601 
602  /* Same calculation used in BM_mesh_normals_update */
603  sub_v3_v3v3(vec1, l->v->co, l->prev->v->co);
604  sub_v3_v3v3(vec2, l->next->v->co, l->v->co);
605  normalize_v3(vec1);
606  normalize_v3(vec2);
607 
608  fac = saacos(-dot_v3v3(vec1, vec2));
609 
610  madd_v3_v3fl(no, l->f->no, fac);
611 }
612 
613 bool BM_vert_calc_normal_ex(const BMVert *v, const char hflag, float r_no[3])
614 {
615  int len = 0;
616 
617  zero_v3(r_no);
618 
619  if (v->e) {
620  const BMEdge *e = v->e;
621  do {
622  if (e->l) {
623  const BMLoop *l = e->l;
624  do {
625  if (l->v == v) {
626  if (BM_elem_flag_test(l->f, hflag)) {
627  bm_loop_normal_accum(l, r_no);
628  len++;
629  }
630  }
631  } while ((l = l->radial_next) != e->l);
632  }
633  } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
634  }
635 
636  if (len) {
637  normalize_v3(r_no);
638  return true;
639  }
640  return false;
641 }
642 
643 bool BM_vert_calc_normal(const BMVert *v, float r_no[3])
644 {
645  int len = 0;
646 
647  zero_v3(r_no);
648 
649  if (v->e) {
650  const BMEdge *e = v->e;
651  do {
652  if (e->l) {
653  const BMLoop *l = e->l;
654  do {
655  if (l->v == v) {
656  bm_loop_normal_accum(l, r_no);
657  len++;
658  }
659  } while ((l = l->radial_next) != e->l);
660  }
661  } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
662  }
663 
664  if (len) {
665  normalize_v3(r_no);
666  return true;
667  }
668  return false;
669 }
670 
672 {
673  int len = 0;
674 
675  zero_v3(v->no);
676 
677  if (v->e) {
678  const BMEdge *e = v->e;
679  do {
680  if (e->l) {
681  const BMLoop *l = e->l;
682  do {
683  if (l->v == v) {
686  len++;
687  }
688  } while ((l = l->radial_next) != e->l);
689  }
690  } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
691  }
692 
693  if (len) {
694  normalize_v3(v->no);
695  }
696 }
697 
699 {
701 }
702 
703 float BM_face_calc_normal(const BMFace *f, float r_no[3])
704 {
705  BMLoop *l;
706 
707  /* common cases first */
708  switch (f->len) {
709  case 4: {
710  const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
711  const float *co2 = (l = l->next)->v->co;
712  const float *co3 = (l = l->next)->v->co;
713  const float *co4 = (l->next)->v->co;
714 
715  return normal_quad_v3(r_no, co1, co2, co3, co4);
716  }
717  case 3: {
718  const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
719  const float *co2 = (l = l->next)->v->co;
720  const float *co3 = (l->next)->v->co;
721 
722  return normal_tri_v3(r_no, co1, co2, co3);
723  }
724  default: {
725  return bm_face_calc_poly_normal(f, r_no);
726  }
727  }
728 }
730 {
731  BM_face_calc_normal(f, f->no);
732 }
733 
735  const BMFace *f,
736  float r_no[3],
737  float const (*vertexCos)[3])
738 {
739  BMLoop *l;
740 
741  /* must have valid index data */
743  (void)bm;
744 
745  /* common cases first */
746  switch (f->len) {
747  case 4: {
748  const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
749  const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
750  const float *co3 = vertexCos[BM_elem_index_get((l = l->next)->v)];
751  const float *co4 = vertexCos[BM_elem_index_get((l->next)->v)];
752 
753  return normal_quad_v3(r_no, co1, co2, co3, co4);
754  }
755  case 3: {
756  const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
757  const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
758  const float *co3 = vertexCos[BM_elem_index_get((l->next)->v)];
759 
760  return normal_tri_v3(r_no, co1, co2, co3);
761  }
762  default: {
763  return bm_face_calc_poly_normal_vertex_cos(f, r_no, vertexCos);
764  }
765  }
766 }
767 
769  BMVert **varr, int varr_len, float r_normal[3], float r_center[3], int *r_index_tangent)
770 {
771  const float varr_len_inv = 1.0f / (float)varr_len;
772 
773  /* Get the center point and collect vector array since we loop over these a lot. */
774  float center[3] = {0.0f, 0.0f, 0.0f};
775  for (int i = 0; i < varr_len; i++) {
776  madd_v3_v3fl(center, varr[i]->co, varr_len_inv);
777  }
778 
779  /* Find the 'co_a' point from center. */
780  int co_a_index = 0;
781  const float *co_a = NULL;
782  {
783  float dist_sq_max = -1.0f;
784  for (int i = 0; i < varr_len; i++) {
785  const float dist_sq_test = len_squared_v3v3(varr[i]->co, center);
786  if (!(dist_sq_test <= dist_sq_max)) {
787  co_a = varr[i]->co;
788  co_a_index = i;
789  dist_sq_max = dist_sq_test;
790  }
791  }
792  }
793 
794  float dir_a[3];
795  sub_v3_v3v3(dir_a, co_a, center);
796  normalize_v3(dir_a);
797 
798  const float *co_b = NULL;
799  float dir_b[3] = {0.0f, 0.0f, 0.0f};
800  {
801  float dist_sq_max = -1.0f;
802  for (int i = 0; i < varr_len; i++) {
803  if (varr[i]->co == co_a) {
804  continue;
805  }
806  float dir_test[3];
807  sub_v3_v3v3(dir_test, varr[i]->co, center);
808  project_plane_normalized_v3_v3v3(dir_test, dir_test, dir_a);
809  const float dist_sq_test = len_squared_v3(dir_test);
810  if (!(dist_sq_test <= dist_sq_max)) {
811  co_b = varr[i]->co;
812  dist_sq_max = dist_sq_test;
813  copy_v3_v3(dir_b, dir_test);
814  }
815  }
816  }
817 
818  if (varr_len <= 3) {
819  normal_tri_v3(r_normal, center, co_a, co_b);
820  goto finally;
821  }
822 
823  normalize_v3(dir_b);
824 
825  const float *co_a_opposite = NULL;
826  const float *co_b_opposite = NULL;
827 
828  {
829  float dot_a_min = FLT_MAX;
830  float dot_b_min = FLT_MAX;
831  for (int i = 0; i < varr_len; i++) {
832  const float *co_test = varr[i]->co;
833  float dot_test;
834 
835  if (co_test != co_a) {
836  dot_test = dot_v3v3(dir_a, co_test);
837  if (dot_test < dot_a_min) {
838  dot_a_min = dot_test;
839  co_a_opposite = co_test;
840  }
841  }
842 
843  if (co_test != co_b) {
844  dot_test = dot_v3v3(dir_b, co_test);
845  if (dot_test < dot_b_min) {
846  dot_b_min = dot_test;
847  co_b_opposite = co_test;
848  }
849  }
850  }
851  }
852 
853  normal_quad_v3(r_normal, co_a, co_b, co_a_opposite, co_b_opposite);
854 
855 finally:
856  if (r_center != NULL) {
857  copy_v3_v3(r_center, center);
858  }
859  if (r_index_tangent != NULL) {
860  *r_index_tangent = co_a_index;
861  }
862 }
863 
864 void BM_verts_calc_normal_from_cloud(BMVert **varr, int varr_len, float r_normal[3])
865 {
866  BM_verts_calc_normal_from_cloud_ex(varr, varr_len, r_normal, NULL, NULL);
867 }
868 
869 float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
870 {
871  const float *v_prev, *v_curr;
872 
873  /* Newell's Method */
874  const BMLoop *l_iter = l_first;
875  const BMLoop *l_term = l_last->next;
876 
877  zero_v3(r_no);
878 
879  v_prev = l_last->v->co;
880  do {
881  v_curr = l_iter->v->co;
882  add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
883  v_prev = v_curr;
884  } while ((l_iter = l_iter->next) != l_term);
885 
886  return normalize_v3(r_no);
887 }
888 
890  const BMFace *f,
891  float r_cent[3],
892  float const (*vertexCos)[3])
893 {
894  /* must have valid index data */
896  (void)bm;
897 
898  bm_face_calc_poly_center_median_vertex_cos(f, r_cent, vertexCos);
899 }
900 
902  BMFace *f,
903  const int cd_loop_mdisp_offset,
904  const bool use_loop_mdisp_flip)
905 {
906  bmesh_kernel_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
907  negate_v3(f->no);
908 }
909 
911 {
912  const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
913  BM_face_normal_flip_ex(bm, f, cd_loop_mdisp_offset, true);
914 }
915 
916 bool BM_face_point_inside_test(const BMFace *f, const float co[3])
917 {
918  float axis_mat[3][3];
919  float(*projverts)[2] = BLI_array_alloca(projverts, f->len);
920 
921  float co_2d[2];
922  BMLoop *l_iter;
923  int i;
924 
926 
927  axis_dominant_v3_to_m3(axis_mat, f->no);
928 
929  mul_v2_m3v3(co_2d, axis_mat, co);
930 
931  for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
932  mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
933  }
934 
935  return isect_point_poly_v2(co_2d, projverts, f->len, false);
936 }
937 
939  BMFace *f,
940  BMFace **r_faces_new,
941  int *r_faces_new_tot,
942  BMEdge **r_edges_new,
943  int *r_edges_new_tot,
944  LinkNode **r_faces_double,
945  const int quad_method,
946  const int ngon_method,
947  const bool use_tag,
948  /* use for ngons only! */
949  MemArena *pf_arena,
950 
951  /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
952  struct Heap *pf_heap)
953 {
954  const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
955  const bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
956  BMLoop *l_first, *l_new;
957  BMFace *f_new;
958  int nf_i = 0;
959  int ne_i = 0;
960 
962 
963  /* ensure both are valid or NULL */
964  BLI_assert((r_faces_new == NULL) == (r_faces_new_tot == NULL));
965 
966  BLI_assert(f->len > 3);
967 
968  {
969  BMLoop **loops = BLI_array_alloca(loops, f->len);
970  uint(*tris)[3] = BLI_array_alloca(tris, f->len);
971  const int totfilltri = f->len - 2;
972  const int last_tri = f->len - 3;
973  int i;
974  /* for mdisps */
975  float f_center[3];
976 
977  if (f->len == 4) {
978  /* even though we're not using BLI_polyfill, fill in 'tris' and 'loops'
979  * so we can share code to handle face creation afterwards. */
980  BMLoop *l_v1, *l_v2;
981 
982  l_first = BM_FACE_FIRST_LOOP(f);
983 
984  switch (quad_method) {
986  l_v1 = l_first;
987  l_v2 = l_first->next->next;
988  break;
989  }
991  l_v1 = l_first->next;
992  l_v2 = l_first->prev;
993  break;
994  }
998  default: {
999  BMLoop *l_v3, *l_v4;
1000  bool split_24;
1001 
1002  l_v1 = l_first->next;
1003  l_v2 = l_first->next->next;
1004  l_v3 = l_first->prev;
1005  l_v4 = l_first;
1006 
1007  if (quad_method == MOD_TRIANGULATE_QUAD_SHORTEDGE) {
1008  float d1, d2;
1009  d1 = len_squared_v3v3(l_v4->v->co, l_v2->v->co);
1010  d2 = len_squared_v3v3(l_v1->v->co, l_v3->v->co);
1011  split_24 = ((d2 - d1) > 0.0f);
1012  }
1013  else if (quad_method == MOD_TRIANGULATE_QUAD_LONGEDGE) {
1014  float d1, d2;
1015  d1 = len_squared_v3v3(l_v4->v->co, l_v2->v->co);
1016  d2 = len_squared_v3v3(l_v1->v->co, l_v3->v->co);
1017  split_24 = ((d2 - d1) < 0.0f);
1018  }
1019  else {
1020  /* first check if the quad is concave on either diagonal */
1021  const int flip_flag = is_quad_flip_v3(
1022  l_v1->v->co, l_v2->v->co, l_v3->v->co, l_v4->v->co);
1023  if (UNLIKELY(flip_flag & (1 << 0))) {
1024  split_24 = true;
1025  }
1026  else if (UNLIKELY(flip_flag & (1 << 1))) {
1027  split_24 = false;
1028  }
1029  else {
1030  split_24 = (BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) >
1031  0.0f);
1032  }
1033  }
1034 
1035  /* named confusingly, l_v1 is in fact the second vertex */
1036  if (split_24) {
1037  l_v1 = l_v4;
1038  // l_v2 = l_v2;
1039  }
1040  else {
1041  // l_v1 = l_v1;
1042  l_v2 = l_v3;
1043  }
1044  break;
1045  }
1046  }
1047 
1048  loops[0] = l_v1;
1049  loops[1] = l_v1->next;
1050  loops[2] = l_v2;
1051  loops[3] = l_v2->next;
1052 
1053  ARRAY_SET_ITEMS(tris[0], 0, 1, 2);
1054  ARRAY_SET_ITEMS(tris[1], 0, 2, 3);
1055  }
1056  else {
1057  BMLoop *l_iter;
1058  float axis_mat[3][3];
1059  float(*projverts)[2] = BLI_array_alloca(projverts, f->len);
1060 
1061  axis_dominant_v3_to_m3_negate(axis_mat, f->no);
1062 
1063  for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
1064  loops[i] = l_iter;
1065  mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
1066  }
1067 
1068  BLI_polyfill_calc_arena(projverts, f->len, 1, tris, pf_arena);
1069 
1070  if (use_beauty) {
1071  BLI_polyfill_beautify(projverts, f->len, tris, pf_arena, pf_heap);
1072  }
1073 
1074  BLI_memarena_clear(pf_arena);
1075  }
1076 
1077  if (cd_loop_mdisp_offset != -1) {
1078  BM_face_calc_center_median(f, f_center);
1079  }
1080 
1081  /* loop over calculated triangles and create new geometry */
1082  for (i = 0; i < totfilltri; i++) {
1083  BMLoop *l_tri[3] = {loops[tris[i][0]], loops[tris[i][1]], loops[tris[i][2]]};
1084 
1085  BMVert *v_tri[3] = {l_tri[0]->v, l_tri[1]->v, l_tri[2]->v};
1086 
1087  f_new = BM_face_create_verts(bm, v_tri, 3, f, BM_CREATE_NOP, true);
1088  l_new = BM_FACE_FIRST_LOOP(f_new);
1089 
1090  BLI_assert(v_tri[0] == l_new->v);
1091 
1092  /* check for duplicate */
1093  if (l_new->radial_next != l_new) {
1094  BMLoop *l_iter = l_new->radial_next;
1095  do {
1096  if (UNLIKELY((l_iter->f->len == 3) && (l_new->prev->v == l_iter->prev->v))) {
1097  /* Check the last tri because we swap last f_new with f at the end... */
1098  BLI_linklist_prepend(r_faces_double, (i != last_tri) ? f_new : f);
1099  break;
1100  }
1101  } while ((l_iter = l_iter->radial_next) != l_new);
1102  }
1103 
1104  /* copy CD data */
1105  BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
1106  BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
1107  BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
1108 
1109  /* add all but the last face which is swapped and removed (below) */
1110  if (i != last_tri) {
1111  if (use_tag) {
1113  }
1114  if (r_faces_new) {
1115  r_faces_new[nf_i++] = f_new;
1116  }
1117  }
1118 
1119  if (use_tag || r_edges_new) {
1120  /* new faces loops */
1121  BMLoop *l_iter;
1122 
1123  l_iter = l_first = l_new;
1124  do {
1125  BMEdge *e = l_iter->e;
1126  /* Confusing! if its not a boundary now, we know it will be later since this will be an
1127  * edge of one of the new faces which we're in the middle of creating. */
1128  bool is_new_edge = (l_iter == l_iter->radial_next);
1129 
1130  if (is_new_edge) {
1131  if (use_tag) {
1133  }
1134  if (r_edges_new) {
1135  r_edges_new[ne_i++] = e;
1136  }
1137  }
1138  /* NOTE: never disable tag's. */
1139  } while ((l_iter = l_iter->next) != l_first);
1140  }
1141 
1142  if (cd_loop_mdisp_offset != -1) {
1143  float f_new_center[3];
1144  BM_face_calc_center_median(f_new, f_new_center);
1145  BM_face_interp_multires_ex(bm, f_new, f, f_new_center, f_center, cd_loop_mdisp_offset);
1146  }
1147  }
1148 
1149  {
1150  /* we can't delete the real face, because some of the callers expect it to remain valid.
1151  * so swap data and delete the last created tri */
1152  bmesh_face_swap_data(f, f_new);
1153  BM_face_kill(bm, f_new);
1154  }
1155  }
1157 
1158  if (r_faces_new_tot) {
1159  *r_faces_new_tot = nf_i;
1160  }
1161 
1162  if (r_edges_new_tot) {
1163  *r_edges_new_tot = ne_i;
1164  }
1165 }
1166 
1167 void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
1168 {
1169  float out[2] = {-FLT_MAX, -FLT_MAX};
1170  float center[2] = {0.0f, 0.0f};
1171  float axis_mat[3][3];
1172  float(*projverts)[2] = BLI_array_alloca(projverts, f->len);
1173  const float *(*edgeverts)[2] = BLI_array_alloca(edgeverts, len);
1174  BMLoop *l;
1175  int i, i_prev, j;
1176 
1178 
1179  axis_dominant_v3_to_m3(axis_mat, f->no);
1180 
1181  for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1182  mul_v2_m3v3(projverts[i], axis_mat, l->v->co);
1183  add_v2_v2(center, projverts[i]);
1184  }
1185 
1186  /* first test for completely convex face */
1187  if (is_poly_convex_v2(projverts, f->len)) {
1188  return;
1189  }
1190 
1191  mul_v2_fl(center, 1.0f / f->len);
1192 
1193  for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1194  BM_elem_index_set(l, i); /* set_dirty */
1195 
1196  /* center the projection for maximum accuracy */
1197  sub_v2_v2(projverts[i], center);
1198 
1199  out[0] = max_ff(out[0], projverts[i][0]);
1200  out[1] = max_ff(out[1], projverts[i][1]);
1201  }
1203 
1204  /* ensure we are well outside the face bounds (value is arbitrary) */
1205  add_v2_fl(out, 1.0f);
1206 
1207  for (i = 0; i < len; i++) {
1208  edgeverts[i][0] = projverts[BM_elem_index_get(loops[i][0])];
1209  edgeverts[i][1] = projverts[BM_elem_index_get(loops[i][1])];
1210  }
1211 
1212  /* do convexity test */
1213  for (i = 0; i < len; i++) {
1214  float mid[2];
1215  mid_v2_v2v2(mid, edgeverts[i][0], edgeverts[i][1]);
1216 
1217  int isect = 0;
1218  int j_prev;
1219  for (j = 0, j_prev = f->len - 1; j < f->len; j_prev = j++) {
1220  const float *f_edge[2] = {projverts[j_prev], projverts[j]};
1221  if (isect_seg_seg_v2(UNPACK2(f_edge), mid, out) == ISECT_LINE_LINE_CROSS) {
1222  isect++;
1223  }
1224  }
1225 
1226  if (isect % 2 == 0) {
1227  loops[i][0] = NULL;
1228  }
1229  }
1230 
1231 #define EDGE_SHARE_VERT(e1, e2) \
1232  ((ELEM((e1)[0], (e2)[0], (e2)[1])) || (ELEM((e1)[1], (e2)[0], (e2)[1])))
1233 
1234  /* do line crossing tests */
1235  for (i = 0, i_prev = f->len - 1; i < f->len; i_prev = i++) {
1236  const float *f_edge[2] = {projverts[i_prev], projverts[i]};
1237  for (j = 0; j < len; j++) {
1238  if ((loops[j][0] != NULL) && !EDGE_SHARE_VERT(f_edge, edgeverts[j])) {
1239  if (isect_seg_seg_v2(UNPACK2(f_edge), UNPACK2(edgeverts[j])) == ISECT_LINE_LINE_CROSS) {
1240  loops[j][0] = NULL;
1241  }
1242  }
1243  }
1244  }
1245 
1246  /* self intersect tests */
1247  for (i = 0; i < len; i++) {
1248  if (loops[i][0]) {
1249  for (j = i + 1; j < len; j++) {
1250  if ((loops[j][0] != NULL) && !EDGE_SHARE_VERT(edgeverts[i], edgeverts[j])) {
1251  if (isect_seg_seg_v2(UNPACK2(edgeverts[i]), UNPACK2(edgeverts[j])) ==
1253  loops[i][0] = NULL;
1254  break;
1255  }
1256  }
1257  }
1258  }
1259  }
1260 
1261 #undef EDGE_SHARE_VERT
1262 }
1263 
1264 void BM_face_splits_check_optimal(BMFace *f, BMLoop *(*loops)[2], int len)
1265 {
1266  int i;
1267 
1268  for (i = 0; i < len; i++) {
1269  BMLoop *l_a_dummy, *l_b_dummy;
1271  loops[i][0]->v, loops[i][1]->v, &l_a_dummy, &l_b_dummy, false)) {
1272  loops[i][0] = NULL;
1273  }
1274  }
1275 }
1276 
1278 {
1279  BMLoop *l = BM_FACE_FIRST_LOOP(f);
1280 
1281  BLI_assert(f->len == 3);
1282 
1283  r_verts[0] = l->v;
1284  l = l->next;
1285  r_verts[1] = l->v;
1286  l = l->next;
1287  r_verts[2] = l->v;
1288 }
1289 
1291 {
1292  BMLoop *l = BM_FACE_FIRST_LOOP(f);
1293 
1294  BLI_assert(f->len == 4);
1295 
1296  r_verts[0] = l->v;
1297  l = l->next;
1298  r_verts[1] = l->v;
1299  l = l->next;
1300  r_verts[2] = l->v;
1301  l = l->next;
1302  r_verts[3] = l->v;
1303 }
1304 
1306 {
1307  BMLoop *l = BM_FACE_FIRST_LOOP(f);
1308 
1309  BLI_assert(f->len == 3);
1310 
1311  r_loops[0] = l;
1312  l = l->next;
1313  r_loops[1] = l;
1314  l = l->next;
1315  r_loops[2] = l;
1316 }
1317 
1319 {
1320  BMLoop *l = BM_FACE_FIRST_LOOP(f);
1321 
1322  BLI_assert(f->len == 4);
1323 
1324  r_loops[0] = l;
1325  l = l->next;
1326  r_loops[1] = l;
1327  l = l->next;
1328  r_loops[2] = l;
1329  l = l->next;
1330  r_loops[3] = l;
1331 }
typedef float(TangentPoint)[2]
CustomData interface, see also DNA_customdata_types.h.
int CustomData_get_offset(const struct CustomData *data, int type)
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
A min-heap / priority queue ADT.
MINLINE float saacos(float fac)
MINLINE float max_ff(float a, float b)
int isect_seg_seg_v2(const float v1[2], const float v2[2], const float v3[2], const float v4[2])
Definition: math_geom.c:1108
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.c:50
int is_quad_flip_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:5845
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.c:379
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
Definition: math_geom.c:3544
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
Definition: math_geom.c:3527
float area_squared_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:99
bool is_poly_convex_v2(const float verts[][2], unsigned int nr)
Definition: math_geom.c:5806
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
bool isect_point_poly_v2(const float pt[2], const float verts[][2], unsigned int nr, bool use_holes)
#define ISECT_LINE_LINE_CROSS
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
Definition: math_matrix.c:917
void mul_v3_m3v3(float r[3], const float M[3][3], const float a[3])
Definition: math_matrix.c:897
void axis_sort_v3(const float axis_values[3], int r_axis_order[3])
Definition: math_vector.c:939
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void minmax_v3v3_v3(float min[3], float max[3], const float vec[3])
Definition: math_vector.c:867
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
MINLINE void sub_v2_v2(float r[2], const float a[2])
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3(float r[3], const float a[3])
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void mul_v2_fl(float r[2], float f)
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE void copy_v3_v3(float r[3], const float a[3])
void project_v3_v3v3(float out[3], const float p[3], const float v_proj[3])
Definition: math_vector.c:600
MINLINE void add_v2_v2(float r[2], const float a[2])
void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
Definition: math_vector.c:652
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE void add_v2_fl(float r[2], float f)
MINLINE void negate_v3(float r[3])
void mid_v2_v2v2(float r[2], const float a[2], const float b[2])
Definition: math_vector.c:244
MINLINE float normalize_v3_v3(float r[3], const float a[3])
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
Definition: math_vector.c:237
MINLINE void zero_v3(float r[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_vector.c:256
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
void void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:208
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
Definition: polyfill_2d.c:875
void BLI_polyfill_calc_arena(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3], struct MemArena *arena)
Definition: polyfill_2d.c:830
void BLI_polyfill_beautify(const float(*coords)[2], unsigned int coords_num, unsigned int(*tris)[3], struct MemArena *arena, struct Heap *eheap)
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNPACK2(a)
#define INIT_MINMAX(min, max)
#define ARRAY_SET_ITEMS(...)
#define UNLIKELY(x)
#define ELEM(...)
These structs are the foundation for all linked lists in the library system.
@ MOD_TRIANGULATE_NGON_BEAUTY
@ MOD_TRIANGULATE_QUAD_SHORTEDGE
@ MOD_TRIANGULATE_QUAD_FIXED
@ MOD_TRIANGULATE_QUAD_LONGEDGE
@ MOD_TRIANGULATE_QUAD_BEAUTY
@ MOD_TRIANGULATE_QUAD_ALTERNATE
NSNotificationCenter * center
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint order
Read Guarded memory(de)allocation.
float BM_verts_calc_rotate_beauty(const BMVert *v1, const BMVert *v2, const BMVert *v3, const BMVert *v4, const short flag, const short method)
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_LOOP
Definition: bmesh_class.h:385
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
#define BM_ELEM_CD_GET_VOID_P(ele, offset)
Definition: bmesh_class.h:541
void BM_elem_attrs_copy(BMesh *bm_src, BMesh *bm_dst, const void *ele_src, void *ele_dst)
void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
Definition: bmesh_core.c:2651
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)
Definition: bmesh_core.c:464
void BM_face_kill(BMesh *bm, BMFace *f)
Definition: bmesh_core.c:828
void bmesh_kernel_loop_reverse(BMesh *bm, BMFace *f, const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
Loop Reverse.
Definition: bmesh_core.c:965
@ BM_CREATE_NOP
Definition: bmesh_core.h:12
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_index_set(ele, index)
Definition: bmesh_inline.h:111
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_elem_flag_enable(ele, hflag)
Definition: bmesh_inline.h:14
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)
Definition: bmesh_interp.c:544
#define BM_ITER_ELEM(ele, iter, data, itype)
@ BM_FACES_OF_EDGE
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_face_calc_tangent_edge_pair(const BMFace *f, float r_tangent[3])
void BM_face_as_array_loop_tri(BMFace *f, BMLoop *r_loops[3])
float BM_face_calc_area_uv(const BMFace *f, int cd_loop_uv_offset)
void poly_rotate_plane(const float normal[3], float(*verts)[3], const uint nverts)
POLY ROTATE PLANE.
void BM_face_splits_check_optimal(BMFace *f, BMLoop *(*loops)[2], int len)
void BM_face_calc_center_bounds(const BMFace *f, float r_cent[3])
void BM_vert_normal_update(BMVert *v)
void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
void BM_face_calc_tangent_vert_diagonal(const BMFace *f, float r_tangent[3])
void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
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, struct Heap *pf_heap)
static int bm_vert_tri_find_unique_edge(BMVert *verts[3])
float BM_face_calc_area_with_mat3(const BMFace *f, const float mat3[3][3])
void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
void BM_verts_calc_normal_from_cloud(BMVert **varr, int varr_len, float r_normal[3])
bool BM_face_point_inside_test(const BMFace *f, const float co[3])
bool BM_vert_calc_normal(const BMVert *v, float r_no[3])
void BM_face_calc_tangent_edge_diagonal(const BMFace *f, float r_tangent[3])
static float bm_face_calc_poly_normal_vertex_cos(const BMFace *f, float r_no[3], float const (*vertexCos)[3])
COMPUTE POLY NORMAL (BMFace)
Definition: bmesh_polygon.c:64
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.
void BM_vert_tri_calc_tangent_edge(BMVert *verts[3], float r_tangent[3])
void BM_face_normal_update(BMFace *f)
void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[3])
bool BM_vert_calc_normal_ex(const BMVert *v, const char hflag, float r_no[3])
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], float const (*vertexCos)[3])
COMPUTE POLY CENTER (BMFace)
Definition: bmesh_polygon.c:90
void BM_face_normal_flip(BMesh *bm, BMFace *f)
void BM_face_calc_tangent_edge(const BMFace *f, float r_tangent[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)
void BM_face_calc_bounds_expand(const BMFace *f, float min[3], float max[3])
float BM_face_calc_area(const BMFace *f)
#define EDGE_SHARE_VERT(e1, e2)
float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
void BM_face_calc_center_median_vcos(const BMesh *bm, const BMFace *f, float r_cent[3], float const (*vertexCos)[3])
float BM_face_calc_normal(const BMFace *f, float r_no[3])
BMESH UPDATE FACE NORMAL.
float BM_face_calc_perimeter_with_mat3(const BMFace *f, const float mat3[3][3])
void BM_face_calc_center_bounds_vcos(const BMesh *bm, const BMFace *f, float r_cent[3], float const (*vertexCos)[3])
static void bm_loop_normal_accum(const BMLoop *l, float no[3])
void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3])
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])
void BM_face_calc_tangent_auto(const BMFace *f, float r_tangent[3])
static float bm_face_calc_poly_normal(const BMFace *f, float n[3])
COMPUTE POLY NORMAL (BMFace)
Definition: bmesh_polygon.c:36
void BM_face_calc_center_median_weighted(const BMFace *f, float r_cent[3])
void BM_vert_normal_update_all(BMVert *v)
float BM_face_calc_perimeter(const BMFace *f)
float BM_face_calc_normal_vcos(const BMesh *bm, const BMFace *f, float r_no[3], float const (*vertexCos)[3])
void BM_edge_normals_update(BMEdge *e)
bool BM_face_is_normal_valid(const BMFace *f)
Definition: bmesh_query.c:2033
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)
Definition: bmesh_query.c:251
float BM_edge_calc_length(const BMEdge *e)
Definition: bmesh_query.c:528
BMLoop * BM_face_find_longest_loop(BMFace *f)
Definition: bmesh_query.c:1508
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition: btQuadWord.h:119
SyclQueue void void size_t num_bytes void
int len
Definition: draw_manager.c:108
static float verts[][3]
IconTextureDrawCall normal
#define fabsf(x)
Definition: metal/compat.h:219
static void area(int d1, int d2, int e1, int e2, float weights[2])
vec_base< T, 3 > cross(const vec_base< T, 3 > &a, const vec_base< T, 3 > &b)
static const pxr::TfToken out("out", pxr::TfToken::Immortal)
#define min(a, b)
Definition: sort.c:35
int len
Definition: bmesh_class.h:267
float no[3]
Definition: bmesh_class.h:271
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
float co[3]
Definition: bmesh_class.h:87
struct BMEdge * e
Definition: bmesh_class.h:97
float no[3]
Definition: bmesh_class.h:88
char elem_index_dirty
Definition: bmesh_class.h:305
CustomData ldata
Definition: bmesh_class.h:337
Definition: BLI_heap.c:43
float max