code cleanup: typos

[blender-staging.git] / source / blender / bmesh / intern / bmesh_mods.c

/*
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
 *
 * ***** END GPL LICENSE BLOCK *****
 */

/** \file blender/bmesh/intern/bmesh_mods.c
 *  \ingroup bmesh
 *
 * This file contains functions for locally modifying
 * the topology of existing mesh data. (split, join, flip etc).
 */

#include "MEM_guardedalloc.h"


#include "BLI_math.h"
#include "BLI_array.h"
#include "BLI_smallhash.h"

#include "BKE_customdata.h"

#include "bmesh.h"
#include "intern/bmesh_private.h"

/**
 * \brief Dissolve Vert
 *
 * Turns the face region surrounding a manifold vertex into a single polygon.
 *
 * \par Example:
 * <pre>
 *              +---------+             +---------+
 *              |  \   /  |             |         |
 *     Before:  |    v    |      After: |         |
 *              |  /   \  |             |         |
 *              +---------+             +---------+
 * </pre>
 *
 * This function can also collapse edges too
 * in cases when it cant merge into faces.
 *
 * \par Example:
 * <pre>
 *     Before:  +----v----+      After: +---------+
 * </pre>
 *
 * \note dissolves vert, in more situations then BM_disk_dissolve
 * (e.g. if the vert is part of a wire edge, etc).
 */
bool BM_vert_dissolve(BMesh *bm, BMVert *v)
{
        const int len = BM_vert_edge_count(v);
        
        if (len == 1) {
                BM_vert_kill(bm, v); /* will kill edges too */
                return true;
        }
        else if (!BM_vert_is_manifold(v)) {
                if (!v->e) {
                        BM_vert_kill(bm, v);
                        return true;
                }
                else if (!v->e->l) {
                        if (len == 2) {
                                return (BM_vert_collapse_edge(bm, v->e, v, true) != NULL);
                        }
                        else {
                                /* used to kill the vertex here, but it may be connected to faces.
                                 * so better do nothing */
                                return false;
                        }
                }
                else {
                        return false;
                }
        }
        else if (len == 2 && BM_vert_face_count(v) == 1) {
                /* boundary vertex on a face */
                return (BM_vert_collapse_edge(bm, v->e, v, true) != NULL);
        }
        else {
                return BM_disk_dissolve(bm, v);
        }
}

/**
 * dissolves all faces around a vert, and removes it.
 */
bool BM_disk_dissolve(BMesh *bm, BMVert *v)
{
        BMFace *f, *f2;
        BMEdge *e, *keepedge = NULL, *baseedge = NULL;
        int len = 0;

        if (!BM_vert_is_manifold(v)) {
                return false;
        }
        
        if (v->e) {
                /* v->e we keep, what else */
                e = v->e;
                do {
                        e = bmesh_disk_edge_next(e, v);
                        if (!(BM_edge_share_face_check(e, v->e))) {
                                keepedge = e;
                                baseedge = v->e;
                                break;
                        }
                        len++;
                } while (e != v->e);
        }
        
        /* this code for handling 2 and 3-valence verts
         * may be totally bad */
        if (keepedge == NULL && len == 3) {
#if 0
                /* handle specific case for three-valence.  solve it by
                 * increasing valence to four.  this may be hackish. .  */
                BMLoop *loop = e->l;
                if (loop->v == v) loop = loop->next;
                if (!BM_face_split(bm, loop->f, v, loop->v, NULL, NULL, false))
                        return false;

                if (!BM_disk_dissolve(bm, v)) {
                        return false;
                }
#else
                if (UNLIKELY(!BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, true))) {
                        return false;
                }
                else if (UNLIKELY(!BM_vert_collapse_faces(bm, v->e, v, 1.0, false, true))) {
                        return false;
                }
#endif
                return true;
        }
        else if (keepedge == NULL && len == 2) {
                /* collapse the vertex */
                e = BM_vert_collapse_faces(bm, v->e, v, 1.0, true, true);

                if (!e) {
                        return false;
                }

                /* handle two-valence */
                f = e->l->f;
                f2 = e->l->radial_next->f;

                if (f != f2 && !BM_faces_join_pair(bm, f, f2, e, true)) {
                        return false;
                }

                return true;
        }

        if (keepedge) {
                bool done = false;

                while (!done) {
                        done = true;
                        e = v->e;
                        do {
                                f = NULL;
                                len = bmesh_radial_length(e->l);
                                if (len == 2 && (e != baseedge) && (e != keepedge)) {
                                        f = BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, true);
                                        /* return if couldn't join faces in manifold
                                         * conditions */
                                        /* !disabled for testing why bad things happen */
                                        if (!f) {
                                                return false;
                                        }
                                }

                                if (f) {
                                        done = false;
                                        break;
                                }
                                e = bmesh_disk_edge_next(e, v);
                        } while (e != v->e);
                }

                /* collapse the vertex */
                /* note, the baseedge can be a boundary of manifold, use this as join_faces arg */
                e = BM_vert_collapse_faces(bm, baseedge, v, 1.0, !BM_edge_is_boundary(baseedge), true);

                if (!e) {
                        return false;
                }
                
                /* get remaining two faces */
                f = e->l->f;
                f2 = e->l->radial_next->f;

                if (f != f2) {
                        /* join two remaining faces */
                        if (!BM_faces_join_pair(bm, f, f2, e, true)) {
                                return false;
                        }
                }
        }

        return true;
}

