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