/*
 * 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) 2017, Blender Foundation
 * This is a new part of Blender
 */

/** \file
 * \ingroup modifiers
 */

#include <stdio.h>

#include "MEM_guardedalloc.h"

#include "BLI_utildefines.h"

#include "BLI_blenlib.h"
#include "BLI_math.h"

#include "BLT_translation.h"

#include "DNA_gpencil_modifier_types.h"
#include "DNA_gpencil_types.h"
#include "DNA_meshdata_types.h"
#include "DNA_object_types.h"
#include "DNA_scene_types.h"
#include "DNA_screen_types.h"

#include "BKE_context.h"
#include "BKE_gpencil.h"
#include "BKE_gpencil_geom.h"
#include "BKE_gpencil_modifier.h"
#include "BKE_screen.h"

#include "UI_interface.h"
#include "UI_resources.h"

#include "RNA_access.h"

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

#include "MOD_gpencil_modifiertypes.h"
#include "MOD_gpencil_ui_common.h"
#include "MOD_gpencil_util.h"

static void initData(GpencilModifierData *md)
{
  BuildGpencilModifierData *gpmd = (BuildGpencilModifierData *)md;

  /* We deliberately set this range to the half the default
   * frame-range to have an immediate effect to suggest use-cases
   */
  gpmd->start_frame = 1;
  gpmd->end_frame = 125;

  /* Init default length of each build effect - Nothing special */
  gpmd->start_delay = 0.0f;
  gpmd->length = 100.0f;
}

static void copyData(const GpencilModifierData *md, GpencilModifierData *target)
{
  BKE_gpencil_modifier_copydata_generic(md, target);
}

static bool dependsOnTime(GpencilModifierData *UNUSED(md))
{
  return true;
}

/* ******************************************** */
/* Build Modifier - Stroke generation logic
 *
 * There are two modes for how the strokes are sequenced (at a macro-level):
 * - Sequential Mode - Strokes appear/disappear one after the other. Only a single one changes at a
 * time.
 * - Concurrent Mode - Multiple strokes appear/disappear at once.
 *
 * Assumptions:
 * - Stroke points are generally equally spaced. This implies that we can just add/remove points,
 *   without worrying about distances between them / adding extra interpolated points between
 *   an visible point and one about to be added/removed (or any similar tapering effects).
 *
 * - All strokes present are fully visible (i.e. we don't have to ignore any)
 */

/* Remove a particular stroke */
static void clear_stroke(bGPDframe *gpf, bGPDstroke *gps)
{
  BLI_remlink(&gpf->strokes, gps);
  BKE_gpencil_free_stroke(gps);
}

/* Clear all strokes in frame */
static void gpf_clear_all_strokes(bGPDframe *gpf)
{
  bGPDstroke *gps, *gps_next;
  for (gps = gpf->strokes.first; gps; gps = gps_next) {
    gps_next = gps->next;
    clear_stroke(gpf, gps);
  }
  BLI_listbase_clear(&gpf->strokes);
}

/* Reduce the number of points in the stroke
 *
 * Note: This won't be called if all points are present/removed
 */