/**
 * \brief Faces Join Pair
 *
 * Joins two adjacent faces together.
 *
 * Because this method calls to #BM_faces_join to do its work, if a pair
 * of faces share multiple edges, the pair of faces will be joined at
 * every edge (not just edge \a e). This part of the functionality might need
 * to be reconsidered.
 *
 * If the windings do not match the winding of the new face will follow
 * \a f1's winding (i.e. \a f2 will be reversed before the join).
 *
 * \return pointer to the combined face
 */
BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, const bool do_del)
{
        BMLoop *l1, *l2;
        BMEdge *jed = NULL;
        BMFace *faces[2] = {f1, f2};
        
        jed = e;
        if (!jed) {
                BMLoop *l_first;
                /* search for an edge that has both these faces in its radial cycle */
                l1 = l_first = BM_FACE_FIRST_LOOP(f1);
                do {
                        if (l1->radial_next->f == f2) {
                                jed = l1->e;
                                break;
                        }
                } while ((l1 = l1->next) != l_first);
        }

        if (UNLIKELY(!jed)) {
                BMESH_ASSERT(0);
                return NULL;
        }
        
        l1 = jed->l;
        
        if (UNLIKELY(!l1)) {
                BMESH_ASSERT(0);
                return NULL;
        }
        
        l2 = l1->radial_next;
        if (l1->v == l2->v) {
                bmesh_loop_reverse(bm, f2);
        }

        f1 = BM_faces_join(bm, faces, 2, do_del);
        
        return f1;
}

/**
 * \brief Connect Verts, Split Face
 *
 * connects two verts together, automatically (if very naively) finding the
 * face they both share (if there is one) and splitting it.  Use this at your
 * own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
 * multiple faces, etc).
 *
 * this is really only meant for cases where you don't know before hand the face
 * the two verts belong to for splitting (e.g. the subdivision operator).
 *
 * \return The newly created edge.
 */
BMEdge *BM_verts_connect(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **r_f)
{
        BMIter fiter;
        BMIter viter;
        BMVert *v_iter;
        BMFace *f_iter;

        /* be warned: this can do weird things in some ngon situation, see BM_face_legal_splits */
        BM_ITER_ELEM (f_iter, &fiter, v1, BM_FACES_OF_VERT) {
                BM_ITER_ELEM (v_iter, &viter, f_iter, BM_FACES_OF_VERT) {
                        if (v_iter == v2) {
                                BMLoop *l_new;

                                f_iter = BM_face_split(bm, f_iter, v1, v2, &l_new, NULL, false);

                                if (r_f) {
                                        *r_f = f_iter;
                                }
                                return l_new->e;
                        }
                }
        }

        if (r_f) {
                *r_f = NULL;
        }
        return NULL;
}

