/*
 * 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) 2005 by the Blender Foundation.
 * All rights reserved.
 */

/** \file
 * \ingroup modifiers
 */

#include "BLI_utildefines.h"

#include "BLI_math.h"
#include "BLI_task.h"

#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
#include "DNA_object_types.h"
#include "DNA_scene_types.h"

#include "BKE_deform.h"
#include "BKE_editmesh.h"
#include "BKE_global.h"
#include "BKE_lib_id.h"
#include "BKE_lib_query.h"
#include "BKE_mesh.h"
#include "BKE_mesh_runtime.h"
#include "BKE_modifier.h"

#include "MEM_guardedalloc.h"

#include "DEG_depsgraph.h"
#include "DEG_depsgraph_query.h"

#include "MOD_util.h"

#ifdef __SSE2__
#  include <emmintrin.h>
#endif

static void initData(ModifierData *md)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;

  mmd->gridsize = 5;
}

static void freeData(ModifierData *md)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;

  if (mmd->bindinfluences) {
    MEM_freeN(mmd->bindinfluences);
  }
  if (mmd->bindoffsets) {
    MEM_freeN(mmd->bindoffsets);
  }
  if (mmd->bindcagecos) {
    MEM_freeN(mmd->bindcagecos);
  }
  if (mmd->dyngrid) {
    MEM_freeN(mmd->dyngrid);
  }
  if (mmd->dyninfluences) {
    MEM_freeN(mmd->dyninfluences);
  }
  if (mmd->dynverts) {
    MEM_freeN(mmd->dynverts);
  }
  if (mmd->bindweights) {
    MEM_freeN(mmd->bindweights); /* deprecated */
  }
  if (mmd->bindcos) {
    MEM_freeN(mmd->bindcos); /* deprecated */
  }
}

static void copyData(const ModifierData *md, ModifierData *target, const int flag)
{
  const MeshDeformModifierData *mmd = (const MeshDeformModifierData *)md;
  MeshDeformModifierData *tmmd = (MeshDeformModifierData *)target;

  modifier_copyData_generic(md, target, flag);

  if (mmd->bindinfluences) {
    tmmd->bindinfluences = MEM_dupallocN(mmd->bindinfluences);
  }
  if (mmd->bindoffsets) {
    tmmd->bindoffsets = MEM_dupallocN(mmd->bindoffsets);
  }
  if (mmd->bindcagecos) {
    tmmd->bindcagecos = MEM_dupallocN(mmd->bindcagecos);
  }
  if (mmd->dyngrid) {
    tmmd->dyngrid = MEM_dupallocN(mmd->dyngrid);
  }
  if (mmd->dyninfluences) {
    tmmd->dyninfluences = MEM_dupallocN(mmd->dyninfluences);
  }
  if (mmd->dynverts) {
    tmmd->dynverts = MEM_dupallocN(mmd->dynverts);
  }
  if (mmd->bindweights) {
    tmmd->bindweights = MEM_dupallocN(mmd->bindweights); /* deprecated */
  }
  if (mmd->bindcos) {
    tmmd->bindcos = MEM_dupallocN(mmd->bindcos); /* deprecated */
  }
}

static void requiredDataMask(Object *UNUSED(ob),
                             ModifierData *md,
                             CustomData_MeshMasks *r_cddata_masks)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;

  /* ask for vertexgroups if we need them */
  if (mmd->defgrp_name[0] != '\0') {
    r_cddata_masks->vmask |= CD_MASK_MDEFORMVERT;
  }
}

static bool isDisabled(const struct Scene *UNUSED(scene),
                       ModifierData *md,
                       bool UNUSED(useRenderParams))
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;

  /* The object type check is only needed here in case we have a placeholder
   * object assigned (because the library containing the mesh is missing).
   *
   * In other cases it should be impossible to have a type mismatch.
   */
  return !mmd->object || mmd->object->type != OB_MESH;
}

static void foreachObjectLink(ModifierData *md, Object *ob, ObjectWalkFunc walk, void *userData)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;

  walk(userData, ob, &mmd->object, IDWALK_CB_NOP);
}

static void updateDepsgraph(ModifierData *md, const ModifierUpdateDepsgraphContext *ctx)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
  if (mmd->object != NULL) {
    DEG_add_object_relation(ctx->node, mmd->object, DEG_OB_COMP_TRANSFORM, "Mesh Deform Modifier");
    DEG_add_object_relation(ctx->node, mmd->object, DEG_OB_COMP_GEOMETRY, "Mesh Deform Modifier");
  }
  /* We need own transformation as well. */
  DEG_add_modifier_to_transform_relation(ctx->node, "Mesh Deform Modifier");
}

