source/blender/blenkernel/intern/BME_tools.c

   1 /*
   2  * BME_tools.c    jan 2007
   3  *
   4  *      Functions for changing the topology of a mesh.
   5  *
   6  *
   7  * ***** BEGIN GPL LICENSE BLOCK *****
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version 2
  12  * of the License, or (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software Foundation,
  21  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  22  *
  23  * The Original Code is Copyright (C) 2004 Blender Foundation.
  24  * All rights reserved.
  25  *
  26  * The Original Code is: all of this file.
  27  *
  28  * Contributor(s): Geoffrey Bantle and Levi Schooley.
  29  *
  30  * ***** END GPL LICENSE BLOCK *****
  31  */
  32
  33 /** \file blender/blenkernel/intern/BME_tools.c
  34  *  \ingroup bke
  35  */
  36
  37
  38 #include <math.h>
  39
  40 #include "MEM_guardedalloc.h"
  41
  42 #include "DNA_meshdata_types.h"
  43 #include "DNA_object_types.h"
  44
  45 #include "BLI_math.h"
  46 #include "BLI_utildefines.h"
  47
  48 #include "BKE_bmesh.h"
  49
  50 /*split this all into a seperate bevel.c file in src*/
  51
  52 /* ------- Bevel code starts here -------- */
  53
  54 BME_TransData_Head *BME_init_transdata(int bufsize) {
  55         BME_TransData_Head *td;
  56
  57         td = MEM_callocN(sizeof(BME_TransData_Head), "BMesh transdata header");
  58         td->gh = BLI_ghash_new(BLI_ghashutil_ptrhash,BLI_ghashutil_ptrcmp, "BME_init_transdata gh");
  59         td->ma = BLI_memarena_new(bufsize, "BME_TransData arena");
  60         BLI_memarena_use_calloc(td->ma);
  61
  62         return td;
  63 }
  64
  65 void BME_free_transdata(BME_TransData_Head *td) {
  66         BLI_ghash_free(td->gh,NULL,NULL);
  67         BLI_memarena_free(td->ma);
  68         MEM_freeN(td);
  69 }
  70
  71 BME_TransData *BME_assign_transdata(
  72         BME_TransData_Head *td, BME_Mesh *bm, BME_Vert *v,
  73         float *co, float *org, float *vec, float *loc,
  74         float factor, float weight, float maxfactor, float *max)
  75 {
  76         BME_TransData *vtd;
  77         int is_new = 0;
  78
  79         if (v == NULL) return NULL;
  80
  81         if ((vtd = BLI_ghash_lookup(td->gh, v)) == NULL && bm != NULL) {
  82                 vtd = BLI_memarena_alloc(td->ma, sizeof(*vtd));
  83                 BLI_ghash_insert(td->gh, v, vtd);
  84                 td->len++;
  85                 is_new = 1;
  86         }
  87
  88         vtd->bm = bm;
  89         vtd->v = v;
  90
  91         if (co != NULL) {
  92                 copy_v3_v3(vtd->co, co);
  93         }
  94
  95         if (org == NULL && is_new) {
  96                 copy_v3_v3(vtd->org, v->co); /* default */
  97         }
  98         else if (org != NULL) {
  99                 copy_v3_v3(vtd->org,org);
 100         }
 101
 102         if (vec != NULL) {
 103                 copy_v3_v3(vtd->vec,vec);
 104                 normalize_v3(vtd->vec);
 105         }
 106
 107         vtd->loc = loc;
 108
 109         vtd->factor = factor;
 110         vtd->weight = weight;
 111         vtd->maxfactor = maxfactor;
 112         vtd->max = max;
 113
 114         return vtd;
 115 }
 116
 117 BME_TransData *BME_get_transdata(BME_TransData_Head *td, BME_Vert *v) {
 118         BME_TransData *vtd;
 119         vtd = BLI_ghash_lookup(td->gh, v);
 120         return vtd;
 121 }
 122
 123 /* a hack (?) to use the transdata memarena to allocate floats for use with the max limits */
 124 float *BME_new_transdata_float(BME_TransData_Head *td) {
 125         return BLI_memarena_alloc(td->ma, sizeof(float));
 126 }
 127
 128 static int BME_is_nonmanifold_vert(BME_Mesh *UNUSED(bm), BME_Vert *v) {
 129         BME_Edge *e, *oe;
 130         BME_Loop *l;
 131         int len, count, flag;
 132
 133         if (v->edge == NULL) {
 134                 /* loose vert */
 135                 return 1;
 136         }
 137
 138         /* count edges while looking for non-manifold edges */
 139         oe = v->edge;
 140         for (len=0,e=v->edge; e != oe || (e == oe && len == 0); len++,e=BME_disk_nextedge(e,v)) {
 141                 if (e->loop == NULL) {
 142                         /* loose edge */
 143                         return 1;
 144                 }
 145
 146                 if (BME_cycle_length(&(e->loop->radial)) > 2) {
 147                         /* edge shared by more than two faces */
 148                         return 1;
 149                 }
 150         }
 151
 152         count = 1;
 153         flag = 1;
 154         e = NULL;
 155         oe = v->edge;
 156         l = oe->loop;
 157         while(e != oe) {
 158                 if (l->v == v) l = l->prev;
 159                 else l = l->next;
 160                 e = l->e;
 161                 count++; /* count the edges */
 162
 163                 if (flag && l->radial.next->data == l) {
 164                         /* we've hit the edge of an open mesh, reset once */
 165                         flag = 0;
 166                         count = 1;
 167                         oe = e;
 168                         e = NULL;
 169                         l = oe->loop;
 170                 }
 171                 else if (l->radial.next->data == l) {
 172                         /* break the loop */
 173                         e = oe;
 174                 }
 175                 else {
 176                         l = l->radial.next->data;
 177                 }
 178         }
 179
 180         if (count < len) {
 181                 /* vert shared by multiple regions */
 182                 return 1;
 183         }
 184
 185         return 0;
 186 }
 187
 188 /* a wrapper for BME_JFKE that [for now just] checks to
 189  * make sure loop directions are compatible */
 190 static BME_Poly *BME_JFKE_safe(BME_Mesh *bm, BME_Poly *f1, BME_Poly *f2, BME_Edge *e) {
 191         BME_Loop *l1, *l2;
 192
 193         l1 = e->loop;
 194         l2 = l1->radial.next->data;
 195         if (l1->v == l2->v) {
 196                 BME_loop_reverse(bm, f2);
 197         }
 198
 199         return BME_JFKE(bm, f1, f2, e);
 200 }
 201
 202 /* a wrapper for BME_SFME that transfers element flags */
 203 static BME_Poly *BME_split_face(BME_Mesh *bm, BME_Poly *f, BME_Vert *v1, BME_Vert *v2, BME_Loop **nl, BME_Edge *example) {
 204         BME_Poly *nf;
 205         nf = BME_SFME(bm,f,v1,v2,nl);
 206         nf->flag = f->flag;
 207         /* if the edge was selected, select this face, too */
 208         if (example && (example->flag & SELECT)) f->flag |= ME_FACE_SEL;
 209         nf->h = f->h;
 210         nf->mat_nr = f->mat_nr;
 211         if (nl && example) {
 212                 (*nl)->e->flag = example->flag;
 213                 (*nl)->e->h = example->h;
 214                 (*nl)->e->crease = example->crease;
 215                 (*nl)->e->bweight = example->bweight;
 216         }
 217
 218         return nf;
 219 }
 220
 221
 222 #if 0
 223 static void BME_data_interp_from_verts(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Vert *v, float fac)
 224 {
 225         void *src[2];
 226         float w[2];
 227         if (v1->data && v2->data) {
 228                 src[0]= v1->data;
 229                 src[1]= v2->data;
 230                 w[0] = 1.0f-fac;
 231                 w[1] = fac;
 232                 CustomData_bmesh_interp(&bm->vdata, src, w, NULL, 2, v->data);
 233         }
 234 }
 235 #endif
 236
 237
 238 static void BME_data_facevert_edgesplit(BME_Mesh *bm, BME_Vert *v1, BME_Vert *UNUSED(v2), BME_Vert *v, BME_Edge *e1, float fac){
 239         void *src[2];
 240         float w[2];
 241         BME_Loop *l=NULL, *v1loop = NULL, *vloop = NULL, *v2loop = NULL;
 242
 243         w[0] = 1.0f - fac;
 244         w[1] = fac;
 245
 246         if(!e1->loop) return;
 247         l = e1->loop;
 248         do{
 249                 if(l->v == v1){
 250                         v1loop = l;
 251                         vloop = v1loop->next;
 252                         v2loop = vloop->next;
 253                 }else if(l->v == v){
 254                         v1loop = l->next;
 255                         vloop = l;
 256                         v2loop = l->prev;
 257
 258                 }
 259
 260                 src[0] = v1loop->data;
 261                 src[1] = v2loop->data;
 262
 263                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, vloop->data);
 264                 l = l->radial.next->data;
 265         }while(l!=e1->loop);
 266 }
 267
 268
 269 /* a wrapper for BME_SEMV that transfers element flags */ /*add custom data interpolation in here!*/
 270 static BME_Vert *BME_split_edge(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Edge **ne, float percent) {
 271         BME_Vert *nv, *v2;
 272         float len;
 273
 274         v2 = BME_edge_getothervert(e,v);
 275         nv = BME_SEMV(bm,v,e,ne);
 276         if (nv == NULL) return NULL;
 277         VECSUB(nv->co,v2->co,v->co);
 278         len = len_v3(nv->co);
 279         VECADDFAC(nv->co,v->co,nv->co,len*percent);
 280         nv->flag = v->flag;
 281         nv->bweight = v->bweight;
 282         if (ne) {
 283                 (*ne)->flag = e->flag;
 284                 (*ne)->h = e->h;
 285                 (*ne)->crease = e->crease;
 286                 (*ne)->bweight = e->bweight;
 287         }
 288         /*v->nv->v2*/
 289         BME_data_facevert_edgesplit(bm,v2, v, nv, e, 0.75);
 290         return nv;
 291 }
 292
 293 static void BME_collapse_vert(BME_Mesh *bm, BME_Edge *ke, BME_Vert *kv, float fac){
 294         void *src[2];
 295         float w[2];
 296         BME_Loop *l=NULL, *kvloop=NULL, *tvloop=NULL;
 297         BME_Vert *tv = BME_edge_getothervert(ke,kv);
 298
 299         w[0] = 1.0f - fac;
 300         w[1] = fac;
 301
 302         if(ke->loop){
 303                 l = ke->loop;
 304                 do{
 305                         if(l->v == tv && l->next->v == kv){
 306                                 tvloop = l;
 307                                 kvloop = l->next;
 308
 309                                 src[0] = kvloop->data;
 310                                 src[1] = tvloop->data;
 311                                 CustomData_bmesh_interp(&bm->ldata, src,w, NULL, 2, kvloop->data);
 312                         }
 313                         l=l->radial.next->data;
 314                 }while(l!=ke->loop);
 315         }
 316         BME_JEKV(bm,ke,kv);
 317 }
 318
 319
 320
 321 static int BME_bevel_is_split_vert(BME_Loop *l) {
 322         /* look for verts that have already been added to the edge when
 323          * beveling other polys; this can be determined by testing the
 324          * vert and the edges around it for originality
 325          */
 326         if ((l->v->tflag1 & BME_BEVEL_ORIG)==0
 327                         && (l->e->tflag1 & BME_BEVEL_ORIG)
 328                         && (l->prev->e->tflag1 & BME_BEVEL_ORIG))
 329         {
 330                 return 1;
 331         }
 332         return 0;
 333 }
 334
 335 /* get a vector, vec, that points from v1->co to wherever makes sense to
 336  * the bevel operation as a whole based on the relationship between v1 and v2
 337  * (won't necessarily be a vec from v1->co to v2->co, though it probably will be);
 338  * the return value is -1 for failure, 0 if we used vert co's, and 1 if we used transform origins */
 339 static int BME_bevel_get_vec(float *vec, BME_Vert *v1, BME_Vert *v2, BME_TransData_Head *td)
 340 {
 341         BME_TransData *vtd1, *vtd2;
 342
 343         vtd1 = BME_get_transdata(td,v1);
 344         vtd2 = BME_get_transdata(td,v2);
 345         if (!vtd1 || !vtd2) {
 346                 //printf("BME_bevel_get_vec() got called without proper BME_TransData\n");
 347                 return -1;
 348         }
 349
 350         /* compare the transform origins to see if we can use the vert co's;
 351          * if they belong to different origins, then we will use the origins to determine
 352          * the vector */
 353         if (compare_v3v3(vtd1->org,vtd2->org,0.000001f)) {
 354                 sub_v3_v3v3(vec, v2->co, v1->co);
 355                 if (len_v3(vec) < 0.000001f) {
 356                         zero_v3(vec);
 357                 }
 358                 return 0;
 359         }
 360         else {
 361                 sub_v3_v3v3(vec,vtd2->org,vtd1->org);
 362                 if (len_v3(vec) < 0.000001f) {
 363                         zero_v3(vec);
 364                 }
 365                 return 1;
 366         }
 367 }
 368
 369 /* "Projects" a vector perpendicular to vec2 against vec1, such that
 370  * the projected vec1 + vec2 has a min distance of 1 from the "edge" defined by vec2.
 371  * note: the direction, is_forward, is used in conjunction with up_vec to determine
 372  * whether this is a convex or concave corner. If it is a concave corner, it will
 373  * be projected "backwards." If vec1 is before vec2, is_forward should be 0 (we are projecting backwards).
 374  * vec1 is the vector to project onto (expected to be normalized)
 375  * vec2 is the direction of projection (pointing away from vec1)
 376  * up_vec is used for orientation (expected to be normalized)
 377  * returns the length of the projected vector that lies along vec1 */
 378 static float BME_bevel_project_vec(float *vec1, float *vec2, float *up_vec, int is_forward, BME_TransData_Head *UNUSED(td))
 379 {
 380         float factor, vec3[3], tmp[3],c1,c2;
 381
 382         cross_v3_v3v3(tmp,vec1,vec2);
 383         normalize_v3(tmp);
 384         factor = dot_v3v3(up_vec,tmp);
 385         if ((factor > 0 && is_forward) || (factor < 0 && !is_forward)) {
 386                 cross_v3_v3v3(vec3,vec2,tmp); /* hmm, maybe up_vec should be used instead of tmp */
 387         }
 388         else {
 389                 cross_v3_v3v3(vec3,tmp,vec2); /* hmm, maybe up_vec should be used instead of tmp */
 390         }
 391         normalize_v3(vec3);
 392         c1 = dot_v3v3(vec3,vec1);
 393         c2 = dot_v3v3(vec1,vec1);
 394         if (fabsf(c1) < 0.000001f || fabsf(c2) < 0.000001f) {
 395                 factor = 0.0f;
 396         }
 397         else {
 398                 factor = c2/c1;
 399         }
 400
 401         return factor;
 402 }
 403
 404 /* BME_bevel_split_edge() is the main math work-house; its responsibilities are:
 405  * using the vert and the loop passed, get or make the split vert, set its coordinates
 406  * and transform properties, and set the max limits.
 407  * Finally, return the split vert. */
 408 static BME_Vert *BME_bevel_split_edge(BME_Mesh *bm, BME_Vert *v, BME_Vert *v1, BME_Loop *l, float *up_vec, float value, BME_TransData_Head *td) {
 409         BME_TransData *vtd, *vtd1 /* , *vtd2 */ /* UNUSED */;
 410         BME_Vert *sv, *v2, *v3 /* , *ov */ /* UNUSED */;
 411         BME_Loop *lv1, *lv2;
 412         BME_Edge *ne, *e1, *e2;
 413         float maxfactor, scale, len, dis, vec1[3], vec2[3], t_up_vec[3];
 414         int is_edge, forward /* , is_split_vert */ /* UNUSED */;
 415
 416         if (l == NULL) {
 417                 /* what you call operator overloading in C :)
 418                  * I wanted to use the same function for both wire edges and poly loops
 419                  * so... here we walk around edges to find the needed verts */
 420                 forward = 1;
 421                 /* is_split_vert = 0; */ /* UNUSED */
 422                 if (v->edge == NULL) {
 423                         //printf("We can't split a loose vert's edge!\n");
 424                         return NULL;
 425                 }
 426                 e1 = v->edge; /* we just use the first two edges */
 427                 e2 = BME_disk_nextedge(v->edge, v);
 428                 if (e1 == e2) {
 429                         //printf("You need at least two edges to use BME_bevel_split_edge()\n");
 430                         return NULL;
 431                 }
 432                 v2 = BME_edge_getothervert(e1, v);
 433                 v3 = BME_edge_getothervert(e2, v);
 434                 if (v1 != v2 && v1 != v3) {
 435                         //printf("Error: more than 2 edges in v's disk cycle, or v1 does not share an edge with v\n");
 436                         return NULL;
 437                 }
 438                 if (v1 == v2) {
 439                         v2 = v3;
 440                 }
 441                 else {
 442                         e1 = e2;
 443                 }
 444                 /* ov = BME_edge_getothervert(e1,v); */ /* UNUSED */
 445                 sv = BME_split_edge(bm,v,e1,&ne,0);
 446                 //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /*this is technically wrong...*/
 447                 //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
 448                 //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
 449                 BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
 450                 sv->tflag1 |= BME_BEVEL_BEVEL;
 451                 ne->tflag1 = BME_BEVEL_ORIG; /* mark edge as original, even though it isn't */
 452                 BME_bevel_get_vec(vec1,v1,v,td);
 453                 BME_bevel_get_vec(vec2,v2,v,td);
 454                 cross_v3_v3v3(t_up_vec,vec1,vec2);
 455                 normalize_v3(t_up_vec);
 456                 up_vec = t_up_vec;
 457         }
 458         else {
 459                 /* establish loop direction */
 460                 if (l->v == v) {
 461                         forward = 1;
 462                         lv1 = l->next;
 463                         lv2 = l->prev;
 464                         v1 = l->next->v;
 465                         v2 = l->prev->v;
 466                 }
 467                 else if (l->next->v == v) {
 468                         forward = 0;
 469                         lv1 = l;
 470                         lv2 = l->next->next;
 471                         v1 = l->v;
 472                         v2 = l->next->next->v;
 473                 }
 474                 else {
 475                         //printf("ERROR: BME_bevel_split_edge() - v must be adjacent to l\n");
 476                         return NULL;
 477                 }
 478
 479                 if (BME_bevel_is_split_vert(lv1)) {
 480                         /* is_split_vert = 1; */ /* UNUSED */
 481                         sv = v1;
 482                         if (forward) v1 = l->next->next->v;
 483                         else v1 = l->prev->v;
 484                 }
 485                 else {
 486                         /* is_split_vert = 0; */ /* UNUSED */
 487                         /* ov = BME_edge_getothervert(l->e,v); */ /* UNUSED */
 488                         sv = BME_split_edge(bm,v,l->e,&ne,0);
 489                         //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /*this is technically wrong...*/
 490                         //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
 491                         //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
 492                         BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
 493                         sv->tflag1 |= BME_BEVEL_BEVEL;
 494                         ne->tflag1 = BME_BEVEL_ORIG; /* mark edge as original, even though it isn't */
 495                 }
 496
 497                 if (BME_bevel_is_split_vert(lv2)) {
 498                         if (forward) v2 = lv2->prev->v;
 499                         else v2 = lv2->next->v;
 500                 }
 501         }
 502
 503         is_edge = BME_bevel_get_vec(vec1,v,v1,td); /* get the vector we will be projecting onto */
 504         BME_bevel_get_vec(vec2,v,v2,td); /* get the vector we will be projecting parallel to */
 505         len = len_v3(vec1);
 506         normalize_v3(vec1);
 507
 508         vtd = BME_get_transdata(td, sv);
 509         vtd1 = BME_get_transdata(td, v);
 510         /* vtd2 = BME_get_transdata(td,v1); */ /* UNUSED */
 511
 512         if (vtd1->loc == NULL) {
 513                 /* this is a vert with data only for calculating initial weights */
 514                 if (vtd1->weight < 0) {
 515                         vtd1->weight = 0;
 516                 }
 517                 scale = vtd1->weight/vtd1->factor;
 518                 if (!vtd1->max) {
 519                         vtd1->max = BME_new_transdata_float(td);
 520                         *vtd1->max = -1;
 521                 }
 522         }
 523         else {
 524                 scale = vtd1->weight;
 525         }
 526         vtd->max = vtd1->max;
 527
 528         if (is_edge && vtd1->loc != NULL) {
 529                 maxfactor = vtd1->maxfactor;
 530         }
 531         else {
 532                 maxfactor = scale*BME_bevel_project_vec(vec1,vec2,up_vec,forward,td);
 533                 if (vtd->maxfactor > 0 && vtd->maxfactor < maxfactor) {
 534                         maxfactor = vtd->maxfactor;
 535                 }
 536         }
 537
 538         dis = (v1->tflag1 & BME_BEVEL_ORIG)? len/3 : len/2;
 539         if (is_edge || dis > maxfactor*value) {
 540                 dis = maxfactor*value;
 541         }
 542         madd_v3_v3v3fl(sv->co, v->co, vec1, dis);
 543         sub_v3_v3v3(vec1, sv->co, vtd1->org);
 544         dis = len_v3(vec1);
 545         normalize_v3(vec1);
 546         BME_assign_transdata(td, bm, sv, vtd1->org, vtd1->org, vec1, sv->co, dis, scale, maxfactor, vtd->max);
 547
 548         return sv;
 549 }
 550
 551 static float BME_bevel_set_max(BME_Vert *v1, BME_Vert *v2, float value, BME_TransData_Head *td) {
 552         BME_TransData *vtd1, *vtd2;
 553         float max, fac1, fac2, vec1[3], vec2[3], vec3[3];
 554
 555         BME_bevel_get_vec(vec1,v1,v2,td);
 556         vtd1 = BME_get_transdata(td,v1);
 557         vtd2 = BME_get_transdata(td,v2);
 558
 559         if (vtd1->loc == NULL) {
 560                 fac1 = 0;
 561         }
 562         else {
 563                 copy_v3_v3(vec2, vtd1->vec);
 564                 mul_v3_fl(vec2, vtd1->factor);
 565                 if (dot_v3v3(vec1, vec1)) {
 566                         project_v3_v3v3(vec2, vec2,vec1);
 567                         fac1 = len_v3(vec2) / value;
 568                 }
 569                 else {
 570                         fac1 = 0;
 571                 }
 572         }
 573
 574         if (vtd2->loc == NULL) {
 575                 fac2 = 0;
 576         }
 577         else {
 578                 copy_v3_v3(vec3, vtd2->vec);
 579                 mul_v3_fl(vec3, vtd2->factor);
 580                 if (dot_v3v3(vec1, vec1)) {
 581                         project_v3_v3v3(vec2, vec3, vec1);
 582                         fac2 = len_v3(vec2) / value;
 583                 }
 584                 else {
 585                         fac2 = 0;
 586                 }
 587         }
 588
 589         if (fac1 || fac2) {
 590                 max = len_v3(vec1) / (fac1 + fac2);
 591                 if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
 592                         *vtd1->max = max;
 593                 }
 594                 if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
 595                         *vtd2->max = max;
 596                 }
 597         }
 598         else {
 599                 max = -1;
 600         }
 601
 602         return max;
 603 }
 604
 605 static BME_Vert *BME_bevel_wire(BME_Mesh *bm, BME_Vert *v, float value, int res, int UNUSED(options), BME_TransData_Head *td) {
 606         BME_Vert *ov1, *ov2, *v1, *v2;
 607
 608         ov1 = BME_edge_getothervert(v->edge, v);
 609         ov2 = BME_edge_getothervert(BME_disk_nextedge(v->edge, v), v);
 610
 611         /* split the edges */
 612         v1 = BME_bevel_split_edge(bm,v,ov1,NULL,NULL,value,td);
 613         v1->tflag1 |= BME_BEVEL_NONMAN;
 614         v2 = BME_bevel_split_edge(bm,v,ov2,NULL,NULL,value,td);
 615         v2->tflag1 |= BME_BEVEL_NONMAN;
 616
 617         if (value > 0.5) {
 618                 BME_bevel_set_max(v1,ov1,value,td);
 619                 BME_bevel_set_max(v2,ov2,value,td);
 620         }
 621
 622         /* remove the original vert */
 623         if (res) {
 624                 BME_JEKV(bm,v->edge,v);
 625         }
 626
 627         return v1;
 628 }
 629
 630 static BME_Loop *BME_bevel_edge(BME_Mesh *bm, BME_Loop *l, float value, int UNUSED(options), float *up_vec, BME_TransData_Head *td) {
 631         BME_Vert *v1, *v2, *kv;
 632         BME_Loop *kl=NULL, *nl;
 633         BME_Edge *e;
 634         BME_Poly *f;
 635
 636         f = l->f;
 637         e = l->e;
 638
 639         if ((l->e->tflag1 & BME_BEVEL_BEVEL) == 0
 640                 && ((l->v->tflag1 & BME_BEVEL_BEVEL) || (l->next->v->tflag1 & BME_BEVEL_BEVEL)))
 641         { /* sanity check */
 642                 return l;
 643         }
 644
 645         /* checks and operations for prev edge */
 646         /* first, check to see if this edge was inset previously */
 647         if ((l->prev->e->tflag1 & BME_BEVEL_ORIG) == 0
 648                 && (l->v->tflag1 & BME_BEVEL_NONMAN) == 0) {
 649                 kl = l->prev->radial.next->data;
 650                 if (kl->v == l->v) kl = kl->prev;
 651                 else kl = kl->next;
 652                 kv = l->v;
 653         }
 654         else {
 655                 kv = NULL;
 656         }
 657         /* get/make the first vert to be used in SFME */
 658         if (l->v->tflag1 & BME_BEVEL_NONMAN){
 659                 v1 = l->v;
 660         }
 661         else { /* we'll need to split the previous edge */
 662                 v1 = BME_bevel_split_edge(bm,l->v,NULL,l->prev,up_vec,value,td);
 663         }
 664         /* if we need to clean up geometry... */
 665         if (kv) {
 666                 l = l->next;
 667                 if (kl->v == kv) {
 668                         BME_split_face(bm,kl->f,kl->prev->v,kl->next->v,&nl,kl->prev->e);
 669                         BME_JFKE(bm,((BME_Loop*)kl->prev->radial.next->data)->f,kl->f,kl->prev->e);
 670                         BME_collapse_vert(bm, kl->e, kv, 1.0);
 671                         //BME_JEKV(bm,kl->e,kv);
 672
 673                 }
 674                 else {
 675                         BME_split_face(bm,kl->f,kl->next->next->v,kl->v,&nl,kl->next->e);
 676                         BME_JFKE(bm,((BME_Loop*)kl->next->radial.next->data)->f,kl->f,kl->next->e);
 677                         BME_collapse_vert(bm, kl->e, kv, 1.0);
 678                         //BME_JEKV(bm,kl->e,kv);
 679                 }
 680                 l = l->prev;
 681         }
 682
 683         /* checks and operations for the next edge */
 684         /* first, check to see if this edge was inset previously  */
 685         if ((l->next->e->tflag1 & BME_BEVEL_ORIG) == 0
 686                 && (l->next->v->tflag1 & BME_BEVEL_NONMAN) == 0) {
 687                 kl = l->next->radial.next->data;
 688                 if (kl->v == l->next->v) kl = kl->prev;
 689                 else kl = kl->next;
 690                 kv = l->next->v;
 691         }
 692         else {
 693                 kv = NULL;
 694         }
 695         /* get/make the second vert to be used in SFME */
 696         if (l->next->v->tflag1 & BME_BEVEL_NONMAN) {
 697                 v2 = l->next->v;
 698         }
 699         else { /* we'll need to split the next edge */
 700                 v2 = BME_bevel_split_edge(bm,l->next->v,NULL,l->next,up_vec,value,td);
 701         }
 702         /* if we need to clean up geometry... */
 703         if (kv) {
 704                 if (kl->v == kv) {
 705                         BME_split_face(bm,kl->f,kl->prev->v,kl->next->v,&nl,kl->prev->e);
 706                         BME_JFKE(bm,((BME_Loop*)kl->prev->radial.next->data)->f,kl->f,kl->prev->e);
 707                         BME_collapse_vert(bm, kl->e, kv, 1.0);
 708                         //BME_JEKV(bm,kl->e,kv);
 709                 }
 710                 else {
 711                         BME_split_face(bm,kl->f,kl->next->next->v,kl->v,&nl,kl->next->e);
 712                         BME_JFKE(bm,((BME_Loop*)kl->next->radial.next->data)->f,kl->f,kl->next->e);
 713                         BME_collapse_vert(bm, kl->e, kv, 1.0);
 714                         //BME_JEKV(bm,kl->e,kv);
 715                 }
 716         }
 717
 718         if ((v1->tflag1 & BME_BEVEL_NONMAN)==0 || (v2->tflag1 & BME_BEVEL_NONMAN)==0) {
 719                 BME_split_face(bm,f,v2,v1,&l,e);
 720                 l->e->tflag1 = BME_BEVEL_BEVEL;
 721                 l = l->radial.next->data;
 722         }
 723
 724         if (l->f != f){
 725                 //printf("Whoops! You got something out of order in BME_bevel_edge()!\n");
 726         }
 727
 728         return l;
 729 }
 730
 731 static BME_Loop *BME_bevel_vert(BME_Mesh *bm, BME_Loop *l, float value, int UNUSED(options), float *up_vec, BME_TransData_Head *td) {
 732         BME_Vert *v1, *v2;
 733         /* BME_Poly *f; */ /* UNUSED */
 734
 735         /* get/make the first vert to be used in SFME */
 736         /* may need to split the previous edge */
 737         v1 = BME_bevel_split_edge(bm,l->v,NULL,l->prev,up_vec,value,td);
 738
 739         /* get/make the second vert to be used in SFME */
 740         /* may need to split this edge (so move l) */
 741         l = l->prev;
 742         v2 = BME_bevel_split_edge(bm,l->next->v,NULL,l->next,up_vec,value,td);
 743         l = l->next->next;
 744
 745         /* "cut off" this corner */
 746         /* f = */ /* UNUSED */ BME_split_face(bm,l->f,v2,v1,NULL,l->e);
 747
 748         return l;
 749 }
 750
 751 /**
 752  *                      BME_bevel_poly
 753  *
 754  *      Polygon inset tool:
 755  *
 756  *      Insets a polygon/face based on the tflag1's of its vertices
 757  *      and edges. Used by the bevel tool only, for now.
 758  *  The parameter "value" is the distance to inset (should be negative).
 759  *  The parameter "options" is not currently used.
 760  *
 761  *      Returns -
 762  *  A BME_Poly pointer to the resulting inner face.
 763 */
 764 static BME_Poly *BME_bevel_poly(BME_Mesh *bm, BME_Poly *f, float value, int options, BME_TransData_Head *td) {
 765         BME_Loop *l, *ol;
 766         BME_TransData *vtd1, *vtd2;
 767         float up_vec[3], vec1[3], vec2[3], vec3[3], fac1, fac2, max = -1;
 768         int len, i;
 769
 770         up_vec[0] = 0.0f;
 771         up_vec[1] = 0.0f;
 772         up_vec[2] = 0.0f;
 773         /* find a good normal for this face (there's better ways, I'm sure) */
 774         ol = f->loopbase;
 775         l = ol->next;
 776         for (i=0,ol=f->loopbase,l=ol->next; l->next!=ol; l=l->next) {
 777                 BME_bevel_get_vec(vec1,l->next->v,ol->v,td);
 778                 BME_bevel_get_vec(vec2,l->v,ol->v,td);
 779                 cross_v3_v3v3(vec3, vec2, vec1);
 780                 add_v3_v3(up_vec, vec3);
 781                 i++;
 782         }
 783         mul_v3_fl(up_vec,1.0f/i);
 784         normalize_v3(up_vec);
 785
 786         for (i=0,len=f->len; i<len; i++,l=l->next) {
 787                 if ((l->e->tflag1 & BME_BEVEL_BEVEL) && (l->e->tflag1 & BME_BEVEL_ORIG)) {
 788                         max = 1.0f;
 789                         l = BME_bevel_edge(bm, l, value, options, up_vec, td);
 790                 }
 791                 else if ((l->v->tflag1 & BME_BEVEL_BEVEL) && (l->v->tflag1 & BME_BEVEL_ORIG) && (l->prev->e->tflag1 & BME_BEVEL_BEVEL) == 0) {
 792                         max = 1.0f;
 793                         l = BME_bevel_vert(bm, l, value, options, up_vec, td);
 794                 }
 795         }
 796
 797         /* max pass */
 798         if (value > 0.5 && max > 0) {
 799                 max = -1;
 800                 for (i=0,len=f->len; i<len; i++,l=l->next) {
 801                         if ((l->e->tflag1 & BME_BEVEL_BEVEL) || (l->e->tflag1 & BME_BEVEL_ORIG)) {
 802                                 BME_bevel_get_vec(vec1,l->v,l->next->v,td);
 803                                 vtd1 = BME_get_transdata(td,l->v);
 804                                 vtd2 = BME_get_transdata(td,l->next->v);
 805                                 if (vtd1->loc == NULL) {
 806                                         fac1 = 0;
 807                                 }
 808                                 else {
 809                                         copy_v3_v3(vec2,vtd1->vec);
 810                                         mul_v3_fl(vec2,vtd1->factor);
 811                                         if (dot_v3v3(vec1, vec1)) {
 812                                                 project_v3_v3v3(vec2,vec2,vec1);
 813                                                 fac1 = len_v3(vec2)/value;
 814                                         }
 815                                         else {
 816                                                 fac1 = 0;
 817                                         }
 818                                 }
 819                                 if (vtd2->loc == NULL) {
 820                                         fac2 = 0;
 821                                 }
 822                                 else {
 823                                         copy_v3_v3(vec3,vtd2->vec);
 824                                         mul_v3_fl(vec3,vtd2->factor);
 825                                         if (dot_v3v3(vec1, vec1)) {
 826                                                 project_v3_v3v3(vec2,vec3,vec1);
 827                                                 fac2 = len_v3(vec2)/value;
 828                                         }
 829                                         else {
 830                                                 fac2 = 0;
 831                                         }
 832                                 }
 833                                 if (fac1 || fac2) {
 834                                         max = len_v3(vec1)/(fac1 + fac2);
 835                                         if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
 836                                                 *vtd1->max = max;
 837                                         }
 838                                         if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
 839                                                 *vtd2->max = max;
 840                                         }
 841                                 }
 842                         }
 843                 }
 844         }
 845
 846         return l->f;
 847 }
 848
 849 static void BME_bevel_add_vweight(BME_TransData_Head *td, BME_Mesh *bm, BME_Vert *v, float weight, float factor, int options)
 850 {
 851         BME_TransData *vtd;
 852
 853         if (v->tflag1 & BME_BEVEL_NONMAN) return;
 854         v->tflag1 |= BME_BEVEL_BEVEL;
 855         if ( (vtd = BME_get_transdata(td, v)) ) {
 856                 if (options & BME_BEVEL_EMIN) {
 857                         vtd->factor = 1.0;
 858                         if (vtd->weight < 0 || weight < vtd->weight) {
 859                                 vtd->weight = weight;
 860                         }
 861                 }
 862                 else if (options & BME_BEVEL_EMAX) {
 863                         vtd->factor = 1.0;
 864                         if (weight > vtd->weight) {
 865                                 vtd->weight = weight;
 866                         }
 867                 }
 868                 else if (vtd->weight < 0) {
 869                         vtd->factor = factor;
 870                         vtd->weight = weight;
 871                 }
 872                 else {
 873                         vtd->factor += factor; /* increment number of edges with weights (will be averaged) */
 874                         vtd->weight += weight; /* accumulate all the weights */
 875                 }
 876         }
 877         else {
 878                 /* we'll use vtd->loc == NULL to mark that this vert is not moving */
 879                 vtd = BME_assign_transdata(td, bm, v, v->co, NULL, NULL, NULL, factor, weight, -1, NULL);
 880         }
 881 }
 882
 883 static float BME_bevel_get_angle(BME_Mesh *UNUSED(bm), BME_Edge *e, BME_Vert *v) {
 884         BME_Vert *v1, *v2;
 885         BME_Loop *l1, *l2;
 886         float vec1[3], vec2[3], vec3[3], vec4[3];
 887
 888         l1 = e->loop;
 889         l2 = e->loop->radial.next->data;
 890         if (l1->v == v) {
 891                 v1 = l1->prev->v;
 892                 v2 = l1->next->v;
 893         }
 894         else {
 895                 v1 = l1->next->next->v;
 896                 v2 = l1->v;
 897         }
 898         VECSUB(vec1,v1->co,v->co);
 899         VECSUB(vec2,v2->co,v->co);
 900         cross_v3_v3v3(vec3,vec1,vec2);
 901
 902         l1 = l2;
 903         if (l1->v == v) {
 904                 v1 = l1->prev->v;
 905                 v2 = l1->next->v;
 906         }
 907         else {
 908                 v1 = l1->next->next->v;
 909                 v2 = l1->v;
 910         }
 911         VECSUB(vec1,v1->co,v->co);
 912         VECSUB(vec2,v2->co,v->co);
 913         cross_v3_v3v3(vec4,vec2,vec1);
 914
 915         normalize_v3(vec3);
 916         normalize_v3(vec4);
 917
 918         return dot_v3v3(vec3,vec4);
 919 }
 920 static int BME_face_sharededges(BME_Poly *f1, BME_Poly *f2){
 921         BME_Loop *l;
 922         int count = 0;
 923
 924         l = f1->loopbase;
 925         do{
 926                 if(BME_radial_find_face(l->e,f2)) count++;
 927                 l = l->next;
 928         }while(l != f1->loopbase);
 929
 930         return count;
 931 }
 932 /**
 933  *                      BME_bevel_initialize
 934  *
 935  *      Prepare the mesh for beveling:
 936  *
 937  *      Sets the tflag1's of the mesh elements based on the options passed.
 938  *
 939  *      Returns -
 940  *  A BME_Mesh pointer to the BMesh passed as a parameter.
 941 */
 942 static BME_Mesh *BME_bevel_initialize(BME_Mesh *bm, int options, int UNUSED(defgrp_index), float angle, BME_TransData_Head *td) {
 943         BME_Vert *v;
 944         BME_Edge *e;
 945         BME_Poly *f;
 946         /* BME_TransData *vtd; */ /* UNUSED */
 947         /* MDeformVert *dvert; */ /* UNUSED */
 948         /* MDeformWeight *dw; */ /* UNUSED */
 949         int len;
 950         float weight, threshold;
 951
 952         /* vert pass */
 953         for (v=bm->verts.first; v; v=v->next) {
 954                 /* dvert = NULL; */ /* UNUSED */
 955                 /* dw = NULL; */ /* UNUSED */
 956                 v->tflag1 = BME_BEVEL_ORIG;
 957                 /* originally coded, a vertex gets tagged with BME_BEVEL_BEVEL in this pass if
 958                  * the vert is manifold (or is shared by only two edges - wire bevel)
 959                  * BME_BEVEL_SELECT is passed and the vert has v->flag&SELECT or
 960                  * BME_BEVEL_VWEIGHT is passed, and the vert has a defgrp and weight
 961                  * BME_BEVEL_ANGLE is not passed
 962                  * BME_BEVEL_EWEIGHT is not passed
 963                  */
 964                 /* originally coded, a vertex gets tagged with BME_BEVEL_NONMAN in this pass if
 965                  * the vert is loose, shared by multiple regions, or is shared by wire edges
 966                  * note: verts belonging to edges of open meshes are not tagged with BME_BEVEL_NONMAN
 967                  */
 968                 /* originally coded, a vertex gets a transform weight set in this pass if
 969                  * BME_BEVEL_VWEIGHT is passed, and the vert has a defgrp and weight
 970                  */
 971
 972                 /* get disk cycle length */
 973                 if (v->edge == NULL) {
 974                         len = 0;
 975                 }
 976                 else {
 977                         len = BME_cycle_length(BME_disk_getpointer(v->edge,v));
 978                         /* we'll assign a default transform data to every vert (except the loose ones) */
 979                         /* vtd = */ /* UNUSED */ BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 0, -1, -1, NULL);
 980                 }
 981
 982                 /* check for non-manifold vert */
 983                 if (BME_is_nonmanifold_vert(bm,v)) {
 984                         v->tflag1 |= BME_BEVEL_NONMAN;
 985                 }
 986
 987                 /* BME_BEVEL_BEVEL tests */
 988                 if ((v->tflag1 & BME_BEVEL_NONMAN) == 0 || len == 2) { /* either manifold vert, or wire vert */
 989                         if (((options & BME_BEVEL_SELECT) && (v->flag & SELECT))
 990                                 || ((options & BME_BEVEL_WEIGHT) && (options & BME_BEVEL_VERT)) /* use weights for verts */
 991                                 || ((options & BME_BEVEL_ANGLE) == 0
 992                                         && (options & BME_BEVEL_SELECT) == 0
 993                                         && (options & BME_BEVEL_WEIGHT) == 0))
 994                         {
 995                                 if (options & BME_BEVEL_WEIGHT) {
 996                                         /* do vert weight stuff */
 997                                         //~ dvert = CustomData_em_get(&bm->vdata,v->data,CD_MDEFORMVERT);
 998                                         //~ if (!dvert) continue;
 999                                         //~ for (i = 0; i < dvert->totweight; ++i) {
1000                                                 //~ if(dvert->dw[i].def_nr == defgrp_index) {
1001                                                         //~ dw = &dvert->dw[i];
1002                                                         //~ break;
1003                                                 //~ }
1004                                         //~ }
1005                                         //~ if (!dw || dw->weight == 0.0) continue;
1006                                         if (v->bweight == 0.0) continue;
1007                                         /* vtd = */ /* UNUSED */ BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 1.0, v->bweight, -1, NULL);
1008                                         v->tflag1 |= BME_BEVEL_BEVEL;
1009                                 }
1010                                 else {
1011                                         /* vtd = */ /* UNUSED */ BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 1.0, 1.0, -1, NULL);
1012                                         v->tflag1 |= BME_BEVEL_BEVEL;
1013                                 }
1014                         }
1015                 }
1016         }
1017
1018         /* edge pass */
1019         threshold = (float)cos((angle + 0.001) * M_PI / 180.0);
1020         for (e=bm->edges.first; e; e=e->next) {
1021                 e->tflag1 = BME_BEVEL_ORIG;
1022                 weight = 0.0;
1023                 /* originally coded, an edge gets tagged with BME_BEVEL_BEVEL in this pass if
1024                  * BME_BEVEL_VERT is not set
1025                  * the edge is manifold (shared by exactly two faces)
1026                  * BME_BEVEL_SELECT is passed and the edge has e->flag&SELECT or
1027                  * BME_BEVEL_EWEIGHT is passed, and the edge has the crease set or
1028                  * BME_BEVEL_ANGLE is passed, and the edge is sharp enough
1029                  * BME_BEVEL_VWEIGHT is passed, and both verts are set for bevel
1030                  */
1031                 /* originally coded, a vertex gets tagged with BME_BEVEL_BEVEL in this pass if
1032                  * the vert belongs to the edge
1033                  * the vert is not tagged with BME_BEVEL_NONMAN
1034                  * the edge is eligible for bevel (even if BME_BEVEL_VERT is set, or the edge is shared by less than 2 faces)
1035                  */
1036                 /* originally coded, a vertex gets a transform weight set in this pass if
1037                  * the vert belongs to the edge
1038                  * the edge has a weight
1039                  */
1040                 /* note: edge weights are cumulative at the verts,
1041                  * i.e. the vert's weight is the average of the weights of its weighted edges
1042                  */
1043
1044                 if (e->loop == NULL) {
1045                         len = 0;
1046                         e->v1->tflag1 |= BME_BEVEL_NONMAN;
1047                         e->v2->tflag1 |= BME_BEVEL_NONMAN;
1048                 }
1049                 else {
1050                         len = BME_cycle_length(&(e->loop->radial));
1051                 }
1052
1053                 if (len > 2) {
1054                         /* non-manifold edge of the worst kind */
1055                         continue;
1056                 }
1057
1058                 if ((options & BME_BEVEL_SELECT) && (e->flag & SELECT)) {
1059                         weight = 1.0;
1060                         /* stupid editmode doesn't always flush selections, or something */
1061                         e->v1->flag |= SELECT;
1062                         e->v2->flag |= SELECT;
1063                 }
1064                 else if ((options & BME_BEVEL_WEIGHT) && (options & BME_BEVEL_VERT) == 0) {
1065                         weight = e->bweight;
1066                 }
1067                 else if (options & BME_BEVEL_ANGLE) {
1068                         if ((e->v1->tflag1 & BME_BEVEL_NONMAN) == 0 && BME_bevel_get_angle(bm,e,e->v1) < threshold) {
1069                                 e->tflag1 |= BME_BEVEL_BEVEL;
1070                                 e->v1->tflag1 |= BME_BEVEL_BEVEL;
1071                                 BME_bevel_add_vweight(td, bm, e->v1, 1.0, 1.0, options);
1072                         }
1073                         else {
1074                                 BME_bevel_add_vweight(td, bm, e->v1, 0.0, 1.0, options);
1075                         }
1076                         if ((e->v2->tflag1 & BME_BEVEL_NONMAN) == 0 && BME_bevel_get_angle(bm,e,e->v2) < threshold) {
1077                                 e->tflag1 |= BME_BEVEL_BEVEL;
1078                                 e->v2->tflag1 |= BME_BEVEL_BEVEL;
1079                                 BME_bevel_add_vweight(td, bm, e->v2, 1.0, 1.0, options);
1080                         }
1081                         else {
1082                                 BME_bevel_add_vweight(td, bm, e->v2, 0.0, 1.0, options);
1083                         }
1084                 }
1085                 //~ else if ((options & BME_BEVEL_VWEIGHT) && (options & BME_BEVEL_VERT) == 0) {
1086                         //~ if ((e->v1->tflag1 & BME_BEVEL_BEVEL) && (e->v2->tflag1 & BME_BEVEL_BEVEL)) {
1087                                 //~ e->tflag1 |= BME_BEVEL_BEVEL;
1088                         //~ }
1089                 //~ }
1090                 else if ((options & BME_BEVEL_SELECT) == 0
1091                         && (options & BME_BEVEL_VERT) == 0)
1092                 {
1093                         weight = 1.0;
1094                 }
1095
1096                 if (weight > 0.0) {
1097                         e->tflag1 |= BME_BEVEL_BEVEL;
1098                         BME_bevel_add_vweight(td, bm, e->v1, weight, 1.0, options);
1099                         BME_bevel_add_vweight(td, bm, e->v2, weight, 1.0, options);
1100                 }
1101
1102                 if (len != 2 || options & BME_BEVEL_VERT) {
1103                         e->tflag1 &= ~BME_BEVEL_BEVEL;
1104                 }
1105         }
1106
1107         /* face pass */
1108         for (f=bm->polys.first; f; f=f->next) f->tflag1 = BME_BEVEL_ORIG;
1109
1110         /*clean up edges with 2 faces that share more than one edge*/
1111         for (e=bm->edges.first; e; e=e->next){
1112                 if(e->tflag1 & BME_BEVEL_BEVEL){
1113                         int count = 0;
1114                         count = BME_face_sharededges(e->loop->f, ((BME_Loop*)e->loop->radial.next->data)->f);
1115                         if(count > 1){
1116                                 e->tflag1 &= ~BME_BEVEL_BEVEL;
1117                         }
1118                 }
1119         }
1120
1121         return bm;
1122
1123 }
1124
1125 /* tags all elements as originals */
1126 static BME_Mesh *BME_bevel_reinitialize(BME_Mesh *bm) {
1127         BME_Vert *v;
1128         BME_Edge *e;
1129         BME_Poly *f;
1130
1131         for (v = bm->verts.first; v; v=v->next) {
1132                 v->tflag1 |= BME_BEVEL_ORIG;
1133         }
1134
1135         for (e=bm->edges.first; e; e=e->next) {
1136                 e->tflag1 |= BME_BEVEL_ORIG;
1137         }
1138
1139         for (f=bm->polys.first; f; f=f->next) {
1140                 f->tflag1 |= BME_BEVEL_ORIG;
1141         }
1142         return bm;
1143
1144 }
1145
1146 /**
1147  *                      BME_bevel_mesh
1148  *
1149  *      Mesh beveling tool:
1150  *
1151  *      Bevels an entire mesh. It currently uses the tflag1's of
1152  *      its vertices and edges to track topological changes.
1153  *  The parameter "value" is the distance to inset (should be negative).
1154  *  The parameter "options" is not currently used.
1155  *
1156  *      Returns -
1157  *  A BME_Mesh pointer to the BMesh passed as a parameter.
1158 */
1159
1160 static void bmesh_dissolve_disk(BME_Mesh *bm, BME_Vert *v){
1161         BME_Poly *f;
1162         BME_Edge *e;
1163         int done, len;
1164
1165         if(v->edge){
1166                 done = 0;
1167                 while(!done){
1168                         done = 1;
1169                         e = v->edge; /*loop the edge looking for a edge to dissolve*/
1170                         do{
1171                                 f = NULL;
1172                                 len = BME_cycle_length(&(e->loop->radial));
1173                                 if(len == 2){
1174                                         f = BME_JFKE_safe(bm,e->loop->f, ((BME_Loop*)(e->loop->radial.next->data))->f, e);
1175                                 }
1176                                 if(f){
1177                                         done = 0;
1178                                         break;
1179                                 }
1180                                 e = BME_disk_nextedge(e,v);
1181                         }while(e != v->edge);
1182                 }
1183                 BME_collapse_vert(bm, v->edge, v, 1.0);
1184                 //BME_JEKV(bm,v->edge,v);
1185         }
1186 }
1187 static BME_Mesh *BME_bevel_mesh(BME_Mesh *bm, float value, int res, int options, int UNUSED(defgrp_index), BME_TransData_Head *td) {
1188         BME_Vert *v, *nv;
1189         BME_Edge *e, *oe;
1190         BME_Loop *l, *l2;
1191         BME_Poly *f;
1192         unsigned int i, len;
1193
1194         for (f=bm->polys.first; f; f=f->next) {
1195                 if(f->tflag1 & BME_BEVEL_ORIG) {
1196                         BME_bevel_poly(bm,f,value,options,td);
1197                 }
1198         }
1199
1200         /* here we will loop through all the verts to clean up the left over geometry */
1201         /* crazy idea. when res == 0, don't remove the original geometry */
1202         for (v = bm->verts.first; v; /* we may kill v, so increment in-loop */) {
1203                 nv = v->next;
1204                 if ((v->tflag1 & BME_BEVEL_NONMAN) && (v->tflag1 & BME_BEVEL_BEVEL) && (v->tflag1 & BME_BEVEL_ORIG)) {
1205                         v = BME_bevel_wire(bm, v, value, res, options, td);
1206                 }
1207                 else if (res && ((v->tflag1 & BME_BEVEL_BEVEL) && (v->tflag1 & BME_BEVEL_ORIG))) {
1208                         int count = 0;
1209                         /* first, make sure we're not sitting on an edge to be removed */
1210                         oe = v->edge;
1211                         e = BME_disk_nextedge(oe,v);
1212                         while ((e->tflag1 & BME_BEVEL_BEVEL) && (e->tflag1 & BME_BEVEL_ORIG)) {
1213                                 e = BME_disk_nextedge(e,v);
1214                                 if (e == oe) {
1215                                         //printf("Something's wrong! We can't remove every edge here!\n");
1216                                         break;
1217                                 }
1218                         }
1219                         /* look for original edges, and remove them */
1220                         oe = e;
1221                         while ( (e = BME_disk_next_edgeflag(oe, v, 0, BME_BEVEL_ORIG | BME_BEVEL_BEVEL)) ) {
1222                                 count++;
1223                                 /* join the faces (we'll split them later) */
1224                                 f = BME_JFKE_safe(bm,e->loop->f,((BME_Loop*)e->loop->radial.next->data)->f,e);
1225                                 if (!f){
1226                                         //printf("Non-manifold geometry not getting tagged right?\n");
1227                                 }
1228                         }
1229
1230                         /*need to do double check *before* you bevel to make sure that manifold edges are for two faces that share only *one* edge to make sure it doesnt hang here!*/
1231
1232
1233                         /* all original edges marked to be beveled have been removed;
1234                          * now we need to link up the edges for this "corner" */
1235                         len = BME_cycle_length(BME_disk_getpointer(v->edge, v));
1236                         for (i=0,e=v->edge; i < len; i++,e=BME_disk_nextedge(e,v)) {
1237                                 l = e->loop;
1238                                 l2 = l->radial.next->data;
1239                                 if (l->v != v) l = l->next;
1240                                 if (l2->v != v) l2 = l2->next;
1241                                 /* look for faces that have had the original edges removed via JFKE */
1242                                 if (l->f->len > 3) {
1243                                         BME_split_face(bm,l->f,l->next->v,l->prev->v,&l,l->e); /* clip this corner off */
1244                                         if (len > 2) {
1245                                                 l->e->tflag1 |= BME_BEVEL_BEVEL;
1246                                         }
1247                                 }
1248                                 if (l2->f->len > 3) {
1249                                         BME_split_face(bm,l2->f,l2->next->v,l2->prev->v,&l,l2->e); /* clip this corner off */
1250                                         if (len > 2) {
1251                                                 l->e->tflag1 |= BME_BEVEL_BEVEL;
1252                                         }
1253                                 }
1254                         }
1255                         bmesh_dissolve_disk(bm, v);
1256                 }
1257                 v = nv;
1258         }
1259
1260         return bm;
1261 }
1262
1263 static BME_Mesh *BME_tesselate(BME_Mesh *bm) {
1264         BME_Loop *l, *nextloop;
1265         BME_Poly *f;
1266
1267         for (f=bm->polys.first; f; f=f->next) {
1268                 l = f->loopbase;
1269                 while (l->f->len > 4) {
1270                         nextloop = l->next->next->next;
1271                         /* make a quad */
1272                         BME_split_face(bm,l->f,l->v,nextloop->v,NULL,l->e);
1273                         l = nextloop;
1274                 }
1275         }
1276         return bm;
1277 }
1278
1279
1280 /*Main bevel function:
1281         Should be only one exported
1282
1283 */
1284
1285 /* options that can be passed:
1286  * BME_BEVEL_VWEIGHT    <---- v, Look at vertex weights; use defgrp_index if option is present
1287  * BME_BEVEL_SELECT             <---- v,e, check selection for verts and edges
1288  * BME_BEVEL_ANGLE              <---- v,e, don't bevel-tag verts - tag verts per edge
1289  * BME_BEVEL_VERT               <---- e, don't tag edges
1290  * BME_BEVEL_EWEIGHT    <---- e, use crease flag for now
1291  * BME_BEVEL_PERCENT    <---- Will need to think about this one; will probably need to incorporate into actual bevel routine
1292  * BME_BEVEL_RADIUS             <---- Will need to think about this one; will probably need to incorporate into actual bevel routine
1293  * All weights/limits are stored per-vertex
1294  */
1295 BME_Mesh *BME_bevel(BME_Mesh *bm, float value, int res, int options, int defgrp_index, float angle, BME_TransData_Head **rtd) {
1296         BME_Vert *v;
1297         BME_TransData_Head *td;
1298         BME_TransData *vtd;
1299         int i;
1300         float fac=1, d;
1301
1302         td = BME_init_transdata(BLI_MEMARENA_STD_BUFSIZE);
1303
1304         BME_bevel_initialize(bm, options, defgrp_index, angle, td);
1305
1306         /* recursion math courtesy of Martin Poirier (theeth) */
1307         for (i=0; i<res-1; i++) {
1308                 if (i==0) fac += 1.0f/3.0f; else fac += 1.0f/(3 * i * 2.0f);
1309         }
1310         d = 1.0f/fac;
1311         /* crazy idea. if res == 0, don't remove original geometry */
1312         for (i=0; i<res || (res==0 && i==0); i++) {
1313                 if (i != 0) BME_bevel_reinitialize(bm);
1314                 BME_model_begin(bm);
1315                 BME_bevel_mesh(bm,d,res,options,defgrp_index,td);
1316                 BME_model_end(bm);
1317                 if (i==0) d /= 3; else d /= 2;
1318         }
1319
1320         BME_tesselate(bm);
1321
1322         if (rtd) {
1323                 *rtd = td;
1324                 return bm;
1325         }
1326
1327         /* transform pass */
1328         for (v = bm->verts.first; v; v=v->next) {
1329                 if ( (vtd = BME_get_transdata(td, v)) ) {
1330                         if (vtd->max && (*vtd->max > 0 && value > *vtd->max)) {
1331                                 d = *vtd->max;
1332                         }
1333                         else {
1334                                 d = value;
1335                         }
1336                         madd_v3_v3v3fl(v->co,vtd->org,vtd->vec,vtd->factor*d);
1337                 }
1338                 v->tflag1 = 0;
1339         }
1340
1341         BME_free_transdata(td);
1342         return bm;
1343 }