/**
 * \brief Face Split
 *
 * Split a face along two vertices. returns the newly made face, and sets
 * the \a r_l member to a loop in the newly created edge.
 *
 * \param bm The bmesh
 * \param f the original face
 * \param v1, v2 vertices which define the split edge, must be different
 * \param r_l pointer which will receive the BMLoop for the split edge in the new face
 * \param example Edge used for attributes of splitting edge, if non-NULL
 * \param nodouble Use an existing edge if found
 *
 * \return Pointer to the newly created face representing one side of the split
 * if the split is successful (and the original original face will be the
 * other side). NULL if the split fails.
 */
BMFace *BM_face_split(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **r_l,
                      BMEdge *example, const bool no_double)
{
        const bool has_mdisp = CustomData_has_layer(&bm->ldata, CD_MDISPS);
        BMFace *f_new, *f_tmp;

        BLI_assert(v1 != v2);

        /* do we have a multires layer? */
        if (has_mdisp) {
                f_tmp = BM_face_copy(bm, bm, f, false, false);
        }
        
#ifdef USE_BMESH_HOLES
        f_new = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, no_double);
#else
        f_new = bmesh_sfme(bm, f, v1, v2, r_l, example, no_double);
#endif
        
        if (f_new) {
                BM_elem_attrs_copy(bm, bm, f, f_new);
                copy_v3_v3(f_new->no, f->no);

                /* handle multires update */
                if (has_mdisp && (f_new != f)) {
                        BMLoop *l_iter;
                        BMLoop *l_first;

                        l_iter = l_first = BM_FACE_FIRST_LOOP(f);
                        do {
                                BM_loop_interp_multires(bm, l_iter, f_tmp);
                        } while ((l_iter = l_iter->next) != l_first);

                        l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
                        do {
                                BM_loop_interp_multires(bm, l_iter, f_tmp);
                        } while ((l_iter = l_iter->next) != l_first);

                        BM_face_kill(bm, f_tmp);

#if 0
                        /* BM_face_multires_bounds_smooth doesn't flip displacement correct */
                        BM_face_multires_bounds_smooth(bm, f);
                        BM_face_multires_bounds_smooth(bm, f_new);
#endif
                }
        }

        return f_new;
}

/**
 * \brief Face Split with intermediate points
 *
 * Like BM_face_split, but with an edge split by \a n intermediate points with given coordinates.
 *
 * \param bm The bmesh
 * \param f the original face
 * \param v1, v2 vertices which define the split edge, must be different
 * \param cos Array of coordinates for intermediate points
 * \param n Length of \a cos (must be > 0)
 * \param r_l pointer which will receive the BMLoop for the first split edge (from \a v1) in the new face
 * \param example Edge used for attributes of splitting edge, if non-NULL
 *
 * \return Pointer to the newly created face representing one side of the split
 * if the split is successful (and the original original face will be the
 * other side). NULL if the split fails.
 */
BMFace *BM_face_split_n(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, float cos[][3], int n,
                        BMLoop **r_l, BMEdge *example)
{
        BMFace *f_new, *f_tmp;
        BMLoop *l_dummy;
        BMEdge *e, *e_new;
        BMVert *v_new;
        int i, j;

        BLI_assert(v1 != v2);

        f_tmp = BM_face_copy(bm, bm, f, true, true);

        if (!r_l)
                r_l = &l_dummy;
        
#ifdef USE_BMESH_HOLES
        f_new = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, false);
#else
        f_new = bmesh_sfme(bm, f, v1, v2, r_l, example, false);