static float meshdeform_dynamic_bind(MeshDeformModifierData *mmd, float (*dco)[3], float vec[3])
{
  MDefCell *cell;
  MDefInfluence *inf;
  float gridvec[3], dvec[3], ivec[3], wx, wy, wz;
  float weight, cageweight, totweight, *cageco;
  int i, j, a, x, y, z, size;
#ifdef __SSE2__
  __m128 co = _mm_setzero_ps();
#else
  float co[3] = {0.0f, 0.0f, 0.0f};
#endif

  totweight = 0.0f;
  size = mmd->dyngridsize;

  for (i = 0; i < 3; i++) {
    gridvec[i] = (vec[i] - mmd->dyncellmin[i] - mmd->dyncellwidth * 0.5f) / mmd->dyncellwidth;
    ivec[i] = (int)gridvec[i];
    dvec[i] = gridvec[i] - ivec[i];
  }

  for (i = 0; i < 8; i++) {
    if (i & 1) {
      x = ivec[0] + 1;
      wx = dvec[0];
    }
    else {
      x = ivec[0];
      wx = 1.0f - dvec[0];
    }

    if (i & 2) {
      y = ivec[1] + 1;
      wy = dvec[1];
    }
    else {
      y = ivec[1];
      wy = 1.0f - dvec[1];
    }

    if (i & 4) {
      z = ivec[2] + 1;
      wz = dvec[2];
    }
    else {
      z = ivec[2];
      wz = 1.0f - dvec[2];
    }

    CLAMP(x, 0, size - 1);
    CLAMP(y, 0, size - 1);
    CLAMP(z, 0, size - 1);

    a = x + y * size + z * size * size;
    weight = wx * wy * wz;

    cell = &mmd->dyngrid[a];
    inf = mmd->dyninfluences + cell->offset;
    for (j = 0; j < cell->totinfluence; j++, inf++) {
      cageco = dco[inf->vertex];
      cageweight = weight * inf->weight;
#ifdef __SSE2__
      {
        __m128 cageweight_r = _mm_set1_ps(cageweight);
        /* This will load one extra element, this is ok because
         * we ignore that part of register anyway.
         */
        __m128 cageco_r = _mm_loadu_ps(cageco);
        co = _mm_add_ps(co, _mm_mul_ps(cageco_r, cageweight_r));
      }
#else
      co[0] += cageweight * cageco[0];
      co[1] += cageweight * cageco[1];
      co[2] += cageweight * cageco[2];
#endif
      totweight += cageweight;
    }
  }

#ifdef __SSE2__
  copy_v3_v3(vec, (float *)&co);
#else
  copy_v3_v3(vec, co);
#endif

  return totweight;
}

typedef struct MeshdeformUserdata {
  /*const*/ MeshDeformModifierData *mmd;
  const MDeformVert *dvert;
  /*const*/ float (*dco)[3];
  int defgrp_index;
  float (*vertexCos)[3];
  float (*cagemat)[4];
  float (*icagemat)[3];
} MeshdeformUserdata;

static void meshdeform_vert_task(void *__restrict userdata,
                                 const int iter,
                                 const TaskParallelTLS *__restrict UNUSED(tls))
{
  MeshdeformUserdata *data = userdata;
  /*const*/ MeshDeformModifierData *mmd = data->mmd;
  const MDeformVert *dvert = data->dvert;
  const int defgrp_index = data->defgrp_index;
  const int *offsets = mmd->bindoffsets;
  const MDefInfluence *__restrict influences = mmd->bindinfluences;
  /*const*/ float(*__restrict dco)[3] = data->dco;
  float(*vertexCos)[3] = data->vertexCos;
  float co[3];
  float weight, totweight, fac = 1.0f;

  if (mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
    if (!mmd->dynverts[iter]) {
      return;
    }
  }

  if (dvert) {
    fac = BKE_defvert_find_weight(&dvert[iter], defgrp_index);

    if (mmd->flag & MOD_MDEF_INVERT_VGROUP) {
      fac = 1.0f - fac;
    }

    if (fac <= 0.0f) {
      return;
    }
  }

  if (mmd->flag & MOD_MDEF_DYNAMIC_BIND) {
    /* transform coordinate into cage's local space */
    mul_v3_m4v3(co, data->cagemat, vertexCos[iter]);
    totweight = meshdeform_dynamic_bind(mmd, dco, co);
  }
  else {
    totweight = 0.0f;
    zero_v3(co);
    int start = offsets[iter];
    int end = offsets[iter + 1];

    for (int a = start; a < end; a++) {
      weight = influences[a].weight;
      madd_v3_v3fl(co, dco[influences[a].vertex], weight);
      totweight += weight;
    }
  }

  if (totweight > 0.0f) {
    mul_v3_fl(co, fac / totweight);
    mul_m3_v3(data->icagemat, co);
    if (G.debug_value != 527) {
      add_v3_v3(vertexCos[iter], co);
    }
    else {
      copy_v3_v3(vertexCos[iter], co);
    }
  }
}

