← Back to branch summary

~ubuntu-branches/ubuntu/utopic/blender/utopic-proposed

« back to all changes in this revision

Viewing changes to source/blender/editors/mesh/editmesh_knife.c

  • Committer: Package Import Robot
  • Author(s): Matthias Klose
  • Date: 2014-02-19 11:24:23 UTC
  • mfrom: (14.2.23 sid)
  • Revision ID: package-import@ubuntu.com-20140219112423-rkmaz2m7ha06d4tk
Tags: 2.69-3ubuntu1
* Merge with Debian; remaining changes:
  - Configure without OpenImageIO on armhf, as it is not available on
    Ubuntu.

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/blender/editors/mesh/editmesh_knife.c
38
38
#include "BLI_listbase.h"
39
39
#include "BLI_string.h"
40
40
#include "BLI_array.h"
 
41
#include "BLI_alloca.h"
41
42
#include "BLI_linklist.h"
42
43
#include "BLI_math.h"
43
44
#include "BLI_smallhash.h"
307
308
        BMIter bmiter;
308
309
        BMFace *f;
309
310
 
310
 
        BM_ITER_ELEM(f, &bmiter, e, BM_FACES_OF_EDGE) {
 
311
        BM_ITER_ELEM (f, &bmiter, e, BM_FACES_OF_EDGE) {
311
312
                knife_append_list(kcd, &kfv->faces, f);
312
313
        }
313
314
}
353
354
                kfv = new_knife_vert(kcd, v->co, kcd->cagecos[BM_elem_index_get(v)]);
354
355
                kfv->v = v;
355
356
                BLI_ghash_insert(kcd->origvertmap, v, kfv);
356
 
                BM_ITER_ELEM(f, &bmiter, v, BM_FACES_OF_VERT) {
 
357
                BM_ITER_ELEM (f, &bmiter, v, BM_FACES_OF_VERT) {
357
358
                        knife_append_list(kcd, &kfv->faces, f);
358
359
                }
359
360
        }
378
379
 
379
380
                BLI_ghash_insert(kcd->origedgemap, e, kfe);
380
381
 
381
 
                BM_ITER_ELEM(f, &bmiter, e, BM_FACES_OF_EDGE) {
 
382
                BM_ITER_ELEM (f, &bmiter, e, BM_FACES_OF_EDGE) {
382
383
                        knife_append_list(kcd, &kfe->faces, f);
383
384
                }
384
385
        }
419
420
 
420
421
                lst = knife_empty_list(kcd);
421
422
 