#endif
        /* bmesh_sfme returns in r_l a Loop for f_new going from v1 to v2.
         * The radial_next is for f and goes from v2 to v1  */

        if (f_new) {
                BM_elem_attrs_copy(bm, bm, f, f_new);
                copy_v3_v3(f_new->no, f->no);

                e = (*r_l)->e;
                for (i = 0; i < n; i++) {
                        v_new = bmesh_semv(bm, v2, e, &e_new);
                        BLI_assert(v_new != NULL);
                        /* bmesh_semv returns in e_new the edge going from v_new to tv */
                        copy_v3_v3(v_new->co, cos[i]);

                        /* interpolate the loop data for the loops with (v == v_new), using orig face */
                        for (j = 0; j < 2; j++) {
                                BMEdge *e_iter = (j == 0) ? e : e_new;
                                BMLoop *l_iter = e_iter->l;
                                do {
                                        if (l_iter->v == v_new) {
                                                /* this interpolates both loop and vertex data */
                                                BM_loop_interp_from_face(bm, l_iter, f_tmp, true, true);
                                        }
                                } while ((l_iter = l_iter->radial_next) != e_iter->l);
                        }
                        e = e_new;
                }
        }

        BM_face_verts_kill(bm, f_tmp);

        return f_new;
}

/**
 * \brief Vert Collapse Faces
 *
 * Collapses vertex \a v_kill that has only two manifold edges
 * onto a vertex it shares an edge with.
 * \a fac defines the amount of interpolation for Custom Data.
 *
 * \note that this is not a general edge collapse function.
 *
 * \note this function is very close to #BM_vert_collapse_edge,
 * both collapse a vertex and return a new edge.
 * Except this takes a factor and merges custom data.
 *
 * \param bm The bmesh
 * \param e_kill The edge to collapse
 * \param v_kill The vertex  to collapse into the edge
 * \param fac The factor along the edge
 * \param join_faces When true the faces around the vertex will be joined
 * otherwise collapse the vertex by merging the 2 edges this vert touches into one.
 * \param kill_degenerate_faces Removes faces with less than 3 verts after collapsing.
 *
 * \returns The New Edge
 */
BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac,
                               const bool join_faces, const bool kill_degenerate_faces)
{
        BMEdge *e_new = NULL;
        BMVert *tv = bmesh_edge_other_vert_get(e_kill, v_kill);

        BMEdge *e2;
        BMVert *tv2;

        BMIter iter;
        BMLoop *l_iter = NULL, *kvloop = NULL, *tvloop = NULL;

        void *src[2];
        float w[2];

        /* Only intended to be called for 2-valence vertices */
        BLI_assert(bmesh_disk_count(v_kill) <= 2);


        /* first modify the face loop data  */
        w[0] = 1.0f - fac;
        w[1] = fac;

        if (e_kill->l) {
                l_iter = e_kill->l;
                do {
                        if (l_iter->v == tv && l_iter->next->v == v_kill) {
                                tvloop = l_iter;
                                kvloop = l_iter->next;

                                src[0] = kvloop->head.data;
                                src[1] = tvloop->head.data;
                                CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, kvloop->head.data);
                        }
                } while ((l_iter = l_iter->radial_next) != e_kill->l);
        }

        /* now interpolate the vertex data */
        BM_data_interp_from_verts(bm, v_kill, tv, v_kill, fac);

        e2 = bmesh_disk_edge_next(e_kill, v_kill);
        tv2 = BM_edge_other_vert(e2, v_kill);

        if (join_faces) {
                BMFace **faces = NULL;
                BMFace *f;
                BLI_array_staticdeclare(faces, 8);

                BM_ITER_ELEM (f, &iter, v_kill, BM_FACES_OF_VERT) {
                        BLI_array_append(faces, f);
                }

                if (BLI_array_count(faces) >= 2) {
                        BMFace *f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
                        if (f2) {
                                BMLoop *l_new = NULL;
                                if (BM_face_split(bm, f2, tv, tv2, &l_new, NULL, false)) {
                                        e_new = l_new->e;
                                }
                        }
                }

                BLI_array_free(faces);
        }
        else {
                /* single face or no faces */
                /* same as BM_vert_collapse_edge() however we already
                 * have vars to perform this operation so don't call. */
                e_new = bmesh_jekv(bm, e_kill, v_kill, true);
                /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */

                if (e_new && kill_degenerate_faces) {
                        BLI_array_declare(bad_faces);
                        BMFace **bad_faces = NULL;

                        BMIter fiter;
                        BMFace *f;
                        BMVert *verts[2] = {e_new->v1, e_new->v2};
                        int i;

                        for (i = 0; i < 2; i++) {
                                /* cant kill data we loop on, build a list and remove those */
                                BLI_array_empty(bad_faces);
                                BM_ITER_ELEM (f, &fiter, verts[i], BM_FACES_OF_VERT) {
                                        if (UNLIKELY(f->len < 3)) {
                                                BLI_array_append(bad_faces, f);
                                        }
                                }
                                while ((f = BLI_array_pop(bad_faces))) {
                                        BM_face_kill(bm, f);
                                }
                        }
                        BLI_array_free(bad_faces);
                }
        }

        return e_new;
}


