import_obj.py

# ##### 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 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.
#
# ##### END GPL LICENSE BLOCK #####

# <pep8 compliant>

# Script copyright (C) Campbell Barton
# Contributors: Campbell Barton, Jiri Hnidek, Paolo Ciccone

"""
This script imports a Wavefront OBJ files to Blender.

Usage:
Run this script from "File->Import" menu and then load the desired OBJ file.
Note, This loads mesh objects and materials only, nurbs and curves are not supported.

http://wiki.blender.org/index.php/Scripts/Manual/Import/wavefront_obj
"""

import os
import time
import bpy
import mathutils
from mathutils.geometry import tesselate_polygon
from io_utils import load_image, unpack_list, unpack_face_list


def BPyMesh_ngon(from_data, indices, PREF_FIX_LOOPS= True):
    '''
    Takes a polyline of indices (fgon)
    and returns a list of face indicie lists.
    Designed to be used for importers that need indices for an fgon to create from existing verts.

    from_data: either a mesh, or a list/tuple of vectors.
    indices: a list of indices to use this list is the ordered closed polyline to fill, and can be a subset of the data given.
    PREF_FIX_LOOPS: If this is enabled polylines that use loops to make multiple polylines are delt with correctly.
    '''

    if not set: # Need sets for this, otherwise do a normal fill.
        PREF_FIX_LOOPS= False

    Vector= mathutils.Vector
    if not indices:
        return []

    #    return []
    def rvec(co): return round(co.x, 6), round(co.y, 6), round(co.z, 6)
    def mlen(co): return abs(co[0])+abs(co[1])+abs(co[2]) # manhatten length of a vector, faster then length

    def vert_treplet(v, i):
        return v, rvec(v), i, mlen(v)

    def ed_key_mlen(v1, v2):
        if v1[3] > v2[3]:
            return v2[1], v1[1]
        else:
            return v1[1], v2[1]


    if not PREF_FIX_LOOPS:
        '''
        Normal single concave loop filling
        '''
        if type(from_data) in (tuple, list):
            verts= [Vector(from_data[i]) for ii, i in enumerate(indices)]
        else:
            verts= [from_data.vertices[i].co for ii, i in enumerate(indices)]

        for i in range(len(verts)-1, 0, -1): # same as reversed(xrange(1, len(verts))):
            if verts[i][1]==verts[i-1][0]:
                verts.pop(i-1)

        fill= fill_polygon([verts])

    else:
        '''
        Seperate this loop into multiple loops be finding edges that are used twice
        This is used by lightwave LWO files a lot
        '''

        if type(from_data) in (tuple, list):
            verts= [vert_treplet(Vector(from_data[i]), ii) for ii, i in enumerate(indices)]
        else:
            verts= [vert_treplet(from_data.vertices[i].co, ii) for ii, i in enumerate(indices)]

        edges= [(i, i-1) for i in range(len(verts))]
        if edges:
            edges[0]= (0,len(verts)-1)

        if not verts:
            return []


        edges_used= set()
        edges_doubles= set()
        # We need to check if any edges are used twice location based.
        for ed in edges:
            edkey= ed_key_mlen(verts[ed[0]], verts[ed[1]])
            if edkey in edges_used:
                edges_doubles.add(edkey)
            else:
                edges_used.add(edkey)

        # Store a list of unconnected loop segments split by double edges.
        # will join later
        loop_segments= []

        v_prev= verts[0]
        context_loop= [v_prev]
        loop_segments= [context_loop]

        for v in verts:
            if v!=v_prev:
                # Are we crossing an edge we removed?
                if ed_key_mlen(v, v_prev) in edges_doubles:
                    context_loop= [v]
                    loop_segments.append(context_loop)
                else:
                    if context_loop and context_loop[-1][1]==v[1]:
                        #raise "as"
                        pass
                    else:
                        context_loop.append(v)

                v_prev= v
        # Now join loop segments

        def join_seg(s1,s2):
            if s2[-1][1]==s1[0][1]: #
                s1,s2= s2,s1
            elif s1[-1][1]==s2[0][1]:
                pass
            else:
                return False

            # If were stuill here s1 and s2 are 2 segments in the same polyline
            s1.pop() # remove the last vert from s1
            s1.extend(s2) # add segment 2 to segment 1

            if s1[0][1]==s1[-1][1]: # remove endpoints double
                s1.pop()

            s2[:]= [] # Empty this segment s2 so we dont use it again.
            return True

        joining_segments= True
        while joining_segments:
            joining_segments= False
            segcount= len(loop_segments)

            for j in range(segcount-1, -1, -1): #reversed(range(segcount)):
                seg_j= loop_segments[j]
                if seg_j:
                    for k in range(j-1, -1, -1): # reversed(range(j)):
                        if not seg_j:
                            break
                        seg_k= loop_segments[k]

                        if seg_k and join_seg(seg_j, seg_k):
                            joining_segments= True

        loop_list= loop_segments

        for verts in loop_list:
            while verts and verts[0][1]==verts[-1][1]:
                verts.pop()

        loop_list= [verts for verts in loop_list if len(verts)>2]
        # DONE DEALING WITH LOOP FIXING


        # vert mapping
        vert_map= [None]*len(indices)
        ii=0
        for verts in loop_list:
            if len(verts)>2:
                for i, vert in enumerate(verts):
                    vert_map[i+ii]= vert[2]
                ii+=len(verts)

        fill= tesselate_polygon([ [v[0] for v in loop] for loop in loop_list ])
        #draw_loops(loop_list)
        #raise 'done loop'
        # map to original indices
        fill= [[vert_map[i] for i in reversed(f)] for f in fill]