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