/**
 * \brief Vert Collapse Faces
 *
 * Collapses a vertex onto another vertex it shares an edge with.
 *
 * \return The New Edge
 */
BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
                              const bool kill_degenerate_faces)
{
        /* nice example implementation but we want loops to have their customdata
         * accounted for */
#if 0
        BMEdge *e_new = NULL;

        /* Collapse between 2 edges */

        /* in this case we want to keep all faces and not join them,
         * rather just get rid of the vertex - see bug [#28645] */
        BMVert *tv  = bmesh_edge_other_vert_get(e_kill, v_kill);
        if (tv) {
                BMEdge *e2 = bmesh_disk_edge_next(e_kill, v_kill);
                if (e2) {
                        BMVert *tv2 = BM_edge_other_vert(e2, v_kill);
                        if (tv2) {
                                /* only action, other calls here only get the edge to return */
                                e_new = bmesh_jekv(bm, e_kill, v_kill);

                                /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
                        }
                }
        }

        return e_new;
#else
        /* with these args faces are never joined, same as above
         * but account for loop customdata */
        return BM_vert_collapse_faces(bm, e_kill, v_kill, 1.0f, false, kill_degenerate_faces);
#endif
}

#undef DO_V_INTERP

/**
 * \brief Edge Split
 *
 * Splits an edge. \a v should be one of the vertices in \a e and defines
 * the "from" end of the splitting operation: the new vertex will be
 * \a percent of the way from \a v to the other end.
 * The newly created edge is attached to \a v and is returned in \a r_e.
 * The original edge \a e will be the other half of the split.
 *
 * \return The new vert
 */
BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float percent)
{
        BMVert *v_new, *v2;
        BMFace **oldfaces = NULL;
        BMEdge *e_dummy;
        BLI_array_staticdeclare(oldfaces, 32);
        const bool do_mdisp = (e->l && CustomData_has_layer(&bm->ldata, CD_MDISPS));

        /* we need this for handling multi-res */
        if (!r_e) {
                r_e = &e_dummy;
        }

        /* do we have a multi-res layer? */
        if (do_mdisp) {
                BMLoop *l;
                int i;
                
                l = e->l;
                do {
                        BLI_array_append(oldfaces, l->f);
                        l = l->radial_next;
                } while (l != e->l);
                
                /* flag existing faces so we can differentiate oldfaces from new faces */
                for (i = 0; i < BLI_array_count(oldfaces); i++) {
                        BM_ELEM_API_FLAG_ENABLE(oldfaces[i], _FLAG_OVERLAP);
                        oldfaces[i] = BM_face_copy(bm, bm, oldfaces[i], true, true);
                        BM_ELEM_API_FLAG_DISABLE(oldfaces[i], _FLAG_OVERLAP);
                }
        }

        v2 = bmesh_edge_other_vert_get(e, v);
        v_new = bmesh_semv(bm, v, e, r_e);

        BLI_assert(v_new != NULL);

        sub_v3_v3v3(v_new->co, v2->co, v->co);
        madd_v3_v3v3fl(v_new->co, v->co, v_new->co, percent);

        if (r_e) {
                (*r_e)->head.hflag = e->head.hflag;
                BM_elem_attrs_copy(bm, bm, e, *r_e);
        }

        /* v->v_new->v2 */
        BM_data_interp_face_vert_edge(bm, v2, v, v_new, e, percent);
        BM_data_interp_from_verts(bm, v, v2, v_new, percent);

        if (do_mdisp) {
                int i, j;

                /* interpolate new/changed loop data from copied old faces */
                for (j = 0; j < 2; j++) {
                        for (i = 0; i < BLI_array_count(oldfaces); i++) {
                                BMEdge *e1 = j ? *r_e : e;
                                BMLoop *l, *l2;
                                
                                l = e1->l;

                                if (UNLIKELY(!l)) {
                                        BMESH_ASSERT(0);
                                        break;
                                }
                                
                                do {
                                        /* check this is an old face */
                                        if (BM_ELEM_API_FLAG_TEST(l->f, _FLAG_OVERLAP)) {
                                                BMLoop *l2_first;

                                                l2 = l2_first = BM_FACE_FIRST_LOOP(l->f);
                                                do {
                                                        BM_loop_interp_multires(bm, l2, oldfaces[i]);
                                                } while ((l2 = l2->next) != l2_first);
                                        }
                                        l = l->radial_next;
                                } while (l != e1->l);
                        }
                }
                
                /* destroy the old faces */
                for (i = 0; i < BLI_array_count(oldfaces); i++) {
                        BM_face_verts_kill(bm, oldfaces[i]);
                }
                
                /* fix boundaries a bit, doesn't work too well quite yet */
#if 0
                for (j = 0; j < 2; j++) {
                        BMEdge *e1 = j ? *r_e : e;
                        BMLoop *l, *l2;
                        
                        l = e1->l;
                        if (UNLIKELY(!l)) {
                                BMESH_ASSERT(0);
                                break;
                        }
                        
                        do {
                                BM_face_multires_bounds_smooth(bm, l->f);
                                l = l->radial_next;
                        } while (l != e1->l);
                }
#endif
                
                BLI_array_free(oldfaces);
        }

        return v_new;
}

/**
 * \brief Split an edge multiple times evenly
 *
 * \param r_varr  Optional array, verts in between (v1 -> v2)
 */
BMVert  *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts, BMVert **r_varr)
{
        int i;
        float percent;
        BMVert *v_new = NULL;
        
        for (i = 0; i < numcuts; i++) {
                percent = 1.0f / (float)(numcuts + 1 - i);
                v_new = BM_edge_split(bm, e, e->v2, NULL, percent);
                if (r_varr) {
                        /* fill in reverse order (v1 -> v2) */
                        r_varr[numcuts - i - 1] = v_new;
                }
        }
        return v_new;
}

#if 0
/**
 * Checks if a face is valid in the data structure
 */
bool BM_face_validate(BMFace *face, FILE *err)
{
        BMIter iter;
        BLI_array_declare(verts);
        BMVert **verts = NULL;
        BMLoop *l;
        int i, j;
        bool ret = true;
        
        if (face->len == 2) {
                fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
                fflush(err);
        }

        BLI_array_grow_items(verts, face->len);
        BM_ITER_ELEM_INDEX (l, &iter, face, BM_LOOPS_OF_FACE, i) {
                verts[i] = l->v;
                if (l->e->v1 == l->e->v2) {
                        fprintf(err, "Found bmesh edge with identical verts!\n");
                        fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
                        fflush(err);
                        ret = false;
                }
        }

        for (i = 0; i < face->len; i++) {
                for (j = 0; j < face->len; j++) {
                        if (j == i) {
                                continue;
                        }

                        if (verts[i] == verts[j]) {
                                fprintf(err, "Found duplicate verts in bmesh face!\n");
                                fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
                                fflush(err);
                                ret = false;
                        }
                }
        }
        
        BLI_array_free(verts);
        return ret;
}
#endif

