Mempool: delay allocating an initial chunk, its not always used
[blender.git] / source / blender / bmesh / operators / bmo_connect_pair.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_pair.c
24  *  \ingroup bmesh
25  *
26  * Connect vertex pair across multiple faces (splits faces).
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math.h"
32 #include "BLI_utildefines.h"
33
34 #include "bmesh.h"
35
36 #include "intern/bmesh_operators_private.h" /* own include */
37
38 #include "BLI_mempool.h"
39 #include "BLI_listbase.h"
40
41 /**
42  * Method for connecting across many faces.
43  *
44  * - use the line between both verts and their normal average to construct a matrix.
45  * - using the matrix, we can find all intersecting verts/edges and build connection data.
46  * - then walk the connected data and find the shortest path (as we do with other shortest-path functions).
47  * - if the connection can't be found - fail.
48  * - with the connection found, split all edges tagging verts (or tag verts that sit on the intersection).
49  * - run the standard connect operator.
50  */
51
52 #define CONNECT_EPS 0.0001f
53 #define VERT_OUT 1
54
55 // #define DEBUG_PRINT
56
57 typedef struct PathContext {
58         ListBase state_lb;
59         float matrix[3][3];
60         float axis_sep;
61
62         BMVert *v_a, *v_b;
63
64         BLI_mempool *link_pool;
65 } PathContext;
66
67 /**
68  * Single linked list where each item contains state and points to previous path item.
69  */
70 typedef struct PathLink {
71         struct PathLink *next;
72         BMElem *ele;       /* edge or vert */
73         BMElem *ele_from;  /* edge or face we game from (not 'next->ele') */
74 } PathLink;
75
76 typedef struct PathLinkState {
77         struct PathLinkState *next, *prev;
78
79         /* chain of links */
80         struct PathLink *link_last;
81
82         /* length along links */
83         float dist;
84         float co_prev[3];
85 } PathLinkState;
86
87 static int state_isect_co_pair(const PathContext *pc,
88                                const float co_a[3], const float co_b[3])
89 {
90         const float diff_a = dot_m3_v3_row_x((float (*)[3])pc->matrix, co_a) - pc->axis_sep;
91         const float diff_b = dot_m3_v3_row_x((float (*)[3])pc->matrix, co_b) - pc->axis_sep;
92
93         const int test_a = (fabsf(diff_a) < CONNECT_EPS) ? 0 : (diff_a < 0.0f) ? -1 : 1;
94         const int test_b = (fabsf(diff_b) < CONNECT_EPS) ? 0 : (diff_b < 0.0f) ? -1 : 1;
95
96         if ((test_a && test_b) && (test_a != test_b)) {
97                 return 1;  /* on either side */
98         }
99         else {
100                 return 0;
101         }
102 }
103
104 static int state_isect_co_exact(const PathContext *pc,
105                                 const float co[3])
106 {
107         const float diff = dot_m3_v3_row_x((float (*)[3])pc->matrix, co) - pc->axis_sep;
108         return (fabsf(diff) <= CONNECT_EPS);
109 }
110
111 static float state_calc_co_pair_fac(const PathContext *pc,
112                                     const float co_a[3], const float co_b[3])
113 {
114         float diff_a, diff_b, diff_tot;
115
116         diff_a = fabsf(dot_m3_v3_row_x((float (*)[3])pc->matrix, co_a) - pc->axis_sep);
117         diff_b = fabsf(dot_m3_v3_row_x((float (*)[3])pc->matrix, co_b) - pc->axis_sep);
118         diff_tot = (diff_a + diff_b);
119         return (diff_tot > FLT_EPSILON) ? (diff_a / diff_tot) : 0.5f;
120 }
121
122 static void state_calc_co_pair(const PathContext *pc,
123                                const float co_a[3], const float co_b[3],
124                                float r_co[3])
125 {
126         const float fac = state_calc_co_pair_fac(pc, co_a, co_b);
127         interp_v3_v3v3(r_co, co_a, co_b, fac);
128 }
129
130 /**
131  * Ideally we wouldn't need this and for most cases we don't.
132  * But when a face has vertices that are on the boundary more then once this becomes tricky.
133  */
134 static bool state_link_find(PathLinkState *state, BMElem *ele)
135 {
136         PathLink *link = state->link_last;
137         BLI_assert(ELEM3(ele->head.htype, BM_VERT, BM_EDGE, BM_FACE));
138         if (link) {
139                 do {
140                         if (link->ele == ele) {
141                                 return true;
142                         }
143                 } while ((link = link->next));
144         }
145         return false;
146 }
147
148 static void state_link_add(PathContext *pc, PathLinkState *state,
149                            BMElem *ele, BMElem *ele_from)
150 {
151         PathLink *step_new = BLI_mempool_alloc(pc->link_pool);
152         BLI_assert(ele != ele_from);
153         BLI_assert(state_link_find(state, ele) == false);
154
155 #ifdef DEBUG_PRINT
156         printf("%s: adding to state %p:%d, %.4f - ", __func__, state, BLI_findindex(&pc->state_lb, state), state->dist);
157         if (ele->head.htype == BM_VERT) {
158                 printf("vert %d, ", BM_elem_index_get(ele));
159         }
160         else if (ele->head.htype == BM_EDGE) {
161                 printf("edge %d, ", BM_elem_index_get(ele));
162         }
163         else {
164                 BLI_assert(0);
165         }
166
167         if (ele_from == NULL) {
168                 printf("from NULL\n");
169         }
170         else if (ele_from->head.htype == BM_EDGE) {
171                 printf("from edge %d\n", BM_elem_index_get(ele_from));
172         }
173         else if (ele_from->head.htype == BM_FACE) {
174                 printf("from face %d\n", BM_elem_index_get(ele_from));
175         }
176         else {
177                 BLI_assert(0);
178         }
179 #endif
180
181         /* track distance */
182         {
183                 float co[3];
184                 if (ele->head.htype == BM_VERT) {
185                         copy_v3_v3(co, ((BMVert *)ele)->co);
186                 }
187                 else if (ele->head.htype == BM_EDGE) {
188                         state_calc_co_pair(pc, ((BMEdge *)ele)->v1->co, ((BMEdge *)ele)->v2->co, co);
189                 }
190                 else {
191                         BLI_assert(0);
192                 }
193
194                 /* tally distance */
195                 if (ele_from) {
196                         state->dist += len_v3v3(state->co_prev, co);
197                 }
198                 copy_v3_v3(state->co_prev, co);
199         }
200
201         step_new->ele = ele;
202         step_new->ele_from = ele_from;
203         step_new->next = state->link_last;
204         state->link_last = step_new;
205 }
206
207 static PathLinkState *state_dupe_add(PathContext *pc,
208                                      PathLinkState *state, const PathLinkState *state_orig)
209 {
210         state = MEM_mallocN(sizeof(*state), __func__);
211         *state = *state_orig;
212         BLI_addhead(&pc->state_lb, state);
213         return state;
214 }
215
216 /* walk around the face edges */
217 static PathLinkState *state_step__face_edges(PathContext *pc,
218                                              PathLinkState *state, const PathLinkState *state_orig,
219                                              BMLoop *l_iter, BMLoop *l_last)
220 {
221         do {
222                 if (state_isect_co_pair(pc, l_iter->v->co, l_iter->next->v->co)) {
223                         BMElem *ele_next      = (BMElem *)l_iter->e;
224                         BMElem *ele_next_from = (BMElem *)l_iter->f;
225
226                         if (state_link_find(state, ele_next) == false) {
227                                 if (state_orig->link_last != state->link_last) {
228                                         state = state_dupe_add(pc, state, state_orig);
229                                 }
230                                 state_link_add(pc, state, ele_next, ele_next_from);
231                         }
232                 }
233         } while ((l_iter = l_iter->next) != l_last);
234         return state;
235 }
236
237 /* walk around the face verts */
238 static PathLinkState *state_step__face_verts(PathContext *pc,
239                                              PathLinkState *state, const PathLinkState *state_orig,
240                                              BMLoop *l_iter, BMLoop *l_last)
241 {
242         do {
243                 if (state_isect_co_exact(pc, l_iter->v->co)) {
244                         BMElem *ele_next      = (BMElem *)l_iter->v;
245                         BMElem *ele_next_from = (BMElem *)l_iter->f;
246
247                         if (state_link_find(state, ele_next) == false) {
248                                 if (state_orig->link_last != state->link_last) {
249                                         state = state_dupe_add(pc, state, state_orig);
250                                 }
251                                 state_link_add(pc, state, ele_next, ele_next_from);
252                         }
253                 }
254         } while ((l_iter = l_iter->next) != l_last);
255         return state;
256 }
257
258 static bool state_step(PathContext *pc, PathLinkState *state)
259 {
260         PathLinkState state_orig = *state;
261         BMElem *ele = state->link_last->ele;
262         const void *ele_from = state->link_last->ele_from;
263
264         if (ele->head.htype == BM_EDGE) {
265                 BMEdge *e = (BMEdge *)ele;
266
267                 BMIter liter;
268                 BMLoop *l_start;
269
270                 BM_ITER_ELEM (l_start, &liter, e, BM_LOOPS_OF_EDGE) {
271                         if (l_start->f != ele_from) {
272                                 /* very similar to block below */
273                                 if (BM_vert_in_face(l_start->f, pc->v_b)) {
274                                         if (state_orig.link_last != state->link_last) {
275                                                 state = state_dupe_add(pc, state, &state_orig);
276                                         }
277
278                                         state_link_add(pc, state, (BMElem *)pc->v_b, (BMElem *)l_start->f);
279                                 }
280                                 else {
281                                         state = state_step__face_edges(pc, state, &state_orig,
282                                                                        l_start->next, l_start);
283                                         state = state_step__face_verts(pc, state, &state_orig,
284                                                                        l_start->next->next, l_start);
285                                 }
286                         }
287                 }
288         }
289         else if (ele->head.htype == BM_VERT) {
290                 BMVert *v = (BMVert *)ele;
291
292                 /* vert loops */
293                 {
294                         BMIter liter;
295                         BMLoop *l_start;
296
297                         BM_ITER_ELEM (l_start, &liter, v, BM_LOOPS_OF_VERT) {
298                                 if (l_start->f != ele_from) {
299                                         /* very similar to block above */
300                                         if (BM_vert_in_face(l_start->f, pc->v_b)) {
301                                                 BMElem *ele_next      = (BMElem *)pc->v_b;
302                                                 BMElem *ele_next_from = (BMElem *)l_start->f;
303
304                                                 if (state_orig.link_last != state->link_last) {
305                                                         state = state_dupe_add(pc, state, &state_orig);
306                                                 }
307                                                 state_link_add(pc, state, ele_next, ele_next_from);
308                                         }
309                                         else {
310                                                 state = state_step__face_edges(pc, state, &state_orig,
311                                                                                l_start->next, l_start->prev);
312                                                 if (l_start->f->len > 3) {
313                                                         /* adjacent verts are handled in state_step__vert_edges */
314                                                         state = state_step__face_verts(pc, state, &state_orig,
315                                                                                        l_start->next->next, l_start->prev);
316                                                 }
317                                         }
318                                 }
319                         }
320                 }
321
322                 /* vert edges  */
323                 {
324                         BMIter eiter;
325                         BMEdge *e;
326                         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
327                                 if ((BMElem *)e != ele_from) {
328                                         BMVert *v_other = BM_edge_other_vert(e, v);
329                                         if (v_other == pc->v_b) {
330                                                 BMElem *ele_next      = (BMElem *)pc->v_b;
331                                                 BMElem *ele_next_from = (BMElem *)e;
332
333                                                 if (state_orig.link_last != state->link_last) {
334                                                         state = state_dupe_add(pc, state, &state_orig);
335                                                 }
336                                                 state_link_add(pc, state, ele_next, ele_next_from);
337                                         }
338                                         else {
339                                                 if (state_isect_co_exact(pc, v_other->co)) {
340                                                         BMElem *ele_next      = (BMElem *)v_other;
341                                                         BMElem *ele_next_from = (BMElem *)e;
342                                                         if (state_link_find(state, ele_next) == false) {
343                                                                 if (state_orig.link_last != state->link_last) {
344                                                                         state = state_dupe_add(pc, state, &state_orig);
345                                                                 }
346                                                                 state_link_add(pc, state, ele_next, ele_next_from);
347                                                         }
348                                                 }
349                                         }
350                                 }
351                         }
352                 }
353
354         }
355         else {
356                 BLI_assert(0);
357         }
358         return (state_orig.link_last != state->link_last);
359 }
360
361 void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
362 {
363         BMOpSlot *op_verts_slot = BMO_slot_get(op->slots_in, "verts");
364
365         PathContext pc;
366         bool found_all;
367         float found_dist_best = -1.0f;
368
369         if (op_verts_slot->len != 2) {
370                 /* fail! */
371                 return;
372         }
373
374         pc.v_a = ((BMVert **)op_verts_slot->data.p)[0];
375         pc.v_b = ((BMVert **)op_verts_slot->data.p)[1];
376
377         /* fail! */
378         if (!(pc.v_a && pc.v_b)) {
379                 return;
380         }
381
382 #ifdef DEBUG_PRINT
383         printf("%s: v_a: %d\n", __func__, BM_elem_index_get(pc.v_a));
384         printf("%s: v_b: %d\n", __func__, BM_elem_index_get(pc.v_b));
385 #endif
386
387         /* setup context */
388         {
389                 BLI_listbase_clear(&pc.state_lb);
390                 pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP);
391         }
392
393         /* calculate matrix */
394         {
395                 float basis_dir[3];
396                 float basis_tmp[3];
397                 float basis_nor[3];
398
399
400                 sub_v3_v3v3(basis_dir, pc.v_a->co, pc.v_b->co);
401
402 #if 0
403                 add_v3_v3v3(basis_nor, pc.v_a->no, pc.v_b->no);
404                 cross_v3_v3v3(basis_tmp, basis_nor, basis_dir);
405                 cross_v3_v3v3(basis_nor, basis_tmp, basis_dir);
406 #else
407                 /* align both normals to the directions before combining */
408                 {
409                         float basis_nor_a[3];
410                         float basis_nor_b[3];
411
412                         /* align normal to direction */
413                         cross_v3_v3v3(basis_tmp,   pc.v_a->no, basis_dir);
414                         cross_v3_v3v3(basis_nor_a, basis_tmp,  basis_dir);
415
416                         cross_v3_v3v3(basis_tmp,   pc.v_b->no, basis_dir);
417                         cross_v3_v3v3(basis_nor_b, basis_tmp,  basis_dir);
418
419                         /* combine the normals */
420                         normalize_v3(basis_nor_a);
421                         normalize_v3(basis_nor_b);
422
423                         /* for flipped faces */
424                         if (dot_v3v3(basis_nor_a, basis_nor_b) < 0.0f) {
425                                 negate_v3(basis_nor_b);
426                         }
427                         add_v3_v3v3(basis_nor, basis_nor_a, basis_nor_b);
428                 }
429 #endif
430
431                 /* get third axis */
432                 cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
433
434                 normalize_v3_v3(pc.matrix[0], basis_tmp);
435                 normalize_v3_v3(pc.matrix[1], basis_dir);
436                 normalize_v3_v3(pc.matrix[2], basis_nor);
437                 invert_m3(pc.matrix);
438
439                 pc.axis_sep = dot_m3_v3_row_x(pc.matrix, pc.v_a->co);
440         }
441
442         /* add first vertex */
443         {
444                 PathLinkState *state;
445                 state = MEM_callocN(sizeof(*state), __func__);
446                 BLI_addtail(&pc.state_lb, state);
447                 state_link_add(&pc, state, (BMElem *)pc.v_a, NULL);
448         }
449
450
451         found_all = false;
452         while (pc.state_lb.first) {
453                 PathLinkState *state, *state_next;
454                 found_all = true;
455                 for (state = pc.state_lb.first; state; state = state_next) {
456                         state_next = state->next;
457                         if (state->link_last->ele == (BMElem *)pc.v_b) {
458                                 /* pass, wait until all are found */
459 #ifdef DEBUG_PRINT
460                                 printf("%s: state %p loop found %.4f\n", __func__, state, state->dist);
461 #endif
462                                 if ((found_dist_best == -1.0f) || (found_dist_best > state->dist)) {
463                                         found_dist_best = state->dist;
464                                 }
465                         }
466                         else if (state_step(&pc, state)) {
467                                 if ((found_dist_best != -1.0f) && (found_dist_best <= state->dist)) {
468                                         BLI_remlink(&pc.state_lb, state);
469                                         MEM_freeN(state);
470                                 }
471                                 else {
472                                         found_all = false;
473                                 }
474                         }
475                         else {
476                                 /* didn't reach the end, remove it,
477                                  * links are shared between states so just free the link_pool at the end */
478                                 BLI_remlink(&pc.state_lb, state);
479                                 MEM_freeN(state);
480                         }
481                 }
482
483                 if (found_all) {
484                         break;
485                 }
486         }
487
488         if (BLI_listbase_is_empty(&pc.state_lb)) {
489                 found_all = false;
490         }
491
492         if (found_all) {
493                 PathLinkState *state, *state_best = NULL;
494                 PathLink *link;
495                 float state_best_dist = FLT_MAX;
496
497                 /* find the best state */
498                 for (state = pc.state_lb.first; state; state = state->next) {
499                         if ((state_best == NULL) || (state->dist < state_best_dist)) {
500                                 state_best = state;
501                                 state_best_dist = state_best->dist;
502                         }
503                 }
504
505                 link = state_best->link_last;
506                 do {
507                         if (link->ele->head.htype == BM_EDGE) {
508                                 BMEdge *e = (BMEdge *)link->ele;
509                                 BMVert *v_new;
510                                 float e_fac = state_calc_co_pair_fac(&pc, e->v1->co, e->v2->co);
511                                 v_new = BM_edge_split(bm, e, e->v1, NULL, e_fac);
512                                 BMO_elem_flag_enable(bm, v_new, VERT_OUT);
513                         }
514                         else if (link->ele->head.htype == BM_VERT) {
515                                 BMVert *v = (BMVert *)link->ele;
516                                 BMO_elem_flag_enable(bm, v, VERT_OUT);
517                         }
518                         else {
519                                 BLI_assert(0);
520                         }
521                 } while ((link = link->next));
522         }
523
524         BMO_elem_flag_enable(bm, pc.v_a, VERT_OUT);
525         BMO_elem_flag_enable(bm, pc.v_b, VERT_OUT);
526
527         BLI_mempool_destroy(pc.link_pool);
528         BLI_freelistN(&pc.state_lb);
529
530 #if 1
531         if (found_all) {
532                 /* leave 'check_degenerate' off, if a user tries to cut with 2 verts,
533                  * always connect even when resulting faces are degenerate [#39418] */
534                 BMOperator op_sub;
535                 BMO_op_initf(bm, &op_sub, 0,
536                              "connect_verts verts=%fv", VERT_OUT);
537                 BMO_op_exec(bm, &op_sub);
538                 BMO_slot_copy(&op_sub, slots_out, "edges.out",
539                               op,      slots_out, "edges.out");
540                 BMO_op_finish(bm, &op_sub);
541         }
542 #endif
543 }