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