/**
 * Calculate the 2 loops which _would_ make up the newly rotated Edge
 * but don't actually change anything.
 *
 * Use this to further inspect if the loops to be connected have issues:
 *
 * Examples:
 * - the newly formed edge already exists
 * - the new face would be degenerate (zero area / concave /  bow-tie)
 * - may want to measure if the new edge gives improved results topology.
 *   over the old one, as with beauty fill.
 *
 * \note #BM_edge_rotate_check must have already run.
 */
void BM_edge_calc_rotate(BMEdge *e, const bool ccw,
                         BMLoop **r_l1, BMLoop **r_l2)
{
        BMVert *v1, *v2;
        BMFace *fa, *fb;

        /* this should have already run */
        BLI_assert(BM_edge_rotate_check(e) == true);

        /* we know this will work */
        BM_edge_face_pair(e, &fa, &fb);

        /* so we can use ccw variable correctly,
         * otherwise we could use the edges verts direct */
        BM_edge_ordered_verts(e, &v1, &v2);

        /* we could swap the verts _or_ the faces, swapping faces
         * gives more predictable results since that way the next vert
         * just stitches from face fa / fb */
        if (ccw) {
                SWAP(BMFace *, fa, fb);
        }

        *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
        *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
}

/**
 * \brief Check if Rotate Edge is OK
 *
 * Quick check to see if we could rotate the edge,
 * use this to avoid calling exceptions on common cases.
 */
bool BM_edge_rotate_check(BMEdge *e)
{
        BMFace *fa, *fb;
        if (BM_edge_face_pair(e, &fa, &fb)) {
                BMLoop *la, *lb;

                la = BM_face_other_vert_loop(fa, e->v2, e->v1);
                lb = BM_face_other_vert_loop(fb, e->v2, e->v1);

                /* check that the next vert in both faces isn't the same
                 * (ie - the next edge doesn't share the same faces).
                 * since we can't rotate usefully in this case. */
                if (la->v == lb->v) {
                        return false;
                }

                /* mirror of the check above but in the opposite direction */
                la = BM_face_other_vert_loop(fa, e->v1, e->v2);
                lb = BM_face_other_vert_loop(fb, e->v1, e->v2);

                if (la->v == lb->v) {
                        return false;
                }

                return true;
        }
        else {
                return false;
        }
}

/**
 * \brief Check if Edge Rotate Gives Degenerate Faces
 *
 * Check 2 cases
 * 1) does the newly forms edge form a flipped face (compare with previous cross product)
 * 2) does the newly formed edge cause a zero area corner (or close enough to be almost zero)
 *
 * \param e The edge to test rotation.
 * \param l1,l2 are the loops of the proposed verts to rotate too and should
 * be the result of calling #BM_edge_calc_rotate
 */
bool BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2)
{
        /* note: for these vars 'old' just means initial edge state. */

        float ed_dir_old[3]; /* edge vector */
        float ed_dir_new[3]; /* edge vector */
        float ed_dir_new_flip[3]; /* edge vector */

        float ed_dir_v1_old[3];
        float ed_dir_v2_old[3];

        float ed_dir_v1_new[3];
        float ed_dir_v2_new[3];

        float cross_old[3];
        float cross_new[3];

        /* original verts - these will be in the edge 'e' */
        BMVert *v1_old, *v2_old;

        /* verts from the loops passed */

        BMVert *v1, *v2;
        /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
        BMVert *v1_alt, *v2_alt;

        /* this should have already run */
        BLI_assert(BM_edge_rotate_check(e) == true);

        BM_edge_ordered_verts(e, &v1_old, &v2_old);

        v1 = l1->v;
        v2 = l2->v;

        /* get the next vert along */
        v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
        v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;

        /* normalize all so comparisons are scale independent */

        BLI_assert(BM_edge_exists(v1_old, v1));
        BLI_assert(BM_edge_exists(v1, v1_alt));

        BLI_assert(BM_edge_exists(v2_old, v2));
        BLI_assert(BM_edge_exists(v2, v2_alt));

        /* old and new edge vecs */
        sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
        sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
        normalize_v3(ed_dir_old);
        normalize_v3(ed_dir_new);

        /* old edge corner vecs */
        sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
        sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
        normalize_v3(ed_dir_v1_old);
        normalize_v3(ed_dir_v2_old);

        /* old edge corner vecs */
        sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
        sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
        normalize_v3(ed_dir_v1_new);
        normalize_v3(ed_dir_v2_new);

        /* compare */
        cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
        cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
        if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
                return false;
        }
        cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
        cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
        if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
                return false;
        }

        negate_v3_v3(ed_dir_new_flip, ed_dir_new);

        /* result is zero area corner */
        if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
            (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
        {
                return false;
        }

        return true;
}

