source/blender/bmesh/operators/bmo_connect.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  * Connect verts across faces (splits faces).
  21  */
  22
  23 #include "BLI_alloca.h"
  24 #include "BLI_linklist_stack.h"
  25 #include "BLI_utildefines.h"
  26 #include "BLI_utildefines_stack.h"
  27
  28 #include "bmesh.h"
  29
  30 #include "intern/bmesh_operators_private.h" /* own include */
  31
  32 #define VERT_INPUT 1
  33
  34 #define EDGE_OUT 1
  35 /* Edge spans 2 VERT_INPUT's, its a nop,
  36  * but include in "edges.out" */
  37 #define EDGE_OUT_ADJ 2
  38
  39 #define FACE_TAG 2
  40 #define FACE_EXCLUDE 4
  41
  42 static int bm_face_connect_verts(BMesh *bm, BMFace *f, const bool check_degenerate)
  43 {
  44   const uint pair_split_max = f->len / 2;
  45   BMLoop *(*loops_split)[2] = BLI_array_alloca(loops_split, pair_split_max);
  46   STACK_DECLARE(loops_split);
  47   BMVert *(*verts_pair)[2] = BLI_array_alloca(verts_pair, pair_split_max);
  48   STACK_DECLARE(verts_pair);
  49
  50   BMLoop *l_tag_prev = NULL, *l_tag_first = NULL;
  51   BMLoop *l_iter, *l_first;
  52   uint i;
  53   int result = 1;
  54
  55   STACK_INIT(loops_split, pair_split_max);
  56   STACK_INIT(verts_pair, pair_split_max);
  57
  58   l_iter = l_first = BM_FACE_FIRST_LOOP(f);
  59   do {
  60     if (BMO_vert_flag_test(bm, l_iter->v, VERT_INPUT) &&
  61         /* ensure this vertex isnt part of a contiguous group */
  62         ((BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT) == 0) ||
  63          (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT) == 0))) {
  64       if (!l_tag_prev) {
  65         l_tag_prev = l_tag_first = l_iter;
  66         continue;
  67       }
  68
  69       if (!BM_loop_is_adjacent(l_tag_prev, l_iter)) {
  70         BMEdge *e;
  71         e = BM_edge_exists(l_tag_prev->v, l_iter->v);
  72         if (e == NULL || !BMO_edge_flag_test(bm, e, EDGE_OUT)) {
  73           BMLoop **l_pair = STACK_PUSH_RET(loops_split);
  74           l_pair[0] = l_tag_prev;
  75           l_pair[1] = l_iter;
  76         }
  77       }
  78
  79       l_tag_prev = l_iter;
  80     }
  81   } while ((l_iter = l_iter->next) != l_first);
  82
  83   if (STACK_SIZE(loops_split) == 0) {
  84     return 0;
  85   }
  86
  87   if (!BM_loop_is_adjacent(l_tag_first, l_tag_prev) &&
  88       /* ensure we don't add the same pair twice */
  89       (((loops_split[0][0] == l_tag_first) && (loops_split[0][1] == l_tag_prev)) == 0)) {
  90     BMLoop **l_pair = STACK_PUSH_RET(loops_split);
  91     l_pair[0] = l_tag_first;
  92     l_pair[1] = l_tag_prev;
  93   }
  94
  95   if (check_degenerate) {
  96     BM_face_splits_check_legal(bm, f, loops_split, STACK_SIZE(loops_split));
  97   }
  98   else {
  99     BM_face_splits_check_optimal(f, loops_split, STACK_SIZE(loops_split));
 100   }
 101
 102   for (i = 0; i < STACK_SIZE(loops_split); i++) {
 103     BMVert **v_pair;
 104     if (loops_split[i][0] == NULL) {
 105       continue;
 106     }
 107
 108     v_pair = STACK_PUSH_RET(verts_pair);
 109     v_pair[0] = loops_split[i][0]->v;
 110     v_pair[1] = loops_split[i][1]->v;
 111   }
 112
 113   /* Clear and re-use to store duplicate faces, to remove after splitting is finished. */
 114   STACK_CLEAR(loops_split);
 115
 116   for (i = 0; i < STACK_SIZE(verts_pair); i++) {
 117     BMFace *f_new;
 118     BMLoop *l_new;
 119     BMLoop *l_pair[2];
 120
 121     /* Note that duplicate edges in this case is very unlikely but it can happen, see T70287. */
 122     bool edge_exists = (BM_edge_exists(verts_pair[i][0], verts_pair[i][1]) != NULL);
 123     if ((l_pair[0] = BM_face_vert_share_loop(f, verts_pair[i][0])) &&
 124         (l_pair[1] = BM_face_vert_share_loop(f, verts_pair[i][1]))) {
 125       f_new = BM_face_split(bm, f, l_pair[0], l_pair[1], &l_new, NULL, edge_exists);
 126
 127       /* Check if duplicate faces have been created, store the loops for removal in this case.
 128        * Note that this matches how triangulate works (newly created duplicates get removed). */
 129       if (UNLIKELY(edge_exists)) {
 130         BMLoop **l_pair_deferred_remove = NULL;
 131         for (int j = 0; j < 2; j++) {
 132           if (BM_face_find_double(l_pair[j]->f)) {
 133             if (l_pair_deferred_remove == NULL) {
 134               l_pair_deferred_remove = STACK_PUSH_RET(loops_split);
 135               l_pair_deferred_remove[0] = NULL;
 136               l_pair_deferred_remove[1] = NULL;
 137             }
 138             l_pair_deferred_remove[j] = l_pair[j];
 139           }
 140         }
 141       }
 142     }
 143     else {
 144       f_new = NULL;
 145       l_new = NULL;
 146     }
 147
 148     if (!l_new || !f_new) {
 149       result = -1;
 150       break;
 151     }
 152
 153     f = f_new;
 154     // BMO_face_flag_enable(bm, f_new, FACE_NEW);
 155     BMO_edge_flag_enable(bm, l_new->e, EDGE_OUT);
 156   }
 157
 158   for (i = 0; i < STACK_SIZE(loops_split); i++) {
 159     for (int j = 0; j < 2; j++) {
 160       if (loops_split[i][j] != NULL) {
 161         BM_face_kill(bm, loops_split[i][j]->f);
 162       }
 163     }
 164   }
 165
 166   return result;
 167 }
 168
 169 void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
 170 {
 171   BMOIter siter;
 172   BMVert *v;
 173   BMFace *f;
 174   const bool check_degenerate = BMO_slot_bool_get(op->slots_in, "check_degenerate");
 175   BLI_LINKSTACK_DECLARE(faces, BMFace *);
 176
 177   BLI_LINKSTACK_INIT(faces);
 178
 179   /* tag so we won't touch ever (typically hidden faces) */
 180   BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces_exclude", BM_FACE, FACE_EXCLUDE);
 181
 182   /* add all faces connected to verts */
 183   BMO_ITER (v, &siter, op->slots_in, "verts", BM_VERT) {
 184     BMIter iter;
 185     BMLoop *l_iter;
 186
 187     BMO_vert_flag_enable(bm, v, VERT_INPUT);
 188     BM_ITER_ELEM (l_iter, &iter, v, BM_LOOPS_OF_VERT) {
 189       f = l_iter->f;
 190       if (!BMO_face_flag_test(bm, f, FACE_EXCLUDE)) {
 191         if (!BMO_face_flag_test(bm, f, FACE_TAG)) {
 192           BMO_face_flag_enable(bm, f, FACE_TAG);
 193           if (f->len > 3) {
 194             BLI_LINKSTACK_PUSH(faces, f);
 195           }
 196         }
 197       }
 198
 199       /* flag edges even if these are not newly created
 200        * this way cut-pairs that include co-linear edges will get
 201        * predictable output. */
 202       if (BMO_vert_flag_test(bm, l_iter->prev->v, VERT_INPUT)) {
 203         BMO_edge_flag_enable(bm, l_iter->prev->e, EDGE_OUT_ADJ);
 204       }
 205       if (BMO_vert_flag_test(bm, l_iter->next->v, VERT_INPUT)) {
 206         BMO_edge_flag_enable(bm, l_iter->e, EDGE_OUT_ADJ);
 207       }
 208     }
 209   }
 210
 211   /* connect faces */
 212   while ((f = BLI_LINKSTACK_POP(faces))) {
 213     if (bm_face_connect_verts(bm, f, check_degenerate) == -1) {
 214       BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
 215     }
 216   }
 217
 218   BLI_LINKSTACK_FREE(faces);
 219
 220   BMO_slot_buffer_from_enabled_flag(
 221       bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT | EDGE_OUT_ADJ);
 222 }