Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / bmesh / operators / bmo_connect_nonplanar.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file \ingroup bmesh
18  *
19  * Connect verts non-planer faces iteratively (splits faces).
20  */
21
22 #include "BLI_math.h"
23 #include "BLI_utildefines.h"
24 #include "BLI_alloca.h"
25 #include "BLI_linklist_stack.h"
26
27 #include "bmesh.h"
28
29 #include "intern/bmesh_operators_private.h" /* own include */
30
31 #define EDGE_OUT        (1 << 0)
32 #define FACE_OUT        (1 << 1)
33
34 /**
35  * Calculates how non-planar the face subset is.
36  */
37 static float bm_face_subset_calc_planar(BMLoop *l_first, BMLoop *l_last, const float no[3])
38 {
39         float axis_mat[3][3];
40         float z_prev, z_curr;
41         float delta_z = 0.0f;
42
43         /* Newell's Method */
44         BMLoop *l_iter = l_first;
45         BMLoop *l_term = l_last->next;
46
47         axis_dominant_v3_to_m3(axis_mat, no);
48
49         z_prev = dot_m3_v3_row_z(axis_mat, l_last->v->co);
50         do {
51                 z_curr = dot_m3_v3_row_z(axis_mat, l_iter->v->co);
52                 delta_z += fabsf(z_curr - z_prev);
53                 z_prev = z_curr;
54         } while ((l_iter = l_iter->next) != l_term);
55
56         return delta_z;
57 }
58
59 static bool bm_face_split_find(BMesh *bm, BMFace *f, BMLoop *l_pair[2], float *r_angle_cos)
60 {
61         BMLoop *l_iter, *l_first;
62         BMLoop **l_arr = BLI_array_alloca(l_arr, f->len);
63         const uint f_len = f->len;
64         uint i_a, i_b;
65         bool found = false;
66
67         /* angle finding */
68         float err_best = FLT_MAX;
69         float angle_best_cos = -FLT_MAX;
70
71         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
72         i_a = 0;
73         do {
74                 l_arr[i_a++] = l_iter;
75         } while ((l_iter = l_iter->next) != l_first);
76
77         /* now for the big search, O(N^2), however faces normally aren't so large */
78         for (i_a = 0; i_a < f_len; i_a++) {
79                 BMLoop *l_a = l_arr[i_a];
80                 for (i_b = i_a + 2; i_b < f_len; i_b++) {
81                         BMLoop *l_b = l_arr[i_b];
82                         /* check these are not touching
83                          * (we could be smarter here) */
84                         if (!BM_loop_is_adjacent(l_a, l_b)) {
85                                 /* first calculate normals */
86                                 float no_a[3], no_b[3];
87
88                                 if (BM_face_calc_normal_subset(l_a, l_b, no_a) != 0.0f &&
89                                     BM_face_calc_normal_subset(l_b, l_a, no_b) != 0.0f)
90                                 {
91                                         const float err_a = bm_face_subset_calc_planar(l_a, l_b, no_a);
92                                         const float err_b = bm_face_subset_calc_planar(l_b, l_a, no_b);
93                                         const float err_test = err_a + err_b;
94
95                                         if (err_test < err_best) {
96                                                 /* check we're legal (we could batch this) */
97                                                 BMLoop *l_split[2] = {l_a, l_b};
98                                                 BM_face_splits_check_legal(bm, f, &l_split, 1);
99                                                 if (l_split[0]) {
100                                                         err_best = err_test;
101                                                         l_pair[0] = l_a;
102                                                         l_pair[1] = l_b;
103
104                                                         angle_best_cos = dot_v3v3(no_a, no_b);
105                                                         found = true;
106                                                 }
107                                         }
108                                 }
109                         }
110                 }
111         }
112
113         *r_angle_cos = angle_best_cos;
114
115         return found;
116 }
117
118 static bool bm_face_split_by_angle(BMesh *bm, BMFace *f, BMFace *r_f_pair[2], const float angle_limit_cos)
119 {
120         BMLoop *l_pair[2];
121         float angle_cos;
122
123         if (bm_face_split_find(bm, f, l_pair, &angle_cos) && (angle_cos < angle_limit_cos)) {
124                 BMFace *f_new;
125                 BMLoop *l_new;
126
127                 f_new = BM_face_split(bm, f, l_pair[0], l_pair[1], &l_new, NULL, false);
128                 if (f_new) {
129                         r_f_pair[0] = f;
130                         r_f_pair[1] = f_new;
131
132                         BMO_face_flag_enable(bm, f, FACE_OUT);
133                         BMO_face_flag_enable(bm, f_new, FACE_OUT);
134                         BMO_edge_flag_enable(bm, l_new->e, EDGE_OUT);
135                         return true;
136                 }
137         }
138
139         return false;
140
141 }
142
143 void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op)
144 {
145         BMOIter siter;
146         BMFace *f;
147         bool changed = false;
148         BLI_LINKSTACK_DECLARE(fstack, BMFace *);
149
150         const float angle_limit_cos = cosf(BMO_slot_float_get(op->slots_in, "angle_limit"));
151
152         BLI_LINKSTACK_INIT(fstack);
153
154         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
155                 if (f->len > 3) {
156                         BLI_LINKSTACK_PUSH(fstack, f);
157                 }
158         }
159
160         while ((f = BLI_LINKSTACK_POP(fstack))) {
161                 BMFace *f_pair[2];
162                 if (bm_face_split_by_angle(bm, f, f_pair, angle_limit_cos)) {
163                         int j;
164                         for (j = 0; j < 2; j++) {
165                                 BM_face_normal_update(f_pair[j]);
166                                 if (f_pair[j]->len > 3) {
167                                         BLI_LINKSTACK_PUSH(fstack, f_pair[j]);
168                                 }
169                         }
170                         changed = true;
171                 }
172         }
173
174         BLI_LINKSTACK_FREE(fstack);
175
176         if (changed) {
177                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
178                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
179         }
180 }