text: /*
   * This program is free software; you can redistribute it and/or
   * modify it under the terms of the GNU General Public License
   * as published by the Free Software Foundation; either version 2
   * of the License, or (at your option) any later version.
   *
   * This program is distributed in the hope that it will be useful,
   * but WITHOUT ANY WARRANTY; without even the implied warranty of
   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   * GNU General Public License for more details.
   *
   * You should have received a copy of the GNU General Public License
   * along with this program; if not, write to the Free Software Foundation,
   * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
   *
   * The Original Code is Copyright (C) 2007 by Janne Karhu.
   * All rights reserved.
   * Adaptive time step
   * Classical SPH
   * Copyright 2011-2012 AutoCRC
   */
  
  /** \file
   * \ingroup bke
   */
  
  #include <stddef.h>
  
  #include <math.h>
  #include <stdlib.h>
  #include <string.h>
  
  #include "MEM_guardedalloc.h"
  
  #include "DNA_anim_types.h"
  #include "DNA_boid_types.h"
  #include "DNA_curve_types.h"
  #include "DNA_listBase.h"
  #include "DNA_mesh_types.h"
  #include "DNA_meshdata_types.h"
  #include "DNA_modifier_types.h"
  #include "DNA_object_force_types.h"
  #include "DNA_object_types.h"
  #include "DNA_particle_types.h"
  #include "DNA_scene_types.h"
  #include "DNA_texture_types.h"
  
  #include "BLI_blenlib.h"
  #include "BLI_edgehash.h"
  #include "BLI_kdopbvh.h"
  #include "BLI_kdtree.h"
  #include "BLI_linklist.h"
  #include "BLI_math.h"
  #include "BLI_rand.h"
  #include "BLI_string_utils.h"
  #include "BLI_task.h"
  #include "BLI_threads.h"
  #include "BLI_utildefines.h"
  
  #include "BKE_animsys.h"
  #include "BKE_boids.h"
  #include "BKE_collision.h"
  #include "BKE_colortools.h"
  #include "BKE_effect.h"
  #include "BKE_lib_id.h"
  #include "BKE_lib_query.h"
  #include "BKE_particle.h"
  
  #include "BKE_bvhutils.h"
  #include "BKE_cloth.h"
  #include "BKE_collection.h"
  #include "BKE_lattice.h"
  #include "BKE_material.h"
  #include "BKE_mesh.h"
  #include "BKE_modifier.h"
  #include "BKE_object.h"
  #include "BKE_pointcache.h"
  #include "BKE_scene.h"
  
  #include "DEG_depsgraph.h"
  #include "DEG_depsgraph_physics.h"
  #include "DEG_depsgraph_query.h"
  
  #include "PIL_time.h"
  
  #include "RE_shader_ext.h"
  
  /* FLUID sim particle import */
  #ifdef WITH_FLUID
  #  include "DNA_fluid_types.h"
  #  include "manta_fluid_API.h"
  #endif  // WITH_FLUID
  
  static ThreadRWMutex psys_bvhtree_rwlock = BLI_RWLOCK_INITIALIZER;
  
  /************************************************/
  /*          Reacting to system events           */
  /************************************************/
  
  static int particles_are_dynamic(ParticleSystem *psys)
  {
    if (psys->pointcache->flag & PTCACHE_BAKED) {
      return 0;
    }
  
    if (psys->part->type == PART_HAIR) {
      return psys->flag & PSYS_HAIR_DYNAMICS;
    }
  
    return ELEM(psys->part->phystype, PART_PHYS_NEWTON, PART_PHYS_BOIDS, PART_PHYS_FLUID);
  }
  
  float psys_get_current_display_percentage(ParticleSystem *psys, const bool use_render_params)
  {
    ParticleSettings *part = psys->part;
  
    if ((use_render_params &&
         !particles_are_dynamic(psys)) ||          /* non-dynamic particles can be rendered fully */
        (part->child_nbr && part->childtype) ||    /* display percentage applies to children */
        (psys->pointcache->flag & PTCACHE_BAKING)) /* baking is always done with full amount */
    {
      return 1.0f;
    }
  
    return psys->part->disp / 100.0f;
  }
  
  static int tot_particles(ParticleSystem *psys, PTCacheID *pid)
  {
    if (pid && psys->pointcache->flag & PTCACHE_EXTERNAL) {
      return pid->cache->totpoint;
    }
    if (psys->part->distr == PART_DISTR_GRID && psys->part->from != PART_FROM_VERT) {
      return psys->part->grid_res * psys->part->grid_res * psys->part->grid_res - psys->totunexist;
    }
  
    return psys->part->totpart - psys->totunexist;
  }
  
  void psys_reset(ParticleSystem *psys, int mode)
  {
    PARTICLE_P;
  
    if (ELEM(mode, PSYS_RESET_ALL, PSYS_RESET_DEPSGRAPH)) {
      if (mode == PSYS_RESET_ALL || !(psys->flag & PSYS_EDITED)) {
        /* don't free if not absolutely necessary */
        if (psys->totpart != tot_particles(psys, NULL)) {
          psys_free_particles(psys);
          psys->totpart = 0;
        }
  
        psys->totkeyed = 0;
        psys->flag &= ~(PSYS_HAIR_DONE | PSYS_KEYED);
  
        if (psys->edit && psys->free_edit) {
          psys->free_edit(psys->edit);
          psys->edit = NULL;
          psys->free_edit = NULL;
        }
      }
    }
    else if (mode == PSYS_RESET_CACHE_MISS) {
      /* set all particles to be skipped */
      LOOP_PARTICLES
      {
        pa->flag |= PARS_NO_DISP;
      }
    }
  
    /* reset children */
    if (psys->child) {
      MEM_freeN(psys->child);
      psys->child = NULL;
    }
  
    psys->totchild = 0;
  
    /* reset path cache */
    psys_free_path_cache(psys, psys->edit);
  
    /* reset point cache */
    BKE_ptcache_invalidate(psys->pointcache);
  
    if (psys->fluid_springs) {
      MEM_freeN(psys->fluid_springs);
      psys->fluid_springs = NULL;
    }
  
    psys->tot_fluidsprings = psys->alloc_fluidsprings = 0;
  }
  
  void psys_unique_name(Object *object, ParticleSystem *psys, const char *defname)
  {
    BLI_uniquename(&object->particlesystem,
                   psys,
                   defname,
                   '.',
                   offsetof(ParticleSystem, name),
                   sizeof(psys->name));
  }
  
  static void realloc_particles(ParticleSimulationData *sim, int new_totpart)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    ParticleData *newpars = NULL;
    BoidParticle *newboids = NULL;
    PARTICLE_P;
    int totpart, totsaved = 0;
  
    if (new_totpart < 0) {
      if ((part->distr == PART_DISTR_GRID) && (part->from != PART_FROM_VERT)) {
        totpart = part->grid_res;
        totpart *= totpart * totpart;
      }
      else {
        totpart = part->totpart;
      }
    }
    else {
      totpart = new_totpart;
    }
  
    if (totpart != psys->totpart) {
      if (psys->edit && psys->free_edit) {
        psys->free_edit(psys->edit);
        psys->edit = NULL;
        psys->free_edit = NULL;
      }
  
      if (totpart) {
        newpars = MEM_callocN(totpart * sizeof(ParticleData), "particles");
        if (newpars == NULL) {
          return;
        }
  
        if (psys->part->phystype == PART_PHYS_BOIDS) {
          newboids = MEM_callocN(totpart * sizeof(BoidParticle), "boid particles");
  
          if (newboids == NULL) {
            /* allocation error! */
            if (newpars) {
              MEM_freeN(newpars);
            }
            return;
          }
        }
      }
  
      if (psys->particles) {
        totsaved = MIN2(psys->totpart, totpart);
        /*save old pars*/
        if (totsaved) {
          memcpy(newpars, psys->particles, totsaved * sizeof(ParticleData));
  
          if (psys->particles->boid) {
            memcpy(newboids, psys->particles->boid, totsaved * sizeof(BoidParticle));
          }
        }
  
        if (psys->particles->keys) {
          MEM_freeN(psys->particles->keys);
        }
  
        if (psys->particles->boid) {
          MEM_freeN(psys->particles->boid);
        }
  
        for (p = 0, pa = newpars; p < totsaved; p++, pa++) {
          if (pa->keys) {
            pa->keys = NULL;
            pa->totkey = 0;
          }
        }
  
        for (p = totsaved, pa = psys->particles + totsaved; p < psys->totpart; p++, pa++) {
          if (pa->hair) {
            MEM_freeN(pa->hair);
          }
        }
  
        MEM_freeN(psys->particles);
        psys_free_pdd(psys);
      }
  
      psys->particles = newpars;
      psys->totpart = totpart;
  
      if (newboids) {
        LOOP_PARTICLES
        {
          pa->boid = newboids++;
        }
      }
    }
  
    if (psys->child) {
      MEM_freeN(psys->child);
      psys->child = NULL;
      psys->totchild = 0;
    }
  }
  
  int psys_get_child_number(Scene *scene, ParticleSystem *psys, const bool use_render_params)
  {
    int nbr;
  
    if (!psys->part->childtype) {
      return 0;
    }
  
    if (use_render_params) {
      nbr = psys->part->ren_child_nbr;
    }
    else {
      nbr = psys->part->child_nbr;
    }
  
    return get_render_child_particle_number(&scene->r, nbr, use_render_params);
  }
  
  int psys_get_tot_child(Scene *scene, ParticleSystem *psys, const bool use_render_params)
  {
    return psys->totpart * psys_get_child_number(scene, psys, use_render_params);
  }
  
  /************************************************/
  /*          Distribution                        */
  /************************************************/
  
  void psys_calc_dmcache(Object *ob, Mesh *mesh_final, Mesh *mesh_original, ParticleSystem *psys)
  {
    /* use for building derived mesh mapping info:
     *
     * node: the allocated links - total derived mesh element count
     * nodearray: the array of nodes aligned with the base mesh's elements, so
     *            each original elements can reference its derived elements
     */
    Mesh *me = (Mesh *)ob->data;
    bool use_modifier_stack = psys->part->use_modifier_stack;
    PARTICLE_P;
  
    /* CACHE LOCATIONS */
    if (!mesh_final->runtime.deformed_only) {
      /* Will use later to speed up subsurf/evaluated mesh. */
      LinkNode *node, *nodedmelem, **nodearray;
      int totdmelem, totelem, i, *origindex, *origindex_poly = NULL;
  
      if (psys->part->from == PART_FROM_VERT) {
        totdmelem = mesh_final->totvert;
  
        if (use_modifier_stack) {
          totelem = totdmelem;
          origindex = NULL;
        }
        else {
          totelem = me->totvert;
          origindex = CustomData_get_layer(&mesh_final->vdata, CD_ORIGINDEX);
        }
      }
      else { /* FROM_FACE/FROM_VOLUME */
        totdmelem = mesh_final->totface;
  
        if (use_modifier_stack) {
          totelem = totdmelem;
          origindex = NULL;
          origindex_poly = NULL;
        }
        else {
          totelem = mesh_original->totface;
          origindex = CustomData_get_layer(&mesh_final->fdata, CD_ORIGINDEX);
  
          /* for face lookups we need the poly origindex too */
          origindex_poly = CustomData_get_layer(&mesh_final->pdata, CD_ORIGINDEX);
          if (origindex_poly == NULL) {
            origindex = NULL;
          }
        }
      }
  
      nodedmelem = MEM_callocN(sizeof(LinkNode) * totdmelem, "psys node elems");
      nodearray = MEM_callocN(sizeof(LinkNode *) * totelem, "psys node array");
  
      for (i = 0, node = nodedmelem; i < totdmelem; i++, node++) {
        int origindex_final;
        node->link = POINTER_FROM_INT(i);
  
        /* may be vertex or face origindex */
        if (use_modifier_stack) {
          origindex_final = i;
        }
        else {
          origindex_final = origindex ? origindex[i] : ORIGINDEX_NONE;
  
          /* if we have a poly source, do an index lookup */
          if (origindex_poly && origindex_final != ORIGINDEX_NONE) {
            origindex_final = origindex_poly[origindex_final];
          }
        }
  
        if (origindex_final != ORIGINDEX_NONE && origindex_final < totelem) {
          if (nodearray[origindex_final]) {
            /* prepend */
            node->next = nodearray[origindex_final];
            nodearray[origindex_final] = node;
          }
          else {
            nodearray[origindex_final] = node;
          }
        }
      }
  
      /* cache the verts/faces! */
      LOOP_PARTICLES
      {
        if (pa->num < 0) {
          pa->num_dmcache = DMCACHE_NOTFOUND;
          continue;
        }
  
        if (use_modifier_stack) {
          if (pa->num < totelem) {
            pa->num_dmcache = DMCACHE_ISCHILD;
          }
          else {
            pa->num_dmcache = DMCACHE_NOTFOUND;
          }
        }
        else {
          if (psys->part->from == PART_FROM_VERT) {
            if (pa->num < totelem && nodearray[pa->num]) {
              pa->num_dmcache = POINTER_AS_INT(nodearray[pa->num]->link);
            }
            else {
              pa->num_dmcache = DMCACHE_NOTFOUND;
            }
          }
          else { /* FROM_FACE/FROM_VOLUME */
            pa->num_dmcache = psys_particle_dm_face_lookup(
                mesh_final, mesh_original, pa->num, pa->fuv, nodearray);
          }
        }
      }
  
      MEM_freeN(nodearray);
      MEM_freeN(nodedmelem);
    }
    else {
      /* TODO PARTICLE, make the following line unnecessary, each function
       * should know to use the num or num_dmcache, set the num_dmcache to
       * an invalid value, just in case */
  
      LOOP_PARTICLES
      {
        pa->num_dmcache = DMCACHE_NOTFOUND;
      }
    }
  }
  
  /* threaded child particle distribution and path caching */
  void psys_thread_context_init(ParticleThreadContext *ctx, ParticleSimulationData *sim)
  {
    memset(ctx, 0, sizeof(ParticleThreadContext));
    ctx->sim = *sim;
    ctx->mesh = ctx->sim.psmd->mesh_final;
    ctx->ma = BKE_object_material_get(sim->ob, sim->psys->part->omat);
  }
  
  void psys_tasks_create(ParticleThreadContext *ctx,
                         int startpart,
                         int endpart,
                         ParticleTask **r_tasks,
                         int *r_numtasks)
  {
    ParticleTask *tasks;
    int numtasks = min_ii(BLI_system_thread_count() * 4, endpart - startpart);
    float particles_per_task = (float)(endpart - startpart) / (float)numtasks, p, pnext;
    int i;
  
    tasks = MEM_callocN(sizeof(ParticleTask) * numtasks, "ParticleThread");
    *r_numtasks = numtasks;
    *r_tasks = tasks;
  
    p = (float)startpart;
    for (i = 0; i < numtasks; i++, p = pnext) {
      pnext = p + particles_per_task;
  
      tasks[i].ctx = ctx;
      tasks[i].begin = (int)p;
      tasks[i].end = min_ii((int)pnext, endpart);
    }
  }
  
  void psys_tasks_free(ParticleTask *tasks, int numtasks)
  {
    int i;
  
    /* threads */
    for (i = 0; i < numtasks; i++) {
      if (tasks[i].rng) {
        BLI_rng_free(tasks[i].rng);
      }
      if (tasks[i].rng_path) {
        BLI_rng_free(tasks[i].rng_path);
      }
    }
  
    MEM_freeN(tasks);
  }
  
  void psys_thread_context_free(ParticleThreadContext *ctx)
  {
    /* path caching */
    if (ctx->vg_length) {
      MEM_freeN(ctx->vg_length);
    }
    if (ctx->vg_clump) {
      MEM_freeN(ctx->vg_clump);
    }
    if (ctx->vg_kink) {
      MEM_freeN(ctx->vg_kink);
    }
    if (ctx->vg_rough1) {
      MEM_freeN(ctx->vg_rough1);
    }
    if (ctx->vg_rough2) {
      MEM_freeN(ctx->vg_rough2);
    }
    if (ctx->vg_roughe) {
      MEM_freeN(ctx->vg_roughe);
    }
    if (ctx->vg_twist) {
      MEM_freeN(ctx->vg_twist);
    }
  
    if (ctx->sim.psys->lattice_deform_data) {
      BKE_lattice_deform_data_destroy(ctx->sim.psys->lattice_deform_data);
      ctx->sim.psys->lattice_deform_data = NULL;
    }
  
    /* distribution */
    if (ctx->jit) {
      MEM_freeN(ctx->jit);
    }
    if (ctx->jitoff) {
      MEM_freeN(ctx->jitoff);
    }
    if (ctx->weight) {
      MEM_freeN(ctx->weight);
    }
    if (ctx->index) {
      MEM_freeN(ctx->index);
    }
    if (ctx->seams) {
      MEM_freeN(ctx->seams);
    }
    // if (ctx->vertpart) MEM_freeN(ctx->vertpart);
    BLI_kdtree_3d_free(ctx->tree);
  
    if (ctx->clumpcurve != NULL) {
      BKE_curvemapping_free(ctx->clumpcurve);
    }
    if (ctx->roughcurve != NULL) {
      BKE_curvemapping_free(ctx->roughcurve);
    }
    if (ctx->twistcurve != NULL) {
      BKE_curvemapping_free(ctx->twistcurve);
    }
  }
  
  static void init_particle_texture(ParticleSimulationData *sim, ParticleData *pa, int p)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    ParticleTexture ptex;
  
    psys_get_texture(sim, pa, &ptex, PAMAP_INIT, 0.f);
  
    switch (part->type) {
      case PART_EMITTER:
        if (ptex.exist < psys_frand(psys, p + 125)) {
          pa->flag |= PARS_UNEXIST;
        }
        pa->time = part->sta + (part->end - part->sta) * ptex.time;
        break;
      case PART_HAIR:
        if (ptex.exist < psys_frand(psys, p + 125)) {
          pa->flag |= PARS_UNEXIST;
        }
        pa->time = 0.f;
        break;
    }
  }
  
  /* set particle parameters that don't change during particle's life */
  void init_particle(ParticleSimulationData *sim, ParticleData *pa)
  {
    ParticleSettings *part = sim->psys->part;
    float birth_time = (float)(pa - sim->psys->particles) / (float)sim->psys->totpart;
  
    pa->flag &= ~PARS_UNEXIST;
    pa->time = part->sta + (part->end - part->sta) * birth_time;
  
    pa->hair_index = 0;
    /* we can't reset to -1 anymore since we've figured out correct index in distribute_particles */
    /* usage other than straight after distribute has to handle this index by itself - jahka*/
    // pa->num_dmcache = DMCACHE_NOTFOUND; /* assume we don't have a derived mesh face */
  }
  
  static void initialize_all_particles(ParticleSimulationData *sim)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    /* Grid distributionsets UNEXIST flag, need to take care of
     * it here because later this flag is being reset.
     *
     * We can't do it for any distribution, because it'll then
     * conflict with texture influence, which does not free
     * unexisting particles and only sets flag.
     *
     * It's not so bad, because only grid distribution sets
     * UNEXIST flag.
     */
    const bool emit_from_volume_grid = (part->distr == PART_DISTR_GRID) &&
                                       (!ELEM(part->from, PART_FROM_VERT, PART_FROM_CHILD));
    PARTICLE_P;
    LOOP_PARTICLES
    {
      if (!(emit_from_volume_grid && (pa->flag & PARS_UNEXIST) != 0)) {
        init_particle(sim, pa);
      }
    }
  }
  
  static void free_unexisting_particles(ParticleSimulationData *sim)
  {
    ParticleSystem *psys = sim->psys;
    PARTICLE_P;
  
    psys->totunexist = 0;
  
    LOOP_PARTICLES
    {
      if (pa->flag & PARS_UNEXIST) {
        psys->totunexist++;
      }
    }
  
    if (psys->totpart && psys->totunexist == psys->totpart) {
      if (psys->particles->boid) {
        MEM_freeN(psys->particles->boid);
      }
  
      MEM_freeN(psys->particles);
      psys->particles = NULL;
      psys->totpart = psys->totunexist = 0;
    }
  
    if (psys->totunexist) {
      int newtotpart = psys->totpart - psys->totunexist;
      ParticleData *npa, *newpars;
  
      npa = newpars = MEM_callocN(newtotpart * sizeof(ParticleData), "particles");
  
      for (p = 0, pa = psys->particles; p < newtotpart; p++, pa++, npa++) {
        while (pa->flag & PARS_UNEXIST) {
          pa++;
        }
  
        memcpy(npa, pa, sizeof(ParticleData));
      }
  
      if (psys->particles->boid) {
        MEM_freeN(psys->particles->boid);
      }
      MEM_freeN(psys->particles);
      psys->particles = newpars;
      psys->totpart -= psys->totunexist;
  
      if (psys->particles->boid) {
        BoidParticle *newboids = MEM_callocN(psys->totpart * sizeof(BoidParticle), "boid particles");
  
        LOOP_PARTICLES
        {
          pa->boid = newboids++;
        }
      }
    }
  }
  
  static void get_angular_velocity_vector(short avemode, ParticleKey *state, float vec[3])
  {
    switch (avemode) {
      case PART_AVE_VELOCITY:
        copy_v3_v3(vec, state->vel);
        break;
      case PART_AVE_HORIZONTAL: {
        float zvec[3];
        zvec[0] = zvec[1] = 0;
        zvec[2] = 1.f;
        cross_v3_v3v3(vec, state->vel, zvec);
        break;
      }
      case PART_AVE_VERTICAL: {
        float zvec[3], temp[3];
        zvec[0] = zvec[1] = 0;
        zvec[2] = 1.f;
        cross_v3_v3v3(temp, state->vel, zvec);
        cross_v3_v3v3(vec, temp, state->vel);
        break;
      }
      case PART_AVE_GLOBAL_X:
        vec[0] = 1.f;
        vec[1] = vec[2] = 0;
        break;
      case PART_AVE_GLOBAL_Y:
        vec[1] = 1.f;
        vec[0] = vec[2] = 0;
        break;
      case PART_AVE_GLOBAL_Z:
        vec[2] = 1.f;
        vec[0] = vec[1] = 0;
        break;
    }
  }
  
  void psys_get_birth_coords(
      ParticleSimulationData *sim, ParticleData *pa, ParticleKey *state, float dtime, float cfra)
  {
    Object *ob = sim->ob;
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    ParticleTexture ptex;
    float fac, phasefac, nor[3] = {0, 0, 0}, loc[3], vel[3] = {0.0, 0.0, 0.0}, rot[4], q2[4];
    float r_vel[3], r_ave[3], r_rot[4], vec[3], p_vel[3] = {0.0, 0.0, 0.0};
    float x_vec[3] = {1.0, 0.0, 0.0}, utan[3] = {0.0, 1.0, 0.0}, vtan[3] = {0.0, 0.0, 1.0},
          rot_vec[3] = {0.0, 0.0, 0.0};
    float q_phase[4];
  
    const bool use_boids = ((part->phystype == PART_PHYS_BOIDS) && (pa->boid != NULL));
    const bool use_tangents = ((use_boids == false) &&
                               ((part->tanfac != 0.0f) || (part->rotmode == PART_ROT_NOR_TAN)));
  
    int p = pa - psys->particles;
  
    /* get birth location from object       */
    if (use_tangents) {
      psys_particle_on_emitter(sim->psmd,
                               part->from,
                               pa->num,
                               pa->num_dmcache,
                               pa->fuv,
                               pa->foffset,
                               loc,
                               nor,
                               utan,
                               vtan,
                               0);
    }
    else {
      psys_particle_on_emitter(
          sim->psmd, part->from, pa->num, pa->num_dmcache, pa->fuv, pa->foffset, loc, nor, 0, 0, 0);
    }
  
    /* get possible textural influence */
    psys_get_texture(sim, pa, &ptex, PAMAP_IVEL, cfra);
  
    /* particles live in global space so    */
    /* let's convert:                       */
    /* -location                            */
    mul_m4_v3(ob->obmat, loc);
  
    /* -normal                              */
    mul_mat3_m4_v3(ob->obmat, nor);
    normalize_v3(nor);
  
    /* -tangent                             */
    if (use_tangents) {
  #if 0
      float phase = vg_rot ?
                        2.0f *
                            (psys_particle_value_from_verts(sim->psmd->dm, part->from, pa, vg_rot) -
                             0.5f) :
                        0.0f;
  #else
      float phase = 0.0f;
  #endif
      mul_v3_fl(vtan, -cosf((float)M_PI * (part->tanphase + phase)));
      fac = -sinf((float)M_PI * (part->tanphase + phase));
      madd_v3_v3fl(vtan, utan, fac);
  
      mul_mat3_m4_v3(ob->obmat, vtan);
  
      copy_v3_v3(utan, nor);
      mul_v3_fl(utan, dot_v3v3(vtan, nor));
      sub_v3_v3(vtan, utan);
  
      normalize_v3(vtan);
    }
  
    /* -velocity (boids need this even if there's no random velocity) */
    if (part->randfac != 0.0f || (part->phystype == PART_PHYS_BOIDS && pa->boid)) {
      r_vel[0] = 2.0f * (psys_frand(psys, p + 10) - 0.5f);
      r_vel[1] = 2.0f * (psys_frand(psys, p + 11) - 0.5f);
      r_vel[2] = 2.0f * (psys_frand(psys, p + 12) - 0.5f);
  
      mul_mat3_m4_v3(ob->obmat, r_vel);
      normalize_v3(r_vel);
    }
  
    /* -angular velocity                    */
    if (part->avemode == PART_AVE_RAND) {
      r_ave[0] = 2.0f * (psys_frand(psys, p + 13) - 0.5f);
      r_ave[1] = 2.0f * (psys_frand(psys, p + 14) - 0.5f);
      r_ave[2] = 2.0f * (psys_frand(psys, p + 15) - 0.5f);
  
      mul_mat3_m4_v3(ob->obmat, r_ave);
      normalize_v3(r_ave);
    }
  
    /* -rotation                            */
    if (part->randrotfac != 0.0f) {
      r_rot[0] = 2.0f * (psys_frand(psys, p + 16) - 0.5f);
      r_rot[1] = 2.0f * (psys_frand(psys, p + 17) - 0.5f);
      r_rot[2] = 2.0f * (psys_frand(psys, p + 18) - 0.5f);
      r_rot[3] = 2.0f * (psys_frand(psys, p + 19) - 0.5f);
      normalize_qt(r_rot);
  
      mat4_to_quat(rot, ob->obmat);
      mul_qt_qtqt(r_rot, r_rot, rot);
    }
  
    if (use_boids) {
      float dvec[3], q[4], mat[3][3];
  
      copy_v3_v3(state->co, loc);
  
      /* boids don't get any initial velocity  */
      zero_v3(state->vel);
  
      /* boids store direction in ave */
      if (fabsf(nor[2]) == 1.0f) {
        sub_v3_v3v3(state->ave, loc, ob->obmat[3]);
        normalize_v3(state->ave);
      }
      else {
        copy_v3_v3(state->ave, nor);
      }
  
      /* calculate rotation matrix */
      project_v3_v3v3(dvec, r_vel, state->ave);
      sub_v3_v3v3(mat[0], state->ave, dvec);
      normalize_v3(mat[0]);
      negate_v3_v3(mat[2], r_vel);
      normalize_v3(mat[2]);
      cross_v3_v3v3(mat[1], mat[2], mat[0]);
  
      /* apply rotation */
      mat3_to_quat_is_ok(q, mat);
      copy_qt_qt(state->rot, q);
    }
    else {
      /* conversion done so now we apply new: */
      /* -velocity from:                      */
  
      /*      *reactions                      */
      if (dtime > 0.f) {
        sub_v3_v3v3(vel, pa->state.vel, pa->prev_state.vel);
      }
  
      /*      *emitter velocity               */
      if (dtime != 0.f && part->obfac != 0.f) {
        sub_v3_v3v3(vel, loc, state->co);
        mul_v3_fl(vel, part->obfac / dtime);
      }
  
      /*      *emitter normal                 */
      if (part->normfac != 0.f) {
        madd_v3_v3fl(vel, nor, part->normfac);
      }
  
      /*      *emitter tangent                */
      if (sim->psmd && part->tanfac != 0.f) {
        madd_v3_v3fl(vel, vtan, part->tanfac);
      }
  
      /*      *emitter object orientation     */
      if (part->ob_vel[0] != 0.f) {
        normalize_v3_v3(vec, ob->obmat[0]);
        madd_v3_v3fl(vel, vec, part->ob_vel[0]);
      }
      if (part->ob_vel[1] != 0.f) {
        normalize_v3_v3(vec, ob->obmat[1]);
        madd_v3_v3fl(vel, vec, part->ob_vel[1]);
      }
      if (part->ob_vel[2] != 0.f) {
        normalize_v3_v3(vec, ob->obmat[2]);
        madd_v3_v3fl(vel, vec, part->ob_vel[2]);
      }
  
      /*      *texture                        */
      /* TODO */
  
      /*      *random                         */
      if (part->randfac != 0.f) {
        madd_v3_v3fl(vel, r_vel, part->randfac);
      }
  
      /*      *particle                       */
      if (part->partfac != 0.f) {
        madd_v3_v3fl(vel, p_vel, part->partfac);
      }
  
      mul_v3_v3fl(state->vel, vel, ptex.ivel);
  
      /* -location from emitter               */
      copy_v3_v3(state->co, loc);
  
      /* -rotation                            */
      unit_qt(state->rot);
  
      if (part->rotmode) {
        bool use_global_space;
  
        /* create vector into which rotation is aligned */
        switch (part->rotmode) {
          case PART_ROT_NOR:
          case PART_ROT_NOR_TAN:
            copy_v3_v3(rot_vec, nor);
            use_global_space = false;
            break;
          case PART_ROT_VEL:
            copy_v3_v3(rot_vec, vel);
            use_global_space = true;
            break;
          case PART_ROT_GLOB_X:
          case PART_ROT_GLOB_Y:
          case PART_ROT_GLOB_Z:
            rot_vec[part->rotmode - PART_ROT_GLOB_X] = 1.0f;
            use_global_space = true;
            break;
          case PART_ROT_OB_X:
          case PART_ROT_OB_Y:
          case PART_ROT_OB_Z:
            copy_v3_v3(rot_vec, ob->obmat[part->rotmode - PART_ROT_OB_X]);
            use_global_space = false;
            break;
          default:
            use_global_space = true;
            break;
        }
  
        /* create rotation quat */
  
        if (use_global_space) {
          negate_v3(rot_vec);
          vec_to_quat(q2, rot_vec, OB_POSX, OB_POSZ);
  
          /* randomize rotation quat */
          if (part->randrotfac != 0.0f) {
            interp_qt_qtqt(rot, q2, r_rot, part->randrotfac);
          }
          else {
            copy_qt_qt(rot, q2);
          }
        }
        else {
          /* calculate rotation in local-space */
          float q_obmat[4];
          float q_imat[4];
  
          mat4_to_quat(q_obmat, ob->obmat);
          invert_qt_qt_normalized(q_imat, q_obmat);
  
          if (part->rotmode != PART_ROT_NOR_TAN) {
            float rot_vec_local[3];
  
            /* rot_vec */
            negate_v3(rot_vec);
            copy_v3_v3(rot_vec_local, rot_vec);
            mul_qt_v3(q_imat, rot_vec_local);
            normalize_v3(rot_vec_local);
  
            vec_to_quat(q2, rot_vec_local, OB_POSX, OB_POSZ);
          }
          else {
            /* (part->rotmode == PART_ROT_NOR_TAN) */
            float tmat[3][3];
  
            /* note: utan_local is not taken from 'utan', we calculate from rot_vec/vtan */
            /* note: it looks like rotation phase may be applied twice (once with vtan, again below)
             * however this isn't the case - campbell */
            float *rot_vec_local = tmat[0];
            float *vtan_local = tmat[1];
            float *utan_local = tmat[2];
  
            /* use tangents */
            BLI_assert(use_tangents == true);
  
            /* rot_vec */
            copy_v3_v3(rot_vec_local, rot_vec);
            mul_qt_v3(q_imat, rot_vec_local);
  
            /* vtan_local */
            copy_v3_v3(vtan_local, vtan); /* flips, cant use */
            mul_qt_v3(q_imat, vtan_local);
  
            /* ensure orthogonal matrix (rot_vec aligned) */
            cross_v3_v3v3(utan_local, vtan_local, rot_vec_local);
            cross_v3_v3v3(vtan_local, utan_local, rot_vec_local);
  
            /* note: no need to normalize */
            mat3_to_quat(q2, tmat);
          }
  
          /* randomize rotation quat */
          if (part->randrotfac != 0.0f) {
            mul_qt_qtqt(r_rot, r_rot, q_imat);
            interp_qt_qtqt(rot, q2, r_rot, part->randrotfac);
          }
          else {
            copy_qt_qt(rot, q2);
          }
  
          mul_qt_qtqt(rot, q_obmat, rot);
        }
  
        /* rotation phase */
        phasefac = part->phasefac;
        if (part->randphasefac != 0.0f) {
          phasefac += part->randphasefac * psys_frand(psys, p + 20);
        }
        axis_angle_to_quat(q_phase, x_vec, phasefac * (float)M_PI);
  
        /* combine base rotation & phase */
        mul_qt_qtqt(state->rot, rot, q_phase);
      }
  
      /* -angular velocity                    */
  
      zero_v3(state->ave);
  
      if (part->avemode) {
        if (part->avemode == PART_AVE_RAND) {
          copy_v3_v3(state->ave, r_ave);
        }
        else {
          get_angular_velocity_vector(part->avemode, state, state->ave);
        }
  
        normalize_v3(state->ave);
        mul_v3_fl(state->ave, part->avefac);
      }
    }
  }
  
  /* recursively evaluate emitter parent anim at cfra */
  static void evaluate_emitter_anim(struct Depsgraph *depsgraph,
                                    Scene *scene,
                                    Object *ob,
                                    float cfra)
  {
    if (ob->parent) {
      evaluate_emitter_anim(depsgraph, scene, ob->parent, cfra);
    }
  
    BKE_object_where_is_calc_time(depsgraph, scene, ob, cfra);
  }
  
  /* sets particle to the emitter surface with initial velocity & rotation */
  void reset_particle(ParticleSimulationData *sim, ParticleData *pa, float dtime, float cfra)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part;
    ParticleTexture ptex;
    int p = pa - psys->particles;
    part = psys->part;
  
    /* get precise emitter matrix if particle is born */
    if (part->type != PART_HAIR && dtime > 0.f && pa->time < cfra && pa->time >= sim->psys->cfra) {
      evaluate_emitter_anim(sim->depsgraph, sim->scene, sim->ob, pa->time);
  
      psys->flag |= PSYS_OB_ANIM_RESTORE;
    }
  
    psys_get_birth_coords(sim, pa, &pa->state, dtime, cfra);
  
    /* Initialize particle settings which depends on texture.
     *
     * We could only do it now because we'll need to know coordinate
     * before sampling the texture.
     */
    init_particle_texture(sim, pa, p);
  
    if (part->phystype == PART_PHYS_BOIDS && pa->boid) {
      BoidParticle *bpa = pa->boid;
  
      /* and gravity in r_ve */
      bpa->gravity[0] = bpa->gravity[1] = 0.0f;
      bpa->gravity[2] = -1.0f;
      if ((sim->scene->physics_settings.flag & PHYS_GLOBAL_GRAVITY) &&
          (sim->scene->physics_settings.gravity[2] != 0.0f)) {
        bpa->gravity[2] = sim->scene->physics_settings.gravity[2];
      }
  
      bpa->data.health = part->boids->health;
      bpa->data.mode = eBoidMode_InAir;
      bpa->data.state_id = ((BoidState *)part->boids->states.first)->id;
      bpa->data.acc[0] = bpa->data.acc[1] = bpa->data.acc[2] = 0.0f;
    }
  
    if (part->type == PART_HAIR) {
      pa->lifetime = 100.0f;
    }
    else {
      /* initialize the lifetime, in case the texture coordinates
       * are from Particles/Strands, which would cause undefined values
       */
      pa->lifetime = part->lifetime * (1.0f - part->randlife * psys_frand(psys, p + 21));
      pa->dietime = pa->time + pa->lifetime;
  
      /* get possible textural influence */
      psys_get_texture(sim, pa, &ptex, PAMAP_LIFE, cfra);
  
      pa->lifetime = part->lifetime * ptex.life;
  
      if (part->randlife != 0.0f) {
        pa->lifetime *= 1.0f - part->randlife * psys_frand(psys, p + 21);
      }
    }
  
    pa->dietime = pa->time + pa->lifetime;
  
    if ((sim->psys->pointcache) && (sim->psys->pointcache->flag & PTCACHE_BAKED) &&
        (sim->psys->pointcache->mem_cache.first)) {
      float dietime = psys_get_dietime_from_cache(sim->psys->pointcache, p);
      pa->dietime = MIN2(pa->dietime, dietime);
    }
  
    if (pa->time > cfra) {
      pa->alive = PARS_UNBORN;
    }
    else if (pa->dietime <= cfra) {
      pa->alive = PARS_DEAD;
    }
    else {
      pa->alive = PARS_ALIVE;
    }
  
    pa->state.time = cfra;
  }
  static void reset_all_particles(ParticleSimulationData *sim, float dtime, float cfra, int from)
  {
    ParticleData *pa;
    int p, totpart = sim->psys->totpart;
  
    for (p = from, pa = sim->psys->particles + from; p < totpart; p++, pa++) {
      reset_particle(sim, pa, dtime, cfra);
    }
  }
  /************************************************/
  /*          Particle targets                    */
  /************************************************/
  ParticleSystem *psys_get_target_system(Object *ob, ParticleTarget *pt)
  {
    ParticleSystem *psys = NULL;
  
    if (pt->ob == NULL || pt->ob == ob) {
      psys = BLI_findlink(&ob->particlesystem, pt->psys - 1);
    }
    else {
      psys = BLI_findlink(&pt->ob->particlesystem, pt->psys - 1);
    }
  
    if (psys) {
      pt->flag |= PTARGET_VALID;
    }
    else {
      pt->flag &= ~PTARGET_VALID;
    }
  
    return psys;
  }
  /************************************************/
  /*          Keyed particles                     */
  /************************************************/
  /* Counts valid keyed targets */
  void psys_count_keyed_targets(ParticleSimulationData *sim)
  {
    ParticleSystem *psys = sim->psys, *kpsys;
    ParticleTarget *pt = psys->targets.first;
    int keys_valid = 1;
    psys->totkeyed = 0;
  
    for (; pt; pt = pt->next) {
      kpsys = psys_get_target_system(sim->ob, pt);
  
      if (kpsys && kpsys->totpart) {
        psys->totkeyed += keys_valid;
        if (psys->flag & PSYS_KEYED_TIMING && pt->duration != 0.0f) {
          psys->totkeyed += 1;
        }
      }
      else {
        keys_valid = 0;
      }
    }
  
    psys->totkeyed *= psys->flag & PSYS_KEYED_TIMING ? 1 : psys->part->keyed_loops;
  }
  
  static void set_keyed_keys(ParticleSimulationData *sim)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSimulationData ksim = {0};
    ParticleTarget *pt;
    PARTICLE_P;
    ParticleKey *key;
    int totpart = psys->totpart, k, totkeys = psys->totkeyed;
    int keyed_flag = 0;
  
    ksim.depsgraph = sim->depsgraph;
    ksim.scene = sim->scene;
  
    /* no proper targets so let's clear and bail out */
    if (psys->totkeyed == 0) {
      free_keyed_keys(psys);
      psys->flag &= ~PSYS_KEYED;
      return;
    }
  
    if (totpart && psys->particles->totkey != totkeys) {
      free_keyed_keys(psys);
  
      key = MEM_callocN(totpart * totkeys * sizeof(ParticleKey), "Keyed keys");
  
      LOOP_PARTICLES
      {
        pa->keys = key;
        pa->totkey = totkeys;
        key += totkeys;
      }
    }
  
    psys->flag &= ~PSYS_KEYED;
  
    pt = psys->targets.first;
    for (k = 0; k < totkeys; k++) {
      ksim.ob = pt->ob ? pt->ob : sim->ob;
      ksim.psys = BLI_findlink(&ksim.ob->particlesystem, pt->psys - 1);
      keyed_flag = (ksim.psys->flag & PSYS_KEYED);
      ksim.psys->flag &= ~PSYS_KEYED;
  
      LOOP_PARTICLES
      {
        key = pa->keys + k;
        key->time = -1.0; /* use current time */
  
        const int p_ksim = (ksim.psys->totpart) ? p % ksim.psys->totpart : 0;
        psys_get_particle_state(&ksim, p_ksim, key, 1);
  
        if (psys->flag & PSYS_KEYED_TIMING) {
          key->time = pa->time + pt->time;
          if (pt->duration != 0.0f && k + 1 < totkeys) {
            copy_particle_key(key + 1, key, 1);
            (key + 1)->time = pa->time + pt->time + pt->duration;
          }
        }
        else if (totkeys > 1) {
          key->time = pa->time + (float)k / (float)(totkeys - 1) * pa->lifetime;
        }
        else {
          key->time = pa->time;
        }
      }
  
      if (psys->flag & PSYS_KEYED_TIMING && pt->duration != 0.0f) {
        k++;
      }
  
      ksim.psys->flag |= keyed_flag;
  
      pt = (pt->next && pt->next->flag & PTARGET_VALID) ? pt->next : psys->targets.first;
    }
  
    psys->flag |= PSYS_KEYED;
  }
  
  /************************************************/
  /*          Point Cache                         */
  /************************************************/
  void psys_make_temp_pointcache(Object *ob, ParticleSystem *psys)
  {
    PointCache *cache = psys->pointcache;
  
    if (cache->flag & PTCACHE_DISK_CACHE && BLI_listbase_is_empty(&cache->mem_cache)) {
      PTCacheID pid;
      BKE_ptcache_id_from_particles(&pid, ob, psys);
      cache->flag &= ~PTCACHE_DISK_CACHE;
      BKE_ptcache_disk_to_mem(&pid);
      cache->flag |= PTCACHE_DISK_CACHE;
    }
  }
  static void psys_clear_temp_pointcache(ParticleSystem *psys)
  {
    if (psys->pointcache->flag & PTCACHE_DISK_CACHE) {
      BKE_ptcache_free_mem(&psys->pointcache->mem_cache);
    }
  }
  void psys_get_pointcache_start_end(Scene *scene, ParticleSystem *psys, int *sfra, int *efra)
  {
    ParticleSettings *part = psys->part;
  
    *sfra = max_ii(1, (int)part->sta);
    *efra = min_ii((int)(part->end + part->lifetime + 1.0f), max_ii(scene->r.pefra, scene->r.efra));
  }
  
  /************************************************/
  /*          Effectors                           */
  /************************************************/
  static void psys_update_particle_bvhtree(ParticleSystem *psys, float cfra)
  {
    if (psys) {
      PARTICLE_P;
      int totpart = 0;
      bool need_rebuild;
  
      BLI_rw_mutex_lock(&psys_bvhtree_rwlock, THREAD_LOCK_READ);
      need_rebuild = !psys->bvhtree || psys->bvhtree_frame != cfra;
      BLI_rw_mutex_unlock(&psys_bvhtree_rwlock);
  
      if (need_rebuild) {
        LOOP_SHOWN_PARTICLES
        {
          totpart++;
        }
  
        BLI_rw_mutex_lock(&psys_bvhtree_rwlock, THREAD_LOCK_WRITE);
  
        BLI_bvhtree_free(psys->bvhtree);
        psys->bvhtree = BLI_bvhtree_new(totpart, 0.0, 4, 6);
  
        LOOP_SHOWN_PARTICLES
        {
          if (pa->alive == PARS_ALIVE) {
            if (pa->state.time == cfra) {
              BLI_bvhtree_insert(psys->bvhtree, p, pa->prev_state.co, 1);
            }
            else {
              BLI_bvhtree_insert(psys->bvhtree, p, pa->state.co, 1);
            }
          }
        }
        BLI_bvhtree_balance(psys->bvhtree);
  
        psys->bvhtree_frame = cfra;
  
        BLI_rw_mutex_unlock(&psys_bvhtree_rwlock);
      }
    }
  }
  void psys_update_particle_tree(ParticleSystem *psys, float cfra)
  {
    if (psys) {
      PARTICLE_P;
      int totpart = 0;
  
      if (!psys->tree || psys->tree_frame != cfra) {
        LOOP_SHOWN_PARTICLES
        {
          totpart++;
        }
  
        BLI_kdtree_3d_free(psys->tree);
        psys->tree = BLI_kdtree_3d_new(psys->totpart);
  
        LOOP_SHOWN_PARTICLES
        {
          if (pa->alive == PARS_ALIVE) {
            if (pa->state.time == cfra) {
              BLI_kdtree_3d_insert(psys->tree, p, pa->prev_state.co);
            }
            else {
              BLI_kdtree_3d_insert(psys->tree, p, pa->state.co);
            }
          }
        }
        BLI_kdtree_3d_balance(psys->tree);
  
        psys->tree_frame = cfra;
      }
    }
  }
  
  static void psys_update_effectors(ParticleSimulationData *sim)
  {
    BKE_effectors_free(sim->psys->effectors);
    sim->psys->effectors = BKE_effectors_create(
        sim->depsgraph, sim->ob, sim->psys, sim->psys->part->effector_weights);
    precalc_guides(sim, sim->psys->effectors);
  }
  
  static void integrate_particle(
      ParticleSettings *part,
      ParticleData *pa,
      float dtime,
      float *external_acceleration,
      void (*force_func)(void *forcedata, ParticleKey *state, float *force, float *impulse),
      void *forcedata)
  {
  #define ZERO_F43 \
    { \
      {0.0f, 0.0f, 0.0f}, {0.0f, 0.0f, 0.0f}, {0.0f, 0.0f, 0.0f}, \
      { \
        0.0f, 0.0f, 0.0f \
      } \
    }
  
    ParticleKey states[5];
    float force[3], acceleration[3], impulse[3], dx[4][3] = ZERO_F43, dv[4][3] = ZERO_F43, oldpos[3];
    float pa_mass = (part->flag & PART_SIZEMASS ? part->mass * pa->size : part->mass);
    int i, steps = 1;
    int integrator = part->integrator;
  
  #undef ZERO_F43
  
    copy_v3_v3(oldpos, pa->state.co);
  
    /* Verlet integration behaves strangely with moving emitters, so do first step with euler. */
    if (pa->prev_state.time < 0.f && integrator == PART_INT_VERLET) {
      integrator = PART_INT_EULER;
    }
  
    switch (integrator) {
      case PART_INT_EULER:
        steps = 1;
        break;
      case PART_INT_MIDPOINT:
        steps = 2;
        break;
      case PART_INT_RK4:
        steps = 4;
        break;
      case PART_INT_VERLET:
        steps = 1;
        break;
    }
  
    for (i = 0; i < steps; i++) {
      copy_particle_key(states + i, &pa->state, 1);
    }
  
    states->time = 0.f;
  
    for (i = 0; i < steps; i++) {
      zero_v3(force);
      zero_v3(impulse);
  
      force_func(forcedata, states + i, force, impulse);
  
      /* force to acceleration*/
      mul_v3_v3fl(acceleration, force, 1.0f / pa_mass);
  
      if (external_acceleration) {
        add_v3_v3(acceleration, external_acceleration);
      }
  
      /* calculate next state */
      add_v3_v3(states[i].vel, impulse);
  
      switch (integrator) {
        case PART_INT_EULER:
          madd_v3_v3v3fl(pa->state.co, states->co, states->vel, dtime);
          madd_v3_v3v3fl(pa->state.vel, states->vel, acceleration, dtime);
          break;
        case PART_INT_MIDPOINT:
          if (i == 0) {
            madd_v3_v3v3fl(states[1].co, states->co, states->vel, dtime * 0.5f);
            madd_v3_v3v3fl(states[1].vel, states->vel, acceleration, dtime * 0.5f);
            states[1].time = dtime * 0.5f;
            /*fra=sim->psys->cfra+0.5f*dfra;*/
          }
          else {
            madd_v3_v3v3fl(pa->state.co, states->co, states[1].vel, dtime);
            madd_v3_v3v3fl(pa->state.vel, states->vel, acceleration, dtime);
          }
          break;
        case PART_INT_RK4:
          switch (i) {
            case 0:
              copy_v3_v3(dx[0], states->vel);
              mul_v3_fl(dx[0], dtime);
              copy_v3_v3(dv[0], acceleration);
              mul_v3_fl(dv[0], dtime);
  
              madd_v3_v3v3fl(states[1].co, states->co, dx[0], 0.5f);
              madd_v3_v3v3fl(states[1].vel, states->vel, dv[0], 0.5f);
              states[1].time = dtime * 0.5f;
              /*fra=sim->psys->cfra+0.5f*dfra;*/
              break;
            case 1:
              madd_v3_v3v3fl(dx[1], states->vel, dv[0], 0.5f);
              mul_v3_fl(dx[1], dtime);
              copy_v3_v3(dv[1], acceleration);
              mul_v3_fl(dv[1], dtime);
  
              madd_v3_v3v3fl(states[2].co, states->co, dx[1], 0.5f);
              madd_v3_v3v3fl(states[2].vel, states->vel, dv[1], 0.5f);
              states[2].time = dtime * 0.5f;
              break;
            case 2:
              madd_v3_v3v3fl(dx[2], states->vel, dv[1], 0.5f);
              mul_v3_fl(dx[2], dtime);
              copy_v3_v3(dv[2], acceleration);
              mul_v3_fl(dv[2], dtime);
  
              add_v3_v3v3(states[3].co, states->co, dx[2]);
              add_v3_v3v3(states[3].vel, states->vel, dv[2]);
              states[3].time = dtime;
              /*fra=cfra;*/
              break;
            case 3:
              add_v3_v3v3(dx[3], states->vel, dv[2]);
              mul_v3_fl(dx[3], dtime);
              copy_v3_v3(dv[3], acceleration);
              mul_v3_fl(dv[3], dtime);
  
              madd_v3_v3v3fl(pa->state.co, states->co, dx[0], 1.0f / 6.0f);
              madd_v3_v3fl(pa->state.co, dx[1], 1.0f / 3.0f);
              madd_v3_v3fl(pa->state.co, dx[2], 1.0f / 3.0f);
              madd_v3_v3fl(pa->state.co, dx[3], 1.0f / 6.0f);
  
              madd_v3_v3v3fl(pa->state.vel, states->vel, dv[0], 1.0f / 6.0f);
              madd_v3_v3fl(pa->state.vel, dv[1], 1.0f / 3.0f);
              madd_v3_v3fl(pa->state.vel, dv[2], 1.0f / 3.0f);
              madd_v3_v3fl(pa->state.vel, dv[3], 1.0f / 6.0f);
          }
          break;
        case PART_INT_VERLET: /* Verlet integration */
          madd_v3_v3v3fl(pa->state.vel, pa->prev_state.vel, acceleration, dtime);
          madd_v3_v3v3fl(pa->state.co, pa->prev_state.co, pa->state.vel, dtime);
  
          sub_v3_v3v3(pa->state.vel, pa->state.co, oldpos);
          mul_v3_fl(pa->state.vel, 1.0f / dtime);
          break;
      }
    }
  }
  
  /* -------------------------------------------------------------------- */
  /** \name SPH fluid physics
   *
   * In theory, there could be unlimited implementation of SPH simulators
   *
   * This code uses in some parts adapted algorithms
   * from the pseudo code as outlined in the Research paper:
   *
   * Titled: Particle-based Viscoelastic Fluid Simulation.
   * Authors: Simon Clavet, Philippe Beaudoin and Pierre Poulin
   * Website: http://www.iro.umontreal.ca/labs/infographie/papers/Clavet-2005-PVFS/
   *
   * Presented at Siggraph, (2005)
   *
   * \{ */
  
  #define PSYS_FLUID_SPRINGS_INITIAL_SIZE 256
  static ParticleSpring *sph_spring_add(ParticleSystem *psys, ParticleSpring *spring)
  {
    /* Are more refs required? */
    if (psys->alloc_fluidsprings == 0 || psys->fluid_springs == NULL) {
      psys->alloc_fluidsprings = PSYS_FLUID_SPRINGS_INITIAL_SIZE;
      psys->fluid_springs = (ParticleSpring *)MEM_callocN(
          psys->alloc_fluidsprings * sizeof(ParticleSpring), "Particle Fluid Springs");
    }
    else if (psys->tot_fluidsprings == psys->alloc_fluidsprings) {
      /* Double the number of refs allocated */
      psys->alloc_fluidsprings *= 2;
      psys->fluid_springs = (ParticleSpring *)MEM_reallocN(
          psys->fluid_springs, psys->alloc_fluidsprings * sizeof(ParticleSpring));
    }
  
    memcpy(psys->fluid_springs + psys->tot_fluidsprings, spring, sizeof(ParticleSpring));
    psys->tot_fluidsprings++;
  
    return psys->fluid_springs + psys->tot_fluidsprings - 1;
  }
  static void sph_spring_delete(ParticleSystem *psys, int j)
  {
    if (j != psys->tot_fluidsprings - 1) {
      psys->fluid_springs[j] = psys->fluid_springs[psys->tot_fluidsprings - 1];
    }
  
    psys->tot_fluidsprings--;
  
    if (psys->tot_fluidsprings < psys->alloc_fluidsprings / 2 &&
        psys->alloc_fluidsprings > PSYS_FLUID_SPRINGS_INITIAL_SIZE) {
      psys->alloc_fluidsprings /= 2;
      psys->fluid_springs = (ParticleSpring *)MEM_reallocN(
          psys->fluid_springs, psys->alloc_fluidsprings * sizeof(ParticleSpring));
    }
  }
  static void sph_springs_modify(ParticleSystem *psys, float dtime)
  {
    SPHFluidSettings *fluid = psys->part->fluid;
    ParticleData *pa1, *pa2;
    ParticleSpring *spring = psys->fluid_springs;
  
    float h, d, Rij[3], rij, Lij;
    int i;
  
    float yield_ratio = fluid->yield_ratio;
    float plasticity = fluid->plasticity_constant;
    /* scale things according to dtime */
    float timefix = 25.f * dtime;
  
    if ((fluid->flag & SPH_VISCOELASTIC_SPRINGS) == 0 || fluid->spring_k == 0.f) {
      return;
    }
  
    /* Loop through the springs */
    for (i = 0; i < psys->tot_fluidsprings; i++, spring++) {
      pa1 = psys->particles + spring->particle_index[0];
      pa2 = psys->particles + spring->particle_index[1];
  
      sub_v3_v3v3(Rij, pa2->prev_state.co, pa1->prev_state.co);
      rij = normalize_v3(Rij);
  
      /* adjust rest length */
      Lij = spring->rest_length;
      d = yield_ratio * timefix * Lij;
  
      if (rij > Lij + d) {  // Stretch
        spring->rest_length += plasticity * (rij - Lij - d) * timefix;
      }
      else if (rij < Lij - d) {  // Compress
        spring->rest_length -= plasticity * (Lij - d - rij) * timefix;
      }
  
      h = 4.f * pa1->size;
  
      if (spring->rest_length > h) {
        spring->delete_flag = 1;
      }
    }
  
    /* Loop through springs backwaqrds - for efficient delete function */
    for (i = psys->tot_fluidsprings - 1; i >= 0; i--) {
      if (psys->fluid_springs[i].delete_flag) {
        sph_spring_delete(psys, i);
      }
    }
  }
  static EdgeHash *sph_springhash_build(ParticleSystem *psys)
  {
    EdgeHash *springhash = NULL;
    ParticleSpring *spring;
    int i = 0;
  
    springhash = BLI_edgehash_new_ex(__func__, psys->tot_fluidsprings);
  
    for (i = 0, spring = psys->fluid_springs; i < psys->tot_fluidsprings; i++, spring++) {
      BLI_edgehash_insert(
          springhash, spring->particle_index[0], spring->particle_index[1], POINTER_FROM_INT(i + 1));
    }
  
    return springhash;
  }
  
  #define SPH_NEIGHBORS 512
  typedef struct SPHNeighbor {
    ParticleSystem *psys;
    int index;
  } SPHNeighbor;
  
  typedef struct SPHRangeData {
    SPHNeighbor neighbors[SPH_NEIGHBORS];
    int tot_neighbors;
  
    float *data;
  
    ParticleSystem *npsys;
    ParticleData *pa;
  
    float h;
    float mass;
    float massfac;
    int use_size;
  } SPHRangeData;
  
  static void sph_evaluate_func(BVHTree *tree,
                                ParticleSystem **psys,
                                const float co[3],
                                SPHRangeData *pfr,
                                float interaction_radius,
                                BVHTree_RangeQuery callback)
  {
    int i;
  
    pfr->tot_neighbors = 0;
  
    for (i = 0; i < 10 && psys[i]; i++) {
      pfr->npsys = psys[i];
      pfr->massfac = psys[i]->part->mass / pfr->mass;
      pfr->use_size = psys[i]->part->flag & PART_SIZEMASS;
  
      if (tree) {
        BLI_bvhtree_range_query(tree, co, interaction_radius, callback, pfr);
        break;
      }
  
      BLI_rw_mutex_lock(&psys_bvhtree_rwlock, THREAD_LOCK_READ);
  
      BLI_bvhtree_range_query(psys[i]->bvhtree, co, interaction_radius, callback, pfr);
  
      BLI_rw_mutex_unlock(&psys_bvhtree_rwlock);
    }
  }
  static void sph_density_accum_cb(void *userdata, int index, const float co[3], float squared_dist)
  {
    SPHRangeData *pfr = (SPHRangeData *)userdata;
    ParticleData *npa = pfr->npsys->particles + index;
    float q;
    float dist;
  
    UNUSED_VARS(co);
  
    if (npa == pfr->pa || squared_dist < FLT_EPSILON) {
      return;
    }
  
    /* Ugh! One particle has too many neighbors! If some aren't taken into
     * account, the forces will be biased by the tree search order. This
     * effectively adds energy to the system, and results in a churning motion.
     * But, we have to stop somewhere, and it's not the end of the world.
     * - jahka and z0r
     */
    if (pfr->tot_neighbors >= SPH_NEIGHBORS) {
      return;
    }
  
    pfr->neighbors[pfr->tot_neighbors].index = index;
    pfr->neighbors[pfr->tot_neighbors].psys = pfr->npsys;
    pfr->tot_neighbors++;
  
    dist = sqrtf(squared_dist);
    q = (1.f - dist / pfr->h) * pfr->massfac;
  
    if (pfr->use_size) {
      q *= npa->size;
    }
  
    pfr->data[0] += q * q;
    pfr->data[1] += q * q * q;
  }
  
  /*
   * Find the Courant number for an SPH particle (used for adaptive time step).
   */
  static void sph_particle_courant(SPHData *sphdata, SPHRangeData *pfr)
  {
    ParticleData *pa, *npa;
    int i;
    float flow[3], offset[3], dist;
  
    zero_v3(flow);
  
    dist = 0.0f;
    if (pfr->tot_neighbors > 0) {
      pa = pfr->pa;
      for (i = 0; i < pfr->tot_neighbors; i++) {
        npa = pfr->neighbors[i].psys->particles + pfr->neighbors[i].index;
        sub_v3_v3v3(offset, pa->prev_state.co, npa->prev_state.co);
        dist += len_v3(offset);
        add_v3_v3(flow, npa->prev_state.vel);
      }
      dist += sphdata->psys[0]->part->fluid->radius;  // TODO: remove this? - z0r
      sphdata->element_size = dist / pfr->tot_neighbors;
      mul_v3_v3fl(sphdata->flow, flow, 1.0f / pfr->tot_neighbors);
    }
    else {
      sphdata->element_size = FLT_MAX;
      copy_v3_v3(sphdata->flow, flow);
    }
  }
  static void sph_force_cb(void *sphdata_v, ParticleKey *state, float *force, float *UNUSED(impulse))
  {
    SPHData *sphdata = (SPHData *)sphdata_v;
    ParticleSystem **psys = sphdata->psys;
    ParticleData *pa = sphdata->pa;
    SPHFluidSettings *fluid = psys[0]->part->fluid;
    ParticleSpring *spring = NULL;
    SPHRangeData pfr;
    SPHNeighbor *pfn;
    float *gravity = sphdata->gravity;
    EdgeHash *springhash = sphdata->eh;
  
    float q, u, rij, dv[3];
    float pressure, near_pressure;
  
    float visc = fluid->viscosity_omega;
    float stiff_visc = fluid->viscosity_beta *
                       (fluid->flag & SPH_FAC_VISCOSITY ? fluid->viscosity_omega : 1.f);
  
    float inv_mass = 1.0f / sphdata->mass;
    float spring_constant = fluid->spring_k;
  
    /* 4.0 seems to be a pretty good value */
    float interaction_radius = fluid->radius *
                               (fluid->flag & SPH_FAC_RADIUS ? 4.0f * pa->size : 1.0f);
    float h = interaction_radius * sphdata->hfac;
    /* 4.77 is an experimentally determined density factor */
    float rest_density = fluid->rest_density * (fluid->flag & SPH_FAC_DENSITY ? 4.77f : 1.f);
    float rest_length = fluid->rest_length *
                        (fluid->flag & SPH_FAC_REST_LENGTH ? 2.588f * pa->size : 1.f);
  
    float stiffness = fluid->stiffness_k;
    float stiffness_near_fac = fluid->stiffness_knear *
                               (fluid->flag & SPH_FAC_REPULSION ? fluid->stiffness_k : 1.f);
  
    ParticleData *npa;
    float vec[3];
    float vel[3];
    float co[3];
    float data[2];
    float density, near_density;
  
    int i, spring_index, index = pa - psys[0]->particles;
  
    data[0] = data[1] = 0;
    pfr.data = data;
    pfr.h = h;
    pfr.pa = pa;
    pfr.mass = sphdata->mass;
  
    sph_evaluate_func(NULL, psys, state->co, &pfr, interaction_radius, sph_density_accum_cb);
  
    density = data[0];
    near_density = data[1];
  
    pressure = stiffness * (density - rest_density);
    near_pressure = stiffness_near_fac * near_density;
  
    pfn = pfr.neighbors;
    for (i = 0; i < pfr.tot_neighbors; i++, pfn++) {
      npa = pfn->psys->particles + pfn->index;
  
      madd_v3_v3v3fl(co, npa->prev_state.co, npa->prev_state.vel, state->time);
  
      sub_v3_v3v3(vec, co, state->co);
      rij = normalize_v3(vec);
  
      q = (1.f - rij / h) * pfn->psys->part->mass * inv_mass;
  
      if (pfn->psys->part->flag & PART_SIZEMASS) {
        q *= npa->size;
      }
  
      copy_v3_v3(vel, npa->prev_state.vel);
  
      /* Double Density Relaxation */
      madd_v3_v3fl(force, vec, -(pressure + near_pressure * q) * q);
  
      /* Viscosity */
      if (visc > 0.f || stiff_visc > 0.f) {
        sub_v3_v3v3(dv, vel, state->vel);
        u = dot_v3v3(vec, dv);
  
        if (u < 0.f && visc > 0.f) {
          madd_v3_v3fl(force, vec, 0.5f * q * visc * u);
        }
  
        if (u > 0.f && stiff_visc > 0.f) {
          madd_v3_v3fl(force, vec, 0.5f * q * stiff_visc * u);
        }
      }
  
      if (spring_constant > 0.f) {
        /* Viscoelastic spring force */
        if (pfn->psys == psys[0] && fluid->flag & SPH_VISCOELASTIC_SPRINGS && springhash) {
          /* BLI_edgehash_lookup appears to be thread-safe. - z0r */
          spring_index = POINTER_AS_INT(BLI_edgehash_lookup(springhash, index, pfn->index));
  
          if (spring_index) {
            spring = psys[0]->fluid_springs + spring_index - 1;
  
            madd_v3_v3fl(
                force, vec, -10.f * spring_constant * (1.f - rij / h) * (spring->rest_length - rij));
          }
          else if (fluid->spring_frames == 0 ||
                   (pa->prev_state.time - pa->time) <= fluid->spring_frames) {
            ParticleSpring temp_spring;
            temp_spring.particle_index[0] = index;
            temp_spring.particle_index[1] = pfn->index;
            temp_spring.rest_length = (fluid->flag & SPH_CURRENT_REST_LENGTH) ? rij : rest_length;
            temp_spring.delete_flag = 0;
  
            BLI_buffer_append(&sphdata->new_springs, ParticleSpring, temp_spring);
          }
        }
        else { /* PART_SPRING_HOOKES - Hooke's spring force */
          madd_v3_v3fl(force, vec, -10.f * spring_constant * (1.f - rij / h) * (rest_length - rij));
        }
      }
    }
  
    /* Artificial buoyancy force in negative gravity direction  */
    if (fluid->buoyancy > 0.f && gravity) {
      madd_v3_v3fl(force, gravity, fluid->buoyancy * (density - rest_density));
    }
  
    if (sphdata->pass == 0 && psys[0]->part->time_flag & PART_TIME_AUTOSF) {
      sph_particle_courant(sphdata, &pfr);
    }
    sphdata->pass++;
  }
  
  static void sphclassical_density_accum_cb(void *userdata,
                                            int index,
                                            const float co[3],
                                            float UNUSED(squared_dist))
  {
    SPHRangeData *pfr = (SPHRangeData *)userdata;
    ParticleData *npa = pfr->npsys->particles + index;
    float q;
    float qfac = 21.0f / (256.f * (float)M_PI);
    float rij, rij_h;
    float vec[3];
  
    /* Exclude particles that are more than 2h away. Can't use squared_dist here
     * because it is not accurate enough. Use current state, i.e. the output of
     * basic_integrate() - z0r */
    sub_v3_v3v3(vec, npa->state.co, co);
    rij = len_v3(vec);
    rij_h = rij / pfr->h;
    if (rij_h > 2.0f) {
      return;
    }
  
    /* Smoothing factor. Utilize the Wendland kernel. gnuplot:
     *     q1(x) = (2.0 - x)**4 * ( 1.0 + 2.0 * x)
     *     plot [0:2] q1(x) */
    q = qfac / pow3f(pfr->h) * pow4f(2.0f - rij_h) * (1.0f + 2.0f * rij_h);
    q *= pfr->npsys->part->mass;
  
    if (pfr->use_size) {
      q *= pfr->pa->size;
    }
  
    pfr->data[0] += q;
    pfr->data[1] += q / npa->sphdensity;
  }
  
  static void sphclassical_neighbor_accum_cb(void *userdata,
                                             int index,
                                             const float co[3],
                                             float UNUSED(squared_dist))
  {
    SPHRangeData *pfr = (SPHRangeData *)userdata;
    ParticleData *npa = pfr->npsys->particles + index;
    float rij, rij_h;
    float vec[3];
  
    if (pfr->tot_neighbors >= SPH_NEIGHBORS) {
      return;
    }
  
    /* Exclude particles that are more than 2h away. Can't use squared_dist here
     * because it is not accurate enough. Use current state, i.e. the output of
     * basic_integrate() - z0r */
    sub_v3_v3v3(vec, npa->state.co, co);
    rij = len_v3(vec);
    rij_h = rij / pfr->h;
    if (rij_h > 2.0f) {
      return;
    }
  
    pfr->neighbors[pfr->tot_neighbors].index = index;
    pfr->neighbors[pfr->tot_neighbors].psys = pfr->npsys;
    pfr->tot_neighbors++;
  }
  static void sphclassical_force_cb(void *sphdata_v,
                                    ParticleKey *state,
                                    float *force,
                                    float *UNUSED(impulse))
  {
    SPHData *sphdata = (SPHData *)sphdata_v;
    ParticleSystem **psys = sphdata->psys;
    ParticleData *pa = sphdata->pa;
    SPHFluidSettings *fluid = psys[0]->part->fluid;
    SPHRangeData pfr;
    SPHNeighbor *pfn;
    float *gravity = sphdata->gravity;
  
    float dq, u, rij, dv[3];
    float pressure, npressure;
  
    float visc = fluid->viscosity_omega;
  
    float interaction_radius;
    float h, hinv;
    /* 4.77 is an experimentally determined density factor */
    float rest_density = fluid->rest_density * (fluid->flag & SPH_FAC_DENSITY ? 4.77f : 1.0f);
  
    /* Use speed of sound squared */
    float stiffness = pow2f(fluid->stiffness_k);
  
    ParticleData *npa;
    float vec[3];
    float co[3];
    float pressureTerm;
  
    int i;
  
    float qfac2 = 42.0f / (256.0f * (float)M_PI);
    float rij_h;
  
    /* 4.0 here is to be consistent with previous formulation/interface */
    interaction_radius = fluid->radius * (fluid->flag & SPH_FAC_RADIUS ? 4.0f * pa->size : 1.0f);
    h = interaction_radius * sphdata->hfac;
    hinv = 1.0f / h;
  
    pfr.h = h;
    pfr.pa = pa;
  
    sph_evaluate_func(
        NULL, psys, state->co, &pfr, interaction_radius, sphclassical_neighbor_accum_cb);
    pressure = stiffness * (pow7f(pa->sphdensity / rest_density) - 1.0f);
  
    /* multiply by mass so that we return a force, not accel */
    qfac2 *= sphdata->mass / pow3f(pfr.h);
  
    pfn = pfr.neighbors;
    for (i = 0; i < pfr.tot_neighbors; i++, pfn++) {
      npa = pfn->psys->particles + pfn->index;
      if (npa == pa) {
        /* we do not contribute to ourselves */
        continue;
      }
  
      /* Find vector to neighbor. Exclude particles that are more than 2h
       * away. Can't use current state here because it may have changed on
       * another thread - so do own mini integration. Unlike basic_integrate,
       * SPH integration depends on neighboring particles. - z0r */
      madd_v3_v3v3fl(co, npa->prev_state.co, npa->prev_state.vel, state->time);
      sub_v3_v3v3(vec, co, state->co);
      rij = normalize_v3(vec);
      rij_h = rij / pfr.h;
      if (rij_h > 2.0f) {
        continue;
      }
  
      npressure = stiffness * (pow7f(npa->sphdensity / rest_density) - 1.0f);
  
      /* First derivative of smoothing factor. Utilize the Wendland kernel.
       * gnuplot:
       *     q2(x) = 2.0 * (2.0 - x)**4 - 4.0 * (2.0 - x)**3 * (1.0 + 2.0 * x)
       *     plot [0:2] q2(x)
       * Particles > 2h away are excluded above. */
      dq = qfac2 * (2.0f * pow4f(2.0f - rij_h) - 4.0f * pow3f(2.0f - rij_h) * (1.0f + 2.0f * rij_h));
  
      if (pfn->psys->part->flag & PART_SIZEMASS) {
        dq *= npa->size;
      }
  
      pressureTerm = pressure / pow2f(pa->sphdensity) + npressure / pow2f(npa->sphdensity);
  
      /* Note that 'minus' is removed, because vec = vecBA, not vecAB.
       * This applies to the viscosity calculation below, too. */
      madd_v3_v3fl(force, vec, pressureTerm * dq);
  
      /* Viscosity */
      if (visc > 0.0f) {
        sub_v3_v3v3(dv, npa->prev_state.vel, pa->prev_state.vel);
        u = dot_v3v3(vec, dv);
        /* Apply parameters */
        u *= -dq * hinv * visc / (0.5f * npa->sphdensity + 0.5f * pa->sphdensity);
        madd_v3_v3fl(force, vec, u);
      }
    }
  
    /* Artificial buoyancy force in negative gravity direction  */
    if (fluid->buoyancy > 0.f && gravity) {
      madd_v3_v3fl(force, gravity, fluid->buoyancy * (pa->sphdensity - rest_density));
    }
  
    if (sphdata->pass == 0 && psys[0]->part->time_flag & PART_TIME_AUTOSF) {
      sph_particle_courant(sphdata, &pfr);
    }
    sphdata->pass++;
  }
  
  static void sphclassical_calc_dens(ParticleData *pa, float UNUSED(dfra), SPHData *sphdata)
  {
    ParticleSystem **psys = sphdata->psys;
    SPHFluidSettings *fluid = psys[0]->part->fluid;
    /* 4.0 seems to be a pretty good value */
    float interaction_radius = fluid->radius *
                               (fluid->flag & SPH_FAC_RADIUS ? 4.0f * psys[0]->part->size : 1.0f);
    SPHRangeData pfr;
    float data[2];
  
    data[0] = 0;
    data[1] = 0;
    pfr.data = data;
    pfr.h = interaction_radius * sphdata->hfac;
    pfr.pa = pa;
    pfr.mass = sphdata->mass;
  
    sph_evaluate_func(
        NULL, psys, pa->state.co, &pfr, interaction_radius, sphclassical_density_accum_cb);
    pa->sphdensity = min_ff(max_ff(data[0], fluid->rest_density * 0.9f), fluid->rest_density * 1.1f);
  }
  
  void psys_sph_init(ParticleSimulationData *sim, SPHData *sphdata)
  {
    ParticleTarget *pt;
    int i;
  
    BLI_buffer_field_init(&sphdata->new_springs, ParticleSpring);
  
    /* Add other coupled particle systems. */
    sphdata->psys[0] = sim->psys;
    for (i = 1, pt = sim->psys->targets.first; i < 10; i++, pt = (pt ? pt->next : NULL)) {
      sphdata->psys[i] = pt ? psys_get_target_system(sim->ob, pt) : NULL;
    }
  
    if (psys_uses_gravity(sim)) {
      sphdata->gravity = sim->scene->physics_settings.gravity;
    }
    else {
      sphdata->gravity = NULL;
    }
    sphdata->eh = sph_springhash_build(sim->psys);
  
    /* These per-particle values should be overridden later, but just for
     * completeness we give them default values now. */
    sphdata->pa = NULL;
    sphdata->mass = 1.0f;
  
    if (sim->psys->part->fluid->solver == SPH_SOLVER_DDR) {
      sphdata->force_cb = sph_force_cb;
      sphdata->density_cb = sph_density_accum_cb;
      sphdata->hfac = 1.0f;
    }
    else {
      /* SPH_SOLVER_CLASSICAL */
      sphdata->force_cb = sphclassical_force_cb;
      sphdata->density_cb = sphclassical_density_accum_cb;
      sphdata->hfac = 0.5f;
    }
  }
  
  static void psys_sph_flush_springs(SPHData *sphdata)
  {
    for (int i = 0; i < sphdata->new_springs.count; i++) {
      /* sph_spring_add is not thread-safe. - z0r */
      sph_spring_add(sphdata->psys[0], &BLI_buffer_at(&sphdata->new_springs, ParticleSpring, i));
    }
  
    BLI_buffer_field_free(&sphdata->new_springs);
  }
  
  void psys_sph_finalize(SPHData *sphdata)
  {
    psys_sph_flush_springs(sphdata);
  
    if (sphdata->eh) {
      BLI_edgehash_free(sphdata->eh, NULL);
      sphdata->eh = NULL;
    }
  }
  
  /* Sample the density field at a point in space. */
  void psys_sph_density(BVHTree *tree, SPHData *sphdata, float co[3], float vars[2])
  {
    ParticleSystem **psys = sphdata->psys;
    SPHFluidSettings *fluid = psys[0]->part->fluid;
    /* 4.0 seems to be a pretty good value */
    float interaction_radius = fluid->radius *
                               (fluid->flag & SPH_FAC_RADIUS ? 4.0f * psys[0]->part->size : 1.0f);
    SPHRangeData pfr;
    float density[2];
  
    density[0] = density[1] = 0.0f;
    pfr.data = density;
    pfr.h = interaction_radius * sphdata->hfac;
    pfr.mass = sphdata->mass;
  
    sph_evaluate_func(tree, psys, co, &pfr, interaction_radius, sphdata->density_cb);
  
    vars[0] = pfr.data[0];
    vars[1] = pfr.data[1];
  }
  
  static void sph_integrate(ParticleSimulationData *sim,
                            ParticleData *pa,
                            float dfra,
                            SPHData *sphdata)
  {
    ParticleSettings *part = sim->psys->part;
    // float timestep = psys_get_timestep(sim); // UNUSED
    float pa_mass = part->mass * (part->flag & PART_SIZEMASS ? pa->size : 1.f);
    float dtime = dfra * psys_get_timestep(sim);
    // int steps = 1; // UNUSED
    float effector_acceleration[3];
  
    sphdata->pa = pa;
    sphdata->mass = pa_mass;
    sphdata->pass = 0;
    // sphdata.element_size and sphdata.flow are set in the callback.
  
    /* restore previous state and treat gravity & effectors as external acceleration*/
    sub_v3_v3v3(effector_acceleration, pa->state.vel, pa->prev_state.vel);
    mul_v3_fl(effector_acceleration, 1.f / dtime);
  
    copy_particle_key(&pa->state, &pa->prev_state, 0);
  
    integrate_particle(part, pa, dtime, effector_acceleration, sphdata->force_cb, sphdata);
  }
  
  /** \} */
  
  /************************************************/
  /*          Basic physics                       */
  /************************************************/
  typedef struct EfData {
    ParticleTexture ptex;
    ParticleSimulationData *sim;
    ParticleData *pa;
  } EfData;
  static void basic_force_cb(void *efdata_v, ParticleKey *state, float *force, float *impulse)
  {
    EfData *efdata = (EfData *)efdata_v;
    ParticleSimulationData *sim = efdata->sim;
    ParticleSettings *part = sim->psys->part;
    ParticleData *pa = efdata->pa;
    EffectedPoint epoint;
    RNG *rng = sim->rng;
  
    /* add effectors */
    pd_point_from_particle(efdata->sim, efdata->pa, state, &epoint);
    if (part->type != PART_HAIR || part->effector_weights->flag & EFF_WEIGHT_DO_HAIR) {
      BKE_effectors_apply(sim->psys->effectors,
                          sim->colliders,
                          part->effector_weights,
                          &epoint,
                          force,
                          NULL,
                          impulse);
    }
  
    mul_v3_fl(force, efdata->ptex.field);
    mul_v3_fl(impulse, efdata->ptex.field);
  
    /* calculate air-particle interaction */
    if (part->dragfac != 0.0f) {
      madd_v3_v3fl(force, state->vel, -part->dragfac * pa->size * pa->size * len_v3(state->vel));
    }
  
    /* brownian force */
    if (part->brownfac != 0.0f) {
      force[0] += (BLI_rng_get_float(rng) - 0.5f) * part->brownfac;
      force[1] += (BLI_rng_get_float(rng) - 0.5f) * part->brownfac;
      force[2] += (BLI_rng_get_float(rng) - 0.5f) * part->brownfac;
    }
  
    if (part->flag & PART_ROT_DYN && epoint.ave) {
      copy_v3_v3(pa->state.ave, epoint.ave);
    }
  }
  /* gathers all forces that effect particles and calculates a new state for the particle */
  static void basic_integrate(ParticleSimulationData *sim, int p, float dfra, float cfra)
  {
    ParticleSettings *part = sim->psys->part;
    ParticleData *pa = sim->psys->particles + p;
    ParticleKey tkey;
    float dtime = dfra * psys_get_timestep(sim), time;
    float *gravity = NULL, gr[3];
    EfData efdata;
  
    psys_get_texture(sim, pa, &efdata.ptex, PAMAP_PHYSICS, cfra);
  
    efdata.pa = pa;
    efdata.sim = sim;
  
    /* add global acceleration (gravitation) */
    if (psys_uses_gravity(sim) &&
        /* normal gravity is too strong for hair so it's disabled by default */
        (part->type != PART_HAIR || part->effector_weights->flag & EFF_WEIGHT_DO_HAIR)) {
      zero_v3(gr);
      madd_v3_v3fl(gr,
                   sim->scene->physics_settings.gravity,
                   part->effector_weights->global_gravity * efdata.ptex.gravity);
      gravity = gr;
    }
  
    /* maintain angular velocity */
    copy_v3_v3(pa->state.ave, pa->prev_state.ave);
  
    integrate_particle(part, pa, dtime, gravity, basic_force_cb, &efdata);
  
    /* damp affects final velocity */
    if (part->dampfac != 0.f) {
      mul_v3_fl(pa->state.vel, 1.f - part->dampfac * efdata.ptex.damp * 25.f * dtime);
    }
  
    // copy_v3_v3(pa->state.ave, states->ave);
  
    /* finally we do guides */
    time = (cfra - pa->time) / pa->lifetime;
    CLAMP(time, 0.0f, 1.0f);
  
    copy_v3_v3(tkey.co, pa->state.co);
    copy_v3_v3(tkey.vel, pa->state.vel);
    tkey.time = pa->state.time;
  
    if (part->type != PART_HAIR) {
      if (do_guides(sim->depsgraph, sim->psys->part, sim->psys->effectors, &tkey, p, time)) {
        copy_v3_v3(pa->state.co, tkey.co);
        /* guides don't produce valid velocity */
        sub_v3_v3v3(pa->state.vel, tkey.co, pa->prev_state.co);
        mul_v3_fl(pa->state.vel, 1.0f / dtime);
        pa->state.time = tkey.time;
      }
    }
  }
  static void basic_rotate(ParticleSettings *part, ParticleData *pa, float dfra, float timestep)
  {
    float rotfac, rot1[4], rot2[4] = {1.0, 0.0, 0.0, 0.0}, dtime = dfra * timestep, extrotfac;
  
    if ((part->flag & PART_ROTATIONS) == 0) {
      unit_qt(pa->state.rot);
      return;
    }
  
    if (part->flag & PART_ROT_DYN) {
      extrotfac = len_v3(pa->state.ave);
    }
    else {
      extrotfac = 0.0f;
    }
  
    if ((part->flag & PART_ROT_DYN) &&
        ELEM(part->avemode, PART_AVE_VELOCITY, PART_AVE_HORIZONTAL, PART_AVE_VERTICAL)) {
      float angle;
      float len1 = len_v3(pa->prev_state.vel);
      float len2 = len_v3(pa->state.vel);
      float vec[3];
  
      if (len1 == 0.0f || len2 == 0.0f) {
        zero_v3(pa->state.ave);
      }
      else {
        cross_v3_v3v3(pa->state.ave, pa->prev_state.vel, pa->state.vel);
        normalize_v3(pa->state.ave);
        angle = dot_v3v3(pa->prev_state.vel, pa->state.vel) / (len1 * len2);
        mul_v3_fl(pa->state.ave, saacos(angle) / dtime);
      }
  
      get_angular_velocity_vector(part->avemode, &pa->state, vec);
      axis_angle_to_quat(rot2, vec, dtime * part->avefac);
    }
  
    rotfac = len_v3(pa->state.ave);
    if (rotfac == 0.0f || (part->flag & PART_ROT_DYN) == 0 || extrotfac == 0.0f) {
      unit_qt(rot1);
    }
    else {
      axis_angle_to_quat(rot1, pa->state.ave, rotfac * dtime);
    }
    mul_qt_qtqt(pa->state.rot, rot1, pa->prev_state.rot);
    mul_qt_qtqt(pa->state.rot, rot2, pa->state.rot);
  
    /* keep rotation quat in good health */
    normalize_qt(pa->state.rot);
  }
  
  /************************************************
   * Collisions
   *
   * The algorithm is roughly:
   *  1. Use a BVH tree to search for faces that a particle may collide with.
   *  2. Use Newton's method to find the exact time at which the collision occurs.
   *     https://en.wikipedia.org/wiki/Newton's_method
   *
   ************************************************/
  #define COLLISION_MIN_RADIUS 0.001f
  #define COLLISION_MIN_DISTANCE 0.0001f
  #define COLLISION_ZERO 0.00001f
  #define COLLISION_INIT_STEP 0.00008f
  typedef float (*NRDistanceFunc)(float *p, float radius, ParticleCollisionElement *pce, float *nor);
  static float nr_signed_distance_to_plane(float *p,
                                           float radius,
                                           ParticleCollisionElement *pce,
                                           float *nor)
  {
    float p0[3], e1[3], e2[3], d;
  
    sub_v3_v3v3(e1, pce->x1, pce->x0);
    sub_v3_v3v3(e2, pce->x2, pce->x0);
    sub_v3_v3v3(p0, p, pce->x0);
  
    cross_v3_v3v3(nor, e1, e2);
    normalize_v3(nor);
  
    d = dot_v3v3(p0, nor);
  
    if (pce->inv_nor == -1) {
      if (d < 0.f) {
        pce->inv_nor = 1;
      }
      else {
        pce->inv_nor = 0;
      }
    }
  
    if (pce->inv_nor == 1) {
      negate_v3(nor);
      d = -d;
    }
  
    return d - radius;
  }
  static float nr_distance_to_edge(float *p,
                                   float radius,
                                   ParticleCollisionElement *pce,
                                   float *UNUSED(nor))
  {
    float v0[3], v1[3], v2[3], c[3];
  
    sub_v3_v3v3(v0, pce->x1, pce->x0);
    sub_v3_v3v3(v1, p, pce->x0);
    sub_v3_v3v3(v2, p, pce->x1);
  
    cross_v3_v3v3(c, v1, v2);
  
    return fabsf(len_v3(c) / len_v3(v0)) - radius;
  }
  static float nr_distance_to_vert(float *p,
                                   float radius,
                                   ParticleCollisionElement *pce,
                                   float *UNUSED(nor))
  {
    return len_v3v3(p, pce->x0) - radius;
  }
  static void collision_interpolate_element(ParticleCollisionElement *pce,
                                            float t,
                                            float fac,
                                            ParticleCollision *col)
  {
    /* t is the current time for newton rhapson */
    /* fac is the starting factor for current collision iteration */
    /* The col->fac's are factors for the particle subframe step start
     * and end during collision modifier step. */
    float f = fac + t * (1.f - fac);
    float mul = col->fac1 + f * (col->fac2 - col->fac1);
    if (pce->tot > 0) {
      madd_v3_v3v3fl(pce->x0, pce->x[0], pce->v[0], mul);
  
      if (pce->tot > 1) {
        madd_v3_v3v3fl(pce->x1, pce->x[1], pce->v[1], mul);
  
        if (pce->tot > 2) {
          madd_v3_v3v3fl(pce->x2, pce->x[2], pce->v[2], mul);
        }
      }
    }
  }
  static void collision_point_velocity(ParticleCollisionElement *pce)
  {
    float v[3];
  
    copy_v3_v3(pce->vel, pce->v[0]);
  
    if (pce->tot > 1) {
      sub_v3_v3v3(v, pce->v[1], pce->v[0]);
      madd_v3_v3fl(pce->vel, v, pce->uv[0]);
  
      if (pce->tot > 2) {
        sub_v3_v3v3(v, pce->v[2], pce->v[0]);
        madd_v3_v3fl(pce->vel, v, pce->uv[1]);
      }
    }
  }
  static float collision_point_distance_with_normal(
      float p[3], ParticleCollisionElement *pce, float fac, ParticleCollision *col, float *nor)
  {
    if (fac >= 0.f) {
      collision_interpolate_element(pce, 0.f, fac, col);
    }
  
    switch (pce->tot) {
      case 1: {
        sub_v3_v3v3(nor, p, pce->x0);
        return normalize_v3(nor);
      }
      case 2: {
        float u, e[3], vec[3];
        sub_v3_v3v3(e, pce->x1, pce->x0);
        sub_v3_v3v3(vec, p, pce->x0);
        u = dot_v3v3(vec, e) / dot_v3v3(e, e);
  
        madd_v3_v3v3fl(nor, vec, e, -u);
        return normalize_v3(nor);
      }
      case 3:
        return nr_signed_distance_to_plane(p, 0.f, pce, nor);
    }
    return 0;
  }
  static void collision_point_on_surface(
      const float p[3], ParticleCollisionElement *pce, float fac, ParticleCollision *col, float *co)
  {
    collision_interpolate_element(pce, 0.f, fac, col);
  
    switch (pce->tot) {
      case 1: {
        sub_v3_v3v3(co, p, pce->x0);
        normalize_v3(co);
        madd_v3_v3v3fl(co, pce->x0, co, col->radius);
        break;
      }
      case 2: {
        float u, e[3], vec[3], nor[3];
        sub_v3_v3v3(e, pce->x1, pce->x0);
        sub_v3_v3v3(vec, p, pce->x0);
        u = dot_v3v3(vec, e) / dot_v3v3(e, e);
  
        madd_v3_v3v3fl(nor, vec, e, -u);
        normalize_v3(nor);
  
        madd_v3_v3v3fl(co, pce->x0, e, pce->uv[0]);
        madd_v3_v3fl(co, nor, col->radius);
        break;
      }
      case 3: {
        float p0[3], e1[3], e2[3], nor[3];
  
        sub_v3_v3v3(e1, pce->x1, pce->x0);
        sub_v3_v3v3(e2, pce->x2, pce->x0);
        sub_v3_v3v3(p0, p, pce->x0);
  
        cross_v3_v3v3(nor, e1, e2);
        normalize_v3(nor);
  
        if (pce->inv_nor == 1) {
          negate_v3(nor);
        }
  
        madd_v3_v3v3fl(co, pce->x0, nor, col->radius);
        madd_v3_v3fl(co, e1, pce->uv[0]);
        madd_v3_v3fl(co, e2, pce->uv[1]);
        break;
      }
    }
  }
  /* find first root in range [0-1] starting from 0 */
  static float collision_newton_rhapson(ParticleCollision *col,
                                        float radius,
                                        ParticleCollisionElement *pce,
                                        NRDistanceFunc distance_func)
  {
    float t0, t1, dt_init, d0, d1, dd, n[3];
    int iter;
  
    pce->inv_nor = -1;
  
    if (col->inv_total_time > 0.0f) {
      /* Initial step size should be small, but not too small or floating point
       * precision errors will appear. - z0r */
      dt_init = COLLISION_INIT_STEP * col->inv_total_time;
    }
    else {
      dt_init = 0.001f;
    }
  
    /* start from the beginning */
    t0 = 0.f;
    collision_interpolate_element(pce, t0, col->f, col);
    d0 = distance_func(col->co1, radius, pce, n);
    t1 = dt_init;
    d1 = 0.f;
  
    for (iter = 0; iter < 10; iter++) {  //, itersum++) {
      /* get current location */
      collision_interpolate_element(pce, t1, col->f, col);
      interp_v3_v3v3(pce->p, col->co1, col->co2, t1);
  
      d1 = distance_func(pce->p, radius, pce, n);
  
      /* particle already inside face, so report collision */
      if (iter == 0 && d0 < 0.f && d0 > -radius) {
        copy_v3_v3(pce->p, col->co1);
        copy_v3_v3(pce->nor, n);
        pce->inside = 1;
        return 0.f;
      }
  
      /* Zero gradient (no movement relative to element). Can't step from
       * here. */
      if (d1 == d0) {
        /* If first iteration, try from other end where the gradient may be
         * greater. Note: code duplicated below. */
        if (iter == 0) {
          t0 = 1.f;
          collision_interpolate_element(pce, t0, col->f, col);
          d0 = distance_func(col->co2, radius, pce, n);
          t1 = 1.0f - dt_init;
          d1 = 0.f;
          continue;
        }
  
        return -1.f;
      }
  
      dd = (t1 - t0) / (d1 - d0);
  
      t0 = t1;
      d0 = d1;
  
      t1 -= d1 * dd;
  
      /* Particle moving away from plane could also mean a strangely rotating
       * face, so check from end. Note: code duplicated above. */
      if (iter == 0 && t1 < 0.f) {
        t0 = 1.f;
        collision_interpolate_element(pce, t0, col->f, col);
        d0 = distance_func(col->co2, radius, pce, n);
        t1 = 1.0f - dt_init;
        d1 = 0.f;
        continue;
      }
      if (iter == 1 && (t1 < -COLLISION_ZERO || t1 > 1.f)) {
        return -1.f;
      }
  
      if (d1 <= COLLISION_ZERO && d1 >= -COLLISION_ZERO) {
        if (t1 >= -COLLISION_ZERO && t1 <= 1.f) {
          if (distance_func == nr_signed_distance_to_plane) {
            copy_v3_v3(pce->nor, n);
          }
  
          CLAMP(t1, 0.f, 1.f);
  
          return t1;
        }
  
        return -1.f;
      }
    }
    return -1.0;
  }
  static int collision_sphere_to_tri(ParticleCollision *col,
                                     float radius,
                                     ParticleCollisionElement *pce,
                                     float *t)
  {
    ParticleCollisionElement *result = &col->pce;
    float ct, u, v;
  
    pce->inv_nor = -1;
    pce->inside = 0;
  
    ct = collision_newton_rhapson(col, radius, pce, nr_signed_distance_to_plane);
  
    if (ct >= 0.f && ct < *t && (result->inside == 0 || pce->inside == 1)) {
      float e1[3], e2[3], p0[3];
      float e1e1, e1e2, e1p0, e2e2, e2p0, inv;
  
      sub_v3_v3v3(e1, pce->x1, pce->x0);
      sub_v3_v3v3(e2, pce->x2, pce->x0);
      /* XXX: add radius correction here? */
      sub_v3_v3v3(p0, pce->p, pce->x0);
  
      e1e1 = dot_v3v3(e1, e1);
      e1e2 = dot_v3v3(e1, e2);
      e1p0 = dot_v3v3(e1, p0);
      e2e2 = dot_v3v3(e2, e2);
      e2p0 = dot_v3v3(e2, p0);
  
      inv = 1.f / (e1e1 * e2e2 - e1e2 * e1e2);
      u = (e2e2 * e1p0 - e1e2 * e2p0) * inv;
      v = (e1e1 * e2p0 - e1e2 * e1p0) * inv;
  
      if (u >= 0.f && u <= 1.f && v >= 0.f && u + v <= 1.f) {
        *result = *pce;
  
        /* normal already calculated in pce */
  
        result->uv[0] = u;
        result->uv[1] = v;
  
        *t = ct;
        return 1;
      }
    }
    return 0;
  }
  static int collision_sphere_to_edges(ParticleCollision *col,
                                       float radius,
                                       ParticleCollisionElement *pce,
                                       float *t)
  {
    ParticleCollisionElement edge[3], *cur = NULL, *hit = NULL;
    ParticleCollisionElement *result = &col->pce;
  
    float ct;
    int i;
  
    for (i = 0; i < 3; i++) {
      cur = edge + i;
      cur->x[0] = pce->x[i];
      cur->x[1] = pce->x[(i + 1) % 3];
      cur->v[0] = pce->v[i];
      cur->v[1] = pce->v[(i + 1) % 3];
      cur->tot = 2;
      cur->inside = 0;
  
      ct = collision_newton_rhapson(col, radius, cur, nr_distance_to_edge);
  
      if (ct >= 0.f && ct < *t) {
        float u, e[3], vec[3];
  
        sub_v3_v3v3(e, cur->x1, cur->x0);
        sub_v3_v3v3(vec, cur->p, cur->x0);
        u = dot_v3v3(vec, e) / dot_v3v3(e, e);
  
        if (u < 0.f || u > 1.f) {
          break;
        }
  
        *result = *cur;
  
        madd_v3_v3v3fl(result->nor, vec, e, -u);
        normalize_v3(result->nor);
  
        result->uv[0] = u;
  
        hit = cur;
        *t = ct;
      }
    }
  
    return hit != NULL;
  }
  static int collision_sphere_to_verts(ParticleCollision *col,
                                       float radius,
                                       ParticleCollisionElement *pce,
                                       float *t)
  {
    ParticleCollisionElement vert[3], *cur = NULL, *hit = NULL;
    ParticleCollisionElement *result = &col->pce;
  
    float ct;
    int i;
  
    for (i = 0; i < 3; i++) {
      cur = vert + i;
      cur->x[0] = pce->x[i];
      cur->v[0] = pce->v[i];
      cur->tot = 1;
      cur->inside = 0;
  
      ct = collision_newton_rhapson(col, radius, cur, nr_distance_to_vert);
  
      if (ct >= 0.f && ct < *t) {
        *result = *cur;
  
        sub_v3_v3v3(result->nor, cur->p, cur->x0);
        normalize_v3(result->nor);
  
        hit = cur;
        *t = ct;
      }
    }
  
    return hit != NULL;
  }
  /* Callback for BVHTree near test */
  void BKE_psys_collision_neartest_cb(void *userdata,
                                      int index,
                                      const BVHTreeRay *ray,
                                      BVHTreeRayHit *hit)
  {
    ParticleCollision *col = (ParticleCollision *)userdata;
    ParticleCollisionElement pce;
    const MVertTri *vt = &col->md->tri[index];
    MVert *x = col->md->x;
    MVert *v = col->md->current_v;
    float t = hit->dist / col->original_ray_length;
    int collision = 0;
  
    pce.x[0] = x[vt->tri[0]].co;
    pce.x[1] = x[vt->tri[1]].co;
    pce.x[2] = x[vt->tri[2]].co;
  
    pce.v[0] = v[vt->tri[0]].co;
    pce.v[1] = v[vt->tri[1]].co;
    pce.v[2] = v[vt->tri[2]].co;
  
    pce.tot = 3;
    pce.inside = 0;
    pce.index = index;
  
    collision = collision_sphere_to_tri(col, ray->radius, &pce, &t);
    if (col->pce.inside == 0) {
      collision += collision_sphere_to_edges(col, ray->radius, &pce, &t);
      collision += collision_sphere_to_verts(col, ray->radius, &pce, &t);
    }
  
    if (collision) {
      hit->dist = col->original_ray_length * t;
      hit->index = index;
  
      collision_point_velocity(&col->pce);
  
      col->hit = col->current;
    }
  }
  static int collision_detect(ParticleData *pa,
                              ParticleCollision *col,
                              BVHTreeRayHit *hit,
                              ListBase *colliders)
  {
    const int raycast_flag = BVH_RAYCAST_DEFAULT & ~(BVH_RAYCAST_WATERTIGHT);
    ColliderCache *coll;
    float ray_dir[3];
  
    if (BLI_listbase_is_empty(colliders)) {
      return 0;
    }
  
    sub_v3_v3v3(ray_dir, col->co2, col->co1);
    hit->index = -1;
    hit->dist = col->original_ray_length = normalize_v3(ray_dir);
    col->pce.inside = 0;
  
    /* even if particle is stationary we want to check for moving colliders */
    /* if hit.dist is zero the bvhtree_ray_cast will just ignore everything */
    if (hit->dist == 0.0f) {
      hit->dist = col->original_ray_length = 0.000001f;
    }
  
    for (coll = colliders->first; coll; coll = coll->next) {
      /* for boids: don't check with current ground object; also skip if permeated */
      bool skip = false;
  
      for (int i = 0; i < col->skip_count; i++) {
        if (coll->ob == col->skip[i]) {
          skip = true;
          break;
        }
      }
  
      if (skip) {
        continue;
      }
  
      /* particles should not collide with emitter at birth */
      if (coll->ob == col->emitter && pa->time < col->cfra && pa->time >= col->old_cfra) {
        continue;
      }
  
      col->current = coll->ob;
      col->md = coll->collmd;
      col->fac1 = (col->old_cfra - coll->collmd->time_x) /
                  (coll->collmd->time_xnew - coll->collmd->time_x);
      col->fac2 = (col->cfra - coll->collmd->time_x) /
                  (coll->collmd->time_xnew - coll->collmd->time_x);
  
      if (col->md && col->md->bvhtree) {
        BLI_bvhtree_ray_cast_ex(col->md->bvhtree,
                                col->co1,
                                ray_dir,
                                col->radius,
                                hit,
                                BKE_psys_collision_neartest_cb,
                                col,
                                raycast_flag);
      }
    }
  
    return hit->index >= 0;
  }
  static int collision_response(ParticleSimulationData *sim,
                                ParticleData *pa,
                                ParticleCollision *col,
                                BVHTreeRayHit *hit,
                                int kill,
                                int dynamic_rotation)
  {
    ParticleCollisionElement *pce = &col->pce;
    PartDeflect *pd = col->hit->pd;
    RNG *rng = sim->rng;
    /* point of collision */
    float co[3];
    /* location factor of collision between this iteration */
    float x = hit->dist / col->original_ray_length;
    /* time factor of collision between timestep */
    float f = col->f + x * (1.0f - col->f);
    /* time since previous collision (in seconds) */
    float dt1 = (f - col->f) * col->total_time;
    /* time left after collision (in seconds) */
    float dt2 = (1.0f - f) * col->total_time;
    /* did particle pass through the collision surface? */
    int through = (BLI_rng_get_float(rng) < pd->pdef_perm) ? 1 : 0;
  
    /* calculate exact collision location */
    interp_v3_v3v3(co, col->co1, col->co2, x);
  
    /* particle dies in collision */
    if (through == 0 && (kill || pd->flag & PDEFLE_KILL_PART)) {
      pa->alive = PARS_DYING;
      pa->dietime = col->old_cfra + (col->cfra - col->old_cfra) * f;
  
      copy_v3_v3(pa->state.co, co);
      interp_v3_v3v3(pa->state.vel, pa->prev_state.vel, pa->state.vel, f);
      interp_qt_qtqt(pa->state.rot, pa->prev_state.rot, pa->state.rot, f);
      interp_v3_v3v3(pa->state.ave, pa->prev_state.ave, pa->state.ave, f);
  
      /* particle is dead so we don't need to calculate further */
      return 0;
    }
    /* figure out velocity and other data after collision */
  
    /* velocity directly before collision to be modified into velocity directly after collision */
    float v0[3];
    /* normal component of v0 */
    float v0_nor[3];
    /* tangential component of v0 */
    float v0_tan[3];
    /* tangential component of collision surface velocity */
    float vc_tan[3];
    float v0_dot, vc_dot;
    float damp = pd->pdef_damp + pd->pdef_rdamp * 2 * (BLI_rng_get_float(rng) - 0.5f);
    float frict = pd->pdef_frict + pd->pdef_rfrict * 2 * (BLI_rng_get_float(rng) - 0.5f);
    float distance, nor[3], dot;
  
    CLAMP(damp, 0.0f, 1.0f);
    CLAMP(frict, 0.0f, 1.0f);
  
    /* get exact velocity right before collision */
    madd_v3_v3v3fl(v0, col->ve1, col->acc, dt1);
  
    /* Convert collider velocity from `1/frame_step` to `1/s` TODO:
     * here we assume 1 frame step for collision modifier. */
    mul_v3_fl(pce->vel, col->inv_timestep);
  
    /* calculate tangential particle velocity */
    v0_dot = dot_v3v3(pce->nor, v0);
    madd_v3_v3v3fl(v0_tan, v0, pce->nor, -v0_dot);
  
    /* calculate tangential collider velocity */
    vc_dot = dot_v3v3(pce->nor, pce->vel);
    madd_v3_v3v3fl(vc_tan, pce->vel, pce->nor, -vc_dot);
  
    /* handle friction effects (tangential and angular velocity) */
    if (frict > 0.0f) {
      /* angular <-> linear velocity */
      if (dynamic_rotation) {
        float vr_tan[3], v1_tan[3], ave[3];
  
        /* linear velocity of particle surface */
        cross_v3_v3v3(vr_tan, pce->nor, pa->state.ave);
        mul_v3_fl(vr_tan, pa->size);
  
        /* change to coordinates that move with the collision plane */
        sub_v3_v3v3(v1_tan, v0_tan, vc_tan);
  
        /* The resulting velocity is a weighted average of particle cm & surface
         * velocity. This weight (related to particle's moment of inertia) could
         * be made a parameter for angular <-> linear conversion.
         */
        madd_v3_v3fl(v1_tan, vr_tan, -0.4);
        mul_v3_fl(v1_tan, 1.0f / 1.4f); /* 1/(1+0.4) */
  
        /* rolling friction is around 0.01 of sliding friction
         * (could be made a parameter) */
        mul_v3_fl(v1_tan, 1.0f - 0.01f * frict);
  
        /* surface_velocity is opposite to cm velocity */
        negate_v3_v3(vr_tan, v1_tan);
  
        /* get back to global coordinates */
        add_v3_v3(v1_tan, vc_tan);
  
        /* convert to angular velocity*/
        cross_v3_v3v3(ave, vr_tan, pce->nor);
        mul_v3_fl(ave, 1.0f / MAX2(pa->size, 0.001f));
  
        /* only friction will cause change in linear & angular velocity */
        interp_v3_v3v3(pa->state.ave, pa->state.ave, ave, frict);
        interp_v3_v3v3(v0_tan, v0_tan, v1_tan, frict);
      }
      else {
        /* just basic friction (unphysical due to the friction model used in Blender) */
        interp_v3_v3v3(v0_tan, v0_tan, vc_tan, frict);
      }
    }
  
    /* Stickiness was possibly added before,
     * so cancel that before calculating new normal velocity.
     * Otherwise particles go flying out of the surface
     * because of high reversed sticky velocity. */
    if (v0_dot < 0.0f) {
      v0_dot += pd->pdef_stickness;
      if (v0_dot > 0.0f) {
        v0_dot = 0.0f;
      }
    }
  
    /* damping and flipping of velocity around normal */
    v0_dot *= 1.0f - damp;
    vc_dot *= through ? damp : 1.0f;
  
    /* calculate normal particle velocity */
    /* special case for object hitting the particle from behind */
    if (through == 0 && ((vc_dot > 0.0f && v0_dot > 0.0f && vc_dot > v0_dot) ||
                         (vc_dot < 0.0f && v0_dot < 0.0f && vc_dot < v0_dot))) {
      mul_v3_v3fl(v0_nor, pce->nor, vc_dot);
    }
    else if (v0_dot > 0.f) {
      mul_v3_v3fl(v0_nor, pce->nor, vc_dot + v0_dot);
    }
    else {
      mul_v3_v3fl(v0_nor, pce->nor, vc_dot + (through ? 1.0f : -1.0f) * v0_dot);
    }
  
    /* combine components together again */
    add_v3_v3v3(v0, v0_nor, v0_tan);
  
    if (col->boid) {
      /* keep boids above ground */
      BoidParticle *bpa = pa->boid;
      if (bpa->data.mode == eBoidMode_OnLand || co[2] <= col->boid_z) {
        co[2] = col->boid_z;
        v0[2] = 0.0f;
      }
    }
  
    /* re-apply acceleration to final location and velocity */
    madd_v3_v3v3fl(pa->state.co, co, v0, dt2);
    madd_v3_v3fl(pa->state.co, col->acc, 0.5f * dt2 * dt2);
    madd_v3_v3v3fl(pa->state.vel, v0, col->acc, dt2);
  
    /* make sure particle stays on the right side of the surface */
    if (!through) {
      distance = collision_point_distance_with_normal(co, pce, -1.f, col, nor);
  
      if (distance < col->radius + COLLISION_MIN_DISTANCE) {
        madd_v3_v3fl(co, nor, col->radius + COLLISION_MIN_DISTANCE - distance);
      }
  
      dot = dot_v3v3(nor, v0);
      if (dot < 0.f) {
        madd_v3_v3fl(v0, nor, -dot);
      }
  
      distance = collision_point_distance_with_normal(pa->state.co, pce, 1.f, col, nor);
  
      if (distance < col->radius + COLLISION_MIN_DISTANCE) {
        madd_v3_v3fl(pa->state.co, nor, col->radius + COLLISION_MIN_DISTANCE - distance);
      }
  
      dot = dot_v3v3(nor, pa->state.vel);
      if (dot < 0.f) {
        madd_v3_v3fl(pa->state.vel, nor, -dot);
      }
    }
  
    /* add stickiness to surface */
    madd_v3_v3fl(pa->state.vel, pce->nor, -pd->pdef_stickness);
  
    /* set coordinates for next iteration */
    copy_v3_v3(col->co1, co);
    copy_v3_v3(col->co2, pa->state.co);
  
    copy_v3_v3(col->ve1, v0);
    copy_v3_v3(col->ve2, pa->state.vel);
  
    col->f = f;
  
    /* if permeability random roll succeeded, disable collider for this sim step */
    if (through) {
      col->skip[col->skip_count++] = col->hit;
    }
  
    return 1;
  }
  static void collision_fail(ParticleData *pa, ParticleCollision *col)
  {
    /* final chance to prevent total failure, so stick to the surface and hope for the best */
    collision_point_on_surface(col->co1, &col->pce, 1.f, col, pa->state.co);
  
    copy_v3_v3(pa->state.vel, col->pce.vel);
    mul_v3_fl(pa->state.vel, col->inv_timestep);
  
    /* printf("max iterations\n"); */
  }
  
  /* Particle - Mesh collision detection and response
   * Features:
   * -friction and damping
   * -angular momentum <-> linear momentum
   * -high accuracy by re-applying particle acceleration after collision
   * -handles moving, rotating and deforming meshes
   * -uses Newton-Rhapson iteration to find the collisions
   * -handles spherical particles and (nearly) point like particles
   */
  static void collision_check(ParticleSimulationData *sim, int p, float dfra, float cfra)
  {
    ParticleSettings *part = sim->psys->part;
    ParticleData *pa = sim->psys->particles + p;
    ParticleCollision col;
    BVHTreeRayHit hit;
    int collision_count = 0;
  
    float timestep = psys_get_timestep(sim);
  
    memset(&col, 0, sizeof(ParticleCollision));
  
    col.total_time = timestep * dfra;
    col.inv_total_time = 1.0f / col.total_time;
    col.inv_timestep = 1.0f / timestep;
  
    col.cfra = cfra;
    col.old_cfra = sim->psys->cfra;
  
    /* get acceleration (from gravity, forcefields etc. to be re-applied in collision response) */
    sub_v3_v3v3(col.acc, pa->state.vel, pa->prev_state.vel);
    mul_v3_fl(col.acc, 1.f / col.total_time);
  
    /* set values for first iteration */
    copy_v3_v3(col.co1, pa->prev_state.co);
    copy_v3_v3(col.co2, pa->state.co);
    copy_v3_v3(col.ve1, pa->prev_state.vel);
    copy_v3_v3(col.ve2, pa->state.vel);
    col.f = 0.0f;
  
    col.radius = ((part->flag & PART_SIZE_DEFL) || (part->phystype == PART_PHYS_BOIDS)) ?
                     pa->size :
                     COLLISION_MIN_RADIUS;
  
    /* override for boids */
    if (part->phystype == PART_PHYS_BOIDS && part->boids->options & BOID_ALLOW_LAND) {
      col.boid = 1;
      col.boid_z = pa->state.co[2];
      col.skip[col.skip_count++] = pa->boid->ground;
    }
  
    /* 10 iterations to catch multiple collisions */
    while (collision_count < PARTICLE_COLLISION_MAX_COLLISIONS) {
      if (collision_detect(pa, &col, &hit, sim->colliders)) {
  
        collision_count++;
  
        if (collision_count == PARTICLE_COLLISION_MAX_COLLISIONS) {
          collision_fail(pa, &col);
        }
        else if (collision_response(
                     sim, pa, &col, &hit, part->flag & PART_DIE_ON_COL, part->flag & PART_ROT_DYN) ==
                 0) {
          return;
        }
      }
      else {
        return;
      }
    }
  }
  /************************************************/
  /*          Hair                                */
  /************************************************/
  /* check if path cache or children need updating and do it if needed */
  static void psys_update_path_cache(ParticleSimulationData *sim,
                                     float cfra,
                                     const bool use_render_params)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    ParticleEditSettings *pset = &sim->scene->toolsettings->particle;
    int distr = 0, alloc = 0, skip = 0;
  
    if ((psys->part->childtype &&
         psys->totchild != psys_get_tot_child(sim->scene, psys, use_render_params)) ||
        psys->recalc & ID_RECALC_PSYS_RESET) {
      alloc = 1;
    }
  
    if (alloc || psys->recalc & ID_RECALC_PSYS_CHILD ||
        (psys->vgroup[PSYS_VG_DENSITY] && (sim->ob && sim->ob->mode & OB_MODE_WEIGHT_PAINT))) {
      distr = 1;
    }
  
    if (distr) {
      if (alloc) {
        realloc_particles(sim, sim->psys->totpart);
      }
  
      if (psys_get_tot_child(sim->scene, psys, use_render_params)) {
        /* don't generate children while computing the hair keys */
        if (!(psys->part->type == PART_HAIR) || (psys->flag & PSYS_HAIR_DONE)) {
          distribute_particles(sim, PART_FROM_CHILD);
  
          if (part->childtype == PART_CHILD_FACES && part->parents != 0.0f) {
            psys_find_parents(sim, use_render_params);
          }
        }
      }
      else {
        psys_free_children(psys);
      }
    }
  
    if ((part->type == PART_HAIR || psys->flag & PSYS_KEYED ||
         psys->pointcache->flag & PTCACHE_BAKED) == 0) {
      skip = 1; /* only hair, keyed and baked stuff can have paths */
    }
    else if (part->ren_as != PART_DRAW_PATH &&
             !(part->type == PART_HAIR && ELEM(part->ren_as, PART_DRAW_OB, PART_DRAW_GR))) {
      skip = 1; /* particle visualization must be set as path */
    }
    else if (DEG_get_mode(sim->depsgraph) != DAG_EVAL_RENDER) {
      if (part->draw_as != PART_DRAW_REND) {
        skip = 1; /* draw visualization */
      }
      else if (psys->pointcache->flag & PTCACHE_BAKING) {
        skip = 1; /* no need to cache paths while baking dynamics */
      }
      else if (psys_in_edit_mode(sim->depsgraph, psys)) {
        if ((pset->flag & PE_DRAW_PART) == 0) {
          skip = 1;
        }
        else if (part->childtype == 0 &&
                 (psys->flag & PSYS_HAIR_DYNAMICS && psys->pointcache->flag & PTCACHE_BAKED) == 0) {
          skip = 1; /* in edit mode paths are needed for child particles and dynamic hair */
        }
      }
    }
  
    if (!skip) {
      psys_cache_paths(sim, cfra, use_render_params);
  
      /* for render, child particle paths are computed on the fly */
      if (part->childtype) {
        if (!psys->totchild) {
          skip = 1;
        }
        else if (psys->part->type == PART_HAIR && (psys->flag & PSYS_HAIR_DONE) == 0) {
          skip = 1;
        }
  
        if (!skip) {
          psys_cache_child_paths(sim, cfra, 0, use_render_params);
        }
      }
    }
    else if (psys->pathcache) {
      psys_free_path_cache(psys, NULL);
    }
  }
  
  static bool psys_hair_use_simulation(ParticleData *pa, float max_length)
  {
    /* Minimum segment length relative to average length.
     * Hairs with segments below this length will be excluded from the simulation,
     * because otherwise the solver will become unstable.
     * The hair system should always make sure the hair segments have reasonable length ratios,
     * but this can happen in old files when e.g. cutting hair.
     */
    const float min_length = 0.1f * max_length;
  
    HairKey *key;
    int k;
  
    if (pa->totkey < 2) {
      return false;
    }
  
    for (k = 1, key = pa->hair + 1; k < pa->totkey; k++, key++) {
      float length = len_v3v3(key->co, (key - 1)->co);
      if (length < min_length) {
        return false;
      }
    }
  
    return true;
  }
  
  static MDeformVert *hair_set_pinning(MDeformVert *dvert, float weight)
  {
    if (dvert) {
      if (!dvert->totweight) {
        dvert->dw = MEM_callocN(sizeof(MDeformWeight), "deformWeight");
        dvert->totweight = 1;
      }
  
      dvert->dw->weight = weight;
      dvert++;
    }
    return dvert;
  }
  
  static void hair_create_input_mesh(ParticleSimulationData *sim,
                                     int totpoint,
                                     int totedge,
                                     Mesh **r_mesh,
                                     ClothHairData **r_hairdata)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    Mesh *mesh;
    ClothHairData *hairdata;
    MVert *mvert;
    MEdge *medge;
    MDeformVert *dvert;
    HairKey *key;
    PARTICLE_P;
    int k, hair_index;
    float hairmat[4][4];
    float max_length;
    float hair_radius;
  
    mesh = *r_mesh;
    if (!mesh) {
      *r_mesh = mesh = BKE_mesh_new_nomain(totpoint, totedge, 0, 0, 0);
      CustomData_add_layer(&mesh->vdata, CD_MDEFORMVERT, CD_CALLOC, NULL, mesh->totvert);
      BKE_mesh_update_customdata_pointers(mesh, false);
    }
    mvert = mesh->mvert;
    medge = mesh->medge;
    dvert = mesh->dvert;
  
    hairdata = *r_hairdata;
    if (!hairdata) {
      *r_hairdata = hairdata = MEM_mallocN(sizeof(ClothHairData) * totpoint, "hair data");
    }
  
    /* calculate maximum segment length */
    max_length = 0.0f;
    LOOP_PARTICLES
    {
      if (!(pa->flag & PARS_UNEXIST)) {
        for (k = 1, key = pa->hair + 1; k < pa->totkey; k++, key++) {
          float length = len_v3v3(key->co, (key - 1)->co);
          if (max_length < length) {
            max_length = length;
          }
        }
      }
    }
  
    psys->clmd->sim_parms->vgroup_mass = 1;
  
    /* XXX placeholder for more flexible future hair settings */
    hair_radius = part->size;
  
    /* make vgroup for pin roots etc.. */
    hair_index = 1;
    LOOP_PARTICLES
    {
      if (!(pa->flag & PARS_UNEXIST)) {
        float root_mat[4][4];
        float bending_stiffness;
        bool use_hair;
  
        pa->hair_index = hair_index;
        use_hair = psys_hair_use_simulation(pa, max_length);
  
        psys_mat_hair_to_object(sim->ob, sim->psmd->mesh_final, psys->part->from, pa, hairmat);
        mul_m4_m4m4(root_mat, sim->ob->obmat, hairmat);
        normalize_m4(root_mat);
  
        bending_stiffness = CLAMPIS(
            1.0f - part->bending_random * psys_frand(psys, p + 666), 0.0f, 1.0f);
  
        for (k = 0, key = pa->hair; k < pa->totkey; k++, key++) {
          ClothHairData *hair;
          float *co, *co_next;
  
          co = key->co;
          co_next = (key + 1)->co;
  
          /* create fake root before actual root to resist bending */
          if (k == 0) {
            hair = &psys->clmd->hairdata[pa->hair_index - 1];
            copy_v3_v3(hair->loc, root_mat[3]);
            copy_m3_m4(hair->rot, root_mat);
  
            hair->radius = hair_radius;
            hair->bending_stiffness = bending_stiffness;
  
            add_v3_v3v3(mvert->co, co, co);
            sub_v3_v3(mvert->co, co_next);
            mul_m4_v3(hairmat, mvert->co);
  
            medge->v1 = pa->hair_index - 1;
            medge->v2 = pa->hair_index;
  
            dvert = hair_set_pinning(dvert, 1.0f);
  
            mvert++;
            medge++;
          }
  
          /* store root transform in cloth data */
          hair = &psys->clmd->hairdata[pa->hair_index + k];
          copy_v3_v3(hair->loc, root_mat[3]);
          copy_m3_m4(hair->rot, root_mat);
  
          hair->radius = hair_radius;
          hair->bending_stiffness = bending_stiffness;
  
          copy_v3_v3(mvert->co, co);
          mul_m4_v3(hairmat, mvert->co);
  
          if (k) {
            medge->v1 = pa->hair_index + k - 1;
            medge->v2 = pa->hair_index + k;
          }
  
          /* roots and disabled hairs should be 1.0, the rest can be anything from 0.0 to 1.0 */
          if (use_hair) {
            dvert = hair_set_pinning(dvert, key->weight);
          }
          else {
            dvert = hair_set_pinning(dvert, 1.0f);
          }
  
          mvert++;
          if (k) {
            medge++;
          }
        }
  
        hair_index += pa->totkey + 1;
      }
    }
  }
  
  static void do_hair_dynamics(ParticleSimulationData *sim)
  {
    ParticleSystem *psys = sim->psys;
    PARTICLE_P;
    EffectorWeights *clmd_effweights;
    int totpoint;
    int totedge;
    float(*deformedVerts)[3];
    bool realloc_roots;
  
    if (!psys->clmd) {
      psys->clmd = (ClothModifierData *)BKE_modifier_new(eModifierType_Cloth);
      psys->clmd->sim_parms->goalspring = 0.0f;
      psys->clmd->sim_parms->flags |= CLOTH_SIMSETTINGS_FLAG_RESIST_SPRING_COMPRESS;
      psys->clmd->coll_parms->flags &= ~CLOTH_COLLSETTINGS_FLAG_SELF;
    }
  
    /* count simulated points */
    totpoint = 0;
    totedge = 0;
    LOOP_PARTICLES
    {
      if (!(pa->flag & PARS_UNEXIST)) {
        /* "out" dm contains all hairs */
        totedge += pa->totkey;
        totpoint += pa->totkey + 1; /* +1 for virtual root point */
      }
    }
  
    /* whether hair root info array has to be reallocated */
    realloc_roots = false;
    if (psys->hair_in_mesh) {
      Mesh *mesh = psys->hair_in_mesh;
      if (totpoint != mesh->totvert || totedge != mesh->totedge) {
        BKE_id_free(NULL, mesh);
        psys->hair_in_mesh = NULL;
        realloc_roots = true;
      }
    }
  
    if (!psys->hair_in_mesh || !psys->clmd->hairdata || realloc_roots) {
      if (psys->clmd->hairdata) {
        MEM_freeN(psys->clmd->hairdata);
        psys->clmd->hairdata = NULL;
      }
    }
  
    hair_create_input_mesh(sim, totpoint, totedge, &psys->hair_in_mesh, &psys->clmd->hairdata);
  
    if (psys->hair_out_mesh) {
      BKE_id_free(NULL, psys->hair_out_mesh);
    }
  
    psys->clmd->point_cache = psys->pointcache;
    /* for hair sim we replace the internal cloth effector weights temporarily
     * to use the particle settings
     */
    clmd_effweights = psys->clmd->sim_parms->effector_weights;
    psys->clmd->sim_parms->effector_weights = psys->part->effector_weights;
  
    BKE_id_copy_ex(NULL, &psys->hair_in_mesh->id, (ID **)&psys->hair_out_mesh, LIB_ID_COPY_LOCALIZE);
    deformedVerts = BKE_mesh_vert_coords_alloc(psys->hair_out_mesh, NULL);
    clothModifier_do(
        psys->clmd, sim->depsgraph, sim->scene, sim->ob, psys->hair_in_mesh, deformedVerts);
    BKE_mesh_vert_coords_apply(psys->hair_out_mesh, deformedVerts);
  
    MEM_freeN(deformedVerts);
  
    /* restore cloth effector weights */
    psys->clmd->sim_parms->effector_weights = clmd_effweights;
  }
  static void hair_step(ParticleSimulationData *sim, float cfra, const bool use_render_params)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    PARTICLE_P;
    float disp = psys_get_current_display_percentage(psys, use_render_params);
  
    LOOP_PARTICLES
    {
      pa->size = part->size;
      if (part->randsize > 0.0f) {
        pa->size *= 1.0f - part->randsize * psys_frand(psys, p + 1);
      }
  
      if (psys_frand(psys, p) > disp) {
        pa->flag |= PARS_NO_DISP;
      }
      else {
        pa->flag &= ~PARS_NO_DISP;
      }
    }
  
    if (psys->recalc & ID_RECALC_PSYS_RESET) {
      /* need this for changing subsurf levels */
      psys_calc_dmcache(sim->ob, sim->psmd->mesh_final, sim->psmd->mesh_original, psys);
  
      if (psys->clmd) {
        cloth_free_modifier(psys->clmd);
      }
    }
  
    /* dynamics with cloth simulation, psys->particles can be NULL with 0 particles T25519. */
    if (psys->part->type == PART_HAIR && psys->flag & PSYS_HAIR_DYNAMICS && psys->particles) {
      do_hair_dynamics(sim);
    }
  
    /* following lines were removed r29079 but cause bug T22811, see report for details */
    psys_update_effectors(sim);
    psys_update_path_cache(sim, cfra, use_render_params);
  
    psys->flag |= PSYS_HAIR_UPDATED;
  }
  
  static void save_hair(ParticleSimulationData *sim, float UNUSED(cfra))
  {
    Object *ob = sim->ob;
    ParticleSystem *psys = sim->psys;
    HairKey *key, *root;
    PARTICLE_P;
  
    invert_m4_m4(ob->imat, ob->obmat);
  
    psys->lattice_deform_data = psys_create_lattice_deform_data(sim);
  
    if (psys->totpart == 0) {
      return;
    }
  
    /* save new keys for elements if needed */
    LOOP_PARTICLES
    {
      /* first time alloc */
      if (pa->totkey == 0 || pa->hair == NULL) {
        pa->hair = MEM_callocN((psys->part->hair_step + 1) * sizeof(HairKey), "HairKeys");
        pa->totkey = 0;
      }
  
      key = root = pa->hair;
      key += pa->totkey;
  
      /* convert from global to geometry space */
      copy_v3_v3(key->co, pa->state.co);
      mul_m4_v3(ob->imat, key->co);
  
      if (pa->totkey) {
        sub_v3_v3(key->co, root->co);
        psys_vec_rot_to_face(sim->psmd->mesh_final, pa, key->co);
      }
  
      key->time = pa->state.time;
  
      key->weight = 1.0f - key->time / 100.0f;
  
      pa->totkey++;
  
      /* Root is always in the origin of hair space
       * so we set it to be so after the last key is saved. */
      if (pa->totkey == psys->part->hair_step + 1) {
        zero_v3(root->co);
      }
    }
  }
  
  /* Code for an adaptive time step based on the Courant-Friedrichs-Lewy
   * condition. */
  static const float MIN_TIMESTEP = 1.0f / 101.0f;
  /* Tolerance of 1.5 means the last subframe neither favors growing nor
   * shrinking (e.g if it were 1.3, the last subframe would tend to be too
   * small). */
  static const float TIMESTEP_EXPANSION_FACTOR = 0.1f;
  static const float TIMESTEP_EXPANSION_TOLERANCE = 1.5f;
  
  /* Calculate the speed of the particle relative to the local scale of the
   * simulation. This should be called once per particle during a simulation
   * step, after the velocity has been updated. element_size defines the scale of
   * the simulation, and is typically the distance to neighboring particles. */
  static void update_courant_num(
      ParticleSimulationData *sim, ParticleData *pa, float dtime, SPHData *sphdata, SpinLock *spin)
  {
    float relative_vel[3];
  
    sub_v3_v3v3(relative_vel, pa->prev_state.vel, sphdata->flow);
  
    const float courant_num = len_v3(relative_vel) * dtime / sphdata->element_size;
    if (sim->courant_num < courant_num) {
      BLI_spin_lock(spin);
      if (sim->courant_num < courant_num) {
        sim->courant_num = courant_num;
      }
      BLI_spin_unlock(spin);
    }
  }
  static float get_base_time_step(ParticleSettings *part)
  {
    return 1.0f / (float)(part->subframes + 1);
  }
  /* Update time step size to suit current conditions. */
  static void update_timestep(ParticleSystem *psys, ParticleSimulationData *sim)
  {
    float dt_target;
    if (sim->courant_num == 0.0f) {
      dt_target = 1.0f;
    }
    else {
      dt_target = psys->dt_frac * (psys->part->courant_target / sim->courant_num);
    }
  
    /* Make sure the time step is reasonable. For some reason, the CLAMP macro
     * doesn't work here. The time step becomes too large. - z0r */
    if (dt_target < MIN_TIMESTEP) {
      dt_target = MIN_TIMESTEP;
    }
    else if (dt_target > get_base_time_step(psys->part)) {
      dt_target = get_base_time_step(psys->part);
    }
  
    /* Decrease time step instantly, but increase slowly. */
    if (dt_target > psys->dt_frac) {
      psys->dt_frac = interpf(dt_target, psys->dt_frac, TIMESTEP_EXPANSION_FACTOR);
    }
    else {
      psys->dt_frac = dt_target;
    }
  }
  
  static float sync_timestep(ParticleSystem *psys, float t_frac)
  {
    /* Sync with frame end if it's close. */
    if (t_frac == 1.0f) {
      return psys->dt_frac;
    }
    if (t_frac + (psys->dt_frac * TIMESTEP_EXPANSION_TOLERANCE) >= 1.0f) {
      return 1.0f - t_frac;
    }
  
    return psys->dt_frac;
  }
  
  /************************************************/
  /*          System Core                         */
  /************************************************/
  
  typedef struct DynamicStepSolverTaskData {
    ParticleSimulationData *sim;
  
    float cfra;
    float timestep;
    float dtime;
  
    SpinLock spin;
  } DynamicStepSolverTaskData;
  
  static void dynamics_step_sphdata_reduce(const void *__restrict UNUSED(userdata),
                                           void *__restrict UNUSED(join_v),
                                           void *__restrict chunk_v)
  {
    SPHData *sphdata = chunk_v;
  
    psys_sph_flush_springs(sphdata);
  }
  
  static void dynamics_step_sph_ddr_task_cb_ex(void *__restrict userdata,
                                               const int p,
                                               const TaskParallelTLS *__restrict tls)
  {
    DynamicStepSolverTaskData *data = userdata;
    ParticleSimulationData *sim = data->sim;
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
  
    SPHData *sphdata = tls->userdata_chunk;
  
    ParticleData *pa;
  
    if ((pa = psys->particles + p)->state.time <= 0.0f) {
      return;
    }
  
    /* do global forces & effectors */
    basic_integrate(sim, p, pa->state.time, data->cfra);
  
    /* actual fluids calculations */
    sph_integrate(sim, pa, pa->state.time, sphdata);
  
    if (sim->colliders) {
      collision_check(sim, p, pa->state.time, data->cfra);
    }
  
    /* SPH particles are not physical particles, just interpolation
     * particles,  thus rotation has not a direct sense for them */
    basic_rotate(part, pa, pa->state.time, data->timestep);
  
    if (part->time_flag & PART_TIME_AUTOSF) {
      update_courant_num(sim, pa, data->dtime, sphdata, &data->spin);
    }
  }
  
  static void dynamics_step_sph_classical_basic_integrate_task_cb_ex(
      void *__restrict userdata, const int p, const TaskParallelTLS *__restrict UNUSED(tls))
  {
    DynamicStepSolverTaskData *data = userdata;
    ParticleSimulationData *sim = data->sim;
    ParticleSystem *psys = sim->psys;
  
    ParticleData *pa;
  
    if ((pa = psys->particles + p)->state.time <= 0.0f) {
      return;
    }
  
    basic_integrate(sim, p, pa->state.time, data->cfra);
  }
  
  static void dynamics_step_sph_classical_calc_density_task_cb_ex(
      void *__restrict userdata, const int p, const TaskParallelTLS *__restrict tls)
  {
    DynamicStepSolverTaskData *data = userdata;
    ParticleSimulationData *sim = data->sim;
    ParticleSystem *psys = sim->psys;
  
    SPHData *sphdata = tls->userdata_chunk;
  
    ParticleData *pa;
  
    if ((pa = psys->particles + p)->state.time <= 0.0f) {
      return;
    }
  
    sphclassical_calc_dens(pa, pa->state.time, sphdata);
  }
  
  static void dynamics_step_sph_classical_integrate_task_cb_ex(void *__restrict userdata,
                                                               const int p,
                                                               const TaskParallelTLS *__restrict tls)
  {
    DynamicStepSolverTaskData *data = userdata;
    ParticleSimulationData *sim = data->sim;
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
  
    SPHData *sphdata = tls->userdata_chunk;
  
    ParticleData *pa;
  
    if ((pa = psys->particles + p)->state.time <= 0.0f) {
      return;
    }
  
    /* actual fluids calculations */
    sph_integrate(sim, pa, pa->state.time, sphdata);
  
    if (sim->colliders) {
      collision_check(sim, p, pa->state.time, data->cfra);
    }
  
    /* SPH particles are not physical particles, just interpolation
     * particles,  thus rotation has not a direct sense for them */
    basic_rotate(part, pa, pa->state.time, data->timestep);
  
    if (part->time_flag & PART_TIME_AUTOSF) {
      update_courant_num(sim, pa, data->dtime, sphdata, &data->spin);
    }
  }
  
  /* unbaked particles are calculated dynamically */
  static void dynamics_step(ParticleSimulationData *sim, float cfra)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    BoidBrainData bbd;
    ParticleTexture ptex;
    PARTICLE_P;
    float timestep;
    /* frame & time changes */
    float dfra, dtime;
    float birthtime, dietime;
  
    /* where have we gone in time since last time */
    dfra = cfra - psys->cfra;
  
    timestep = psys_get_timestep(sim);
    dtime = dfra * timestep;
  
    if (dfra < 0.0f) {
      LOOP_EXISTING_PARTICLES
      {
        psys_get_texture(sim, pa, &ptex, PAMAP_SIZE, cfra);
        pa->size = part->size * ptex.size;
        if (part->randsize > 0.0f) {
          pa->size *= 1.0f - part->randsize * psys_frand(psys, p + 1);
        }
  
        reset_particle(sim, pa, dtime, cfra);
      }
      return;
    }
  
    /* for now do both, boids us 'rng' */
    sim->rng = BLI_rng_new_srandom(31415926 + (int)cfra + psys->seed);
  
    psys_update_effectors(sim);
  
    if (part->type != PART_HAIR) {
      sim->colliders = BKE_collider_cache_create(sim->depsgraph, sim->ob, part->collision_group);
    }
  
    /* initialize physics type specific stuff */
    switch (part->phystype) {
      case PART_PHYS_BOIDS: {
        ParticleTarget *pt = psys->targets.first;
        bbd.sim = sim;
        bbd.part = part;
        bbd.cfra = cfra;
        bbd.dfra = dfra;
        bbd.timestep = timestep;
        bbd.rng = sim->rng;
  
        psys_update_particle_tree(psys, cfra);
  
        boids_precalc_rules(part, cfra);
  
        for (; pt; pt = pt->next) {
          ParticleSystem *psys_target = psys_get_target_system(sim->ob, pt);
          if (psys_target && psys_target != psys) {
            psys_update_particle_tree(psys_target, cfra);
          }
        }
        break;
      }
      case PART_PHYS_FLUID: {
        ParticleTarget *pt = psys->targets.first;
        psys_update_particle_bvhtree(psys, cfra);
  
        for (; pt;
             pt = pt->next) { /* Updating others systems particle tree for fluid-fluid interaction */
          if (pt->ob) {
            psys_update_particle_bvhtree(BLI_findlink(&pt->ob->particlesystem, pt->psys - 1), cfra);
          }
        }
        break;
      }
    }
    /* initialize all particles for dynamics */
    LOOP_SHOWN_PARTICLES
    {
      copy_particle_key(&pa->prev_state, &pa->state, 1);
  
      psys_get_texture(sim, pa, &ptex, PAMAP_SIZE, cfra);
  
      pa->size = part->size * ptex.size;
      if (part->randsize > 0.0f) {
        pa->size *= 1.0f - part->randsize * psys_frand(psys, p + 1);
      }
  
      birthtime = pa->time;
      dietime = pa->dietime;
  
      /* store this, so we can do multiple loops over particles */
      pa->state.time = dfra;
  
      if (dietime <= cfra && psys->cfra < dietime) {
        /* particle dies some time between this and last step */
        pa->state.time = dietime - ((birthtime > psys->cfra) ? birthtime : psys->cfra);
        pa->alive = PARS_DYING;
      }
      else if (birthtime <= cfra && birthtime >= psys->cfra) {
        /* particle is born some time between this and last step*/
        reset_particle(sim, pa, dfra * timestep, cfra);
        pa->alive = PARS_ALIVE;
        pa->state.time = cfra - birthtime;
      }
      else if (dietime < cfra) {
        /* nothing to be done when particle is dead */
      }
  
      /* only reset unborn particles if they're shown or if the particle is born soon*/
      if (pa->alive == PARS_UNBORN &&
          (part->flag & PART_UNBORN || (cfra + psys->pointcache->step > pa->time))) {
        reset_particle(sim, pa, dtime, cfra);
      }
      else if (part->phystype == PART_PHYS_NO) {
        reset_particle(sim, pa, dtime, cfra);
      }
  
      if (ELEM(pa->alive, PARS_ALIVE, PARS_DYING) == 0 ||
          (pa->flag & (PARS_UNEXIST | PARS_NO_DISP))) {
        pa->state.time = -1.f;
      }
    }
  
    switch (part->phystype) {
      case PART_PHYS_NEWTON: {
        LOOP_DYNAMIC_PARTICLES
        {
          /* do global forces & effectors */
          basic_integrate(sim, p, pa->state.time, cfra);
  
          /* deflection */
          if (sim->colliders) {
            collision_check(sim, p, pa->state.time, cfra);
          }
  
          /* rotations */
          basic_rotate(part, pa, pa->state.time, timestep);
        }
        break;
      }
      case PART_PHYS_BOIDS: {
        LOOP_DYNAMIC_PARTICLES
        {
          bbd.goal_ob = NULL;
  
          boid_brain(&bbd, p, pa);
  
          if (pa->alive != PARS_DYING) {
            boid_body(&bbd, pa);
  
            /* deflection */
            if (sim->colliders) {
              collision_check(sim, p, pa->state.time, cfra);
            }
          }
        }
        break;
      }
      case PART_PHYS_FLUID: {
        SPHData sphdata;
        psys_sph_init(sim, &sphdata);
  
        DynamicStepSolverTaskData task_data = {
            .sim = sim,
            .cfra = cfra,
            .timestep = timestep,
            .dtime = dtime,
        };
  
        BLI_spin_init(&task_data.spin);
  
        if (part->fluid->solver == SPH_SOLVER_DDR) {
          /* Apply SPH forces using double-density relaxation algorithm
           * (Clavat et. al.) */
  
          TaskParallelSettings settings;
          BLI_parallel_range_settings_defaults(&settings);
          settings.use_threading = (psys->totpart > 100);
          settings.userdata_chunk = &sphdata;
          settings.userdata_chunk_size = sizeof(sphdata);
          settings.func_reduce = dynamics_step_sphdata_reduce;
          BLI_task_parallel_range(
              0, psys->totpart, &task_data, dynamics_step_sph_ddr_task_cb_ex, &settings);
  
          sph_springs_modify(psys, timestep);
        }
        else {
          /* SPH_SOLVER_CLASSICAL */
          /* Apply SPH forces using classical algorithm (due to Gingold
           * and Monaghan). Note that, unlike double-density relaxation,
           * this algorithm is separated into distinct loops. */
  
          {
            TaskParallelSettings settings;
            BLI_parallel_range_settings_defaults(&settings);
            settings.use_threading = (psys->totpart > 100);
            BLI_task_parallel_range(0,
                                    psys->totpart,
                                    &task_data,
                                    dynamics_step_sph_classical_basic_integrate_task_cb_ex,
                                    &settings);
          }
  
          /* calculate summation density */
          /* Note that we could avoid copying sphdata for each thread here (it's only read here),
           * but doubt this would gain us anything except confusion... */
          {
            TaskParallelSettings settings;
            BLI_parallel_range_settings_defaults(&settings);
            settings.use_threading = (psys->totpart > 100);
            settings.userdata_chunk = &sphdata;
            settings.userdata_chunk_size = sizeof(sphdata);
            settings.func_reduce = dynamics_step_sphdata_reduce;
            BLI_task_parallel_range(0,
                                    psys->totpart,
                                    &task_data,
                                    dynamics_step_sph_classical_calc_density_task_cb_ex,
                                    &settings);
          }
  
          /* do global forces & effectors */
          {
            TaskParallelSettings settings;
            BLI_parallel_range_settings_defaults(&settings);
            settings.use_threading = (psys->totpart > 100);
            settings.userdata_chunk = &sphdata;
            settings.userdata_chunk_size = sizeof(sphdata);
            settings.func_reduce = dynamics_step_sphdata_reduce;
            BLI_task_parallel_range(0,
                                    psys->totpart,
                                    &task_data,
                                    dynamics_step_sph_classical_integrate_task_cb_ex,
                                    &settings);
          }
        }
  
        BLI_spin_end(&task_data.spin);
  
        psys_sph_finalize(&sphdata);
        break;
      }
    }
  
    /* finalize particle state and time after dynamics */
    LOOP_DYNAMIC_PARTICLES
    {
      if (pa->alive == PARS_DYING) {
        pa->alive = PARS_DEAD;
        pa->state.time = pa->dietime;
      }
      else {
        pa->state.time = cfra;
      }
    }
  
    BKE_collider_cache_free(&sim->colliders);
    BLI_rng_free(sim->rng);
    sim->rng = NULL;
  }
  
  static void update_children(ParticleSimulationData *sim, const bool use_render_params)
  {
    if ((sim->psys->part->type == PART_HAIR) && (sim->psys->flag & PSYS_HAIR_DONE) == 0) {
      /* don't generate children while growing hair - waste of time */
      psys_free_children(sim->psys);
    }
    else if (sim->psys->part->childtype) {
      if (sim->psys->totchild != psys_get_tot_child(sim->scene, sim->psys, use_render_params)) {
        distribute_particles(sim, PART_FROM_CHILD);
      }
      else {
        /* Children are up to date, nothing to do. */
      }
    }
    else {
      psys_free_children(sim->psys);
    }
  }
  /* updates cached particles' alive & other flags etc..*/
  static void cached_step(ParticleSimulationData *sim, float cfra, const bool use_render_params)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    ParticleTexture ptex;
    PARTICLE_P;
    float disp, dietime;
  
    psys_update_effectors(sim);
  
    disp = psys_get_current_display_percentage(psys, use_render_params);
  
    LOOP_PARTICLES
    {
      psys_get_texture(sim, pa, &ptex, PAMAP_SIZE, cfra);
      pa->size = part->size * ptex.size;
      if (part->randsize > 0.0f) {
        pa->size *= 1.0f - part->randsize * psys_frand(psys, p + 1);
      }
  
      psys->lattice_deform_data = psys_create_lattice_deform_data(sim);
  
      dietime = pa->dietime;
  
      /* update alive status and push events */
      if (pa->time > cfra) {
        pa->alive = PARS_UNBORN;
        if (part->flag & PART_UNBORN && (psys->pointcache->flag & PTCACHE_EXTERNAL) == 0) {
          reset_particle(sim, pa, 0.0f, cfra);
        }
      }
      else if (dietime <= cfra) {
        pa->alive = PARS_DEAD;
      }
      else {
        pa->alive = PARS_ALIVE;
      }
  
      if (psys->lattice_deform_data) {
        BKE_lattice_deform_data_destroy(psys->lattice_deform_data);
        psys->lattice_deform_data = NULL;
      }
  
      if (psys_frand(psys, p) > disp) {
        pa->flag |= PARS_NO_DISP;
      }
      else {
        pa->flag &= ~PARS_NO_DISP;
      }
    }
  }
  
  static bool particles_has_flip(short parttype)
  {
    return (parttype == PART_FLUID_FLIP);
  }
  
  static bool particles_has_tracer(short parttype)
  {
    return (parttype == PART_FLUID_TRACER);
  }
  
  static bool particles_has_spray(short parttype)
  {
    return ((parttype == PART_FLUID_SPRAY) || (parttype == PART_FLUID_SPRAYFOAM) ||
            (parttype == PART_FLUID_SPRAYFOAMBUBBLE));
  }
  
  static bool particles_has_bubble(short parttype)
  {
    return ((parttype == PART_FLUID_BUBBLE) || (parttype == PART_FLUID_FOAMBUBBLE) ||
            (parttype == PART_FLUID_SPRAYFOAMBUBBLE));
  }
  
  static bool particles_has_foam(short parttype)
  {
    return ((parttype == PART_FLUID_FOAM) || (parttype == PART_FLUID_SPRAYFOAM) ||
            (parttype == PART_FLUID_SPRAYFOAMBUBBLE));
  }
  
  static void particles_fluid_step(ParticleSimulationData *sim,
                                   int cfra,
                                   const bool use_render_params)
  {
    ParticleSystem *psys = sim->psys;
    if (psys->particles) {
      MEM_freeN(psys->particles);
      psys->particles = 0;
      psys->totpart = 0;
    }
  
  #ifndef WITH_FLUID
    UNUSED_VARS(use_render_params, cfra);
  #else
    {
      Object *ob = sim->ob;
      FluidModifierData *fmd = (FluidModifierData *)BKE_modifiers_findby_type(ob,
                                                                              eModifierType_Fluid);
  
      if (fmd && fmd->domain && fmd->domain->fluid) {
        FluidDomainSettings *fds = fmd->domain;
  
        ParticleSettings *part = psys->part;
        ParticleData *pa = NULL;
  
        int p, totpart = 0, tottypepart = 0;
        int flagActivePart, activeParts = 0;
        float posX, posY, posZ, velX, velY, velZ;
        float resX, resY, resZ;
        int upres = 1;
        char debugStrBuffer[256];
        float tmp[3] = {0}, tmp2[3] = {0};
  
        /* Helper variables for scaling. */
        float min[3], max[3], size[3], cell_size_scaled[3], max_size;
  
        /* Sanity check: parts also enabled in fluid domain? */
        if ((particles_has_flip(part->type) &&
             (fds->particle_type & FLUID_DOMAIN_PARTICLE_FLIP) == 0) ||
            (particles_has_spray(part->type) &&
             (fds->particle_type & FLUID_DOMAIN_PARTICLE_SPRAY) == 0) ||
            (particles_has_bubble(part->type) &&
             (fds->particle_type & FLUID_DOMAIN_PARTICLE_BUBBLE) == 0) ||
            (particles_has_foam(part->type) &&
             (fds->particle_type & FLUID_DOMAIN_PARTICLE_FOAM) == 0) ||
            (particles_has_tracer(part->type) &&
             (fds->particle_type & FLUID_DOMAIN_PARTICLE_TRACER) == 0)) {
          BLI_snprintf(debugStrBuffer,
                       sizeof(debugStrBuffer),
                       "particles_fluid_step::error - found particle system that is not enabled in "
                       "fluid domain\n");
          return;
        }
  
        /* Count particle amount. tottypepart is only important for snd particles. */
        if (part->type == PART_FLUID_FLIP) {
          tottypepart = totpart = manta_liquid_get_num_flip_particles(fds->fluid);
        }
        if (particles_has_spray(part->type) || particles_has_bubble(part->type) ||
            particles_has_foam(part->type) || particles_has_tracer(part->type)) {
          totpart = manta_liquid_get_num_snd_particles(fds->fluid);
  
          /* tottypepart is the amount of particles of a snd particle type. */
          for (p = 0; p < totpart; p++) {
            flagActivePart = manta_liquid_get_snd_particle_flag_at(fds->fluid, p);
            if (particles_has_spray(part->type) && (flagActivePart & PARTICLE_TYPE_SPRAY)) {
              tottypepart++;
            }
            if (particles_has_bubble(part->type) && (flagActivePart & PARTICLE_TYPE_BUBBLE)) {
              tottypepart++;
            }
            if (particles_has_foam(part->type) && (flagActivePart & PARTICLE_TYPE_FOAM)) {
              tottypepart++;
            }
            if (particles_has_tracer(part->type) && (flagActivePart & PARTICLE_TYPE_TRACER)) {
              tottypepart++;
            }
          }
        }
        /* Sanity check: no particles present. */
        if (!totpart || !tottypepart) {
          return;
        }
  
        /* How many particles to display? */
        tottypepart = (use_render_params) ? tottypepart : (part->disp * tottypepart) / 100;
  
        part->totpart = tottypepart;
        part->sta = part->end = 1.0f;
        part->lifetime = sim->scene->r.efra + 1;
  
        /* Allocate particles. */
        realloc_particles(sim, part->totpart);
  
        /* Set some randomness when choosing which particles to display. */
        sim->rng = BLI_rng_new_srandom(31415926 + (int)cfra + psys->seed);
        double r, dispProb = (double)part->disp / 100.0;
  
        /* Loop over *all* particles. Will break out of loop before tottypepart amount exceeded. */
        for (p = 0, pa = psys->particles; p < totpart; p++) {
  
          /* Apply some randomness and determine which particles to skip. */
          r = BLI_rng_get_double(sim->rng);
          if (r > dispProb) {
            continue;
          }
  
          /* flag, res, upres, pos, vel for FLIP and snd particles have different getters. */
          if (part->type == PART_FLUID_FLIP) {
            flagActivePart = manta_liquid_get_flip_particle_flag_at(fds->fluid, p);
  
            resX = (float)manta_get_res_x(fds->fluid);
            resY = (float)manta_get_res_y(fds->fluid);
            resZ = (float)manta_get_res_z(fds->fluid);
  
            upres = 1;
  
            posX = manta_liquid_get_flip_particle_position_x_at(fds->fluid, p);
            posY = manta_liquid_get_flip_particle_position_y_at(fds->fluid, p);
            posZ = manta_liquid_get_flip_particle_position_z_at(fds->fluid, p);
  
            velX = manta_liquid_get_flip_particle_velocity_x_at(fds->fluid, p);
            velY = manta_liquid_get_flip_particle_velocity_y_at(fds->fluid, p);
            velZ = manta_liquid_get_flip_particle_velocity_z_at(fds->fluid, p);
          }
          else if (particles_has_spray(part->type) || particles_has_bubble(part->type) ||
                   particles_has_foam(part->type) || particles_has_tracer(part->type)) {
            flagActivePart = manta_liquid_get_snd_particle_flag_at(fds->fluid, p);
  
            resX = (float)manta_liquid_get_particle_res_x(fds->fluid);
            resY = (float)manta_liquid_get_particle_res_y(fds->fluid);
            resZ = (float)manta_liquid_get_particle_res_z(fds->fluid);
  
            upres = manta_liquid_get_particle_upres(fds->fluid);
  
            posX = manta_liquid_get_snd_particle_position_x_at(fds->fluid, p);
            posY = manta_liquid_get_snd_particle_position_y_at(fds->fluid, p);
            posZ = manta_liquid_get_snd_particle_position_z_at(fds->fluid, p);
  
            velX = manta_liquid_get_snd_particle_velocity_x_at(fds->fluid, p);
            velY = manta_liquid_get_snd_particle_velocity_y_at(fds->fluid, p);
            velZ = manta_liquid_get_snd_particle_velocity_z_at(fds->fluid, p);
          }
          else {
            BLI_snprintf(debugStrBuffer,
                         sizeof(debugStrBuffer),
                         "particles_fluid_step::error - unknown particle system type\n");
            return;
          }
  #  if 0
          /* Debugging: Print type of particle system and current particles. */
          printf("system type is %d and particle type is %d\n", part->type, flagActivePart);
  #  endif
  
          /* Type of particle must match current particle system type
           * (only important for snd particles). */
          if ((flagActivePart & PARTICLE_TYPE_SPRAY) && !particles_has_spray(part->type)) {
            continue;
          }
          if ((flagActivePart & PARTICLE_TYPE_BUBBLE) && !particles_has_bubble(part->type)) {
            continue;
          }
          if ((flagActivePart & PARTICLE_TYPE_FOAM) && !particles_has_foam(part->type)) {
            continue;
          }
          if ((flagActivePart & PARTICLE_TYPE_TRACER) && !particles_has_tracer(part->type)) {
            continue;
          }
  #  if 0
          /* Debugging: Print type of particle system and current particles. */
          printf("system type is %d and particle type is %d\n", part->type, flagActivePart);
  #  endif
          /* Particle system has allocated 'tottypepart' particles - so break early before exceeded.
           */
          if (activeParts >= tottypepart) {
            break;
          }
  
          /* Only show active particles, i.e. filter out dead particles that just Mantaflow needs.
           * Mantaflow convention: PARTICLE_TYPE_DELETE == inactive particle. */
          if ((flagActivePart & PARTICLE_TYPE_DELETE) == 0) {
            activeParts++;
  
            /* Use particle system settings for particle size. */
            pa->size = part->size;
            if (part->randsize > 0.0f) {
              pa->size *= 1.0f - part->randsize * psys_frand(psys, p + 1);
            }
  
            /* Get size (dimension) but considering scaling */
            copy_v3_v3(cell_size_scaled, fds->cell_size);
            mul_v3_v3(cell_size_scaled, ob->scale);
            madd_v3fl_v3fl_v3fl_v3i(min, fds->p0, cell_size_scaled, fds->res_min);
            madd_v3fl_v3fl_v3fl_v3i(max, fds->p0, cell_size_scaled, fds->res_max);
            sub_v3_v3v3(size, max, min);
  
            /* Biggest dimension will be used for up-scaling. */
            max_size = MAX3(size[0] / (float)upres, size[1] / (float)upres, size[2] / (float)upres);
  
            /* Set particle position. */
            const float posParticle[3] = {posX, posY, posZ};
            copy_v3_v3(pa->state.co, posParticle);
  
            /* Normalize to unit cube around 0. */
            float resDomain[3] = {resX, resY, resZ};
            mul_v3_fl(resDomain, 0.5f);
            sub_v3_v3(pa->state.co, resDomain);
            mul_v3_fl(pa->state.co, fds->dx);
  
            /* Match domain dimension / size. */
            float scaleAbs[3] = {
                1. / fabsf(ob->scale[0]), 1. / fabsf(ob->scale[1]), 1. / fabsf(ob->scale[2])};
            mul_v3_fl(scaleAbs, max_size);
            mul_v3_v3(pa->state.co, scaleAbs);
  
            /* Match domain scale. */
            mul_m4_v3(ob->obmat, pa->state.co);
  
            /* Add origin offset to particle position. */
            zero_v3(tmp);
            zero_v3(tmp2);
            sub_v3_v3v3(tmp2, fds->p1, fds->p0);
            mul_v3_fl(tmp2, 0.5f);
            add_v3_v3v3(tmp, tmp, fds->p1);
            sub_v3_v3(tmp, tmp2);
            mul_v3_v3(tmp, ob->scale);
            add_v3_v3(pa->state.co, tmp);
  #  if 0
            /* Debugging: Print particle coordinates. */
            printf("pa->state.co[0]: %f, pa->state.co[1]: %f, pa->state.co[2]: %f\n",
            pa->state.co[0], pa->state.co[1], pa->state.co[2]);
  #  endif
            /* Set particle velocity. */
            const float velParticle[3] = {velX, velY, velZ};
            copy_v3_v3(pa->state.vel, velParticle);
            mul_v3_fl(pa->state.vel, fds->dx);
  #  if 0
            /* Debugging: Print particle velocity. */
            printf("pa->state.vel[0]: %f, pa->state.vel[1]: %f, pa->state.vel[2]: %f\n",
            pa->state.vel[0], pa->state.vel[1], pa->state.vel[2]);
  #  endif
            /* Set default angular velocity and particle rotation. */
            zero_v3(pa->state.ave);
            unit_qt(pa->state.rot);
  
            pa->time = 1.f;
            pa->dietime = sim->scene->r.efra + 1;
            pa->lifetime = sim->scene->r.efra;
            pa->alive = PARS_ALIVE;
  
            /* Increasing particle settings pointer only for active particles. */
            pa++;
          }
        }
  #  if 0
        /* Debugging: Print number of active particles. */
        printf("active parts: %d\n", activeParts);
  #  endif
        totpart = psys->totpart = part->totpart = activeParts;
  
        BLI_rng_free(sim->rng);
        sim->rng = NULL;
  
      } /* Fluid sim particles done. */
    }
  #endif /* WITH_FLUID */
  }
  
  static int emit_particles(ParticleSimulationData *sim, PTCacheID *pid, float UNUSED(cfra))
  {
    ParticleSystem *psys = sim->psys;
    int oldtotpart = psys->totpart;
    int totpart = tot_particles(psys, pid);
  
    if (totpart != oldtotpart) {
      realloc_particles(sim, totpart);
    }
  
    return totpart - oldtotpart;
  }
  
  /**
   * Calculates the next state for all particles of the system.
   * In particles code most 'cfra - ending' are frames,
   * 'time - ending' are 'cfra * timestep' (seconds).
   *
   * 1. Emit particles
   * 2. Check cache (if used) and return if frame is cached
   * 3. Do dynamics
   * 4. Save to cache
   */
  static void system_step(ParticleSimulationData *sim, float cfra, const bool use_render_params)
  {
    ParticleSystem *psys = sim->psys;
    ParticleSettings *part = psys->part;
    PointCache *cache = psys->pointcache;
    PTCacheID ptcacheid, *pid = NULL;
    PARTICLE_P;
    float disp, cache_cfra = cfra; /*, *vg_vel= 0, *vg_tan= 0, *vg_rot= 0, *vg_size= 0; */
    int startframe = 0, endframe = 100, oldtotpart = 0;
  
    /* cache shouldn't be used for hair or "continue physics" */
    if (part->type != PART_HAIR) {
      psys_clear_temp_pointcache(psys);
  
      /* set suitable cache range automatically */
      if ((cache->flag & (PTCACHE_BAKING | PTCACHE_BAKED)) == 0) {
        psys_get_pointcache_start_end(sim->scene, psys, &cache->startframe, &cache->endframe);
      }
  
      pid = &ptcacheid;
      BKE_ptcache_id_from_particles(pid, sim->ob, psys);
  
      BKE_ptcache_id_time(pid, sim->scene, 0.0f, &startframe, &endframe, NULL);
  
      /* clear everything on start frame, or when psys needs full reset! */
      if ((cfra == startframe) || (psys->recalc & ID_RECALC_PSYS_RESET)) {
        BKE_ptcache_id_reset(sim->scene, pid, PTCACHE_RESET_OUTDATED);
        BKE_ptcache_validate(cache, startframe);
        cache->flag &= ~PTCACHE_REDO_NEEDED;
      }
  
      CLAMP(cache_cfra, startframe, endframe);
    }
  
    /* 1. emit particles and redo particles if needed */
    oldtotpart = psys->totpart;
    if (emit_particles(sim, pid, cfra) || psys->recalc & ID_RECALC_PSYS_RESET) {
      distribute_particles(sim, part->from);
      initialize_all_particles(sim);
      /* reset only just created particles (on startframe all particles are recreated) */
      reset_all_particles(sim, 0.0, cfra, oldtotpart);
      free_unexisting_particles(sim);
  
      if (psys->fluid_springs) {
        MEM_freeN(psys->fluid_springs);
        psys->fluid_springs = NULL;
      }
  
      psys->tot_fluidsprings = psys->alloc_fluidsprings = 0;
  
      /* flag for possible explode modifiers after this system */
      sim->psmd->flag |= eParticleSystemFlag_Pars;
  
      BKE_ptcache_id_clear(pid, PTCACHE_CLEAR_AFTER, cfra);
    }
  
    /* 2. try to read from the cache */
    if (pid) {
      int cache_result = BKE_ptcache_read(pid, cache_cfra, true);
  
      if (ELEM(cache_result, PTCACHE_READ_EXACT, PTCACHE_READ_INTERPOLATED)) {
        cached_step(sim, cfra, use_render_params);
        update_children(sim, use_render_params);
        psys_update_path_cache(sim, cfra, use_render_params);
  
        BKE_ptcache_validate(cache, (int)cache_cfra);
  
        if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED) {
          BKE_ptcache_write(pid, (int)cache_cfra);
        }
  
        return;
      }
      /* Cache is supposed to be baked, but no data was found so bail out */
      if (cache->flag & PTCACHE_BAKED) {
        psys_reset(psys, PSYS_RESET_CACHE_MISS);
        return;
      }
      if (cache_result == PTCACHE_READ_OLD) {
        psys->cfra = (float)cache->simframe;
        cached_step(sim, psys->cfra, use_render_params);
      }
  
      /* if on second frame, write cache for first frame */
      if (psys->cfra == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact == 0)) {
        BKE_ptcache_write(pid, startframe);
      }
    }
    else {
      BKE_ptcache_invalidate(cache);
    }
  
    /* 3. do dynamics */
    /* set particles to be not calculated TODO: can't work with pointcache */
    disp = psys_get_current_display_percentage(psys, use_render_params);
  
    LOOP_PARTICLES
    {
      if (psys_frand(psys, p) > disp) {
        pa->flag |= PARS_NO_DISP;
      }
      else {
        pa->flag &= ~PARS_NO_DISP;
      }
    }
  
    if (psys->totpart) {
      int dframe, totframesback = 0;
      float t_frac, dt_frac;
  
      /* handle negative frame start at the first frame by doing
       * all the steps before the first frame */
      if ((int)cfra == startframe && part->sta < startframe) {
        totframesback = (startframe - (int)part->sta);
      }
  
      if (!(part->time_flag & PART_TIME_AUTOSF)) {
        /* Constant time step */
        psys->dt_frac = get_base_time_step(part);
      }
      else if ((int)cfra == startframe) {
        /* Variable time step; initialize to sub-frames. */
        psys->dt_frac = get_base_time_step(part);
      }
      else if (psys->dt_frac < MIN_TIMESTEP) {
        /* Variable time step; subsequent frames */
        psys->dt_frac = MIN_TIMESTEP;
      }
  
      for (dframe = -totframesback; dframe <= 0; dframe++) {
        /* simulate each subframe */
        dt_frac = psys->dt_frac;
        for (t_frac = dt_frac; t_frac <= 1.0f; t_frac += dt_frac) {
          sim->courant_num = 0.0f;
          dynamics_step(sim, cfra + dframe + t_frac - 1.f);
          psys->cfra = cfra + dframe + t_frac - 1.f;
  
          if (part->time_flag & PART_TIME_AUTOSF) {
            update_timestep(psys, sim);
          }
          /* Even without AUTOSF dt_frac may not add up to 1.0 due to float precision. */
          dt_frac = sync_timestep(psys, t_frac);
        }
      }
    }
  
    /* 4. only write cache starting from second frame */
    if (pid) {
      BKE_ptcache_validate(cache, (int)cache_cfra);
      if ((int)cache_cfra != startframe) {
        BKE_ptcache_write(pid, (int)cache_cfra);
      }
    }
  
    update_children(sim, use_render_params);
  
    /* cleanup */
    if (psys->lattice_deform_data) {
      BKE_lattice_deform_data_destroy(psys->lattice_deform_data);
      psys->lattice_deform_data = NULL;
    }
  }
  
  /* system type has changed so set sensible defaults and clear non applicable flags */
  void psys_changed_type(Object *ob, ParticleSystem *psys)
  {
    ParticleSettings *part = psys->part;
    PTCacheID pid;
  
    BKE_ptcache_id_from_particles(&pid, ob, psys);
  
    if (part->phystype != PART_PHYS_KEYED) {
      psys->flag &= ~PSYS_KEYED;
    }
  
    if (part->type == PART_HAIR) {
      if (ELEM(part->ren_as, PART_DRAW_NOT, PART_DRAW_PATH, PART_DRAW_OB, PART_DRAW_GR) == 0) {
        part->ren_as = PART_DRAW_PATH;
      }
  
      if (part->distr == PART_DISTR_GRID) {
        part->distr = PART_DISTR_JIT;
      }
  
      if (ELEM(part->draw_as, PART_DRAW_NOT, PART_DRAW_REND, PART_DRAW_PATH) == 0) {
        part->draw_as = PART_DRAW_REND;
      }
  
      CLAMP(part->path_start, 0.0f, 100.0f);
      CLAMP(part->path_end, 0.0f, 100.0f);
  
      BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_ALL, 0);
    }
    else {
      free_hair(ob, psys, 1);
  
      CLAMP(part->path_start, 0.0f, MAX2(100.0f, part->end + part->lifetime));
      CLAMP(part->path_end, 0.0f, MAX2(100.0f, part->end + part->lifetime));
    }
  
    psys_reset(psys, PSYS_RESET_ALL);
  }
  void psys_check_boid_data(ParticleSystem *psys)
  {
    BoidParticle *bpa;
    PARTICLE_P;
  
    pa = psys->particles;
  
    if (!pa) {
      return;
    }
  
    if (psys->part && psys->part->phystype == PART_PHYS_BOIDS) {
      if (!pa->boid) {
        bpa = MEM_callocN(psys->totpart * sizeof(BoidParticle), "Boid Data");
  
        LOOP_PARTICLES
        {
          pa->boid = bpa++;
        }
      }
    }
    else if (pa->boid) {
      MEM_freeN(pa->boid);
      LOOP_PARTICLES
      {
        pa->boid = NULL;
      }
    }
  }
  
  void BKE_particlesettings_fluid_default_settings(ParticleSettings *part)
  {
    SPHFluidSettings *fluid = part->fluid;
  
    fluid->spring_k = 0.f;
    fluid->plasticity_constant = 0.1f;
    fluid->yield_ratio = 0.1f;
    fluid->rest_length = 1.f;
    fluid->viscosity_omega = 2.f;
    fluid->viscosity_beta = 0.1f;
    fluid->stiffness_k = 1.f;
    fluid->stiffness_knear = 1.f;
    fluid->rest_density = 1.f;
    fluid->buoyancy = 0.f;
    fluid->radius = 1.f;
    fluid->flag |= SPH_FAC_REPULSION | SPH_FAC_DENSITY | SPH_FAC_RADIUS | SPH_FAC_VISCOSITY |
                   SPH_FAC_REST_LENGTH;
  }
  
  static void psys_prepare_physics(ParticleSimulationData *sim)
  {
    ParticleSettings *part = sim->psys->part;
  
    if (ELEM(part->phystype, PART_PHYS_NO, PART_PHYS_KEYED)) {
      PTCacheID pid;
      BKE_ptcache_id_from_particles(&pid, sim->ob, sim->psys);
      BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_ALL, 0);
    }
    else {
      free_keyed_keys(sim->psys);
      sim->psys->flag &= ~PSYS_KEYED;
    }
  
    /* RNA Update must ensure this is true. */
    if (part->phystype == PART_PHYS_BOIDS) {
      BLI_assert(part->boids != NULL);
    }
    else if (part->phystype == PART_PHYS_FLUID) {
      BLI_assert(part->fluid != NULL);
    }
  
    psys_check_boid_data(sim->psys);
  }
  static int hair_needs_recalc(ParticleSystem *psys)
  {
    if (!(psys->flag & PSYS_EDITED) && (!psys->edit || !psys->edit->edited) &&
        ((psys->flag & PSYS_HAIR_DONE) == 0 || psys->recalc & ID_RECALC_PSYS_RESET ||
         (psys->part->flag & PART_HAIR_REGROW && !psys->edit))) {
      return 1;
    }
  
    return 0;
  }
  
  static ParticleSettings *particle_settings_localize(ParticleSettings *particle_settings)
  {
    ParticleSettings *particle_settings_local = (ParticleSettings *)BKE_id_copy_ex(
        NULL, (ID *)&particle_settings->id, NULL, LIB_ID_COPY_LOCALIZE);
    return particle_settings_local;
  }
  
  static void particle_settings_free_local(ParticleSettings *particle_settings)
  {
    BKE_libblock_free_datablock(&particle_settings->id, 0);
    BKE_libblock_free_data(&particle_settings->id, false);
    MEM_freeN(particle_settings);
  }
  
  /* main particle update call, checks that things are ok on the large scale and
   * then advances in to actual particle calculations depending on particle type */
  void particle_system_update(struct Depsgraph *depsgraph,
                              Scene *scene,
                              Object *ob,
                              ParticleSystem *psys,
                              const bool use_render_params)
  {
    ParticleSimulationData sim = {0};
    ParticleSettings *part = psys->part;
    ParticleSystem *psys_orig = psys_orig_get(psys);
    float cfra;
    ParticleSystemModifierData *psmd = psys_get_modifier(ob, psys);
  
    /* drawdata is outdated after ANY change */
    if (psys->pdd) {
      psys->pdd->flag &= ~PARTICLE_DRAW_DATA_UPDATED;
    }
  
    if (!psys_check_enabled(ob, psys, use_render_params)) {
      return;
    }
  
    cfra = DEG_get_ctime(depsgraph);
  
    sim.depsgraph = depsgraph;
    sim.scene = scene;
    sim.ob = ob;
    sim.psys = psys;
    sim.psmd = psmd;
  
    /* system was already updated from modifier stack */
    if (sim.psmd->flag & eParticleSystemFlag_psys_updated) {
      sim.psmd->flag &= ~eParticleSystemFlag_psys_updated;
      /* make sure it really was updated to cfra */
      if (psys->cfra == cfra) {
        return;
      }
    }
  
    if (!sim.psmd->mesh_final) {
      return;
    }
  
    if (part->from != PART_FROM_VERT) {
      BKE_mesh_tessface_ensure(sim.psmd->mesh_final);
    }
  
    /* to verify if we need to restore object afterwards */
    psys->flag &= ~PSYS_OB_ANIM_RESTORE;
  
    if (psys->recalc & ID_RECALC_PSYS_RESET) {
      psys->totunexist = 0;
    }
  
    /* setup necessary physics type dependent additional data if it doesn't yet exist */
    psys_prepare_physics(&sim);
  
    if (part->type == PART_HAIR) {
      /* nothing to do so bail out early */
      if (psys->totpart == 0 && part->totpart == 0) {
        psys_free_path_cache(psys, NULL);
        free_hair(ob, psys, 0);
        psys->flag |= PSYS_HAIR_DONE;
      }
      /* (re-)create hair */
      else if (hair_needs_recalc(psys)) {
        float hcfra = 0.0f;
        int i, recalc = psys->recalc;
  
        free_hair(ob, psys, 0);
  
        if (psys_orig->edit && psys_orig->free_edit) {
          psys_orig->free_edit(psys_orig->edit);
          psys_orig->edit = NULL;
          psys_orig->free_edit = NULL;
        }
  
        /* first step is negative so particles get killed and reset */
        psys->cfra = 1.0f;
  
        ParticleSettings *part_local = part;
        if ((part->flag & PART_HAIR_REGROW) == 0) {
          part_local = particle_settings_localize(part);
          psys->part = part_local;
        }
  
        for (i = 0; i <= part->hair_step; i++) {
          hcfra = 100.0f * (float)i / (float)psys->part->hair_step;
          if ((part->flag & PART_HAIR_REGROW) == 0) {
            const AnimationEvalContext anim_eval_context = BKE_animsys_eval_context_construct(
                depsgraph, hcfra);
            BKE_animsys_evaluate_animdata(
                &part_local->id, part_local->adt, &anim_eval_context, ADT_RECALC_ANIM, false);
          }
          system_step(&sim, hcfra, use_render_params);
          psys->cfra = hcfra;
          psys->recalc = 0;
          save_hair(&sim, hcfra);
        }
  
        if (part_local != part) {
          particle_settings_free_local(part_local);
          psys->part = part;
        }
  
        psys->flag |= PSYS_HAIR_DONE;
        psys->recalc = recalc;
      }
      else if (psys->flag & PSYS_EDITED) {
        psys->flag |= PSYS_HAIR_DONE;
      }
  
      if (psys->flag & PSYS_HAIR_DONE) {
        hair_step(&sim, cfra, use_render_params);
      }
    }
    else if (particles_has_flip(part->type) || particles_has_spray(part->type) ||
             particles_has_bubble(part->type) || particles_has_foam(part->type) ||
             particles_has_tracer(part->type)) {
      particles_fluid_step(&sim, (int)cfra, use_render_params);
    }
    else {
      switch (part->phystype) {
        case PART_PHYS_NO:
        case PART_PHYS_KEYED: {
          PARTICLE_P;
          float disp = psys_get_current_display_percentage(psys, use_render_params);
          bool free_unexisting = false;
  
          /* Particles without dynamics haven't been reset yet because they don't use pointcache */
          if (psys->recalc & ID_RECALC_PSYS_RESET) {
            psys_reset(psys, PSYS_RESET_ALL);
          }
  
          if (emit_particles(&sim, NULL, cfra) || (psys->recalc & ID_RECALC_PSYS_RESET)) {
            free_keyed_keys(psys);
            distribute_particles(&sim, part->from);
            initialize_all_particles(&sim);
            free_unexisting = true;
  
            /* flag for possible explode modifiers after this system */
            sim.psmd->flag |= eParticleSystemFlag_Pars;
          }
  
          LOOP_EXISTING_PARTICLES
          {
            pa->size = part->size;
            if (part->randsize > 0.0f) {
              pa->size *= 1.0f - part->randsize * psys_frand(psys, p + 1);
            }
  
            reset_particle(&sim, pa, 0.0, cfra);
  
            if (psys_frand(psys, p) > disp) {
              pa->flag |= PARS_NO_DISP;
            }
            else {
              pa->flag &= ~PARS_NO_DISP;
            }
          }
  
          /* free unexisting after resetting particles */
          if (free_unexisting) {
            free_unexisting_particles(&sim);
          }
  
          if (part->phystype == PART_PHYS_KEYED) {
            psys_count_keyed_targets(&sim);
            set_keyed_keys(&sim);
            psys_update_path_cache(&sim, (int)cfra, use_render_params);
          }
          break;
        }
        default: {
          /* the main dynamic particle system step */
          system_step(&sim, cfra, use_render_params);
          break;
        }
      }
    }
  
    /* make sure emitter is left at correct time (particle emission can change this) */
    if (psys->flag & PSYS_OB_ANIM_RESTORE) {
      evaluate_emitter_anim(depsgraph, scene, ob, cfra);
      psys->flag &= ~PSYS_OB_ANIM_RESTORE;
    }
  
    if (psys_orig->edit) {
      psys_orig->edit->flags |= PT_CACHE_EDIT_UPDATE_PARTICLE_FROM_EVAL;
    }
  
    psys->cfra = cfra;
    psys->recalc = 0;
  
    if (DEG_is_active(depsgraph)) {
      if (psys_orig != psys) {
        if (psys_orig->edit != NULL && psys_orig->edit->psys == psys_orig) {
          psys_orig->edit->psys_eval = psys;
          psys_orig->edit->psmd_eval = psmd;
        }
        psys_orig->flag = (psys->flag & ~PSYS_SHARED_CACHES);
        psys_orig->cfra = psys->cfra;
        psys_orig->recalc = psys->recalc;
        psys_orig->part->totpart = part->totpart;
      }
    }
  
    /* Save matrix for duplicators,
     * at rendertime the actual dupliobject's matrix is used so don't update! */
    invert_m4_m4(psys->imat, ob->obmat);
  
    BKE_particle_batch_cache_dirty_tag(psys, BKE_PARTICLE_BATCH_DIRTY_ALL);
  }
  
  /* ID looper */
  
  void BKE_particlesystem_id_loop(ParticleSystem *psys, ParticleSystemIDFunc func, void *userdata)
  {
    ParticleTarget *pt;
  
    func(psys, (ID **)&psys->part, userdata, IDWALK_CB_USER | IDWALK_CB_NEVER_NULL);
    func(psys, (ID **)&psys->target_ob, userdata, IDWALK_CB_NOP);
    func(psys, (ID **)&psys->parent, userdata, IDWALK_CB_NOP);
  
    for (pt = psys->targets.first; pt; pt = pt->next) {
      func(psys, (ID **)&pt->ob, userdata, IDWALK_CB_NOP);
    }
  
    /* Even though psys->part should never be NULL, this can happen as an exception during deletion.
     * See ID_REMAP_SKIP/FORCE/FLAG_NEVER_NULL_USAGE in BKE_library_remap. */
    if (psys->part && psys->part->phystype == PART_PHYS_BOIDS) {
      ParticleData *pa;
      int p;
  
      for (p = 0, pa = psys->particles; p < psys->totpart; p++, pa++) {
        func(psys, (ID **)&pa->boid->ground, userdata, IDWALK_CB_NOP);
      }
    }
  }
  
  void BKE_particlesystem_reset_all(struct Object *object)
  {
    for (ModifierData *md = object->modifiers.first; md != NULL; md = md->next) {
      if (md->type != eModifierType_ParticleSystem) {
        continue;
      }
      ParticleSystemModifierData *psmd = (ParticleSystemModifierData *)md;
      ParticleSystem *psys = psmd->psys;
      psys->recalc |= ID_RECALC_PSYS_RESET;
    }
  }
  
  /* **** Depsgraph evaluation **** */
  
  void BKE_particle_settings_eval_reset(struct Depsgraph *depsgraph,
                                        ParticleSettings *particle_settings)
  {
    DEG_debug_print_eval(depsgraph, __func__, particle_settings->id.name, particle_settings);
    particle_settings->id.recalc |= ID_RECALC_PSYS_RESET;
  }
  
  void BKE_particle_system_eval_init(struct Depsgraph *depsgraph, Object *object)
  {
    DEG_debug_print_eval(depsgraph, __func__, object->id.name, object);
    for (ParticleSystem *psys = object->particlesystem.first; psys != NULL; psys = psys->next) {
      psys->recalc |= (psys->part->id.recalc & ID_RECALC_PSYS_ALL);
    }
  }
  