c28d748b2eb04d0e77eb97a74959d68f6fff3d2d
[blender.git] / source / blender / bmesh / intern / bmesh_mods.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file
18  * \ingroup bmesh
19  *
20  * This file contains functions for locally modifying
21  * the topology of existing mesh data. (split, join, flip etc).
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "BLI_math.h"
27 #include "BLI_array.h"
28
29 #include "BKE_customdata.h"
30
31 #include "bmesh.h"
32 #include "intern/bmesh_private.h"
33
34 /**
35  * \brief Dissolve Vert
36  *
37  * Turns the face region surrounding a manifold vertex into a single polygon.
38  *
39  * \par Example:
40  * <pre>
41  *              +---------+             +---------+
42  *              |  \   /  |             |         |
43  *     Before:  |    v    |      After: |         |
44  *              |  /   \  |             |         |
45  *              +---------+             +---------+
46  * </pre>
47  *
48  * This function can also collapse edges too
49  * in cases when it cant merge into faces.
50  *
51  * \par Example:
52  * <pre>
53  *     Before:  +----v----+      After: +---------+
54  * </pre>
55  *
56  * \note dissolves vert, in more situations then BM_disk_dissolve
57  * (e.g. if the vert is part of a wire edge, etc).
58  */
59 bool BM_vert_dissolve(BMesh *bm, BMVert *v)
60 {
61   /* logic for 3 or more is identical */
62   const int len = BM_vert_edge_count_at_most(v, 3);
63
64   if (len == 1) {
65     BM_vert_kill(bm, v); /* will kill edges too */
66     return true;
67   }
68   else if (!BM_vert_is_manifold(v)) {
69     if (!v->e) {
70       BM_vert_kill(bm, v);
71       return true;
72     }
73     else if (!v->e->l) {
74       if (len == 2) {
75         return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL);
76       }
77       else {
78         /* used to kill the vertex here, but it may be connected to faces.
79          * so better do nothing */
80         return false;
81       }
82     }
83     else {
84       return false;
85     }
86   }
87   else if (len == 2 && BM_vert_face_count_is_equal(v, 1)) {
88     /* boundary vertex on a face */
89     return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL);
90   }
91   else {
92     return BM_disk_dissolve(bm, v);
93   }
94 }
95
96 /**
97  * dissolves all faces around a vert, and removes it.
98  */
99 bool BM_disk_dissolve(BMesh *bm, BMVert *v)
100 {
101   BMEdge *e, *keepedge = NULL, *baseedge = NULL;
102   int len = 0;
103
104   if (!BM_vert_is_manifold(v)) {
105     return false;
106   }
107
108   if (v->e) {
109     /* v->e we keep, what else */
110     e = v->e;
111     do {
112       e = bmesh_disk_edge_next(e, v);
113       if (!(BM_edge_share_face_check(e, v->e))) {
114         keepedge = e;
115         baseedge = v->e;
116         break;
117       }
118       len++;
119     } while (e != v->e);
120   }
121
122   /* this code for handling 2 and 3-valence verts
123    * may be totally bad */
124   if (keepedge == NULL && len == 3) {
125 #if 0
126     /* handle specific case for three-valence.  solve it by
127      * increasing valence to four.  this may be hackish. .  */
128     BMLoop *l_a = BM_face_vert_share_loop(e->l->f, v);
129     BMLoop *l_b = (e->l->v == v) ? e->l->next : e->l;
130
131     if (!BM_face_split(bm, e->l->f, l_a, l_b, NULL, NULL, false)) {
132       return false;
133     }
134
135     if (!BM_disk_dissolve(bm, v)) {
136       return false;
137     }
138 #else
139     if (UNLIKELY(!BM_faces_join_pair(bm, e->l, e->l->radial_next, true))) {
140       return false;
141     }
142     else if (UNLIKELY(!BM_vert_collapse_faces(bm, v->e, v, 1.0, true, false, true))) {
143       return false;
144     }
145 #endif
146     return true;
147   }
148   else if (keepedge == NULL && len == 2) {
149     /* collapse the vertex */
150     e = BM_vert_collapse_faces(bm, v->e, v, 1.0, true, true, true);
151
152     if (!e) {
153       return false;
154     }
155
156     /* handle two-valence */
157     if (e->l != e->l->radial_next) {
158       if (!BM_faces_join_pair(bm, e->l, e->l->radial_next, true)) {
159         return false;
160       }
161     }
162
163     return true;
164   }
165
166   if (keepedge) {
167     bool done = false;
168
169     while (!done) {
170       done = true;
171       e = v->e;
172       do {
173         BMFace *f = NULL;
174         if (BM_edge_is_manifold(e) && (e != baseedge) && (e != keepedge)) {
175           f = BM_faces_join_pair(bm, e->l, e->l->radial_next, true);
176           /* return if couldn't join faces in manifold
177            * conditions */
178           /* !disabled for testing why bad things happen */
179           if (!f) {
180             return false;
181           }
182         }
183
184         if (f) {
185           done = false;
186           break;
187         }
188       } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
189     }
190
191     /* collapse the vertex */
192     /* note, the baseedge can be a boundary of manifold, use this as join_faces arg */
193     e = BM_vert_collapse_faces(bm, baseedge, v, 1.0, true, !BM_edge_is_boundary(baseedge), true);
194
195     if (!e) {
196       return false;
197     }
198
199     if (e->l) {
200       /* get remaining two faces */
201       if (e->l != e->l->radial_next) {
202         /* join two remaining faces */
203         if (!BM_faces_join_pair(bm, e->l, e->l->radial_next, true)) {
204           return false;
205         }
206       }
207     }
208   }
209
210   return true;
211 }
212
213 /**
214  * \brief Faces Join Pair
215  *
216  * Joins two adjacent faces together.
217  *
218  * \note This method calls to #BM_faces_join to do its work.
219  * This means connected edges which also share the two faces will be joined.
220  *
221  * If the windings do not match the winding of the new face will follow
222  * \a l_a's winding (i.e. \a l_b will be reversed before the join).
223  *
224  * \return The combined face or NULL on failure.
225  */
226 BMFace *BM_faces_join_pair(BMesh *bm, BMLoop *l_a, BMLoop *l_b, const bool do_del)
227 {
228   BLI_assert((l_a != l_b) && (l_a->e == l_b->e));
229
230   if (l_a->v == l_b->v) {
231     const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
232     bmesh_kernel_loop_reverse(bm, l_b->f, cd_loop_mdisp_offset, true);
233   }
234
235   BMFace *faces[2] = {l_a->f, l_b->f};
236   return BM_faces_join(bm, faces, 2, do_del);
237 }
238
239 /**
240  * \brief Face Split
241  *
242  * Split a face along two vertices. returns the newly made face, and sets
243  * the \a r_l member to a loop in the newly created edge.
244  *
245  * \param bm: The bmesh
246  * \param f: the original face
247  * \param l_a, l_b: Loops of this face, their vertices define
248  * the split edge to be created (must be differ and not can't be adjacent in the face).
249  * \param r_l: pointer which will receive the BMLoop for the split edge in the new face
250  * \param example: Edge used for attributes of splitting edge, if non-NULL
251  * \param no_double: Use an existing edge if found
252  *
253  * \return Pointer to the newly created face representing one side of the split
254  * if the split is successful (and the original original face will be the
255  * other side). NULL if the split fails.
256  */
257 BMFace *BM_face_split(BMesh *bm,
258                       BMFace *f,
259                       BMLoop *l_a,
260                       BMLoop *l_b,
261                       BMLoop **r_l,
262                       BMEdge *example,
263                       const bool no_double)
264 {
265   const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
266   BMFace *f_new, *f_tmp;
267
268   BLI_assert(l_a != l_b);
269   BLI_assert(f == l_a->f && f == l_b->f);
270   BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
271
272   /* could be an assert */
273   if (UNLIKELY(BM_loop_is_adjacent(l_a, l_b)) || UNLIKELY((f != l_a->f || f != l_b->f))) {
274     if (r_l) {
275       *r_l = NULL;
276     }
277     return NULL;
278   }
279
280   /* do we have a multires layer? */
281   if (cd_loop_mdisp_offset != -1) {
282     f_tmp = BM_face_copy(bm, bm, f, false, false);
283   }
284
285 #ifdef USE_BMESH_HOLES
286   f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, r_l, NULL, example, no_double);
287 #else
288   f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, r_l, example, no_double);
289 #endif
290
291   if (f_new) {
292     /* handle multires update */
293     if (cd_loop_mdisp_offset != -1) {
294       float f_dst_center[3];
295       float f_src_center[3];
296
297       BM_face_calc_center_median(f_tmp, f_src_center);
298
299       BM_face_calc_center_median(f, f_dst_center);
300       BM_face_interp_multires_ex(bm, f, f_tmp, f_dst_center, f_src_center, cd_loop_mdisp_offset);
301
302       BM_face_calc_center_median(f_new, f_dst_center);
303       BM_face_interp_multires_ex(
304           bm, f_new, f_tmp, f_dst_center, f_src_center, cd_loop_mdisp_offset);
305
306 #if 0
307       /* BM_face_multires_bounds_smooth doesn't flip displacement correct */
308       BM_face_multires_bounds_smooth(bm, f);
309       BM_face_multires_bounds_smooth(bm, f_new);
310 #endif
311     }
312   }
313
314   if (cd_loop_mdisp_offset != -1) {
315     BM_face_kill(bm, f_tmp);
316   }
317
318   return f_new;
319 }
320
321 /**
322  * \brief Face Split with intermediate points
323  *
324  * Like BM_face_split, but with an edge split by \a n intermediate points with given coordinates.
325  *
326  * \param bm: The bmesh.
327  * \param f: the original face.
328  * \param l_a, l_b: Vertices which define the split edge, must be different.
329  * \param cos: Array of coordinates for intermediate points.
330  * \param n: Length of \a cos (must be > 0).
331  * \param r_l: pointer which will receive the BMLoop.
332  * for the first split edge (from \a l_a) in the new face.
333  * \param example: Edge used for attributes of splitting edge, if non-NULL.
334  *
335  * \return Pointer to the newly created face representing one side of the split
336  * if the split is successful (and the original original face will be the
337  * other side). NULL if the split fails.
338  */
339 BMFace *BM_face_split_n(BMesh *bm,
340                         BMFace *f,
341                         BMLoop *l_a,
342                         BMLoop *l_b,
343                         float cos[][3],
344                         int n,
345                         BMLoop **r_l,
346                         BMEdge *example)
347 {
348   BMFace *f_new, *f_tmp;
349   BMLoop *l_new;
350   BMEdge *e, *e_new;
351   BMVert *v_new;
352   // BMVert *v_a = l_a->v; /* UNUSED */
353   BMVert *v_b = l_b->v;
354   int i, j;
355
356   BLI_assert(l_a != l_b);
357   BLI_assert(f == l_a->f && f == l_b->f);
358   BLI_assert(!((n == 0) && BM_loop_is_adjacent(l_a, l_b)));
359
360   /* could be an assert */
361   if (UNLIKELY((n == 0) && BM_loop_is_adjacent(l_a, l_b)) || UNLIKELY(l_a->f != l_b->f)) {
362     if (r_l) {
363       *r_l = NULL;
364     }
365     return NULL;
366   }
367
368   f_tmp = BM_face_copy(bm, bm, f, true, true);
369
370 #ifdef USE_BMESH_HOLES
371   f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, &l_new, NULL, example, false);
372 #else
373   f_new = bmesh_kernel_split_face_make_edge(bm, f, l_a, l_b, &l_new, example, false);
374 #endif
375   /* bmesh_kernel_split_face_make_edge returns in 'l_new'
376    * a Loop for f_new going from 'v_a' to 'v_b'.
377    * The radial_next is for 'f' and goes from 'v_b' to 'v_a'  */
378
379   if (f_new) {
380     e = l_new->e;
381     for (i = 0; i < n; i++) {
382       v_new = bmesh_kernel_split_edge_make_vert(bm, v_b, e, &e_new);
383       BLI_assert(v_new != NULL);
384       /* bmesh_kernel_split_edge_make_vert returns in 'e_new'
385        * the edge going from 'v_new' to 'v_b'. */
386       copy_v3_v3(v_new->co, cos[i]);
387
388       /* interpolate the loop data for the loops with (v == v_new), using orig face */
389       for (j = 0; j < 2; j++) {
390         BMEdge *e_iter = (j == 0) ? e : e_new;
391         BMLoop *l_iter = e_iter->l;
392         do {
393           if (l_iter->v == v_new) {
394             /* this interpolates both loop and vertex data */
395             BM_loop_interp_from_face(bm, l_iter, f_tmp, true, true);
396           }
397         } while ((l_iter = l_iter->radial_next) != e_iter->l);
398       }
399       e = e_new;
400     }
401   }
402
403   BM_face_verts_kill(bm, f_tmp);
404
405   if (r_l) {
406     *r_l = l_new;
407   }
408
409   return f_new;
410 }
411
412 /**
413  * \brief Vert Collapse Faces
414  *
415  * Collapses vertex \a v_kill that has only two manifold edges
416  * onto a vertex it shares an edge with.
417  * \a fac defines the amount of interpolation for Custom Data.
418  *
419  * \note that this is not a general edge collapse function.
420  *
421  * \note this function is very close to #BM_vert_collapse_edge,
422  * both collapse a vertex and return a new edge.
423  * Except this takes a factor and merges custom data.
424  *
425  * \param bm: The bmesh
426  * \param e_kill: The edge to collapse
427  * \param v_kill: The vertex  to collapse into the edge
428  * \param fac: The factor along the edge
429  * \param join_faces: When true the faces around the vertex will be joined
430  * otherwise collapse the vertex by merging the 2 edges this vert touches into one.
431  * \param kill_degenerate_faces: Removes faces with less than 3 verts after collapsing.
432  *
433  * \returns The New Edge
434  */
435 BMEdge *BM_vert_collapse_faces(BMesh *bm,
436                                BMEdge *e_kill,
437                                BMVert *v_kill,
438                                float fac,
439                                const bool do_del,
440                                const bool join_faces,
441                                const bool kill_degenerate_faces)
442 {
443   BMEdge *e_new = NULL;
444   BMVert *tv = BM_edge_other_vert(e_kill, v_kill);
445
446   BMEdge *e2;
447   BMVert *tv2;
448
449   /* Only intended to be called for 2-valence vertices */
450   BLI_assert(bmesh_disk_count(v_kill) <= 2);
451
452   /* first modify the face loop data */
453
454   if (e_kill->l) {
455     BMLoop *l_iter;
456     const float w[2] = {1.0f - fac, fac};
457
458     l_iter = e_kill->l;
459     do {
460       if (l_iter->v == tv && l_iter->next->v == v_kill) {
461         const void *src[2];
462         BMLoop *tvloop = l_iter;
463         BMLoop *kvloop = l_iter->next;
464
465         src[0] = kvloop->head.data;
466         src[1] = tvloop->head.data;
467         CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, kvloop->head.data);
468       }
469     } while ((l_iter = l_iter->radial_next) != e_kill->l);
470   }
471
472   /* now interpolate the vertex data */
473   BM_data_interp_from_verts(bm, v_kill, tv, v_kill, fac);
474
475   e2 = bmesh_disk_edge_next(e_kill, v_kill);
476   tv2 = BM_edge_other_vert(e2, v_kill);
477
478   if (join_faces) {
479     BMIter fiter;
480     BMFace **faces = NULL;
481     BMFace *f;
482     BLI_array_staticdeclare(faces, BM_DEFAULT_ITER_STACK_SIZE);
483
484     BM_ITER_ELEM (f, &fiter, v_kill, BM_FACES_OF_VERT) {
485       BLI_array_append(faces, f);
486     }
487
488     if (BLI_array_len(faces) >= 2) {
489       BMFace *f2 = BM_faces_join(bm, faces, BLI_array_len(faces), true);
490       if (f2) {
491         BMLoop *l_a, *l_b;
492
493         if ((l_a = BM_face_vert_share_loop(f2, tv)) && (l_b = BM_face_vert_share_loop(f2, tv2))) {
494           BMLoop *l_new;
495
496           if (BM_face_split(bm, f2, l_a, l_b, &l_new, NULL, false)) {
497             e_new = l_new->e;
498           }
499         }
500       }
501     }
502
503     BLI_assert(BLI_array_len(faces) < 8);
504
505     BLI_array_free(faces);
506   }
507   else {
508     /* single face or no faces */
509     /* same as BM_vert_collapse_edge() however we already
510      * have vars to perform this operation so don't call. */
511     e_new = bmesh_kernel_join_edge_kill_vert(
512         bm, e_kill, v_kill, do_del, true, kill_degenerate_faces);
513     /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
514   }
515
516   return e_new;
517 }
518
519 /**
520  * \brief Vert Collapse Faces
521  *
522  * Collapses a vertex onto another vertex it shares an edge with.
523  *
524  * \return The New Edge
525  */
526 BMEdge *BM_vert_collapse_edge(
527     BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces)
528 {
529   /* nice example implementation but we want loops to have their customdata
530    * accounted for */
531 #if 0
532   BMEdge *e_new = NULL;
533
534   /* Collapse between 2 edges */
535
536   /* in this case we want to keep all faces and not join them,
537    * rather just get rid of the vertex - see bug [#28645] */
538   BMVert *tv = BM_edge_other_vert(e_kill, v_kill);
539   if (tv) {
540     BMEdge *e2 = bmesh_disk_edge_next(e_kill, v_kill);
541     if (e2) {
542       BMVert *tv2 = BM_edge_other_vert(e2, v_kill);
543       if (tv2) {
544         /* only action, other calls here only get the edge to return */
545         e_new = bmesh_kernel_join_edge_kill_vert(
546             bm, e_kill, v_kill, do_del, true, kill_degenerate_faces);
547       }
548     }
549   }
550
551   return e_new;
552 #else
553   /* with these args faces are never joined, same as above
554    * but account for loop customdata */
555   return BM_vert_collapse_faces(bm, e_kill, v_kill, 1.0f, do_del, false, kill_degenerate_faces);
556 #endif
557 }
558
559 #undef DO_V_INTERP
560
561 /**
562  * Collapse and edge into a single vertex.
563  */
564 BMVert *BM_edge_collapse(
565     BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces)
566 {
567   return bmesh_kernel_join_vert_kill_edge(bm, e_kill, v_kill, do_del, true, kill_degenerate_faces);
568 }
569
570 /**
571  * \brief Edge Split
572  *
573  * <pre>
574  * Before: v
575  *         +-----------------------------------+
576  *                           e
577  *
578  * After:  v                 v_new (returned)
579  *         +-----------------+-----------------+
580  *                 r_e                e
581  * </pre>
582  *
583  * \param e: The edge to split.
584  * \param v: One of the vertices in \a e and defines the "from" end of the splitting operation,
585  * the new vertex will be \a fac of the way from \a v to the other end.
586  * \param r_e: The newly created edge.
587  * \return  The new vertex.
588  */
589 BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
590 {
591   BMVert *v_new, *v_other;
592   BMEdge *e_new;
593   BMFace **oldfaces = NULL;
594   BLI_array_staticdeclare(oldfaces, 32);
595   const int cd_loop_mdisp_offset = BM_edge_is_wire(e) ?
596                                        -1 :
597                                        CustomData_get_offset(&bm->ldata, CD_MDISPS);
598
599   BLI_assert(BM_vert_in_edge(e, v) == true);
600
601   /* do we have a multi-res layer? */
602   if (cd_loop_mdisp_offset != -1) {
603     BMLoop *l;
604     int i;
605
606     l = e->l;
607     do {
608       BLI_array_append(oldfaces, l->f);
609       l = l->radial_next;
610     } while (l != e->l);
611
612     /* flag existing faces so we can differentiate oldfaces from new faces */
613     for (i = 0; i < BLI_array_len(oldfaces); i++) {
614       BM_ELEM_API_FLAG_ENABLE(oldfaces[i], _FLAG_OVERLAP);
615       oldfaces[i] = BM_face_copy(bm, bm, oldfaces[i], true, true);
616       BM_ELEM_API_FLAG_DISABLE(oldfaces[i], _FLAG_OVERLAP);
617     }
618   }
619
620   v_other = BM_edge_other_vert(e, v);
621   v_new = bmesh_kernel_split_edge_make_vert(bm, v, e, &e_new);
622   if (r_e != NULL) {
623     *r_e = e_new;
624   }
625
626   BLI_assert(v_new != NULL);
627   BLI_assert(BM_vert_in_edge(e_new, v) && BM_vert_in_edge(e_new, v_new));
628   BLI_assert(BM_vert_in_edge(e, v_new) && BM_vert_in_edge(e, v_other));
629
630   sub_v3_v3v3(v_new->co, v_other->co, v->co);
631   madd_v3_v3v3fl(v_new->co, v->co, v_new->co, fac);
632
633   e_new->head.hflag = e->head.hflag;
634   BM_elem_attrs_copy(bm, bm, e, e_new);
635
636   /* v->v_new->v2 */
637   BM_data_interp_face_vert_edge(bm, v_other, v, v_new, e, fac);
638   BM_data_interp_from_verts(bm, v, v_other, v_new, fac);
639
640   if (cd_loop_mdisp_offset != -1) {
641     int i, j;
642
643     /* interpolate new/changed loop data from copied old faces */
644     for (i = 0; i < BLI_array_len(oldfaces); i++) {
645       float f_center_old[3];
646
647       BM_face_calc_center_median(oldfaces[i], f_center_old);
648
649       for (j = 0; j < 2; j++) {
650         BMEdge *e1 = j ? e_new : e;
651         BMLoop *l;
652
653         l = e1->l;
654
655         if (UNLIKELY(!l)) {
656           BMESH_ASSERT(0);
657           break;
658         }
659
660         do {
661           /* check this is an old face */
662           if (BM_ELEM_API_FLAG_TEST(l->f, _FLAG_OVERLAP)) {
663             float f_center[3];
664
665             BM_face_calc_center_median(l->f, f_center);
666             BM_face_interp_multires_ex(
667                 bm, l->f, oldfaces[i], f_center, f_center_old, cd_loop_mdisp_offset);
668           }
669           l = l->radial_next;
670         } while (l != e1->l);
671       }
672     }
673
674     /* destroy the old faces */
675     for (i = 0; i < BLI_array_len(oldfaces); i++) {
676       BM_face_verts_kill(bm, oldfaces[i]);
677     }
678
679     /* fix boundaries a bit, doesn't work too well quite yet */
680 #if 0
681     for (j = 0; j < 2; j++) {
682       BMEdge *e1 = j ? e_new : e;
683       BMLoop *l, *l2;
684
685       l = e1->l;
686       if (UNLIKELY(!l)) {
687         BMESH_ASSERT(0);
688         break;
689       }
690
691       do {
692         BM_face_multires_bounds_smooth(bm, l->f);
693         l = l->radial_next;
694       } while (l != e1->l);
695     }
696 #endif
697
698     BLI_array_free(oldfaces);
699   }
700
701   return v_new;
702 }
703
704 /**
705  * \brief Split an edge multiple times evenly
706  *
707  * \param r_varr: Optional array, verts in between (v1 -> v2)
708  */
709 BMVert *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts, BMVert **r_varr)
710 {
711   int i;
712   float percent;
713   BMVert *v_new = NULL;
714
715   for (i = 0; i < numcuts; i++) {
716     percent = 1.0f / (float)(numcuts + 1 - i);
717     v_new = BM_edge_split(bm, e, e->v2, NULL, percent);
718     if (r_varr) {
719       /* fill in reverse order (v1 -> v2) */
720       r_varr[numcuts - i - 1] = v_new;
721     }
722   }
723   return v_new;
724 }
725
726 /**
727  * Swap v1 & v2
728  *
729  * \note Typically we shouldn't care about this, however it's used when extruding wire edges.
730  */
731 void BM_edge_verts_swap(BMEdge *e)
732 {
733   SWAP(BMVert *, e->v1, e->v2);
734   SWAP(BMDiskLink, e->v1_disk_link, e->v2_disk_link);
735 }
736
737 #if 0
738 /**
739  * Checks if a face is valid in the data structure
740  */
741 bool BM_face_validate(BMFace *face, FILE *err)
742 {
743   BMIter iter;
744   BLI_array_declare(verts);
745   BMVert **verts = NULL;
746   BMLoop *l;
747   int i, j;
748   bool ret = true;
749
750   if (face->len == 2) {
751     fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
752     fflush(err);
753   }
754
755   BLI_array_grow_items(verts, face->len);
756   BM_ITER_ELEM_INDEX (l, &iter, face, BM_LOOPS_OF_FACE, i) {
757     verts[i] = l->v;
758     if (l->e->v1 == l->e->v2) {
759       fprintf(err, "Found bmesh edge with identical verts!\n");
760       fprintf(err, "  edge ptr: %p, vert: %p\n", l->e, l->e->v1);
761       fflush(err);
762       ret = false;
763     }
764   }
765
766   for (i = 0; i < face->len; i++) {
767     for (j = 0; j < face->len; j++) {
768       if (j == i) {
769         continue;
770       }
771
772       if (verts[i] == verts[j]) {
773         fprintf(err, "Found duplicate verts in bmesh face!\n");
774         fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
775         fflush(err);
776         ret = false;
777       }
778     }
779   }
780
781   BLI_array_free(verts);
782   return ret;
783 }
784 #endif
785
786 /**
787  * Calculate the 2 loops which _would_ make up the newly rotated Edge
788  * but don't actually change anything.
789  *
790  * Use this to further inspect if the loops to be connected have issues:
791  *
792  * Examples:
793  * - the newly formed edge already exists
794  * - the new face would be degenerate (zero area / concave /  bow-tie)
795  * - may want to measure if the new edge gives improved results topology.
796  *   over the old one, as with beauty fill.
797  *
798  * \note #BM_edge_rotate_check must have already run.
799  */
800 void BM_edge_calc_rotate(BMEdge *e, const bool ccw, BMLoop **r_l1, BMLoop **r_l2)
801 {
802   BMVert *v1, *v2;
803   BMFace *fa, *fb;
804
805   /* this should have already run */
806   BLI_assert(BM_edge_rotate_check(e) == true);
807
808   /* we know this will work */
809   BM_edge_face_pair(e, &fa, &fb);
810
811   /* so we can use ccw variable correctly,
812    * otherwise we could use the edges verts direct */
813   BM_edge_ordered_verts(e, &v1, &v2);
814
815   /* we could swap the verts _or_ the faces, swapping faces
816    * gives more predictable results since that way the next vert
817    * just stitches from face fa / fb */
818   if (!ccw) {
819     SWAP(BMFace *, fa, fb);
820   }
821
822   *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
823   *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
824 }
825
826 /**
827  * \brief Check if Rotate Edge is OK
828  *
829  * Quick check to see if we could rotate the edge,
830  * use this to avoid calling exceptions on common cases.
831  */
832 bool BM_edge_rotate_check(BMEdge *e)
833 {
834   BMFace *fa, *fb;
835   if (BM_edge_face_pair(e, &fa, &fb)) {
836     BMLoop *la, *lb;
837
838     la = BM_face_other_vert_loop(fa, e->v2, e->v1);
839     lb = BM_face_other_vert_loop(fb, e->v2, e->v1);
840
841     /* check that the next vert in both faces isn't the same
842      * (ie - the next edge doesn't share the same faces).
843      * since we can't rotate usefully in this case. */
844     if (la->v == lb->v) {
845       return false;
846     }
847
848     /* mirror of the check above but in the opposite direction */
849     la = BM_face_other_vert_loop(fa, e->v1, e->v2);
850     lb = BM_face_other_vert_loop(fb, e->v1, e->v2);
851
852     if (la->v == lb->v) {
853       return false;
854     }
855
856     return true;
857   }
858   else {
859     return false;
860   }
861 }
862
863 /**
864  * \brief Check if Edge Rotate Gives Degenerate Faces
865  *
866  * Check 2 cases
867  * 1) does the newly forms edge form a flipped face (compare with previous cross product)
868  * 2) does the newly formed edge cause a zero area corner (or close enough to be almost zero)
869  *
870  * \param e: The edge to test rotation.
871  * \param l1, l2: are the loops of the proposed verts to rotate too and should
872  * be the result of calling #BM_edge_calc_rotate
873  */
874 bool BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2)
875 {
876   /* note: for these vars 'old' just means initial edge state. */
877
878   float ed_dir_old[3];      /* edge vector */
879   float ed_dir_new[3];      /* edge vector */
880   float ed_dir_new_flip[3]; /* edge vector */
881
882   float ed_dir_v1_old[3];
883   float ed_dir_v2_old[3];
884
885   float ed_dir_v1_new[3];
886   float ed_dir_v2_new[3];
887
888   float cross_old[3];
889   float cross_new[3];
890
891   /* original verts - these will be in the edge 'e' */
892   BMVert *v1_old, *v2_old;
893
894   /* verts from the loops passed */
895
896   BMVert *v1, *v2;
897   /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
898   BMVert *v1_alt, *v2_alt;
899
900   /* this should have already run */
901   BLI_assert(BM_edge_rotate_check(e) == true);
902
903   BM_edge_ordered_verts(e, &v1_old, &v2_old);
904
905   v1 = l1->v;
906   v2 = l2->v;
907
908   /* get the next vert along */
909   v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
910   v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
911
912   /* normalize all so comparisons are scale independent */
913
914   BLI_assert(BM_edge_exists(v1_old, v1));
915   BLI_assert(BM_edge_exists(v1, v1_alt));
916
917   BLI_assert(BM_edge_exists(v2_old, v2));
918   BLI_assert(BM_edge_exists(v2, v2_alt));
919
920   /* old and new edge vecs */
921   sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
922   sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
923   normalize_v3(ed_dir_old);
924   normalize_v3(ed_dir_new);
925
926   /* old edge corner vecs */
927   sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
928   sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
929   normalize_v3(ed_dir_v1_old);
930   normalize_v3(ed_dir_v2_old);
931
932   /* old edge corner vecs */
933   sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
934   sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
935   normalize_v3(ed_dir_v1_new);
936   normalize_v3(ed_dir_v2_new);
937
938   /* compare */
939   cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
940   cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
941   if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
942     return false;
943   }
944   cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
945   cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
946   if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
947     return false;
948   }
949
950   negate_v3_v3(ed_dir_new_flip, ed_dir_new);
951
952   /* result is zero area corner */
953   if ((dot_v3v3(ed_dir_new, ed_dir_v1_new) > 0.999f) ||
954       (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f)) {
955     return false;
956   }
957
958   return true;
959 }
960
961 bool BM_edge_rotate_check_beauty(BMEdge *e, BMLoop *l1, BMLoop *l2)
962 {
963   /* Stupid check for now:
964    * Could compare angles of surrounding edges
965    * before & after, but this is OK.*/
966   return (len_squared_v3v3(e->v1->co, e->v2->co) > len_squared_v3v3(l1->v->co, l2->v->co));
967 }
968
969 /**
970  * \brief Rotate Edge
971  *
972  * Spins an edge topologically,
973  * either counter-clockwise or clockwise depending on \a ccw.
974  *
975  * \return The spun edge, NULL on error
976  * (e.g., if the edge isn't surrounded by exactly two faces).
977  *
978  * \note This works by dissolving the edge then re-creating it,
979  * so the returned edge won't have the same pointer address as the original one.
980  *
981  * \see header definition for \a check_flag enum.
982  */
983 BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
984 {
985   BMVert *v1, *v2;
986   BMLoop *l1, *l2;
987   BMFace *f;
988   BMEdge *e_new = NULL;
989   char f_active_prev = 0;
990   char f_hflag_prev_1;
991   char f_hflag_prev_2;
992
993   if (!BM_edge_rotate_check(e)) {
994     return NULL;
995   }
996
997   BM_edge_calc_rotate(e, ccw, &l1, &l2);
998
999   /* the loops will be freed so assign verts */
1000   v1 = l1->v;
1001   v2 = l2->v;
1002
1003   /* --------------------------------------- */
1004   /* Checking Code - make sure we can rotate */
1005
1006   if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
1007     if (!BM_edge_rotate_check_beauty(e, l1, l2)) {
1008       return NULL;
1009     }
1010   }
1011
1012   /* check before applying */
1013   if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
1014     if (BM_edge_exists(v1, v2)) {
1015       return NULL;
1016     }
1017   }
1018
1019   /* slowest, check last */
1020   if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
1021     if (!BM_edge_rotate_check_degenerate(e, l1, l2)) {
1022       return NULL;
1023     }
1024   }
1025   /* Done Checking */
1026   /* ------------- */
1027
1028   /* --------------- */
1029   /* Rotate The Edge */
1030
1031   /* first create the new edge, this is so we can copy the customdata from the old one
1032    * if splice if disabled, always add in a new edge even if theres one there. */
1033   e_new = BM_edge_create(
1034       bm, v1, v2, e, (check_flag & BM_EDGEROT_CHECK_SPLICE) ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
1035
1036   f_hflag_prev_1 = l1->f->head.hflag;
1037   f_hflag_prev_2 = l2->f->head.hflag;
1038
1039   /* maintain active face */
1040   if (bm->act_face == l1->f) {
1041     f_active_prev = 1;
1042   }
1043   else if (bm->act_face == l2->f) {
1044     f_active_prev = 2;
1045   }
1046
1047   const bool is_flipped = !BM_edge_is_contiguous(e);
1048
1049   /* don't delete the edge, manually remove the edge after so we can copy its attributes */
1050   f = BM_faces_join_pair(
1051       bm, BM_face_edge_share_loop(l1->f, e), BM_face_edge_share_loop(l2->f, e), true);
1052
1053   if (f == NULL) {
1054     return NULL;
1055   }
1056
1057   /* note, this assumes joining the faces _didnt_ also remove the verts.
1058    * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
1059    * break this */
1060   if ((l1 = BM_face_vert_share_loop(f, v1)) && (l2 = BM_face_vert_share_loop(f, v2)) &&
1061       BM_face_split(bm, f, l1, l2, NULL, NULL, true)) {
1062     /* we should really be able to know the faces some other way,
1063      * rather then fetching them back from the edge, but this is predictable
1064      * where using the return values from face split isn't. - campbell */
1065     BMFace *fa, *fb;
1066     if (BM_edge_face_pair(e_new, &fa, &fb)) {
1067       fa->head.hflag = f_hflag_prev_1;
1068       fb->head.hflag = f_hflag_prev_2;
1069
1070       if (f_active_prev == 1) {
1071         bm->act_face = fa;
1072       }
1073       else if (f_active_prev == 2) {
1074         bm->act_face = fb;
1075       }
1076
1077       if (is_flipped) {
1078         BM_face_normal_flip(bm, fb);
1079
1080         if (ccw) {
1081           /* needed otherwise ccw toggles direction */
1082           e_new->l = e_new->l->radial_next;
1083         }
1084       }
1085     }
1086   }
1087   else {
1088     return NULL;
1089   }
1090
1091   return e_new;
1092 }
1093
1094 /**
1095  * \brief Rip a single face from a vertex fan
1096  */
1097 BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *l_sep)
1098 {
1099   return bmesh_kernel_unglue_region_make_vert(bm, l_sep);
1100 }
1101
1102 BMVert *BM_face_loop_separate_multi_isolated(BMesh *bm, BMLoop *l_sep)
1103 {
1104   return bmesh_kernel_unglue_region_make_vert_multi_isolated(bm, l_sep);
1105 }
1106
1107 BMVert *BM_face_loop_separate_multi(BMesh *bm, BMLoop **larr, int larr_len)
1108 {
1109   return bmesh_kernel_unglue_region_make_vert_multi(bm, larr, larr_len);
1110 }