Revert "UI: use correct singular and plural nouns in report messages"
[blender.git] / source / blender / editors / physics / particle_edit.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) 2007 by Janne Karhu.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup edphys
22  */
23
24 #include <stdlib.h>
25 #include <math.h>
26 #include <string.h>
27 #include <assert.h>
28
29 #include "MEM_guardedalloc.h"
30
31 #include "DNA_scene_types.h"
32 #include "DNA_mesh_types.h"
33 #include "DNA_meshdata_types.h"
34 #include "DNA_view3d_types.h"
35 #include "DNA_screen_types.h"
36 #include "DNA_space_types.h"
37
38 #include "BLI_math.h"
39 #include "BLI_lasso_2d.h"
40 #include "BLI_listbase.h"
41 #include "BLI_rect.h"
42 #include "BLI_kdtree.h"
43 #include "BLI_rand.h"
44 #include "BLI_task.h"
45 #include "BLI_utildefines.h"
46
47 #include "BKE_bvhutils.h"
48 #include "BKE_context.h"
49 #include "BKE_global.h"
50 #include "BKE_main.h"
51 #include "BKE_mesh.h"
52 #include "BKE_mesh_runtime.h"
53 #include "BKE_modifier.h"
54 #include "BKE_object.h"
55 #include "BKE_particle.h"
56 #include "BKE_pointcache.h"
57 #include "BKE_report.h"
58 #include "BKE_scene.h"
59
60 #include "DEG_depsgraph.h"
61
62 #include "ED_object.h"
63 #include "ED_physics.h"
64 #include "ED_mesh.h"
65 #include "ED_particle.h"
66 #include "ED_screen.h"
67 #include "ED_select_utils.h"
68 #include "ED_view3d.h"
69
70 #include "GPU_immediate.h"
71 #include "GPU_immediate_util.h"
72 #include "GPU_state.h"
73
74 #include "UI_resources.h"
75
76 #include "WM_api.h"
77 #include "WM_types.h"
78 #include "WM_message.h"
79 #include "WM_toolsystem.h"
80
81 #include "RNA_access.h"
82 #include "RNA_define.h"
83
84 #include "DEG_depsgraph_query.h"
85
86 #include "PIL_time_utildefines.h"
87
88 #include "physics_intern.h"
89
90 #include "particle_edit_utildefines.h"
91
92 /**************************** utilities *******************************/
93
94 bool PE_poll(bContext *C)
95 {
96   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
97   Scene *scene = CTX_data_scene(C);
98   Object *ob = CTX_data_active_object(C);
99
100   if (!scene || !ob || !(ob->mode & OB_MODE_PARTICLE_EDIT)) {
101     return false;
102   }
103
104   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
105   if (edit == NULL) {
106     return false;
107   }
108   if (edit->psmd_eval == NULL || edit->psmd_eval->mesh_final == NULL) {
109     return false;
110   }
111
112   return true;
113 }
114
115 bool PE_hair_poll(bContext *C)
116 {
117   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
118   Scene *scene = CTX_data_scene(C);
119   Object *ob = CTX_data_active_object(C);
120
121   if (!scene || !ob || !(ob->mode & OB_MODE_PARTICLE_EDIT)) {
122     return false;
123   }
124
125   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
126   if (edit == NULL || edit->psys == NULL) {
127     return false;
128   }
129   if (edit->psmd_eval == NULL || edit->psmd_eval->mesh_final == NULL) {
130     return false;
131   }
132
133   return true;
134 }
135
136 bool PE_poll_view3d(bContext *C)
137 {
138   ScrArea *sa = CTX_wm_area(C);
139   ARegion *ar = CTX_wm_region(C);
140
141   return (PE_poll(C) && (sa && sa->spacetype == SPACE_VIEW3D) &&
142           (ar && ar->regiontype == RGN_TYPE_WINDOW));
143 }
144
145 void PE_free_ptcache_edit(PTCacheEdit *edit)
146 {
147   POINT_P;
148
149   if (edit == 0) {
150     return;
151   }
152
153   if (edit->points) {
154     LOOP_POINTS {
155       if (point->keys) {
156         MEM_freeN(point->keys);
157       }
158     }
159
160     MEM_freeN(edit->points);
161   }
162
163   if (edit->mirror_cache) {
164     MEM_freeN(edit->mirror_cache);
165   }
166
167   if (edit->emitter_cosnos) {
168     MEM_freeN(edit->emitter_cosnos);
169     edit->emitter_cosnos = 0;
170   }
171
172   if (edit->emitter_field) {
173     BLI_kdtree_3d_free(edit->emitter_field);
174     edit->emitter_field = 0;
175   }
176
177   psys_free_path_cache(edit->psys, edit);
178
179   MEM_freeN(edit);
180 }
181
182 /************************************************/
183 /*          Edit Mode Helpers                   */
184 /************************************************/
185
186 int PE_start_edit(PTCacheEdit *edit)
187 {
188   if (edit) {
189     edit->edited = 1;
190     if (edit->psys) {
191       edit->psys->flag |= PSYS_EDITED;
192     }
193     return 1;
194   }
195
196   return 0;
197 }
198
199 ParticleEditSettings *PE_settings(Scene *scene)
200 {
201   return scene->toolsettings ? &scene->toolsettings->particle : NULL;
202 }
203
204 static float pe_brush_size_get(const Scene *UNUSED(scene), ParticleBrushData *brush)
205 {
206   // here we can enable unified brush size, needs more work...
207   // UnifiedPaintSettings *ups = &scene->toolsettings->unified_paint_settings;
208   // float size = (ups->flag & UNIFIED_PAINT_SIZE) ? ups->size : brush->size;
209
210   return brush->size * U.pixelsize;
211 }
212
213 PTCacheEdit *PE_get_current_from_psys(ParticleSystem *psys)
214 {
215   if (psys->part && psys->part->type == PART_HAIR) {
216     if ((psys->flag & PSYS_HAIR_DYNAMICS) != 0 && (psys->pointcache->flag & PTCACHE_BAKED) != 0) {
217       return psys->pointcache->edit;
218     }
219     else {
220       return psys->edit;
221     }
222   }
223   else if (psys->pointcache->flag & PTCACHE_BAKED) {
224     return psys->pointcache->edit;
225   }
226   return NULL;
227 }
228
229 /* NOTE: Similar to creation of edit, but only updates pointers in the
230  * existing struct.
231  */
232 static void pe_update_hair_particle_edit_pointers(PTCacheEdit *edit)
233 {
234   ParticleSystem *psys = edit->psys;
235   ParticleData *pa = psys->particles;
236   for (int p = 0; p < edit->totpoint; p++) {
237     PTCacheEditPoint *point = &edit->points[p];
238     HairKey *hair_key = pa->hair;
239     for (int k = 0; k < point->totkey; k++) {
240       PTCacheEditKey *key = &point->keys[k];
241       key->co = hair_key->co;
242       key->time = &hair_key->time;
243       key->flag = hair_key->editflag;
244       if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
245         key->flag |= PEK_USE_WCO;
246         hair_key->editflag |= PEK_USE_WCO;
247       }
248       hair_key++;
249     }
250     pa++;
251   }
252 }
253
254 /* always gets at least the first particlesystem even if PSYS_CURRENT flag is not set
255  *
256  * note: this function runs on poll, therefore it can runs many times a second
257  * keep it fast! */
258 static PTCacheEdit *pe_get_current(Depsgraph *depsgraph, Scene *scene, Object *ob, int create)
259 {
260   ParticleEditSettings *pset = PE_settings(scene);
261   PTCacheEdit *edit = NULL;
262   ListBase pidlist;
263   PTCacheID *pid;
264
265   if (pset == NULL || ob == NULL) {
266     return NULL;
267   }
268
269   pset->scene = scene;
270   pset->object = ob;
271
272   BKE_ptcache_ids_from_object(&pidlist, ob, NULL, 0);
273
274   /* in the case of only one editable thing, set pset->edittype accordingly */
275   if (BLI_listbase_is_single(&pidlist)) {
276     pid = pidlist.first;
277     switch (pid->type) {
278       case PTCACHE_TYPE_PARTICLES:
279         pset->edittype = PE_TYPE_PARTICLES;
280         break;
281       case PTCACHE_TYPE_SOFTBODY:
282         pset->edittype = PE_TYPE_SOFTBODY;
283         break;
284       case PTCACHE_TYPE_CLOTH:
285         pset->edittype = PE_TYPE_CLOTH;
286         break;
287     }
288   }
289
290   for (pid = pidlist.first; pid; pid = pid->next) {
291     if (pset->edittype == PE_TYPE_PARTICLES && pid->type == PTCACHE_TYPE_PARTICLES) {
292       ParticleSystem *psys = pid->calldata;
293
294       if (psys->flag & PSYS_CURRENT) {
295         if (psys->part && psys->part->type == PART_HAIR) {
296           if (psys->flag & PSYS_HAIR_DYNAMICS && psys->pointcache->flag & PTCACHE_BAKED) {
297             if (create && !psys->pointcache->edit) {
298               PE_create_particle_edit(depsgraph, scene, ob, pid->cache, NULL);
299             }
300             edit = pid->cache->edit;
301           }
302           else {
303             if (create && !psys->edit) {
304               if (psys->flag & PSYS_HAIR_DONE) {
305                 PE_create_particle_edit(depsgraph, scene, ob, NULL, psys);
306               }
307             }
308             edit = psys->edit;
309           }
310         }
311         else {
312           if (create && pid->cache->flag & PTCACHE_BAKED && !pid->cache->edit) {
313             PE_create_particle_edit(depsgraph, scene, ob, pid->cache, psys);
314           }
315           edit = pid->cache->edit;
316         }
317
318         break;
319       }
320     }
321     else if (pset->edittype == PE_TYPE_SOFTBODY && pid->type == PTCACHE_TYPE_SOFTBODY) {
322       if (create && pid->cache->flag & PTCACHE_BAKED && !pid->cache->edit) {
323         pset->flag |= PE_FADE_TIME;
324         // NICE TO HAVE but doesn't work: pset->brushtype = PE_BRUSH_COMB;
325         PE_create_particle_edit(depsgraph, scene, ob, pid->cache, NULL);
326       }
327       edit = pid->cache->edit;
328       break;
329     }
330     else if (pset->edittype == PE_TYPE_CLOTH && pid->type == PTCACHE_TYPE_CLOTH) {
331       if (create && pid->cache->flag & PTCACHE_BAKED && !pid->cache->edit) {
332         pset->flag |= PE_FADE_TIME;
333         // NICE TO HAVE but doesn't work: pset->brushtype = PE_BRUSH_COMB;
334         PE_create_particle_edit(depsgraph, scene, ob, pid->cache, NULL);
335       }
336       edit = pid->cache->edit;
337       break;
338     }
339   }
340
341   /* Don't consider inactive or render dependency graphs, since they might be evaluated for a
342    * different number of children. or have different pointer to evaluated particle system or
343    * modifier which will also cause troubles. */
344   if (edit && DEG_is_active(depsgraph)) {
345     edit->pid = *pid;
346     if (edit->flags & PT_CACHE_EDIT_UPDATE_PARTICLE_FROM_EVAL) {
347       if (edit->psys != NULL && edit->psys_eval != NULL) {
348         psys_copy_particles(edit->psys, edit->psys_eval);
349         pe_update_hair_particle_edit_pointers(edit);
350       }
351       edit->flags &= ~PT_CACHE_EDIT_UPDATE_PARTICLE_FROM_EVAL;
352     }
353   }
354
355   BLI_freelistN(&pidlist);
356
357   return edit;
358 }
359
360 PTCacheEdit *PE_get_current(Depsgraph *depsgraph, Scene *scene, Object *ob)
361 {
362   return pe_get_current(depsgraph, scene, ob, 0);
363 }
364
365 PTCacheEdit *PE_create_current(Depsgraph *depsgraph, Scene *scene, Object *ob)
366 {
367   return pe_get_current(depsgraph, scene, ob, 1);
368 }
369
370 void PE_current_changed(Depsgraph *depsgraph, Scene *scene, Object *ob)
371 {
372   if (ob->mode == OB_MODE_PARTICLE_EDIT) {
373     PE_create_current(depsgraph, scene, ob);
374   }
375 }
376
377 void PE_hide_keys_time(Scene *scene, PTCacheEdit *edit, float cfra)
378 {
379   ParticleEditSettings *pset = PE_settings(scene);
380   POINT_P;
381   KEY_K;
382
383   if (pset->flag & PE_FADE_TIME && pset->selectmode == SCE_SELECT_POINT) {
384     LOOP_POINTS {
385       LOOP_KEYS {
386         if (fabsf(cfra - *key->time) < pset->fade_frames) {
387           key->flag &= ~PEK_HIDE;
388         }
389         else {
390           key->flag |= PEK_HIDE;
391           // key->flag &= ~PEK_SELECT;
392         }
393       }
394     }
395   }
396   else {
397     LOOP_POINTS {
398       LOOP_KEYS {
399         key->flag &= ~PEK_HIDE;
400       }
401     }
402   }
403 }
404
405 static int pe_x_mirror(Object *ob)
406 {
407   if (ob->type == OB_MESH) {
408     return (((Mesh *)ob->data)->editflag & ME_EDIT_MIRROR_X);
409   }
410
411   return 0;
412 }
413
414 /****************** common struct passed to callbacks ******************/
415
416 typedef struct PEData {
417   ViewContext vc;
418
419   const bContext *context;
420   Main *bmain;
421   Scene *scene;
422   ViewLayer *view_layer;
423   Object *ob;
424   Mesh *mesh;
425   PTCacheEdit *edit;
426   BVHTreeFromMesh shape_bvh;
427   Depsgraph *depsgraph;
428
429   RNG *rng;
430
431   const int *mval;
432   const rcti *rect;
433   float rad;
434   float dval;
435   int select;
436   eSelectOp sel_op;
437
438   float *dvec;
439   float combfac;
440   float pufffac;
441   float cutfac;
442   float smoothfac;
443   float weightfac;
444   float growfac;
445   int totrekey;
446
447   int invert;
448   int tot;
449   float vec[3];
450
451   int select_action;
452   int select_toggle_action;
453   bool is_changed;
454 } PEData;
455
456 static void PE_set_data(bContext *C, PEData *data)
457 {
458   memset(data, 0, sizeof(*data));
459
460   data->context = C;
461   data->bmain = CTX_data_main(C);
462   data->scene = CTX_data_scene(C);
463   data->view_layer = CTX_data_view_layer(C);
464   data->ob = CTX_data_active_object(C);
465   data->depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
466   data->edit = PE_get_current(data->depsgraph, data->scene, data->ob);
467 }
468
469 static void PE_set_view3d_data(bContext *C, PEData *data)
470 {
471   PE_set_data(C, data);
472
473   Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
474   ED_view3d_viewcontext_init(C, &data->vc, depsgraph);
475
476   if (!XRAY_ENABLED(data->vc.v3d)) {
477     if (data->vc.v3d->flag & V3D_INVALID_BACKBUF) {
478       /* needed or else the draw matrix can be incorrect */
479       view3d_operator_needs_opengl(C);
480
481       ED_view3d_backbuf_depth_validate(&data->vc);
482       /* we may need to force an update here by setting the rv3d as dirty
483        * for now it seems ok, but take care!:
484        * rv3d->depths->dirty = 1; */
485       ED_view3d_depth_update(data->vc.ar);
486     }
487   }
488 }
489
490 static bool PE_create_shape_tree(PEData *data, Object *shapeob)
491 {
492   Mesh *mesh = BKE_object_get_evaluated_mesh(data->depsgraph, shapeob);
493
494   memset(&data->shape_bvh, 0, sizeof(data->shape_bvh));
495
496   if (!mesh) {
497     return false;
498   }
499
500   return (BKE_bvhtree_from_mesh_get(&data->shape_bvh, mesh, BVHTREE_FROM_LOOPTRI, 4) != NULL);
501 }
502
503 static void PE_free_shape_tree(PEData *data)
504 {
505   free_bvhtree_from_mesh(&data->shape_bvh);
506 }
507
508 static void PE_create_random_generator(PEData *data)
509 {
510   uint rng_seed = (uint)(PIL_check_seconds_timer_i() & UINT_MAX);
511   rng_seed ^= POINTER_AS_UINT(data->ob);
512   rng_seed ^= POINTER_AS_UINT(data->edit);
513   data->rng = BLI_rng_new(rng_seed);
514 }
515
516 static void PE_free_random_generator(PEData *data)
517 {
518   if (data->rng != NULL) {
519     BLI_rng_free(data->rng);
520     data->rng = NULL;
521   }
522 }
523
524 /*************************** selection utilities *******************************/
525
526 static bool key_test_depth(const PEData *data, const float co[3], const int screen_co[2])
527 {
528   View3D *v3d = data->vc.v3d;
529   ViewDepths *vd = data->vc.rv3d->depths;
530   float depth;
531
532   /* nothing to do */
533   if (XRAY_ENABLED(v3d)) {
534     return true;
535   }
536
537   /* used to calculate here but all callers have  the screen_co already, so pass as arg */
538 #if 0
539   if (ED_view3d_project_int_global(data->vc.ar,
540                                    co,
541                                    screen_co,
542                                    V3D_PROJ_TEST_CLIP_BB | V3D_PROJ_TEST_CLIP_WIN |
543                                        V3D_PROJ_TEST_CLIP_NEAR) != V3D_PROJ_RET_OK) {
544     return 0;
545   }
546 #endif
547
548   /* check if screen_co is within bounds because brush_cut uses out of screen coords */
549   if (screen_co[0] >= 0 && screen_co[0] < vd->w && screen_co[1] >= 0 && screen_co[1] < vd->h) {
550     BLI_assert(vd && vd->depths);
551     /* we know its not clipped */
552     depth = vd->depths[screen_co[1] * vd->w + screen_co[0]];
553   }
554   else {
555     return 0;
556   }
557
558   float win[3];
559   ED_view3d_project(data->vc.ar, co, win);
560
561   if (win[2] - 0.00001f > depth) {
562     return 0;
563   }
564   else {
565     return 1;
566   }
567 }
568
569 static bool key_inside_circle(const PEData *data, float rad, const float co[3], float *distance)
570 {
571   float dx, dy, dist;
572   int screen_co[2];
573
574   /* TODO, should this check V3D_PROJ_TEST_CLIP_BB too? */
575   if (ED_view3d_project_int_global(data->vc.ar, co, screen_co, V3D_PROJ_TEST_CLIP_WIN) !=
576       V3D_PROJ_RET_OK) {
577     return 0;
578   }
579
580   dx = data->mval[0] - screen_co[0];
581   dy = data->mval[1] - screen_co[1];
582   dist = sqrtf(dx * dx + dy * dy);
583
584   if (dist > rad) {
585     return 0;
586   }
587
588   if (key_test_depth(data, co, screen_co)) {
589     if (distance) {
590       *distance = dist;
591     }
592
593     return 1;
594   }
595
596   return 0;
597 }
598
599 static bool key_inside_rect(PEData *data, const float co[3])
600 {
601   int screen_co[2];
602
603   if (ED_view3d_project_int_global(data->vc.ar, co, screen_co, V3D_PROJ_TEST_CLIP_WIN) !=
604       V3D_PROJ_RET_OK) {
605     return 0;
606   }
607
608   if (screen_co[0] > data->rect->xmin && screen_co[0] < data->rect->xmax &&
609       screen_co[1] > data->rect->ymin && screen_co[1] < data->rect->ymax) {
610     return key_test_depth(data, co, screen_co);
611   }
612
613   return 0;
614 }
615
616 static bool key_inside_test(PEData *data, const float co[3])
617 {
618   if (data->mval) {
619     return key_inside_circle(data, data->rad, co, NULL);
620   }
621   else {
622     return key_inside_rect(data, co);
623   }
624 }
625
626 static bool point_is_selected(PTCacheEditPoint *point)
627 {
628   KEY_K;
629
630   if (point->flag & PEP_HIDE) {
631     return 0;
632   }
633
634   LOOP_SELECTED_KEYS {
635     return 1;
636   }
637
638   return 0;
639 }
640
641 /*************************** iterators *******************************/
642
643 typedef void (*ForPointFunc)(PEData *data, int point_index);
644 typedef void (*ForHitPointFunc)(PEData *data, int point_index, float mouse_distance);
645
646 typedef void (*ForKeyFunc)(PEData *data, int point_index, int key_index, bool is_inside);
647
648 typedef void (*ForKeyMatFunc)(PEData *data,
649                               const float mat[4][4],
650                               const float imat[4][4],
651                               int point_index,
652                               int key_index,
653                               PTCacheEditKey *key);
654 typedef void (*ForHitKeyMatFunc)(PEData *data,
655                                  float mat[4][4],
656                                  float imat[4][4],
657                                  int point_index,
658                                  int key_index,
659                                  PTCacheEditKey *key,
660                                  float mouse_distance);
661
662 enum eParticleSelectFlag {
663   PSEL_NEAREST = (1 << 0),
664   PSEL_ALL_KEYS = (1 << 1),
665 };
666
667 static void for_mouse_hit_keys(PEData *data, ForKeyFunc func, const enum eParticleSelectFlag flag)
668 {
669   ParticleEditSettings *pset = PE_settings(data->scene);
670   PTCacheEdit *edit = data->edit;
671   POINT_P;
672   KEY_K;
673   int nearest_point, nearest_key;
674   float dist = data->rad;
675
676   /* in path select mode we have no keys */
677   if (pset->selectmode == SCE_SELECT_PATH) {
678     return;
679   }
680
681   nearest_point = -1;
682   nearest_key = -1;
683
684   LOOP_VISIBLE_POINTS {
685     if (pset->selectmode == SCE_SELECT_END) {
686       if (point->totkey) {
687         /* only do end keys */
688         key = point->keys + point->totkey - 1;
689
690         if (flag & PSEL_NEAREST) {
691           if (key_inside_circle(data, dist, KEY_WCO, &dist)) {
692             nearest_point = p;
693             nearest_key = point->totkey - 1;
694           }
695         }
696         else {
697           const bool is_inside = key_inside_test(data, KEY_WCO);
698           if (is_inside || (flag & PSEL_ALL_KEYS)) {
699             func(data, p, point->totkey - 1, is_inside);
700           }
701         }
702       }
703     }
704     else {
705       /* do all keys */
706       LOOP_VISIBLE_KEYS {
707         if (flag & PSEL_NEAREST) {
708           if (key_inside_circle(data, dist, KEY_WCO, &dist)) {
709             nearest_point = p;
710             nearest_key = k;
711           }
712         }
713         else {
714           const bool is_inside = key_inside_test(data, KEY_WCO);
715           if (is_inside || (flag & PSEL_ALL_KEYS)) {
716             func(data, p, k, is_inside);
717           }
718         }
719       }
720     }
721   }
722
723   /* do nearest only */
724   if (flag & PSEL_NEAREST) {
725     if (nearest_point != -1) {
726       func(data, nearest_point, nearest_key, true);
727     }
728   }
729 }
730
731 static void foreach_mouse_hit_point(PEData *data, ForHitPointFunc func, int selected)
732 {
733   ParticleEditSettings *pset = PE_settings(data->scene);
734   PTCacheEdit *edit = data->edit;
735   POINT_P;
736   KEY_K;
737
738   /* all is selected in path mode */
739   if (pset->selectmode == SCE_SELECT_PATH) {
740     selected = 0;
741   }
742
743   LOOP_VISIBLE_POINTS {
744     if (pset->selectmode == SCE_SELECT_END) {
745       if (point->totkey) {
746         /* only do end keys */
747         key = point->keys + point->totkey - 1;
748
749         if (selected == 0 || key->flag & PEK_SELECT) {
750           float mouse_distance;
751           if (key_inside_circle(data, data->rad, KEY_WCO, &mouse_distance)) {
752             func(data, p, mouse_distance);
753           }
754         }
755       }
756     }
757     else {
758       /* do all keys */
759       LOOP_VISIBLE_KEYS {
760         if (selected == 0 || key->flag & PEK_SELECT) {
761           float mouse_distance;
762           if (key_inside_circle(data, data->rad, KEY_WCO, &mouse_distance)) {
763             func(data, p, mouse_distance);
764             break;
765           }
766         }
767       }
768     }
769   }
770 }
771
772 typedef struct KeyIterData {
773   PEData *data;
774   PTCacheEdit *edit;
775   int selected;
776   ForHitKeyMatFunc func;
777 } KeyIterData;
778
779 static void foreach_mouse_hit_key_iter(void *__restrict iter_data_v,
780                                        const int iter,
781                                        const TaskParallelTLS *__restrict UNUSED(tls))
782 {
783   KeyIterData *iter_data = (KeyIterData *)iter_data_v;
784   PEData *data = iter_data->data;
785   PTCacheEdit *edit = data->edit;
786   PTCacheEditPoint *point = &edit->points[iter];
787   if (point->flag & PEP_HIDE) {
788     return;
789   }
790   ParticleSystem *psys = edit->psys;
791   ParticleSystemModifierData *psmd_eval = iter_data->edit->psmd_eval;
792   ParticleEditSettings *pset = PE_settings(data->scene);
793   const int selected = iter_data->selected;
794   float mat[4][4], imat[4][4];
795   unit_m4(mat);
796   unit_m4(imat);
797   if (pset->selectmode == SCE_SELECT_END) {
798     if (point->totkey) {
799       /* only do end keys */
800       PTCacheEditKey *key = point->keys + point->totkey - 1;
801
802       if (selected == 0 || key->flag & PEK_SELECT) {
803         float mouse_distance;
804         if (key_inside_circle(data, data->rad, KEY_WCO, &mouse_distance)) {
805           if (edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
806             psys_mat_hair_to_global(
807                 data->ob, psmd_eval->mesh_final, psys->part->from, psys->particles + iter, mat);
808             invert_m4_m4(imat, mat);
809           }
810           iter_data->func(data, mat, imat, iter, point->totkey - 1, key, mouse_distance);
811         }
812       }
813     }
814   }
815   else {
816     /* do all keys */
817     PTCacheEditKey *key;
818     int k;
819     LOOP_VISIBLE_KEYS {
820       if (selected == 0 || key->flag & PEK_SELECT) {
821         float mouse_distance;
822         if (key_inside_circle(data, data->rad, KEY_WCO, &mouse_distance)) {
823           if (edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
824             psys_mat_hair_to_global(
825                 data->ob, psmd_eval->mesh_final, psys->part->from, psys->particles + iter, mat);
826             invert_m4_m4(imat, mat);
827           }
828           iter_data->func(data, mat, imat, iter, k, key, mouse_distance);
829         }
830       }
831     }
832   }
833 }
834
835 static void foreach_mouse_hit_key(PEData *data, ForHitKeyMatFunc func, int selected)
836 {
837   PTCacheEdit *edit = data->edit;
838   ParticleEditSettings *pset = PE_settings(data->scene);
839   /* all is selected in path mode */
840   if (pset->selectmode == SCE_SELECT_PATH) {
841     selected = 0;
842   }
843
844   KeyIterData iter_data;
845   iter_data.data = data;
846   iter_data.edit = edit;
847   iter_data.selected = selected;
848   iter_data.func = func;
849
850   TaskParallelSettings settings;
851   BLI_parallel_range_settings_defaults(&settings);
852   settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
853   BLI_task_parallel_range(0, edit->totpoint, &iter_data, foreach_mouse_hit_key_iter, &settings);
854 }
855
856 static void foreach_selected_point(PEData *data, ForPointFunc func)
857 {
858   PTCacheEdit *edit = data->edit;
859   POINT_P;
860
861   LOOP_SELECTED_POINTS {
862     func(data, p);
863   }
864 }
865
866 static void foreach_selected_key(PEData *data, ForKeyFunc func)
867 {
868   PTCacheEdit *edit = data->edit;
869   POINT_P;
870   KEY_K;
871
872   LOOP_VISIBLE_POINTS {
873     LOOP_SELECTED_KEYS {
874       func(data, p, k, true);
875     }
876   }
877 }
878
879 static void foreach_point(PEData *data, ForPointFunc func)
880 {
881   PTCacheEdit *edit = data->edit;
882   POINT_P;
883
884   LOOP_POINTS {
885     func(data, p);
886   }
887 }
888
889 static int count_selected_keys(Scene *scene, PTCacheEdit *edit)
890 {
891   ParticleEditSettings *pset = PE_settings(scene);
892   POINT_P;
893   KEY_K;
894   int sel = 0;
895
896   LOOP_VISIBLE_POINTS {
897     if (pset->selectmode == SCE_SELECT_POINT) {
898       LOOP_SELECTED_KEYS {
899         sel++;
900       }
901     }
902     else if (pset->selectmode == SCE_SELECT_END) {
903       if (point->totkey) {
904         key = point->keys + point->totkey - 1;
905         if (key->flag & PEK_SELECT) {
906           sel++;
907         }
908       }
909     }
910   }
911
912   return sel;
913 }
914
915 /************************************************/
916 /*          Particle Edit Mirroring             */
917 /************************************************/
918
919 static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
920 {
921   PTCacheEdit *edit;
922   ParticleSystemModifierData *psmd_eval;
923   KDTree_3d *tree;
924   KDTreeNearest_3d nearest;
925   HairKey *key;
926   PARTICLE_P;
927   float mat[4][4], co[3];
928   int index, totpart;
929
930   edit = psys->edit;
931   psmd_eval = edit->psmd_eval;
932   totpart = psys->totpart;
933
934   if (!psmd_eval->mesh_final) {
935     return;
936   }
937
938   tree = BLI_kdtree_3d_new(totpart);
939
940   /* insert particles into kd tree */
941   LOOP_PARTICLES
942   {
943     key = pa->hair;
944     psys_mat_hair_to_orco(ob, psmd_eval->mesh_final, psys->part->from, pa, mat);
945     copy_v3_v3(co, key->co);
946     mul_m4_v3(mat, co);
947     BLI_kdtree_3d_insert(tree, p, co);
948   }
949
950   BLI_kdtree_3d_balance(tree);
951
952   /* lookup particles and set in mirror cache */
953   if (!edit->mirror_cache) {
954     edit->mirror_cache = MEM_callocN(sizeof(int) * totpart, "PE mirror cache");
955   }
956
957   LOOP_PARTICLES
958   {
959     key = pa->hair;
960     psys_mat_hair_to_orco(ob, psmd_eval->mesh_final, psys->part->from, pa, mat);
961     copy_v3_v3(co, key->co);
962     mul_m4_v3(mat, co);
963     co[0] = -co[0];
964
965     index = BLI_kdtree_3d_find_nearest(tree, co, &nearest);
966
967     /* this needs a custom threshold still, duplicated for editmode mirror */
968     if (index != -1 && index != p && (nearest.dist <= 0.0002f)) {
969       edit->mirror_cache[p] = index;
970     }
971     else {
972       edit->mirror_cache[p] = -1;
973     }
974   }
975
976   /* make sure mirrors are in two directions */
977   LOOP_PARTICLES
978   {
979     if (edit->mirror_cache[p]) {
980       index = edit->mirror_cache[p];
981       if (edit->mirror_cache[index] != p) {
982         edit->mirror_cache[p] = -1;
983       }
984     }
985   }
986
987   BLI_kdtree_3d_free(tree);
988 }
989
990 static void PE_mirror_particle(
991     Object *ob, Mesh *mesh, ParticleSystem *psys, ParticleData *pa, ParticleData *mpa)
992 {
993   HairKey *hkey, *mhkey;
994   PTCacheEditPoint *point, *mpoint;
995   PTCacheEditKey *key, *mkey;
996   PTCacheEdit *edit;
997   float mat[4][4], mmat[4][4], immat[4][4];
998   int i, mi, k;
999
1000   edit = psys->edit;
1001   i = pa - psys->particles;
1002
1003   /* find mirrored particle if needed */
1004   if (!mpa) {
1005     if (!edit->mirror_cache) {
1006       PE_update_mirror_cache(ob, psys);
1007     }
1008
1009     if (!edit->mirror_cache) {
1010       return; /* something went wrong! */
1011     }
1012
1013     mi = edit->mirror_cache[i];
1014     if (mi == -1) {
1015       return;
1016     }
1017     mpa = psys->particles + mi;
1018   }
1019   else {
1020     mi = mpa - psys->particles;
1021   }
1022
1023   point = edit->points + i;
1024   mpoint = edit->points + mi;
1025
1026   /* make sure they have the same amount of keys */
1027   if (pa->totkey != mpa->totkey) {
1028     if (mpa->hair) {
1029       MEM_freeN(mpa->hair);
1030     }
1031     if (mpoint->keys) {
1032       MEM_freeN(mpoint->keys);
1033     }
1034
1035     mpa->hair = MEM_dupallocN(pa->hair);
1036     mpa->totkey = pa->totkey;
1037     mpoint->keys = MEM_dupallocN(point->keys);
1038     mpoint->totkey = point->totkey;
1039
1040     mhkey = mpa->hair;
1041     mkey = mpoint->keys;
1042     for (k = 0; k < mpa->totkey; k++, mkey++, mhkey++) {
1043       mkey->co = mhkey->co;
1044       mkey->time = &mhkey->time;
1045       mkey->flag &= ~PEK_SELECT;
1046     }
1047   }
1048
1049   /* mirror positions and tags */
1050   psys_mat_hair_to_orco(ob, mesh, psys->part->from, pa, mat);
1051   psys_mat_hair_to_orco(ob, mesh, psys->part->from, mpa, mmat);
1052   invert_m4_m4(immat, mmat);
1053
1054   hkey = pa->hair;
1055   mhkey = mpa->hair;
1056   key = point->keys;
1057   mkey = mpoint->keys;
1058   for (k = 0; k < pa->totkey; k++, hkey++, mhkey++, key++, mkey++) {
1059     copy_v3_v3(mhkey->co, hkey->co);
1060     mul_m4_v3(mat, mhkey->co);
1061     mhkey->co[0] = -mhkey->co[0];
1062     mul_m4_v3(immat, mhkey->co);
1063
1064     if (key->flag & PEK_TAG) {
1065       mkey->flag |= PEK_TAG;
1066     }
1067
1068     mkey->length = key->length;
1069   }
1070
1071   if (point->flag & PEP_TAG) {
1072     mpoint->flag |= PEP_TAG;
1073   }
1074   if (point->flag & PEP_EDIT_RECALC) {
1075     mpoint->flag |= PEP_EDIT_RECALC;
1076   }
1077 }
1078
1079 static void PE_apply_mirror(Object *ob, ParticleSystem *psys)
1080 {
1081   PTCacheEdit *edit;
1082   ParticleSystemModifierData *psmd_eval;
1083   POINT_P;
1084
1085   if (!psys) {
1086     return;
1087   }
1088
1089   edit = psys->edit;
1090   psmd_eval = edit->psmd_eval;
1091
1092   if (psmd_eval == NULL || psmd_eval->mesh_final == NULL) {
1093     return;
1094   }
1095
1096   if (!edit->mirror_cache) {
1097     PE_update_mirror_cache(ob, psys);
1098   }
1099
1100   if (!edit->mirror_cache) {
1101     return; /* something went wrong */
1102   }
1103
1104   /* we delay settings the PARS_EDIT_RECALC for mirrored particles
1105    * to avoid doing mirror twice */
1106   LOOP_POINTS {
1107     if (point->flag & PEP_EDIT_RECALC) {
1108       PE_mirror_particle(ob, psmd_eval->mesh_final, psys, psys->particles + p, NULL);
1109
1110       if (edit->mirror_cache[p] != -1) {
1111         edit->points[edit->mirror_cache[p]].flag &= ~PEP_EDIT_RECALC;
1112       }
1113     }
1114   }
1115
1116   LOOP_POINTS {
1117     if (point->flag & PEP_EDIT_RECALC) {
1118       if (edit->mirror_cache[p] != -1) {
1119         edit->points[edit->mirror_cache[p]].flag |= PEP_EDIT_RECALC;
1120       }
1121     }
1122   }
1123 }
1124
1125 /************************************************/
1126 /*          Edit Calculation                    */
1127 /************************************************/
1128
1129 typedef struct DeflectEmitterIter {
1130   Object *object;
1131   ParticleSystem *psys;
1132   PTCacheEdit *edit;
1133   float dist;
1134   float emitterdist;
1135 } DeflectEmitterIter;
1136
1137 static void deflect_emitter_iter(void *__restrict iter_data_v,
1138                                  const int iter,
1139                                  const TaskParallelTLS *__restrict UNUSED(tls))
1140 {
1141   DeflectEmitterIter *iter_data = (DeflectEmitterIter *)iter_data_v;
1142   PTCacheEdit *edit = iter_data->edit;
1143   PTCacheEditPoint *point = &edit->points[iter];
1144   if ((point->flag & PEP_EDIT_RECALC) == 0) {
1145     return;
1146   }
1147   Object *object = iter_data->object;
1148   ParticleSystem *psys = iter_data->psys;
1149   ParticleSystemModifierData *psmd_eval = iter_data->edit->psmd_eval;
1150   PTCacheEditKey *key;
1151   int k;
1152   float hairimat[4][4], hairmat[4][4];
1153   int index;
1154   float *vec, *nor, dvec[3], dot, dist_1st = 0.0f;
1155   const float dist = iter_data->dist;
1156   const float emitterdist = iter_data->emitterdist;
1157   psys_mat_hair_to_object(
1158       object, psmd_eval->mesh_final, psys->part->from, psys->particles + iter, hairmat);
1159
1160   LOOP_KEYS {
1161     mul_m4_v3(hairmat, key->co);
1162   }
1163
1164   LOOP_KEYS {
1165     if (k == 0) {
1166       dist_1st = len_v3v3((key + 1)->co, key->co);
1167       dist_1st *= dist * emitterdist;
1168     }
1169     else {
1170       index = BLI_kdtree_3d_find_nearest(edit->emitter_field, key->co, NULL);
1171
1172       vec = edit->emitter_cosnos + index * 6;
1173       nor = vec + 3;
1174
1175       sub_v3_v3v3(dvec, key->co, vec);
1176
1177       dot = dot_v3v3(dvec, nor);
1178       copy_v3_v3(dvec, nor);
1179
1180       if (dot > 0.0f) {
1181         if (dot < dist_1st) {
1182           normalize_v3(dvec);
1183           mul_v3_fl(dvec, dist_1st - dot);
1184           add_v3_v3(key->co, dvec);
1185         }
1186       }
1187       else {
1188         normalize_v3(dvec);
1189         mul_v3_fl(dvec, dist_1st - dot);
1190         add_v3_v3(key->co, dvec);
1191       }
1192       if (k == 1) {
1193         dist_1st *= 1.3333f;
1194       }
1195     }
1196   }
1197
1198   invert_m4_m4(hairimat, hairmat);
1199
1200   LOOP_KEYS {
1201     mul_m4_v3(hairimat, key->co);
1202   }
1203 }
1204
1205 /* tries to stop edited particles from going through the emitter's surface */
1206 static void pe_deflect_emitter(Scene *scene, Object *ob, PTCacheEdit *edit)
1207 {
1208   ParticleEditSettings *pset = PE_settings(scene);
1209   ParticleSystem *psys;
1210   const float dist = ED_view3d_select_dist_px() * 0.01f;
1211
1212   if (edit == NULL || edit->psys == NULL || (pset->flag & PE_DEFLECT_EMITTER) == 0 ||
1213       (edit->psys->flag & PSYS_GLOBAL_HAIR)) {
1214     return;
1215   }
1216
1217   psys = edit->psys;
1218
1219   if (edit->psmd_eval == NULL || edit->psmd_eval->mesh_final == NULL) {
1220     return;
1221   }
1222
1223   DeflectEmitterIter iter_data;
1224   iter_data.object = ob;
1225   iter_data.psys = psys;
1226   iter_data.edit = edit;
1227   iter_data.dist = dist;
1228   iter_data.emitterdist = pset->emitterdist;
1229
1230   TaskParallelSettings settings;
1231   BLI_parallel_range_settings_defaults(&settings);
1232   settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
1233   BLI_task_parallel_range(0, edit->totpoint, &iter_data, deflect_emitter_iter, &settings);
1234 }
1235
1236 typedef struct ApplyLengthsIterData {
1237   PTCacheEdit *edit;
1238 } ApplyLengthsIterData;
1239
1240 static void apply_lengths_iter(void *__restrict iter_data_v,
1241                                const int iter,
1242                                const TaskParallelTLS *__restrict UNUSED(tls))
1243 {
1244   ApplyLengthsIterData *iter_data = (ApplyLengthsIterData *)iter_data_v;
1245   PTCacheEdit *edit = iter_data->edit;
1246   PTCacheEditPoint *point = &edit->points[iter];
1247   if ((point->flag & PEP_EDIT_RECALC) == 0) {
1248     return;
1249   }
1250   PTCacheEditKey *key;
1251   int k;
1252   LOOP_KEYS {
1253     if (k) {
1254       float dv1[3];
1255       sub_v3_v3v3(dv1, key->co, (key - 1)->co);
1256       normalize_v3(dv1);
1257       mul_v3_fl(dv1, (key - 1)->length);
1258       add_v3_v3v3(key->co, (key - 1)->co, dv1);
1259     }
1260   }
1261 }
1262
1263 /* force set distances between neighboring keys */
1264 static void PE_apply_lengths(Scene *scene, PTCacheEdit *edit)
1265 {
1266   ParticleEditSettings *pset = PE_settings(scene);
1267
1268   if (edit == 0 || (pset->flag & PE_KEEP_LENGTHS) == 0) {
1269     return;
1270   }
1271
1272   if (edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR) {
1273     return;
1274   }
1275
1276   ApplyLengthsIterData iter_data;
1277   iter_data.edit = edit;
1278
1279   TaskParallelSettings settings;
1280   BLI_parallel_range_settings_defaults(&settings);
1281   settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
1282   BLI_task_parallel_range(0, edit->totpoint, &iter_data, apply_lengths_iter, &settings);
1283 }
1284
1285 typedef struct IterateLengthsIterData {
1286   PTCacheEdit *edit;
1287   ParticleEditSettings *pset;
1288 } IterateLengthsIterData;
1289
1290 static void iterate_lengths_iter(void *__restrict iter_data_v,
1291                                  const int iter,
1292                                  const TaskParallelTLS *__restrict UNUSED(tls))
1293 {
1294   IterateLengthsIterData *iter_data = (IterateLengthsIterData *)iter_data_v;
1295   PTCacheEdit *edit = iter_data->edit;
1296   PTCacheEditPoint *point = &edit->points[iter];
1297   if ((point->flag & PEP_EDIT_RECALC) == 0) {
1298     return;
1299   }
1300   ParticleEditSettings *pset = iter_data->pset;
1301   float tlen;
1302   float dv0[3] = {0.0f, 0.0f, 0.0f};
1303   float dv1[3] = {0.0f, 0.0f, 0.0f};
1304   float dv2[3] = {0.0f, 0.0f, 0.0f};
1305   for (int j = 1; j < point->totkey; j++) {
1306     PTCacheEditKey *key;
1307     int k;
1308     float mul = 1.0f / (float)point->totkey;
1309     if (pset->flag & PE_LOCK_FIRST) {
1310       key = point->keys + 1;
1311       k = 1;
1312       dv1[0] = dv1[1] = dv1[2] = 0.0;
1313     }
1314     else {
1315       key = point->keys;
1316       k = 0;
1317       dv0[0] = dv0[1] = dv0[2] = 0.0;
1318     }
1319
1320     for (; k < point->totkey; k++, key++) {
1321       if (k) {
1322         sub_v3_v3v3(dv0, (key - 1)->co, key->co);
1323         tlen = normalize_v3(dv0);
1324         mul_v3_fl(dv0, (mul * (tlen - (key - 1)->length)));
1325       }
1326       if (k < point->totkey - 1) {
1327         sub_v3_v3v3(dv2, (key + 1)->co, key->co);
1328         tlen = normalize_v3(dv2);
1329         mul_v3_fl(dv2, mul * (tlen - key->length));
1330       }
1331       if (k) {
1332         add_v3_v3((key - 1)->co, dv1);
1333       }
1334       add_v3_v3v3(dv1, dv0, dv2);
1335     }
1336   }
1337 }
1338
1339 /* try to find a nice solution to keep distances between neighboring keys */
1340 static void pe_iterate_lengths(Scene *scene, PTCacheEdit *edit)
1341 {
1342   ParticleEditSettings *pset = PE_settings(scene);
1343   if (edit == 0 || (pset->flag & PE_KEEP_LENGTHS) == 0) {
1344     return;
1345   }
1346   if (edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR) {
1347     return;
1348   }
1349
1350   IterateLengthsIterData iter_data;
1351   iter_data.edit = edit;
1352   iter_data.pset = pset;
1353
1354   TaskParallelSettings settings;
1355   BLI_parallel_range_settings_defaults(&settings);
1356   settings.scheduling_mode = TASK_SCHEDULING_DYNAMIC;
1357   BLI_task_parallel_range(0, edit->totpoint, &iter_data, iterate_lengths_iter, &settings);
1358 }
1359
1360 /* set current distances to be kept between neighboring keys */
1361 void recalc_lengths(PTCacheEdit *edit)
1362 {
1363   POINT_P;
1364   KEY_K;
1365
1366   if (edit == 0) {
1367     return;
1368   }
1369
1370   LOOP_EDITED_POINTS {
1371     key = point->keys;
1372     for (k = 0; k < point->totkey - 1; k++, key++) {
1373       key->length = len_v3v3(key->co, (key + 1)->co);
1374     }
1375   }
1376 }
1377
1378 /* calculate a tree for finding nearest emitter's vertice */
1379 void recalc_emitter_field(Depsgraph *UNUSED(depsgraph), Object *UNUSED(ob), ParticleSystem *psys)
1380 {
1381   PTCacheEdit *edit = psys->edit;
1382   Mesh *mesh = edit->psmd_eval->mesh_final;
1383   float *vec, *nor;
1384   int i, totface /*, totvert*/;
1385
1386   if (!mesh) {
1387     return;
1388   }
1389
1390   if (edit->emitter_cosnos) {
1391     MEM_freeN(edit->emitter_cosnos);
1392   }
1393
1394   BLI_kdtree_3d_free(edit->emitter_field);
1395
1396   totface = mesh->totface;
1397   /*totvert=dm->getNumVerts(dm);*/ /*UNUSED*/
1398
1399   edit->emitter_cosnos = MEM_callocN(totface * 6 * sizeof(float), "emitter cosnos");
1400
1401   edit->emitter_field = BLI_kdtree_3d_new(totface);
1402
1403   vec = edit->emitter_cosnos;
1404   nor = vec + 3;
1405
1406   for (i = 0; i < totface; i++, vec += 6, nor += 6) {
1407     MFace *mface = &mesh->mface[i];
1408     MVert *mvert;
1409
1410     mvert = &mesh->mvert[mface->v1];
1411     copy_v3_v3(vec, mvert->co);
1412     copy_v3fl_v3s(nor, mvert->no);
1413
1414     mvert = &mesh->mvert[mface->v2];
1415     add_v3_v3v3(vec, vec, mvert->co);
1416     add_v3fl_v3fl_v3s(nor, nor, mvert->no);
1417
1418     mvert = &mesh->mvert[mface->v3];
1419     add_v3_v3v3(vec, vec, mvert->co);
1420     add_v3fl_v3fl_v3s(nor, nor, mvert->no);
1421
1422     if (mface->v4) {
1423       mvert = &mesh->mvert[mface->v4];
1424       add_v3_v3v3(vec, vec, mvert->co);
1425       add_v3fl_v3fl_v3s(nor, nor, mvert->no);
1426
1427       mul_v3_fl(vec, 0.25);
1428     }
1429     else {
1430       mul_v3_fl(vec, 1.0f / 3.0f);
1431     }
1432
1433     normalize_v3(nor);
1434
1435     BLI_kdtree_3d_insert(edit->emitter_field, i, vec);
1436   }
1437
1438   BLI_kdtree_3d_balance(edit->emitter_field);
1439 }
1440
1441 static void PE_update_selection(Depsgraph *depsgraph, Scene *scene, Object *ob, int useflag)
1442 {
1443   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
1444   HairKey *hkey;
1445   POINT_P;
1446   KEY_K;
1447
1448   /* flag all particles to be updated if not using flag */
1449   if (!useflag) {
1450     LOOP_POINTS {
1451       point->flag |= PEP_EDIT_RECALC;
1452     }
1453   }
1454
1455   /* flush edit key flag to hair key flag to preserve selection
1456    * on save */
1457   if (edit->psys) {
1458     LOOP_POINTS {
1459       hkey = edit->psys->particles[p].hair;
1460       LOOP_KEYS {
1461         hkey->editflag = key->flag;
1462         hkey++;
1463       }
1464     }
1465   }
1466
1467   psys_cache_edit_paths(depsgraph, scene, ob, edit, CFRA, G.is_rendering);
1468
1469   /* disable update flag */
1470   LOOP_POINTS {
1471     point->flag &= ~PEP_EDIT_RECALC;
1472   }
1473
1474   DEG_id_tag_update(&ob->id, ID_RECALC_SELECT);
1475 }
1476
1477 void update_world_cos(Object *ob, PTCacheEdit *edit)
1478 {
1479   ParticleSystem *psys = edit->psys;
1480   ParticleSystemModifierData *psmd_eval = edit->psmd_eval;
1481   POINT_P;
1482   KEY_K;
1483   float hairmat[4][4];
1484
1485   if (psys == 0 || psys->edit == 0 || psmd_eval == NULL || psmd_eval->mesh_final == NULL) {
1486     return;
1487   }
1488
1489   LOOP_POINTS {
1490     if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
1491       psys_mat_hair_to_global(
1492           ob, psmd_eval->mesh_final, psys->part->from, psys->particles + p, hairmat);
1493     }
1494
1495     LOOP_KEYS {
1496       copy_v3_v3(key->world_co, key->co);
1497       if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
1498         mul_m4_v3(hairmat, key->world_co);
1499       }
1500     }
1501   }
1502 }
1503 static void update_velocities(PTCacheEdit *edit)
1504 {
1505   /*TODO: get frs_sec properly */
1506   float vec1[3], vec2[3], frs_sec, dfra;
1507   POINT_P;
1508   KEY_K;
1509
1510   /* hair doesn't use velocities */
1511   if (edit->psys || !edit->points || !edit->points->keys->vel) {
1512     return;
1513   }
1514
1515   frs_sec = edit->pid.flag & PTCACHE_VEL_PER_SEC ? 25.0f : 1.0f;
1516
1517   LOOP_EDITED_POINTS {
1518     LOOP_KEYS {
1519       if (k == 0) {
1520         dfra = *(key + 1)->time - *key->time;
1521
1522         if (dfra <= 0.0f) {
1523           continue;
1524         }
1525
1526         sub_v3_v3v3(key->vel, (key + 1)->co, key->co);
1527
1528         if (point->totkey > 2) {
1529           sub_v3_v3v3(vec1, (key + 1)->co, (key + 2)->co);
1530           project_v3_v3v3(vec2, vec1, key->vel);
1531           sub_v3_v3v3(vec2, vec1, vec2);
1532           madd_v3_v3fl(key->vel, vec2, 0.5f);
1533         }
1534       }
1535       else if (k == point->totkey - 1) {
1536         dfra = *key->time - *(key - 1)->time;
1537
1538         if (dfra <= 0.0f) {
1539           continue;
1540         }
1541
1542         sub_v3_v3v3(key->vel, key->co, (key - 1)->co);
1543
1544         if (point->totkey > 2) {
1545           sub_v3_v3v3(vec1, (key - 2)->co, (key - 1)->co);
1546           project_v3_v3v3(vec2, vec1, key->vel);
1547           sub_v3_v3v3(vec2, vec1, vec2);
1548           madd_v3_v3fl(key->vel, vec2, 0.5f);
1549         }
1550       }
1551       else {
1552         dfra = *(key + 1)->time - *(key - 1)->time;
1553
1554         if (dfra <= 0.0f) {
1555           continue;
1556         }
1557
1558         sub_v3_v3v3(key->vel, (key + 1)->co, (key - 1)->co);
1559       }
1560       mul_v3_fl(key->vel, frs_sec / dfra);
1561     }
1562   }
1563 }
1564
1565 void PE_update_object(Depsgraph *depsgraph, Scene *scene, Object *ob, int useflag)
1566 {
1567   /* use this to do partial particle updates, not usable when adding or
1568    * removing, then a full redo is necessary and calling this may crash */
1569   ParticleEditSettings *pset = PE_settings(scene);
1570   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
1571   POINT_P;
1572
1573   if (!edit) {
1574     return;
1575   }
1576
1577   /* flag all particles to be updated if not using flag */
1578   if (!useflag) {
1579     LOOP_POINTS {
1580       point->flag |= PEP_EDIT_RECALC;
1581     }
1582   }
1583
1584   /* do post process on particle edit keys */
1585   pe_iterate_lengths(scene, edit);
1586   pe_deflect_emitter(scene, ob, edit);
1587   PE_apply_lengths(scene, edit);
1588   if (pe_x_mirror(ob)) {
1589     PE_apply_mirror(ob, edit->psys);
1590   }
1591   if (edit->psys) {
1592     update_world_cos(ob, edit);
1593   }
1594   if (pset->flag & PE_AUTO_VELOCITY) {
1595     update_velocities(edit);
1596   }
1597
1598   /* Only do this for emitter particles because drawing PE_FADE_TIME is not respected in 2.8 yet
1599    * and flagging with PEK_HIDE will prevent selection. This might get restored once this is
1600    * supported in drawing (but doesn't make much sense for hair anyways). */
1601   if (edit->psys->part->type == PART_EMITTER) {
1602     PE_hide_keys_time(scene, edit, CFRA);
1603   }
1604
1605   /* regenerate path caches */
1606   psys_cache_edit_paths(depsgraph, scene, ob, edit, CFRA, G.is_rendering);
1607
1608   /* disable update flag */
1609   LOOP_POINTS {
1610     point->flag &= ~PEP_EDIT_RECALC;
1611   }
1612
1613   if (edit->psys) {
1614     edit->psys->flag &= ~PSYS_HAIR_UPDATED;
1615   }
1616 }
1617
1618 /************************************************/
1619 /*          Edit Selections                     */
1620 /************************************************/
1621
1622 /*-----selection callbacks-----*/
1623
1624 static void select_key(PEData *data, int point_index, int key_index, bool UNUSED(is_inside))
1625 {
1626   PTCacheEdit *edit = data->edit;
1627   PTCacheEditPoint *point = edit->points + point_index;
1628   PTCacheEditKey *key = point->keys + key_index;
1629
1630   if (data->select) {
1631     key->flag |= PEK_SELECT;
1632   }
1633   else {
1634     key->flag &= ~PEK_SELECT;
1635   }
1636
1637   point->flag |= PEP_EDIT_RECALC;
1638   data->is_changed = true;
1639 }
1640
1641 static void select_key_op(PEData *data, int point_index, int key_index, bool is_inside)
1642 {
1643   PTCacheEdit *edit = data->edit;
1644   PTCacheEditPoint *point = edit->points + point_index;
1645   PTCacheEditKey *key = point->keys + key_index;
1646   const bool is_select = key->flag & PEK_SELECT;
1647   const int sel_op_result = ED_select_op_action_deselected(data->sel_op, is_select, is_inside);
1648   if (sel_op_result != -1) {
1649     SET_FLAG_FROM_TEST(key->flag, sel_op_result, PEK_SELECT);
1650     point->flag |= PEP_EDIT_RECALC;
1651     data->is_changed = true;
1652   }
1653 }
1654
1655 static void select_keys(PEData *data,
1656                         int point_index,
1657                         int UNUSED(key_index),
1658                         bool UNUSED(is_inside))
1659 {
1660   PTCacheEdit *edit = data->edit;
1661   PTCacheEditPoint *point = edit->points + point_index;
1662   KEY_K;
1663
1664   LOOP_KEYS {
1665     if (data->select) {
1666       key->flag |= PEK_SELECT;
1667     }
1668     else {
1669       key->flag &= ~PEK_SELECT;
1670     }
1671   }
1672
1673   point->flag |= PEP_EDIT_RECALC;
1674 }
1675
1676 static void extend_key_select(PEData *data, int point_index, int key_index, bool UNUSED(is_inside))
1677 {
1678   PTCacheEdit *edit = data->edit;
1679   PTCacheEditPoint *point = edit->points + point_index;
1680   PTCacheEditKey *key = point->keys + key_index;
1681
1682   if ((key->flag & PEK_SELECT) == 0) {
1683     key->flag |= PEK_SELECT;
1684     point->flag |= PEP_EDIT_RECALC;
1685     data->is_changed = true;
1686   }
1687 }
1688
1689 static void deselect_key_select(PEData *data,
1690                                 int point_index,
1691                                 int key_index,
1692                                 bool UNUSED(is_inside))
1693 {
1694   PTCacheEdit *edit = data->edit;
1695   PTCacheEditPoint *point = edit->points + point_index;
1696   PTCacheEditKey *key = point->keys + key_index;
1697
1698   if ((key->flag & PEK_SELECT) != 0) {
1699     key->flag &= ~PEK_SELECT;
1700     point->flag |= PEP_EDIT_RECALC;
1701     data->is_changed = true;
1702   }
1703 }
1704
1705 static void toggle_key_select(PEData *data, int point_index, int key_index, bool UNUSED(is_inside))
1706 {
1707   PTCacheEdit *edit = data->edit;
1708   PTCacheEditPoint *point = edit->points + point_index;
1709   PTCacheEditKey *key = point->keys + key_index;
1710
1711   key->flag ^= PEK_SELECT;
1712   point->flag |= PEP_EDIT_RECALC;
1713   data->is_changed = true;
1714 }
1715
1716 /************************ de select all operator ************************/
1717
1718 static bool select_action_apply(PTCacheEditPoint *point, PTCacheEditKey *key, int action)
1719 {
1720   bool changed = false;
1721   switch (action) {
1722     case SEL_SELECT:
1723       if ((key->flag & PEK_SELECT) == 0) {
1724         key->flag |= PEK_SELECT;
1725         point->flag |= PEP_EDIT_RECALC;
1726         changed = true;
1727       }
1728       break;
1729     case SEL_DESELECT:
1730       if (key->flag & PEK_SELECT) {
1731         key->flag &= ~PEK_SELECT;
1732         point->flag |= PEP_EDIT_RECALC;
1733         changed = true;
1734       }
1735       break;
1736     case SEL_INVERT:
1737       if ((key->flag & PEK_SELECT) == 0) {
1738         key->flag |= PEK_SELECT;
1739         point->flag |= PEP_EDIT_RECALC;
1740         changed = true;
1741       }
1742       else {
1743         key->flag &= ~PEK_SELECT;
1744         point->flag |= PEP_EDIT_RECALC;
1745         changed = true;
1746       }
1747       break;
1748   }
1749   return changed;
1750 }
1751
1752 static int pe_select_all_exec(bContext *C, wmOperator *op)
1753 {
1754   Scene *scene = CTX_data_scene(C);
1755   Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
1756   Object *ob = CTX_data_active_object(C);
1757   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
1758   POINT_P;
1759   KEY_K;
1760   int action = RNA_enum_get(op->ptr, "action");
1761
1762   if (action == SEL_TOGGLE) {
1763     action = SEL_SELECT;
1764     LOOP_VISIBLE_POINTS {
1765       LOOP_SELECTED_KEYS {
1766         action = SEL_DESELECT;
1767         break;
1768       }
1769
1770       if (action == SEL_DESELECT) {
1771         break;
1772       }
1773     }
1774   }
1775
1776   bool changed = false;
1777   LOOP_VISIBLE_POINTS {
1778     LOOP_VISIBLE_KEYS {
1779       changed |= select_action_apply(point, key, action);
1780     }
1781   }
1782
1783   if (changed) {
1784     PE_update_selection(depsgraph, scene, ob, 1);
1785     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, ob);
1786   }
1787   return OPERATOR_FINISHED;
1788 }
1789
1790 void PARTICLE_OT_select_all(wmOperatorType *ot)
1791 {
1792   /* identifiers */
1793   ot->name = "(De)select All";
1794   ot->idname = "PARTICLE_OT_select_all";
1795   ot->description = "(De)select all particles' keys";
1796
1797   /* api callbacks */
1798   ot->exec = pe_select_all_exec;
1799   ot->poll = PE_poll;
1800
1801   /* flags */
1802   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1803
1804   WM_operator_properties_select_all(ot);
1805 }
1806
1807 /************************ pick select operator ************************/
1808
1809 bool PE_mouse_particles(bContext *C, const int mval[2], bool extend, bool deselect, bool toggle)
1810 {
1811   PEData data;
1812   Scene *scene = CTX_data_scene(C);
1813   Object *ob = CTX_data_active_object(C);
1814   PTCacheEdit *edit = PE_get_current(data.depsgraph, scene, ob);
1815   POINT_P;
1816   KEY_K;
1817
1818   if (!PE_start_edit(edit)) {
1819     return false;
1820   }
1821
1822   if (!extend && !deselect && !toggle) {
1823     LOOP_VISIBLE_POINTS {
1824       LOOP_SELECTED_KEYS {
1825         key->flag &= ~PEK_SELECT;
1826         point->flag |= PEP_EDIT_RECALC;
1827       }
1828     }
1829   }
1830
1831   PE_set_view3d_data(C, &data);
1832   data.mval = mval;
1833   data.rad = ED_view3d_select_dist_px();
1834
1835   /* 1 = nearest only */
1836   if (extend) {
1837     for_mouse_hit_keys(&data, extend_key_select, PSEL_NEAREST);
1838   }
1839   else if (deselect) {
1840     for_mouse_hit_keys(&data, deselect_key_select, PSEL_NEAREST);
1841   }
1842   else {
1843     for_mouse_hit_keys(&data, toggle_key_select, PSEL_NEAREST);
1844   }
1845
1846   if (data.is_changed) {
1847     PE_update_selection(data.depsgraph, scene, ob, 1);
1848     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
1849   }
1850
1851   return true;
1852 }
1853
1854 /************************ select root operator ************************/
1855
1856 static void select_root(PEData *data, int point_index)
1857 {
1858   PTCacheEditPoint *point = data->edit->points + point_index;
1859   PTCacheEditKey *key = point->keys;
1860
1861   if (point->flag & PEP_HIDE) {
1862     return;
1863   }
1864
1865   if (data->select_action != SEL_TOGGLE) {
1866     data->is_changed = select_action_apply(point, key, data->select_action);
1867   }
1868   else if (key->flag & PEK_SELECT) {
1869     data->select_toggle_action = SEL_DESELECT;
1870   }
1871 }
1872
1873 static int select_roots_exec(bContext *C, wmOperator *op)
1874 {
1875   PEData data;
1876   int action = RNA_enum_get(op->ptr, "action");
1877
1878   PE_set_data(C, &data);
1879
1880   if (action == SEL_TOGGLE) {
1881     data.select_action = SEL_TOGGLE;
1882     data.select_toggle_action = SEL_SELECT;
1883
1884     foreach_point(&data, select_root);
1885
1886     action = data.select_toggle_action;
1887   }
1888
1889   data.select_action = action;
1890   foreach_point(&data, select_root);
1891
1892   if (data.is_changed) {
1893     PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
1894     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
1895   }
1896   return OPERATOR_FINISHED;
1897 }
1898
1899 void PARTICLE_OT_select_roots(wmOperatorType *ot)
1900 {
1901   /* identifiers */
1902   ot->name = "Select Roots";
1903   ot->idname = "PARTICLE_OT_select_roots";
1904   ot->description = "Select roots of all visible particles";
1905
1906   /* api callbacks */
1907   ot->exec = select_roots_exec;
1908   ot->poll = PE_poll;
1909
1910   /* flags */
1911   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1912
1913   /* properties */
1914   WM_operator_properties_select_action(ot, SEL_SELECT, false);
1915 }
1916
1917 /************************ select tip operator ************************/
1918
1919 static void select_tip(PEData *data, int point_index)
1920 {
1921   PTCacheEditPoint *point = data->edit->points + point_index;
1922   PTCacheEditKey *key;
1923
1924   if (point->totkey == 0) {
1925     return;
1926   }
1927
1928   key = &point->keys[point->totkey - 1];
1929
1930   if (point->flag & PEP_HIDE) {
1931     return;
1932   }
1933
1934   if (data->select_action != SEL_TOGGLE) {
1935     data->is_changed = select_action_apply(point, key, data->select_action);
1936   }
1937   else if (key->flag & PEK_SELECT) {
1938     data->select_toggle_action = SEL_DESELECT;
1939   }
1940 }
1941
1942 static int select_tips_exec(bContext *C, wmOperator *op)
1943 {
1944   PEData data;
1945   int action = RNA_enum_get(op->ptr, "action");
1946
1947   PE_set_data(C, &data);
1948
1949   if (action == SEL_TOGGLE) {
1950     data.select_action = SEL_TOGGLE;
1951     data.select_toggle_action = SEL_SELECT;
1952
1953     foreach_point(&data, select_tip);
1954
1955     action = data.select_toggle_action;
1956   }
1957
1958   data.select_action = action;
1959   foreach_point(&data, select_tip);
1960
1961   if (data.is_changed) {
1962     PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
1963     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
1964
1965     return OPERATOR_FINISHED;
1966   }
1967   return OPERATOR_CANCELLED;
1968 }
1969
1970 void PARTICLE_OT_select_tips(wmOperatorType *ot)
1971 {
1972   /* identifiers */
1973   ot->name = "Select Tips";
1974   ot->idname = "PARTICLE_OT_select_tips";
1975   ot->description = "Select tips of all visible particles";
1976
1977   /* api callbacks */
1978   ot->exec = select_tips_exec;
1979   ot->poll = PE_poll;
1980
1981   /* flags */
1982   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1983
1984   /* properties */
1985   WM_operator_properties_select_action(ot, SEL_SELECT, false);
1986 }
1987
1988 /*********************** select random operator ************************/
1989
1990 enum { RAN_HAIR, RAN_POINTS };
1991
1992 static const EnumPropertyItem select_random_type_items[] = {
1993     {RAN_HAIR, "HAIR", 0, "Hair", ""},
1994     {RAN_POINTS, "POINTS", 0, "Points", ""},
1995     {0, NULL, 0, NULL, NULL},
1996 };
1997
1998 static int select_random_exec(bContext *C, wmOperator *op)
1999 {
2000   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
2001   PEData data;
2002   int type;
2003
2004   /* used by LOOP_VISIBLE_POINTS, LOOP_VISIBLE_KEYS and LOOP_KEYS */
2005   PTCacheEdit *edit;
2006   PTCacheEditPoint *point;
2007   PTCacheEditKey *key;
2008   int p;
2009   int k;
2010
2011   const float randfac = RNA_float_get(op->ptr, "percent") / 100.0f;
2012   const int seed = WM_operator_properties_select_random_seed_increment_get(op);
2013   const bool select = (RNA_enum_get(op->ptr, "action") == SEL_SELECT);
2014   RNG *rng;
2015
2016   type = RNA_enum_get(op->ptr, "type");
2017
2018   PE_set_data(C, &data);
2019   data.select_action = SEL_SELECT;
2020   edit = PE_get_current(depsgraph, data.scene, data.ob);
2021
2022   rng = BLI_rng_new_srandom(seed);
2023
2024   switch (type) {
2025     case RAN_HAIR:
2026       LOOP_VISIBLE_POINTS {
2027         int flag = ((BLI_rng_get_float(rng) < randfac) == select) ? SEL_SELECT : SEL_DESELECT;
2028         LOOP_KEYS {
2029           data.is_changed |= select_action_apply(point, key, flag);
2030         }
2031       }
2032       break;
2033     case RAN_POINTS:
2034       LOOP_VISIBLE_POINTS {
2035         LOOP_VISIBLE_KEYS {
2036           int flag = ((BLI_rng_get_float(rng) < randfac) == select) ? SEL_SELECT : SEL_DESELECT;
2037           data.is_changed |= select_action_apply(point, key, flag);
2038         }
2039       }
2040       break;
2041   }
2042
2043   BLI_rng_free(rng);
2044
2045   if (data.is_changed) {
2046     PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
2047     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
2048   }
2049   return OPERATOR_FINISHED;
2050 }
2051
2052 void PARTICLE_OT_select_random(wmOperatorType *ot)
2053 {
2054   /* identifiers */
2055   ot->name = "Select Random";
2056   ot->idname = "PARTICLE_OT_select_random";
2057   ot->description = "Select a randomly distributed set of hair or points";
2058
2059   /* api callbacks */
2060   ot->exec = select_random_exec;
2061   ot->poll = PE_poll;
2062
2063   /* flags */
2064   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2065
2066   /* properties */
2067   WM_operator_properties_select_random(ot);
2068   ot->prop = RNA_def_enum(ot->srna,
2069                           "type",
2070                           select_random_type_items,
2071                           RAN_HAIR,
2072                           "Type",
2073                           "Select either hair or points");
2074 }
2075
2076 /************************ select linked operator ************************/
2077
2078 static int select_linked_exec(bContext *C, wmOperator *op)
2079 {
2080   PEData data;
2081   int mval[2];
2082   int location[2];
2083
2084   RNA_int_get_array(op->ptr, "location", location);
2085   mval[0] = location[0];
2086   mval[1] = location[1];
2087
2088   PE_set_view3d_data(C, &data);
2089   data.mval = mval;
2090   data.rad = 75.0f;
2091   data.select = !RNA_boolean_get(op->ptr, "deselect");
2092
2093   for_mouse_hit_keys(&data, select_keys, PSEL_NEAREST);
2094   PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
2095   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
2096
2097   return OPERATOR_FINISHED;
2098 }
2099
2100 static int select_linked_invoke(bContext *C, wmOperator *op, const wmEvent *event)
2101 {
2102   RNA_int_set_array(op->ptr, "location", event->mval);
2103   return select_linked_exec(C, op);
2104 }
2105
2106 void PARTICLE_OT_select_linked(wmOperatorType *ot)
2107 {
2108   /* identifiers */
2109   ot->name = "Select Linked";
2110   ot->idname = "PARTICLE_OT_select_linked";
2111   ot->description = "Select nearest particle from mouse pointer";
2112
2113   /* api callbacks */
2114   ot->exec = select_linked_exec;
2115   ot->invoke = select_linked_invoke;
2116   ot->poll = PE_poll_view3d;
2117
2118   /* flags */
2119   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2120
2121   /* properties */
2122   RNA_def_boolean(
2123       ot->srna, "deselect", 0, "Deselect", "Deselect linked keys rather than selecting them");
2124   RNA_def_int_vector(ot->srna, "location", 2, NULL, 0, INT_MAX, "Location", "", 0, 16384);
2125 }
2126
2127 /************************ box select operator ************************/
2128 bool PE_deselect_all_visible_ex(PTCacheEdit *edit)
2129 {
2130   bool changed = false;
2131   POINT_P;
2132   KEY_K;
2133
2134   LOOP_VISIBLE_POINTS {
2135     LOOP_SELECTED_KEYS {
2136       if ((key->flag & PEK_SELECT) != 0) {
2137         key->flag &= ~PEK_SELECT;
2138         point->flag |= PEP_EDIT_RECALC;
2139         changed = true;
2140       }
2141     }
2142   }
2143   return changed;
2144 }
2145
2146 bool PE_deselect_all_visible(bContext *C)
2147 {
2148   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
2149   Scene *scene = CTX_data_scene(C);
2150   Object *ob = CTX_data_active_object(C);
2151   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2152   if (!PE_start_edit(edit)) {
2153     return false;
2154   }
2155   return PE_deselect_all_visible_ex(edit);
2156 }
2157
2158 bool PE_box_select(bContext *C, const rcti *rect, const int sel_op)
2159 {
2160   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
2161   Scene *scene = CTX_data_scene(C);
2162   Object *ob = CTX_data_active_object(C);
2163   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2164   PEData data;
2165
2166   if (!PE_start_edit(edit)) {
2167     return false;
2168   }
2169
2170   PE_set_view3d_data(C, &data);
2171   data.rect = rect;
2172   data.sel_op = sel_op;
2173
2174   if (SEL_OP_USE_PRE_DESELECT(sel_op)) {
2175     data.is_changed = PE_deselect_all_visible_ex(edit);
2176   }
2177
2178   if (BLI_rcti_is_empty(rect)) {
2179     /* pass */
2180   }
2181   else {
2182     for_mouse_hit_keys(&data, select_key_op, PSEL_ALL_KEYS);
2183   }
2184
2185   if (data.is_changed) {
2186     PE_update_selection(data.depsgraph, scene, ob, 1);
2187     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, ob);
2188   }
2189   return data.is_changed;
2190 }
2191
2192 /************************ circle select operator ************************/
2193
2194 bool PE_circle_select(bContext *C, const int sel_op, const int mval[2], float rad)
2195 {
2196   BLI_assert(ELEM(sel_op, SEL_OP_SET, SEL_OP_ADD, SEL_OP_SUB));
2197   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
2198   Scene *scene = CTX_data_scene(C);
2199   Object *ob = CTX_data_active_object(C);
2200   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2201   PEData data;
2202
2203   if (!PE_start_edit(edit)) {
2204     return false;
2205   }
2206
2207   const bool select = (sel_op != SEL_OP_SUB);
2208
2209   PE_set_view3d_data(C, &data);
2210   data.mval = mval;
2211   data.rad = rad;
2212   data.select = select;
2213
2214   if (SEL_OP_USE_PRE_DESELECT(sel_op)) {
2215     data.is_changed = PE_deselect_all_visible_ex(edit);
2216   }
2217   for_mouse_hit_keys(&data, select_key, 0);
2218   if (data.is_changed) {
2219     PE_update_selection(data.depsgraph, scene, ob, 1);
2220     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, ob);
2221   }
2222   return data.is_changed;
2223 }
2224
2225 /************************ lasso select operator ************************/
2226
2227 int PE_lasso_select(bContext *C, const int mcords[][2], const short moves, const int sel_op)
2228 {
2229   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
2230   Scene *scene = CTX_data_scene(C);
2231   Object *ob = CTX_data_active_object(C);
2232   ARegion *ar = CTX_wm_region(C);
2233   ParticleEditSettings *pset = PE_settings(scene);
2234   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2235   ParticleSystem *psys = edit->psys;
2236   ParticleSystemModifierData *psmd_eval = edit->psmd_eval;
2237   POINT_P;
2238   KEY_K;
2239   float co[3], mat[4][4];
2240   int screen_co[2];
2241
2242   PEData data;
2243
2244   unit_m4(mat);
2245
2246   if (!PE_start_edit(edit)) {
2247     return OPERATOR_CANCELLED;
2248   }
2249
2250   /* only for depths */
2251   PE_set_view3d_data(C, &data);
2252
2253   if (SEL_OP_USE_PRE_DESELECT(sel_op)) {
2254     data.is_changed |= PE_deselect_all_visible_ex(edit);
2255   }
2256
2257   LOOP_VISIBLE_POINTS {
2258     if (edit->psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
2259       psys_mat_hair_to_global(
2260           ob, psmd_eval->mesh_final, psys->part->from, psys->particles + p, mat);
2261     }
2262
2263     if (pset->selectmode == SCE_SELECT_POINT) {
2264       LOOP_VISIBLE_KEYS {
2265         copy_v3_v3(co, key->co);
2266         mul_m4_v3(mat, co);
2267         const bool is_select = key->flag & PEK_SELECT;
2268         const bool is_inside =
2269             ((ED_view3d_project_int_global(ar, co, screen_co, V3D_PROJ_TEST_CLIP_WIN) ==
2270               V3D_PROJ_RET_OK) &&
2271              BLI_lasso_is_point_inside(mcords, moves, screen_co[0], screen_co[1], IS_CLIPPED) &&
2272              key_test_depth(&data, co, screen_co));
2273         const int sel_op_result = ED_select_op_action_deselected(sel_op, is_select, is_inside);
2274         if (sel_op_result != -1) {
2275           SET_FLAG_FROM_TEST(key->flag, sel_op_result, PEK_SELECT);
2276           point->flag |= PEP_EDIT_RECALC;
2277           data.is_changed = true;
2278         }
2279       }
2280     }
2281     else if (pset->selectmode == SCE_SELECT_END) {
2282       if (point->totkey) {
2283         key = point->keys + point->totkey - 1;
2284         copy_v3_v3(co, key->co);
2285         mul_m4_v3(mat, co);
2286         const bool is_select = key->flag & PEK_SELECT;
2287         const bool is_inside =
2288             ((ED_view3d_project_int_global(ar, co, screen_co, V3D_PROJ_TEST_CLIP_WIN) ==
2289               V3D_PROJ_RET_OK) &&
2290              BLI_lasso_is_point_inside(mcords, moves, screen_co[0], screen_co[1], IS_CLIPPED) &&
2291              key_test_depth(&data, co, screen_co));
2292         const int sel_op_result = ED_select_op_action_deselected(sel_op, is_select, is_inside);
2293         if (sel_op_result != -1) {
2294           SET_FLAG_FROM_TEST(key->flag, sel_op_result, PEK_SELECT);
2295           point->flag |= PEP_EDIT_RECALC;
2296           data.is_changed = true;
2297         }
2298       }
2299     }
2300   }
2301
2302   if (data.is_changed) {
2303     PE_update_selection(data.depsgraph, scene, ob, 1);
2304     WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, ob);
2305     return OPERATOR_FINISHED;
2306   }
2307   return OPERATOR_CANCELLED;
2308 }
2309
2310 /*************************** hide operator **************************/
2311
2312 static int hide_exec(bContext *C, wmOperator *op)
2313 {
2314   Object *ob = CTX_data_active_object(C);
2315   Scene *scene = CTX_data_scene(C);
2316   Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
2317
2318   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2319   POINT_P;
2320   KEY_K;
2321
2322   if (RNA_boolean_get(op->ptr, "unselected")) {
2323     LOOP_UNSELECTED_POINTS {
2324       point->flag |= PEP_HIDE;
2325       point->flag |= PEP_EDIT_RECALC;
2326
2327       LOOP_KEYS {
2328         key->flag &= ~PEK_SELECT;
2329       }
2330     }
2331   }
2332   else {
2333     LOOP_SELECTED_POINTS {
2334       point->flag |= PEP_HIDE;
2335       point->flag |= PEP_EDIT_RECALC;
2336
2337       LOOP_KEYS {
2338         key->flag &= ~PEK_SELECT;
2339       }
2340     }
2341   }
2342
2343   PE_update_selection(depsgraph, scene, ob, 1);
2344   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, ob);
2345
2346   return OPERATOR_FINISHED;
2347 }
2348
2349 void PARTICLE_OT_hide(wmOperatorType *ot)
2350 {
2351   /* identifiers */
2352   ot->name = "Hide Selected";
2353   ot->idname = "PARTICLE_OT_hide";
2354   ot->description = "Hide selected particles";
2355
2356   /* api callbacks */
2357   ot->exec = hide_exec;
2358   ot->poll = PE_poll;
2359
2360   /* flags */
2361   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2362
2363   /* props */
2364   RNA_def_boolean(ot->srna, "unselected", 0, "Unselected", "Hide unselected rather than selected");
2365 }
2366
2367 /*************************** reveal operator **************************/
2368
2369 static int reveal_exec(bContext *C, wmOperator *op)
2370 {
2371   Object *ob = CTX_data_active_object(C);
2372   Scene *scene = CTX_data_scene(C);
2373   Depsgraph *depsgraph = CTX_data_ensure_evaluated_depsgraph(C);
2374   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2375   const bool select = RNA_boolean_get(op->ptr, "select");
2376   POINT_P;
2377   KEY_K;
2378
2379   LOOP_POINTS {
2380     if (point->flag & PEP_HIDE) {
2381       point->flag &= ~PEP_HIDE;
2382       point->flag |= PEP_EDIT_RECALC;
2383
2384       LOOP_KEYS {
2385         SET_FLAG_FROM_TEST(key->flag, select, PEK_SELECT);
2386       }
2387     }
2388   }
2389
2390   PE_update_selection(depsgraph, scene, ob, 1);
2391   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, ob);
2392
2393   return OPERATOR_FINISHED;
2394 }
2395
2396 void PARTICLE_OT_reveal(wmOperatorType *ot)
2397 {
2398   /* identifiers */
2399   ot->name = "Reveal";
2400   ot->idname = "PARTICLE_OT_reveal";
2401   ot->description = "Show hidden particles";
2402
2403   /* api callbacks */
2404   ot->exec = reveal_exec;
2405   ot->poll = PE_poll;
2406
2407   /* flags */
2408   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2409
2410   /* props */
2411   RNA_def_boolean(ot->srna, "select", true, "Select", "");
2412 }
2413
2414 /************************ select less operator ************************/
2415
2416 static void select_less_keys(PEData *data, int point_index)
2417 {
2418   PTCacheEdit *edit = data->edit;
2419   PTCacheEditPoint *point = edit->points + point_index;
2420   KEY_K;
2421
2422   LOOP_SELECTED_KEYS {
2423     if (k == 0) {
2424       if (((key + 1)->flag & PEK_SELECT) == 0) {
2425         key->flag |= PEK_TAG;
2426       }
2427     }
2428     else if (k == point->totkey - 1) {
2429       if (((key - 1)->flag & PEK_SELECT) == 0) {
2430         key->flag |= PEK_TAG;
2431       }
2432     }
2433     else {
2434       if ((((key - 1)->flag & (key + 1)->flag) & PEK_SELECT) == 0) {
2435         key->flag |= PEK_TAG;
2436       }
2437     }
2438   }
2439
2440   LOOP_KEYS {
2441     if ((key->flag & PEK_TAG) && (key->flag & PEK_SELECT)) {
2442       key->flag &= ~(PEK_TAG | PEK_SELECT);
2443       point->flag |= PEP_EDIT_RECALC; /* redraw selection only */
2444       data->is_changed = true;
2445     }
2446   }
2447 }
2448
2449 static int select_less_exec(bContext *C, wmOperator *UNUSED(op))
2450 {
2451   PEData data;
2452
2453   PE_set_data(C, &data);
2454   foreach_point(&data, select_less_keys);
2455
2456   PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
2457   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
2458
2459   return OPERATOR_FINISHED;
2460 }
2461
2462 void PARTICLE_OT_select_less(wmOperatorType *ot)
2463 {
2464   /* identifiers */
2465   ot->name = "Select Less";
2466   ot->idname = "PARTICLE_OT_select_less";
2467   ot->description = "Deselect boundary selected keys of each particle";
2468
2469   /* api callbacks */
2470   ot->exec = select_less_exec;
2471   ot->poll = PE_poll;
2472
2473   /* flags */
2474   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2475 }
2476
2477 /************************ select more operator ************************/
2478
2479 static void select_more_keys(PEData *data, int point_index)
2480 {
2481   PTCacheEdit *edit = data->edit;
2482   PTCacheEditPoint *point = edit->points + point_index;
2483   KEY_K;
2484
2485   LOOP_KEYS {
2486     if (key->flag & PEK_SELECT) {
2487       continue;
2488     }
2489
2490     if (k == 0) {
2491       if ((key + 1)->flag & PEK_SELECT) {
2492         key->flag |= PEK_TAG;
2493       }
2494     }
2495     else if (k == point->totkey - 1) {
2496       if ((key - 1)->flag & PEK_SELECT) {
2497         key->flag |= PEK_TAG;
2498       }
2499     }
2500     else {
2501       if (((key - 1)->flag | (key + 1)->flag) & PEK_SELECT) {
2502         key->flag |= PEK_TAG;
2503       }
2504     }
2505   }
2506
2507   LOOP_KEYS {
2508     if ((key->flag & PEK_TAG) && (key->flag & PEK_SELECT) == 0) {
2509       key->flag &= ~PEK_TAG;
2510       key->flag |= PEK_SELECT;
2511       point->flag |= PEP_EDIT_RECALC; /* redraw selection only */
2512       data->is_changed = true;
2513     }
2514   }
2515 }
2516
2517 static int select_more_exec(bContext *C, wmOperator *UNUSED(op))
2518 {
2519   PEData data;
2520
2521   PE_set_data(C, &data);
2522   foreach_point(&data, select_more_keys);
2523
2524   PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
2525   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_SELECTED, data.ob);
2526
2527   return OPERATOR_FINISHED;
2528 }
2529
2530 void PARTICLE_OT_select_more(wmOperatorType *ot)
2531 {
2532   /* identifiers */
2533   ot->name = "Select More";
2534   ot->idname = "PARTICLE_OT_select_more";
2535   ot->description = "Select keys linked to boundary selected keys of each particle";
2536
2537   /* api callbacks */
2538   ot->exec = select_more_exec;
2539   ot->poll = PE_poll;
2540
2541   /* flags */
2542   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2543 }
2544
2545 /************************ rekey operator ************************/
2546
2547 static void rekey_particle(PEData *data, int pa_index)
2548 {
2549   PTCacheEdit *edit = data->edit;
2550   ParticleSystem *psys = edit->psys;
2551   ParticleSimulationData sim = {0};
2552   ParticleData *pa = psys->particles + pa_index;
2553   PTCacheEditPoint *point = edit->points + pa_index;
2554   ParticleKey state;
2555   HairKey *key, *new_keys, *okey;
2556   PTCacheEditKey *ekey;
2557   float dval, sta, end;
2558   int k;
2559
2560   sim.depsgraph = data->depsgraph;
2561   sim.scene = data->scene;
2562   sim.ob = data->ob;
2563   sim.psys = edit->psys;
2564
2565   pa->flag |= PARS_REKEY;
2566
2567   key = new_keys = MEM_callocN(data->totrekey * sizeof(HairKey), "Hair re-key keys");
2568
2569   okey = pa->hair;
2570   /* root and tip stay the same */
2571   copy_v3_v3(key->co, okey->co);
2572   copy_v3_v3((key + data->totrekey - 1)->co, (okey + pa->totkey - 1)->co);
2573
2574   sta = key->time = okey->time;
2575   end = (key + data->totrekey - 1)->time = (okey + pa->totkey - 1)->time;
2576   dval = (end - sta) / (float)(data->totrekey - 1);
2577
2578   /* interpolate new keys from old ones */
2579   for (k = 1, key++; k < data->totrekey - 1; k++, key++) {
2580     state.time = (float)k / (float)(data->totrekey - 1);
2581     psys_get_particle_on_path(&sim, pa_index, &state, 0);
2582     copy_v3_v3(key->co, state.co);
2583     key->time = sta + k * dval;
2584   }
2585
2586   /* replace keys */
2587   if (pa->hair) {
2588     MEM_freeN(pa->hair);
2589   }
2590   pa->hair = new_keys;
2591
2592   point->totkey = pa->totkey = data->totrekey;
2593
2594   if (point->keys) {
2595     MEM_freeN(point->keys);
2596   }
2597   ekey = point->keys = MEM_callocN(pa->totkey * sizeof(PTCacheEditKey), "Hair re-key edit keys");
2598
2599   for (k = 0, key = pa->hair; k < pa->totkey; k++, key++, ekey++) {
2600     ekey->co = key->co;
2601     ekey->time = &key->time;
2602     ekey->flag |= PEK_SELECT;
2603     if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
2604       ekey->flag |= PEK_USE_WCO;
2605     }
2606   }
2607
2608   pa->flag &= ~PARS_REKEY;
2609   point->flag |= PEP_EDIT_RECALC;
2610 }
2611
2612 static int rekey_exec(bContext *C, wmOperator *op)
2613 {
2614   PEData data;
2615
2616   PE_set_data(C, &data);
2617
2618   data.dval = 1.0f / (float)(data.totrekey - 1);
2619   data.totrekey = RNA_int_get(op->ptr, "keys_number");
2620
2621   foreach_selected_point(&data, rekey_particle);
2622
2623   recalc_lengths(data.edit);
2624   PE_update_object(data.depsgraph, data.scene, data.ob, 1);
2625   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_EDITED, data.ob);
2626
2627   return OPERATOR_FINISHED;
2628 }
2629
2630 void PARTICLE_OT_rekey(wmOperatorType *ot)
2631 {
2632   /* identifiers */
2633   ot->name = "Rekey";
2634   ot->idname = "PARTICLE_OT_rekey";
2635   ot->description = "Change the number of keys of selected particles (root and tip keys included)";
2636
2637   /* api callbacks */
2638   ot->exec = rekey_exec;
2639   ot->invoke = WM_operator_props_popup;
2640   ot->poll = PE_hair_poll;
2641
2642   /* flags */
2643   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2644
2645   /* properties */
2646   RNA_def_int(ot->srna, "keys_number", 2, 2, INT_MAX, "Number of Keys", "", 2, 100);
2647 }
2648
2649 static void rekey_particle_to_time(
2650     const bContext *C, Scene *scene, Object *ob, int pa_index, float path_time)
2651 {
2652   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
2653   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
2654   ParticleSystem *psys;
2655   ParticleSimulationData sim = {0};
2656   ParticleData *pa;
2657   ParticleKey state;
2658   HairKey *new_keys, *key;
2659   PTCacheEditKey *ekey;
2660   int k;
2661
2662   if (!edit || !edit->psys) {
2663     return;
2664   }
2665
2666   psys = edit->psys;
2667
2668   sim.depsgraph = depsgraph;
2669   sim.scene = scene;
2670   sim.ob = ob;
2671   sim.psys = psys;
2672
2673   pa = psys->particles + pa_index;
2674
2675   pa->flag |= PARS_REKEY;
2676
2677   key = new_keys = MEM_dupallocN(pa->hair);
2678
2679   /* interpolate new keys from old ones (roots stay the same) */
2680   for (k = 1, key++; k < pa->totkey; k++, key++) {
2681     state.time = path_time * (float)k / (float)(pa->totkey - 1);
2682     psys_get_particle_on_path(&sim, pa_index, &state, 0);
2683     copy_v3_v3(key->co, state.co);
2684   }
2685
2686   /* replace hair keys */
2687   if (pa->hair) {
2688     MEM_freeN(pa->hair);
2689   }
2690   pa->hair = new_keys;
2691
2692   /* update edit pointers */
2693   for (k = 0, key = pa->hair, ekey = edit->points[pa_index].keys; k < pa->totkey;
2694        k++, key++, ekey++) {
2695     ekey->co = key->co;
2696     ekey->time = &key->time;
2697   }
2698
2699   pa->flag &= ~PARS_REKEY;
2700 }
2701
2702 /************************* utilities **************************/
2703
2704 static int remove_tagged_particles(Object *ob, ParticleSystem *psys, int mirror)
2705 {
2706   PTCacheEdit *edit = psys->edit;
2707   ParticleData *pa, *npa = 0, *new_pars = 0;
2708   POINT_P;
2709   PTCacheEditPoint *npoint = 0, *new_points = 0;
2710   ParticleSystemModifierData *psmd_eval;
2711   int i, new_totpart = psys->totpart, removed = 0;
2712
2713   if (mirror) {
2714     /* mirror tags */
2715     psmd_eval = edit->psmd_eval;
2716
2717     LOOP_TAGGED_POINTS {
2718       PE_mirror_particle(ob, psmd_eval->mesh_final, psys, psys->particles + p, NULL);
2719     }
2720   }
2721
2722   LOOP_TAGGED_POINTS {
2723     new_totpart--;
2724     removed++;
2725   }
2726
2727   if (new_totpart != psys->totpart) {
2728     if (new_totpart) {
2729       npa = new_pars = MEM_callocN(new_totpart * sizeof(ParticleData), "ParticleData array");
2730       npoint = new_points = MEM_callocN(new_totpart * sizeof(PTCacheEditPoint),
2731                                         "PTCacheEditKey array");
2732
2733       if (ELEM(NULL, new_pars, new_points)) {
2734         /* allocation error! */
2735         if (new_pars) {
2736           MEM_freeN(new_pars);
2737         }
2738         if (new_points) {
2739           MEM_freeN(new_points);
2740         }
2741         return 0;
2742       }
2743     }
2744
2745     pa = psys->particles;
2746     point = edit->points;
2747     for (i = 0; i < psys->totpart; i++, pa++, point++) {
2748       if (point->flag & PEP_TAG) {
2749         if (point->keys) {
2750           MEM_freeN(point->keys);
2751         }
2752         if (pa->hair) {
2753           MEM_freeN(pa->hair);
2754         }
2755       }
2756       else {
2757         memcpy(npa, pa, sizeof(ParticleData));
2758         memcpy(npoint, point, sizeof(PTCacheEditPoint));
2759         npa++;
2760         npoint++;
2761       }
2762     }
2763
2764     if (psys->particles) {
2765       MEM_freeN(psys->particles);
2766     }
2767     psys->particles = new_pars;
2768
2769     if (edit->points) {
2770       MEM_freeN(edit->points);
2771     }
2772     edit->points = new_points;
2773
2774     if (edit->mirror_cache) {
2775       MEM_freeN(edit->mirror_cache);
2776       edit->mirror_cache = NULL;
2777     }
2778
2779     if (psys->child) {
2780       MEM_freeN(psys->child);
2781       psys->child = NULL;
2782       psys->totchild = 0;
2783     }
2784
2785     edit->totpoint = psys->totpart = new_totpart;
2786   }
2787
2788   return removed;
2789 }
2790
2791 static void remove_tagged_keys(Depsgraph *depsgraph, Object *ob, ParticleSystem *psys)
2792 {
2793   PTCacheEdit *edit = psys->edit;
2794   ParticleData *pa;
2795   HairKey *hkey, *nhkey, *new_hkeys = 0;
2796   POINT_P;
2797   KEY_K;
2798   PTCacheEditKey *nkey, *new_keys;
2799   short new_totkey;
2800
2801   if (pe_x_mirror(ob)) {
2802     /* mirror key tags */
2803     ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
2804     ParticleSystemModifierData *psmd_eval = (ParticleSystemModifierData *)modifier_get_evaluated(
2805         depsgraph, ob, &psmd->modifier);
2806
2807     LOOP_POINTS {
2808       LOOP_TAGGED_KEYS {
2809         PE_mirror_particle(ob, psmd_eval->mesh_final, psys, psys->particles + p, NULL);
2810         break;
2811       }
2812     }
2813   }
2814
2815   LOOP_POINTS {
2816     new_totkey = point->totkey;
2817     LOOP_TAGGED_KEYS {
2818       new_totkey--;
2819     }
2820     /* we can't have elements with less than two keys*/
2821     if (new_totkey < 2) {
2822       point->flag |= PEP_TAG;
2823     }
2824   }
2825   remove_tagged_particles(ob, psys, pe_x_mirror(ob));
2826
2827   LOOP_POINTS {
2828     pa = psys->particles + p;
2829     new_totkey = pa->totkey;
2830
2831     LOOP_TAGGED_KEYS {
2832       new_totkey--;
2833     }
2834
2835     if (new_totkey != pa->totkey) {
2836       nhkey = new_hkeys = MEM_callocN(new_totkey * sizeof(HairKey), "HairKeys");
2837       nkey = new_keys = MEM_callocN(new_totkey * sizeof(PTCacheEditKey), "particle edit keys");
2838
2839       hkey = pa->hair;
2840       LOOP_KEYS {
2841         while (key->flag & PEK_TAG && hkey < pa->hair + pa->totkey) {
2842           key++;
2843           hkey++;
2844         }
2845
2846         if (hkey < pa->hair + pa->totkey) {
2847           copy_v3_v3(nhkey->co, hkey->co);
2848           nhkey->editflag = hkey->editflag;
2849           nhkey->time = hkey->time;
2850           nhkey->weight = hkey->weight;
2851
2852           nkey->co = nhkey->co;
2853           nkey->time = &nhkey->time;
2854           /* these can be copied from old edit keys */
2855           nkey->flag = key->flag;
2856           nkey->ftime = key->ftime;
2857           nkey->length = key->length;
2858           copy_v3_v3(nkey->world_co, key->world_co);
2859         }
2860         nkey++;
2861         nhkey++;
2862         hkey++;
2863       }
2864
2865       if (pa->hair) {
2866         MEM_freeN(pa->hair);
2867       }
2868
2869       if (point->keys) {
2870         MEM_freeN(point->keys);
2871       }
2872
2873       pa->hair = new_hkeys;
2874       point->keys = new_keys;
2875
2876       point->totkey = pa->totkey = new_totkey;
2877
2878       /* flag for recalculating length */
2879       point->flag |= PEP_EDIT_RECALC;
2880     }
2881   }
2882 }
2883
2884 /************************ subdivide opertor *********************/
2885
2886 /* works like normal edit mode subdivide, inserts keys between neighboring selected keys */
2887 static void subdivide_particle(PEData *data, int pa_index)
2888 {
2889   PTCacheEdit *edit = data->edit;
2890   ParticleSystem *psys = edit->psys;
2891   ParticleSimulationData sim = {0};
2892   ParticleData *pa = psys->particles + pa_index;
2893   PTCacheEditPoint *point = edit->points + pa_index;
2894   ParticleKey state;
2895   HairKey *key, *nkey, *new_keys;
2896   PTCacheEditKey *ekey, *nekey, *new_ekeys;
2897
2898   int k;
2899   short totnewkey = 0;
2900   float endtime;
2901
2902   sim.depsgraph = data->depsgraph;
2903   sim.scene = data->scene;
2904   sim.ob = data->ob;
2905   sim.psys = edit->psys;
2906
2907   for (k = 0, ekey = point->keys; k < pa->totkey - 1; k++, ekey++) {
2908     if (ekey->flag & PEK_SELECT && (ekey + 1)->flag & PEK_SELECT) {
2909       totnewkey++;
2910     }
2911   }
2912
2913   if (totnewkey == 0) {
2914     return;
2915   }
2916
2917   pa->flag |= PARS_REKEY;
2918
2919   nkey = new_keys = MEM_callocN((pa->totkey + totnewkey) * (sizeof(HairKey)),
2920                                 "Hair subdivide keys");
2921   nekey = new_ekeys = MEM_callocN((pa->totkey + totnewkey) * (sizeof(PTCacheEditKey)),
2922                                   "Hair subdivide edit keys");
2923
2924   key = pa->hair;
2925   endtime = key[pa->totkey - 1].time;
2926
2927   for (k = 0, ekey = point->keys; k < pa->totkey - 1; k++, key++, ekey++) {
2928
2929     memcpy(nkey, key, sizeof(HairKey));
2930     memcpy(nekey, ekey, sizeof(PTCacheEditKey));
2931
2932     nekey->co = nkey->co;
2933     nekey->time = &nkey->time;
2934
2935     nkey++;
2936     nekey++;
2937
2938     if (ekey->flag & PEK_SELECT && (ekey + 1)->flag & PEK_SELECT) {
2939       nkey->time = (key->time + (key + 1)->time) * 0.5f;
2940       state.time = (endtime != 0.0f) ? nkey->time / endtime : 0.0f;
2941       psys_get_particle_on_path(&sim, pa_index, &state, 0);
2942       copy_v3_v3(nkey->co, state.co);
2943
2944       nekey->co = nkey->co;
2945       nekey->time = &nkey->time;
2946       nekey->flag |= PEK_SELECT;
2947       if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
2948         nekey->flag |= PEK_USE_WCO;
2949       }
2950
2951       nekey++;
2952       nkey++;
2953     }
2954   }
2955   /*tip still not copied*/
2956   memcpy(nkey, key, sizeof(HairKey));
2957   memcpy(nekey, ekey, sizeof(PTCacheEditKey));
2958
2959   nekey->co = nkey->co;
2960   nekey->time = &nkey->time;
2961
2962   if (pa->hair) {
2963     MEM_freeN(pa->hair);
2964   }
2965   pa->hair = new_keys;
2966
2967   if (point->keys) {
2968     MEM_freeN(point->keys);
2969   }
2970   point->keys = new_ekeys;
2971
2972   point->totkey = pa->totkey = pa->totkey + totnewkey;
2973   point->flag |= PEP_EDIT_RECALC;
2974   pa->flag &= ~PARS_REKEY;
2975 }
2976
2977 static int subdivide_exec(bContext *C, wmOperator *UNUSED(op))
2978 {
2979   PEData data;
2980
2981   PE_set_data(C, &data);
2982   foreach_point(&data, subdivide_particle);
2983
2984   recalc_lengths(data.edit);
2985   PE_update_selection(data.depsgraph, data.scene, data.ob, 1);
2986   PE_update_object(data.depsgraph, data.scene, data.ob, 1);
2987   DEG_id_tag_update(&data.ob->id, ID_RECALC_SELECT);
2988   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_EDITED, data.ob);
2989
2990   return OPERATOR_FINISHED;
2991 }
2992
2993 void PARTICLE_OT_subdivide(wmOperatorType *ot)
2994 {
2995   /* identifiers */
2996   ot->name = "Subdivide";
2997   ot->idname = "PARTICLE_OT_subdivide";
2998   ot->description = "Subdivide selected particles segments (adds keys)";
2999
3000   /* api callbacks */
3001   ot->exec = subdivide_exec;
3002   ot->poll = PE_hair_poll;
3003
3004   /* flags */
3005   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
3006 }
3007
3008 /************************ remove doubles opertor *********************/
3009
3010 static int remove_doubles_exec(bContext *C, wmOperator *op)
3011 {
3012   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
3013   Scene *scene = CTX_data_scene(C);
3014   Object *ob = CTX_data_active_object(C);
3015   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
3016   ParticleSystem *psys = edit->psys;
3017   ParticleSystemModifierData *psmd_eval;
3018   KDTree_3d *tree;
3019   KDTreeNearest_3d nearest[10];
3020   POINT_P;
3021   float mat[4][4], co[3], threshold = RNA_float_get(op->ptr, "threshold");
3022   int n, totn, removed, totremoved;
3023
3024   if (psys->flag & PSYS_GLOBAL_HAIR) {
3025     return OPERATOR_CANCELLED;
3026   }
3027
3028   edit = psys->edit;
3029   psmd_eval = edit->psmd_eval;
3030   totremoved = 0;
3031
3032   do {
3033     removed = 0;
3034
3035     tree = BLI_kdtree_3d_new(psys->totpart);
3036
3037     /* insert particles into kd tree */
3038     LOOP_SELECTED_POINTS {
3039       psys_mat_hair_to_object(
3040           ob, psmd_eval->mesh_final, psys->part->from, psys->particles + p, mat);
3041       copy_v3_v3(co, point->keys->co);
3042       mul_m4_v3(mat, co);
3043       BLI_kdtree_3d_insert(tree, p, co);
3044     }
3045
3046     BLI_kdtree_3d_balance(tree);
3047
3048     /* tag particles to be removed */
3049     LOOP_SELECTED_POINTS {
3050       psys_mat_hair_to_object(
3051           ob, psmd_eval->mesh_final, psys->part->from, psys->particles + p, mat);
3052       copy_v3_v3(co, point->keys->co);
3053       mul_m4_v3(mat, co);
3054
3055       totn = BLI_kdtree_3d_find_nearest_n(tree, co, nearest, 10);
3056
3057       for (n = 0; n < totn; n++) {
3058         /* this needs a custom threshold still */
3059         if (nearest[n].index > p && nearest[n].dist < threshold) {
3060           if (!(point->flag & PEP_TAG)) {
3061             point->flag |= PEP_TAG;
3062             removed++;
3063           }
3064         }
3065       }
3066     }
3067
3068     BLI_kdtree_3d_free(tree);
3069
3070     /* remove tagged particles - don't do mirror here! */
3071     remove_tagged_particles(ob, psys, 0);
3072     totremoved += removed;
3073   } while (removed);
3074
3075   if (totremoved == 0) {
3076     return OPERATOR_CANCELLED;
3077   }
3078
3079   BKE_reportf(op->reports, RPT_INFO, "Removed %d double particle(s)", totremoved);
3080
3081   DEG_id_tag_update(&ob->id, ID_RECALC_GEOMETRY);
3082   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_EDITED, ob);
3083
3084   return OPERATOR_FINISHED;
3085 }
3086
3087 void PARTICLE_OT_remove_doubles(wmOperatorType *ot)
3088 {
3089   /* identifiers */
3090   ot->name = "Remove Doubles";
3091   ot->idname = "PARTICLE_OT_remove_doubles";
3092   ot->description = "Remove selected particles close enough of others";
3093
3094   /* api callbacks */
3095   ot->exec = remove_doubles_exec;
3096   ot->poll = PE_hair_poll;
3097
3098   /* flags */
3099   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
3100
3101   /* properties */
3102   RNA_def_float(ot->srna,
3103                 "threshold",
3104                 0.0002f,
3105                 0.0f,
3106                 FLT_MAX,
3107                 "Merge Distance",
3108                 "Threshold distance within which particles are removed",
3109                 0.00001f,
3110                 0.1f);
3111 }
3112
3113 static int weight_set_exec(bContext *C, wmOperator *op)
3114 {
3115   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
3116   Scene *scene = CTX_data_scene(C);
3117   ParticleEditSettings *pset = PE_settings(scene);
3118   Object *ob = CTX_data_active_object(C);
3119   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
3120   ParticleSystem *psys = edit->psys;
3121   POINT_P;
3122   KEY_K;
3123   HairKey *hkey;
3124   float weight;
3125   ParticleBrushData *brush = &pset->brush[pset->brushtype];
3126   float factor = RNA_float_get(op->ptr, "factor");
3127
3128   weight = brush->strength;
3129   edit = psys->edit;
3130
3131   LOOP_SELECTED_POINTS {
3132     ParticleData *pa = psys->particles + p;
3133
3134     LOOP_SELECTED_KEYS {
3135       hkey = pa->hair + k;
3136       hkey->weight = interpf(weight, hkey->weight, factor);
3137     }
3138   }
3139
3140   DEG_id_tag_update(&ob->id, ID_RECALC_GEOMETRY);
3141   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_EDITED, ob);
3142
3143   return OPERATOR_FINISHED;
3144 }
3145
3146 void PARTICLE_OT_weight_set(wmOperatorType *ot)
3147 {
3148   /* identifiers */
3149   ot->name = "Weight Set";
3150   ot->idname = "PARTICLE_OT_weight_set";
3151   ot->description = "Set the weight of selected keys";
3152
3153   /* api callbacks */
3154   ot->exec = weight_set_exec;
3155   ot->poll = PE_hair_poll;
3156
3157   /* flags */
3158   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
3159
3160   RNA_def_float(ot->srna,
3161                 "factor",
3162                 1,
3163                 0,
3164                 1,
3165                 "Factor",
3166                 "Interpolation factor between current brush weight, and keys' weights",
3167                 0,
3168                 1);
3169 }
3170
3171 /************************ cursor drawing *******************************/
3172
3173 static void brush_drawcursor(bContext *C, int x, int y, void *UNUSED(customdata))
3174 {
3175   Scene *scene = CTX_data_scene(C);
3176   ParticleEditSettings *pset = PE_settings(scene);
3177   ParticleBrushData *brush;
3178
3179   if (!WM_toolsystem_active_tool_is_brush(C)) {
3180     return;
3181   }
3182
3183   brush = &pset->brush[pset->brushtype];
3184
3185   if (brush) {
3186     uint pos = GPU_vertformat_attr_add(immVertexFormat(), "pos", GPU_COMP_F32, 2, GPU_FETCH_FLOAT);
3187     immBindBuiltinProgram(GPU_SHADER_2D_UNIFORM_COLOR);
3188
3189     immUniformColor4ub(255, 255, 255, 128);
3190
3191     GPU_line_smooth(true);
3192     GPU_blend(true);
3193
3194     imm_draw_circle_wire_2d(pos, (float)x, (float)y, pe_brush_size_get(scene, brush), 40);
3195
3196     GPU_blend(false);
3197     GPU_line_smooth(false);
3198
3199     immUnbindProgram();
3200   }
3201 }
3202
3203 static void toggle_particle_cursor(bContext *C, int enable)
3204 {
3205   ParticleEditSettings *pset = PE_settings(CTX_data_scene(C));
3206
3207   if (pset->paintcursor && !enable) {
3208     WM_paint_cursor_end(CTX_wm_manager(C), pset->paintcursor);
3209     pset->paintcursor = NULL;
3210   }
3211   else if (enable) {
3212     pset->paintcursor = WM_paint_cursor_activate(
3213         CTX_wm_manager(C), SPACE_VIEW3D, RGN_TYPE_WINDOW, PE_poll_view3d, brush_drawcursor, NULL);
3214   }
3215 }
3216
3217 /*************************** delete operator **************************/
3218
3219 enum { DEL_PARTICLE, DEL_KEY };
3220
3221 static const EnumPropertyItem delete_type_items[] = {
3222     {DEL_PARTICLE, "PARTICLE", 0, "Particle", ""},
3223     {DEL_KEY, "KEY", 0, "Key", ""},
3224     {0, NULL, 0, NULL, NULL},
3225 };
3226
3227 static void set_delete_particle(PEData *data, int pa_index)
3228 {
3229   PTCacheEdit *edit = data->edit;
3230
3231   edit->points[pa_index].flag |= PEP_TAG;
3232 }
3233
3234 static void set_delete_particle_key(PEData *data,
3235                                     int pa_index,
3236                                     int key_index,
3237                                     bool UNUSED(is_inside))
3238 {
3239   PTCacheEdit *edit = data->edit;
3240
3241   edit->points[pa_index].keys[key_index].flag |= PEK_TAG;
3242 }
3243
3244 static int delete_exec(bContext *C, wmOperator *op)
3245 {
3246   PEData data;
3247   int type = RNA_enum_get(op->ptr, "type");
3248
3249   PE_set_data(C, &data);
3250
3251   if (type == DEL_KEY) {
3252     foreach_selected_key(&data, set_delete_particle_key);
3253     remove_tagged_keys(data.depsgraph, data.ob, data.edit->psys);
3254     recalc_lengths(data.edit);
3255   }
3256   else if (type == DEL_PARTICLE) {
3257     foreach_selected_point(&data, set_delete_particle);
3258     remove_tagged_particles(data.ob, data.edit->psys, pe_x_mirror(data.ob));
3259     recalc_lengths(data.edit);
3260   }
3261
3262   DEG_id_tag_update(&data.ob->id, ID_RECALC_GEOMETRY);
3263   BKE_particle_batch_cache_dirty_tag(data.edit->psys, BKE_PARTICLE_BATCH_DIRTY_ALL);
3264   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_EDITED, data.ob);
3265
3266   return OPERATOR_FINISHED;
3267 }
3268
3269 void PARTICLE_OT_delete(wmOperatorType *ot)
3270 {
3271   /* identifiers */
3272   ot->name = "Delete";
3273   ot->idname = "PARTICLE_OT_delete";
3274   ot->description = "Delete selected particles or keys";
3275
3276   /* api callbacks */
3277   ot->exec = delete_exec;
3278   ot->invoke = WM_menu_invoke;
3279   ot->poll = PE_hair_poll;
3280
3281   /* flags */
3282   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
3283
3284   /* properties */
3285   ot->prop = RNA_def_enum(ot->srna,
3286                           "type",
3287                           delete_type_items,
3288                           DEL_PARTICLE,
3289                           "Type",
3290                           "Delete a full particle or only keys");
3291 }
3292
3293 /*************************** mirror operator **************************/
3294
3295 static void PE_mirror_x(Depsgraph *depsgraph, Scene *scene, Object *ob, int tagged)
3296 {
3297   Mesh *me = (Mesh *)(ob->data);
3298   ParticleSystemModifierData *psmd_eval;
3299   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
3300   ParticleSystem *psys = edit->psys;
3301   ParticleData *pa, *newpa, *new_pars;
3302   PTCacheEditPoint *newpoint, *new_points;
3303   POINT_P;
3304   KEY_K;
3305   HairKey *hkey;
3306   int *mirrorfaces = NULL;
3307   int rotation, totpart, newtotpart;
3308
3309   if (psys->flag & PSYS_GLOBAL_HAIR) {
3310     return;
3311   }
3312
3313   psmd_eval = edit->psmd_eval;
3314   if (!psmd_eval->mesh_final) {
3315     return;
3316   }
3317
3318   const bool use_dm_final_indices = (psys->part->use_modifier_stack &&
3319                                      !psmd_eval->mesh_final->runtime.deformed_only);
3320
3321   /* NOTE: this is not nice to use tessfaces but hard to avoid since pa->num uses tessfaces */
3322   BKE_mesh_tessface_ensure(me);
3323
3324   /* NOTE: In case psys uses Mesh tessface indices, we mirror final Mesh itself, not orig mesh.
3325    * Avoids an (impossible) mesh -> orig -> mesh tessface indices conversion. */
3326   mirrorfaces = mesh_get_x_mirror_faces(
3327       ob, NULL, use_dm_final_indices ? psmd_eval->mesh_final : NULL);
3328
3329   if (!edit->mirror_cache) {
3330     PE_update_mirror_cache(ob, psys);
3331   }
3332
3333   totpart = psys->totpart;
3334   newtotpart = psys->totpart;
3335   LOOP_VISIBLE_POINTS {
3336     pa = psys->particles + p;
3337
3338     if (!tagged) {
3339       if (point_is_selected(point)) {
3340         if (edit->mirror_cache[p] != -1) {
3341           /* already has a mirror, don't need to duplicate */
3342           PE_mirror_particle(ob, psmd_eval->mesh_final, psys, pa, NULL);
3343           continue;
3344         }
3345         else {
3346           point->flag |= PEP_TAG;
3347         }
3348       }
3349     }
3350
3351     if ((point->flag & PEP_TAG) && mirrorfaces[pa->num * 2] != -1) {
3352       newtotpart++;
3353     }
3354   }
3355
3356   if (newtotpart != psys->totpart) {
3357     MFace *mtessface = use_dm_final_indices ? psmd_eval->mesh_final->mface : me->mface;
3358
3359     /* allocate new arrays and copy existing */
3360     new_pars = MEM_callocN(newtotpart * sizeof(ParticleData), "ParticleData new");
3361     new_points = MEM_callocN(newtotpart * sizeof(PTCacheEditPoint), "PTCacheEditPoint new");
3362
3363     if (psys->particles) {
3364       memcpy(new_pars, psys->particles, totpart * sizeof(ParticleData));
3365       MEM_freeN(psys->particles);
3366     }
3367     psys->particles = new_pars;
3368
3369     if (edit->points) {
3370       memcpy(new_points, edit->points, totpart * sizeof(PTCacheEditPoint));
3371       MEM_freeN(edit->points);
3372     }
3373     edit->points = new_points;
3374
3375     if (edit->mirror_cache) {
3376       MEM_freeN(edit->mirror_cache);
3377       edit->mirror_cache = NULL;
3378     }
3379
3380     edit->totpoint = psys->totpart = newtotpart;
3381
3382     /* create new elements */
3383     newpa = psys->particles + totpart;
3384     newpoint = edit->points + totpart;
3385
3386     for (p = 0, point = edit->points; p < totpart; p++, point++) {
3387       pa = psys->particles + p;
3388       const int pa_num = pa->num;
3389
3390       if (point->flag & PEP_HIDE) {
3391         continue;
3392       }
3393
3394       if (!(point->flag & PEP_TAG) || mirrorfaces[pa_num * 2] == -1) {
3395         continue;
3396       }
3397
3398       /* duplicate */
3399       *newpa = *pa;
3400       *newpoint = *point;
3401       if (pa->hair) {
3402         newpa->hair = MEM_dupallocN(pa->hair);
3403       }
3404       if (point->keys) {
3405         newpoint->keys = MEM_dupallocN(point->keys);
3406       }
3407
3408       /* rotate weights according to vertex index rotation */
3409       rotation = mirrorfaces[pa_num * 2 + 1];
3410       newpa->fuv[0] = pa->fuv[2];
3411       newpa->fuv[1] = pa->fuv[1];
3412       newpa->fuv[2] = pa->fuv[0];
3413       newpa->fuv[3] = pa->fuv[3];
3414       while (rotation--) {
3415         if (mtessface[pa_num].v4) {
3416           SHIFT4(float, newpa->fuv[0], newpa->fuv[1], newpa->fuv[2], newpa->fuv[3]);
3417         }
3418         else {
3419           SHIFT3(float, newpa->fuv[0], newpa->fuv[1], newpa->fuv[2]);
3420         }
3421       }
3422
3423       /* assign face index */
3424       /* NOTE: mesh_get_x_mirror_faces generates -1 for non-found mirror,
3425        * same as DMCACHE_NOTFOUND. */
3426       newpa->num = mirrorfaces[pa_num * 2];
3427
3428       if (use_dm_final_indices) {
3429         newpa->num_dmcache = DMCACHE_ISCHILD;
3430       }
3431       else {
3432         newpa->num_dmcache = psys_particle_dm_face_lookup(
3433             psmd_eval->mesh_final, psmd_eval->mesh_original, newpa->num, newpa->fuv, NULL);
3434       }
3435
3436       /* update edit key pointers */
3437       key = newpoint->keys;
3438       for (k = 0, hkey = newpa->hair; k < newpa->totkey; k++, hkey++, key++) {
3439         key->co = hkey->co;
3440         key->time = &hkey->time;
3441       }
3442
3443       /* map key positions as mirror over x axis */
3444       PE_mirror_particle(ob, psmd_eval->mesh_final, psys, pa, newpa);
3445
3446       newpa++;
3447       newpoint++;
3448     }
3449   }
3450
3451   LOOP_POINTS {
3452     point->flag &= ~PEP_TAG;
3453   }
3454
3455   MEM_freeN(mirrorfaces);
3456 }
3457
3458 static int mirror_exec(bContext *C, wmOperator *UNUSED(op))
3459 {
3460   Depsgraph *depsgraph = CTX_data_depsgraph_pointer(C);
3461   Scene *scene = CTX_data_scene(C);
3462   Object *ob = CTX_data_active_object(C);
3463   PTCacheEdit *edit = PE_get_current(depsgraph, scene, ob);
3464
3465   PE_mirror_x(depsgraph, scene, ob, 0);
3466
3467   update_world_cos(ob, edit);
3468   psys_free_path_cache(NULL, edit);
3469
3470   WM_event_add_notifier(C, NC_OBJECT | ND_PARTICLE | NA_EDITED, ob);
3471   BKE_particle_batch_cache_dirty_tag(edit->psys, BKE_PARTICLE_BATCH_DIRTY_ALL);
3472   DEG_id_tag_update(&ob->id, ID_RECALC_GEOMETRY);
3473
3474   return OPERATOR_FINISHED;
3475 }
3476
3477 void PARTICLE_OT_mirror(wmOperatorType *ot)
3478 {
3479   /* identifiers */
3480   ot->name = "Mirror";
3481   ot->idname = "PARTICLE_OT_mirror";
3482   ot->description = "Duplicate and mirror the selected particles along the local X axis";
3483
3484   /* api callbacks */
3485   ot->exec = mirror_exec;
3486   ot->poll = PE_hair_poll;
3487
3488   /* flags */
3489   ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
3490 }
3491
3492 /************************* brush edit callbacks ********************/
3493
3494 static void brush_comb(PEData *data,
3495                        float UNUSED(mat[4][4]),
3496                        float imat[4][4],
3497                        int point_index,
3498                        int key_index,
3499                        PTCacheEditKey *key,
3500                        float mouse_distance)
3501 {
3502   ParticleEditSettings *pset = PE_settings(data->scene);
3503   float cvec[3], fac;
3504
3505   if (pset->flag & PE_LOCK_FIRST && key_index == 0) {
3506     return;
3507   }
3508
3509   fac = (float)pow((double)(1.0f - mouse_distance / data->rad), (double)data->combfac);
3510
3511   copy_v3_v3(cvec, data->dvec);
3512   mul_mat3_m4_v3(imat, cvec);
3513   mul_v3_fl(cvec, fac);
3514   add_v3_v3(key->co, cvec);
3515
3516   (data->edit->points + point_index)->flag |= PEP_EDIT_RECALC;
3517 }
3518
3519 static void brush_cut(PEData *data, int pa_index)
3520 {
3521   PTCacheEdit *edit = data->edit;
3522   ARegion *ar = data->vc.ar;
3523   Object *ob = data->ob;
3524   ParticleEditSettings *pset = PE_settings(data->scene);
3525   ParticleCacheKey *key = edit->pathcache[pa_index];
3526   float rad2, cut_time = 1.0;
3527   float x0, x1, v0, v1, o0, o1, xo0, xo1, d, dv;
3528   int k, cut, keys = (int)pow(2.0, (double)pset->draw_step);
3529   int screen_co[2];
3530
3531   BLI_assert(data->rng != NULL);
3532   /* blunt scissors */
3533   if (BLI_rng_get_float(data->rng) > data->cutfac) {
3534     return;
3535   }
3536
3537   /* don't cut hidden */
3538   if (edit->points[pa_index].flag & PEP_HIDE) {
3539     return;
3540   }
3541
3542   if (ED_view3d_project_int_global(ar, key->co, screen_co, V3D_PROJ_TEST_CLIP_NEAR) !=
3543       V3D_PROJ_RET_OK) {
3544     return;
3545   }
3546
3547   rad2 = data->rad * data->rad;
3548
3549   cut = 0;
3550
3551   x0 = (float)screen_co[0];
3552   x1 = (float)screen_co[1];
3553
3554   o0 = (float)data->mval[0];
3555   o1 = (float)data->mval[1];
3556
3557   xo0 = x0 - o0;
3558   xo1 = x1 - o1;
3559
3560   /* check if root is inside circle */
3561   if (xo0 * xo0 + xo1 * xo1 < rad2 && key_test_depth(data, key->co, screen_co)) {
3562     cut_time = -1.0f;
3563     cut = 1;
3564   }
3565   else {
3566     /* calculate path time closest to root that was inside the circle */
3567     for (k = 1, key++; k <= keys; k++, key++) {
3568
3569       if ((ED_view3d_project_int_global(ar, key->co, screen_co, V3D_PROJ_TEST_CLIP_NEAR) !=
3570            V3D_PROJ_RET_OK) ||
3571           key_test_depth(data, key->co, screen_co) == 0) {
3572         x0 = (float)screen_co[0];
3573         x1 = (float)screen_co[1];
3574
3575         xo0 = x0 - o0;
3576         xo1 = x1 - o1;
3577         continue;
3578       }
3579
3580       v0 = (float)screen_co[0] - x0;
3581       v1 = (float)screen_co[1] - x1;
3582
3583       dv = v0 * v0 + v1 * v1;
3584
3585       d = (v0 * xo1 - v1 * xo0);
3586
3587       d = dv * rad2 - d * d;
3588
3589       if (d > 0.0f) {
3590         d = sqrtf(d);
3591
3592         cut_time = -(v0 * xo0 + v1 * xo1 + d);
3593
3594         if (cut_time > 0.0f) {
3595           cut_time /= dv;
3596
3597           if (cut_time < 1.0f) {
3598             cut_time += (float)(k - 1);
3599             cut_time /= (float)keys;
3600             cut = 1;
3601             break;
3602           }
3603         }
3604       }
3605
3606       x0 = (float)screen_co[0];
3607       x1 = (float)screen_co[1];
3608
3609       xo0 = x0 - o0;
3610       xo1 = x1 - o1;
3611     }
3612   }
3613
3614   if (cut) {
3615     if (cut_time < 0.0f) {
3616       edit->points[pa_index].flag |= PEP_TAG;
3617     }
3618     else {
3619       rekey_particle_to_time(data->context, data->scene, ob, pa_index, cut_time);
3620       edit->points[pa_index].flag |= PEP_EDIT_RECALC;
3621     }
3622   }
3623 }
3624
3625 static void brush_length(PEData *data, int point_index, float UNUSED(mouse_distance))
3626 {
3627   PTCacheEdit *edit = data->edit;
3628   PTCacheEditPoint *point = edit->points + point_index;
3629   KEY_K;
3630   float dvec[3], pvec[3] = {0.0f, 0.0f, 0.0f};
3631
3632   LOOP_KEYS {
3633     if (k == 0) {
3634       copy_v3_v3(pvec, key->co);
3635     }
3636     else {
3637       sub_v3_v3v3(dvec, key->co, pvec);
3638       copy_v3_v3(pvec, key->co);
3639       mul_v3_fl(dvec, data->growfac);
3640       add_v3_v3v3(key->co, (key - 1)->co, dvec);
3641     }
3642   }
3643
3644   point->flag |= PEP_EDIT_RECALC;
3645 }
3646
3647 static void brush_puff(PEData *data, int point_index, float mouse_distance)
3648 {
3649   PTCacheEdit *edit = data->edit;
3650   ParticleSystem *psys = edit->psys;
3651   PTCacheEditPoint *point = edit->points + point_index;
3652   KEY_K;
3653   float mat[4][4], imat[4][4];
3654
3655   float onor_prev[3];           /* previous normal (particle-space) */
3656   float ofs_prev[3];            /* accumulate offset for puff_volume (particle-space) */
3657   float co_root[3], no_root[3]; /* root location and normal (global-space) */
3658   float co_prev[3], co[3];      /* track key coords as we loop (global-space) */
3659   float fac = 0.0f, length_accum = 0.0f;
3660   bool puff_volume = false;
3661   bool changed = false;
3662
3663   zero_v3(ofs_prev);
3664
3665   {
3666     ParticleEditSettings *pset = PE_settings(data->scene);
3667     ParticleBrushData *brush = &pset->brush[pset->brushtype];
3668     puff_volume = (brush->flag & PE_BRUSH_DATA_PUFF_VOLUME) != 0;
3669   }
3670
3671   if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
3672     psys_mat_hair_to_global(
3673         data->ob, data->mesh, psys->part->from, psys->particles + point_index, mat);
3674     invert_m4_m4(imat, mat);
3675   }
3676   else {
3677     unit_m4(mat);
3678     unit_m4(imat);
3679   }
3680
3681   LOOP_KEYS {
3682     float kco[3];
3683
3684     if (k == 0) {
3685       /* find root coordinate and normal on emitter */
3686       copy_v3_v3(co, key->co);
3687       mul_m4_v3(mat, co);
3688
3689       /* use 'kco' as the object space version of worldspace 'co',
3690        * ob->imat is set before calling */
3691       mul_v3_m4v3(kco, data->ob->imat, co);
3692
3693       point_index = BLI_kdtree_3d_find_nearest(edit->emitter_field, kco, NULL);
3694       if (point_index == -1) {
3695         return;
3696       }
3697
3698       copy_v3_v3(co_root, co);
3699       copy_v3_v3(no_root, &edit->emitter_cosnos[point_index * 6 + 3]);
3700       mul_mat3_m4_v3(data->ob->obmat, no_root); /* normal into global-space */
3701       normalize_v3(no_root);
3702
3703       if (puff_volume) {
3704         copy_v3_v3(onor_prev, no_root);
3705         mul_mat3_m4_v3(imat, onor_prev); /* global-space into particle space */
3706         normalize_v3(onor_prev);
3707       }
3708
3709       fac = (float)pow((double)(1.0f - mouse_distance / data->rad), (double)data->pufffac);
3710       fac *= 0.025f;
3711       if (data->invert) {
3712         fac = -fac;
3713       }
3714     }
3715     else {
3716       /* compute position as if hair was standing up straight.
3717        * */
3718       float length;
3719       copy_v3_v3(co_prev, co);
3720       copy_v3_v3(co, key->co);
3721       mul_m4_v3(mat, co);
3722       length = len_v3v3(co_prev, co);
3723       length_accum += length;
3724
3725       if ((data->select == 0 || (key->flag & PEK_SELECT)) && !(key->flag & PEK_HIDE)) {
3726         float dco[3]; /* delta temp var */
3727
3728         madd_v3_v3v3fl(kco, co_root, no_root, length_accum);
3729
3730         /* blend between the current and straight position */
3731         sub_v3_v3v3(dco, kco, co);
3732         madd_v3_v3fl(co, dco, fac);
3733         /* keep the same distance from the root or we get glitches [#35406] */
3734         dist_ensure_v3_v3fl(co, co_root, length_accum);
3735
3736         /* re-use dco to compare before and after translation and add to the offset  */
3737         copy_v3_v3(dco, key->co);
3738
3739         mul_v3_m4v3(key->co, imat, co);
3740
3741         if (puff_volume) {
3742           /* accumulate the total distance moved to apply to unselected
3743            * keys that come after */
3744           sub_v3_v3v3(ofs_prev, key->co, dco);
3745         }
3746         changed = true;
3747       }
3748       else {
3749
3750         if (puff_volume) {
3751 #if 0
3752           /* this is simple but looks bad, adds annoying kinks */
3753           add_v3_v3(key->co, ofs);
3754 #else
3755           /* translate (not rotate) the rest of the hair if its not selected  */
3756           {
3757 #  if 0 /* kindof works but looks worse then what's below */
3758
3759             /* Move the unselected point on a vector based on the
3760              * hair direction and the offset */
3761             float c1[3], c2[3];
3762             sub_v3_v3v3(dco, lastco, co);
3763             mul_mat3_m4_v3(imat, dco); /* into particle space */
3764
3765             /* move the point along a vector perpendicular to the
3766              * hairs direction, reduces odd kinks, */
3767             cross_v3_v3v3(c1, ofs, dco);
3768             cross_v3_v3v3(c2, c1, dco);
3769             normalize_v3(c2);
3770             mul_v3_fl(c2, len_v3(ofs));
3771             add_v3_v3(key->co, c2);
3772 #  else
3773             /* Move the unselected point on a vector based on the
3774              * the normal of the closest geometry */
3775             float oco[3], onor[3];
3776             copy_v3_v3(oco, key->co);
3777             mul_m4_v3(mat, oco);
3778
3779             /* use 'kco' as the object space version of worldspace 'co',
3780              * ob->imat is set before calling */
3781             mul_v3_m4v3(kco, data->ob->imat, oco);
3782
3783             point_index = BLI_kdtree_3d_find_nearest(edit->emitter_field, kco, NULL);
3784             if (point_index != -1) {
3785               copy_v3_v3(onor, &edit->emitter_cosnos[point_index * 6 + 3]);
3786               mul_mat3_m4_v3(data->ob->obmat, onor); /* normal into worldspace */
3787          &nb