path: root/source/blender/editors/uvedit/uvedit_rip.c

/*
 * 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.
 */

/** \file
 * \ingroup eduv
 */

#include <math.h>
#include <stdlib.h>
#include <string.h>

#include "MEM_guardedalloc.h"

#include "BLI_ghash.h"
#include "BLI_linklist_stack.h"
#include "BLI_math.h"
#include "BLI_math_vector.h"
#include "BLI_utildefines.h"

#include "DNA_image_types.h"
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
#include "DNA_node_types.h"
#include "DNA_object_types.h"
#include "DNA_scene_types.h"
#include "DNA_space_types.h"

#include "BKE_context.h"
#include "BKE_customdata.h"
#include "BKE_editmesh.h"
#include "BKE_layer.h"
#include "BKE_report.h"

#include "DEG_depsgraph.h"

#include "ED_screen.h"
#include "ED_transform.h"
#include "ED_uvedit.h"

#include "RNA_access.h"
#include "RNA_define.h"

#include "WM_api.h"
#include "WM_types.h"

#include "UI_view2d.h"

#include "uvedit_intern.h"

/* -------------------------------------------------------------------- */
/** \name UV Loop Rip Data Struct
 * \{ */

/** Unordered loop data, stored in #BMLoop.head.index. */
typedef struct ULData {
  /** When this UV is selected as well as the next UV. */
  uint is_select_edge : 1;
  /**
   * When only this UV is selected and none of the other UV's
   * around the connected fan are attached to an edge.
   *
   * In this case there is no need to detect contiguous loops,
   * each isolated case is handled on it's own, no need to walk over selected edges.
   *
   * \note This flag isn't flushed to other loops which could also have this enabled.
   * Currently it's not necessary since we can start off on any one of these loops,
   * then walk onto the other loops around the uv-fan, without having the flag to be
   * set on all loops.
   */
  uint is_select_vert_single : 1;
  /** This could be a face-tag. */
  uint is_select_all : 1;
  /** Use when building the rip-pairs stack. */
  uint in_stack : 1;
  /** Set once this has been added into a #UVRipPairs. */
  uint in_rip_pairs : 1;
  /** The side this loop is part of. */
  uint side : 1;
  /**
   * Paranoid check to ensure we don't enter eternal loop swapping sides,
   * this could happen with float precision error, making a swap to measure as slightly better
   * depending on the order of addition.
   */
  uint side_was_swapped : 1;
} ULData;

/** Ensure this fits in an int (loop index). */
BLI_STATIC_ASSERT(sizeof(ULData) <= sizeof(int), "");

BLI_INLINE ULData *UL(BMLoop *l)
{
  return (ULData *)&l->head.index;
}

/** \} */

/* -------------------------------------------------------------------- */
/** \name UV Utilities
 * \{ */

static BMLoop *bm_loop_find_other_radial_loop_with_visible_face(BMLoop *l_src,
                                                                const int cd_loop_uv_offset)
{
  BMLoop *l_other = NULL;
  BMLoop *l_iter = l_src->radial_next;
  if (l_iter != l_src) {
    do {
      if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG) && UL(l_iter)->is_select_edge &&
          BM_loop_uv_share_edge_check(l_src, l_iter, cd_loop_uv_offset)) {
        /* Check UV's are contiguous. */
        if (l_other == NULL) {
          l_other = l_iter;
        }
        else {
          /* Only use when there is a single alternative. */
          l_other = NULL;
          break;
        }
      }
    } while ((l_iter = l_iter->radial_next) != l_src);
  }
  return l_other;
}

static BMLoop *bm_loop_find_other_fan_loop_with_visible_face(BMLoop *l_src,
                                                             BMVert *v_src,
                                                             const int cd_loop_uv_offset)
{
  BLI_assert(BM_vert_in_edge(l_src->e, v_src));
  BMLoop *l_other = NULL;
  BMLoop *l_iter = l_src->radial_next;
  if (l_iter != l_src) {
    do {
      if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG) &&
          BM_loop_uv_share_edge_check(l_src, l_iter, cd_loop_uv_offset)) {
        /* Check UV's are contiguous. */
        if (l_other == NULL) {
          l_other = l_iter;
        }
        else {
          /* Only use when there is a single alternative. */
          l_other = NULL;
          break;
        }
      }
    } while ((l_iter = l_iter->radial_next) != l_src);
  }
  if (l_other != NULL) {
    if (l_other->v == v_src) {
      /* do nothing. */
    }
    else if (l_other->next->v == v_src) {
      l_other = l_other->next;
    }
    else if (l_other->prev->v == v_src) {
      l_other = l_other->prev;
    }
    else {
      BLI_assert(0);
    }
  }
  return l_other;
}

