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