import numpy as np
import networkx as nx
from collections import deque

from .geometry  import faces_to_edges
from .points    import unitize
from .grouping  import group_rows
from .triangles import normals
from .util      import is_sequence
from .constants import *

def fix_face_winding(mesh):
    '''
    Traverse and change mesh faces in-place to make sure winding is coherent, 
    or that edges on adjacent faces are in opposite directions
    '''
    # we create the face adjacency graph: 
    # every node in g is an index of mesh.faces
    # every edge in g represents two faces which are connected
    graph_all = nx.from_edgelist(mesh.face_adjacency)
    flipped   = 0
    # we are going to traverse the graph using BFS, so we have to start
    # a traversal for every connected component
    for graph in nx.connected_component_subgraphs(graph_all):
        start = graph.nodes()[0]
        # we traverse every pair of faces in the graph
        # we modify mesh.faces and mesh.face_normals in place 
        for face_pair in nx.bfs_edges(graph, start):
            # for each pair of faces, we convert them into edges,
            # find the edge that both faces share, and then see if the edges
            # are reversed in order as you would expect in a well constructed mesh
            pair    = mesh.faces[[face_pair]]            
            edges   = faces_to_edges(pair, sort=False)
            overlap = group_rows(np.sort(edges,axis=1), require_count=2)
            if len(overlap) == 0:
                # only happens on non-watertight meshes
                continue
            edge_pair = edges[[overlap[0]]]
            if edge_pair[0][0] == edge_pair[1][0]:
                # if the edges aren't reversed, invert the order of one of the faces
                flipped += 1
                mesh.faces[face_pair[1]] = mesh.faces[face_pair[1]][::-1]
    log.info('Flipped %d/%d edges', flipped, len(mesh.faces)*3)
def fix_normals_direction(mesh):
    '''
    Check to see if a mesh has normals pointed outside the solid using ray tests.

    If the mesh is not watertight, this is meaningless.
    '''
    # force face normals to be regenerated according to the right-hand rule
    mesh.face_normals = None
    # which direction should our test rays go
    direction = -mesh.face_normals[0]
    # origin of test ray
    origin    = mesh.vertices[mesh.faces[0]].mean(axis=0)
    origin   -= direction * mesh.box_size.max() * 2
    rays = [[origin, direction]]
    location, hit_id = mesh.ray.intersects_location(rays, return_id=True)
    # the distance along the ray vector the hit happened at
    projection = np.dot(location - origin, direction)
    # the face index of the farthest face along the vector
    face_outer = hit_id[0][projection.argmax()]
    # the normal of this presumed outer face
    normal_outer = mesh.face_normals[face_outer]
    # dot product with our direction to see if it is pointing inside or 
    # outside
    normal_sign  = np.sign(np.dot(normal_outer, direction))

    if normal_sign < 0:
        # reverse the face normals
        mesh.face_normals *= normal_sign
        # since normals were regenerated, this means winding is backwards
        # if winding is incoherent this won't fix anything
        mesh.faces = np.fliplr(mesh.faces)

def fix_normals(mesh):
    '''
    Fix the winding and direction of a mesh face and face normals in-place

    Really only meaningful on watertight meshes, but will orient all 
    faces and winding in a uniform way for non-watertight face patches as well.
    '''
    fix_face_winding(mesh)
    fix_normals_direction(mesh)

def broken_faces(mesh, color=None):
    '''
    Return the index of faces in the mesh which break the watertight status
    of the mesh. If color is set, change the color of the broken faces. 
    '''
    adjacency = nx.from_edgelist(mesh.face_adjacency)
    broken    = [k for k, v in adjacency.degree().iteritems() if v != 3]
    broken    = np.array(broken)
    if color is not None:
        if not is_sequence(color): color = [255,0,0]
        mesh.visual.face_colors[broken] = color
    return broken

