source/blender/bmesh/tools/bmesh_wireframe.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): Campbell Barton
  19  *
  20  * ***** END GPL LICENSE BLOCK *****
  21  */
  22
  23 /** \file blender/bmesh/operators/bmesh_wireframe.c
  24  *  \ingroup bmesh
  25  *
  26  * Creates a solid wireframe from conected faces.
  27  */
  28
  29 #include "MEM_guardedalloc.h"
  30
  31 #include "DNA_object_types.h"
  32 #include "DNA_meshdata_types.h"
  33
  34 #include "BLI_math.h"
  35
  36 #include "bmesh.h"
  37
  38 #include "BKE_deform.h"
  39 #include "BKE_customdata.h"
  40
  41 #include "bmesh_wireframe.h"
  42
  43 static BMLoop *bm_edge_tag_faceloop(BMEdge *e)
  44 {
  45         BMLoop *l, *l_first;
  46
  47         l = l_first = e->l;
  48         do {
  49                 if (BM_elem_flag_test(l->f, BM_ELEM_TAG)) {
  50                         return l;
  51                 }
  52         } while ((l = l->radial_next) != l_first);
  53
  54         /* in the case this is used, we know this will never happen */
  55         return NULL;
  56 }
  57
  58 static void bm_vert_boundary_tangent(BMVert *v, float r_no[3], float r_no_face[3],
  59                                      BMVert **r_va_other, BMVert **r_vb_other)
  60 {
  61         BMIter iter;
  62         BMEdge *e_iter;
  63
  64         BMEdge *e_a = NULL, *e_b = NULL;
  65         BMVert *v_a, *v_b;
  66
  67         BMLoop *l_a, *l_b;
  68
  69         float no_face[3], no_edge[3];
  70         float tvec_a[3], tvec_b[3];
  71
  72         /* get 2 boundary edges, there should only _be_ 2,
  73          * in case there are more - results wont be valid of course */
  74         BM_ITER_ELEM (e_iter, &iter, v, BM_EDGES_OF_VERT) {
  75                 if (BM_elem_flag_test(e_iter, BM_ELEM_TAG)) {
  76                         if (e_a == NULL) {
  77                                 e_a = e_iter;
  78                         }
  79                         else {
  80                                 e_b = e_iter;
  81                                 break;
  82                         }
  83                 }
  84         }
  85
  86         if (e_a && e_b) {
  87                 /* note, with an incorrectly flushed selection this can crash */
  88                 l_a = bm_edge_tag_faceloop(e_a);
  89                 l_b = bm_edge_tag_faceloop(e_b);
  90
  91                 /* average edge face normal */
  92                 add_v3_v3v3(no_face, l_a->f->no, l_b->f->no);
  93
  94                 /* average edge direction */
  95                 v_a = BM_edge_other_vert(e_a, v);
  96                 v_b = BM_edge_other_vert(e_b, v);
  97
  98                 sub_v3_v3v3(tvec_a, v->co, v_a->co);
  99                 sub_v3_v3v3(tvec_b, v_b->co, v->co);
 100                 normalize_v3(tvec_a);
 101                 normalize_v3(tvec_b);
 102                 add_v3_v3v3(no_edge, tvec_a, tvec_b); /* not unit length but this is ok */
 103
 104                 /* check are we flipped the right way */
 105                 BM_edge_calc_face_tangent(e_a, l_a, tvec_a);
 106                 BM_edge_calc_face_tangent(e_b, l_b, tvec_b);
 107                 add_v3_v3(tvec_a, tvec_b);
 108
 109                 *r_va_other = v_a;
 110                 *r_vb_other = v_b;
 111         }
 112         else {
 113                 /* degenerate case - vertex connects a boundary edged face to other faces,
 114                  * so we have only one boundary face - only use it for calculations */
 115                 l_a = bm_edge_tag_faceloop(e_a);
 116
 117                 copy_v3_v3(no_face, l_a->f->no);
 118
 119                 /* edge direction */
 120                 v_a = BM_edge_other_vert(e_a, v);
 121                 v_b = NULL;
 122
 123                 sub_v3_v3v3(no_edge, v->co, v_a->co);
 124
 125                 /* check are we flipped the right way */
 126                 BM_edge_calc_face_tangent(e_a, l_a, tvec_a);
 127
 128                 *r_va_other = NULL;
 129                 *r_vb_other = NULL;
 130         }
 131
 132         /* find the normal */
 133         cross_v3_v3v3(r_no, no_edge, no_face);
 134         normalize_v3(r_no);
 135
 136         if (dot_v3v3(r_no, tvec_a) > 0.0f) {
 137                 negate_v3(r_no);
 138         }
 139
 140         copy_v3_v3(r_no_face, no_face);
 141 }
 142
 143 /* check if we are the only tagged loop-face around this edge */
 144 static bool bm_loop_is_radial_boundary(BMLoop *l_first)
 145 {
 146         BMLoop *l = l_first->radial_next;
 147
 148         if (l == l_first) {
 149                 return true; /* a real boundary */
 150         }
 151         else {
 152                 do {
 153                         if (BM_elem_flag_test(l->f, BM_ELEM_TAG)) {
 154                                 return false;
 155                         }
 156                 } while ((l = l->radial_next) != l_first);
 157         }
 158         return true;
 159 }
 160
 161 /**
 162  * \param def_nr  -1 for no vertex groups.
 163  *
 164  * \note All edge tags must be cleared.
 165  * \note Behavior matches MOD_solidify.c
 166  */
 167 void BM_mesh_wireframe(
 168         BMesh *bm,
 169         const float offset,
 170         const float offset_fac,
 171         const float offset_fac_vg,
 172         const bool use_replace,
 173         const bool use_boundary,
 174         const bool use_even_offset,
 175         const bool use_relative_offset,
 176         const bool use_crease,
 177         const float crease_weight,
 178         const int defgrp_index,
 179         const bool defgrp_invert,
 180         const short mat_offset,
 181         const short mat_max,
 182         /* for operators */
 183         const bool use_tag
 184         )
 185 {
 186         const float ofs_orig = -(((-offset_fac + 1.0f) * 0.5f) * offset);
 187         const float ofs_new  = offset + ofs_orig;
 188         const float ofs_mid  = (ofs_orig + ofs_new) / 2.0f;
 189         const float inset = offset / 2.0f;
 190         int cd_edge_crease_offset = use_crease ? CustomData_get_offset(&bm->edata, CD_CREASE) : -1;
 191         const int cd_dvert_offset = (defgrp_index != -1) ? CustomData_get_offset(&bm->vdata, CD_MDEFORMVERT) : -1;
 192         const float offset_fac_vg_inv = 1.0f - offset_fac_vg;
 193
 194         const int totvert_orig = bm->totvert;
 195
 196         BMIter iter;
 197         BMIter itersub;
 198
 199         /* filled only with boundary verts */
 200         BMVert **verts_src      = MEM_mallocN(sizeof(BMVert *) * totvert_orig, __func__);
 201         BMVert **verts_neg      = MEM_mallocN(sizeof(BMVert *) * totvert_orig, __func__);
 202         BMVert **verts_pos      = MEM_mallocN(sizeof(BMVert *) * totvert_orig, __func__);
 203
 204         /* will over-alloc, but makes for easy lookups by index to keep aligned  */
 205         BMVert **verts_boundary = use_boundary ?
 206                                   MEM_mallocN(sizeof(BMVert *) * totvert_orig, __func__) : NULL;
 207
 208         float  *verts_relfac    = (use_relative_offset || (cd_dvert_offset != -1)) ?
 209                                   MEM_mallocN(sizeof(float) * totvert_orig, __func__) : NULL;
 210
 211         /* may over-alloc if not all faces have wire */
 212         BMVert **verts_loop;
 213         int verts_loop_tot = 0;
 214
 215         BMVert *v_src;
 216
 217         BMFace *f_src;
 218         BMLoop *l;
 219
 220         float tvec[3];
 221         float fac, fac_shell;
 222
 223         int i;
 224
 225         if (use_crease && cd_edge_crease_offset == -1) {
 226                 BM_data_layer_add(bm, &bm->edata, CD_CREASE);
 227                 cd_edge_crease_offset = CustomData_get_offset(&bm->edata, CD_CREASE);
 228         }
 229
 230         BM_mesh_elem_index_ensure(bm, BM_VERT);
 231
 232         BM_ITER_MESH_INDEX (v_src, &iter, bm, BM_VERTS_OF_MESH, i) {
 233                 BM_elem_flag_disable(v_src, BM_ELEM_TAG);
 234                 verts_src[i] = v_src;
 235         }
 236
 237         /* setup tags, all faces and verts will be tagged which will be duplicated */
 238
 239         BM_ITER_MESH (f_src, &iter, bm, BM_FACES_OF_MESH) {
 240
 241                 if (use_tag) {
 242                         if (!BM_elem_flag_test(f_src, BM_ELEM_TAG)) {
 243                                 continue;
 244                         }
 245                 }
 246                 else {
 247                         BM_elem_flag_enable(f_src, BM_ELEM_TAG);
 248                 }
 249
 250
 251                 verts_loop_tot += f_src->len;
 252                 BM_ITER_ELEM (l, &itersub, f_src, BM_LOOPS_OF_FACE) {
 253                         BM_elem_flag_enable(l->v, BM_ELEM_TAG);
 254
 255                         /* also tag boundary edges */
 256                         BM_elem_flag_set(l->e, BM_ELEM_TAG, bm_loop_is_radial_boundary(l));
 257                 }
 258         }
 259
 260         /* duplicate tagged verts */
 261         for (i = 0; i < totvert_orig; i++) {
 262                 v_src = verts_src[i];
 263                 if (BM_elem_flag_test(v_src, BM_ELEM_TAG)) {
 264                         fac = 1.0f;
 265
 266                         if (verts_relfac) {
 267                                 if (use_relative_offset) {
 268                                         verts_relfac[i] = BM_vert_calc_mean_tagged_edge_length(v_src);
 269                                 }
 270                                 else {
 271                                         verts_relfac[i] = 1.0f;
 272                                 }
 273
 274
 275                                 if (cd_dvert_offset != -1) {
 276                                         MDeformVert *dvert = BM_ELEM_CD_GET_VOID_P(v_src, cd_dvert_offset);
 277                                         float defgrp_fac = defvert_find_weight(dvert, defgrp_index);
 278
 279                                         if (defgrp_invert) {
 280                                                 defgrp_fac = 1.0f - defgrp_fac;
 281                                         }
 282
 283                                         if (offset_fac_vg > 0.0f) {
 284                                                 defgrp_fac = (offset_fac_vg + (defgrp_fac * offset_fac_vg_inv));
 285                                         }
 286
 287                                         verts_relfac[i] *= defgrp_fac;
 288                                 }
 289
 290                                 fac *= verts_relfac[i];
 291                         }
 292
 293
 294                         verts_neg[i] = BM_vert_create(bm, NULL, v_src, BM_CREATE_NOP);
 295                         verts_pos[i] = BM_vert_create(bm, NULL, v_src, BM_CREATE_NOP);
 296
 297                         if (offset == 0.0f) {
 298                                 madd_v3_v3v3fl(verts_neg[i]->co, v_src->co, v_src->no, ofs_orig * fac);
 299                                 madd_v3_v3v3fl(verts_pos[i]->co, v_src->co, v_src->no,  ofs_new * fac);
 300                         }
 301                         else {
 302                                 madd_v3_v3v3fl(tvec, v_src->co, v_src->no, ofs_mid * fac);
 303
 304                                 madd_v3_v3v3fl(verts_neg[i]->co, tvec, v_src->no, (ofs_mid - ofs_orig) * fac);
 305                                 madd_v3_v3v3fl(verts_pos[i]->co, tvec, v_src->no,  (ofs_mid - ofs_new) * fac);
 306                         }
 307                 }
 308                 else {
 309                         /* could skip this */
 310                         verts_neg[i] = NULL;
 311                         verts_pos[i] = NULL;
 312                 }
 313
 314                 /* conflicts with BM_vert_calc_mean_tagged_edge_length */
 315                 if (use_relative_offset == false) {
 316                         BM_elem_flag_disable(v_src, BM_ELEM_TAG);
 317                 }
 318         }
 319
 320         if (use_relative_offset) {
 321                 BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, false);
 322         }
 323
 324         verts_loop = MEM_mallocN(sizeof(BMVert *) * verts_loop_tot, __func__);
 325         verts_loop_tot = 0; /* count up again */
 326
 327         BM_ITER_MESH (f_src, &iter, bm, BM_FACES_OF_MESH) {
 328
 329                 if (use_tag && !BM_elem_flag_test(f_src, BM_ELEM_TAG)) {
 330                         continue;
 331                 }
 332
 333                 BM_ITER_ELEM (l, &itersub, f_src, BM_LOOPS_OF_FACE) {
 334                         BM_elem_index_set(l, verts_loop_tot); /* set_loop */
 335
 336                         BM_loop_calc_face_tangent(l, tvec);
 337
 338                         /* create offset vert */
 339                         fac = 1.0f;
 340
 341                         if (verts_relfac) {
 342                                 fac *= verts_relfac[BM_elem_index_get(l->v)];
 343                         }
 344
 345                         fac_shell = fac;
 346                         if (use_even_offset) {
 347                                 fac_shell *= shell_angle_to_dist(((float)M_PI - BM_loop_calc_face_angle(l)) * 0.5f);
 348                         }
 349
 350
 351                         madd_v3_v3v3fl(tvec, l->v->co, tvec, inset * fac_shell);
 352                         if (offset != 0.0f) {
 353                                 madd_v3_v3fl(tvec, l->v->no, ofs_mid * fac);
 354                         }
 355                         verts_loop[verts_loop_tot] = BM_vert_create(bm, tvec, l->v, BM_CREATE_NOP);
 356
 357
 358                         if (use_boundary) {
 359                                 if (BM_elem_flag_test(l->e, BM_ELEM_TAG)) {  /* is this a boundary? */
 360                                         BMVert *v_pair[2] = {l->v, l->next->v};
 361
 362                                         for (i = 0; i < 2; i++) {
 363                                                 BMVert *v_boundary = v_pair[i];
 364                                                 if (!BM_elem_flag_test(v_boundary, BM_ELEM_TAG)) {
 365                                                         const int v_boundary_index = BM_elem_index_get(v_boundary);
 366                                                         float no_face[3];
 367                                                         BMVert *va_other;
 368                                                         BMVert *vb_other;
 369
 370                                                         BM_elem_flag_enable(v_boundary, BM_ELEM_TAG);
 371
 372                                                         bm_vert_boundary_tangent(v_boundary, tvec, no_face, &va_other, &vb_other);
 373
 374                                                         /* create offset vert */
 375                                                         /* similar to code above but different angle calc */
 376                                                         fac = 1.0f;
 377
 378                                                         if (verts_relfac) {
 379                                                                 fac *= verts_relfac[v_boundary_index];
 380                                                         }
 381
 382                                                         fac_shell = fac;
 383                                                         if (use_even_offset) {
 384                                                                 if (va_other) {  /* for verts with only one boundary edge - this will be NULL */
 385                                                                         fac_shell *= shell_angle_to_dist(((float)M_PI -
 386                                                                                                           angle_on_axis_v3v3v3_v3(va_other->co,
 387                                                                                                                                   v_boundary->co,
 388                                                                                                                                   vb_other->co,
 389                                                                                                                                   no_face)) * 0.5f);
 390                                                                 }
 391                                                         }
 392
 393
 394                                                         madd_v3_v3v3fl(tvec, v_boundary->co, tvec, inset * fac_shell);
 395                                                         if (offset != 0.0f) {
 396                                                                 madd_v3_v3fl(tvec, v_boundary->no, ofs_mid * fac);
 397                                                         }
 398                                                         verts_boundary[v_boundary_index] = BM_vert_create(bm, tvec, v_boundary, BM_CREATE_NOP);
 399                                                 }
 400                                         }
 401                                 }
 402                         }
 403
 404                         verts_loop_tot++;
 405                 }
 406         }
 407
 408         BM_ITER_MESH (f_src, &iter, bm, BM_FACES_OF_MESH) {
 409
 410                 /* skip recently added faces */
 411                 if (BM_elem_index_get(f_src) == -1) {
 412                         continue;
 413                 }
 414
 415                 if (use_tag && !BM_elem_flag_test(f_src, BM_ELEM_TAG)) {
 416                         continue;
 417                 }
 418
 419                 BM_elem_flag_disable(f_src, BM_ELEM_TAG);
 420
 421                 BM_ITER_ELEM (l, &itersub, f_src, BM_LOOPS_OF_FACE) {
 422                         BMFace *f_new;
 423                         BMLoop *l_new;
 424                         BMLoop *l_next = l->next;
 425                         BMVert *v_l1 = verts_loop[BM_elem_index_get(l)];
 426                         BMVert *v_l2 = verts_loop[BM_elem_index_get(l_next)];
 427
 428                         BMVert *v_src_l1 = l->v;
 429                         BMVert *v_src_l2 = l_next->v;
 430
 431                         const int i_1 = BM_elem_index_get(v_src_l1);
 432                         const int i_2 = BM_elem_index_get(v_src_l2);
 433
 434                         BMVert *v_neg1 = verts_neg[i_1];
 435                         BMVert *v_neg2 = verts_neg[i_2];
 436
 437                         BMVert *v_pos1 = verts_pos[i_1];
 438                         BMVert *v_pos2 = verts_pos[i_2];
 439
 440                         f_new = BM_face_create_quad_tri(bm, v_l1, v_l2, v_neg2, v_neg1, f_src, false);
 441                         if (mat_offset) f_new->mat_nr = CLAMPIS(f_new->mat_nr + mat_offset, 0, mat_max);
 442                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
 443                         l_new = BM_FACE_FIRST_LOOP(f_new);
 444
 445                         BM_elem_attrs_copy(bm, bm, l,      l_new);
 446                         BM_elem_attrs_copy(bm, bm, l,      l_new->prev);
 447                         BM_elem_attrs_copy(bm, bm, l_next, l_new->next);
 448                         BM_elem_attrs_copy(bm, bm, l_next, l_new->next->next);
 449
 450                         f_new = BM_face_create_quad_tri(bm, v_l2, v_l1, v_pos1, v_pos2, f_src, false);
 451
 452                         if (mat_offset) f_new->mat_nr = CLAMPIS(f_new->mat_nr + mat_offset, 0, mat_max);
 453                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
 454                         l_new = BM_FACE_FIRST_LOOP(f_new);
 455
 456                         BM_elem_attrs_copy(bm, bm, l_next, l_new);
 457                         BM_elem_attrs_copy(bm, bm, l_next, l_new->prev);
 458                         BM_elem_attrs_copy(bm, bm, l,      l_new->next);
 459                         BM_elem_attrs_copy(bm, bm, l,      l_new->next->next);
 460
 461                         if (use_boundary) {
 462                                 if (BM_elem_flag_test(l->e, BM_ELEM_TAG)) {
 463                                         /* we know its a boundary and this is the only face user (which is being wire'd) */
 464                                         /* we know we only touch this edge/face once */
 465                                         BMVert *v_b1 = verts_boundary[i_1];
 466                                         BMVert *v_b2 = verts_boundary[i_2];
 467
 468                                         f_new = BM_face_create_quad_tri(bm, v_b2, v_b1, v_neg1, v_neg2, f_src, false);
 469                                         if (mat_offset) f_new->mat_nr = CLAMPIS(f_new->mat_nr + mat_offset, 0, mat_max);
 470                                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
 471                                         l_new = BM_FACE_FIRST_LOOP(f_new);
 472
 473                                         BM_elem_attrs_copy(bm, bm, l_next, l_new);
 474                                         BM_elem_attrs_copy(bm, bm, l_next, l_new->prev);
 475                                         BM_elem_attrs_copy(bm, bm, l,      l_new->next);
 476                                         BM_elem_attrs_copy(bm, bm, l,      l_new->next->next);
 477
 478                                         f_new = BM_face_create_quad_tri(bm, v_b1, v_b2, v_pos2, v_pos1, f_src, false);
 479                                         if (mat_offset) f_new->mat_nr = CLAMPIS(f_new->mat_nr + mat_offset, 0, mat_max);
 480                                         BM_elem_flag_enable(f_new, BM_ELEM_TAG);
 481                                         l_new = BM_FACE_FIRST_LOOP(f_new);
 482
 483                                         BM_elem_attrs_copy(bm, bm, l,      l_new);
 484                                         BM_elem_attrs_copy(bm, bm, l,      l_new->prev);
 485                                         BM_elem_attrs_copy(bm, bm, l_next, l_new->next);
 486                                         BM_elem_attrs_copy(bm, bm, l_next, l_new->next->next);
 487
 488                                         if (use_crease) {
 489                                                 BMEdge *e_new;
 490                                                 e_new = BM_edge_exists(v_pos1, v_b1);
 491                                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 492
 493                                                 e_new = BM_edge_exists(v_pos2, v_b2);
 494                                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 495
 496                                                 e_new = BM_edge_exists(v_neg1, v_b1);
 497                                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 498
 499                                                 e_new = BM_edge_exists(v_neg2, v_b2);
 500                                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 501                                         }
 502                                 }
 503                         }
 504
 505                         if (use_crease) {
 506                                 BMEdge *e_new;
 507                                 e_new = BM_edge_exists(v_pos1, v_l1);
 508                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 509
 510                                 e_new = BM_edge_exists(v_pos2, v_l2);
 511                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 512
 513                                 e_new = BM_edge_exists(v_neg1, v_l1);
 514                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 515
 516                                 e_new = BM_edge_exists(v_neg2, v_l2);
 517                                 BM_ELEM_CD_SET_FLOAT(e_new, cd_edge_crease_offset, crease_weight);
 518                         }
 519
 520                 }
 521         }
 522
 523         if (use_boundary) {
 524                 MEM_freeN(verts_boundary);
 525         }
 526
 527         if (verts_relfac) {
 528                 MEM_freeN(verts_relfac);
 529         }
 530
 531         if (use_replace) {
 532                 for (i = 0; i < totvert_orig; i++) {
 533                         BM_vert_kill(bm, verts_src[i]);
 534                 }
 535         }
 536
 537         MEM_freeN(verts_src);
 538         MEM_freeN(verts_neg);
 539         MEM_freeN(verts_pos);
 540         MEM_freeN(verts_loop);
 541 }