422
 
                BM_ITER_ELEM(e, &bmiter, f, BM_EDGES_OF_FACE) {
 
423
                BM_ITER_ELEM (e, &bmiter, f, BM_EDGES_OF_FACE) {
423
424
                        knife_append_list(kcd, lst, get_bm_knife_edge(kcd, e));
424
425
                }
425
426
 
496
497
 * and move cur data to prev. */
497
498
static void knife_add_single_cut(KnifeTool_OpData *kcd)
498
499
{
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
 
 
 
500
        KnifeEdge *kfe, *kfe2 = NULL, *kfe3 = NULL;
 
501
 
 
502
        if ((kcd->prev.vert && kcd->prev.vert == kcd->curr.vert) ||
 
503
            (kcd->prev.edge && kcd->prev.edge == kcd->curr.edge))
 
504
        {
 
505
                kcd->prev = kcd->curr;
 
506
                return;
 
507
        }
 
508
 
 
509
        kfe = new_knife_edge(kcd);
506
510
        kfe->draw = true;
507
511
 
508
512
        if (kcd->prev.vert) {
572
576
 
573
577
        if      (lh1->l < lh2->l) return -1;
574
578
        else if (lh1->l > lh2->l) return 1;
 
579
        else if (lh1->v && lh2->v) {
 
580
                /* want like verts to sort together; just compare pointers */
 
581
                if      (lh1->v < lh2->v) return -1;
 
582
                else if (lh1->v > lh2->v) return 1;
 
583
                else return 0;
 
584
        }
575
585
        else return 0;
576
586
}
577
587
 
578
588
/* If there's a linehit connected (same face) as testi in range [firsti, lasti], return the first such, else -1.
 
589
 * It also counts as connected if both linehits are snapped to the same vertex.
579
590
 * If testi is out of range, look for connection to f instead, if f is non-NULL */
580
591
static int find_connected_linehit(KnifeTool_OpData *kcd, int testi, BMFace *f, int firsti, int lasti)
581
592
{
582
593
        int i;
 
594
        ListBase *testfaces, *ifaces;
 
595
        BMFace *testface, *iface;
 
596
        BMEdgeHit *lh;
 
597
        bool shareface;
583
598
 
 
599
        if (testi >= 0 && testi < kcd->totlinehit) {
 
600
                testface = NULL;
 
601
                testfaces = NULL;
 
602
                lh = &kcd->linehits[testi];
 
603
                if (lh->v)
 
604
                        testfaces = &lh->v->faces;
 
605
                else if (lh->kfe)
 
606
                        testfaces = &lh->kfe->faces;
 
607
                else if (lh->f) {
 
608
                        testfaces = NULL;
 
609
                        testface = lh->f;
 
610
                }
 
611
        }
 
612
        else {
 
613
                testface = f;
 
614
                testfaces = NULL;
 
615
        }
584
616
        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
 
                }
 
617
                shareface = false;
 
618
                lh = &kcd->linehits[i];
 
619
                iface = NULL;
 
620
                ifaces = NULL;
 
621
                if (lh->v)
 
622
                        ifaces = &lh->v->faces;
 
623
                else if (lh->kfe)
 
624
                        ifaces = &lh->kfe->faces;
 
625
                else if (lh->f) {
 
626
                        ifaces = NULL;
 
627
                        iface = lh->f;
 
628
                }
 
629
                if (testfaces) {
 
630
                        if (ifaces)
 
631
                                shareface = (knife_find_common_face(testfaces, ifaces) != NULL);
 
632
                        else if (iface)
 
633
                                shareface = (find_ref(testfaces, iface) != NULL);
 
634
                }
 
635
                else if (ifaces) {
 
636
                        if (testface)
 
637
                                shareface = (find_ref(ifaces, testface) != NULL);
 
638
                }
 
639
                else if (testface && iface) {
 
640
                        shareface = (testface == iface);
 
641
                }
 
642
                if (shareface)
 
643
                        return i;
596
644
        }
597
645
        return -1;
598
646
}
599
647
 
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)
 
648
/* Sort in order of distance along cut line.
 
649
 * Remove any successive linehits that are snapped to the same vertex.
 
650
 * If joinfaces, treat hits at same distance as follows: try to find
 
651
 * ordering so that preceding and succeeding hits will share a face.
 
652
 */
 
653
static void knife_sort_linehits(KnifeTool_OpData *kcd, bool joinfaces)
602
654
{
603
655
        int i, j, k, nexti, nsame;
604
656
 
605
657
        qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
606
658
 
 
659
        /* Remove duplicated linehits snapped to same vertex */
 
660
        i = j = 0;  /* loop copies from j to i */
 
661
        while (j < kcd->totlinehit) {
 
662
                nsame = 0;
 
663
                if (kcd->linehits[j].v) {
 
664
                        for (k = j + 1; k < kcd->totlinehit; k++) {
 
665
                                if (kcd->linehits[k].v != kcd->linehits[j].v)
 
666
                                        break;
 
667
                                nsame++;
 
668
                        }
 
669
                }
 
670
                if (i != j)
 
671
                        kcd->linehits[i] = kcd->linehits[j];
 
672
                i++;
 
673
                j += 1 + nsame;
 
674
        }
 
675
        kcd->totlinehit = i;
 
676
 
 
677
        if (!joinfaces)
 
678
                return;
 
679
 
607
680
        /* for ranges of equal "l", swap if neccesary to make predecessor and
608
681
         * successor faces connected to the linehits at either end of the range */
609
682
        for (i = 0; i < kcd->totlinehit - 1; i = nexti) {
652
725
                knife_edge_append_face(kcd, kfenew, f);
653
726
}
654
727
 
 
728
#if 0
655
729
static void knife_get_vert_faces(KnifeTool_OpData *kcd, KnifeVert *kfv, BMFace *facef, ListBase *lst)
656
730
{
657
731
        BMIter bmiter;
684
758
                }
685
759
        }
686
760
}
 
761
#endif
 
762
 
 
763
static void copy_hit_from_posdata(BMEdgeHit *lh, KnifePosData *pos, float lambda)
 
