source/blender/blenkernel/intern/particle.c

   1 /*
   2  * ***** BEGIN GPL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  * The Original Code is Copyright (C) 2007 by Janne Karhu.
  19  * All rights reserved.
  20  *
  21  * The Original Code is: all of this file.
  22  *
  23  * Contributor(s): none yet.
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 /** \file blender/blenkernel/intern/particle.c
  29  *  \ingroup bke
  30  */
  31
  32
  33 #include <stdlib.h>
  34 #include <math.h>
  35 #include <string.h>
  36
  37 #include "MEM_guardedalloc.h"
  38
  39 #include "DNA_curve_types.h"
  40 #include "DNA_group_types.h"
  41 #include "DNA_key_types.h"
  42 #include "DNA_material_types.h"
  43 #include "DNA_mesh_types.h"
  44 #include "DNA_meshdata_types.h"
  45 #include "DNA_particle_types.h"
  46 #include "DNA_smoke_types.h"
  47 #include "DNA_scene_types.h"
  48 #include "DNA_dynamicpaint_types.h"
  49
  50 #include "BLI_blenlib.h"
  51 #include "BLI_noise.h"
  52 #include "BLI_math.h"
  53 #include "BLI_utildefines.h"
  54 #include "BLI_kdtree.h"
  55 #include "BLI_rand.h"
  56 #include "BLI_task.h"
  57 #include "BLI_threads.h"
  58 #include "BLI_linklist.h"
  59
  60 #include "BLT_translation.h"
  61
  62 #include "BKE_anim.h"
  63 #include "BKE_animsys.h"
  64
  65 #include "BKE_boids.h"
  66 #include "BKE_cloth.h"
  67 #include "BKE_colortools.h"
  68 #include "BKE_effect.h"
  69 #include "BKE_global.h"
  70 #include "BKE_group.h"
  71 #include "BKE_main.h"
  72 #include "BKE_lattice.h"
  73
  74 #include "BKE_displist.h"
  75 #include "BKE_particle.h"
  76 #include "BKE_material.h"
  77 #include "BKE_key.h"
  78 #include "BKE_library.h"
  79 #include "BKE_depsgraph.h"
  80 #include "BKE_modifier.h"
  81 #include "BKE_mesh.h"
  82 #include "BKE_cdderivedmesh.h"
  83 #include "BKE_pointcache.h"
  84 #include "BKE_scene.h"
  85 #include "BKE_deform.h"
  86
  87 #include "RE_render_ext.h"
  88
  89 unsigned int PSYS_FRAND_SEED_OFFSET[PSYS_FRAND_COUNT];
  90 unsigned int PSYS_FRAND_SEED_MULTIPLIER[PSYS_FRAND_COUNT];
  91 float PSYS_FRAND_BASE[PSYS_FRAND_COUNT];
  92
  93 void psys_init_rng(void)
  94 {
  95         int i;
  96         BLI_srandom(5831); /* arbitrary */
  97         for (i = 0; i < PSYS_FRAND_COUNT; ++i) {
  98                 PSYS_FRAND_BASE[i] = BLI_frand();
  99                 PSYS_FRAND_SEED_OFFSET[i] = (unsigned int)BLI_rand();
 100                 PSYS_FRAND_SEED_MULTIPLIER[i] = (unsigned int)BLI_rand();
 101         }
 102 }
 103
 104 static void get_child_modifier_parameters(ParticleSettings *part, ParticleThreadContext *ctx,
 105                                           ChildParticle *cpa, short cpa_from, int cpa_num, float *cpa_fuv, float *orco, ParticleTexture *ptex);
 106 static void get_cpa_texture(DerivedMesh *dm, ParticleSystem *psys, ParticleSettings *part, ParticleData *par,
 107                                                         int child_index, int face_index, const float fw[4], float *orco, ParticleTexture *ptex, int event, float cfra);
 108 extern void do_child_modifiers(ParticleThreadContext *ctx, ParticleSimulationData *sim,
 109                                ParticleTexture *ptex, const float par_co[3], const float par_vel[3], const float par_rot[4], const float par_orco[3],
 110                                ChildParticle *cpa, const float orco[3], float mat[4][4], ParticleKey *state, float t);
 111
 112 /* few helpers for countall etc. */
 113 int count_particles(ParticleSystem *psys)
 114 {
 115         ParticleSettings *part = psys->part;
 116         PARTICLE_P;
 117         int tot = 0;
 118
 119         LOOP_SHOWN_PARTICLES {
 120                 if (pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN) == 0) {}
 121                 else if (pa->alive == PARS_DEAD && (part->flag & PART_DIED) == 0) {}
 122                 else tot++;
 123         }
 124         return tot;
 125 }
 126 int count_particles_mod(ParticleSystem *psys, int totgr, int cur)
 127 {
 128         ParticleSettings *part = psys->part;
 129         PARTICLE_P;
 130         int tot = 0;
 131
 132         LOOP_SHOWN_PARTICLES {
 133                 if (pa->alive == PARS_UNBORN && (part->flag & PART_UNBORN) == 0) {}
 134                 else if (pa->alive == PARS_DEAD && (part->flag & PART_DIED) == 0) {}
 135                 else if (p % totgr == cur) tot++;
 136         }
 137         return tot;
 138 }
 139 /* we allocate path cache memory in chunks instead of a big contiguous
 140  * chunk, windows' memory allocater fails to find big blocks of memory often */
 141
 142 #define PATH_CACHE_BUF_SIZE 1024
 143
 144 static ParticleCacheKey **psys_alloc_path_cache_buffers(ListBase *bufs, int tot, int totkeys)
 145 {
 146         LinkData *buf;
 147         ParticleCacheKey **cache;
 148         int i, totkey, totbufkey;
 149
 150         tot = MAX2(tot, 1);
 151         totkey = 0;
 152         cache = MEM_callocN(tot * sizeof(void *), "PathCacheArray");
 153
 154         while (totkey < tot) {
 155                 totbufkey = MIN2(tot - totkey, PATH_CACHE_BUF_SIZE);
 156                 buf = MEM_callocN(sizeof(LinkData), "PathCacheLinkData");
 157                 buf->data = MEM_callocN(sizeof(ParticleCacheKey) * totbufkey * totkeys, "ParticleCacheKey");
 158
 159                 for (i = 0; i < totbufkey; i++)
 160                         cache[totkey + i] = ((ParticleCacheKey *)buf->data) + i * totkeys;
 161
 162                 totkey += totbufkey;
 163                 BLI_addtail(bufs, buf);
 164         }
 165
 166         return cache;
 167 }
 168
 169 static void psys_free_path_cache_buffers(ParticleCacheKey **cache, ListBase *bufs)
 170 {
 171         LinkData *buf;
 172
 173         if (cache)
 174                 MEM_freeN(cache);
 175
 176         for (buf = bufs->first; buf; buf = buf->next)
 177                 MEM_freeN(buf->data);
 178         BLI_freelistN(bufs);
 179 }
 180
 181 /************************************************/
 182 /*                      Getting stuff                                           */
 183 /************************************************/
 184 /* get object's active particle system safely */
 185 ParticleSystem *psys_get_current(Object *ob)
 186 {
 187         ParticleSystem *psys;
 188         if (ob == NULL) return NULL;
 189
 190         for (psys = ob->particlesystem.first; psys; psys = psys->next) {
 191                 if (psys->flag & PSYS_CURRENT)
 192                         return psys;
 193         }
 194
 195         return NULL;
 196 }
 197 short psys_get_current_num(Object *ob)
 198 {
 199         ParticleSystem *psys;
 200         short i;
 201
 202         if (ob == NULL) return 0;
 203
 204         for (psys = ob->particlesystem.first, i = 0; psys; psys = psys->next, i++)
 205                 if (psys->flag & PSYS_CURRENT)
 206                         return i;
 207
 208         return i;
 209 }
 210 void psys_set_current_num(Object *ob, int index)
 211 {
 212         ParticleSystem *psys;
 213         short i;
 214
 215         if (ob == NULL) return;
 216
 217         for (psys = ob->particlesystem.first, i = 0; psys; psys = psys->next, i++) {
 218                 if (i == index)
 219                         psys->flag |= PSYS_CURRENT;
 220                 else
 221                         psys->flag &= ~PSYS_CURRENT;
 222         }
 223 }
 224
 225 #if 0 /* UNUSED */
 226 Object *psys_find_object(Scene *scene, ParticleSystem *psys)
 227 {
 228         Base *base;
 229         ParticleSystem *tpsys;
 230
 231         for (base = scene->base.first; base; base = base->next) {
 232                 for (tpsys = base->object->particlesystem.first; psys; psys = psys->next) {
 233                         if (tpsys == psys)
 234                                 return base->object;
 235                 }
 236         }
 237
 238         return NULL;
 239 }
 240 #endif
 241
 242 struct LatticeDeformData *psys_create_lattice_deform_data(ParticleSimulationData *sim)
 243 {
 244         struct LatticeDeformData *lattice_deform_data = NULL;
 245
 246         if (psys_in_edit_mode(sim->scene, sim->psys) == 0) {
 247                 Object *lattice = NULL;
 248                 ModifierData *md = (ModifierData *)psys_get_modifier(sim->ob, sim->psys);
 249
 250                 for (; md; md = md->next) {
 251                         if (md->type == eModifierType_Lattice) {
 252                                 LatticeModifierData *lmd = (LatticeModifierData *)md;
 253                                 lattice = lmd->object;
 254                                 break;
 255                         }
 256                 }
 257                 if (lattice)
 258                         lattice_deform_data = init_latt_deform(lattice, NULL);
 259         }
 260
 261         return lattice_deform_data;
 262 }
 263 void psys_disable_all(Object *ob)
 264 {
 265         ParticleSystem *psys = ob->particlesystem.first;
 266
 267         for (; psys; psys = psys->next)
 268                 psys->flag |= PSYS_DISABLED;
 269 }
 270 void psys_enable_all(Object *ob)
 271 {
 272         ParticleSystem *psys = ob->particlesystem.first;
 273
 274         for (; psys; psys = psys->next)
 275                 psys->flag &= ~PSYS_DISABLED;
 276 }
 277 bool psys_in_edit_mode(Scene *scene, ParticleSystem *psys)
 278 {
 279         return (scene->basact && (scene->basact->object->mode & OB_MODE_PARTICLE_EDIT) && psys == psys_get_current((scene->basact)->object) && (psys->edit || psys->pointcache->edit) && !psys->renderdata);
 280 }
 281 bool psys_check_enabled(Object *ob, ParticleSystem *psys)
 282 {
 283         ParticleSystemModifierData *psmd;
 284
 285         if (psys->flag & PSYS_DISABLED || psys->flag & PSYS_DELETE || !psys->part)
 286                 return 0;
 287
 288         psmd = psys_get_modifier(ob, psys);
 289         if (psys->renderdata || G.is_rendering) {
 290                 if (!(psmd->modifier.mode & eModifierMode_Render))
 291                         return 0;
 292         }
 293         else if (!(psmd->modifier.mode & eModifierMode_Realtime))
 294                 return 0;
 295
 296         return 1;
 297 }
 298
 299 bool psys_check_edited(ParticleSystem *psys)
 300 {
 301         if (psys->part && psys->part->type == PART_HAIR)
 302                 return (psys->flag & PSYS_EDITED || (psys->edit && psys->edit->edited));
 303         else
 304                 return (psys->pointcache->edit && psys->pointcache->edit->edited);
 305 }
 306
 307 void psys_check_group_weights(ParticleSettings *part)
 308 {
 309         ParticleDupliWeight *dw, *tdw;
 310         GroupObject *go;
 311         int current = 0;
 312
 313         if (part->ren_as == PART_DRAW_GR && part->dup_group && part->dup_group->gobject.first) {
 314                 /* first remove all weights that don't have an object in the group */
 315                 dw = part->dupliweights.first;
 316                 while (dw) {
 317                         if (!BKE_group_object_exists(part->dup_group, dw->ob)) {
 318                                 tdw = dw->next;
 319                                 BLI_freelinkN(&part->dupliweights, dw);
 320                                 dw = tdw;
 321                         }
 322                         else
 323                                 dw = dw->next;
 324                 }
 325
 326                 /* then add objects in the group to new list */
 327                 go = part->dup_group->gobject.first;
 328                 while (go) {
 329                         dw = part->dupliweights.first;
 330                         while (dw && dw->ob != go->ob)
 331                                 dw = dw->next;
 332
 333                         if (!dw) {
 334                                 dw = MEM_callocN(sizeof(ParticleDupliWeight), "ParticleDupliWeight");
 335                                 dw->ob = go->ob;
 336                                 dw->count = 1;
 337                                 BLI_addtail(&part->dupliweights, dw);
 338                         }
 339
 340                         go = go->next;
 341                 }
 342
 343                 dw = part->dupliweights.first;
 344                 for (; dw; dw = dw->next) {
 345                         if (dw->flag & PART_DUPLIW_CURRENT) {
 346                                 current = 1;
 347                                 break;
 348                         }
 349                 }
 350
 351                 if (!current) {
 352                         dw = part->dupliweights.first;
 353                         if (dw)
 354                                 dw->flag |= PART_DUPLIW_CURRENT;
 355                 }
 356         }
 357         else {
 358                 BLI_freelistN(&part->dupliweights);
 359         }
 360 }
 361 int psys_uses_gravity(ParticleSimulationData *sim)
 362 {
 363         return sim->scene->physics_settings.flag & PHYS_GLOBAL_GRAVITY && sim->psys->part && sim->psys->part->effector_weights->global_gravity != 0.0f;
 364 }
 365 /************************************************/
 366 /*                      Freeing stuff                                           */
 367 /************************************************/
 368 static void fluid_free_settings(SPHFluidSettings *fluid)
 369 {
 370         if (fluid)
 371                 MEM_freeN(fluid);
 372 }
 373
 374 void BKE_particlesettings_free(ParticleSettings *part)
 375 {
 376         MTex *mtex;
 377         int a;
 378         BKE_animdata_free(&part->id);
 379
 380         if (part->clumpcurve)
 381                 curvemapping_free(part->clumpcurve);
 382         if (part->roughcurve)
 383                 curvemapping_free(part->roughcurve);
 384
 385         free_partdeflect(part->pd);
 386         free_partdeflect(part->pd2);
 387
 388         if (part->effector_weights)
 389                 MEM_freeN(part->effector_weights);
 390
 391         BLI_freelistN(&part->dupliweights);
 392
 393         boid_free_settings(part->boids);
 394         fluid_free_settings(part->fluid);
 395
 396         for (a = 0; a < MAX_MTEX; a++) {
 397                 mtex = part->mtex[a];
 398                 if (mtex && mtex->tex)
 399                         id_us_min(&mtex->tex->id);
 400                 if (mtex)
 401                         MEM_freeN(mtex);
 402         }
 403 }
 404
 405 void free_hair(Object *UNUSED(ob), ParticleSystem *psys, int dynamics)
 406 {
 407         PARTICLE_P;
 408
 409         LOOP_PARTICLES {
 410                 if (pa->hair)
 411                         MEM_freeN(pa->hair);
 412                 pa->hair = NULL;
 413                 pa->totkey = 0;
 414         }
 415
 416         psys->flag &= ~PSYS_HAIR_DONE;
 417
 418         if (psys->clmd) {
 419                 if (dynamics) {
 420                         BKE_ptcache_free_list(&psys->ptcaches);
 421                         psys->pointcache = NULL;
 422
 423                         modifier_free((ModifierData *)psys->clmd);
 424
 425                         psys->clmd = NULL;
 426                         psys->pointcache = BKE_ptcache_add(&psys->ptcaches);
 427                 }
 428                 else {
 429                         cloth_free_modifier(psys->clmd);
 430                 }
 431         }
 432
 433         if (psys->hair_in_dm)
 434                 psys->hair_in_dm->release(psys->hair_in_dm);
 435         psys->hair_in_dm = NULL;
 436
 437         if (psys->hair_out_dm)
 438                 psys->hair_out_dm->release(psys->hair_out_dm);
 439         psys->hair_out_dm = NULL;
 440 }
 441 void free_keyed_keys(ParticleSystem *psys)
 442 {
 443         PARTICLE_P;
 444
 445         if (psys->part->type == PART_HAIR)
 446                 return;
 447
 448         if (psys->particles && psys->particles->keys) {
 449                 MEM_freeN(psys->particles->keys);
 450
 451                 LOOP_PARTICLES {
 452                         if (pa->keys) {
 453                                 pa->keys = NULL;
 454                                 pa->totkey = 0;
 455                         }
 456                 }
 457         }
 458 }
 459 static void free_child_path_cache(ParticleSystem *psys)
 460 {
 461         psys_free_path_cache_buffers(psys->childcache, &psys->childcachebufs);
 462         psys->childcache = NULL;
 463         psys->totchildcache = 0;
 464 }
 465 void psys_free_path_cache(ParticleSystem *psys, PTCacheEdit *edit)
 466 {
 467         if (edit) {
 468                 psys_free_path_cache_buffers(edit->pathcache, &edit->pathcachebufs);
 469                 edit->pathcache = NULL;
 470                 edit->totcached = 0;
 471         }
 472         if (psys) {
 473                 psys_free_path_cache_buffers(psys->pathcache, &psys->pathcachebufs);
 474                 psys->pathcache = NULL;
 475                 psys->totcached = 0;
 476
 477                 free_child_path_cache(psys);
 478         }
 479 }
 480 void psys_free_children(ParticleSystem *psys)
 481 {
 482         if (psys->child) {
 483                 MEM_freeN(psys->child);
 484                 psys->child = NULL;
 485                 psys->totchild = 0;
 486         }
 487
 488         free_child_path_cache(psys);
 489 }
 490 void psys_free_particles(ParticleSystem *psys)
 491 {
 492         PARTICLE_P;
 493
 494         if (psys->particles) {
 495                 if (psys->part->type == PART_HAIR) {
 496                         LOOP_PARTICLES {
 497                                 if (pa->hair)
 498                                         MEM_freeN(pa->hair);
 499                         }
 500                 }
 501
 502                 if (psys->particles->keys)
 503                         MEM_freeN(psys->particles->keys);
 504
 505                 if (psys->particles->boid)
 506                         MEM_freeN(psys->particles->boid);
 507
 508                 MEM_freeN(psys->particles);
 509                 psys->particles = NULL;
 510                 psys->totpart = 0;
 511         }
 512 }
 513 void psys_free_pdd(ParticleSystem *psys)
 514 {
 515         if (psys->pdd) {
 516                 if (psys->pdd->cdata)
 517                         MEM_freeN(psys->pdd->cdata);
 518                 psys->pdd->cdata = NULL;
 519
 520                 if (psys->pdd->vdata)
 521                         MEM_freeN(psys->pdd->vdata);
 522                 psys->pdd->vdata = NULL;
 523
 524                 if (psys->pdd->ndata)
 525                         MEM_freeN(psys->pdd->ndata);
 526                 psys->pdd->ndata = NULL;
 527
 528                 if (psys->pdd->vedata)
 529                         MEM_freeN(psys->pdd->vedata);
 530                 psys->pdd->vedata = NULL;
 531
 532                 psys->pdd->totpoint = 0;
 533                 psys->pdd->tot_vec_size = 0;
 534         }
 535 }
 536 /* free everything */
 537 void psys_free(Object *ob, ParticleSystem *psys)
 538 {
 539         if (psys) {
 540                 int nr = 0;
 541                 ParticleSystem *tpsys;
 542
 543                 psys_free_path_cache(psys, NULL);
 544
 545                 free_hair(ob, psys, 1);
 546
 547                 psys_free_particles(psys);
 548
 549                 if (psys->edit && psys->free_edit)
 550                         psys->free_edit(psys->edit);
 551
 552                 if (psys->child) {
 553                         MEM_freeN(psys->child);
 554                         psys->child = NULL;
 555                         psys->totchild = 0;
 556                 }
 557
 558                 /* check if we are last non-visible particle system */
 559                 for (tpsys = ob->particlesystem.first; tpsys; tpsys = tpsys->next) {
 560                         if (tpsys->part) {
 561                                 if (ELEM(tpsys->part->ren_as, PART_DRAW_OB, PART_DRAW_GR)) {
 562                                         nr++;
 563                                         break;
 564                                 }
 565                         }
 566                 }
 567                 /* clear do-not-draw-flag */
 568                 if (!nr)
 569                         ob->transflag &= ~OB_DUPLIPARTS;
 570
 571                 if (psys->part) {
 572                         id_us_min(&psys->part->id);
 573                         psys->part = NULL;
 574                 }
 575
 576                 BKE_ptcache_free_list(&psys->ptcaches);
 577                 psys->pointcache = NULL;
 578
 579                 BLI_freelistN(&psys->targets);
 580
 581                 BLI_bvhtree_free(psys->bvhtree);
 582                 BLI_kdtree_free(psys->tree);
 583
 584                 if (psys->fluid_springs)
 585                         MEM_freeN(psys->fluid_springs);
 586
 587                 pdEndEffectors(&psys->effectors);
 588
 589                 if (psys->pdd) {
 590                         psys_free_pdd(psys);
 591                         MEM_freeN(psys->pdd);
 592                 }
 593
 594                 MEM_freeN(psys);
 595         }
 596 }
 597
 598 /************************************************/
 599 /*                      Rendering                                                       */
 600 /************************************************/
 601 /* these functions move away particle data and bring it back after
 602  * rendering, to make different render settings possible without
 603  * removing the previous data. this should be solved properly once */
 604
 605 void psys_render_set(Object *ob, ParticleSystem *psys, float viewmat[4][4], float winmat[4][4], int winx, int winy, int timeoffset)
 606 {
 607         ParticleRenderData *data;
 608         ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
 609
 610         if (psys->renderdata)
 611                 return;
 612
 613         data = MEM_callocN(sizeof(ParticleRenderData), "ParticleRenderData");
 614
 615         data->child = psys->child;
 616         data->totchild = psys->totchild;
 617         data->pathcache = psys->pathcache;
 618         data->pathcachebufs.first = psys->pathcachebufs.first;
 619         data->pathcachebufs.last = psys->pathcachebufs.last;
 620         data->totcached = psys->totcached;
 621         data->childcache = psys->childcache;
 622         data->childcachebufs.first = psys->childcachebufs.first;
 623         data->childcachebufs.last = psys->childcachebufs.last;
 624         data->totchildcache = psys->totchildcache;
 625
 626         if (psmd->dm_final)
 627                 data->dm = CDDM_copy(psmd->dm_final);
 628         data->totdmvert = psmd->totdmvert;
 629         data->totdmedge = psmd->totdmedge;
 630         data->totdmface = psmd->totdmface;
 631
 632         psys->child = NULL;
 633         psys->pathcache = NULL;
 634         psys->childcache = NULL;
 635         psys->totchild = psys->totcached = psys->totchildcache = 0;
 636         BLI_listbase_clear(&psys->pathcachebufs);
 637         BLI_listbase_clear(&psys->childcachebufs);
 638
 639         copy_m4_m4(data->winmat, winmat);
 640         mul_m4_m4m4(data->viewmat, viewmat, ob->obmat);
 641         mul_m4_m4m4(data->mat, winmat, data->viewmat);
 642         data->winx = winx;
 643         data->winy = winy;
 644
 645         data->timeoffset = timeoffset;
 646
 647         psys->renderdata = data;
 648
 649         /* Hair can and has to be recalculated if everything isn't displayed. */
 650         if (psys->part->disp != 100 && psys->part->type == PART_HAIR)
 651                 psys->recalc |= PSYS_RECALC_RESET;
 652 }
 653
 654 void psys_render_restore(Object *ob, ParticleSystem *psys)
 655 {
 656         ParticleRenderData *data;
 657         ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
 658         float render_disp = psys_get_current_display_percentage(psys);
 659         float disp;
 660
 661         data = psys->renderdata;
 662         if (!data)
 663                 return;
 664
 665         if (data->elems)
 666                 MEM_freeN(data->elems);
 667
 668         if (psmd->dm_final) {
 669                 psmd->dm_final->needsFree = 1;
 670                 psmd->dm_final->release(psmd->dm_final);
 671         }
 672         if (psmd->dm_deformed) {
 673                 psmd->dm_deformed->needsFree = 1;
 674                 psmd->dm_deformed->release(psmd->dm_deformed);
 675                 psmd->dm_deformed = NULL;
 676         }
 677
 678         psys_free_path_cache(psys, NULL);
 679
 680         if (psys->child) {
 681                 MEM_freeN(psys->child);
 682                 psys->child = 0;
 683                 psys->totchild = 0;
 684         }
 685
 686         psys->child = data->child;
 687         psys->totchild = data->totchild;
 688         psys->pathcache = data->pathcache;
 689         psys->pathcachebufs.first = data->pathcachebufs.first;
 690         psys->pathcachebufs.last = data->pathcachebufs.last;
 691         psys->totcached = data->totcached;
 692         psys->childcache = data->childcache;
 693         psys->childcachebufs.first = data->childcachebufs.first;
 694         psys->childcachebufs.last = data->childcachebufs.last;
 695         psys->totchildcache = data->totchildcache;
 696
 697         psmd->dm_final = data->dm;
 698         psmd->totdmvert = data->totdmvert;
 699         psmd->totdmedge = data->totdmedge;
 700         psmd->totdmface = data->totdmface;
 701         psmd->flag &= ~eParticleSystemFlag_psys_updated;
 702
 703         if (psmd->dm_final) {
 704                 if (!psmd->dm_final->deformedOnly) {
 705                         if (ob->derivedDeform) {
 706                                 psmd->dm_deformed = CDDM_copy(ob->derivedDeform);
 707                         }
 708                         else {
 709                                 psmd->dm_deformed = CDDM_from_mesh((Mesh *)ob->data);
 710                         }
 711                         DM_ensure_tessface(psmd->dm_deformed);
 712                 }
 713                 psys_calc_dmcache(ob, psmd->dm_final, psmd->dm_deformed, psys);
 714         }
 715
 716         MEM_freeN(data);
 717         psys->renderdata = NULL;
 718
 719         /* restore particle display percentage */
 720         disp = psys_get_current_display_percentage(psys);
 721
 722         if (disp != render_disp) {
 723                 /* Hair can and has to be recalculated if everything isn't displayed. */
 724                 if (psys->part->type == PART_HAIR) {
 725                         psys->recalc |= PSYS_RECALC_RESET;
 726                 }
 727                 else {
 728                         PARTICLE_P;
 729
 730                         LOOP_PARTICLES {
 731                                 if (psys_frand(psys, p) > disp)
 732                                         pa->flag |= PARS_NO_DISP;
 733                                 else
 734                                         pa->flag &= ~PARS_NO_DISP;
 735                         }
 736                 }
 737         }
 738 }
 739
 740 bool psys_render_simplify_params(ParticleSystem *psys, ChildParticle *cpa, float *params)
 741 {
 742         ParticleRenderData *data;
 743         ParticleRenderElem *elem;
 744         float x, w, scale, alpha, lambda, t, scalemin, scalemax;
 745         int b;
 746
 747         if (!(psys->renderdata && (psys->part->simplify_flag & PART_SIMPLIFY_ENABLE)))
 748                 return false;
 749
 750         data = psys->renderdata;
 751         if (!data->do_simplify)
 752                 return false;
 753         b = (data->index_mf_to_mpoly) ? DM_origindex_mface_mpoly(data->index_mf_to_mpoly, data->index_mp_to_orig, cpa->num) : cpa->num;
 754         if (b == ORIGINDEX_NONE) {
 755                 return false;
 756         }
 757
 758         elem = &data->elems[b];
 759
 760         lambda = elem->lambda;
 761         t = elem->t;
 762         scalemin = elem->scalemin;
 763         scalemax = elem->scalemax;
 764
 765         if (!elem->reduce) {
 766                 scale = scalemin;
 767                 alpha = 1.0f;
 768         }
 769         else {
 770                 x = (elem->curchild + 0.5f) / elem->totchild;
 771                 if (x < lambda - t) {
 772                         scale = scalemax;
 773                         alpha = 1.0f;
 774                 }
 775                 else if (x >= lambda + t) {
 776                         scale = scalemin;
 777                         alpha = 0.0f;
 778                 }
 779                 else {
 780                         w = (lambda + t - x) / (2.0f * t);
 781                         scale = scalemin + (scalemax - scalemin) * w;
 782                         alpha = w;
 783                 }
 784         }
 785
 786         params[0] = scale;
 787         params[1] = alpha;
 788
 789         elem->curchild++;
 790
 791         return 1;
 792 }
 793
 794 /************************************************/
 795 /*                      Interpolation                                           */
 796 /************************************************/
 797 static float interpolate_particle_value(float v1, float v2, float v3, float v4, const float w[4], int four)
 798 {
 799         float value;
 800
 801         value = w[0] * v1 + w[1] * v2 + w[2] * v3;
 802         if (four)
 803                 value += w[3] * v4;
 804
 805         CLAMP(value, 0.f, 1.f);
 806
 807         return value;
 808 }
 809
 810 void psys_interpolate_particle(short type, ParticleKey keys[4], float dt, ParticleKey *result, bool velocity)
 811 {
 812         float t[4];
 813
 814         if (type < 0) {
 815                 interp_cubic_v3(result->co, result->vel, keys[1].co, keys[1].vel, keys[2].co, keys[2].vel, dt);
 816         }
 817         else {
 818                 key_curve_position_weights(dt, t, type);
 819
 820                 interp_v3_v3v3v3v3(result->co, keys[0].co, keys[1].co, keys[2].co, keys[3].co, t);
 821
 822                 if (velocity) {
 823                         float temp[3];
 824
 825                         if (dt > 0.999f) {
 826                                 key_curve_position_weights(dt - 0.001f, t, type);
 827                                 interp_v3_v3v3v3v3(temp, keys[0].co, keys[1].co, keys[2].co, keys[3].co, t);
 828                                 sub_v3_v3v3(result->vel, result->co, temp);
 829                         }
 830                         else {
 831                                 key_curve_position_weights(dt + 0.001f, t, type);
 832                                 interp_v3_v3v3v3v3(temp, keys[0].co, keys[1].co, keys[2].co, keys[3].co, t);
 833                                 sub_v3_v3v3(result->vel, temp, result->co);
 834                         }
 835                 }
 836         }
 837 }
 838
 839
 840 typedef struct ParticleInterpolationData {
 841         HairKey *hkey[2];
 842
 843         DerivedMesh *dm;
 844         MVert *mvert[2];
 845
 846         int keyed;
 847         ParticleKey *kkey[2];
 848
 849         PointCache *cache;
 850         PTCacheMem *pm;
 851
 852         PTCacheEditPoint *epoint;
 853         PTCacheEditKey *ekey[2];
 854
 855         float birthtime, dietime;
 856         int bspline;
 857 } ParticleInterpolationData;
 858 /* Assumes pointcache->mem_cache exists, so for disk cached particles call psys_make_temp_pointcache() before use */
 859 /* It uses ParticleInterpolationData->pm to store the current memory cache frame so it's thread safe. */
 860 static void get_pointcache_keys_for_time(Object *UNUSED(ob), PointCache *cache, PTCacheMem **cur, int index, float t, ParticleKey *key1, ParticleKey *key2)
 861 {
 862         static PTCacheMem *pm = NULL;
 863         int index1, index2;
 864
 865         if (index < 0) { /* initialize */
 866                 *cur = cache->mem_cache.first;
 867
 868                 if (*cur)
 869                         *cur = (*cur)->next;
 870         }
 871         else {
 872                 if (*cur) {
 873                         while (*cur && (*cur)->next && (float)(*cur)->frame < t)
 874                                 *cur = (*cur)->next;
 875
 876                         pm = *cur;
 877
 878                         index2 = BKE_ptcache_mem_index_find(pm, index);
 879                         index1 = BKE_ptcache_mem_index_find(pm->prev, index);
 880
 881                         BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
 882                         if (index1 < 0)
 883                                 copy_particle_key(key1, key2, 1);
 884                         else
 885                                 BKE_ptcache_make_particle_key(key1, index1, pm->prev->data, (float)pm->prev->frame);
 886                 }
 887                 else if (cache->mem_cache.first) {
 888                         pm = cache->mem_cache.first;
 889                         index2 = BKE_ptcache_mem_index_find(pm, index);
 890                         BKE_ptcache_make_particle_key(key2, index2, pm->data, (float)pm->frame);
 891                         copy_particle_key(key1, key2, 1);
 892                 }
 893         }
 894 }
 895 static int get_pointcache_times_for_particle(PointCache *cache, int index, float *start, float *end)
 896 {
 897         PTCacheMem *pm;
 898         int ret = 0;
 899
 900         for (pm = cache->mem_cache.first; pm; pm = pm->next) {
 901                 if (BKE_ptcache_mem_index_find(pm, index) >= 0) {
 902                         *start = pm->frame;
 903                         ret++;
 904                         break;
 905                 }
 906         }
 907
 908         for (pm = cache->mem_cache.last; pm; pm = pm->prev) {
 909                 if (BKE_ptcache_mem_index_find(pm, index) >= 0) {
 910                         *end = pm->frame;
 911                         ret++;
 912                         break;
 913                 }
 914         }
 915
 916         return ret == 2;
 917 }
 918
 919 float psys_get_dietime_from_cache(PointCache *cache, int index)
 920 {
 921         PTCacheMem *pm;
 922         int dietime = 10000000; /* some max value so that we can default to pa->time+lifetime */
 923
 924         for (pm = cache->mem_cache.last; pm; pm = pm->prev) {
 925                 if (BKE_ptcache_mem_index_find(pm, index) >= 0)
 926                         return (float)pm->frame;
 927         }
 928
 929         return (float)dietime;
 930 }
 931
 932 static void init_particle_interpolation(Object *ob, ParticleSystem *psys, ParticleData *pa, ParticleInterpolationData *pind)
 933 {
 934
 935         if (pind->epoint) {
 936                 PTCacheEditPoint *point = pind->epoint;
 937
 938                 pind->ekey[0] = point->keys;
 939                 pind->ekey[1] = point->totkey > 1 ? point->keys + 1 : NULL;
 940
 941                 pind->birthtime = *(point->keys->time);
 942                 pind->dietime = *((point->keys + point->totkey - 1)->time);
 943         }
 944         else if (pind->keyed) {
 945                 ParticleKey *key = pa->keys;
 946                 pind->kkey[0] = key;
 947                 pind->kkey[1] = pa->totkey > 1 ? key + 1 : NULL;
 948
 949                 pind->birthtime = key->time;
 950                 pind->dietime = (key + pa->totkey - 1)->time;
 951         }
 952         else if (pind->cache) {
 953                 float start = 0.0f, end = 0.0f;
 954                 get_pointcache_keys_for_time(ob, pind->cache, &pind->pm, -1, 0.0f, NULL, NULL);
 955                 pind->birthtime = pa ? pa->time : pind->cache->startframe;
 956                 pind->dietime = pa ? pa->dietime : pind->cache->endframe;
 957
 958                 if (get_pointcache_times_for_particle(pind->cache, pa - psys->particles, &start, &end)) {
 959                         pind->birthtime = MAX2(pind->birthtime, start);
 960                         pind->dietime = MIN2(pind->dietime, end);
 961                 }
 962         }
 963         else {
 964                 HairKey *key = pa->hair;
 965                 pind->hkey[0] = key;
 966                 pind->hkey[1] = key + 1;
 967
 968                 pind->birthtime = key->time;
 969                 pind->dietime = (key + pa->totkey - 1)->time;
 970
 971                 if (pind->dm) {
 972                         pind->mvert[0] = CDDM_get_vert(pind->dm, pa->hair_index);
 973                         pind->mvert[1] = pind->mvert[0] + 1;
 974                 }
 975         }
 976 }
 977 static void edit_to_particle(ParticleKey *key, PTCacheEditKey *ekey)
 978 {
 979         copy_v3_v3(key->co, ekey->co);
 980         if (ekey->vel) {
 981                 copy_v3_v3(key->vel, ekey->vel);
 982         }
 983         key->time = *(ekey->time);
 984 }
 985 static void hair_to_particle(ParticleKey *key, HairKey *hkey)
 986 {
 987         copy_v3_v3(key->co, hkey->co);
 988         key->time = hkey->time;
 989 }
 990
 991 static void mvert_to_particle(ParticleKey *key, MVert *mvert, HairKey *hkey)
 992 {
 993         copy_v3_v3(key->co, mvert->co);
 994         key->time = hkey->time;
 995 }
 996
 997 static void do_particle_interpolation(ParticleSystem *psys, int p, ParticleData *pa, float t, ParticleInterpolationData *pind, ParticleKey *result)
 998 {
 999         PTCacheEditPoint *point = pind->epoint;
1000         ParticleKey keys[4];
1001         int point_vel = (point && point->keys->vel);
1002         float real_t, dfra, keytime, invdt = 1.f;
1003
1004         /* billboards wont fill in all of these, so start cleared */
1005         memset(keys, 0, sizeof(keys));
1006
1007         /* interpret timing and find keys */
1008         if (point) {
1009                 if (result->time < 0.0f)
1010                         real_t = -result->time;
1011                 else
1012                         real_t = *(pind->ekey[0]->time) + t * (*(pind->ekey[0][point->totkey - 1].time) - *(pind->ekey[0]->time));
1013
1014                 while (*(pind->ekey[1]->time) < real_t)
1015                         pind->ekey[1]++;
1016
1017                 pind->ekey[0] = pind->ekey[1] - 1;
1018         }
1019         else if (pind->keyed) {
1020                 /* we have only one key, so let's use that */
1021                 if (pind->kkey[1] == NULL) {
1022                         copy_particle_key(result, pind->kkey[0], 1);
1023                         return;
1024                 }
1025
1026                 if (result->time < 0.0f)
1027                         real_t = -result->time;
1028                 else
1029                         real_t = pind->kkey[0]->time + t * (pind->kkey[0][pa->totkey - 1].time - pind->kkey[0]->time);
1030
1031                 if (psys->part->phystype == PART_PHYS_KEYED && psys->flag & PSYS_KEYED_TIMING) {
1032                         ParticleTarget *pt = psys->targets.first;
1033
1034                         pt = pt->next;
1035
1036                         while (pt && pa->time + pt->time < real_t)
1037                                 pt = pt->next;
1038
1039                         if (pt) {
1040                                 pt = pt->prev;
1041
1042                                 if (pa->time + pt->time + pt->duration > real_t)
1043                                         real_t = pa->time + pt->time;
1044                         }
1045                         else
1046                                 real_t = pa->time + ((ParticleTarget *)psys->targets.last)->time;
1047                 }
1048
1049                 CLAMP(real_t, pa->time, pa->dietime);
1050
1051                 while (pind->kkey[1]->time < real_t)
1052                         pind->kkey[1]++;
1053
1054                 pind->kkey[0] = pind->kkey[1] - 1;
1055         }
1056         else if (pind->cache) {
1057                 if (result->time < 0.0f) /* flag for time in frames */
1058                         real_t = -result->time;
1059                 else
1060                         real_t = pa->time + t * (pa->dietime - pa->time);
1061         }
1062         else {
1063                 if (result->time < 0.0f)
1064                         real_t = -result->time;
1065                 else
1066                         real_t = pind->hkey[0]->time + t * (pind->hkey[0][pa->totkey - 1].time - pind->hkey[0]->time);
1067
1068                 while (pind->hkey[1]->time < real_t) {
1069                         pind->hkey[1]++;
1070                         pind->mvert[1]++;
1071                 }
1072
1073                 pind->hkey[0] = pind->hkey[1] - 1;
1074         }
1075
1076         /* set actual interpolation keys */
1077         if (point) {
1078                 edit_to_particle(keys + 1, pind->ekey[0]);
1079                 edit_to_particle(keys + 2, pind->ekey[1]);
1080         }
1081         else if (pind->dm) {
1082                 pind->mvert[0] = pind->mvert[1] - 1;
1083                 mvert_to_particle(keys + 1, pind->mvert[0], pind->hkey[0]);
1084                 mvert_to_particle(keys + 2, pind->mvert[1], pind->hkey[1]);
1085         }
1086         else if (pind->keyed) {
1087                 memcpy(keys + 1, pind->kkey[0], sizeof(ParticleKey));
1088                 memcpy(keys + 2, pind->kkey[1], sizeof(ParticleKey));
1089         }
1090         else if (pind->cache) {
1091                 get_pointcache_keys_for_time(NULL, pind->cache, &pind->pm, p, real_t, keys + 1, keys + 2);
1092         }
1093         else {
1094                 hair_to_particle(keys + 1, pind->hkey[0]);
1095                 hair_to_particle(keys + 2, pind->hkey[1]);
1096         }
1097
1098         /* set secondary interpolation keys for hair */
1099         if (!pind->keyed && !pind->cache && !point_vel) {
1100                 if (point) {
1101                         if (pind->ekey[0] != point->keys)
1102                                 edit_to_particle(keys, pind->ekey[0] - 1);
1103                         else
1104                                 edit_to_particle(keys, pind->ekey[0]);
1105                 }
1106                 else if (pind->dm) {
1107                         if (pind->hkey[0] != pa->hair)
1108                                 mvert_to_particle(keys, pind->mvert[0] - 1, pind->hkey[0] - 1);
1109                         else
1110                                 mvert_to_particle(keys, pind->mvert[0], pind->hkey[0]);
1111                 }
1112                 else {
1113                         if (pind->hkey[0] != pa->hair)
1114                                 hair_to_particle(keys, pind->hkey[0] - 1);
1115                         else
1116                                 hair_to_particle(keys, pind->hkey[0]);
1117                 }
1118
1119                 if (point) {
1120                         if (pind->ekey[1] != point->keys + point->totkey - 1)
1121                                 edit_to_particle(keys + 3, pind->ekey[1] + 1);
1122                         else
1123                                 edit_to_particle(keys + 3, pind->ekey[1]);
1124                 }
1125                 else if (pind->dm) {
1126                         if (pind->hkey[1] != pa->hair + pa->totkey - 1)
1127                                 mvert_to_particle(keys + 3, pind->mvert[1] + 1, pind->hkey[1] + 1);
1128                         else
1129                                 mvert_to_particle(keys + 3, pind->mvert[1], pind->hkey[1]);
1130                 }
1131                 else {
1132                         if (pind->hkey[1] != pa->hair + pa->totkey - 1)
1133                                 hair_to_particle(keys + 3, pind->hkey[1] + 1);
1134                         else
1135                                 hair_to_particle(keys + 3, pind->hkey[1]);
1136                 }
1137         }
1138
1139         dfra = keys[2].time - keys[1].time;
1140         keytime = (real_t - keys[1].time) / dfra;
1141
1142         /* convert velocity to timestep size */
1143         if (pind->keyed || pind->cache || point_vel) {
1144                 invdt = dfra * 0.04f * (psys ? psys->part->timetweak : 1.f);
1145                 mul_v3_fl(keys[1].vel, invdt);
1146                 mul_v3_fl(keys[2].vel, invdt);
1147                 interp_qt_qtqt(result->rot, keys[1].rot, keys[2].rot, keytime);
1148         }
1149
1150         /* 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)*/
1151         psys_interpolate_particle((pind->keyed || pind->cache || point_vel) ? -1 /* signal for cubic interpolation */
1152                                   : (pind->bspline ? KEY_BSPLINE : KEY_CARDINAL),
1153                                   keys, keytime, result, 1);
1154
1155         /* the velocity needs to be converted back from cubic interpolation */
1156         if (pind->keyed || pind->cache || point_vel)
1157                 mul_v3_fl(result->vel, 1.f / invdt);
1158 }
1159
1160 static void interpolate_pathcache(ParticleCacheKey *first, float t, ParticleCacheKey *result)
1161 {
1162         int i = 0;
1163         ParticleCacheKey *cur = first;
1164
1165         /* scale the requested time to fit the entire path even if the path is cut early */
1166         t *= (first + first->segments)->time;
1167
1168         while (i < first->segments && cur->time < t)
1169                 cur++;
1170
1171         if (cur->time == t)
1172                 *result = *cur;
1173         else {
1174                 float dt = (t - (cur - 1)->time) / (cur->time - (cur - 1)->time);
1175                 interp_v3_v3v3(result->co, (cur - 1)->co, cur->co, dt);
1176                 interp_v3_v3v3(result->vel, (cur - 1)->vel, cur->vel, dt);
1177                 interp_qt_qtqt(result->rot, (cur - 1)->rot, cur->rot, dt);
1178                 result->time = t;
1179         }
1180
1181         /* first is actual base rotation, others are incremental from first */
1182         if (cur == first || cur - 1 == first)
1183                 copy_qt_qt(result->rot, first->rot);
1184         else
1185                 mul_qt_qtqt(result->rot, first->rot, result->rot);
1186 }
1187
1188 /************************************************/
1189 /*                      Particles on a dm                                       */
1190 /************************************************/
1191 /* interpolate a location on a face based on face coordinates */
1192 void psys_interpolate_face(MVert *mvert, MFace *mface, MTFace *tface, float (*orcodata)[3],
1193                            float w[4], float vec[3], float nor[3], float utan[3], float vtan[3],
1194                            float orco[3], float ornor[3])
1195 {
1196         float *v1 = 0, *v2 = 0, *v3 = 0, *v4 = 0;
1197         float e1[3], e2[3], s1, s2, t1, t2;
1198         float *uv1, *uv2, *uv3, *uv4;
1199         float n1[3], n2[3], n3[3], n4[3];
1200         float tuv[4][2];
1201         float *o1, *o2, *o3, *o4;
1202
1203         v1 = mvert[mface->v1].co;
1204         v2 = mvert[mface->v2].co;
1205         v3 = mvert[mface->v3].co;
1206
1207         normal_short_to_float_v3(n1, mvert[mface->v1].no);
1208         normal_short_to_float_v3(n2, mvert[mface->v2].no);
1209         normal_short_to_float_v3(n3, mvert[mface->v3].no);
1210
1211         if (mface->v4) {
1212                 v4 = mvert[mface->v4].co;
1213                 normal_short_to_float_v3(n4, mvert[mface->v4].no);
1214
1215                 interp_v3_v3v3v3v3(vec, v1, v2, v3, v4, w);
1216
1217                 if (nor) {
1218                         if (mface->flag & ME_SMOOTH)
1219                                 interp_v3_v3v3v3v3(nor, n1, n2, n3, n4, w);
1220                         else
1221                                 normal_quad_v3(nor, v1, v2, v3, v4);
1222                 }
1223         }
1224         else {
1225                 interp_v3_v3v3v3(vec, v1, v2, v3, w);
1226
1227                 if (nor) {
1228                         if (mface->flag & ME_SMOOTH)
1229                                 interp_v3_v3v3v3(nor, n1, n2, n3, w);
1230                         else
1231                                 normal_tri_v3(nor, v1, v2, v3);
1232                 }
1233         }
1234
1235         /* calculate tangent vectors */
1236         if (utan && vtan) {
1237                 if (tface) {
1238                         uv1 = tface->uv[0];
1239                         uv2 = tface->uv[1];
1240                         uv3 = tface->uv[2];
1241                         uv4 = tface->uv[3];
1242                 }
1243                 else {
1244                         uv1 = tuv[0]; uv2 = tuv[1]; uv3 = tuv[2]; uv4 = tuv[3];
1245                         map_to_sphere(uv1, uv1 + 1, v1[0], v1[1], v1[2]);
1246                         map_to_sphere(uv2, uv2 + 1, v2[0], v2[1], v2[2]);
1247                         map_to_sphere(uv3, uv3 + 1, v3[0], v3[1], v3[2]);
1248                         if (v4)
1249                                 map_to_sphere(uv4, uv4 + 1, v4[0], v4[1], v4[2]);
1250                 }
1251
1252                 if (v4) {
1253                         s1 = uv3[0] - uv1[0];
1254                         s2 = uv4[0] - uv1[0];
1255
1256                         t1 = uv3[1] - uv1[1];
1257                         t2 = uv4[1] - uv1[1];
1258
1259                         sub_v3_v3v3(e1, v3, v1);
1260                         sub_v3_v3v3(e2, v4, v1);
1261                 }
1262                 else {
1263                         s1 = uv2[0] - uv1[0];
1264                         s2 = uv3[0] - uv1[0];
1265
1266                         t1 = uv2[1] - uv1[1];
1267                         t2 = uv3[1] - uv1[1];
1268
1269                         sub_v3_v3v3(e1, v2, v1);
1270                         sub_v3_v3v3(e2, v3, v1);
1271                 }
1272
1273                 vtan[0] = (s1 * e2[0] - s2 * e1[0]);
1274                 vtan[1] = (s1 * e2[1] - s2 * e1[1]);
1275                 vtan[2] = (s1 * e2[2] - s2 * e1[2]);
1276
1277                 utan[0] = (t1 * e2[0] - t2 * e1[0]);
1278                 utan[1] = (t1 * e2[1] - t2 * e1[1]);
1279                 utan[2] = (t1 * e2[2] - t2 * e1[2]);
1280         }
1281
1282         if (orco) {
1283                 if (orcodata) {
1284                         o1 = orcodata[mface->v1];
1285                         o2 = orcodata[mface->v2];
1286                         o3 = orcodata[mface->v3];
1287
1288                         if (mface->v4) {
1289                                 o4 = orcodata[mface->v4];
1290
1291                                 interp_v3_v3v3v3v3(orco, o1, o2, o3, o4, w);
1292
1293                                 if (ornor)
1294                                         normal_quad_v3(ornor, o1, o2, o3, o4);
1295                         }
1296                         else {
1297                                 interp_v3_v3v3v3(orco, o1, o2, o3, w);
1298
1299                                 if (ornor)
1300                                         normal_tri_v3(ornor, o1, o2, o3);
1301                         }
1302                 }
1303                 else {
1304                         copy_v3_v3(orco, vec);
1305                         if (ornor && nor)
1306                                 copy_v3_v3(ornor, nor);
1307                 }
1308         }
1309 }
1310 void psys_interpolate_uvs(const MTFace *tface, int quad, const float w[4], float uvco[2])
1311 {
1312         float v10 = tface->uv[0][0];
1313         float v11 = tface->uv[0][1];
1314         float v20 = tface->uv[1][0];
1315         float v21 = tface->uv[1][1];
1316         float v30 = tface->uv[2][0];
1317         float v31 = tface->uv[2][1];
1318         float v40, v41;
1319
1320         if (quad) {
1321                 v40 = tface->uv[3][0];
1322                 v41 = tface->uv[3][1];
1323
1324                 uvco[0] = w[0] * v10 + w[1] * v20 + w[2] * v30 + w[3] * v40;
1325                 uvco[1] = w[0] * v11 + w[1] * v21 + w[2] * v31 + w[3] * v41;
1326         }
1327         else {
1328                 uvco[0] = w[0] * v10 + w[1] * v20 + w[2] * v30;
1329                 uvco[1] = w[0] * v11 + w[1] * v21 + w[2] * v31;
1330         }
1331 }
1332
1333 void psys_interpolate_mcol(const MCol *mcol, int quad, const float w[4], MCol *mc)
1334 {
1335         const char *cp1, *cp2, *cp3, *cp4;
1336         char *cp;
1337
1338         cp = (char *)mc;
1339         cp1 = (const char *)&mcol[0];
1340         cp2 = (const char *)&mcol[1];
1341         cp3 = (const char *)&mcol[2];
1342
1343         if (quad) {
1344                 cp4 = (char *)&mcol[3];
1345
1346                 cp[0] = (int)(w[0] * cp1[0] + w[1] * cp2[0] + w[2] * cp3[0] + w[3] * cp4[0]);
1347                 cp[1] = (int)(w[0] * cp1[1] + w[1] * cp2[1] + w[2] * cp3[1] + w[3] * cp4[1]);
1348                 cp[2] = (int)(w[0] * cp1[2] + w[1] * cp2[2] + w[2] * cp3[2] + w[3] * cp4[2]);
1349                 cp[3] = (int)(w[0] * cp1[3] + w[1] * cp2[3] + w[2] * cp3[3] + w[3] * cp4[3]);
1350         }
1351         else {
1352                 cp[0] = (int)(w[0] * cp1[0] + w[1] * cp2[0] + w[2] * cp3[0]);
1353                 cp[1] = (int)(w[0] * cp1[1] + w[1] * cp2[1] + w[2] * cp3[1]);
1354                 cp[2] = (int)(w[0] * cp1[2] + w[1] * cp2[2] + w[2] * cp3[2]);
1355                 cp[3] = (int)(w[0] * cp1[3] + w[1] * cp2[3] + w[2] * cp3[3]);
1356         }
1357 }
1358
1359 static float psys_interpolate_value_from_verts(DerivedMesh *dm, short from, int index, const float fw[4], const float *values)
1360 {
1361         if (values == 0 || index == -1)
1362                 return 0.0;
1363
1364         switch (from) {
1365                 case PART_FROM_VERT:
1366                         return values[index];
1367                 case PART_FROM_FACE:
1368                 case PART_FROM_VOLUME:
1369                 {
1370                         MFace *mf = dm->getTessFaceData(dm, index, CD_MFACE);
1371                         return interpolate_particle_value(values[mf->v1], values[mf->v2], values[mf->v3], values[mf->v4], fw, mf->v4);
1372                 }
1373
1374         }
1375         return 0.0f;
1376 }
1377
1378 /* conversion of pa->fw to origspace layer coordinates */
1379 static void psys_w_to_origspace(const float w[4], float uv[2])
1380 {
1381         uv[0] = w[1] + w[2];
1382         uv[1] = w[2] + w[3];
1383 }
1384
1385 /* conversion of pa->fw to weights in face from origspace */
1386 static void psys_origspace_to_w(OrigSpaceFace *osface, int quad, const float w[4], float neww[4])
1387 {
1388         float v[4][3], co[3];
1389
1390         v[0][0] = osface->uv[0][0]; v[0][1] = osface->uv[0][1]; v[0][2] = 0.0f;
1391         v[1][0] = osface->uv[1][0]; v[1][1] = osface->uv[1][1]; v[1][2] = 0.0f;
1392         v[2][0] = osface->uv[2][0]; v[2][1] = osface->uv[2][1]; v[2][2] = 0.0f;
1393
1394         psys_w_to_origspace(w, co);
1395         co[2] = 0.0f;
1396
1397         if (quad) {
1398                 v[3][0] = osface->uv[3][0]; v[3][1] = osface->uv[3][1]; v[3][2] = 0.0f;
1399                 interp_weights_poly_v3(neww, v, 4, co);
1400         }
1401         else {
1402                 interp_weights_poly_v3(neww, v, 3, co);
1403                 neww[3] = 0.0f;
1404         }
1405 }
1406
1407 /**
1408  * Find the final derived mesh tessface for a particle, from its original tessface index.
1409  * This is slow and can be optimized but only for many lookups.
1410  *
1411  * \param dm_final final DM, it may not have the same topology as original mesh.
1412  * \param dm_deformed deformed-only DM, it has the exact same topology as original mesh.
1413  * \param findex_orig the input tessface index.
1414  * \param fw face weights (position of the particle inside the \a findex_orig tessface).
1415  * \param poly_nodes may be NULL, otherwise an array of linked list, one for each final DM polygon, containing all
1416  *                   its tessfaces indices.
1417  * \return the DM tessface index.
1418  */
1419 int psys_particle_dm_face_lookup(
1420         DerivedMesh *dm_final, DerivedMesh *dm_deformed,
1421         int findex_orig, const float fw[4], struct LinkNode **poly_nodes)
1422 {
1423         MFace *mtessface_final;
1424         OrigSpaceFace *osface_final;
1425         int pindex_orig;
1426         float uv[2], (*faceuv)[2];
1427
1428         const int *index_mf_to_mpoly_deformed = NULL;
1429         const int *index_mf_to_mpoly = NULL;
1430         const int *index_mp_to_orig = NULL;
1431
1432         const int totface_final = dm_final->getNumTessFaces(dm_final);
1433         const int totface_deformed = dm_deformed ? dm_deformed->getNumTessFaces(dm_deformed) : totface_final;
1434
1435         if (ELEM(0, totface_final, totface_deformed)) {
1436                 return DMCACHE_NOTFOUND;
1437         }
1438
1439         index_mf_to_mpoly = dm_final->getTessFaceDataArray(dm_final, CD_ORIGINDEX);
1440         index_mp_to_orig = dm_final->getPolyDataArray(dm_final, CD_ORIGINDEX);
1441         BLI_assert(index_mf_to_mpoly);
1442
1443         if (dm_deformed) {
1444                 index_mf_to_mpoly_deformed = dm_deformed->getTessFaceDataArray(dm_deformed, CD_ORIGINDEX);
1445         }
1446         else {
1447                 BLI_assert(dm_final->deformedOnly);
1448                 index_mf_to_mpoly_deformed = index_mf_to_mpoly;
1449         }
1450         BLI_assert(index_mf_to_mpoly_deformed);
1451
1452         pindex_orig = index_mf_to_mpoly_deformed[findex_orig];
1453
1454         if (dm_deformed == NULL) {
1455                 dm_deformed = dm_final;
1456         }
1457
1458         index_mf_to_mpoly_deformed = NULL;
1459
1460         mtessface_final = dm_final->getTessFaceArray(dm_final);
1461         osface_final = dm_final->getTessFaceDataArray(dm_final, CD_ORIGSPACE);
1462
1463         if (osface_final == NULL) {
1464                 /* Assume we don't need osface_final data, and we get a direct 1-1 mapping... */
1465                 if (findex_orig < totface_final) {
1466                         //printf("\tNO CD_ORIGSPACE, assuming not needed\n");
1467                         return findex_orig;
1468                 }
1469                 else {
1470                         printf("\tNO CD_ORIGSPACE, error out of range\n");
1471                         return DMCACHE_NOTFOUND;
1472                 }
1473         }
1474         else if (findex_orig >= dm_deformed->getNumTessFaces(dm_deformed)) {
1475                 return DMCACHE_NOTFOUND;  /* index not in the original mesh */
1476         }
1477
1478         psys_w_to_origspace(fw, uv);
1479
1480         if (poly_nodes) {
1481                 /* we can have a restricted linked list of faces to check, faster! */
1482                 LinkNode *tessface_node = poly_nodes[pindex_orig];
1483
1484                 for (; tessface_node; tessface_node = tessface_node->next) {
1485                         int findex_dst = GET_INT_FROM_POINTER(tessface_node->link);
1486                         faceuv = osface_final[findex_dst].uv;
1487
1488                         /* check that this intersects - Its possible this misses :/ -
1489                          * could also check its not between */
1490                         if (mtessface_final[findex_dst].v4) {
1491                                 if (isect_point_quad_v2(uv, faceuv[0], faceuv[1], faceuv[2], faceuv[3])) {
1492                                         return findex_dst;
1493                                 }
1494                         }
1495                         else if (isect_point_tri_v2(uv, faceuv[0], faceuv[1], faceuv[2])) {
1496                                 return findex_dst;
1497                         }
1498                 }
1499         }
1500         else { /* if we have no node, try every face */
1501                 for (int findex_dst = 0; findex_dst < totface_final; findex_dst++) {
1502                         /* If current tessface from 'final' DM and orig tessface (given by index) map to the same orig poly... */
1503                         if (DM_origindex_mface_mpoly(index_mf_to_mpoly, index_mp_to_orig, findex_dst) == pindex_orig) {
1504                                 faceuv = osface_final[findex_dst].uv;
1505
1506                                 /* check that this intersects - Its possible this misses :/ -
1507                                  * could also check its not between */
1508                                 if (mtessface_final[findex_dst].v4) {
1509                                         if (isect_point_quad_v2(uv, faceuv[0], faceuv[1], faceuv[2], faceuv[3])) {
1510                                                 return findex_dst;
1511                                         }
1512                                 }
1513                                 else if (isect_point_tri_v2(uv, faceuv[0], faceuv[1], faceuv[2])) {
1514                                         return findex_dst;
1515                                 }
1516                         }
1517                 }
1518         }
1519
1520         return DMCACHE_NOTFOUND;
1521 }
1522
1523 static int psys_map_index_on_dm(DerivedMesh *dm, int from, int index, int index_dmcache, const float fw[4], float UNUSED(foffset), int *mapindex, float mapfw[4])
1524 {
1525         if (index < 0)
1526                 return 0;
1527
1528         if (dm->deformedOnly || index_dmcache == DMCACHE_ISCHILD) {
1529                 /* for meshes that are either only deformed or for child particles, the
1530                  * index and fw do not require any mapping, so we can directly use it */
1531                 if (from == PART_FROM_VERT) {
1532                         if (index >= dm->getNumVerts(dm))
1533                                 return 0;
1534
1535                         *mapindex = index;
1536                 }
1537                 else { /* FROM_FACE/FROM_VOLUME */
1538                         if (index >= dm->getNumTessFaces(dm))
1539                                 return 0;
1540
1541                         *mapindex = index;
1542                         copy_v4_v4(mapfw, fw);
1543                 }
1544         }
1545         else {
1546                 /* for other meshes that have been modified, we try to map the particle
1547                  * to their new location, which means a different index, and for faces
1548                  * also a new face interpolation weights */
1549                 if (from == PART_FROM_VERT) {
1550                         if (index_dmcache == DMCACHE_NOTFOUND || index_dmcache > dm->getNumVerts(dm))
1551                                 return 0;
1552
1553                         *mapindex = index_dmcache;
1554                 }
1555                 else { /* FROM_FACE/FROM_VOLUME */
1556                            /* find a face on the derived mesh that uses this face */
1557                         MFace *mface;
1558                         OrigSpaceFace *osface;
1559                         int i;
1560
1561                         i = index_dmcache;
1562
1563                         if (i == DMCACHE_NOTFOUND || i >= dm->getNumTessFaces(dm))
1564                                 return 0;
1565
1566                         *mapindex = i;
1567
1568                         /* modify the original weights to become
1569                          * weights for the derived mesh face */
1570                         osface = dm->getTessFaceDataArray(dm, CD_ORIGSPACE);
1571                         mface = dm->getTessFaceData(dm, i, CD_MFACE);
1572
1573                         if (osface == NULL)
1574                                 mapfw[0] = mapfw[1] = mapfw[2] = mapfw[3] = 0.0f;
1575                         else
1576                                 psys_origspace_to_w(&osface[i], mface->v4, fw, mapfw);
1577                 }
1578         }
1579
1580         return 1;
1581 }
1582
1583 /* interprets particle data to get a point on a mesh in object space */
1584 void psys_particle_on_dm(DerivedMesh *dm_final, int from, int index, int index_dmcache,
1585                          const float fw[4], float foffset, float vec[3], float nor[3], float utan[3], float vtan[3],
1586                          float orco[3], float ornor[3])
1587 {
1588         float tmpnor[3], mapfw[4];
1589         float (*orcodata)[3];
1590         int mapindex;
1591
1592         if (!psys_map_index_on_dm(dm_final, from, index, index_dmcache, fw, foffset, &mapindex, mapfw)) {
1593                 if (vec) { vec[0] = vec[1] = vec[2] = 0.0; }
1594                 if (nor) { nor[0] = nor[1] = 0.0; nor[2] = 1.0; }
1595                 if (orco) { orco[0] = orco[1] = orco[2] = 0.0; }
1596                 if (ornor) { ornor[0] = ornor[1] = 0.0; ornor[2] = 1.0; }
1597                 if (utan) { utan[0] = utan[1] = utan[2] = 0.0; }
1598                 if (vtan) { vtan[0] = vtan[1] = vtan[2] = 0.0; }
1599
1600                 return;
1601         }
1602
1603         orcodata = dm_final->getVertDataArray(dm_final, CD_ORCO);
1604
1605         if (from == PART_FROM_VERT) {
1606                 dm_final->getVertCo(dm_final, mapindex, vec);
1607
1608                 if (nor) {
1609                         dm_final->getVertNo(dm_final, mapindex, nor);
1610                         normalize_v3(nor);
1611                 }
1612
1613                 if (orco) {
1614                         if (orcodata) {
1615                                 copy_v3_v3(orco, orcodata[mapindex]);
1616                         }
1617                         else {
1618                                 copy_v3_v3(orco, vec);
1619                         }
1620                 }
1621
1622                 if (ornor) {
1623                         dm_final->getVertNo(dm_final, mapindex, ornor);
1624                         normalize_v3(ornor);
1625                 }
1626
1627                 if (utan && vtan) {
1628                         utan[0] = utan[1] = utan[2] = 0.0f;
1629                         vtan[0] = vtan[1] = vtan[2] = 0.0f;
1630                 }
1631         }
1632         else { /* PART_FROM_FACE / PART_FROM_VOLUME */
1633                 MFace *mface;
1634                 MTFace *mtface;
1635                 MVert *mvert;
1636
1637                 mface = dm_final->getTessFaceData(dm_final, mapindex, CD_MFACE);
1638                 mvert = dm_final->getVertDataArray(dm_final, CD_MVERT);
1639                 mtface = CustomData_get_layer(&dm_final->faceData, CD_MTFACE);
1640
1641                 if (mtface)
1642                         mtface += mapindex;
1643
1644                 if (from == PART_FROM_VOLUME) {
1645                         psys_interpolate_face(mvert, mface, mtface, orcodata, mapfw, vec, tmpnor, utan, vtan, orco, ornor);
1646                         if (nor)
1647                                 copy_v3_v3(nor, tmpnor);
1648
1649                         normalize_v3(tmpnor);  /* XXX Why not normalize tmpnor before copying it into nor??? -- mont29 */
1650                         mul_v3_fl(tmpnor, -foffset);
1651                         add_v3_v3(vec, tmpnor);
1652                 }
1653                 else
1654                         psys_interpolate_face(mvert, mface, mtface, orcodata, mapfw, vec, nor, utan, vtan, orco, ornor);
1655         }
1656 }
1657
1658 float psys_particle_value_from_verts(DerivedMesh *dm, short from, ParticleData *pa, float *values)
1659 {
1660         float mapfw[4];
1661         int mapindex;
1662
1663         if (!psys_map_index_on_dm(dm, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, &mapindex, mapfw))
1664                 return 0.0f;
1665
1666         return psys_interpolate_value_from_verts(dm, from, mapindex, mapfw, values);
1667 }
1668
1669 ParticleSystemModifierData *psys_get_modifier(Object *ob, ParticleSystem *psys)
1670 {
1671         ModifierData *md;
1672         ParticleSystemModifierData *psmd;
1673
1674         for (md = ob->modifiers.first; md; md = md->next) {
1675                 if (md->type == eModifierType_ParticleSystem) {
1676                         psmd = (ParticleSystemModifierData *) md;
1677                         if (psmd->psys == psys) {
1678                                 return psmd;
1679                         }
1680                 }
1681         }
1682         return NULL;
1683 }
1684 /************************************************/
1685 /*                      Particles on a shape                            */
1686 /************************************************/
1687 /* ready for future use */
1688 static void psys_particle_on_shape(int UNUSED(distr), int UNUSED(index),
1689                                    float *UNUSED(fuv), float vec[3], float nor[3], float utan[3], float vtan[3],
1690                                    float orco[3], float ornor[3])
1691 {
1692         /* TODO */
1693         float zerovec[3] = {0.0f, 0.0f, 0.0f};
1694         if (vec) {
1695                 copy_v3_v3(vec, zerovec);
1696         }
1697         if (nor) {
1698                 copy_v3_v3(nor, zerovec);
1699         }
1700         if (utan) {
1701                 copy_v3_v3(utan, zerovec);
1702         }
1703         if (vtan) {
1704                 copy_v3_v3(vtan, zerovec);
1705         }
1706         if (orco) {
1707                 copy_v3_v3(orco, zerovec);
1708         }
1709         if (ornor) {
1710                 copy_v3_v3(ornor, zerovec);
1711         }
1712 }
1713 /************************************************/
1714 /*                      Particles on emitter                            */
1715 /************************************************/
1716
1717 CustomDataMask psys_emitter_customdata_mask(ParticleSystem *psys)
1718 {
1719         CustomDataMask dataMask = 0;
1720         MTex *mtex;
1721         int i;
1722
1723         if (!psys->part)
1724                 return 0;
1725
1726         for (i = 0; i < MAX_MTEX; i++) {
1727                 mtex = psys->part->mtex[i];
1728                 if (mtex && mtex->mapto && (mtex->texco & TEXCO_UV))
1729                         dataMask |= CD_MASK_MTFACE;
1730         }
1731
1732         if (psys->part->tanfac != 0.0f)
1733                 dataMask |= CD_MASK_MTFACE;
1734
1735         /* ask for vertexgroups if we need them */
1736         for (i = 0; i < PSYS_TOT_VG; i++) {
1737                 if (psys->vgroup[i]) {
1738                         dataMask |= CD_MASK_MDEFORMVERT;
1739                         break;
1740                 }
1741         }
1742
1743         /* particles only need this if they are after a non deform modifier, and
1744          * the modifier stack will only create them in that case. */
1745         dataMask |= CD_MASK_ORIGSPACE_MLOOP | CD_MASK_ORIGINDEX;
1746
1747         dataMask |= CD_MASK_ORCO;
1748
1749         return dataMask;
1750 }
1751
1752 void psys_particle_on_emitter(ParticleSystemModifierData *psmd, int from, int index, int index_dmcache,
1753                               float fuv[4], float foffset, float vec[3], float nor[3], float utan[3], float vtan[3],
1754                               float orco[3], float ornor[3])
1755 {
1756         if (psmd && psmd->dm_final) {
1757                 if (psmd->psys->part->distr == PART_DISTR_GRID && psmd->psys->part->from != PART_FROM_VERT) {
1758                         if (vec)
1759                                 copy_v3_v3(vec, fuv);
1760
1761                         if (orco)
1762                                 copy_v3_v3(orco, fuv);
1763                         return;
1764                 }
1765                 /* we cant use the num_dmcache */
1766                 psys_particle_on_dm(psmd->dm_final, from, index, index_dmcache, fuv, foffset, vec, nor, utan, vtan, orco, ornor);
1767         }
1768         else
1769                 psys_particle_on_shape(from, index, fuv, vec, nor, utan, vtan, orco, ornor);
1770
1771 }
1772 /************************************************/
1773 /*                      Path Cache                                                      */
1774 /************************************************/
1775
1776 extern void do_kink(ParticleKey *state, const float par_co[3], const float par_vel[3], const float par_rot[4], float time, float freq, float shape, float amplitude, float flat,
1777                     short type, short axis, float obmat[4][4], int smooth_start);
1778 extern float do_clump(ParticleKey *state, const float par_co[3], float time, const float orco_offset[3], float clumpfac, float clumppow, float pa_clump,
1779                       bool use_clump_noise, float clump_noise_size, CurveMapping *clumpcurve);
1780
1781 void precalc_guides(ParticleSimulationData *sim, ListBase *effectors)
1782 {
1783         EffectedPoint point;
1784         ParticleKey state;
1785         EffectorData efd;
1786         EffectorCache *eff;
1787         ParticleSystem *psys = sim->psys;
1788         EffectorWeights *weights = sim->psys->part->effector_weights;
1789         GuideEffectorData *data;
1790         PARTICLE_P;
1791
1792         if (!effectors)
1793                 return;
1794
1795         LOOP_PARTICLES {
1796                 psys_particle_on_emitter(sim->psmd, sim->psys->part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, state.co, 0, 0, 0, 0, 0);
1797
1798                 mul_m4_v3(sim->ob->obmat, state.co);
1799                 mul_mat3_m4_v3(sim->ob->obmat, state.vel);
1800
1801                 pd_point_from_particle(sim, pa, &state, &point);
1802
1803                 for (eff = effectors->first; eff; eff = eff->next) {
1804                         if (eff->pd->forcefield != PFIELD_GUIDE)
1805                                 continue;
1806
1807                         if (!eff->guide_data)
1808                                 eff->guide_data = MEM_callocN(sizeof(GuideEffectorData) * psys->totpart, "GuideEffectorData");
1809
1810                         data = eff->guide_data + p;
1811
1812                         sub_v3_v3v3(efd.vec_to_point, state.co, eff->guide_loc);
1813                         copy_v3_v3(efd.nor, eff->guide_dir);
1814                         efd.distance = len_v3(efd.vec_to_point);
1815
1816                         copy_v3_v3(data->vec_to_point, efd.vec_to_point);
1817                         data->strength = effector_falloff(eff, &efd, &point, weights);
1818                 }
1819         }
1820 }
1821
1822 int do_guides(ParticleSettings *part, ListBase *effectors, ParticleKey *state, int index, float time)
1823 {
1824         CurveMapping *clumpcurve = (part->child_flag & PART_CHILD_USE_CLUMP_CURVE) ? part->clumpcurve : NULL;
1825         CurveMapping *roughcurve = (part->child_flag & PART_CHILD_USE_ROUGH_CURVE) ? part->roughcurve : NULL;
1826         EffectorCache *eff;
1827         PartDeflect *pd;
1828         Curve *cu;
1829         GuideEffectorData *data;
1830
1831         float effect[3] = {0.0f, 0.0f, 0.0f}, veffect[3] = {0.0f, 0.0f, 0.0f};
1832         float guidevec[4], guidedir[3], rot2[4], temp[3];
1833         float guidetime, radius, weight, angle, totstrength = 0.0f;
1834         float vec_to_point[3];
1835
1836         if (effectors) for (eff = effectors->first; eff; eff = eff->next) {
1837                 pd = eff->pd;
1838
1839                 if (pd->forcefield != PFIELD_GUIDE)
1840                         continue;
1841
1842                 data = eff->guide_data + index;
1843
1844                 if (data->strength <= 0.0f)
1845                         continue;
1846
1847                 guidetime = time / (1.0f - pd->free_end);
1848
1849                 if (guidetime > 1.0f)
1850                         continue;
1851
1852                 cu = (Curve *)eff->ob->data;
1853
1854                 if (pd->flag & PFIELD_GUIDE_PATH_ADD) {
1855                         if (where_on_path(eff->ob, data->strength * guidetime, guidevec, guidedir, NULL, &radius, &weight) == 0)
1856                                 return 0;
1857                 }
1858                 else {
1859                         if (where_on_path(eff->ob, guidetime, guidevec, guidedir, NULL, &radius, &weight) == 0)
1860                                 return 0;
1861                 }
1862
1863                 mul_m4_v3(eff->ob->obmat, guidevec);
1864                 mul_mat3_m4_v3(eff->ob->obmat, guidedir);
1865
1866                 normalize_v3(guidedir);
1867
1868                 copy_v3_v3(vec_to_point, data->vec_to_point);
1869
1870                 if (guidetime != 0.0f) {
1871                         /* curve direction */
1872                         cross_v3_v3v3(temp, eff->guide_dir, guidedir);
1873                         angle = dot_v3v3(eff->guide_dir, guidedir) / (len_v3(eff->guide_dir));
1874                         angle = saacos(angle);
1875                         axis_angle_to_quat(rot2, temp, angle);
1876                         mul_qt_v3(rot2, vec_to_point);
1877
1878                         /* curve tilt */
1879                         axis_angle_to_quat(rot2, guidedir, guidevec[3] - eff->guide_loc[3]);
1880                         mul_qt_v3(rot2, vec_to_point);
1881                 }
1882
1883                 /* curve taper */
1884                 if (cu->taperobj)
1885                         mul_v3_fl(vec_to_point, BKE_displist_calc_taper(eff->scene, cu->taperobj, (int)(data->strength * guidetime * 100.0f), 100));
1886
1887                 else { /* curve size*/
1888                         if (cu->flag & CU_PATH_RADIUS) {
1889                                 mul_v3_fl(vec_to_point, radius);
1890                         }
1891                 }
1892
1893                 if (clumpcurve)
1894                         curvemapping_changed_all(clumpcurve);
1895                 if (roughcurve)
1896                         curvemapping_changed_all(roughcurve);
1897
1898                 {
1899                         ParticleKey key;
1900                         float par_co[3] = {0.0f, 0.0f, 0.0f};
1901                         float par_vel[3] = {0.0f, 0.0f, 0.0f};
1902                         float par_rot[4] = {1.0f, 0.0f, 0.0f, 0.0f};
1903                         float orco_offset[3] = {0.0f, 0.0f, 0.0f};
1904
1905                         copy_v3_v3(key.co, vec_to_point);
1906                         do_kink(&key, par_co, par_vel, par_rot, guidetime, pd->kink_freq, pd->kink_shape, pd->kink_amp, 0.f, pd->kink, pd->kink_axis, 0, 0);
1907                         do_clump(&key, par_co, guidetime, orco_offset, pd->clump_fac, pd->clump_pow, 1.0f,
1908                                  part->child_flag & PART_CHILD_USE_CLUMP_NOISE, part->clump_noise_size, clumpcurve);
1909                         copy_v3_v3(vec_to_point, key.co);
1910                 }
1911
1912                 add_v3_v3(vec_to_point, guidevec);
1913
1914                 //sub_v3_v3v3(pa_loc, pa_loc, pa_zero);
1915                 madd_v3_v3fl(effect, vec_to_point, data->strength);
1916                 madd_v3_v3fl(veffect, guidedir, data->strength);
1917                 totstrength += data->strength;
1918
1919                 if (pd->flag & PFIELD_GUIDE_PATH_WEIGHT)
1920                         totstrength *= weight;
1921         }
1922
1923         if (totstrength != 0.0f) {
1924                 if (totstrength > 1.0f)
1925                         mul_v3_fl(effect, 1.0f / totstrength);
1926                 CLAMP(totstrength, 0.0f, 1.0f);
1927                 //add_v3_v3(effect, pa_zero);
1928                 interp_v3_v3v3(state->co, state->co, effect, totstrength);
1929
1930                 normalize_v3(veffect);
1931                 mul_v3_fl(veffect, len_v3(state->vel));
1932                 copy_v3_v3(state->vel, veffect);
1933                 return 1;
1934         }
1935         return 0;
1936 }
1937
1938 static void do_path_effectors(ParticleSimulationData *sim, int i, ParticleCacheKey *ca, int k, int steps, float *UNUSED(rootco), float effector, float UNUSED(dfra), float UNUSED(cfra), float *length, float *vec)
1939 {
1940         float force[3] = {0.0f, 0.0f, 0.0f};
1941         ParticleKey eff_key;
1942         EffectedPoint epoint;
1943
1944         /* Don't apply effectors for dynamic hair, otherwise the effectors don't get applied twice. */
1945         if (sim->psys->flag & PSYS_HAIR_DYNAMICS)
1946                 return;
1947
1948         copy_v3_v3(eff_key.co, (ca - 1)->co);
1949         copy_v3_v3(eff_key.vel, (ca - 1)->vel);
1950         copy_qt_qt(eff_key.rot, (ca - 1)->rot);
1951
1952         pd_point_from_particle(sim, sim->psys->particles + i, &eff_key, &epoint);
1953         pdDoEffectors(sim->psys->effectors, sim->colliders, sim->psys->part->effector_weights, &epoint, force, NULL);
1954
1955         mul_v3_fl(force, effector * powf((float)k / (float)steps, 100.0f * sim->psys->part->eff_hair) / (float)steps);
1956
1957         add_v3_v3(force, vec);
1958
1959         normalize_v3(force);
1960
1961         if (k < steps)
1962                 sub_v3_v3v3(vec, (ca + 1)->co, ca->co);
1963
1964         madd_v3_v3v3fl(ca->co, (ca - 1)->co, force, *length);
1965
1966         if (k < steps)
1967                 *length = len_v3(vec);
1968 }
1969 static void offset_child(ChildParticle *cpa, ParticleKey *par, float *par_rot, ParticleKey *child, float flat, float radius)
1970 {
1971         copy_v3_v3(child->co, cpa->fuv);
1972         mul_v3_fl(child->co, radius);
1973
1974         child->co[0] *= flat;
1975
1976         copy_v3_v3(child->vel, par->vel);
1977
1978         if (par_rot) {
1979                 mul_qt_v3(par_rot, child->co);
1980                 copy_qt_qt(child->rot, par_rot);
1981         }
1982         else
1983                 unit_qt(child->rot);
1984
1985         add_v3_v3(child->co, par->co);
1986 }
1987 float *psys_cache_vgroup(DerivedMesh *dm, ParticleSystem *psys, int vgroup)
1988 {
1989         float *vg = 0;
1990
1991         if (vgroup < 0) {
1992                 /* hair dynamics pinning vgroup */
1993
1994         }
1995         else if (psys->vgroup[vgroup]) {
1996                 MDeformVert *dvert = dm->getVertDataArray(dm, CD_MDEFORMVERT);
1997                 if (dvert) {
1998                         int totvert = dm->getNumVerts(dm), i;
1999                         vg = MEM_callocN(sizeof(float) * totvert, "vg_cache");
2000                         if (psys->vg_neg & (1 << vgroup)) {
2001                                 for (i = 0; i < totvert; i++)
2002                                         vg[i] = 1.0f - defvert_find_weight(&dvert[i], psys->vgroup[vgroup] - 1);
2003                         }
2004                         else {
2005                                 for (i = 0; i < totvert; i++)
2006                                         vg[i] =  defvert_find_weight(&dvert[i], psys->vgroup[vgroup] - 1);
2007                         }
2008                 }
2009         }
2010         return vg;
2011 }
2012 void psys_find_parents(ParticleSimulationData *sim)
2013 {
2014         ParticleSystem *psys = sim->psys;
2015         ParticleSettings *part = sim->psys->part;
2016         KDTree *tree;
2017         ChildParticle *cpa;
2018         ParticleTexture ptex;
2019         int p, totparent, totchild = sim->psys->totchild;
2020         float co[3], orco[3];
2021         int from = PART_FROM_FACE;
2022         totparent = (int)(totchild * part->parents * 0.3f);
2023
2024         if ((sim->psys->renderdata || G.is_rendering) && part->child_nbr && part->ren_child_nbr)
2025                 totparent *= (float)part->child_nbr / (float)part->ren_child_nbr;
2026
2027         /* hard limit, workaround for it being ignored above */
2028         if (sim->psys->totpart < totparent) {
2029                 totparent = sim->psys->totpart;
2030         }
2031
2032         tree = BLI_kdtree_new(totparent);
2033
2034         for (p = 0, cpa = sim->psys->child; p < totparent; p++, cpa++) {
2035                 psys_particle_on_emitter(sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco, 0);
2036
2037                 /* Check if particle doesn't exist because of texture influence. Insert only existing particles into kdtree. */
2038                 get_cpa_texture(sim->psmd->dm_final, psys, part, psys->particles + cpa->pa[0], p, cpa->num, cpa->fuv, orco, &ptex, PAMAP_DENS | PAMAP_CHILD, psys->cfra);
2039
2040                 if (ptex.exist >= psys_frand(psys, p + 24)) {
2041                         BLI_kdtree_insert(tree, p, orco);
2042                 }
2043         }
2044
2045         BLI_kdtree_balance(tree);
2046
2047         for (; p < totchild; p++, cpa++) {
2048                 psys_particle_on_emitter(sim->psmd, from, cpa->num, DMCACHE_ISCHILD, cpa->fuv, cpa->foffset, co, 0, 0, 0, orco, 0);
2049                 cpa->parent = BLI_kdtree_find_nearest(tree, orco, NULL);
2050         }
2051
2052         BLI_kdtree_free(tree);
2053 }
2054
2055 static bool psys_thread_context_init_path(ParticleThreadContext *ctx, ParticleSimulationData *sim, Scene *scene, float cfra, int editupdate)
2056 {
2057         ParticleSystem *psys = sim->psys;
2058         ParticleSettings *part = psys->part;
2059         int totparent = 0, between = 0;
2060         int segments = 1 << part->draw_step;
2061         int totchild = psys->totchild;
2062
2063         psys_thread_context_init(ctx, sim);
2064
2065         /*---start figuring out what is actually wanted---*/
2066         if (psys_in_edit_mode(scene, psys)) {
2067                 ParticleEditSettings *pset = &scene->toolsettings->particle;
2068
2069                 if ((psys->renderdata == 0 && G.is_rendering == 0) && (psys->edit == NULL || pset->flag & PE_DRAW_PART) == 0)
2070                         totchild = 0;
2071
2072                 segments = 1 << pset->draw_step;
2073         }
2074
2075         if (totchild && part->childtype == PART_CHILD_FACES) {
2076                 totparent = (int)(totchild * part->parents * 0.3f);
2077
2078                 if ((psys->renderdata || G.is_rendering) && part->child_nbr && part->ren_child_nbr)
2079                         totparent *= (float)part->child_nbr / (float)part->ren_child_nbr;
2080
2081                 /* part->parents could still be 0 so we can't test with totparent */
2082                 between = 1;
2083         }
2084
2085         if (psys->renderdata || G.is_rendering)
2086                 segments = 1 << part->ren_step;
2087         else {
2088                 totchild = (int)((float)totchild * (float)part->disp / 100.0f);
2089                 totparent = MIN2(totparent, totchild);
2090         }
2091
2092         if (totchild == 0)
2093                 return false;
2094
2095         /* fill context values */
2096         ctx->between = between;
2097         ctx->segments = segments;
2098         if (ELEM(part->kink, PART_KINK_SPIRAL))
2099                 ctx->extra_segments = max_ii(part->kink_extra_steps, 1);
2100         else
2101                 ctx->extra_segments = 0;
2102         ctx->totchild = totchild;
2103         ctx->totparent = totparent;
2104         ctx->parent_pass = 0;
2105         ctx->cfra = cfra;
2106         ctx->editupdate = editupdate;
2107
2108         psys->lattice_deform_data = psys_create_lattice_deform_data(&ctx->sim);
2109
2110         /* cache all relevant vertex groups if they exist */
2111         ctx->vg_length = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_LENGTH);
2112         ctx->vg_clump = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_CLUMP);
2113         ctx->vg_kink = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_KINK);
2114         ctx->vg_rough1 = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_ROUGH1);
2115         ctx->vg_rough2 = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_ROUGH2);
2116         ctx->vg_roughe = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_ROUGHE);
2117         if (psys->part->flag & PART_CHILD_EFFECT)
2118                 ctx->vg_effector = psys_cache_vgroup(ctx->dm, psys, PSYS_VG_EFFECTOR);
2119
2120         /* prepare curvemapping tables */
2121         if ((part->child_flag & PART_CHILD_USE_CLUMP_CURVE) && part->clumpcurve) {
2122                 ctx->clumpcurve = curvemapping_copy(part->clumpcurve);
2123                 curvemapping_changed_all(ctx->clumpcurve);
2124         }
2125         else {
2126                 ctx->clumpcurve = NULL;
2127         }
2128         if ((part->child_flag & PART_CHILD_USE_ROUGH_CURVE) && part->roughcurve) {
2129                 ctx->roughcurve = curvemapping_copy(part->roughcurve);
2130                 curvemapping_changed_all(ctx->roughcurve);
2131         }
2132         else {
2133                 ctx->roughcurve = NULL;
2134         }
2135
2136         return true;
2137 }
2138
2139 static void psys_task_init_path(ParticleTask *task, ParticleSimulationData *sim)
2140 {
2141         /* init random number generator */
2142         int seed = 31415926 + sim->psys->seed;
2143
2144         task->rng_path = BLI_rng_new(seed);
2145 }
2146
2147 /* note: this function must be thread safe, except for branching! */
2148 static void psys_thread_create_path(ParticleTask *task, struct ChildParticle *cpa, ParticleCacheKey *child_keys, int i)
2149 {
2150         ParticleThreadContext *ctx = task->ctx;
2151         Object *ob = ctx->sim.ob;
2152         ParticleSystem *psys = ctx->sim.psys;
2153         ParticleSettings *part = psys->part;
2154         ParticleCacheKey **cache = psys->childcache;
2155         ParticleCacheKey **pcache = psys_in_edit_mode(ctx->sim.scene, psys) && psys->edit ? psys->edit->pathcache : psys->pathcache;
2156         ParticleCacheKey *child, *key[4];
2157         ParticleTexture ptex;
2158         float *cpa_fuv = 0, *par_rot = 0, rot[4];
2159         float orco[3], ornor[3], hairmat[4][4], dvec[3], off1[4][3], off2[4][3];
2160         float eff_length, eff_vec[3], weight[4];
2161         int k, cpa_num;
2162         short cpa_from;
2163
2164         if (!pcache)
2165                 return;
2166
2167         if (ctx->between) {
2168                 ParticleData *pa = psys->particles + cpa->pa[0];
2169                 int w, needupdate;
2170                 float foffset, wsum = 0.f;
2171                 float co[3];
2172                 float p_min = part->parting_min;
2173                 float p_max = part->parting_max;
2174                 /* Virtual parents don't work nicely with parting. */
2175                 float p_fac = part->parents > 0.f ? 0.f : part->parting_fac;
2176
2177                 if (ctx->editupdate) {
2178                         needupdate = 0;
2179                         w = 0;
2180                         while (w < 4 && cpa->pa[w] >= 0) {
2181                                 if (psys->edit->points[cpa->pa[w]].flag & PEP_EDIT_RECALC) {
2182                                         needupdate = 1;
2183                                         break;
2184                                 }
2185                                 w++;
2186                         }
2187
2188                         if (!needupdate)
2189                                 return;
2190                         else
2191                                 memset(child_keys, 0, sizeof(*child_keys) * (ctx->segments + 1));
2192                 }
2193
2194                 /* get parent paths */
2195                 for (w = 0; w < 4; w++) {
2196                         if (cpa->pa[w] >= 0) {
2197                                 key[w] = pcache[cpa->pa[w]];
2198                                 weight[w] = cpa->w[w];
2199                         }
2200                         else {
2201                                 key[w] = pcache[0];
2202                                 weight[w] = 0.f;
2203                         }
2204                 }
2205
2206                 /* modify weights to create parting */
2207                 if (p_fac > 0.f) {
2208                         for (w = 0; w < 4; w++) {
2209                                 if (w && weight[w] > 0.f) {
2210                                         float d;
2211                                         if (part->flag & PART_CHILD_LONG_HAIR) {
2212                                                 /* For long hair use tip distance/root distance as parting factor instead of root to tip angle. */
2213                                                 float d1 = len_v3v3(key[0]->co, key[w]->co);
2214                                                 float d2 = len_v3v3((key[0] + key[0]->segments - 1)->co, (key[w] + key[w]->segments - 1)->co);
2215
2216                                                 d = d1 > 0.f ? d2 / d1 - 1.f : 10000.f;
2217                                         }
2218                                         else {
2219                                                 float v1[3], v2[3];
2220                                                 sub_v3_v3v3(v1, (key[0] + key[0]->segments - 1)->co, key[0]->co);
2221                                                 sub_v3_v3v3(v2, (key[w] + key[w]->segments - 1)->co, key[w]->co);
2222                                                 normalize_v3(v1);
2223                                                 normalize_v3(v2);
2224
2225                                                 d = RAD2DEGF(saacos(dot_v3v3(v1, v2)));
2226                                         }
2227
2228                                         if (p_max > p_min)
2229                                                 d = (d - p_min) / (p_max - p_min);
2230                                         else
2231                                                 d = (d - p_min) <= 0.f ? 0.f : 1.f;
2232
2233                                         CLAMP(d, 0.f, 1.f);
2234
2235                                         if (d > 0.f)
2236                                                 weight[w] *= (1.f - d);
2237                                 }
2238                                 wsum += weight[w];
2239                         }
2240                         for (w = 0; w < 4; w++)
2241                                 weight[w] /= wsum;
2242
2243                         interp_v4_v4v4(weight, cpa->w, weight, p_fac);
2244                 }
2245
2246                 /* get the original coordinates (orco) for texture usage */
2247                 cpa_num = cpa->num;
2248
2249                 foffset = cpa->foffset;
2250                 cpa_fuv = cpa->fuv;
2251                 cpa_from = PART_FROM_FACE;
2252
2253                 psys_particle_on_emitter(ctx->sim.psmd, cpa_from, cpa_num, DMCACHE_ISCHILD, cpa->fuv, foffset, co, ornor, 0, 0, orco, 0);
2254
2255                 mul_m4_v3(ob->obmat, co);
2256
2257                 for (w = 0; w < 4; w++)
2258                         sub_v3_v3v3(off1[w], co, key[w]->co);
2259
2260                 psys_mat_hair_to_global(ob, ctx->sim.psmd->dm_final, psys->part->from, pa, hairmat);
2261         }
2262         else {
2263                 ParticleData *pa = psys->particles + cpa->parent;
2264                 float co[3];
2265                 if (ctx->editupdate) {
2266                         if (!(psys->edit->points[cpa->parent].flag & PEP_EDIT_RECALC))
2267                                 return;
2268
2269                         memset(child_keys, 0, sizeof(*child_keys) * (ctx->segments + 1));
2270                 }
2271
2272                 /* get the parent path */
2273                 key[0] = pcache[cpa->parent];
2274
2275                 /* get the original coordinates (orco) for texture usage */
2276                 cpa_from = part->from;
2277                 cpa_num = pa->num;
2278                 /* XXX hack to avoid messed up particle num and subsequent crash (#40733) */
2279                 if (cpa_num > ctx->sim.psmd->dm_final->getNumTessFaces(ctx->sim.psmd->dm_final))
2280                         cpa_num = 0;
2281                 cpa_fuv = pa->fuv;
2282
2283                 psys_particle_on_emitter(ctx->sim.psmd, cpa_from, cpa_num, DMCACHE_ISCHILD, cpa_fuv, pa->foffset, co, ornor, 0, 0, orco, 0);
2284
2285                 psys_mat_hair_to_global(ob, ctx->sim.psmd->dm_final, psys->part->from, pa, hairmat);
2286         }
2287
2288         child_keys->segments = ctx->segments;
2289
2290         /* get different child parameters from textures & vgroups */
2291         get_child_modifier_parameters(part, ctx, cpa, cpa_from, cpa_num, cpa_fuv, orco, &ptex);
2292
2293         if (ptex.exist < psys_frand(psys, i + 24)) {
2294                 child_keys->segments = -1;
2295                 return;
2296         }
2297
2298         /* create the child path */
2299         for (k = 0, child = child_keys; k <= ctx->segments; k++, child++) {
2300                 if (ctx->between) {
2301                         int w = 0;
2302
2303                         zero_v3(child->co);
2304                         zero_v3(child->vel);
2305                         unit_qt(child->rot);
2306
2307                         for (w = 0; w < 4; w++) {
2308                                 copy_v3_v3(off2[w], off1[w]);
2309
2310                                 if (part->flag & PART_CHILD_LONG_HAIR) {
2311                                         /* Use parent rotation (in addition to emission location) to determine child offset. */
2312                                         if (k)
2313                                                 mul_qt_v3((key[w] + k)->rot, off2[w]);
2314
2315                                         /* Fade the effect of rotation for even lengths in the end */
2316                                         project_v3_v3v3(dvec, off2[w], (key[w] + k)->vel);
2317                                         madd_v3_v3fl(off2[w], dvec, -(float)k / (float)ctx->segments);
2318                                 }
2319
2320                                 add_v3_v3(off2[w], (key[w] + k)->co);
2321                         }
2322
2323                         /* child position is the weighted sum of parent positions */
2324                         interp_v3_v3v3v3v3(child->co, off2[0], off2[1], off2[2], off2[3], weight);
2325                         interp_v3_v3v3v3v3(child->vel, (key[0] + k)->vel, (key[1] + k)->vel, (key[2] + k)->vel, (key[3] + k)->vel, weight);
2326
2327                         copy_qt_qt(child->rot, (key[0] + k)->rot);
2328                 }
2329                 else {
2330                         if (k) {
2331                                 mul_qt_qtqt(rot, (key[0] + k)->rot, key[0]->rot);
2332                                 par_rot = rot;
2333                         }
2334                         else {
2335                                 par_rot = key[0]->rot;
2336                         }
2337                         /* offset the child from the parent position */
2338                         offset_child(cpa, (ParticleKey *)(key[0] + k), par_rot, (ParticleKey *)child, part->childflat, part->childrad);
2339                 }
2340
2341                 child->time = (float)k / (float)ctx->segments;
2342         }
2343
2344         /* apply effectors */
2345         if (part->flag & PART_CHILD_EFFECT) {
2346                 for (k = 0, child = child_keys; k <= ctx->segments; k++, child++) {
2347                         if (k) {
2348                                 do_path_effectors(&ctx->sim, cpa->pa[0], child, k, ctx->segments, child_keys->co, ptex.effector, 0.0f, ctx->cfra, &eff_length, eff_vec);
2349                         }
2350                         else {
2351                                 sub_v3_v3v3(eff_vec, (child + 1)->co, child->co);
2352                                 eff_length = len_v3(eff_vec);
2353                         }
2354                 }
2355         }
2356
2357         {
2358                 ParticleData *pa = NULL;
2359                 ParticleCacheKey *par = NULL;
2360                 float par_co[3];
2361                 float par_orco[3];
2362
2363                 if (ctx->totparent) {
2364                         if (i >= ctx->totparent) {
2365                                 pa = &psys->particles[cpa->parent];
2366                                 /* this is now threadsafe, virtual parents are calculated before rest of children */
2367                                 BLI_assert(cpa->parent < psys->totchildcache);
2368                                 par = cache[cpa->parent];
2369                         }
2370                 }
2371                 else if (cpa->parent >= 0) {
2372                         pa = &psys->particles[cpa->parent];
2373                         par = pcache[cpa->parent];
2374
2375                         /* If particle is unexisting, try to pick a viable parent from particles used for interpolation. */
2376                         for (k = 0; k < 4 && pa && (pa->flag & PARS_UNEXIST); k++) {
2377                                 if (cpa->pa[k] >= 0) {
2378                                         pa = &psys->particles[cpa->pa[k]];
2379                                         par = pcache[cpa->pa[k]];
2380                                 }
2381                         }
2382
2383                         if (pa->flag & PARS_UNEXIST) pa = NULL;
2384                 }
2385
2386                 if (pa) {
2387                         ListBase modifiers;
2388                         BLI_listbase_clear(&modifiers);
2389
2390                         psys_particle_on_emitter(ctx->sim.psmd, part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset,
2391                                                  par_co, NULL, NULL, NULL, par_orco, NULL);
2392
2393                         psys_apply_child_modifiers(ctx, &modifiers, cpa, &ptex, orco, ornor, hairmat, child_keys, par, par_orco);
2394                 }
2395                 else
2396                         zero_v3(par_orco);
2397         }
2398
2399         /* Hide virtual parents */
2400         if (i < ctx->totparent)
2401                 child_keys->segments = -1;
2402 }
2403
2404 static void exec_child_path_cache(TaskPool * __restrict UNUSED(pool), void *taskdata, int UNUSED(threadid))
2405 {
2406         ParticleTask *task = taskdata;
2407         ParticleThreadContext *ctx = task->ctx;
2408         ParticleSystem *psys = ctx->sim.psys;
2409         ParticleCacheKey **cache = psys->childcache;
2410         ChildParticle *cpa;
2411         int i;
2412
2413         cpa = psys->child + task->begin;
2414         for (i = task->begin; i < task->end; ++i, ++cpa) {
2415                 BLI_assert(i < psys->totchildcache);
2416                 psys_thread_create_path(task, cpa, cache[i], i);
2417         }
2418 }
2419
2420 void psys_cache_child_paths(ParticleSimulationData *sim, float cfra, int editupdate)
2421 {
2422         TaskScheduler *task_scheduler;
2423         TaskPool *task_pool;
2424         ParticleThreadContext ctx;
2425         ParticleTask *tasks_parent, *tasks_child;
2426         int numtasks_parent, numtasks_child;
2427         int i, totchild, totparent;
2428
2429         if (sim->psys->flag & PSYS_GLOBAL_HAIR)
2430                 return;
2431
2432         /* create a task pool for child path tasks */
2433         if (!psys_thread_context_init_path(&ctx, sim, sim->scene, cfra, editupdate))
2434                 return;
2435
2436         task_scheduler = BLI_task_scheduler_get();
2437         task_pool = BLI_task_pool_create(task_scheduler, &ctx);
2438         totchild = ctx.totchild;
2439         totparent = ctx.totparent;
2440
2441         if (editupdate && sim->psys->childcache && totchild == sim->psys->totchildcache) {
2442                 ; /* just overwrite the existing cache */
2443         }
2444         else {
2445                 /* clear out old and create new empty path cache */
2446                 free_child_path_cache(sim->psys);
2447
2448                 sim->psys->childcache = psys_alloc_path_cache_buffers(&sim->psys->childcachebufs, totchild, ctx.segments + ctx.extra_segments + 1);
2449                 sim->psys->totchildcache = totchild;
2450         }
2451
2452         /* cache parent paths */
2453         ctx.parent_pass = 1;
2454         psys_tasks_create(&ctx, 0, totparent, &tasks_parent, &numtasks_parent);
2455         for (i = 0; i < numtasks_parent; ++i) {
2456                 ParticleTask *task = &tasks_parent[i];
2457
2458                 psys_task_init_path(task, sim);
2459                 BLI_task_pool_push(task_pool, exec_child_path_cache, task, false, TASK_PRIORITY_LOW);
2460         }
2461         BLI_task_pool_work_and_wait(task_pool);
2462
2463         /* cache child paths */
2464         ctx.parent_pass = 0;
2465         psys_tasks_create(&ctx, totparent, totchild, &tasks_child, &numtasks_child);
2466         for (i = 0; i < numtasks_child; ++i) {
2467                 ParticleTask *task = &tasks_child[i];
2468
2469                 psys_task_init_path(task, sim);
2470                 BLI_task_pool_push(task_pool, exec_child_path_cache, task, false, TASK_PRIORITY_LOW);
2471         }
2472         BLI_task_pool_work_and_wait(task_pool);
2473
2474         BLI_task_pool_free(task_pool);
2475
2476         psys_tasks_free(tasks_parent, numtasks_parent);
2477         psys_tasks_free(tasks_child, numtasks_child);
2478
2479         psys_thread_context_free(&ctx);
2480 }
2481
2482 /* figure out incremental rotations along path starting from unit quat */
2483 static void cache_key_incremental_rotation(ParticleCacheKey *key0, ParticleCacheKey *key1, ParticleCacheKey *key2, float *prev_tangent, int i)
2484 {
2485         float cosangle, angle, tangent[3], normal[3], q[4];
2486
2487         switch (i) {
2488                 case 0:
2489                         /* start from second key */
2490                         break;
2491                 case 1:
2492                         /* calculate initial tangent for incremental rotations */
2493                         sub_v3_v3v3(prev_tangent, key0->co, key1->co);
2494                         normalize_v3(prev_tangent);
2495                         unit_qt(key1->rot);
2496                         break;
2497                 default:
2498                         sub_v3_v3v3(tangent, key0->co, key1->co);
2499                         normalize_v3(tangent);
2500
2501                         cosangle = dot_v3v3(tangent, prev_tangent);
2502
2503                         /* note we do the comparison on cosangle instead of
2504                          * angle, since floating point accuracy makes it give
2505                          * different results across platforms */
2506                         if (cosangle > 0.999999f) {
2507                                 copy_v4_v4(key1->rot, key2->rot);
2508                         }
2509                         else {
2510                                 angle = saacos(cosangle);
2511                                 cross_v3_v3v3(normal, prev_tangent, tangent);
2512                                 axis_angle_to_quat(q, normal, angle);
2513                                 mul_qt_qtqt(key1->rot, q, key2->rot);
2514                         }
2515
2516                         copy_v3_v3(prev_tangent, tangent);
2517         }
2518 }
2519
2520 /**
2521  * Calculates paths ready for drawing/rendering
2522  * - Useful for making use of opengl vertex arrays for super fast strand drawing.
2523  * - Makes child strands possible and creates them too into the cache.
2524  * - Cached path data is also used to determine cut position for the editmode tool. */
2525 void psys_cache_paths(ParticleSimulationData *sim, float cfra)
2526 {
2527         PARTICLE_PSMD;
2528         ParticleEditSettings *pset = &sim->scene->toolsettings->particle;
2529         ParticleSystem *psys = sim->psys;
2530         ParticleSettings *part = psys->part;
2531         ParticleCacheKey *ca, **cache;
2532
2533         DerivedMesh *hair_dm = (psys->part->type == PART_HAIR && psys->flag & PSYS_HAIR_DYNAMICS) ? psys->hair_out_dm : NULL;
2534
2535         ParticleKey result;
2536
2537         Material *ma;
2538         ParticleInterpolationData pind;
2539         ParticleTexture ptex;
2540
2541         PARTICLE_P;
2542
2543         float birthtime = 0.0, dietime = 0.0;
2544         float t, time = 0.0, dfra = 1.0 /* , frs_sec = sim->scene->r.frs_sec*/ /*UNUSED*/;
2545         float col[4] = {0.5f, 0.5f, 0.5f, 1.0f};
2546         float prev_tangent[3] = {0.0f, 0.0f, 0.0f}, hairmat[4][4];
2547         float rotmat[3][3];
2548         int k;
2549         int segments = (int)pow(2.0, (double)((psys->renderdata || G.is_rendering) ? part->ren_step : part->draw_step));
2550         int totpart = psys->totpart;
2551         float length, vec[3];
2552         float *vg_effector = NULL;
2553         float *vg_length = NULL, pa_length = 1.0f;
2554         int keyed, baked;
2555
2556         /* we don't have anything valid to create paths from so let's quit here */
2557         if ((psys->flag & PSYS_HAIR_DONE || psys->flag & PSYS_KEYED || psys->pointcache) == 0)
2558                 return;
2559
2560         if (psys_in_edit_mode(sim->scene, psys))
2561                 if (psys->renderdata == 0 && (psys->edit == NULL || pset->flag & PE_DRAW_PART) == 0)
2562                         return;
2563
2564         keyed = psys->flag & PSYS_KEYED;
2565         baked = psys->pointcache->mem_cache.first && psys->part->type != PART_HAIR;
2566
2567         /* clear out old and create new empty path cache */
2568         psys_free_path_cache(psys, psys->edit);
2569         cache = psys->pathcache = psys_alloc_path_cache_buffers(&psys->pathcachebufs, totpart, segments + 1);
2570
2571         psys->lattice_deform_data = psys_create_lattice_deform_data(sim);
2572         ma = give_current_material(sim->ob, psys->part->omat);
2573         if (ma && (psys->part->draw_col == PART_DRAW_COL_MAT))
2574                 copy_v3_v3(col, &ma->r);
2575
2576         if ((psys->flag & PSYS_GLOBAL_HAIR) == 0) {
2577                 if ((psys->part->flag & PART_CHILD_EFFECT) == 0)
2578                         vg_effector = psys_cache_vgroup(psmd->dm_final, psys, PSYS_VG_EFFECTOR);
2579
2580                 if (!psys->totchild)
2581                         vg_length = psys_cache_vgroup(psmd->dm_final, psys, PSYS_VG_LENGTH);
2582         }
2583
2584         /* ensure we have tessfaces to be used for mapping */
2585         if (part->from != PART_FROM_VERT) {
2586                 DM_ensure_tessface(psmd->dm_final);
2587         }
2588
2589         /*---first main loop: create all actual particles' paths---*/
2590         LOOP_PARTICLES {
2591                 if (!psys->totchild) {
2592                         psys_get_texture(sim, pa, &ptex, PAMAP_LENGTH, 0.f);
2593                         pa_length = ptex.length * (1.0f - part->randlength * psys_frand(psys, psys->seed + p));
2594                         if (vg_length)
2595                                 pa_length *= psys_particle_value_from_verts(psmd->dm_final, part->from, pa, vg_length);
2596                 }
2597
2598                 pind.keyed = keyed;
2599                 pind.cache = baked ? psys->pointcache : NULL;
2600                 pind.epoint = NULL;
2601                 pind.bspline = (psys->part->flag & PART_HAIR_BSPLINE);
2602                 pind.dm = hair_dm;
2603
2604                 memset(cache[p], 0, sizeof(*cache[p]) * (segments + 1));
2605
2606                 cache[p]->segments = segments;
2607
2608                 /*--get the first data points--*/
2609                 init_particle_interpolation(sim->ob, sim->psys, pa, &pind);
2610
2611                 /* hairmat is needed for for non-hair particle too so we get proper rotations */
2612                 psys_mat_hair_to_global(sim->ob, psmd->dm_final, psys->part->from, pa, hairmat);
2613                 copy_v3_v3(rotmat[0], hairmat[2]);
2614                 copy_v3_v3(rotmat[1], hairmat[1]);
2615                 copy_v3_v3(rotmat[2], hairmat[0]);
2616
2617                 if (part->draw & PART_ABS_PATH_TIME) {
2618                         birthtime = MAX2(pind.birthtime, part->path_start);
2619                         dietime = MIN2(pind.dietime, part->path_end);
2620                 }
2621                 else {
2622                         float tb = pind.birthtime;
2623                         birthtime = tb + part->path_start * (pind.dietime - tb);
2624                         dietime = tb + part->path_end * (pind.dietime - tb);
2625                 }
2626
2627                 if (birthtime >= dietime) {
2628                         cache[p]->segments = -1;
2629                         continue;
2630                 }
2631
2632                 dietime = birthtime + pa_length * (dietime - birthtime);
2633
2634                 /*--interpolate actual path from data points--*/
2635                 for (k = 0, ca = cache[p]; k <= segments; k++, ca++) {
2636                         time = (float)k / (float)segments;
2637                         t = birthtime + time * (dietime - birthtime);
2638                         result.time = -t;
2639                         do_particle_interpolation(psys, p, pa, t, &pind, &result);
2640                         copy_v3_v3(ca->co, result.co);
2641
2642                         /* dynamic hair is in object space */
2643                         /* keyed and baked are already in global space */
2644                         if (hair_dm)
2645                                 mul_m4_v3(sim->ob->obmat, ca->co);
2646                         else if (!keyed && !baked && !(psys->flag & PSYS_GLOBAL_HAIR))
2647                                 mul_m4_v3(hairmat, ca->co);
2648
2649                         copy_v3_v3(ca->col, col);
2650                 }
2651
2652                 if (part->type == PART_HAIR) {
2653                         HairKey *hkey;
2654
2655                         for (k = 0, hkey = pa->hair; k < pa->totkey; ++k, ++hkey) {
2656                                 mul_v3_m4v3(hkey->world_co, hairmat, hkey->co);
2657                         }
2658                 }
2659
2660                 /*--modify paths and calculate rotation & velocity--*/
2661
2662                 if (!(psys->flag & PSYS_GLOBAL_HAIR)) {
2663                         /* apply effectors */
2664                         if ((psys->part->flag & PART_CHILD_EFFECT) == 0) {
2665                                 float effector = 1.0f;
2666                                 if (vg_effector)
2667                                         effector *= psys_particle_value_from_verts(psmd->dm_final, psys->part->from, pa, vg_effector);
2668
2669                                 sub_v3_v3v3(vec, (cache[p] + 1)->co, cache[p]->co);
2670                                 length = len_v3(vec);
2671
2672                                 for (k = 1, ca = cache[p] + 1; k <= segments; k++, ca++)
2673                                         do_path_effectors(sim, p, ca, k, segments, cache[p]->co, effector, dfra, cfra, &length, vec);
2674                         }
2675
2676                         /* apply guide curves to path data */
2677                         if (sim->psys->effectors && (psys->part->flag & PART_CHILD_EFFECT) == 0) {
2678                                 for (k = 0, ca = cache[p]; k <= segments; k++, ca++)
2679                                         /* ca is safe to cast, since only co and vel are used */
2680                                         do_guides(sim->psys->part, sim->psys->effectors, (ParticleKey *)ca, p, (float)k / (float)segments);
2681                         }
2682
2683                         /* lattices have to be calculated separately to avoid mixups between effector calculations */
2684                         if (psys->lattice_deform_data) {
2685                                 for (k = 0, ca = cache[p]; k <= segments; k++, ca++)
2686                                         calc_latt_deform(psys->lattice_deform_data, ca->co, 1.0f);
2687                         }
2688                 }
2689
2690                 /* finally do rotation & velocity */
2691                 for (k = 1, ca = cache[p] + 1; k <= segments; k++, ca++) {
2692                         cache_key_incremental_rotation(ca, ca - 1, ca - 2, prev_tangent, k);
2693
2694                         if (k == segments)
2695                                 copy_qt_qt(ca->rot, (ca - 1)->rot);
2696
2697                         /* set velocity */
2698                         sub_v3_v3v3(ca->vel, ca->co, (ca - 1)->co);
2699
2700                         if (k == 1)
2701                                 copy_v3_v3((ca - 1)->vel, ca->vel);
2702
2703                         ca->time = (float)k / (float)segments;
2704                 }
2705                 /* First rotation is based on emitting face orientation.
2706                  * This is way better than having flipping rotations resulting
2707                  * from using a global axis as a rotation pole (vec_to_quat()).
2708                  * It's not an ideal solution though since it disregards the
2709                  * initial tangent, but taking that in to account will allow
2710                  * the possibility of flipping again. -jahka
2711                  */
2712                 mat3_to_quat_is_ok(cache[p]->rot, rotmat);
2713         }
2714
2715         psys->totcached = totpart;
2716
2717         if (psys->lattice_deform_data) {
2718                 end_latt_deform(psys->lattice_deform_data);
2719                 psys->lattice_deform_data = NULL;
2720         }
2721
2722         if (vg_effector)
2723                 MEM_freeN(vg_effector);
2724
2725         if (vg_length)
2726                 MEM_freeN(vg_length);
2727 }
2728 void psys_cache_edit_paths(Scene *scene, Object *ob, PTCacheEdit *edit, float cfra)
2729 {
2730         ParticleCacheKey *ca, **cache = edit->pathcache;
2731         ParticleEditSettings *pset = &scene->toolsettings->particle;
2732
2733         PTCacheEditPoint *point = NULL;
2734         PTCacheEditKey *ekey = NULL;
2735
2736         ParticleSystem *psys = edit->psys;
2737         ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
2738         ParticleData *pa = psys ? psys->particles : NULL;
2739
2740         ParticleInterpolationData pind;
2741         ParticleKey result;
2742
2743         float birthtime = 0.0f, dietime = 0.0f;
2744         float t, time = 0.0f, keytime = 0.0f /*, frs_sec */;
2745         float hairmat[4][4], rotmat[3][3], prev_tangent[3] = {0.0f, 0.0f, 0.0f};
2746         int k, i;
2747         int segments = 1 << pset->draw_step;
2748         int totpart = edit->totpoint, recalc_set = 0;
2749         float sel_col[3];
2750         float nosel_col[3];
2751
2752         segments = MAX2(segments, 4);
2753
2754         if (!cache || edit->totpoint != edit->totcached) {
2755                 /* clear out old and create new empty path cache */
2756                 psys_free_path_cache(edit->psys, edit);
2757                 cache = edit->pathcache = psys_alloc_path_cache_buffers(&edit->pathcachebufs, totpart, segments + 1);
2758
2759                 /* set flag for update (child particles check this too) */
2760                 for (i = 0, point = edit->points; i < totpart; i++, point++)
2761                         point->flag |= PEP_EDIT_RECALC;
2762                 recalc_set = 1;
2763         }
2764
2765         /* frs_sec = (psys || edit->pid.flag & PTCACHE_VEL_PER_SEC) ? 25.0f : 1.0f; */ /* UNUSED */
2766
2767         if (pset->brushtype == PE_BRUSH_WEIGHT) {
2768                 ; /* use weight painting colors now... */
2769         }
2770         else {
2771                 sel_col[0] = (float)edit->sel_col[0] / 255.0f;
2772                 sel_col[1] = (float)edit->sel_col[1] / 255.0f;
2773                 sel_col[2] = (float)edit->sel_col[2] / 255.0f;
2774                 nosel_col[0] = (float)edit->nosel_col[0] / 255.0f;
2775                 nosel_col[1] = (float)edit->nosel_col[1] / 255.0f;
2776                 nosel_col[2] = (float)edit->nosel_col[2] / 255.0f;
2777         }
2778
2779         /*---first main loop: create all actual particles' paths---*/
2780         for (i = 0, point = edit->points; i < totpart; i++, pa += pa ? 1 : 0, point++) {
2781                 if (edit->totcached && !(point->flag & PEP_EDIT_RECALC))
2782                         continue;
2783
2784                 if (point->totkey == 0)
2785                         continue;
2786
2787                 ekey = point->keys;
2788
2789                 pind.keyed = 0;
2790                 pind.cache = NULL;
2791                 pind.epoint = point;
2792                 pind.bspline = psys ? (psys->part->flag & PART_HAIR_BSPLINE) : 0;
2793                 pind.dm = NULL;
2794
2795
2796                 /* should init_particle_interpolation set this ? */
2797                 if (pset->brushtype == PE_BRUSH_WEIGHT) {
2798                         pind.hkey[0] = NULL;
2799                         /* pa != NULL since the weight brush is only available for hair */
2800                         pind.hkey[1] = pa->hair;
2801                 }
2802
2803
2804                 memset(cache[i], 0, sizeof(*cache[i]) * (segments + 1));
2805
2806                 cache[i]->segments = segments;
2807
2808                 /*--get the first data points--*/
2809                 init_particle_interpolation(ob, psys, pa, &pind);
2810
2811                 if (psys) {
2812                         psys_mat_hair_to_global(ob, psmd->dm_final, psys->part->from, pa, hairmat);
2813                         copy_v3_v3(rotmat[0], hairmat[2]);
2814                         copy_v3_v3(rotmat[1], hairmat[1]);
2815                         copy_v3_v3(rotmat[2], hairmat[0]);
2816                 }
2817
2818                 birthtime = pind.birthtime;
2819                 dietime = pind.dietime;
2820
2821                 if (birthtime >= dietime) {
2822                         cache[i]->segments = -1;
2823                         continue;
2824                 }
2825
2826                 /*--interpolate actual path from data points--*/
2827                 for (k = 0, ca = cache[i]; k <= segments; k++, ca++) {
2828                         time = (float)k / (float)segments;
2829                         t = birthtime + time * (dietime - birthtime);
2830                         result.time = -t;
2831                         do_particle_interpolation(psys, i, pa, t, &pind, &result);
2832                         copy_v3_v3(ca->co, result.co);
2833
2834                         /* non-hair points are already in global space */
2835                         if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
2836                                 mul_m4_v3(hairmat, ca->co);
2837
2838                                 if (k) {
2839                                         cache_key_incremental_rotation(ca, ca - 1, ca - 2, prev_tangent, k);
2840
2841                                         if (k == segments)
2842                                                 copy_qt_qt(ca->rot, (ca - 1)->rot);
2843
2844                                         /* set velocity */
2845                                         sub_v3_v3v3(ca->vel, ca->co, (ca - 1)->co);
2846
2847                                         if (k == 1)
2848                                                 copy_v3_v3((ca - 1)->vel, ca->vel);
2849                                 }
2850                         }
2851                         else {
2852                                 ca->vel[0] = ca->vel[1] = 0.0f;
2853                                 ca->vel[2] = 1.0f;
2854                         }
2855
2856                         /* selection coloring in edit mode */
2857                         if (pset->brushtype == PE_BRUSH_WEIGHT) {
2858                                 float t2;
2859
2860                                 if (k == 0) {
2861                                         weight_to_rgb(ca->col, pind.hkey[1]->weight);
2862                                 }
2863                                 else {
2864                                         float w1[3], w2[3];
2865                                         keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
2866
2867                                         weight_to_rgb(w1, pind.hkey[0]->weight);
2868                                         weight_to_rgb(w2, pind.hkey[1]->weight);
2869
2870                                         interp_v3_v3v3(ca->col, w1, w2, keytime);
2871                                 }
2872
2873                                 /* at the moment this is only used for weight painting.
2874                                  * will need to move out of this check if its used elsewhere. */
2875                                 t2 = birthtime + ((float)k / (float)segments) * (dietime - birthtime);
2876
2877                                 while (pind.hkey[1]->time < t2) pind.hkey[1]++;
2878                                 pind.hkey[0] = pind.hkey[1] - 1;
2879                         }
2880                         else {
2881                                 if ((ekey + (pind.ekey[0] - point->keys))->flag & PEK_SELECT) {
2882                                         if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
2883                                                 copy_v3_v3(ca->col, sel_col);
2884                                         }
2885                                         else {
2886                                                 keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
2887                                                 interp_v3_v3v3(ca->col, sel_col, nosel_col, keytime);
2888                                         }
2889                                 }
2890                                 else {
2891                                         if ((ekey + (pind.ekey[1] - point->keys))->flag & PEK_SELECT) {
2892                                                 keytime = (t - (*pind.ekey[0]->time)) / ((*pind.ekey[1]->time) - (*pind.ekey[0]->time));
2893                                                 interp_v3_v3v3(ca->col, nosel_col, sel_col, keytime);
2894                                         }
2895                                         else {
2896                                                 copy_v3_v3(ca->col, nosel_col);
2897                                         }
2898                                 }
2899                         }
2900
2901                         ca->time = t;
2902                 }
2903                 if (psys && !(psys->flag & PSYS_GLOBAL_HAIR)) {
2904                         /* First rotation is based on emitting face orientation.
2905                          * This is way better than having flipping rotations resulting
2906                          * from using a global axis as a rotation pole (vec_to_quat()).
2907                          * It's not an ideal solution though since it disregards the
2908                          * initial tangent, but taking that in to account will allow
2909                          * the possibility of flipping again. -jahka
2910                          */
2911                         mat3_to_quat_is_ok(cache[i]->rot, rotmat);
2912                 }
2913         }
2914
2915         edit->totcached = totpart;
2916
2917         if (psys) {
2918                 ParticleSimulationData sim = {0};
2919                 sim.scene = scene;
2920                 sim.ob = ob;
2921                 sim.psys = psys;
2922                 sim.psmd = psys_get_modifier(ob, psys);
2923
2924                 psys_cache_child_paths(&sim, cfra, 1);
2925         }
2926
2927         /* clear recalc flag if set here */
2928         if (recalc_set) {
2929                 for (i = 0, point = edit->points; i < totpart; i++, point++)
2930                         point->flag &= ~PEP_EDIT_RECALC;
2931         }
2932 }
2933 /************************************************/
2934 /*                      Particle Key handling                           */
2935 /************************************************/
2936 void copy_particle_key(ParticleKey *to, ParticleKey *from, int time)
2937 {
2938         if (time) {
2939                 memcpy(to, from, sizeof(ParticleKey));
2940         }
2941         else {
2942                 float to_time = to->time;
2943                 memcpy(to, from, sizeof(ParticleKey));
2944                 to->time = to_time;
2945         }
2946 }
2947 void psys_get_from_key(ParticleKey *key, float loc[3], float vel[3], float rot[4], float *time)
2948 {
2949         if (loc) copy_v3_v3(loc, key->co);
2950         if (vel) copy_v3_v3(vel, key->vel);
2951         if (rot) copy_qt_qt(rot, key->rot);
2952         if (time) *time = key->time;
2953 }
2954 /*-------changing particle keys from space to another-------*/
2955 #if 0
2956 static void key_from_object(Object *ob, ParticleKey *key)
2957 {
2958         float q[4];
2959
2960         add_v3_v3(key->vel, key->co);
2961
2962         mul_m4_v3(ob->obmat, key->co);
2963         mul_m4_v3(ob->obmat, key->vel);
2964         mat4_to_quat(q, ob->obmat);
2965
2966         sub_v3_v3v3(key->vel, key->vel, key->co);
2967         mul_qt_qtqt(key->rot, q, key->rot);
2968 }
2969 #endif
2970
2971 static void triatomat(float *v1, float *v2, float *v3, float (*uv)[2], float mat[4][4])
2972 {
2973         float det, w1, w2, d1[2], d2[2];
2974
2975         memset(mat, 0, sizeof(float) * 4 * 4);
2976         mat[3][3] = 1.0f;
2977
2978         /* first axis is the normal */
2979         normal_tri_v3(mat[2], v1, v2, v3);
2980
2981         /* second axis along (1, 0) in uv space */
2982         if (uv) {
2983                 d1[0] = uv[1][0] - uv[0][0];
2984                 d1[1] = uv[1][1] - uv[0][1];
2985                 d2[0] = uv[2][0] - uv[0][0];
2986                 d2[1] = uv[2][1] - uv[0][1];
2987
2988                 det = d2[0] * d1[1] - d2[1] * d1[0];
2989
2990                 if (det != 0.0f) {
2991                         det = 1.0f / det;
2992                         w1 = -d2[1] * det;
2993                         w2 = d1[1] * det;
2994
2995                         mat[1][0] = w1 * (v2[0] - v1[0]) + w2 * (v3[0] - v1[0]);
2996                         mat[1][1] = w1 * (v2[1] - v1[1]) + w2 * (v3[1] - v1[1]);
2997                         mat[1][2] = w1 * (v2[2] - v1[2]) + w2 * (v3[2] - v1[2]);
2998                         normalize_v3(mat[1]);
2999                 }
3000                 else
3001                         mat[1][0] = mat[1][1] = mat[1][2] = 0.0f;
3002         }
3003         else {
3004                 sub_v3_v3v3(mat[1], v2, v1);
3005                 normalize_v3(mat[1]);
3006         }
3007
3008         /* third as a cross product */
3009         cross_v3_v3v3(mat[0], mat[1], mat[2]);
3010 }
3011
3012 static void psys_face_mat(Object *ob, DerivedMesh *dm, ParticleData *pa, float mat[4][4], int orco)
3013 {
3014         float v[3][3];
3015         MFace *mface;
3016         OrigSpaceFace *osface;
3017         float (*orcodata)[3];
3018
3019         int i = (ELEM(pa->num_dmcache, DMCACHE_ISCHILD, DMCACHE_NOTFOUND)) ? pa->num : pa->num_dmcache;
3020         if (i == -1 || i >= dm->getNumTessFaces(dm)) { unit_m4(mat); return; }
3021
3022         mface = dm->getTessFaceData(dm, i, CD_MFACE);
3023         osface = dm->getTessFaceData(dm, i, CD_ORIGSPACE);
3024
3025         if (orco && (orcodata = dm->getVertDataArray(dm, CD_ORCO))) {
3026                 copy_v3_v3(v[0], orcodata[mface->v1]);
3027                 copy_v3_v3(v[1], orcodata[mface->v2]);
3028                 copy_v3_v3(v[2], orcodata[mface->v3]);
3029
3030                 /* ugly hack to use non-transformed orcos, since only those
3031                  * give symmetric results for mirroring in particle mode */
3032                 if (DM_get_vert_data_layer(dm, CD_ORIGINDEX))
3033                         BKE_mesh_orco_verts_transform(ob->data, v, 3, 1);
3034         }
3035         else {
3036                 dm->getVertCo(dm, mface->v1, v[0]);
3037                 dm->getVertCo(dm, mface->v2, v[1]);
3038                 dm->getVertCo(dm, mface->v3, v[2]);
3039         }
3040
3041         triatomat(v[0], v[1], v[2], (osface) ? osface->uv : NULL, mat);
3042 }
3043
3044 void psys_mat_hair_to_object(Object *UNUSED(ob), DerivedMesh *dm, short from, ParticleData *pa, float hairmat[4][4])
3045 {
3046         float vec[3];
3047
3048         /* can happen when called from a different object's modifier */
3049         if (!dm) {
3050                 unit_m4(hairmat);
3051                 return;
3052         }
3053
3054         psys_face_mat(0, dm, pa, hairmat, 0);
3055         psys_particle_on_dm(dm, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, vec, 0, 0, 0, 0, 0);
3056         copy_v3_v3(hairmat[3], vec);
3057 }
3058
3059 void psys_mat_hair_to_orco(Object *ob, DerivedMesh *dm, short from, ParticleData *pa, float hairmat[4][4])
3060 {
3061         float vec[3], orco[3];
3062
3063         psys_face_mat(ob, dm, pa, hairmat, 1);
3064         psys_particle_on_dm(dm, from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, vec, 0, 0, 0, orco, 0);
3065
3066         /* see psys_face_mat for why this function is called */
3067         if (DM_get_vert_data_layer(dm, CD_ORIGINDEX))
3068                 BKE_mesh_orco_verts_transform(ob->data, &orco, 1, 1);
3069         copy_v3_v3(hairmat[3], orco);
3070 }
3071
3072 void psys_vec_rot_to_face(DerivedMesh *dm, ParticleData *pa, float vec[3])
3073 {
3074         float mat[4][4];
3075
3076         psys_face_mat(0, dm, pa, mat, 0);
3077         transpose_m4(mat); /* cheap inverse for rotation matrix */
3078         mul_mat3_m4_v3(mat, vec);
3079 }
3080
3081 void psys_mat_hair_to_global(Object *ob, DerivedMesh *dm, short from, ParticleData *pa, float hairmat[4][4])
3082 {
3083         float facemat[4][4];
3084
3085         psys_mat_hair_to_object(ob, dm, from, pa, facemat);
3086
3087         mul_m4_m4m4(hairmat, ob->obmat, facemat);
3088 }
3089
3090 /************************************************/
3091 /*                      ParticleSettings handling                       */
3092 /************************************************/
3093 ModifierData *object_add_particle_system(Scene *scene, Object *ob, const char *name)
3094 {
3095         ParticleSystem *psys;
3096         ModifierData *md;
3097         ParticleSystemModifierData *psmd;
3098
3099         if (!ob || ob->type != OB_MESH)
3100                 return NULL;
3101
3102         psys = ob->particlesystem.first;
3103         for (; psys; psys = psys->next)
3104                 psys->flag &= ~PSYS_CURRENT;
3105
3106         psys = MEM_callocN(sizeof(ParticleSystem), "particle_system");
3107         psys->pointcache = BKE_ptcache_add(&psys->ptcaches);
3108         BLI_addtail(&ob->particlesystem, psys);
3109
3110         psys->part = psys_new_settings(DATA_("ParticleSettings"), NULL);
3111
3112         if (BLI_listbase_count_ex(&ob->particlesystem, 2) > 1)
3113                 BLI_snprintf(psys->name, sizeof(psys->name), DATA_("ParticleSystem %i"), BLI_listbase_count(&ob->particlesystem));
3114         else
3115                 BLI_strncpy(psys->name, DATA_("ParticleSystem"), sizeof(psys->name));
3116
3117         md = modifier_new(eModifierType_ParticleSystem);
3118
3119         if (name)
3120                 BLI_strncpy_utf8(md->name, name, sizeof(md->name));
3121         else
3122                 BLI_snprintf(md->name, sizeof(md->name), DATA_("ParticleSystem %i"), BLI_listbase_count(&ob->particlesystem));
3123         modifier_unique_name(&ob->modifiers, md);
3124
3125         psmd = (ParticleSystemModifierData *) md;
3126         psmd->psys = psys;
3127         BLI_addtail(&ob->modifiers, md);
3128