/**
 * A version of #BM_vert_step_fan_loop that checks UV's.
 */
static BMLoop *bm_vert_step_fan_loop_uv(BMLoop *l, BMEdge **e_step, const int cd_loop_uv_offset)
{
  BMEdge *e_prev = *e_step;
  BMLoop *l_next;
  if (l->e == e_prev) {
    l_next = l->prev;
  }
  else if (l->prev->e == e_prev) {
    l_next = l;
  }
  else {
    BLI_assert(0);
    return NULL;
  }

  *e_step = l_next->e;

  return bm_loop_find_other_fan_loop_with_visible_face(l_next, l->v, cd_loop_uv_offset);
}

static void bm_loop_uv_select_single_vert_validate(BMLoop *l_init, const int cd_loop_uv_offset)
{
  const MLoopUV *luv_init = BM_ELEM_CD_GET_VOID_P(l_init, cd_loop_uv_offset);
  BMIter liter;
  BMLoop *l;
  bool is_single_vert = true;
  BM_ITER_ELEM (l, &liter, l_init->v, BM_LOOPS_OF_VERT) {
    const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
    if (equals_v2v2(luv_init->uv, luv->uv)) {
      if (UL(l->prev)->is_select_edge || UL(l)->is_select_edge) {
        is_single_vert = false;
        break;
      }
    }
  }
  if (is_single_vert == false) {
    BM_ITER_ELEM (l, &liter, l_init->v, BM_LOOPS_OF_VERT) {
      if (UL(l)->is_select_vert_single) {
        const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
        if (equals_v2v2(luv_init->uv, luv->uv)) {
          UL(l)->is_select_vert_single = false;
        }
      }
    }
  }
}

/**
 * The corner return values calculate the angle between both loops,
 * the edge values pick the closest to the either edge (ignoring the center).
 *
 * \param dir: Direction to calculate the angle to (normalized and aspect corrected).
 */
static void bm_loop_calc_uv_angle_from_dir(BMLoop *l,
                                           const float dir[2],
                                           const float aspect_y,
                                           const int cd_loop_uv_offset,
                                           float *r_corner_angle,
                                           float *r_edge_angle,
                                           int *r_edge_index)
{
  /* Calculate 3 directions, return the shortest angle. */
  float dir_test[3][2];
  const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
  const MLoopUV *luv_prev = BM_ELEM_CD_GET_VOID_P(l->prev, cd_loop_uv_offset);
  const MLoopUV *luv_next = BM_ELEM_CD_GET_VOID_P(l->next, cd_loop_uv_offset);

  sub_v2_v2v2(dir_test[0], luv->uv, luv_prev->uv);
  sub_v2_v2v2(dir_test[2], luv->uv, luv_next->uv);
  dir_test[0][1] /= aspect_y;
  dir_test[2][1] /= aspect_y;

  normalize_v2(dir_test[0]);
  normalize_v2(dir_test[2]);

  /* Calculate the orthogonal line (same as negating one, then adding). */
  sub_v2_v2v2(dir_test[1], dir_test[0], dir_test[2]);
  normalize_v2(dir_test[1]);

  /* Rotate 90 degrees. */
  SWAP(float, dir_test[1][0], dir_test[1][1]);
  dir_test[1][1] *= -1.0f;

  if (BM_face_uv_calc_cross(l->f, cd_loop_uv_offset) > 0.0f) {
    negate_v2(dir_test[1]);
  }

  const float angles[3] = {
      angle_v2v2(dir, dir_test[0]),
      angle_v2v2(dir, dir_test[1]),
      angle_v2v2(dir, dir_test[2]),
  };

  /* Set the corner values. */
  *r_corner_angle = angles[1];

  /* Set the edge values. */
  if (angles[0] < angles[2]) {
    *r_edge_angle = angles[0];
    *r_edge_index = -1;
  }
  else {
    *r_edge_angle = angles[2];
    *r_edge_index = 1;
  }
}