764
{
 
765
        lh->kfe = pos->edge;
 
766
        lh->v = pos->vert;
 
767
        lh->f = pos->bmface;
 
768
        copy_v3_v3(lh->hit, pos->co);
 
769
        copy_v3_v3(lh->cagehit, pos->cage);
 
770
        copy_v3_v3(lh->realhit, pos->co);
 
771
        lh->l = lambda;
 
772
        /* perc and schit not used by callers of this function */
 
773
}
687
774
 
688
775
/* BMESH_TODO: add more functionality to cut-through:
689
776
 *    - cutting "in face" (e.g., holes) should cut in all faces, not just visible one
690
777
 *    - perhaps improve O(n^2) algorithm used here */
691
778
static void knife_cut_through(KnifeTool_OpData *kcd)
692
779
{
693
 
        BMEdgeHit *lh, *lh2;
 
780
        BMEdgeHit *lh, *lh2, *linehits;
694
781
        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;
 
782
        KnifeEdge *kfe, *kfe2;
 
783
        KnifeVert *v1, *v2, *lastv;
 
784
        ListBase *faces1, *faces2;
699
785
        KnifeEdge **splitkfe;
700
 
        int i, j;
 
786
        bool needprev, needcurr;
 
787
        int i, j, n;
701
788
 
702
789
        if (!kcd->totlinehit) {
703
790
                /* if no linehits then no interesting back face stuff to do */
705
792
                return;
706
793
        }
707
794
 
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++) {
 
795
        /* sort eliminates hits on same vertices */
 
796
        knife_sort_linehits(kcd, false);
 
797
 
 
798
        /* code is cleaner if make prev and curr into hits (if they are on edges or verts) */
 
799
        n = kcd->totlinehit;
 
800
        needprev = ((kcd->prev.vert && kcd->prev.vert != kcd->linehits[0].v) || kcd->prev.edge);
 
801
        needcurr = ((kcd->curr.vert && kcd->curr.vert != kcd->linehits[n - 1].v) || kcd->curr.edge);
 
802
        n += needprev + needcurr;
 
803
        linehits = MEM_callocN(n * sizeof(BMEdgeHit), "knife_cut_through");
 
804
        i = 0;
 
805
        if (needprev) {
 
806
                copy_hit_from_posdata(&linehits[0], &kcd->prev, 0.0f);
 
807
                i++;
 
808
        }
 
809
        memcpy(linehits + i, kcd->linehits, kcd->totlinehit * sizeof(BMEdgeHit));
 
810
        i += kcd->totlinehit;
 
811
        if (needcurr)
 
812
                copy_hit_from_posdata(&linehits[i], &kcd->curr, 1.0f);
 
813
 
 
814
 
 
815
        splitkfe = MEM_callocN(n * sizeof(KnifeEdge *), "knife_cut_through");
 
816
 
 
817
        lastv = NULL;
 
818
        for (i = 0, lh = linehits; i < n; i++, lh++) {
763
819
                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
 
                                }
 
820
                v1 = NULL;
 
821
 
 
822
                /* get faces incident on hit lh */
 
823
                if (lh->v) {
 
824
                        v1 = lh->v;
 
825
                        faces1 = &v1->faces;
 
826
                }
 
827
                else if (kfe) {
 
828
                        faces1 = &kfe->faces;
 
829
                }
 
830
 
 
831
                /* For each following hit, connect if lh1 an lh2 share a face */
 
832
                for (j = i + 1, lh2 = lh + 1; j < n; j++, lh2++) {
 
833
                        kfe2 = lh2->kfe;
 
834
                        v2 = NULL;
 
835
                        if (lh2->v) {
 
836
                                v2 = lh2->v;
 
837
                                faces2 = &v2->faces;
 
838
                        }
 
839
                        else if (kfe2) {
 
840
                                faces2 = &kfe2->faces;
 
841
                        }
 
842
 
 
843
                        f = knife_find_common_face(faces1, faces2);
 
844
                        if (f) {
 
845
                                if (!v1)
 
846
                                        v1 = splitkfe[i] ? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
 
847
                                if (!v2)
 
848
                                        v2 = splitkfe[j] ? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
 
849
                                knife_add_single_cut_through(kcd, v1, v2, f);
 
850
                                lastv = v2;
790
851
                        }
791
852
                }
792
853
        }
793
854
 
794
855
        MEM_freeN(splitkfe);
 
856
        MEM_freeN(linehits);
795
857
        MEM_freeN(kcd->linehits);
796
858
        kcd->linehits = NULL;
797
859
        kcd->totlinehit = 0;
815
877
                BMEdgeHit *lh, *lastlh, *firstlh;
