Sorry, three commits in one, became difficult to untangle..
[blender-staging.git] / source / blender / editors / physics / particle_edit.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2007 by Janne Karhu.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include <stdlib.h>
31 #include <math.h>
32 #include <string.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "DNA_scene_types.h"
37 #include "DNA_mesh_types.h"
38 #include "DNA_meshdata_types.h"
39 #include "DNA_modifier_types.h"
40 #include "DNA_object_force.h"
41 #include "DNA_object_types.h"
42 #include "DNA_vec_types.h"
43 #include "DNA_userdef_types.h"
44 #include "DNA_view3d_types.h"
45 #include "DNA_screen_types.h"
46 #include "DNA_space_types.h"
47 #include "DNA_windowmanager_types.h"
48
49 #include "BKE_DerivedMesh.h"
50 #include "BKE_depsgraph.h"
51
52 #include "BKE_context.h"
53 #include "BKE_global.h"
54 #include "BKE_object.h"
55 #include "BKE_mesh.h"
56 #include "BKE_modifier.h"
57 #include "BKE_particle.h"
58 #include "BKE_report.h"
59 #include "BKE_scene.h"
60 #include "BKE_utildefines.h"
61 #include "BKE_pointcache.h"
62
63 #include "BLI_arithb.h"
64 #include "BLI_blenlib.h"
65 #include "BLI_dynstr.h"
66 #include "BLI_kdtree.h"
67 #include "BLI_rand.h"
68
69 #include "PIL_time.h"
70
71 #include "BIF_gl.h"
72 #include "BIF_glutil.h"
73
74 #include "ED_mesh.h"
75 #include "ED_particle.h"
76 #include "ED_view3d.h"
77
78 #include "UI_interface.h"
79 #include "UI_resources.h"
80
81 #include "WM_api.h"
82 #include "WM_types.h"
83
84 #include "RNA_access.h"
85 #include "RNA_define.h"
86
87 #include "physics_intern.h"
88
89 static void PE_create_particle_edit(Scene *scene, Object *ob, PointCache *cache, ParticleSystem *psys);
90 static void PTCacheUndo_clear(PTCacheEdit *edit);
91
92 #define KEY_K                                   PTCacheEditKey *key; int k
93 #define POINT_P                                 PTCacheEditPoint *point; int p
94 #define LOOP_POINTS                             for(p=0, point=edit->points; p<edit->totpoint; p++, point++)
95 #define LOOP_VISIBLE_POINTS             for(p=0, point=edit->points; p<edit->totpoint; p++, point++) if(!(point->flag & PEP_HIDE))
96 #define LOOP_SELECTED_POINTS    for(p=0, point=edit->points; p<edit->totpoint; p++, point++) if(point_is_selected(point))
97 #define LOOP_UNSELECTED_POINTS  for(p=0, point=edit->points; p<edit->totpoint; p++, point++) if(!point_is_selected(point))
98 #define LOOP_EDITED_POINTS              for(p=0, point=edit->points; p<edit->totpoint; p++, point++) if(point->flag & PEP_EDIT_RECALC)
99 #define LOOP_TAGGED_POINTS              for(p=0, point=edit->points; p<edit->totpoint; p++, point++) if(point->flag & PEP_TAG)
100 #define LOOP_KEYS                               for(k=0, key=point->keys; k<point->totkey; k++, key++)
101 #define LOOP_VISIBLE_KEYS               for(k=0, key=point->keys; k<point->totkey; k++, key++) if(!(key->flag & PEK_HIDE))
102 #define LOOP_SELECTED_KEYS              for(k=0, key=point->keys; k<point->totkey; k++, key++) if((key->flag & PEK_SELECT) && !(key->flag & PEK_HIDE))
103 #define LOOP_TAGGED_KEYS                for(k=0, key=point->keys; k<point->totkey; k++, key++) if(key->flag & PEK_TAG)
104
105 #define KEY_WCO                                 (key->flag & PEK_USE_WCO ? key->world_co : key->co)
106
107 /**************************** utilities *******************************/
108
109 int PE_poll(bContext *C)
110 {
111         Scene *scene= CTX_data_scene(C);
112         Object *ob= CTX_data_active_object(C);
113         PTCacheEdit *edit;
114
115         if(!scene || !ob)
116                 return 0;
117         
118         edit= PE_get_current(scene, ob);
119
120         return (edit && (ob->mode & OB_MODE_PARTICLE_EDIT));
121 }
122
123 int PE_hair_poll(bContext *C)
124 {
125         Scene *scene= CTX_data_scene(C);
126         Object *ob= CTX_data_active_object(C);
127         PTCacheEdit *edit;
128
129         if(!scene || !ob)
130                 return 0;
131         
132         edit= PE_get_current(scene, ob);
133
134         return (edit && edit->psys && (ob->mode & OB_MODE_PARTICLE_EDIT));
135 }
136
137 int PE_poll_3dview(bContext *C)
138 {
139         return PE_poll(C) && CTX_wm_area(C)->spacetype == SPACE_VIEW3D &&
140                 CTX_wm_region(C)->regiontype == RGN_TYPE_WINDOW;
141 }
142
143 void PE_free_ptcache_edit(PTCacheEdit *edit)
144 {
145         POINT_P;
146
147         if(edit==0) return;
148
149         PTCacheUndo_clear(edit);
150
151         if(edit->points) {
152                 LOOP_POINTS {
153                         if(point->keys) 
154                                 MEM_freeN(point->keys);
155                 }
156
157                 MEM_freeN(edit->points);
158         }
159
160         if(edit->mirror_cache)
161                 MEM_freeN(edit->mirror_cache);
162
163         if(edit->emitter_cosnos) {
164                 MEM_freeN(edit->emitter_cosnos);
165                 edit->emitter_cosnos= 0;
166         }
167
168         if(edit->emitter_field) {
169                 BLI_kdtree_free(edit->emitter_field);
170                 edit->emitter_field= 0;
171         }
172
173         psys_free_path_cache(NULL, edit);
174
175         MEM_freeN(edit);
176 }
177
178 /************************************************/
179 /*                      Edit Mode Helpers                                       */
180 /************************************************/
181
182 int PE_start_edit(PTCacheEdit *edit)
183 {
184         if(edit) {
185                 edit->edited = 1;
186                 if(edit->psys)
187                         edit->psys->flag |= PSYS_EDITED;
188                 return 1;
189         }
190
191         return 0;
192 }
193
194 ParticleEditSettings *PE_settings(Scene *scene)
195 {
196         return &scene->toolsettings->particle;
197 }
198
199 /* always gets atleast the first particlesystem even if PSYS_CURRENT flag is not set */
200 PTCacheEdit *PE_get_current(Scene *scene, Object *ob)
201 {
202         ParticleEditSettings *pset= PE_settings(scene);
203         PTCacheEdit *edit = NULL;
204         ListBase pidlist;
205         PTCacheID *pid;
206
207         pset->scene = scene;
208         pset->object = ob;
209
210         if(ob==NULL)
211                 return NULL;
212
213         BKE_ptcache_ids_from_object(&pidlist, ob);
214
215         /* in the case of only one editable thing, set pset->edittype accordingly */
216         if(pidlist.first && pidlist.first == pidlist.last) {
217                 pid = pidlist.first;
218                 switch(pid->type) {
219                         case PTCACHE_TYPE_PARTICLES:
220                                 pset->edittype = PE_TYPE_PARTICLES;
221                                 break;
222                         case PTCACHE_TYPE_SOFTBODY:
223                                 pset->edittype = PE_TYPE_SOFTBODY;
224                                 break;
225                         case PTCACHE_TYPE_CLOTH:
226                                 pset->edittype = PE_TYPE_CLOTH;
227                                 break;
228                 }
229         }
230
231         for(pid=pidlist.first; pid; pid=pid->next) {
232                 if(pset->edittype == PE_TYPE_PARTICLES && pid->type == PTCACHE_TYPE_PARTICLES) {
233                         ParticleSystem *psys = pid->calldata;
234
235                         if(psys->flag & PSYS_CURRENT) {
236                                 if(psys->part && psys->part->type == PART_HAIR) {
237                                         if(psys->flag & PSYS_HAIR_DYNAMICS && psys->pointcache->flag & PTCACHE_BAKED) {
238                                                 if(!psys->pointcache->edit)
239                                                         PE_create_particle_edit(scene, ob, pid->cache, NULL);
240                                                 edit = pid->cache->edit;
241                                         }
242                                         else {
243                                                 if(!psys->edit && psys->flag & PSYS_HAIR_DONE)
244                                                         PE_create_particle_edit(scene, ob, NULL, psys);
245                                                 edit = psys->edit;
246                                         }
247                                 }
248                                 else {
249                                         if(pid->cache->flag & PTCACHE_BAKED && !pid->cache->edit)
250                                                 PE_create_particle_edit(scene, ob, pid->cache, psys);
251                                         edit = pid->cache->edit;
252                                 }
253
254                                 break;
255                         }
256                 }
257                 else if(pset->edittype == PE_TYPE_SOFTBODY && pid->type == PTCACHE_TYPE_SOFTBODY) {
258                         if(pid->cache->flag & PTCACHE_BAKED && !pid->cache->edit)
259                                 PE_create_particle_edit(scene, ob, pid->cache, NULL);
260                         edit = pid->cache->edit;
261                         break;
262                 }
263                 else if(pset->edittype == PE_TYPE_CLOTH && pid->type == PTCACHE_TYPE_CLOTH) {
264                         if(pid->cache->flag & PTCACHE_BAKED && !pid->cache->edit)
265                                 PE_create_particle_edit(scene, ob, pid->cache, NULL);
266                         edit = pid->cache->edit;
267                         break;
268                 }
269         }
270
271         if(edit)
272                 edit->pid = *pid;
273
274         BLI_freelistN(&pidlist);
275
276         return edit;
277 }
278
279 void PE_hide_keys_time(Scene *scene, PTCacheEdit *edit, float cfra)
280 {
281         ParticleEditSettings *pset=PE_settings(scene);
282         POINT_P; KEY_K;
283
284
285         if(pset->flag & PE_FADE_TIME && pset->selectmode==SCE_SELECT_POINT) {
286                 LOOP_POINTS {
287                         LOOP_KEYS {
288                                 if(fabs(cfra-*key->time) < pset->fade_frames)
289                                         key->flag &= ~PEK_HIDE;
290                                 else {
291                                         key->flag |= PEK_HIDE;
292                                         //key->flag &= ~PEK_SELECT;
293                                 }
294                         }
295                 }
296         }
297         else {
298                 LOOP_POINTS {
299                         LOOP_KEYS {
300                                 key->flag &= ~PEK_HIDE;
301                         }
302                 }
303         }
304 }
305
306 /****************** common struct passed to callbacks ******************/
307
308 typedef struct PEData {
309         ViewContext vc;
310         bglMats mats;
311         
312         Scene *scene;
313         Object *ob;
314         DerivedMesh *dm;
315         PTCacheEdit *edit;
316
317         short *mval;
318         rcti *rect;
319         float rad;
320         float dist;
321         float dval;
322         int select;
323
324         float *dvec;
325         float combfac;
326         float pufffac;
327         float cutfac;
328         float smoothfac;
329         float weightfac;
330         float growfac;
331         int totrekey;
332
333         int invert;
334         int tot;
335         float vec[3];
336 } PEData;
337
338 static void PE_set_data(bContext *C, PEData *data)
339 {
340         memset(data, 0, sizeof(*data));
341
342         data->scene= CTX_data_scene(C);
343         data->ob= CTX_data_active_object(C);
344         data->edit= PE_get_current(data->scene, data->ob);
345 }
346
347 static void PE_set_view3d_data(bContext *C, PEData *data)
348 {
349         PE_set_data(C, data);
350
351         view3d_set_viewcontext(C, &data->vc);
352         view3d_get_transformation(&data->vc, data->ob, &data->mats);
353
354         if((data->vc.v3d->drawtype>OB_WIRE) && (data->vc.v3d->flag & V3D_ZBUF_SELECT))
355                 view3d_validate_backbuf(&data->vc);
356 }
357
358 /*************************** selection utilities *******************************/
359
360 static int key_test_depth(PEData *data, float co[3])
361 {
362         View3D *v3d= data->vc.v3d;
363         RegionView3D *rv3d= data->vc.rv3d;
364         double ux, uy, uz;
365         float depth;
366         short wco[3], x,y;
367
368         /* nothing to do */
369         if((v3d->drawtype<=OB_WIRE) || (v3d->flag & V3D_ZBUF_SELECT)==0)
370                 return 1;
371
372         project_short(data->vc.ar, co, wco);
373         
374         if(wco[0] == IS_CLIPPED)
375                 return 0;
376
377         gluProject(co[0],co[1],co[2], data->mats.modelview, data->mats.projection,
378                 (GLint *)data->mats.viewport, &ux, &uy, &uz);
379
380         x=wco[0];
381         y=wco[1];
382
383         // XXX verify ..
384
385         if(rv3d->depths && x<rv3d->depths->w && y<rv3d->depths->h) {
386                 /* the 0.0001 is an experimental threshold to make selecting keys right next to a surface work better */
387                 if((float)uz - 0.0001 > rv3d->depths->depths[y*rv3d->depths->w+x])
388                         return 0;
389                 else
390                         return 1;
391         }
392         else {
393                 x+= (short)data->vc.ar->winrct.xmin;
394                 y+= (short)data->vc.ar->winrct.ymin;
395
396                 glReadPixels(x, y, 1, 1, GL_DEPTH_COMPONENT, GL_FLOAT, &depth);
397
398                 if((float)uz - 0.0001 > depth)
399                         return 0;
400                 else
401                         return 1;
402         }
403 }
404
405 static int key_inside_circle(PEData *data, float rad, float co[3], float *distance)
406 {
407         float dx, dy, dist;
408         short sco[2];
409
410         project_short(data->vc.ar, co, sco);
411         
412         if(sco[0] == IS_CLIPPED)
413                 return 0;
414         
415         dx= data->mval[0] - sco[0];
416         dy= data->mval[1] - sco[1];
417         dist= sqrt(dx*dx + dy*dy);
418
419         if(dist > rad)
420                 return 0;
421
422         if(key_test_depth(data, co)) {
423                 if(distance)
424                         *distance=dist;
425
426                 return 1;
427         }
428         
429         return 0;
430 }
431
432 static int key_inside_rect(PEData *data, float co[3])
433 {
434         short sco[2];
435
436         project_short(data->vc.ar, co,sco);
437
438         if(sco[0] == IS_CLIPPED)
439                 return 0;
440         
441         if(sco[0] > data->rect->xmin && sco[0] < data->rect->xmax &&
442            sco[1] > data->rect->ymin && sco[1] < data->rect->ymax)
443                 return key_test_depth(data, co);
444
445         return 0;
446 }
447
448 static int key_inside_test(PEData *data, float co[3])
449 {
450         if(data->mval)
451                 return key_inside_circle(data, data->rad, co, NULL);
452         else
453                 return key_inside_rect(data, co);
454 }
455
456 static int point_is_selected(PTCacheEditPoint *point)
457 {
458         KEY_K;
459         int sel;
460
461         if(point->flag & PEP_HIDE)
462                 return 0;
463
464         sel= 0;
465
466         LOOP_SELECTED_KEYS {
467                 return 1;
468         }
469         
470         return 0;
471 }
472
473 /*************************** iterators *******************************/
474
475 typedef void (*ForPointFunc)(PEData *data, int point_index);
476 typedef void (*ForKeyFunc)(PEData *data, int point_index, int key_index);
477 typedef void (*ForKeyMatFunc)(PEData *data, float mat[][4], float imat[][4], int point_index, int key_index, PTCacheEditKey *key);
478
479 static void for_mouse_hit_keys(PEData *data, ForKeyFunc func, int nearest)
480 {
481         ParticleEditSettings *pset= PE_settings(data->scene);
482         PTCacheEdit *edit= data->edit;
483         POINT_P; KEY_K;
484         int nearest_point, nearest_key;
485         float dist= data->rad;
486
487         /* in path select mode we have no keys */
488         if(pset->selectmode==SCE_SELECT_PATH)
489                 return;
490
491         nearest_point= -1;
492         nearest_key= -1;
493
494         LOOP_VISIBLE_POINTS {
495                 if(pset->selectmode == SCE_SELECT_END) {
496                         /* only do end keys */
497                         key= point->keys + point->totkey-1;
498
499                         if(nearest) {
500                                 if(key_inside_circle(data, dist, KEY_WCO, &dist)) {
501                                         nearest_point= p;
502                                         nearest_key= point->totkey-1;
503                                 }
504                         }
505                         else if(key_inside_test(data, KEY_WCO))
506                                 func(data, p, point->totkey-1);
507                 }
508                 else {
509                         /* do all keys */
510                         LOOP_VISIBLE_KEYS {
511                                 if(nearest) {
512                                         if(key_inside_circle(data, dist, KEY_WCO, &dist)) {
513                                                 nearest_point= p;
514                                                 nearest_key= k;
515                                         }
516                                 }
517                                 else if(key_inside_test(data, KEY_WCO))
518                                         func(data, p, k);
519                         }
520                 }
521         }
522
523         /* do nearest only */
524         if(nearest && nearest_point > -1)
525                 func(data, nearest_point, nearest_key);
526 }
527
528 static void foreach_mouse_hit_point(PEData *data, ForPointFunc func, int selected)
529 {
530         ParticleEditSettings *pset= PE_settings(data->scene);
531         PTCacheEdit *edit= data->edit;
532         POINT_P; KEY_K;
533
534         /* all is selected in path mode */
535         if(pset->selectmode==SCE_SELECT_PATH)
536                 selected=0;
537
538         LOOP_VISIBLE_POINTS {
539                 if(pset->selectmode==SCE_SELECT_END) {
540                         /* only do end keys */
541                         key= point->keys + point->totkey - 1;
542
543                         if(selected==0 || key->flag & PEK_SELECT)
544                                 if(key_inside_circle(data, data->rad, KEY_WCO, &data->dist))
545                                         func(data, p);
546                 }
547                 else {
548                         /* do all keys */
549                         LOOP_VISIBLE_KEYS {
550                                 if(selected==0 || key->flag & PEK_SELECT) {
551                                         if(key_inside_circle(data, data->rad, KEY_WCO, &data->dist)) {
552                                                 func(data, p);
553                                                 break;
554                                         }
555                                 }
556                         }
557                 }
558         }
559 }
560
561 static void foreach_mouse_hit_key(PEData *data, ForKeyMatFunc func, int selected)
562 {
563         PTCacheEdit *edit = data->edit;
564         ParticleSystem *psys = edit->psys;
565         ParticleSystemModifierData *psmd = NULL;
566         ParticleEditSettings *pset= PE_settings(data->scene);
567         POINT_P; KEY_K;
568         float mat[4][4], imat[4][4];
569
570         if(edit->psys)
571                 psmd= psys_get_modifier(data->ob, edit->psys);
572
573         /* all is selected in path mode */
574         if(pset->selectmode==SCE_SELECT_PATH)
575                 selected= 0;
576
577         Mat4One(imat);
578         Mat4One(mat);
579
580         LOOP_VISIBLE_POINTS {
581                 if(edit->psys && !(edit->psys->flag & PSYS_GLOBAL_HAIR)) {
582                         psys_mat_hair_to_global(data->ob, psmd->dm, psys->part->from, psys->particles + p, mat);
583                         Mat4Invert(imat,mat);
584                 }
585
586                 if(pset->selectmode==SCE_SELECT_END) {
587                         /* only do end keys */
588                         key= point->keys + point->totkey-1;
589
590                         if(selected==0 || key->flag & PEK_SELECT)
591                                 if(key_inside_circle(data, data->rad, KEY_WCO, &data->dist))
592                                         func(data, mat, imat, p, point->totkey-1, key);
593                 }
594                 else {
595                         /* do all keys */
596                         LOOP_VISIBLE_KEYS {
597                                 if(selected==0 || key->flag & PEK_SELECT)
598                                         if(key_inside_circle(data, data->rad, KEY_WCO, &data->dist))
599                                                 func(data, mat, imat, p, k, key);
600                         }
601                 }
602         }
603 }
604
605 static void foreach_selected_point(PEData *data, ForPointFunc func)
606 {
607         PTCacheEdit *edit = data->edit;
608         POINT_P;
609
610         LOOP_SELECTED_POINTS {
611                 func(data, p);
612         }
613 }
614
615 static void foreach_selected_key(PEData *data, ForKeyFunc func)
616 {
617         PTCacheEdit *edit = data->edit;
618         POINT_P; KEY_K;
619
620         LOOP_VISIBLE_POINTS {
621                 LOOP_SELECTED_KEYS {
622                         func(data, p, k);
623                 }
624         }
625 }
626
627 static void foreach_point(PEData *data, ForPointFunc func)
628 {
629         PTCacheEdit *edit = data->edit;
630         POINT_P;
631
632         LOOP_POINTS { 
633                 func(data, p);
634         }
635 }
636
637 static int count_selected_keys(Scene *scene, PTCacheEdit *edit)
638 {
639         ParticleEditSettings *pset= PE_settings(scene);
640         POINT_P; KEY_K;
641         int sel= 0;
642
643         LOOP_VISIBLE_POINTS {
644                 if(pset->selectmode==SCE_SELECT_POINT) {
645                         LOOP_SELECTED_KEYS {
646                                 sel++;
647                         }
648                 }
649                 else if(pset->selectmode==SCE_SELECT_END) {
650                         key = point->keys + point->totkey - 1;
651                         if(key->flag & PEK_SELECT)
652                                 sel++;
653                 }
654         }
655
656         return sel;
657 }
658
659 /************************************************/
660 /*                      Particle Edit Mirroring                         */
661 /************************************************/
662
663 static void PE_update_mirror_cache(Object *ob, ParticleSystem *psys)
664 {
665         PTCacheEdit *edit;
666         ParticleSystemModifierData *psmd;
667         KDTree *tree;
668         KDTreeNearest nearest;
669         HairKey *key;
670         PARTICLE_P;
671         float mat[4][4], co[3];
672         int index, totpart;
673
674         edit= psys->edit;
675         psmd= psys_get_modifier(ob, psys);
676         totpart= psys->totpart;
677
678         tree= BLI_kdtree_new(totpart);
679
680         /* insert particles into kd tree */
681         LOOP_PARTICLES {
682                 key = pa->hair;
683                 psys_mat_hair_to_orco(ob, psmd->dm, psys->part->from, pa, mat);
684                 VECCOPY(co, key->co);
685                 Mat4MulVecfl(mat, co);
686                 BLI_kdtree_insert(tree, p, co, NULL);
687         }
688
689         BLI_kdtree_balance(tree);
690
691         /* lookup particles and set in mirror cache */
692         if(!edit->mirror_cache)
693                 edit->mirror_cache= MEM_callocN(sizeof(int)*totpart, "PE mirror cache");
694         
695         LOOP_PARTICLES {
696                 key = pa->hair;
697                 psys_mat_hair_to_orco(ob, psmd->dm, psys->part->from, pa, mat);
698                 VECCOPY(co, key->co);
699                 Mat4MulVecfl(mat, co);
700                 co[0]= -co[0];
701
702                 index= BLI_kdtree_find_nearest(tree, co, NULL, &nearest);
703
704                 /* this needs a custom threshold still, duplicated for editmode mirror */
705                 if(index != -1 && index != p && (nearest.dist <= 0.0002f))
706                         edit->mirror_cache[p]= index;
707                 else
708                         edit->mirror_cache[p]= -1;
709         }
710
711         /* make sure mirrors are in two directions */
712         LOOP_PARTICLES {
713                 if(edit->mirror_cache[p]) {
714                         index= edit->mirror_cache[p];
715                         if(edit->mirror_cache[index] != p)
716                                 edit->mirror_cache[p]= -1;
717                 }
718         }
719
720         BLI_kdtree_free(tree);
721 }
722
723 static void PE_mirror_particle(Object *ob, DerivedMesh *dm, ParticleSystem *psys, ParticleData *pa, ParticleData *mpa)
724 {
725         HairKey *hkey, *mhkey;
726         PTCacheEditPoint *point, *mpoint;
727         PTCacheEditKey *key, *mkey;
728         PTCacheEdit *edit;
729         float mat[4][4], mmat[4][4], immat[4][4];
730         int i, mi, k;
731
732         edit= psys->edit;
733         i= pa - psys->particles;
734
735         /* find mirrored particle if needed */
736         if(!mpa) {
737                 if(!edit->mirror_cache)
738                         PE_update_mirror_cache(ob, psys);
739
740                 mi= edit->mirror_cache[i];
741                 if(mi == -1)
742                         return;
743                 mpa= psys->particles + mi;
744         }
745         else
746                 mi= mpa - psys->particles;
747
748         point = edit->points + i;
749         mpoint = edit->points + mi;
750
751         /* make sure they have the same amount of keys */
752         if(pa->totkey != mpa->totkey) {
753                 if(mpa->hair) MEM_freeN(mpa->hair);
754                 if(mpoint->keys) MEM_freeN(mpoint->keys);
755
756                 mpa->hair= MEM_dupallocN(pa->hair);
757                 mpoint->keys= MEM_dupallocN(point->keys);
758                 mpoint->totkey= point->totkey;
759
760                 mhkey= mpa->hair;
761                 mkey= mpoint->keys;
762                 for(k=0; k<mpa->totkey; k++, mkey++, mhkey++) {
763                         mkey->co= mhkey->co;
764                         mkey->time= &mhkey->time;
765                         mkey->flag &= PEK_SELECT;
766                 }
767         }
768
769         /* mirror positions and tags */
770         psys_mat_hair_to_orco(ob, dm, psys->part->from, pa, mat);
771         psys_mat_hair_to_orco(ob, dm, psys->part->from, mpa, mmat);
772         Mat4Invert(immat, mmat);
773
774         hkey=pa->hair;
775         mhkey=mpa->hair;
776         key= point->keys;
777         mkey= mpoint->keys;
778         for(k=0; k<pa->totkey; k++, hkey++, mhkey++, key++, mkey++) {
779                 VECCOPY(mhkey->co, hkey->co);
780                 Mat4MulVecfl(mat, mhkey->co);
781                 mhkey->co[0]= -mhkey->co[0];
782                 Mat4MulVecfl(immat, mhkey->co);
783
784                 if(key->flag & PEK_TAG)
785                         mkey->flag |= PEK_TAG;
786         }
787
788         if(point->flag & PEP_TAG)
789                 mpoint->flag |= PEP_TAG;
790         if(point->flag & PEP_EDIT_RECALC)
791                 mpoint->flag |= PEP_EDIT_RECALC;
792 }
793
794 static void PE_apply_mirror(Object *ob, ParticleSystem *psys)
795 {
796         PTCacheEdit *edit;
797         ParticleSystemModifierData *psmd;
798         POINT_P;
799
800         if(!psys)
801                 return;
802
803         edit= psys->edit;
804         psmd= psys_get_modifier(ob, psys);
805
806         /* we delay settings the PARS_EDIT_RECALC for mirrored particles
807          * to avoid doing mirror twice */
808         LOOP_POINTS {
809                 if(point->flag & PEP_EDIT_RECALC) {
810                         PE_mirror_particle(ob, psmd->dm, psys, psys->particles + p, NULL);
811
812                         if(edit->mirror_cache[p] != -1)
813                                 edit->points[edit->mirror_cache[p]].flag &= ~PEP_EDIT_RECALC;
814                 }
815         }
816
817         LOOP_POINTS {
818                 if(point->flag & PEP_EDIT_RECALC)
819                         if(edit->mirror_cache[p] != -1)
820                                 edit->points[edit->mirror_cache[p]].flag |= PEP_EDIT_RECALC;
821         }
822 }
823
824 /************************************************/
825 /*                      Edit Calculation                                        */
826 /************************************************/
827 /* tries to stop edited particles from going through the emitter's surface */
828 static void pe_deflect_emitter(Scene *scene, Object *ob, PTCacheEdit *edit)
829 {
830         ParticleEditSettings *pset= PE_settings(scene);
831         ParticleSystem *psys;
832         ParticleSystemModifierData *psmd;
833         POINT_P; KEY_K;
834         int index;
835         float *vec, *nor, dvec[3], dot, dist_1st;
836         float hairimat[4][4], hairmat[4][4];
837
838         if(edit==NULL || edit->psys==NULL || (pset->flag & PE_DEFLECT_EMITTER)==0 || (edit->psys->flag & PSYS_GLOBAL_HAIR))
839                 return;
840
841         psys = edit->psys;
842         psmd = psys_get_modifier(ob,psys);
843
844         LOOP_EDITED_POINTS {
845                 psys_mat_hair_to_object(ob, psmd->dm, psys->part->from, psys->particles + p, hairmat);
846         
847                 LOOP_KEYS {
848                         Mat4MulVecfl(hairmat, key->co);
849                 }
850
851                 LOOP_KEYS {
852                         if(k==0) {
853                                 dist_1st = VecLenf((key+1)->co, key->co);
854                                 dist_1st *= 0.75f * pset->emitterdist;
855                         }
856                         else {
857                                 index= BLI_kdtree_find_nearest(edit->emitter_field,key->co,NULL,NULL);
858                                 
859                                 vec=edit->emitter_cosnos +index*6;
860                                 nor=vec+3;
861
862                                 VecSubf(dvec, key->co, vec);
863
864                                 dot=Inpf(dvec,nor);
865                                 VECCOPY(dvec,nor);
866
867                                 if(dot>0.0f) {
868                                         if(dot<dist_1st) {
869                                                 Normalize(dvec);
870                                                 VecMulf(dvec,dist_1st-dot);
871                                                 VecAddf(key->co,key->co,dvec);
872                                         }
873                                 }
874                                 else {
875                                         Normalize(dvec);
876                                         VecMulf(dvec,dist_1st-dot);
877                                         VecAddf(key->co,key->co,dvec);
878                                 }
879                                 if(k==1)
880                                         dist_1st*=1.3333f;
881                         }
882                 }
883                 
884                 Mat4Invert(hairimat,hairmat);
885
886                 LOOP_KEYS {
887                         Mat4MulVecfl(hairimat, key->co);
888                 }
889         }
890 }
891 /* force set distances between neighbouring keys */
892 void PE_apply_lengths(Scene *scene, PTCacheEdit *edit)
893 {
894         
895         ParticleEditSettings *pset=PE_settings(scene);
896         POINT_P; KEY_K;
897         float dv1[3];
898
899         if(edit==0 || (pset->flag & PE_KEEP_LENGTHS)==0)
900                 return;
901
902         if(edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR)
903                 return;
904
905         LOOP_EDITED_POINTS {
906                 LOOP_KEYS {
907                         if(k) {
908                                 VecSubf(dv1, key->co, (key - 1)->co);
909                                 Normalize(dv1);
910                                 VecMulf(dv1, (key - 1)->length);
911                                 VecAddf(key->co, (key - 1)->co, dv1);
912                         }
913                 }
914         }
915 }
916 /* try to find a nice solution to keep distances between neighbouring keys */
917 static void pe_iterate_lengths(Scene *scene, PTCacheEdit *edit)
918 {
919         ParticleEditSettings *pset=PE_settings(scene);
920         POINT_P;
921         PTCacheEditKey *key;
922         int j, k;
923         float tlen;
924         float dv0[3]= {0.0f, 0.0f, 0.0f};
925         float dv1[3]= {0.0f, 0.0f, 0.0f};
926         float dv2[3]= {0.0f, 0.0f, 0.0f};
927
928         if(edit==0 || (pset->flag & PE_KEEP_LENGTHS)==0)
929                 return;
930
931         if(edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR)
932                 return;
933
934         LOOP_EDITED_POINTS {
935                 for(j=1; j<point->totkey; j++) {
936                         float mul= 1.0f / (float)point->totkey;
937
938                         if(pset->flag & PE_LOCK_FIRST) {
939                                 key= point->keys + 1;
940                                 k= 1;
941                                 dv1[0]= dv1[1]= dv1[2]= 0.0;
942                         }
943                         else {
944                                 key= point->keys;
945                                 k= 0;
946                                 dv0[0]= dv0[1]= dv0[2]= 0.0;
947                         }
948
949                         for(; k<point->totkey; k++, key++) {
950                                 if(k) {
951                                         VecSubf(dv0, (key - 1)->co, key->co);
952                                         tlen= Normalize(dv0);
953                                         VecMulf(dv0, (mul * (tlen - (key - 1)->length)));
954                                 }
955
956                                 if(k < point->totkey - 1) {
957                                         VecSubf(dv2, (key + 1)->co, key->co);
958                                         tlen= Normalize(dv2);
959                                         VecMulf(dv2, mul * (tlen - key->length));
960                                 }
961
962                                 if(k) {
963                                         VecAddf((key-1)->co,(key-1)->co,dv1);
964                                 }
965
966                                 VECADD(dv1,dv0,dv2);
967                         }
968                 }
969         }
970 }
971 /* set current distances to be kept between neighbouting keys */
972 static void recalc_lengths(PTCacheEdit *edit)
973 {
974         POINT_P; KEY_K;
975
976         if(edit==0)
977                 return;
978
979         LOOP_EDITED_POINTS {
980                 key= point->keys;
981                 for(k=0; k<point->totkey-1; k++, key++) {
982                         key->length= VecLenf(key->co, (key + 1)->co);
983                 }
984         }
985 }
986
987 /* calculate a tree for finding nearest emitter's vertice */
988 static void recalc_emitter_field(Object *ob, ParticleSystem *psys)
989 {
990         DerivedMesh *dm=psys_get_modifier(ob,psys)->dm;
991         PTCacheEdit *edit= psys->edit;
992         MFace *mface;
993         MVert *mvert;
994         float *vec, *nor;
995         int i, totface, totvert;
996
997         if(edit->emitter_cosnos)
998                 MEM_freeN(edit->emitter_cosnos);
999
1000         BLI_kdtree_free(edit->emitter_field);
1001
1002         totface=dm->getNumFaces(dm);
1003         totvert=dm->getNumVerts(dm);
1004
1005         edit->emitter_cosnos=MEM_callocN(totface*6*sizeof(float),"emitter cosnos");
1006
1007         edit->emitter_field= BLI_kdtree_new(totface);
1008
1009         vec=edit->emitter_cosnos;
1010         nor=vec+3;
1011
1012         mvert=dm->getVertDataArray(dm,CD_MVERT);
1013         for(i=0; i<totface; i++, vec+=6, nor+=6) {
1014                 mface=dm->getFaceData(dm,i,CD_MFACE);
1015
1016                 mvert=dm->getVertData(dm,mface->v1,CD_MVERT);
1017                 VECCOPY(vec,mvert->co);
1018                 VECCOPY(nor,mvert->no);
1019
1020                 mvert=dm->getVertData(dm,mface->v2,CD_MVERT);
1021                 VECADD(vec,vec,mvert->co);
1022                 VECADD(nor,nor,mvert->no);
1023
1024                 mvert=dm->getVertData(dm,mface->v3,CD_MVERT);
1025                 VECADD(vec,vec,mvert->co);
1026                 VECADD(nor,nor,mvert->no);
1027
1028                 if(mface->v4) {
1029                         mvert=dm->getVertData(dm,mface->v4,CD_MVERT);
1030                         VECADD(vec,vec,mvert->co);
1031                         VECADD(nor,nor,mvert->no);
1032                         
1033                         VecMulf(vec,0.25);
1034                 }
1035                 else
1036                         VecMulf(vec,0.3333f);
1037
1038                 Normalize(nor);
1039
1040                 BLI_kdtree_insert(edit->emitter_field, i, vec, NULL);
1041         }
1042
1043         BLI_kdtree_balance(edit->emitter_field);
1044 }
1045
1046 static void PE_update_selection(Scene *scene, Object *ob, int useflag)
1047 {
1048         PTCacheEdit *edit= PE_get_current(scene, ob);
1049         HairKey *hkey;
1050         POINT_P; KEY_K;
1051
1052         /* flag all particles to be updated if not using flag */
1053         if(!useflag)
1054                 LOOP_POINTS
1055                         point->flag |= PEP_EDIT_RECALC;
1056
1057         /* flush edit key flag to hair key flag to preserve selection 
1058          * on save */
1059         if(edit->psys) LOOP_POINTS {
1060                 hkey = edit->psys->particles[p].hair;
1061                 LOOP_KEYS {
1062                         hkey->editflag= key->flag;
1063                         hkey++;
1064                 }
1065         }
1066
1067         psys_cache_edit_paths(scene, ob, edit, CFRA);
1068
1069
1070         /* disable update flag */
1071         LOOP_POINTS
1072                 point->flag &= ~PEP_EDIT_RECALC;
1073 }
1074
1075 static void update_world_cos(Object *ob, PTCacheEdit *edit)
1076 {
1077         ParticleSystem *psys = edit->psys;
1078         ParticleSystemModifierData *psmd= psys_get_modifier(ob, psys);
1079         POINT_P; KEY_K;
1080         float hairmat[4][4];
1081
1082         if(psys==0 || psys->edit==0)
1083                 return;
1084
1085         LOOP_POINTS {
1086                 if(!(psys->flag & PSYS_GLOBAL_HAIR))
1087                         psys_mat_hair_to_global(ob, psmd->dm, psys->part->from, psys->particles+p, hairmat);
1088
1089                 LOOP_KEYS {
1090                         VECCOPY(key->world_co,key->co);
1091                         if(!(psys->flag & PSYS_GLOBAL_HAIR))
1092                                 Mat4MulVecfl(hairmat, key->world_co);
1093                 }
1094         }
1095 }
1096 static void update_velocities(Object *ob, PTCacheEdit *edit)
1097 {
1098         /*TODO: get frs_sec properly */
1099         float vec1[3], vec2[3], frs_sec, dfra;
1100         POINT_P; KEY_K;
1101
1102         /* hair doesn't use velocities */
1103         if(edit->psys || !edit->points || !edit->points->keys->vel)
1104                 return;
1105
1106         frs_sec = edit->pid.flag & PTCACHE_VEL_PER_SEC ? 25.0f : 1.0f;
1107
1108         LOOP_EDITED_POINTS {
1109                 LOOP_KEYS {
1110                         if(k==0) {
1111                                 dfra = *(key+1)->time - *key->time;
1112
1113                                 if(dfra <= 0.0f)
1114                                         continue;
1115
1116                                 VECSUB(key->vel, (key+1)->co, key->co);
1117
1118                                 if(point->totkey>2) {
1119                                         VECSUB(vec1, (key+1)->co, (key+2)->co);
1120                                         Projf(vec2, vec1, key->vel);
1121                                         VECSUB(vec2, vec1, vec2);
1122                                         VECADDFAC(key->vel, key->vel, vec2, 0.5f);
1123                                 }
1124                         }
1125                         else if(k==point->totkey-1) {
1126                                 dfra = *key->time - *(key-1)->time;
1127
1128                                 if(dfra <= 0.0f)
1129                                         continue;
1130
1131                                 VECSUB(key->vel, key->co, (key-1)->co);
1132
1133                                 if(point->totkey>2) {
1134                                         VECSUB(vec1, (key-2)->co, (key-1)->co);
1135                                         Projf(vec2, vec1, key->vel);
1136                                         VECSUB(vec2, vec1, vec2);
1137                                         VECADDFAC(key->vel, key->vel, vec2, 0.5f);
1138                                 }
1139                         }
1140                         else {
1141                                 dfra = *(key+1)->time - *(key-1)->time;
1142                                 
1143                                 if(dfra <= 0.0f)
1144                                         continue;
1145
1146                                 VECSUB(key->vel, (key+1)->co, (key-1)->co);
1147                         }
1148                         VecMulf(key->vel, frs_sec/dfra);
1149                 }
1150         }
1151 }
1152 void PE_update_object(Scene *scene, Object *ob, int useflag)
1153 {
1154         ParticleEditSettings *pset= PE_settings(scene);
1155         PTCacheEdit *edit = PE_get_current(scene, ob);
1156         POINT_P;
1157
1158         if(!edit)
1159                 return;
1160
1161         /* flag all particles to be updated if not using flag */
1162         if(!useflag)
1163                 LOOP_POINTS {
1164                         point->flag |= PEP_EDIT_RECALC;
1165                 }
1166
1167         /* do post process on particle edit keys */
1168         pe_iterate_lengths(scene, edit);
1169         pe_deflect_emitter(scene, ob, edit);
1170         PE_apply_lengths(scene, edit);
1171         if(pset->flag & PE_X_MIRROR)
1172                 PE_apply_mirror(ob,edit->psys);
1173         if(edit->psys)
1174                 update_world_cos(ob, edit);
1175         if(pset->flag & PE_AUTO_VELOCITY)
1176                 update_velocities(ob, edit);
1177         PE_hide_keys_time(scene, edit, CFRA);
1178
1179         /* regenerate path caches */
1180         psys_cache_edit_paths(scene, ob, edit, CFRA);
1181
1182         /* disable update flag */
1183         LOOP_POINTS {
1184                 point->flag &= ~PEP_EDIT_RECALC;
1185         }
1186
1187         if(edit->psys)
1188                 edit->psys->flag &= ~PSYS_HAIR_UPDATED;
1189
1190         DAG_id_flush_update(&ob->id, OB_RECALC_DATA);
1191 }
1192
1193 /************************************************/
1194 /*                      Edit Selections                                         */
1195 /************************************************/
1196
1197 /*-----selection callbacks-----*/
1198
1199 static void select_key(PEData *data, int point_index, int key_index)
1200 {
1201         PTCacheEdit *edit = data->edit;
1202         PTCacheEditPoint *point = edit->points + point_index;
1203         PTCacheEditKey *key = point->keys + key_index;
1204
1205         if(data->select)
1206                 key->flag |= PEK_SELECT;
1207         else
1208                 key->flag &= ~PEK_SELECT;
1209
1210         point->flag |= PEP_EDIT_RECALC;
1211 }
1212
1213 static void select_keys(PEData *data, int point_index, int key_index)
1214 {
1215         PTCacheEdit *edit = data->edit;
1216         PTCacheEditPoint *point = edit->points + point_index;
1217         KEY_K;
1218
1219         LOOP_KEYS {
1220                 if(data->select)
1221                         key->flag |= PEK_SELECT;
1222                 else
1223                         key->flag &= ~PEK_SELECT;
1224         }
1225
1226         point->flag |= PEP_EDIT_RECALC;
1227 }
1228
1229 static void toggle_key_select(PEData *data, int point_index, int key_index)
1230 {
1231         PTCacheEdit *edit = data->edit;
1232         PTCacheEditPoint *point = edit->points + point_index;
1233         PTCacheEditKey *key = point->keys + key_index;
1234
1235         key->flag ^= PEK_SELECT;
1236         point->flag |= PEP_EDIT_RECALC;
1237 }
1238
1239 /************************ de select all operator ************************/
1240
1241 static int de_select_all_exec(bContext *C, wmOperator *op)
1242 {
1243         Scene *scene= CTX_data_scene(C);
1244         Object *ob= CTX_data_active_object(C);
1245         PTCacheEdit *edit= PE_get_current(scene, ob);
1246         POINT_P; KEY_K;
1247         int sel= 0;
1248         
1249         LOOP_VISIBLE_POINTS {
1250                 LOOP_SELECTED_KEYS {
1251                         sel= 1;
1252                         key->flag &= ~PEK_SELECT;
1253                         point->flag |= PEP_EDIT_RECALC;
1254                 }
1255         }
1256
1257         if(sel==0) {
1258                 LOOP_VISIBLE_POINTS {
1259                         LOOP_KEYS {
1260                                 if(!(key->flag & PEK_SELECT)) {
1261                                         key->flag |= PEK_SELECT;
1262                                         point->flag |= PEP_EDIT_RECALC;
1263                                 }
1264                         }
1265                 }
1266         }
1267
1268         PE_update_selection(scene, ob, 1);
1269         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, ob);
1270
1271         return OPERATOR_FINISHED;
1272 }
1273
1274 void PARTICLE_OT_select_all_toggle(wmOperatorType *ot)
1275 {
1276         /* identifiers */
1277         ot->name= "Select or Deselect All";
1278         ot->idname= "PARTICLE_OT_select_all_toggle";
1279         
1280         /* api callbacks */
1281         ot->exec= de_select_all_exec;
1282         ot->poll= PE_poll;
1283
1284         /* flags */
1285         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1286 }
1287
1288 /************************ pick select operator ************************/
1289
1290 int PE_mouse_particles(bContext *C, short *mval, int extend)
1291 {
1292         PEData data;
1293         Scene *scene= CTX_data_scene(C);
1294         Object *ob= CTX_data_active_object(C);
1295         PTCacheEdit *edit= PE_get_current(scene, ob);
1296         POINT_P; KEY_K;
1297         
1298         if(!PE_start_edit(edit))
1299                 return OPERATOR_CANCELLED;
1300
1301         if(!extend) {
1302                 LOOP_VISIBLE_POINTS {
1303                         LOOP_SELECTED_KEYS {
1304                                 key->flag &= ~PEK_SELECT;
1305                                 point->flag |= PEP_EDIT_RECALC;
1306                         }
1307                 }
1308         }
1309
1310         PE_set_view3d_data(C, &data);
1311         data.mval= mval;
1312         data.rad= 75.0f;
1313
1314         for_mouse_hit_keys(&data, toggle_key_select, 1);  /* nearest only */
1315
1316         PE_update_selection(scene, ob, 1);
1317         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, data.ob);
1318
1319         return OPERATOR_FINISHED;
1320 }
1321
1322 /************************ select first operator ************************/
1323
1324 static void select_root(PEData *data, int point_index)
1325 {
1326         data->edit->points[point_index].keys->flag |= PEK_SELECT;
1327 }
1328
1329 static int select_first_exec(bContext *C, wmOperator *op)
1330 {
1331         PEData data;
1332
1333         PE_set_data(C, &data);
1334         foreach_point(&data, select_root);
1335         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, data.ob);
1336
1337         return OPERATOR_FINISHED;
1338 }
1339
1340 void PARTICLE_OT_select_first(wmOperatorType *ot)
1341 {
1342         /* identifiers */
1343         ot->name= "Select First";
1344         ot->idname= "PARTICLE_OT_select_first";
1345         
1346         /* api callbacks */
1347         ot->exec= select_first_exec;
1348         ot->poll= PE_poll;
1349
1350         /* flags */
1351         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1352 }
1353
1354 /************************ select last operator ************************/
1355
1356 static void select_tip(PEData *data, int point_index)
1357 {
1358         PTCacheEditPoint *point = data->edit->points + point_index;
1359         point->keys[point->totkey - 1].flag |= PEK_SELECT;
1360 }
1361
1362 static int select_last_exec(bContext *C, wmOperator *op)
1363 {
1364         PEData data;
1365
1366         PE_set_data(C, &data);
1367         foreach_point(&data, select_tip);
1368         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, data.ob);
1369
1370         return OPERATOR_FINISHED;
1371 }
1372
1373 void PARTICLE_OT_select_last(wmOperatorType *ot)
1374 {
1375         /* identifiers */
1376         ot->name= "Select Last";
1377         ot->idname= "PARTICLE_OT_select_last";
1378         
1379         /* api callbacks */
1380         ot->exec= select_last_exec;
1381         ot->poll= PE_poll;
1382
1383         /* flags */
1384         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1385 }
1386
1387 /************************ select linked operator ************************/
1388
1389 static int select_linked_exec(bContext *C, wmOperator *op)
1390 {
1391         PEData data;
1392         short mval[2];
1393         int location[2];
1394
1395         RNA_int_get_array(op->ptr, "location", location);
1396         mval[0]= location[0];
1397         mval[1]= location[1];
1398
1399         view3d_operator_needs_opengl(C);
1400
1401         PE_set_view3d_data(C, &data);
1402         data.mval= mval;
1403         data.rad=75.0f;
1404         data.select= !RNA_boolean_get(op->ptr, "deselect");
1405
1406         for_mouse_hit_keys(&data, select_keys, 1);  /* nearest only */
1407         PE_update_selection(data.scene, data.ob, 1);
1408         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, data.ob);
1409
1410         return OPERATOR_FINISHED;
1411 }
1412
1413 static int select_linked_invoke(bContext *C, wmOperator *op, wmEvent *event)
1414 {
1415         ARegion *ar= CTX_wm_region(C);
1416         int location[2];
1417
1418         location[0]= event->x - ar->winrct.xmin;
1419         location[1]= event->y - ar->winrct.ymin;
1420         RNA_int_set_array(op->ptr, "location", location);
1421
1422         return select_linked_exec(C, op);
1423 }
1424
1425 void PARTICLE_OT_select_linked(wmOperatorType *ot)
1426 {
1427         /* identifiers */
1428         ot->name= "Select Linked";
1429         ot->idname= "PARTICLE_OT_select_linked";
1430         
1431         /* api callbacks */
1432         ot->exec= select_linked_exec;
1433         ot->invoke= select_linked_invoke;
1434         ot->poll= PE_poll_3dview;
1435
1436         /* flags */
1437         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1438
1439         /* properties */
1440         RNA_def_boolean(ot->srna, "deselect", 0, "Deselect", "Deselect linked keys rather than selecting them.");
1441         RNA_def_int_vector(ot->srna, "location", 2, NULL, 0, INT_MAX, "Location", "", 0, 16384);
1442 }
1443
1444 /************************ border select operator ************************/
1445
1446 int PE_border_select(bContext *C, rcti *rect, int select)
1447 {
1448         Scene *scene= CTX_data_scene(C);
1449         Object *ob= CTX_data_active_object(C);
1450         PTCacheEdit *edit= PE_get_current(scene, ob);
1451         PEData data;
1452
1453         if(!PE_start_edit(edit))
1454                 return OPERATOR_CANCELLED;
1455
1456         PE_set_view3d_data(C, &data);
1457         data.rect= rect;
1458         data.select= select;
1459
1460         for_mouse_hit_keys(&data, select_key, 0);
1461
1462         PE_update_selection(scene, ob, 1);
1463         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, ob);
1464
1465         return OPERATOR_FINISHED;
1466 }
1467
1468 /************************ circle select operator ************************/
1469
1470 int PE_circle_select(bContext *C, int selecting, short *mval, float rad)
1471 {
1472         Scene *scene= CTX_data_scene(C);
1473         Object *ob= CTX_data_active_object(C);
1474         PTCacheEdit *edit= PE_get_current(scene, ob);
1475         PEData data;
1476
1477         if(!PE_start_edit(edit))
1478                 return OPERATOR_FINISHED;
1479
1480         PE_set_view3d_data(C, &data);
1481         data.mval= mval;
1482         data.rad= rad;
1483         data.select= selecting;
1484
1485         for_mouse_hit_keys(&data, select_key, 0);
1486
1487         PE_update_selection(scene, ob, 1);
1488         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, ob);
1489
1490         return OPERATOR_FINISHED;
1491 }
1492
1493 /************************ lasso select operator ************************/
1494
1495 int PE_lasso_select(bContext *C, short mcords[][2], short moves, short select)
1496 {
1497         Scene *scene= CTX_data_scene(C);
1498         Object *ob= CTX_data_active_object(C);
1499         ARegion *ar= CTX_wm_region(C);
1500         ParticleEditSettings *pset= PE_settings(scene);
1501         PTCacheEdit *edit = PE_get_current(scene, ob);
1502         ParticleSystem *psys = edit->psys;
1503         ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
1504         POINT_P; KEY_K;
1505         float co[3], mat[4][4];
1506         short vertco[2];
1507
1508         if(!PE_start_edit(edit))
1509                 return OPERATOR_CANCELLED;
1510
1511         Mat4One(mat);
1512
1513         LOOP_VISIBLE_POINTS {
1514                 if(edit->psys && !(psys->flag & PSYS_GLOBAL_HAIR))
1515                         psys_mat_hair_to_global(ob, psmd->dm, psys->part->from, psys->particles + p, mat);
1516
1517                 if(pset->selectmode==SCE_SELECT_POINT) {
1518                         LOOP_KEYS {
1519                                 VECCOPY(co, key->co);
1520                                 Mat4MulVecfl(mat, co);
1521                                 project_short(ar, co, vertco);
1522                                 if((vertco[0] != IS_CLIPPED) && lasso_inside(mcords,moves,vertco[0],vertco[1])) {
1523                                         if(select && !(key->flag & PEK_SELECT)) {
1524                                                 key->flag |= PEK_SELECT;
1525                                                 point->flag |= PEP_EDIT_RECALC;
1526                                         }
1527                                         else if(key->flag & PEK_SELECT) {
1528                                                 key->flag &= ~PEK_SELECT;
1529                                                 point->flag |= PEP_EDIT_RECALC;
1530                                         }
1531                                 }
1532                         }
1533                 }
1534                 else if(pset->selectmode==SCE_SELECT_END) {
1535                         key= point->keys + point->totkey - 1;
1536
1537                         VECCOPY(co, key->co);
1538                         Mat4MulVecfl(mat, co);
1539                         project_short(ar, co,vertco);
1540                         if((vertco[0] != IS_CLIPPED) && lasso_inside(mcords,moves,vertco[0],vertco[1])) {
1541                                 if(select && !(key->flag & PEK_SELECT)) {
1542                                         key->flag |= PEK_SELECT;
1543                                         point->flag |= PEP_EDIT_RECALC;
1544                                 }
1545                                 else if(key->flag & PEK_SELECT) {
1546                                         key->flag &= ~PEK_SELECT;
1547                                         point->flag |= PEP_EDIT_RECALC;
1548                                 }
1549                         }
1550                 }
1551         }
1552
1553         PE_update_selection(scene, ob, 1);
1554         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, ob);
1555
1556         return OPERATOR_FINISHED;
1557 }
1558
1559 /*************************** hide operator **************************/
1560
1561 static int hide_exec(bContext *C, wmOperator *op)
1562 {
1563         Object *ob= CTX_data_active_object(C);
1564         Scene *scene= CTX_data_scene(C);
1565         PTCacheEdit *edit= PE_get_current(scene, ob);
1566         POINT_P; KEY_K;
1567         
1568         if(RNA_enum_get(op->ptr, "unselected")) {
1569                 LOOP_UNSELECTED_POINTS {
1570                         point->flag |= PEP_HIDE;
1571                         point->flag |= PEP_EDIT_RECALC;
1572
1573                         LOOP_KEYS
1574                                 key->flag &= ~PEK_SELECT;
1575                 }
1576         }
1577         else {
1578                 LOOP_SELECTED_POINTS {
1579                         point->flag |= PEP_HIDE;
1580                         point->flag |= PEP_EDIT_RECALC;
1581
1582                         LOOP_KEYS
1583                                 key->flag &= ~PEK_SELECT;
1584                 }
1585         }
1586
1587         PE_update_selection(scene, ob, 1);
1588         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, ob);
1589
1590         return OPERATOR_FINISHED;
1591 }
1592
1593 void PARTICLE_OT_hide(wmOperatorType *ot)
1594 {
1595         /* identifiers */
1596         ot->name= "Hide Selected";
1597         ot->idname= "PARTICLE_OT_hide";
1598         
1599         /* api callbacks */
1600         ot->exec= hide_exec;
1601         ot->poll= PE_poll;
1602
1603         /* flags */
1604         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1605
1606         /* props */
1607         RNA_def_boolean(ot->srna, "unselected", 0, "Unselected", "Hide unselected rather than selected.");
1608 }
1609
1610 /*************************** reveal operator **************************/
1611
1612 static int reveal_exec(bContext *C, wmOperator *op)
1613 {
1614         Object *ob= CTX_data_active_object(C);
1615         Scene *scene= CTX_data_scene(C);
1616         PTCacheEdit *edit= PE_get_current(scene, ob);
1617         POINT_P; KEY_K;
1618
1619         LOOP_POINTS {
1620                 if(point->flag & PEP_HIDE) {
1621                         point->flag &= ~PEP_HIDE;
1622                         point->flag |= PEP_EDIT_RECALC;
1623
1624                         LOOP_KEYS
1625                                 key->flag |= PEK_SELECT;
1626                 }
1627         }
1628
1629         PE_update_selection(scene, ob, 1);
1630         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, ob);
1631
1632         return OPERATOR_FINISHED;
1633 }
1634
1635 void PARTICLE_OT_reveal(wmOperatorType *ot)
1636 {
1637         /* identifiers */
1638         ot->name= "Reveal";
1639         ot->idname= "PARTICLE_OT_reveal";
1640         
1641         /* api callbacks */
1642         ot->exec= reveal_exec;
1643         ot->poll= PE_poll;
1644
1645         /* flags */
1646         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1647 }
1648
1649 /************************ select less operator ************************/
1650
1651 static void select_less_keys(PEData *data, int point_index)
1652 {
1653         PTCacheEdit *edit= data->edit;
1654         PTCacheEditPoint *point = edit->points + point_index;
1655         KEY_K;
1656
1657         LOOP_SELECTED_KEYS {
1658                 if(k==0) {
1659                         if(((key+1)->flag&PEK_SELECT)==0)
1660                                 key->flag |= PEK_TAG;
1661                 }
1662                 else if(k==point->totkey-1) {
1663                         if(((key-1)->flag&PEK_SELECT)==0)
1664                                 key->flag |= PEK_TAG;
1665                 }
1666                 else {
1667                         if((((key-1)->flag & (key+1)->flag) & PEK_SELECT)==0)
1668                                 key->flag |= PEK_TAG;
1669                 }
1670         }
1671
1672         LOOP_KEYS {
1673                 if(key->flag&PEK_TAG)
1674                         key->flag &= ~(PEK_TAG|PEK_SELECT);
1675         }
1676 }
1677
1678 static int select_less_exec(bContext *C, wmOperator *op)
1679 {
1680         PEData data;
1681
1682         PE_set_data(C, &data);
1683         foreach_point(&data, select_less_keys);
1684         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, data.ob);
1685
1686         return OPERATOR_FINISHED;
1687 }
1688
1689 void PARTICLE_OT_select_less(wmOperatorType *ot)
1690 {
1691         /* identifiers */
1692         ot->name= "Select Less";
1693         ot->idname= "PARTICLE_OT_select_less";
1694         
1695         /* api callbacks */
1696         ot->exec= select_less_exec;
1697         ot->poll= PE_poll;
1698
1699         /* flags */
1700         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1701 }
1702
1703 /************************ select more operator ************************/
1704
1705 static void select_more_keys(PEData *data, int point_index)
1706 {
1707         PTCacheEdit *edit= data->edit;
1708         PTCacheEditPoint *point = edit->points + point_index;
1709         KEY_K;
1710
1711         LOOP_KEYS {
1712                 if(key->flag & PEK_SELECT) continue;
1713
1714                 if(k==0) {
1715                         if((key+1)->flag&PEK_SELECT)
1716                                 key->flag |= PEK_TAG;
1717                 }
1718                 else if(k==point->totkey-1) {
1719                         if((key-1)->flag&PEK_SELECT)
1720                                 key->flag |= PEK_TAG;
1721                 }
1722                 else {
1723                         if(((key-1)->flag | (key+1)->flag) & PEK_SELECT)
1724                                 key->flag |= PEK_TAG;
1725                 }
1726         }
1727
1728         LOOP_KEYS {
1729                 if(key->flag&PEK_TAG) {
1730                         key->flag &= ~PEK_TAG;
1731                         key->flag |= PEK_SELECT;
1732                 }
1733         }
1734 }
1735
1736 static int select_more_exec(bContext *C, wmOperator *op)
1737 {
1738         PEData data;
1739
1740         PE_set_data(C, &data);
1741         foreach_point(&data, select_more_keys);
1742         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_SELECT, data.ob);
1743
1744         return OPERATOR_FINISHED;
1745 }
1746
1747 void PARTICLE_OT_select_more(wmOperatorType *ot)
1748 {
1749         /* identifiers */
1750         ot->name= "Select More";
1751         ot->idname= "PARTICLE_OT_select_more";
1752         
1753         /* api callbacks */
1754         ot->exec= select_more_exec;
1755         ot->poll= PE_poll;
1756
1757         /* flags */
1758         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1759 }
1760
1761 /************************ rekey operator ************************/
1762
1763 static void rekey_particle(PEData *data, int pa_index)
1764 {
1765         PTCacheEdit *edit= data->edit;
1766         ParticleSystem *psys= edit->psys;
1767         ParticleSimulationData sim = {data->scene, data->ob, edit->psys, NULL};
1768         ParticleData *pa= psys->particles + pa_index;
1769         PTCacheEditPoint *point = edit->points + pa_index;
1770         ParticleKey state;
1771         HairKey *key, *new_keys, *okey;
1772         PTCacheEditKey *ekey;
1773         float dval, sta, end;
1774         int k;
1775
1776         pa->flag |= PARS_REKEY;
1777
1778         key= new_keys= MEM_callocN(data->totrekey * sizeof(HairKey),"Hair re-key keys");
1779
1780         okey = pa->hair;
1781         /* root and tip stay the same */
1782         VECCOPY(key->co, okey->co);
1783         VECCOPY((key + data->totrekey - 1)->co, (okey + pa->totkey - 1)->co);
1784
1785         sta= key->time= okey->time;
1786         end= (key + data->totrekey - 1)->time= (okey + pa->totkey - 1)->time;
1787         dval= (end - sta) / (float)(data->totrekey - 1);
1788
1789         /* interpolate new keys from old ones */
1790         for(k=1,key++; k<data->totrekey-1; k++,key++) {
1791                 state.time= (float)k / (float)(data->totrekey-1);
1792                 psys_get_particle_on_path(&sim, pa_index, &state, 0);
1793                 VECCOPY(key->co, state.co);
1794                 key->time= sta + k * dval;
1795         }
1796
1797         /* replace keys */
1798         if(pa->hair)
1799                 MEM_freeN(pa->hair);
1800         pa->hair= new_keys;
1801
1802         point->totkey=pa->totkey=data->totrekey;
1803
1804
1805         if(point->keys)
1806                 MEM_freeN(point->keys);
1807         ekey= point->keys= MEM_callocN(pa->totkey * sizeof(PTCacheEditKey),"Hair re-key edit keys");
1808                 
1809         for(k=0, key=pa->hair; k<pa->totkey; k++, key++, ekey++) {
1810                 ekey->co= key->co;
1811                 ekey->time= &key->time;
1812                 if(!(psys->flag & PSYS_GLOBAL_HAIR))
1813                         ekey->flag |= PEK_USE_WCO;
1814         }
1815
1816         pa->flag &= ~PARS_REKEY;
1817         point->flag |= PEP_EDIT_RECALC;
1818 }
1819
1820 static int rekey_exec(bContext *C, wmOperator *op)
1821 {
1822         PEData data;
1823
1824         PE_set_data(C, &data);
1825
1826         data.dval= 1.0f / (float)(data.totrekey-1);
1827         data.totrekey= RNA_int_get(op->ptr, "keys");
1828
1829         foreach_selected_point(&data, rekey_particle);
1830         
1831         recalc_lengths(data.edit);
1832         PE_update_object(data.scene, data.ob, 1);
1833         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_DATA, data.ob);
1834
1835         return OPERATOR_FINISHED;
1836 }
1837
1838 void PARTICLE_OT_rekey(wmOperatorType *ot)
1839 {
1840         /* identifiers */
1841         ot->name= "Rekey";
1842         ot->idname= "PARTICLE_OT_rekey";
1843         
1844         /* api callbacks */
1845         ot->exec= rekey_exec;
1846         ot->invoke= WM_operator_props_popup;
1847         ot->poll= PE_poll;
1848
1849         /* flags */
1850         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1851
1852         /* properties */
1853         RNA_def_int(ot->srna, "keys", 2, 2, INT_MAX, "Number of Keys", "", 2, 100);
1854 }
1855
1856 static void rekey_particle_to_time(Scene *scene, Object *ob, int pa_index, float path_time)
1857 {
1858         PTCacheEdit *edit= PE_get_current(scene, ob);
1859         ParticleSystem *psys;
1860         ParticleSimulationData sim = {scene, ob, edit ? edit->psys : NULL, NULL};
1861         ParticleData *pa;
1862         ParticleKey state;
1863         HairKey *new_keys, *key;
1864         PTCacheEditKey *ekey;
1865         int k;
1866
1867         if(!edit || !edit->psys) return;
1868
1869         psys = edit->psys;
1870
1871         pa= psys->particles + pa_index;
1872
1873         pa->flag |= PARS_REKEY;
1874
1875         key= new_keys= MEM_dupallocN(pa->hair);
1876         
1877         /* interpolate new keys from old ones (roots stay the same) */
1878         for(k=1, key++; k < pa->totkey; k++, key++) {
1879                 state.time= path_time * (float)k / (float)(pa->totkey-1);
1880                 psys_get_particle_on_path(&sim, pa_index, &state, 0);
1881                 VECCOPY(key->co, state.co);
1882         }
1883
1884         /* replace hair keys */
1885         if(pa->hair)
1886                 MEM_freeN(pa->hair);
1887         pa->hair= new_keys;
1888
1889         /* update edit pointers */
1890         for(k=0, key=pa->hair, ekey=edit->points[pa_index].keys; k<pa->totkey; k++, key++, ekey++) {
1891                 ekey->co= key->co;
1892                 ekey->time= &key->time;
1893         }
1894
1895         pa->flag &= ~PARS_REKEY;
1896 }
1897
1898 /************************* utilities **************************/
1899
1900 static int remove_tagged_particles(Scene *scene, Object *ob, ParticleSystem *psys)
1901 {
1902         PTCacheEdit *edit = psys->edit;
1903         ParticleEditSettings *pset= PE_settings(scene);
1904         ParticleData *pa, *npa=0, *new_pars=0;
1905         POINT_P;
1906         PTCacheEditPoint *npoint=0, *new_points=0;
1907         ParticleSystemModifierData *psmd;
1908         int i, totpart, new_totpart= psys->totpart, removed= 0;
1909
1910         if(pset->flag & PE_X_MIRROR) {
1911                 /* mirror tags */
1912                 psmd= psys_get_modifier(ob, psys);
1913                 totpart= psys->totpart;
1914
1915                 LOOP_TAGGED_POINTS {
1916                         PE_mirror_particle(ob, psmd->dm, psys, psys->particles + p, NULL);
1917                 }
1918         }
1919
1920         LOOP_TAGGED_POINTS {
1921                 new_totpart--;
1922                 removed++;
1923         }
1924
1925         if(new_totpart != psys->totpart) {
1926                 if(new_totpart) {
1927                         npa= new_pars= MEM_callocN(new_totpart * sizeof(ParticleData), "ParticleData array");
1928                         npoint= new_points= MEM_callocN(new_totpart * sizeof(PTCacheEditPoint), "PTCacheEditKey array");
1929                 }
1930
1931                 pa= psys->particles;
1932                 point= edit->points;
1933                 for(i=0; i<psys->totpart; i++, pa++, point++) {
1934                         if(point->flag & PEP_TAG) {
1935                                 if(point->keys)
1936                                         MEM_freeN(point->keys);
1937                                 if(pa->hair)
1938                                         MEM_freeN(pa->hair);
1939                         }
1940                         else {
1941                                 memcpy(npa, pa, sizeof(ParticleData));
1942                                 memcpy(npoint, point, sizeof(PTCacheEditPoint));
1943                                 npa++;
1944                                 npoint++;
1945                         }
1946                 }
1947
1948                 if(psys->particles) MEM_freeN(psys->particles);
1949                 psys->particles= new_pars;
1950
1951                 if(edit->points) MEM_freeN(edit->points);
1952                 edit->points= new_points;
1953
1954                 if(edit->mirror_cache) {
1955                         MEM_freeN(edit->mirror_cache);
1956                         edit->mirror_cache= NULL;
1957                 }
1958
1959                 edit->totpoint= psys->totpart= new_totpart;
1960         }
1961
1962         return removed;
1963 }
1964
1965 static void remove_tagged_keys(Scene *scene, Object *ob, ParticleSystem *psys)
1966 {
1967         PTCacheEdit *edit= psys->edit;
1968         ParticleEditSettings *pset= PE_settings(scene);
1969         ParticleData *pa;
1970         HairKey *hkey, *nhkey, *new_hkeys=0;
1971         POINT_P; KEY_K;
1972         ParticleSystemModifierData *psmd;
1973         short new_totkey;
1974
1975         if(pset->flag & PE_X_MIRROR) {
1976                 /* mirror key tags */
1977                 psmd= psys_get_modifier(ob, psys);
1978
1979                 LOOP_POINTS {
1980                         LOOP_TAGGED_KEYS {
1981                                 PE_mirror_particle(ob, psmd->dm, psys, psys->particles + p, NULL);
1982                                 break;
1983                         }
1984                 }
1985         }
1986
1987         LOOP_POINTS {
1988                 new_totkey= point->totkey;
1989                 LOOP_TAGGED_KEYS {
1990                         new_totkey--;
1991                 }
1992                 /* we can't have elements with less than two keys*/
1993                 if(new_totkey < 2)
1994                         point->flag |= PEP_TAG;
1995         }
1996         remove_tagged_particles(scene, ob, psys);
1997
1998         LOOP_POINTS {
1999                 pa = psys->particles + p;
2000                 new_totkey= pa->totkey;
2001
2002                 LOOP_TAGGED_KEYS {
2003                         new_totkey--;
2004                 }
2005
2006                 if(new_totkey != pa->totkey) {
2007                         hkey= pa->hair;
2008                         nhkey= new_hkeys= MEM_callocN(new_totkey*sizeof(HairKey), "HairKeys");
2009
2010                         LOOP_KEYS {
2011                                 while(key->flag & PEK_TAG && hkey < pa->hair + pa->totkey) {
2012                                         key++;
2013                                         hkey++;
2014                                 }
2015
2016                                 if(hkey < pa->hair + pa->totkey) {
2017                                         VECCOPY(nhkey->co, hkey->co);
2018                                         nhkey->time= hkey->time;
2019                                         nhkey->weight= hkey->weight;
2020                                 }
2021                                 hkey++;
2022                                 nhkey++;
2023                         }
2024                         if(pa->hair)
2025                                 MEM_freeN(pa->hair);
2026                         
2027                         pa->hair= new_hkeys;
2028
2029                         point->totkey= pa->totkey= new_totkey;
2030
2031                         if(point->keys)
2032                                 MEM_freeN(point->keys);
2033                         key= point->keys= MEM_callocN(new_totkey*sizeof(PTCacheEditKey), "particle edit keys");
2034
2035                         hkey = pa->hair;
2036                         LOOP_KEYS {
2037                                 key->co= hkey->co;
2038                                 key->time= &hkey->time;
2039                                 hkey++;
2040                         }
2041                 }
2042         }
2043 }
2044
2045 /************************ subdivide opertor *********************/
2046
2047 /* works like normal edit mode subdivide, inserts keys between neighbouring selected keys */
2048 static void subdivide_particle(PEData *data, int pa_index)
2049 {
2050         PTCacheEdit *edit= data->edit;
2051         ParticleSystem *psys= edit->psys;
2052         ParticleSimulationData sim = {data->scene, data->ob, edit->psys, NULL};
2053         ParticleData *pa= psys->particles + pa_index;
2054         PTCacheEditPoint *point = edit->points + pa_index;
2055         ParticleKey state;
2056         HairKey *key, *nkey, *new_keys;
2057         PTCacheEditKey *ekey, *nekey, *new_ekeys;
2058
2059         int k;
2060         short totnewkey=0;
2061         float endtime;
2062
2063         for(k=0, ekey=point->keys; k<pa->totkey-1; k++,ekey++) {
2064                 if(ekey->flag&PEK_SELECT && (ekey+1)->flag&PEK_SELECT)
2065                         totnewkey++;
2066         }
2067
2068         if(totnewkey==0) return;
2069
2070         pa->flag |= PARS_REKEY;
2071
2072         nkey= new_keys= MEM_callocN((pa->totkey+totnewkey)*(sizeof(HairKey)),"Hair subdivide keys");
2073         nekey= new_ekeys= MEM_callocN((pa->totkey+totnewkey)*(sizeof(PTCacheEditKey)),"Hair subdivide edit keys");
2074         
2075         key = pa->hair;
2076         endtime= key[pa->totkey-1].time;
2077
2078         for(k=0, ekey=point->keys; k<pa->totkey-1; k++, key++, ekey++) {
2079
2080                 memcpy(nkey,key,sizeof(HairKey));
2081                 memcpy(nekey,ekey,sizeof(PTCacheEditKey));
2082
2083                 nekey->co= nkey->co;
2084                 nekey->time= &nkey->time;
2085
2086                 nkey++;
2087                 nekey++;
2088
2089                 if(ekey->flag & PEK_SELECT && (ekey+1)->flag & PEK_SELECT) {
2090                         nkey->time= (key->time + (key+1)->time)*0.5f;
2091                         state.time= (endtime != 0.0f)? nkey->time/endtime: 0.0f;
2092                         psys_get_particle_on_path(&sim, pa_index, &state, 0);
2093                         VECCOPY(nkey->co, state.co);
2094
2095                         nekey->co= nkey->co;
2096                         nekey->time= &nkey->time;
2097                         nekey->flag |= PEK_SELECT;
2098                         if(!(psys->flag & PSYS_GLOBAL_HAIR))
2099                                 nekey->flag |= PEK_USE_WCO;
2100
2101                         nekey++;
2102                         nkey++;
2103                 }
2104         }
2105         /*tip still not copied*/
2106         memcpy(nkey,key,sizeof(HairKey));
2107         memcpy(nekey,ekey,sizeof(PTCacheEditKey));
2108
2109         nekey->co= nkey->co;
2110         nekey->time= &nkey->time;
2111
2112         if(pa->hair)
2113                 MEM_freeN(pa->hair);
2114         pa->hair= new_keys;
2115
2116         if(point->keys)
2117                 MEM_freeN(point->keys);
2118         point->keys= new_ekeys;
2119
2120         point->totkey = pa->totkey = pa->totkey + totnewkey;
2121         point->flag |= PEP_EDIT_RECALC;
2122         pa->flag &= ~PARS_REKEY;
2123 }
2124
2125 static int subdivide_exec(bContext *C, wmOperator *op)
2126 {
2127         PEData data;
2128
2129         PE_set_data(C, &data);
2130         foreach_point(&data, subdivide_particle);
2131         
2132         recalc_lengths(data.edit);
2133         PE_update_object(data.scene, data.ob, 1);
2134         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_DATA, data.ob);
2135
2136         return OPERATOR_FINISHED;
2137 }
2138
2139 void PARTICLE_OT_subdivide(wmOperatorType *ot)
2140 {
2141         /* identifiers */
2142         ot->name= "Subdivide";
2143         ot->idname= "PARTICLE_OT_subdivide";
2144         
2145         /* api callbacks */
2146         ot->exec= subdivide_exec;
2147         ot->poll= PE_poll;
2148
2149         /* flags */
2150         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2151 }
2152
2153 /************************ remove doubles opertor *********************/
2154
2155 static int remove_doubles_exec(bContext *C, wmOperator *op)
2156 {
2157         Scene *scene= CTX_data_scene(C);
2158         Object *ob= CTX_data_active_object(C);
2159         ParticleEditSettings *pset=PE_settings(scene);
2160         PTCacheEdit *edit= PE_get_current(scene, ob);
2161         ParticleSystem *psys = edit->psys;
2162         ParticleSystemModifierData *psmd;
2163         KDTree *tree;
2164         KDTreeNearest nearest[10];
2165         POINT_P;
2166         float mat[4][4], co[3], threshold= RNA_float_get(op->ptr, "threshold");
2167         int n, totn, removed, flag, totremoved;
2168
2169         if(psys->flag & PSYS_GLOBAL_HAIR)
2170                 return OPERATOR_CANCELLED;
2171
2172         edit= psys->edit;
2173         psmd= psys_get_modifier(ob, psys);
2174         totremoved= 0;
2175
2176         do {
2177                 removed= 0;
2178
2179                 tree=BLI_kdtree_new(psys->totpart);
2180                         
2181                 /* insert particles into kd tree */
2182                 LOOP_SELECTED_POINTS {
2183                         psys_mat_hair_to_object(ob, psmd->dm, psys->part->from, psys->particles+p, mat);
2184                         VECCOPY(co, point->keys->co);
2185                         Mat4MulVecfl(mat, co);
2186                         BLI_kdtree_insert(tree, p, co, NULL);
2187                 }
2188
2189                 BLI_kdtree_balance(tree);
2190
2191                 /* tag particles to be removed */
2192                 LOOP_SELECTED_POINTS {
2193                         psys_mat_hair_to_object(ob, psmd->dm, psys->part->from, psys->particles+p, mat);
2194                         VECCOPY(co, point->keys->co);
2195                         Mat4MulVecfl(mat, co);
2196
2197                         totn= BLI_kdtree_find_n_nearest(tree,10,co,NULL,nearest);
2198
2199                         for(n=0; n<totn; n++) {
2200                                 /* this needs a custom threshold still */
2201                                 if(nearest[n].index > p && nearest[n].dist < threshold) {
2202                                         if(!(point->flag & PEP_TAG)) {
2203                                                 point->flag |= PEP_TAG;
2204                                                 removed++;
2205                                         }
2206                                 }
2207                         }
2208                 }
2209
2210                 BLI_kdtree_free(tree);
2211
2212                 /* remove tagged particles - don't do mirror here! */
2213                 flag= pset->flag;
2214                 pset->flag &= ~PE_X_MIRROR;
2215                 remove_tagged_particles(scene, ob, psys);
2216                 pset->flag= flag;
2217                 totremoved += removed;
2218         } while(removed);
2219
2220         if(totremoved == 0)
2221                 return OPERATOR_CANCELLED;
2222
2223         BKE_reportf(op->reports, RPT_INFO, "Remove %d double particles.", totremoved);
2224
2225         PE_update_object(scene, ob, 0);
2226         DAG_id_flush_update(&ob->id, OB_RECALC_DATA);
2227         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_DATA, ob);
2228
2229         return OPERATOR_FINISHED;
2230 }
2231
2232 void PARTICLE_OT_remove_doubles(wmOperatorType *ot)
2233 {
2234         /* identifiers */
2235         ot->name= "Remove Doubles";
2236         ot->idname= "PARTICLE_OT_remove_doubles";
2237         
2238         /* api callbacks */
2239         ot->exec= remove_doubles_exec;
2240         ot->poll= PE_poll;
2241
2242         /* flags */
2243         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2244
2245         /* properties */
2246         RNA_def_float(ot->srna, "threshold", 0.0002f, 0.0f, FLT_MAX, "Threshold", "Threshold distance withing which particles are removed", 0.00001f, 0.1f);
2247 }
2248
2249 /************************ cursor drawing *******************************/
2250
2251 static void brush_drawcursor(bContext *C, int x, int y, void *customdata)
2252 {
2253         ParticleEditSettings *pset= PE_settings(CTX_data_scene(C));
2254         ParticleBrushData *brush;
2255
2256         if(pset->brushtype < 0)
2257                 return;
2258
2259         brush= &pset->brush[pset->brushtype];
2260
2261         if(brush) {
2262                 glPushMatrix();
2263
2264                 glTranslatef((float)x, (float)y, 0.0f);
2265
2266                 glColor4ub(255, 255, 255, 128);
2267                 glEnable(GL_LINE_SMOOTH );
2268                 glEnable(GL_BLEND);
2269                 glutil_draw_lined_arc(0.0, M_PI*2.0, brush->size, 40);
2270                 glDisable(GL_BLEND);
2271                 glDisable(GL_LINE_SMOOTH );
2272                 
2273                 glPopMatrix();
2274         }
2275 }
2276
2277 static void toggle_particle_cursor(bContext *C, int enable)
2278 {
2279         ParticleEditSettings *pset= PE_settings(CTX_data_scene(C));
2280
2281         if(pset->paintcursor && !enable) {
2282                 WM_paint_cursor_end(CTX_wm_manager(C), pset->paintcursor);
2283                 pset->paintcursor = NULL;
2284         }
2285         else if(enable)
2286                 pset->paintcursor= WM_paint_cursor_activate(CTX_wm_manager(C), PE_poll_3dview, brush_drawcursor, NULL);
2287 }
2288
2289 /********************* radial control operator *********************/
2290
2291 static int brush_radial_control_invoke(bContext *C, wmOperator *op, wmEvent *event)
2292 {
2293         ParticleEditSettings *pset= PE_settings(CTX_data_scene(C));
2294         ParticleBrushData *brush;
2295         int mode = RNA_enum_get(op->ptr, "mode");
2296         float original_value=1.0f;
2297
2298         if(pset->brushtype < 0)
2299                 return OPERATOR_CANCELLED;
2300
2301         brush= &pset->brush[pset->brushtype];
2302
2303         toggle_particle_cursor(C, 0);
2304
2305         if(mode == WM_RADIALCONTROL_SIZE)
2306                 original_value = brush->size;
2307         else if(mode == WM_RADIALCONTROL_STRENGTH)
2308                 original_value = brush->strength;
2309
2310         RNA_float_set(op->ptr, "initial_value", original_value);
2311
2312         return WM_radial_control_invoke(C, op, event);
2313 }
2314
2315 static int brush_radial_control_modal(bContext *C, wmOperator *op, wmEvent *event)
2316 {
2317         int ret = WM_radial_control_modal(C, op, event);
2318
2319         if(ret != OPERATOR_RUNNING_MODAL)
2320                 toggle_particle_cursor(C, 1);
2321
2322         return ret;
2323 }
2324
2325 static int brush_radial_control_exec(bContext *C, wmOperator *op)
2326 {
2327         ParticleEditSettings *pset= PE_settings(CTX_data_scene(C));
2328         ParticleBrushData *brush;
2329         int mode = RNA_enum_get(op->ptr, "mode");
2330         float new_value = RNA_float_get(op->ptr, "new_value");
2331
2332         if(pset->brushtype < 0)
2333                 return OPERATOR_CANCELLED;
2334
2335         brush= &pset->brush[pset->brushtype];
2336
2337         if(mode == WM_RADIALCONTROL_SIZE)
2338                 brush->size= new_value;
2339         else if(mode == WM_RADIALCONTROL_STRENGTH)
2340                 brush->strength= new_value;
2341
2342         return OPERATOR_FINISHED;
2343 }
2344
2345 void PARTICLE_OT_brush_radial_control(wmOperatorType *ot)
2346 {
2347         WM_OT_radial_control_partial(ot);
2348
2349         ot->name= "Brush Radial Control";
2350         ot->idname= "PARTICLE_OT_brush_radial_control";
2351
2352         ot->invoke= brush_radial_control_invoke;
2353         ot->modal= brush_radial_control_modal;
2354         ot->exec= brush_radial_control_exec;
2355         ot->poll= PE_poll;
2356         
2357         /* flags */
2358         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
2359 }
2360
2361 /*************************** delete operator **************************/
2362
2363 enum { DEL_PARTICLE, DEL_KEY };
2364
2365 static EnumPropertyItem delete_type_items[]= {
2366         {DEL_PARTICLE, "PARTICLE", 0, "Particle", ""},
2367         {DEL_KEY, "KEY", 0, "Key", ""},
2368         {0, NULL, 0, NULL, NULL}};
2369
2370 static void set_delete_particle(PEData *data, int pa_index)
2371 {
2372         PTCacheEdit *edit= data->edit;
2373
2374         edit->points[pa_index].flag |= PEP_TAG;
2375 }
2376
2377 static void set_delete_particle_key(PEData *data, int pa_index, int key_index)
2378 {
2379         PTCacheEdit *edit= data->edit;
2380
2381         edit->points[pa_index].keys[key_index].flag |= PEK_TAG;
2382 }
2383
2384 static int delete_exec(bContext *C, wmOperator *op)
2385 {
2386         PEData data;
2387         int type= RNA_enum_get(op->ptr, "type");
2388
2389         PE_set_data(C, &data);
2390
2391         if(type == DEL_KEY) {
2392                 foreach_selected_key(&data, set_delete_particle_key);
2393                 remove_tagged_keys(data.scene, data.ob, data.edit->psys);
2394                 recalc_lengths(data.edit);
2395         }
2396         else if(type == DEL_PARTICLE) {
2397                 foreach_selected_point(&data, set_delete_particle);
2398                 remove_tagged_particles(data.scene, data.ob, data.edit->psys);
2399                 recalc_lengths(data.edit);
2400         }
2401
2402         PE_update_object(data.scene, data.ob, 0);
2403
2404         DAG_id_flush_update(&data.ob->id, OB_RECALC_DATA);
2405         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_DATA, data.ob);
2406
2407         return OPERATOR_FINISHED;
2408 }
2409
2410 void PARTICLE_OT_delete(wmOperatorType *ot)
2411 {
2412         /* identifiers */
2413         ot->name= "Delete";
2414         ot->idname= "PARTICLE_OT_delete";
2415         
2416         /* api callbacks */
2417         ot->exec= delete_exec;
2418         ot->invoke= WM_menu_invoke;
2419         ot->poll= PE_hair_poll;
2420
2421         /* flags */
2422         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2423
2424         /* properties */
2425         RNA_def_enum(ot->srna, "type", delete_type_items, DEL_PARTICLE, "Type", "Delete a full particle or only keys.");
2426 }
2427
2428 /*************************** mirror operator **************************/
2429
2430 static void PE_mirror_x(Scene *scene, Object *ob, int tagged)
2431 {
2432         Mesh *me= (Mesh*)(ob->data);
2433         ParticleSystemModifierData *psmd;
2434         PTCacheEdit *edit= PE_get_current(scene, ob);
2435         ParticleSystem *psys = edit->psys;
2436         ParticleData *pa, *newpa, *new_pars;
2437         PTCacheEditPoint *newpoint, *new_points;
2438         POINT_P; KEY_K;
2439         HairKey *hkey;
2440         int *mirrorfaces;
2441         int rotation, totpart, newtotpart;
2442
2443         if(psys->flag & PSYS_GLOBAL_HAIR)
2444                 return;
2445
2446         psmd= psys_get_modifier(ob, psys);
2447
2448         mirrorfaces= mesh_get_x_mirror_faces(ob, NULL);
2449
2450         if(!edit->mirror_cache)
2451                 PE_update_mirror_cache(ob, psys);
2452
2453         totpart= psys->totpart;
2454         newtotpart= psys->totpart;
2455         LOOP_VISIBLE_POINTS {
2456                 pa = psys->particles + p;
2457                 if(!tagged) {
2458                         if(point_is_selected(point)) {
2459                                 if(edit->mirror_cache[p] != -1) {
2460                                         /* already has a mirror, don't need to duplicate */
2461                                         PE_mirror_particle(ob, psmd->dm, psys, pa, NULL);
2462                                         continue;
2463                                 }
2464                                 else
2465                                         point->flag |= PEP_TAG;
2466                         }
2467                 }
2468
2469                 if((point->flag & PEP_TAG) && mirrorfaces[pa->num*2] != -1)
2470                         newtotpart++;
2471         }
2472
2473         if(newtotpart != psys->totpart) {
2474                 /* allocate new arrays and copy existing */
2475                 new_pars= MEM_callocN(newtotpart*sizeof(ParticleData), "ParticleData new");
2476                 new_points= MEM_callocN(newtotpart*sizeof(PTCacheEditPoint), "PTCacheEditPoint new");
2477
2478                 if(psys->particles) {
2479                         memcpy(new_pars, psys->particles, totpart*sizeof(ParticleData));
2480                         MEM_freeN(psys->particles);
2481                 }
2482                 psys->particles= new_pars;
2483
2484                 if(edit->points) {
2485                         memcpy(new_points, edit->points, totpart*sizeof(PTCacheEditPoint));
2486                         MEM_freeN(edit->points);
2487                 }
2488                 edit->points= new_points;
2489
2490                 if(edit->mirror_cache) {
2491                         MEM_freeN(edit->mirror_cache);
2492                         edit->mirror_cache= NULL;
2493                 }
2494
2495                 edit->totpoint= psys->totpart= newtotpart;
2496                         
2497                 /* create new elements */
2498                 newpa= psys->particles + totpart;
2499                 newpoint= edit->points + totpart;
2500
2501                 LOOP_VISIBLE_POINTS {
2502                         pa = psys->particles + p;
2503
2504                         if(!(point->flag & PEP_TAG) || mirrorfaces[pa->num*2] == -1)
2505                                 continue;
2506
2507                         /* duplicate */
2508                         *newpa= *pa;
2509                         *newpoint= *point;
2510                         if(pa->hair) newpa->hair= MEM_dupallocN(pa->hair);
2511                         if(point->keys) newpoint->keys= MEM_dupallocN(point->keys);
2512
2513                         /* rotate weights according to vertex index rotation */
2514                         rotation= mirrorfaces[pa->num*2+1];
2515                         newpa->fuv[0]= pa->fuv[2];
2516                         newpa->fuv[1]= pa->fuv[1];
2517                         newpa->fuv[2]= pa->fuv[0];
2518                         newpa->fuv[3]= pa->fuv[3];
2519                         while(rotation-- > 0)
2520                                 if(me->mface[pa->num].v4)
2521                                         SHIFT4(float, newpa->fuv[0], newpa->fuv[1], newpa->fuv[2], newpa->fuv[3])
2522                                 else
2523                                         SHIFT3(float, newpa->fuv[0], newpa->fuv[1], newpa->fuv[2])
2524
2525                         /* assign face inddex */
2526                         newpa->num= mirrorfaces[pa->num*2];
2527                         newpa->num_dmcache= psys_particle_dm_face_lookup(ob,psmd->dm,newpa->num,newpa->fuv, NULL);
2528
2529                         /* update edit key pointers */
2530                         key= newpoint->keys;
2531                         for(k=0, hkey=newpa->hair; k<newpa->totkey; k++, hkey++, key++) {
2532                                 key->co= hkey->co;
2533                                 key->time= &hkey->time;
2534                         }
2535
2536                         /* map key positions as mirror over x axis */
2537                         PE_mirror_particle(ob, psmd->dm, psys, pa, newpa);
2538
2539                         newpa++;
2540                         newpoint++;
2541                 }
2542         }
2543
2544         LOOP_POINTS {
2545                 point->flag &= ~PEP_TAG;
2546         }
2547
2548         MEM_freeN(mirrorfaces);
2549 }
2550
2551 static int mirror_exec(bContext *C, wmOperator *op)
2552 {
2553         Scene *scene= CTX_data_scene(C);
2554         Object *ob= CTX_data_active_object(C);
2555         PTCacheEdit *edit= PE_get_current(scene, ob);
2556         
2557         PE_mirror_x(scene, ob, 0);
2558
2559         update_world_cos(ob, edit);
2560         WM_event_add_notifier(C, NC_OBJECT|ND_PARTICLE_DATA, ob);
2561         DAG_id_flush_update(&ob->id, OB_RECALC_DATA);
2562
2563         return OPERATOR_FINISHED;
2564 }
2565
2566 void PARTICLE_OT_mirror(wmOperatorType *ot)
2567 {
2568         /* identifiers */
2569         ot->name= "Mirror";
2570         ot->idname= "PARTICLE_OT_mirror";
2571         
2572         /* api callbacks */
2573         ot->exec= mirror_exec;
2574         ot->poll= PE_poll;
2575
2576         /* flags */
2577         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2578 }
2579
2580 /*********************** set brush operator **********************/
2581
2582 static EnumPropertyItem brush_type_items[]= {
2583         {PE_BRUSH_NONE, "NONE", 0, "None", ""},
2584         {PE_BRUSH_COMB, "COMB", 0, "Comb", ""},
2585         {PE_BRUSH_SMOOTH, "SMOOTH", 0, "Smooth", ""},
2586         {PE_BRUSH_ADD, "ADD", 0, "Add", ""},
2587         {PE_BRUSH_LENGTH, "LENGTH", 0, "Length", ""},
2588         {PE_BRUSH_PUFF, "PUFF", 0, "Puff", ""},
2589         {PE_BRUSH_CUT, "CUT", 0, "Cut", ""},
2590         {0, NULL, 0, NULL, NULL}
2591 };
2592
2593 static int set_brush_exec(bContext *C, wmOperator *op)
2594 {
2595         Scene *scene= CTX_data_scene(C);
2596         ParticleEditSettings *pset= PE_settings(scene);
2597
2598         pset->brushtype= RNA_enum_get(op->ptr, "type");
2599
2600         return OPERATOR_FINISHED;
2601 }
2602
2603 void PARTICLE_OT_brush_set(wmOperatorType *ot)
2604 {
2605         /* identifiers */
2606         ot->name= "Set Brush";
2607         ot->idname= "PARTICLE_OT_brush_set";
2608         
2609         /* api callbacks */
2610         ot->exec= set_brush_exec;
2611         ot->invoke= WM_menu_invoke;
2612         ot->poll= PE_poll;
2613
2614         /* properties */
2615         RNA_def_enum(ot->srna, "type", brush_type_items, PE_BRUSH_NONE, "Type", "Brush type to select for editing.");
2616 }
2617
2618
2619 /*********************** set mode operator **********************/
2620
2621 static EnumPropertyItem edit_type_items[]= {
2622         {PE_TYPE_PARTICLES, "PARTICLES", 0, "Particles", ""},
2623         {PE_TYPE_SOFTBODY, "SOFTBODY", 0, "Soft body", ""},
2624         {PE_TYPE_CLOTH, "CLOTH", 0, "Cloth", ""},
2625         {0, NULL, 0, NULL, NULL}
2626 };
2627
2628 static int set_edit_mode_exec(bContext *C, wmOperator *op)
2629 {
2630         Scene *scene= CTX_data_scene(C);
2631         ParticleEditSettings *pset= PE_settings(scene);
2632
2633         pset->edittype= RNA_enum_get(op->ptr, "type");
2634
2635         return OPERATOR_FINISHED;
2636 }
2637
2638 void PARTICLE_OT_edit_type_set(wmOperatorType *ot)
2639 {
2640         /* identifiers */
2641         ot->name= "Set Edit Type";
2642         ot->idname= "PARTICLE_OT_edit_type_set";
2643         
2644         /* api callbacks */
2645         ot->exec= set_edit_mode_exec;
2646         ot->invoke= WM_menu_invoke;
2647         ot->poll= PE_poll;
2648
2649         /* properties */
2650         RNA_def_enum(ot->srna, "type", edit_type_items, PE_TYPE_PARTICLES, "Type", "Edit type to select for editing.");
2651 }
2652
2653 /************************* brush edit callbacks ********************/
2654
2655 static void brush_comb(PEData *data, float mat[][4], float imat[][4], int point_index, int key_index, PTCacheEditKey *key)
2656 {
2657         ParticleEditSettings *pset= PE_settings(data->scene);
2658         float cvec[3], fac;
2659
2660         if(pset->flag & PE_LOCK_FIRST && key_index == 0) return;
2661
2662         fac= (float)pow((double)(1.0f - data->dist / data->rad), (double)data->combfac);
2663
2664         VECCOPY(cvec,data->dvec);
2665         Mat4Mul3Vecfl(imat,cvec);
2666         VecMulf(cvec, fac);
2667         VECADD(key->co, key->co, cvec);
2668
2669         (data->edit->points + point_index)->flag |= PEP_EDIT_RECALC;
2670 }
2671
2672 static void brush_cut(PEData *data, int pa_index)
2673 {
2674         PTCacheEdit *edit = data->edit;
2675         ARegion *ar= data->vc.ar;
2676         Object *ob= data->ob;
2677         ParticleEditSettings *pset= PE_settings(data->scene);
2678         ParticleCacheKey *key= edit->pathcache[pa_index];
2679         float rad2, cut_time= 1.0;
2680         float x0, x1, v0, v1, o0, o1, xo0, xo1, d, dv;
2681         int k, cut, keys= (int)pow(2.0, (double)pset->draw_step);
2682         short vertco[2];
2683
2684         /* blunt scissors */
2685         if(BLI_frand() > data->cutfac) return;
2686
2687         rad2= data->rad * data->rad;
2688
2689         cut=0;
2690
2691         project_short_noclip(ar, key->co, vertco);
2692         x0= (float)vertco[0];
2693         x1= (float)vertco[1];
2694
2695         o0= (float)data->mval[0];
2696         o1= (float)data->mval[1];
2697         
2698         xo0= x0 - o0;
2699         xo1= x1 - o1;
2700
2701         /* check if root is inside circle */
2702         if(xo0*xo0 + xo1*xo1 < rad2 && key_test_depth(data, key->co)) {
2703                 cut_time= -1.0f;
2704                 cut= 1;
2705         }
2706         else {
2707                 /* calculate path time closest to root that was inside the circle */
2708                 for(k=1, key++; k<=keys; k++, key++) {
2709                         project_short_noclip(ar, key->co, vertco);
2710
2711                         if(key_test_depth(data, key->co) == 0) {
2712                                 x0= (float)vertco[0];
2713                                 x1= (float)vertco[1];
2714
2715                                 xo0= x0 - o0;
2716                                 xo1= x1 - o1;
2717                                 continue;
2718                         }
2719
2720                         v0= (float)vertco[0] - x0;
2721                         v1= (float)vertco[1] - x1;
2722
2723                         dv= v0*v0 + v1*v1;
2724
2725                         d= (v0*xo1 - v1*xo0);
2726                         
2727                         d= dv * rad2 - d*d;
2728
2729                         if(d > 0.0f) {
2730                                 d= sqrt(d);
2731
2732                                 cut_time= -(v0*xo0 + v1*xo1 + d);
2733
2734                                 if(cut_time > 0.0f) {
2735                                         cut_time /= dv;
2736
2737                                         if(cut_time < 1.0f) {
2738                                                 cut_time += (float)(k-1);
2739                                                 cut_time /= (float)keys;
2740                                                 cut= 1;
2741                                                 break;
2742                                         }
2743                                 }
2744                         }
2745
2746                         x0= (float)vertco[0];
2747                         x1= (float)vertco[1];
2748
2749                         xo0= x0 - o0;
2750                         xo1= x1 - o1;
2751                 }
2752         }
2753
2754         if(cut) {
2755                 if(cut_time < 0.0f) {
2756                         edit->points[pa_index].flag |= PEP_TAG;
2757                 }
2758                 else {
2759                         rekey_particle_to_time(data->scene, ob, pa_index, cut_time);
2760                         edit->points[pa_index].flag |= PEP_EDIT_RECALC;
2761                 }
2762         }
2763 }
2764
2765 static void brush_length(PEData *data, int point_index)
2766 {
2767         PTCacheEdit *edit= data->edit;
2768         PTCacheEditPoint *point = edit->points + point_index;
2769         KEY_K;
2770         float dvec[3],pvec[3];
2771
2772         LOOP_KEYS {
2773                 if(k==0) {
2774                         VECCOPY(pvec,key->co);
2775                 }
2776                 else {
2777                         VECSUB(dvec,key->co,pvec);
2778                         VECCOPY(pvec,key->co);
2779                         VecMulf(dvec,data->growfac);
2780                         VECADD(key->co,(key-1)->co,dvec);
2781                 }
2782         }
2783
2784         point->flag |= PEP_EDIT_RECALC;
2785 }
2786
2787 static void brush_puff(PEData *data, int point_index)
2788 {
2789         PTCacheEdit *edit = data->edit;
2790         ParticleSystem *psys = edit->psys;
2791         PTCacheEditPoint *point = edit->points + point_index;
2792         KEY_K;
2793         float mat[4][4], imat[4][4];
2794         float lastco[3], rootco[3], co[3], nor[3], kco[3], dco[3], fac, length;
2795
2796         if(psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
2797                 psys_mat_hair_to_global(data->ob, data->dm, psys->part->from, psys->particles + point_index, mat);
2798                 Mat4Invert(imat,mat);
2799         }
2800         else {
2801                 Mat4One(mat);
2802                 Mat4One(imat);
2803         }
2804
2805         LOOP_KEYS {
2806                 if(k==0) {
2807                         /* find root coordinate and normal on emitter */
2808                         VECCOPY(co, key->co);
2809                         Mat4MulVecfl(mat, co);
2810
2811                         point_index= BLI_kdtree_find_nearest(edit->emitter_field, co, NULL, NULL);
2812                         if(point_index == -1) return;
2813
2814                         VECCOPY(rootco, co);
2815                         VecCopyf(nor, &edit->emitter_cosnos[point_index*6+3]);
2816                         Normalize(nor);
2817                         length= 0.0f;
2818
2819                         fac= (float)pow((double)(1.0f - data->dist / data->rad), (double)data->pufffac);
2820                         fac *= 0.025f;
2821                         if(data->invert)
2822                                 fac= -fac;
2823                 }
2824                 else {
2825                         /* compute position as if hair was standing up straight */
2826                         VECCOPY(lastco, co);
2827                         VECCOPY(co, key->co);
2828                         Mat4MulVecfl(mat, co);
2829                         length += VecLenf(lastco, co);
2830
2831                         VECADDFAC(kco, rootco, nor, length);
2832
2833                         /* blend between the current and straight position */
2834                         VECSUB(dco, kco, co);
2835                         VECADDFAC(co, co, dco, fac);
2836
2837                         VECCOPY(key->co, co);
2838                         Mat4MulVecfl(imat, key->co);
2839                 }
2840         }
2841
2842         point->flag |= PEP_EDIT_RECALC;
2843 }
2844
2845 static void brush_smooth_get(PEData *data, float mat[][4], float imat[][4], int point_index, int key_index, PTCacheEditKey *key)
2846 {       
2847         if(key_index) {
2848                 float dvec[3];
2849
2850                 VecSubf(dvec,key->co,(key-1)->co);
2851                 Mat4Mul3Vecfl(mat,dvec);
2852                 VECADD(data->vec,data->vec,dvec);
2853                 data->tot++;
2854         }
2855 }
2856
2857 static void brush_smooth_do(PEData *data, float mat[][4], float imat[][4], int point_index, int key_index, PTCacheEditKey *key)
2858 {
2859         float vec[3], dvec[3];
2860         
2861         if(key_index) {
2862                 VECCOPY(vec,data->vec);
2863                 Mat4Mul3Vecfl(imat,vec);
2864
2865                 VecSubf(dvec,key->co,(key-1)->co);
2866
2867                 VECSUB(dvec,vec,dvec);
2868                 VecMulf(dvec,data->smoothfac);
2869                 
2870                 VECADD(key->co,key->co,dvec);
2871         }
2872
2873         (data->edit->points + point_index)->flag |= PEP_EDIT_RECALC;
2874 }
2875
2876 static void brush_add(PEData *data, short number)
2877 {
2878         Scene *scene= data->scene;
2879         Object *ob= data->ob;
2880         PTCacheEdit *edit = data->edit;
2881         ParticleSystem *psys= edit->psys;
2882         ParticleData *add_pars= MEM_callocN(number*sizeof(ParticleData),"ParticleData add");
2883         ParticleSystemModifierData *psmd= psys_get_modifier(ob,psys);
2884         ParticleSimulationData sim = {scene, ob, psys, psmd};
2885         ParticleEditSettings *pset= PE_settings(scene);
2886         int i, k, n= 0, totpart= psys->totpart;
2887         short mco[2];
2888         short dmx= 0, dmy= 0;
2889         float co1[3], co2[3], min_d, imat[4][4];
2890         float framestep, timestep= psys_get_timestep(&sim);
2891         short size= pset->brush[PE_BRUSH_ADD].size;
2892         short size2= size*size;
2893         DerivedMesh *dm=0;
2894         Mat4Invert(imat,ob->obmat);
2895
2896         if(psys->flag & PSYS_GLOBAL_HAIR)
2897                 return;
2898
2899         BLI_srandom(psys->seed+data->mval[0]+data->mval[1]);
2900         
2901         /* painting onto the deformed mesh, could be an option? */
2902         if(psmd->dm->deformedOnly)
2903                 dm= psmd->dm;
2904         else
2905                 dm= mesh_get_derived_deform(scene, ob, CD_MASK_BAREMESH);
2906
2907         for(i=0; i<number; i++) {
2908                 if(number>1) {
2909                         dmx=dmy=size;
2910                         while(dmx*dmx+dmy*dmy>size2) {
2911                                 dmx=(short)((2.0f*BLI_frand()-1.0f)*size);
2912                                 dmy=(short)((2.0f*BLI_frand()-1.0f)*size);
2913                         }
2914                 }
2915
2916                 mco[0]= data->mval[0] + dmx;
2917                 mco[1]= data->mval[1] + dmy;
2918                 viewline(data->vc.ar, data->vc.v3d, mco, co1, co2);
2919
2920                 Mat4MulVecfl(imat,co1);
2921                 Mat4MulVecfl(imat,co2);
2922                 min_d=2.0;
2923                 
2924                 /* warning, returns the derived mesh face */
2925                 if(psys_intersect_dm(scene, ob,dm,0,co1,co2,&min_d,&add_pars[n].num,add_pars[n].fuv,0,0,0,0)) {
2926                         add_pars[n].num_dmcache= psys_particle_dm_face_lookup(ob,psmd->dm,add_pars[n].num,add_pars[n].fuv,NULL);
2927                         n++;
2928                 }
2929         }
2930         if(n) {
2931                 int newtotpart=totpart+n;
2932                 float hairmat[4][4], cur_co[3];
2933                 KDTree *tree=0;
2934                 ParticleData *pa, *new_pars= MEM_callocN(newtotpart*sizeof(ParticleData),"ParticleData new");
2935                 PTCacheEditPoint *point, *new_points= MEM_callocN(newtotpart*sizeof(PTCacheEditPoint),"PTCacheEditPoint array new");
2936                 PTCacheEditKey *key;
2937                 HairKey *hkey;
2938
2939                 /* save existing elements */
2940                 memcpy(new_pars, psys->particles, totpart * sizeof(ParticleData));
2941                 memcpy(new_points, edit->points, totpart * sizeof(PTCacheEditPoint));
2942
2943                 /* change old arrays to new ones */
2944                 if(psys->particles) MEM_freeN(psys->particles);
2945                 psys->particles= new_pars;
2946
2947                 if(edit->points) MEM_freeN(edit->points);
2948                 edit->points= new_points;
2949
2950                 if(edit->mirror_cache) {
2951                         MEM_freeN(edit->mirror_cache);
2952                         edit->mirror_cache= NULL;
2953                 }
2954
2955                 /* create tree for interpolation */
2956                 if(pset->flag & PE_INTERPOLATE_ADDED && psys->totpart) {
2957                         tree=BLI_kdtree_new(psys->totpart);
2958                         
2959                         for(i=0, pa=psys->particles; i<totpart; i++, pa++) {
2960                                 psys_particle_on_dm(psmd->dm,psys->part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,cur_co,0,0,0,0,0);
2961                                 BLI_kdtree_insert(tree, i, cur_co, NULL);
2962                         }
2963
2964                         BLI_kdtree_balance(tree);
2965                 }
2966
2967                 edit->totpoint= psys->totpart= newtotpart;
2968
2969                 /* create new elements */
2970                 pa= psys->particles + totpart;
2971                 point= edit->points + totpart;
2972
2973                 for(i=totpart; i<newtotpart; i++, pa++, point++) {
2974                         memcpy(pa, add_pars + i - totpart, sizeof(ParticleData));
2975                         pa->hair= MEM_callocN(pset->totaddkey * sizeof(HairKey), "BakeKey key add");
2976                         key= point->keys= MEM_callocN(pset->totaddkey * sizeof(PTCacheEditKey), "PTCacheEditKey add");
2977                         point->totkey= pa->totkey= pset->totaddkey;
2978
2979                         for(k=0, hkey=pa->hair; k<pa->totkey; k++, hkey++, key++) {
2980                                 key->co= hkey->co;
2981                                 key->time= &hkey->time;
2982                         }
2983                         
2984                         pa->size= 1.0f;
2985                         initialize_particle(&sim, pa,i);
2986                         reset_particle(&sim, pa, 0.0, 1.0);
2987                         point->flag |= PEP_EDIT_RECALC;
2988                         if(pset->flag & PE_X_MIRROR)
2989                                 point->flag |= PEP_TAG; /* signal for duplicate */
2990                         
2991                         framestep= pa->lifetime/(float)(pset->totaddkey-1);
2992
2993                         if(tree) {
2994                                 HairKey *hkey;
2995                                 ParticleKey key[3];
2996                                 KDTreeNearest ptn[3];
2997                                 int w, maxw;
2998                                 float maxd, mind, dd, totw=0.0, weight[3];
2999
3000                                 psys_particle_on_dm(psmd->dm,psys->part->from,pa->num,pa->num_dmcache,pa->fuv,pa->foffset,co1,0,0,0,0,0);
3001                                 maxw= BLI_kdtree_find_n_nearest(tree,3,co1,NULL,ptn);
3002
3003                                 maxd= ptn[maxw-1].dist;
3004                                 mind= ptn[0].dist;
3005                                 dd= maxd - mind;
3006                                 
3007                                 for(w=0; w<maxw; w++) {
3008                                         weight[w]= (float)pow(2.0, (double)(-6.0f * ptn[w].dist / maxd));
3009                                         totw += weight[w];
3010                                 }
3011                                 for(;w<3; w++) {
3012                                         weight[w]= 0.0f;
3013                                 }
3014
3015                                 for(w=0; w<maxw; w++)
3016                                         weight[w] /= totw;
3017
3018                                 for(k=0; k<pset->totaddkey; k++) {
3019                                         hkey= (HairKey*)pa->hair + k;
3020                                         hkey->time= pa->time + k * framestep;
3021
3022                                         key[0].time= hkey->time/ 100.0f;
3023                                         psys_get_particle_on_path(&sim, ptn[0].index, key, 0);
3024                                         VecMulf(key[0].co, weight[0]);
3025                                         
3026                                         if(maxw>1) {
3027                                                 key[1].time= key[0].time;
3028                                                 psys_get_particle_on_path(&sim, ptn[1].index, key + 1, 0);
3029                                                 VecMulf(key[1].co, weight[1]);
3030                                                 VECADD(key[0].co, key[0].co, key[1].co);
3031
3032                                                 if(maxw>2) {                                            
3033                                                         key[2].time= key[0].time;
3034                                                         psys_get_particle_on_path(&sim, ptn[2].index, key + 2, 0);
3035                                                         VecMulf(key[2].co, weight[2]);
3036                                                         VECADD(key[0].co, key[0].co, key[2].co);
3037                                                 }
3038                                         }
3039
3040                                         if(k==0)
3041                                                 VECSUB(co1, pa->state.co, key[0].co);
3042
3043                                         VECADD(hkey->co, key[0].co, co1);
3044
3045                                         hkey->time= key[0].time;
3046                                 }
3047                         }
3048                         else {
3049                                 for(k=0, hkey=pa->hair; k<pset->totaddkey; k++, hkey++) {
3050                                         VECADDFAC(hkey->co, pa->state.co, pa->state.vel, k * framestep * timestep);
3051                                         hkey->time += k * framestep;
3052                                 }
3053                         }
3054                         for(k=0, hkey=pa->hair; k<pset->totaddkey; k++, hkey++) {
3055                                 psys_mat_hair_to_global(ob, psmd->dm, psys->part->from, pa, hairmat);
3056                                 Mat4Invert(imat,hairmat);
3057                                 Mat4MulVecfl(imat, hkey->co);
3058                         }
3059                 }
3060
3061                 if(tree)
3062                         BLI_kdtree_free(tree);
3063         }
3064         if(add_pars)
3065                 MEM_freeN(add_pars);
3066         
3067         if(!psmd->dm->deformedOnly)
3068                 dm->release(dm);
3069 }
3070
3071 /************************* brush edit operator ********************/
3072
3073 typedef struct BrushEdit {
3074         Scene *scene;
3075         Object *ob;
3076         PTCacheEdit *edit;
3077
3078         int first;
3079         int lastmouse[2];
3080 } BrushEdit;
3081
3082 static int brush_edit_init(bContext *C, wmOperator *op)
3083 {
3084         Scene *scene= CTX_data_scene(C);
3085         Object *ob= CTX_data_active_object(C);
3086         ParticleEditSettings *pset= PE_settings(scene);
3087         PTCacheEdit *edit= PE_get_current(scene, ob);
3088         ARegion *ar= CTX_wm_region(C);
3089         BrushEdit *bedit;
3090
3091         if(pset->brushtype < 0)
3092                 return 0;
3093
3094         initgrabz(ar->regiondata, ob->obmat[3][0], ob->obmat[3][1], ob->obmat[3][2]);
3095
3096         bedit= MEM_callocN(sizeof(BrushEdit), "BrushEdit");
3097         bedit->first= 1;
3098         op->customdata= bedit;
3099
3100         bedit->scene= scene;
3101         bedit->ob= ob;
3102         bedit->edit= edit;
3103
3104         return 1;
3105 }
3106
3107 static void brush_edit_apply(bContext *C, wmOperator *op, PointerRNA *itemptr)
3108 {
3109         BrushEdit *bedit= op->customdata;
3110         Scene *scene= bedit->scene;
3111         Object *ob= bedit->ob;
3112         PTCacheEdit *edit= bedit->edit;
3113         ParticleEditSettings *pset= PE_settings(scene);
3114         ParticleSystemModifierData *psmd= edit->psys ? psys_get_modifier(ob, edit->psys) : NULL;
3115         ParticleBrushData *brush= &pset->brush[pset->brushtype];
3116         ARegion *ar= CTX_wm_region(C);
3117         float vec[3], mousef[2];
3118         short mval[2], mvalo[2];
3119         int flip, mouse[2], dx, dy, removed= 0, selected= 0;
3120         int lock_root = pset->flag & PE_LOCK_FIRST;
3121
3122         if(!PE_start_edit(edit))
3123                 return;
3124
3125         RNA_float_get_array(itemptr, "mouse", mousef);
3126         mouse[0] = mousef[0];
3127         mouse[1] = mousef[1];
3128         flip= RNA_boolean_get(itemptr, "flip");
3129
3130         if(bedit->first) {
3131                 bedit->lastmouse[0]= mouse[0];
3132                 bedit->lastmouse[1]= mouse[1];
3133         }
3134
3135         dx= mouse[0] - bedit->lastmouse[0];
3136         dy= mouse[1] - bedit->lastmouse[1];
3137
3138         mval[0]= mouse[0];
3139         mval[1]= mouse[1];
3140
3141         mvalo[0]= bedit->lastmouse[0];
3142         mvalo[1]= bedit->lastmouse[1];
3143
3144         /* disable locking temporatily for disconnected hair */
3145         if(edit->psys && edit->psys->flag & PSYS_GLOBAL_HAIR)
3146                 pset->flag &= ~PE_LOCK_FIRST;
3147
3148         if(((pset->brushtype == PE_BRUSH_ADD) ?
3149                 (sqrt(dx * dx + dy * dy) > pset->brush[PE_BRUSH_ADD].step) : (dx != 0 || dy != 0))
3150                 || bedit->first) {
3151
3152                 view3d_operator_needs_opengl(C);
3153                 selected= (short)count_selected_keys(scene, edit);
3154
3155                 switch(pset->brushtype) {
3156                         case PE_BRUSH_COMB:
3157                         {
3158                                 PEData data;
3159
3160                                 PE_set_view3d_data(C, &data);
3161                                 data.mval= mval;
3162                                 data.rad= (float)brush->size;
3163
3164                                 data.combfac= (float)(brush->strength - 50) / 50.0f;
3165                                 if(data.combfac < 0.0f)
3166                                         data.combfac= 1.0f - 9.0f * data.combfac;
3167                                 else
3168                                         data.combfac= 1.0f - data.combfac;
3169
3170                                 Mat4Invert(ob->imat, ob->obmat);
3171
3172                                 window_to_3d_delta(ar, vec, dx, dy);
3173                                 data.dvec= vec;
3174
3175                                 foreach_mouse_hit_key(&data, brush_comb, selected);
3176                                 break;
3177                         }
3178                         case PE_BRUSH_CUT:
3179                         {
3180                                 PEData data;
3181                                 
3182                                 if(edit->psys && edit->pathcache) {
3183                                         PE_set_view3d_data(C, &data);
3184                                         data.mval= mval;
3185                                         data.rad= (float)brush->size;
3186