static void reduce_stroke_points(bGPDstroke *gps,
                                 const int num_points,
                                 const eBuildGpencil_Transition transition)
{
  bGPDspoint *new_points = MEM_callocN(sizeof(bGPDspoint) * num_points, __func__);
  MDeformVert *new_dvert = NULL;
  if ((gps->dvert != NULL) && (num_points > 0)) {
    new_dvert = MEM_callocN(sizeof(MDeformVert) * num_points, __func__);
  }

  /* Which end should points be removed from */
  switch (transition) {
    case GP_BUILD_TRANSITION_GROW:   /* Show in forward order =
                                      * Remove ungrown-points from end of stroke. */
    case GP_BUILD_TRANSITION_SHRINK: /* Hide in reverse order =
                                      * Remove dead-points from end of stroke. */
    {
      /* copy over point data */
      memcpy(new_points, gps->points, sizeof(bGPDspoint) * num_points);
      if ((gps->dvert != NULL) && (num_points > 0)) {
        memcpy(new_dvert, gps->dvert, sizeof(MDeformVert) * num_points);

        /* free unused point weights */
        for (int i = num_points; i < gps->totpoints; i++) {
          MDeformVert *dvert = &gps->dvert[i];
          BKE_gpencil_free_point_weights(dvert);
        }
      }
      break;
    }

    /* Hide in forward order = Remove points from start of stroke */
    case GP_BUILD_TRANSITION_FADE: {
      /* num_points is the number of points left after reducing.
       * We need to know how many to remove
       */
      const int offset = gps->totpoints - num_points;

      /* copy over point data */
      memcpy(new_points, gps->points + offset, sizeof(bGPDspoint) * num_points);
      if ((gps->dvert != NULL) && (num_points > 0)) {
        memcpy(new_dvert, gps->dvert + offset, sizeof(MDeformVert) * num_points);

        /* free unused weights */
        for (int i = 0; i < offset; i++) {
          MDeformVert *dvert = &gps->dvert[i];
          BKE_gpencil_free_point_weights(dvert);
        }
      }
      break;
    }

    default:
      printf("ERROR: Unknown transition %d in %s()\n", (int)transition, __func__);
      break;
  }

  /* replace stroke geometry */
  MEM_SAFE_FREE(gps->points);
  MEM_SAFE_FREE(gps->dvert);
  gps->points = new_points;
  gps->dvert = new_dvert;
  gps->totpoints = num_points;

  /* Calc geometry data. */
  BKE_gpencil_stroke_geometry_update(gps);
}

/* --------------------------------------------- */

/* Stroke Data Table Entry - This represents one stroke being generated */
typedef struct tStrokeBuildDetails {
  bGPDstroke *gps;

  /* Indices - first/last indices for the stroke's points (overall) */
  size_t start_idx, end_idx;

  /* Number of points - Cache for more convenient access */
  int totpoints;
} tStrokeBuildDetails;

/* Sequential - Show strokes one after the other */
static void build_sequential(BuildGpencilModifierData *mmd, bGPDframe *gpf, float fac)
{
  const size_t tot_strokes = BLI_listbase_count(&gpf->strokes);
  bGPDstroke *gps;
  size_t i;

  /* 1) Compute proportion of time each stroke should occupy */
  /* NOTE: This assumes that the total number of points won't overflow! */
  tStrokeBuildDetails *table = MEM_callocN(sizeof(tStrokeBuildDetails) * tot_strokes, __func__);
  size_t totpoints = 0;

  /* 1.1) First pass - Tally up points */
  for (gps = gpf->strokes.first, i = 0; gps; gps = gps->next, i++) {
    tStrokeBuildDetails *cell = &table[i];

    cell->gps = gps;
    cell->totpoints = gps->totpoints;

    totpoints += cell->totpoints;
  }

  /* 1.2) Second pass - Compute the overall indices for points */
  for (i = 0; i < tot_strokes; i++) {
    tStrokeBuildDetails *cell = &table[i];

    if (i == 0) {
      cell->start_idx = 0;
    }
    else {
      cell->start_idx = (cell - 1)->end_idx;
    }
    cell->end_idx = cell->start_idx + cell->totpoints - 1;
  }

  /* 2) Determine the global indices for points that should be visible */
  size_t first_visible = 0;
  size_t last_visible = 0;

  switch (mmd->transition) {
    /* Show in forward order
     *  - As fac increases, the number of visible points increases
     */
    case GP_BUILD_TRANSITION_GROW:
      first_visible = 0; /* always visible */
      last_visible = (size_t)roundf(totpoints * fac);
      break;

    /* Hide in reverse order
     *  - As fac increases, the number of points visible at the end decreases
     */
    case GP_BUILD_TRANSITION_SHRINK:
      first_visible = 0; /* always visible (until last point removed) */
      last_visible = (size_t)(totpoints * (1.0f - fac));
      break;

    /* Hide in forward order
     *  - As fac increases, the early points start getting hidden
     */
    case GP_BUILD_TRANSITION_FADE:
      first_visible = (size_t)(totpoints * fac);
      last_visible = totpoints; /* i.e. visible until the end, unless first overlaps this */
      break;
  }

  /* 3) Go through all strokes, deciding which to keep, and/or how much of each to keep */
  for (i = 0; i < tot_strokes; i++) {
    tStrokeBuildDetails *cell = &table[i];

    /* Determine what portion of the stroke is visible */
    if ((cell->end_idx < first_visible) || (cell->start_idx > last_visible)) {
      /* Not visible at all - Either ended before */
      clear_stroke(gpf, cell->gps);
    }
    else {
      /* Some proportion of stroke is visible */
      if ((first_visible <= cell->start_idx) && (last_visible >= cell->end_idx)) {
        /* Do nothing - whole stroke is visible */
      }
      else if (first_visible > cell->start_idx) {
        /* Starts partway through this stroke */
        int num_points = cell->end_idx - first_visible;
        reduce_stroke_points(cell->gps, num_points, mmd->transition);
      }
      else {
        /* Ends partway through this stroke */
        int num_points = last_visible - cell->start_idx;
        reduce_stroke_points(cell->gps, num_points, mmd->transition);
      }
    }
  }

  /* Free table */
  MEM_freeN(table);
}

