source/blender/blenkernel/intern/BME_tools.c

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