#include <functional>
#include <vector>
#include "GEO_uv_parametrizer.hh"
#include "BLI_array.hh"
#include "BLI_convexhull_2d.h"
#include "BLI_ghash.h"
#include "BLI_math_geom.h"
#include "BLI_math_matrix.h"
#include "BLI_math_rotation.h"
#include "BLI_math_vector.h"
#include "BLI_polyfill_2d.h"
#include "BLI_polyfill_2d_beautify.h"
#include "BLI_rand.h"
#include "GEO_uv_pack.hh"
#include "eigen_capi.h"

Classes
struct	blender::geometry::PHashLink
struct	blender::geometry::PHash
struct	blender::geometry::PVert
union	blender::geometry::PVert::PVertUnion
struct	blender::geometry::PEdge
union	blender::geometry::PEdge::PEdgeUnion
struct	blender::geometry::PFace
union	blender::geometry::PFace::PFaceUnion
struct	blender::geometry::PChart
struct	blender::geometry::PAbfSystem
struct	blender::geometry::GeoUVPinIndex

Namespaces
namespace	blender
namespace	blender::geometry

Macros
#define	param_warning(message)
#define	UNUSED_FUNCTION_NO_SLIM UNUSED_FUNCTION
#define	PEDGE_VERTEX_FLAGS (PEDGE_PIN)
#define	PHASH_hash(ph, item)
#define	PHASH_edge(v1, v2)
#define	ABF_MAX_ITER 20
#define	P_STRETCH_ITER 20

Typedefs
using	blender::geometry::PHashKey = uintptr_t

Enumerations
enum	blender::geometry::PVertFlag { blender::geometry::PVERT_PIN = 1 , blender::geometry::PVERT_SELECT = 2 , blender::geometry::PVERT_INTERIOR = 4 , blender::geometry::PVERT_COLLAPSE = 8 , blender::geometry::PVERT_SPLIT = 16 }
enum	blender::geometry::PEdgeFlag { blender::geometry::PEDGE_SEAM = 1 , blender::geometry::PEDGE_VERTEX_SPLIT = 2 , blender::geometry::PEDGE_PIN = 4 , blender::geometry::PEDGE_SELECT = 8 , blender::geometry::PEDGE_DONE = 16 , blender::geometry::PEDGE_FILLED = 32 , blender::geometry::PEDGE_COLLAPSE = 64 , blender::geometry::PEDGE_COLLAPSE_EDGE = 128 , blender::geometry::PEDGE_COLLAPSE_PAIR = 256 }
enum	blender::geometry::PFaceFlag { blender::geometry::PFACE_CONNECTED = 1 , blender::geometry::PFACE_FILLED = 2 , blender::geometry::PFACE_COLLAPSE = 4 , blender::geometry::PFACE_DONE = 8 }

