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