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