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