816
878
                int i;
817
879
 
818
 
                knife_sort_linehits(kcd);
 
880
                knife_sort_linehits(kcd, true);
819
881
 
820
882
                lh = kcd->linehits;
821
883
                lastlh = firstlh = NULL;
847
909
                                continue;
848
910
 
849
911
                        /* first linehit may be down face parallel to view */
850
 
                        if (!lastlh && fabsf(lh->l) < KNIFE_FLT_EPS)
 
912
                        if (!lastlh && !lh->v && fabsf(lh->l) < KNIFE_FLT_EPS)
851
913
                                continue;
852
914
 
853
915
                        if (kcd->prev.is_space) {
854
916
                                kcd->prev.is_space = 0;
855
917
                                copy_v3_v3(kcd->prev.co, lh->hit);
856
918
                                copy_v3_v3(kcd->prev.cage, lh->cagehit);
857
 
                                kcd->prev.vert = NULL;
 
919
                                kcd->prev.vert = lh->v;
858
920
                                kcd->prev.edge = lh->kfe;
859
921
                                kcd->prev.bmface = lh->f;
860
922
                                continue;
1171
1233
        return sqrtf(max_fff(s1, s2, s3));
1172
1234
}
1173
1235
 
 
1236
/**
 
1237
 * given a tri, return 3 planes aligned with the tri's normal.
 
1238
 *
 
1239
 * If the triangle were extruded along its normal,
 
1240
 * the planes calculated would be the 3 sides around the extrusion.
 
1241
 */
 
1242
static void plane_from_tri_clip3_v3(
 
1243
        float tri_plane_clip[3][4],
 
1244
        const float v0[3], const float v1[3], const float v2[3])
 
1245
{
 
1246
        float tri_norm[3];
 
1247
        float tvec[3], cross[3];
 
1248
 
 
1249
        normal_tri_v3(tri_norm, v0, v1, v2);
 
1250
 
 
1251
        sub_v3_v3v3(tvec, v0, v1);
 
1252
        cross_v3_v3v3(cross, tvec, tri_norm);
 
1253
        plane_from_point_normal_v3(tri_plane_clip[0], v0, cross);
 
1254
 
 
1255
        sub_v3_v3v3(tvec, v1, v2);
 
1256
        cross_v3_v3v3(cross, tvec, tri_norm);
 
1257
        plane_from_point_normal_v3(tri_plane_clip[1], v1, cross);
 
1258
 
 
1259
        sub_v3_v3v3(tvec, v2, v0);
 
1260
        cross_v3_v3v3(cross, tvec, tri_norm);
 
1261
        plane_from_point_normal_v3(tri_plane_clip[2], v2, cross);
 
1262
}
 
1263
 
 
1264
/**
 
1265
 * Given a line that is planar with a tri, clip the segment by that tri.
 
1266
 *
 
1267
 * This is needed so we end up with both points in the triangle.
 
1268
 */
 
1269
static bool isect_line_tri_coplanar_v3(
 
1270
        const float p1[3], const float p2[3],
 
1271
        const float v0[3], const float v1[3], const float v2[3],
 
1272
        float r_isects[2][3],
 
1273
 
 
1274
        /* avoid re-calculating every time */
 
1275
        float tri_plane[4], float tri_plane_clip[3][4])
 
1276
{
 
1277
        float p1_tmp[3] = {UNPACK3(p1)};
 
1278
        float p2_tmp[3] = {UNPACK3(p2)};
 
1279
 
 
1280
        (void)v0, (void)v1, (void)v2;
 
1281
 
 
1282
        /* first check if the points are planar with the tri */
 
1283
        if ((fabsf(dist_squared_to_plane_v3(p1, tri_plane)) < KNIFE_FLT_EPS_SQUARED) &&
 
1284
            (fabsf(dist_squared_to_plane_v3(p2, tri_plane)) < KNIFE_FLT_EPS_SQUARED) &&
 
1285
            /* clip the segment by planes around the triangle so we can be sure the points
 
1286
             * aren't outside the triangle */
 
1287
            (clip_segment_v3_plane_n(p1_tmp, p2_tmp, tri_plane_clip, 3)))
 
1288
        {
 
1289
                copy_v3_v3(r_isects[0], p1_tmp);
 
1290
                copy_v3_v3(r_isects[1], p2_tmp);
 
1291
 
 
1292
                return true;
 
1293
        }
 
1294
        else {
 
1295
                return false;
 
1296
        }
 
1297
}
 