Functions
static PHash *	blender::geometry::phash_new (PHashLink **list, int sizehint)
static void	blender::geometry::phash_safe_delete (PHash **pph)
static int	blender::geometry::phash_size (PHash *ph)
static void	blender::geometry::phash_insert (PHash ph, PHashLink link)
static PHashLink *	blender::geometry::phash_lookup (PHash *ph, PHashKey key)
static PHashLink *	blender::geometry::phash_next (PHash ph, PHashKey key, PHashLink link)
static void	blender::geometry::fix_large_angle (const float v_fix[3], const float v1[3], const float v2[3], double r_fix, double r_a1, double *r_a2)
static void	blender::geometry::p_triangle_angles (const float v1[3], const float v2[3], const float v3[3], double r_a1, double r_a2, double *r_a3)
static void	blender::geometry::p_face_angles (PFace f, double r_a1, double r_a2, double r_a3)
static float	blender::geometry::p_vec_cos (const float v1[3], const float v2[3], const float v3[3])
static void	blender::geometry::p_triangle_cos (const float v1[3], const float v2[3], const float v3[3], float r_cos1, float r_cos2, float *r_cos3)
static void UNUSED_FUNCTION	blender::geometry::p_face_cos (PFace f, float r_cos1, float r_cos2, float r_cos3)
static float	blender::geometry::p_face_area (PFace *f)
static float	blender::geometry::p_area_signed (const float v1[2], const float v2[2], const float v3[2])
static float	blender::geometry::p_face_uv_area_signed (PFace *f)
static float	blender::geometry::p_edge_length (PEdge *e)
static float	blender::geometry::p_edge_length_squared (PEdge *e)
static float	blender::geometry::p_edge_uv_length (PEdge *e)
static void	blender::geometry::p_chart_uv_bbox (PChart *chart, float minv[2], float maxv[2])
static float	blender::geometry::p_chart_uv_area (PChart *chart)
static void	blender::geometry::p_chart_uv_scale (PChart *chart, const float scale)
static void	blender::geometry::uv_parametrizer_scale_x (ParamHandle *phandle, const float scale_x)
static void	blender::geometry::p_chart_uv_translate (PChart *chart, const float trans[2])
static void	blender::geometry::p_chart_uv_transform (PChart *chart, const float mat[2][2])
static void	blender::geometry::p_chart_uv_to_array (PChart chart, float(points)[2])
static bool	blender::geometry::p_intersect_line_2d_dir (const float v1[2], const float dir1[2], const float v2[2], const float dir2[2], float r_isect[2])
static PEdge *	blender::geometry::p_wheel_edge_next (PEdge *e)
static const PEdge *	blender::geometry::p_wheel_edge_next (const PEdge *e)
static PEdge *	blender::geometry::p_wheel_edge_prev (PEdge *e)
static PEdge *	blender::geometry::p_boundary_edge_next (PEdge *e)
static PEdge *	blender::geometry::p_boundary_edge_prev (PEdge *e)
static bool	blender::geometry::p_vert_interior (PVert *v)
static void	blender::geometry::p_face_flip (PFace *f)
static void	blender::geometry::p_vert_load_pin_select_uvs (ParamHandle handle, PVert v)
static void	blender::geometry::p_flush_uvs (ParamHandle handle, PChart chart)
static void	blender::geometry::p_face_backup_uvs (PFace *f)
static void	blender::geometry::p_face_restore_uvs (PFace *f)
static PVert *	blender::geometry::p_vert_add (ParamHandle handle, PHashKey key, const float co[3], const float weight, PEdge e)
static PVert *	blender::geometry::p_vert_lookup (ParamHandle handle, PHashKey key, const float co[3], const float weight, PEdge e)
static PVert *	blender::geometry::p_vert_copy (ParamHandle handle, PVert v)
static PEdge *	blender::geometry::p_edge_lookup (ParamHandle handle, const PHashKey vkeys)
static int	blender::geometry::p_face_exists (ParamHandle handle, const ParamKey pvkeys, int i1, int i2, int i3)
static bool	blender::geometry::p_edge_implicit_seam (PEdge e, PEdge ep)
static bool	blender::geometry::p_edge_has_pair (ParamHandle handle, PEdge e, bool topology_from_uvs, PEdge **r_pair)
static bool	blender::geometry::p_edge_connect_pair (ParamHandle handle, PEdge e, bool topology_from_uvs, PEdge ***stack)
static int	blender::geometry::p_connect_pairs (ParamHandle *handle, bool topology_from_uvs)
static void	blender::geometry::p_split_vert (ParamHandle handle, PChart chart, PEdge *e)
static PChart **	blender::geometry::p_split_charts (ParamHandle handle, PChart chart, int ncharts)
static PFace *	blender::geometry::p_face_add (ParamHandle *handle)
static PFace *	blender::geometry::p_face_add_construct (ParamHandle handle, ParamKey key, const ParamKey vkeys, const float co, float uv, const float weight, int i1, int i2, int i3, const bool pin, const bool *select)
static PFace *	blender::geometry::p_face_add_fill (ParamHandle handle, PChart chart, PVert v1, PVert v2, PVert *v3)
static void	blender::geometry::p_chart_boundaries (PChart chart, PEdge *r_outer)
static float	blender::geometry::p_edge_boundary_angle (PEdge *e)
static void	blender::geometry::p_chart_fill_boundary (ParamHandle handle, PChart chart, PEdge *be, int nedges)
static void	blender::geometry::p_chart_fill_boundaries (ParamHandle handle, PChart chart, const PEdge *outer)
static void	blender::geometry::p_vert_fix_edge_pointer (PVert *v)
static void	blender::geometry::p_collapsing_verts (PEdge edge, PEdge pair, PVert r_newv, PVert r_keepv)
static void	blender::geometry::p_collapse_edge (PEdge edge, PEdge pair)
static bool	blender::geometry::p_collapse_allowed_topologic (PEdge edge, PEdge pair)
static void	blender::geometry::p_collapse_cost_vertex (PVert vert, float r_mincost, PEdge *r_mine, const std::function< float(PEdge , PEdge )> &collapse_cost_fn, const std::function< float(PEdge , PEdge *)> &collapse_allowed_fn)
static void	blender::geometry::p_chart_post_collapse_flush (PChart chart, PEdge collapsed)
static void	blender::geometry::p_chart_simplify_compute (PChart chart, std::function< float(PEdge , PEdge )> collapse_cost_fn, std::function< float(PEdge , PEdge *)> collapse_allowed_fn)
static void	blender::geometry::p_abf_setup_system (PAbfSystem *sys)
static void	blender::geometry::p_abf_free_system (PAbfSystem *sys)
static void	blender::geometry::p_abf_compute_sines (PAbfSystem *sys)
static float	blender::geometry::p_abf_compute_sin_product (PAbfSystem sys, PVert v, int aid)
static float	blender::geometry::p_abf_compute_grad_alpha (PAbfSystem sys, PFace f, PEdge *e)
static float	blender::geometry::p_abf_compute_gradient (PAbfSystem sys, PChart chart)
static void	blender::geometry::p_abf_adjust_alpha (PAbfSystem *sys, const int id, const float dlambda1, const float pre)
static bool	blender::geometry::p_abf_matrix_invert (PAbfSystem sys, PChart chart)
static bool	blender::geometry::p_chart_abf_solve (PChart *chart)
static void	blender::geometry::p_chart_pin_positions (PChart chart, PVert pin1, PVert *pin2)
static bool	blender::geometry::p_chart_symmetry_pins (PChart chart, PEdge outer, PVert pin1, PVert pin2)
static void	blender::geometry::p_chart_extrema_verts (PChart chart, PVert pin1, PVert *pin2)
static void	blender::geometry::p_chart_lscm_begin (PChart *chart, bool live, bool abf)
static bool	blender::geometry::p_chart_lscm_solve (ParamHandle handle, PChart chart)
static void	blender::geometry::p_chart_lscm_transform_single_pin (PChart *chart)
static void	blender::geometry::p_chart_lscm_end (PChart *chart)
static void	blender::geometry::p_stretch_pin_boundary (PChart *chart)
static float	blender::geometry::p_face_stretch (PFace *f)
static float	blender::geometry::p_stretch_compute_vertex (PVert *v)
static void	blender::geometry::p_chart_stretch_minimize (PChart chart, RNG rng)
static int	blender::geometry::p_compare_geometric_uv (const void a, const void b)
static bool	blender::geometry::p_chart_convex_hull (PChart chart, PVert *r_verts, int r_nverts, int *r_right)
static float	blender::geometry::p_rectangle_area (float p1, float dir, float p2, float p3, float *p4)
static float	blender::geometry::p_chart_minimum_area_angle (PChart *chart)
static void	blender::geometry::p_chart_rotate_minimum_area (PChart *chart)
static void	blender::geometry::p_chart_rotate_fit_aabb (PChart *chart)
static GeoUVPinIndex *	blender::geometry::new_geo_uv_pinindex (ParamHandle *handle, const float uv[2])
static void	blender::geometry::p_add_ngon (ParamHandle handle, const ParamKey key, const int nverts, const ParamKey vkeys, const float co, float uv, const float weight, const bool pin, const bool *select)
Chart Construction:
Faces and seams may only be added between ParamHandle::ParamHandle() and #geometry::uv_parametrizer_construct_end. The pointers to co and uv are stored, rather than being copied. Vertices are implicitly created. In #geometry::uv_parametrizer_construct_end the mesh will be split up according to the seams. The resulting charts must be manifold, connected and open (at least one boundary loop). The output will be written to the uv pointers.
void	blender::geometry::uv_parametrizer_aspect_ratio (ParamHandle *handle, float aspect_y)
ParamKey	blender::geometry::uv_find_pin_index (ParamHandle *handle, const int bmvertindex, const float uv[2])
void	blender::geometry::uv_prepare_pin_index (ParamHandle *handle, const int bmvertindex, const float uv[2])
void	blender::geometry::uv_parametrizer_face_add (ParamHandle handle, const ParamKey key, const int nverts, const ParamKey vkeys, const float co, float uv, const float weight, const bool pin, const bool *select)
void	blender::geometry::uv_parametrizer_edge_set_seam (ParamHandle phandle, const ParamKey vkeys)
void	blender::geometry::uv_parametrizer_construct_end (ParamHandle phandle, bool fill_holes, bool topology_from_uvs, int r_count_failed=nullptr)
Least Squares Conformal Maps:
Charts with less than two pinned vertices are assigned two pins. LSCM is divided to three steps: Begin: compute matrix and its factorization (expensive). Solve using pinned coordinates (cheap). End: clean up. UV coordinates are allowed to change within begin/end, for quick re-solving.
void	blender::geometry::uv_parametrizer_lscm_begin (ParamHandle *handle, bool live, bool abf)
void	blender::geometry::uv_parametrizer_lscm_solve (ParamHandle handle, int count_changed, int *count_failed)
void	blender::geometry::uv_parametrizer_lscm_end (ParamHandle *handle)
Stretch
void	blender::geometry::uv_parametrizer_stretch_begin (ParamHandle *handle)
void	blender::geometry::uv_parametrizer_stretch_blend (ParamHandle *handle, float blend)
void	blender::geometry::uv_parametrizer_stretch_iter (ParamHandle *handle)
void	blender::geometry::uv_parametrizer_stretch_end (ParamHandle *handle)
Packing
void	blender::geometry::uv_parametrizer_pack (ParamHandle *handle, float margin, bool do_rotate, bool ignore_pinned)
Average area for all charts
void	blender::geometry::uv_parametrizer_average (ParamHandle *handle, bool ignore_pinned, bool scale_uv, bool shear)
Flushing
void	blender::geometry::uv_parametrizer_flush (ParamHandle *handle)
void	blender::geometry::uv_parametrizer_flush_restore (ParamHandle *handle)
SLIM:
begin: data is gathered into matrices and transferred to SLIM. solve: compute cheap initialization (if necessary) and refine iteratively. end: clean up.
void	blender::geometry::uv_parametrizer_slim_solve (ParamHandle phandle, const ParamSlimOptions slim_options, int count_changed, int count_failed)
void	blender::geometry::uv_parametrizer_slim_live_begin (ParamHandle phandle, const ParamSlimOptions slim_options)
void	blender::geometry::uv_parametrizer_slim_stretch_iteration (ParamHandle *phandle, float blend)
void	blender::geometry::uv_parametrizer_slim_live_solve_iteration (ParamHandle *phandle)
void	blender::geometry::uv_parametrizer_slim_live_end (ParamHandle *phandle)
bool	blender::geometry::uv_parametrizer_is_slim (const ParamHandle *phandle)

