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