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