/** \} */

/* -------------------------------------------------------------------- */
/** \name UV Rip Single
 * \{ */

typedef struct UVRipSingle {
  /** Walk around the selected UV point, store #BMLoop. */
  GSet *loops;
} UVRipSingle;

/**
 * Handle single loop, the following cases:
 *
 * - An isolated fan, without a shared UV edge to other fans which share the same coordinate,
 *   in this case we just need to pick the closest fan to \a co.
 *
 * - In the case of contiguous loops (part of the same fan).
 *   Rip away the loops connected to the closest edge.
 *
 * - In the case of 2 contiguous loops.
 *   Rip the closest loop away.
 *
 * \note This matches the behavior of edit-mesh rip tool.
 */
static UVRipSingle *uv_rip_single_from_loop(BMLoop *l_init_orig,
                                            const float co[2],
                                            const float aspect_y,
                                            const int cd_loop_uv_offset)
{
  UVRipSingle *rip = MEM_callocN(sizeof(*rip), __func__);
  const float *co_center =
      (((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_init_orig, cd_loop_uv_offset))->uv);
  rip->loops = BLI_gset_ptr_new(__func__);

  /* Track the closest loop, start walking from this so in the event we have multiple
   * disconnected fans, we can rip away loops connected to this one. */
  BMLoop *l_init = NULL;
  BMLoop *l_init_edge = NULL;
  float corner_angle_best = FLT_MAX;
  float edge_angle_best = FLT_MAX;
  int edge_index_best = 0; /* -1 or +1 (never center). */

  /* Calculate the direction from the cursor with aspect correction. */
  float dir_co[2];
  sub_v2_v2v2(dir_co, co_center, co);
  dir_co[1] /= aspect_y;
  if (UNLIKELY(normalize_v2(dir_co) == 0.0)) {
    dir_co[1] = 1.0f;
  }

  int uv_fan_count_all = 0;
  {
    BMIter liter;
    BMLoop *l;
    BM_ITER_ELEM (l, &liter, l_init_orig->v, BM_LOOPS_OF_VERT) {
      if (BM_elem_flag_test(l->f, BM_ELEM_TAG)) {
        const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
        if (equals_v2v2(co_center, luv->uv)) {
          uv_fan_count_all += 1;
          /* Clear at the same time. */
          UL(l)->is_select_vert_single = true;
          UL(l)->side = 0;
          BLI_gset_add(rip->loops, l);

          /* Update `l_init_close` */
          float corner_angle_test;
          float edge_angle_test;
          int edge_index_test;
          bm_loop_calc_uv_angle_from_dir(l,
                                         dir_co,
                                         aspect_y,
                                         cd_loop_uv_offset,
                                         &corner_angle_test,
                                         &edge_angle_test,
                                         &edge_index_test);
          if ((corner_angle_best == FLT_MAX) || (corner_angle_test < corner_angle_best)) {
            corner_angle_best = corner_angle_test;
            l_init = l;
          }

          /* Trick so we don't consider concave corners further away than they should be. */
          edge_angle_test = min_ff(corner_angle_test, edge_angle_test);

          if ((edge_angle_best == FLT_MAX) || (edge_angle_test < edge_angle_best)) {
            edge_angle_best = edge_angle_test;
            edge_index_best = edge_index_test;
            l_init_edge = l;
          }
        }
      }
    }
  }

  /* Walk around the `l_init` in both directions of the UV fan. */
  int uv_fan_count_contiguous = 1;
  UL(l_init)->side = 1;
  for (int i = 0; i < 2; i += 1) {
    BMEdge *e_prev = i ? l_init->e : l_init->prev->e;
    BMLoop *l_iter = l_init;
    while (((l_iter = bm_vert_step_fan_loop_uv(l_iter, &e_prev, cd_loop_uv_offset)) != l_init) &&
           (l_iter != NULL) && (UL(l_iter)->side == 0)) {
      uv_fan_count_contiguous += 1;
      /* Keep. */
      UL(l_iter)->side = 1;
    }
    /* May be useful to know if the fan is closed, currently it's not needed. */
#if 0
    if (l_iter == l_init) {
      is_closed = true;
    }
#endif
  }

  if (uv_fan_count_contiguous != uv_fan_count_all) {
    /* Simply rip off the current fan, all tagging is done. */
  }
  else {
    GSetIterator gs_iter;
    GSET_ITER (gs_iter, rip->loops) {
      BMLoop *l = BLI_gsetIterator_getKey(&gs_iter);
      UL(l)->side = 0;
    }

    if (uv_fan_count_contiguous <= 2) {
      /* Simple case, rip away the closest loop. */
      UL(l_init)->side = 1;
    }
    else {
      /* Rip away from the closest edge. */
      BMLoop *l_radial_init = (edge_index_best == -1) ? l_init_edge->prev : l_init_edge;
      BMLoop *l_radial_iter = l_radial_init;
      do {
        if (BM_loop_uv_share_edge_check(l_radial_init, l_radial_iter, cd_loop_uv_offset)) {
          BMLoop *l = (l_radial_iter->v == l_init->v) ? l_radial_iter : l_radial_iter->next;
          BLI_assert(l->v == l_init->v);
          /* Keep. */
          UL(l)->side = 1;
        }
      } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_init);
    }
  }

  return rip;
}

