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) 2008, Blender Foundation
   * This is a new part of Blender
   */
  
  /** \file
   * \ingroup bke
   */
  
  #include <math.h>
  #include <stddef.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  #include "CLG_log.h"
  
  #include "MEM_guardedalloc.h"
  
  #include "BLI_blenlib.h"
  #include "BLI_ghash.h"
  #include "BLI_hash.h"
  #include "BLI_math_vector.h"
  #include "BLI_polyfill_2d.h"
  
  #include "BLT_translation.h"
  
  #include "DNA_gpencil_modifier_types.h"
  #include "DNA_gpencil_types.h"
  #include "DNA_mesh_types.h"
  #include "DNA_meshdata_types.h"
  #include "DNA_scene_types.h"
  
  #include "BKE_deform.h"
  #include "BKE_gpencil.h"
  #include "BKE_gpencil_geom.h"
  #include "BKE_main.h"
  #include "BKE_material.h"
  #include "BKE_object.h"
  
  #include "DEG_depsgraph_query.h"
  
  /* GP Object - Boundbox Support */
  /**
   *Get min/max coordinate bounds for single stroke.
   * \param gps: Grease pencil stroke
   * \param use_select: Include only selected points
   * \param r_min: Result minimum coordinates
   * \param r_max: Result maximum coordinates
   * \return True if it was possible to calculate
   */
  bool BKE_gpencil_stroke_minmax(const bGPDstroke *gps,
                                 const bool use_select,
                                 float r_min[3],
                                 float r_max[3])
  {
    const bGPDspoint *pt;
    int i;
    bool changed = false;
  
    if (ELEM(NULL, gps, r_min, r_max)) {
      return false;
    }
  
    for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
      if ((use_select == false) || (pt->flag & GP_SPOINT_SELECT)) {
        minmax_v3v3_v3(r_min, r_max, &pt->x);
        changed = true;
      }
    }
    return changed;
  }
  
  /**
   * Get min/max bounds of all strokes in grease pencil data-block.
   * \param gpd: Grease pencil datablock
   * \param r_min: Result minimum coordinates
   * \param r_max: Result maximum coordinates
   * \return True if it was possible to calculate
   */
  bool BKE_gpencil_data_minmax(const bGPdata *gpd, float r_min[3], float r_max[3])
  {
    bool changed = false;
  
    INIT_MINMAX(r_min, r_max);
  
    if (gpd == NULL) {
      return changed;
    }
  
    LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
      bGPDframe *gpf = gpl->actframe;
  
      if (gpf != NULL) {
        LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
          changed |= BKE_gpencil_stroke_minmax(gps, false, r_min, r_max);
        }
      }
    }
  
    return changed;
  }
  
  /**
   * Compute center of bounding box.
   * \param gpd: Grease pencil data-block
   * \param r_centroid: Location of the center
   */
  void BKE_gpencil_centroid_3d(bGPdata *gpd, float r_centroid[3])
  {
    float min[3], max[3], tot[3];
  
    BKE_gpencil_data_minmax(gpd, min, max);
  
    add_v3_v3v3(tot, min, max);
    mul_v3_v3fl(r_centroid, tot, 0.5f);
  }
  
  /**
   * Compute stroke bounding box.
   * \param gps: Grease pencil Stroke
   */
  void BKE_gpencil_stroke_boundingbox_calc(bGPDstroke *gps)
  {
    INIT_MINMAX(gps->boundbox_min, gps->boundbox_max);
    BKE_gpencil_stroke_minmax(gps, false, gps->boundbox_min, gps->boundbox_max);
  }
  
  /**
   * Create bounding box values.
   * \param ob: Grease pencil object
   */
  static void boundbox_gpencil(Object *ob)
  {
    BoundBox *bb;
    bGPdata *gpd;
    float min[3], max[3];
  
    if (ob->runtime.bb == NULL) {
      ob->runtime.bb = MEM_callocN(sizeof(BoundBox), "GPencil boundbox");
    }
  
    bb = ob->runtime.bb;
    gpd = ob->data;
  
    if (!BKE_gpencil_data_minmax(gpd, min, max)) {
      min[0] = min[1] = min[2] = -1.0f;
      max[0] = max[1] = max[2] = 1.0f;
    }
  
    BKE_boundbox_init_from_minmax(bb, min, max);
  
    bb->flag &= ~BOUNDBOX_DIRTY;
  }
  
  /**
   * Get grease pencil object bounding box.
   * \param ob: Grease pencil object
   * \return Bounding box
   */
  BoundBox *BKE_gpencil_boundbox_get(Object *ob)
  {
    if (ELEM(NULL, ob, ob->data)) {
      return NULL;
    }
  
    bGPdata *gpd = (bGPdata *)ob->data;
    if ((ob->runtime.bb) && ((gpd->flag & GP_DATA_CACHE_IS_DIRTY) == 0)) {
      return ob->runtime.bb;
    }
  
    boundbox_gpencil(ob);
  
    Object *ob_orig = (Object *)DEG_get_original_id(&ob->id);
    /* Update orig object's boundbox with re-computed evaluated values. This function can be
     * called with the evaluated object and need update the original object bound box data
     * to keep both values synchronized. */
    if ((ob_orig != NULL) && (ob != ob_orig)) {
      if (ob_orig->runtime.bb == NULL) {
        ob_orig->runtime.bb = MEM_callocN(sizeof(BoundBox), "GPencil boundbox");
      }
      for (int i = 0; i < 8; i++) {
        copy_v3_v3(ob_orig->runtime.bb->vec[i], ob->runtime.bb->vec[i]);
      }
    }
  
    return ob->runtime.bb;
  }
  
  /* ************************************************** */
  
  static int stroke_march_next_point(const bGPDstroke *gps,
                                     const int index_next_pt,
                                     const float *current,
                                     const float dist,
                                     float *result,
                                     float *pressure,
                                     float *strength,
                                     float *vert_color,
                                     float *ratio_result,
                                     int *index_from,
                                     int *index_to)
  {
    float remaining_till_next = 0.0f;
    float remaining_march = dist;
    float step_start[3];
    float point[3];
    int next_point_index = index_next_pt;
    bGPDspoint *pt = NULL;
  
    if (!(next_point_index < gps->totpoints)) {
      return -1;
    }
  
    copy_v3_v3(step_start, current);
    pt = &gps->points[next_point_index];
    copy_v3_v3(point, &pt->x);
    remaining_till_next = len_v3v3(point, step_start);
  
    while (remaining_till_next < remaining_march) {
      remaining_march -= remaining_till_next;
      pt = &gps->points[next_point_index];
      copy_v3_v3(point, &pt->x);
      copy_v3_v3(step_start, point);
      next_point_index++;
      if (!(next_point_index < gps->totpoints)) {
        next_point_index = gps->totpoints - 1;
        break;
      }
      pt = &gps->points[next_point_index];
      copy_v3_v3(point, &pt->x);
      remaining_till_next = len_v3v3(point, step_start);
    }
    if (remaining_till_next < remaining_march) {
      pt = &gps->points[next_point_index];
      copy_v3_v3(result, &pt->x);
      *pressure = gps->points[next_point_index].pressure;
      *strength = gps->points[next_point_index].strength;
      memcpy(vert_color, gps->points[next_point_index].vert_color, sizeof(float[4]));
  
      *index_from = next_point_index - 1;
      *index_to = next_point_index;
      *ratio_result = 1.0f;
  
      return 0;
    }
  
    float ratio = remaining_march / remaining_till_next;
    interp_v3_v3v3(result, step_start, point, ratio);
    *pressure = interpf(
        gps->points[next_point_index].pressure, gps->points[next_point_index - 1].pressure, ratio);
    *strength = interpf(
        gps->points[next_point_index].strength, gps->points[next_point_index - 1].strength, ratio);
    interp_v4_v4v4(vert_color,
                   gps->points[next_point_index - 1].vert_color,
                   gps->points[next_point_index].vert_color,
                   ratio);
  
    *index_from = next_point_index - 1;
    *index_to = next_point_index;
    *ratio_result = ratio;
  
    return next_point_index;
  }
  
  static int stroke_march_next_point_no_interp(const bGPDstroke *gps,
                                               const int index_next_pt,
                                               const float *current,
                                               const float dist,
                                               float *result)
  {
    float remaining_till_next = 0.0f;
    float remaining_march = dist;
    float step_start[3];
    float point[3];
    int next_point_index = index_next_pt;
    bGPDspoint *pt = NULL;
  
    if (!(next_point_index < gps->totpoints)) {
      return -1;
    }
  
    copy_v3_v3(step_start, current);
    pt = &gps->points[next_point_index];
    copy_v3_v3(point, &pt->x);
    remaining_till_next = len_v3v3(point, step_start);
  
    while (remaining_till_next < remaining_march) {
      remaining_march -= remaining_till_next;
      pt = &gps->points[next_point_index];
      copy_v3_v3(point, &pt->x);
      copy_v3_v3(step_start, point);
      next_point_index++;
      if (!(next_point_index < gps->totpoints)) {
        next_point_index = gps->totpoints - 1;
        break;
      }
      pt = &gps->points[next_point_index];
      copy_v3_v3(point, &pt->x);
      remaining_till_next = len_v3v3(point, step_start);
    }
    if (remaining_till_next < remaining_march) {
      pt = &gps->points[next_point_index];
      copy_v3_v3(result, &pt->x);
      return 0;
    }
  
    float ratio = remaining_march / remaining_till_next;
    interp_v3_v3v3(result, step_start, point, ratio);
    return next_point_index;
  }
  
  static int stroke_march_count(const bGPDstroke *gps, const float dist)
  {
    int point_count = 0;
    float point[3];
    int next_point_index = 1;
    bGPDspoint *pt = NULL;
  
    pt = &gps->points[0];
    copy_v3_v3(point, &pt->x);
    point_count++;
  
    while ((next_point_index = stroke_march_next_point_no_interp(
                gps, next_point_index, point, dist, point)) > -1) {
      point_count++;
      if (next_point_index == 0) {
        break; /* last point finished */
      }
    }
    return point_count;
  }
  
  static void stroke_defvert_create_nr_list(MDeformVert *dv_list,
                                            int count,
                                            ListBase *result,
                                            int *totweight)
  {
    LinkData *ld;
    MDeformVert *dv;
    MDeformWeight *dw;
    int i, j;
    int tw = 0;
    for (i = 0; i < count; i++) {
      dv = &dv_list[i];
  
      /* find def_nr in list, if not exist, then create one */
      for (j = 0; j < dv->totweight; j++) {
        bool found = false;
        dw = &dv->dw[j];
        for (ld = result->first; ld; ld = ld->next) {
          if (ld->data == POINTER_FROM_INT(dw->def_nr)) {
            found = true;
            break;
          }
        }
        if (!found) {
          ld = MEM_callocN(sizeof(LinkData), "def_nr_item");
          ld->data = POINTER_FROM_INT(dw->def_nr);
          BLI_addtail(result, ld);
          tw++;
        }
      }
    }
  
    *totweight = tw;
  }
  
  static MDeformVert *stroke_defvert_new_count(int count, int totweight, ListBase *def_nr_list)
  {
    int i, j;
    LinkData *ld;
    MDeformVert *dst = MEM_mallocN(count * sizeof(MDeformVert), "new_deformVert");
  
    for (i = 0; i < count; i++) {
      dst[i].dw = MEM_mallocN(sizeof(MDeformWeight) * totweight, "new_deformWeight");
      dst[i].totweight = totweight;
      j = 0;
      /* re-assign deform groups */
      for (ld = def_nr_list->first; ld; ld = ld->next) {
        dst[i].dw[j].def_nr = POINTER_AS_INT(ld->data);
        j++;
      }
    }
  
    return dst;
  }
  
  static void stroke_interpolate_deform_weights(
      bGPDstroke *gps, int index_from, int index_to, float ratio, MDeformVert *vert)
  {
    const MDeformVert *vl = &gps->dvert[index_from];
    const MDeformVert *vr = &gps->dvert[index_to];
  
    for (int i = 0; i < vert->totweight; i++) {
      float wl = BKE_defvert_find_weight(vl, vert->dw[i].def_nr);
      float wr = BKE_defvert_find_weight(vr, vert->dw[i].def_nr);
      vert->dw[i].weight = interpf(wr, wl, ratio);
    }
  }
  
  /**
   * Resample a stroke
   * \param gps: Stroke to sample
   * \param dist: Distance of one segment
   */
  bool BKE_gpencil_stroke_sample(bGPDstroke *gps, const float dist, const bool select)
  {
    bGPDspoint *pt = gps->points;
    bGPDspoint *pt1 = NULL;
    bGPDspoint *pt2 = NULL;
    LinkData *ld;
    ListBase def_nr_list = {0};
  
    if (gps->totpoints < 2 || dist < FLT_EPSILON) {
      return false;
    }
    /* TODO: Implement feature point preservation. */
    int count = stroke_march_count(gps, dist);
  
    bGPDspoint *new_pt = MEM_callocN(sizeof(bGPDspoint) * count, "gp_stroke_points_sampled");
    MDeformVert *new_dv = NULL;
  
    int result_totweight;
  
    if (gps->dvert != NULL) {
      stroke_defvert_create_nr_list(gps->dvert, gps->totpoints, &def_nr_list, &result_totweight);
      new_dv = stroke_defvert_new_count(count, result_totweight, &def_nr_list);
    }
  
    int next_point_index = 1;
    int i = 0;
    float pressure, strength, ratio_result;
    float vert_color[4];
    int index_from, index_to;
    float last_coord[3];
  
    /*  1st point is always at the start */
    pt1 = &gps->points[0];
    copy_v3_v3(last_coord, &pt1->x);
    pt2 = &new_pt[i];
    copy_v3_v3(&pt2->x, last_coord);
    new_pt[i].pressure = pt[0].pressure;
    new_pt[i].strength = pt[0].strength;
    memcpy(new_pt[i].vert_color, pt[0].vert_color, sizeof(float[4]));
    if (select) {
      new_pt[i].flag |= GP_SPOINT_SELECT;
    }
    i++;
  
    if (new_dv) {
      stroke_interpolate_deform_weights(gps, 0, 0, 0, &new_dv[0]);
    }
  
    /* The rest. */
    while ((next_point_index = stroke_march_next_point(gps,
                                                       next_point_index,
                                                       last_coord,
                                                       dist,
                                                       last_coord,
                                                       &pressure,
                                                       &strength,
                                                       vert_color,
                                                       &ratio_result,
                                                       &index_from,
                                                       &index_to)) > -1) {
      pt2 = &new_pt[i];
      copy_v3_v3(&pt2->x, last_coord);
      new_pt[i].pressure = pressure;
      new_pt[i].strength = strength;
      memcpy(new_pt[i].vert_color, vert_color, sizeof(float[4]));
      if (select) {
        new_pt[i].flag |= GP_SPOINT_SELECT;
      }
  
      if (new_dv) {
        stroke_interpolate_deform_weights(gps, index_from, index_to, ratio_result, &new_dv[i]);
      }
  
      i++;
      if (next_point_index == 0) {
        break; /* last point finished */
      }
    }
  
    gps->points = new_pt;
    /* Free original vertex list. */
    MEM_freeN(pt);
  
    if (new_dv) {
      /* Free original weight data. */
      BKE_gpencil_free_stroke_weights(gps);
      MEM_freeN(gps->dvert);
      while ((ld = BLI_pophead(&def_nr_list))) {
        MEM_freeN(ld);
      }
  
      gps->dvert = new_dv;
    }
  
    gps->totpoints = i;
  
    /* Calc geometry data. */
    BKE_gpencil_stroke_geometry_update(gps);
  
    return true;
  }
  
  /**
   * Backbone stretch similar to Freestyle.
   * \param gps: Stroke to sample
   * \param dist: Distance of one segment
   * \param tip_length: Ignore tip jittering, set zero to use default value.
   */
  bool BKE_gpencil_stroke_stretch(bGPDstroke *gps, const float dist, const float tip_length)
  {
    bGPDspoint *pt = gps->points, *last_pt, *second_last, *next_pt;
    float threshold = (tip_length == 0 ? 0.001f : tip_length);
  
    if (gps->totpoints < 2 || dist < FLT_EPSILON) {
      return false;
    }
  
    last_pt = &pt[gps->totpoints - 1];
    second_last = &pt[gps->totpoints - 2];
    next_pt = &pt[1];
  
    float len1 = 0.0f;
    float len2 = 0.0f;
  
    int i = 1;
    while (len1 < threshold && gps->totpoints > i) {
      next_pt = &pt[i];
      len1 = len_v3v3(&next_pt->x, &pt->x);
      i++;
    }
  
    i = 2;
    while (len2 < threshold && gps->totpoints >= i) {
      second_last = &pt[gps->totpoints - i];
      len2 = len_v3v3(&last_pt->x, &second_last->x);
      i++;
    }
  
    float extend1 = (len1 + dist) / len1;
    float extend2 = (len2 + dist) / len2;
  
    float result1[3], result2[3];
  
    interp_v3_v3v3(result1, &next_pt->x, &pt->x, extend1);
    interp_v3_v3v3(result2, &second_last->x, &last_pt->x, extend2);
  
    copy_v3_v3(&pt->x, result1);
    copy_v3_v3(&last_pt->x, result2);
  
    return true;
  }
  
  /**
   * Trim stroke to needed segments
   * \param gps: Target stroke
   * \param index_from: the index of the first point to be used in the trimmed result
   * \param index_to: the index of the last point to be used in the trimmed result
   */
  bool BKE_gpencil_stroke_trim_points(bGPDstroke *gps, const int index_from, const int index_to)
  {
    bGPDspoint *pt = gps->points, *new_pt;
    MDeformVert *dv, *new_dv;
  
    const int new_count = index_to - index_from + 1;
  
    if (new_count >= gps->totpoints) {
      return false;
    }
  
    if (new_count == 1) {
      BKE_gpencil_free_stroke_weights(gps);
      MEM_freeN(gps->points);
      gps->points = NULL;
      gps->dvert = NULL;
      gps->totpoints = 0;
      return false;
    }
  
    new_pt = MEM_callocN(sizeof(bGPDspoint) * new_count, "gp_stroke_points_trimmed");
  
    for (int i = 0; i < new_count; i++) {
      memcpy(&new_pt[i], &pt[i + index_from], sizeof(bGPDspoint));
    }
  
    if (gps->dvert) {
      new_dv = MEM_callocN(sizeof(MDeformVert) * new_count, "gp_stroke_dverts_trimmed");
      for (int i = 0; i < new_count; i++) {
        dv = &gps->dvert[i + index_from];
        new_dv[i].flag = dv->flag;
        new_dv[i].totweight = dv->totweight;
        new_dv[i].dw = MEM_callocN(sizeof(MDeformWeight) * dv->totweight,
                                   "gp_stroke_dverts_dw_trimmed");
        for (int j = 0; j < dv->totweight; j++) {
          new_dv[i].dw[j].weight = dv->dw[j].weight;
          new_dv[i].dw[j].def_nr = dv->dw[j].def_nr;
        }
      }
      MEM_freeN(gps->dvert);
      gps->dvert = new_dv;
    }
  
    MEM_freeN(gps->points);
    gps->points = new_pt;
    gps->totpoints = new_count;
  
    return true;
  }
  
  /**
   * Split stroke.
   * \param gpf: Grease pencil frame
   * \param gps: Grease pencil original stroke
   * \param before_index: Position of the point to split
   * \param remaining_gps: Secondary stroke after split.
   * \return True if the split was done
   */
  bool BKE_gpencil_stroke_split(bGPDframe *gpf,
                                bGPDstroke *gps,
                                const int before_index,
                                bGPDstroke **remaining_gps)
  {
    bGPDstroke *new_gps;
    bGPDspoint *pt = gps->points, *new_pt;
    MDeformVert *dv, *new_dv;
  
    if (before_index >= gps->totpoints || before_index == 0) {
      return false;
    }
  
    const int new_count = gps->totpoints - before_index;
    const int old_count = before_index;
  
    /* Handle remaining segments first. */
  
    new_gps = BKE_gpencil_stroke_add_existing_style(
        gpf, gps, gps->mat_nr, new_count, gps->thickness);
  
    new_pt = new_gps->points; /* Allocated from above. */
  
    for (int i = 0; i < new_count; i++) {
      memcpy(&new_pt[i], &pt[i + before_index], sizeof(bGPDspoint));
    }
  
    if (gps->dvert) {
      new_dv = MEM_callocN(sizeof(MDeformVert) * new_count,
                           "gp_stroke_dverts_remaining(MDeformVert)");
      for (int i = 0; i < new_count; i++) {
        dv = &gps->dvert[i + before_index];
        new_dv[i].flag = dv->flag;
        new_dv[i].totweight = dv->totweight;
        new_dv[i].dw = MEM_callocN(sizeof(MDeformWeight) * dv->totweight,
                                   "gp_stroke_dverts_dw_remaining(MDeformWeight)");
        for (int j = 0; j < dv->totweight; j++) {
          new_dv[i].dw[j].weight = dv->dw[j].weight;
          new_dv[i].dw[j].def_nr = dv->dw[j].def_nr;
        }
      }
      new_gps->dvert = new_dv;
    }
  
    (*remaining_gps) = new_gps;
  
    /* Trim the original stroke into a shorter one.
     * Keep the end point. */
  
    BKE_gpencil_stroke_trim_points(gps, 0, old_count);
    BKE_gpencil_stroke_geometry_update(gps);
    return true;
  }
  
  /**
   * Shrink the stroke by length.
   * \param gps: Stroke to shrink
   * \param dist: delta length
   */
  bool BKE_gpencil_stroke_shrink(bGPDstroke *gps, const float dist)
  {
    bGPDspoint *pt = gps->points, *second_last;
    int i;
  
    if (gps->totpoints < 2 || dist < FLT_EPSILON) {
      return false;
    }
  
    second_last = &pt[gps->totpoints - 2];
  
    float len1, this_len1, cut_len1;
    float len2, this_len2, cut_len2;
    int index_start, index_end;
  
    len1 = len2 = this_len1 = this_len2 = cut_len1 = cut_len2 = 0.0f;
  
    i = 1;
    while (len1 < dist && gps->totpoints > i - 1) {
      this_len1 = len_v3v3(&pt[i].x, &pt[i + 1].x);
      len1 += this_len1;
      cut_len1 = len1 - dist;
      i++;
    }
    index_start = i - 2;
  
    i = 2;
    while (len2 < dist && gps->totpoints >= i) {
      second_last = &pt[gps->totpoints - i];
      this_len2 = len_v3v3(&second_last[1].x, &second_last->x);
      len2 += this_len2;
      cut_len2 = len2 - dist;
      i++;
    }
    index_end = gps->totpoints - i + 2;
  
    if (len1 < dist || len2 < dist || index_end <= index_start) {
      index_start = index_end = 0; /* empty stroke */
    }
  
    if ((index_end == index_start + 1) && (cut_len1 + cut_len2 > 1.0f)) {
      index_start = index_end = 0; /* no length left to cut */
    }
  
    BKE_gpencil_stroke_trim_points(gps, index_start, index_end);
  
    if (gps->totpoints == 0) {
      return false;
    }
  
    pt = gps->points;
  
    float cut1 = cut_len1 / this_len1;
    float cut2 = cut_len2 / this_len2;
  
    float result1[3], result2[3];
  
    interp_v3_v3v3(result1, &pt[1].x, &pt[0].x, cut1);
    interp_v3_v3v3(result2, &pt[gps->totpoints - 2].x, &pt[gps->totpoints - 1].x, cut2);
  
    copy_v3_v3(&pt[0].x, result1);
    copy_v3_v3(&pt[gps->totpoints - 1].x, result2);
  
    return true;
  }
  
  /**
   * Apply smooth position to stroke point.
   * \param gps: Stroke to smooth
   * \param i: Point index
   * \param inf: Amount of smoothing to apply
   */
  bool BKE_gpencil_stroke_smooth(bGPDstroke *gps, int i, float inf)
  {
    bGPDspoint *pt = &gps->points[i];
    float sco[3] = {0.0f};
  
    /* Do nothing if not enough points to smooth out */
    if (gps->totpoints <= 2) {
      return false;
    }
  
    /* Only affect endpoints by a fraction of the normal strength,
     * to prevent the stroke from shrinking too much
     */
    if ((i == 0) || (i == gps->totpoints - 1)) {
      inf *= 0.1f;
    }
  
    /* Compute smoothed coordinate by taking the ones nearby */
    /* XXX: This is potentially slow,
     *      and suffers from accumulation error as earlier points are handled before later ones. */
    {
      /* XXX: this is hardcoded to look at 2 points on either side of the current one
       * (i.e. 5 items total). */
      const int steps = 2;
      const float average_fac = 1.0f / (float)(steps * 2 + 1);
      int step;
  
      /* add the point itself */
      madd_v3_v3fl(sco, &pt->x, average_fac);
  
      /* n-steps before/after current point */
      /* XXX: review how the endpoints are treated by this algorithm. */
      /* XXX: falloff measures should also introduce some weighting variations,
       *      so that further-out points get less weight. */
      for (step = 1; step <= steps; step++) {
        bGPDspoint *pt1, *pt2;
        int before = i - step;
        int after = i + step;
  
        CLAMP_MIN(before, 0);
        CLAMP_MAX(after, gps->totpoints - 1);
  
        pt1 = &gps->points[before];
        pt2 = &gps->points[after];
  
        /* add both these points to the average-sum (s += p[i]/n) */
        madd_v3_v3fl(sco, &pt1->x, average_fac);
        madd_v3_v3fl(sco, &pt2->x, average_fac);
      }
    }
  
    /* Based on influence factor, blend between original and optimal smoothed coordinate */
    interp_v3_v3v3(&pt->x, &pt->x, sco, inf);
  
    return true;
  }
  
  /**
   * Apply smooth strength to stroke point.
   * \param gps: Stroke to smooth
   * \param point_index: Point index
   * \param influence: Amount of smoothing to apply
   */
  bool BKE_gpencil_stroke_smooth_strength(bGPDstroke *gps, int point_index, float influence)
  {
    bGPDspoint *ptb = &gps->points[point_index];
  
    /* Do nothing if not enough points */
    if ((gps->totpoints <= 2) || (point_index < 1)) {
      return false;
    }
    /* Only affect endpoints by a fraction of the normal influence */
    float inf = influence;
    if ((point_index == 0) || (point_index == gps->totpoints - 1)) {
      inf *= 0.01f;
    }
    /* Limit max influence to reduce pop effect. */
    CLAMP_MAX(inf, 0.98f);
  
    float total = 0.0f;
    float max_strength = 0.0f;
    const int steps = 4;
    const float average_fac = 1.0f / (float)(steps * 2 + 1);
    int step;
  
    /* add the point itself */
    total += ptb->strength * average_fac;
    max_strength = ptb->strength;
  
    /* n-steps before/after current point */
    for (step = 1; step <= steps; step++) {
      bGPDspoint *pt1, *pt2;
      int before = point_index - step;
      int after = point_index + step;
  
      CLAMP_MIN(before, 0);
      CLAMP_MAX(after, gps->totpoints - 1);
  
      pt1 = &gps->points[before];
      pt2 = &gps->points[after];
  
      /* add both these points to the average-sum (s += p[i]/n) */
      total += pt1->strength * average_fac;
      total += pt2->strength * average_fac;
      /* Save max value. */
      if (max_strength < pt1->strength) {
        max_strength = pt1->strength;
      }
      if (max_strength < pt2->strength) {
        max_strength = pt2->strength;
      }
    }
  
    /* Based on influence factor, blend between original and optimal smoothed value. */
    ptb->strength = interpf(ptb->strength, total, inf);
    /* Clamp to maximum stroke strength to avoid weird results. */
    CLAMP_MAX(ptb->strength, max_strength);
  
    return true;
  }
  
  /**
   * Apply smooth for thickness to stroke point (use pressure).
   * \param gps: Stroke to smooth
   * \param point_index: Point index
   * \param influence: Amount of smoothing to apply
   */
  bool BKE_gpencil_stroke_smooth_thickness(bGPDstroke *gps, int point_index, float influence)
  {
    bGPDspoint *ptb = &gps->points[point_index];
  
    /* Do nothing if not enough points */
    if ((gps->totpoints <= 2) || (point_index < 1)) {
      return false;
    }
    /* Only affect endpoints by a fraction of the normal influence */
    float inf = influence;
    if ((point_index == 0) || (point_index == gps->totpoints - 1)) {
      inf *= 0.01f;
    }
    /* Limit max influence to reduce pop effect. */
    CLAMP_MAX(inf, 0.98f);
  
    float total = 0.0f;
    float max_pressure = 0.0f;
    const int steps = 4;
    const float average_fac = 1.0f / (float)(steps * 2 + 1);
    int step;
  
    /* add the point itself */
    total += ptb->pressure * average_fac;
    max_pressure = ptb->pressure;
  
    /* n-steps before/after current point */
    for (step = 1; step <= steps; step++) {
      bGPDspoint *pt1, *pt2;
      int before = point_index - step;
      int after = point_index + step;
  
      CLAMP_MIN(before, 0);
      CLAMP_MAX(after, gps->totpoints - 1);
  
      pt1 = &gps->points[before];
      pt2 = &gps->points[after];
  
      /* add both these points to the average-sum (s += p[i]/n) */
      total += pt1->pressure * average_fac;
      total += pt2->pressure * average_fac;
      /* Save max value. */
      if (max_pressure < pt1->pressure) {
        max_pressure = pt1->pressure;
      }
      if (max_pressure < pt2->pressure) {
        max_pressure = pt2->pressure;
      }
    }
  
    /* Based on influence factor, blend between original and optimal smoothed value. */
    ptb->pressure = interpf(ptb->pressure, total, inf);
    /* Clamp to maximum stroke thickness to avoid weird results. */
    CLAMP_MAX(ptb->pressure, max_pressure);
    return true;
  }
  
  /**
   * Apply smooth for UV rotation to stroke point (use pressure).
   * \param gps: Stroke to smooth
   * \param point_index: Point index
   * \param influence: Amount of smoothing to apply
   */
  bool BKE_gpencil_stroke_smooth_uv(bGPDstroke *gps, int point_index, float influence)
  {
    bGPDspoint *ptb = &gps->points[point_index];
  
    /* Do nothing if not enough points */
    if (gps->totpoints <= 2) {
      return false;
    }
  
    /* Compute theoretical optimal value */
    bGPDspoint *pta, *ptc;
    int before = point_index - 1;
    int after = point_index + 1;
  
    CLAMP_MIN(before, 0);
    CLAMP_MAX(after, gps->totpoints - 1);
  
    pta = &gps->points[before];
    ptc = &gps->points[after];
  
    /* the optimal value is the corresponding to the interpolation of the pressure
     * at the distance of point b
     */
    float fac = line_point_factor_v3(&ptb->x, &pta->x, &ptc->x);
    /* sometimes the factor can be wrong due stroke geometry, so use middle point */
    if ((fac < 0.0f) || (fac > 1.0f)) {
      fac = 0.5f;
    }
    float optimal = interpf(ptc->uv_rot, pta->uv_rot, fac);
  
    /* Based on influence factor, blend between original and optimal */
    ptb->uv_rot = interpf(optimal, ptb->uv_rot, influence);
    CLAMP(ptb->uv_rot, -M_PI_2, M_PI_2);
  
    return true;
  }
  
  /**
   * Get points of stroke always flat to view not affected
   * by camera view or view position.
   * \param points: Array of grease pencil points (3D)
   * \param totpoints: Total of points
   * \param points2d: Result array of 2D points
   * \param r_direction: Return Concave (-1), Convex (1), or Auto-detect (0)
   */
  void BKE_gpencil_stroke_2d_flat(const bGPDspoint *points,
                                  int totpoints,
                                  float (*points2d)[2],
                                  int *r_direction)
  {
    BLI_assert(totpoints >= 2);
  
    const bGPDspoint *pt0 = &points[0];
    const bGPDspoint *pt1 = &points[1];
    const bGPDspoint *pt3 = &points[(int)(totpoints * 0.75)];
  
    float locx[3];
    float locy[3];
    float loc3[3];
    float normal[3];
  
    /* local X axis (p0 -> p1) */
    sub_v3_v3v3(locx, &pt1->x, &pt0->x);
  
    /* point vector at 3/4 */
    float v3[3];
    if (totpoints == 2) {
      mul_v3_v3fl(v3, &pt3->x, 0.001f);
    }
    else {
      copy_v3_v3(v3, &pt3->x);
    }
  
    sub_v3_v3v3(loc3, v3, &pt0->x);
  
    /* vector orthogonal to polygon plane */
    cross_v3_v3v3(normal, locx, loc3);
  
    /* local Y axis (cross to normal/x axis) */
    cross_v3_v3v3(locy, normal, locx);
  
    /* Normalize vectors */
    normalize_v3(locx);
    normalize_v3(locy);
  
    /* Get all points in local space */
    for (int i = 0; i < totpoints; i++) {
      const bGPDspoint *pt = &points[i];
      float loc[3];
  
      /* Get local space using first point as origin */
      sub_v3_v3v3(loc, &pt->x, &pt0->x);
  
      points2d[i][0] = dot_v3v3(loc, locx);
      points2d[i][1] = dot_v3v3(loc, locy);
    }
  
    /* Concave (-1), Convex (1), or Auto-detect (0)? */
    *r_direction = (int)locy[2];
  }
  
  /**
   * Get points of stroke always flat to view not affected by camera view or view position
   * using another stroke as reference.
   * \param ref_points: Array of reference points (3D)
   * \param ref_totpoints: Total reference points
   * \param points: Array of points to flat (3D)
   * \param totpoints: Total points
   * \param points2d: Result array of 2D points
   * \param scale: Scale factor
   * \param r_direction: Return Concave (-1), Convex (1), or Auto-detect (0)
   */
  void BKE_gpencil_stroke_2d_flat_ref(const bGPDspoint *ref_points,
                                      int ref_totpoints,
                                      const bGPDspoint *points,
                                      int totpoints,
                                      float (*points2d)[2],
                                      const float scale,
                                      int *r_direction)
  {
    BLI_assert(totpoints >= 2);
  
    const bGPDspoint *pt0 = &ref_points[0];
    const bGPDspoint *pt1 = &ref_points[1];
    const bGPDspoint *pt3 = &ref_points[(int)(ref_totpoints * 0.75)];
  
    float locx[3];
    float locy[3];
    float loc3[3];
    float normal[3];
  
    /* local X axis (p0 -> p1) */
    sub_v3_v3v3(locx, &pt1->x, &pt0->x);
  
    /* point vector at 3/4 */
    float v3[3];
    if (totpoints == 2) {
      mul_v3_v3fl(v3, &pt3->x, 0.001f);
    }
    else {
      copy_v3_v3(v3, &pt3->x);
    }
  
    sub_v3_v3v3(loc3, v3, &pt0->x);
  
    /* vector orthogonal to polygon plane */
    cross_v3_v3v3(normal, locx, loc3);
  
    /* local Y axis (cross to normal/x axis) */
    cross_v3_v3v3(locy, normal, locx);
  
    /* Normalize vectors */
    normalize_v3(locx);
    normalize_v3(locy);
  
    /* Get all points in local space */
    for (int i = 0; i < totpoints; i++) {
      const bGPDspoint *pt = &points[i];
      float loc[3];
      float v1[3];
      float vn[3] = {0.0f, 0.0f, 0.0f};
  
      /* apply scale to extremes of the stroke to get better collision detection
       * the scale is divided to get more control in the UI parameter
       */
      /* first point */
      if (i == 0) {
        const bGPDspoint *pt_next = &points[i + 1];
        sub_v3_v3v3(vn, &pt->x, &pt_next->x);
        normalize_v3(vn);
        mul_v3_fl(vn, scale / 10.0f);
        add_v3_v3v3(v1, &pt->x, vn);
      }
      /* last point */
      else if (i == totpoints - 1) {
        const bGPDspoint *pt_prev = &points[i - 1];
        sub_v3_v3v3(vn, &pt->x, &pt_prev->x);
        normalize_v3(vn);
        mul_v3_fl(vn, scale / 10.0f);
        add_v3_v3v3(v1, &pt->x, vn);
      }
      else {
        copy_v3_v3(v1, &pt->x);
      }
  
      /* Get local space using first point as origin (ref stroke) */
      sub_v3_v3v3(loc, v1, &pt0->x);
  
      points2d[i][0] = dot_v3v3(loc, locx);
      points2d[i][1] = dot_v3v3(loc, locy);
    }
  
    /* Concave (-1), Convex (1), or Auto-detect (0)? */
    *r_direction = (int)locy[2];
  }
  
  /* Calc texture coordinates using flat projected points. */
  static void gpencil_calc_stroke_fill_uv(const float (*points2d)[2],
                                          bGPDstroke *gps,
                                          const float minv[2],
                                          const float maxv[2],
                                          float (*r_uv)[2])
  {
    const float s = sin(gps->uv_rotation);
    const float c = cos(gps->uv_rotation);
  
    /* Calc center for rotation. */
    float center[2] = {0.5f, 0.5f};
    float d[2];
    d[0] = maxv[0] - minv[0];
    d[1] = maxv[1] - minv[1];
    for (int i = 0; i < gps->totpoints; i++) {
      r_uv[i][0] = (points2d[i][0] - minv[0]) / d[0];
      r_uv[i][1] = (points2d[i][1] - minv[1]) / d[1];
  
      /* Apply translation. */
      add_v2_v2(r_uv[i], gps->uv_translation);
  
      /* Apply Rotation. */
      r_uv[i][0] -= center[0];
      r_uv[i][1] -= center[1];
  
      float x = r_uv[i][0] * c - r_uv[i][1] * s;
      float y = r_uv[i][0] * s + r_uv[i][1] * c;
  
      r_uv[i][0] = x + center[0];
      r_uv[i][1] = y + center[1];
  
      /* Apply scale. */
      if (gps->uv_scale != 0.0f) {
        mul_v2_fl(r_uv[i], 1.0f / gps->uv_scale);
      }
    }
  }
  
  /**
   * Triangulate stroke to generate data for filling areas.
   * \param gps: Grease pencil stroke
   */
  void BKE_gpencil_stroke_fill_triangulate(bGPDstroke *gps)
  {
    BLI_assert(gps->totpoints >= 3);
  
    /* allocate memory for temporary areas */
    gps->tot_triangles = gps->totpoints - 2;
    uint(*tmp_triangles)[3] = MEM_mallocN(sizeof(*tmp_triangles) * gps->tot_triangles,
                                          "GP Stroke temp triangulation");
    float(*points2d)[2] = MEM_mallocN(sizeof(*points2d) * gps->totpoints,
                                      "GP Stroke temp 2d points");
    float(*uv)[2] = MEM_mallocN(sizeof(*uv) * gps->totpoints, "GP Stroke temp 2d uv data");
  
    int direction = 0;
  
    /* convert to 2d and triangulate */
    BKE_gpencil_stroke_2d_flat(gps->points, gps->totpoints, points2d, &direction);
    BLI_polyfill_calc(points2d, (uint)gps->totpoints, direction, tmp_triangles);
  
    /* calc texture coordinates automatically */
    float minv[2];
    float maxv[2];
    /* first needs bounding box data */
    ARRAY_SET_ITEMS(minv, -1.0f, -1.0f);
    ARRAY_SET_ITEMS(maxv, 1.0f, 1.0f);
  
    /* calc uv data */
    gpencil_calc_stroke_fill_uv(points2d, gps, minv, maxv, uv);
  
    /* Save triangulation data. */
    if (gps->tot_triangles > 0) {
      MEM_SAFE_FREE(gps->triangles);
      gps->triangles = MEM_callocN(sizeof(*gps->triangles) * gps->tot_triangles,
                                   "GP Stroke triangulation");
  
      for (int i = 0; i < gps->tot_triangles; i++) {
        memcpy(gps->triangles[i].verts, tmp_triangles[i], sizeof(uint[3]));
      }
  
      /* Copy UVs to bGPDspoint. */
      for (int i = 0; i < gps->totpoints; i++) {
        copy_v2_v2(gps->points[i].uv_fill, uv[i]);
      }
    }
    else {
      /* No triangles needed - Free anything allocated previously */
      if (gps->triangles) {
        MEM_freeN(gps->triangles);
      }
  
      gps->triangles = NULL;
    }
  
    /* clear memory */
    MEM_SAFE_FREE(tmp_triangles);
    MEM_SAFE_FREE(points2d);
    MEM_SAFE_FREE(uv);
  }
  
  /**
   * Update Stroke UV data.
   * \param gps: Grease pencil stroke
   */
  void BKE_gpencil_stroke_uv_update(bGPDstroke *gps)
  {
    if (gps == NULL || gps->totpoints == 0) {
      return;
    }
  
    bGPDspoint *pt = gps->points;
    float totlen = 0.0f;
    pt[0].uv_fac = totlen;
    for (int i = 1; i < gps->totpoints; i++) {
      totlen += len_v3v3(&pt[i - 1].x, &pt[i].x);
      pt[i].uv_fac = totlen;
    }
  }
  
  /**
   * Recalc all internal geometry data for the stroke
   * \param gps: Grease pencil stroke
   */
  void BKE_gpencil_stroke_geometry_update(bGPDstroke *gps)
  {
    if (gps == NULL) {
      return;
    }
  
    if (gps->totpoints > 2) {
      BKE_gpencil_stroke_fill_triangulate(gps);
    }
    else {
      gps->tot_triangles = 0;
      MEM_SAFE_FREE(gps->triangles);
    }
  
    /* calc uv data along the stroke */
    BKE_gpencil_stroke_uv_update(gps);
  
    /* Calc stroke bounding box. */
    BKE_gpencil_stroke_boundingbox_calc(gps);
  }
  
  /**
   * Calculate grease pencil stroke length.
   * \param gps: Grease pencil stroke
   * \param use_3d: Set to true to use 3D points
   * \return Length of the stroke
   */
  float BKE_gpencil_stroke_length(const bGPDstroke *gps, bool use_3d)
  {
    if (!gps->points || gps->totpoints < 2) {
      return 0.0f;
    }
    float *last_pt = &gps->points[0].x;
    float total_length = 0.0f;
    for (int i = 1; i < gps->totpoints; i++) {
      bGPDspoint *pt = &gps->points[i];
      if (use_3d) {
        total_length += len_v3v3(&pt->x, last_pt);
      }
      else {
        total_length += len_v2v2(&pt->x, last_pt);
      }
      last_pt = &pt->x;
    }
    return total_length;
  }
  
  /**
   * Trim stroke to the first intersection or loop.
   * \param gps: Stroke data
   */
  bool BKE_gpencil_stroke_trim(bGPDstroke *gps)
  {
    if (gps->totpoints < 4) {
      return false;
    }
    bool intersect = false;
    int start = 0;
    int end = 0;
    float point[3];
    /* loop segments from start until we have an intersection */
    for (int i = 0; i < gps->totpoints - 2; i++) {
      start = i;
      bGPDspoint *a = &gps->points[start];
      bGPDspoint *b = &gps->points[start + 1];
      for (int j = start + 2; j < gps->totpoints - 1; j++) {
        end = j + 1;
        bGPDspoint *c = &gps->points[j];
        bGPDspoint *d = &gps->points[end];
        float pointb[3];
        /* get intersection */
        if (isect_line_line_v3(&a->x, &b->x, &c->x, &d->x, point, pointb)) {
          if (len_v3(point) > 0.0f) {
            float closest[3];
            /* check intersection is on both lines */
            float lambda = closest_to_line_v3(closest, point, &a->x, &b->x);
            if ((lambda <= 0.0f) || (lambda >= 1.0f)) {
              continue;
            }
            lambda = closest_to_line_v3(closest, point, &c->x, &d->x);
            if ((lambda <= 0.0f) || (lambda >= 1.0f)) {
              continue;
            }
  
            intersect = true;
            break;
          }
        }
      }
      if (intersect) {
        break;
      }
    }
  
    /* trim unwanted points */
    if (intersect) {
  
      /* save points */
      bGPDspoint *old_points = MEM_dupallocN(gps->points);
      MDeformVert *old_dvert = NULL;
      MDeformVert *dvert_src = NULL;
  
      if (gps->dvert != NULL) {
        old_dvert = MEM_dupallocN(gps->dvert);
      }
  
      /* resize gps */
      int newtot = end - start + 1;
  
      gps->points = MEM_recallocN(gps->points, sizeof(*gps->points) * newtot);
      if (gps->dvert != NULL) {
        gps->dvert = MEM_recallocN(gps->dvert, sizeof(*gps->dvert) * newtot);
      }
  
      for (int i = 0; i < newtot; i++) {
        int idx = start + i;
        bGPDspoint *pt_src = &old_points[idx];
        bGPDspoint *pt_new = &gps->points[i];
        memcpy(pt_new, pt_src, sizeof(bGPDspoint));
        if (gps->dvert != NULL) {
          dvert_src = &old_dvert[idx];
          MDeformVert *dvert = &gps->dvert[i];
          memcpy(dvert, dvert_src, sizeof(MDeformVert));
          if (dvert_src->dw) {
            memcpy(dvert->dw, dvert_src->dw, sizeof(MDeformWeight));
          }
        }
        if (idx == start || idx == end) {
          copy_v3_v3(&pt_new->x, point);
        }
      }
  
      gps->totpoints = newtot;
  
      MEM_SAFE_FREE(old_points);
      MEM_SAFE_FREE(old_dvert);
    }
  
    BKE_gpencil_stroke_geometry_update(gps);
  
    return intersect;
  }
  
  /**
   * Close grease pencil stroke.
   * \param gps: Stroke to close
   */
  bool BKE_gpencil_stroke_close(bGPDstroke *gps)
  {
    bGPDspoint *pt1 = NULL;
    bGPDspoint *pt2 = NULL;
  
    /* Only can close a stroke with 3 points or more. */
    if (gps->totpoints < 3) {
      return false;
    }
  
    /* Calc average distance between points to get same level of sampling. */
    float dist_tot = 0.0f;
    for (int i = 0; i < gps->totpoints - 1; i++) {
      pt1 = &gps->points[i];
      pt2 = &gps->points[i + 1];
      dist_tot += len_v3v3(&pt1->x, &pt2->x);
    }
    /* Calc the average distance. */
    float dist_avg = dist_tot / (gps->totpoints - 1);
  
    /* Calc distance between last and first point. */
    pt1 = &gps->points[gps->totpoints - 1];
    pt2 = &gps->points[0];
    float dist_close = len_v3v3(&pt1->x, &pt2->x);
  
    /* if the distance to close is very small, don't need add points and just enable cyclic. */
    if (dist_close <= dist_avg) {
      gps->flag |= GP_STROKE_CYCLIC;
      return true;
    }
  
    /* Calc number of points required using the average distance. */
    int tot_newpoints = MAX2(dist_close / dist_avg, 1);
  
    /* Resize stroke array. */
    int old_tot = gps->totpoints;
    gps->totpoints += tot_newpoints;
    gps->points = MEM_recallocN(gps->points, sizeof(*gps->points) * gps->totpoints);
    if (gps->dvert != NULL) {
      gps->dvert = MEM_recallocN(gps->dvert, sizeof(*gps->dvert) * gps->totpoints);
    }
  
    /* Generate new points */
    pt1 = &gps->points[old_tot - 1];
    pt2 = &gps->points[0];
    bGPDspoint *pt = &gps->points[old_tot];
    for (int i = 1; i < tot_newpoints + 1; i++, pt++) {
      float step = (tot_newpoints > 1) ? ((float)i / (float)tot_newpoints) : 0.99f;
      /* Clamp last point to be near, but not on top of first point. */
      if ((tot_newpoints > 1) && (i == tot_newpoints)) {
        step *= 0.99f;
      }
  
      /* Average point. */
      interp_v3_v3v3(&pt->x, &pt1->x, &pt2->x, step);
      pt->pressure = interpf(pt2->pressure, pt1->pressure, step);
      pt->strength = interpf(pt2->strength, pt1->strength, step);
      pt->flag = 0;
      interp_v4_v4v4(pt->vert_color, pt1->vert_color, pt2->vert_color, step);
  
      /* Set weights. */
      if (gps->dvert != NULL) {
        MDeformVert *dvert1 = &gps->dvert[old_tot - 1];
        MDeformWeight *dw1 = BKE_defvert_ensure_index(dvert1, 0);
        float weight_1 = dw1 ? dw1->weight : 0.0f;
  
        MDeformVert *dvert2 = &gps->dvert[0];
        MDeformWeight *dw2 = BKE_defvert_ensure_index(dvert2, 0);
        float weight_2 = dw2 ? dw2->weight : 0.0f;
  
        MDeformVert *dvert_final = &gps->dvert[old_tot + i - 1];
        dvert_final->totweight = 0;
        MDeformWeight *dw = BKE_defvert_ensure_index(dvert_final, 0);
        if (dvert_final->dw) {
          dw->weight = interpf(weight_2, weight_1, step);
        }
      }
    }
  
    /* Enable cyclic flag. */
    gps->flag |= GP_STROKE_CYCLIC;
  
    return true;
  }
  
  /**
   * Dissolve points in stroke.
   * \param gpf: Grease pencil frame
   * \param gps: Grease pencil stroke
   * \param tag: Type of tag for point
   */
  void BKE_gpencil_dissolve_points(bGPDframe *gpf, bGPDstroke *gps, const short tag)
  {
    bGPDspoint *pt;
    MDeformVert *dvert = NULL;
    int i;
  
    int tot = gps->totpoints; /* number of points in new buffer */
    /* first pass: count points to remove */
    /* Count how many points are selected (i.e. how many to remove) */
    for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
      if (pt->flag & tag) {
        /* selected point - one of the points to remove */
        tot--;
      }
    }
  
    /* if no points are left, we simply delete the entire stroke */
    if (tot <= 0) {
      /* remove the entire stroke */
      if (gps->points) {
        MEM_freeN(gps->points);
      }
      if (gps->dvert) {
        BKE_gpencil_free_stroke_weights(gps);
        MEM_freeN(gps->dvert);
      }
      if (gps->triangles) {
        MEM_freeN(gps->triangles);
      }
      BLI_freelinkN(&gpf->strokes, gps);
    }
    else {
      /* just copy all points to keep into a smaller buffer */
      bGPDspoint *new_points = MEM_callocN(sizeof(bGPDspoint) * tot, "new gp stroke points copy");
      bGPDspoint *npt = new_points;
  
      MDeformVert *new_dvert = NULL;
      MDeformVert *ndvert = NULL;
  
      if (gps->dvert != NULL) {
        new_dvert = MEM_callocN(sizeof(MDeformVert) * tot, "new gp stroke weights copy");
        ndvert = new_dvert;
      }
  
      (gps->dvert != NULL) ? dvert = gps->dvert : NULL;
      for (i = 0, pt = gps->points; i < gps->totpoints; i++, pt++) {
        if ((pt->flag & tag) == 0) {
          *npt = *pt;
          npt++;
  
          if (gps->dvert != NULL) {
            *ndvert = *dvert;
            ndvert->dw = MEM_dupallocN(dvert->dw);
            ndvert++;
          }
        }
        if (gps->dvert != NULL) {
          dvert++;
        }
      }
  
      /* free the old buffer */
      if (gps->points) {
        MEM_freeN(gps->points);
      }
      if (gps->dvert) {
        BKE_gpencil_free_stroke_weights(gps);
        MEM_freeN(gps->dvert);
      }
  
      /* save the new buffer */
      gps->points = new_points;
      gps->dvert = new_dvert;
      gps->totpoints = tot;
  
      /* triangles cache needs to be recalculated */
      BKE_gpencil_stroke_geometry_update(gps);
    }
  }
  
  /**
   * Calculate stroke normals.
   * \param gps: Grease pencil stroke
   * \param r_normal: Return Normal vector normalized
   */
  void BKE_gpencil_stroke_normal(const bGPDstroke *gps, float r_normal[3])
  {
    if (gps->totpoints < 3) {
      zero_v3(r_normal);
      return;
    }
  
    bGPDspoint *points = gps->points;
    int totpoints = gps->totpoints;
  
    const bGPDspoint *pt0 = &points[0];
    const bGPDspoint *pt1 = &points[1];
    const bGPDspoint *pt3 = &points[(int)(totpoints * 0.75)];
  
    float vec1[3];
    float vec2[3];
  
    /* initial vector (p0 -> p1) */
    sub_v3_v3v3(vec1, &pt1->x, &pt0->x);
  
    /* point vector at 3/4 */
    sub_v3_v3v3(vec2, &pt3->x, &pt0->x);
  
    /* vector orthogonal to polygon plane */
    cross_v3_v3v3(r_normal, vec1, vec2);
  
    /* Normalize vector */
    normalize_v3(r_normal);
  }
  
  /* Stroke Simplify ------------------------------------- */
  
  /** Reduce a series of points to a simplified version, but
   * maintains the general shape of the series
   *
   * Ramer - Douglas - Peucker algorithm
   * by http ://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
   * \param gps: Grease pencil stroke
   * \param epsilon: Epsilon value to define precision of the algorithm
   */
  void BKE_gpencil_stroke_simplify_adaptive(bGPDstroke *gps, float epsilon)
  {
    bGPDspoint *old_points = MEM_dupallocN(gps->points);
    int totpoints = gps->totpoints;
    char *marked = NULL;
    char work;
  
    int start = 0;
    int end = gps->totpoints - 1;
  
    marked = MEM_callocN(totpoints, "GP marked array");
    marked[start] = 1;
    marked[end] = 1;
  
    work = 1;
    int totmarked = 0;
    /* while still reducing */
    while (work) {
      int ls, le;
      work = 0;
  
      ls = start;
      le = start + 1;
  
      /* while not over interval */
      while (ls < end) {
        int max_i = 0;
        /* divided to get more control */
        float max_dist = epsilon / 10.0f;
  
        /* find the next marked point */
        while (marked[le] == 0) {
          le++;
        }
  
        for (int i = ls + 1; i < le; i++) {
          float point_on_line[3];
          float dist;
  
          closest_to_line_segment_v3(
              point_on_line, &old_points[i].x, &old_points[ls].x, &old_points[le].x);
  
          dist = len_v3v3(point_on_line, &old_points[i].x);
  
          if (dist > max_dist) {
            max_dist = dist;
            max_i = i;
          }
        }
  
        if (max_i != 0) {
          work = 1;
          marked[max_i] = 1;
          totmarked++;
        }
  
        ls = le;
        le = ls + 1;
      }
    }
  
    /* adding points marked */
    MDeformVert *old_dvert = NULL;
    MDeformVert *dvert_src = NULL;
  
    if (gps->dvert != NULL) {
      old_dvert = MEM_dupallocN(gps->dvert);
    }
    /* resize gps */
    int j = 0;
    for (int i = 0; i < totpoints; i++) {
      bGPDspoint *pt_src = &old_points[i];
      bGPDspoint *pt = &gps->points[j];
  
      if ((marked[i]) || (i == 0) || (i == totpoints - 1)) {
        memcpy(pt, pt_src, sizeof(bGPDspoint));
        if (gps->dvert != NULL) {
          dvert_src = &old_dvert[i];
          MDeformVert *dvert = &gps->dvert[j];
          memcpy(dvert, dvert_src, sizeof(MDeformVert));
          if (dvert_src->dw) {
            memcpy(dvert->dw, dvert_src->dw, sizeof(MDeformWeight));
          }
        }
        j++;
      }
      else {
        if (gps->dvert != NULL) {
          dvert_src = &old_dvert[i];
          BKE_gpencil_free_point_weights(dvert_src);
        }
      }
    }
  
    gps->totpoints = j;
  
    /* Calc geometry data. */
    BKE_gpencil_stroke_geometry_update(gps);
  
    MEM_SAFE_FREE(old_points);
    MEM_SAFE_FREE(old_dvert);
    MEM_SAFE_FREE(marked);
  }
  
  /**
   * Simplify alternate vertex of stroke except extremes.
   * \param gps: Grease pencil stroke
   */
  void BKE_gpencil_stroke_simplify_fixed(bGPDstroke *gps)
  {
    if (gps->totpoints < 5) {
      return;
    }
  
    /* save points */
    bGPDspoint *old_points = MEM_dupallocN(gps->points);
    MDeformVert *old_dvert = NULL;
    MDeformVert *dvert_src = NULL;
  
    if (gps->dvert != NULL) {
      old_dvert = MEM_dupallocN(gps->dvert);
    }
  
    /* resize gps */
    int newtot = (gps->totpoints - 2) / 2;
    if (((gps->totpoints - 2) % 2) > 0) {
      newtot++;
    }
    newtot += 2;
  
    gps->points = MEM_recallocN(gps->points, sizeof(*gps->points) * newtot);
    if (gps->dvert != NULL) {
      gps->dvert = MEM_recallocN(gps->dvert, sizeof(*gps->dvert) * newtot);
    }
  
    int j = 0;
    for (int i = 0; i < gps->totpoints; i++) {
      bGPDspoint *pt_src = &old_points[i];
      bGPDspoint *pt = &gps->points[j];
  
      if ((i == 0) || (i == gps->totpoints - 1) || ((i % 2) > 0.0)) {
        memcpy(pt, pt_src, sizeof(bGPDspoint));
        if (gps->dvert != NULL) {
          dvert_src = &old_dvert[i];
          MDeformVert *dvert = &gps->dvert[j];
          memcpy(dvert, dvert_src, sizeof(MDeformVert));
          if (dvert_src->dw) {
            memcpy(dvert->dw, dvert_src->dw, sizeof(MDeformWeight));
          }
        }
        j++;
      }
      else {
        if (gps->dvert != NULL) {
          dvert_src = &old_dvert[i];
          BKE_gpencil_free_point_weights(dvert_src);
        }
      }
    }
  
    gps->totpoints = j;
    /* Calc geometry data. */
    BKE_gpencil_stroke_geometry_update(gps);
  
    MEM_SAFE_FREE(old_points);
    MEM_SAFE_FREE(old_dvert);
  }
  
  /**
   * Subdivide grease pencil stroke.
   * \param gps: Grease pencil stroke
   * \param level: Level of subdivision
   * \param type: Type of subdivision
   */
  void BKE_gpencil_stroke_subdivide(bGPDstroke *gps, int level, int type)
  {
    bGPDspoint *temp_points;
    MDeformVert *temp_dverts = NULL;
    MDeformVert *dvert = NULL;
    MDeformVert *dvert_final = NULL;
    MDeformVert *dvert_next = NULL;
    int totnewpoints, oldtotpoints;
    int i2;
  
    for (int s = 0; s < level; s++) {
      totnewpoints = gps->totpoints - 1;
      /* duplicate points in a temp area */
      temp_points = MEM_dupallocN(gps->points);
      oldtotpoints = gps->totpoints;
  
      /* resize the points arrays */
      gps->totpoints += totnewpoints;
      gps->points = MEM_recallocN(gps->points, sizeof(*gps->points) * gps->totpoints);
      if (gps->dvert != NULL) {
        temp_dverts = MEM_dupallocN(gps->dvert);
        gps->dvert = MEM_recallocN(gps->dvert, sizeof(*gps->dvert) * gps->totpoints);
      }
  
      /* move points from last to first to new place */
      i2 = gps->totpoints - 1;
      for (int i = oldtotpoints - 1; i > 0; i--) {
        bGPDspoint *pt = &temp_points[i];
        bGPDspoint *pt_final = &gps->points[i2];
  
        copy_v3_v3(&pt_final->x, &pt->x);
        pt_final->pressure = pt->pressure;
        pt_final->strength = pt->strength;
        pt_final->time = pt->time;
        pt_final->flag = pt->flag;
        pt_final->runtime.pt_orig = pt->runtime.pt_orig;
        pt_final->runtime.idx_orig = pt->runtime.idx_orig;
        copy_v4_v4(pt_final->vert_color, pt->vert_color);
  
        if (gps->dvert != NULL) {
          dvert = &temp_dverts[i];
          dvert_final = &gps->dvert[i2];
          dvert_final->totweight = dvert->totweight;
          dvert_final->dw = dvert->dw;
        }
        i2 -= 2;
      }
      /* interpolate mid points */
      i2 = 1;
      for (int i = 0; i < oldtotpoints - 1; i++) {
        bGPDspoint *pt = &temp_points[i];
        bGPDspoint *next = &temp_points[i + 1];
        bGPDspoint *pt_final = &gps->points[i2];
  
        /* add a half way point */
        interp_v3_v3v3(&pt_final->x, &pt->x, &next->x, 0.5f);
        pt_final->pressure = interpf(pt->pressure, next->pressure, 0.5f);
        pt_final->strength = interpf(pt->strength, next->strength, 0.5f);
        CLAMP(pt_final->strength, GPENCIL_STRENGTH_MIN, 1.0f);
        pt_final->time = interpf(pt->time, next->time, 0.5f);
        pt_final->runtime.pt_orig = NULL;
        pt_final->flag = 0;
        interp_v4_v4v4(pt_final->vert_color, pt->vert_color, next->vert_color, 0.5f);
  
        if (gps->dvert != NULL) {
          dvert = &temp_dverts[i];
          dvert_next = &temp_dverts[i + 1];
          dvert_final = &gps->dvert[i2];
  
          dvert_final->totweight = dvert->totweight;
          dvert_final->dw = MEM_dupallocN(dvert->dw);
  
          /* interpolate weight values */
          for (int d = 0; d < dvert->totweight; d++) {
            MDeformWeight *dw_a = &dvert->dw[d];
            if (dvert_next->totweight > d) {
              MDeformWeight *dw_b = &dvert_next->dw[d];
              MDeformWeight *dw_final = &dvert_final->dw[d];
              dw_final->weight = interpf(dw_a->weight, dw_b->weight, 0.5f);
            }
          }
        }
  
        i2 += 2;
      }
  
      MEM_SAFE_FREE(temp_points);
      MEM_SAFE_FREE(temp_dverts);
  
      /* move points to smooth stroke (not simple type )*/
      if (type != GP_SUBDIV_SIMPLE) {
        /* duplicate points in a temp area with the new subdivide data */
        temp_points = MEM_dupallocN(gps->points);
  
        /* extreme points are not changed */
        for (int i = 0; i < gps->totpoints - 2; i++) {
          bGPDspoint *pt = &temp_points[i];
          bGPDspoint *next = &temp_points[i + 1];
          bGPDspoint *pt_final = &gps->points[i + 1];
  
          /* move point */
          interp_v3_v3v3(&pt_final->x, &pt->x, &next->x, 0.5f);
        }
        /* free temp memory */
        MEM_SAFE_FREE(temp_points);
      }
    }
  
    /* Calc geometry data. */
    BKE_gpencil_stroke_geometry_update(gps);
  }
  
  /* Merge by distance ------------------------------------- */
  
  /**
   * Reduce a series of points when the distance is below a threshold.
   * Special case for first and last points (both are keeped) for other points,
   * the merge point always is at first point.
   * \param gpf: Grease Pencil frame
   * \param gps: Grease Pencil stroke
   * \param threshold: Distance between points
   * \param use_unselected: Set to true to analyze all stroke and not only selected points
   */
  void BKE_gpencil_stroke_merge_distance(bGPDframe *gpf,
                                         bGPDstroke *gps,
                                         const float threshold,
                                         const bool use_unselected)
  {
    bGPDspoint *pt = NULL;
    bGPDspoint *pt_next = NULL;
    float tagged = false;
    /* Use square distance to speed up loop */
    const float th_square = threshold * threshold;
    /* Need to have something to merge. */
    if (gps->totpoints < 2) {
      return;
    }
    int i = 0;
    int step = 1;
    while ((i < gps->totpoints - 1) && (i + step < gps->totpoints)) {
      pt = &gps->points[i];
      if (pt->flag & GP_SPOINT_TAG) {
        i++;
        step = 1;
        continue;
      }
      pt_next = &gps->points[i + step];
      /* Do not recalc tagged points. */
      if (pt_next->flag & GP_SPOINT_TAG) {
        step++;
        continue;
      }
      /* Check if contiguous points are selected. */
      if (!use_unselected) {
        if (((pt->flag & GP_SPOINT_SELECT) == 0) || ((pt_next->flag & GP_SPOINT_SELECT) == 0)) {
          i++;
          step = 1;
          continue;
        }
      }
      float len_square = len_squared_v3v3(&pt->x, &pt_next->x);
      if (len_square <= th_square) {
        tagged = true;
        if (i != gps->totpoints - 1) {
          /* Tag second point for delete. */
          pt_next->flag |= GP_SPOINT_TAG;
        }
        else {
          pt->flag |= GP_SPOINT_TAG;
        }
        /* Jump to next pair of points, keeping first point segment equals.*/
        step++;
      }
      else {
        /* Analyze next point. */
        i++;
        step = 1;
      }
    }
  
    /* Always untag extremes. */
    pt = &gps->points[0];
    pt->flag &= ~GP_SPOINT_TAG;
    pt = &gps->points[gps->totpoints - 1];
    pt->flag &= ~GP_SPOINT_TAG;
  
    /* Dissolve tagged points */
    if (tagged) {
      BKE_gpencil_dissolve_points(gpf, gps, GP_SPOINT_TAG);
    }
  
    /* Calc geometry data. */
    BKE_gpencil_stroke_geometry_update(gps);
  }
  
  typedef struct GpEdge {
    uint v1, v2;
    /* Coordinates. */
    float v1_co[3], v2_co[3];
    /* Normals. */
    float n1[3], n2[3];
    /* Direction of the segment. */
    float vec[3];
    int flag;
  } GpEdge;
  
  static int gpencil_next_edge(
      GpEdge *gp_edges, int totedges, GpEdge *gped_init, const float threshold, const bool reverse)
  {
    int edge = -1;
    float last_angle = 999999.0f;
    for (int i = 0; i < totedges; i++) {
      GpEdge *gped = &gp_edges[i];
      if (gped->flag != 0) {
        continue;
      }
      if (reverse) {
        if (gped_init->v1 != gped->v2) {
          continue;
        }
      }
      else {
        if (gped_init->v2 != gped->v1) {
          continue;
        }
      }
      /* Look for straight lines. */
      float angle = angle_v3v3(gped->vec, gped_init->vec);
      if ((angle < threshold) && (angle <= last_angle)) {
        edge = i;
        last_angle = angle;
      }
    }
  
    return edge;
  }
  
  static int gpencil_walk_edge(GHash *v_table,
                               GpEdge *gp_edges,
                               int totedges,
                               uint *stroke_array,
                               int init_idx,
                               const float angle,
                               const bool reverse)
  {
    GpEdge *gped_init = &gp_edges[init_idx];
    int idx = 1;
    int edge = 0;
    while (edge > -1) {
      edge = gpencil_next_edge(gp_edges, totedges, gped_init, angle, reverse);
      if (edge > -1) {
        GpEdge *gped = &gp_edges[edge];
        stroke_array[idx] = edge;
        gped->flag = 1;
        gped_init = &gp_edges[edge];
        idx++;
  
        /* Avoid to follow already visited vertice. */
        if (reverse) {
          if (BLI_ghash_haskey(v_table, POINTER_FROM_INT(gped->v1))) {
            edge = -1;
          }
          else {
            BLI_ghash_insert(v_table, POINTER_FROM_INT(gped->v1), POINTER_FROM_INT(gped->v1));
          }
        }
        else {
          if (BLI_ghash_haskey(v_table, POINTER_FROM_INT(gped->v2))) {
            edge = -1;
          }
          else {
            BLI_ghash_insert(v_table, POINTER_FROM_INT(gped->v2), POINTER_FROM_INT(gped->v2));
          }
        }
      }
    }
  
    return idx;
  }
  
  static void gpencil_generate_edgeloops(Object *ob,
                                         bGPDframe *gpf_stroke,
                                         int stroke_mat_index,
                                         const float angle,
                                         const int thickness,
                                         const float offset,
                                         const float matrix[4][4],
                                         const bool use_seams)
  {
    Mesh *me = (Mesh *)ob->data;
    if (me->totedge == 0) {
      return;
    }
  
    /* Arrays for all edge vertices (forward and backward) that form a edge loop.
     * This is reused for each edgeloop to create gpencil stroke. */
    uint *stroke = MEM_callocN(sizeof(uint) * me->totedge * 2, __func__);
    uint *stroke_fw = MEM_callocN(sizeof(uint) * me->totedge, __func__);
    uint *stroke_bw = MEM_callocN(sizeof(uint) * me->totedge, __func__);
  
    /* Create array with all edges. */
    GpEdge *gp_edges = MEM_callocN(sizeof(GpEdge) * me->totedge, __func__);
    GpEdge *gped = NULL;
    for (int i = 0; i < me->totedge; i++) {
      MEdge *ed = &me->medge[i];
      gped = &gp_edges[i];
      MVert *mv1 = &me->mvert[ed->v1];
      normal_short_to_float_v3(gped->n1, mv1->no);
  
      gped->v1 = ed->v1;
      copy_v3_v3(gped->v1_co, mv1->co);
  
      MVert *mv2 = &me->mvert[ed->v2];
      normal_short_to_float_v3(gped->n2, mv2->no);
      gped->v2 = ed->v2;
      copy_v3_v3(gped->v2_co, mv2->co);
  
      sub_v3_v3v3(gped->vec, mv1->co, mv2->co);
  
      /* If use seams, mark as done if not a seam. */
      if ((use_seams) && ((ed->flag & ME_SEAM) == 0)) {
        gped->flag = 1;
      }
    }
  
    /* Loop edges to find edgeloops */
    bool pending = true;
    int e = 0;
    while (pending) {
      /* Clear arrays of stroke. */
      memset(stroke_fw, 0, sizeof(uint) * me->totedge);
      memset(stroke_bw, 0, sizeof(uint) * me->totedge);
      memset(stroke, 0, sizeof(uint) * me->totedge * 2);
  
      gped = &gp_edges[e];
      /* Look first unused edge. */
      if (gped->flag != 0) {
        e++;
        if (e == me->totedge) {
          pending = false;
        }
        continue;
      }
      /* Add current edge to arrays. */
      stroke_fw[0] = e;
      stroke_bw[0] = e;
      gped->flag = 1;
  
      /* Hash used to avoid loop over same vertice. */
      GHash *v_table = BLI_ghash_int_new(__func__);
      /* Look forward edges. */
      int totedges = gpencil_walk_edge(v_table, gp_edges, me->totedge, stroke_fw, e, angle, false);
      /* Look backward edges. */
      int totbw = gpencil_walk_edge(v_table, gp_edges, me->totedge, stroke_bw, e, angle, true);
  
      BLI_ghash_free(v_table, NULL, NULL);
  
      /* Join both arrays. */
      int array_len = 0;
      for (int i = totbw - 1; i > 0; i--) {
        stroke[array_len] = stroke_bw[i];
        array_len++;
      }
      for (int i = 0; i < totedges; i++) {
        stroke[array_len] = stroke_fw[i];
        array_len++;
      }
  
      /* Create Stroke. */
      bGPDstroke *gps_stroke = BKE_gpencil_stroke_add(
          gpf_stroke, MAX2(stroke_mat_index, 0), array_len + 1, thickness * thickness, false);
  
      /* Create first segment. */
      float fpt[3];
      uint v = stroke[0];
      gped = &gp_edges[v];
      bGPDspoint *pt = &gps_stroke->points[0];
      mul_v3_v3fl(fpt, gped->n1, offset);
      add_v3_v3v3(&pt->x, gped->v1_co, fpt);
      mul_m4_v3(matrix, &pt->x);
  
      pt->pressure = 1.0f;
      pt->strength = 1.0f;
  
      pt = &gps_stroke->points[1];
      mul_v3_v3fl(fpt, gped->n2, offset);
      add_v3_v3v3(&pt->x, gped->v2_co, fpt);
      mul_m4_v3(matrix, &pt->x);
  
      pt->pressure = 1.0f;
      pt->strength = 1.0f;
  
      /* Add next segments. */
      for (int i = 1; i < array_len; i++) {
        v = stroke[i];
        gped = &gp_edges[v];
  
        pt = &gps_stroke->points[i + 1];
        mul_v3_v3fl(fpt, gped->n2, offset);
        add_v3_v3v3(&pt->x, gped->v2_co, fpt);
        mul_m4_v3(matrix, &pt->x);
  
        pt->pressure = 1.0f;
        pt->strength = 1.0f;
      }
  
      BKE_gpencil_stroke_geometry_update(gps_stroke);
    }
  
    /* Free memory. */
    MEM_SAFE_FREE(stroke);
    MEM_SAFE_FREE(stroke_fw);
    MEM_SAFE_FREE(stroke_bw);
    MEM_SAFE_FREE(gp_edges);
  }
  
  /* Helper: Add gpencil material using material as base. */
  static Material *gpencil_add_material(Main *bmain,
                                        Object *ob_gp,
                                        const char *name,
                                        const float color[4],
                                        const bool use_stroke,
                                        const bool use_fill,
                                        int *r_idx)
  {
    Material *mat_gp = BKE_gpencil_object_material_new(bmain, ob_gp, name, r_idx);
    MaterialGPencilStyle *gp_style = mat_gp->gp_style;
  
    /* Stroke color. */
    if (use_stroke) {
      ARRAY_SET_ITEMS(gp_style->stroke_rgba, 0.0f, 0.0f, 0.0f, 1.0f);
      gp_style->flag |= GP_MATERIAL_STROKE_SHOW;
    }
    else {
      copy_v4_v4(gp_style->stroke_rgba, color);
      gp_style->flag &= ~GP_MATERIAL_STROKE_SHOW;
    }
  
    /* Fill color. */
    copy_v4_v4(gp_style->fill_rgba, color);
    if (use_fill) {
      gp_style->flag |= GP_MATERIAL_FILL_SHOW;
    }
  
    /* Check at least one is enabled. */
    if (((gp_style->flag & GP_MATERIAL_STROKE_SHOW) == 0) &&
        ((gp_style->flag & GP_MATERIAL_FILL_SHOW) == 0)) {
      gp_style->flag |= GP_MATERIAL_STROKE_SHOW;
    }
  
    return mat_gp;
  }
  
  static int gpencil_material_find_index_by_name(Object *ob, const char *name)
  {
    for (int i = 0; i < ob->totcol; i++) {
      Material *ma = BKE_object_material_get(ob, i + 1);
      if ((ma != NULL) && (ma->gp_style != NULL) && (STREQ(ma->id.name + 2, name))) {
        return i;
      }
    }
  
    return -1;
  }
  
  /**
   * Create the name with the object name and a suffix.
   */
  static void make_element_name(const char *obname, const char *name, const int maxlen, char *r_name)
  {
    char str[256];
    SNPRINTF(str, "%s_%s", obname, name);
  
    /* Replace any point by underscore. */
    BLI_str_replace_char(str, '.', '_');
  
    BLI_strncpy_utf8(r_name, str, maxlen);
  }
  
  /**
   * Convert a mesh object to grease pencil stroke.
   *
   * \param bmain: Main thread pointer.
   * \param depsgraph: Original depsgraph.
   * \param scene: Original scene.
   * \param ob_gp: Grease pencil object to add strokes.
   * \param ob_mesh: Mesh to convert.
   * \param angle: Limit angle to consider a edgeloop ends.
   * \param thickness: Thickness of the strokes.
   * \param offset: Offset along the normals.
   * \param matrix: Transformation matrix.
   * \param frame_offset: Destination frame number offset.
   * \param use_seams: Only export seam edges.
   * \param use_faces: Export faces as filled strokes.
   */
  bool BKE_gpencil_convert_mesh(Main *bmain,
                                Depsgraph *depsgraph,
                                Scene *scene,
                                Object *ob_gp,
                                Object *ob_mesh,
                                const float angle,
                                const int thickness,
                                const float offset,
                                const float matrix[4][4],
                                const int frame_offset,
                                const bool use_seams,
                                const bool use_faces)
  {
    if (ELEM(NULL, ob_gp, ob_mesh) || (ob_gp->type != OB_GPENCIL) || (ob_gp->data == NULL)) {
      return false;
    }
  
    bGPdata *gpd = (bGPdata *)ob_gp->data;
  
    /* Use evaluated data to get mesh with all modifiers on top. */
    Object *ob_eval = (Object *)DEG_get_evaluated_object(depsgraph, ob_mesh);
    Mesh *me_eval = BKE_object_get_evaluated_mesh(ob_eval);
    MPoly *mp, *mpoly = me_eval->mpoly;
    MLoop *mloop = me_eval->mloop;
    int mpoly_len = me_eval->totpoly;
    char element_name[200];
  
    /* Need at least an edge. */
    if (me_eval->totvert < 2) {
      return false;
    }
  
    const float default_colors[2][4] = {{0.0f, 0.0f, 0.0f, 1.0f}, {0.7f, 0.7f, 0.7f, 1.0f}};
    /* Create stroke material. */
    make_element_name(ob_mesh->id.name + 2, "Stroke", 64, element_name);
    int stroke_mat_index = gpencil_material_find_index_by_name(ob_gp, element_name);
  
    if (stroke_mat_index == -1) {
      gpencil_add_material(
          bmain, ob_gp, element_name, default_colors[0], true, false, &stroke_mat_index);
    }
  
    /* Export faces as filled strokes. */
    if (use_faces) {
  
      /* Read all polygons and create fill for each. */
      if (mpoly_len > 0) {
        make_element_name(ob_mesh->id.name + 2, "Fills", 128, element_name);
        /* Create Layer and Frame. */
        bGPDlayer *gpl_fill = BKE_gpencil_layer_named_get(gpd, element_name);
        if (gpl_fill == NULL) {
          gpl_fill = BKE_gpencil_layer_addnew(gpd, element_name, true);
        }
        bGPDframe *gpf_fill = BKE_gpencil_layer_frame_get(
            gpl_fill, CFRA + frame_offset, GP_GETFRAME_ADD_NEW);
        int i;
        for (i = 0, mp = mpoly; i < mpoly_len; i++, mp++) {
          MLoop *ml = &mloop[mp->loopstart];
          /* Find material. */
          int mat_idx = 0;
          Material *ma = BKE_object_material_get(ob_mesh, mp->mat_nr + 1);
          make_element_name(
              ob_mesh->id.name + 2, (ma != NULL) ? ma->id.name + 2 : "Fill", 64, element_name);
          mat_idx = gpencil_material_find_index_by_name(ob_gp, element_name);
          if (mat_idx == -1) {
            float color[4];
            if (ma != NULL) {
              copy_v3_v3(color, &ma->r);
              color[3] = 1.0f;
            }
            else {
              copy_v4_v4(color, default_colors[1]);
            }
            gpencil_add_material(bmain, ob_gp, element_name, color, false, true, &mat_idx);
          }
  
          bGPDstroke *gps_fill = BKE_gpencil_stroke_add(gpf_fill, mat_idx, mp->totloop, 10, false);
          gps_fill->flag |= GP_STROKE_CYCLIC;
  
          /* Add points to strokes. */
          for (int j = 0; j < mp->totloop; j++, ml++) {
            MVert *mv = &me_eval->mvert[ml->v];
            bGPDspoint *pt = &gps_fill->points[j];
            copy_v3_v3(&pt->x, mv->co);
            mul_m4_v3(matrix, &pt->x);
            pt->pressure = 1.0f;
            pt->strength = 1.0f;
          }
          /* If has only 3 points subdivide. */
          if (mp->totloop == 3) {
            BKE_gpencil_stroke_subdivide(gps_fill, 1, GP_SUBDIV_SIMPLE);
          }
  
          BKE_gpencil_stroke_geometry_update(gps_fill);
        }
      }
    }
  
    /* Create stroke from edges. */
    make_element_name(ob_mesh->id.name + 2, "Lines", 128, element_name);
  
    /* Create Layer and Frame. */
    bGPDlayer *gpl_stroke = BKE_gpencil_layer_named_get(gpd, element_name);
    if (gpl_stroke == NULL) {
      gpl_stroke = BKE_gpencil_layer_addnew(gpd, element_name, true);
    }
    bGPDframe *gpf_stroke = BKE_gpencil_layer_frame_get(
        gpl_stroke, CFRA + frame_offset, GP_GETFRAME_ADD_NEW);
  
    gpencil_generate_edgeloops(
        ob_eval, gpf_stroke, stroke_mat_index, angle, thickness, offset, matrix, use_seams);
  
    /* Tag for recalculation */
    DEG_id_tag_update(&gpd->id, ID_RECALC_GEOMETRY | ID_RECALC_COPY_ON_WRITE);
  
    return true;
  }
  
  /**
   * Apply grease pencil Transforms.
   * \param gpd: Grease pencil data-block
   * \param mat: Transformation matrix
   */
  void BKE_gpencil_transform(bGPdata *gpd, const float mat[4][4])
  {
    if (gpd == NULL) {
      return;
    }
  
    const float scalef = mat4_to_scale(mat);
    LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
      /* FIXME: For now, we just skip parented layers.
       * Otherwise, we have to update each frame to find
       * the current parent position/effects.
       */
      if (gpl->parent) {
        continue;
      }
  
      LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
        LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
          bGPDspoint *pt;
          int i;
  
          for (pt = gps->points, i = 0; i < gps->totpoints; pt++, i++) {
            mul_m4_v3(mat, &pt->x);
            pt->pressure *= scalef;
          }
  
          /* Distortion may mean we need to re-triangulate. */
          BKE_gpencil_stroke_geometry_update(gps);
        }
      }
    }
  }
  
  /* Used for "move only origins" in object_data_transform.c */
  int BKE_gpencil_stroke_point_count(bGPdata *gpd)
  {
    int total_points = 0;
  
    if (gpd == NULL) {
      return 0;
    }
  
    LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
      /* FIXME: For now, we just skip parented layers.
       * Otherwise, we have to update each frame to find
       * the current parent position/effects.
       */
      if (gpl->parent) {
        continue;
      }
  
      LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
        LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
          total_points += gps->totpoints;
        }
      }
    }
    return total_points;
  }
  
  /* Used for "move only origins" in object_data_transform.c */
  void BKE_gpencil_point_coords_get(bGPdata *gpd, GPencilPointCoordinates *elem_data)
  {
    if (gpd == NULL) {
      return;
    }
  
    LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
      /* FIXME: For now, we just skip parented layers.
       * Otherwise, we have to update each frame to find
       * the current parent position/effects.
       */
      if (gpl->parent) {
        continue;
      }
  
      LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
        LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
          bGPDspoint *pt;
          int i;
  
          for (pt = gps->points, i = 0; i < gps->totpoints; pt++, i++) {
            copy_v3_v3(elem_data->co, &pt->x);
            elem_data->pressure = pt->pressure;
            elem_data++;
          }
        }
      }
    }
  }
  
  /* Used for "move only origins" in object_data_transform.c */
  void BKE_gpencil_point_coords_apply(bGPdata *gpd, const GPencilPointCoordinates *elem_data)
  {
    if (gpd == NULL) {
      return;
    }
  
    LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
      /* FIXME: For now, we just skip parented layers.
       * Otherwise, we have to update each frame to find
       * the current parent position/effects.
       */
      if (gpl->parent) {
        continue;
      }
  
      LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
        LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
          bGPDspoint *pt;
          int i;
  
          for (pt = gps->points, i = 0; i < gps->totpoints; pt++, i++) {
            copy_v3_v3(&pt->x, elem_data->co);
            pt->pressure = elem_data->pressure;
            elem_data++;
          }
  
          /* Distortion may mean we need to re-triangulate. */
          BKE_gpencil_stroke_geometry_update(gps);
        }
      }
    }
  }
  
  /* Used for "move only origins" in object_data_transform.c */
  void BKE_gpencil_point_coords_apply_with_mat4(bGPdata *gpd,
                                                const GPencilPointCoordinates *elem_data,
                                                const float mat[4][4])
  {
    if (gpd == NULL) {
      return;
    }
  
    const float scalef = mat4_to_scale(mat);
    LISTBASE_FOREACH (bGPDlayer *, gpl, &gpd->layers) {
      /* FIXME: For now, we just skip parented layers.
       * Otherwise, we have to update each frame to find
       * the current parent position/effects.
       */
      if (gpl->parent) {
        continue;
      }
  
      LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
        LISTBASE_FOREACH (bGPDstroke *, gps, &gpf->strokes) {
          bGPDspoint *pt;
          int i;
  
          for (pt = gps->points, i = 0; i < gps->totpoints; pt++, i++) {
            mul_v3_m4v3(&pt->x, mat, elem_data->co);
            pt->pressure = elem_data->pressure * scalef;
            elem_data++;
          }
  
          /* Distortion may mean we need to re-triangulate. */
          BKE_gpencil_stroke_geometry_update(gps);
        }
      }
    }
  }
  
  /**
   * Set a random color to stroke using vertex color.
   * \param gps: Stroke
   */
  void BKE_gpencil_stroke_set_random_color(bGPDstroke *gps)
  {
    BLI_assert(gps->totpoints > 0);
  
    float color[4] = {1.0f, 1.0f, 1.0f, 1.0f};
    bGPDspoint *pt = &gps->points[0];
    color[0] *= BLI_hash_int_01(BLI_hash_int_2d(gps->totpoints / 5, pt->x + pt->z));
    color[1] *= BLI_hash_int_01(BLI_hash_int_2d(gps->totpoints + pt->x, pt->y * pt->z + pt->x));
    color[2] *= BLI_hash_int_01(BLI_hash_int_2d(gps->totpoints - pt->x, pt->z * pt->x + pt->y));
    for (int i = 0; i < gps->totpoints; i++) {
      pt = &gps->points[i];
      copy_v4_v4(pt->vert_color, color);
    }
  }
  /** \} */
  