Variables
static int	blender::geometry::PHashSizes []

Degenerate Geometry Fixing
static const float	blender::geometry::CORR_ZERO_AREA_EPS = 1.0e-10f
static void	blender::geometry::p_chart_flush_collapsed_uvs (PChart *chart)
static bool	blender::geometry::p_collapse_doubles_allowed (PEdge edge, PEdge pair, float threshold_squared)
static float	blender::geometry::p_collapse_doubles_cost (PEdge edge, PEdge pair)
static void UNUSED_FUNCTION	blender::geometry::p_chart_collapse_doubles (PChart *chart, const float threshold)
static bool	blender::geometry::p_validate_corrected_coords_point (const PEdge *corr_e, const float corr_co1[3], const float corr_co2[3], const float min_area, const float min_angle_cos)
static bool	blender::geometry::p_validate_corrected_coords (const PEdge *corr_e, const float corr_co[3], float min_area, float min_angle_cos)
static bool	blender::geometry::p_edge_matrix (float R[3][3], const float edge_dir[3])
static bool	blender::geometry::p_edge_matrix (float R[3][3], const PEdge *e)
static bool	blender::geometry::p_chart_correct_degenerate_triangle_point (PFace *f, float min_area, float min_angle_cos)
static bool	blender::geometry::p_chart_correct_degenerate_triangles2 (PChart *chart, float min_area, float min_angle)
static bool	blender::geometry::p_validate_triangle_angles (const PVert vert1, const PVert vert2, const PVert *vert3, const float min_angle_cos)
static bool UNUSED_FUNCTION_NO_SLIM	blender::geometry::p_chart_correct_degenerate_triangles (PChart *chart, const float min_area, const float min_angle)