static void uv_rip_single_free(UVRipSingle *rip)
{
  BLI_gset_free(rip->loops, NULL);
  MEM_freeN(rip);
}

/** \} */

/* -------------------------------------------------------------------- */
/** \name UV Rip Loop Pairs
 * \{ */

typedef struct UVRipPairs {
  /** Walk along the UV selection, store #BMLoop. */
  GSet *loops;
} UVRipPairs;

static void uv_rip_pairs_add(UVRipPairs *rip, BMLoop *l)
{
  ULData *ul = UL(l);
  BLI_assert(!BLI_gset_haskey(rip->loops, l));
  BLI_assert(ul->in_rip_pairs == false);
  ul->in_rip_pairs = true;
  BLI_gset_add(rip->loops, l);
}

static void uv_rip_pairs_remove(UVRipPairs *rip, BMLoop *l)
{
  ULData *ul = UL(l);
  BLI_assert(BLI_gset_haskey(rip->loops, l));
  BLI_assert(ul->in_rip_pairs == true);
  ul->in_rip_pairs = false;
  BLI_gset_remove(rip->loops, l, NULL);
}

/**
 * \note While this isn't especially efficient,
 * this is only needed for rip-pairs end-points (only two per contiguous selection loop).
 */
static float uv_rip_pairs_calc_uv_angle(BMLoop *l_init,
                                        uint side,
                                        const float aspect_y,
                                        const int cd_loop_uv_offset)
{
  BMIter liter;
  const MLoopUV *luv_init = BM_ELEM_CD_GET_VOID_P(l_init, cd_loop_uv_offset);
  float angle_of_side = 0.0f;
  BMLoop *l;
  BM_ITER_ELEM (l, &liter, l_init->v, BM_LOOPS_OF_VERT) {
    if (UL(l)->in_rip_pairs) {
      if (UL(l)->side == side) {
        const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
        if (equals_v2v2(luv_init->uv, luv->uv)) {
          const MLoopUV *luv_prev = BM_ELEM_CD_GET_VOID_P(l->prev, cd_loop_uv_offset);
          const MLoopUV *luv_next = BM_ELEM_CD_GET_VOID_P(l->next, cd_loop_uv_offset);
          float dir_prev[2], dir_next[2];
          sub_v2_v2v2(dir_prev, luv_prev->uv, luv->uv);
          sub_v2_v2v2(dir_next, luv_next->uv, luv->uv);
          dir_prev[1] /= aspect_y;
          dir_next[1] /= aspect_y;
          const float luv_angle = angle_v2v2(dir_prev, dir_next);
          if (LIKELY(isfinite(luv_angle))) {
            angle_of_side += luv_angle;
          }
        }
      }
    }
  }
  return angle_of_side;
}

