bmesh: being back bevel modifier from 2.62 stable.
[blender-staging.git] / source / blender / bmesh / tools / BME_bevel.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Geoffrey Bantle and Levi Schooley.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 #include <math.h>
29
30 #include "MEM_guardedalloc.h"
31
32 #include "DNA_listBase.h"
33 #include "DNA_meshdata_types.h"
34 #include "DNA_mesh_types.h"
35
36 #include "BKE_utildefines.h"
37 #include "BKE_tessmesh.h"
38 #include "BKE_bmesh.h"
39 #include "BLI_math.h"
40 #include "BLI_blenlib.h"
41 #include "BLI_ghash.h"
42 #include "BLI_memarena.h"
43
44 #include "bmesh.h"
45 #include "intern/bmesh_private.h"
46
47 /* BMESH_TODO
48  *
49  * Date: 2011-11-24 06:25
50  * Sender: Andrew Wiggin
51  * Status update: I have code changes to actually make basic bevel modifier work. The things that still need to be done:
52  * - clean up the changes
53  * - get bevel by weight and bevel by angles working
54  * - the code uses adaptations of a couple of bmesh APIs,
55  * that work a little differently. for example, a join faces that doesn't just create a new face and then delete the
56  * original two faces and all associated loops, it extends one of the original faces to cover all the original loops
57  * (except for the loop on the join edge which is of course deleted). the bevel code currently requires this because it
58  * expects to be able to continue walking loop lists and doesn't like for loops to be deleted out from under it
59  * while working...
60  * but bmesh APIs don't do it this way because it makes it trickier to manage the interp during these operations,
61  * so I need to decide what to do in these cases.
62  */
63
64 /* ------- Bevel code starts here -------- */
65
66 BME_TransData_Head *BME_init_transdata(int bufsize)
67 {
68         BME_TransData_Head *td;
69
70         td = MEM_callocN(sizeof(BME_TransData_Head), "BM transdata header");
71         td->gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "BME_init_transdata gh");
72         td->ma = BLI_memarena_new(bufsize, "BME_TransData arena");
73         BLI_memarena_use_calloc(td->ma);
74
75         return td;
76 }
77
78 void BME_free_transdata(BME_TransData_Head *td)
79 {
80         BLI_ghash_free(td->gh, NULL, NULL);
81         BLI_memarena_free(td->ma);
82         MEM_freeN(td);
83 }
84
85 BME_TransData *BME_assign_transdata(
86         BME_TransData_Head *td, BMesh *bm, BMVert *v,
87         float *co, float *org, float *vec, float *loc,
88         float factor, float weight, float maxfactor, float *max)
89 {
90         BME_TransData *vtd;
91         int is_new = 0;
92
93         if (v == NULL) {
94                 return NULL;
95         }
96
97         if ((vtd = BLI_ghash_lookup(td->gh, v)) == NULL && bm != NULL) {
98                 vtd = BLI_memarena_alloc(td->ma, sizeof(*vtd));
99                 BLI_ghash_insert(td->gh, v, vtd);
100                 td->len++;
101                 is_new = 1;
102         }
103
104         vtd->bm = bm;
105         vtd->v = v;
106
107         if (co != NULL) {
108                 copy_v3_v3(vtd->co, co);
109         }
110
111         if (org == NULL && is_new) {
112                 copy_v3_v3(vtd->org, v->co); /* default */
113         }
114         else if (org != NULL) {
115                 copy_v3_v3(vtd->org, org);
116         }
117
118         if (vec != NULL) {
119                 copy_v3_v3(vtd->vec, vec);
120                 normalize_v3(vtd->vec);
121         }
122
123         vtd->loc = loc;
124
125         vtd->factor = factor;
126         vtd->weight = weight;
127         vtd->maxfactor = maxfactor;
128         vtd->max = max;
129
130         return vtd;
131 }
132
133 BME_TransData *BME_get_transdata(BME_TransData_Head *td, BMVert *v)
134 {
135         BME_TransData *vtd;
136         vtd = BLI_ghash_lookup(td->gh, v);
137         return vtd;
138 }
139
140 /* a hack (?) to use the transdata memarena to allocate floats for use with the max limits */
141 float *BME_new_transdata_float(BME_TransData_Head *td)
142 {
143         return BLI_memarena_alloc(td->ma, sizeof(float));
144 }
145
146 /* BM_disk_dissolve is a real mess, and crashes bevel if called instead of this.
147  * The drawback, though, is that this code doesn't merge customdata. */
148 static int BME_Bevel_Dissolve_Disk(BMesh *bm, BMVert *v)
149 {
150         BMIter iter;
151         BMEdge *e, *elast;
152         BMLoop *l1, *l2;
153
154         if (!BM_vert_is_manifold(bm, v)) {
155                 return 0;
156         }
157
158         BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
159                 if (BM_edge_face_count(e) != 2) {
160                         return 0;
161                 }
162         }
163
164         if (BM_vert_edge_count(v) > 2) {
165                 while (BM_vert_edge_count(v) > 2) {
166                         e = v->e;
167                         l1 = e->l;
168                         l2 = l1->radial_next;
169                         bmesh_jfke(bm, l1->f, l2->f, e);
170                 }
171
172                 e = v->e;
173                 elast = bmesh_disk_edge_next(e, v);
174
175                 /* BMESH_TODO, figure out if its possible we had a double edge here and need to splice it,
176                  * last bool arg */
177                 bmesh_jekv(bm, e, v, FALSE);
178
179                 l1 = elast->l;
180                 l2 = l1->radial_next;
181                 bmesh_jfke(bm, l1->f, l2->f, elast);
182         }
183
184         return 1;
185 }
186
187 static int BME_bevel_is_split_vert(BMesh *bm, BMLoop *l)
188 {
189         /* look for verts that have already been added to the edge when
190          * beveling other polys; this can be determined by testing the
191          * vert and the edges around it for originality
192          */
193         if (!BMO_elem_flag_test(bm, l->v, BME_BEVEL_ORIG) &&
194              BMO_elem_flag_test(bm, l->e, BME_BEVEL_ORIG) &&
195              BMO_elem_flag_test(bm, l->prev->e, BME_BEVEL_ORIG))
196         {
197                 return 1;
198         }
199         return 0;
200 }
201
202 /* get a vector, vec, that points from v1->co to wherever makes sense to
203  * the bevel operation as a whole based on the relationship between v1 and v2
204  * (won't necessarily be a vec from v1->co to v2->co, though it probably will be);
205  * the return value is -1 for failure, 0 if we used vert co's, and 1 if we used transform origins */
206 static int BME_bevel_get_vec(float *vec, BMVert *v1, BMVert *v2, BME_TransData_Head *td)
207 {
208         BME_TransData *vtd1, *vtd2;
209
210         vtd1 = BME_get_transdata(td, v1);
211         vtd2 = BME_get_transdata(td, v2);
212         if (!vtd1 || !vtd2) {
213                 //printf("BME_bevel_get_vec() got called without proper BME_TransData\n");
214                 return -1;
215         }
216
217         /* compare the transform origins to see if we can use the vert co's;
218          * if they belong to different origins, then we will use the origins to determine
219          * the vector */
220         if (compare_v3v3(vtd1->org, vtd2->org, 0.000001f)) {
221                 sub_v3_v3v3(vec, v2->co, v1->co);
222                 if (len_v3(vec) < 0.000001f) {
223                         zero_v3(vec);
224                 }
225                 return 0;
226         }
227         else {
228                 sub_v3_v3v3(vec, vtd2->org, vtd1->org);
229                 if (len_v3(vec) < 0.000001f) {
230                         zero_v3(vec);
231                 }
232                 return 1;
233         }
234 }
235
236 /* "Projects" a vector perpendicular to vec2 against vec1, such that
237  * the projected vec1 + vec2 has a min distance of 1 from the "edge" defined by vec2.
238  * note: the direction, is_forward, is used in conjunction with up_vec to determine
239  * whether this is a convex or concave corner. If it is a concave corner, it will
240  * be projected "backwards." If vec1 is before vec2, is_forward should be 0 (we are projecting backwards).
241  * vec1 is the vector to project onto (expected to be normalized)
242  * vec2 is the direction of projection (pointing away from vec1)
243  * up_vec is used for orientation (expected to be normalized)
244  * returns the length of the projected vector that lies along vec1 */
245 static float BME_bevel_project_vec(float *vec1, float *vec2, float *up_vec, int is_forward, BME_TransData_Head *UNUSED(td))
246 {
247         float factor, vec3[3], tmp[3], c1, c2;
248
249         cross_v3_v3v3(tmp, vec1, vec2);
250         normalize_v3(tmp);
251         factor = dot_v3v3(up_vec, tmp);
252         if ((factor > 0 && is_forward) || (factor < 0 && !is_forward)) {
253                 cross_v3_v3v3(vec3, vec2, tmp); /* hmm, maybe up_vec should be used instead of tmp */
254         }
255         else {
256                 cross_v3_v3v3(vec3, tmp, vec2); /* hmm, maybe up_vec should be used instead of tmp */
257         }
258         normalize_v3(vec3);
259         c1 = dot_v3v3(vec3, vec1);
260         c2 = dot_v3v3(vec1, vec1);
261         if (fabsf(c1) < 0.000001f || fabsf(c2) < 0.000001f) {
262                 factor = 0.0f;
263         }
264         else {
265                 factor = c2 / c1;
266         }
267
268         return factor;
269 }
270
271 /* BME_bevel_split_edge() is the main math work-house; its responsibilities are:
272  * using the vert and the loop passed, get or make the split vert, set its coordinates
273  * and transform properties, and set the max limits.
274  * Finally, return the split vert. */
275 static BMVert *BME_bevel_split_edge(BMesh *bm, BMVert *v, BMVert *v1, BMLoop *l, float *up_vec, float value, BME_TransData_Head *td)
276 {
277         BME_TransData *vtd, *vtd1, *vtd2;
278         BMVert *sv, *v2, *v3, *ov;
279         BMLoop *lv1, *lv2;
280         BMEdge *ne, *e1, *e2;
281         float maxfactor, scale, len, dis, vec1[3], vec2[3], t_up_vec[3];
282         int is_edge, forward, is_split_vert;
283
284         if (l == NULL) {
285                 /* what you call operator overloading in C :)
286                  * I wanted to use the same function for both wire edges and poly loops
287                  * so... here we walk around edges to find the needed verts */
288                 forward = 1;
289                 is_split_vert = 0;
290                 if (v->e == NULL) {
291                         //printf("We can't split a loose vert's edge!\n");
292                         return NULL;
293                 }
294                 e1 = v->e; /* we just use the first two edges */
295                 e2 = bmesh_disk_edge_next(v->e, v);
296                 if (e1 == e2) {
297                         //printf("You need at least two edges to use BME_bevel_split_edge()\n");
298                         return NULL;
299                 }
300                 v2 = BM_edge_other_vert(e1, v);
301                 v3 = BM_edge_other_vert(e2, v);
302                 if (v1 != v2 && v1 != v3) {
303                         //printf("Error: more than 2 edges in v's disk cycle, or v1 does not share an edge with v\n");
304                         return NULL;
305                 }
306                 if (v1 == v2) {
307                         v2 = v3;
308                 }
309                 else {
310                         e1 = e2;
311                 }
312                 ov = BM_edge_other_vert(e1, v);
313                 sv = BM_edge_split(bm, e1, v, &ne, 0);
314                 //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /* this is technically wrong.. */
315                 //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
316                 //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
317                 BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
318                 BMO_elem_flag_enable(bm, sv, BME_BEVEL_BEVEL);
319                 BMO_elem_flag_enable(bm, ne, BME_BEVEL_ORIG); /* mark edge as original, even though it isn't */
320                 BME_bevel_get_vec(vec1, v1, v, td);
321                 BME_bevel_get_vec(vec2, v2, v, td);
322                 cross_v3_v3v3(t_up_vec, vec1, vec2);
323                 normalize_v3(t_up_vec);
324                 up_vec = t_up_vec;
325         }
326         else {
327                 /* establish loop direction */
328                 if (l->v == v) {
329                         forward = 1;
330                         lv1 = l->next;
331                         lv2 = l->prev;
332                         v1 = l->next->v;
333                         v2 = l->prev->v;
334                 }
335                 else if (l->next->v == v) {
336                         forward = 0;
337                         lv1 = l;
338                         lv2 = l->next->next;
339                         v1 = l->v;
340                         v2 = l->next->next->v;
341                 }
342                 else {
343                         //printf("ERROR: BME_bevel_split_edge() - v must be adjacent to l\n");
344                         return NULL;
345                 }
346
347                 if (BME_bevel_is_split_vert(bm, lv1)) {
348                         is_split_vert = 1;
349                         sv = v1;
350                         v1 = forward ? l->next->next->v : l->prev->v;
351                 }
352                 else {
353                         is_split_vert = 0;
354                         ov = BM_edge_other_vert(l->e, v);
355                         sv = BM_edge_split(bm, l->e, v, &ne, 0);
356                         //BME_data_interp_from_verts(bm, v, ov, sv, 0.25); /* this is technically wrong.. */
357                         //BME_data_interp_from_faceverts(bm, v, ov, sv, 0.25);
358                         //BME_data_interp_from_faceverts(bm, ov, v, sv, 0.25);
359                         BME_assign_transdata(td, bm, sv, sv->co, sv->co, NULL, sv->co, 0, -1, -1, NULL); /* quick default */
360                         BMO_elem_flag_enable(bm, sv, BME_BEVEL_BEVEL);
361                         BMO_elem_flag_enable(bm, ne, BME_BEVEL_ORIG); /* mark edge as original, even though it isn't */
362                 }
363
364                 if (BME_bevel_is_split_vert(bm, lv2)) {
365                         v2 = forward ? lv2->prev->v : lv2->next->v;
366                 }
367         }
368
369         is_edge = BME_bevel_get_vec(vec1, v, v1, td); /* get the vector we will be projecting onto */
370         BME_bevel_get_vec(vec2, v, v2, td); /* get the vector we will be projecting parallel to */
371         len = len_v3(vec1);
372         normalize_v3(vec1);
373
374         vtd = BME_get_transdata(td, sv);
375         vtd1 = BME_get_transdata(td, v);
376         vtd2 = BME_get_transdata(td, v1);
377
378         if (vtd1->loc == NULL) {
379                 /* this is a vert with data only for calculating initial weights */
380                 if (vtd1->weight < 0) {
381                         vtd1->weight = 0;
382                 }
383                 scale = vtd1->weight / vtd1->factor;
384                 if (!vtd1->max) {
385                         vtd1->max = BME_new_transdata_float(td);
386                         *vtd1->max = -1;
387                 }
388         }
389         else {
390                 scale = vtd1->weight;
391         }
392         vtd->max = vtd1->max;
393
394         if (is_edge && vtd1->loc != NULL) {
395                 maxfactor = vtd1->maxfactor;
396         }
397         else {
398                 maxfactor = scale * BME_bevel_project_vec(vec1, vec2, up_vec, forward, td);
399                 if (vtd->maxfactor > 0 && vtd->maxfactor < maxfactor) {
400                         maxfactor = vtd->maxfactor;
401                 }
402         }
403
404         dis = BMO_elem_flag_test(bm, v1, BME_BEVEL_ORIG) ? len / 3 : len / 2;
405         if (is_edge || dis > maxfactor * value) {
406                 dis = maxfactor * value;
407         }
408         madd_v3_v3v3fl(sv->co, v->co, vec1, dis);
409         sub_v3_v3v3(vec1, sv->co, vtd1->org);
410         dis = len_v3(vec1);
411         normalize_v3(vec1);
412         BME_assign_transdata(td, bm, sv, vtd1->org, vtd1->org, vec1, sv->co, dis, scale, maxfactor, vtd->max);
413
414         return sv;
415 }
416
417 #if 0 /* UNUSED */
418 static float BME_bevel_set_max(BMVert *v1, BMVert *v2, float value, BME_TransData_Head *td)
419 {
420         BME_TransData *vtd1, *vtd2;
421         float max, fac1, fac2, vec1[3], vec2[3], vec3[3];
422
423         BME_bevel_get_vec(vec1, v1, v2, td);
424         vtd1 = BME_get_transdata(td, v1);
425         vtd2 = BME_get_transdata(td, v2);
426
427         if (vtd1->loc == NULL) {
428                 fac1 = 0;
429         }
430         else {
431                 copy_v3_v3(vec2, vtd1->vec);
432                 mul_v3_fl(vec2, vtd1->factor);
433                 if (dot_v3v3(vec1, vec1)) {
434                         project_v3_v3v3(vec2, vec2, vec1);
435                         fac1 = len_v3(vec2) / value;
436                 }
437                 else {
438                         fac1 = 0;
439                 }
440         }
441
442         if (vtd2->loc == NULL) {
443                 fac2 = 0;
444         }
445         else {
446                 copy_v3_v3(vec3, vtd2->vec);
447                 mul_v3_fl(vec3, vtd2->factor);
448                 if (dot_v3v3(vec1, vec1)) {
449                         project_v3_v3v3(vec2, vec3, vec1);
450                         fac2 = len_v3(vec2) / value;
451                 }
452                 else {
453                         fac2 = 0;
454                 }
455         }
456
457         if (fac1 || fac2) {
458                 max = len_v3(vec1) / (fac1 + fac2);
459                 if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
460                         *vtd1->max = max;
461                 }
462                 if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
463                         *vtd2->max = max;
464                 }
465         }
466         else {
467                 max = -1;
468         }
469
470         return max;
471 }
472 #endif
473
474 #if 0 /* UNUSED */
475 static BMVert *BME_bevel_wire(BMesh *bm, BMVert *v, float value, int res, int UNUSED(options), BME_TransData_Head *td)
476 {
477         BMVert *ov1, *ov2, *v1, *v2;
478
479         ov1 = BM_edge_other_vert(v->e, v);
480         ov2 = BM_edge_other_vert(bmesh_disk_edge_next(v->e, v), v);
481
482         /* split the edges */
483         v1 = BME_bevel_split_edge(bm, v, ov1, NULL, NULL, value, td);
484         BMO_elem_flag_enable(bm, v1, BME_BEVEL_NONMAN);
485         v2 = BME_bevel_split_edge(bm, v, ov2, NULL, NULL, value, td);
486         BMO_elem_flag_enable(bm, v2, BME_BEVEL_NONMAN);
487
488         if (value > 0.5) {
489                 BME_bevel_set_max(v1, ov1, value, td);
490                 BME_bevel_set_max(v2, ov2, value, td);
491         }
492
493         /* remove the original vert */
494         if (res) {
495                 /* bmesh_jekv; */
496
497                 //void BM_vert_collapse_faces(BMesh *bm, BMEdge *ke, BMVert *kv, float fac, int calcnorm) {
498                 //hrm, why is there a fac here? it just removes a vert
499                 BM_vert_collapse_edge(bm, v->e, v);
500         }
501
502         return v1;
503 }
504 #endif
505
506 static BMLoop *BME_bevel_edge(BMesh *bm, BMLoop *l, float value, int UNUSED(options), float *up_vec, BME_TransData_Head *td)
507 {
508         BMVert *v1, *v2, *kv;
509         BMLoop *kl = NULL, *nl;
510         BMEdge *e, *ke, *se;
511         BMFace *f, *jf;
512
513         f = l->f;
514         e = l->e;
515
516         /* sanity check */
517         if (!BMO_elem_flag_test(bm, l->e, BME_BEVEL_BEVEL) &&
518             (BMO_elem_flag_test(bm, l->v, BME_BEVEL_BEVEL) || BMO_elem_flag_test(bm, l->next->v, BME_BEVEL_BEVEL)))
519         {
520                 return l;
521         }
522
523         /* checks and operations for prev edge */
524         /* first, check to see if this edge was inset previously */
525         if (!BMO_elem_flag_test(bm, l->prev->e, BME_BEVEL_ORIG) &&
526             !BMO_elem_flag_test(bm, l->v, BME_BEVEL_NONMAN))
527         {
528                 kl = l->prev->radial_next;
529                 kl = (kl->v == l->v) ? kl->prev : kl->next;
530                 kv = l->v;
531         }
532         else {
533                 kv = NULL;
534         }
535         /* get/make the first vert to be used in SFME */
536         if (BMO_elem_flag_test(bm, l->v, BME_BEVEL_NONMAN)) {
537                 v1 = l->v;
538         }
539         else { /* we'll need to split the previous edge */
540                 v1 = BME_bevel_split_edge(bm, l->v, NULL, l->prev, up_vec, value, td);
541         }
542         /* if we need to clean up geometry... */
543         if (kv) {
544                 se = l->next->e;
545                 jf = NULL;
546                 if (kl->v == kv) {
547                         BM_face_split(bm, kl->f, kl->prev->v, kl->next->v, &nl, kl->prev->e, FALSE);
548                         ke = kl->e;
549                         /* BMESH-TODO: jfke doesn't handle customdata */
550                         jf = bmesh_jfke(bm, kl->prev->radial_next->f, kl->f, kl->prev->e);
551                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
552                 }
553                 else {
554                         BM_face_split(bm, kl->f, kl->next->next->v, kl->v, &nl, kl->next->e, FALSE);
555                         ke = kl->e;
556                         /* BMESH-TODO: jfke doesn't handle customdata */
557                         jf = bmesh_jfke(bm, kl->next->radial_next->f, kl->f, kl->next->e);
558                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
559                 }
560                 /* find saved loop pointer */
561                 l = se->l;
562                 while (l->f != jf) {
563                         l = l->radial_next;
564                         BLI_assert(l != se->l);
565                 }
566                 l = l->prev;
567         }
568
569         /* checks and operations for the next edge */
570         /* first, check to see if this edge was inset previously  */
571         if (!BMO_elem_flag_test(bm, l->next->e, BME_BEVEL_ORIG) &&
572             !BMO_elem_flag_test(bm, l->next->v, BME_BEVEL_NONMAN))
573         {
574                 kl = l->next->radial_next;
575                 kl = (kl->v == l->next->v) ? kl->prev : kl->next;
576                 kv = l->next->v;
577         }
578         else {
579                 kv = NULL;
580         }
581         /* get/make the second vert to be used in SFME */
582         if (BMO_elem_flag_test(bm, l->next->v, BME_BEVEL_NONMAN)) {
583                 v2 = l->next->v;
584         }
585         else { /* we'll need to split the next edge */
586                 v2 = BME_bevel_split_edge(bm, l->next->v, NULL, l->next, up_vec, value, td);
587         }
588         /* if we need to clean up geometry... */
589         if (kv) {
590                 se = l->e;
591                 jf = NULL;
592                 if (kl->v == kv) {
593                         BM_face_split(bm, kl->f, kl->prev->v, kl->next->v, &nl, kl->prev->e, FALSE);
594                         ke = kl->e;
595                         /* BMESH-TODO: jfke doesn't handle customdata */
596                         jf = bmesh_jfke(bm, kl->prev->radial_next->f, kl->f, kl->prev->e);
597                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
598                 }
599                 else {
600                         BM_face_split(bm, kl->f, kl->next->next->v, kl->v, &nl, kl->next->e, FALSE);
601                         ke = kl->e;
602                         /* BMESH-TODO: jfke doesn't handle customdata */
603                         jf = bmesh_jfke(bm, kl->next->radial_next->f, kl->f, kl->next->e);
604                         BM_vert_collapse_edge(bm, ke, kv, FALSE);
605                 }
606                 /* find saved loop pointer */
607                 l = se->l;
608                 while (l->f != jf) {
609                         l = l->radial_next;
610                         BLI_assert(l != se->l);
611                 }
612         }
613
614         if (!BMO_elem_flag_test(bm, v1, BME_BEVEL_NONMAN) || !BMO_elem_flag_test(bm, v2, BME_BEVEL_NONMAN)) {
615                 BM_face_split(bm, f, v2, v1, &l, e, FALSE);
616                 BMO_elem_flag_enable(bm, l->e, BME_BEVEL_BEVEL);
617                 l = l->radial_next;
618         }
619
620         if (l->f != f) {
621                 //printf("Whoops! You got something out of order in BME_bevel_edge()!\n");
622         }
623
624         return l;
625 }
626
627 static BMLoop *BME_bevel_vert(BMesh *bm, BMLoop *l, float value, int UNUSED(options), float *up_vec, BME_TransData_Head *td)
628 {
629         BMVert *v1, *v2;
630         BMFace *f;
631
632         /* get/make the first vert to be used in SFME */
633         /* may need to split the previous edge */
634         v1 = BME_bevel_split_edge(bm, l->v, NULL, l->prev, up_vec, value, td);
635
636         /* get/make the second vert to be used in SFME */
637         /* may need to split this edge (so move l) */
638         l = l->prev;
639         v2 = BME_bevel_split_edge(bm, l->next->v, NULL, l->next, up_vec, value, td);
640         l = l->next->next;
641
642         /* "cut off" this corner */
643         f = BM_face_split(bm, l->f, v2, v1, NULL, l->e, FALSE);
644
645         return l;
646 }
647
648 /*
649  *                      BME_bevel_poly
650  *
651  *      Polygon inset tool:
652  *
653  *      Insets a polygon/face based on the flagss of its vertices
654  *      and edges. Used by the bevel tool only, for now.
655  *  The parameter "value" is the distance to inset (should be negative).
656  *  The parameter "options" is not currently used.
657  *
658  *      Returns -
659  *  A BMFace pointer to the resulting inner face.
660  */
661 static BMFace *BME_bevel_poly(BMesh *bm, BMFace *f, float value, int options, BME_TransData_Head *td)
662 {
663         BMLoop *l/*, *o */;
664         BME_TransData *vtd1, *vtd2;
665         float up_vec[3], vec1[3], vec2[3], vec3[3], fac1, fac2, max = -1;
666         int len, i;
667         BMIter iter;
668
669         zero_v3(up_vec);
670
671         /* find a good normal for this face (there's better ways, I'm sure) */
672         BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
673                 BME_bevel_get_vec(vec1, l->v, l->next->v, td);
674                 BME_bevel_get_vec(vec2, l->prev->v, l->v, td);
675                 cross_v3_v3v3(vec3, vec2, vec1);
676                 add_v3_v3(up_vec, vec3);
677         }
678         normalize_v3(up_vec);
679
680         /* Can't use a BM_LOOPS_OF_FACE iterator here, because the loops are being modified
681          * and so the end condition will never hi */
682         for (l = BM_FACE_FIRST_LOOP(f)->prev, i = 0, len = f->len; i < len; i++, l = l->next) {
683                 if (BMO_elem_flag_test(bm, l->e, BME_BEVEL_BEVEL) && BMO_elem_flag_test(bm, l->e, BME_BEVEL_ORIG)) {
684                         max = 1.0f;
685                         l = BME_bevel_edge(bm, l, value, options, up_vec, td);
686                 }
687                 else if (BMO_elem_flag_test(bm, l->v, BME_BEVEL_BEVEL) &&
688                          BMO_elem_flag_test(bm, l->v, BME_BEVEL_ORIG) &&
689                         !BMO_elem_flag_test(bm, l->prev->e, BME_BEVEL_BEVEL))
690                 {
691                         max = 1.0f;
692                         l = BME_bevel_vert(bm, l, value, options, up_vec, td);
693                 }
694         }
695
696         f = l->f;
697
698         /* max pass */
699         if (value > 0.5f && max > 0) {
700                 max = -1;
701                 BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
702                         if (BMO_elem_flag_test(bm, l->e, BME_BEVEL_BEVEL) || BMO_elem_flag_test(bm, l->e, BME_BEVEL_ORIG)) {
703                                 BME_bevel_get_vec(vec1, l->v, l->next->v, td);
704                                 vtd1 = BME_get_transdata(td, l->v);
705                                 vtd2 = BME_get_transdata(td, l->next->v);
706                                 if (vtd1->loc == NULL) {
707                                         fac1 = 0;
708                                 }
709                                 else {
710                                         copy_v3_v3(vec2, vtd1->vec);
711                                         mul_v3_fl(vec2, vtd1->factor);
712                                         if (dot_v3v3(vec1, vec1)) {
713                                                 project_v3_v3v3(vec2, vec2, vec1);
714                                                 fac1 = len_v3(vec2) / value;
715                                         }
716                                         else {
717                                                 fac1 = 0;
718                                         }
719                                 }
720                                 if (vtd2->loc == NULL) {
721                                         fac2 = 0;
722                                 }
723                                 else {
724                                         copy_v3_v3(vec3, vtd2->vec);
725                                         mul_v3_fl(vec3, vtd2->factor);
726                                         if (dot_v3v3(vec1, vec1)) {
727                                                 project_v3_v3v3(vec2, vec3, vec1);
728                                                 fac2 = len_v3(vec2) / value;
729                                         }
730                                         else {
731                                                 fac2 = 0;
732                                         }
733                                 }
734                                 if (fac1 || fac2) {
735                                         max = len_v3(vec1)/(fac1 + fac2);
736                                         if (vtd1->max && (*vtd1->max < 0 || max < *vtd1->max)) {
737                                                 *vtd1->max = max;
738                                         }
739                                         if (vtd2->max && (*vtd2->max < 0 || max < *vtd2->max)) {
740                                                 *vtd2->max = max;
741                                         }
742                                 }
743                         }
744                 }
745         }
746
747         /* return l->f; */
748         return NULL;
749 }
750
751 static void BME_bevel_add_vweight(BME_TransData_Head *td, BMesh *bm, BMVert *v, float weight, float factor, int options)
752 {
753         BME_TransData *vtd;
754
755         if (BMO_elem_flag_test(bm, v, BME_BEVEL_NONMAN)) {
756                 return;
757         }
758
759         BMO_elem_flag_enable(bm, v, BME_BEVEL_BEVEL);
760         if ((vtd = BME_get_transdata(td, v))) {
761                 if (options & BME_BEVEL_EMIN) {
762                         vtd->factor = 1.0;
763                         if (vtd->weight < 0 || weight < vtd->weight) {
764                                 vtd->weight = weight;
765                         }
766                 }
767                 else if (options & BME_BEVEL_EMAX) {
768                         vtd->factor = 1.0;
769                         if (weight > vtd->weight) {
770                                 vtd->weight = weight;
771                         }
772                 }
773                 else if (vtd->weight < 0) {
774                         vtd->factor = factor;
775                         vtd->weight = weight;
776                 }
777                 else {
778                         vtd->factor += factor; /* increment number of edges with weights (will be averaged) */
779                         vtd->weight += weight; /* accumulate all the weights */
780                 }
781         }
782         else {
783                 /* we'll use vtd->loc == NULL to mark that this vert is not moving */
784                 vtd = BME_assign_transdata(td, bm, v, v->co, NULL, NULL, NULL, factor, weight, -1, NULL);
785         }
786 }
787
788 static void bevel_init_verts(BMesh *bm, int options, BME_TransData_Head *td)
789 {
790         BMVert *v;
791         BMIter iter;
792         float weight;
793         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
794                 weight = 0.0f;
795                 if (!BMO_elem_flag_test(bm, v, BME_BEVEL_NONMAN)) {
796                         /* modifiers should not use selection */
797                         if (options & BME_BEVEL_SELECT) {
798                                 if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
799                                         weight = 1.0f;
800                                 }
801                         }
802                         /* bevel weight NYI */
803                         else if (options & BME_BEVEL_WEIGHT) {
804                                 weight = BM_elem_float_data_get(&bm->vdata, v, CD_BWEIGHT);
805                         }
806                         else {
807                                 weight = 1.0f;
808                         }
809
810                         if (weight > 0.0f) {
811                                 BMO_elem_flag_enable(bm, v, BME_BEVEL_BEVEL);
812                                 BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 1.0, weight, -1, NULL);
813                         }
814                 }
815         }
816 }
817
818 static void bevel_init_edges(BMesh *bm, int options, BME_TransData_Head *td)
819 {
820         BMEdge *e;
821         int count;
822         float weight;
823         BMIter iter;
824         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
825                 weight = 0.0;
826                 if (!BMO_elem_flag_test(bm, e, BME_BEVEL_NONMAN)) {
827                         if(options & BME_BEVEL_SELECT) {
828                                 if(BM_elem_flag_test(e, BM_ELEM_SELECT)) weight = 1.0;
829                         }
830                         else if(options & BME_BEVEL_WEIGHT) {
831                                 weight = BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT);
832                         }
833                         else {
834                                 weight = 1.0;
835                         }
836
837                         if(weight > 0.0) {
838                                 BMO_elem_flag_enable(bm, e, BME_BEVEL_BEVEL);
839                                 BMO_elem_flag_enable(bm, e->v1, BME_BEVEL_BEVEL);
840                                 BMO_elem_flag_enable(bm, e->v2, BME_BEVEL_BEVEL);
841                                 BME_bevel_add_vweight(td, bm, e->v1, weight, 1.0, options);
842                                 BME_bevel_add_vweight(td, bm, e->v2, weight, 1.0, options);
843                         }
844                 }
845         }
846
847         /* clean up edges with 2 faces that share more than one edg */
848         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
849                 if(BMO_elem_flag_test(bm, e, BME_BEVEL_BEVEL)) {
850                         count = BM_face_share_edge_count(e->l->f, e->l->radial_next->f);
851                         if(count > 1) BMO_elem_flag_disable(bm, e, BME_BEVEL_BEVEL);
852                 }
853         }
854 }
855
856 static BMesh *BME_bevel_initialize(BMesh *bm, int options, int UNUSED(defgrp_index), float UNUSED(angle), BME_TransData_Head *td)
857 {
858         BMVert *v/*, *v2 */;
859         BMEdge *e/*, *curedg */;
860         BMFace *f;
861         BMIter iter;
862         int /* wire, */ len;
863
864         /* tag non-manifold geometr */
865         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
866                 BMO_elem_flag_enable(bm, v, BME_BEVEL_ORIG);
867                 if(v->e) {
868                         BME_assign_transdata(td, bm, v, v->co, v->co, NULL, NULL, 0, -1, -1, NULL);
869                         if (!BM_vert_is_manifold(bm, v)) {
870                                 BMO_elem_flag_enable(bm, v, BME_BEVEL_NONMAN);
871                         }
872
873                         /* test wire ver */
874                         len = BM_vert_edge_count(v);
875                         if (len == 2 && BM_vert_is_wire(bm, v))
876                                 BMO_elem_flag_disable(bm, v, BME_BEVEL_NONMAN);
877                 }
878                 else {
879                         BMO_elem_flag_enable(bm, v, BME_BEVEL_NONMAN);
880                 }
881         }
882
883         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
884                 BMO_elem_flag_enable(bm, e, BME_BEVEL_ORIG);
885                 if (!BM_edge_is_manifold(bm, e)) {
886                         BMO_elem_flag_enable(bm, e->v1, BME_BEVEL_NONMAN);
887                         BMO_elem_flag_enable(bm, e->v2, BME_BEVEL_NONMAN);
888                         BMO_elem_flag_enable(bm, e, BME_BEVEL_NONMAN);
889                 }
890                 if(BMO_elem_flag_test(bm, e->v1, BME_BEVEL_NONMAN) || BMO_elem_flag_test(bm, e->v2, BME_BEVEL_NONMAN)) {
891                         BMO_elem_flag_enable(bm, e, BME_BEVEL_NONMAN);
892                 }
893         }
894
895         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
896                 BMO_elem_flag_enable(bm, f, BME_BEVEL_ORIG);
897         }
898
899         if(options & BME_BEVEL_VERT) {
900                 bevel_init_verts(bm, options, td);
901         }
902         else {
903                 bevel_init_edges(bm, options, td);
904         }
905
906         return bm;
907
908 }
909
910 #if 0
911
912 static BMesh *BME_bevel_reinitialize(BMesh *bm)
913 {
914         BMVert *v;
915         BMEdge *e;
916         BMFace *f;
917         BMIter iter;
918
919         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
920                 BMO_elem_flag_enable(bm, v, BME_BEVEL_ORIG);
921         }
922         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
923                 BMO_elem_flag_enable(bm, e, BME_BEVEL_ORIG);
924         }
925         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
926                 BMO_elem_flag_enable(bm, f, BME_BEVEL_ORIG);
927         }
928         return bm;
929
930 }
931
932 #endif
933
934 /**
935  *                      BME_bevel_mesh
936  *
937  *      Mesh beveling tool:
938  *
939  *      Bevels an entire mesh. It currently uses the flags of
940  *      its vertices and edges to track topological changes.
941  *  The parameter "value" is the distance to inset (should be negative).
942  *  The parameter "options" is not currently used.
943  *
944  *      Returns -
945  *  A BMesh pointer to the BM passed as a parameter.
946  */
947
948 static BMesh *BME_bevel_mesh(BMesh *bm, float value, int UNUSED(res), int options, int UNUSED(defgrp_index), BME_TransData_Head *td)
949 {
950         BMVert *v;
951         BMEdge *e, *curedge;
952         BMLoop *l, *l2;
953         BMFace *f;
954         BMIter iter;
955
956         /* unsigned int i, len; */
957
958         /* bevel poly */
959         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
960                 if(BMO_elem_flag_test(bm, f, BME_BEVEL_ORIG)) {
961                         BME_bevel_poly(bm, f, value, options, td);
962                 }
963         }
964
965         /* get rid of beveled edge */
966         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
967                 if(BMO_elem_flag_test(bm, e, BME_BEVEL_BEVEL) && BMO_elem_flag_test(bm, e, BME_BEVEL_ORIG)) {
968                         BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e);
969                 }
970         }
971
972         /* link up corners and cli */
973         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
974                 if(BMO_elem_flag_test(bm, v, BME_BEVEL_ORIG) && BMO_elem_flag_test(bm, v, BME_BEVEL_BEVEL)) {
975                         curedge = v->e;
976                         do {
977                                 l = curedge->l;
978                                 l2 = l->radial_next;
979                                 if(l->v != v) l = l->next;
980                                 if(l2->v != v) l2 = l2->next;
981                                 if(l->f->len > 3)
982                                         BM_face_split(bm, l->f, l->next->v, l->prev->v, &l, l->e, FALSE); /* clip this corner off */
983                                 if(l2->f->len > 3)
984                                         BM_face_split(bm, l2->f, l2->next->v, l2->prev->v, &l, l2->e, FALSE); /* clip this corner off */
985                                 curedge = bmesh_disk_edge_next(curedge, v);
986                         } while(curedge != v->e);
987                         BME_Bevel_Dissolve_Disk(bm, v);
988                 }
989         }
990
991         /* Debug print, remov */
992         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
993                 if(f->len == 2) {
994                         printf("warning");
995                 }
996         }
997
998         return bm;
999 }
1000
1001 BMesh *BME_bevel(BMEditMesh *em, float value, int res, int options, int defgrp_index, float angle,
1002                  BME_TransData_Head **rtd, int do_tessface)
1003 {
1004         BMesh *bm = em->bm;
1005         BMVert *v;
1006         BMIter iter;
1007
1008         BME_TransData_Head *td;
1009         BME_TransData *vtd;
1010         int i;
1011         double fac = 1, d;
1012
1013         td = BME_init_transdata(BLI_MEMARENA_STD_BUFSIZE);
1014         /* recursion math courtesy of Martin Poirier (theeth) */
1015         for (i = 0; i < res - 1; i++) {
1016                 if (i == 0) fac += 1.0f / 3.0f; else fac += 1.0f / (3 * i * 2.0f);
1017         }
1018         d = 1.0f / fac;
1019
1020         for (i = 0; i < res || (res == 0 && i == 0); i++) {
1021                 BMO_push(bm, NULL);
1022                 BME_bevel_initialize(bm, options, defgrp_index, angle, td);
1023                 //if (i != 0) BME_bevel_reinitialize(bm);
1024                 bmesh_edit_begin(bm, 0);
1025                 BME_bevel_mesh(bm, (float)d, res, options, defgrp_index, td);
1026                 bmesh_edit_end(bm, 0);
1027                 d /= (i == 0) ? 3.0 : 2.0;
1028                 BMO_pop(bm);
1029         }
1030
1031         /* possibly needed when running as a tool (which is no longer functional)
1032          * but keep as an optioin for now */
1033         if (do_tessface) {
1034                 BMEdit_RecalcTessellation(em);
1035         }
1036
1037         /* interactive preview? */
1038         if (rtd) {
1039                 *rtd = td;
1040                 return bm;
1041         }
1042
1043         /* otherwise apply transforms */
1044         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
1045                 if ((vtd = BME_get_transdata(td, v))) {
1046                         if (vtd->max && (*vtd->max > 0 && value > *vtd->max)) {
1047                                 d = *vtd->max;
1048                         }
1049                         else {
1050                                 d = value;
1051                         }
1052                         madd_v3_v3v3fl(v->co, vtd->org, vtd->vec, vtd->factor * d);
1053                 }
1054         }
1055
1056         BME_free_transdata(td);
1057         return bm;
1058 }