static void meshdeformModifier_do(ModifierData *md,
                                  const ModifierEvalContext *ctx,
                                  Mesh *mesh,
                                  float (*vertexCos)[3],
                                  int numVerts)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
  Object *ob = ctx->object;

  Mesh *cagemesh;
  MDeformVert *dvert = NULL;
  float imat[4][4], cagemat[4][4], iobmat[4][4], icagemat[3][3], cmat[4][4];
  float co[3], (*dco)[3] = NULL, (*bindcagecos)[3];
  int a, totvert, totcagevert, defgrp_index;
  float(*cagecos)[3] = NULL;
  MeshdeformUserdata data;

  static int recursive_bind_sentinel = 0;

  if (mmd->object == NULL || (mmd->bindcagecos == NULL && mmd->bindfunc == NULL)) {
    return;
  }

  /* Get cage mesh.
   *
   * Only do this is the target object is in edit mode by itself, meaning
   * we don't allow linked edit meshes here.
   * This is because editbmesh_get_mesh_cage_and_final() might easily
   * conflict with the thread which evaluates object which is in the edit
   * mode for this mesh.
   *
   * We'll support this case once granular dependency graph is landed.
   */
  Object *ob_target = mmd->object;
  cagemesh = BKE_modifier_get_evaluated_mesh_from_evaluated_object(ob_target, false);
  if (cagemesh == NULL) {
    modifier_setError(md, "Cannot get mesh from cage object");
    return;
  }

  /* compute matrices to go in and out of cage object space */
  invert_m4_m4(imat, ob_target->obmat);
  mul_m4_m4m4(cagemat, imat, ob->obmat);
  mul_m4_m4m4(cmat, mmd->bindmat, cagemat);
  invert_m4_m4(iobmat, cmat);
  copy_m3_m4(icagemat, iobmat);

  /* bind weights if needed */
  if (!mmd->bindcagecos) {
    /* progress bar redraw can make this recursive .. */
    if (!DEG_is_active(ctx->depsgraph)) {
      modifier_setError(md, "Attempt to bind from inactive dependency graph");
      goto finally;
    }
    if (!recursive_bind_sentinel) {
      recursive_bind_sentinel = 1;
      mmd->bindfunc(mmd, cagemesh, (float *)vertexCos, numVerts, cagemat);
      recursive_bind_sentinel = 0;
    }

    goto finally;
  }

  /* verify we have compatible weights */
  totvert = numVerts;
  totcagevert = cagemesh->totvert;

  if (mmd->totvert != totvert) {
    modifier_setError(md, "Verts changed from %d to %d", mmd->totvert, totvert);
    goto finally;
  }
  else if (mmd->totcagevert != totcagevert) {
    modifier_setError(md, "Cage verts changed from %d to %d", mmd->totcagevert, totcagevert);
    goto finally;
  }
  else if (mmd->bindcagecos == NULL) {
    modifier_setError(md, "Bind data missing");
    goto finally;
  }

  /* setup deformation data */
  cagecos = BKE_mesh_vert_coords_alloc(cagemesh, NULL);
  bindcagecos = (float(*)[3])mmd->bindcagecos;

  /* We allocate 1 element extra to make it possible to
   * load the values to SSE registers, which are float4.
   */
  dco = MEM_calloc_arrayN((totcagevert + 1), sizeof(*dco), "MDefDco");
  zero_v3(dco[totcagevert]);
  for (a = 0; a < totcagevert; a++) {
    /* get cage vertex in world space with binding transform */
    copy_v3_v3(co, cagecos[a]);

    if (G.debug_value != 527) {
      mul_m4_v3(mmd->bindmat, co);
      /* compute difference with world space bind coord */
      sub_v3_v3v3(dco[a], co, bindcagecos[a]);
    }
    else {
      copy_v3_v3(dco[a], co);
    }
  }

  MOD_get_vgroup(ob, mesh, mmd->defgrp_name, &dvert, &defgrp_index);

  /* Initialize data to be pass to the for body function. */
  data.mmd = mmd;
  data.dvert = dvert;
  data.dco = dco;
  data.defgrp_index = defgrp_index;
  data.vertexCos = vertexCos;
  data.cagemat = cagemat;
  data.icagemat = icagemat;

  /* Do deformation. */
  TaskParallelSettings settings;
  BLI_parallel_range_settings_defaults(&settings);
  settings.min_iter_per_thread = 16;
  BLI_task_parallel_range(0, totvert, &data, meshdeform_vert_task, &settings);