static int uv_rip_pairs_loop_count_on_side(BMLoop *l_init, uint side, const int cd_loop_uv_offset)
{
  const MLoopUV *luv_init = BM_ELEM_CD_GET_VOID_P(l_init, cd_loop_uv_offset);
  int count = 0;
  BMIter liter;
  BMLoop *l;
  BM_ITER_ELEM (l, &liter, l_init->v, BM_LOOPS_OF_VERT) {
    if (UL(l)->in_rip_pairs) {
      if (UL(l)->side == side) {
        const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
        if (equals_v2v2(luv_init->uv, luv->uv)) {
          count += 1;
        }
      }
    }
  }
  return count;
}

static bool uv_rip_pairs_loop_change_sides_test(BMLoop *l_switch,
                                                BMLoop *l_target,
                                                const float aspect_y,
                                                const int cd_loop_uv_offset)
{
  const int side_a = UL(l_switch)->side;
  const int side_b = UL(l_target)->side;

  BLI_assert(UL(l_switch)->side != UL(l_target)->side);

  /* First, check if this is a simple grid topology,
   * in that case always choose the adjacent edge. */
  const int count_a = uv_rip_pairs_loop_count_on_side(l_switch, side_a, cd_loop_uv_offset);
  const int count_b = uv_rip_pairs_loop_count_on_side(l_target, side_b, cd_loop_uv_offset);
  if (count_a + count_b == 4) {
    return count_a > count_b;
  }
  else {
    const float angle_a_before = uv_rip_pairs_calc_uv_angle(
        l_switch, side_a, aspect_y, cd_loop_uv_offset);
    const float angle_b_before = uv_rip_pairs_calc_uv_angle(
        l_target, side_b, aspect_y, cd_loop_uv_offset);

    UL(l_switch)->side = side_b;

    const float angle_a_after = uv_rip_pairs_calc_uv_angle(
        l_switch, side_a, aspect_y, cd_loop_uv_offset);
    const float angle_b_after = uv_rip_pairs_calc_uv_angle(
        l_target, side_b, aspect_y, cd_loop_uv_offset);

    UL(l_switch)->side = side_a;

    return fabsf(angle_a_before - angle_b_before) > fabsf(angle_a_after - angle_b_after);
  }
}

/**
 * Create 2x sides of a UV rip-pairs, the result is unordered, supporting non-contiguous rails.
 *
 * \param l_init: A loop on a boundary which can be used to initialize flood-filling.
 * This will always be added to the first side. Other loops will be added to the second side.
 *
 * \note We could have more than two sides, however in practice this almost never happens.
 */
