# ##### BEGIN GPL LICENSE BLOCK #####
#
#  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 FI
TNESS FOR A PARTICULAR PURPOSE.  See the
#  GNU General Public License for more d
etails.
#
#  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.
#
# ##### END GPL LICENSE BLOCK #####

# TODO <pep8 compliant>

from mathutils import Matrix, Vector, geometry
import bpy
from bpy.types import Operator

DEG_TO_RAD = 0.017453292519943295 # pi/180.0
SMALL_NUM = 0.00000001  # see bug [#31598] why we dont have smaller values

global USER_FILL_HOLES
global USER_FILL_HOLES_QUALITY
USER_FILL_HOLES = None
USER_FILL_HOLES_QUALITY = None

def pointInTri2D(v, v1, v2, v3):
    key = v1.x, v1.y, v2.x, v2.y, v3.x, v3.y

    # Commented because its slower to do the bounds check, we should really cache the bounds info for each face.
    '''
    # BOUNDS CHECK
    xmin= 1000000
    ymin= 1000000

    xmax= -1000000
    ymax= -1000000

    for i in (0,2,4):
        x= key[i]
        y= key[i+1]

        if xmax<x:	xmax= x
        if ymax<y:	ymax= y
        if xmin>x:	xmin= x
        if ymin>y:	ymin= y

    x= v.x
    y= v.y

    if x<xmin or x>xmax or y < ymin or y > ymax:
        return False
    # Done with bounds check
    '''
    try:
        mtx = dict_matrix[key]
        if not mtx:
            return False
    except:
        side1 = v2 - v1
        side2 = v3 - v1

        nor = side1.cross(side2)

        mtx = Matrix((side1, side2, nor))

        # Zero area 2d tri, even tho we throw away zero area faces
        # the projection UV can result in a zero area UV.
        if not mtx.determinant():
            dict_matrix[key] = None
            return False

        mtx.invert()

        dict_matrix[key] = mtx

    uvw = (v - v1) * mtx
    return 0 <= uvw[0] and 0 <= uvw[1] and uvw[0] + uvw[1] <= 1


def boundsIsland(faces):
    minx = maxx = faces[0].uv[0][0] # Set initial bounds.
    miny = maxy = faces[0].uv[0][1]
    # print len(faces), minx, maxx, miny , maxy
    for f in faces:
        for uv in f.uv:
            x= uv.x
            y= uv.y
            if x<minx: minx= x
            if y<miny: miny= y
            if x>maxx: maxx= x
            if y>maxy: maxy= y

    return minx, miny, maxx, maxy

"""
def boundsEdgeLoop(edges):
    minx = maxx = edges[0][0] # Set initial bounds.
    miny = maxy = edges[0][1]
    # print len(faces), minx, maxx, miny , maxy
    for ed in edges:
        for pt in ed:
            x= pt[0]
            y= pt[1]
            if x<minx: x= minx
            if y<miny: y= miny
            if x>maxx: x= maxx
            if y>maxy: y= maxy

    return minx, miny, maxx, maxy
"""

# Turns the islands into a list of unpordered edges (Non internal)
# Only for UV's
# only returns outline edges for intersection tests. and unique points.

def island2Edge(island):

    # Vert index edges
    edges = {}

    unique_points= {}

    for f in island:
        f_uvkey= map(tuple, f.uv)


        for vIdx, edkey in enumerate(f.edge_keys):
            unique_points[f_uvkey[vIdx]] = f.uv[vIdx]

            if f.v[vIdx].index > f.v[vIdx-1].index:
                i1= vIdx-1;	i2= vIdx
            else:
                i1= vIdx;	i2= vIdx-1

            try:	edges[ f_uvkey[i1], f_uvkey[i2] ] *= 0 # sets any edge with more than 1 user to 0 are not returned.
            except:	edges[ f_uvkey[i1], f_uvkey[i2] ] = (f.uv[i1] - f.uv[i2]).length,

    # If 2 are the same then they will be together, but full [a,b] order is not correct.

    # Sort by length


    length_sorted_edges = [(Vector(key[0]), Vector(key[1]), value) for key, value in edges.items() if value != 0]

    try:	length_sorted_edges.sort(key = lambda A: -A[2]) # largest first
    except:	length_sorted_edges.sort(lambda A, B: cmp(B[2], A[2]))

    # Its okay to leave the length in there.
    #for e in length_sorted_edges:
    #	e.pop(2)

    # return edges and unique points
    return length_sorted_edges, [v.to_3d() for v in unique_points.values()]

