Blender  V3.3
mesh_evaluate.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
10 #include <climits>
11 
12 #include "MEM_guardedalloc.h"
13 
14 #include "DNA_mesh_types.h"
15 #include "DNA_meshdata_types.h"
16 #include "DNA_object_types.h"
17 
18 #include "BLI_alloca.h"
19 #include "BLI_bitmap.h"
20 #include "BLI_edgehash.h"
21 #include "BLI_index_range.hh"
22 #include "BLI_math.h"
23 #include "BLI_span.hh"
24 #include "BLI_utildefines.h"
25 
26 #include "BKE_customdata.h"
27 
28 #include "BKE_mesh.h"
29 #include "BKE_multires.h"
30 
33 using blender::Span;
34 
35 /* -------------------------------------------------------------------- */
39 /*
40  * COMPUTE POLY NORMAL
41  *
42  * Computes the normal of a planar
43  * polygon See Graphics Gems for
44  * computing newell normal.
45  */
46 static void mesh_calc_ngon_normal(const MPoly *mpoly,
47  const MLoop *loopstart,
48  const MVert *mvert,
49  float normal[3])
50 {
51  const int nverts = mpoly->totloop;
52  const float *v_prev = mvert[loopstart[nverts - 1].v].co;
53  const float *v_curr;
54 
55  zero_v3(normal);
56 
57  /* Newell's Method */
58  for (int i = 0; i < nverts; i++) {
59  v_curr = mvert[loopstart[i].v].co;
60  add_newell_cross_v3_v3v3(normal, v_prev, v_curr);
61  v_prev = v_curr;
62  }
63 
64  if (UNLIKELY(normalize_v3(normal) == 0.0f)) {
65  normal[2] = 1.0f; /* other axis set to 0.0 */
66  }
67 }
68 
69 void BKE_mesh_calc_poly_normal(const MPoly *mpoly,
70  const MLoop *loopstart,
71  const MVert *mvarray,
72  float r_no[3])
73 {
74  if (mpoly->totloop > 4) {
75  mesh_calc_ngon_normal(mpoly, loopstart, mvarray, r_no);
76  }
77  else if (mpoly->totloop == 3) {
79  r_no, mvarray[loopstart[0].v].co, mvarray[loopstart[1].v].co, mvarray[loopstart[2].v].co);
80  }
81  else if (mpoly->totloop == 4) {
82  normal_quad_v3(r_no,
83  mvarray[loopstart[0].v].co,
84  mvarray[loopstart[1].v].co,
85  mvarray[loopstart[2].v].co,
86  mvarray[loopstart[3].v].co);
87  }
88  else { /* horrible, two sided face! */
89  r_no[0] = 0.0;
90  r_no[1] = 0.0;
91  r_no[2] = 1.0;
92  }
93 }
94 /* duplicate of function above _but_ takes coords rather than mverts */
95 static void mesh_calc_ngon_normal_coords(const MPoly *mpoly,
96  const MLoop *loopstart,
97  const float (*vertex_coords)[3],
98  float r_normal[3])
99 {
100  const int nverts = mpoly->totloop;
101  const float *v_prev = vertex_coords[loopstart[nverts - 1].v];
102  const float *v_curr;
103 
104  zero_v3(r_normal);
105 
106  /* Newell's Method */
107  for (int i = 0; i < nverts; i++) {
108  v_curr = vertex_coords[loopstart[i].v];
109  add_newell_cross_v3_v3v3(r_normal, v_prev, v_curr);
110  v_prev = v_curr;
111  }
112 
113  if (UNLIKELY(normalize_v3(r_normal) == 0.0f)) {
114  r_normal[2] = 1.0f; /* other axis set to 0.0 */
115  }
116 }
117 
119  const MLoop *loopstart,
120  const float (*vertex_coords)[3],
121  float r_no[3])
122 {
123  if (mpoly->totloop > 4) {
124  mesh_calc_ngon_normal_coords(mpoly, loopstart, vertex_coords, r_no);
125  }
126  else if (mpoly->totloop == 3) {
127  normal_tri_v3(r_no,
128  vertex_coords[loopstart[0].v],
129  vertex_coords[loopstart[1].v],
130  vertex_coords[loopstart[2].v]);
131  }
132  else if (mpoly->totloop == 4) {
133  normal_quad_v3(r_no,
134  vertex_coords[loopstart[0].v],
135  vertex_coords[loopstart[1].v],
136  vertex_coords[loopstart[2].v],
137  vertex_coords[loopstart[3].v]);
138  }
139  else { /* horrible, two sided face! */
140  r_no[0] = 0.0;
141  r_no[1] = 0.0;
142  r_no[2] = 1.0;
143  }
144 }
145 
146 static void mesh_calc_ngon_center(const MPoly *mpoly,
147  const MLoop *loopstart,
148  const MVert *mvert,
149  float cent[3])
150 {
151  const float w = 1.0f / (float)mpoly->totloop;
152 
153  zero_v3(cent);
154 
155  for (int i = 0; i < mpoly->totloop; i++) {
156  madd_v3_v3fl(cent, mvert[(loopstart++)->v].co, w);
157  }
158 }
159 
161  const MLoop *loopstart,
162  const MVert *mvarray,
163  float r_cent[3])
164 {
165  if (mpoly->totloop == 3) {
166  mid_v3_v3v3v3(r_cent,
167  mvarray[loopstart[0].v].co,
168  mvarray[loopstart[1].v].co,
169  mvarray[loopstart[2].v].co);
170  }
171  else if (mpoly->totloop == 4) {
172  mid_v3_v3v3v3v3(r_cent,
173  mvarray[loopstart[0].v].co,
174  mvarray[loopstart[1].v].co,
175  mvarray[loopstart[2].v].co,
176  mvarray[loopstart[3].v].co);
177  }
178  else {
179  mesh_calc_ngon_center(mpoly, loopstart, mvarray, r_cent);
180  }
181 }
182 
183 float BKE_mesh_calc_poly_area(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray)
184 {
185  if (mpoly->totloop == 3) {
186  return area_tri_v3(
187  mvarray[loopstart[0].v].co, mvarray[loopstart[1].v].co, mvarray[loopstart[2].v].co);
188  }
189 
190  const MLoop *l_iter = loopstart;
191  float(*vertexcos)[3] = (float(*)[3])BLI_array_alloca(vertexcos, (size_t)mpoly->totloop);
192 
193  /* pack vertex cos into an array for area_poly_v3 */
194  for (int i = 0; i < mpoly->totloop; i++, l_iter++) {
195  copy_v3_v3(vertexcos[i], mvarray[l_iter->v].co);
196  }
197 
198  /* finally calculate the area */
199  float area = area_poly_v3((const float(*)[3])vertexcos, (uint)mpoly->totloop);
200 
201  return area;
202 }
203 
204 float BKE_mesh_calc_area(const Mesh *me)
205 {
206  MVert *mvert = me->mvert;
207  MLoop *mloop = me->mloop;
208  MPoly *mpoly = me->mpoly;
209 
210  MPoly *mp;
211  int i = me->totpoly;
212  float total_area = 0;
213 
214  for (mp = mpoly; i--; mp++) {
215  MLoop *ml_start = &mloop[mp->loopstart];
216 
217  total_area += BKE_mesh_calc_poly_area(mp, ml_start, mvert);
218  }
219  return total_area;
220 }
221 
222 float BKE_mesh_calc_poly_uv_area(const MPoly *mpoly, const MLoopUV *uv_array)
223 {
224 
225  int i, l_iter = mpoly->loopstart;
226  float area;
227  float(*vertexcos)[2] = (float(*)[2])BLI_array_alloca(vertexcos, (size_t)mpoly->totloop);
228 
229  /* pack vertex cos into an array for area_poly_v2 */
230  for (i = 0; i < mpoly->totloop; i++, l_iter++) {
231  copy_v2_v2(vertexcos[i], uv_array[l_iter].uv);
232  }
233 
234  /* finally calculate the area */
235  area = area_poly_v2(vertexcos, (uint)mpoly->totloop);
236 
237  return area;
238 }
239 
241  const MLoop *loopstart,
242  const MVert *mvarray,
243  float r_cent[3])
244 {
245  const float *v_pivot, *v_step1;
246  float total_volume = 0.0f;
247 
248  zero_v3(r_cent);
249 
250  v_pivot = mvarray[loopstart[0].v].co;
251  v_step1 = mvarray[loopstart[1].v].co;
252 
253  for (int i = 2; i < mpoly->totloop; i++) {
254  const float *v_step2 = mvarray[loopstart[i].v].co;
255 
256  /* Calculate the 6x volume of the tetrahedron formed by the 3 vertices
257  * of the triangle and the origin as the fourth vertex */
258  const float tetra_volume = volume_tri_tetrahedron_signed_v3_6x(v_pivot, v_step1, v_step2);
259  total_volume += tetra_volume;
260 
261  /* Calculate the centroid of the tetrahedron formed by the 3 vertices
262  * of the triangle and the origin as the fourth vertex.
263  * The centroid is simply the average of the 4 vertices.
264  *
265  * Note that the vector is 4x the actual centroid
266  * so the division can be done once at the end. */
267  for (uint j = 0; j < 3; j++) {
268  r_cent[j] += tetra_volume * (v_pivot[j] + v_step1[j] + v_step2[j]);
269  }
270 
271  v_step1 = v_step2;
272  }
273 
274  return total_volume;
275 }
276 
283  const MLoop *loopstart,
284  const MVert *mvarray,
285  const float reference_center[3],
286  float r_cent[3])
287 {
288  /* See: mesh_calc_poly_volume_centroid for comments. */
289  float v_pivot[3], v_step1[3];
290  float total_volume = 0.0f;
291  zero_v3(r_cent);
292  sub_v3_v3v3(v_pivot, mvarray[loopstart[0].v].co, reference_center);
293  sub_v3_v3v3(v_step1, mvarray[loopstart[1].v].co, reference_center);
294  for (int i = 2; i < mpoly->totloop; i++) {
295  float v_step2[3];
296  sub_v3_v3v3(v_step2, mvarray[loopstart[i].v].co, reference_center);
297  const float tetra_volume = volume_tri_tetrahedron_signed_v3_6x(v_pivot, v_step1, v_step2);
298  total_volume += tetra_volume;
299  for (uint j = 0; j < 3; j++) {
300  r_cent[j] += tetra_volume * (v_pivot[j] + v_step1[j] + v_step2[j]);
301  }
302  copy_v3_v3(v_step1, v_step2);
303  }
304  return total_volume;
305 }
306 
313 static float mesh_calc_poly_area_centroid(const MPoly *mpoly,
314  const MLoop *loopstart,
315  const MVert *mvarray,
316  float r_cent[3])
317 {
318  float total_area = 0.0f;
319  float v1[3], v2[3], v3[3], normal[3], tri_cent[3];
320 
321  BKE_mesh_calc_poly_normal(mpoly, loopstart, mvarray, normal);
322  copy_v3_v3(v1, mvarray[loopstart[0].v].co);
323  copy_v3_v3(v2, mvarray[loopstart[1].v].co);
324  zero_v3(r_cent);
325 
326  for (int i = 2; i < mpoly->totloop; i++) {
327  copy_v3_v3(v3, mvarray[loopstart[i].v].co);
328 
329  float tri_area = area_tri_signed_v3(v1, v2, v3, normal);
330  total_area += tri_area;
331 
332  mid_v3_v3v3v3(tri_cent, v1, v2, v3);
333  madd_v3_v3fl(r_cent, tri_cent, tri_area);
334 
335  copy_v3_v3(v2, v3);
336  }
337 
338  mul_v3_fl(r_cent, 1.0f / total_area);
339 
340  return total_area;
341 }
342 
344  const MLoop *loopstart,
345  const MVert *mvarray,
346  float angles[])
347 {
348  float nor_prev[3];
349  float nor_next[3];
350 
351  int i_this = mpoly->totloop - 1;
352  int i_next = 0;
353 
354  sub_v3_v3v3(nor_prev, mvarray[loopstart[i_this - 1].v].co, mvarray[loopstart[i_this].v].co);
355  normalize_v3(nor_prev);
356 
357  while (i_next < mpoly->totloop) {
358  sub_v3_v3v3(nor_next, mvarray[loopstart[i_this].v].co, mvarray[loopstart[i_next].v].co);
359  normalize_v3(nor_next);
360  angles[i_this] = angle_normalized_v3v3(nor_prev, nor_next);
361 
362  /* step */
363  copy_v3_v3(nor_prev, nor_next);
364  i_this = i_next;
365  i_next++;
366  }
367 }
368 
369 void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop)
370 {
371  const MLoop *ml, *ml_next;
372  int i = mp->totloop;
373 
374  ml_next = mloop; /* first loop */
375  ml = &ml_next[i - 1]; /* last loop */
376 
377  while (i-- != 0) {
378  BLI_edgehash_reinsert(ehash, ml->v, ml_next->v, nullptr);
379 
380  ml = ml_next;
381  ml_next++;
382  }
383 }
384 
385 void BKE_mesh_poly_edgebitmap_insert(uint *edge_bitmap, const MPoly *mp, const MLoop *mloop)
386 {
387  const MLoop *ml;
388  int i = mp->totloop;
389 
390  ml = mloop;
391 
392  while (i-- != 0) {
393  BLI_BITMAP_ENABLE(edge_bitmap, ml->e);
394  ml++;
395  }
396 }
397 
400 /* -------------------------------------------------------------------- */
404 bool BKE_mesh_center_median(const Mesh *me, float r_cent[3])
405 {
406  int i = me->totvert;
407  const MVert *mvert;
408  zero_v3(r_cent);
409  for (mvert = me->mvert; i--; mvert++) {
410  add_v3_v3(r_cent, mvert->co);
411  }
412  /* otherwise we get NAN for 0 verts */
413  if (me->totvert) {
414  mul_v3_fl(r_cent, 1.0f / (float)me->totvert);
415  }
416  return (me->totvert != 0);
417 }
418 
419 bool BKE_mesh_center_median_from_polys(const Mesh *me, float r_cent[3])
420 {
421  int i = me->totpoly;
422  int tot = 0;
423  const MPoly *mpoly = me->mpoly;
424  const MLoop *mloop = me->mloop;
425  const MVert *mvert = me->mvert;
426  zero_v3(r_cent);
427  for (; i--; mpoly++) {
428  int loopend = mpoly->loopstart + mpoly->totloop;
429  for (int j = mpoly->loopstart; j < loopend; j++) {
430  add_v3_v3(r_cent, mvert[mloop[j].v].co);
431  }
432  tot += mpoly->totloop;
433  }
434  /* otherwise we get NAN for 0 verts */
435  if (me->totpoly) {
436  mul_v3_fl(r_cent, 1.0f / (float)tot);
437  }
438  return (me->totpoly != 0);
439 }
440 
441 bool BKE_mesh_center_bounds(const Mesh *me, float r_cent[3])
442 {
443  float min[3], max[3];
444  INIT_MINMAX(min, max);
445  if (BKE_mesh_minmax(me, min, max)) {
446  mid_v3_v3v3(r_cent, min, max);
447  return true;
448  }
449 
450  return false;
451 }
452 
453 bool BKE_mesh_center_of_surface(const Mesh *me, float r_cent[3])
454 {
455  int i = me->totpoly;
456  MPoly *mpoly;
457  float poly_area;
458  float total_area = 0.0f;
459  float poly_cent[3];
460 
461  zero_v3(r_cent);
462 
463  /* calculate a weighted average of polygon centroids */
464  for (mpoly = me->mpoly; i--; mpoly++) {
465  poly_area = mesh_calc_poly_area_centroid(
466  mpoly, me->mloop + mpoly->loopstart, me->mvert, poly_cent);
467 
468  madd_v3_v3fl(r_cent, poly_cent, poly_area);
469  total_area += poly_area;
470  }
471  /* otherwise we get NAN for 0 polys */
472  if (me->totpoly) {
473  mul_v3_fl(r_cent, 1.0f / total_area);
474  }
475 
476  /* zero area faces cause this, fallback to median */
477  if (UNLIKELY(!is_finite_v3(r_cent))) {
478  return BKE_mesh_center_median(me, r_cent);
479  }
480 
481  return (me->totpoly != 0);
482 }
483 
484 bool BKE_mesh_center_of_volume(const Mesh *me, float r_cent[3])
485 {
486  int i = me->totpoly;
487  MPoly *mpoly;
488  float poly_volume;
489  float total_volume = 0.0f;
490  float poly_cent[3];
491 
492  /* Use an initial center to avoid numeric instability of geometry far away from the center. */
493  float init_cent[3];
494  const bool init_cent_result = BKE_mesh_center_median_from_polys(me, init_cent);
495 
496  zero_v3(r_cent);
497 
498  /* calculate a weighted average of polyhedron centroids */
499  for (mpoly = me->mpoly; i--; mpoly++) {
501  mpoly, me->mloop + mpoly->loopstart, me->mvert, init_cent, poly_cent);
502 
503  /* poly_cent is already volume-weighted, so no need to multiply by the volume */
504  add_v3_v3(r_cent, poly_cent);
505  total_volume += poly_volume;
506  }
507  /* otherwise we get NAN for 0 polys */
508  if (total_volume != 0.0f) {
509  /* multiply by 0.25 to get the correct centroid */
510  /* no need to divide volume by 6 as the centroid is weighted by 6x the volume,
511  * so it all cancels out. */
512  mul_v3_fl(r_cent, 0.25f / total_volume);
513  }
514 
515  /* this can happen for non-manifold objects, fallback to median */
516  if (UNLIKELY(!is_finite_v3(r_cent))) {
517  copy_v3_v3(r_cent, init_cent);
518  return init_cent_result;
519  }
520  add_v3_v3(r_cent, init_cent);
521  return (me->totpoly != 0);
522 }
523 
526 /* -------------------------------------------------------------------- */
530 static bool mesh_calc_center_centroid_ex(const MVert *mverts,
531  int UNUSED(mverts_num),
532  const MLoopTri *looptri,
533  int looptri_num,
534  const MLoop *mloop,
535  float r_center[3])
536 {
537 
538  zero_v3(r_center);
539 
540  if (looptri_num == 0) {
541  return false;
542  }
543 
544  float totweight = 0.0f;
545  const MLoopTri *lt;
546  int i;
547  for (i = 0, lt = looptri; i < looptri_num; i++, lt++) {
548  const MVert *v1 = &mverts[mloop[lt->tri[0]].v];
549  const MVert *v2 = &mverts[mloop[lt->tri[1]].v];
550  const MVert *v3 = &mverts[mloop[lt->tri[2]].v];
551  float area;
552 
553  area = area_tri_v3(v1->co, v2->co, v3->co);
554  madd_v3_v3fl(r_center, v1->co, area);
555  madd_v3_v3fl(r_center, v2->co, area);
556  madd_v3_v3fl(r_center, v3->co, area);
557  totweight += area;
558  }
559  if (totweight == 0.0f) {
560  return false;
561  }
562 
563  mul_v3_fl(r_center, 1.0f / (3.0f * totweight));
564 
565  return true;
566 }
567 
568 void BKE_mesh_calc_volume(const MVert *mverts,
569  const int mverts_num,
570  const MLoopTri *looptri,
571  const int looptri_num,
572  const MLoop *mloop,
573  float *r_volume,
574  float r_center[3])
575 {
576  const MLoopTri *lt;
577  float center[3];
578  float totvol;
579  int i;
580 
581  if (r_volume) {
582  *r_volume = 0.0f;
583  }
584  if (r_center) {
585  zero_v3(r_center);
586  }
587 
588  if (looptri_num == 0) {
589  return;
590  }
591 
592  if (!mesh_calc_center_centroid_ex(mverts, mverts_num, looptri, looptri_num, mloop, center)) {
593  return;
594  }
595 
596  totvol = 0.0f;
597 
598  for (i = 0, lt = looptri; i < looptri_num; i++, lt++) {
599  const MVert *v1 = &mverts[mloop[lt->tri[0]].v];
600  const MVert *v2 = &mverts[mloop[lt->tri[1]].v];
601  const MVert *v3 = &mverts[mloop[lt->tri[2]].v];
602  float vol;
603 
604  vol = volume_tetrahedron_signed_v3(center, v1->co, v2->co, v3->co);
605  if (r_volume) {
606  totvol += vol;
607  }
608  if (r_center) {
609  /* averaging factor 1/3 is applied in the end */
610  madd_v3_v3fl(r_center, v1->co, vol);
611  madd_v3_v3fl(r_center, v2->co, vol);
612  madd_v3_v3fl(r_center, v3->co, vol);
613  }
614  }
615 
616  /* NOTE: Depending on arbitrary centroid position,
617  * totvol can become negative even for a valid mesh.
618  * The true value is always the positive value.
619  */
620  if (r_volume) {
621  *r_volume = fabsf(totvol);
622  }
623  if (r_center) {
624  /* NOTE: Factor 1/3 is applied once for all vertices here.
625  * This also automatically negates the vector if totvol is negative.
626  */
627  if (totvol != 0.0f) {
628  mul_v3_fl(r_center, (1.0f / 3.0f) / totvol);
629  }
630  }
631 }
632 
635 void BKE_mesh_mdisp_flip(MDisps *md, const bool use_loop_mdisp_flip)
636 {
637  if (UNLIKELY(!md->totdisp || !md->disps)) {
638  return;
639  }
640 
641  const int sides = (int)sqrt(md->totdisp);
642  float(*co)[3] = md->disps;
643 
644  for (int x = 0; x < sides; x++) {
645  float *co_a, *co_b;
646 
647  for (int y = 0; y < x; y++) {
648  co_a = co[y * sides + x];
649  co_b = co[x * sides + y];
650 
651  swap_v3_v3(co_a, co_b);
652  SWAP(float, co_a[0], co_a[1]);
653  SWAP(float, co_b[0], co_b[1]);
654 
655  if (use_loop_mdisp_flip) {
656  co_a[2] *= -1.0f;
657  co_b[2] *= -1.0f;
658  }
659  }
660 
661  co_a = co[x * sides + x];
662 
663  SWAP(float, co_a[0], co_a[1]);
664 
665  if (use_loop_mdisp_flip) {
666  co_a[2] *= -1.0f;
667  }
668  }
669 }
670 
672  MLoop *mloop,
673  CustomData *ldata,
674  float (*lnors)[3],
675  MDisps *mdisp,
676  const bool use_loop_mdisp_flip)
677 {
678  int loopstart = mpoly->loopstart;
679  int loopend = loopstart + mpoly->totloop - 1;
680  const bool loops_in_ldata = (CustomData_get_layer(ldata, CD_MLOOP) == mloop);
681 
682  if (mdisp) {
683  for (int i = loopstart; i <= loopend; i++) {
684  BKE_mesh_mdisp_flip(&mdisp[i], use_loop_mdisp_flip);
685  }
686  }
687 
688  /* Note that we keep same start vertex for flipped face. */
689 
690  /* We also have to update loops edge
691  * (they will get their original 'other edge', that is,
692  * the original edge of their original previous loop)... */
693  uint prev_edge_index = mloop[loopstart].e;
694  mloop[loopstart].e = mloop[loopend].e;
695 
696  for (loopstart++; loopend > loopstart; loopstart++, loopend--) {
697  mloop[loopend].e = mloop[loopend - 1].e;
698  SWAP(uint, mloop[loopstart].e, prev_edge_index);
699 
700  if (!loops_in_ldata) {
701  SWAP(MLoop, mloop[loopstart], mloop[loopend]);
702  }
703  if (lnors) {
704  swap_v3_v3(lnors[loopstart], lnors[loopend]);
705  }
706  CustomData_swap(ldata, loopstart, loopend);
707  }
708  /* Even if we did not swap the other 'pivot' loop, we need to set its swapped edge. */
709  if (loopstart == loopend) {
710  mloop[loopstart].e = prev_edge_index;
711  }
712 }
713 
714 void BKE_mesh_polygon_flip(MPoly *mpoly, MLoop *mloop, CustomData *ldata)
715 {
716  MDisps *mdisp = (MDisps *)CustomData_get_layer(ldata, CD_MDISPS);
717  BKE_mesh_polygon_flip_ex(mpoly, mloop, ldata, nullptr, mdisp, true);
718 }
719 
720 void BKE_mesh_polygons_flip(MPoly *mpoly, MLoop *mloop, CustomData *ldata, int totpoly)
721 {
722  MDisps *mdisp = (MDisps *)CustomData_get_layer(ldata, CD_MDISPS);
723  MPoly *mp;
724  int i;
725 
726  for (mp = mpoly, i = 0; i < totpoly; mp++, i++) {
727  BKE_mesh_polygon_flip_ex(mp, mloop, ldata, nullptr, mdisp, true);
728  }
729 }
730 
731 /* -------------------------------------------------------------------- */
736  const MLoop *mloop,
737  MEdge *medge,
738  const int totedge,
739  MPoly *mpoly,
740  const int totpoly)
741 {
742  int i, j;
743 
744  for (i = 0; i < totedge; i++) {
745  MEdge *e = &medge[i];
746  if (mvert[e->v1].flag & ME_HIDE || mvert[e->v2].flag & ME_HIDE) {
747  e->flag |= ME_HIDE;
748  }
749  else {
750  e->flag &= ~ME_HIDE;
751  }
752  }
753  for (i = 0; i < totpoly; i++) {
754  MPoly *p = &mpoly[i];
755  p->flag &= (char)~ME_HIDE;
756  for (j = 0; j < p->totloop; j++) {
757  if (mvert[mloop[p->loopstart + j].v].flag & ME_HIDE) {
758  p->flag |= ME_HIDE;
759  }
760  }
761  }
762 }
764 {
766  me->mvert, me->mloop, me->medge, me->totedge, me->mpoly, me->totpoly);
767 }
768 
770  const MLoop *mloop,
771  MEdge *medge,
772  const int UNUSED(totedge),
773  const MPoly *mpoly,
774  const int totpoly)
775 {
776  int i = totpoly;
777  for (const MPoly *mp = mpoly; i--; mp++) {
778  if (mp->flag & ME_HIDE) {
779  const MLoop *ml;
780  int j = mp->totloop;
781  for (ml = &mloop[mp->loopstart]; j--; ml++) {
782  mvert[ml->v].flag |= ME_HIDE;
783  medge[ml->e].flag |= ME_HIDE;
784  }
785  }
786  }
787 
788  i = totpoly;
789  for (const MPoly *mp = mpoly; i--; mp++) {
790  if ((mp->flag & ME_HIDE) == 0) {
791  const MLoop *ml;
792  int j = mp->totloop;
793  for (ml = &mloop[mp->loopstart]; j--; ml++) {
794  mvert[ml->v].flag &= (char)~ME_HIDE;
795  medge[ml->e].flag &= (short)~ME_HIDE;
796  }
797  }
798  }
799 }
801 {
803  me->mvert, me->mloop, me->medge, me->totedge, me->mpoly, me->totpoly);
804 }
805 
807  const int totvert,
808  const MLoop *mloop,
809  MEdge *medge,
810  const int totedge,
811  const MPoly *mpoly,
812  const int totpoly)
813 {
814  MVert *mv;
815  MEdge *med;
816  const MPoly *mp;
817 
818  int i = totvert;
819  for (mv = mvert; i--; mv++) {
820  mv->flag &= (char)~SELECT;
821  }
822 
823  i = totedge;
824  for (med = medge; i--; med++) {
825  med->flag &= ~SELECT;
826  }
827 
828  i = totpoly;
829  for (mp = mpoly; i--; mp++) {
830  /* Assume if its selected its not hidden and none of its verts/edges are hidden
831  * (a common assumption). */
832  if (mp->flag & ME_FACE_SEL) {
833  const MLoop *ml;
834  int j;
835  j = mp->totloop;
836  for (ml = &mloop[mp->loopstart]; j--; ml++) {
837  mvert[ml->v].flag |= SELECT;
838  medge[ml->e].flag |= SELECT;
839  }
840  }
841  }
842 }
844 {
846  me->mvert, me->totvert, me->mloop, me->medge, me->totedge, me->mpoly, me->totpoly);
847 }
848 
850  const Span<MLoop> loops,
851  MutableSpan<MEdge> edges,
852  MutableSpan<MPoly> polys)
853 {
854  for (const int i : edges.index_range()) {
855  if ((edges[i].flag & ME_HIDE) == 0) {
856  MEdge &edge = edges[i];
857  if ((verts[edge.v1].flag & SELECT) && (verts[edge.v2].flag & SELECT)) {
858  edge.flag |= SELECT;
859  }
860  else {
861  edge.flag &= ~SELECT;
862  }
863  }
864  }
865 
866  for (const int i : polys.index_range()) {
867  if (polys[i].flag & ME_HIDE) {
868  continue;
869  }
870  MPoly &poly = polys[i];
871  bool all_verts_selected = true;
872  for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
873  if (!(verts[loop.v].flag & SELECT)) {
874  all_verts_selected = false;
875  }
876  }
877  if (all_verts_selected) {
878  poly.flag |= ME_FACE_SEL;
879  }
880  else {
881  poly.flag &= (char)~ME_FACE_SEL;
882  }
883  }
884 }
885 
887 {
889  {me->mloop, me->totloop},
890  {me->medge, me->totedge},
891  {me->mpoly, me->totpoly});
892 }
893 
896 /* -------------------------------------------------------------------- */
901  const int totpoly,
902  const MLoop *mloop,
903  const int totvert,
904 
905  const float (*vert_cos_src)[3],
906  const float (*vert_cos_dst)[3],
907 
908  const float (*vert_cos_org)[3],
909  float (*vert_cos_new)[3])
910 {
911  const MPoly *mp;
912  int i;
913 
914  int *vert_accum = (int *)MEM_calloc_arrayN((size_t)totvert, sizeof(*vert_accum), __func__);
915 
916  memset(vert_cos_new, '\0', sizeof(*vert_cos_new) * (size_t)totvert);
917 
918  for (i = 0, mp = mpoly; i < totpoly; i++, mp++) {
919  const MLoop *loopstart = mloop + mp->loopstart;
920 
921  for (int j = 0; j < mp->totloop; j++) {
922  uint v_prev = loopstart[(mp->totloop + (j - 1)) % mp->totloop].v;
923  uint v_curr = loopstart[j].v;
924  uint v_next = loopstart[(j + 1) % mp->totloop].v;
925 
926  float tvec[3];
927 
929  vert_cos_dst[v_curr],
930  vert_cos_org[v_prev],
931  vert_cos_org[v_curr],
932  vert_cos_org[v_next],
933  vert_cos_src[v_prev],
934  vert_cos_src[v_curr],
935  vert_cos_src[v_next]);
936 
937  add_v3_v3(vert_cos_new[v_curr], tvec);
938  vert_accum[v_curr] += 1;
939  }
940  }
941 
942  for (i = 0; i < totvert; i++) {
943  if (vert_accum[i]) {
944  mul_v3_fl(vert_cos_new[i], 1.0f / (float)vert_accum[i]);
945  }
946  else {
947  copy_v3_v3(vert_cos_new[i], vert_cos_org[i]);
948  }
949  }
950 
951  MEM_freeN(vert_accum);
952 }
953 
typedef float(TangentPoint)[2]
CustomData interface, see also DNA_customdata_types.h.
void * CustomData_get_layer(const struct CustomData *data, int type)
void CustomData_swap(struct CustomData *data, int index_a, int index_b)
Definition: customdata.cc:3319
bool BKE_mesh_minmax(const struct Mesh *me, float r_min[3], float r_max[3])
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
bool BLI_edgehash_reinsert(EdgeHash *eh, unsigned int v0, unsigned int v1, void *val)
Definition: edgehash.c:268
sqrt(x)+1/max(0
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
float area_poly_v3(const float verts[][3], unsigned int nr)
Definition: math_geom.c:125
void transform_point_by_tri_v3(float pt_tar[3], float const pt_src[3], const float tri_tar_p1[3], const float tri_tar_p2[3], const float tri_tar_p3[3], const float tri_src_p1[3], const float tri_src_p2[3], const float tri_src_p3[3])
Definition: math_geom.c:3862
float area_tri_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float normal[3])
Definition: math_geom.c:107
float volume_tri_tetrahedron_signed_v3_6x(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:255
float area_tri_v3(const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:92
float volume_tetrahedron_signed_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_geom.c:243
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
float area_poly_v2(const float verts[][2], unsigned int nr)
Definition: math_geom.c:174
void mid_v3_v3v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3], const float v4[3])
Definition: math_vector.c:263
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
MINLINE float normalize_v3(float r[3])
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 copy_v2_v2(float r[2], const float a[2])
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE void copy_v3_v3(float r[3], const float a[3])
bool is_finite_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:349
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
Definition: math_vector.c:237
MINLINE void swap_v3_v3(float a[3], float b[3])
MINLINE void zero_v3(float r[3])
float angle_normalized_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
Definition: math_vector.c:445
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
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNUSED_FUNCTION(x)
#define INIT_MINMAX(min, max)
#define SWAP(type, a, b)
#define UNUSED(x)
#define UNLIKELY(x)
@ ME_HIDE
@ ME_FACE_SEL
Object is a sort of wrapper for general info.
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 y
_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 const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition: btQuadWord.h:119
constexpr IndexRange index_range() const
Definition: BLI_span.hh:661
constexpr Span slice(int64_t start, int64_t size) const
Definition: BLI_span.hh:142
#define SELECT
static float verts[][3]
IconTextureDrawCall normal
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_calloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:32
bool BKE_mesh_center_median_from_polys(const Mesh *me, float r_cent[3])
static void mesh_calc_ngon_normal(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvert, float normal[3])
static float mesh_calc_poly_volume_centroid_with_reference_center(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray, const float reference_center[3], float r_cent[3])
static void mesh_calc_ngon_normal_coords(const MPoly *mpoly, const MLoop *loopstart, const float(*vertex_coords)[3], float r_normal[3])
void BKE_mesh_polygon_flip_ex(MPoly *mpoly, MLoop *mloop, CustomData *ldata, float(*lnors)[3], MDisps *mdisp, const bool use_loop_mdisp_flip)
static void mesh_flush_select_from_verts(const Span< MVert > verts, const Span< MLoop > loops, MutableSpan< MEdge > edges, MutableSpan< MPoly > polys)
void BKE_mesh_polygons_flip(MPoly *mpoly, MLoop *mloop, CustomData *ldata, int totpoly)
void BKE_mesh_calc_poly_normal(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray, float r_no[3])
bool BKE_mesh_center_of_surface(const Mesh *me, float r_cent[3])
bool BKE_mesh_center_bounds(const Mesh *me, float r_cent[3])
void BKE_mesh_poly_edgebitmap_insert(uint *edge_bitmap, const MPoly *mp, const MLoop *mloop)
void BKE_mesh_mdisp_flip(MDisps *md, const bool use_loop_mdisp_flip)
float BKE_mesh_calc_area(const Mesh *me)
void BKE_mesh_calc_poly_angles(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray, float angles[])
void BKE_mesh_flush_hidden_from_polys(Mesh *me)
float BKE_mesh_calc_poly_area(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray)
void BKE_mesh_flush_select_from_polys_ex(MVert *mvert, const int totvert, const MLoop *mloop, MEdge *medge, const int totedge, const MPoly *mpoly, const int totpoly)
void BKE_mesh_calc_poly_center(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray, float r_cent[3])
void BKE_mesh_polygon_flip(MPoly *mpoly, MLoop *mloop, CustomData *ldata)
void BKE_mesh_calc_relative_deform(const MPoly *mpoly, const int totpoly, const MLoop *mloop, const int totvert, const float(*vert_cos_src)[3], const float(*vert_cos_dst)[3], const float(*vert_cos_org)[3], float(*vert_cos_new)[3])
void BKE_mesh_calc_poly_normal_coords(const MPoly *mpoly, const MLoop *loopstart, const float(*vertex_coords)[3], float r_no[3])
bool BKE_mesh_center_median(const Mesh *me, float r_cent[3])
static float UNUSED_FUNCTION() mesh_calc_poly_volume_centroid(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray, float r_cent[3])
void BKE_mesh_flush_hidden_from_verts(Mesh *me)
void BKE_mesh_flush_select_from_verts(Mesh *me)
void BKE_mesh_poly_edgehash_insert(EdgeHash *ehash, const MPoly *mp, const MLoop *mloop)
void BKE_mesh_flush_hidden_from_polys_ex(MVert *mvert, const MLoop *mloop, MEdge *medge, const int UNUSED(totedge), const MPoly *mpoly, const int totpoly)
float BKE_mesh_calc_poly_uv_area(const MPoly *mpoly, const MLoopUV *uv_array)
void BKE_mesh_calc_volume(const MVert *mverts, const int mverts_num, const MLoopTri *looptri, const int looptri_num, const MLoop *mloop, float *r_volume, float r_center[3])
static bool mesh_calc_center_centroid_ex(const MVert *mverts, int UNUSED(mverts_num), const MLoopTri *looptri, int looptri_num, const MLoop *mloop, float r_center[3])
static float mesh_calc_poly_area_centroid(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvarray, float r_cent[3])
void BKE_mesh_flush_hidden_from_verts_ex(const MVert *mvert, const MLoop *mloop, MEdge *medge, const int totedge, MPoly *mpoly, const int totpoly)
bool BKE_mesh_center_of_volume(const Mesh *me, float r_cent[3])
static void mesh_calc_ngon_center(const MPoly *mpoly, const MLoop *loopstart, const MVert *mvert, float cent[3])
void BKE_mesh_flush_select_from_polys(Mesh *me)
#define fabsf(x)
Definition: metal/compat.h:219
static void area(int d1, int d2, int e1, int e2, float weights[2])
#define min(a, b)
Definition: sort.c:35
float co[3]
Definition: bmesh_class.h:87
float(* disps)[3]
unsigned int tri[3]
unsigned int e
unsigned int v
float co[3]
struct MEdge * medge
struct MVert * mvert
int totedge
int totvert
struct MLoop * mloop
int totpoly
int totloop
struct MPoly * mpoly
float max