static UVRipPairs *uv_rip_pairs_from_loop(BMLoop *l_init,
                                          const float aspect_y,
                                          const int cd_loop_uv_offset)
{
  UVRipPairs *rip = MEM_callocN(sizeof(*rip), __func__);
  rip->loops = BLI_gset_ptr_new(__func__);

  /* We can rely on this stack being small, as we're walking down two sides of an edge loop,
   * so the stack wont be much larger than the total number of fans at any one vertex. */
  BLI_SMALLSTACK_DECLARE(stack, BMLoop *);

  /* Needed for cases when we walk onto loops which already have a side assigned,
   * in this case we need to pick a better side (see #uv_rip_pairs_loop_change_sides_test)
   * and put the loop back in the stack,
   * which is needed in the case adjacent loops should also switch sides. */
#define UV_SET_SIDE_AND_REMOVE_FROM_RAIL(loop, side_value) \
  { \
    BLI_assert(UL(loop)->side_was_swapped == false); \
    BLI_assert(UL(loop)->side != side_value); \
    if (!UL(loop)->in_stack) { \
      BLI_SMALLSTACK_PUSH(stack, loop); \
      UL(loop)->in_stack = true; \
    } \
    if (UL(loop)->in_rip_pairs) { \
      uv_rip_pairs_remove(rip, loop); \
    } \
    UL(loop)->side = side_value; \
    UL(loop)->side_was_swapped = true; \
  }

  /* Initialize the stack. */
  BLI_SMALLSTACK_PUSH(stack, l_init);
  UL(l_init)->in_stack = true;

  BMLoop *l_step;
  while ((l_step = BLI_SMALLSTACK_POP(stack))) {
    int side = UL(l_step)->side;
    UL(l_step)->in_stack = false;

    /* Note that we could add all loops into the rip-pairs when adding into the stack,
     * however this complicates removal, so add into the rip-pairs when popping from the stack. */
    uv_rip_pairs_add(rip, l_step);

    /* Add to the other side if it exists. */
    if (UL(l_step)->is_select_edge) {
      BMLoop *l_other = bm_loop_find_other_radial_loop_with_visible_face(l_step,
                                                                         cd_loop_uv_offset);
      if (l_other != NULL) {
        if (!UL(l_other)->in_rip_pairs && !UL(l_other)->in_stack) {
          BLI_SMALLSTACK_PUSH(stack, l_other);
          UL(l_other)->in_stack = true;
          UL(l_other)->side = !side;
        }
        else {
          if (UL(l_other)->side == side) {
            if (UL(l_other)->side_was_swapped == false) {
              UV_SET_SIDE_AND_REMOVE_FROM_RAIL(l_other, !side);
            }
          }
        }
      }

      /* Add the next loop along the edge on the same side. */
      l_other = l_step->next;
      if (!UL(l_other)->in_rip_pairs && !UL(l_other)->in_stack) {
        BLI_SMALLSTACK_PUSH(stack, l_other);
        UL(l_other)->in_stack = true;
        UL(l_other)->side = side;
      }
      else {
        if (UL(l_other)->side != side) {
          if ((UL(l_other)->side_was_swapped == false) &&
              uv_rip_pairs_loop_change_sides_test(l_other, l_step, aspect_y, cd_loop_uv_offset)) {
            UV_SET_SIDE_AND_REMOVE_FROM_RAIL(l_other, side);
          }
        }
      }
    }

    /* Walk over the fan of loops, starting from `l_step` in both directions. */
    for (int i = 0; i < 2; i++) {
      BMLoop *l_radial_first = i ? l_step : l_step->prev;
      if (l_radial_first != l_radial_first->radial_next) {
        BMEdge *e_radial = l_radial_first->e;
        BMLoop *l_radial_iter = l_radial_first->radial_next;
        do {
          /* Not a boundary and visible. */
          if (!UL(l_radial_iter)->is_select_edge &&
              BM_elem_flag_test(l_radial_iter->f, BM_ELEM_TAG)) {
            BMLoop *l_other = (l_radial_iter->v == l_step->v) ? l_radial_iter :
                                                                l_radial_iter->next;
            BLI_assert(l_other->v == l_step->v);
            if (BM_edge_uv_share_vert_check(e_radial, l_other, l_step, cd_loop_uv_offset)) {
              if (!UL(l_other)->in_rip_pairs && !UL(l_other)->in_stack) {
                BLI_SMALLSTACK_PUSH(stack, l_other);
                UL(l_other)->in_stack = true;
                UL(l_other)->side = side;
              }
              else {
                if (UL(l_other)->side != side) {
                  if ((UL(l_other)->side_was_swapped == false) &&
                      uv_rip_pairs_loop_change_sides_test(
                          l_other, l_step, aspect_y, cd_loop_uv_offset)) {
                    UV_SET_SIDE_AND_REMOVE_FROM_RAIL(l_other, side);
                  }
                }
              }
            }
          }
        } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_first);
      }
    }
  }

#undef UV_SET_SIDE_AND_REMOVE_FROM_RAIL

  return rip;
}

static void uv_rip_pairs_free(UVRipPairs *rip)
{
  BLI_gset_free(rip->loops, NULL);
  MEM_freeN(rip);
}

/**
 * This is an approximation, it's easily good enough for our purpose.
 */
static bool uv_rip_pairs_calc_center_and_direction(UVRipPairs *rip,
                                                   const int cd_loop_uv_offset,
                                                   float r_center[2],
                                                   float r_dir_side[2][2])
{
  zero_v2(r_center);
  int center_total = 0;
  int side_total[2] = {0, 0};

  for (int i = 0; i < 2; i++) {
    zero_v2(r_dir_side[i]);
  }
  GSetIterator gs_iter;
  GSET_ITER (gs_iter, rip->loops) {
    BMLoop *l = BLI_gsetIterator_getKey(&gs_iter);
    int side = UL(l)->side;
    const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
    add_v2_v2(r_center, luv->uv);

    float dir[2];
    if (!UL(l)->is_select_edge) {
      const MLoopUV *luv_next = BM_ELEM_CD_GET_VOID_P(l->next, cd_loop_uv_offset);
      sub_v2_v2v2(dir, luv_next->uv, luv->uv);
      add_v2_v2(r_dir_side[side], dir);
    }
    if (!UL(l->prev)->is_select_edge) {
      const MLoopUV *luv_prev = BM_ELEM_CD_GET_VOID_P(l->prev, cd_loop_uv_offset);
      sub_v2_v2v2(dir, luv_prev->uv, luv->uv);
      add_v2_v2(r_dir_side[side], dir);
    }
    side_total[side] += 1;
  }
  center_total += BLI_gset_len(rip->loops);

  for (int i = 0; i < 2; i++) {
    normalize_v2(r_dir_side[i]);
  }
  mul_v2_fl(r_center, 1.0f / center_total);

  /* If only a single side is selected, don't handle this rip-pairs. */
  return side_total[0] && side_total[1];
}