1298
 
1174
1299
static BMEdgeHit *knife_edge_tri_isect(KnifeTool_OpData *kcd, BMBVHTree *bmtree,
1175
1300
                                       const float v1[3],  const float v2[3], const float v3[3],
1176
1301
                                       SmallHash *ehash, bglMats *mats, int *count)
1180
1305
        BLI_array_declare(edges);
1181
1306
        BVHTreeOverlap *results, *result;
1182
1307
        BMLoop **ls;
1183
 
        float cos[9], lambda;
 
1308
        float cos[9], tri_norm[3], tri_plane[4], isects[2][3], lambda;
 
1309
        float tri_plane_clip[3][4];
1184
1310
        unsigned int tot = 0;
1185
 
        int i;
 
1311
        int i, j, n_isects;
 
1312
 
1186
1313
 
1187
1314
        /* for comparing distances, error of intersection depends on triangle scale.
1188
1315
         * need to scale down before squaring for accurate comparison */
1193
1320
        copy_v3_v3(cos + 3, v2);
1194
1321
        copy_v3_v3(cos + 6, v3);
1195
1322
 
 
1323
        /* avoid re-calculation in #isect_line_tri_coplanar_v3 */
 
1324
        normal_tri_v3(tri_norm, v1, v2, v3);
 
1325
        plane_from_point_normal_v3(tri_plane, v1, tri_norm);
 
1326
        plane_from_tri_clip3_v3(tri_plane_clip, v1, v2, v3);
 
1327
 
1196
1328
        BLI_bvhtree_insert(tree2, 0, cos, 3);
1197
1329
        BLI_bvhtree_balance(tree2);
1198
1330
 
1216
1348
                                continue;  /* We already found a hit on this knife edge */
1217
1349
                        }
1218
1350
 
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
 
 
 
1351
                        n_isects = 0;
 
1352
 
 
1353
                        if (isect_line_tri_coplanar_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3,
 
1354
                                                       isects,
 
1355
                                                       /* cached values */
 
1356
                                                       tri_plane, tri_plane_clip))
 
1357
                        {
 
1358
                                /* both kfe ends are in cutting triangle */
 
1359
                                n_isects = 2;
 
1360
                        }
 
1361
                        else if (isect_line_tri_epsilon_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3,
 
1362
                                                           &lambda, NULL, depsilon))
 
1363
                        {
 
1364
                                /* kfe intersects cutting triangle lambda of the way along kfe */
 
1365
                                interp_v3_v3v3(isects[0], kfe->v1->cageco, kfe->v2->cageco, lambda);
 
1366
                                n_isects = 1;
 
1367
                        }
 
1368
 
 
1369
                        for (j = 0; j < n_isects; j++) {
 
1370
                                float p[3];
 
1371
 
 
1372
                                copy_v3_v3(p, isects[j]);
1224
1373
                                if (kcd->curr.vert && len_squared_v3v3(kcd->curr.vert->cageco, p) < depsilon_sq) {
1225
1374
                                        continue;
1226
1375
                                }
1238
1387
                                        continue;
1239
1388
                                }
1240
1389
 
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
1390
                                if (kcd->cut_through) {
1246
1391
                                        f_hit = NULL;
1247
1392
                                }
1248
1393
                                else {
1249
1394
                                        /* check if this point is visible in the viewport */
1250
 
                                        float p1[3], lambda1;
 
1395
                                        float p1[3], no[3], view[3], sp[2];
 
1396
                                        float lambda1;
 
1397
 
 
1398
                                        /* screen projection */
 
1399
                                        knife_project_v2(kcd, p, sp);
 
1400
                                        ED_view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
 
1401
                                        mul_m4_v3(kcd->ob->imat, view);
1251
1402
 
1252
1403
                                        /* if face isn't planer, p may be behind the current tesselated tri,
1253
1404
                                         * so move it onto that and then a little towards eye */
1267
1418
                                        add_v3_v3(p1, no);
1268
1419
                                                
1269
1420
                                        /* ray cast */
1270
 
                                        f_hit = BKE_bmbvh_ray_cast(bmtree, p1, no, NULL, NULL, NULL);
 
1421
                                        f_hit = BKE_bmbvh_ray_cast(bmtree, p1, no, KNIFE_FLT_EPS, NULL, NULL, NULL);
1271
1422
                                }
