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