/* --------------------------------------------- */

/* Concurrent - Show multiple strokes at once */
static void build_concurrent(BuildGpencilModifierData *mmd, bGPDframe *gpf, float fac)
{
  bGPDstroke *gps, *gps_next;
  int max_points = 0;

  const bool reverse = (mmd->transition != GP_BUILD_TRANSITION_GROW);

  /* 1) Determine the longest stroke, to figure out when short strokes should start */
  /* FIXME: A *really* long stroke here could dwarf everything else, causing bad timings */
  for (gps = gpf->strokes.first; gps; gps = gps->next) {
    if (gps->totpoints > max_points) {
      max_points = gps->totpoints;
    }
  }
  if (max_points == 0) {
    printf("ERROR: Strokes are all empty (GP Build Modifier: %s)\n", __func__);
    return;
  }

  /* 2) For each stroke, determine how it should be handled */
  for (gps = gpf->strokes.first; gps; gps = gps_next) {
    gps_next = gps->next;

    /* Relative Length of Stroke - Relative to the longest stroke,
     * what proportion of the available time should this stroke use
     */
    const float relative_len = (float)gps->totpoints / (float)max_points;

    /* Determine how many points should be left in the stroke */
    int num_points = 0;

    switch (mmd->time_alignment) {
      case GP_BUILD_TIMEALIGN_START: /* all start on frame 1 */
      {
        /* Build effect occurs over when fac = 0, to fac = relative_len */
        if (fac <= relative_len) {
          /* Scale fac to fit relative_len */
          const float scaled_fac = fac / MAX2(relative_len, PSEUDOINVERSE_EPSILON);

          if (reverse) {
            num_points = (int)roundf((1.0f - scaled_fac) * gps->totpoints);
          }
          else {
            num_points = (int)roundf(scaled_fac * gps->totpoints);
          }
        }
        else {
          /* Build effect has ended */
          if (reverse) {
            num_points = 0;
          }
          else {
            num_points = gps->totpoints;
          }
        }

        break;
      }
      case GP_BUILD_TIMEALIGN_END: /* all end on same frame */
      {
        /* Build effect occurs over  1.0 - relative_len, to 1.0  (i.e. over the end of the range)
         */
        const float start_fac = 1.0f - relative_len;

        if (fac >= start_fac) {
          const float scaled_fac = (fac - start_fac) / MAX2(relative_len, PSEUDOINVERSE_EPSILON);

          if (reverse) {
            num_points = (int)roundf((1.0f - scaled_fac) * gps->totpoints);
          }
          else {
            num_points = (int)roundf(scaled_fac * gps->totpoints);
          }
        }
        else {
          /* Build effect hasn't started */
          if (reverse) {
            num_points = gps->totpoints;
          }
          else {
            num_points = 0;
          }
        }

        break;
      }
    }

    /* Modify the stroke geometry */
    if (num_points <= 0) {
      /* Nothing Left - Delete the stroke */
      clear_stroke(gpf, gps);
    }
    else if (num_points < gps->totpoints) {
      /* Remove some points */
      reduce_stroke_points(gps, num_points, mmd->transition);
    }
  }
}

