Merged revision(s) 58452-58584 from trunk/blender into soc-2013-dingto.
[blender-staging.git] / source / blender / editors / mesh / editmesh_knife.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  * The Original Code is Copyright (C) 2007 Blender Foundation.
19  * All rights reserved.
20  *
21  * 
22  * Contributor(s): Joseph Eagar, Joshua Leung, Howard Trickey,
23  *                 Campbell Barton
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/mesh/editmesh_knife.c
29  *  \ingroup edmesh
30  */
31
32 #ifdef _MSC_VER
33 #  define _USE_MATH_DEFINES
34 #endif
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_listbase.h"
39 #include "BLI_string.h"
40 #include "BLI_array.h"
41 #include "BLI_linklist.h"
42 #include "BLI_math.h"
43 #include "BLI_smallhash.h"
44 #include "BLI_memarena.h"
45
46 #include "BLF_translation.h"
47
48 #include "BKE_DerivedMesh.h"
49 #include "BKE_context.h"
50 #include "BKE_editmesh.h"
51 #include "BKE_editmesh_bvh.h"
52
53 #include "BIF_gl.h"
54 #include "BIF_glutil.h" /* for paint cursor */
55
56 #include "ED_screen.h"
57 #include "ED_space_api.h"
58 #include "ED_view3d.h"
59 #include "ED_mesh.h"
60
61 #include "WM_api.h"
62 #include "WM_types.h"
63
64 #include "DNA_object_types.h"
65 #include "UI_resources.h"
66
67 #include "RNA_access.h"
68 #include "RNA_define.h"
69
70 #include "mesh_intern.h"  /* own include */
71
72 /* this code here is kindof messy. . .I might need to eventually rework it - joeedh */
73
74 #define KMAXDIST    10  /* max mouse distance from edge before not detecting it */
75
76 #define KNIFE_FLT_EPS          0.00001f
77 #define KNIFE_FLT_EPS_SQUARED  (KNIFE_FLT_EPS * KNIFE_FLT_EPS)
78
79 typedef struct KnifeColors {
80         unsigned char line[3];
81         unsigned char edge[3];
82         unsigned char curpoint[3];
83         unsigned char curpoint_a[4];
84         unsigned char point[3];
85         unsigned char point_a[4];
86 } KnifeColors;
87
88 /* knifetool operator */
89 typedef struct KnifeVert {
90         BMVert *v; /* non-NULL if this is an original vert */
91         ListBase edges;
92         ListBase faces;
93
94         float co[3], cageco[3], sco[2]; /* sco is screen coordinates for cageco */
95         bool is_face, in_space;
96         bool draw;
97 } KnifeVert;
98
99 typedef struct Ref {
100         struct Ref *next, *prev;
101         void *ref;
102 } Ref;
103
104 typedef struct KnifeEdge {
105         KnifeVert *v1, *v2;
106         BMFace *basef; /* face to restrict face fill to */
107         ListBase faces;
108
109         BMEdge *e /* , *e_old */; /* non-NULL if this is an original edge */
110         bool draw;
111 } KnifeEdge;
112
113 typedef struct BMEdgeHit {
114         KnifeEdge *kfe;
115         float hit[3], cagehit[3];
116         float realhit[3]; /* used in midpoint mode */
117         float schit[2];
118         float l; /* lambda along cut line */
119         float perc; /* lambda along hit line */
120         KnifeVert *v; /* set if snapped to a vert */
121         BMFace *f;
122 } BMEdgeHit;
123
124 typedef struct KnifePosData {
125         float co[3];
126         float cage[3];
127
128         /* At most one of vert, edge, or bmface should be non-NULL,
129          * saying whether the point is snapped to a vertex, edge, or in a face.
130          * If none are set, this point is in space and is_space should be true. */
131         KnifeVert *vert;
132         KnifeEdge *edge;
133         BMFace *bmface;
134         bool is_space;
135
136         float mval[2]; /* mouse screen position (may be non-integral if snapped to something) */
137 } KnifePosData;
138
139 /* struct for properties used while drawing */
140 typedef struct KnifeTool_OpData {
141         ARegion *ar;        /* region that knifetool was activated in */
142         void *draw_handle;  /* for drawing preview loop */
143         ViewContext vc;     /* note: _don't_ use 'mval', instead use the one we define below */
144         float mval[2];      /* mouse value with snapping applied */
145         //bContext *C;
146
147         Object *ob;
148         BMEditMesh *em;
149
150         MemArena *arena;
151
152         GHash *origvertmap;
153         GHash *origedgemap;
154
155         GHash *kedgefacemap;
156
157         BMBVHTree *bmbvh;
158
159         BLI_mempool *kverts;
160         BLI_mempool *kedges;
161
162         float vthresh;
163         float ethresh;
164
165         /* used for drag-cutting */
166         BMEdgeHit *linehits;
167         int totlinehit;
168
169         /* Data for mouse-position-derived data (cur) and previous click (prev) */
170         KnifePosData curr, prev;
171
172         int totkedge, totkvert;
173
174         BLI_mempool *refs;
175
176         float projmat[4][4];
177
178         KnifeColors colors;
179
180         /* run by the UI or not */
181         bool is_interactive;
182
183         /* operatpr options */
184         bool cut_through;    /* preference, can be modified at runtime (that feature may go) */
185         bool only_select;    /* set on initialization */
186         bool select_result;  /* set on initialization */
187
188         bool is_ortho;
189         float ortho_extent;
190         float clipsta, clipend;
191
192         enum {
193                 MODE_IDLE,
194                 MODE_DRAGGING,
195                 MODE_CONNECT,
196                 MODE_PANNING
197         } mode;
198
199         int prevmode;
200         bool snap_midpoints, extend;
201         bool ignore_edge_snapping;
202         bool ignore_vert_snapping;
203
204         enum {
205                 ANGLE_FREE,
206                 ANGLE_0,
207                 ANGLE_45,
208                 ANGLE_90,
209                 ANGLE_135
210         } angle_snapping;
211
212         const float (*cagecos)[3];
213 } KnifeTool_OpData;
214
215 static ListBase *knife_get_face_kedges(KnifeTool_OpData *kcd, BMFace *f);
216
217 #if 0
218 static void knife_input_ray_cast(KnifeTool_OpData *kcd, const float mval[2],
219                                  float r_origin[3], float r_ray[3]);
220 #endif
221 static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
222                                     float r_origin[3], float r_dest[3]);
223
224 static void knife_update_header(bContext *C, KnifeTool_OpData *kcd)
225 {
226         #define HEADER_LENGTH 256
227         char header[HEADER_LENGTH];
228
229         BLI_snprintf(header, HEADER_LENGTH, IFACE_("LMB: define cut lines, Return/Spacebar: confirm, Esc or RMB: cancel, "
230                                                    "E: new cut, Ctrl: midpoint snap (%s), Shift: ignore snap (%s), "
231                                                    "C: angle constrain (%s), Z: cut through (%s)"),
232                      kcd->snap_midpoints ? IFACE_("On") : IFACE_("Off"),
233                      kcd->ignore_edge_snapping ?  IFACE_("On") : IFACE_("Off"),
234                      kcd->angle_snapping ? IFACE_("On") : IFACE_("Off"),
235                      kcd->cut_through ? IFACE_("On") : IFACE_("Off"));
236
237         ED_area_headerprint(CTX_wm_area(C), header);
238 }
239
240 #if 0
241 BLI_INLINE int round_ftoi(float x)
242 {
243         return x > 0.0f ?  (int)(x + 0.5f) : (int)(x - 0.5f);
244 }
245 #endif
246
247 static void knife_project_v2(const KnifeTool_OpData *kcd, const float co[3], float sco[2])
248 {
249         ED_view3d_project_float_v2_m4(kcd->ar, co, sco, (float (*)[4])kcd->projmat);
250 }
251
252 static void knife_pos_data_clear(KnifePosData *kpd)
253 {
254         zero_v3(kpd->co);
255         zero_v3(kpd->cage);
256         kpd->vert = NULL;
257         kpd->edge = NULL;
258         kpd->bmface = NULL;
259         zero_v2(kpd->mval);
260 }
261
262 static ListBase *knife_empty_list(KnifeTool_OpData *kcd)
263 {
264         ListBase *lst;
265
266         lst = BLI_memarena_alloc(kcd->arena, sizeof(ListBase));
267         lst->first = lst->last = NULL;
268         return lst;
269 }
270
271 static void knife_append_list(KnifeTool_OpData *kcd, ListBase *lst, void *elem)
272 {
273         Ref *ref;
274
275         ref = BLI_mempool_calloc(kcd->refs);
276         ref->ref = elem;
277         BLI_addtail(lst, ref);
278 }
279
280 static Ref *find_ref(ListBase *lb, void *ref)
281 {
282         Ref *ref1;
283
284         for (ref1 = lb->first; ref1; ref1 = ref1->next) {
285                 if (ref1->ref == ref)
286                         return ref1;
287         }
288
289         return NULL;
290 }
291
292 static KnifeEdge *new_knife_edge(KnifeTool_OpData *kcd)
293 {
294         kcd->totkedge++;
295         return BLI_mempool_calloc(kcd->kedges);
296 }
297
298 static void knife_add_to_vert_edges(KnifeTool_OpData *kcd, KnifeEdge *kfe)
299 {
300         knife_append_list(kcd, &kfe->v1->edges, kfe);
301         knife_append_list(kcd, &kfe->v2->edges, kfe);
302 }
303
304 /* Add faces of an edge to a KnifeVert's faces list.  No checks for dups. */
305 static void knife_add_edge_faces_to_vert(KnifeTool_OpData *kcd, KnifeVert *kfv, BMEdge *e)
306 {
307         BMIter bmiter;
308         BMFace *f;
309
310         BM_ITER_ELEM(f, &bmiter, e, BM_FACES_OF_EDGE) {
311                 knife_append_list(kcd, &kfv->faces, f);
312         }
313 }
314
315 /* Find a face in common in the two faces lists.
316  * If more than one, return the first; if none, return NULL */
317 static BMFace *knife_find_common_face(ListBase *faces1, ListBase *faces2)
318 {
319         Ref *ref1, *ref2;
320
321         for (ref1 = faces1->first; ref1; ref1 = ref1->next) {
322                 for (ref2 = faces2->first; ref2; ref2 = ref2->next) {
323                         if (ref1->ref == ref2->ref)
324                                 return (BMFace *)(ref1->ref);
325                 }
326         }
327         return NULL;
328 }
329
330 static KnifeVert *new_knife_vert(KnifeTool_OpData *kcd, const float co[3], const float cageco[3])
331 {
332         KnifeVert *kfv = BLI_mempool_calloc(kcd->kverts);
333
334         kcd->totkvert++;
335
336         copy_v3_v3(kfv->co, co);
337         copy_v3_v3(kfv->cageco, cageco);
338
339         knife_project_v2(kcd, kfv->co, kfv->sco);
340
341         return kfv;
342 }
343
344 /* get a KnifeVert wrapper for an existing BMVert */
345 static KnifeVert *get_bm_knife_vert(KnifeTool_OpData *kcd, BMVert *v)
346 {
347         KnifeVert *kfv = BLI_ghash_lookup(kcd->origvertmap, v);
348
349         if (!kfv) {
350                 BMIter bmiter;
351                 BMFace *f;
352
353                 kfv = new_knife_vert(kcd, v->co, kcd->cagecos[BM_elem_index_get(v)]);
354                 kfv->v = v;
355                 BLI_ghash_insert(kcd->origvertmap, v, kfv);
356                 BM_ITER_ELEM(f, &bmiter, v, BM_FACES_OF_VERT) {
357                         knife_append_list(kcd, &kfv->faces, f);
358                 }
359         }
360
361         return kfv;
362 }
363
364 /* get a KnifeEdge wrapper for an existing BMEdge */
365 static KnifeEdge *get_bm_knife_edge(KnifeTool_OpData *kcd, BMEdge *e)
366 {
367         KnifeEdge *kfe = BLI_ghash_lookup(kcd->origedgemap, e);
368         if (!kfe) {
369                 BMIter bmiter;
370                 BMFace *f;
371
372                 kfe = new_knife_edge(kcd);
373                 kfe->e = e;
374                 kfe->v1 = get_bm_knife_vert(kcd, e->v1);
375                 kfe->v2 = get_bm_knife_vert(kcd, e->v2);
376
377                 knife_add_to_vert_edges(kcd, kfe);
378
379                 BLI_ghash_insert(kcd->origedgemap, e, kfe);
380
381                 BM_ITER_ELEM(f, &bmiter, e, BM_FACES_OF_EDGE) {
382                         knife_append_list(kcd, &kfe->faces, f);
383                 }
384         }
385
386         return kfe;
387 }
388
389 /* User has just clicked for first time or first time after a restart (E key).
390  * Copy the current position data into prev. */
391 static void knife_start_cut(KnifeTool_OpData *kcd)
392 {
393         kcd->prev = kcd->curr;
394         kcd->curr.is_space = 0; /*TODO: why do we do this? */
395
396         if (kcd->prev.vert == NULL && kcd->prev.edge == NULL && is_zero_v3(kcd->prev.cage)) {
397                 /* Make prevcage a point on the view ray to mouse closest to a point on model: choose vertex 0 */
398                 float origin[3], origin_ofs[3];
399                 BMVert *v0;
400
401                 knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
402                 v0 = BM_vert_at_index(kcd->em->bm, 0);
403                 if (v0) {
404                         closest_to_line_v3(kcd->prev.cage, v0->co, origin_ofs, origin);
405                         copy_v3_v3(kcd->prev.co, kcd->prev.cage); /*TODO: do we need this? */
406                         copy_v3_v3(kcd->curr.cage, kcd->prev.cage);
407                         copy_v3_v3(kcd->curr.co, kcd->prev.co);
408                 }
409         }
410 }
411
412 static ListBase *knife_get_face_kedges(KnifeTool_OpData *kcd, BMFace *f)
413 {
414         ListBase *lst = BLI_ghash_lookup(kcd->kedgefacemap, f);
415
416         if (!lst) {
417                 BMIter bmiter;
418                 BMEdge *e;
419
420                 lst = knife_empty_list(kcd);
421
422                 BM_ITER_ELEM(e, &bmiter, f, BM_EDGES_OF_FACE) {
423                         knife_append_list(kcd, lst, get_bm_knife_edge(kcd, e));
424                 }
425
426                 BLI_ghash_insert(kcd->kedgefacemap, f, lst);
427         }
428
429         return lst;
430 }
431
432 /* finds the proper face to restrict face fill to */
433 static void knife_find_basef(KnifeEdge *kfe)
434 {
435         kfe->basef = knife_find_common_face(&kfe->v1->faces, &kfe->v2->faces);
436 }
437
438 static void knife_edge_append_face(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMFace *f)
439 {
440         knife_append_list(kcd, knife_get_face_kedges(kcd, f), kfe);
441         knife_append_list(kcd, &kfe->faces, f);
442 }
443
444 static KnifeVert *knife_split_edge(KnifeTool_OpData *kcd, KnifeEdge *kfe, float co[3], KnifeEdge **newkfe_out)
445 {
446         KnifeEdge *newkfe = new_knife_edge(kcd);
447         Ref *ref;
448         BMFace *f;
449         float perc, cageco[3], l12;
450
451         l12 = len_v3v3(kfe->v1->co, kfe->v2->co);
452         if (l12 < KNIFE_FLT_EPS) {
453                 copy_v3_v3(cageco, kfe->v1->cageco);
454         }
455         else {
456                 perc = len_v3v3(co, kfe->v1->co) / l12;
457                 interp_v3_v3v3(cageco, kfe->v1->cageco, kfe->v2->cageco, perc);
458         }
459
460         newkfe->v1 = kfe->v1;
461         newkfe->v2 = new_knife_vert(kcd, co, cageco);
462         newkfe->v2->draw = 1;
463         if (kfe->e) {
464                 knife_add_edge_faces_to_vert(kcd, newkfe->v2, kfe->e);
465         }
466         else {
467                 /* kfe cuts across an existing face.
468                  * If v1 and v2 are in multiple faces together (e.g., if they
469                  * are in doubled polys) then this arbitrarily chooses one of them */
470                 f = knife_find_common_face(&kfe->v1->faces, &kfe->v2->faces);
471                 if (f)
472                         knife_append_list(kcd, &newkfe->v2->faces, f);
473         }
474         newkfe->basef = kfe->basef;
475
476         ref = find_ref(&kfe->v1->edges, kfe);
477         BLI_remlink(&kfe->v1->edges, ref);
478
479         kfe->v1 = newkfe->v2;
480         BLI_addtail(&kfe->v1->edges, ref);
481
482         for (ref = kfe->faces.first; ref; ref = ref->next)
483                 knife_edge_append_face(kcd, newkfe, ref->ref);
484
485         knife_add_to_vert_edges(kcd, newkfe);
486
487         newkfe->draw = kfe->draw;
488         newkfe->e = kfe->e;
489
490         *newkfe_out = newkfe;
491
492         return newkfe->v2;
493 }
494
495 /* Make a single KnifeEdge for cut from kcd->prev to kcd->curr.
496  * and move cur data to prev. */
497 static void knife_add_single_cut(KnifeTool_OpData *kcd)
498 {
499         KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
500
501         if (kcd->prev.vert && kcd->prev.vert == kcd->curr.vert)
502                 return;
503         if (kcd->prev.edge && kcd->prev.edge == kcd->curr.edge)
504                 return;
505
506         kfe->draw = true;
507
508         if (kcd->prev.vert) {
509                 kfe->v1 = kcd->prev.vert;
510         }
511         else if (kcd->prev.edge) {
512                 kfe->v1 = knife_split_edge(kcd, kcd->prev.edge, kcd->prev.co, &kfe2);
513         }
514         else {
515                 kfe->v1 = new_knife_vert(kcd, kcd->prev.co, kcd->prev.co);
516                 kfe->v1->draw = kfe->draw = !kcd->prev.is_space;
517                 kfe->v1->in_space = kcd->prev.is_space;
518                 kfe->draw = !kcd->prev.is_space;
519                 kfe->v1->is_face = true;
520                 if (kfe->v1->draw && kcd->prev.bmface)
521                         knife_append_list(kcd, &kfe->v1->faces, kcd->prev.bmface);
522         }
523
524         if (kcd->curr.vert) {
525                 kfe->v2 = kcd->curr.vert;
526         }
527         else if (kcd->curr.edge) {
528                 kfe->v2 = knife_split_edge(kcd, kcd->curr.edge, kcd->curr.co, &kfe3);
529                 kcd->curr.vert = kfe->v2;
530         }
531         else {
532                 kfe->v2 = new_knife_vert(kcd, kcd->curr.co, kcd->curr.co);
533                 kfe->v2->draw = !kcd->curr.is_space;
534                 kfe->v2->is_face = true;
535                 kfe->v2->in_space = kcd->curr.is_space;
536                 if (kfe->v2->draw && kcd->curr.bmface)
537                         knife_append_list(kcd, &kfe->v2->faces, kcd->curr.bmface);
538
539                 if (kcd->curr.is_space)
540                         kfe->draw = false;
541
542                 kcd->curr.vert = kfe->v2;
543         }
544
545         knife_find_basef(kfe);
546
547         knife_add_to_vert_edges(kcd, kfe);
548
549         if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
550                 knife_edge_append_face(kcd, kfe, kfe->basef);
551
552         /* sanity check to make sure we're in the right edge/face lists */
553         if (kcd->curr.bmface) {
554                 if (!find_ref(&kfe->faces, kcd->curr.bmface)) {
555                         knife_edge_append_face(kcd, kfe, kcd->curr.bmface);
556                 }
557
558                 if (kcd->prev.bmface && kcd->prev.bmface != kcd->curr.bmface) {
559                         if (!find_ref(&kfe->faces, kcd->prev.bmface)) {
560                                 knife_edge_append_face(kcd, kfe, kcd->prev.bmface);
561                         }
562                 }
563         }
564
565         /* set up for next cut */
566         kcd->prev = kcd->curr;
567 }
568
569 static int verge_linehit(const void *vlh1, const void *vlh2)
570 {
571         const BMEdgeHit *lh1 = vlh1, *lh2 = vlh2;
572
573         if      (lh1->l < lh2->l) return -1;
574         else if (lh1->l > lh2->l) return 1;
575         else return 0;
576 }
577
578 /* If there's a linehit connected (same face) as testi in range [firsti, lasti], return the first such, else -1.
579  * If testi is out of range, look for connection to f instead, if f is non-NULL */
580 static int find_connected_linehit(KnifeTool_OpData *kcd, int testi, BMFace *f, int firsti, int lasti)
581 {
582         int i;
583
584         for (i = firsti; i <= lasti; i++) {
585                 if (testi >= 0 && testi < kcd->totlinehit) {
586                         if (knife_find_common_face(&kcd->linehits[testi].kfe->faces,
587                                                    &kcd->linehits[i].kfe->faces))
588                         {
589                                 return i;
590                         }
591                 }
592                 else if (f) {
593                         if (find_ref(&kcd->linehits[i].kfe->faces, f))
594                                 return i;
595                 }
596         }
597         return -1;
598 }
599
600 /* Sort in order of distance along cut line, but take care when distances are equal */
601 static void knife_sort_linehits(KnifeTool_OpData *kcd)
602 {
603         int i, j, k, nexti, nsame;
604
605         qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
606
607         /* for ranges of equal "l", swap if neccesary to make predecessor and
608          * successor faces connected to the linehits at either end of the range */
609         for (i = 0; i < kcd->totlinehit - 1; i = nexti) {
610                 for (j = i + 1; j < kcd->totlinehit; j++) {
611                         if (fabsf(kcd->linehits[j].l - kcd->linehits[i].l) > KNIFE_FLT_EPS)
612                                 break;
613                 }
614                 nexti = j;
615                 j--;
616                 nsame = j - i;
617                 if (nsame > 0) {
618                         /* find something connected to predecessor of equal range */
619                         k = find_connected_linehit(kcd, i - 1, kcd->prev.bmface, i, j);
620                         if (k != -1) {
621                                 if (k != i) {
622                                         SWAP(BMEdgeHit, kcd->linehits[i], kcd->linehits[k]);
623                                 }
624                                 i++;
625                                 nsame--;
626                         }
627                         if (nsame > 0) {
628                                 /* find something connected to successor of equal range */
629                                 k = find_connected_linehit(kcd, j + 1, kcd->curr.bmface, i, j);
630                                 if (k != -1 && k != j) {
631                                         SWAP(BMEdgeHit, kcd->linehits[j], kcd->linehits[k]);
632                                 }
633                         }
634                         /* rest of same range doesn't matter because we won't connect them */
635                 }
636         }
637 }
638
639 static void knife_add_single_cut_through(KnifeTool_OpData *kcd, KnifeVert *v1, KnifeVert *v2, BMFace *f)
640 {
641         KnifeEdge *kfenew;
642
643         kfenew = new_knife_edge(kcd);
644         kfenew->basef = f;
645         kfenew->v1 = v1;
646         kfenew->v2 = v2;
647         kfenew->draw = true;
648
649         knife_add_to_vert_edges(kcd, kfenew);
650
651         if (!find_ref(&kfenew->faces, f))
652                 knife_edge_append_face(kcd, kfenew, f);
653 }
654
655 static void knife_get_vert_faces(KnifeTool_OpData *kcd, KnifeVert *kfv, BMFace *facef, ListBase *lst)
656 {
657         BMIter bmiter;
658         BMFace *f;
659         Ref *r;
660
661         if (kfv->is_face && facef) {
662                 knife_append_list(kcd, lst, facef);
663         }
664         else if (kfv->v) {
665                 BM_ITER_ELEM (f, &bmiter, kfv->v, BM_FACES_OF_VERT) {
666                         knife_append_list(kcd, lst, f);
667                 }
668         }
669         else {
670                 for (r = kfv->faces.first; r; r = r->next) {
671                         knife_append_list(kcd, lst, r->ref);
672                 }
673         }
674 }
675
676 static void knife_get_edge_faces(KnifeTool_OpData *kcd, KnifeEdge *kfe, ListBase *lst)
677 {
678         BMIter bmiter;
679         BMFace *f;
680
681         if (kfe->e) {
682                 BM_ITER_ELEM (f, &bmiter, kfe->e, BM_FACES_OF_EDGE) {
683                         knife_append_list(kcd, lst, f);
684                 }
685         }
686 }
687
688 /* BMESH_TODO: add more functionality to cut-through:
689  *    - cutting "in face" (e.g., holes) should cut in all faces, not just visible one
690  *    - perhaps improve O(n^2) algorithm used here */
691 static void knife_cut_through(KnifeTool_OpData *kcd)
692 {
693         BMEdgeHit *lh, *lh2;
694         BMFace *f;
695         KnifeEdge *kfe, *kfe2, *kfe3;
696         KnifeVert *v1, *v2, *firstv = NULL, *lastv = NULL;
697         ListBase firstfaces = {NULL, NULL}, lastfaces = {NULL, NULL};
698         Ref *r, *r2;
699         KnifeEdge **splitkfe;
700         int i, j;
701
702         if (!kcd->totlinehit) {
703                 /* if no linehits then no interesting back face stuff to do */
704                 knife_add_single_cut(kcd);
705                 return;
706         }
707
708         /* TODO: probably don't need to sort at all */
709         qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
710         splitkfe = MEM_callocN(kcd->totlinehit * sizeof(KnifeEdge *), "knife_cut_through");
711
712         if (kcd->prev.vert) {
713                 if (kcd->prev.vert == kcd->curr.vert)
714                         return;
715                 firstv = kcd->prev.vert;
716                 knife_get_vert_faces(kcd, firstv, kcd->prev.bmface, &firstfaces);
717         }
718         else if (kcd->prev.edge) {
719                 if (kcd->prev.edge == kcd->curr.edge)
720                         return;
721                 firstv = knife_split_edge(kcd, kcd->prev.edge, kcd->prev.co, &kfe3);
722                 knife_get_edge_faces(kcd, kcd->prev.edge, &firstfaces);
723         }
724
725         if (kcd->curr.vert) {
726                 lastv = kcd->curr.vert;
727                 knife_get_vert_faces(kcd, lastv, kcd->curr.bmface, &lastfaces);
728         }
729         else if (kcd->curr.edge) {
730                 lastv = knife_split_edge(kcd, kcd->curr.edge, kcd->curr.co, &kfe3);
731                 knife_get_edge_faces(kcd, kcd->curr.edge, &lastfaces);
732         }
733
734         if (firstv) {
735                 /* For each face incident to firstv,
736                  * find the first following linehit (if any) sharing that face and connect */
737                 for (r = firstfaces.first; r; r = r->next) {
738                         bool found = false;
739                         f = r->ref;
740                         for (j = 0, lh2 = kcd->linehits; j < kcd->totlinehit && !found; j++, lh2++) {
741                                 kfe2 = lh2->kfe;
742                                 for (r2 = kfe2->faces.first; r2; r2 = r2->next) {
743                                         if (r2->ref == f) {
744                                                 v2 = splitkfe[j] ? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
745                                                 knife_add_single_cut_through(kcd, firstv, v2, f);
746                                                 found = true;
747                                                 break;
748                                         }
749                                 }
750                         }
751                         if (!found && lastv) {
752                                 for (r2 = lastfaces.first; r2; r2 = r2->next) {
753                                         if (r2->ref == f) {
754                                                 knife_add_single_cut_through(kcd, firstv, lastv, f);
755                                                 break;
756                                         }
757                                 }
758                         }
759                 }
760         }
761
762         for (i = 0, lh = kcd->linehits; i < kcd->totlinehit; i++, lh++) {
763                 kfe = lh->kfe;
764
765                 /* For each face attached to edge for this linehit,
766                  * find the first following linehit (if any) sharing that face and connect */
767                 for (r = kfe->faces.first; r; r = r->next) {
768                         bool found = false;
769                         f = r->ref;
770                         for (j = i + 1, lh2 = lh + 1; j < kcd->totlinehit && !found; j++, lh2++) {
771                                 kfe2 = lh2->kfe;
772                                 for (r2 = kfe2->faces.first; r2; r2 = r2->next) {
773                                         if (r2->ref == f) {
774                                                 v1 = splitkfe[i] ? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
775                                                 v2 = splitkfe[j] ? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
776                                                 knife_add_single_cut_through(kcd, v1, v2, f);
777                                                 found = true;
778                                                 break;
779                                         }
780                                 }
781                         }
782                         if (!found && lastv) {
783                                 for (r2 = lastfaces.first; r2; r2 = r2->next) {
784                                         if (r2->ref == f) {
785                                                 v1 = splitkfe[i] ? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
786                                                 knife_add_single_cut_through(kcd, v1, lastv, f);
787                                                 break;
788                                         }
789                                 }
790                         }
791                 }
792         }
793
794         MEM_freeN(splitkfe);
795         MEM_freeN(kcd->linehits);
796         kcd->linehits = NULL;
797         kcd->totlinehit = 0;
798
799         /* set up for next cut */
800         kcd->curr.vert = lastv;
801         kcd->prev = kcd->curr;
802 }
803
804 /* User has just left-clicked after the first time.
805  * Add all knife cuts implied by line from prev to curr.
806  * If that line crossed edges then kcd->linehits will be non-NULL. */
807 static void knife_add_cut(KnifeTool_OpData *kcd)
808 {
809         KnifePosData savcur = kcd->curr;
810
811         if (kcd->cut_through) {
812                 knife_cut_through(kcd);
813         }
814         else if (kcd->linehits) {
815                 BMEdgeHit *lh, *lastlh, *firstlh;
816                 int i;
817
818                 knife_sort_linehits(kcd);
819
820                 lh = kcd->linehits;
821                 lastlh = firstlh = NULL;
822                 for (i = 0; i < kcd->totlinehit; i++, (lastlh = lh), lh++) {
823                         BMFace *f = lastlh ? lastlh->f : lh->f;
824
825                         if (lastlh && len_squared_v3v3(lastlh->hit, lh->hit) == 0.0f) {
826                                 if (!firstlh)
827                                         firstlh = lastlh;
828                                 continue;
829                         }
830                         else if (lastlh && firstlh) {
831                                 if (firstlh->v || lastlh->v) {
832                                         KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
833
834                                         kcd->prev.vert = kfv;
835                                         copy_v3_v3(kcd->prev.co, firstlh->hit);
836                                         copy_v3_v3(kcd->prev.cage, firstlh->cagehit);
837                                         kcd->prev.edge = NULL;
838                                         kcd->prev.bmface = f;
839                                         /* TODO: should we set prev.in_space = 0 ? */
840                                 }
841                                 lastlh = firstlh = NULL;
842                         }
843
844                         if (len_squared_v3v3(kcd->prev.cage, lh->realhit) < KNIFE_FLT_EPS_SQUARED)
845                                 continue;
846                         if (len_squared_v3v3(kcd->curr.cage, lh->realhit) < KNIFE_FLT_EPS_SQUARED)
847                                 continue;
848
849                         /* first linehit may be down face parallel to view */
850                         if (!lastlh && fabsf(lh->l) < KNIFE_FLT_EPS)
851                                 continue;
852
853                         if (kcd->prev.is_space) {
854                                 kcd->prev.is_space = 0;
855                                 copy_v3_v3(kcd->prev.co, lh->hit);
856                                 copy_v3_v3(kcd->prev.cage, lh->cagehit);
857                                 kcd->prev.vert = NULL;
858                                 kcd->prev.edge = lh->kfe;
859                                 kcd->prev.bmface = lh->f;
860                                 continue;
861                         }
862
863                         kcd->curr.is_space = 0;
864                         kcd->curr.edge = lh->kfe;
865                         kcd->curr.bmface = lh->f;
866                         kcd->curr.vert = lh->v;
867                         copy_v3_v3(kcd->curr.co, lh->hit);
868                         copy_v3_v3(kcd->curr.cage, lh->cagehit);
869
870                         /* don't draw edges down faces parallel to view */
871                         if (lastlh && fabsf(lastlh->l - lh->l) < KNIFE_FLT_EPS) {
872                                 kcd->prev = kcd->curr;
873                                 continue;
874                         }
875
876                         knife_add_single_cut(kcd);
877                 }
878
879                 if (savcur.is_space) {
880                         kcd->prev = savcur;
881                 }
882                 else {
883                         kcd->curr = savcur;
884                         knife_add_single_cut(kcd);
885                 }
886
887                 MEM_freeN(kcd->linehits);
888                 kcd->linehits = NULL;
889                 kcd->totlinehit = 0;
890         }
891         else {
892                 knife_add_single_cut(kcd);
893         }
894 }
895
896 static void knife_finish_cut(KnifeTool_OpData *UNUSED(kcd))
897 {
898
899 }
900
901 static void knifetool_draw_angle_snapping(const KnifeTool_OpData *kcd)
902 {
903         bglMats mats;
904         double u[3], u1[2], u2[2], v1[3], v2[3], dx, dy;
905         double wminx, wminy, wmaxx, wmaxy;
906
907         /* make u the window coords of prevcage */
908         view3d_get_transformation(kcd->ar, kcd->vc.rv3d, kcd->ob, &mats);
909         gluProject(kcd->prev.cage[0], kcd->prev.cage[1], kcd->prev.cage[2],
910                    mats.modelview, mats.projection, mats.viewport,
911                    &u[0], &u[1], &u[2]);
912
913         /* make u1, u2 the points on window going through u at snap angle */
914         wminx = kcd->ar->winrct.xmin;
915         wmaxx = kcd->ar->winrct.xmin + kcd->ar->winx;
916         wminy = kcd->ar->winrct.ymin;
917         wmaxy = kcd->ar->winrct.ymin + kcd->ar->winy;
918
919         switch (kcd->angle_snapping) {
920                 case ANGLE_0:
921                         u1[0] = wminx;
922                         u2[0] = wmaxx;
923                         u1[1] = u2[1] = u[1];
924                         break;
925                 case ANGLE_90:
926                         u1[0] = u2[0] = u[0];
927                         u1[1] = wminy;
928                         u2[1] = wmaxy;
929                         break;
930                 case ANGLE_45:
931                         /* clip against left or bottom */
932                         dx = u[0] - wminx;
933                         dy = u[1] - wminy;
934                         if (dy > dx) {
935                                 u1[0] = wminx;
936                                 u1[1] = u[1] - dx;
937                         }
938                         else {
939                                 u1[0] = u[0] - dy;
940                                 u1[1] = wminy;
941                         }
942                         /* clip against right or top */
943                         dx = wmaxx - u[0];
944                         dy = wmaxy - u[1];
945                         if (dy > dx) {
946                                 u2[0] = wmaxx;
947                                 u2[1] = u[1] + dx;
948                         }
949                         else {
950                                 u2[0] = u[0] + dy;
951                                 u2[1] = wmaxy;
952                         }
953                         break;
954                 case ANGLE_135:
955                         /* clip against right or bottom */
956                         dx = wmaxx - u[0];
957                         dy = u[1] - wminy;
958                         if (dy > dx) {
959                                 u1[0] = wmaxx;
960                                 u1[1] = u[1] - dx;
961                         }
962                         else {
963                                 u1[0] = u[0] + dy;
964                                 u1[1] = wminy;
965                         }
966                         /* clip against left or top */
967                         dx = u[0] - wminx;
968                         dy = wmaxy - u[1];
969                         if (dy > dx) {
970                                 u2[0] = wminx;
971                                 u2[1] = u[1] + dx;
972                         }
973                         else {
974                                 u2[0] = u[0] - dy;
975                                 u2[1] = wmaxy;
976                         }
977                         break;
978                 default:
979                         return;
980         }
981
982         /* unproject u1 and u2 back into object space */
983         gluUnProject(u1[0], u1[1], 0.0,
984                      mats.modelview, mats.projection, mats.viewport,
985                      &v1[0], &v1[1], &v1[2]);
986         gluUnProject(u2[0], u2[1], 0.0,
987                      mats.modelview, mats.projection, mats.viewport,
988                      &v2[0], &v2[1], &v2[2]);
989
990         UI_ThemeColor(TH_TRANSFORM);
991         glLineWidth(2.0);
992         glBegin(GL_LINES);
993         glVertex3dv(v1);
994         glVertex3dv(v2);
995         glEnd();
996 }
997
998 static void knife_init_colors(KnifeColors *colors)
999 {
1000         /* possible BMESH_TODO: add explicit themes or calculate these by
1001          * figuring out contrasting colors with grid / edges / verts
1002          * a la UI_make_axis_color */
1003         UI_GetThemeColor3ubv(TH_NURB_VLINE, colors->line);
1004         UI_GetThemeColor3ubv(TH_NURB_ULINE, colors->edge);
1005         UI_GetThemeColor3ubv(TH_HANDLE_SEL_VECT, colors->curpoint);
1006         UI_GetThemeColor3ubv(TH_HANDLE_SEL_VECT, colors->curpoint_a);
1007         colors->curpoint_a[3] = 102;
1008         UI_GetThemeColor3ubv(TH_ACTIVE_SPLINE, colors->point);
1009         UI_GetThemeColor3ubv(TH_ACTIVE_SPLINE, colors->point_a);
1010         colors->point_a[3] = 102;
1011 }
1012
1013 /* modal loop selection drawing callback */
1014 static void knifetool_draw(const bContext *C, ARegion *UNUSED(ar), void *arg)
1015 {
1016         View3D *v3d = CTX_wm_view3d(C);
1017         const KnifeTool_OpData *kcd = arg;
1018
1019         if (v3d->zbuf) glDisable(GL_DEPTH_TEST);
1020
1021         glPolygonOffset(1.0f, 1.0f);
1022
1023         glPushMatrix();
1024         glMultMatrixf(kcd->ob->obmat);
1025
1026         if (kcd->mode == MODE_DRAGGING) {
1027                 if (kcd->angle_snapping != ANGLE_FREE)
1028                         knifetool_draw_angle_snapping(kcd);
1029
1030                 glColor3ubv(kcd->colors.line);
1031                 
1032                 glLineWidth(2.0);
1033
1034                 glBegin(GL_LINES);
1035                 glVertex3fv(kcd->prev.cage);
1036                 glVertex3fv(kcd->curr.cage);
1037                 glEnd();
1038
1039                 glLineWidth(1.0);
1040         }
1041
1042         if (kcd->curr.edge) {
1043                 glColor3ubv(kcd->colors.edge);
1044                 glLineWidth(2.0);
1045
1046                 glBegin(GL_LINES);
1047                 glVertex3fv(kcd->curr.edge->v1->cageco);
1048                 glVertex3fv(kcd->curr.edge->v2->cageco);
1049                 glEnd();
1050
1051                 glLineWidth(1.0);
1052         }
1053         else if (kcd->curr.vert) {
1054                 glColor3ubv(kcd->colors.point);
1055                 glPointSize(11);
1056
1057                 glBegin(GL_POINTS);
1058                 glVertex3fv(kcd->curr.cage);
1059                 glEnd();
1060         }
1061
1062         if (kcd->curr.bmface) {
1063                 glColor3ubv(kcd->colors.curpoint);
1064                 glPointSize(9);
1065
1066                 glBegin(GL_POINTS);
1067                 glVertex3fv(kcd->curr.cage);
1068                 glEnd();
1069         }
1070
1071         if (kcd->totlinehit > 0) {
1072                 const float vthresh4 = kcd->vthresh / 4.0f;
1073                 const float vthresh4_sq = vthresh4 * vthresh4;
1074
1075                 BMEdgeHit *lh;
1076                 int i;
1077
1078                 glEnable(GL_BLEND);
1079                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1080
1081                 /* draw any snapped verts first */
1082                 glColor4ubv(kcd->colors.point_a);
1083                 glPointSize(11);
1084                 glBegin(GL_POINTS);
1085                 lh = kcd->linehits;
1086                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
1087                         float sv1[2], sv2[2];
1088
1089                         knife_project_v2(kcd, lh->kfe->v1->cageco, sv1);
1090                         knife_project_v2(kcd, lh->kfe->v2->cageco, sv2);
1091                         knife_project_v2(kcd, lh->cagehit, lh->schit);
1092
1093                         if (len_squared_v2v2(lh->schit, sv1) < vthresh4_sq) {
1094                                 copy_v3_v3(lh->cagehit, lh->kfe->v1->cageco);
1095                                 glVertex3fv(lh->cagehit);
1096                                 lh->v = lh->kfe->v1;
1097                         }
1098                         else if (len_squared_v2v2(lh->schit, sv2) < vthresh4_sq) {
1099                                 copy_v3_v3(lh->cagehit, lh->kfe->v2->cageco);
1100                                 glVertex3fv(lh->cagehit);
1101                                 lh->v = lh->kfe->v2;
1102                         }
1103                 }
1104                 glEnd();
1105
1106                 /* now draw the rest */
1107                 glColor4ubv(kcd->colors.curpoint_a);
1108                 glPointSize(7);
1109                 glBegin(GL_POINTS);
1110                 lh = kcd->linehits;
1111                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
1112                         glVertex3fv(lh->cagehit);
1113                 }
1114                 glEnd();
1115                 glDisable(GL_BLEND);
1116         }
1117
1118         if (kcd->totkedge > 0) {
1119                 BLI_mempool_iter iter;
1120                 KnifeEdge *kfe;
1121
1122                 glLineWidth(1.0);
1123                 glBegin(GL_LINES);
1124
1125                 BLI_mempool_iternew(kcd->kedges, &iter);
1126                 for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
1127                         if (!kfe->draw)
1128                                 continue;
1129
1130                         glColor3ubv(kcd->colors.line);
1131
1132                         glVertex3fv(kfe->v1->cageco);
1133                         glVertex3fv(kfe->v2->cageco);
1134                 }
1135
1136                 glEnd();
1137                 glLineWidth(1.0);
1138         }
1139
1140         if (kcd->totkvert > 0) {
1141                 BLI_mempool_iter iter;
1142                 KnifeVert *kfv;
1143
1144                 glPointSize(5.0);
1145
1146                 glBegin(GL_POINTS);
1147                 BLI_mempool_iternew(kcd->kverts, &iter);
1148                 for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1149                         if (!kfv->draw)
1150                                 continue;
1151
1152                         glColor3ubv(kcd->colors.point);
1153
1154                         glVertex3fv(kfv->cageco);
1155                 }
1156
1157                 glEnd();
1158         }
1159
1160         glPopMatrix();
1161
1162         if (v3d->zbuf) glEnable(GL_DEPTH_TEST);
1163 }
1164
1165 static float len_v3_tri_side_max(const float v1[3], const float v2[3], const float v3[3])
1166 {
1167         const float s1 = len_squared_v3v3(v1, v2);
1168         const float s2 = len_squared_v3v3(v2, v3);
1169         const float s3 = len_squared_v3v3(v3, v1);
1170
1171         return sqrtf(max_fff(s1, s2, s3));
1172 }
1173
1174 static BMEdgeHit *knife_edge_tri_isect(KnifeTool_OpData *kcd, BMBVHTree *bmtree,
1175                                        const float v1[3],  const float v2[3], const float v3[3],
1176                                        SmallHash *ehash, bglMats *mats, int *count)
1177 {
1178         BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON * 4, 8, 8), *tree = BKE_bmbvh_tree_get(bmtree);
1179         BMEdgeHit *edges = NULL;
1180         BLI_array_declare(edges);
1181         BVHTreeOverlap *results, *result;
1182         BMLoop **ls;
1183         float cos[9], lambda;
1184         unsigned int tot = 0;
1185         int i;
1186
1187         /* for comparing distances, error of intersection depends on triangle scale.
1188          * need to scale down before squaring for accurate comparison */
1189         const float depsilon = (FLT_EPSILON / 2.0f) * len_v3_tri_side_max(v1, v2, v3);
1190         const float depsilon_sq = depsilon * depsilon;
1191
1192         copy_v3_v3(cos + 0, v1);
1193         copy_v3_v3(cos + 3, v2);
1194         copy_v3_v3(cos + 6, v3);
1195
1196         BLI_bvhtree_insert(tree2, 0, cos, 3);
1197         BLI_bvhtree_balance(tree2);
1198
1199         result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
1200
1201         for (i = 0; i < tot; i++, result++) {
1202                 BMLoop *l1;
1203                 BMFace *f_hit;
1204                 ListBase *lst;
1205                 Ref *ref;
1206
1207                 ls = (BMLoop **)kcd->em->looptris[result->indexA];
1208
1209                 l1 = ls[0];
1210                 lst = knife_get_face_kedges(kcd, l1->f);
1211
1212                 for (ref = lst->first; ref; ref = ref->next) {
1213                         KnifeEdge *kfe = ref->ref;
1214
1215                         if (BLI_smallhash_haskey(ehash, (uintptr_t)kfe)) {
1216                                 continue;  /* We already found a hit on this knife edge */
1217                         }
1218
1219                         if (isect_line_tri_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3, &lambda, NULL)) {
1220                                 float p[3], no[3], view[3], sp[2];
1221
1222                                 interp_v3_v3v3(p, kfe->v1->cageco, kfe->v2->cageco, lambda);
1223
1224                                 if (kcd->curr.vert && len_squared_v3v3(kcd->curr.vert->cageco, p) < depsilon_sq) {
1225                                         continue;
1226                                 }
1227                                 if (kcd->prev.vert && len_squared_v3v3(kcd->prev.vert->cageco, p) < depsilon_sq) {
1228                                         continue;
1229                                 }
1230                                 if (len_squared_v3v3(kcd->prev.cage, p) < depsilon_sq ||
1231                                     len_squared_v3v3(kcd->curr.cage, p) < depsilon_sq)
1232                                 {
1233                                         continue;
1234                                 }
1235                                 if ((kcd->vc.rv3d->rflag & RV3D_CLIPPING) &&
1236                                     ED_view3d_clipping_test(kcd->vc.rv3d, p, true))
1237                                 {
1238                                         continue;
1239                                 }
1240
1241                                 knife_project_v2(kcd, p, sp);
1242                                 ED_view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
1243                                 mul_m4_v3(kcd->ob->imat, view);
1244
1245                                 if (kcd->cut_through) {
1246                                         f_hit = NULL;
1247                                 }
1248                                 else {
1249                                         /* check if this point is visible in the viewport */
1250                                         float p1[3], lambda1;
1251
1252                                         /* if face isn't planer, p may be behind the current tesselated tri,
1253                                          * so move it onto that and then a little towards eye */
1254                                         if (isect_line_tri_v3(p, view, ls[0]->v->co, ls[1]->v->co, ls[2]->v->co, &lambda1, NULL)) {
1255                                                 interp_v3_v3v3(p1, p, view, lambda1);
1256                                         }
1257                                         else {
1258                                                 copy_v3_v3(p1, p);
1259                                         }
1260                                         sub_v3_v3(view, p1);
1261                                         normalize_v3(view);
1262
1263                                         copy_v3_v3(no, view);
1264                                         mul_v3_fl(no, 0.003);
1265
1266                                         /* go towards view a bit */
1267                                         add_v3_v3(p1, no);
1268                                                 
1269                                         /* ray cast */
1270                                         f_hit = BKE_bmbvh_ray_cast(bmtree, p1, no, NULL, NULL, NULL);
1271                                 }
1272
1273                                 /* ok, if visible add the new point */
1274                                 if (!f_hit && !BLI_smallhash_haskey(ehash, (uintptr_t)kfe)) {
1275                                         BMEdgeHit hit;
1276         
1277                                         if (len_squared_v3v3(p, kcd->curr.co) < depsilon_sq ||
1278                                             len_squared_v3v3(p, kcd->prev.co) < depsilon_sq)
1279                                         {
1280                                                 continue;
1281                                         }
1282
1283                                         hit.kfe = kfe;
1284                                         hit.v = NULL;
1285
1286                                         knife_find_basef(kfe);
1287                                         hit.f = kfe->basef;
1288                                         hit.perc = len_v3v3(p, kfe->v1->cageco) / len_v3v3(kfe->v1->cageco, kfe->v2->cageco);
1289                                         copy_v3_v3(hit.cagehit, p);
1290
1291                                         interp_v3_v3v3(p, kfe->v1->co, kfe->v2->co, hit.perc);
1292                                         copy_v3_v3(hit.realhit, p);
1293
1294                                         /* BMESH_TODO: should also snap to vertices */
1295                                         if (kcd->snap_midpoints) {
1296                                                 float perc = hit.perc;
1297
1298                                                 /* select the closest from the edge endpoints or the midpoint */
1299                                                 if (perc < 0.25f) {
1300                                                         perc = 0.0f;
1301                                                 }
1302                                                 else if (perc < 0.75f) {
1303                                                         perc = 0.5f;
1304                                                 }
1305                                                 else {
1306                                                         perc = 1.0f;
1307                                                 }
1308
1309                                                 interp_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co, perc);
1310                                                 interp_v3_v3v3(hit.cagehit, kfe->v1->cageco, kfe->v2->cageco, perc);
1311                                         }
1312                                         else {
1313                                                 copy_v3_v3(hit.hit, p);
1314                                         }
1315                                         knife_project_v2(kcd, hit.cagehit, hit.schit);
1316
1317                                         BLI_array_append(edges, hit);
1318                                         BLI_smallhash_insert(ehash, (uintptr_t)kfe, NULL);
1319                                 }
1320                         }
1321                 }
1322         }
1323
1324         if (results)
1325                 MEM_freeN(results);
1326
1327         BLI_bvhtree_free(tree2);
1328         *count = BLI_array_count(edges);
1329
1330         return edges;
1331 }
1332
1333 static void knife_bgl_get_mats(KnifeTool_OpData *UNUSED(kcd), bglMats *mats)
1334 {
1335         bgl_get_mats(mats);
1336         //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
1337         //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
1338 }
1339
1340 /* Calculate maximum excursion from (0,0,0) of mesh */
1341 static void calc_ortho_extent(KnifeTool_OpData *kcd)
1342 {
1343         BMIter iter;
1344         BMVert *v;
1345         BMesh *bm = kcd->em->bm;
1346         float max_xyz = 0.0f;
1347         int i;
1348
1349         BM_ITER_MESH(v, &iter, bm, BM_VERTS_OF_MESH) {
1350                 for (i = 0; i < 3; i++)
1351                         max_xyz = max_ff(max_xyz, fabs(v->co[i]));
1352         }
1353         kcd->ortho_extent = max_xyz;
1354 }
1355
1356 /* Clip the line (v1, v2) to planes perpendicular to it and distances d from
1357  * the closest point on the line to the origin */
1358 static void clip_to_ortho_planes(float v1[3], float v2[3], float d)
1359 {
1360         float closest[3];
1361         const float origin[3] = {0.0f, 0.0f, 0.0f};
1362
1363         closest_to_line_v3(closest, origin, v1, v2);
1364         dist_ensure_v3_v3fl(v1, closest, d);
1365         dist_ensure_v3_v3fl(v2, closest, d);
1366 }
1367
1368 /* Finds visible (or all, if cutting through) edges that intersects the current screen drag line */
1369 static void knife_find_line_hits(KnifeTool_OpData *kcd)
1370 {
1371         bglMats mats;
1372         BMEdgeHit *e1, *e2;
1373         SmallHash hash, *ehash = &hash;
1374         float v1[3], v2[3], v3[3], v4[4], s1[2], s2[2];
1375         int i, c1, c2;
1376
1377         knife_bgl_get_mats(kcd, &mats);
1378
1379         if (kcd->linehits) {
1380                 MEM_freeN(kcd->linehits);
1381                 kcd->linehits = NULL;
1382                 kcd->totlinehit = 0;
1383         }
1384
1385         copy_v3_v3(v1, kcd->prev.cage);
1386         copy_v3_v3(v2, kcd->curr.cage);
1387
1388         /* project screen line's 3d coordinates back into 2d */
1389         knife_project_v2(kcd, v1, s1);
1390         knife_project_v2(kcd, v2, s2);
1391
1392         if (len_squared_v2v2(s1, s2) < 1)
1393                 return;
1394
1395         /* unproject screen line */
1396         ED_view3d_win_to_segment(kcd->ar, kcd->vc.v3d, s1, v1, v3, true);
1397         ED_view3d_win_to_segment(kcd->ar, kcd->vc.v3d, s2, v2, v4, true);
1398
1399         mul_m4_v3(kcd->ob->imat, v1);
1400         mul_m4_v3(kcd->ob->imat, v2);
1401         mul_m4_v3(kcd->ob->imat, v3);
1402         mul_m4_v3(kcd->ob->imat, v4);
1403
1404         /* numeric error, 'v1' -> 'v2', 'v2' -> 'v4' can end up being ~2000 units apart in otho mode
1405          * (from ED_view3d_win_to_segment_clip() above)
1406          * this gives precision error in 'knife_edge_tri_isect', rather then solving properly
1407          * (which may involve using doubles everywhere!),
1408          * limit the distance between these points */
1409         if (kcd->is_ortho) {
1410                 if (kcd->ortho_extent == 0.0f)
1411                         calc_ortho_extent(kcd);
1412                 clip_to_ortho_planes(v1, v3, kcd->ortho_extent + 10.0f);
1413                 clip_to_ortho_planes(v2, v4, kcd->ortho_extent + 10.0f);
1414         }
1415
1416         BLI_smallhash_init(ehash);
1417
1418         /* test two triangles of sceen line's plane */
1419         e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
1420         e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v2, v3, v4, ehash, &mats, &c2);
1421         if (c1 && c2) {
1422                 e1 = MEM_reallocN(e1, sizeof(BMEdgeHit) * (c1 + c2));
1423                 memcpy(e1 + c1, e2, sizeof(BMEdgeHit) * c2);
1424                 MEM_freeN(e2);
1425         }
1426         else if (c2) {
1427                 e1 = e2;
1428         }
1429
1430         kcd->linehits = e1;
1431         kcd->totlinehit = c1 + c2;
1432
1433         /* find position along screen line, used for sorting */
1434         for (i = 0; i < kcd->totlinehit; i++) {
1435                 BMEdgeHit *lh = e1 + i;
1436
1437                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
1438         }
1439
1440         BLI_smallhash_release(ehash);
1441 }
1442
1443 /* this works but gives numeric problems [#33400] */
1444 #if 0
1445 static void knife_input_ray_cast(KnifeTool_OpData *kcd, const float mval[2],
1446                                  float r_origin[3], float r_ray[3])
1447 {
1448         bglMats mats;
1449         float imat[3][3];
1450
1451         knife_bgl_get_mats(kcd, &mats);
1452
1453         /* unproject to find view ray */
1454         ED_view3d_unproject(&mats, r_origin, mval[0], mval[1], 0.0f);
1455
1456         if (kcd->is_ortho) {
1457                 negate_v3_v3(r_ray, kcd->vc.rv3d->viewinv[2]);
1458         }
1459         else {
1460                 sub_v3_v3v3(r_ray, r_origin, kcd->vc.rv3d->viewinv[3]);
1461         }
1462         normalize_v3(r_ray);
1463
1464         /* transform into object space */
1465         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1466         copy_m3_m4(imat, kcd->ob->obmat);
1467         invert_m3(imat);
1468
1469         mul_m4_v3(kcd->ob->imat, r_origin);
1470         mul_m3_v3(imat, r_ray);
1471 }
1472 #endif
1473
1474 static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
1475                                     float r_origin[3], float r_origin_ofs[3])
1476 {
1477         bglMats mats;
1478
1479         knife_bgl_get_mats(kcd, &mats);
1480
1481         /* unproject to find view ray */
1482         ED_view3d_unproject(&mats, r_origin,     mval[0], mval[1], 0.0f);
1483         ED_view3d_unproject(&mats, r_origin_ofs, mval[0], mval[1], ofs);
1484
1485         /* transform into object space */
1486         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat); 
1487
1488         mul_m4_v3(kcd->ob->imat, r_origin);
1489         mul_m4_v3(kcd->ob->imat, r_origin_ofs);
1490 }
1491
1492 static BMFace *knife_find_closest_face(KnifeTool_OpData *kcd, float co[3], float cageco[3], bool *is_space)
1493 {
1494         BMFace *f;
1495         float dist = KMAXDIST;
1496         float origin[3];
1497         float origin_ofs[3];
1498         float ray[3];
1499
1500         /* unproject to find view ray */
1501         knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1502         sub_v3_v3v3(ray, origin_ofs, origin);
1503
1504         f = BKE_bmbvh_ray_cast(kcd->bmbvh, origin, ray, NULL, co, cageco);
1505
1506         if (is_space)
1507                 *is_space = !f;
1508
1509         if (!f) {
1510                 if (kcd->is_interactive) {
1511                         /* try to use backbuffer selection method if ray casting failed */
1512                         f = EDBM_face_find_nearest(&kcd->vc, &dist);
1513
1514                         /* cheat for now; just put in the origin instead
1515                          * of a true coordinate on the face.
1516                          * This just puts a point 1.0f infront of the view. */
1517                         add_v3_v3v3(co, origin, ray);
1518                 }
1519         }
1520
1521         return f;
1522 }
1523
1524 /* find the 2d screen space density of vertices within a radius.  used to scale snapping
1525  * distance for picking edges/verts.*/
1526 static int knife_sample_screen_density(KnifeTool_OpData *kcd, const float radius)
1527 {
1528         BMFace *f;
1529         bool is_space;
1530         float co[3], cageco[3], sco[2];
1531
1532         BLI_assert(kcd->is_interactive == true);
1533
1534         f = knife_find_closest_face(kcd, co, cageco, &is_space);
1535
1536         if (f && !is_space) {
1537                 const float radius_sq = radius * radius;
1538                 ListBase *lst;
1539                 Ref *ref;
1540                 float dis_sq;
1541                 int c = 0;
1542
1543                 knife_project_v2(kcd, cageco, sco);
1544
1545                 lst = knife_get_face_kedges(kcd, f);
1546                 for (ref = lst->first; ref; ref = ref->next) {
1547                         KnifeEdge *kfe = ref->ref;
1548                         int i;
1549
1550                         for (i = 0; i < 2; i++) {
1551                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1552
1553                                 knife_project_v2(kcd, kfv->cageco, kfv->sco);
1554
1555                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
1556                                 if (dis_sq < radius_sq) {
1557                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1558                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
1559                                                         c++;
1560                                                 }
1561                                         }
1562                                         else {
1563                                                 c++;
1564                                         }
1565                                 }
1566                         }
1567                 }
1568
1569                 return c;
1570         }
1571
1572         return 0;
1573 }
1574
1575 /* returns snapping distance for edges/verts, scaled by the density of the
1576  * surrounding mesh (in screen space)*/
1577 static float knife_snap_size(KnifeTool_OpData *kcd, float maxsize)
1578 {
1579         float density;
1580
1581         if (kcd->is_interactive) {
1582                 density = (float)knife_sample_screen_density(kcd, maxsize * 2.0f);
1583         }
1584         else {
1585                 density = 1.0f;
1586         }
1587
1588         if (density < 1.0f)
1589                 density = 1.0f;
1590
1591         return min_ff(maxsize / (density * 0.5f), maxsize);
1592 }
1593
1594 /* p is closest point on edge to the mouse cursor */
1595 static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr, bool *is_space)
1596 {
1597         BMFace *f;
1598         float co[3], cageco[3], sco[2];
1599         float maxdist = knife_snap_size(kcd, kcd->ethresh);
1600
1601         if (kcd->ignore_vert_snapping)
1602                 maxdist *= 0.5f;
1603
1604         f = knife_find_closest_face(kcd, co, cageco, NULL);
1605         *is_space = !f;
1606
1607         /* set p to co, in case we don't find anything, means a face cut */
1608         copy_v3_v3(p, co);
1609         copy_v3_v3(cagep, cageco);
1610
1611         kcd->curr.bmface = f;
1612
1613         if (f) {
1614                 const float maxdist_sq = maxdist * maxdist;
1615                 KnifeEdge *cure = NULL;
1616                 ListBase *lst;
1617                 Ref *ref;
1618                 float dis_sq, curdis_sq = FLT_MAX;
1619
1620                 knife_project_v2(kcd, cageco, sco);
1621
1622                 /* look through all edges associated with this face */
1623                 lst = knife_get_face_kedges(kcd, f);
1624                 for (ref = lst->first; ref; ref = ref->next) {
1625                         KnifeEdge *kfe = ref->ref;
1626
1627                         /* project edge vertices into screen space */
1628                         knife_project_v2(kcd, kfe->v1->cageco, kfe->v1->sco);
1629                         knife_project_v2(kcd, kfe->v2->cageco, kfe->v2->sco);
1630
1631                         dis_sq = dist_squared_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1632                         if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1633                                 if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1634                                         float lambda = line_point_factor_v2(sco, kfe->v1->sco, kfe->v2->sco);
1635                                         float vec[3];
1636
1637                                         interp_v3_v3v3(vec, kfe->v1->cageco, kfe->v2->cageco, lambda);
1638
1639                                         if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, true) == 0) {
1640                                                 cure = kfe;
1641                                                 curdis_sq = dis_sq;
1642                                         }
1643                                 }
1644                                 else {
1645                                         cure = kfe;
1646                                         curdis_sq = dis_sq;
1647                                 }
1648                         }
1649                 }
1650
1651                 if (fptr)
1652                         *fptr = f;
1653
1654                 if (cure && p) {
1655                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1656                                 KnifeVert *edgesnap = NULL;
1657
1658                                 if (kcd->snap_midpoints) {
1659                                         mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
1660                                         mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
1661                                 }
1662                                 else {
1663                                         float d;
1664
1665                                         closest_to_line_segment_v3(cagep, cageco, cure->v1->cageco, cure->v2->cageco);
1666                                         d = len_v3v3(cagep, cure->v1->cageco) / len_v3v3(cure->v1->cageco, cure->v2->cageco);
1667                                         interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
1668                                 }
1669
1670                                 /* update mouse coordinates to the snapped-to edge's screen coordinates
1671                                  * this is important for angle snap, which uses the previous mouse position */
1672                                 edgesnap = new_knife_vert(kcd, p, cagep);
1673                                 kcd->curr.mval[0] = edgesnap->sco[0];
1674                                 kcd->curr.mval[1] = edgesnap->sco[1];
1675
1676                         }
1677                         else {
1678                                 return NULL;
1679                         }
1680                 }
1681
1682                 return cure;
1683         }
1684
1685         if (fptr)
1686                 *fptr = NULL;
1687
1688         return NULL;
1689 }
1690
1691 /* find a vertex near the mouse cursor, if it exists */
1692 static KnifeVert *knife_find_closest_vert(KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr,
1693                                           bool *is_space)
1694 {
1695         BMFace *f;
1696         float co[3], cageco[3], sco[2], maxdist = knife_snap_size(kcd, kcd->vthresh);
1697
1698         if (kcd->ignore_vert_snapping)
1699                 maxdist *= 0.5f;
1700
1701         f = knife_find_closest_face(kcd, co, cageco, is_space);
1702
1703         /* set p to co, in case we don't find anything, means a face cut */
1704         copy_v3_v3(p, co);
1705         copy_v3_v3(cagep, p);
1706         kcd->curr.bmface = f;
1707
1708         if (f) {
1709                 const float maxdist_sq = maxdist * maxdist;
1710                 ListBase *lst;
1711                 Ref *ref;
1712                 KnifeVert *curv = NULL;
1713                 float dis_sq, curdis_sq = FLT_MAX;
1714
1715                 knife_project_v2(kcd, cageco, sco);
1716
1717                 lst = knife_get_face_kedges(kcd, f);
1718                 for (ref = lst->first; ref; ref = ref->next) {
1719                         KnifeEdge *kfe = ref->ref;
1720                         int i;
1721
1722                         for (i = 0; i < 2; i++) {
1723                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1724
1725                                 knife_project_v2(kcd, kfv->cageco, kfv->sco);
1726
1727                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
1728                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1729                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1730                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
1731                                                         curv = kfv;
1732                                                         curdis_sq = dis_sq;
1733                                                 }
1734                                         }
1735                                         else {
1736                                                 curv = kfv;
1737                                                 curdis_sq = dis_sq;
1738                                         }
1739                                 }
1740                         }
1741                 }
1742
1743                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
1744                         if (fptr)
1745                                 *fptr = f;
1746
1747                         if (curv && p) {
1748                                 copy_v3_v3(p, curv->co);
1749                                 copy_v3_v3(cagep, curv->cageco);
1750
1751                                 /* update mouse coordinates to the snapped-to vertex's screen coordinates
1752                                  * this is important for angle snap, which uses the previous mouse position */
1753                                 kcd->curr.mval[0] = curv->sco[0];
1754                                 kcd->curr.mval[1] = curv->sco[1];
1755                         }
1756
1757                         return curv;
1758                 }
1759                 else {
1760                         if (fptr)
1761                                 *fptr = f;
1762
1763                         return NULL;
1764                 }
1765         }
1766
1767         if (fptr)
1768                 *fptr = NULL;
1769
1770         return NULL;
1771 }
1772
1773 /* update both kcd->curr.mval and kcd->mval to snap to required angle */
1774 static void knife_snap_angle(KnifeTool_OpData *kcd)
1775 {
1776         float dx, dy;
1777         float w, abs_tan;
1778
1779         dx = kcd->curr.mval[0] - kcd->prev.mval[0];
1780         dy = kcd->curr.mval[1] - kcd->prev.mval[1];
1781         if (dx == 0.0f && dy == 0.0f)
1782                 return;
1783
1784         if (dx == 0.0f) {
1785                 kcd->angle_snapping = ANGLE_90;
1786                 kcd->curr.mval[0] = kcd->prev.mval[0];
1787         }
1788
1789         w = dy / dx;
1790         abs_tan = fabsf(w);
1791         if (abs_tan <= 0.4142f) { /* tan(22.5 degrees) = 0.4142 */
1792                 kcd->angle_snapping = ANGLE_0;
1793                 kcd->curr.mval[1] = kcd->prev.mval[1];
1794         }
1795         else if (abs_tan < 2.4142f) { /* tan(67.5 degrees) = 2.4142 */
1796                 if (w > 0) {
1797                         kcd->angle_snapping = ANGLE_45;
1798                         kcd->curr.mval[1] = kcd->prev.mval[1] + dx;
1799                 }
1800                 else {
1801                         kcd->angle_snapping = ANGLE_135;
1802                         kcd->curr.mval[1] = kcd->prev.mval[1] - dx;
1803                 }
1804         }
1805         else {
1806                 kcd->angle_snapping = ANGLE_90;
1807                 kcd->curr.mval[0] = kcd->prev.mval[0];
1808         }
1809
1810         copy_v2_v2(kcd->mval, kcd->curr.mval);
1811 }
1812
1813 /* update active knife edge/vert pointers */
1814 static int knife_update_active(KnifeTool_OpData *kcd)
1815 {
1816         knife_pos_data_clear(&kcd->curr);
1817         copy_v2_v2(kcd->curr.mval, kcd->mval);
1818         if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING)
1819                 knife_snap_angle(kcd);
1820
1821         /* XXX knife_snap_angle updates the view coordinate mouse values to constrained angles,
1822          * which current mouse values are set to current mouse values are then used
1823          * for vertex and edge snap detection, without regard to the exact angle constraint */
1824         kcd->curr.vert = knife_find_closest_vert(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
1825
1826         if (!kcd->curr.vert) {
1827                 kcd->curr.edge = knife_find_closest_edge(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
1828         }
1829
1830         /* if no hits are found this would normally default to (0, 0, 0) so instead
1831          * get a point at the mouse ray closest to the previous point.
1832          * Note that drawing lines in `free-space` isn't properly supported
1833          * but theres no guarantee (0, 0, 0) has any geometry either - campbell */
1834         if (kcd->curr.vert == NULL && kcd->curr.edge == NULL) {
1835                 float origin[3];
1836                 float origin_ofs[3];
1837
1838                 knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1839
1840                 closest_to_line_v3(kcd->curr.cage, kcd->prev.cage, origin_ofs, origin);
1841         }
1842
1843         if (kcd->mode == MODE_DRAGGING) {
1844                 knife_find_line_hits(kcd);
1845         }
1846         return 1;
1847 }
1848
1849 #define SCANFILL_CUTS 0
1850 #if SCANFILL_CUTS
1851
1852 #define MARK            4
1853 #define DEL             8
1854 #define VERT_ON_EDGE    16
1855 #define VERT_ORIG       32
1856 #define FACE_FLIP       64
1857 #define BOUNDARY        128
1858 #define FACE_NEW        256
1859
1860 typedef struct facenet_entry {
1861         struct facenet_entry *next, *prev;
1862         KnifeEdge *kfe;
1863 } facenet_entry;
1864
1865 static void rnd_offset_co(RNG *rng, float co[3], float scale)
1866 {
1867         int i;
1868
1869         for (i = 0; i < 3; i++) {
1870                 co[i] += (BLI_rng_get_float(rng) - 0.5) * scale;
1871         }
1872 }
1873
1874 static void remerge_faces(KnifeTool_OpData *kcd)
1875 {
1876         BMesh *bm = kcd->em->bm;
1877         SmallHash svisit, *visit = &svisit;
1878         BMIter iter;
1879         BMFace *f;
1880         BMFace **stack = NULL;
1881         BLI_array_declare(stack);
1882         BMFace **faces = NULL;
1883         BLI_array_declare(faces);
1884         BMOperator bmop;
1885         int idx;
1886
1887         BMO_op_initf(bm, &bmop, "beautify_fill faces=%ff edges=%Fe", FACE_NEW, BOUNDARY);
1888
1889         BMO_op_exec(bm, &bmop);
1890         BMO_slot_buffer_flag_enable(bm, &bmop, "geom.out", BM_FACE, FACE_NEW);
1891
1892         BMO_op_finish(bm, &bmop);
1893
1894         BLI_smallhash_init(visit);
1895         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1896                 BMIter eiter;
1897                 BMEdge *e;
1898                 BMFace *f2;
1899
1900                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
1901                         continue;
1902
1903                 if (BLI_smallhash_haskey(visit, (uintptr_t)f))
1904                         continue;
1905
1906                 BLI_array_empty(stack);
1907                 BLI_array_empty(faces);
1908                 BLI_array_append(stack, f);
1909                 BLI_smallhash_insert(visit, (uintptr_t)f, NULL);
1910
1911                 do {
1912                         f2 = BLI_array_pop(stack);
1913
1914                         BLI_array_append(faces, f2);
1915
1916                         BM_ITER_ELEM (e, &eiter, f2, BM_EDGES_OF_FACE) {
1917                                 BMIter fiter;
1918                                 BMFace *f3;
1919
1920                                 if (BMO_elem_flag_test(bm, e, BOUNDARY))
1921                                         continue;
1922
1923                                 BM_ITER_ELEM (f3, &fiter, e, BM_FACES_OF_EDGE) {
1924                                         if (!BMO_elem_flag_test(bm, f3, FACE_NEW))
1925                                                 continue;
1926                                         if (BLI_smallhash_haskey(visit, (uintptr_t)f3))
1927                                                 continue;
1928
1929                                         BLI_smallhash_insert(visit, (uintptr_t)f3, NULL);
1930                                         BLI_array_append(stack, f3);
1931                                 }
1932                         }
1933                 } while (BLI_array_count(stack) > 0);
1934
1935                 if (BLI_array_count(faces) > 0) {
1936                         idx = BM_elem_index_get(faces[0]);
1937
1938                         f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
1939                         if (f2) {
1940                                 BMO_elem_flag_enable(bm, f2, FACE_NEW);
1941                                 BM_elem_index_set(f2, idx); /* set_dirty! *//* BMESH_TODO, check if this is valid or not */
1942                         }
1943                 }
1944         }
1945         /* BMESH_TODO, check if the code above validates the indices */
1946         /* bm->elem_index_dirty &= ~BM_FACE; */
1947         bm->elem_index_dirty |= BM_FACE;
1948
1949         BLI_smallhash_release(visit);
1950
1951         BLI_array_free(stack);
1952         BLI_array_free(faces);
1953 }
1954
1955 /* use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1956 static void knifenet_fill_faces(KnifeTool_OpData *kcd)
1957 {
1958         ScanFillContext sf_ctx;
1959         BMesh *bm = kcd->em->bm;
1960         BMIter bmiter;
1961         BLI_mempool_iter iter;
1962         BMFace *f;
1963         BMEdge *e;
1964         KnifeVert *kfv;
1965         KnifeEdge *kfe;
1966         facenet_entry *entry;
1967         ListBase *face_nets = MEM_callocN(sizeof(ListBase) * bm->totface, "face_nets");
1968         BMFace **faces = MEM_callocN(sizeof(BMFace *) * bm->totface, "faces knife");
1969         MemArena *arena = BLI_memarena_new(1 << 16, "knifenet_fill_faces");
1970         SmallHash shash;
1971         RNG *rng;
1972         int i, j, k = 0, totface = bm->totface;
1973
1974         BMO_push(bm, NULL);
1975         bmesh_edit_begin(bm, BMO_OPTYPE_FLAG_UNTAN_MULTIRES | BMO_OPTYPE_FLAG_NORMALS_CALC | BMO_OPTYPE_FLAG_SELECT_FLUSH);
1976
1977         /* BMESH_TODO this should be valid now, leaving here until we can ensure this - campbell */
1978         i = 0;
1979         BM_ITER_MESH (f, &bmiter, bm, BM_FACES_OF_MESH) {
1980                 BM_elem_index_set(f, i); /* set_inline */
1981                 faces[i] = f;
1982                 i++;
1983         }
1984         bm->elem_index_dirty &= ~BM_FACE;
1985
1986         BM_ITER_MESH (e, &bmiter, bm, BM_EDGES_OF_MESH) {
1987                 BMO_elem_flag_enable(bm, e, BOUNDARY);
1988         }
1989
1990         /* turn knife verts into real verts, as necessary */
1991         BLI_mempool_iternew(kcd->kverts, &iter);
1992         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1993                 if (!kfv->v) {
1994                         /* shouldn't we be at least copying the normal? - if not some comment here should explain why - campbell */
1995                         kfv->v = BM_vert_create(bm, kfv->co, NULL);
1996                         kfv->flag = 1;
1997                         BMO_elem_flag_enable(bm, kfv->v, DEL);
1998                 }
1999                 else {
2000                         kfv->flag = 0;
2001                         BMO_elem_flag_enable(bm, kfv->v, VERT_ORIG);
2002                 }
2003
2004                 BMO_elem_flag_enable(bm, kfv->v, MARK);
2005         }
2006
2007         /* we want to only do changed faces.  first, go over new edges and add to
2008          * face net lists.*/
2009         i = j = k = 0;
2010         BLI_mempool_iternew(kcd->kedges, &iter);
2011         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2012                 Ref *ref;
2013                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
2014                         continue;
2015
2016                 i++;
2017
2018                 if (kfe->e && kfe->v1->v == kfe->e->v1 && kfe->v2->v == kfe->e->v2) {
2019                         kfe->e_old = kfe->e;
2020                         continue;
2021                 }
2022
2023                 j++;
2024
2025                 if (kfe->e) {
2026                         kfe->e_old = kfe->e;
2027
2028                         BMO_elem_flag_enable(bm, kfe->e, DEL);
2029                         BMO_elem_flag_disable(bm, kfe->e, BOUNDARY);
2030                         kfe->e = NULL;
2031                 }
2032
2033                 kfe->e = BM_edge_create(bm, kfe->v1->v, kfe->v2->v, NULL, BM_CREATE_NO_DOUBLE);
2034                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
2035
2036                 for (ref = kfe->faces.first; ref; ref = ref->next) {
2037                         f = ref->ref;
2038
2039                         entry = BLI_memarena_alloc(arena, sizeof(*entry));
2040                         entry->kfe = kfe;
2041                         BLI_addtail(face_nets + BM_elem_index_get(f), entry);
2042                 }
2043         }
2044
2045         /* go over original edges, and add to faces with new geometry */
2046         BLI_mempool_iternew(kcd->kedges, &iter);
2047         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2048                 Ref *ref;
2049
2050                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
2051                         continue;
2052                 if (!(kfe->e_old && kfe->v1->v == kfe->e_old->v1 && kfe->v2->v == kfe->e_old->v2))
2053                         continue;
2054
2055                 k++;
2056
2057                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
2058                 kfe->e_old = kfe->e;
2059
2060                 for (ref = kfe->faces.first; ref; ref = ref->next) {
2061                         f = ref->ref;
2062
2063                         if (face_nets[BM_elem_index_get(f)].first) {
2064                                 entry = BLI_memarena_alloc(arena, sizeof(*entry));
2065                                 entry->kfe = kfe;
2066                                 BLI_addtail(face_nets + BM_elem_index_get(f), entry);
2067                         }
2068                 }
2069         }
2070
2071         rng = BLI_rng_new(0);
2072
2073         for (i = 0; i < totface; i++) {
2074                 SmallHash *hash = &shash;
2075                 ScanFillFace *sf_tri;
2076                 ScanFillVert *sf_vert, *sf_vert_last;
2077                 int j;
2078                 float rndscale = (KNIFE_FLT_EPS / 4.0f);
2079
2080                 f = faces[i];
2081                 BLI_smallhash_init(hash);
2082
2083                 if (face_nets[i].first)
2084                         BMO_elem_flag_enable(bm, f, DEL);
2085
2086                 BLI_scanfill_begin(&sf_ctx);
2087
2088                 for (entry = face_nets[i].first; entry; entry = entry->next) {
2089                         if (!BLI_smallhash_haskey(hash, (uintptr_t)entry->kfe->v1)) {
2090                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, entry->kfe->v1->v->co);
2091                                 sf_vert->poly_nr = 0;
2092                                 rnd_offset_co(rng, sf_vert->co, rndscale);
2093                                 sf_vert->tmp.p = entry->kfe->v1->v;
2094                                 BLI_smallhash_insert(hash, (uintptr_t)entry->kfe->v1, sf_vert);
2095                         }
2096
2097                         if (!BLI_smallhash_haskey(hash, (uintptr_t)entry->kfe->v2)) {
2098                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, entry->kfe->v2->v->co);
2099                                 sf_vert->poly_nr = 0;
2100                                 rnd_offset_co(rng, sf_vert->co, rndscale);
2101                                 sf_vert->tmp.p = entry->kfe->v2->v;
2102                                 BLI_smallhash_insert(hash, (uintptr_t)entry->kfe->v2, sf_vert);
2103                         }
2104                 }
2105
2106                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
2107                         sf_vert_last = BLI_smallhash_lookup(hash, (uintptr_t)entry->kfe->v1);
2108                         sf_vert = BLI_smallhash_lookup(hash, (uintptr_t)entry->kfe->v2);
2109
2110                         sf_vert->poly_nr++;
2111                         sf_vert_last->poly_nr++;
2112                 }
2113
2114                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
2115                         sf_vert_last = BLI_smallhash_lookup(hash, (uintptr_t)entry->kfe->v1);
2116                         sf_vert = BLI_smallhash_lookup(hash, (uintptr_t)entry->kfe->v2);
2117
2118                         if (sf_vert->poly_nr > 1 && sf_vert_last->poly_nr > 1) {
2119                                 ScanFillEdge *sf_edge;
2120                                 sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
2121                                 if (entry->kfe->e_old)
2122                                         sf_edge->f = SF_EDGE_BOUNDARY;  /* mark as original boundary edge */
2123
2124                                 BMO_elem_flag_disable(bm, entry->kfe->e->v1, DEL);
2125                                 BMO_elem_flag_disable(bm, entry->kfe->e->v2, DEL);
2126                         }
2127                         else {
2128                                 if (sf_vert_last->poly_nr < 2)
2129                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert_last);
2130                                 if (sf_vert->poly_nr < 2)
2131                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
2132                         }
2133                 }
2134
2135                 BLI_scanfill_calc(&sf_ctx, 0);
2136
2137                 for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
2138                         BMVert *v1 = sf_tri->v3->tmp.p, *v2 = sf_tri->v2->tmp.p, *v3 = sf_tri->v1->tmp.p;
2139                         BMFace *f2;
2140                         BMLoop *l_iter;
2141                         BMVert *verts[3] = {v1, v2, v3};
2142
2143                         if (v1 == v2 || v2 == v3 || v1 == v3)
2144                                 continue;
2145                         if (BM_face_exists(bm, verts, 3, &f2))
2146                                 continue;
2147
2148                         f2 = BM_face_create_quad_tri(bm,
2149                                                      v1, v2, v3, NULL,
2150                                                      NULL, false);
2151
2152                         BMO_elem_flag_enable(bm, f2, FACE_NEW);
2153
2154                         l_iter = BM_FACE_FIRST_LOOP(f2);
2155                         do {
2156                                 BMO_elem_flag_disable(bm, l_iter->e, DEL);
2157                         } while ((l_iter = l_iter->next) != BM_FACE_FIRST_LOOP(f2));
2158
2159                         BMO_elem_flag_disable(bm, f2, DEL);
2160                         BM_elem_index_set(f2, i); /* set_dirty! *//* note, not 100% sure this is dirty? need to check */
2161
2162                         BM_face_normal_update(f2);
2163                         if (dot_v3v3(f->no, f2->no) < 0.0f) {
2164                                 BM_face_normal_flip(bm, f2);
2165                         }
2166                 }
2167
2168                 BLI_scanfill_end(&sf_ctx);
2169                 BLI_smallhash_release(hash);
2170         }
2171         bm->elem_index_dirty |= BM_FACE;
2172
2173         /* interpolate customdata */
2174         BM_ITER_MESH (f, &bmiter, bm, BM_FACES_OF_MESH) {
2175                 BMLoop *l1;
2176                 BMFace *f2;
2177                 BMIter liter1;
2178
2179                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
2180                         continue;
2181
2182                 f2 = faces[BM_elem_index_get(f)];
2183                 if (BM_elem_index_get(f) < 0 || BM_elem_index_get(f) >= totface) {
2184                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
2185                 }
2186
2187                 BM_elem_attrs_copy(bm, bm, f2, f);
2188
2189                 BM_ITER_ELEM (l1, &liter1, f, BM_LOOPS_OF_FACE) {
2190                         BM_loop_interp_from_face(bm, l1, f2, true, true);
2191                 }
2192         }
2193
2194         /* merge triangles back into faces */
2195         remerge_faces(kcd);
2196
2197         /* delete left over faces */
2198         BMO_op_callf(bm, BMO_FLAG_DEFAULTS, "delete geom=%ff context=%i", DEL, DEL_ONLYFACES);
2199         BMO_op_callf(bm, BMO_FLAG_DEFAULTS, "delete geom=%fe context=%i", DEL, DEL_EDGES);
2200         BMO_op_callf(bm, BMO_FLAG_DEFAULTS, "delete geom=%fv context=%i", DEL, DEL_VERTS);
2201
2202         if (face_nets) 
2203                 MEM_freeN(face_nets);
2204         if (faces)
2205                 MEM_freeN(faces);
2206         BLI_memarena_free(arena);
2207         BLI_rng_free(rng);
2208
2209         BMO_error_clear(bm); /* remerge_faces sometimes raises errors, so make sure to clear them */
2210
2211         bmesh_edit_end(bm, BMO_OPTYPE_FLAG_UNTAN_MULTIRES | BMO_OPTYPE_FLAG_NORMALS_CALC | BMO_OPTYPE_FLAG_SELECT_FLUSH);
2212         BMO_pop(bm);
2213 }
2214
2215 #else  /* use direct (non-scanfill) method for cuts */
2216
2217 /* sort list of kverts by fraction along edge e */
2218 static void sort_by_frac_along(ListBase *lst, BMEdge *e)
2219 {
2220         /* note, since we know the point is along the edge, sort from distance to v1co */
2221         const float *v1co = e->v1->co;
2222 //      const float *v2co = e->v2->co;
2223         Ref *cur = NULL, *prev = NULL, *next = NULL;
2224
2225         if (lst->first == lst->last)
2226                 return;
2227
2228         for (cur = ((Ref *)lst->first)->next; cur; cur = next) {
2229                 KnifeVert *vcur = cur->ref;
2230 #if 0
2231                 const float vcur_fac = line_point_factor_v3(vcur->co, v1co, v2co);
2232 #else
2233                 const float vcur_fac = len_squared_v3v3(v1co, vcur->co);
2234 #endif
2235
2236                 next = cur->next;
2237                 prev = cur->prev;
2238
2239                 BLI_remlink(lst, cur);
2240
2241                 while (prev) {
2242                         KnifeVert *vprev = prev->ref;
2243 #if 0
2244                         if (line_point_factor_v3(vprev->co, v1co, v2co) <= vcur_fac)
2245                                 break;
2246 #else
2247                         if (len_squared_v3v3(v1co, vprev->co) <= vcur_fac)
2248                                 break;
2249 #endif
2250                         prev = prev->prev;
2251                 }
2252
2253                 BLI_insertlinkafter(lst, prev, cur);
2254         }
2255 }
2256
2257 /* The chain so far goes from an instantiated vertex to kfv (some may be reversed).
2258  * If possible, complete the chain to another instantiated vertex and return 1, else return 0.
2259  * The visited hash says which KnifeVert's have already been tried, not including kfv. */
2260 static bool find_chain_search(KnifeTool_OpData *kcd, KnifeVert *kfv, ListBase *fedges, SmallHash *visited,
2261                               ListBase *chain)
2262 {
2263         Ref *r;
2264         KnifeEdge *kfe;
2265         KnifeVert *kfv_other;
2266
2267         if (kfv->v)
2268                 return true;
2269
2270         BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
2271         /* Try all possible next edges. Could either go through fedges
2272          * (all the KnifeEdges for the face being cut) or could go through
2273          * kve->edges and restrict to cutting face and uninstantiated edges.
2274          * Not clear which is better. Let's do the first. */
2275         for (r = fedges->first; r; r = r->next) {
2276                 kfe = r->ref;
2277                 kfv_other = NULL;
2278                 if (kfe->v1 == kfv)
2279                         kfv_other = kfe->v2;
2280                 else if (kfe->v2 == kfv)
2281                         kfv_other = kfe->v1;
2282                 if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
2283                         knife_append_list(kcd, chain, kfe);
2284                         if (find_chain_search(kcd, kfv_other, fedges, visited, chain))
2285                                 return true;
2286                         BLI_remlink(chain, chain->last);
2287                 }
2288         }
2289         return false;
2290 }
2291
2292 static ListBase *find_chain_from_vertex(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMVert *v, ListBase *fedges)
2293 {
2294         SmallHash visited_, *visited = &visited_;
2295         ListBase *ans;
2296         bool found;
2297
2298         ans = knife_empty_list(kcd);
2299         knife_append_list(kcd, ans, kfe);
2300         found = false;
2301         BLI_smallhash_init(visited);
2302         if (kfe->v1->v == v) {
2303                 BLI_smallhash_insert(visited, (uintptr_t)(kfe->v1), NULL);
2304                 found = find_chain_search(kcd, kfe->v2, fedges, visited, ans);
2305         }
2306         else {
2307                 BLI_assert(kfe->v2->v == v);
2308                 BLI_smallhash_insert(visited, (uintptr_t)(kfe->v2), NULL);
2309                 found = find_chain_search(kcd, kfe->v1, fedges, visited, ans);
2310         }
2311
2312         BLI_smallhash_release(visited);
2313
2314         if (found)
2315                 return ans;
2316         else
2317                 return NULL;
2318 }
2319
2320 /* Find a chain in fedges from one instantiated vertex to another.
2321  * Remove the edges in the chain from fedges and return a separate list of the chain. */
2322 static ListBase *find_chain(KnifeTool_OpData *kcd, ListBase *fedges)
2323 {
2324         Ref *r, *ref;
2325         KnifeEdge *kfe;
2326         BMVert *v1, *v2;
2327         ListBase *ans;
2328
2329         ans = NULL;
2330
2331         for (r = fedges->first; r; r = r->next) {
2332                 kfe = r->ref;
2333                 v1 = kfe->v1->v;
2334                 v2 = kfe->v2->v;
2335                 if (v1 && v2) {
2336                         ans = knife_empty_list(kcd);
2337                         knife_append_list(kcd, ans, kfe);
2338                         break;
2339                 }
2340                 if (v1)
2341                         ans = find_chain_from_vertex(kcd, kfe, v1, fedges);
2342                 else if (v2)
2343                         ans = find_chain_from_vertex(kcd, kfe, v2, fedges);
2344                 if (ans)
2345                         break;
2346         }
2347         if (ans) {
2348                 BLI_assert(BLI_countlist(ans) > 0);
2349                 for (r = ans->first; r; r = r->next) {
2350                         ref = find_ref(fedges, r->ref);
2351                         BLI_assert(ref != NULL);
2352                         BLI_remlink(fedges, ref);
2353                 }
2354         }
2355         return ans;
2356 }
2357
2358 /* The hole so far goes from kfvfirst to kfv (some may be reversed).
2359  * If possible, complete the hole back to kfvfirst and return 1, else return 0.
2360  * The visited hash says which KnifeVert's have already been tried, not including kfv or kfvfirst. */
2361 static bool find_hole_search(KnifeTool_OpData *kcd, KnifeVert *kfvfirst, KnifeVert *kfv, ListBase *fedges,
2362                              SmallHash *visited, ListBase *hole)
2363 {
2364         Ref *r;
2365         KnifeEdge *kfe, *kfelast;
2366         KnifeVert *kfv_other;
2367
2368         if (kfv == kfvfirst)
2369                 return true;
2370
2371         BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
2372         kfelast = ((Ref *)hole->last)->ref;
2373         for (r = fedges->first; r; r = r->next) {
2374                 kfe = r->ref;
2375                 if (kfe == kfelast)
2376                         continue;
2377                 if (kfe->v1->v || kfe->v2->v)
2378                         continue;
2379                 kfv_other = NULL;
2380                 if (kfe->v1 == kfv)
2381                         kfv_other = kfe->v2;
2382                 else if (kfe->v2 == kfv)
2383                         kfv_other = kfe->v1;
2384                 if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
2385                         knife_append_list(kcd, hole, kfe);
2386                         if (find_hole_search(kcd, kfvfirst, kfv_other, fedges, visited, hole))
2387                                 return true;
2388                         BLI_remlink(hole, hole->last);
2389                 }
2390         }
2391         return false;
2392 }
2393
2394 /* Find a hole (simple cycle with no instantiated vertices).
2395  * Remove the edges in the cycle from fedges and return a separate list of the cycle */
2396 static ListBase *find_hole(KnifeTool_OpData *kcd, ListBase *fedges)
2397 {
2398         ListBase *ans;
2399         Ref *r, *ref;
2400         KnifeEdge *kfe;
2401         SmallHash visited_, *visited = &visited_;
2402         bool found;
2403
2404         ans = NULL;
2405         found = false;
2406
2407         for (r = fedges->first; r && !found; r = r->next) {
2408                 kfe = r->ref;
2409                 if (kfe->v1->v || kfe->v2->v || kfe->v1 == kfe->v2)
2410                         continue;
2411
2412                 BLI_smallhash_init(visited);
2413                 ans = knife_empty_list(kcd);
2414                 knife_append_list(kcd, ans, kfe);
2415
2416                 found = find_hole_search(kcd, kfe->v1, kfe->v2, fedges, visited, ans);
2417
2418                 BLI_smallhash_release(visited);
2419         }
2420
2421         if (found) {
2422                 for (r = ans->first; r; r = r->next) {
2423                         kfe = r->ref;
2424                         ref = find_ref(fedges, r->ref);
2425                         if (ref)
2426                                 BLI_remlink(fedges, ref);
2427                 }
2428                 return ans;
2429         }
2430         else {
2431                 return NULL;
2432         }
2433 }
2434
2435 /* Try to find "nice" diagonals - short, and far apart from each other.
2436  * If found, return true and make a 'main chain' going across f which uses
2437  * the two diagonals and one part of the hole, and a 'side chain' that
2438  * completes the hole. */
2439 static bool find_hole_chains(KnifeTool_OpData *kcd, ListBase *hole, BMFace *f, ListBase **mainchain,
2440                              ListBase **sidechain)
2441 {
2442         float **fco, **hco;
2443         BMVert **fv;
2444         KnifeVert **hv;
2445         KnifeEdge **he;
2446         Ref *r;
2447         KnifeVert *kfv, *kfvother;
2448         KnifeEdge *kfe;
2449         ListBase *chain;
2450         BMVert *v;
2451         BMIter iter;
2452         int nh, nf, i, j, k, m, ax, ay, sep = 0 /* Quite warnings */, bestsep;
2453         int besti[2], bestj[2];
2454         float d, bestd;
2455
2456         nh = BLI_countlist(hole);
2457         nf = f->len;
2458         if (nh < 2 || nf < 3)
2459                 return false;
2460
2461         /* Gather 2d projections of hole and face vertex coordinates.
2462          * Use best-axis projection - not completely accurate, maybe revisit */
2463         axis_dominant_v3(&ax, &ay, f->no);
2464         hco = BLI_memarena_alloc(kcd->arena, nh * sizeof(float *));
2465         fco = BLI_memarena_alloc(kcd->arena, nf * sizeof(float *));
2466         hv = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeVert *));
2467         fv = BLI_memarena_alloc(kcd->arena, nf * sizeof(BMVert *));
2468         he = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeEdge *));
2469
2470         i = 0;
2471         kfv = NULL;
2472         kfvother = NULL;
2473         for (r = hole->first; r; r = r->next) {
2474                 kfe = r->ref;
2475                 he[i] = kfe;
2476                 if (kfvother == NULL) {
2477                         kfv = kfe->v1;
2478                 }
2479                 else {
2480                         kfv = kfvother;
2481                         BLI_assert(kfv == kfe->v1 || kfv == kfe->v2);
2482                 }
2483                 hco[i] = BLI_memarena_alloc(kcd->arena, 2 * sizeof(float));
2484                 hco[i][0] = kfv->co[ax];
2485                 hco[i][1] = kfv->co[ay];
2486                 hv[i] = kfv;
2487                 kfvother = (kfe->v1 == kfv) ? kfe->v2 : kfe->v1;
2488                 i++;
2489         }
2490
2491         j = 0;
2492         BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
2493                 fco[j] = BLI_memarena_alloc(kcd->arena, 2 * sizeof(float));
2494                 fco[j][0] = v->co[ax];
2495                 fco[j][1] = v->co[ay];
2496                 fv[j] = v;
2497                 j++;
2498         }
2499
2500         /* For first diagonal  (m == 0), want shortest length.
2501          * For second diagonal (m == 1), want max separation of index of hole
2502          * vertex from the hole vertex used in the first diagonal, and from there
2503          * want the one with shortest length not to the same vertex as the first diagonal. */
2504         for (m = 0; m < 2; m++) {
2505                 besti[m] = -1;
2506                 bestj[m] = -1;
2507                 bestd = FLT_MAX;
2508                 bestsep = 0;
2509                 for (i = 0; i < nh; i++) {
2510                         if (m == 1) {
2511                                 if (i == besti[0])
2512                                         continue;
2513                                 sep = (i + nh - besti[0]) % nh;
2514                                 sep = MIN2(sep, nh - sep);
2515                                 if (sep < bestsep)
2516                                         continue;
2517                                 bestd = FLT_MAX;
2518                         }
2519                         for (j = 0; j < nf; j++) {
2520                                 bool ok;
2521
2522                                 if (m == 1 && j == bestj[0])
2523                                         continue;
2524                                 d = len_squared_v2v2(hco[i], fco[j]);
2525                                 if (d > bestd)
2526                                         continue;
2527
2528                                 ok = true;
2529                                 for (k = 0; k < nh && ok; k++) {
2530                                         if (k == i || (k + 1) % nh == i)
2531                                                 continue;
2532                                         if (isect_line_line_v2(hco[i], fco[j], hco[k], hco[(k + 1) % nh]))
2533                                                 ok = false;
2534                                 }
2535                                 if (!ok)
2536                                         continue;
2537                                 for (k = 0; k < nf && ok; k++) {
2538                                         if (k == j || (k + 1) % nf == j)
2539                                                 continue;
2540                                         if (isect_line_line_v2(hco[i], fco[j], fco[k], fco[(k + 1) % nf]))
2541                                                 ok = false;
2542                                 }
2543                                 if (ok) {
2544                                         besti[m] = i;
2545                                         bestj[m] = j;
2546                                         if (m == 1)
2547                                                 bestsep = sep;
2548                                         bestd = d;
2549                                 }
2550                         }
2551                 }
2552         }
2553
2554         if (besti[0] != -1 && besti[1] != -1) {
2555                 BLI_assert(besti[0] != besti[1] && bestj[0] != bestj[1]);
2556                 kfe = new_knife_edge(kcd);
2557                 kfe->v1 = get_bm_knife_vert(kcd, fv[bestj[0]]);
2558                 kfe->v2 = hv[besti[0]];
2559                 chain = knife_empty_list(kcd);
2560                 knife_append_list(kcd, chain, kfe);
2561                 for (i = besti[0]; i != besti[1]; i = (i + 1) % nh) {
2562                         knife_append_list(kcd, chain, he[i]);
2563                 }
2564                 kfe = new_knife_edge(kcd);
2565                 kfe->v1 = hv[besti[1]];
2566                 kfe->v2 = get_bm_knife_vert(kcd, fv[bestj[1]]);
2567                 knife_append_list(kcd, chain, kfe);
2568                 *mainchain = chain;
2569
2570                 chain = knife_empty_list(kcd);
2571                 for (i = besti[1]; i != besti[0]; i = (i + 1) % nh) {
2572                         knife_append_list(kcd, chain, he[i]);
2573                 }
2574                 *sidechain = chain;
2575
2576                 return true;
2577         }
2578         else {
2579                 return false;
2580         }
2581 }
2582
2583 static bool knife_edge_in_face(KnifeTool_OpData *UNUSED(kcd), KnifeEdge *kfe, BMFace *f)
2584 {
2585         /* BMesh *bm = kcd->em->bm; */ /* UNUSED */
2586         BMVert *v1, *v2;
2587         BMLoop *l1, *l2, *l;
2588         float mid[3];
2589         BMIter iter;
2590         int v1inside, v2inside;
2591
2592         if (!f)
2593                 return false;
2594
2595         v1 = kfe->v1->v;
2596         v2 = kfe->v2->v;
2597         l1 = NULL;
2598         l2 = NULL;
2599
2600         /* find out if v1 and v2, if set, are part of the face */
2601         BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
2602                 if (v1 && l->v == v1)
2603                         l1 = l;
2604                 if (v2 && l->v == v2)
2605                         l2 = l;
2606         }
2607
2608         /* BM_face_point_inside_test uses best-axis projection so this isn't most accurate test... */
2609         v1inside = l1 ? 0 : BM_face_point_inside_test(f, kfe->v1->co);
2610         v2inside = l2 ? 0 : BM_face_point_inside_test(f, kfe->v2->co);
2611         if ((l1 && v2inside) || (l2 && v1inside) || (v1inside && v2inside))
2612                 return true;
2613         if (l1 && l2) {
2614                 /* Can have case where v1 and v2 are on shared chain between two faces.
2615                  * BM_face_legal_splits does visibility and self-intersection tests,
2616                  * but it is expensive and maybe a bit buggy, so use a simple
2617                  * "is the midpoint in the face" test */
2618                 mid_v3_v3v3(mid, kfe->v1->co, kfe->v2->co);
2619                 return BM_face_point_inside_test(f, mid);
2620         }
2621         return false;
2622 }
2623
2624 /* Split face f with KnifeEdges on chain.  f remains as one side, the face formed is put in *newface.
2625  * The new face will be on the left side of the chain as viewed from the normal-out side of f. */
2626 static void knife_make_chain_cut(KnifeTool_OpData *kcd, BMFace *f, ListBase *chain, BMFace **r_f_new)
2627 {
2628         BMesh *bm = kcd->em->bm;
2629         KnifeEdge *kfe, *kfelast;
2630         BMVert *v1, *v2;
2631         BMFace *f_new;
2632         Ref *ref;
2633         KnifeVert *kfv, *kfvprev;
2634         BMLoop *l_new, *l_iter;
2635         int i;
2636         int nco = BLI_countlist(chain) - 1;
2637         float (*cos)[3] = BLI_array_alloca(cos, nco);
2638         KnifeVert **kverts = BLI_array_alloca(kverts, nco);
2639
2640         kfe = ((Ref *)chain->first)->ref;
2641         v1 = kfe->v1->v ? kfe->v1->v : kfe->v2->v;
2642         kfelast = ((Ref *)chain->last)->ref;
2643         v2 = kfelast->v2->v ? kfelast->v2->v : kfelast->v1->v;
2644         BLI_assert(v1 != NULL && v2 != NULL);
2645         kfvprev = kfe->v1->v == v1 ? kfe->v1 : kfe->v2;
2646         for (ref = chain->first, i = 0; i < nco && ref != chain->last; ref = ref->next, i++) {
2647                 kfe = ref->ref;
2648                 BLI_assert(kfvprev == kfe->v1 || kfvprev == kfe->v2);
2649                 kfv = kfe->v1 == kfvprev ? kfe->v2 : kfe->v1;
2650                 copy_v3_v3(cos[i], kfv->co);
2651                 kverts[i] = kfv;
2652                 kfvprev = kfv;
2653         }
2654         BLI_assert(i == nco);
2655         l_new = NULL;
2656         if (nco == 0) {
2657                 /* Want to prevent creating two-sided polygons */
2658                 if (BM_edge_exists(v1, v2)) {
2659                         f_new = NULL;
2660                 }
2661                 else {
2662                         f_new = BM_face_split(bm, f, v1, v2, &l_new, NULL, true);
2663                 }
2664         }
2665         else {
2666                 f_new = BM_face_split_n(bm, f, v1, v2, cos, nco, &l_new, NULL);
2667                 if (f_new) {
2668                         /* Now go through lnew chain matching up chain kv's and assign real v's to them */
2669                         for (l_iter = l_new->next, i = 0; i < nco; l_iter = l_iter->next, i++) {
2670                                 BLI_assert(equals_v3v3(cos[i], l_iter->v->co));
2671                                 if (kcd->select_result) {
2672                                         BM_edge_select_set(bm, l_iter->e, true);
2673                                 }
2674                                 kverts[i]->v = l_iter->v;
2675                         }
2676                 }
2677         }
2678
2679         /* the select chain above doesnt account for the first loop */
2680         if (kcd->select_result) {
2681                 if (l_new) {
2682                         BM_edge_select_set(bm, l_new->e, true);
2683                 }
2684         }
2685         else {
2686                 BM_elem_select_copy(bm, bm, f, f_new);
2687         }
2688
2689         *r_f_new = f_new;
2690 }
2691
2692 static void knife_make_face_cuts(KnifeTool_OpData *kcd, BMFace *f, ListBase *kfedges)
2693 {
2694         BMesh *bm = kcd->em->bm;
2695         KnifeEdge *kfe;
2696         BMFace *fnew, *fnew2, *fhole;
2697         ListBase *chain, *hole, *sidechain;
2698         ListBase *fnew_kfedges, *fnew2_kfedges;
2699         Ref *ref, *refnext;
2700         int count, oldcount;
2701
2702         oldcount = BLI_countlist(kfedges);
2703         while ((chain = find_chain(kcd, kfedges)) != NULL) {
2704                 knife_make_chain_cut(kcd, f, chain, &fnew);
2705                 if (!fnew) {
2706                         return;
2707                 }
2708
2709                 /* Move kfedges to fnew_kfedges if they are now in fnew.
2710                  * The chain edges were removed already */
2711                 fnew_kfedges = knife_empty_list(kcd);
2712                 for (ref = kfedges->first; ref; ref = refnext) {
2713                         kfe = ref->ref;
2714                         refnext = ref->next;
2715                         if (knife_edge_in_face(kcd, kfe, fnew)) {
2716                                 BLI_remlink(kfedges, ref);
2717                                 kfe->basef = fnew;
2718                                 knife_append_list(kcd, fnew_kfedges, kfe);
2719                         }
2720                 }
2721                 if (fnew_kfedges->first)
2722                         knife_make_face_cuts(kcd, fnew, fnew_kfedges);
2723
2724                 /* find_chain should always remove edges if it returns true,
2725                  * but guard against infinite loop anyway */
2726                 count = BLI_countlist(kfedges);
2727                 if (count >= oldcount) {
2728                         BLI_assert(!"knife find_chain infinite loop");
2729                         return;
2730                 }
2731                 oldcount = count;
2732         }
2733
2734         while ((hole = find_hole(kcd, kfedges)) != NULL) {
2735                 if (find_hole_chains(kcd, hole, f, &chain, &sidechain)) {
2736                         /* chain goes across f and sidechain comes back
2737                          * from the second last vertex to the second vertex.
2738                          */
2739                         knife_make_chain_cut(kcd, f, chain, &fnew);
2740                         if (!fnew) {
2741                                 BLI_assert(!"knife failed hole cut");
2742                                 return;
2743                         }
2744                         kfe = ((Ref *)sidechain->first)->ref;
2745                         if (knife_edge_in_face(kcd, kfe, f)) {
2746                                 knife_make_chain_cut(kcd, f, sidechain, &fnew2);
2747                                 if (fnew2 == NULL) {
2748                                         return;
2749                                 }
2750                                 fhole = f;
2751                         }
2752                         else if (knife_edge_in_face(kcd, kfe, fnew)) {
2753                                 knife_make_chain_cut(kcd, fnew, sidechain, &fnew2);
2754                                 if (fnew2 == NULL) {
2755                                         return;
2756                                 }
2757                                 fhole = fnew2;
2758                         }
2759                         else {
2760                                 /* shouldn't happen except in funny edge cases */
2761                                 return;
2762                         }
2763                         BM_face_kill(bm, fhole);
2764                         /* Move kfedges to either fnew or fnew2 if appropriate.
2765                          * The hole edges were removed already */
2766                         fnew_kfedges = knife_empty_list(kcd);
2767                         fnew2_kfedges = knife_empty_list(kcd);
2768                         for (ref = kfedges->first; ref; ref = refnext) {
2769                                 kfe = ref->ref;
2770                                 refnext = ref->next;
2771                                 if (knife_edge_in_face(kcd, kfe, fnew)) {
2772                                         BLI_remlink(kfedges, ref);
2773                                         kfe->basef = fnew;
2774                                         knife_append_list(kcd, fnew_kfedges, kfe);
2775                                 }
2776                                 else if (knife_edge_in_face(kcd, kfe, fnew2)) {
2777                                         BLI_remlink(kfedges, ref);
2778                                         kfe->basef = fnew2;
2779                                         knife_append_list(kcd, fnew2_kfedges, kfe);
2780                                 }
2781                         }
2782                         /* We'll skip knife edges that are in the newly formed hole.
2783                          * (Maybe we shouldn't have made a hole in the first place?) */
2784                         if (fnew != fhole && fnew_kfedges->first)
2785                                 knife_make_face_cuts(kcd, fnew, fnew_kfedges);
2786                         if (fnew2 != fhole && fnew2_kfedges->first)
2787                                 knife_make_face_cuts(kcd, fnew2, fnew2_kfedges);
2788                         if (f == fhole)
2789                                 break;
2790                         /* find_hole should always remove edges if it returns true,
2791                          * but guard against infinite loop anyway */
2792                         count = BLI_countlist(kfedges);
2793                         if (count >= oldcount) {
2794                                 BLI_assert(!"knife find_hole infinite loop");
2795                                 return;
2796                         }
2797                         oldcount = count;
2798                 }
2799         }
2800 }
2801
2802 /* Use the network of KnifeEdges and KnifeVerts accumulated to make real BMVerts and BMEdedges */
2803 static void knife_make_cuts(KnifeTool_OpData *kcd)
2804 {
2805         BMesh *bm = kcd->em->bm;
2806         KnifeEdge *kfe;
2807         KnifeVert *kfv;
2808         BMFace *f;
2809         BMEdge *e, *enew;
2810         ListBase *lst;
2811         Ref *ref;
2812         float pct;
2813         SmallHashIter hiter;
2814         BLI_mempool_iter iter;
2815         SmallHash fhash_, *fhash = &fhash_;
2816         SmallHash ehash_, *ehash = &ehash_;
2817
2818         BLI_smallhash_init(fhash);
2819         BLI_smallhash_init(ehash);
2820
2821         /* put list of cutting edges for a face into fhash, keyed by face */
2822         BLI_mempool_iternew(kcd->kedges, &iter);
2823         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2824                 f = kfe->basef;
2825                 if (!f || kfe->e)
2826                         continue;
2827                 lst = BLI_smallhash_lookup(fhash, (uintptr_t)f);
2828                 if (!lst) {
2829                         lst = knife_empty_list(kcd);
2830                         BLI_smallhash_insert(fhash, (uintptr_t)f, lst);
2831                 }
2832                 knife_append_list(kcd, lst, kfe);
2833         }
2834
2835         /* put list of splitting vertices for an edge into ehash, keyed by edge */
2836         BLI_mempool_iternew(kcd->kverts, &iter);
2837         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
2838                 if (kfv->v)
2839                         continue;  /* already have a BMVert */
2840                 for (ref = kfv->edges.first; ref; ref = ref->next) {
2841                         kfe = ref->ref;
2842                         e = kfe->e;
2843                         if (!e)
2844                                 continue;
2845                         lst = BLI_smallhash_lookup(ehash, (uintptr_t)e);
2846                         if (!lst) {
2847                                 lst = knife_empty_list(kcd);
2848                                 BLI_smallhash_insert(ehash, (uintptr_t)e, lst);
2849                         }
2850                         /* there can be more than one kfe in kfv's list with same e */
2851                         if (!find_ref(lst, kfv))
2852                                 knife_append_list(kcd, lst, kfv);
2853                 }
2854         }
2855
2856         /* split bmesh edges where needed */
2857         for (lst = BLI_smallhash_iternew(ehash, &hiter, (uintptr_t *)&e); lst;
2858              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&e))
2859         {
2860                 sort_by_frac_along(lst, e);
2861                 for (ref = lst->first; ref; ref = ref->next) {
2862                         kfv = ref->ref;
2863                         pct = line_point_factor_v3(kfv->co, e->v1->co, e->v2->co);
2864                         kfv->v = BM_edge_split(bm, e, e->v1, &enew, pct);
2865                 }
2866         }
2867
2868         if (kcd->only_select) {
2869                 EDBM_flag_disable_all(kcd->em, BM_ELEM_SELECT);
2870         }
2871
2872         /* do cuts for each face */
2873         for (lst = BLI_smallhash_iternew(fhash, &hiter, (uintptr_t *)&f); lst;
2874              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&f))
2875         {
2876                 knife_make_face_cuts(kcd, f, lst);
2877         }
2878
2879         BLI_smallhash_release(fhash);
2880         BLI_smallhash_release(ehash);
2881 }
2882 #endif
2883
2884 /* called on tool confirmation */
2885 static void knifetool_finish_ex(KnifeTool_OpData *kcd)
2886 {
2887 #if SCANFILL_CUTS
2888         knifenet_fill_faces(kcd);
2889 #else
2890         knife_make_cuts(kcd);
2891 #endif
2892
2893         EDBM_selectmode_flush(kcd->em);
2894         EDBM_mesh_normals_update(kcd->em);
2895         EDBM_update_generic(kcd->em, true, true);
2896 }
2897 static void knifetool_finish(wmOperator *op)
2898 {
2899         KnifeTool_OpData *kcd = op->customdata;
2900         knifetool_finish_ex(kcd);
2901 }
2902
2903 static void knife_recalc_projmat(KnifeTool_OpData *kcd)
2904 {
2905         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
2906         ED_view3d_ob_project_mat_get(kcd->ar->regiondata, kcd->ob, kcd->projmat);
2907         //mul_m4_m4m4(kcd->projmat, kcd->vc.rv3d->winmat, kcd->vc.rv3d->viewmat);
2908
2909         kcd->is_ortho = ED_view3d_clip_range_get(kcd->vc.v3d, kcd->vc.rv3d,
2910                                                  &kcd->clipsta, &kcd->clipend, true);
2911 }
2912
2913 /* called when modal loop selection is done... */
2914 static void knifetool_exit_ex(bContext *C, KnifeTool_OpData *kcd)
2915 {
2916         if (!kcd)
2917                 return;
2918
2919         if (kcd->is_interactive) {
2920                 WM_cursor_restore(CTX_wm_window(C));
2921
2922                 /* deactivate the extra drawing stuff in 3D-View */
2923                 ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
2924         }
2925
2926         /* free the custom data */
2927         BLI_mempool_destroy(kcd->refs);
2928         BLI_mempool_destroy(kcd->kverts);
2929         BLI_mempool_destroy(kcd->kedges);
2930
2931         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
2932         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
2933         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
2934
2935         BKE_bmbvh_free(kcd->bmbvh);
2936         BLI_memarena_free(kcd->arena);
2937
2938         /* tag for redraw */
2939         ED_region_tag_redraw(kcd->ar);
2940
2941         if (kcd->cagecos)
2942                 MEM_freeN((void *)kcd->cagecos);
2943
2944         if (kcd->linehits)
2945                 MEM_freeN(kcd->linehits);
2946
2947         /* destroy kcd itself */
2948         MEM_freeN(kcd);
2949 }
2950 static void knifetool_exit(bContext *C, wmOperator *op)
2951 {
2952         KnifeTool_OpData *kcd = op->customdata;
2953         knifetool_exit_ex(C, kcd);
2954         op->customdata = NULL;
2955 }
2956
2957 static void knifetool_update_mval(KnifeTool_OpData *kcd, const float mval[2])
2958 {
2959         knife_recalc_projmat(kcd);
2960         copy_v2_v2(kcd->mval, mval);
2961
2962         if (knife_update_active(kcd)) {
2963                 ED_region_tag_redraw(kcd->ar);
2964         }
2965 }
2966
2967 static void knifetool_update_mval_i(KnifeTool_OpData *kcd, const int mval_i[2])
2968 {
2969         float mval[2] = {UNPACK2(mval_i)};
2970         knifetool_update_mval(kcd, mval);
2971 }
2972
2973 /* called when modal loop selection gets set up... */
2974 static void knifetool_init(bContext *C, KnifeTool_OpData *kcd,
2975                            const bool only_select, const bool cut_through, const bool is_interactive)
2976 {
2977         Scene *scene = CTX_data_scene(C);
2978         Object *obedit = CTX_data_edit_object(C);
2979
2980         /* assign the drawing handle for drawing preview line... */
2981         kcd->ob = obedit;
2982         kcd->ar = CTX_wm_region(C);
2983
2984         em_setup_viewcontext(C, &kcd->vc);
2985
2986         kcd->em = BKE_editmesh_from_object(kcd->ob);
2987
2988         BM_mesh_elem_index_ensure(kcd->em->bm, BM_VERT);
2989
2990         kcd->cagecos = (const float (*)[3])BKE_editmesh_vertexCos_get(kcd->em, scene, NULL);
2991
2992         kcd->bmbvh = BKE_bmbvh_new(kcd->em,
2993                                   BMBVH_RETURN_ORIG |
2994                                   (only_select ? BMBVH_RESPECT_SELECT : BMBVH_RESPECT_HIDDEN),
2995                                   kcd->cagecos, false);
2996
2997         kcd->arena = BLI_memarena_new(1 << 15, "knife");
2998         kcd->vthresh = KMAXDIST - 1;
2999         kcd->ethresh = KMAXDIST;
3000
3001         kcd->extend = true;
3002
3003         knife_recalc_projmat(kcd);
3004
3005         ED_region_tag_redraw(kcd->ar);
3006
3007         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0);
3008         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
3009         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
3010
3011         kcd->origedgemap = BLI_ghash_ptr_new("knife origedgemap");
3012         kcd->origvertmap = BLI_ghash_ptr_new("knife origvertmap");
3013         kcd->kedgefacemap = BLI_ghash_ptr_new("knife origvertmap");
3014
3015         /* cut all the way through the mesh if use_occlude_geometry button not pushed */
3016         kcd->is_interactive = is_interactive;
3017         kcd->cut_through = cut_through;
3018         kcd->only_select = only_select;
3019
3020         /* can't usefully select resulting edges in face mode */
3021         kcd->select_result = (kcd->em->selectmode != SCE_SELECT_FACE);
3022
3023         knife_pos_data_clear(&kcd->curr);
3024         knife_pos_data_clear(&kcd->prev);
3025
3026         if (is_interactive) {
3027                 kcd->draw_handle = ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
3028
3029                 knife_init_colors(&kcd->colors);
3030         }
3031 }
3032
3033 static int knifetool_cancel(bContext *C, wmOperator *op)
3034 {
3035         /* this is just a wrapper around exit() */
3036         knifetool_exit(C, op);
3037         return OPERATOR_CANCELLED;
3038 }
3039
3040 static int knifetool_invoke(bContext *C, wmOperator *op, const wmEvent *event)
3041 {
3042         const bool only_select = RNA_boolean_get(op->ptr, "only_selected");
3043         const bool cut_through = !RNA_boolean_get(op->ptr, "use_occlude_geometry");
3044
3045         KnifeTool_OpData *kcd;
3046
3047         view3d_operator_needs_opengl(C);
3048
3049         /* alloc new customdata */
3050         kcd = op->customdata = MEM_callocN(sizeof(KnifeTool_OpData), __func__);
3051
3052         knifetool_init(C, kcd, only_select, cut_through, true);
3053