Fix error in recent vert/edge-slide commits
[blender.git] / source / blender / bmesh / tools / bmesh_bisect_plane.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/tools/bmesh_bisect_plane.c
24  *  \ingroup bmesh
25  *
26  * Cut the geometry in half using a plane.
27  *
28  * \par Implementation
29  * This simply works by splitting tagged edges whos verts span either side of
30  * the plane, then splitting faces along their dividing verts.
31  * The only complex case is when a ngon spans the axis multiple times,
32  * in this case we need to do some extra checks to correctly bisect the ngon.
33  * see: #bm_face_bisect_verts
34  */
35
36 #include <limits.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BLI_utildefines.h"
41 #include "BLI_stackdefines.h"
42 #include "BLI_alloca.h"
43 #include "BLI_linklist.h"
44 #include "BLI_linklist_stack.h"
45 #include "BLI_math.h"
46
47 #include "bmesh.h"
48 #include "bmesh_bisect_plane.h"  /* own include */
49
50 #include "BLI_strict_flags.h"  /* keep last */
51
52
53 /* -------------------------------------------------------------------- */
54 /* Math utils */
55
56 static short plane_point_test_v3(const float plane[4], const float co[3], const float eps, float *r_depth)
57 {
58         const float f = plane_point_side_v3(plane, co);
59         *r_depth = f;
60
61         if      (f <= -eps) return -1;
62         else if (f >=  eps) return  1;
63         else                return  0;
64 }
65
66
67 /* -------------------------------------------------------------------- */
68 /* Wrappers to hide internal data-structure abuse,
69  * later we may want to move this into some hash lookup
70  * to a separate struct, but for now we can store in BMesh data */
71
72 #define BM_VERT_DIR(v)     ((short *)(&(v)->head.index))[0]    /* Direction -1/0/1 */
73 #define BM_VERT_SKIP(v)    ((short *)(&(v)->head.index))[1]    /* Skip Vert 0/1 */
74 #define BM_VERT_DIST(v)    ((v)->no[0])         /* Distance from the plane. */
75 #define BM_VERT_SORTVAL(v) ((v)->no[1])         /* Temp value for sorting. */
76 #define BM_VERT_LOOPINDEX(v)                    /* The verts index within a face (temp var) */ \
77         (*((unsigned int *)(&(v)->no[2])))
78
79 /**
80  * Hide flag access
81  * (for more readable code since same flag is used differently for vert/edgeface)...
82  */
83
84 /* enable when vertex is in the center and its faces have been added to the stack */
85 BLI_INLINE void vert_is_center_enable(BMVert *v) { BM_elem_flag_enable(v, BM_ELEM_TAG); }
86 BLI_INLINE void vert_is_center_disable(BMVert *v) { BM_elem_flag_disable(v, BM_ELEM_TAG); }
87 BLI_INLINE bool vert_is_center_test(BMVert *v) { return (BM_elem_flag_test(v, BM_ELEM_TAG) != 0); }
88
89 /* enable when the edge can be cut */
90 BLI_INLINE void edge_is_cut_enable(BMEdge *e) { BM_elem_flag_enable(e, BM_ELEM_TAG); }
91 BLI_INLINE void edge_is_cut_disable(BMEdge *e) { BM_elem_flag_disable(e, BM_ELEM_TAG); }
92 BLI_INLINE bool edge_is_cut_test(BMEdge *e) { return (BM_elem_flag_test(e, BM_ELEM_TAG) != 0); }
93
94 /* enable when the faces are added to the stack */
95 BLI_INLINE void face_in_stack_enable(BMFace *f) { BM_elem_flag_disable(f, BM_ELEM_TAG); }
96 BLI_INLINE void face_in_stack_disable(BMFace *f) { BM_elem_flag_enable(f, BM_ELEM_TAG); }
97 BLI_INLINE bool face_in_stack_test(BMFace *f) { return (BM_elem_flag_test(f, BM_ELEM_TAG) == 0); }
98
99 /* -------------------------------------------------------------------- */
100 /* BMesh utils */
101
102 static int bm_vert_sortval_cb(const void *v_a_v, const void *v_b_v)
103 {
104         const float val_a = BM_VERT_SORTVAL(*((BMVert **)v_a_v));
105         const float val_b = BM_VERT_SORTVAL(*((BMVert **)v_b_v));
106
107         if      (val_a > val_b) return  1;
108         else if (val_a < val_b) return -1;
109                                 return  0;
110 }
111
112
113 static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], const short oflag_center)
114 {
115         /* unlikely more than 2 verts are needed */
116         const unsigned int f_len_orig = (unsigned int)f->len;
117         BMVert **vert_split_arr = BLI_array_alloca(vert_split_arr, f_len_orig);
118         STACK_DECLARE(vert_split_arr);
119         BMLoop *l_iter, *l_first;
120         bool use_dirs[3] = {false, false, false};
121         bool is_inside = false;
122
123         STACK_INIT(vert_split_arr, f_len_orig);
124
125         l_first = BM_FACE_FIRST_LOOP(f);
126
127         /* add plane-aligned verts to the stack
128          * and check we have verts from both sides in this face,
129          * ... that the face doesn't only have boundary verts on the plane for eg. */
130         l_iter = l_first;
131         do {
132                 if (vert_is_center_test(l_iter->v)) {
133                         BLI_assert(BM_VERT_DIR(l_iter->v) == 0);
134
135                         /* if both are -1 or 1, or both are zero:
136                          * don't flip 'inside' var while walking */
137                         BM_VERT_SKIP(l_iter->v) = (((BM_VERT_DIR(l_iter->prev->v) ^ BM_VERT_DIR(l_iter->next->v))) == 0);
138
139                         STACK_PUSH(vert_split_arr, l_iter->v);
140                 }
141                 use_dirs[BM_VERT_DIR(l_iter->v) + 1] = true;
142         } while ((l_iter = l_iter->next) != l_first);
143
144         if ((STACK_SIZE(vert_split_arr) > 1) &&
145             (use_dirs[0] && use_dirs[2]))
146         {
147                 if (LIKELY(STACK_SIZE(vert_split_arr) == 2)) {
148                         BMLoop *l_new;
149                         BMLoop *l_a, *l_b;
150
151                         l_a = BM_face_vert_share_loop(f, vert_split_arr[0]);
152                         l_b = BM_face_vert_share_loop(f, vert_split_arr[1]);
153
154                         /* common case, just cut the face once */
155                         BM_face_split(bm, f, l_a, l_b, &l_new, NULL, true);
156                         if (l_new) {
157                                 if (oflag_center) {
158                                         BMO_elem_flag_enable(bm, l_new->e, oflag_center);
159                                         BMO_elem_flag_enable(bm, l_new->f, oflag_center);
160                                         BMO_elem_flag_enable(bm, f,        oflag_center);
161                                 }
162                         }
163                 }
164                 else {
165                         /* less common case, _complicated_ we need to calculate how to do multiple cuts */
166                         float (*face_verts_proj_2d)[2] = BLI_array_alloca(face_verts_proj_2d, f_len_orig);
167                         float axis_mat[3][3];
168
169                         BMFace **face_split_arr = BLI_array_alloca(face_split_arr, STACK_SIZE(vert_split_arr));
170                         STACK_DECLARE(face_split_arr);
171
172                         float sort_dir[3];
173                         unsigned int i;
174
175
176                         /* ---- */
177                         /* Calculate the direction to sort verts in the face intersecting the plane */
178
179                         /* exact dir isn't so important,
180                          * just need a dir for sorting verts across face,
181                          * 'sort_dir' could be flipped either way, it not important, we only need to order the array
182                          */
183                         cross_v3_v3v3(sort_dir, f->no, plane);
184                         if (UNLIKELY(normalize_v3(sort_dir) == 0.0f)) {
185                                 /* find any 2 verts and get their direction */
186                                 for (i = 0; i < STACK_SIZE(vert_split_arr); i++) {
187                                         if (!equals_v3v3(vert_split_arr[0]->co, vert_split_arr[i]->co)) {
188                                                 sub_v3_v3v3(sort_dir, vert_split_arr[0]->co, vert_split_arr[i]->co);
189                                                 normalize_v3(sort_dir);
190                                         }
191                                 }
192                                 if (UNLIKELY(i == STACK_SIZE(vert_split_arr))) {
193                                         /* ok, we can't do anything useful here,
194                                          * face has no area or so, bail out, this is highly unlikely but not impossible */
195                                         goto finally;
196                                 }
197                         }
198
199
200                         /* ---- */
201                         /* Calculate 2d coords to use for intersection checks */
202
203                         /* get the faces 2d coords */
204                         BLI_assert(BM_face_is_normal_valid(f));
205                         axis_dominant_v3_to_m3(axis_mat, f->no);
206
207                         l_iter = l_first;
208                         i = 0;
209                         do {
210                                 BM_VERT_LOOPINDEX(l_iter->v) = i;
211                                 mul_v2_m3v3(face_verts_proj_2d[i], axis_mat, l_iter->v->co);
212                                 i++;
213                         } while ((l_iter = l_iter->next) != l_first);
214
215
216                         /* ---- */
217                         /* Sort the verts across the face from one side to another */
218                         for (i = 0; i < STACK_SIZE(vert_split_arr); i++) {
219                                 BMVert *v = vert_split_arr[i];
220                                 BM_VERT_SORTVAL(v) = dot_v3v3(sort_dir, v->co);
221                         }
222
223                         qsort(vert_split_arr, STACK_SIZE(vert_split_arr), sizeof(*vert_split_arr), bm_vert_sortval_cb);
224
225
226                         /* ---- */
227                         /* Split the face across sorted splits */
228
229                         /* note: we don't know which face gets which splits,
230                          * so at the moment we have to search all faces for the vert pair,
231                          * while not all that nice, typically there are < 5 resulting faces,
232                          * so its not _that_ bad. */
233
234                         STACK_INIT(face_split_arr, STACK_SIZE(vert_split_arr));
235                         STACK_PUSH(face_split_arr, f);
236
237                         for (i = 0; i < STACK_SIZE(vert_split_arr) - 1; i++) {
238                                 BMVert *v_a = vert_split_arr[i];
239                                 BMVert *v_b = vert_split_arr[i + 1];
240
241                                 if (!BM_VERT_SKIP(v_a)) {
242                                         is_inside = !is_inside;
243                                 }
244
245                                 if (is_inside) {
246                                         BMLoop *l_a, *l_b;
247                                         bool found = false;
248                                         unsigned int j;
249
250                                         for (j = 0; j < STACK_SIZE(face_split_arr); j++) {
251                                                 /* would be nice to avoid loop lookup here,
252                                                  * but we need to know which face the verts are in */
253                                                 if ((l_a = BM_face_vert_share_loop(face_split_arr[j], v_a)) &&
254                                                     (l_b = BM_face_vert_share_loop(face_split_arr[j], v_b)))
255                                                 {
256                                                         found = true;
257                                                         break;
258                                                 }
259                                         }
260
261                                         /* ideally wont happen, but it can for self intersecting faces */
262                                         // BLI_assert(found == true);
263
264                                         /* in fact this simple test is good enough,
265                                          * test if the loops are adjacent */
266                                         if (found && !BM_loop_is_adjacent(l_a, l_b)) {
267                                                 BMFace *f_tmp;
268                                                 f_tmp = BM_face_split(bm, face_split_arr[j], l_a, l_b, NULL, NULL, true);
269                                                 if (f_tmp) {
270                                                         if (f_tmp != face_split_arr[j]) {
271                                                                 STACK_PUSH(face_split_arr, f_tmp);
272                                                                 BLI_assert(STACK_SIZE(face_split_arr) <= STACK_SIZE(vert_split_arr));
273                                                         }
274                                                 }
275                                         }
276                                 }
277                                 else {
278                                         // printf("no intersect\n");
279                                 }
280                         }
281                 }
282         }
283
284
285 finally:
286         (void)vert_split_arr;
287 }
288
289 /* -------------------------------------------------------------------- */
290 /* Main logic */
291
292 /**
293  * \param use_snap_center  Snap verts onto the plane.
294  * \param use_tag  Only bisect tagged edges and faces.
295  * \param oflag_center  Operator flag, enabled for geometry on the axis (existing and created)
296  */
297 void BM_mesh_bisect_plane(
298         BMesh *bm, const float plane[4],
299         const bool use_snap_center, const bool use_tag,
300         const short oflag_center, const float eps)
301 {
302         unsigned int einput_len;
303         unsigned int i;
304         BMEdge **edges_arr = MEM_mallocN(sizeof(*edges_arr) * (size_t)bm->totedge, __func__);
305
306         BLI_LINKSTACK_DECLARE(face_stack, BMFace *);
307
308         BMVert *v;
309         BMFace *f;
310
311         BMIter iter;
312
313         if (use_tag) {
314                 /* build tagged edge array */
315                 BMEdge *e;
316                 einput_len = 0;
317
318                 /* flush edge tags to verts */
319                 BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, false);
320
321                 /* keep face tags as is */
322                 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
323                         if (edge_is_cut_test(e)) {
324                                 edges_arr[einput_len++] = e;
325
326                                 /* flush edge tags to verts */
327                                 BM_elem_flag_enable(e->v1, BM_ELEM_TAG);
328                                 BM_elem_flag_enable(e->v2, BM_ELEM_TAG);
329                         }
330                 }
331
332                 /* face tags are set by caller */
333         }
334         else {
335                 BMEdge *e;
336                 einput_len = (unsigned int)bm->totedge;
337                 BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
338                         edge_is_cut_enable(e);
339                         edges_arr[i] = e;
340                 }
341
342                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
343                         face_in_stack_disable(f);
344                 }
345         }
346
347
348         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
349
350                 if (use_tag && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
351                         vert_is_center_disable(v);
352
353                         /* these should never be accessed */
354                         BM_VERT_DIR(v) = 0;
355                         BM_VERT_DIST(v) = 0.0f;
356
357                         continue;
358                 }
359
360                 vert_is_center_disable(v);
361                 BM_VERT_DIR(v) = plane_point_test_v3(plane, v->co, eps, &(BM_VERT_DIST(v)));
362
363                 if (BM_VERT_DIR(v) == 0) {
364                         if (oflag_center) {
365                                 BMO_elem_flag_enable(bm, v, oflag_center);
366                         }
367                         if (use_snap_center) {
368                                 closest_to_plane_v3(v->co, plane, v->co);
369                         }
370                 }
371         }
372
373         /* store a stack of faces to be evaluated for splitting */
374         BLI_LINKSTACK_INIT(face_stack);
375
376         for (i = 0; i < einput_len; i++) {
377                 /* we could check edge_is_cut_test(e) but there is no point */
378                 BMEdge *e = edges_arr[i];
379                 const int side[2] = {BM_VERT_DIR(e->v1), BM_VERT_DIR(e->v2)};
380                 const float dist[2] = {BM_VERT_DIST(e->v1), BM_VERT_DIST(e->v2)};
381
382                 if (side[0] && side[1] && (side[0] != side[1])) {
383                         const float e_fac = fabsf(dist[0]) / fabsf(dist[0] - dist[1]);
384                         BMVert *v_new;
385
386                         if (e->l) {
387                                 BMLoop *l_iter, *l_first;
388                                 l_iter = l_first = e->l;
389                                 do {
390                                         if (!face_in_stack_test(l_iter->f)) {
391                                                 face_in_stack_enable(l_iter->f);
392                                                 BLI_LINKSTACK_PUSH(face_stack, l_iter->f);
393                                         }
394                                 } while ((l_iter = l_iter->radial_next) != l_first);
395                         }
396
397                         v_new = BM_edge_split(bm, e, e->v1, NULL, e_fac);
398                         vert_is_center_enable(v_new);
399                         if (oflag_center) {
400                                 BMO_elem_flag_enable(bm, v_new, oflag_center);
401                         }
402
403                         BM_VERT_DIR(v_new) = 0;
404                         BM_VERT_DIST(v_new) = 0.0f;
405                 }
406                 else if (side[0] == 0 || side[1] == 0) {
407                         /* check if either edge verts are aligned,
408                          * if so - tag and push all faces that use it into the stack */
409                         unsigned int j;
410                         BM_ITER_ELEM_INDEX (v, &iter, e, BM_VERTS_OF_EDGE, j) {
411                                 if (side[j] == 0) {
412                                         if (vert_is_center_test(v) == 0) {
413                                                 BMIter itersub;
414                                                 BMLoop *l_iter;
415
416                                                 vert_is_center_enable(v);
417
418                                                 BM_ITER_ELEM (l_iter, &itersub, v, BM_LOOPS_OF_VERT) {
419                                                         if (!face_in_stack_test(l_iter->f)) {
420                                                                 face_in_stack_enable(l_iter->f);
421                                                                 BLI_LINKSTACK_PUSH(face_stack, l_iter->f);
422                                                         }
423                                                 }
424
425                                         }
426                                 }
427                         }
428
429                         /* if both verts are on the center - tag it */
430                         if (oflag_center) {
431                                 if (side[0] == 0 && side[1] == 0) {
432                                         BMO_elem_flag_enable(bm, e, oflag_center);
433                                 }
434                         }
435                 }
436         }
437
438         MEM_freeN(edges_arr);
439
440         while ((f = BLI_LINKSTACK_POP(face_stack))) {
441                 bm_face_bisect_verts(bm, f, plane, oflag_center);
442         }
443
444         /* now we have all faces to split in the stack */
445         BLI_LINKSTACK_FREE(face_stack);
446 }