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