1272
1423
 
1273
1424
                                /* ok, if visible add the new point */
1282
1433
 
1283
1434
                                        hit.kfe = kfe;
1284
1435
                                        hit.v = NULL;
 
1436
                                        hit.l = 0.0f;
1285
1437
 
1286
1438
                                        knife_find_basef(kfe);
1287
1439
                                        hit.f = kfe->basef;
1291
1443
                                        interp_v3_v3v3(p, kfe->v1->co, kfe->v2->co, hit.perc);
1292
1444
                                        copy_v3_v3(hit.realhit, p);
1293
1445
 
1294
 
                                        /* BMESH_TODO: should also snap to vertices */
1295
1446
                                        if (kcd->snap_midpoints) {
1296
1447
                                                float perc = hit.perc;
1297
1448
 
1309
1460
                                                interp_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co, perc);
1310
1461
                                                interp_v3_v3v3(hit.cagehit, kfe->v1->cageco, kfe->v2->cageco, perc);
1311
1462
                                        }
 
1463
                                        else if (hit.perc < KNIFE_FLT_EPS || hit.perc > 1.0f - KNIFE_FLT_EPS) {
 
1464
                                                /* snap to vert */
 
1465
                                                hit.v = (hit.perc < KNIFE_FLT_EPS) ? kfe->v1 : kfe->v2;
 
1466
                                                copy_v3_v3(hit.hit, hit.v->co);
 
1467
                                                copy_v3_v3(hit.cagehit, hit.v->co);
 
1468
                                        }
1312
1469
                                        else {
1313
1470
                                                copy_v3_v3(hit.hit, p);
1314
1471
                                        }
1346
1503
        float max_xyz = 0.0f;
1347
1504
        int i;
1348
1505
 
1349
 
        BM_ITER_MESH(v, &iter, bm, BM_VERTS_OF_MESH) {
 
1506
        BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1350
1507
                for (i = 0; i < 3; i++)
1351
1508
                        max_xyz = max_ff(max_xyz, fabs(v->co[i]));
1352
1509
        }
1389
1546
        knife_project_v2(kcd, v1, s1);
1390
1547
        knife_project_v2(kcd, v2, s2);
1391
1548
 
1392
 
        if (len_squared_v2v2(s1, s2) < 1)
1393
 
                return;
 
1549
        if (kcd->is_interactive) {
 
1550
                if (len_squared_v2v2(s1, s2) < 1.0f) {
 
1551
                        return;
 
1552
                }
 
1553
        }
 
1554
        else {
 
1555
                if (len_squared_v2v2(s1, s2) < KNIFE_FLT_EPS_SQUARED) {
 
1556
                        return;
 
1557
                }
 
1558
        }
1394
1559
 
1395
1560
        /* unproject screen line */
1396
1561
        ED_view3d_win_to_segment(kcd->ar, kcd->vc.v3d, s1, v1, v3, true);
1501
1666
        knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1502
1667
        sub_v3_v3v3(ray, origin_ofs, origin);
1503
1668
 
1504
 
        f = BKE_bmbvh_ray_cast(kcd->bmbvh, origin, ray, NULL, co, cageco);
 
1669
        f = BKE_bmbvh_ray_cast(kcd->bmbvh, origin, ray, 0.0f, NULL, co, cageco);
1505
1670
 
1506
1671
        if (is_space)
1507
1672
                *is_space = !f;
1651
1816
                if (fptr)
1652
1817
                        *fptr = f;
1653
1818
 
