BMesh: backport minor changes from 2.8
[blender.git] / source / blender / bmesh / intern / bmesh_polygon.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_polygon.c
24  *  \ingroup bmesh
25  *
26  * This file contains code for dealing
27  * with polygons (normal/area calculation,
28  * tessellation, etc)
29  */
30
31 #include "DNA_listBase.h"
32 #include "DNA_modifier_types.h"
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_alloca.h"
37 #include "BLI_math.h"
38 #include "BLI_memarena.h"
39 #include "BLI_polyfill_2d.h"
40 #include "BLI_polyfill_2d_beautify.h"
41 #include "BLI_linklist.h"
42 #include "BLI_edgehash.h"
43 #include "BLI_heap.h"
44
45 #include "bmesh.h"
46 #include "bmesh_tools.h"
47
48 #include "BKE_customdata.h"
49
50 #include "intern/bmesh_private.h"
51
52 /**
53  * \brief COMPUTE POLY NORMAL (BMFace)
54  *
55  * Same as #normal_poly_v3 but operates directly on a bmesh face.
56  */
57 static float bm_face_calc_poly_normal(const BMFace *f, float n[3])
58 {
59         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
60         BMLoop *l_iter  = l_first;
61         const float *v_prev = l_first->prev->v->co;
62         const float *v_curr = l_first->v->co;
63
64         zero_v3(n);
65
66         /* Newell's Method */
67         do {
68                 add_newell_cross_v3_v3v3(n, v_prev, v_curr);
69
70                 l_iter = l_iter->next;
71                 v_prev = v_curr;
72                 v_curr = l_iter->v->co;
73
74         } while (l_iter != l_first);
75
76         return normalize_v3(n);
77 }
78
79 /**
80  * \brief COMPUTE POLY NORMAL (BMFace)
81  *
82  * Same as #bm_face_calc_poly_normal
83  * but takes an array of vertex locations.
84  */
85 static float bm_face_calc_poly_normal_vertex_cos(
86         const BMFace *f, float r_no[3],
87         float const (*vertexCos)[3])
88 {
89         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
90         BMLoop *l_iter  = l_first;
91         const float *v_prev = vertexCos[BM_elem_index_get(l_first->prev->v)];
92         const float *v_curr = vertexCos[BM_elem_index_get(l_first->v)];
93
94         zero_v3(r_no);
95
96         /* Newell's Method */
97         do {
98                 add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
99
100                 l_iter = l_iter->next;
101                 v_prev = v_curr;
102                 v_curr = vertexCos[BM_elem_index_get(l_iter->v)];
103         } while (l_iter != l_first);
104
105         return normalize_v3(r_no);
106 }
107
108 /**
109  * \brief COMPUTE POLY CENTER (BMFace)
110  */
111 static void bm_face_calc_poly_center_mean_vertex_cos(
112         const BMFace *f, float r_cent[3],
113         float const (*vertexCos)[3])
114 {
115         const BMLoop *l_first, *l_iter;
116
117         zero_v3(r_cent);
118
119         /* Newell's Method */
120         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
121         do {
122                 add_v3_v3(r_cent, vertexCos[BM_elem_index_get(l_iter->v)]);
123         } while ((l_iter = l_iter->next) != l_first);
124         mul_v3_fl(r_cent, 1.0f / f->len);
125 }
126
127 /**
128  * For tools that insist on using triangles, ideally we would cache this data.
129  *
130  * \param use_fixed_quad: When true, always split quad along (0 -> 2) regardless of concave corners,
131  * (as done in #BM_mesh_calc_tessellation).
132  * \param r_loops: Store face loop pointers, (f->len)
133  * \param r_index: Store triangle triples, indices into \a r_loops,  `((f->len - 2) * 3)`
134  */
135 void BM_face_calc_tessellation(
136         const BMFace *f, const bool use_fixed_quad,
137         BMLoop **r_loops, uint (*r_index)[3])
138 {
139         BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
140         BMLoop *l_iter;
141
142         if (f->len == 3) {
143                 *r_loops++ = (l_iter = l_first);
144                 *r_loops++ = (l_iter = l_iter->next);
145                 *r_loops++ = (         l_iter->next);
146
147                 r_index[0][0] = 0;
148                 r_index[0][1] = 1;
149                 r_index[0][2] = 2;
150         }
151         else if (f->len == 4 && use_fixed_quad) {
152                 *r_loops++ = (l_iter = l_first);
153                 *r_loops++ = (l_iter = l_iter->next);
154                 *r_loops++ = (l_iter = l_iter->next);
155                 *r_loops++ = (         l_iter->next);
156
157                 r_index[0][0] = 0;
158                 r_index[0][1] = 1;
159                 r_index[0][2] = 2;
160
161                 r_index[1][0] = 0;
162                 r_index[1][1] = 2;
163                 r_index[1][2] = 3;
164         }
165         else {
166                 float axis_mat[3][3];
167                 float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
168                 int j;
169
170                 axis_dominant_v3_to_m3(axis_mat, f->no);
171
172                 j = 0;
173                 l_iter = l_first;
174                 do {
175                         mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
176                         r_loops[j] = l_iter;
177                         j++;
178                 } while ((l_iter = l_iter->next) != l_first);
179
180                 /* complete the loop */
181                 BLI_polyfill_calc(projverts, f->len, -1, r_index);
182         }
183 }
184
185 /**
186  * Return a point inside the face.
187  */
188 void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
189 {
190         const BMLoop *l_tri[3];
191
192         if (f->len == 3) {
193                 const BMLoop *l = BM_FACE_FIRST_LOOP(f);
194                 ARRAY_SET_ITEMS(l_tri, l, l->next, l->prev);
195         }
196         else {
197                 /* tessellation here seems overkill when in many cases this will be the center,
198                  * but without this we can't be sure the point is inside a concave face. */
199                 const int tottri = f->len - 2;
200                 BMLoop **loops = BLI_array_alloca(loops, f->len);
201                 uint (*index)[3] = BLI_array_alloca(index, tottri);
202                 int j;
203                 int j_best = 0;  /* use as fallback when unset */
204                 float area_best  = -1.0f;
205
206                 BM_face_calc_tessellation(f, false, loops, index);
207
208                 for (j = 0; j < tottri; j++) {
209                         const float *p1 = loops[index[j][0]]->v->co;
210                         const float *p2 = loops[index[j][1]]->v->co;
211                         const float *p3 = loops[index[j][2]]->v->co;
212                         const float area = area_squared_tri_v3(p1, p2, p3);
213                         if (area > area_best) {
214                                 j_best = j;
215                                 area_best = area;
216                         }
217                 }
218
219                 ARRAY_SET_ITEMS(l_tri, loops[index[j_best][0]], loops[index[j_best][1]], loops[index[j_best][2]]);
220         }
221
222         mid_v3_v3v3v3(r_co, l_tri[0]->v->co, l_tri[1]->v->co, l_tri[2]->v->co);
223 }
224
225 /**
226  * get the area of the face
227  */
228 float BM_face_calc_area(const BMFace *f)
229 {
230         /* inline 'area_poly_v3' logic, avoid creating a temp array */
231         const BMLoop *l_iter, *l_first;
232         float n[3];
233
234         zero_v3(n);
235         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
236         do {
237                 add_newell_cross_v3_v3v3(n, l_iter->v->co, l_iter->next->v->co);
238         } while ((l_iter = l_iter->next) != l_first);
239         return len_v3(n) * 0.5f;
240 }
241
242 /**
243  * Get the area of the face in world space.
244  */
245 float BM_face_calc_area_with_mat3(const BMFace *f, float mat3[3][3])
246 {
247         /* inline 'area_poly_v3' logic, avoid creating a temp array */
248         const BMLoop *l_iter, *l_first;
249         float co[3];
250         float n[3];
251
252         zero_v3(n);
253         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
254         mul_v3_m3v3(co, mat3, l_iter->v->co);
255         do {
256                 float co_next[3];
257                 mul_v3_m3v3(co_next, mat3, l_iter->next->v->co);
258                 add_newell_cross_v3_v3v3(n, co, co_next);
259                 copy_v3_v3(co, co_next);
260         } while ((l_iter = l_iter->next) != l_first);
261         return len_v3(n) * 0.5f;
262 }
263
264 /**
265  * compute the perimeter of an ngon
266  */
267 float BM_face_calc_perimeter(const BMFace *f)
268 {
269         const BMLoop *l_iter, *l_first;
270         float perimeter = 0.0f;
271
272         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
273         do {
274                 perimeter += len_v3v3(l_iter->v->co, l_iter->next->v->co);
275         } while ((l_iter = l_iter->next) != l_first);
276
277         return perimeter;
278 }
279
280 /**
281  * Calculate the perimeter of a ngon in world space.
282  */
283 float BM_face_calc_perimeter_with_mat3(const BMFace *f, float mat3[3][3])
284 {
285         const BMLoop *l_iter, *l_first;
286         float co[3];
287         float perimeter = 0.0f;
288
289         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
290         mul_v3_m3v3(co, mat3, l_iter->v->co);
291         do {
292                 float co_next[3];
293                 mul_v3_m3v3(co_next, mat3, l_iter->next->v->co);
294                 perimeter += len_v3v3(co, co_next);
295                 copy_v3_v3(co, co_next);
296         } while ((l_iter = l_iter->next) != l_first);
297
298         return perimeter;
299 }
300
301 /**
302  * Utility function to calculate the edge which is most different from the other two.
303  *
304  * \return The first edge index, where the second vertex is ``(index + 1) % 3``.
305  */
306 static int bm_vert_tri_find_unique_edge(BMVert *verts[3])
307 {
308         /* find the most 'unique' loop, (greatest difference to others) */
309 #if 1
310         /* optimized version that avoids sqrt */
311         float difs[3];
312         for (int i_prev = 1, i_curr = 2, i_next = 0;
313              i_next < 3;
314              i_prev = i_curr, i_curr = i_next++)
315         {
316                 const float *co = verts[i_curr]->co;
317                 const float *co_other[2] = {verts[i_prev]->co, verts[i_next]->co};
318                 float proj_dir[3];
319                 mid_v3_v3v3(proj_dir, co_other[0], co_other[1]);
320                 sub_v3_v3(proj_dir, co);
321
322                 float proj_pair[2][3];
323                 project_v3_v3v3(proj_pair[0], co_other[0], proj_dir);
324                 project_v3_v3v3(proj_pair[1], co_other[1], proj_dir);
325                 difs[i_next] = len_squared_v3v3(proj_pair[0], proj_pair[1]);
326         }
327 #else
328         const float lens[3] = {
329                 len_v3v3(verts[0]->co, verts[1]->co),
330                 len_v3v3(verts[1]->co, verts[2]->co),
331                 len_v3v3(verts[2]->co, verts[0]->co),
332         };
333         const float difs[3] = {
334                 fabsf(lens[1] - lens[2]),
335                 fabsf(lens[2] - lens[0]),
336                 fabsf(lens[0] - lens[1]),
337         };
338 #endif
339
340         int order[3] = {0, 1, 2};
341         axis_sort_v3(difs, order);
342
343         return order[0];
344 }
345
346 /**
347  * Calculate a tangent from any 3 vertices.
348  *
349  * The tangent aligns to the most *unique* edge
350  * (the edge most unlike the other two).
351  *
352  * \param r_tangent: Calculated unit length tangent (return value).
353  */
354 void BM_vert_tri_calc_tangent_edge(BMVert *verts[3], float r_tangent[3])
355 {
356         const int index = bm_vert_tri_find_unique_edge(verts);
357
358         sub_v3_v3v3(r_tangent, verts[index]->co, verts[(index + 1) % 3]->co);
359
360         normalize_v3(r_tangent);
361 }
362
363 /**
364  * Calculate a tangent from any 3 vertices,
365  *
366  * The tangent follows the center-line formed by the most unique edges center
367  * and the opposite vertex.
368  *
369  * \param r_tangent: Calculated unit length tangent (return value).
370  */
371 void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3])
372 {
373         const int index = bm_vert_tri_find_unique_edge(verts);
374
375         const float *v_a     = verts[index]->co;
376         const float *v_b     = verts[(index + 1) % 3]->co;
377         const float *v_other = verts[(index + 2) % 3]->co;
378
379         mid_v3_v3v3(r_tangent, v_a, v_b);
380         sub_v3_v3v3(r_tangent, v_other, r_tangent);
381
382         normalize_v3(r_tangent);
383 }
384
385 /**
386  * Compute the tangent of the face, using the longest edge.
387  */
388 void  BM_face_calc_tangent_edge(const BMFace *f, float r_tangent[3])
389 {
390         const BMLoop *l_long  = BM_face_find_longest_loop((BMFace *)f);
391
392         sub_v3_v3v3(r_tangent, l_long->v->co, l_long->next->v->co);
393
394         normalize_v3(r_tangent);
395
396 }
397
398 /**
399  * Compute the tangent of the face, using the two longest disconnected edges.
400  *
401  * \param r_tangent: Calculated unit length tangent (return value).
402  */
403 void  BM_face_calc_tangent_edge_pair(const BMFace *f, float r_tangent[3])
404 {
405         if (f->len == 3) {
406                 BMVert *verts[3];
407
408                 BM_face_as_array_vert_tri((BMFace *)f, verts);
409
410                 BM_vert_tri_calc_tangent_edge_pair(verts, r_tangent);
411         }
412         else if (f->len == 4) {
413                 /* Use longest edge pair */
414                 BMVert *verts[4];
415                 float vec[3], vec_a[3], vec_b[3];
416
417                 BM_face_as_array_vert_quad((BMFace *)f, verts);
418
419                 sub_v3_v3v3(vec_a, verts[3]->co, verts[2]->co);
420                 sub_v3_v3v3(vec_b, verts[0]->co, verts[1]->co);
421                 add_v3_v3v3(r_tangent, vec_a, vec_b);
422
423                 sub_v3_v3v3(vec_a, verts[0]->co, verts[3]->co);
424                 sub_v3_v3v3(vec_b, verts[1]->co, verts[2]->co);
425                 add_v3_v3v3(vec, vec_a, vec_b);
426                 /* use the longest edge length */
427                 if (len_squared_v3(r_tangent) < len_squared_v3(vec)) {
428                         copy_v3_v3(r_tangent, vec);
429                 }
430         }
431         else {
432                 /* For ngons use two longest disconnected edges */
433                 BMLoop *l_long = BM_face_find_longest_loop((BMFace *)f);
434                 BMLoop *l_long_other = NULL;
435
436                 float len_max_sq = 0.0f;
437                 float vec_a[3], vec_b[3];
438
439                 BMLoop *l_iter = l_long->prev->prev;
440                 BMLoop *l_last = l_long->next;
441
442                 do {
443                         const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
444                         if (len_sq >= len_max_sq) {
445                                 l_long_other = l_iter;
446                                 len_max_sq = len_sq;
447                         }
448                 } while ((l_iter = l_iter->prev) != l_last);
449
450                 sub_v3_v3v3(vec_a, l_long->next->v->co, l_long->v->co);
451                 sub_v3_v3v3(vec_b, l_long_other->v->co, l_long_other->next->v->co);
452                 add_v3_v3v3(r_tangent, vec_a, vec_b);
453
454                 /* Edges may not be opposite side of the ngon,
455                  * this could cause problems for ngons with multiple-aligned edges of the same length.
456                  * Fallback to longest edge. */
457                 if (UNLIKELY(normalize_v3(r_tangent) == 0.0f)) {
458                         normalize_v3_v3(r_tangent, vec_a);
459                 }
460         }
461 }
462
463 /**
464  * Compute the tangent of the face, using the edge farthest away from any vertex in the face.
465  *
466  * \param r_tangent: Calculated unit length tangent (return value).
467  */
468 void  BM_face_calc_tangent_edge_diagonal(const BMFace *f, float r_tangent[3])
469 {
470         BMLoop *l_iter, *l_first;
471
472         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
473
474         /* incase of degenerate faces */
475         zero_v3(r_tangent);
476
477         /* warning: O(n^2) loop here, take care! */
478         float dist_max_sq = 0.0f;
479         do {
480                 BMLoop *l_iter_other = l_iter->next;
481                 BMLoop *l_iter_last = l_iter->prev;
482                 do {
483                         BLI_assert(!ELEM(l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co));
484                         float co_other[3], vec[3];
485                         closest_to_line_segment_v3(co_other, l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co);
486                         sub_v3_v3v3(vec, l_iter->v->co, co_other);
487
488                         const float dist_sq = len_squared_v3(vec);
489                         if (dist_sq > dist_max_sq) {
490                                 dist_max_sq = dist_sq;
491                                 copy_v3_v3(r_tangent, vec);
492                         }
493                 } while ((l_iter_other = l_iter_other->next) != l_iter_last);
494         } while ((l_iter = l_iter->next) != l_first);
495
496         normalize_v3(r_tangent);
497 }
498
499 /**
500  * Compute the tangent of the face, using longest distance between vertices on the face.
501  *
502  * \note The logic is almost identical to #BM_face_calc_tangent_edge_diagonal
503  */
504 void  BM_face_calc_tangent_vert_diagonal(const BMFace *f, float r_tangent[3])
505 {
506         BMLoop *l_iter, *l_first;
507
508         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
509
510         /* incase of degenerate faces */
511         zero_v3(r_tangent);
512
513         /* warning: O(n^2) loop here, take care! */
514         float dist_max_sq = 0.0f;
515         do {
516                 BMLoop *l_iter_other = l_iter->next;
517                 do {
518                         float vec[3];
519                         sub_v3_v3v3(vec, l_iter->v->co, l_iter_other->v->co);
520
521                         const float dist_sq = len_squared_v3(vec);
522                         if (dist_sq > dist_max_sq) {
523                                 dist_max_sq = dist_sq;
524                                 copy_v3_v3(r_tangent, vec);
525                         }
526                 } while ((l_iter_other = l_iter_other->next) != l_iter);
527         } while ((l_iter = l_iter->next) != l_first);
528
529         normalize_v3(r_tangent);
530 }
531
532 /**
533  * Compute a meaningful direction along the face (use for gizmo axis).
534  *
535  * \note Callers shouldn't depend on the *exact* method used here.
536  */
537 void BM_face_calc_tangent_auto(const BMFace *f, float r_tangent[3])
538 {
539         if (f->len == 3) {
540                 /* most 'unique' edge of a triangle */
541                 BMVert *verts[3];
542                 BM_face_as_array_vert_tri((BMFace *)f, verts);
543                 BM_vert_tri_calc_tangent_edge(verts, r_tangent);
544         }
545         else if (f->len == 4) {
546                 /* longest edge pair of a quad */
547                 BM_face_calc_tangent_edge_pair((BMFace *)f, r_tangent);
548         }
549         else {
550                 /* longest edge of an ngon */
551                 BM_face_calc_tangent_edge((BMFace *)f, r_tangent);
552         }
553 }
554
555 /**
556  * expands bounds (min/max must be initialized).
557  */
558 void BM_face_calc_bounds_expand(const BMFace *f, float min[3], float max[3])
559 {
560         const BMLoop *l_iter, *l_first;
561         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
562         do {
563                 minmax_v3v3_v3(min, max, l_iter->v->co);
564         } while ((l_iter = l_iter->next) != l_first);
565 }
566
567 /**
568  * computes center of face in 3d.  uses center of bounding box.
569  */
570 void BM_face_calc_center_bounds(const BMFace *f, float r_cent[3])
571 {
572         const BMLoop *l_iter, *l_first;
573         float min[3], max[3];
574
575         INIT_MINMAX(min, max);
576
577         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
578         do {
579                 minmax_v3v3_v3(min, max, l_iter->v->co);
580         } while ((l_iter = l_iter->next) != l_first);
581
582         mid_v3_v3v3(r_cent, min, max);
583 }
584
585 /**
586  * computes the center of a face, using the mean average
587  */
588 void BM_face_calc_center_mean(const BMFace *f, float r_cent[3])
589 {
590         const BMLoop *l_iter, *l_first;
591
592         zero_v3(r_cent);
593
594         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
595         do {
596                 add_v3_v3(r_cent, l_iter->v->co);
597         } while ((l_iter = l_iter->next) != l_first);
598         mul_v3_fl(r_cent, 1.0f / (float) f->len);
599 }
600
601 /**
602  * computes the center of a face, using the mean average
603  * weighted by edge length
604  */
605 void BM_face_calc_center_mean_weighted(const BMFace *f, float r_cent[3])
606 {
607         const BMLoop *l_iter;
608         const BMLoop *l_first;
609         float totw = 0.0f;
610         float w_prev;
611
612         zero_v3(r_cent);
613
614
615         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
616         w_prev = BM_edge_calc_length(l_iter->prev->e);
617         do {
618                 const float w_curr = BM_edge_calc_length(l_iter->e);
619                 const float w = (w_curr + w_prev);
620                 madd_v3_v3fl(r_cent, l_iter->v->co, w);
621                 totw += w;
622                 w_prev = w_curr;
623         } while ((l_iter = l_iter->next) != l_first);
624
625         if (totw != 0.0f)
626                 mul_v3_fl(r_cent, 1.0f / (float) totw);
627 }
628
629 /**
630  * \brief POLY ROTATE PLANE
631  *
632  * Rotates a polygon so that it's
633  * normal is pointing towards the mesh Z axis
634  */
635 void poly_rotate_plane(const float normal[3], float (*verts)[3], const uint nverts)
636 {
637         float mat[3][3];
638         float co[3];
639         uint i;
640
641         co[2] = 0.0f;
642
643         axis_dominant_v3_to_m3(mat, normal);
644         for (i = 0; i < nverts; i++) {
645                 mul_v2_m3v3(co, mat, verts[i]);
646                 copy_v3_v3(verts[i], co);
647         }
648 }
649
650 /**
651  * updates face and vertex normals incident on an edge
652  */
653 void BM_edge_normals_update(BMEdge *e)
654 {
655         BMIter iter;
656         BMFace *f;
657
658         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
659                 BM_face_normal_update(f);
660         }
661
662         BM_vert_normal_update(e->v1);
663         BM_vert_normal_update(e->v2);
664 }
665
666 static void bm_loop_normal_accum(const BMLoop *l, float no[3])
667 {
668         float vec1[3], vec2[3], fac;
669
670         /* Same calculation used in BM_mesh_normals_update */
671         sub_v3_v3v3(vec1, l->v->co, l->prev->v->co);
672         sub_v3_v3v3(vec2, l->next->v->co, l->v->co);
673         normalize_v3(vec1);
674         normalize_v3(vec2);
675
676         fac = saacos(-dot_v3v3(vec1, vec2));
677
678         madd_v3_v3fl(no, l->f->no, fac);
679 }
680
681 bool BM_vert_calc_normal_ex(const BMVert *v, const char hflag, float r_no[3])
682 {
683         int len = 0;
684
685         zero_v3(r_no);
686
687         if (v->e) {
688                 const BMEdge *e = v->e;
689                 do {
690                         if (e->l) {
691                                 const BMLoop *l = e->l;
692                                 do {
693                                         if (l->v == v) {
694                                                 if (BM_elem_flag_test(l->f, hflag)) {
695                                                         bm_loop_normal_accum(l, r_no);
696                                                         len++;
697                                                 }
698                                         }
699                                 } while ((l = l->radial_next) != e->l);
700                         }
701                 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
702         }
703
704         if (len) {
705                 normalize_v3(r_no);
706                 return true;
707         }
708         else {
709                 return false;
710         }
711 }
712
713 bool BM_vert_calc_normal(const BMVert *v, float r_no[3])
714 {
715         int len = 0;
716
717         zero_v3(r_no);
718
719         if (v->e) {
720                 const BMEdge *e = v->e;
721                 do {
722                         if (e->l) {
723                                 const BMLoop *l = e->l;
724                                 do {
725                                         if (l->v == v) {
726                                                 bm_loop_normal_accum(l, r_no);
727                                                 len++;
728                                         }
729                                 } while ((l = l->radial_next) != e->l);
730                         }
731                 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
732         }
733
734         if (len) {
735                 normalize_v3(r_no);
736                 return true;
737         }
738         else {
739                 return false;
740         }
741 }
742
743 void BM_vert_normal_update_all(BMVert *v)
744 {
745         int len = 0;
746
747         zero_v3(v->no);
748
749         if (v->e) {
750                 const BMEdge *e = v->e;
751                 do {
752                         if (e->l) {
753                                 const BMLoop *l = e->l;
754                                 do {
755                                         if (l->v == v) {
756                                                 BM_face_normal_update(l->f);
757                                                 bm_loop_normal_accum(l, v->no);
758                                                 len++;
759                                         }
760                                 } while ((l = l->radial_next) != e->l);
761                         }
762                 } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
763         }
764
765         if (len) {
766                 normalize_v3(v->no);
767         }
768 }
769
770 /**
771  * update a vert normal (but not the faces incident on it)
772  */
773 void BM_vert_normal_update(BMVert *v)
774 {
775         BM_vert_calc_normal(v, v->no);
776 }
777
778 /**
779  * \brief BMESH UPDATE FACE NORMAL
780  *
781  * Updates the stored normal for the
782  * given face. Requires that a buffer
783  * of sufficient length to store projected
784  * coordinates for all of the face's vertices
785  * is passed in as well.
786  */
787
788 float BM_face_calc_normal(const BMFace *f, float r_no[3])
789 {
790         BMLoop *l;
791
792         /* common cases first */
793         switch (f->len) {
794                 case 4:
795                 {
796                         const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
797                         const float *co2 = (l = l->next)->v->co;
798                         const float *co3 = (l = l->next)->v->co;
799                         const float *co4 = (l->next)->v->co;
800
801                         return normal_quad_v3(r_no, co1, co2, co3, co4);
802                 }
803                 case 3:
804                 {
805                         const float *co1 = (l = BM_FACE_FIRST_LOOP(f))->v->co;
806                         const float *co2 = (l = l->next)->v->co;
807                         const float *co3 = (l->next)->v->co;
808
809                         return normal_tri_v3(r_no, co1, co2, co3);
810                 }
811                 default:
812                 {
813                         return bm_face_calc_poly_normal(f, r_no);
814                 }
815         }
816 }
817 void BM_face_normal_update(BMFace *f)
818 {
819         BM_face_calc_normal(f, f->no);
820 }
821
822 /* exact same as 'BM_face_calc_normal' but accepts vertex coords */
823 float BM_face_calc_normal_vcos(
824         const BMesh *bm, const BMFace *f, float r_no[3],
825         float const (*vertexCos)[3])
826 {
827         BMLoop *l;
828
829         /* must have valid index data */
830         BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
831         (void)bm;
832
833         /* common cases first */
834         switch (f->len) {
835                 case 4:
836                 {
837                         const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
838                         const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
839                         const float *co3 = vertexCos[BM_elem_index_get((l = l->next)->v)];
840                         const float *co4 = vertexCos[BM_elem_index_get((l->next)->v)];
841
842                         return normal_quad_v3(r_no, co1, co2, co3, co4);
843                 }
844                 case 3:
845                 {
846                         const float *co1 = vertexCos[BM_elem_index_get((l = BM_FACE_FIRST_LOOP(f))->v)];
847                         const float *co2 = vertexCos[BM_elem_index_get((l = l->next)->v)];
848                         const float *co3 = vertexCos[BM_elem_index_get((l->next)->v)];
849
850                         return normal_tri_v3(r_no, co1, co2, co3);
851                 }
852                 default:
853                 {
854                         return bm_face_calc_poly_normal_vertex_cos(f, r_no, vertexCos);
855                 }
856         }
857 }
858
859 /**
860  * Calculates the face subset normal.
861  */
862 float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3])
863 {
864         const float *v_prev, *v_curr;
865
866         /* Newell's Method */
867         const BMLoop *l_iter = l_first;
868         const BMLoop *l_term = l_last->next;
869
870         zero_v3(r_no);
871
872         v_prev = l_last->v->co;
873         do {
874                 v_curr = l_iter->v->co;
875                 add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
876                 v_prev = v_curr;
877         } while ((l_iter = l_iter->next) != l_term);
878
879         return normalize_v3(r_no);
880 }
881
882 /* exact same as 'BM_face_calc_normal' but accepts vertex coords */
883 void BM_face_calc_center_mean_vcos(
884         const BMesh *bm, const BMFace *f, float r_cent[3],
885         float const (*vertexCos)[3])
886 {
887         /* must have valid index data */
888         BLI_assert((bm->elem_index_dirty & BM_VERT) == 0);
889         (void)bm;
890
891         bm_face_calc_poly_center_mean_vertex_cos(f, r_cent, vertexCos);
892 }
893
894 /**
895  * \brief Face Flip Normal
896  *
897  * Reverses the winding of a face.
898  * \note This updates the calculated normal.
899  */
900 void BM_face_normal_flip_ex(
901         BMesh *bm, BMFace *f,
902         const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
903 {
904         bmesh_kernel_loop_reverse(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
905         negate_v3(f->no);
906 }
907
908 void BM_face_normal_flip(BMesh *bm, BMFace *f)
909 {
910         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
911         BM_face_normal_flip_ex(bm, f, cd_loop_mdisp_offset, true);
912 }
913
914 /**
915  * BM POINT IN FACE
916  *
917  * Projects co onto face f, and returns true if it is inside
918  * the face bounds.
919  *
920  * \note this uses a best-axis projection test,
921  * instead of projecting co directly into f's orientation space,
922  * so there might be accuracy issues.
923  */
924 bool BM_face_point_inside_test(const BMFace *f, const float co[3])
925 {
926         float axis_mat[3][3];
927         float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
928
929         float co_2d[2];
930         BMLoop *l_iter;
931         int i;
932
933         BLI_assert(BM_face_is_normal_valid(f));
934
935         axis_dominant_v3_to_m3(axis_mat, f->no);
936
937         mul_v2_m3v3(co_2d, axis_mat, co);
938
939         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
940                 mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
941         }
942
943         return isect_point_poly_v2(co_2d, projverts, f->len, false);
944 }
945
946 /**
947  * \brief BMESH TRIANGULATE FACE
948  *
949  * Breaks all quads and ngons down to triangles.
950  * It uses polyfill for the ngons splitting, and
951  * the beautify operator when use_beauty is true.
952  *
953  * \param r_faces_new if non-null, must be an array of BMFace pointers,
954  * with a length equal to (f->len - 3). It will be filled with the new
955  * triangles (not including the original triangle).
956  *
957  * \param r_faces_double: When newly created faces are duplicates of existing faces, they're added to this list.
958  * Caller must handle de-duplication.
959  * This is done because its possible _all_ faces exist already,
960  * and in that case we would have to remove all faces including the one passed,
961  * which causes complications adding/removing faces while looking over them.
962  *
963  * \note The number of faces is _almost_ always (f->len - 3),
964  *       However there may be faces that already occupying the
965  *       triangles we would make, so the caller must check \a r_faces_new_tot.
966  *
967  * \note use_tag tags new flags and edges.
968  */
969 void BM_face_triangulate(
970         BMesh *bm, BMFace *f,
971         BMFace **r_faces_new,
972         int     *r_faces_new_tot,
973         BMEdge **r_edges_new,
974         int     *r_edges_new_tot,
975         LinkNode **r_faces_double,
976         const int quad_method,
977         const int ngon_method,
978         const bool use_tag,
979         /* use for ngons only! */
980         MemArena *pf_arena,
981
982         /* use for MOD_TRIANGULATE_NGON_BEAUTY only! */
983         struct Heap *pf_heap)
984 {
985         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
986         const bool use_beauty = (ngon_method == MOD_TRIANGULATE_NGON_BEAUTY);
987         BMLoop *l_first, *l_new;
988         BMFace *f_new;
989         int nf_i = 0;
990         int ne_i = 0;
991
992         BLI_assert(BM_face_is_normal_valid(f));
993
994         /* ensure both are valid or NULL */
995         BLI_assert((r_faces_new == NULL) == (r_faces_new_tot == NULL));
996
997         BLI_assert(f->len > 3);
998
999         {
1000                 BMLoop **loops = BLI_array_alloca(loops, f->len);
1001                 uint (*tris)[3] = BLI_array_alloca(tris, f->len);
1002                 const int totfilltri = f->len - 2;
1003                 const int last_tri = f->len - 3;
1004                 int i;
1005                 /* for mdisps */
1006                 float f_center[3];
1007
1008                 if (f->len == 4) {
1009                         /* even though we're not using BLI_polyfill, fill in 'tris' and 'loops'
1010                          * so we can share code to handle face creation afterwards. */
1011                         BMLoop *l_v1, *l_v2;
1012
1013                         l_first = BM_FACE_FIRST_LOOP(f);
1014
1015                         switch (quad_method) {
1016                                 case MOD_TRIANGULATE_QUAD_FIXED:
1017                                 {
1018                                         l_v1 = l_first;
1019                                         l_v2 = l_first->next->next;
1020                                         break;
1021                                 }
1022                                 case MOD_TRIANGULATE_QUAD_ALTERNATE:
1023                                 {
1024                                         l_v1 = l_first->next;
1025                                         l_v2 = l_first->prev;
1026                                         break;
1027                                 }
1028                                 case MOD_TRIANGULATE_QUAD_SHORTEDGE:
1029                                 case MOD_TRIANGULATE_QUAD_BEAUTY:
1030                                 default:
1031                                 {
1032                                         BMLoop *l_v3, *l_v4;
1033                                         bool split_24;
1034
1035                                         l_v1 = l_first->next;
1036                                         l_v2 = l_first->next->next;
1037                                         l_v3 = l_first->prev;
1038                                         l_v4 = l_first;
1039
1040                                         if (quad_method == MOD_TRIANGULATE_QUAD_SHORTEDGE) {
1041                                                 float d1, d2;
1042                                                 d1 = len_squared_v3v3(l_v4->v->co, l_v2->v->co);
1043                                                 d2 = len_squared_v3v3(l_v1->v->co, l_v3->v->co);
1044                                                 split_24 = ((d2 - d1) > 0.0f);
1045                                         }
1046                                         else {
1047                                                 /* first check if the quad is concave on either diagonal */
1048                                                 const int flip_flag = is_quad_flip_v3(l_v1->v->co, l_v2->v->co, l_v3->v->co, l_v4->v->co);
1049                                                 if (UNLIKELY(flip_flag & (1 << 0))) {
1050                                                         split_24 = true;
1051                                                 }
1052                                                 else if (UNLIKELY(flip_flag & (1 << 1))) {
1053                                                         split_24 = false;
1054                                                 }
1055                                                 else {
1056                                                         split_24 = (BM_verts_calc_rotate_beauty(l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) > 0.0f);
1057                                                 }
1058                                         }
1059
1060                                         /* named confusingly, l_v1 is in fact the second vertex */
1061                                         if (split_24) {
1062                                                 l_v1 = l_v4;
1063                                                 //l_v2 = l_v2;
1064                                         }
1065                                         else {
1066                                                 //l_v1 = l_v1;
1067                                                 l_v2 = l_v3;
1068                                         }
1069                                         break;
1070                                 }
1071                         }
1072
1073                         loops[0] = l_v1;
1074                         loops[1] = l_v1->next;
1075                         loops[2] = l_v2;
1076                         loops[3] = l_v2->next;
1077
1078                         ARRAY_SET_ITEMS(tris[0], 0, 1, 2);
1079                         ARRAY_SET_ITEMS(tris[1], 0, 2, 3);
1080                 }
1081                 else {
1082                         BMLoop *l_iter;
1083                         float axis_mat[3][3];
1084                         float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
1085
1086                         axis_dominant_v3_to_m3_negate(axis_mat, f->no);
1087
1088                         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) {
1089                                 loops[i] = l_iter;
1090                                 mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co);
1091                         }
1092
1093                         BLI_polyfill_calc_arena(projverts, f->len, 1, tris,
1094                                                 pf_arena);
1095
1096                         if (use_beauty) {
1097                                 BLI_polyfill_beautify(
1098                                         projverts, f->len, tris,
1099                                         pf_arena, pf_heap);
1100                         }
1101
1102                         BLI_memarena_clear(pf_arena);
1103                 }
1104
1105                 if (cd_loop_mdisp_offset != -1) {
1106                         BM_face_calc_center_mean(f, f_center);
1107                 }
1108
1109                 /* loop over calculated triangles and create new geometry */
1110                 for (i = 0; i < totfilltri; i++) {
1111                         BMLoop *l_tri[3] = {
1112                             loops[tris[i][0]],
1113                             loops[tris[i][1]],
1114                             loops[tris[i][2]]};
1115
1116                         BMVert *v_tri[3] = {
1117                             l_tri[0]->v,
1118                             l_tri[1]->v,
1119                             l_tri[2]->v};
1120
1121                         f_new = BM_face_create_verts(bm, v_tri, 3, f, BM_CREATE_NOP, true);
1122                         l_new = BM_FACE_FIRST_LOOP(f_new);
1123
1124                         BLI_assert(v_tri[0] == l_new->v);
1125
1126                         /* check for duplicate */
1127                         if (l_new->radial_next != l_new) {
1128                                 BMLoop *l_iter = l_new->radial_next;
1129                                 do {
1130                                         if (UNLIKELY((l_iter->f->len == 3) && (l_new->prev->v == l_iter->prev->v))) {
1131                                                 /* Check the last tri because we swap last f_new with f at the end... */
1132                                                 BLI_linklist_prepend(r_faces_double, (i != last_tri) ? f_new : f);
1133                                                 break;
1134                                         }
1135                                 } while ((l_iter = l_iter->radial_next) != l_new);
1136                         }
1137
1138                         /* copy CD data */
1139                         BM_elem_attrs_copy(bm, bm, l_tri[0], l_new);
1140                         BM_elem_attrs_copy(bm, bm, l_tri[1], l_new->next);
1141                         BM_elem_attrs_copy(bm, bm, l_tri[2], l_new->prev);
1142
1143                         /* add all but the last face which is swapped and removed (below) */
1144                         if (i != last_tri) {
1145                                 if (use_tag) {
1146                                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
1147                                 }
1148                                 if (r_faces_new) {
1149                                         r_faces_new[nf_i++] = f_new;
1150                                 }
1151                         }
1152
1153                         if (use_tag || r_edges_new) {
1154                                 /* new faces loops */
1155                                 BMLoop *l_iter;
1156
1157                                 l_iter = l_first = l_new;
1158                                 do {
1159                                         BMEdge *e = l_iter->e;
1160                                         /* confusing! if its not a boundary now, we know it will be later
1161                                          * since this will be an edge of one of the new faces which we're in the middle of creating */
1162                                         bool is_new_edge = (l_iter == l_iter->radial_next);
1163
1164                                         if (is_new_edge) {
1165                                                 if (use_tag) {
1166                                                         BM_elem_flag_enable(e, BM_ELEM_TAG);
1167                                                 }
1168                                                 if (r_edges_new) {
1169                                                         r_edges_new[ne_i++] = e;
1170                                                 }
1171                                         }
1172                                         /* note, never disable tag's */
1173                                 } while ((l_iter = l_iter->next) != l_first);
1174                         }
1175
1176                         if (cd_loop_mdisp_offset != -1) {
1177                                 float f_new_center[3];
1178                                 BM_face_calc_center_mean(f_new, f_new_center);
1179                                 BM_face_interp_multires_ex(bm, f_new, f, f_new_center, f_center, cd_loop_mdisp_offset);
1180                         }
1181                 }
1182
1183                 {
1184                         /* we can't delete the real face, because some of the callers expect it to remain valid.
1185                          * so swap data and delete the last created tri */
1186                         bmesh_face_swap_data(f, f_new);
1187                         BM_face_kill(bm, f_new);
1188                 }
1189         }
1190         bm->elem_index_dirty |= BM_FACE;
1191
1192         if (r_faces_new_tot) {
1193                 *r_faces_new_tot = nf_i;
1194         }
1195
1196         if (r_edges_new_tot) {
1197                 *r_edges_new_tot = ne_i;
1198         }
1199 }
1200
1201 /**
1202  * each pair of loops defines a new edge, a split.  this function goes
1203  * through and sets pairs that are geometrically invalid to null.  a
1204  * split is invalid, if it forms a concave angle or it intersects other
1205  * edges in the face, or it intersects another split.  in the case of
1206  * intersecting splits, only the first of the set of intersecting
1207  * splits survives
1208  */
1209 void BM_face_splits_check_legal(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len)
1210 {
1211         float out[2] = {-FLT_MAX, -FLT_MAX};
1212         float center[2] = {0.0f, 0.0f};
1213         float axis_mat[3][3];
1214         float (*projverts)[2] = BLI_array_alloca(projverts, f->len);
1215         const float *(*edgeverts)[2] = BLI_array_alloca(edgeverts, len);
1216         BMLoop *l;
1217         int i, i_prev, j;
1218
1219         BLI_assert(BM_face_is_normal_valid(f));
1220
1221         axis_dominant_v3_to_m3(axis_mat, f->no);
1222
1223         for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1224                 mul_v2_m3v3(projverts[i], axis_mat, l->v->co);
1225                 add_v2_v2(center, projverts[i]);
1226         }
1227
1228         /* first test for completely convex face */
1229         if (is_poly_convex_v2(projverts, f->len)) {
1230                 return;
1231         }
1232
1233         mul_v2_fl(center, 1.0f / f->len);
1234
1235         for (i = 0, l = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l = l->next) {
1236                 BM_elem_index_set(l, i);  /* set_dirty */
1237
1238                 /* center the projection for maximum accuracy */
1239                 sub_v2_v2(projverts[i], center);
1240
1241                 out[0] = max_ff(out[0], projverts[i][0]);
1242                 out[1] = max_ff(out[1], projverts[i][1]);
1243         }
1244         bm->elem_index_dirty |= BM_LOOP;
1245
1246         /* ensure we are well outside the face bounds (value is arbitrary) */
1247         add_v2_fl(out, 1.0f);
1248
1249         for (i = 0; i < len; i++) {
1250                 edgeverts[i][0] = projverts[BM_elem_index_get(loops[i][0])];
1251                 edgeverts[i][1] = projverts[BM_elem_index_get(loops[i][1])];
1252         }
1253
1254         /* do convexity test */
1255         for (i = 0; i < len; i++) {
1256                 float mid[2];
1257                 mid_v2_v2v2(mid, edgeverts[i][0], edgeverts[i][1]);
1258
1259                 int isect = 0;
1260                 int j_prev;
1261                 for (j = 0, j_prev = f->len - 1; j < f->len; j_prev = j++) {
1262                         const float *f_edge[2] = {projverts[j_prev], projverts[j]};
1263                         if (isect_seg_seg_v2(UNPACK2(f_edge), mid, out) == ISECT_LINE_LINE_CROSS) {
1264                                 isect++;
1265                         }
1266                 }
1267
1268                 if (isect % 2 == 0) {
1269                         loops[i][0] = NULL;
1270                 }
1271         }
1272
1273 #define EDGE_SHARE_VERT(e1, e2) \
1274         ((ELEM((e1)[0], (e2)[0], (e2)[1])) || \
1275          (ELEM((e1)[1], (e2)[0], (e2)[1])))
1276
1277         /* do line crossing tests */
1278         for (i = 0, i_prev = f->len - 1; i < f->len; i_prev = i++) {
1279                 const float *f_edge[2] = {projverts[i_prev], projverts[i]};
1280                 for (j = 0; j < len; j++) {
1281                         if ((loops[j][0] != NULL) &&
1282                             !EDGE_SHARE_VERT(f_edge, edgeverts[j]))
1283                         {
1284                                 if (isect_seg_seg_v2(UNPACK2(f_edge), UNPACK2(edgeverts[j])) == ISECT_LINE_LINE_CROSS) {
1285                                         loops[j][0] = NULL;
1286                                 }
1287                         }
1288                 }
1289         }
1290
1291         /* self intersect tests */
1292         for (i = 0; i < len; i++) {
1293                 if (loops[i][0]) {
1294                         for (j = i + 1; j < len; j++) {
1295                                 if ((loops[j][0] != NULL) &&
1296                                     !EDGE_SHARE_VERT(edgeverts[i], edgeverts[j]))
1297                                 {
1298                                         if (isect_seg_seg_v2(UNPACK2(edgeverts[i]), UNPACK2(edgeverts[j])) == ISECT_LINE_LINE_CROSS) {
1299                                                 loops[i][0] = NULL;
1300                                                 break;
1301                                         }
1302                                 }
1303                         }
1304                 }
1305         }
1306
1307 #undef EDGE_SHARE_VERT
1308 }
1309
1310 /**
1311  * This simply checks that the verts don't connect faces which would have more optimal splits.
1312  * but _not_ check for correctness.
1313  */
1314 void BM_face_splits_check_optimal(BMFace *f, BMLoop *(*loops)[2], int len)
1315 {
1316         int i;
1317
1318         for (i = 0; i < len; i++) {
1319                 BMLoop *l_a_dummy, *l_b_dummy;
1320                 if (f != BM_vert_pair_share_face_by_angle(loops[i][0]->v, loops[i][1]->v, &l_a_dummy, &l_b_dummy, false)) {
1321                         loops[i][0] = NULL;
1322                 }
1323         }
1324 }
1325
1326 /**
1327  * Small utility functions for fast access
1328  *
1329  * faster alternative to:
1330  * BM_iter_as_array(bm, BM_VERTS_OF_FACE, f, (void **)v, 3);
1331  */
1332 void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[3])
1333 {
1334         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1335
1336         BLI_assert(f->len == 3);
1337
1338         r_verts[0] = l->v; l = l->next;
1339         r_verts[1] = l->v; l = l->next;
1340         r_verts[2] = l->v;
1341 }
1342
1343 /**
1344  * faster alternative to:
1345  * BM_iter_as_array(bm, BM_VERTS_OF_FACE, f, (void **)v, 4);
1346  */
1347 void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4])
1348 {
1349         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1350
1351         BLI_assert(f->len == 4);
1352
1353         r_verts[0] = l->v; l = l->next;
1354         r_verts[1] = l->v; l = l->next;
1355         r_verts[2] = l->v; l = l->next;
1356         r_verts[3] = l->v;
1357 }
1358
1359
1360 /**
1361  * Small utility functions for fast access
1362  *
1363  * faster alternative to:
1364  * BM_iter_as_array(bm, BM_LOOPS_OF_FACE, f, (void **)l, 3);
1365  */
1366 void BM_face_as_array_loop_tri(BMFace *f, BMLoop *r_loops[3])
1367 {
1368         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1369
1370         BLI_assert(f->len == 3);
1371
1372         r_loops[0] = l; l = l->next;
1373         r_loops[1] = l; l = l->next;
1374         r_loops[2] = l;
1375 }
1376
1377 /**
1378  * faster alternative to:
1379  * BM_iter_as_array(bm, BM_LOOPS_OF_FACE, f, (void **)l, 4);
1380  */
1381 void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4])
1382 {
1383         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1384
1385         BLI_assert(f->len == 4);
1386
1387         r_loops[0] = l; l = l->next;
1388         r_loops[1] = l; l = l->next;
1389         r_loops[2] = l; l = l->next;
1390         r_loops[3] = l;
1391 }
1392
1393
1394 /**
1395  * \brief BM_mesh_calc_tessellation get the looptris and its number from a certain bmesh
1396  * \param looptris
1397  *
1398  * \note \a looptris Must be pre-allocated to at least the size of given by: poly_to_tri_count
1399  */
1400 void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot)
1401 {
1402         /* use this to avoid locking pthread for _every_ polygon
1403          * and calling the fill function */
1404 #define USE_TESSFACE_SPEEDUP
1405
1406         /* this assumes all faces can be scan-filled, which isn't always true,
1407          * worst case we over alloc a little which is acceptable */
1408 #ifndef NDEBUG
1409         const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
1410 #endif
1411
1412         BMIter iter;
1413         BMFace *efa;
1414         int i = 0;
1415
1416         MemArena *arena = NULL;
1417
1418         BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
1419                 /* don't consider two-edged faces */
1420                 if (UNLIKELY(efa->len < 3)) {
1421                         /* do nothing */
1422                 }
1423
1424 #ifdef USE_TESSFACE_SPEEDUP
1425
1426                 /* no need to ensure the loop order, we know its ok */
1427
1428                 else if (efa->len == 3) {
1429 #if 0
1430                         int j;
1431                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) {
1432                                 looptris[i][j] = l;
1433                         }
1434                         i += 1;
1435 #else
1436                         /* more cryptic but faster */
1437                         BMLoop *l;
1438                         BMLoop **l_ptr = looptris[i++];
1439                         l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
1440                         l_ptr[1] = l = l->next;
1441                         l_ptr[2] = l->next;
1442 #endif
1443                 }
1444                 else if (efa->len == 4) {
1445 #if 0
1446                         BMLoop *ltmp[4];
1447                         int j;
1448                         BLI_array_grow_items(looptris, 2);
1449                         BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) {
1450                                 ltmp[j] = l;
1451                         }
1452
1453                         looptris[i][0] = ltmp[0];
1454                         looptris[i][1] = ltmp[1];
1455                         looptris[i][2] = ltmp[2];
1456                         i += 1;
1457
1458                         looptris[i][0] = ltmp[0];
1459                         looptris[i][1] = ltmp[2];
1460                         looptris[i][2] = ltmp[3];
1461                         i += 1;
1462 #else
1463                         /* more cryptic but faster */
1464                         BMLoop *l;
1465                         BMLoop **l_ptr_a = looptris[i++];
1466                         BMLoop **l_ptr_b = looptris[i++];
1467                         (l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa));
1468                         (l_ptr_a[1]              = l = l->next);
1469                         (l_ptr_a[2] = l_ptr_b[1] = l = l->next);
1470                         (             l_ptr_b[2] = l->next);
1471 #endif
1472
1473                         if (UNLIKELY(is_quad_flip_v3_first_third_fast(
1474                                              l_ptr_a[0]->v->co,
1475                                              l_ptr_a[1]->v->co,
1476                                              l_ptr_a[2]->v->co,
1477                                              l_ptr_b[2]->v->co)))
1478                         {
1479                                 /* flip out of degenerate 0-2 state. */
1480                                 l_ptr_a[2] = l_ptr_b[2];
1481                                 l_ptr_b[0] = l_ptr_a[1];
1482                         }
1483                 }
1484
1485 #endif /* USE_TESSFACE_SPEEDUP */
1486
1487                 else {
1488                         int j;
1489
1490                         BMLoop *l_iter;
1491                         BMLoop *l_first;
1492                         BMLoop **l_arr;
1493
1494                         float axis_mat[3][3];
1495                         float (*projverts)[2];
1496                         uint (*tris)[3];
1497
1498                         const int totfilltri = efa->len - 2;
1499
1500                         if (UNLIKELY(arena == NULL)) {
1501                                 arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1502                         }
1503
1504                         tris = BLI_memarena_alloc(arena, sizeof(*tris) * totfilltri);
1505                         l_arr = BLI_memarena_alloc(arena, sizeof(*l_arr) * efa->len);
1506                         projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * efa->len);
1507
1508                         axis_dominant_v3_to_m3_negate(axis_mat, efa->no);
1509
1510                         j = 0;
1511                         l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
1512                         do {
1513                                 l_arr[j] = l_iter;
1514                                 mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
1515                                 j++;
1516                         } while ((l_iter = l_iter->next) != l_first);
1517
1518                         BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, arena);
1519
1520                         for (j = 0; j < totfilltri; j++) {
1521                                 BMLoop **l_ptr = looptris[i++];
1522                                 uint *tri = tris[j];
1523
1524                                 l_ptr[0] = l_arr[tri[0]];
1525                                 l_ptr[1] = l_arr[tri[1]];
1526                                 l_ptr[2] = l_arr[tri[2]];
1527                         }
1528
1529                         BLI_memarena_clear(arena);
1530                 }
1531         }
1532
1533         if (arena) {
1534                 BLI_memarena_free(arena);
1535                 arena = NULL;
1536         }
1537
1538         *r_looptris_tot = i;
1539
1540         BLI_assert(i <= looptris_tot);
1541
1542 #undef USE_TESSFACE_SPEEDUP
1543
1544 }
1545
1546
1547 /**
1548  * A version of #BM_mesh_calc_tessellation that avoids degenerate triangles.
1549  */
1550 void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot)
1551 {
1552         /* this assumes all faces can be scan-filled, which isn't always true,
1553          * worst case we over alloc a little which is acceptable */
1554 #ifndef NDEBUG
1555         const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop);
1556 #endif
1557
1558         BMIter iter;
1559         BMFace *efa;
1560         int i = 0;
1561
1562         MemArena *pf_arena = NULL;
1563
1564         /* use_beauty */
1565         Heap *pf_heap = NULL;
1566
1567         BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) {
1568                 /* don't consider two-edged faces */
1569                 if (UNLIKELY(efa->len < 3)) {
1570                         /* do nothing */
1571                 }
1572                 else if (efa->len == 3) {
1573                         BMLoop *l;
1574                         BMLoop **l_ptr = looptris[i++];
1575                         l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa);
1576                         l_ptr[1] = l = l->next;
1577                         l_ptr[2] = l->next;
1578                 }
1579                 else if (efa->len == 4) {
1580                         BMLoop *l_v1 = BM_FACE_FIRST_LOOP(efa);
1581                         BMLoop *l_v2 = l_v1->next;
1582                         BMLoop *l_v3 = l_v2->next;
1583                         BMLoop *l_v4 = l_v1->prev;
1584
1585                         /* #BM_verts_calc_rotate_beauty performs excessive checks we don't need!
1586                          * It's meant for rotating edges, it also calculates a new normal.
1587                          *
1588                          * Use #BLI_polyfill_beautify_quad_rotate_calc since we have the normal.
1589                          */
1590 #if 0
1591                         const bool split_13 = (BM_verts_calc_rotate_beauty(
1592                                 l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) < 0.0f);
1593 #else
1594                         float axis_mat[3][3], v_quad[4][2];
1595                         axis_dominant_v3_to_m3(axis_mat, efa->no);
1596                         mul_v2_m3v3(v_quad[0], axis_mat, l_v1->v->co);
1597                         mul_v2_m3v3(v_quad[1], axis_mat, l_v2->v->co);
1598                         mul_v2_m3v3(v_quad[2], axis_mat, l_v3->v->co);
1599                         mul_v2_m3v3(v_quad[3], axis_mat, l_v4->v->co);
1600
1601                         const bool split_13 = BLI_polyfill_beautify_quad_rotate_calc(
1602                                 v_quad[0], v_quad[1], v_quad[2], v_quad[3]) < 0.0f;
1603 #endif
1604
1605                         BMLoop **l_ptr_a = looptris[i++];
1606                         BMLoop **l_ptr_b = looptris[i++];
1607                         if (split_13) {
1608                                 l_ptr_a[0] = l_v1;
1609                                 l_ptr_a[1] = l_v2;
1610                                 l_ptr_a[2] = l_v3;
1611
1612                                 l_ptr_b[0] = l_v1;
1613                                 l_ptr_b[1] = l_v3;
1614                                 l_ptr_b[2] = l_v4;
1615                         }
1616                         else {
1617                                 l_ptr_a[0] = l_v1;
1618                                 l_ptr_a[1] = l_v2;
1619                                 l_ptr_a[2] = l_v4;
1620
1621                                 l_ptr_b[0] = l_v2;
1622                                 l_ptr_b[1] = l_v3;
1623                                 l_ptr_b[2] = l_v4;
1624                         }
1625                 }
1626                 else {
1627                         int j;
1628
1629                         BMLoop *l_iter;
1630                         BMLoop *l_first;
1631                         BMLoop **l_arr;
1632
1633                         float axis_mat[3][3];
1634                         float (*projverts)[2];
1635                         unsigned int (*tris)[3];
1636
1637                         const int totfilltri = efa->len - 2;
1638
1639                         if (UNLIKELY(pf_arena == NULL)) {
1640                                 pf_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
1641                                 pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
1642                         }
1643
1644                         tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * totfilltri);
1645                         l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len);
1646                         projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len);
1647
1648                         axis_dominant_v3_to_m3_negate(axis_mat, efa->no);
1649
1650                         j = 0;
1651                         l_iter = l_first = BM_FACE_FIRST_LOOP(efa);
1652                         do {
1653                                 l_arr[j] = l_iter;
1654                                 mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co);
1655                                 j++;
1656                         } while ((l_iter = l_iter->next) != l_first);
1657
1658                         BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, pf_arena);
1659
1660                         BLI_polyfill_beautify(projverts, efa->len, tris, pf_arena, pf_heap);
1661
1662                         for (j = 0; j < totfilltri; j++) {
1663                                 BMLoop **l_ptr = looptris[i++];
1664                                 unsigned int *tri = tris[j];
1665
1666                                 l_ptr[0] = l_arr[tri[0]];
1667                                 l_ptr[1] = l_arr[tri[1]];
1668                                 l_ptr[2] = l_arr[tri[2]];
1669                         }
1670
1671                         BLI_memarena_clear(pf_arena);
1672                 }
1673         }
1674
1675         if (pf_arena) {
1676                 BLI_memarena_free(pf_arena);
1677
1678                 BLI_heap_free(pf_heap, NULL);
1679         }
1680
1681         *r_looptris_tot = i;
1682
1683         BLI_assert(i <= looptris_tot);
1684
1685 }