def fill_holes(mesh, raise_watertight=True):
    '''
    Fill single- triangle holes on triangular meshes by adding new triangles
    to fill the holes. New triangles will have proper winding and normals, 
    and if face colors exist the color of the last face will be assigned
    to the new triangles. 
    
    Arguments
    ---------
    mesh: Trimesh object
    raise_watertight: boolean, if True will raise an error if a 
                      watertight mesh cannot be created. 

    '''
    edges        = faces_to_edges(mesh.faces, sort=False)
    edges_sorted = np.sort(edges, axis=1)
    # we know that in a watertight mesh, every edge will be included twice
    # thus, every edge which appears only once is part of the boundary of a hole.
    boundary_groups = group_rows(edges_sorted, require_count=1)

    if len(boundary_groups) < 3: return
    
    boundary_edges  = edges[boundary_groups]
    index_as_dict   = [{'index': i} for i in boundary_groups]

    # we create a graph of the boundary edges, and find cycles.
    graph  = nx.from_edgelist(np.column_stack((boundary_edges, index_as_dict)))
    cycles = np.array(nx.cycle_basis(graph))

    new_faces  = deque()
    new_vertex = deque()
    for hole in cycles:
        # convert the hole, which is a polygon of vertex indices
        # to triangles and new vertices
        faces, vertex = _hole_to_faces(hole        = hole, 
                                       vertices    = mesh.vertices)
        if len(faces) == 0:
            if raise_watertight: 
                raise MeshError('Cannot create watertight mesh!')
            continue
        # remeshing returns new vertices as negative indices, so change those
        # to absolute indices which won't be screwed up by the later appends
        faces = np.array(faces)
        faces[faces < 0] += len(new_vertex) + len(mesh.vertices) + len(vertex) 
        new_vertex.extend(vertex)
        new_faces.extend(faces)
    new_faces  = np.array(new_faces)
    new_vertex = np.array(new_vertex)

    # no new faces have been added, so nothing further to do
    if len(new_faces) == 0: return

    for face_index, face in enumerate(new_faces):
        # we compare the edge from the new face with 
        # the boundary edge from the source mesh
        edge_test     = face[0:2]
        edge_boundary = edges[graph.get_edge_data(*edge_test)['index']]
        
        # in a well construced mesh, the winding is such that adjacent triangles
        # have reversed edges to each other. Here we check to make sure the 
        # edges are reversed, and if they aren't we simply reverse the face
        reversed = edge_test[0] == edge_boundary[1]
        if not reversed:
            new_faces[face_index] = face[::-1]

    if len(new_vertex) != 0:
        mesh.vertices = np.vstack((mesh.vertices, new_vertex))

    # since the winding is now correct, we can get consistant normals
    # just by doing the cross products on the face edges 
    new_normals, valid = normals(mesh.vertices[new_faces])

    # if face colors exist, assign the last face color to the new faces
    # note that this is a little cheesey, but it is very inexpensive and 
    # is the right thing to do if the mesh is a single color. 
    color_shape = np.shape(mesh.visual.face_colors)
    if len(color_shape) == 2 and color_shape[1] == 3:
        new_colors = np.tile(mesh.visual.face_colors[-1], 
                             (np.sum(valid), 1))
        new_colors = np.vstack((mesh.visual.face_colors, 
                                new_colors))

    mesh.face_normals = np.vstack((mesh.face_normals, new_normals[valid]))
    mesh.faces        = np.vstack((mesh.faces, new_faces[valid]))
    mesh.visual.face_colors = new_colors

    log.debug('Filled in mesh with %i triangles', np.sum(valid))

def _hole_to_faces(hole, vertices=None):
    '''
    Given a loop of vertex indices  representing a hole, turn it into 
    triangular faces.
    If unable to do so, return None

    Arguments
    ---------
    hole:     ordered loop of vertex indices
    vertices: the vertices referenced by hole. 
              If we were to add more involved remeshing algorithms, these 
              would be required, however since we are only adding triangles
              and triangulated quads it is not necessary. 
    fill_planar: fill larger holes if every vertex of the boundary lies on a plane
                 this will not work reliably on non- convex holes 
    Returns
    ---------
    (n, 3) new faces 
    (m, 3) new vertices
    '''
    hole = np.array(hole)
    # the case where the hole is just a single missing triangle
    if len(hole) == 3: 
        return [hole], []
    # the hole is a quad, which we fill with two triangles
    if len(hole) == 4: 
        face_A = hole[[0,1,2]]
        face_B = hole[[2,3,0]]
        return [face_A, face_B], []       
    return [], []