/** \} */

/* -------------------------------------------------------------------- */
/** \name UV Rip Main Function
 * \{ */

/**
 * \return true when a change was made.
 */
static bool uv_rip_object(Scene *scene, Object *obedit, const float co[2], const float aspect_y)
{
  Mesh *me = (Mesh *)obedit->data;
  BMEditMesh *em = me->edit_mesh;
  BMesh *bm = em->bm;
  const int cd_loop_uv_offset = CustomData_get_offset(&em->bm->ldata, CD_MLOOPUV);

  BMFace *efa;
  BMIter iter, liter;
  BMLoop *l;

  const ULData ul_clear = {0};

  bool changed = false;

  BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
    BM_elem_flag_set(efa, BM_ELEM_TAG, uvedit_face_visible_test(scene, efa));
    BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
      ULData *ul = UL(l);
      *ul = ul_clear;
    }
  }
  bm->elem_index_dirty |= BM_LOOP;

  bool is_select_all_any = false;
  BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
    if (BM_elem_flag_test(efa, BM_ELEM_TAG)) {
      bool is_all = true;
      BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
        const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
        if (luv->flag & MLOOPUV_VERTSEL) {
          const MLoopUV *luv_prev = BM_ELEM_CD_GET_VOID_P(l->prev, cd_loop_uv_offset);
          const MLoopUV *luv_next = BM_ELEM_CD_GET_VOID_P(l->next, cd_loop_uv_offset);
          if (luv_next->flag & MLOOPUV_VERTSEL) {
            UL(l)->is_select_edge = true;
          }
          else {
            if ((luv_prev->flag & MLOOPUV_VERTSEL) == 0) {
              /* #bm_loop_uv_select_single_vert_validate validates below. */
              UL(l)->is_select_vert_single = true;
            }
          }
        }
        else {
          is_all = false;
        }
      }
      if (is_all) {
        BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
          UL(l)->is_select_all = true;
        }
        is_select_all_any = true;
      }
    }
  }

  /* Remove #ULData.is_select_vert_single when connected to selected edges. */
  BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
    if (BM_elem_flag_test(efa, BM_ELEM_TAG)) {
      BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
        if (UL(l)->is_select_vert_single) {
          bm_loop_uv_select_single_vert_validate(l, cd_loop_uv_offset);
        }
      }
    }
  }

  /* Special case: if we have selected faces, isolated them.
   * This isn't a rip, however it's useful for users as a quick way
   * to detach the selection.
   *
   * We could also extract an edge loop from the boundary
   * however in practice it's not that useful, see T78751. */
  if (is_select_all_any) {
    BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
      BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
        if (!UL(l)->is_select_all) {
          MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
          if (luv->flag & MLOOPUV_VERTSEL) {
            luv->flag &= ~MLOOPUV_VERTSEL;
            changed = true;
          }
        }
      }
    }
    return changed;
  }

  /* Extract loop pairs or single loops. */
  BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
    if (BM_elem_flag_test(efa, BM_ELEM_TAG)) {
      BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) {
        if (UL(l)->is_select_edge) {
          if (!UL(l)->in_rip_pairs) {
            UVRipPairs *rip = uv_rip_pairs_from_loop(l, aspect_y, cd_loop_uv_offset);
            float center[2];
            float dir_cursor[2];
            float dir_side[2][2];
            int side_from_cursor = -1;
            if (uv_rip_pairs_calc_center_and_direction(rip, cd_loop_uv_offset, center, dir_side)) {
              for (int i = 0; i < 2; i++) {
                sub_v2_v2v2(dir_cursor, center, co);
                normalize_v2(dir_cursor);
              }
              side_from_cursor = (dot_v2v2(dir_side[0], dir_cursor) -
                                  dot_v2v2(dir_side[1], dir_cursor)) < 0.0f;
            }
            GSetIterator gs_iter;
            GSET_ITER (gs_iter, rip->loops) {
              BMLoop *l_iter = BLI_gsetIterator_getKey(&gs_iter);
              ULData *ul = UL(l_iter);
              if (ul->side == side_from_cursor) {
                uvedit_uv_select_disable(em, scene, l_iter, cd_loop_uv_offset);
                changed = true;
              }
              /* Ensure we don't operate on these again. */
              *ul = ul_clear;
            }
            uv_rip_pairs_free(rip);
          }
        }
        else if (UL(l)->is_select_vert_single) {
          UVRipSingle *rip = uv_rip_single_from_loop(l, co, aspect_y, cd_loop_uv_offset);
          /* We only ever use one side. */
          const int side_from_cursor = 0;
          GSetIterator gs_iter;
          GSET_ITER (gs_iter, rip->loops) {
            BMLoop *l_iter = BLI_gsetIterator_getKey(&gs_iter);
            ULData *ul = UL(l_iter);
            if (ul->side == side_from_cursor) {
              uvedit_uv_select_disable(em, scene, l_iter, cd_loop_uv_offset);
              changed = true;
            }
            /* Ensure we don't operate on these again. */
            *ul = ul_clear;
          }
          uv_rip_single_free(rip);
        }
      }
    }
  }
  return changed;
}