/* --------------------------------------------- */
static void generate_geometry(GpencilModifierData *md,
                              Depsgraph *depsgraph,
                              bGPDlayer *gpl,
                              bGPDframe *gpf)
{
  BuildGpencilModifierData *mmd = (BuildGpencilModifierData *)md;
  const bool reverse = (mmd->transition != GP_BUILD_TRANSITION_GROW);
  const bool is_percentage = (mmd->flag & GP_BUILD_PERCENTAGE);

  const float ctime = DEG_get_ctime(depsgraph);

  /* Early exit if it's an empty frame */
  if (gpf->strokes.first == NULL) {
    return;
  }

  /* Omit layer if filter by layer */
  if (mmd->layername[0] != '\0') {
    if ((mmd->flag & GP_BUILD_INVERT_LAYER) == 0) {
      if (!STREQ(mmd->layername, gpl->info)) {
        return;
      }
    }
    else {
      if (STREQ(mmd->layername, gpl->info)) {
        return;
      }
    }
  }
  /* verify layer pass */
  if (mmd->layer_pass > 0) {
    if ((mmd->flag & GP_BUILD_INVERT_LAYERPASS) == 0) {
      if (gpl->pass_index != mmd->layer_pass) {
        return;
      }
    }
    else {
      if (gpl->pass_index == mmd->layer_pass) {
        return;
      }
    }
  }

  /* Early exit if outside of the frame range for this modifier
   * (e.g. to have one forward, and one backwards modifier)
   */
  if (mmd->flag & GP_BUILD_RESTRICT_TIME) {
    if ((ctime < mmd->start_frame) || (ctime > mmd->end_frame)) {
      return;
    }
  }

  /* Compute start and end frames for the animation effect
   * By default, the upper bound is given by the "maximum length" setting
   */
  float start_frame = gpf->framenum + mmd->start_delay;
  float end_frame = start_frame + mmd->length;

  if (gpf->next) {
    /* Use the next frame or upper bound as end frame, whichever is lower/closer */
    end_frame = MIN2(end_frame, gpf->next->framenum);
  }

  /* Early exit if current frame is outside start/end bounds */
  /* NOTE: If we're beyond the next/previous frames (if existent),
   * then we wouldn't have this problem anyway... */
  if (ctime < start_frame) {
    /* Before Start - Animation hasn't started. Display initial state. */
    if (reverse) {
      /* 1) Reverse = Start with all, end with nothing.
       *    ==> Do nothing (everything already present)
       */
    }
    else {
      /* 2) Forward Order = Start with nothing, end with the full frame.
       *    ==> Free all strokes, and return an empty frame
       */
      gpf_clear_all_strokes(gpf);
    }

    /* Early exit */
    return;
  }
  if (ctime >= end_frame) {
    /* Past End - Animation finished. Display final result. */
    if (reverse) {
      /* 1) Reverse = Start with all, end with nothing.
       *    ==> Free all strokes, and return an empty frame
       */
      gpf_clear_all_strokes(gpf);
    }
    else {
      /* 2) Forward Order = Start with nothing, end with the full frame.
       *    ==> Do Nothing (everything already present)
       */
    }

    /* Early exit */
    return;
  }

  /* Determine how far along we are between the keyframes */
  float fac = is_percentage ? mmd->percentage_fac :
                              (ctime - start_frame) / (end_frame - start_frame);

  /* Time management mode */
  switch (mmd->mode) {
    case GP_BUILD_MODE_SEQUENTIAL:
      build_sequential(mmd, gpf, fac);
      break;

    case GP_BUILD_MODE_CONCURRENT:
      build_concurrent(mmd, gpf, fac);
      break;

    default:
      printf("Unsupported build mode (%d) for GP Build Modifier: '%s'\n",
             mmd->mode,
             mmd->modifier.name);
      break;
  }
}

/* Entry-point for Build Modifier */
static void generateStrokes(GpencilModifierData *md, Depsgraph *depsgraph, Object *ob)
{
  Scene *scene = DEG_get_evaluated_scene(depsgraph);
  bGPdata *gpd = (bGPdata *)ob->data;

  LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
    bGPDframe *gpf = BKE_gpencil_frame_retime_get(depsgraph, scene, ob, gpl);
    if (gpf == NULL) {
      continue;
    }
    generate_geometry(md, depsgraph, gpl, gpf);
  }
}