bool BM_edge_rotate_check_beauty(BMEdge *e,
                                 BMLoop *l1, BMLoop *l2)
{
        /* Stupid check for now:
         * Could compare angles of surrounding edges
         * before & after, but this is OK.*/
        return (len_squared_v3v3(e->v1->co, e->v2->co) >
                len_squared_v3v3(l1->v->co, l2->v->co));
}

/**
 * \brief Rotate Edge
 *
 * Spins an edge topologically,
 * either counter-clockwise or clockwise depending on \a ccw.
 *
 * \return The spun edge, NULL on error
 * (e.g., if the edge isn't surrounded by exactly two faces).
 *
 * \note This works by dissolving the edge then re-creating it,
 * so the returned edge won't have the same pointer address as the original one.
 *
 * \see header definition for \a check_flag enum.
 */
BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
{
        BMVert *v1, *v2;
        BMLoop *l1, *l2;
        BMFace *f;
        BMEdge *e_new = NULL;
        char f_hflag_prev_1;
        char f_hflag_prev_2;

        if (!BM_edge_rotate_check(e)) {
                return NULL;
        }

        BM_edge_calc_rotate(e, ccw, &l1, &l2);

        /* the loops will be freed so assign verts */
        v1 = l1->v;
        v2 = l2->v;

        /* --------------------------------------- */
        /* Checking Code - make sure we can rotate */

        if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
                if (!BM_edge_rotate_check_beauty(e, l1, l2)) {
                        return NULL;
                }
        }

        /* check before applying */
        if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
                if (BM_edge_exists(v1, v2)) {
                        return NULL;
                }
        }

        /* slowest, check last */
        if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
                if (!BM_edge_rotate_check_degenerate(e, l1, l2)) {
                        return NULL;
                }
        }
        /* Done Checking */
        /* ------------- */



        /* --------------- */
        /* Rotate The Edge */

        /* first create the new edge, this is so we can copy the customdata from the old one
         * if splice if disabled, always add in a new edge even if theres one there. */
        e_new = BM_edge_create(bm, v1, v2, e, (check_flag & BM_EDGEROT_CHECK_SPLICE) != 0);

        f_hflag_prev_1 = l1->f->head.hflag;
        f_hflag_prev_2 = l2->f->head.hflag;

        /* don't delete the edge, manually remove the edge after so we can copy its attributes */
        f = BM_faces_join_pair(bm, l1->f, l2->f, NULL, true);

        if (f == NULL) {
                return NULL;
        }

        /* note, this assumes joining the faces _didnt_ also remove the verts.
         * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
         * break this */
        if (!BM_face_split(bm, f, v1, v2, NULL, NULL, true)) {
                return NULL;
        }
        else {
                /* we should really be able to know the faces some other way,
                 * rather then fetching them back from the edge, but this is predictable
                 * where using the return values from face split isn't. - campbell */
                BMFace *fa, *fb;
                if (BM_edge_face_pair(e_new, &fa, &fb)) {
                        fa->head.hflag = f_hflag_prev_1;
                        fb->head.hflag = f_hflag_prev_2;
                }
        }

        return e_new;
}

/**
 * \brief Rip a single face from a vertex fan
 */
BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv)
{
        return bmesh_urmv(bm, sf, sv);
}

/**
 * \brief Rip a single face from a vertex fan
 *
 * \note same as #BM_face_vert_separate but faster (avoids a loop lookup)
 */
BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl)
{
        return bmesh_urmv_loop(bm, sl);
}