finally:
  MEM_SAFE_FREE(dco);
  MEM_SAFE_FREE(cagecos);
}

static void deformVerts(ModifierData *md,
                        const ModifierEvalContext *ctx,
                        Mesh *mesh,
                        float (*vertexCos)[3],
                        int numVerts)
{
  Mesh *mesh_src = MOD_deform_mesh_eval_get(ctx->object, NULL, mesh, NULL, numVerts, false, false);

  MOD_previous_vcos_store(md, vertexCos); /* if next modifier needs original vertices */

  meshdeformModifier_do(md, ctx, mesh_src, vertexCos, numVerts);

  if (!ELEM(mesh_src, NULL, mesh)) {
    BKE_id_free(NULL, mesh_src);
  }
}

static void deformVertsEM(ModifierData *md,
                          const ModifierEvalContext *ctx,
                          struct BMEditMesh *editData,
                          Mesh *mesh,
                          float (*vertexCos)[3],
                          int numVerts)
{
  Mesh *mesh_src = MOD_deform_mesh_eval_get(
      ctx->object, editData, mesh, NULL, numVerts, false, false);

  meshdeformModifier_do(md, ctx, mesh_src, vertexCos, numVerts);

  if (!ELEM(mesh_src, NULL, mesh)) {
    BKE_id_free(NULL, mesh_src);
  }
}

#define MESHDEFORM_MIN_INFLUENCE 0.00001f

void modifier_mdef_compact_influences(ModifierData *md)
{
  MeshDeformModifierData *mmd = (MeshDeformModifierData *)md;
  float weight, *weights, totweight;
  int totinfluence, totvert, totcagevert, a, b;

  weights = mmd->bindweights;
  if (!weights) {
    return;
  }

  totvert = mmd->totvert;
  totcagevert = mmd->totcagevert;

  /* count number of influences above threshold */
  for (b = 0; b < totvert; b++) {
    for (a = 0; a < totcagevert; a++) {
      weight = weights[a + b * totcagevert];

      if (weight > MESHDEFORM_MIN_INFLUENCE) {
        mmd->totinfluence++;
      }
    }
  }

  /* allocate bind influences */
  mmd->bindinfluences = MEM_calloc_arrayN(
      mmd->totinfluence, sizeof(MDefInfluence), "MDefBindInfluence");
  mmd->bindoffsets = MEM_calloc_arrayN((totvert + 1), sizeof(int), "MDefBindOffset");

  /* write influences */
  totinfluence = 0;

  for (b = 0; b < totvert; b++) {
    mmd->bindoffsets[b] = totinfluence;
    totweight = 0.0f;

    /* sum total weight */
    for (a = 0; a < totcagevert; a++) {
      weight = weights[a + b * totcagevert];

      if (weight > MESHDEFORM_MIN_INFLUENCE) {
        totweight += weight;
      }
    }

    /* assign weights normalized */
    for (a = 0; a < totcagevert; a++) {
      weight = weights[a + b * totcagevert];

      if (weight > MESHDEFORM_MIN_INFLUENCE) {
        mmd->bindinfluences[totinfluence].weight = weight / totweight;
        mmd->bindinfluences[totinfluence].vertex = a;
        totinfluence++;
      }
    }
  }

  mmd->bindoffsets[b] = totinfluence;

  /* free */
  MEM_freeN(mmd->bindweights);
  mmd->bindweights = NULL;
}

ModifierTypeInfo modifierType_MeshDeform = {
    /* name */ "MeshDeform",
    /* structName */ "MeshDeformModifierData",
    /* structSize */ sizeof(MeshDeformModifierData),
    /* type */ eModifierTypeType_OnlyDeform,
    /* flags */ eModifierTypeFlag_AcceptsCVs | eModifierTypeFlag_AcceptsLattice |
        eModifierTypeFlag_SupportsEditmode,

    /* copyData */ copyData,

    /* deformVerts */ deformVerts,
    /* deformMatrices */ NULL,
    /* deformVertsEM */ deformVertsEM,
    /* deformMatricesEM */ NULL,
    /* applyModifier */ NULL,

    /* initData */ initData,
    /* requiredDataMask */ requiredDataMask,
    /* freeData */ freeData,
    /* isDisabled */ isDisabled,
    /* updateDepsgraph */ updateDepsgraph,
    /* dependsOnTime */ NULL,
    /* dependsOnNormals */ NULL,
    /* foreachObjectLink */ foreachObjectLink,
    /* foreachIDLink */ NULL,
    /* foreachTexLink */ NULL,
    /* freeRuntimeData */ NULL,
};
