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