Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[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 "MEM_guardedalloc.h"
30
31 #include "BLI_math.h"
32 #include "BLI_utildefines.h"
33 #include "BLI_alloca.h"
34
35 #include "bmesh.h"
36
37 #include "intern/bmesh_operators_private.h" /* own include */
38
39 #define EDGE_OUT        (1 << 0)
40 #define FACE_OUT        (1 << 1)
41
42 /**
43  * Calculates the face subset normal.
44  */
45 static bool bm_face_subset_calc_normal(BMLoop *l_first, BMLoop *l_last, float r_no[3])
46 {
47         float const *v_prev, *v_curr;
48
49         /* Newell's Method */
50         BMLoop *l_iter = l_first;
51         BMLoop *l_term = l_last->next;
52
53         zero_v3(r_no);
54
55         v_prev = l_last->v->co;
56         do {
57                 v_curr = l_iter->v->co;
58                 add_newell_cross_v3_v3v3(r_no, v_prev, v_curr);
59                 v_prev = v_curr;
60         } while ((l_iter = l_iter->next) != l_term);
61
62         return (normalize_v3(r_no) != 0.0f);
63 }
64
65 /**
66  * Calculates how non-planar the face subset is.
67  */
68 static float bm_face_subset_calc_planar(BMLoop *l_first, BMLoop *l_last, const float no[3])
69 {
70         float axis_mat[3][3];
71         float z_prev, z_curr;
72         float delta_z = 0.0f;
73
74         /* Newell's Method */
75         BMLoop *l_iter = l_first;
76         BMLoop *l_term = l_last->next;
77
78         axis_dominant_v3_to_m3(axis_mat, no);
79
80         z_prev = mul_m3_v3_single_z(axis_mat, l_last->v->co);
81         do {
82                 z_curr = mul_m3_v3_single_z(axis_mat, l_iter->v->co);
83                 delta_z += fabsf(z_curr - z_prev);
84                 z_prev = z_curr;
85         } while ((l_iter = l_iter->next) != l_term);
86
87         return delta_z;
88 }
89
90 static bool bm_face_split_find(BMFace *f, BMVert *v_pair[2], float *r_angle)
91 {
92         BMLoop *l_iter, *l_first;
93         BMLoop **l_arr = BLI_array_alloca(l_arr, f->len);
94         const unsigned int f_len = f->len;
95         unsigned int i_a, i_b;
96         bool found = false;
97
98         /* angle finding */
99         float err_best = FLT_MAX;
100         float angle_best = FLT_MAX;
101
102         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
103         i_a = 0;
104         do {
105                 l_arr[i_a++] = l_iter;
106         } while ((l_iter = l_iter->next) != l_first);
107
108         /* now for the big search, O(N^2), however faces normally aren't so large */
109         for (i_a = 0; i_a < f_len; i_a++) {
110                 BMLoop *l_a = l_arr[i_a];
111                 for (i_b = i_a + 2; i_b < f_len; i_b++) {
112                         BMLoop *l_b = l_arr[i_b];
113                         /* check these are not touching
114                          * (we could be smarter here) */
115                         if ((l_a->next != l_b) &&
116                             (l_a->prev != l_b))
117                         {
118                                 /* first calculate normals */
119                                 float no_a[3], no_b[3];
120
121                                 if (bm_face_subset_calc_normal(l_a, l_b, no_a) &&
122                                     bm_face_subset_calc_normal(l_b, l_a, no_b))
123                                 {
124                                         const float err_a = bm_face_subset_calc_planar(l_a, l_b, no_a);
125                                         const float err_b = bm_face_subset_calc_planar(l_b, l_a, no_b);
126                                         const float err_test = err_a + err_b;
127
128                                         if (err_test < err_best) {
129                                                 /* check we're legal (we could batch this) */
130                                                 BMLoop *l_split[2] = {l_a, l_b};
131                                                 BM_face_legal_splits(f, &l_split, 1);
132                                                 if (l_split[0]) {
133                                                         err_best = err_test;
134                                                         v_pair[0] = l_a->v;
135                                                         v_pair[1] = l_b->v;
136
137                                                         angle_best = angle_normalized_v3v3(no_a, no_b);
138                                                         found = true;
139                                                 }
140                                         }
141                                 }
142                         }
143                 }
144         }
145
146         *r_angle = angle_best;
147
148         return found;
149
150
151 }
152
153 static bool bm_face_split_by_angle(BMesh *bm, BMFace *f, BMFace *r_f_pair[2], const float angle_limit)
154 {
155         BMVert *v_pair[2];
156         float angle;
157
158         if (bm_face_split_find(f, v_pair, &angle) && (angle > angle_limit)) {
159                 BMFace *f_new;
160                 BMLoop *l_new;
161                 f_new = BM_face_split(bm, f, v_pair[0], v_pair[1], &l_new, NULL, false);
162                 if (f_new) {
163                         r_f_pair[0] = f;
164                         r_f_pair[1] = f_new;
165
166                         BMO_elem_flag_enable(bm, f, FACE_OUT);
167                         BMO_elem_flag_enable(bm, f_new, FACE_OUT);
168                         BMO_elem_flag_enable(bm, l_new->e, EDGE_OUT);
169                         return true;
170                 }
171         }
172
173         return false;
174
175 }
176
177 void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
178 {
179         BMOIter siter;
180         BMFace *f;
181         int totface = 0, totloop = 0;
182         int tottris;
183         BMFace **fstack;
184         STACK_DECLARE(fstack);
185
186         const float angle_limit = BMO_slot_float_get(op->slots_in, "angle_limit");
187
188
189         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
190                 if (f->len > 3) {
191                         totface += 1;
192                         totloop += f->len;
193                 }
194         }
195
196         if (totface == 0) {
197                 return;
198         }
199
200         /* over alloc, if we split every face */
201         tottris = poly_to_tri_count(totface, totloop);
202         fstack = MEM_mallocN(sizeof(BMFace *) * tottris, __func__);
203
204         STACK_INIT(fstack);
205
206         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
207                 if (f->len > 3) {
208                         STACK_PUSH(fstack, f);
209                 }
210         }
211
212         while ((f = STACK_POP(fstack))) {
213                 BMFace *f_pair[2];
214                 if (bm_face_split_by_angle(bm, f, f_pair, angle_limit)) {
215                         int j;
216                         for (j = 0; j < 2; j++) {
217                                 if (f_pair[j]->len > 3) {
218                                         STACK_PUSH(fstack, f_pair[j]);
219                                 }
220                         }
221                 }
222         }
223
224         MEM_freeN(fstack);
225
226         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
227         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
228 }