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