/** \} */

/* -------------------------------------------------------------------- */
/** \name UV Rip Operator
 * \{ */

static int uv_rip_exec(bContext *C, wmOperator *op)
{
  SpaceImage *sima = CTX_wm_space_image(C);
  Scene *scene = CTX_data_scene(C);
  ViewLayer *view_layer = CTX_data_view_layer(C);

  bool changed_multi = false;

  float co[2];
  RNA_float_get_array(op->ptr, "location", co);

  float aspx, aspy;
  {
    /* Note that we only want to run this on the  */
    Object *obedit = CTX_data_edit_object(C);
    ED_uvedit_get_aspect(obedit, &aspx, &aspy);
  }
  const float aspect_y = aspx / aspy;

  uint objects_len = 0;
  Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data_with_uvs(
      view_layer, ((View3D *)NULL), &objects_len);

  for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
    Object *obedit = objects[ob_index];

    if (uv_rip_object(scene, obedit, co, aspect_y)) {
      changed_multi = true;
      uvedit_live_unwrap_update(sima, scene, obedit);
      DEG_id_tag_update(obedit->data, 0);
      WM_event_add_notifier(C, NC_GEOM | ND_DATA, obedit->data);
    }
  }
  MEM_freeN(objects);

  if (!changed_multi) {
    BKE_report(op->reports, RPT_ERROR, "Rip failed");
    return OPERATOR_CANCELLED;
  }
  return OPERATOR_FINISHED;
}

static int uv_rip_invoke(bContext *C, wmOperator *op, const wmEvent *event)
{
  ARegion *ar = CTX_wm_region(C);
  float co[2];

  UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1], &co[0], &co[1]);
  RNA_float_set_array(op->ptr, "location", co);

  return uv_rip_exec(C, op);
}

void UV_OT_rip(wmOperatorType *ot)
{
  /* identifiers */
  ot->name = "UV Rip";
  ot->description = "Rip selected vertices or a selected region";
  ot->idname = "UV_OT_rip";
  ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;

  /* api callbacks */
  ot->exec = uv_rip_exec;
  ot->invoke = uv_rip_invoke;
  ot->poll = ED_operator_uvedit;

  /* translation data */
  Transform_Properties(ot, P_MIRROR_DUMMY);

  /* properties */
  RNA_def_float_vector(
      ot->srna,
      "location",
      2,
      NULL,
      -FLT_MAX,
      FLT_MAX,
      "Location",
      "Mouse location in normalized coordinates, 0.0 to 1.0 is within the image bounds",
      -100.0f,
      100.0f);
}

/** \} */