Renaming: sl > scene_layer
[blender.git] / source / blender / editors / curve / editcurve_select.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) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): John Roper
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/curve/editcurve_select.c
29  *  \ingroup edcurve
30  */
31
32 #include "DNA_object_types.h"
33 #include "DNA_scene_types.h"
34
35 #include "MEM_guardedalloc.h"
36
37 #include "BLI_bitmap.h"
38 #include "BLI_math.h"
39 #include "BLI_rand.h"
40 #include "BLI_heap.h"
41
42 #include "BKE_context.h"
43 #include "BKE_curve.h"
44 #include "BKE_fcurve.h"
45 #include "BKE_report.h"
46
47 #include "WM_api.h"
48 #include "WM_types.h"
49
50 #include "ED_screen.h"
51 #include "ED_types.h"
52 #include "ED_view3d.h"
53 #include "ED_curve.h"
54
55 #include "curve_intern.h"
56
57
58 #include "RNA_access.h"
59 #include "RNA_define.h"
60
61
62 /* returns 1 in case (de)selection was successful */
63 bool select_beztriple(BezTriple *bezt, bool selstatus, short flag, eVisible_Types hidden)
64 {
65         if ((bezt->hide == 0) || (hidden == HIDDEN)) {
66                 if (selstatus == SELECT) { /* selects */
67                         bezt->f1 |= flag;
68                         bezt->f2 |= flag;
69                         bezt->f3 |= flag;
70                         return true;
71                 }
72                 else { /* deselects */
73                         bezt->f1 &= ~flag;
74                         bezt->f2 &= ~flag;
75                         bezt->f3 &= ~flag;
76                         return true;
77                 }
78         }
79
80         return false;
81 }
82
83 /* returns 1 in case (de)selection was successful */
84 bool select_bpoint(BPoint *bp, bool selstatus, short flag, bool hidden)
85 {
86         if ((bp->hide == 0) || (hidden == 1)) {
87                 if (selstatus == SELECT) {
88                         bp->f1 |= flag;
89                         return true;
90                 }
91                 else {
92                         bp->f1 &= ~flag;
93                         return true;
94                 }
95         }
96
97         return false;
98 }
99
100 static bool swap_selection_beztriple(BezTriple *bezt)
101 {
102         if (bezt->f2 & SELECT)
103                 return select_beztriple(bezt, DESELECT, SELECT, VISIBLE);
104         else
105                 return select_beztriple(bezt, SELECT, SELECT, VISIBLE);
106 }
107
108 static bool swap_selection_bpoint(BPoint *bp)
109 {
110         if (bp->f1 & SELECT)
111                 return select_bpoint(bp, DESELECT, SELECT, VISIBLE);
112         else
113                 return select_bpoint(bp, SELECT, SELECT, VISIBLE);
114 }
115
116 bool ED_curve_nurb_select_check(Curve *cu, Nurb *nu)
117 {
118         if (nu->type == CU_BEZIER) {
119                 BezTriple *bezt;
120                 int i;
121
122                 for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
123                         if (BEZT_ISSEL_ANY_HIDDENHANDLES(cu, bezt)) {
124                                 return true;
125                         }
126                 }
127         }
128         else {
129                 BPoint *bp;
130                 int i;
131
132                 for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
133                         if (bp->f1 & SELECT) {
134                                 return true;
135                         }
136                 }
137         }
138         return false;
139 }
140
141 int ED_curve_nurb_select_count(Curve *cu, Nurb *nu)
142 {
143         int sel = 0;
144
145         if (nu->type == CU_BEZIER) {
146                 BezTriple *bezt;
147                 int i;
148
149                 for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
150                         if (BEZT_ISSEL_ANY_HIDDENHANDLES(cu, bezt)) {
151                                 sel++;
152                         }
153                 }
154         }
155         else {
156                 BPoint *bp;
157                 int i;
158
159                 for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
160                         if (bp->f1 & SELECT) {
161                                 sel++;
162                         }
163                 }
164         }
165
166         return sel;
167 }
168
169 void ED_curve_nurb_select_all(Nurb *nu)
170 {
171         int i;
172
173         if (nu->bezt) {
174                 BezTriple *bezt;
175                 for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
176                         if (bezt->hide == 0) {
177                                 BEZT_SEL_ALL(bezt);
178                         }
179                 }
180         }
181         else if (nu->bp) {
182                 BPoint *bp;
183                 for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
184                         if (bp->hide == 0) {
185                                 bp->f1 |= SELECT;
186                         }
187                 }
188         }
189 }
190
191 void ED_curve_select_all(EditNurb *editnurb)
192 {
193         Nurb *nu;
194         for (nu = editnurb->nurbs.first; nu; nu = nu->next) {
195                 ED_curve_nurb_select_all(nu);
196         }
197 }
198
199 void ED_curve_nurb_deselect_all(Nurb *nu)
200 {
201         int i;
202
203         if (nu->bezt) {
204                 BezTriple *bezt;
205                 for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
206                         BEZT_DESEL_ALL(bezt);
207                 }
208         }
209         else if (nu->bp) {
210                 BPoint *bp;
211                 for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
212                         bp->f1 &= ~SELECT;
213                 }
214         }
215 }
216
217 bool ED_curve_select_check(Curve *cu, struct EditNurb *editnurb)
218 {
219         Nurb *nu;
220
221         for (nu = editnurb->nurbs.first; nu; nu = nu->next) {
222                 if (ED_curve_nurb_select_check(cu, nu)) {
223                         return true;
224                 }
225         }
226
227         return false;
228 }
229
230 void ED_curve_deselect_all(EditNurb *editnurb)
231 {
232         Nurb *nu;
233
234         for (nu = editnurb->nurbs.first; nu; nu = nu->next) {
235                 ED_curve_nurb_deselect_all(nu);
236         }
237 }
238
239 void ED_curve_select_swap(EditNurb *editnurb, bool hide_handles)
240 {
241         Nurb *nu;
242         BPoint *bp;
243         BezTriple *bezt;
244         int a;
245
246         for (nu = editnurb->nurbs.first; nu; nu = nu->next) {
247                 if (nu->type == CU_BEZIER) {
248                         bezt = nu->bezt;
249                         a = nu->pntsu;
250                         while (a--) {
251                                 if (bezt->hide == 0) {
252                                         bezt->f2 ^= SELECT; /* always do the center point */
253                                         if (!hide_handles) {
254                                                 bezt->f1 ^= SELECT;
255                                                 bezt->f3 ^= SELECT;
256                                         }
257                                 }
258                                 bezt++;
259                         }
260                 }
261                 else {
262                         bp = nu->bp;
263                         a = nu->pntsu * nu->pntsv;
264                         while (a--) {
265                                 swap_selection_bpoint(bp);
266                                 bp++;
267                         }
268                 }
269         }
270 }
271
272 /**
273  * \param next: -1/1 for prev/next
274  * \param cont: when true select continuously
275  * \param selstatus: inverts behavior
276  */
277 static void select_adjacent_cp(
278         ListBase *editnurb, short next,
279         const bool cont, const bool selstatus)
280 {
281         Nurb *nu;
282         BezTriple *bezt;
283         BPoint *bp;
284         int a;
285         bool lastsel = false;
286
287         if (next == 0) return;
288
289         for (nu = editnurb->first; nu; nu = nu->next) {
290                 lastsel = false;
291                 if (nu->type == CU_BEZIER) {
292                         a = nu->pntsu;
293                         bezt = nu->bezt;
294                         if (next < 0) bezt = &nu->bezt[a - 1];
295                         while (a--) {
296                                 if (a - abs(next) < 0) break;
297                                 if ((lastsel == false) && (bezt->hide == 0) && ((bezt->f2 & SELECT) || (selstatus == DESELECT))) {
298                                         bezt += next;
299                                         if (!(bezt->f2 & SELECT) || (selstatus == DESELECT)) {
300                                                 bool sel = select_beztriple(bezt, selstatus, SELECT, VISIBLE);
301                                                 if (sel && !cont) lastsel = true;
302                                         }
303                                 }
304                                 else {
305                                         bezt += next;
306                                         lastsel = false;
307                                 }
308                                 /* move around in zigzag way so that we go through each */
309                                 bezt -= (next - next / abs(next));
310                         }
311                 }
312                 else {
313                         a = nu->pntsu * nu->pntsv;
314                         bp = nu->bp;
315                         if (next < 0) bp = &nu->bp[a - 1];
316                         while (a--) {
317                                 if (a - abs(next) < 0) break;
318                                 if ((lastsel == false) && (bp->hide == 0) && ((bp->f1 & SELECT) || (selstatus == DESELECT))) {
319                                         bp += next;
320                                         if (!(bp->f1 & SELECT) || (selstatus == DESELECT)) {
321                                                 bool sel = select_bpoint(bp, selstatus, SELECT, VISIBLE);
322                                                 if (sel && !cont) lastsel = true;
323                                         }
324                                 }
325                                 else {
326                                         bp += next;
327                                         lastsel = false;
328                                 }
329                                 /* move around in zigzag way so that we go through each */
330                                 bp -= (next - next / abs(next));
331                         }
332                 }
333         }
334 }
335
336 /**************** select start/end operators **************/
337
338 /* (de)selects first or last of visible part of each Nurb depending on selFirst
339  * selFirst: defines the end of which to select
340  * doswap: defines if selection state of each first/last control point is swapped
341  * selstatus: selection status in case doswap is false
342  */
343 static void selectend_nurb(Object *obedit, eEndPoint_Types selfirst, bool doswap, bool selstatus)
344 {
345         ListBase *editnurb = object_editcurve_get(obedit);
346         Nurb *nu;
347         BPoint *bp;
348         BezTriple *bezt;
349         Curve *cu;
350         int a;
351
352         if (obedit == NULL) return;
353
354         cu = (Curve *)obedit->data;
355         cu->actvert = CU_ACT_NONE;
356
357         for (nu = editnurb->first; nu; nu = nu->next) {
358                 if (nu->type == CU_BEZIER) {
359                         a = nu->pntsu;
360
361                         /* which point? */
362                         if (selfirst == LAST) { /* select last */
363                                 bezt = &nu->bezt[a - 1];
364                         }
365                         else { /* select first */
366                                 bezt = nu->bezt;
367                         }
368
369                         while (a--) {
370                                 bool sel;
371                                 if (doswap) sel = swap_selection_beztriple(bezt);
372                                 else sel = select_beztriple(bezt, selstatus, SELECT, VISIBLE);
373
374                                 if (sel == true) break;
375                         }
376                 }
377                 else {
378                         a = nu->pntsu * nu->pntsv;
379
380                         /* which point? */
381                         if (selfirst == LAST) { /* select last */
382                                 bp = &nu->bp[a - 1];
383                         }
384                         else { /* select first */
385                                 bp = nu->bp;
386                         }
387
388                         while (a--) {
389                                 if (bp->hide == 0) {
390                                         bool sel;
391                                         if (doswap) sel = swap_selection_bpoint(bp);
392                                         else sel = select_bpoint(bp, selstatus, SELECT, VISIBLE);
393
394                                         if (sel == true) break;
395                                 }
396                         }
397                 }
398         }
399 }
400
401 static int de_select_first_exec(bContext *C, wmOperator *UNUSED(op))
402 {
403         Object *obedit = CTX_data_edit_object(C);
404
405         selectend_nurb(obedit, FIRST, true, DESELECT);
406         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
407         BKE_curve_nurb_vert_active_validate(obedit->data);
408
409         return OPERATOR_FINISHED;
410 }
411
412 void CURVE_OT_de_select_first(wmOperatorType *ot)
413 {
414         /* identifiers */
415         ot->name = "(De)select First";
416         ot->idname = "CURVE_OT_de_select_first";
417         ot->description = "(De)select first of visible part of each NURBS";
418
419         /* api cfirstbacks */
420         ot->exec = de_select_first_exec;
421         ot->poll = ED_operator_editcurve;
422
423         /* flags */
424         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
425 }
426
427 static int de_select_last_exec(bContext *C, wmOperator *UNUSED(op))
428 {
429         Object *obedit = CTX_data_edit_object(C);
430
431         selectend_nurb(obedit, LAST, true, DESELECT);
432         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
433         BKE_curve_nurb_vert_active_validate(obedit->data);
434
435         return OPERATOR_FINISHED;
436 }
437
438 void CURVE_OT_de_select_last(wmOperatorType *ot)
439 {
440         /* identifiers */
441         ot->name = "(De)select Last";
442         ot->idname = "CURVE_OT_de_select_last";
443         ot->description = "(De)select last of visible part of each NURBS";
444
445         /* api clastbacks */
446         ot->exec = de_select_last_exec;
447         ot->poll = ED_operator_editcurve;
448
449         /* flags */
450         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
451 }
452
453 static int de_select_all_exec(bContext *C, wmOperator *op)
454 {
455         Object *obedit = CTX_data_edit_object(C);
456         Curve *cu = obedit->data;
457         int action = RNA_enum_get(op->ptr, "action");
458
459         if (action == SEL_TOGGLE) {
460                 action = SEL_SELECT;
461                 if (ED_curve_select_check(cu, cu->editnurb)) {
462                         action = SEL_DESELECT;
463                 }
464         }
465
466         switch (action) {
467                 case SEL_SELECT:
468                         ED_curve_select_all(cu->editnurb);
469                         break;
470                 case SEL_DESELECT:
471                         ED_curve_deselect_all(cu->editnurb);
472                         break;
473                 case SEL_INVERT:
474                         ED_curve_select_swap(cu->editnurb, (cu->drawflag & CU_HIDE_HANDLES) != 0);
475                         break;
476         }
477
478         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
479         BKE_curve_nurb_vert_active_validate(cu);
480
481         return OPERATOR_FINISHED;
482 }
483
484 void CURVE_OT_select_all(wmOperatorType *ot)
485 {
486         /* identifiers */
487         ot->name = "(De)select All";
488         ot->idname = "CURVE_OT_select_all";
489         ot->description = "(De)select all control points";
490
491         /* api callbacks */
492         ot->exec = de_select_all_exec;
493         ot->poll = ED_operator_editsurfcurve;
494
495         /* flags */
496         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
497
498         /* properties */
499         WM_operator_properties_select_all(ot);
500 }
501
502
503
504 /***************** select linked operator ******************/
505
506 static int select_linked_exec(bContext *C, wmOperator *UNUSED(op))
507 {
508         Object *obedit = CTX_data_edit_object(C);
509         Curve *cu = (Curve *)obedit->data;
510         EditNurb *editnurb = cu->editnurb;
511         ListBase *nurbs = &editnurb->nurbs;
512         Nurb *nu;
513
514         for (nu = nurbs->first; nu; nu = nu->next) {
515                 if (ED_curve_nurb_select_check(cu, nu)) {
516                         ED_curve_nurb_select_all(nu);
517                 }
518         }
519
520         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
521
522         return OPERATOR_FINISHED;
523 }
524
525 static int select_linked_invoke(bContext *C, wmOperator *op, const wmEvent *UNUSED(event))
526 {
527         return select_linked_exec(C, op);
528 }
529
530 void CURVE_OT_select_linked(wmOperatorType *ot)
531 {
532         /* identifiers */
533         ot->name = "Select Linked All";
534         ot->idname = "CURVE_OT_select_linked";
535         ot->description = "Select all control points linked to active one";
536
537         /* api callbacks */
538         ot->exec = select_linked_exec;
539         ot->invoke = select_linked_invoke;
540         ot->poll = ED_operator_editsurfcurve;
541
542         /* flags */
543         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
544
545         /* properties */
546 }
547
548
549 /***************** select linked pick operator ******************/
550
551 static int select_linked_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event)
552 {
553         Object *obedit = CTX_data_edit_object(C);
554         ViewContext vc;
555         Nurb *nu;
556         BezTriple *bezt;
557         BPoint *bp;
558         int a;
559         const bool select = !RNA_boolean_get(op->ptr, "deselect");
560
561         view3d_operator_needs_opengl(C);
562         view3d_set_viewcontext(C, &vc);
563
564         if (!ED_curve_pick_vert(&vc, 1, event->mval, &nu, &bezt, &bp, NULL)) {
565                 return OPERATOR_CANCELLED;
566         }
567
568         if (bezt) {
569                 a = nu->pntsu;
570                 bezt = nu->bezt;
571                 while (a--) {
572                         select_beztriple(bezt, select, SELECT, VISIBLE);
573                         bezt++;
574                 }
575         }
576         else if (bp) {
577                 a = nu->pntsu * nu->pntsv;
578                 bp = nu->bp;
579                 while (a--) {
580                         select_bpoint(bp, select, SELECT, VISIBLE);
581                         bp++;
582                 }
583         }
584
585         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
586         if (!select) {
587                 BKE_curve_nurb_vert_active_validate(obedit->data);
588         }
589
590         return OPERATOR_FINISHED;
591 }
592
593 void CURVE_OT_select_linked_pick(wmOperatorType *ot)
594 {
595         /* identifiers */
596         ot->name = "Select Linked";
597         ot->idname = "CURVE_OT_select_linked_pick";
598         ot->description = "Select all control points linked to already selected ones";
599
600         /* api callbacks */
601         ot->invoke = select_linked_pick_invoke;
602         ot->poll = ED_operator_editsurfcurve_region_view3d;
603
604         /* flags */
605         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
606
607         /* properties */
608         RNA_def_boolean(ot->srna, "deselect", 0, "Deselect", "Deselect linked control points rather than selecting them");
609 }
610
611 /***************** select row operator **********************/
612
613 static int select_row_exec(bContext *C, wmOperator *UNUSED(op))
614 {
615         Object *obedit = CTX_data_edit_object(C);
616         Curve *cu = obedit->data;
617         ListBase *editnurb = object_editcurve_get(obedit);
618         static BPoint *last = NULL;
619         static int direction = 0;
620         Nurb *nu = NULL;
621         BPoint *bp = NULL;
622         int u = 0, v = 0, a, b;
623
624         if (!BKE_curve_nurb_vert_active_get(cu, &nu, (void *)&bp))
625                 return OPERATOR_CANCELLED;
626
627         if (last == bp) {
628                 direction = 1 - direction;
629                 BKE_nurbList_flag_set(editnurb, 0);
630         }
631         last = bp;
632
633         u = cu->actvert % nu->pntsu;
634         v = cu->actvert / nu->pntsu;
635         bp = nu->bp;
636         for (a = 0; a < nu->pntsv; a++) {
637                 for (b = 0; b < nu->pntsu; b++, bp++) {
638                         if (direction) {
639                                 if (a == v) select_bpoint(bp, SELECT, SELECT, VISIBLE);
640                         }
641                         else {
642                                 if (b == u) select_bpoint(bp, SELECT, SELECT, VISIBLE);
643                         }
644                 }
645         }
646
647         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
648
649         return OPERATOR_FINISHED;
650 }
651
652 void CURVE_OT_select_row(wmOperatorType *ot)
653 {
654         /* identifiers */
655         ot->name = "Select Control Point Row";
656         ot->idname = "CURVE_OT_select_row";
657         ot->description = "Select a row of control points including active one";
658
659         /* api callbacks */
660         ot->exec = select_row_exec;
661         ot->poll = ED_operator_editsurf;
662
663         /* flags */
664         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
665 }
666
667 /***************** select next operator **********************/
668
669 static int select_next_exec(bContext *C, wmOperator *UNUSED(op))
670 {
671         Object *obedit = CTX_data_edit_object(C);
672         ListBase *editnurb = object_editcurve_get(obedit);
673
674         select_adjacent_cp(editnurb, 1, 0, SELECT);
675         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
676
677         return OPERATOR_FINISHED;
678 }
679
680 void CURVE_OT_select_next(wmOperatorType *ot)
681 {
682         /* identifiers */
683         ot->name = "Select Next";
684         ot->idname = "CURVE_OT_select_next";
685         ot->description = "Select control points following already selected ones along the curves";
686
687         /* api callbacks */
688         ot->exec = select_next_exec;
689         ot->poll = ED_operator_editcurve;
690
691         /* flags */
692         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
693 }
694
695 /***************** select previous operator **********************/
696
697 static int select_previous_exec(bContext *C, wmOperator *UNUSED(op))
698 {
699         Object *obedit = CTX_data_edit_object(C);
700         ListBase *editnurb = object_editcurve_get(obedit);
701
702         select_adjacent_cp(editnurb, -1, 0, SELECT);
703         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
704
705         return OPERATOR_FINISHED;
706 }
707
708 void CURVE_OT_select_previous(wmOperatorType *ot)
709 {
710         /* identifiers */
711         ot->name = "Select Previous";
712         ot->idname = "CURVE_OT_select_previous";
713         ot->description = "Select control points preceding already selected ones along the curves";
714
715         /* api callbacks */
716         ot->exec = select_previous_exec;
717         ot->poll = ED_operator_editcurve;
718
719         /* flags */
720         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
721 }
722
723 /***************** select more operator **********************/
724
725 static int select_more_exec(bContext *C, wmOperator *UNUSED(op))
726 {
727         Object *obedit = CTX_data_edit_object(C);
728         ListBase *editnurb = object_editcurve_get(obedit);
729         Nurb *nu;
730         BPoint *bp, *tempbp;
731         int a;
732         short sel = 0;
733
734         /* note that NURBS surface is a special case because we mimic */
735         /* the behavior of "select more" of mesh tools.       */
736         /* The algorithm is designed to work in planar cases so it    */
737         /* may not be optimal always (example: end of NURBS sphere)   */
738         if (obedit->type == OB_SURF) {
739                 for (nu = editnurb->first; nu; nu = nu->next) {
740                         BLI_bitmap *selbpoints;
741                         a = nu->pntsu * nu->pntsv;
742                         bp = nu->bp;
743                         selbpoints = BLI_BITMAP_NEW(a, "selectlist");
744                         while (a > 0) {
745                                 if ((!BLI_BITMAP_TEST(selbpoints, a)) && (bp->hide == 0) && (bp->f1 & SELECT)) {
746                                         /* upper control point */
747                                         if (a % nu->pntsu != 0) {
748                                                 tempbp = bp - 1;
749                                                 if (!(tempbp->f1 & SELECT)) select_bpoint(tempbp, SELECT, SELECT, VISIBLE);
750                                         }
751
752                                         /* left control point. select only if it is not selected already */
753                                         if (a - nu->pntsu > 0) {
754                                                 sel = 0;
755                                                 tempbp = bp + nu->pntsu;
756                                                 if (!(tempbp->f1 & SELECT)) sel = select_bpoint(tempbp, SELECT, SELECT, VISIBLE);
757                                                 /* make sure selected bpoint is discarded */
758                                                 if (sel == 1) BLI_BITMAP_ENABLE(selbpoints, a - nu->pntsu);
759                                         }
760
761                                         /* right control point */
762                                         if (a + nu->pntsu < nu->pntsu * nu->pntsv) {
763                                                 tempbp = bp - nu->pntsu;
764                                                 if (!(tempbp->f1 & SELECT)) select_bpoint(tempbp, SELECT, SELECT, VISIBLE);
765                                         }
766
767                                         /* lower control point. skip next bp in case selection was made */
768                                         if (a % nu->pntsu != 1) {
769                                                 sel = 0;
770                                                 tempbp = bp + 1;
771                                                 if (!(tempbp->f1 & SELECT)) sel = select_bpoint(tempbp, SELECT, SELECT, VISIBLE);
772                                                 if (sel) {
773                                                         bp++;
774                                                         a--;
775                                                 }
776                                         }
777                                 }
778
779                                 bp++;
780                                 a--;
781                         }
782
783                         MEM_freeN(selbpoints);
784                 }
785         }
786         else {
787                 select_adjacent_cp(editnurb, 1, 0, SELECT);
788                 select_adjacent_cp(editnurb, -1, 0, SELECT);
789         }
790
791         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
792
793         return OPERATOR_FINISHED;
794 }
795
796 void CURVE_OT_select_more(wmOperatorType *ot)
797 {
798         /* identifiers */
799         ot->name = "Select More";
800         ot->idname = "CURVE_OT_select_more";
801         ot->description = "Select control points directly linked to already selected ones";
802
803         /* api callbacks */
804         ot->exec = select_more_exec;
805         ot->poll = ED_operator_editsurfcurve;
806
807         /* flags */
808         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
809 }
810
811 /******************** select less operator *****************/
812
813 /* basic method: deselect if control point doesn't have all neighbors selected */
814 static int select_less_exec(bContext *C, wmOperator *UNUSED(op))
815 {
816         Object *obedit = CTX_data_edit_object(C);
817         ListBase *editnurb = object_editcurve_get(obedit);
818         Nurb *nu;
819         BPoint *bp;
820         BezTriple *bezt;
821         int a;
822         int sel = 0;
823         bool lastsel = false;
824
825         if (obedit->type == OB_SURF) {
826                 for (nu = editnurb->first; nu; nu = nu->next) {
827                         BLI_bitmap *selbpoints;
828                         a = nu->pntsu * nu->pntsv;
829                         bp = nu->bp;
830                         selbpoints = BLI_BITMAP_NEW(a, "selectlist");
831                         while (a--) {
832                                 if ((bp->hide == 0) && (bp->f1 & SELECT)) {
833                                         sel = 0;
834
835                                         /* check if neighbors have been selected */
836                                         /* edges of surface are an exception */
837                                         if ((a + 1) % nu->pntsu == 0) {
838                                                 sel++;
839                                         }
840                                         else {
841                                                 bp--;
842                                                 if (BLI_BITMAP_TEST(selbpoints, a + 1) || ((bp->hide == 0) && (bp->f1 & SELECT))) sel++;
843                                                 bp++;
844                                         }
845
846                                         if ((a + 1) % nu->pntsu == 1) {
847                                                 sel++;
848                                         }
849                                         else {
850                                                 bp++;
851                                                 if ((bp->hide == 0) && (bp->f1 & SELECT)) sel++;
852                                                 bp--;
853                                         }
854
855                                         if (a + 1 > nu->pntsu * nu->pntsv - nu->pntsu) {
856                                                 sel++;
857                                         }
858                                         else {
859                                                 bp -= nu->pntsu;
860                                                 if (BLI_BITMAP_TEST(selbpoints, a + nu->pntsu) || ((bp->hide == 0) && (bp->f1 & SELECT))) sel++;
861                                                 bp += nu->pntsu;
862                                         }
863
864                                         if (a < nu->pntsu) {
865                                                 sel++;
866                                         }
867                                         else {
868                                                 bp += nu->pntsu;
869                                                 if ((bp->hide == 0) && (bp->f1 & SELECT)) sel++;
870                                                 bp -= nu->pntsu;
871                                         }
872
873                                         if (sel != 4) {
874                                                 select_bpoint(bp, DESELECT, SELECT, VISIBLE);
875                                                 BLI_BITMAP_ENABLE(selbpoints, a);
876                                         }
877                                 }
878                                 else {
879                                         lastsel = false;
880                                 }
881
882                                 bp++;
883                         }
884
885                         MEM_freeN(selbpoints);
886                 }
887         }
888         else {
889                 for (nu = editnurb->first; nu; nu = nu->next) {
890                         lastsel = false;
891                         /* check what type of curve/nurb it is */
892                         if (nu->type == CU_BEZIER) {
893                                 a = nu->pntsu;
894                                 bezt = nu->bezt;
895                                 while (a--) {
896                                         if ((bezt->hide == 0) && (bezt->f2 & SELECT)) {
897                                                 sel = (lastsel == 1);
898
899                                                 /* check if neighbors have been selected */
900                                                 /* first and last are exceptions */
901                                                 if (a == nu->pntsu - 1) {
902                                                         sel++;
903                                                 }
904                                                 else {
905                                                         bezt--;
906                                                         if ((bezt->hide == 0) && (bezt->f2 & SELECT)) sel++;
907                                                         bezt++;
908                                                 }
909
910                                                 if (a == 0) {
911                                                         sel++;
912                                                 }
913                                                 else {
914                                                         bezt++;
915                                                         if ((bezt->hide == 0) && (bezt->f2 & SELECT)) sel++;
916                                                         bezt--;
917                                                 }
918
919                                                 if (sel != 2) {
920                                                         select_beztriple(bezt, DESELECT, SELECT, VISIBLE);
921                                                         lastsel = true;
922                                                 }
923                                                 else {
924                                                         lastsel = false;
925                                                 }
926                                         }
927                                         else {
928                                                 lastsel = false;
929                                         }
930
931                                         bezt++;
932                                 }
933                         }
934                         else {
935                                 a = nu->pntsu * nu->pntsv;
936                                 bp = nu->bp;
937                                 while (a--) {
938                                         if ((lastsel == false) && (bp->hide == 0) && (bp->f1 & SELECT)) {
939                                                 sel = 0;
940
941                                                 /* first and last are exceptions */
942                                                 if (a == nu->pntsu * nu->pntsv - 1) {
943                                                         sel++;
944                                                 }
945                                                 else {
946                                                         bp--;
947                                                         if ((bp->hide == 0) && (bp->f1 & SELECT)) sel++;
948                                                         bp++;
949                                                 }
950
951                                                 if (a == 0) {
952                                                         sel++;
953                                                 }
954                                                 else {
955                                                         bp++;
956                                                         if ((bp->hide == 0) && (bp->f1 & SELECT)) sel++;
957                                                         bp--;
958                                                 }
959
960                                                 if (sel != 2) {
961                                                         select_bpoint(bp, DESELECT, SELECT, VISIBLE);
962                                                         lastsel = true;
963                                                 }
964                                                 else {
965                                                         lastsel = false;
966                                                 }
967                                         }
968                                         else {
969                                                 lastsel = false;
970                                         }
971
972                                         bp++;
973                                 }
974                         }
975                 }
976         }
977
978         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
979         BKE_curve_nurb_vert_active_validate(obedit->data);
980
981         return OPERATOR_FINISHED;
982 }
983
984 void CURVE_OT_select_less(wmOperatorType *ot)
985 {
986         /* identifiers */
987         ot->name = "Select Less";
988         ot->idname = "CURVE_OT_select_less";
989         ot->description = "Reduce current selection by deselecting boundary elements";
990
991         /* api callbacks */
992         ot->exec = select_less_exec;
993         ot->poll = ED_operator_editsurfcurve;
994
995         /* flags */
996         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
997 }
998
999 /********************** select random *********************/
1000
1001 static void curve_select_random(ListBase *editnurb, float randfac, int seed, bool select)
1002 {
1003         Nurb *nu;
1004         BezTriple *bezt;
1005         BPoint *bp;
1006         int a;
1007
1008         RNG *rng = BLI_rng_new_srandom(seed);
1009
1010         for (nu = editnurb->first; nu; nu = nu->next) {
1011                 if (nu->type == CU_BEZIER) {
1012                         bezt = nu->bezt;
1013                         a = nu->pntsu;
1014                         while (a--) {
1015                                 if (!bezt->hide) {
1016                                         if (BLI_rng_get_float(rng) < randfac) {
1017                                                 select_beztriple(bezt, select, SELECT, VISIBLE);
1018                                         }
1019                                 }
1020                                 bezt++;
1021                         }
1022                 }
1023                 else {
1024                         bp = nu->bp;
1025                         a = nu->pntsu * nu->pntsv;
1026
1027                         while (a--) {
1028                                 if (!bp->hide) {
1029                                         if (BLI_rng_get_float(rng) < randfac) {
1030                                                 select_bpoint(bp, select, SELECT, VISIBLE);
1031                                         }
1032                                 }
1033                                 bp++;
1034                         }
1035                 }
1036         }
1037
1038         BLI_rng_free(rng);
1039 }
1040
1041 static int curve_select_random_exec(bContext *C, wmOperator *op)
1042 {
1043         Object *obedit = CTX_data_edit_object(C);
1044         ListBase *editnurb = object_editcurve_get(obedit);
1045         const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
1046         const float randfac = RNA_float_get(op->ptr, "percent") / 100.0f;
1047         const int seed = WM_operator_properties_select_random_seed_increment_get(op);
1048
1049         curve_select_random(editnurb, randfac, seed, select);
1050         BKE_curve_nurb_vert_active_validate(obedit->data);
1051
1052         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
1053
1054         return OPERATOR_FINISHED;
1055 }
1056
1057 void CURVE_OT_select_random(wmOperatorType *ot)
1058 {
1059         /* identifiers */
1060         ot->name = "Select Random";
1061         ot->idname = "CURVE_OT_select_random";
1062         ot->description = "Randomly select some control points";
1063
1064         /* api callbacks */
1065         ot->exec = curve_select_random_exec;
1066         ot->poll = ED_operator_editsurfcurve;
1067
1068         /* flags */
1069         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1070
1071         /* properties */
1072         WM_operator_properties_select_random(ot);
1073 }
1074
1075 /********************* every nth number of point *******************/
1076
1077 static void select_nth_bezt(Nurb *nu, BezTriple *bezt, const struct CheckerIntervalParams *params)
1078 {
1079         int a, start;
1080
1081         start = bezt - nu->bezt;
1082         a = nu->pntsu;
1083         bezt = &nu->bezt[a - 1];
1084
1085         while (a--) {
1086                 const int depth = abs(start - a);
1087                 if (WM_operator_properties_checker_interval_test(params, depth)) {
1088                         select_beztriple(bezt, DESELECT, SELECT, HIDDEN);
1089                 }
1090
1091                 bezt--;
1092         }
1093 }
1094
1095 static void select_nth_bp(Nurb *nu, BPoint *bp, const struct CheckerIntervalParams *params)
1096 {
1097         int a, startrow, startpnt;
1098         int row, pnt;
1099
1100         startrow = (bp - nu->bp) / nu->pntsu;
1101         startpnt = (bp - nu->bp) % nu->pntsu;
1102
1103         a = nu->pntsu * nu->pntsv;
1104         bp = &nu->bp[a - 1];
1105         row = nu->pntsv - 1;
1106         pnt = nu->pntsu - 1;
1107
1108         while (a--) {
1109                 const int depth = abs(pnt - startpnt) + abs(row - startrow);
1110                 if (WM_operator_properties_checker_interval_test(params, depth)) {
1111                         select_bpoint(bp, DESELECT, SELECT, HIDDEN);
1112                 }
1113
1114                 pnt--;
1115                 if (pnt < 0) {
1116                         pnt = nu->pntsu - 1;
1117                         row--;
1118                 }
1119
1120                 bp--;
1121         }
1122 }
1123
1124 static bool ed_curve_select_nth(Curve *cu, const struct CheckerIntervalParams *params)
1125 {
1126         Nurb *nu = NULL;
1127         void *vert = NULL;
1128
1129         if (!BKE_curve_nurb_vert_active_get(cu, &nu, &vert))
1130                 return false;
1131
1132         if (nu->bezt) {
1133                 select_nth_bezt(nu, vert, params);
1134         }
1135         else {
1136                 select_nth_bp(nu, vert, params);
1137         }
1138
1139         return true;
1140 }
1141
1142 static int select_nth_exec(bContext *C, wmOperator *op)
1143 {
1144         Object *obedit = CTX_data_edit_object(C);
1145         struct CheckerIntervalParams op_params;
1146
1147         WM_operator_properties_checker_interval_from_op(op, &op_params);
1148
1149         if (!ed_curve_select_nth(obedit->data, &op_params)) {
1150                 if (obedit->type == OB_SURF) {
1151                         BKE_report(op->reports, RPT_ERROR, "Surface has not got active point");
1152                 }
1153                 else {
1154                         BKE_report(op->reports, RPT_ERROR, "Curve has not got active point");
1155                 }
1156
1157                 return OPERATOR_CANCELLED;
1158         }
1159
1160         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
1161
1162         return OPERATOR_FINISHED;
1163 }
1164
1165 void CURVE_OT_select_nth(wmOperatorType *ot)
1166 {
1167         /* identifiers */
1168         ot->name = "Checker Deselect";
1169         ot->description = "Deselect every other vertex";
1170         ot->idname = "CURVE_OT_select_nth";
1171
1172         /* api callbacks */
1173         ot->exec = select_nth_exec;
1174         ot->poll = ED_operator_editsurfcurve;
1175
1176         /* flags */
1177         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1178
1179         WM_operator_properties_checker_interval(ot, false);
1180 }
1181
1182
1183 /* -------------------------------------------------------------------- */
1184 /* Select Similar */
1185
1186 /** \name Select Similar
1187  * \{ */
1188
1189 enum {
1190         SIM_CMP_EQ = 0,
1191         SIM_CMP_GT,
1192         SIM_CMP_LT,
1193 };
1194
1195 static EnumPropertyItem curve_prop_similar_compare_types[] = {
1196         {SIM_CMP_EQ, "EQUAL", 0, "Equal", ""},
1197         {SIM_CMP_GT, "GREATER", 0, "Greater", ""},
1198         {SIM_CMP_LT, "LESS", 0, "Less", ""},
1199
1200         {0, NULL, 0, NULL, NULL}
1201 };
1202
1203 enum {
1204         SIMCURHAND_TYPE = 0,
1205         SIMCURHAND_RADIUS,
1206         SIMCURHAND_WEIGHT,
1207         SIMCURHAND_DIRECTION,
1208 };
1209
1210 static EnumPropertyItem curve_prop_similar_types[] = {
1211         {SIMCURHAND_TYPE, "TYPE", 0, "Type", ""},
1212         {SIMCURHAND_RADIUS, "RADIUS", 0, "Radius", ""},
1213         {SIMCURHAND_WEIGHT, "WEIGHT", 0, "Weight", ""},
1214         {SIMCURHAND_DIRECTION, "DIRECTION", 0, "Direction", ""},
1215         {0, NULL, 0, NULL, NULL}
1216 };
1217
1218 static int curve_select_similar_cmp_fl(const float delta, const float thresh, const int compare)
1219 {
1220         switch (compare) {
1221                 case SIM_CMP_EQ:
1222                         return (fabsf(delta) <= thresh);
1223                 case SIM_CMP_GT:
1224                         return ((delta + thresh) >= 0.0f);
1225                 case SIM_CMP_LT:
1226                         return ((delta - thresh) <= 0.0f);
1227                 default:
1228                         BLI_assert(0);
1229                         return 0;
1230         }
1231 }
1232
1233
1234 static void curve_select_similar_direction__bezt(Nurb *nu, const float dir_ref[3], float angle_cos)
1235 {
1236         BezTriple *bezt;
1237         int i;
1238
1239         for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
1240                 if (!bezt->hide) {
1241                         float dir[3];
1242                         BKE_nurb_bezt_calc_normal(nu, bezt, dir);
1243                         if (fabsf(dot_v3v3(dir_ref, dir)) >= angle_cos) {
1244                                 select_beztriple(bezt, SELECT, SELECT, VISIBLE);
1245                         }
1246                 }
1247         }
1248 }
1249
1250 static void curve_select_similar_direction__bp(Nurb *nu, const float dir_ref[3], float angle_cos)
1251 {
1252         BPoint *bp;
1253         int i;
1254
1255         for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
1256                 if (!bp->hide) {
1257                         float dir[3];
1258                         BKE_nurb_bpoint_calc_normal(nu, bp, dir);
1259                         if (fabsf(dot_v3v3(dir_ref, dir)) >= angle_cos) {
1260                                 select_bpoint(bp, SELECT, SELECT, VISIBLE);
1261                         }
1262                 }
1263         }
1264 }
1265
1266 static bool curve_select_similar_direction(ListBase *editnurb, Curve *cu, float thresh)
1267 {
1268         Nurb *nu, *act_nu;
1269         void *act_vert;
1270         float dir[3];
1271         float angle_cos;
1272
1273         if (!BKE_curve_nurb_vert_active_get(cu, &act_nu, &act_vert)) {
1274                 return false;
1275         }
1276
1277         if (act_nu->type == CU_BEZIER) {
1278                 BKE_nurb_bezt_calc_normal(act_nu, act_vert, dir);
1279         }
1280         else {
1281                 BKE_nurb_bpoint_calc_normal(act_nu, act_vert, dir);
1282         }
1283
1284         /* map 0-1 to radians, 'cos' for comparison */
1285         angle_cos = cosf(thresh * (float)M_PI_2);
1286
1287         for (nu = editnurb->first; nu; nu = nu->next) {
1288                 if (nu->type == CU_BEZIER) {
1289                         curve_select_similar_direction__bezt(nu, dir, angle_cos);
1290                 }
1291                 else {
1292                         curve_select_similar_direction__bp(nu, dir, angle_cos);
1293                 }
1294         }
1295
1296         return true;
1297 }
1298
1299 static void curve_select_similar_radius__bezt(Nurb *nu, float radius_ref, int compare, float thresh)
1300 {
1301         BezTriple *bezt;
1302         int i;
1303
1304         for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
1305                 if (!bezt->hide) {
1306                         if (curve_select_similar_cmp_fl(bezt->radius - radius_ref, thresh, compare)) {
1307                                 select_beztriple(bezt, SELECT, SELECT, VISIBLE);
1308                         }
1309                 }
1310         }
1311 }
1312
1313 static void curve_select_similar_radius__bp(Nurb *nu, float radius_ref, int compare, float thresh)
1314 {
1315         BPoint *bp;
1316         int i;
1317
1318         for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
1319                 if (!bp->hide) {
1320                         if (curve_select_similar_cmp_fl(bp->radius - radius_ref, thresh, compare)) {
1321                                 select_bpoint(bp, SELECT, SELECT, VISIBLE);
1322                         }
1323                 }
1324         }
1325 }
1326
1327 static bool curve_select_similar_radius(ListBase *editnurb, Curve *cu, float compare, float thresh)
1328 {
1329         Nurb *nu, *act_nu;
1330         void *act_vert;
1331         float radius_ref;
1332
1333         if (!BKE_curve_nurb_vert_active_get(cu, &act_nu, &act_vert)) {
1334                 return false;
1335         }
1336
1337         if (act_nu->type == CU_BEZIER) {
1338                 radius_ref = ((BezTriple *)act_vert)->radius;
1339         }
1340         else {
1341                 radius_ref = ((BPoint *)act_vert)->radius;
1342         }
1343
1344         /* make relative */
1345         thresh *= radius_ref;
1346
1347         for (nu = editnurb->first; nu; nu = nu->next) {
1348                 if (nu->type == CU_BEZIER) {
1349                         curve_select_similar_radius__bezt(nu, radius_ref, compare, thresh);
1350                 }
1351                 else {
1352                         curve_select_similar_radius__bp(nu, radius_ref, compare, thresh);
1353                 }
1354         }
1355
1356         return true;
1357 }
1358
1359 static void curve_select_similar_weight__bezt(Nurb *nu, float weight_ref, int compare, float thresh)
1360 {
1361         BezTriple *bezt;
1362         int i;
1363
1364         for (i = nu->pntsu, bezt = nu->bezt; i--; bezt++) {
1365                 if (!bezt->hide) {
1366                         if (curve_select_similar_cmp_fl(bezt->weight - weight_ref, thresh, compare)) {
1367                                 select_beztriple(bezt, SELECT, SELECT, VISIBLE);
1368                         }
1369                 }
1370         }
1371 }
1372
1373 static void curve_select_similar_weight__bp(Nurb *nu, float weight_ref, int compare, float thresh)
1374 {
1375         BPoint *bp;
1376         int i;
1377
1378         for (i = nu->pntsu * nu->pntsv, bp = nu->bp; i--; bp++) {
1379                 if (!bp->hide) {
1380                         if (curve_select_similar_cmp_fl(bp->weight - weight_ref, thresh, compare)) {
1381                                 select_bpoint(bp, SELECT, SELECT, VISIBLE);
1382                         }
1383                 }
1384         }
1385 }
1386
1387 static bool curve_select_similar_weight(ListBase *editnurb, Curve *cu, float compare, float thresh)
1388 {
1389         Nurb *nu, *act_nu;
1390         void *act_vert;
1391         float weight_ref;
1392
1393         if (!BKE_curve_nurb_vert_active_get(cu, &act_nu, &act_vert))
1394                 return false;
1395
1396         if (act_nu->type == CU_BEZIER) {
1397                 weight_ref = ((BezTriple *)act_vert)->weight;
1398         }
1399         else {
1400                 weight_ref = ((BPoint *)act_vert)->weight;
1401         }
1402
1403         for (nu = editnurb->first; nu; nu = nu->next) {
1404                 if (nu->type == CU_BEZIER) {
1405                         curve_select_similar_weight__bezt(nu, weight_ref, compare, thresh);
1406                 }
1407                 else {
1408                         curve_select_similar_weight__bp(nu, weight_ref, compare, thresh);
1409                 }
1410         }
1411
1412         return true;
1413 }
1414
1415 static bool curve_select_similar_type(ListBase *editnurb, Curve *cu)
1416 {
1417         Nurb *nu, *act_nu;
1418         int type_ref;
1419
1420         /* Get active nurb type */
1421         act_nu = BKE_curve_nurb_active_get(cu);
1422
1423         if (!act_nu)
1424                 return false;
1425
1426         /* Get the active nurb type */
1427         type_ref = act_nu->type;
1428
1429         for (nu = editnurb->first; nu; nu = nu->next) {
1430                 if (nu->type == type_ref) {
1431                         ED_curve_nurb_select_all(nu);
1432                 }
1433         }
1434
1435         return true;
1436 }
1437
1438 static int curve_select_similar_exec(bContext *C, wmOperator *op)
1439 {
1440         Object *obedit = CTX_data_edit_object(C);
1441         Curve *cu = obedit->data;
1442         ListBase *editnurb = object_editcurve_get(obedit);
1443         bool changed = false;
1444
1445         /* Get props */
1446         const int type = RNA_enum_get(op->ptr, "type");
1447         const float thresh = RNA_float_get(op->ptr, "threshold");
1448         const int compare = RNA_enum_get(op->ptr, "compare");
1449
1450         switch (type) {
1451                 case SIMCURHAND_TYPE:
1452                         changed = curve_select_similar_type(editnurb, cu);
1453                         break;
1454                 case SIMCURHAND_RADIUS:
1455                         changed = curve_select_similar_radius(editnurb, cu, compare, thresh);
1456                         break;
1457                 case SIMCURHAND_WEIGHT:
1458                         changed = curve_select_similar_weight(editnurb, cu, compare, thresh);
1459                         break;
1460                 case SIMCURHAND_DIRECTION:
1461                         changed = curve_select_similar_direction(editnurb, cu, thresh);
1462                         break;
1463         }
1464
1465         if (changed) {
1466                 WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
1467                 return OPERATOR_FINISHED;
1468         }
1469         else {
1470                 return OPERATOR_CANCELLED;
1471         }
1472 }
1473
1474 void CURVE_OT_select_similar(wmOperatorType *ot)
1475 {
1476         /* identifiers */
1477         ot->name = "Select Similar";
1478         ot->idname = "CURVE_OT_select_similar";
1479         ot->description = "Select similar curve points by property type";
1480
1481         /* api callbacks */
1482         ot->invoke = WM_menu_invoke;
1483         ot->exec = curve_select_similar_exec;
1484         ot->poll = ED_operator_editsurfcurve;
1485
1486         /* flags */
1487         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1488
1489         /* properties */
1490         ot->prop = RNA_def_enum(ot->srna, "type", curve_prop_similar_types, SIMCURHAND_WEIGHT, "Type", "");
1491         RNA_def_enum(ot->srna, "compare", curve_prop_similar_compare_types, SIM_CMP_EQ, "Compare", "");
1492         RNA_def_float(ot->srna, "threshold", 0.1, 0.0, FLT_MAX, "Threshold", "", 0.0, 100.0);
1493 }
1494
1495 /** \} */
1496
1497
1498 /* -------------------------------------------------------------------- */
1499 /* Select Shortest Path */
1500
1501 /** \name Select Path
1502  * \{ */
1503
1504 static float curve_calc_dist_pair(const Nurb *nu, int a, int b)
1505 {
1506         const float *a_fl, *b_fl;
1507
1508         if (nu->type == CU_BEZIER) {
1509                 a_fl = nu->bezt[a].vec[1];
1510                 b_fl = nu->bezt[b].vec[1];
1511         }
1512         else {
1513                 a_fl = nu->bp[a].vec;
1514                 b_fl = nu->bp[b].vec;
1515         }
1516
1517         return len_v3v3(a_fl, b_fl);
1518 }
1519
1520 static float curve_calc_dist_span(Nurb *nu, int vert_src, int vert_dst)
1521 {
1522         const int u = nu->pntsu;
1523         int i_prev, i;
1524         float dist = 0.0f;
1525
1526         BLI_assert(nu->pntsv == 1);
1527
1528         i_prev = vert_src;
1529         i = (i_prev + 1) % u;
1530
1531         while (true) {
1532                 dist += curve_calc_dist_pair(nu, i_prev, i);
1533
1534                 if (i == vert_dst) {
1535                         break;
1536                 }
1537                 i = (i + 1) % u;
1538         }
1539         return dist;
1540 }
1541
1542 static void curve_select_shortest_path_curve(Nurb *nu, int vert_src, int vert_dst)
1543 {
1544         const int u = nu->pntsu;
1545         int i;
1546
1547         if (vert_src > vert_dst) {
1548                 SWAP(int, vert_src, vert_dst);
1549         }
1550
1551         if (nu->flagu & CU_NURB_CYCLIC) {
1552                 if (curve_calc_dist_span(nu, vert_src, vert_dst) >
1553                     curve_calc_dist_span(nu, vert_dst, vert_src))
1554                 {
1555                         SWAP(int, vert_src, vert_dst);
1556                 }
1557         }
1558
1559         i = vert_src;
1560         while (true) {
1561                 if (nu->type & CU_BEZIER) {
1562                         select_beztriple(&nu->bezt[i], SELECT, SELECT, HIDDEN);
1563                 }
1564                 else {
1565                         select_bpoint(&nu->bp[i], SELECT, SELECT, HIDDEN);
1566                 }
1567
1568                 if (i == vert_dst) {
1569                         break;
1570                 }
1571                 i = (i + 1) % u;
1572         }
1573 }
1574
1575 static void curve_select_shortest_path_surf(Nurb *nu, int vert_src, int vert_dst)
1576 {
1577         Heap *heap;
1578
1579         int i, vert_curr;
1580
1581         int totu = nu->pntsu;
1582         int totv = nu->pntsv;
1583         int vert_num = totu * totv;
1584
1585         /* custom data */
1586         struct PointAdj {
1587                 int vert, vert_prev;
1588                 float cost;
1589         } *data;
1590
1591         /* init connectivity data */
1592         data = MEM_mallocN(sizeof(*data) * vert_num, __func__);
1593         for (i = 0; i < vert_num; i++) {
1594                 data[i].vert = i;
1595                 data[i].vert_prev  = -1;
1596                 data[i].cost  = FLT_MAX;
1597         }
1598
1599         /* init heap */
1600         heap = BLI_heap_new();
1601
1602         BLI_heap_insert(heap, 0.0f, &data[vert_src].vert);
1603         data[vert_src].cost = 0.0f;
1604         data[vert_src].vert_prev = vert_src;  /* nop */
1605
1606         while (!BLI_heap_is_empty(heap)) {
1607                 int axis, sign;
1608                 int u, v;
1609
1610                 vert_curr = *((int *)BLI_heap_popmin(heap));
1611                 if (vert_curr == vert_dst) {
1612                         break;
1613                 }
1614
1615                 BKE_nurb_index_to_uv(nu, vert_curr, &u, &v);
1616
1617                 /* loop over 4 adjacent verts */
1618                 for (sign = -1; sign != 3; sign += 2) {
1619                         for (axis = 0; axis != 2; axis += 1) {
1620                                 int uv_other[2] = {u, v};
1621                                 int vert_other;
1622
1623                                 uv_other[axis] += sign;
1624
1625                                 vert_other = BKE_nurb_index_from_uv(nu, uv_other[0], uv_other[1]);
1626                                 if (vert_other != -1) {
1627                                         const float dist = data[vert_curr].cost + curve_calc_dist_pair(nu, vert_curr, vert_other);
1628
1629                                         if (data[vert_other].cost > dist) {
1630                                                 data[vert_other].cost = dist;
1631                                                 if (data[vert_other].vert_prev == -1) {
1632                                                         BLI_heap_insert(heap, data[vert_other].cost, &data[vert_other].vert);
1633                                                 }
1634                                                 data[vert_other].vert_prev = vert_curr;
1635                                         }
1636                                 }
1637
1638                         }
1639                 }
1640
1641         }
1642
1643         BLI_heap_free(heap, NULL);
1644
1645         if (vert_curr == vert_dst) {
1646                 i = 0;
1647                 while (vert_curr != vert_src && i++ < vert_num) {
1648                         if (nu->type == CU_BEZIER) {
1649                                 select_beztriple(&nu->bezt[vert_curr], SELECT, SELECT, HIDDEN);
1650                         }
1651                         else {
1652                                 select_bpoint(&nu->bp[vert_curr], SELECT, SELECT, HIDDEN);
1653                         }
1654                         vert_curr = data[vert_curr].vert_prev;
1655                 }
1656         }
1657
1658         MEM_freeN(data);
1659 }
1660
1661 static int edcu_shortest_path_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event)
1662 {
1663         Object *obedit = CTX_data_edit_object(C);
1664         Curve *cu = obedit->data;
1665         Nurb *nu_src = BKE_curve_nurb_active_get(cu);
1666         int vert_src = cu->actvert;
1667
1668         ViewContext vc;
1669         Nurb *nu_dst;
1670         BezTriple *bezt_dst;
1671         BPoint *bp_dst;
1672         int vert_dst;
1673         void *vert_dst_p;
1674
1675         if (vert_src == CU_ACT_NONE) {
1676                 return OPERATOR_PASS_THROUGH;
1677         }
1678
1679         view3d_operator_needs_opengl(C);
1680         view3d_set_viewcontext(C, &vc);
1681
1682         if (!ED_curve_pick_vert(&vc, 1, event->mval, &nu_dst, &bezt_dst, &bp_dst, NULL)) {
1683                 return OPERATOR_PASS_THROUGH;
1684         }
1685
1686         if (nu_src != nu_dst) {
1687                 BKE_report(op->reports, RPT_ERROR, "Control point belongs to another spline");
1688                 return OPERATOR_CANCELLED;
1689         }
1690
1691         vert_dst_p = bezt_dst ? (void *)bezt_dst : (void *)bp_dst;
1692         vert_dst = BKE_curve_nurb_vert_index_get(nu_dst, vert_dst_p);
1693         if (vert_src == vert_dst) {
1694                 return OPERATOR_CANCELLED;
1695         }
1696
1697         if ((obedit->type == OB_SURF) && (nu_src->pntsv > 1)) {
1698                 curve_select_shortest_path_surf(nu_src, vert_src, vert_dst);
1699         }
1700         else {
1701                 curve_select_shortest_path_curve(nu_src, vert_src, vert_dst);
1702         }
1703
1704         BKE_curve_nurb_vert_active_set(cu, nu_dst, vert_dst_p);
1705
1706         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
1707         return OPERATOR_FINISHED;
1708 }
1709
1710 void CURVE_OT_shortest_path_pick(wmOperatorType *ot)
1711 {
1712         /* identifiers */
1713         ot->name = "Pick Shortest Path";
1714         ot->idname = "CURVE_OT_shortest_path_pick";
1715         ot->description = "Select shortest path between two selections";
1716
1717         /* api callbacks */
1718         ot->invoke = edcu_shortest_path_pick_invoke;
1719         ot->poll = ED_operator_editsurfcurve_region_view3d;
1720
1721         /* flags */
1722         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1723 }
1724
1725 /** \} */