c9ce2c5f6b88d8bd23e6237b17e9ebc60f934588
[blender.git] / source / blender / bmesh / operators / bmo_connect_nonplanar.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  * Contributor(s): Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_connect_nonplanar.c
24  *  \ingroup bmesh
25  *
26  * Connect verts non-planer faces iteratively (splits faces).
27  */
28
29 #include "BLI_math.h"
30 #include "BLI_utildefines.h"
31 #include "BLI_alloca.h"
32 #include "BLI_linklist_stack.h"
33
34 #include "bmesh.h"
35
36 #include "intern/bmesh_operators_private.h" /* own include */
37
38 #define EDGE_OUT        (1 << 0)
39 #define FACE_OUT        (1 << 1)
40
41 /**
42  * Calculates how non-planar the face subset is.
43  */
44 static float bm_face_subset_calc_planar(BMLoop *l_first, BMLoop *l_last, const float no[3])
45 {
46         float axis_mat[3][3];
47         float z_prev, z_curr;
48         float delta_z = 0.0f;
49
50         /* Newell's Method */
51         BMLoop *l_iter = l_first;
52         BMLoop *l_term = l_last->next;
53
54         axis_dominant_v3_to_m3(axis_mat, no);
55
56         z_prev = dot_m3_v3_row_z(axis_mat, l_last->v->co);
57         do {
58                 z_curr = dot_m3_v3_row_z(axis_mat, l_iter->v->co);
59                 delta_z += fabsf(z_curr - z_prev);
60                 z_prev = z_curr;
61         } while ((l_iter = l_iter->next) != l_term);
62
63         return delta_z;
64 }
65
66 static bool bm_face_split_find(BMesh *bm, BMFace *f, BMLoop *l_pair[2], float *r_angle)
67 {
68         BMLoop *l_iter, *l_first;
69         BMLoop **l_arr = BLI_array_alloca(l_arr, f->len);
70         const unsigned int f_len = f->len;
71         unsigned int i_a, i_b;
72         bool found = false;
73
74         /* angle finding */
75         float err_best = FLT_MAX;
76         float angle_best = FLT_MAX;
77
78         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
79         i_a = 0;
80         do {
81                 l_arr[i_a++] = l_iter;
82         } while ((l_iter = l_iter->next) != l_first);
83
84         /* now for the big search, O(N^2), however faces normally aren't so large */
85         for (i_a = 0; i_a < f_len; i_a++) {
86                 BMLoop *l_a = l_arr[i_a];
87                 for (i_b = i_a + 2; i_b < f_len; i_b++) {
88                         BMLoop *l_b = l_arr[i_b];
89                         /* check these are not touching
90                          * (we could be smarter here) */
91                         if (!BM_loop_is_adjacent(l_a, l_b)) {
92                                 /* first calculate normals */
93                                 float no_a[3], no_b[3];
94
95                                 if (BM_face_calc_normal_subset(l_a, l_b, no_a) != 0.0f &&
96                                     BM_face_calc_normal_subset(l_b, l_a, no_b) != 0.0f)
97                                 {
98                                         const float err_a = bm_face_subset_calc_planar(l_a, l_b, no_a);
99                                         const float err_b = bm_face_subset_calc_planar(l_b, l_a, no_b);
100                                         const float err_test = err_a + err_b;
101
102                                         if (err_test < err_best) {
103                                                 /* check we're legal (we could batch this) */
104                                                 BMLoop *l_split[2] = {l_a, l_b};
105                                                 BM_face_splits_check_legal(bm, f, &l_split, 1);
106                                                 if (l_split[0]) {
107                                                         err_best = err_test;
108                                                         l_pair[0] = l_a;
109                                                         l_pair[1] = l_b;
110
111                                                         angle_best = angle_normalized_v3v3(no_a, no_b);
112                                                         found = true;
113                                                 }
114                                         }
115                                 }
116                         }
117                 }
118         }
119
120         *r_angle = angle_best;
121
122         return found;
123
124
125 }
126
127 static bool bm_face_split_by_angle(BMesh *bm, BMFace *f, BMFace *r_f_pair[2], const float angle_limit)
128 {
129         BMLoop *l_pair[2];
130         float angle;
131
132         if (bm_face_split_find(bm, f, l_pair, &angle) && (angle > angle_limit)) {
133                 BMFace *f_new;
134                 BMLoop *l_new;
135
136                 f_new = BM_face_split(bm, f, l_pair[0], l_pair[1], &l_new, NULL, false);
137                 if (f_new) {
138                         r_f_pair[0] = f;
139                         r_f_pair[1] = f_new;
140
141                         BMO_elem_flag_enable(bm, f, FACE_OUT);
142                         BMO_elem_flag_enable(bm, f_new, FACE_OUT);
143                         BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT);
144                         return true;
145                 }
146         }
147
148         return false;
149
150 }
151
152 void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
153 {
154         BMOIter siter;
155         BMFace *f;
156         bool changed = false;
157         BLI_LINKSTACK_DECLARE(fstack, BMFace *);
158
159         const float angle_limit = BMO_slot_float_get(op->slots_in, "angle_limit");
160
161         BLI_LINKSTACK_INIT(fstack);
162
163         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
164                 if (f->len > 3) {
165                         BLI_LINKSTACK_PUSH(fstack, f);
166                 }
167         }
168
169         while ((f = BLI_LINKSTACK_POP(fstack))) {
170                 BMFace *f_pair[2];
171                 if (bm_face_split_by_angle(bm, f, f_pair, angle_limit)) {
172                         int j;
173                         for (j = 0; j < 2; j++) {
174                                 BM_face_normal_update(f_pair[j]);
175                                 if (f_pair[j]->len > 3) {
176                                         BLI_LINKSTACK_PUSH(fstack, f_pair[j]);
177                                 }
178                         }
179                         changed = true;
180                 }
181         }
182
183         BLI_LINKSTACK_FREE(fstack);
184
185         if (changed) {
186                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
187                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
188         }
189 }