1654
 
                if (cure && p) {
 
1819
                if (cure) {
1655
1820
                        if (!kcd->ignore_edge_snapping || !(cure->e)) {
1656
1821
                                KnifeVert *edgesnap = NULL;
1657
1822
 
1744
1909
                        if (fptr)
1745
1910
                                *fptr = f;
1746
1911
 
1747
 
                        if (curv && p) {
 
1912
                        if (curv) {
1748
1913
                                copy_v3_v3(p, curv->co);
1749
1914
                                copy_v3_v3(cagep, curv->cageco);
1750
1915
 
1992
2157
        for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1993
2158
                if (!kfv->v) {
1994
2159
                        /* 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);
 
2160
                        kfv->v = BM_vert_create(bm, kfv->co, NULL, BM_CREATE_NOP);
1996
2161
                        kfv->flag = 1;
1997
2162
                        BMO_elem_flag_enable(bm, kfv->v, DEL);
1998
2163
                }
2623
2788
 
2624
2789
/* Split face f with KnifeEdges on chain.  f remains as one side, the face formed is put in *newface.
2625
2790
 * 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 **newface)
 
2791
static void knife_make_chain_cut(KnifeTool_OpData *kcd, BMFace *f, ListBase *chain, BMFace **r_f_new)
2627
2792
{
2628
2793
        BMesh *bm = kcd->em->bm;
2629
2794
        KnifeEdge *kfe, *kfelast;
2630
2795
        BMVert *v1, *v2;
2631
 
        BMFace *fnew;
 
2796
        BMFace *f_new;
2632
2797
        Ref *ref;
2633
2798
        KnifeVert *kfv, *kfvprev;
2634
 
        BMLoop *lnew, *l_iter;
 
2799
        BMLoop *l_new, *l_iter;
2635
2800
        int i;
2636
2801
        int nco = BLI_countlist(chain) - 1;
2637
2802
        float (*cos)[3] = BLI_array_alloca(cos, nco);
2652
2817
                kfvprev = kfv;
2653
2818
        }
2654
2819
        BLI_assert(i == nco);
2655
 
        lnew = NULL;
 
2820
        l_new = NULL;
2656
2821
        if (nco == 0) {
2657
2822
                /* Want to prevent creating two-sided polygons */
2658
 
                if (BM_edge_exists(v1, v2)) {
2659
 
                        *newface = NULL;
 
2823
                if (v1 == v2 || BM_edge_exists(v1, v2)) {
 
2824
                        f_new = NULL;
2660
2825
                }
2661
2826
                else {
2662
 
                        *newface = BM_face_split(bm, f, v1, v2, &lnew, NULL, true);
 
2827
                        f_new = BM_face_split(bm, f, v1, v2, &l_new, NULL, true);
2663
2828
                }
2664
2829
        }
2665
2830
        else {
2666
 
                fnew = BM_face_split_n(bm, f, v1, v2, cos, nco, &lnew, NULL);
2667
 
                *newface = fnew;
2668
 
 
2669
 
                if (fnew) {
 
2831
                f_new = BM_face_split_n(bm, f, v1, v2, cos, nco, &l_new, NULL);
 
2832
                if (f_new) {
2670
2833
                        /* Now go through lnew chain matching up chain kv's and assign real v's to them */
2671
 
                        for (l_iter = lnew->next, i = 0; i < nco; l_iter = l_iter->next, i++) {
 
2834
                        for (l_iter = l_new->next, i = 0; i < nco; l_iter = l_iter->next, i++) {
2672
2835
                                BLI_assert(equals_v3v3(cos[i], l_iter->v->co));
2673
2836
                                if (kcd->select_result) {
2674
2837
                                        BM_edge_select_set(bm, l_iter->e, true);
2680
2843
 
2681
2844
        /* the select chain above doesnt account for the first loop */
2682
2845
        if (kcd->select_result) {
2683
 
                if (lnew) {
2684
 
                        BM_edge_select_set(bm, lnew->e, true);
 
2846
                if (l_new) {
 
2847
                        BM_edge_select_set(bm, l_new->e, true);
2685
2848
                }
2686
2849
        }
 
2850
        else if (f_new) {
 
2851
                BM_elem_select_copy(bm, bm, f_new, f);
 
2852
        }
 
2853
 
 
2854
        *r_f_new = f_new;
2687
2855
}
2688
2856
 
2689
2857
static void knife_make_face_cuts(KnifeTool_OpData *kcd, BMFace *f, ListBase *kfedges)
2887
3055
        knife_make_cuts(kcd);
2888
3056
#endif
2889
3057
 
 
3058
        EDBM_selectmode_flush(kcd->em);
2890
3059
        EDBM_mesh_normals_update(kcd->em);
2891
3060
        EDBM_update_generic(kcd->em, true, true);
2892
3061
}
2913
3082
                return;
2914
3083
 
2915
3084
        if (kcd->is_interactive) {
2916
 
                WM_cursor_restore(CTX_wm_window(C));
 
3085
                WM_cursor_modal_restore(CTX_wm_window(C));
2917
3086
 
2918
3087
                /* deactivate the extra drawing stuff in 3D-View */
2919
3088
                ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
3048
3217
        knifetool_init(C, kcd, only_select, cut_through, true);
3049
3218
 
3050
3219
        /* add a modal handler for this operator - handles loop selection */
3051
 
        WM_cursor_modal(CTX_wm_window(C), BC_KNIFECURSOR);
 
3220
        WM_cursor_modal_set(CTX_wm_window(C), BC_KNIFECURSOR);
3052
3221
        WM_event_add_modal_handler(C, op);
3053
3222
 
3054
3223
        knifetool_update_mval_i(kcd, event->mval);
3068
3237
        KNF_MODEL_IGNORE_SNAP_OFF,
3069
3238
        KNF_MODAL_ADD_CUT,
3070
3239
        KNF_MODAL_ANGLE_SNAP_TOGGLE,
3071
 
        KNF_MODAL_CUT_THROUGH_TOGGLE
 
3240
        KNF_MODAL_CUT_THROUGH_TOGGLE,
 
3241
        KNF_MODAL_PANNING
3072
3242
};
3073
3243
 
3074
3244
wmKeyMap *knifetool_modal_keymap(wmKeyConfig *keyconf)
3084
3254
                {KNF_MODAL_CUT_THROUGH_TOGGLE, "CUT_THROUGH_TOGGLE", 0, "Toggle Cut Through", ""},
3085
3255
                {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
3086
3256
                {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
 
3257
                {KNF_MODAL_PANNING, "PANNING", 0, "Panning", ""},
3087
3258
                {0, NULL, 0, NULL, NULL}
3088
3259
        };
3089
3260
 
3097
3268
 
3098
3269
        /* items for modal map */
3099
3270
        WM_modalkeymap_add_item(keymap, ESCKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CANCEL);
 
3271
        WM_modalkeymap_add_item(keymap, MIDDLEMOUSE, KM_ANY, KM_ANY, 0, KNF_MODAL_PANNING);
3100
3272
        WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_ADD_CUT);
3101
3273
        WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CANCEL);
3102
3274
        WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
3222
3394
 
3223
3395
                                ED_region_tag_redraw(kcd->ar);
3224
3396
                                break;
 
3397
                        case KNF_MODAL_PANNING:
 
3398
                                if (event->val != KM_RELEASE) {
 
3399
                                        if (kcd->mode != MODE_PANNING) {
 
3400
                                                kcd->prevmode = kcd->mode;
 
3401
                                                kcd->mode = MODE_PANNING;
 
3402
                                        }
 
3403
                                }
 
3404
                                else {
 
3405
                                        kcd->mode = kcd->prevmode;
 
3406
                                }
 
3407
 
 
3408
                                ED_region_tag_redraw(kcd->ar);
 
3409
                                return OPERATOR_PASS_THROUGH;
 
3410
                                break;
3225
3411
                }
3226
3412
        }
3227
3413
        else { /* non-modal-mapped events */
3228
3414
                switch (event->type) {
 
3415
                        case MOUSEPAN:
 
3416
                        case MOUSEZOOM:
 
3417
                        case MOUSEROTATE:
3229
3418
                        case WHEELUPMOUSE:
3230
3419
                        case WHEELDOWNMOUSE:
3231
3420
                                return OPERATOR_PASS_THROUGH;
3232
 
                        case MIDDLEMOUSE:
3233
 
                                if (event->val != KM_RELEASE) {
3234
 
                                        if (kcd->mode != MODE_PANNING)
3235
 
                                                kcd->prevmode = kcd->mode;
3236
 
                                        kcd->mode = MODE_PANNING;
3237
 
                                }
3238
 
                                else {
3239
 
                                        kcd->mode = kcd->prevmode;
3240
 
                                }
3241
 
 
3242
 
                                ED_region_tag_redraw(kcd->ar);
3243
 
                                return OPERATOR_PASS_THROUGH;
3244
 
 
3245
3421
                        case MOUSEMOVE: /* mouse moved somewhere to select another loop */
3246
3422
                                if (kcd->mode != MODE_PANNING) {
3247
3423
                                        knifetool_update_mval_i(kcd, event->mval);
3349
3525
                while (p) {
3350
3526
                        const float (*mval_fl)[2] = p->link;
3351
3527
                        const int mval_tot = MEM_allocN_len(mval_fl) / sizeof(*mval_fl);
3352
 
                        isect += (int)isect_point_poly_v2(cent_ss, mval_fl, mval_tot - 1);
 
3528
                        isect += (int)isect_point_poly_v2(cent_ss, mval_fl, mval_tot - 1, false);
3353
3529
                        p = p->next;
3354
3530
                }
3355
3531