# ========================= NOT WORKING????
# Find if a points inside an edge loop, unordered.
# pt is and x/y
# edges are a non ordered loop of edges.
# offsets are the edge x and y offset.
"""
def pointInEdges(pt, edges):
    #
    x1 = pt[0]
    y1 = pt[1]

    # Point to the left of this line.
    x2 = -100000
    y2 = -10000
    intersectCount = 0
    for ed in edges:
        xi, yi = lineIntersection2D(x1,y1, x2,y2, ed[0][0], ed[0][1], ed[1][0], ed[1][1])
        if xi is not None: # Is there an intersection.
            intersectCount+=1

    return intersectCount % 2
"""

def pointInIsland(pt, island):
    vec1, vec2, vec3 = Vector(), Vector(), Vector()
    for f in island:
        vec1.x, vec1.y = f.uv[0]
        vec2.x, vec2.y = f.uv[1]
        vec3.x, vec3.y = f.uv[2]

        if pointInTri2D(pt, vec1, vec2, vec3):
            return True

        if len(f.v) == 4:
            vec1.x, vec1.y = f.uv[0]
            vec2.x, vec2.y = f.uv[2]
            vec3.x, vec3.y = f.uv[3]
            if pointInTri2D(pt, vec1, vec2, vec3):
                return True
    return False


# box is (left,bottom, right, top)
def islandIntersectUvIsland(source, target, SourceOffset):
    # Is 1 point in the box, inside the vertLoops
    edgeLoopsSource = source[6] # Pretend this is offset
    edgeLoopsTarget = target[6]

    # Edge intersect test
    for ed in edgeLoopsSource:
        for seg in edgeLoopsTarget:
            i = geometry.intersect_line_line_2d(seg[0],
                                                seg[1],
                                                SourceOffset+ed[0],
                                                SourceOffset+ed[1],
                                                )
            if i:
                return 1 # LINE INTERSECTION

    # 1 test for source being totally inside target
    SourceOffset.resize_3d()
    for pv in source[7]:
        if pointInIsland(pv+SourceOffset, target[0]):
            return 2 # SOURCE INSIDE TARGET

    # 2 test for a part of the target being totally inside the source.
    for pv in target[7]:
        if pointInIsland(pv-SourceOffset, source[0]):
            return 3 # PART OF TARGET INSIDE SOURCE.

    return 0 # NO INTERSECTION


def rotate_uvs(uv_points, angle):

    if angle != 0.0:
        mat = Matrix.Rotation(angle, 2)
        for uv in uv_points:
            uv[:] = mat * uv


def optiRotateUvIsland(faces):
    uv_points = [uv for f in faces  for uv in f.uv]
    angle = geometry.box_fit_2d(uv_points)

    if angle != 0.0:
        rotate_uvs(uv_points, angle)

    # orient them vertically (could be an option)
    minx, miny, maxx, maxy = boundsIsland(faces)
    w, h = maxx - minx, maxy - miny
    # use epsilon so we dont randomly rotate (almost) perfect squares.
    if h + 0.00001 < w:
        from math import pi
        angle = pi / 2.0
        rotate_uvs(uv_points, angle)


# Takes an island list and tries to find concave, hollow areas to pack smaller islands into.
def mergeUvIslands(islandList):
    global USER_FILL_HOLES
    global USER_FILL_HOLES_QUALITY


    # Pack islands to bottom LHS
    # Sync with island

    #islandTotFaceArea = [] # A list of floats, each island area
    #islandArea = [] # a list of tuples ( area, w,h)


    decoratedIslandList = []

    islandIdx = len(islandList)
    while islandIdx:
        islandIdx-=1
        minx, miny, maxx, maxy = boundsIsland(islandList[islandIdx])
        w, h = maxx-minx, maxy-miny

        totFaceArea = 0
        offset= Vector((minx, miny))
        for f in islandList[islandIdx]:
            for uv in f.uv:
                uv -= offset

            totFaceArea += f.area

        islandBoundsArea = w*h
      