static void panel_draw(const bContext *C, Panel *panel)
{
  uiLayout *row, *sub;
  uiLayout *layout = panel->layout;

  PointerRNA ptr;
  PointerRNA ob_ptr;
  gpencil_modifier_panel_get_property_pointers(C, panel, &ob_ptr, &ptr);

  int mode = RNA_enum_get(&ptr, "mode");

  uiLayoutSetPropSep(layout, true);

  uiItemR(layout, &ptr, "mode", 0, NULL, ICON_NONE);
  if (mode == GP_BUILD_MODE_CONCURRENT) {
    uiItemR(layout, &ptr, "concurrent_time_alignment", 0, NULL, ICON_NONE);
  }

  uiItemS(layout);

  uiItemR(layout, &ptr, "transition", 0, NULL, ICON_NONE);
  uiItemR(layout, &ptr, "start_delay", 0, NULL, ICON_NONE);
  uiItemR(layout, &ptr, "length", 0, IFACE_("Frames"), ICON_NONE);

  uiItemS(layout);

  row = uiLayoutRowWithHeading(layout, true, IFACE_("Use Factor"));
  uiItemR(row, &ptr, "use_percentage", 0, "", ICON_NONE);
  sub = uiLayoutRow(row, true);
  uiLayoutSetActive(sub, RNA_boolean_get(&ptr, "use_percentage"));
  uiItemR(sub, &ptr, "percentage_factor", 0, "", ICON_NONE);

  /* Check for incompatible time modifier. */
  Object *ob = ob_ptr.data;
  GpencilModifierData *md = ptr.data;
  if (BKE_gpencil_modifiers_findby_type(ob, eGpencilModifierType_Time) != NULL) {
    BKE_gpencil_modifier_set_error(md, "Build and Time Offset modifiers are incompatible");
  }

  gpencil_modifier_panel_end(layout, &ptr);
}

static void frame_range_header_draw(const bContext *C, Panel *panel)
{
  uiLayout *layout = panel->layout;

  PointerRNA ptr;
  gpencil_modifier_panel_get_property_pointers(C, panel, NULL, &ptr);

  uiItemR(layout, &ptr, "use_restrict_frame_range", 0, IFACE_("Custom Range"), ICON_NONE);
}

static void frame_range_panel_draw(const bContext *C, Panel *panel)
{
  uiLayout *col;
  uiLayout *layout = panel->layout;

  PointerRNA ptr;
  gpencil_modifier_panel_get_property_pointers(C, panel, NULL, &ptr);

  uiLayoutSetPropSep(layout, true);

  col = uiLayoutColumn(layout, false);
  uiItemR(col, &ptr, "frame_start", 0, IFACE_("Start"), ICON_NONE);
  uiItemR(col, &ptr, "frame_end", 0, IFACE_("End"), ICON_NONE);
}

static void mask_panel_draw(const bContext *C, Panel *panel)
{
  gpencil_modifier_masking_panel_draw(C, panel, false, false);
}

static void panelRegister(ARegionType *region_type)
{
  PanelType *panel_type = gpencil_modifier_panel_register(
      region_type, eGpencilModifierType_Build, panel_draw);
  gpencil_modifier_subpanel_register(
      region_type, "frame_range", "", frame_range_header_draw, frame_range_panel_draw, panel_type);
  gpencil_modifier_subpanel_register(
      region_type, "_mask", "Influence", NULL, mask_panel_draw, panel_type);
}

/* ******************************************** */

GpencilModifierTypeInfo modifierType_Gpencil_Build = {
    /* name */ "Build",
    /* structName */ "BuildGpencilModifierData",
    /* structSize */ sizeof(BuildGpencilModifierData),
    /* type */ eGpencilModifierTypeType_Gpencil,
    /* flags */ eGpencilModifierTypeFlag_NoApply,

    /* copyData */ copyData,

    /* deformStroke */ NULL,
    /* generateStrokes */ generateStrokes,
    /* bakeModifier */ NULL,
    /* remapTime */ NULL,

    /* initData */ initData,
    /* freeData */ NULL,
    /* isDisabled */ NULL,
    /* updateDepsgraph */ NULL,
    /* dependsOnTime */ dependsOnTime,
    /* foreachObjectLink */ NULL,
    /* foreachIDLink */ NULL,
    /* foreachTexLink */ NULL,
    /* panelRegister */ panelRegister,
};