Cleanup: remove redundant doxygen \file argument
[blender.git] / source / blender / bmesh / operators / bmo_connect_concave.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 vertices so all resulting faces are convex.
20  *
21  * Implementation:
22  *
23  * - triangulate all concave face (tagging convex verts),
24  * - rotate edges (beautify) so edges will connect nearby verts.
25  * - sort long edges (longest first),
26  *   put any edges between 2 convex verts last since they often split convex regions.
27  * - merge the sorted edges as long as they don't create convex ngons.
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_math.h"
33 #include "BLI_utildefines.h"
34 #include "BLI_alloca.h"
35 #include "BLI_memarena.h"
36 #include "BLI_heap.h"
37 #include "BLI_polyfill_2d.h"
38 #include "BLI_polyfill_2d_beautify.h"
39 #include "BLI_linklist.h"
40
41 #include "bmesh.h"
42
43 #include "intern/bmesh_operators_private.h" /* own include */
44
45 #define EDGE_OUT        (1 << 0)
46 #define FACE_OUT        (1 << 1)
47
48 static int bm_edge_length_cmp(const void *a_, const void *b_)
49 {
50         const BMEdge *e_a = *(const void **)a_;
51         const BMEdge *e_b = *(const void **)b_;
52
53         int e_a_concave = ((BM_elem_flag_test(e_a->v1, BM_ELEM_TAG)) && (BM_elem_flag_test(e_a->v2, BM_ELEM_TAG)));
54         int e_b_concave = ((BM_elem_flag_test(e_b->v1, BM_ELEM_TAG)) && (BM_elem_flag_test(e_b->v2, BM_ELEM_TAG)));
55
56         /* merge edges between concave edges last since these
57          * are most likely to remain and be the main dividers */
58         if      (e_a_concave < e_b_concave) return -1;
59         else if (e_a_concave > e_b_concave) return  1;
60         else {
61                 /* otherwise shortest edges last */
62                 const float e_a_len = BM_edge_calc_length_squared(e_a);
63                 const float e_b_len = BM_edge_calc_length_squared(e_b);
64                 if      (e_a_len < e_b_len) return  1;
65                 else if (e_a_len > e_b_len) return -1;
66                 else                        return  0;
67         }
68 }
69
70 static bool bm_face_split_by_concave(
71         BMesh *bm, BMFace *f_base, const float eps,
72
73         MemArena *pf_arena,
74         struct Heap *pf_heap)
75 {
76         const int f_base_len = f_base->len;
77         int faces_array_tot = f_base_len - 3;
78         int edges_array_tot = f_base_len - 3;
79         BMFace  **faces_array = BLI_array_alloca(faces_array, faces_array_tot);
80         BMEdge  **edges_array = BLI_array_alloca(edges_array, edges_array_tot);
81         const int quad_method = 0, ngon_method = 0;  /* beauty */
82         LinkNode *faces_double = NULL;
83
84         float normal[3];
85         BLI_assert(f_base->len > 3);
86
87         copy_v3_v3(normal, f_base->no);
88
89         BM_face_triangulate(
90                 bm, f_base,
91                 faces_array, &faces_array_tot,
92                 edges_array, &edges_array_tot,
93                 &faces_double,
94                 quad_method, ngon_method, false,
95                 pf_arena,
96                 pf_heap);
97
98         BLI_assert(edges_array_tot <= f_base_len - 3);
99
100         if (faces_array_tot) {
101                 int i;
102                 for (i = 0; i < faces_array_tot; i++) {
103                         BMFace *f = faces_array[i];
104                         BMO_face_flag_enable(bm, f, FACE_OUT);
105                 }
106         }
107         BMO_face_flag_enable(bm, f_base, FACE_OUT);
108
109         if (edges_array_tot) {
110                 int i;
111
112                 qsort(edges_array, edges_array_tot, sizeof(*edges_array), bm_edge_length_cmp);
113
114                 for (i = 0; i < edges_array_tot; i++) {
115                         BMLoop *l_pair[2];
116                         BMEdge *e = edges_array[i];
117                         BMO_edge_flag_enable(bm, e, EDGE_OUT);
118
119                         if (BM_edge_is_contiguous(e) &&
120                             BM_edge_loop_pair(e, &l_pair[0], &l_pair[1]))
121                         {
122                                 bool ok = true;
123                                 int j;
124                                 for (j = 0; j < 2; j++) {
125                                         BMLoop *l = l_pair[j];
126
127                                         /* check that merging the edge (on this side)
128                                          * wouldn't result in a convex face-loop.
129                                          *
130                                          * This is the (l->next, l->prev) we would have once joined.
131                                          */
132                                         float cross[3];
133                                         cross_tri_v3(
134                                                 cross,
135                                                 l->v->co,
136                                                 l->radial_next->next->next->v->co,
137                                                 l->prev->v->co
138                                                 );
139
140                                         if (dot_v3v3(cross, normal) <= eps) {
141                                                 ok = false;
142                                                 break;
143                                         }
144                                 }
145
146                                 if (ok) {
147                                         BMFace *f_new, *f_pair[2] = {l_pair[0]->f, l_pair[1]->f};
148                                         f_new = BM_faces_join(bm, f_pair, 2, true);
149                                         if (f_new) {
150                                                 BMO_face_flag_enable(bm, f_new, FACE_OUT);
151                                         }
152                                 }
153                         }
154                 }
155         }
156
157         BLI_heap_clear(pf_heap, NULL);
158
159         while (faces_double) {
160                 LinkNode *next = faces_double->next;
161                 BM_face_kill(bm, faces_double->link);
162                 MEM_freeN(faces_double);
163                 faces_double = next;
164         }
165
166         return true;
167 }
168
169 static bool bm_face_convex_tag_verts(BMFace *f)
170 {
171         bool is_concave = false;
172         if (f->len > 3) {
173                 const BMLoop *l_iter, *l_first;
174
175                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
176                 do {
177                         if (BM_loop_is_convex(l_iter) == false) {
178                                 is_concave = true;
179                                 BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG);
180                         }
181                         else {
182                                 BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
183                         }
184                 } while ((l_iter = l_iter->next) != l_first);
185         }
186         return is_concave;
187 }
188
189 void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op)
190 {
191         BMOIter siter;
192         BMFace *f;
193         bool changed = false;
194
195         MemArena *pf_arena;
196         Heap *pf_heap;
197
198         pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__);
199         pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE);
200
201         BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
202                 if (f->len > 3 && bm_face_convex_tag_verts(f)) {
203                         if (bm_face_split_by_concave(
204                                 bm, f, FLT_EPSILON,
205                                 pf_arena, pf_heap))
206                         {
207                                 changed = true;
208                         }
209                 }
210         }
211
212         if (changed) {
213                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
214                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
215         }
216
217         BLI_memarena_free(pf_arena);
218         BLI_heap_free(pf_heap, NULL);
219 }