Reason of all this work: Commiting my work-in-progress on reviewed collision system...
[blender.git] / source / blender / blenkernel / intern / particle.c
1 /* particle.c
2  *
3  *
4  * $Id: particle.c $
5  *
6  * ***** BEGIN GPL 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.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2007 by Janne Karhu.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL LICENSE BLOCK *****
30  */
31
32 #include <stdlib.h>
33 #include <math.h>
34 #include <string.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "DNA_scene_types.h"
39 #include "DNA_particle_types.h"
40 #include "DNA_mesh_types.h"
41 #include "DNA_meshdata_types.h"
42 #include "DNA_modifier_types.h"
43 #include "DNA_object_force.h"
44 #include "DNA_texture_types.h"
45 #include "DNA_material_types.h"
46 #include "DNA_object_types.h"
47 #include "DNA_curve_types.h"
48 #include "DNA_key_types.h"
49
50 #include "BLI_arithb.h"
51 #include "BLI_blenlib.h"
52 #include "BLI_dynstr.h"
53 #include "BLI_kdtree.h"
54 #include "BLI_linklist.h"
55 #include "BLI_rand.h"
56 #include "BLI_threads.h"
57
58 #include "BKE_anim.h"
59
60 #include "BKE_global.h"
61 #include "BKE_main.h"
62 #include "BKE_lattice.h"
63 #include "BKE_utildefines.h"
64 #include "BKE_displist.h"
65 #include "BKE_particle.h"
66 #include "BKE_DerivedMesh.h"
67 #include "BKE_ipo.h"
68 #include "BKE_object.h"
69 #include "BKE_softbody.h"
70 #include "BKE_material.h"
71 #include "BKE_key.h"
72 #include "BKE_library.h"
73 #include "BKE_depsgraph.h"
74 #include "BKE_bad_level_calls.h"
75 #include "BKE_modifier.h"
76 #include "BKE_mesh.h"
77 #include "BKE_cdderivedmesh.h"
78 #include "BKE_pointcache.h"
79
80 #include "blendef.h"
81 #include "RE_render_ext.h"
82
83 static void key_from_object(Object *ob, ParticleKey *key);
84 static void get_cpa_texture(DerivedMesh *dm, Material *ma, int face_index,
85                                 float *fuv, float *orco, ParticleTexture *ptex, int event);
86
87 /* few helpers for countall etc. */
88 int count_particles(ParticleSystem *psys){
89         ParticleSettings *part=psys->part;
90         ParticleData *pa;
91         int tot=0,p;
92
93         for(p=0,pa=psys->particles; p<psys->totpart; p++,pa++){
94                 if(pa->alive == PARS_KILLED);
95                 else if(pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN)==0);
96                 else if(pa->alive == PARS_DEAD && (part->flag & PART_DIED)==0);
97                 else if(pa->flag & (PARS_UNEXIST+PARS_NO_DISP));
98                 else tot++;
99         }
100         return tot;
101 }
102 int count_particles_mod(ParticleSystem *psys, int totgr, int cur){
103         ParticleSettings *part=psys->part;
104         ParticleData *pa;
105         int tot=0,p;
106
107         for(p=0,pa=psys->particles; p<psys->totpart; p++,pa++){
108                 if(pa->alive == PARS_KILLED);
109                 else if(pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN)==0);
110                 else if(pa->alive == PARS_DEAD && (part->flag & PART_DIED)==0);
111                 else if(pa->flag & (PARS_UNEXIST+PARS_NO_DISP));
112                 else if(p%totgr==cur) tot++;
113         }
114         return tot;
115 }
116 int psys_count_keys(ParticleSystem *psys)
117 {
118         ParticleData *pa;
119         int i, totpart=psys->totpart, totkey=0;
120
121         for(i=0, pa=psys->particles; i<totpart; i++, pa++)
122                 totkey += pa->totkey;
123
124         return totkey;
125 }
126 /* remember to free the pointer returned from this! */
127 char *psys_menu_string(Object *ob, int for_sb)
128 {
129         ParticleSystem *psys;
130         DynStr *ds;
131         char *str, num[6];
132         int i;
133
134         ds = BLI_dynstr_new();
135
136         if(for_sb)
137                 BLI_dynstr_append(ds, "|Object%x-1");
138         
139         for(i=0,psys=ob->particlesystem.first; psys; i++,psys=psys->next){
140
141                 BLI_dynstr_append(ds, "|");
142                 sprintf(num,"%i. ",i+1);
143                 BLI_dynstr_append(ds, num);
144                 BLI_dynstr_append(ds, psys->part->id.name+2);
145                 sprintf(num,"%%x%i",i+1);
146                 BLI_dynstr_append(ds, num);
147         }
148         
149         str = BLI_dynstr_get_cstring(ds);
150
151         BLI_dynstr_free(ds);
152
153         return str;
154 }
155 /************************************************/
156 /*                      Getting stuff                                           */
157 /************************************************/
158 /* get object's active particle system safely */
159 ParticleSystem *psys_get_current(Object *ob)
160 {
161         ParticleSystem *psys;
162         if(ob==0) return 0;
163
164         for(psys=ob->particlesystem.first; psys; psys=psys->next){
165                 if(psys->flag & PSYS_CURRENT)
166                         return psys;
167         }
168         
169         return 0;
170 }
171 short psys_get_current_num(Object *ob)
172 {
173         ParticleSystem *psys;
174         short i;
175
176         if(ob==0) return 0;
177
178         for(psys=ob->particlesystem.first, i=0; psys; psys=psys->next, i++)
179                 if(psys->flag & PSYS_CURRENT)
180                         return i;
181         
182         return i;
183 }
184 /* change object's active particle system */
185 void psys_change_act(void *ob_v, void *act_v)
186 {
187         Object *ob = ob_v;
188         ParticleSystem *npsys, *psys;
189         short act = *((short*)act_v)-1;
190
191         if(act>=0){
192                 npsys=BLI_findlink(&ob->particlesystem,act);
193                 psys=psys_get_current(ob);
194
195                 if(psys)
196                         psys->flag &= ~PSYS_CURRENT;
197                 if(npsys)
198                         npsys->flag |= PSYS_CURRENT;
199         }
200 }
201 Object *psys_get_lattice(Object *ob, ParticleSystem *psys)
202 {
203         Object *lattice=0;
204         
205         if(psys_in_edit_mode(psys)==0){
206
207                 ModifierData *md = (ModifierData*)psys_get_modifier(ob,psys);
208
209                 for(; md; md=md->next){
210                         if(md->type==eModifierType_Lattice){
211                                 LatticeModifierData *lmd = (LatticeModifierData *)md;
212                                 lattice=lmd->object;
213                                 break;
214                         }
215                 }
216                 if(lattice)
217                         init_latt_deform(lattice,0);
218         }
219
220         return lattice;
221 }
222 void psys_disable_all(Object *ob)
223 {
224         ParticleSystem *psys=ob->particlesystem.first;
225
226         for(; psys; psys=psys->next)
227                 psys->flag |= PSYS_DISABLED;
228 }
229 void psys_enable_all(Object *ob)
230 {
231         ParticleSystem *psys=ob->particlesystem.first;
232
233         for(; psys; psys=psys->next)
234                 psys->flag &= ~PSYS_DISABLED;
235 }
236 int psys_ob_has_hair(Object *ob)
237 {
238         ParticleSystem *psys = ob->particlesystem.first;
239
240         for(; psys; psys=psys->next)
241                 if(psys->part->type == PART_HAIR)
242                         return 1;
243
244         return 0;
245 }
246 int psys_in_edit_mode(ParticleSystem *psys)
247 {
248         return ((G.f & G_PARTICLEEDIT) && psys==psys_get_current(OBACT) && psys->edit);
249 }
250 int psys_check_enabled(Object *ob, ParticleSystem *psys)
251 {
252         ParticleSystemModifierData *psmd;
253         Mesh *me;
254
255         if(psys->flag & PSYS_DISABLED)
256                 return 0;
257
258         if(ob->type == OB_MESH) {
259                 me= (Mesh*)ob->data;
260                 if(me->mr && me->mr->current != 1)
261                         return 0;
262         }
263
264         psmd= psys_get_modifier(ob, psys);
265         if(psys->renderdata) {
266                 if(!(psmd->modifier.mode & eModifierMode_Render))
267                         return 0;
268         }
269         else if(!(psmd->modifier.mode & eModifierMode_Realtime))
270                 return 0;
271         
272         return 1;
273 }
274
275 /************************************************/
276 /*                      Freeing stuff                                           */
277 /************************************************/
278 void psys_free_settings(ParticleSettings *part)
279 {
280         if(part->pd)
281                 MEM_freeN(part->pd);
282 }
283
284 void free_hair(ParticleSystem *psys, int softbody)
285 {
286         ParticleData *pa;
287         int i, totpart=psys->totpart;
288
289         for(i=0, pa=psys->particles; i<totpart; i++, pa++) {
290                 if(pa->hair)
291                         MEM_freeN(pa->hair);
292                 pa->hair = NULL;
293         }
294
295         psys->flag &= ~PSYS_HAIR_DONE;
296
297         if(softbody && psys->soft) {
298                 sbFree(psys->soft);
299                 psys->soft = NULL;
300         }
301 }
302 void free_keyed_keys(ParticleSystem *psys)
303 {
304         if(psys->particles && psys->particles->keys)
305                 MEM_freeN(psys->particles->keys);
306 }
307 void free_child_path_cache(ParticleSystem *psys)
308 {
309         if(psys->childcache){
310                 if(psys->childcache[0])
311                         MEM_freeN(psys->childcache[0]);
312
313                 MEM_freeN(psys->childcache);
314
315                 psys->childcache = NULL;
316                 psys->totchildcache = 0;
317         }
318 }
319 void psys_free_path_cache(ParticleSystem *psys)
320 {
321         if(psys->pathcache){
322                 if(psys->pathcache[0])
323                         MEM_freeN(psys->pathcache[0]);
324
325                 MEM_freeN(psys->pathcache);
326
327                 psys->pathcache = NULL;
328                 psys->totcached = 0;
329         }
330         free_child_path_cache(psys);
331 }
332 void psys_free_children(ParticleSystem *psys)
333 {
334         if(psys->child) {
335                 MEM_freeN(psys->child);
336                 psys->child=0;
337                 psys->totchild=0;
338         }
339
340         free_child_path_cache(psys);
341 }
342 /* free everything */
343 void psys_free(Object *ob, ParticleSystem * psys)
344 {
345         if(psys){
346                 if(ob->particlesystem.first == NULL && G.f & G_PARTICLEEDIT)
347                         G.f &= ~G_PARTICLEEDIT;
348
349                 psys_free_path_cache(psys);
350
351                 free_hair(psys, 1);
352
353                 free_keyed_keys(psys);
354
355                 PE_free_particle_edit(psys);
356
357                 if(psys->particles){
358                         MEM_freeN(psys->particles);
359                         psys->particles = 0;
360                         psys->totpart = 0;
361                 }
362
363                 if(psys->child){
364                         MEM_freeN(psys->child);
365                         psys->child = 0;
366                         psys->totchild = 0;
367                 }
368
369                 if(psys->effectors.first)
370                         psys_end_effectors(psys);
371
372                 if(psys->part){
373                         psys->part->id.us--;            
374                         psys->part=0;
375                 }
376
377                 if(psys->reactevents.first)
378                         BLI_freelistN(&psys->reactevents);
379
380                 if(psys->pointcache)
381                         BKE_ptcache_free(psys->pointcache);
382
383                 MEM_freeN(psys);
384         }
385 }
386
387 /* these functions move away particle data and bring it back after
388  * rendering, to make different render settings possible without
389  * removing the previous data. this should be solved properly once */
390
391 typedef struct ParticleRenderElem {
392         int curchild, totchild, reduce;
393         float lambda, t, scalemin, scalemax;
394 } ParticleRenderElem;
395
396 typedef struct ParticleRenderData {
397         ChildParticle *child;
398         ParticleCacheKey **pathcache;
399         ParticleCacheKey **childcache;
400         int totchild, totcached, totchildcache;
401         DerivedMesh *dm;
402         int totdmvert, totdmedge, totdmface;
403
404         float mat[4][4];
405         float viewmat[4][4], winmat[4][4];
406         int winx, winy;
407
408         int dosimplify;
409         int timeoffset;
410         ParticleRenderElem *elems;
411         int *origindex;
412 } ParticleRenderData;
413
414 static float psys_render_viewport_falloff(double rate, float dist, float width)
415 {
416         return pow(rate, dist/width);
417 }
418
419 static float psys_render_projected_area(ParticleSystem *psys, float *center, float area, double vprate, float *viewport)
420 {
421         ParticleRenderData *data= psys->renderdata;
422         float co[4], view[3], ortho1[3], ortho2[3], w, dx, dy, radius;
423         
424         /* transform to view space */
425         VECCOPY(co, center);
426         co[3]= 1.0f;
427         Mat4MulVec4fl(data->viewmat, co);
428         
429         /* compute two vectors orthogonal to view vector */
430         VECCOPY(view, co);
431         Normalize(view);
432         VecOrthoBasisf(view, ortho1, ortho2);
433
434         /* compute on screen minification */
435         w= co[2]*data->winmat[2][3] + data->winmat[3][3];
436         dx= data->winx*ortho2[0]*data->winmat[0][0];
437         dy= data->winy*ortho2[1]*data->winmat[1][1];
438         w= sqrt(dx*dx + dy*dy)/w;
439
440         /* w squared because we are working with area */
441         area= area*w*w;
442
443         /* viewport of the screen test */
444
445         /* project point on screen */
446         Mat4MulVec4fl(data->winmat, co);
447         if(co[3] != 0.0f) {
448                 co[0]= 0.5f*data->winx*(1.0f + co[0]/co[3]);
449                 co[1]= 0.5f*data->winy*(1.0f + co[1]/co[3]);
450         }
451
452         /* screen space radius */
453         radius= sqrt(area/M_PI);
454
455         /* make smaller using fallof once over screen edge */
456         *viewport= 1.0f;
457
458         if(co[0]+radius < 0.0f)
459                 *viewport *= psys_render_viewport_falloff(vprate, -(co[0]+radius), data->winx);
460         else if(co[0]-radius > data->winx)
461                 *viewport *= psys_render_viewport_falloff(vprate, (co[0]-radius) - data->winx, data->winx);
462
463         if(co[1]+radius < 0.0f)
464                 *viewport *= psys_render_viewport_falloff(vprate, -(co[1]+radius), data->winy);
465         else if(co[1]-radius > data->winy)
466                 *viewport *= psys_render_viewport_falloff(vprate, (co[1]-radius) - data->winy, data->winy);
467         
468         return area;
469 }
470
471 void psys_render_set(Object *ob, ParticleSystem *psys, float viewmat[][4], float winmat[][4], int winx, int winy, int timeoffset)
472 {
473         ParticleRenderData*data;
474         ParticleSystemModifierData *psmd= psys_get_modifier(ob, psys);
475
476         if(!G.rendering)
477                 return;
478         if(psys->renderdata)
479                 return;
480
481         data= MEM_callocN(sizeof(ParticleRenderData), "ParticleRenderData");
482
483         data->child= psys->child;
484         data->totchild= psys->totchild;
485         data->pathcache= psys->pathcache;
486         data->totcached= psys->totcached;
487         data->childcache= psys->childcache;
488         data->totchildcache= psys->totchildcache;
489
490         if(psmd->dm)
491                 data->dm= CDDM_copy(psmd->dm);
492         data->totdmvert= psmd->totdmvert;
493         data->totdmedge= psmd->totdmedge;
494         data->totdmface= psmd->totdmface;
495
496         psys->child= NULL;
497         psys->pathcache= NULL;
498         psys->childcache= NULL;
499         psys->totchild= psys->totcached= psys->totchildcache= 0;
500
501         Mat4CpyMat4(data->winmat, winmat);
502         Mat4MulMat4(data->viewmat, ob->obmat, viewmat);
503         Mat4MulMat4(data->mat, data->viewmat, winmat);
504         data->winx= winx;
505         data->winy= winy;
506
507         data->timeoffset= timeoffset;
508
509         psys->renderdata= data;
510 }
511
512 void psys_render_restore(Object *ob, ParticleSystem *psys)
513 {
514         ParticleRenderData*data;
515         ParticleSystemModifierData *psmd= psys_get_modifier(ob, psys);
516
517         data= psys->renderdata;
518         if(!data)
519                 return;
520         
521         if(data->elems)
522                 MEM_freeN(data->elems);
523
524         if(psmd->dm) {
525                 psmd->dm->needsFree= 1;
526                 psmd->dm->release(psmd->dm);
527         }
528
529         psys_free_path_cache(psys);
530
531         if(psys->child){
532                 MEM_freeN(psys->child);
533                 psys->child= 0;
534                 psys->totchild= 0;
535         }
536
537         psys->child= data->child;
538         psys->totchild= data->totchild;
539         psys->pathcache= data->pathcache;
540         psys->totcached= data->totcached;
541         psys->childcache= data->childcache;
542         psys->totchildcache= data->totchildcache;
543
544         psmd->dm= data->dm;
545         psmd->totdmvert= data->totdmvert;
546         psmd->totdmedge= data->totdmedge;
547         psmd->totdmface= data->totdmface;
548         psmd->flag &= ~eParticleSystemFlag_psys_updated;
549
550         if(psmd->dm)
551                 psys_calc_dmcache(ob, psmd->dm, psys);
552
553         MEM_freeN(data);
554         psys->renderdata= NULL;
555 }
556
557 int psys_render_simplify_distribution(ParticleThreadContext *ctx, int tot)
558 {
559         DerivedMesh *dm= ctx->dm;
560         Mesh *me= (Mesh*)(ctx->ob->data);
561         MFace *mf, *mface;
562         MVert *mvert;
563         ParticleRenderData *data;
564         ParticleRenderElem *elems, *elem;
565         ParticleSettings *part= ctx->psys->part;
566         float *facearea, (*facecenter)[3], size[3], fac, powrate, scaleclamp;
567         float co1[3], co2[3], co3[3], co4[3], lambda, arearatio, t, area, viewport;
568         double vprate;
569         int *origindex, *facetotvert;
570         int a, b, totorigface, totface, newtot, skipped;
571
572         if(part->draw_as!=PART_DRAW_PATH || !(part->draw & PART_DRAW_REN_STRAND))
573                 return tot;
574         if(!ctx->psys->renderdata)
575                 return tot;
576
577         data= ctx->psys->renderdata;
578         if(data->timeoffset)
579                 return 0;
580         if(!(part->simplify_flag & PART_SIMPLIFY_ENABLE))
581                 return tot;
582
583         mvert= dm->getVertArray(dm);
584         mface= dm->getFaceArray(dm);
585         origindex= dm->getFaceDataArray(dm, CD_ORIGINDEX);
586         totface= dm->getNumFaces(dm);
587         totorigface= me->totface;
588
589         if(totface == 0 || totorigface == 0 || origindex == NULL)
590                 return tot;
591
592         facearea= MEM_callocN(sizeof(float)*totorigface, "SimplifyFaceArea");
593         facecenter= MEM_callocN(sizeof(float[3])*totorigface, "SimplifyFaceCenter");
594         facetotvert= MEM_callocN(sizeof(int)*totorigface, "SimplifyFaceArea");
595         elems= MEM_callocN(sizeof(ParticleRenderElem)*totorigface, "SimplifyFaceElem");
596
597         if(data->elems)
598                 MEM_freeN(data->elems);
599
600         data->dosimplify= 1;
601         data->elems= elems;
602         data->origindex= origindex;
603
604         /* compute number of children per original face */
605         for(a=0; a<tot; a++) {
606                 b= origindex[ctx->index[a]];
607                 if(b != -1)
608                         elems[b].totchild++;
609         }
610
611         /* compute areas and centers of original faces */
612         for(mf=mface, a=0; a<totface; a++, mf++) {
613                 b= origindex[a];
614
615                 if(b != -1) {
616                         VECCOPY(co1, mvert[mf->v1].co);
617                         VECCOPY(co2, mvert[mf->v2].co);
618                         VECCOPY(co3, mvert[mf->v3].co);
619
620                         VECADD(facecenter[b], facecenter[b], co1);
621                         VECADD(facecenter[b], facecenter[b], co2);
622                         VECADD(facecenter[b], facecenter[b], co3);
623
624                         if(mf->v4) {
625                                 VECCOPY(co4, mvert[mf->v4].co);
626                                 VECADD(facecenter[b], facecenter[b], co4);
627                                 facearea[b] += AreaQ3Dfl(co1, co2, co3, co4);
628                                 facetotvert[b] += 4;
629                         }
630                         else {
631                                 facearea[b] += AreaT3Dfl(co1, co2, co3);
632                                 facetotvert[b] += 3;
633                         }
634                 }
635         }
636
637         for(a=0; a<totorigface; a++)
638                 if(facetotvert[a] > 0)
639                         VecMulf(facecenter[a], 1.0f/facetotvert[a]);
640
641         /* for conversion from BU area / pixel area to reference screen size */
642         mesh_get_texspace(me, 0, 0, size);
643         fac= ((size[0] + size[1] + size[2])/3.0f)/part->simplify_refsize;
644         fac= fac*fac;
645
646         powrate= log(0.5f)/log(part->simplify_rate*0.5f);
647         if(part->simplify_flag & PART_SIMPLIFY_VIEWPORT)
648                 vprate= pow(1.0 - part->simplify_viewport, 5.0);
649         else
650                 vprate= 1.0;
651
652         /* set simplification parameters per original face */
653         for(a=0, elem=elems; a<totorigface; a++, elem++) {
654                 area = psys_render_projected_area(ctx->psys, facecenter[a], facearea[a], vprate, &viewport);
655                 arearatio= fac*area/facearea[a];
656
657                 if((arearatio < 1.0f || viewport < 1.0f) && elem->totchild) {
658                         /* lambda is percentage of elements to keep */
659                         lambda= (arearatio < 1.0f)? pow(arearatio, powrate): 1.0f;
660                         lambda *= viewport;
661
662                         lambda= MAX2(lambda, 1.0f/elem->totchild);
663
664                         /* compute transition region */
665                         t= part->simplify_transition;
666                         elem->t= (lambda-t < 0.0f)? lambda: (lambda+t > 1.0f)? 1.0f-lambda: t;
667                         elem->reduce= 1;
668
669                         /* scale at end and beginning of the transition region */
670                         elem->scalemax= (lambda+t < 1.0f)? 1.0f/lambda: 1.0f/(1.0f - elem->t*elem->t/t);
671                         elem->scalemin= (lambda+t < 1.0f)? 0.0f: elem->scalemax*(1.0f-elem->t/t);
672
673                         elem->scalemin= sqrt(elem->scalemin);
674                         elem->scalemax= sqrt(elem->scalemax);
675
676                         /* clamp scaling */
677                         scaleclamp= MIN2(elem->totchild, 10.0f);
678                         elem->scalemin= MIN2(scaleclamp, elem->scalemin);
679                         elem->scalemax= MIN2(scaleclamp, elem->scalemax);
680
681                         /* extend lambda to include transition */
682                         lambda= lambda + elem->t;
683                         if(lambda > 1.0f)
684                                 lambda= 1.0f;
685                 }
686                 else {
687                         lambda= arearatio;
688
689                         elem->scalemax= 1.0f; //sqrt(lambda);
690                         elem->scalemin= 1.0f; //sqrt(lambda);
691                         elem->reduce= 0;
692                 }
693
694                 elem->lambda= lambda;
695                 elem->scalemin= sqrt(elem->scalemin);
696                 elem->scalemax= sqrt(elem->scalemax);
697                 elem->curchild= 0;
698         }
699
700         MEM_freeN(facearea);
701         MEM_freeN(facecenter);
702         MEM_freeN(facetotvert);
703
704         /* move indices and set random number skipping */
705         ctx->skip= MEM_callocN(sizeof(int)*tot, "SimplificationSkip");
706
707         skipped= 0;
708         for(a=0, newtot=0; a<tot; a++) {
709                 b= origindex[ctx->index[a]];
710                 if(b != -1) {
711                         if(elems[b].curchild++ < ceil(elems[b].lambda*elems[b].totchild)) {
712                                 ctx->index[newtot]= ctx->index[a];
713                                 ctx->skip[newtot]= skipped;
714                                 skipped= 0;
715                                 newtot++;
716                         }
717                         else skipped++;
718                 }
719                 else skipped++;
720         }
721
722         for(a=0, elem=elems; a<totorigface; a++, elem++)
723                 elem->curchild= 0;
724
725         return newtot;
726 }
727
728 int psys_render_simplify_params(ParticleSystem *psys, ChildParticle *cpa, float *params)
729 {
730         ParticleRenderData *data;
731         ParticleRenderElem *elem;
732         float x, w, scale, alpha, lambda, t, scalemin, scalemax;
733         int b;
734
735         if(!(psys->renderdata && (psys->part->simplify_flag & PART_SIMPLIFY_ENABLE)))
736                 return 0;
737         
738         data= psys->renderdata;
739         if(!data->dosimplify)
740                 return 0;
741         
742         b= data->origindex[cpa->num];
743         if(b == -1)
744                 return 0;
745
746         elem= &data->elems[b];
747
748         lambda= elem->lambda;
749         t= elem->t;
750         scalemin= elem->scalemin;
751         scalemax= elem->scalemax;
752
753         if(!elem->reduce) {
754                 scale= scalemin;
755                 alpha= 1.0f;
756         }
757         else {
758                 x= (elem->curchild+0.5f)/elem->totchild;
759                 if(x < lambda-t) {
760                         scale= scalemax;
761                         alpha= 1.0f;
762                 }
763                 else if(x >= lambda+t) {
764                         scale= scalemin;
765                         alpha= 0.0f;
766                 }
767                 else {
768                         w= (lambda+t - x)/(2.0f*t);
769                         scale= scalemin + (scalemax - scalemin)*w;
770                         alpha= w;
771                 }
772         }
773
774         params[0]= scale;
775         params[1]= alpha;
776
777         elem->curchild++;
778
779         return 1;
780 }
781
782 /************************************************/
783 /*                      Interpolated Particles                          */
784 /************************************************/
785 static float interpolate_particle_value(float v1, float v2, float v3, float v4, float *w, int four)
786 {
787         float value;
788
789         value= w[0]*v1 + w[1]*v2 + w[2]*v3;
790         if(four)
791                 value += w[3]*v4;
792         
793         return value;
794 }
795 static void weighted_particle_vector(float *v1, float *v2, float *v3, float *v4, float *weights, float *vec)
796 {
797         vec[0]= weights[0]*v1[0] + weights[1]*v2[0] + weights[2]*v3[0] + weights[3]*v4[0];
798         vec[1]= weights[0]*v1[1] + weights[1]*v2[1] + weights[2]*v3[1] + weights[3]*v4[1];
799         vec[2]= weights[0]*v1[2] + weights[1]*v2[2] + weights[2]*v3[2] + weights[3]*v4[2];
800 }
801 static void interpolate_particle(short type, ParticleKey keys[4], float dt, ParticleKey *result, int velocity)
802 {
803         float t[4];
804
805         if(type<0) {
806                 VecfCubicInterpol(keys[1].co, keys[1].vel, keys[2].co, keys[2].vel, dt, result->co, result->vel);
807         }
808         else {
809                 set_four_ipo(dt, t, type);
810
811                 weighted_particle_vector(keys[0].co, keys[1].co, keys[2].co, keys[3].co, t, result->co);
812
813                 if(velocity){
814                         float temp[3];
815
816                         if(dt>0.999f){
817                                 set_four_ipo(dt-0.001f, t, type);
818                                 weighted_particle_vector(keys[0].co, keys[1].co, keys[2].co, keys[3].co, t, temp);
819                                 VECSUB(result->vel, result->co, temp);
820                         }
821                         else{
822                                 set_four_ipo(dt+0.001f, t, type);
823                                 weighted_particle_vector(keys[0].co, keys[1].co, keys[2].co, keys[3].co, t, temp);
824                                 VECSUB(result->vel, temp, result->co);
825                         }
826                 }
827         }
828 }
829
830
831
832 /************************************************/
833 /*                      Particles on a dm                                       */
834 /************************************************/
835 /* interpolate a location on a face based on face coordinates */
836 void psys_interpolate_face(MVert *mvert, MFace *mface, MTFace *tface, float (*orcodata)[3], float *w, float *vec, float *nor, float *utan, float *vtan, float *orco,float *ornor){
837         float *v1=0, *v2=0, *v3=0, *v4=0;
838         float e1[3],e2[3],s1,s2,t1,t2;
839         float *uv1, *uv2, *uv3, *uv4;
840         float n1[3], n2[3], n3[3], n4[3];
841         float tuv[4][2];
842         float *o1, *o2, *o3, *o4;
843
844         v1= (mvert+mface->v1)->co;
845         v2= (mvert+mface->v2)->co;
846         v3= (mvert+mface->v3)->co;
847         VECCOPY(n1,(mvert+mface->v1)->no);
848         VECCOPY(n2,(mvert+mface->v2)->no);
849         VECCOPY(n3,(mvert+mface->v3)->no);
850         Normalize(n1);
851         Normalize(n2);
852         Normalize(n3);
853
854         if(mface->v4) {
855                 v4= (mvert+mface->v4)->co;
856                 VECCOPY(n4,(mvert+mface->v4)->no);
857                 Normalize(n4);
858                 
859                 vec[0]= w[0]*v1[0] + w[1]*v2[0] + w[2]*v3[0] + w[3]*v4[0];
860                 vec[1]= w[0]*v1[1] + w[1]*v2[1] + w[2]*v3[1] + w[3]*v4[1];
861                 vec[2]= w[0]*v1[2] + w[1]*v2[2] + w[2]*v3[2] + w[3]*v4[2];
862
863                 if(nor){
864                         if(mface->flag & ME_SMOOTH){
865                                 nor[0]= w[0]*n1[0] + w[1]*n2[0] + w[2]*n3[0] + w[3]*n4[0];
866                                 nor[1]= w[0]*n1[1] + w[1]*n2[1] + w[2]*n3[1] + w[3]*n4[1];
867                                 nor[2]= w[0]*n1[2] + w[1]*n2[2] + w[2]*n3[2] + w[3]*n4[2];
868                         }
869                         else
870                                 CalcNormFloat4(v1,v2,v3,v4,nor);
871                 }
872         }
873         else {
874                 vec[0]= w[0]*v1[0] + w[1]*v2[0] + w[2]*v3[0];
875                 vec[1]= w[0]*v1[1] + w[1]*v2[1] + w[2]*v3[1];
876                 vec[2]= w[0]*v1[2] + w[1]*v2[2] + w[2]*v3[2];
877                 
878                 if(nor){
879                         if(mface->flag & ME_SMOOTH){
880                                 nor[0]= w[0]*n1[0] + w[1]*n2[0] + w[2]*n3[0];
881                                 nor[1]= w[0]*n1[1] + w[1]*n2[1] + w[2]*n3[1];
882                                 nor[2]= w[0]*n1[2] + w[1]*n2[2] + w[2]*n3[2];
883                         }
884                         else
885                                 CalcNormFloat(v1,v2,v3,nor);
886                 }
887         }
888         
889         /* calculate tangent vectors */
890         if(utan && vtan){
891                 if(tface){
892                         uv1= tface->uv[0];
893                         uv2= tface->uv[1];
894                         uv3= tface->uv[2];
895                         uv4= tface->uv[3];
896                 }
897                 else{
898                         uv1= tuv[0]; uv2= tuv[1]; uv3= tuv[2]; uv4= tuv[3];
899                         spheremap(v1[0], v1[1], v1[2], uv1, uv1+1);
900                         spheremap(v2[0], v2[1], v2[2], uv2, uv2+1);
901                         spheremap(v3[0], v3[1], v3[2], uv3, uv3+1);
902                         if(v4)
903                                 spheremap(v4[0], v4[1], v4[2], uv4, uv4+1);
904                 }
905
906                 if(v4){
907                         s1= uv3[0] - uv1[0];
908                         s2= uv4[0] - uv1[0];
909
910                         t1= uv3[1] - uv1[1];
911                         t2= uv4[1] - uv1[1];
912
913                         VecSubf(e1, v3, v1);
914                         VecSubf(e2, v4, v1);
915                 }
916                 else{
917                         s1= uv2[0] - uv1[0];
918                         s2= uv3[0] - uv1[0];
919
920                         t1= uv2[1] - uv1[1];
921                         t2= uv3[1] - uv1[1];
922
923                         VecSubf(e1, v2, v1);
924                         VecSubf(e2, v3, v1);
925                 }
926
927                 vtan[0] = (s1*e2[0] - s2*e1[0]);
928                 vtan[1] = (s1*e2[1] - s2*e1[1]);
929                 vtan[2] = (s1*e2[2] - s2*e1[2]);
930
931                 utan[0] = (t1*e2[0] - t2*e1[0]);
932                 utan[1] = (t1*e2[1] - t2*e1[1]);
933                 utan[2] = (t1*e2[2] - t2*e1[2]);
934         }
935
936         if(orco) {
937                 if(orcodata) {
938                         o1= orcodata[mface->v1];
939                         o2= orcodata[mface->v2];
940                         o3= orcodata[mface->v3];
941
942                         if(mface->v4) {
943                                 o4= orcodata[mface->v4];
944                                 orco[0]= w[0]*o1[0] + w[1]*o2[0] + w[2]*o3[0] + w[3]*o4[0];
945                                 orco[1]= w[0]*o1[1] + w[1]*o2[1] + w[2]*o3[1] + w[3]*o4[1];
946                                 orco[2]= w[0]*o1[2] + w[1]*o2[2] + w[2]*o3[2] + w[3]*o4[2];
947
948                                 if(ornor)
949                                         CalcNormFloat4(o1, o2, o3, o4, ornor);
950                         }
951                         else {
952                                 orco[0]= w[0]*o1[0] + w[1]*o2[0] + w[2]*o3[0];
953                                 orco[1]= w[0]*o1[1] + w[1]*o2[1] + w[2]*o3[1];
954                                 orco[2]= w[0]*o1[2] + w[1]*o2[2] + w[2]*o3[2];
955
956                                 if(ornor)
957                                         CalcNormFloat(o1, o2, o3, ornor);
958                         }
959                 }
960                 else {
961                         VECCOPY(orco, vec);
962                         if(ornor)
963                                 VECCOPY(ornor, nor);
964                 }
965         }
966 }
967 void psys_interpolate_uvs(MTFace *tface, int quad, float *w, float *uvco)
968 {
969         float v10= tface->uv[0][0];
970         float v11= tface->uv[0][1];
971         float v20= tface->uv[1][0];
972         float v21= tface->uv[1][1];
973         float v30= tface->uv[2][0];
974         float v31= tface->uv[2][1];
975         float v40,v41;
976
977         if(quad) {
978                 v40= tface->uv[3][0];
979                 v41= tface->uv[3][1];
980
981                 uvco[0]= w[0]*v10 + w[1]*v20 + w[2]*v30 + w[3]*v40;
982                 uvco[1]= w[0]*v11 + w[1]*v21 + w[2]*v31 + w[3]*v41;
983         }
984         else {
985                 uvco[0]= w[0]*v10 + w[1]*v20 + w[2]*v30;
986                 uvco[1]= w[0]*v11 + w[1]*v21 + w[2]*v31;
987         }
988 }
989
990 void psys_interpolate_mcol(MCol *mcol, int quad, float *w, MCol *mc)
991 {
992         char *cp, *cp1, *cp2, *cp3, *cp4;
993
994         cp= (char *)mc;
995         cp1= (char *)&mcol[0];
996         cp2= (char *)&mcol[1];
997         cp3= (char *)&mcol[2];
998         
999         if(quad) {
1000                 cp4= (char *)&mcol[3];
1001
1002                 cp[0]= (int)(w[0]*cp1[0] + w[1]*cp2[0] + w[2]*cp3[0] + w[3]*cp4[0]);
1003                 cp[1]= (int)(w[0]*cp1[1] + w[1]*cp2[1] + w[2]*cp3[1] + w[3]*cp4[1]);
1004                 cp[2]= (int)(w[0]*cp1[2] + w[1]*cp2[2] + w[2]*cp3[2] + w[3]*cp4[2]);
1005                 cp[3]= (int)(w[0]*cp1[3] + w[1]*cp2[3] + w[2]*cp3[3] + w[3]*cp4[3]);
1006         }
1007         else {
1008                 cp[0]= (int)(w[0]*cp1[0] + w[1]*cp2[0] + w[2]*cp3[0]);
1009                 cp[1]= (int)(w[0]*cp1[1] + w[1]*cp2[1] + w[2]*cp3[1]);
1010                 cp[2]= (int)(w[0]*cp1[2] + w[1]*cp2[2] + w[2]*cp3[2]);
1011                 cp[3]= (int)(w[0]*cp1[3] + w[1]*cp2[3] + w[2]*cp3[3]);
1012         }
1013 }
1014
1015 float psys_interpolate_value_from_verts(DerivedMesh *dm, short from, int index, float *fw, float *values)
1016 {
1017         if(values==0 || index==-1)
1018                 return 0.0;
1019
1020         switch(from){
1021                 case PART_FROM_VERT:
1022                         return values[index];
1023                 case PART_FROM_FACE:
1024                 case PART_FROM_VOLUME:
1025                 {
1026                         MFace *mf=dm->getFaceData(dm,index,CD_MFACE);
1027                         return interpolate_particle_value(values[mf->v1],values[mf->v2],values[mf->v3],values[mf->v4],fw,mf->v4);
1028                 }
1029                         
1030         }
1031         return 0.0;
1032 }
1033
1034 /* conversion of pa->fw to origspace layer coordinates */
1035 static void psys_w_to_origspace(float *w, float *uv)
1036 {
1037         uv[0]= w[1] + w[2];
1038         uv[1]= w[2] + w[3];
1039 }
1040
1041 /* conversion of pa->fw to weights in face from origspace */
1042 static void psys_origspace_to_w(OrigSpaceFace *osface, int quad, float *w, float *neww)
1043 {
1044         float v[4][3], co[3];
1045
1046         v[0][0]= osface->uv[0][0]; v[0][1]= osface->uv[0][1]; v[0][2]= 0.0f;
1047         v[1][0]= osface->uv[1][0]; v[1][1]= osface->uv[1][1]; v[1][2]= 0.0f;
1048         v[2][0]= osface->uv[2][0]; v[2][1]= osface->uv[2][1]; v[2][2]= 0.0f;
1049
1050         psys_w_to_origspace(w, co);
1051         co[2]= 0.0f;
1052         
1053         if(quad) {
1054                 v[3][0]= osface->uv[3][0]; v[3][1]= osface->uv[3][1]; v[3][2]= 0.0f;
1055                 MeanValueWeights(v, 4, co, neww);
1056         }
1057         else {
1058                 MeanValueWeights(v, 3, co, neww);
1059                 neww[3]= 0.0f;
1060         }
1061 }
1062
1063 /* find the derived mesh face for a particle, set the mf passed.
1064 This is slow, can be optimized but only for many lookups, return the face lookup index*/
1065 int psys_particle_dm_face_lookup(Object *ob, DerivedMesh *dm, int index, float *fw, struct LinkNode *node)
1066 {
1067         Mesh *me= (Mesh*)ob->data;
1068         MFace *mface;
1069         OrigSpaceFace *osface;
1070         int *origindex;
1071         int quad, findex, totface;
1072         float uv[2], (*faceuv)[2];
1073
1074         mface = dm->getFaceDataArray(dm, CD_MFACE);
1075         origindex = dm->getFaceDataArray(dm, CD_ORIGINDEX);
1076         osface = dm->getFaceDataArray(dm, CD_ORIGSPACE);
1077
1078         totface = dm->getNumFaces(dm);
1079         
1080         if(osface==NULL || origindex==NULL) {
1081                 /* Assume we dont need osface data */
1082                 if (index <totface) {
1083                         //printf("\tNO CD_ORIGSPACE, assuming not needed\n");
1084                         return index;
1085                 } else {
1086                         printf("\tNO CD_ORIGSPACE, error out of range\n");
1087                         return DMCACHE_NOTFOUND;
1088                 }
1089         }
1090         else if(index >= me->totface)
1091                 return DMCACHE_NOTFOUND; /* index not in the original mesh */
1092
1093         psys_w_to_origspace(fw, uv);
1094         
1095         if(node) { /* we have a linked list of faces that we use, faster! */
1096                 for(;node; node=node->next) {
1097                         findex= GET_INT_FROM_POINTER(node->link);
1098                         faceuv= osface[findex].uv;
1099                         quad= mface[findex].v4;
1100
1101                         /* check that this intersects - Its possible this misses :/ -
1102                          * could also check its not between */
1103                         if(quad) {
1104                                 if(IsectPQ2Df(uv, faceuv[0], faceuv[1], faceuv[2], faceuv[3]))
1105                                         return findex;
1106                         }
1107                         else if(IsectPT2Df(uv, faceuv[0], faceuv[1], faceuv[2]))
1108                                 return findex;
1109                 }
1110         }
1111         else { /* if we have no node, try every face */
1112                 for(findex=0; findex<totface; findex++) {
1113                         if(origindex[findex] == index) {
1114                                 faceuv= osface[findex].uv;
1115                                 quad= mface[findex].v4;
1116
1117                                 /* check that this intersects - Its possible this misses :/ -
1118                                  * could also check its not between */
1119                                 if(quad) {
1120                                         if(IsectPQ2Df(uv, faceuv[0], faceuv[1], faceuv[2], faceuv[3]))
1121                                                 return findex;
1122                                 }
1123                                 else if(IsectPT2Df(uv, faceuv[0], faceuv[1], faceuv[2]))
1124                                         return findex;
1125                         }
1126                 }
1127         }
1128
1129         return DMCACHE_NOTFOUND;
1130 }
1131
1132 /* interprets particle data to get a point on a mesh in object space */
1133 #define PARTICLE_ON_DM_ERROR \
1134         { if(vec) { vec[0]=vec[1]=vec[2]=0.0; } \
1135           if(nor) { nor[0]=nor[1]=0.0; nor[2]=1.0; } \
1136           if(orco) { orco[0]=orco[1]=orco[2]=0.0; } \
1137           if(ornor) { ornor[0]=ornor[1]=0.0; ornor[2]=1.0; } \
1138           if(utan) { utan[0]=utan[1]=utan[2]=0.0; } \
1139           if(vtan) { vtan[0]=vtan[1]=vtan[2]=0.0; } }
1140
1141 void psys_particle_on_dm(Object *ob, DerivedMesh *dm, int from, int index, int index_dmcache, float *fw, float foffset, float *vec, float *nor, float *utan, float *vtan, float *orco, float *ornor)
1142 {
1143         float temp1[3];
1144         float (*orcodata)[3];
1145
1146         if(index < 0) { /* 'no dm' error has happened! */
1147                 PARTICLE_ON_DM_ERROR;
1148                 return;
1149         }
1150         orcodata= dm->getVertDataArray(dm, CD_ORCO);
1151
1152         if (dm->deformedOnly || index_dmcache == DMCACHE_ISCHILD) {
1153                 /* this works for meshes with deform verts only - constructive modifiers wont work properly*/
1154                 if(from == PART_FROM_VERT) {
1155                         if(index >= dm->getNumVerts(dm)) {
1156                                 PARTICLE_ON_DM_ERROR;
1157                                 return;
1158                         }
1159         
1160                         dm->getVertCo(dm,index,vec);
1161                         if(nor){
1162                                 dm->getVertNo(dm,index,nor);
1163                                 Normalize(nor);
1164                         }
1165                         if(orco)
1166                                 VECCOPY(orco, orcodata[index])
1167                         if(ornor) {
1168                                 dm->getVertNo(dm,index,nor);
1169                                 Normalize(nor);
1170                         }
1171                 }
1172                 else { /* PART_FROM_FACE / PART_FROM_VOLUME */
1173                         MFace *mface;
1174                         MTFace *mtface=0;
1175                         MVert *mvert;
1176                         int uv_index;
1177
1178                         if(index >= dm->getNumFaces(dm)) {
1179                                 PARTICLE_ON_DM_ERROR;
1180                                 return;
1181                         }
1182                         
1183                         mface=dm->getFaceData(dm,index,CD_MFACE);
1184                         mvert=dm->getVertDataArray(dm,CD_MVERT);
1185                         uv_index=CustomData_get_active_layer_index(&dm->faceData,CD_MTFACE);
1186
1187                         if(uv_index>=0){
1188                                 CustomDataLayer *layer=&dm->faceData.layers[uv_index];
1189                                 mtface= &((MTFace*)layer->data)[index];
1190                         }
1191
1192                         if(from==PART_FROM_VOLUME){
1193                                 psys_interpolate_face(mvert,mface,mtface,orcodata,fw,vec,temp1,utan,vtan,orco,ornor);
1194                                 if(nor)
1195                                         VECCOPY(nor,temp1);
1196                                 Normalize(temp1);
1197                                 VecMulf(temp1,-foffset);
1198                                 VECADD(vec,vec,temp1);
1199                         }
1200                         else
1201                                 psys_interpolate_face(mvert,mface,mtface,orcodata,fw,vec,nor,utan,vtan,orco,ornor);
1202                 }
1203         } else {
1204                 /* Need to support constructive modifiers, this is a bit more tricky
1205                         we need a customdata layer like UV's so we can position the particle */
1206                 
1207                 /* Only face supported at the moment */
1208                 if(ELEM(from, PART_FROM_FACE, PART_FROM_VOLUME)) {
1209                         /* find a face on the derived mesh that uses this face */
1210                         Mesh *me= (Mesh*)ob->data;
1211                         MVert *mvert;
1212                         MFace *mface;
1213                         MTFace *mtface;
1214                         OrigSpaceFace *osface;
1215                         int *origindex;
1216                         float fw_mod[4];
1217                         int i, totface;
1218                         
1219                         mvert= dm->getVertDataArray(dm,CD_MVERT);
1220
1221                         osface= dm->getFaceDataArray(dm, CD_ORIGSPACE);
1222                         origindex= dm->getFaceDataArray(dm, CD_ORIGINDEX);
1223
1224                         /* For this to work we need origindex and OrigSpace coords */
1225                         if(origindex==NULL || osface==NULL || index>=me->totface) {
1226                                 PARTICLE_ON_DM_ERROR;
1227                                 return;
1228                         }
1229                         
1230                         if (index_dmcache == DMCACHE_NOTFOUND)
1231                                 i = psys_particle_dm_face_lookup(ob, dm, index, fw, (LinkNode*)NULL);
1232                         else
1233                                 i = index_dmcache;
1234
1235                         totface = dm->getNumFaces(dm);
1236
1237                         /* Any time this happens, and the face has not been removed,
1238                         * its a BUG watch out for this error! */
1239                         if (i==-1) {
1240                                 printf("Cannot find original face %i\n", index);
1241                                 PARTICLE_ON_DM_ERROR;
1242                                 return;
1243                         }
1244                         else if(i >= totface)
1245                                 return;
1246
1247                         mface= dm->getFaceData(dm, i, CD_MFACE);
1248                         mtface= dm->getFaceData(dm, i, CD_MTFACE); 
1249                         osface += i;
1250
1251                         /* we need to modify the original weights to become weights for
1252                          * the derived mesh face */
1253                         psys_origspace_to_w(osface, mface->v4, fw, fw_mod);
1254
1255                         if(from==PART_FROM_VOLUME){
1256                                 psys_interpolate_face(mvert,mface,mtface,orcodata,fw_mod,vec,temp1,utan,vtan,orco,ornor);
1257                                 if(nor)
1258                                         VECCOPY(nor,temp1);
1259                                 Normalize(temp1);
1260                                 VecMulf(temp1,-foffset);
1261                                 VECADD(vec,vec,temp1);
1262                         }
1263                         else
1264                                 psys_interpolate_face(mvert,mface,mtface,orcodata,fw_mod,vec,nor,utan,vtan,orco,ornor);
1265                 }
1266                 else if(from == PART_FROM_VERT) {
1267                         if (index_dmcache == DMCACHE_NOTFOUND || index_dmcache > dm->getNumVerts(dm)) {
1268                                 PARTICLE_ON_DM_ERROR;
1269                                 return;
1270                         }
1271
1272                         dm->getVertCo(dm,index_dmcache,vec);
1273                         if(nor) {
1274                                 dm->getVertNo(dm,index_dmcache,nor);
1275                                 Normalize(nor);
1276                         }
1277                         if(orco)
1278                                 VECCOPY(orco, orcodata[index])
1279                         if(ornor) {
1280                                 dm->getVertNo(dm,index_dmcache,nor);
1281                                 Normalize(nor);
1282                         }
1283                         if(utan && vtan) {
1284                                 utan[0]= utan[1]= utan[2]= 0.0f;
1285                                 vtan[0]= vtan[1]= vtan[2]= 0.0f;
1286                         }
1287                 }
1288                 else {
1289                         PARTICLE_ON_DM_ERROR;
1290                 }
1291         }
1292 }
1293 #undef PARTICLE_ON_DM_ERROR
1294
1295 ParticleSystemModifierData *psys_get_modifier(Object *ob, ParticleSystem *psys)
1296 {
1297         ModifierData *md;
1298         ParticleSystemModifierData *psmd;
1299
1300         for(md=ob->modifiers.first; md; md=md->next){
1301                 if(md->type==eModifierType_ParticleSystem){
1302                         psmd= (ParticleSystemModifierData*) md;
1303                         if(psmd->psys==psys){
1304                                 return psmd;
1305                         }
1306                 }
1307         }
1308         return 0;
1309 }
1310 /************************************************/
1311 /*                      Particles on a shape                            */
1312 /************************************************/
1313 /* ready for future use */
1314 void psys_particle_on_shape(int distr, int index, float *fuv, float *vec, float *nor, float *utan, float *vtan, float *orco, float *ornor)
1315 {
1316         /* TODO */
1317         float zerovec[3]={0.0f,0.0f,0.0f};
1318         if(vec){
1319                 VECCOPY(vec,zerovec);
1320         }
1321         if(nor){
1322                 VECCOPY(nor,zerovec);
1323         }
1324         if(utan){
1325                 VECCOPY(utan,zerovec);
1326         }
1327         if(vtan){
1328                 VECCOPY(vtan,zerovec);
1329         }
1330         if(orco){
1331                 VECCOPY(orco,zerovec);
1332         }
1333         if(ornor){
1334                 VECCOPY(ornor,zerovec);
1335         }
1336 }
1337 /************************************************/
1338 /*                      Particles on emitter                            */
1339 /************************************************/
1340 void psys_particle_on_emitter(Object *ob, ParticleSystemModifierData *psmd, int from, int index, int index_dmcache, float *fuv, float foffset, float *vec, float *nor, float *utan, float *vtan, float *orco, float *ornor){
1341         if(psmd){
1342                 if(psmd->psys->part->distr==PART_DISTR_GRID){
1343                         if(vec){
1344                                 VECCOPY(vec,fuv);
1345                         }
1346                         return;
1347                 }
1348                 /* we cant use the num_dmcache */
1349                 psys_particle_on_dm(ob, psmd->dm,from,index,index_dmcache,fuv,foffset,vec,nor,utan,vtan,orco,ornor);
1350         }
1351         else
1352                 psys_particle_on_shape(from,index,fuv,vec,nor,utan,vtan,orco,ornor);
1353
1354 }
1355 /************************************************/
1356 /*                      Path Cache                                                      */
1357 /************************************************/
1358 static void hair_to_particle(ParticleKey *key, HairKey *hkey)
1359 {
1360         VECCOPY(key->co, hkey->co);
1361         key->time = hkey->time;
1362 }
1363 static void bp_to_particle(ParticleKey *key, BodyPoint *bp, HairKey *hkey)
1364 {
1365         VECCOPY(key->co, bp->pos);
1366         key->time = hkey->time;
1367 }
1368 static float vert_weight(MDeformVert *dvert, int group)
1369 {
1370         MDeformWeight *dw;
1371         int i;
1372         
1373         if(dvert) {
1374                 dw= dvert->dw;
1375                 for(i= dvert->totweight; i>0; i--, dw++) {
1376                         if(dw->def_nr == group) return dw->weight;
1377                         if(i==1) break; /*otherwise dw will point to somewhere it shouldn't*/
1378                 }
1379         }
1380         return 0.0;
1381 }
1382 static void do_prekink(ParticleKey *state, ParticleKey *par, float *par_rot, float time, float freq, float shape, float amplitude, short type, short axis, float obmat[][4])
1383 {
1384         float vec[3]={0.0,0.0,0.0}, q1[4]={1,0,0,0},q2[4];
1385         float t;
1386
1387         CLAMP(time,0.0,1.0);
1388
1389         if(shape!=0.0f && type!=PART_KINK_BRAID) {
1390                 if(shape<0.0f)
1391                         time= (float)pow(time, 1.0+shape);
1392                 else
1393                         time= (float)pow(time, 1.0/(1.0-shape));
1394         }
1395
1396         t=time;
1397
1398         t*=(float)M_PI*freq;
1399
1400         if(par==0) return;
1401
1402         switch(type){
1403                 case PART_KINK_CURL:
1404                         vec[axis]=1.0;
1405                         if(par_rot)
1406                                 QUATCOPY(q2,par_rot)
1407                         else
1408                                 vectoquat(par->vel,axis,(axis+1)%3, q2);
1409                         QuatMulVecf(q2,vec);
1410                         VecMulf(vec,amplitude);
1411                         VECADD(state->co,state->co,vec);
1412
1413                         VECSUB(vec,state->co,par->co);
1414
1415                         if(t!=0.0)
1416                                 VecRotToQuat(par->vel,t,q1);
1417                         
1418                         QuatMulVecf(q1,vec);
1419                         
1420                         VECADD(state->co,par->co,vec);
1421                         break;
1422                 case PART_KINK_RADIAL:
1423                         VECSUB(vec,state->co,par->co);
1424
1425                         Normalize(vec);
1426                         VecMulf(vec,amplitude*(float)sin(t));
1427
1428                         VECADD(state->co,state->co,vec);
1429                         break;
1430                 case PART_KINK_WAVE:
1431                         vec[axis]=1.0;
1432                         if(obmat)
1433                                 Mat4MulVecfl(obmat,vec);
1434
1435                         if(par_rot)
1436                                 QuatMulVecf(par_rot,vec);
1437
1438                         Projf(q1,vec,par->vel);
1439                         
1440                         VECSUB(vec,vec,q1);
1441                         Normalize(vec);
1442
1443                         VecMulf(vec,amplitude*(float)sin(t));
1444
1445                         VECADD(state->co,state->co,vec);
1446                         break;
1447                 case PART_KINK_BRAID:
1448                         if(par){
1449                                 float y_vec[3]={0.0,1.0,0.0};
1450                                 float z_vec[3]={0.0,0.0,1.0};
1451                                 float vec_from_par[3], vec_one[3], radius, state_co[3];
1452                                 float inp_y,inp_z,length;
1453                                 
1454                                 if(par_rot)
1455                                         QUATCOPY(q2,par_rot)
1456                                 else
1457                                         vectoquat(par->vel,axis,(axis+1)%3,q2);
1458                                 QuatMulVecf(q2,y_vec);
1459                                 QuatMulVecf(q2,z_vec);
1460                                 
1461                                 VECSUB(vec_from_par,state->co,par->co);
1462                                 VECCOPY(vec_one,vec_from_par);
1463                                 radius=Normalize(vec_one);
1464
1465                                 inp_y=Inpf(y_vec,vec_one);
1466                                 inp_z=Inpf(z_vec,vec_one);
1467
1468                                 if(inp_y>0.5){
1469                                         VECCOPY(state_co,y_vec);
1470
1471                                         VecMulf(y_vec,amplitude*(float)cos(t));
1472                                         VecMulf(z_vec,amplitude/2.0f*(float)sin(2.0f*t));
1473                                 }
1474                                 else if(inp_z>0.0){
1475                                         VECCOPY(state_co,z_vec);
1476                                         VecMulf(state_co,(float)sin(M_PI/3.0f));
1477                                         VECADDFAC(state_co,state_co,y_vec,-0.5f);
1478
1479                                         VecMulf(y_vec,-amplitude*(float)cos(t + M_PI/3.0f));
1480                                         VecMulf(z_vec,amplitude/2.0f*(float)cos(2.0f*t + M_PI/6.0f));
1481                                 }
1482                                 else{
1483                                         VECCOPY(state_co,z_vec);
1484                                         VecMulf(state_co,-(float)sin(M_PI/3.0f));
1485                                         VECADDFAC(state_co,state_co,y_vec,-0.5f);
1486
1487                                         VecMulf(y_vec,amplitude*(float)-sin(t+M_PI/6.0f));
1488                                         VecMulf(z_vec,amplitude/2.0f*(float)-sin(2.0f*t+M_PI/3.0f));
1489                                 }
1490
1491                                 VecMulf(state_co,amplitude);
1492                                 VECADD(state_co,state_co,par->co);
1493                                 VECSUB(vec_from_par,state->co,state_co);
1494
1495                                 length=Normalize(vec_from_par);
1496                                 VecMulf(vec_from_par,MIN2(length,amplitude/2.0f));
1497
1498                                 VECADD(state_co,par->co,y_vec);
1499                                 VECADD(state_co,state_co,z_vec);
1500                                 VECADD(state_co,state_co,vec_from_par);
1501
1502                                 shape=(2.0f*(float)M_PI)*(1.0f+shape);
1503
1504                                 if(t<shape){
1505                                         shape=t/shape;
1506                                         shape=(float)sqrt((double)shape);
1507                                         VecLerpf(state->co,state->co,state_co,shape);
1508                                 }
1509                                 else{
1510                                         VECCOPY(state->co,state_co);
1511                                 }
1512                         }
1513                         break;
1514         }
1515 }
1516 static void do_clump(ParticleKey *state, ParticleKey *par, float time, float clumpfac, float clumppow, float pa_clump)
1517 {
1518         if(par && clumpfac!=0.0){
1519                 float clump, cpow;
1520
1521                 if(clumppow<0.0)
1522                         cpow=1.0f+clumppow;
1523                 else
1524                         cpow=1.0f+9.0f*clumppow;
1525
1526                 if(clumpfac<0.0) /* clump roots instead of tips */
1527                         clump = -clumpfac*pa_clump*(float)pow(1.0-(double)time,(double)cpow);
1528                 else
1529                         clump = clumpfac*pa_clump*(float)pow((double)time,(double)cpow);
1530                 VecLerpf(state->co,state->co,par->co,clump);
1531         }
1532 }
1533 int do_guide(ParticleKey *state, int pa_num, float time, ListBase *lb)
1534 {
1535         PartDeflect *pd;
1536         ParticleEffectorCache *ec;
1537         Object *eob;
1538         Curve *cu;
1539         ParticleKey key, par;
1540
1541         float effect[3]={0.0,0.0,0.0}, distance, f_force, mindist, totforce=0.0;
1542         float guidevec[4], guidedir[3], rot2[4], temp[3], angle, pa_loc[3], pa_zero[3]={0.0f,0.0f,0.0f};
1543         float veffect[3]={0.0,0.0,0.0}, guidetime;
1544
1545         effect[0]=effect[1]=effect[2]=0.0;
1546
1547         if(lb->first){
1548                 for(ec = lb->first; ec; ec= ec->next){
1549                         eob= ec->ob;
1550                         if(ec->type & PSYS_EC_EFFECTOR){
1551                                 pd=eob->pd;
1552                                 if(pd->forcefield==PFIELD_GUIDE){
1553                                         cu = (Curve*)eob->data;
1554
1555                                         distance=ec->distances[pa_num];
1556                                         mindist=pd->f_strength;
1557
1558                                         VECCOPY(pa_loc, ec->locations+3*pa_num);
1559                                         VECCOPY(pa_zero,pa_loc);
1560                                         VECADD(pa_zero,pa_zero,ec->firstloc);
1561
1562                                         guidetime=time/(1.0-pd->free_end);
1563
1564                                         /* WARNING: bails out with continue here */
1565                                         if(((pd->flag & PFIELD_USEMAX) && distance>pd->maxdist) || guidetime>1.0f) continue;
1566
1567                                         if(guidetime>1.0f) continue;
1568
1569                                         /* calculate contribution factor for this guide */
1570                                         f_force=1.0f;
1571                                         if(distance<=mindist);
1572                                         else if(pd->flag & PFIELD_USEMAX) {
1573                                                 if(mindist>=pd->maxdist) f_force= 0.0f;
1574                                                 else if(pd->f_power!=0.0f){
1575                                                         f_force= 1.0f - (distance-mindist)/(pd->maxdist - mindist);
1576                                                         f_force = (float)pow(f_force, pd->f_power);
1577                                                 }
1578                                         }
1579                                         else if(pd->f_power!=0.0f){
1580                                                 f_force= 1.0f/(1.0f + distance-mindist);
1581                                                 f_force = (float)pow(f_force, pd->f_power);
1582                                         }
1583
1584                                         if(pd->flag & PFIELD_GUIDE_PATH_ADD)
1585                                                 where_on_path(eob, f_force*guidetime, guidevec, guidedir);
1586                                         else
1587                                                 where_on_path(eob, guidetime, guidevec, guidedir);
1588
1589                                         Mat4MulVecfl(ec->ob->obmat,guidevec);
1590                                         Mat4Mul3Vecfl(ec->ob->obmat,guidedir);
1591
1592                                         Normalize(guidedir);
1593
1594                                         if(guidetime!=0.0){
1595                                                 /* curve direction */
1596                                                 Crossf(temp, ec->firstdir, guidedir);
1597                                                 angle=Inpf(ec->firstdir,guidedir)/(VecLength(ec->firstdir));
1598                                                 angle=saacos(angle);
1599                                                 VecRotToQuat(temp,angle,rot2);
1600                                                 QuatMulVecf(rot2,pa_loc);
1601
1602                                                 /* curve tilt */
1603                                                 VecRotToQuat(guidedir,guidevec[3]-ec->firstloc[3],rot2);
1604                                                 QuatMulVecf(rot2,pa_loc);
1605
1606                                                 //vectoquat(guidedir, pd->kink_axis, (pd->kink_axis+1)%3, q);
1607                                                 //QuatMul(par.rot,rot2,q);
1608                                         }
1609                                         //else{
1610                                         //      par.rot[0]=1.0f;
1611                                         //      par.rot[1]=par.rot[2]=par.rot[3]=0.0f;
1612                                         //}
1613
1614                                         /* curve taper */
1615                                         if(cu->taperobj)
1616                                                 VecMulf(pa_loc,calc_taper(cu->taperobj,(int)(f_force*guidetime*100.0),100));
1617                                         /* TODO */
1618                                         //else{
1619                                         ///* curve size*/
1620                                         //      calc_curve_subdiv_radius(cu,cu->nurb.first,((Nurb*)cu->nurb.first)->
1621                                         //}
1622                                         par.co[0]=par.co[1]=par.co[2]=0.0f;
1623                                         VECCOPY(key.co,pa_loc);
1624                                         do_prekink(&key, &par, 0, guidetime, pd->kink_freq, pd->kink_shape, pd->kink_amp, pd->kink, pd->kink_axis, 0);
1625                                         do_clump(&key, &par, guidetime, pd->clump_fac, pd->clump_pow, 1.0f);
1626                                         VECCOPY(pa_loc,key.co);
1627
1628                                         VECADD(pa_loc,pa_loc,guidevec);
1629                                         VECSUB(pa_loc,pa_loc,pa_zero);
1630                                         VECADDFAC(effect,effect,pa_loc,f_force);
1631                                         VECADDFAC(veffect,veffect,guidedir,f_force);
1632                                         totforce+=f_force;
1633                                 }
1634                         }
1635                 }
1636
1637                 if(totforce!=0.0){
1638                         if(totforce>1.0)
1639                                 VecMulf(effect,1.0f/totforce);
1640                         CLAMP(totforce,0.0,1.0);
1641                         VECADD(effect,effect,pa_zero);
1642                         VecLerpf(state->co,state->co,effect,totforce);
1643
1644                         Normalize(veffect);
1645                         VecMulf(veffect,VecLength(state->vel));
1646                         VECCOPY(state->vel,veffect);
1647                         return 1;
1648                 }
1649         }
1650         return 0;
1651 }
1652 static void do_rough(float *loc, float t, float fac, float size, float thres, ParticleKey *state)
1653 {
1654         float rough[3];
1655         float rco[3];
1656
1657         if(thres!=0.0)
1658                 if((float)fabs((float)(-1.5+loc[0]+loc[1]+loc[2]))<1.5f*thres) return;
1659
1660         VECCOPY(rco,loc);
1661         VecMulf(rco,t);
1662         rough[0]=-1.0f+2.0f*BLI_gTurbulence(size, rco[0], rco[1], rco[2], 2,0,2);
1663         rough[1]=-1.0f+2.0f*BLI_gTurbulence(size, rco[1], rco[2], rco[0], 2,0,2);
1664         rough[2]=-1.0f+2.0f*BLI_gTurbulence(size, rco[2], rco[0], rco[1], 2,0,2);
1665         VECADDFAC(state->co,state->co,rough,fac);
1666 }
1667 static void do_rough_end(float *loc, float t, float fac, float shape, ParticleKey *state, ParticleKey *par)
1668 {
1669         float rough[3], rnor[3];
1670         float roughfac;
1671
1672         roughfac=fac*(float)pow((double)t,shape);
1673         VECCOPY(rough,loc);
1674         rough[0]=-1.0f+2.0f*rough[0];
1675         rough[1]=-1.0f+2.0f*rough[1];
1676         rough[2]=-1.0f+2.0f*rough[2];
1677         VecMulf(rough,roughfac);
1678
1679
1680         if(par){
1681                 VECCOPY(rnor,par->vel);
1682         }
1683         else{
1684                 VECCOPY(rnor,state->vel);
1685         }
1686         Normalize(rnor);
1687         Projf(rnor,rough,rnor);
1688         VECSUB(rough,rough,rnor);
1689
1690         VECADD(state->co,state->co,rough);
1691 }
1692 static void do_path_effectors(Object *ob, ParticleSystem *psys, int i, ParticleCacheKey *ca, int k, int steps, float *rootco, float effector, float dfra, float cfra, float *length, float *vec)
1693 {
1694         float force[3] = {0.0f,0.0f,0.0f}, vel[3] = {0.0f,0.0f,0.0f};
1695         ParticleKey eff_key;
1696         ParticleData *pa;
1697
1698         VECCOPY(eff_key.co,(ca-1)->co);
1699         VECCOPY(eff_key.vel,(ca-1)->vel);
1700         QUATCOPY(eff_key.rot,(ca-1)->rot);
1701
1702         pa= psys->particles+i;
1703         do_effectors(i, pa, &eff_key, ob, psys, rootco, force, vel, dfra, cfra);
1704
1705         VecMulf(force, effector*pow((float)k / (float)steps, 100.0f * psys->part->eff_hair) / (float)steps);
1706
1707         VecAddf(force, force, vec);
1708
1709         Normalize(force);
1710
1711         if(k < steps) {
1712                 VecSubf(vec, (ca+1)->co, ca->co);
1713                 *length = VecLength(vec);
1714         }
1715
1716         VECADDFAC(ca->co, (ca-1)->co, force, *length);
1717 }
1718 static int check_path_length(int k, ParticleCacheKey *keys, ParticleCacheKey *state, float max_length, float *cur_length, float length, float *dvec)
1719 {
1720         if(*cur_length + length > max_length){
1721                 //if(p<totparent){
1722                 //      if(k<=(int)cache[totpart+p]->time){
1723                 //              /* parents need to be calculated fully first so that they don't mess up their children */
1724                 //              /* we'll make a note of where we got to though so that they're easy to finish later */
1725                 //              state->time=(max_length-*cur_length)/length;
1726                 //              cache[totpart+p]->time=(float)k;
1727                 //      }
1728                 //}
1729                 //else{
1730                 VecMulf(dvec, (max_length - *cur_length) / length);
1731                 VECADD(state->co, (state - 1)->co, dvec);
1732                 keys->steps = k;
1733                 /* something over the maximum step value */
1734                 return k=100000;
1735                 //}
1736         }
1737         else {
1738                 *cur_length+=length;
1739                 return k;
1740         }
1741 }
1742 static void finalize_path_length(ParticleCacheKey *keys)
1743 {
1744         ParticleCacheKey *state = keys;
1745         float dvec[3];
1746         state += state->steps;
1747
1748         VECSUB(dvec, state->co, (state - 1)->co);
1749         VecMulf(dvec, state->steps);
1750         VECADD(state->co, (state - 1)->co, dvec);
1751 }
1752 static void offset_child(ChildParticle *cpa, ParticleKey *par, ParticleKey *child, float flat, float radius)
1753 {
1754         VECCOPY(child->co,cpa->fuv);
1755         VecMulf(child->co,radius);
1756
1757         child->co[0]*=flat;
1758
1759         VECCOPY(child->vel,par->vel);
1760
1761         QuatMulVecf(par->rot,child->co);
1762
1763         QUATCOPY(child->rot,par->rot);
1764
1765         VECADD(child->co,child->co,par->co);
1766 }
1767 float *psys_cache_vgroup(DerivedMesh *dm, ParticleSystem *psys, int vgroup)
1768 {
1769         float *vg=0;
1770
1771         if(psys->vgroup[vgroup]){
1772                 MDeformVert *dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
1773                 if(dvert){
1774                         int totvert=dm->getNumVerts(dm), i;
1775                         vg=MEM_callocN(sizeof(float)*totvert, "vg_cache");
1776                         if(psys->vg_neg&(1<<vgroup)){
1777                                 for(i=0; i<totvert; i++)
1778                                         vg[i]=1.0f-vert_weight(dvert+i,psys->vgroup[vgroup]-1);
1779                         }
1780                         else{
1781                                 for(i=0; i<totvert; i++)
1782                                         vg[i]=vert_weight(dvert+i,psys->vgroup[vgroup]-1);
1783                         }
1784                 }
1785         }
1786         return vg;
1787 }
1788 void psys_find_parents(Object *ob, ParticleSystemModifierData *psmd, ParticleSystem *psys)
1789 {
1790         ParticleSettings *part=psys->part;
1791         KDTree *tree;
1792         ChildParticle *cpa;
1793         int p, totparent,totchild=psys->totchild;
1794         float co[3], orco[3];
1795         int from=PART_FROM_FACE;
1796         totparent=(int)(totchild*part->parents*0.3);
1797
1798         tree=BLI_kdtree_new(totparent);
1799
1800         for(p=0,cpa=psys->child; p<totparent; p++,cpa++){
1801                 psys_particle_on_emitter(ob,psmd,from,cpa->num,-1,cpa->fuv,cpa->foffset,co,0,0,0,orco,0);
1802                 BLI_kdtree_insert(tree, p, orco, NULL);
1803         }
1804
1805         BLI_kdtree_balance(tree);
1806
1807         for(; p<totchild; p++,cpa++){
1808                 psys_particle_on_emitter(ob,psmd,from,cpa->num,DMCACHE_ISCHILD,cpa->fuv,cpa->foffset,co,0,0,0,orco,0);
1809                 cpa->parent=BLI_kdtree_find_nearest(tree, orco, NULL, NULL);
1810         }
1811
1812         BLI_kdtree_free(tree);
1813 }
1814
1815 static void get_strand_normal(Material *ma, float *surfnor, float surfdist, float *nor)
1816 {
1817         float cross[3], nstrand[3], vnor[3], blend;
1818
1819         if(!((ma->mode & MA_STR_SURFDIFF) || (ma->strand_surfnor > 0.0f)))
1820                 return;
1821
1822         if(ma->mode & MA_STR_SURFDIFF) {
1823                 Crossf(cross, surfnor, nor);
1824                 Crossf(nstrand, nor, cross);
1825
1826                 blend= INPR(nstrand, surfnor);
1827                 CLAMP(blend, 0.0f, 1.0f);
1828
1829                 VecLerpf(vnor, nstrand, surfnor, blend);
1830                 Normalize(vnor);
1831         }
1832         else
1833                 VECCOPY(vnor, nor)
1834         
1835         if(ma->strand_surfnor > 0.0f) {
1836                 if(ma->strand_surfnor > surfdist) {
1837                         blend= (ma->strand_surfnor - surfdist)/ma->strand_surfnor;
1838                         VecLerpf(vnor, vnor, surfnor, blend);
1839                         Normalize(vnor);
1840                 }
1841         }
1842
1843         VECCOPY(nor, vnor);
1844 }
1845
1846 int psys_threads_init_path(ParticleThread *threads, float cfra, int editupdate)
1847 {
1848         ParticleThreadContext *ctx= threads[0].ctx;
1849         Object *ob= ctx->ob;
1850         ParticleSystem *psys= ctx->psys;
1851         ParticleSettings *part = psys->part;
1852         ParticleEditSettings *pset = &G.scene->toolsettings->particle;
1853         int totparent=0, between=0;
1854         int steps = (int)pow(2.0,(double)part->draw_step);
1855         int totchild = psys->totchild;
1856         int i, seed, totthread= threads[0].tot;
1857
1858         /*---start figuring out what is actually wanted---*/
1859         if(psys_in_edit_mode(psys))
1860                 if(psys->renderdata==0 && (psys->edit==NULL || pset->flag & PE_SHOW_CHILD)==0)
1861                         totchild=0;
1862
1863         if(totchild && part->from!=PART_FROM_PARTICLE && part->childtype==PART_CHILD_FACES){
1864                 totparent=(int)(totchild*part->parents*0.3);
1865                 /* part->parents could still be 0 so we can't test with totparent */
1866                 between=1;
1867         }
1868
1869         if(psys->renderdata)
1870                 steps=(int)pow(2.0,(double)part->ren_step);
1871         else{
1872                 totchild=(int)((float)totchild*(float)part->disp/100.0f);
1873                 totparent=MIN2(totparent,totchild);
1874         }
1875
1876         if(totchild==0) return 0;
1877
1878         /* init random number generator */
1879         if(ctx->psys->part->flag & PART_ANIM_BRANCHING)
1880                 seed= 31415926 + ctx->psys->seed + (int)cfra;
1881         else
1882                 seed= 31415926 + ctx->psys->seed;
1883         
1884         if(part->flag & PART_BRANCHING || ctx->editupdate || totchild < 10000)
1885                 totthread= 1;
1886         
1887         for(i=0; i<totthread; i++) {
1888                 threads[i].rng_path= rng_new(seed);
1889                 threads[i].tot= totthread;
1890         }
1891
1892         /* fill context values */
1893         ctx->between= between;
1894         ctx->steps= steps;
1895         ctx->totchild= totchild;
1896         ctx->totparent= totparent;
1897         ctx->cfra= cfra;
1898
1899         psys->lattice = psys_get_lattice(ob, psys);
1900
1901         /* cache all relevant vertex groups if they exist */
1902         if(part->from!=PART_FROM_PARTICLE){
1903                 ctx->vg_length = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_LENGTH);
1904                 ctx->vg_clump = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_CLUMP);
1905                 ctx->vg_kink = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_KINK);
1906                 ctx->vg_rough1 = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_ROUGH1);
1907                 ctx->vg_rough2 = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_ROUGH2);
1908                 ctx->vg_roughe = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_ROUGHE);
1909                 if(psys->part->flag & PART_CHILD_EFFECT)
1910                         ctx->vg_effector = psys_cache_vgroup(ctx->dm,psys,PSYS_VG_EFFECTOR);
1911         }
1912
1913         /* set correct ipo timing */
1914         if(part->flag&PART_ABS_TIME && part->ipo){
1915                 calc_ipo(part->ipo, cfra);
1916                 execute_ipo((ID *)part, part->ipo);
1917         }
1918
1919         return 1;
1920 }
1921
1922 /* note: this function must be thread safe, except for branching! */
1923 void psys_thread_create_path(ParticleThread *thread, struct ChildParticle *cpa, ParticleCacheKey *keys, int i)
1924 {
1925         ParticleThreadContext *ctx= thread->ctx;
1926         Object *ob= ctx->ob;
1927         ParticleSystem *psys = ctx->psys;
1928         ParticleSettings *part = psys->part;
1929         ParticleCacheKey **cache= psys->childcache;
1930         ParticleCacheKey **pcache= psys->pathcache;
1931         ParticleCacheKey *state, *par = NULL, *key[4];
1932         ParticleData *pa;
1933         ParticleTexture ptex;
1934         float *cpa_fuv=0;
1935         float co[3], orco[3], ornor[3], t, rough_t, cpa_1st[3], dvec[3];
1936         float branch_begin, branch_end, branch_prob, branchfac, rough_rand;
1937         float pa_rough1, pa_rough2, pa_roughe;
1938         float length, pa_length, pa_clump, pa_kink, pa_effector;
1939         float max_length = 1.0f, cur_length = 0.0f;
1940         float eff_length, eff_vec[3];
1941         int k, cpa_num, guided=0;
1942         short cpa_from;
1943
1944         if(part->flag & PART_BRANCHING) {
1945                 branch_begin=rng_getFloat(thread->rng_path);
1946                 branch_end=branch_begin+(1.0f-branch_begin)*rng_getFloat(thread->rng_path);
1947                 branch_prob=rng_getFloat(thread->rng_path);
1948                 rough_rand=rng_getFloat(thread->rng_path);
1949         }
1950         else {
1951                 branch_begin= 0.0f;
1952                 branch_end= 0.0f;
1953                 branch_prob= 0.0f;
1954                 rough_rand= 0.0f;
1955         }
1956
1957         if(i<psys->totpart){
1958                 branch_begin=0.0f;
1959                 branch_end=1.0f;
1960                 branch_prob=0.0f;
1961         }
1962
1963         if(ctx->between){
1964                 int w, needupdate;
1965                 float foffset;
1966
1967                 if(ctx->editupdate && !(part->flag & PART_BRANCHING)) {
1968                         needupdate= 0;
1969                         w= 0;
1970                         while(w<4 && cpa->pa[w]>=0) {
1971                                 if(psys->particles[cpa->pa[w]].flag & PARS_EDIT_RECALC) {
1972                                         needupdate= 1;
1973                                         break;
1974                                 }
1975                                 w++;
1976                         }
1977
1978                         if(!needupdate)
1979                                 return;
1980                         else
1981                                 memset(keys, 0, sizeof(*keys)*(ctx->steps+1));
1982                 }
1983
1984                 /* get parent paths */
1985                 w= 0;
1986                 while(w<4 && cpa->pa[w]>=0){
1987                         key[w] = pcache[cpa->pa[w]];
1988                         w++;
1989                 }
1990
1991                 /* get the original coordinates (orco) for texture usage */
1992                 cpa_num = cpa->num;
1993                 
1994                 foffset= cpa->foffset;
1995                 if(part->childtype == PART_CHILD_FACES)
1996                         foffset = -(2.0f + part->childspread);
1997                 cpa_fuv = cpa->fuv;
1998                 cpa_from = PART_FROM_FACE;
1999
2000                 psys_particle_on_emitter(ob,ctx->psmd,cpa_from,cpa_num,DMCACHE_ISCHILD,cpa->fuv,foffset,co,ornor,0,0,orco,0);
2001
2002                 /* we need to save the actual root position of the child for positioning it accurately to the surface of the emitter */
2003                 VECCOPY(cpa_1st,co);
2004                 Mat4MulVecfl(ob->obmat,cpa_1st);
2005
2006                 pa=0;
2007         }
2008         else{
2009                 if(ctx->editupdate && !(part->flag & PART_BRANCHING)) {
2010                         if(!(psys->particles[cpa->parent].flag & PARS_EDIT_RECALC))
2011                                 return;
2012
2013                         memset(keys, 0, sizeof(*keys)*(ctx->steps+1));
2014                 }
2015
2016                 /* get the parent path */
2017                 key[0]=pcache[cpa->parent];
2018
2019                 /* get the original coordinates (orco) for texture usage */
2020                 pa=psys->particles+cpa->parent;
2021
2022                 cpa_from=part->from;
2023                 cpa_num=pa->num;
2024                 cpa_fuv=pa->fuv;
2025
2026                 psys_particle_on_emitter(ob,ctx->psmd,cpa_from,cpa_num,DMCACHE_ISCHILD,cpa_fuv,pa->foffset,co,ornor,0,0,orco,0);
2027         }
2028
2029         keys->steps = ctx->steps;
2030
2031         /* correct child ipo timing */
2032         if((part->flag&PART_ABS_TIME)==0 && part->ipo){
2033                 float dsta=part->end-part->sta;
2034                 calc_ipo(part->ipo, 100.0f*(ctx->cfra-(part->sta+dsta*cpa->rand[1]))/(part->lifetime*(1.0f - part->randlife*cpa->rand[0])));
2035                 execute_ipo((ID *)part, part->ipo);
2036         }
2037
2038         /* get different child parameters from textures & vgroups */
2039         ptex.length=part->length*(1.0f - part->randlength*cpa->rand[0]);
2040         ptex.clump=1.0;
2041         ptex.kink=1.0;
2042         ptex.rough= 1.0;
2043
2044         get_cpa_texture(ctx->dm,ctx->ma,cpa_num,cpa_fuv,orco,&ptex,
2045                 MAP_PA_LENGTH|MAP_PA_CLUMP|MAP_PA_KINK|MAP_PA_ROUGH);
2046         
2047         pa_length=ptex.length;
2048         pa_clump=ptex.clump;
2049         pa_kink=ptex.kink;
2050         pa_rough1=ptex.rough;
2051         pa_rough2=ptex.rough;
2052         pa_roughe=ptex.rough;
2053         pa_effector= 1.0f;
2054
2055         if(ctx->vg_length)
2056                 pa_length*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_length);
2057         if(ctx->vg_clump)
2058                 pa_clump*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_clump);
2059         if(ctx->vg_kink)
2060                 pa_kink*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_kink);
2061         if(ctx->vg_rough1)
2062                 pa_rough1*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_rough1);
2063         if(ctx->vg_rough2)
2064                 pa_rough2*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_rough2);
2065         if(ctx->vg_roughe)
2066                 pa_roughe*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_roughe);
2067         if(ctx->vg_effector)
2068                 pa_effector*=psys_interpolate_value_from_verts(ctx->dm,cpa_from,cpa_num,cpa_fuv,ctx->vg_effector);
2069
2070         /* create the child path */
2071         for(k=0,state=keys; k<=ctx->steps; k++,state++){
2072                 if(ctx->between){
2073                         int w=0;
2074
2075                         state->co[0] = state->co[1] = state->co[2] = 0.0f;
2076                         state->vel[0] = state->vel[1] = state->vel[2] = 0.0f;
2077                         state->rot[0] = state->rot[1] = state->rot[2] = state->rot[3] = 0.0f;
2078
2079                         //QUATCOPY(state->rot,key[0]->rot);
2080
2081                         /* child position is the weighted sum of parent positions */
2082                         while(w<4 && cpa->pa[w]>=0){
2083                                 state->co[0] += cpa->w[w] * key[w]->co[0];
2084                                 state->co[1] += cpa->w[w] * key[w]->co[1];
2085                                 state->co[2] += cpa->w[w] * key[w]->co[2];
2086
2087                                 state->vel[0] += cpa->w[w] * key[w]->vel[0];
2088                                 state->vel[1] += cpa->w[w] * key[w]->vel[1];
2089                                 state->vel[2] += cpa->w[w] * key[w]->vel[2];
2090                                 key[w]++;
2091                                 w++;
2092                         }
2093                         if(k==0){
2094                                 /* calculate the offset between actual child root position and first position interpolated from parents */
2095                                 VECSUB(cpa_1st,cpa_1st,state->co);
2096                         }
2097                         /* apply offset for correct positioning */
2098                         VECADD(state->co,state->co,cpa_1st);
2099                 }
2100                 else{
2101                         /* offset the child from the parent position */
2102                         offset_child(cpa, (ParticleKey*)key[0], (ParticleKey*)state, part->childflat, part->childrad);
2103
2104                         key[0]++;
2105                 }
2106         }
2107
2108         /* apply effectors */
2109         if(part->flag & PART_CHILD_EFFECT) {
2110                 for(k=0,state=keys; k<=ctx->steps; k++,state++) {
2111                         if(k) {
2112                                 do_path_effectors(ob, psys, cpa->pa[0], state, k, ctx->steps, keys->co, pa_effector, 0.0f, ctx->cfra, &eff_length, eff_vec);
2113                         }
2114                         else {
2115                                 VecSubf(eff_vec,(state+1)->co,state->co);
2116                                 eff_length= VecLength(eff_vec);
2117                         }
2118                 }
2119         }
2120
2121         for(k=0,state=keys; k<=ctx->steps; k++,state++){
2122                 t=(float)k/(float)ctx->steps;
2123
2124                 if(ctx->totparent){
2125                         if(i>=ctx->totparent)
2126                                 /* this is not threadsafe, but should only happen for
2127                                  * branching particles particles, which are not threaded */
2128                                 par = cache[cpa->parent] + k;
2129                         else
2130                                 par=0;
2131                 }
2132                 else if(cpa->parent>=0){
2133                         par=pcache[cpa->parent]+k;
2134                 }
2135
2136                 /* apply different deformations to the child path */
2137                 if(part->flag & PART_CHILD_EFFECT)
2138                         /* state is safe to cast, since only co and vel are used */
2139                         guided = do_guide((ParticleKey*)state, cpa->parent, t, &(psys->effectors));
2140
2141                 if(guided==0){
2142                         if(part->kink)
2143                                 do_prekink((ParticleKey*)state, (ParticleKey*)par, par->rot, t,
2144                                 part->kink_freq * pa_kink, part->kink_shape, part->kink_amp, part->kink, part->kink_axis, ob->obmat);
2145                                         
2146                         do_clump((ParticleKey*)state, (ParticleKey*)par, t, part->clumpfac, part->clumppow, pa_clump);
2147                 }
2148
2149                 if(part->flag & PART_BRANCHING && ctx->between == 0 && part->flag & PART_ANIM_BRANCHING)
2150                         rough_t = t * rough_rand;
2151                 else
2152                         rough_t = t;
2153
2154                 if(part->rough1 != 0.0 && pa_rough1 != 0.0)
2155                         do_rough(orco, rough_t, pa_rough1*part->rough1, part->rough1_size, 0.0, (ParticleKey*)state);
2156
2157                 if(part->rough2 != 0.0 && pa_rough2 != 0.0)
2158                         do_rough(cpa->rand, rough_t, pa_rough2*part->rough2, part->rough2_size, part->rough2_thres, (ParticleKey*)state);
2159
2160                 if(part->rough_end != 0.0 && pa_roughe != 0.0)
2161                         do_rough_end(cpa->rand, rough_t, pa_roughe*part->rough_end, part->rough_end_shape, (ParticleKey*)state, (ParticleKey*)par);
2162
2163                 if(part->flag & PART_BRANCHING && ctx->between==0){
2164                         if(branch_prob > part->branch_thres){
2165                                 branchfac=0.0f;
2166                         }
2167                         else{
2168                                 if(part->flag & PART_SYMM_BRANCHING){
2169                                         if(t < branch_begin || t > branch_end)
2170                                                 branchfac=0.0f;
2171                                         else{
2172                                                 if((t-branch_begin)/(branch_end-branch_begin)<0.5)
2173                                                         branchfac=2.0f*(t-branch_begin)/(branch_end-branch_begin);
2174                                                 else
2175                                                         branchfac=2.0f*(branch_end-t)/(branch_end-branch_begin);
2176
2177                                                 CLAMP(branchfac,0.0f,1.0f);
2178                                         }
2179                                 }
2180                                 else{
2181                                         if(t < branch_begin){
2182                                                 branchfac=0.0f;
2183                                         }
2184                                         else{
2185                                                 branchfac=(t-branch_begin)/((1.0f-branch_begin)*0.5f);
2186                                                 CLAMP(branchfac,0.0f,1.0f);
2187                                         }
2188                                 }
2189                         }
2190
2191                         if(i<psys->totpart)
2192                                 VecLerpf(state->co, (pcache[i] + k)->co, state->co, branchfac);
2193                         else
2194                                 /* this is not threadsafe, but should only happen for
2195                                  * branching particles particles, which are not threaded */
2196                                 VecLerpf(state->co, (cache[i - psys->totpart] + k)->co, state->co, branchfac);
2197                 }
2198
2199                 /* we have to correct velocity because of kink & clump */
2200                 if(k>1){
2201                         VECSUB((state-1)->vel,state->co,(state-2)->co);
2202                         VecMulf((state-1)->vel,0.5);
2203
2204                         if(ctx->ma && (part->draw & PART_DRAW_MAT_COL))
2205                                 get_strand_normal(ctx->ma, ornor, cur_length, (state-1)->vel);
2206                 }
2207
2208                 /* check if path needs to be cut before actual end of data points */
2209                 if(k){
2210                         VECSUB(dvec,state->co,(state-1)->co);
2211                         if(part->flag&PART_ABS_LENGTH)
2212                                 length=VecLength(dvec);
2213                         else
2214                                 length=1.0f/(float)ctx->steps;
2215
2216                         k=check_path_length(k,keys,state,max_length,&cur_length,length,dvec);
2217                 }
2218                 else{
2219                         /* initialize length calculation */
2220                         if(part->flag&PART_ABS_LENGTH)
2221                                 max_length= part->abslength*pa_length;
2222                         else
2223                                 max_length= pa_length;
2224
2225                         cur_length= 0.0f;
2226                 }
2227
2228                 if(ctx->ma && (part->draw & PART_DRAW_MAT_COL)) {
2229                         VECCOPY(state->col, &ctx->ma->r)
2230                         get_strand_normal(ctx->ma, ornor, cur_length, state->vel);
2231                 }
2232         }
2233
2234         /* now let's finalise the interpolated parents that we might have left half done before */
2235         if(i<ctx->totparent)
2236                 finalize_path_length(keys);
2237 }
2238
2239 void *exec_child_path_cache(void *data)
2240 {
2241         ParticleThread *thread= (ParticleThread*)data;
2242         ParticleThreadContext *ctx= thread->ctx;
2243         ParticleSystem *psys= ctx->psys;
2244         ParticleCacheKey **cache= psys->childcache;
2245         ChildParticle *cpa;
2246         int i, totchild= ctx->totchild;
2247         
2248         cpa= psys->child + thread->num;
2249         for(i=thread->num; i<totchild; i+=thread->tot, cpa+=thread->tot)
2250                 psys_thread_create_path(thread, cpa, cache[i], i);
2251
2252         return 0;
2253 }
2254
2255 void psys_cache_child_paths(Object *ob, ParticleSystem *psys, float cfra, int editupdate)
2256 {
2257         ParticleSettings *part = psys->part;
2258         ParticleThread *pthreads;
2259         ParticleThreadContext *ctx;
2260         ParticleCacheKey **cache, *tcache;
2261         ListBase threads;
2262         int i, totchild, totparent, totthread;
2263         unsigned long totchildstep;
2264
2265         pthreads= psys_threads_create(ob, psys);
2266
2267         if(!psys_threads_init_path(pthreads, cfra, editupdate)) {
2268                 psys_threads_free(pthreads);
2269                 return;
2270         }
2271
2272         ctx= pthreads[0].ctx;
2273         totchild= ctx->totchild;
2274         totparent= ctx->totparent;
2275
2276         if(editupdate && psys->childcache && !(part->flag & PART_BRANCHING) && totchild == psys->totchildcache) {
2277                 cache = psys->childcache;
2278         }
2279         else {
2280                 /* clear out old and create new empty path cache */
2281                 free_child_path_cache(psys);
2282
2283                 cache = psys->childcache = MEM_callocN(totchild*sizeof(void *), "Child path cache array");
2284                 totchildstep= totchild*(ctx->steps + 1);
2285                 tcache = MEM_callocN(totchildstep*sizeof(ParticleCacheKey), "Child path cache");
2286                 for(i=0; i<totchild; i++)
2287                         cache[i] = tcache + i * (ctx->steps + 1);
2288
2289                 psys->totchildcache = totchild;
2290         }
2291
2292         totthread= pthreads[0].tot;
2293
2294         if(totthread > 1) {
2295                 BLI_init_threads(&threads, exec_child_path_cache, totthread);
2296
2297                 for(i=0; i<totthread; i++)
2298                         BLI_insert_thread(&threads, &pthreads[i]);
2299
2300                 BLI_end_threads(&threads);
2301         }
2302         else
2303                 exec_child_path_cache(&pthreads[0]);
2304
2305         psys_threads_free(pthreads);
2306 }
2307
2308 /* Calculates paths ready for drawing/rendering.                                                                        */
2309 /* -Usefull for making use of opengl vertex arrays for super fast strand drawing.       */
2310 /* -Makes child strands possible and creates them too into the cache.                           */
2311 /* -Cached path data is also used to determine cut position for the editmode tool.      */
2312 void psys_cache_paths(Object *ob, ParticleSystem *psys, float cfra, int editupdate)
2313 {
2314         ParticleCacheKey *ca, **cache=psys->pathcache;
2315         ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
2316         ParticleEditSettings *pset = &G.scene->toolsettings->particle;
2317         
2318         ParticleData *pa;
2319         ParticleKey keys[4], result, *kkey[2] = {NULL, NULL};
2320         HairKey *hkey[2] = {NULL, NULL};
2321
2322         ParticleEdit *edit = 0;
2323         ParticleEditKey *ekey = 0;
2324
2325         SoftBody *soft = 0;
2326         BodyPoint *bp[2] = {NULL, NULL};
2327         
2328         Material *ma;
2329         
2330         float birthtime = 0.0, dietime = 0.0;
2331         float t, time = 0.0, keytime = 0.0, dfra = 1.0, frs_sec = G.scene->r.frs_sec;
2332         float col[3] = {0.5f, 0.5f, 0.5f};
2333         float prev_tangent[3], hairmat[4][4];
2334         int k,i;
2335         int steps = (int)pow(2.0, (double)psys->part->draw_step);
2336         int totpart = psys->totpart;
2337         char nosel[4], sel[4];
2338         float sel_col[3];
2339         float nosel_col[3];
2340         float length, vec[3];
2341         float *vg_effector= NULL, effector=0.0f;
2342
2343         /* we don't have anything valid to create paths from so let's quit here */
2344         if((psys->flag & PSYS_HAIR_DONE)==0 && (psys->flag & PSYS_KEYED)==0)
2345                 return;
2346
2347         if(psys->renderdata)
2348                 steps = (int)pow(2.0, (double)psys->part->ren_step);
2349         else if(psys_in_edit_mode(psys)){
2350                 edit=psys->edit;
2351                 
2352                 //timed = edit->draw_timed;
2353
2354                 PE_get_colors(sel,nosel);
2355                 if(pset->brushtype == PE_BRUSH_WEIGHT){
2356                         sel_col[0] = sel_col[1] = sel_col[2] = 1.0f;
2357                         nosel_col[0] = nosel_col[1] = nosel_col[2] = 0.0f;
2358                 }
2359                 else{
2360                         sel_col[0] = (float)sel[0] / 255.0f;
2361                         sel_col[1] = (float)sel[1] / 255.0f;
2362                         sel_col[2] = (float)sel[2] / 255.0f;
2363                         nosel_col[0] = (float)nosel[0] / 255.0f;
2364                         nosel_col[1] = (float)nosel[1] / 255.0f;
2365                         nosel_col[2] = (float)nosel[2] / 255.0f;
2366                 }
2367         }
2368
2369         if(editupdate && psys->pathcache && totpart == psys->totcached) {
2370                 cache = psys->pathcache;
2371         }
2372         else {
2373                 /* clear out old and create new empty path cache */
2374                 psys_free_path_cache(psys);
2375
2376                 /* allocate cache array for fast access and set pointers to contiguous mem block */
2377                 cache = psys->pathcache = MEM_callocN(MAX2(1, totpart) * sizeof(void *), "Path cache array");
2378                 cache[0] = MEM_callocN(totpart * (steps + 1) * sizeof(ParticleCacheKey), "Path cache");
2379                 for(i=1; i<totpart; i++)
2380                         cache[i] = cache[0] + i * (steps + 1);
2381         }
2382
2383         if(edit==NULL && psys->soft && psys->softflag & OB_SB_ENABLE)
2384                 soft = psys->soft;
2385         
2386         psys->lattice = psys_get_lattice(ob, psys);
2387         ma= give_current_material(ob, psys->part->omat);
2388         if(ma && (psys->part->draw & PART_DRAW_MAT_COL))
2389                 VECCOPY(col, &ma->r)
2390         
2391         if(psys->part->from!=PART_FROM_PARTICLE) {
2392                 if(!(psys->part->flag & PART_CHILD_EFFECT))
2393                         vg_effector = psys_cache_vgroup(psmd->dm, psys, PSYS_VG_EFFECTOR);
2394         }
2395
2396         /*---first main loop: create all actual particles' paths---*/
2397         for(i=0,pa=psys->particles; i<totpart; i++, pa++){
2398                 if(psys && edit==NULL && (pa->flag & PARS_NO_DISP || pa->flag & PARS_UNEXIST)) {
2399                         if(soft)
2400                                 bp[0] += pa->totkey; /* TODO use of initialized value? */
2401                         continue;
2402                 }
2403
2404                 if(editupdate && !(pa->flag & PARS_EDIT_RECALC)) continue;
2405                 else memset(cache[i], 0, sizeof(*cache[i])*(steps+1));
2406
2407                 cache[i]->steps = steps;
2408
2409                 if(edit)
2410                         ekey = edit->keys[i];
2411
2412                 /*--get the first data points--*/
2413                 if(psys->flag & PSYS_KEYED) {
2414                         kkey[0] = pa->keys;
2415                         kkey[1] = kkey[0] + 1;
2416
2417                         birthtime = kkey[0]->time;
2418                         dietime = kkey[0][pa->totkey-1].time;
2419                 }
2420                 else {
2421                         hkey[0] = pa->hair;
2422                         hkey[1] = hkey[0] + 1;
2423
2424                         birthtime = hkey[0]->time;
2425                         dietime = hkey[0][pa->totkey-1].time;
2426
2427                         psys_mat_hair_to_global(ob, psmd->dm, psys->part->from, pa, hairmat);
2428                 }
2429
2430                 if(soft){
2431                         bp[0] = soft->bpoint + pa->bpi;
2432                         bp[1] = bp[0] + 1;
2433                 }
2434
2435                 /*--interpolate actual path from data points--*/
2436                 for(k=0, ca=cache[i]; k<=steps; k++, ca++){
2437                         time = (float)k / (float)steps;
2438
2439                         t = birthtime + time * (dietime - birthtime);
2440
2441                         if(psys->flag & PSYS_KEYED) {
2442                                 while(kkey[1]->time < t) {
2443                                         kkey[1]++;
2444                                 }
2445
2446                                 kkey[0] = kkey[1] - 1;                          
2447                         }
2448                         else {
2449                                 while(hkey[1]->time < t) {
2450                                         hkey[1]++;
2451                                         bp[1]++;
2452                                 }
2453
2454                                 hkey[0] = hkey[1] - 1;
2455                         }
2456
2457                         if(soft) {
2458                                 bp[0] = bp[1] - 1;
2459                                 bp_to_particle(keys + 1, bp[0], hkey[0]);
2460                                 bp_to_particle(keys + 2, bp[1], hkey[1]);
2461                         }
2462                         else if(psys->flag & PSYS_KEYED) {
2463                                 memcpy(keys + 1, kkey[0], sizeof(ParticleKey));
2464                                 memcpy(keys + 2, kkey[1], sizeof(ParticleKey));
2465                         }
2466                         else {
2467                                 hair_to_particle(keys + 1, hkey[0]);
2468                                 hair_to_particle(keys + 2, hkey[1]);
2469                         }
2470
2471
2472                         if((psys->flag & PSYS_KEYED)==0) {
2473                                 if(soft) {
2474                                         if(hkey[0] != pa->hair)
2475                                                 bp_to_particle(keys, bp[0] - 1, hkey[0] - 1);
2476                                         else
2477                                                 bp_to_particle(keys, bp[0], hkey[0]);
2478                                 }
2479                                 else {
2480                                         if(hkey[0] != pa->hair)
2481                                                 hair_to_particle(keys, hkey[0] - 1);
2482                                         else
2483                                                 hair_to_particle(keys, hkey[0]);
2484                                 }
2485
2486                                 if(soft) {
2487                                         if(hkey[1] != pa->hair + pa->totkey - 1)
2488                                                 bp_to_particle(keys + 3, bp[1] + 1, hkey[1] + 1);
2489                                         else
2490                                                 bp_to_particle(keys + 3, bp[1], hkey[1]);
2491                                 }
2492                                 else {
2493                                         if(hkey[1] != pa->hair + pa->totkey - 1)
2494                                                 hair_to_particle(keys + 3, hkey[1] + 1);
2495                                         else
2496                                                 hair_to_particle(keys + 3, hkey[1]);
2497                                 }
2498                         }
2499
2500                         dfra = keys[2].time - keys[1].time;
2501
2502                         keytime = (t - keys[1].time) / dfra;
2503
2504                         /* convert velocity to timestep size */
2505                         if(psys->flag & PSYS_KEYED){
2506                                 VecMulf(keys[1].vel, dfra / frs_sec);
2507                                 VecMulf(keys[2].vel, dfra / frs_sec);
2508                         }
2509
2510                         /* now we should have in chronologiacl order k1<=k2<=t<=k3<=k4 with keytime between [0,1]->[k2,k3] (k1 & k4 used for cardinal & bspline interpolation)*/
2511                         interpolate_particle((psys->flag & PSYS_KEYED) ? -1 /* signal for cubic interpolation */
2512                                 : ((psys->part->flag & PART_HAIR_BSPLINE) ? KEY_BSPLINE : KEY_CARDINAL)
2513                                 ,keys, keytime, &result, 0);
2514
2515                         /* the velocity needs to be converted back from cubic interpolation */
2516                         if(psys->flag & PSYS_KEYED){
2517                                 VecMulf(result.vel, frs_sec / dfra);
2518                         }
2519                         else if(soft==NULL) { /* softbody and keyed are allready in global space */
2520                                 Mat4MulVecfl(hairmat, result.co);
2521                         }
2522
2523                         VECCOPY(ca->co, result.co);
2524
2525                         /* selection coloring in edit mode */
2526                         if(edit){
2527                                 if(pset->brushtype==PE_BRUSH_WEIGHT){
2528                                         if(k==steps)
2529                                                 VecLerpf(ca->col, nosel_col, sel_col, hkey[0]->weight);
2530                                         else
2531                                                 VecLerpf(ca->col, nosel_col, sel_col,
2532                                                 (1.0f - keytime) * hkey[0]->weight + keytime * hkey[1]->weight);
2533                                 }
2534                                 else{
2535                                         if((ekey + (hkey[0] - pa->hair))->flag & PEK_SELECT){
2536                                                 if((ekey + (hkey[1] - pa->hair))->flag & PEK_SELECT){
2537                                                         VECCOPY(ca->col, sel_col);
2538                                                 }
2539                                                 else{
2540                                                         VecLerpf(ca->col, sel_col, nosel_col, keytime);
2541                                                 }
2542                                         }
2543                                         else{
2544                                                 if((ekey + (hkey[1] - pa->hair))->flag & PEK_SELECT){
2545                                                         VecLerpf(ca->col, nosel_col, sel_col, keytime);
2546                                                 }
2547                                                 else{
2548                                                         VECCOPY(ca->col, nosel_col);
2549                                                 }
2550                                         }
2551                                 }
2552                         }
2553                         else{
2554                                 VECCOPY(ca->col, col);
2555                         }
2556                 }
2557                 
2558                 /*--modify paths--*/
2559
2560                 VecSubf(vec,(cache[i]+1)->co,cache[i]->co);
2561                 length = VecLength(vec);
2562
2563                 effector= 1.0f;
2564                 if(vg_effector)
2565                         effector*= psys_interpolate_value_from_verts(psmd->dm,psys->part->from,pa->num,pa->fuv,vg_effector);
2566
2567                 for(k=0, ca=cache[i]; k<=steps; k++, ca++) {
2568                         /* apply effectors */
2569                         if(!(psys->part->flag & PART_CHILD_EFFECT) && edit==0 && k)
2570                                 do_path_effectors(ob, psys, i, ca, k, steps, cache[i]->co, effector, dfra, cfra, &length, vec);
2571
2572                         /* apply guide curves to path data */
2573                         if(edit==0 && psys->effectors.first && (psys->part->flag & PART_CHILD_EFFECT)==0)
2574                                 /* ca is safe to cast, since only co and vel are used */
2575                                 do_guide((ParticleKey*)ca, i, (float)k/(float)steps, &psys->effectors);
2576
2577                         /* apply lattice */
2578                         if(psys->lattice && edit==0)
2579                                 calc_latt_deform(ca->co, 1.0f);
2580
2581                         /* figure out rotation */
2582                         
2583                         if(k) {
2584                                 float cosangle, angle, tangent[3], normal[3], q[4];
2585
2586                                 if(k == 1) {
2587                                         VECSUB(tangent, ca->co, (ca - 1)->co);
2588
2589                                         vectoquat(tangent, OB_POSX, OB_POSZ, (ca-1)->rot);
2590
2591                                         VECCOPY(prev_tangent, tangent);
2592                                         Normalize(prev_tangent);
2593                                 }
2594                                 else {
2595                                         VECSUB(tangent, ca->co, (ca - 1)->co);
2596                                         Normalize(tangent);
2597
2598                                         cosangle= Inpf(tangent, prev_tangent);
2599
2600                                         /* note we do the comparison on cosangle instead of
2601                                          * angle, since floating point accuracy makes it give
2602                                          * different results across platforms */
2603                                         if(cosangle > 0.999999f) {
2604                                                 QUATCOPY((ca - 1)->rot, (ca - 2)->rot);
2605                                         }
2606                                         else {
2607                                                 angle= saacos(cosangle);
2608                                                 Crossf(normal, prev_tangent, tangent);
2609                                                 VecRotToQuat(normal, angle, q);
2610                                                 QuatMul((ca - 1)->rot, q, (ca - 2)->rot);
2611                                         }
2612
2613                                         VECCOPY(prev_tangent, tangent);
2614                                 }
2615
2616                                 if(k == steps)
2617                                         QUATCOPY(ca->rot, (ca - 1)->rot);
2618                         }
2619
2620                         
2621                         /* set velocity */
2622
2623                         if(k){
2624                                 VECSUB(ca->vel, ca->co, (ca-1)->co);
2625
2626                                 if(k==1) {
2627                                         VECCOPY((ca-1)->vel, ca->vel);
2628                                 }
2629
2630                         }
2631
2632                 }
2633         }
2634
2635         psys->totcached = totpart;
2636
2637         if(psys && psys->lattice){
2638                 end_latt_deform();
2639                 psys->lattice=0;
2640         }
2641
2642         if(vg_effector)
2643                 MEM_freeN(vg_effector);
2644 }
2645 /************************************************/
2646 /*                      Particle Key handling                           */
2647 /************************************************/
2648 void copy_particle_key(ParticleKey *to, ParticleKey *from, int time){
2649         if(time){
2650                 memcpy(to,from,sizeof(ParticleKey));
2651         }
2652         else{
2653                 float to_time=to->time;
2654                 memcpy(to,from,sizeof(ParticleKey));
2655                 to->time=to_time;
2656         }
2657         /*
2658         VECCOPY(to->co,from->co);
2659         VECCOPY(to->vel,from->vel);
2660         QUATCOPY(to->rot,from->rot);
2661         if(time)
2662                 to->time=from->time;
2663         to->flag=from->flag;
2664         to->sbw=from->sbw;
2665         */
2666 }
2667 void psys_get_from_key(ParticleKey *key, float *loc, float *vel, float *rot, float *time){
2668         if(loc) VECCOPY(loc,key->co);
2669         if(vel) VECCOPY(vel,key->vel);
2670         if(rot) QUATCOPY(rot,key->rot);
2671         if(time) *time=key->time;
2672 }
2673 /*-------changing particle keys from space to another-------*/
2674 void psys_key_to_object(Object *ob, ParticleKey *key, float imat[][4]){
2675         float q[4], imat2[4][4];
2676
2677         if(imat==0){
2678                 Mat4Invert(imat2,ob->obmat);
2679                 imat=imat2;
2680         }
2681
2682         VECADD(key->vel,key->vel,key->co);
2683
2684         Mat4MulVecfl(imat,key->co);
2685         Mat4MulVecfl(imat,key->vel);
2686         Mat4ToQuat(imat,q);
2687
2688         VECSUB(key->vel,key->vel,key->co);
2689         QuatMul(key->rot,q,key->rot);
2690 }
2691 static void key_from_object(Object *ob, ParticleKey *key){
2692         float q[4];
2693
2694         VECADD(key->vel,key->vel,key->co);
2695
2696         Mat4MulVecfl(ob->obmat,key->co);
2697         Mat4MulVecfl(ob->obmat,key->vel);
2698         Mat4ToQuat(ob->obmat,q);
2699
2700         VECSUB(key->vel,key->vel,key->co);
2701         QuatMul(key->rot,q,key->rot);
2702 }
2703
2704 static void triatomat(float *v1, float *v2, float *v3, float (*uv)[2], float mat[][4])
2705 {
2706         float det, w1, w2, d1[2], d2[2];
2707
2708         memset(mat, 0, sizeof(float)*4*4);
2709         mat[3][3]= 1.0f;
2710
2711         /* first axis is the normal */
2712         CalcNormFloat(v1, v2, v3, mat[2]);
2713
2714         /* second axis along (1, 0) in uv space */
2715         if(uv) {
2716                 d1[0]= uv[1][0] - uv[0][0];
2717                 d1[1]= uv[1][1] - uv[0][1];
2718                 d2[0]= uv[2][0] - uv[0][0];
2719                 d2[1]= uv[2][1] - uv[0][1];
2720
2721                 det = d2[0]*d1[1] - d2[1]*d1[0];
2722
2723                 if(det != 0.0f) {
2724                         det= 1.0f/det;
2725                         w1= -d2[1]*det;
2726                         w2= d1[1]*det;
2727
2728                         mat[1][0]= w1*(v2[0] - v1[0]) + w2*(v3[0] - v1[0]);
2729                         mat[1][1]= w1*(v2[1] - v1[1]) + w2*(v3[1] - v1[1]);
2730                         mat[1][2]= w1*(v2[2] - v1[2]) + w2*(v3[2] - v1[2]);
2731                         Normalize(mat[1]);
2732                 }
2733                 else
2734                         mat[1][0]= mat[1][1]= mat[1][2]= 0.0f;
2735         }
2736         else {
2737                 VecSubf(mat[1], v2, v1);
2738                 Normalize(mat[1]);
2739         }
2740         
2741         /* third as a cross product */
2742         Crossf(mat[0], mat[1], mat[2]);
2743 }
2744
2745 static void psys_face_mat(Object *ob, DerivedMesh *dm, ParticleData *pa, float mat[][4], int orco)
2746 {
2747         float v[3][3];
2748         MFace *mface;
2749         OrigSpaceFace *osface;
2750         float (*orcodata)[3];
2751
2752         int i = pa->num_dmcache==DMCACHE_NOTFOUND ? pa->num : pa->num_dmcache;
2753         
2754         if (i==-1 || i >= dm->getNumFaces(dm)) { Mat4One(mat); return; }
2755
2756         mface=dm->getFaceData(dm,i,CD_MFACE);
2757         osface=dm->getFaceData(dm,i,CD_ORIGSPACE);
2758         
2759         if(orco && (orcodata=dm->getVertDataArray(dm, CD_ORCO))) {
2760                 VECCOPY(v[0], orcodata[mface->v1]);
2761                 VECCOPY(v[1], orcodata[mface->v2]);
2762                 VECCOPY(v[2], orcodata[mface->v3]);
2763
2764                 /* ugly hack to use non-transformed orcos, since only those
2765                  * give symmetric results for mirroring in particle mode */
2766                 transform_mesh_orco_verts(ob->data, v, 3, 1);
2767         }
2768         else {
2769                 dm->getVertCo(dm,mface->v1,v[0]);
2770                 dm->getVertCo(dm,mface->v2,v[1]);
2771                 dm->getVertCo(dm,mface->v3,v[2]);
2772         }
2773
2774         triatomat(v[0], v[1], v[2], (osface)? osface->uv: NULL, mat);
2775 }
2776
2777 void psys_mat_hair_to_object(Object *ob, DerivedMesh *dm, short from, ParticleData *pa, float hairmat[][4])
2778 {
2779         float vec[3];
2780
2781         psys_face_mat(0, dm, pa, hairmat, 0);
2782         psys_particle_on_dm(ob, dm, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, vec, 0, 0, 0, 0, 0);
2783         VECCOPY(hairmat[3],vec);
2784 }
2785
2786 void psys_mat_hair_to_orco(Object *ob, DerivedMesh *dm, short from, ParticleData *pa, float hairmat[][4])
2787 {
2788         float vec[3], orco[3];
2789
2790         psys_face_mat(ob, dm, pa, hairmat, 1);
2791         psys_particle_on_dm(ob, dm, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, vec, 0, 0, 0, orco, 0);
2792
2793         /* see psys_face_mat for why this function is called */
2794         transform_mesh_orco_verts(ob->data, &orco, 1, 1);
2795         VECCOPY(hairmat[3],orco);
2796 }
2797
2798 /*
2799 void psys_key_to_geometry(DerivedMesh *dm, ParticleData *pa, ParticleKey *key)
2800 {
2801         float q[4], v1[3], v2[3], v3[3];
2802
2803         dm->getVertCo(dm,pa->verts[0],v1);
2804         dm->getVertCo(dm,pa->verts[1],v2);
2805         dm->getVertCo(dm,pa->verts[2],v3);
2806
2807         triatoquat(v1, v2, v3, q);
2808
2809         QuatInv(q);
2810
2811         VECSUB(key->co,key->co,v1);
2812
2813         VECADD(key->vel,key->vel,key->co);
2814
2815         QuatMulVecf(q, key->co);
2816         QuatMulVecf(q, key->vel);
2817         
2818         VECSUB(key->vel,key->vel,key->co);
2819
2820         QuatMul(key->rot,q,key->rot);
2821 }
2822
2823 void psys_key_from_geometry(DerivedMesh *dm, ParticleData *pa, ParticleKey *key)
2824 {
2825         float q[4], v1[3], v2[3], v3[3];
2826
2827         dm->getVertCo(dm,pa->verts[0],v1);
2828         dm->getVertCo(dm,pa->verts[1],v2);
2829         dm->getVertCo(dm,pa->verts[2],v3);
2830
2831         triatoquat(v1, v2, v3, q);
2832
2833         VECADD(key->vel,key->vel,key->co);
2834
2835         QuatMulVecf(q, key->co);
2836         QuatMulVecf(q, key->vel);
2837         
2838         VECSUB(key->vel,key->vel,key->co);
2839
2840         VECADD(key->co,key->co,v1);
2841
2842         QuatMul(key->rot,q,key->rot);
2843 }
2844 */
2845
2846 void psys_vec_rot_to_face(DerivedMesh *dm, ParticleData *pa, float *vec)//to_geometry(DerivedMesh *dm, ParticleData *pa, float *vec)
2847 {
2848         float mat[4][4];
2849
2850         psys_face_mat(0, dm, pa, mat, 0);
2851         Mat4Transp(mat); /* cheap inverse for rotation matrix */
2852         Mat4Mul3Vecfl(mat, vec);
2853 }
2854
2855 /* unused */
2856 #if 0
2857 static void psys_vec_rot_from_face(DerivedMesh *dm, ParticleData *pa, float *vec)//from_geometry(DerivedMesh *dm, ParticleData *pa, float *vec)
2858 {
2859         float q[4], v1[3], v2[3], v3[3];
2860         /*
2861         dm->getVertCo(dm,pa->verts[0],v1);
2862         dm->getVertCo(dm,pa->verts[1],v2);
2863         dm->getVertCo(dm,pa->verts[2],v3);
2864         */
2865         /* replace with this */
2866         MFace *mface;
2867         int i; // = psys_particle_dm_face_lookup(dm, pa->num, pa->fuv, pa->foffset, (LinkNode*)NULL);
2868         i = pa->num_dmcache==DMCACHE_NOTFOUND ? pa->num : pa->num_dmcache;
2869         if (i==-1 || i >= dm->getNumFaces(dm)) { vec[0] = vec[1] = 0; vec[2] = 1; return; }
2870         mface=dm->getFaceData(dm,i,CD_MFACE);
2871         
2872         dm->getVertCo(dm,mface->v1,v1);
2873         dm->getVertCo(dm,mface->v2,v2);
2874         dm->getVertCo(dm,mface->v3,v3);
2875         /* done */
2876         
2877         triatoquat(v1, v2, v3, q);
2878
2879         QuatMulVecf(q, vec);
2880
2881         //VECADD(vec,vec,v1);
2882 }
2883 #endif
2884
2885 void psys_mat_hair_to_global(Object *ob, DerivedMesh *dm, short from, ParticleData *pa, float hairmat[][4])
2886 {
2887         float facemat[4][4];
2888
2889         psys_mat_hair_to_object(ob, dm, from, pa, facemat);
2890
2891         Mat4MulMat4(hairmat, facemat, ob->obmat);
2892 }
2893
2894 /************************************************/
2895 /*                      ParticleSettings handling                       */
2896 /************************************************/
2897 static void default_particle_settings(ParticleSettings *part)
2898 {
2899         int i;
2900
2901         part->type= PART_EMITTER;
2902         part->distr= PART_DISTR_JIT;
2903         part->draw_as=PART_DRAW_DOT;
2904         part->bb_uv_split=1;
2905         part->bb_align=PART_BB_VIEW;
2906         part->bb_split_offset=PART_BB_OFF_LINEAR;
2907         part->flag=PART_REACT_MULTIPLE|PART_HAIR_GEOMETRY;
2908
2909         part->sta= 1.0;
2910         part->end= 100.0;
2911         part->lifetime= 50.0;
2912         part->jitfac= 1.0;
2913         part->totpart= 1000;
2914         part->grid_res= 10;
2915         part->timetweak= 1.0;
2916         part->keyed_time= 0.5;
2917         //part->userjit;
2918         
2919         part->integrator= PART_INT_MIDPOINT;
2920         part->phystype= PART_PHYS_NEWTON;
2921         part->hair_step= 5;
2922         part->keys_step= 5;
2923         part->draw_step= 2;
2924         part->ren_step= 3;
2925         part->adapt_angle= 5;
2926         part->adapt_pix= 3;
2927         part->kink_axis= 2;
2928         part->reactevent= PART_EVENT_DEATH;
2929         part->disp=100;
2930         part->from= PART_FROM_FACE;
2931         part->length= 1.0;
2932         part->nbetween= 4;
2933         part->boidneighbours= 5;
2934
2935         part->max_vel = 10.0f;
2936         part->average_vel = 0.3f;
2937         part->max_tan_acc = 0.2f;
2938         part->max_lat_acc = 1.0f;
2939
2940         part->reactshape=1.0f;
2941
2942         part->mass=1.0;
2943         part->size=1.0;
2944         part->childsize=1.0;
2945
2946         part->child_nbr=10;
2947         part->ren_child_nbr=100;
2948         part->childrad=0.2f;
2949         part->childflat=0.0f;
2950         part->clumppow=0.0f;
2951         part->kink_amp=0.2f;
2952         part->kink_freq=2.0;
2953
2954         part->rough1_size=1.0;
2955         part->rough2_size=1.0;
2956         part->rough_end_shape=1.0;
2957
2958         part->draw_line[0]=0.5;
2959
2960         part->banking=1.0;
2961         part->max_bank=1.0;
2962
2963         for(i=0; i<BOID_TOT_RULES; i++){
2964                 part->boidrule[i]=(char)i;
2965                 part->boidfac[i]=0.5;
2966         }
2967
2968         part->ipo = NULL;
2969
2970         part->simplify_refsize= 1920;
2971         part->simplify_rate= 1.0f;
2972         part->simplify_transition= 0.1f;
2973         part->simplify_viewport= 0.8;
2974 }
2975
2976
2977 ParticleSettings *psys_new_settings(char *name, Main *main)
2978 {
2979         ParticleSettings *part;
2980
2981         part= alloc_libblock(&main->particle, ID_PA, name);
2982         
2983         default_particle_settings(part);
2984
2985         return part;
2986 }
2987
2988 ParticleSettings *psys_copy_settings(ParticleSettings *part)
2989 {
2990         ParticleSettings *partn;
2991         
2992         partn= copy_libblock(part);
2993         if(partn->pd) partn->pd= MEM_dupallocN(part->pd);
2994         
2995         return partn;
2996 }
2997
2998 void make_local_particlesettings(ParticleSettings *part)
2999 {
3000         Object *ob;
3001         ParticleSettings *par;
3002         int local=0, lib=0;
3003
3004         /* - only lib users: do nothing
3005             * - only local users: set flag
3006             * - mixed: make copy
3007             */
3008         
3009         if(part->id.lib==0) return;
3010         if(part->id.us==1) {
3011                 part->id.lib= 0;
3012                 part->id.flag= LIB_LOCAL;
3013                 new_id(0, (ID *)part, 0);
3014                 return;
3015         }
3016         
3017         /* test objects */
3018         ob= G.main->object.first;
3019         while(ob) {
3020                 ParticleSystem *psys=ob->particlesystem.first;
3021                 for(; psys; psys=psys->next){
3022                         if(psys->part==part) {
3023                                 if(ob->id.lib) lib= 1;
3024                                 else local= 1;
3025                         }
3026                 }
3027                 ob= ob->id.next;
3028         }
3029         
3030         if(local && lib==0) {
3031                 part->id.lib= 0;
3032                 part->id.flag= LIB_LOCAL;
3033                 new_id(0, (ID *)part, 0);
3034         }
3035         else if(local && lib) {
3036                 
3037                 par= psys_copy_settings(part);
3038                 par->id.us= 0;
3039                 
3040                 /* do objects */
3041                 ob= G.main->object.first;
3042                 while(ob) {
3043                         ParticleSystem *psys=ob->particlesystem.first;
3044                         for(; psys; psys=psys->next){
3045                                 if(psys->part==part && ob->id.lib==0) {
3046                                         psys->part= par;
3047                                         par->id.us++;
3048                                         part->id.us--;
3049                                 }
3050                         }
3051                         ob= ob->id.next;
3052                 }
3053         }
3054 }
3055
3056 /* should be integrated to depgraph signals */
3057 void psys_flush_settings(ParticleSettings *part, int event, int hair_recalc)
3058 {
3059         Base *base;
3060         Object *ob, *tob;
3061         ParticleSystem *psys;
3062         int flush;
3063
3064         /* update all that have same particle settings */
3065         for(base = G.scene->base.first; base; base= base->next) {
3066                 if(base->object->particlesystem.first) {
3067                         ob=base->object;
3068                         flush=0;
3069                         for(psys=ob->particlesystem.first; psys; psys=psys->next){
3070                                 if(psys->part==part){
3071                                         psys->recalc |= event;
3072                                         if(hair_recalc)
3073                                                 psys->recalc |= PSYS_RECALC_HAIR;
3074                                         flush++;
3075                                 }
3076                                 else if(psys->part->type==PART_REACTOR){
3077                                         ParticleSystem *tpsys;
3078                                         tob=psys->target_ob;
3079                                         if(tob==0)
3080                                                 tob=ob;
3081                                         tpsys=BLI_findlink(&tob->particlesystem,psys->target_psys-1);
3082
3083                                         if(tpsys && tpsys->part==part){
3084                                                 psys->recalc |= event;
3085                                                 flush++;
3086                                         }
3087                                 }
3088                         }
3089                         if(flush)
3090                                 DAG_object_flush_update(G.scene, ob, OB_RECALC_DATA);
3091                 }
3092         }
3093 }
3094
3095 LinkNode *psys_using_settings(ParticleSettings *part, int flush_update)
3096 {
3097         Object *ob, *tob;
3098         ParticleSystem *psys, *tpsys;
3099         LinkNode *node= NULL;
3100         int found;
3101
3102         /* update all that have same particle settings */
3103         for(ob=G.main->object.first; ob; ob=ob->id.next) {
3104                 found= 0;
3105
3106                 for(psys=ob->particlesystem.first; psys; psys=psys->next) {
3107                         if(psys->part == part) {
3108                                 BLI_linklist_append(&node, psys);
3109                                 found++;
3110                         }
3111                         else if(psys->part->type == PART_REACTOR){
3112                                 tob= (psys->target_ob)? psys->target_ob: ob;
3113                                 tpsys= BLI_findlink(&tob->particlesystem, psys->target_psys-1);
3114
3115                                 if(tpsys && tpsys->part==part) {
3116                                         BLI_linklist_append(&node, tpsys);
3117                                         found++;
3118                                 }
3119                         }
3120                 }
3121
3122                 if(flush_update && found)
3123              &nb