io_export_unreal_psk_psa.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 3 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, see <http://www.gnu.org/licenses/>.
#  All rights reserved.
#
#======================= END GPL LICENSE BLOCK =============================

bl_info = {
    "name": "Export Unreal Engine Format(.psk/.psa)",
    "author": "Darknet/Optimus_P-Fat/Active_Trash/Sinsoft/VendorX/Spoof",
    "version": (2, 7),
    "blender": (2, 65, 4),
    "location": "File > Export > Skeletal Mesh/Animation Data (.psk/.psa)",
    "description": "Export Skeleletal Mesh/Animation Data",
    "warning": "",
    "wiki_url": "http://wiki.blender.org/index.php/Extensions:2.6/Py/"\
        "Scripts/Import-Export/Unreal_psk_psa",
    "tracker_url": "https://projects.blender.org/tracker/index.php?"\
        "func=detail&aid=21366",
    "category": "Import-Export"}

"""
-- Unreal Skeletal Mesh and Animation Export (.psk  and .psa) export script v0.0.1 --<br> 

- NOTES:
- This script Exports To Unreal's PSK and PSA file formats for Skeletal Meshes and Animations. <br>
- This script DOES NOT support vertex animation! These require completely different file formats. <br>

- v0.0.1
- Initial version

- v0.0.2
- This version adds support for more than one material index!

[ - Edit by: Darknet
- v0.0.3 - v0.0.12
- This will work on UT3 and it is a stable version that work with vehicle for testing. 
- Main Bone fix no dummy needed to be there.
- Just bone issues position, rotation, and offset for psk.
- The armature bone position, rotation, and the offset of the bone is fix. It was to deal with skeleton mesh export for psk.
- Animation is fix for position, offset, rotation bone support one rotation direction when armature build. 
- It will convert your mesh into triangular when exporting to psk file.
- Did not work with psa export yet.

- v0.0.13
- The animatoin will support different bone rotations when export the animation.

- v0.0.14
- Fixed Action set keys frames when there is no pose keys and it will ignore it.

- v0.0.15
- Fixed multiple objects when exporting to psk. Select one mesh to export to psk.
- ]

- v0.1.1
- Blender 2.50 svn (Support)

Credit to:
- export_cal3d.py (Position of the Bones Format)
- blender2md5.py (Animation Translation Format)
- export_obj.py (Blender 2.5/Pyhton 3.x Format)

- freenode #blendercoder -> user -> ideasman42

- Give Credit to those who work on this script.

- http://sinsoft.com
"""


#===========================================================================
"""
NOTES for Jan 2012 refactor (Spoof)

    * THIS IS A WORK IN PROGRESS. These modifications were originally
    intended for internal use and are incomplete. Use at your own risk! *

TODO

- (Blender 2.62) changes to Matrix math
- (Blender 2.62) check for long names
- option to manually set the root bone for export

CHANGES

- new bone parsing to allow advanced rigging
- identification of armature and mesh
- removed the need to apply an action to the armature
- fixed anim rate to work correctly in UDK (no more FPS fudging)
- progress reporting while processing smooth groups
- more informative logging
- code refactor for clarity and modularity
    - naming conventions unified to use lowercase_with_underscore
    - C++ datatypes and PSK/PSA classes remain CamelCaseStyle for clarity
    - names such as 'ut' and 'unreal' unified to 'udk'
    - simplification of code structure
    - removed legacy code paths

USAGE

This version of the exporter is more selective over which bones are considered
part of the UDK skeletal mesh, and allows greater flexibility for adding
control bones to aid in animation.

Taking advantage of this script requires the following methodology:

    * Place all exportable bones into a bone hierarchy extending from a single
    root. This root bone must have use_deform enabled. All other root bones
    in the armature must disable use_deform. *

The script searches for a root bone with use_deform set true and considers all
bones parented to it as part of the UDK skeletal mesh. Thus only these bones
are exported and all other bones are ignored.

This removes many restrictions on the rigger/animator, who can add control
bone hierarchies to the rig, and keyframe any element into actions. With this
approach you can build complex animation rigs in a similar vein to the Rigify
add-on, by Nathan Vegdahl. However...

    * Rigify is incompatible with this script *

Rigify interlaces deformer bones within a single hierarchy making it difficult
to deconstruct for export. It also splits some meta-rig bones into multiple
deformer bones (bad for optimising a game character). I had partial success
writing a parser for the structure, but it was taking too much time and,
considering the other issues with Rigify, it was abandoned.
"""
#===========================================================================

import bmesh
import os
import time
import bpy
import mathutils
import math
import random
import operator
import sys
from bpy.props import *
from struct import pack

# REFERENCE MATERIAL JUST IN CASE:
# 
# U = x / sqrt(x^2 + y^2 + z^2)
# V = y / sqrt(x^2 + y^2 + z^2)
#
# Triangles specifed counter clockwise for front face
#
# defines for sizeofs
SIZE_FQUAT              = 16
SIZE_FVECTOR            = 12
SIZE_VJOINTPOS          = 44
SIZE_ANIMINFOBINARY     = 168
SIZE_VCHUNKHEADER       = 32
SIZE_VMATERIAL          = 88
SIZE_VBONE              = 120
SIZE_FNAMEDBONEBINARY   = 120
SIZE_VRAWBONEINFLUENCE  = 12
SIZE_VQUATANIMKEY       = 32
SIZE_VVERTEX            = 16
SIZE_VPOINT             = 12
SIZE_VTRIANGLE          = 12

MaterialName            = []

#===========================================================================
# Custom exception class
#===========================================================================
class Error( Exception ):

    def __init__(self, message):
        self.message = message

#===========================================================================
# Verbose logging with loop truncation
#===========================================================================
def verbose( msg, iteration=-1, max_iterations=4, msg_truncated="..." ):

    if bpy.context.scene.udk_option_verbose == True:
        # limit the number of times a loop can output messages
        if iteration > max_iterations:
            return
        elif iteration == max_iterations:
            print(msg_truncated)
            return

        print(msg)
    
#===========================================================================
# Log header/separator
#===========================================================================
def header( msg, justify='LEFT', spacer='_', cols=78 ):
    
    if justify == 'LEFT':
        s = '{:{spacer}<{cols}}'.format(msg+" ", spacer=spacer, cols=cols)
    
    elif justify == 'RIGHT':
        s = '{:{spacer}>{cols}}'.format(" "+msg, spacer=spacer, cols=cols)
    
    else:
        s = '{:{spacer}^{cols}}'.format(" "+msg+" ", spacer=spacer, cols=cols)
    
    return "\n" + s + "\n"

#===========================================================================
# Generic Object->Integer mapping
# the object must be usable as a dictionary key
#===========================================================================
class ObjMap:
    
    def __init__(self):
        self.dict = {}
        self.next = 0
    
    def get(self, obj):
        if obj in self.dict:
            return self.dict[obj]
        else:
            id = self.next
            self.next = self.next + 1
            self.dict[obj] = id
            return id
    
    def items(self):
        getval = operator.itemgetter(0)
        getkey = operator.itemgetter(1)
        return map(getval, sorted(self.dict.items(), key=getkey))

#===========================================================================
# RG - UNREAL DATA STRUCTS - CONVERTED FROM C STRUCTS GIVEN ON UDN SITE 
# provided here: http://udn.epicgames.com/Two/BinaryFormatSpecifications.html
# updated UDK (Unreal Engine 3): http://udn.epicgames.com/Three/BinaryFormatSpecifications.html
#===========================================================================
class FQuat:

    def __init__(self): 
        self.X = 0.0
        self.Y = 0.0
        self.Z = 0.0
        self.W = 1.0
        
    def dump(self):
        return pack('ffff', self.X, self.Y, self.Z, self.W)
        
    def __cmp__(self, other):
        return cmp(self.X, other.X) \
            or cmp(self.Y, other.Y) \
            or cmp(self.Z, other.Z) \
            or cmp(self.W, other.W)
        
    def __hash__(self):
        return hash(self.X) ^ hash(self.Y) ^ hash(self.Z) ^ hash(self.W)
        
    def __str__(self):
        return "[%f,%f,%f,%f](FQuat)" % (self.X, self.Y, self.Z, self.W)

class FVector(object):

    def __init__(self, X=0.0, Y=0.0, Z=0.0):
        self.X = X
        self.Y = Y
        self.Z = Z
        
    def dump(self):
        return pack('fff', self.X, self.Y, self.Z)
        
    def __cmp__(self, other):
        return cmp(self.X, other.X) \
            or cmp(self.Y, other.Y) \
            or cmp(self.Z, other.Z)
        
    def _key(self):
        return (type(self).__name__, self.X, self.Y, self.Z)
        
    def __hash__(self):
        return hash(self._key())
        
    def __eq__(self, other):
        if not hasattr(other, '_key'):
            return False
        return self._key() == other._key() 
        
    def dot(self, other):
        return self.X * other.X + self.Y * other.Y + self.Z * other.Z
    
    def cross(self, other):
        return FVector(self.Y * other.Z - self.Z * other.Y,
                self.Z * other.X - self.X * other.Z,
                self.X * other.Y - self.Y * other.X)
                
    def sub(self, other):
        return FVector(self.X - other.X,
            self.Y - other.Y,
            self.Z - other.Z)

class VJointPos:

    def __init__(self):
        self.Orientation    = FQuat()
        self.Position       = FVector()
        self.Length         = 0.0
        self.XSize          = 0.0
        self.YSize          = 0.0
        self.ZSize          = 0.0
        
    def dump(self):
        return self.Orientation.dump() + self.Position.dump() + pack('4f', self.Length, self.XSize, self.YSize, self.ZSize)

class AnimInfoBinary:

    def __init__(self):
        self.Name           = ""    # length=64
        self.Group          = ""    # length=64
        self.TotalBones     = 0
        self.RootInclude    = 0
        self.KeyCompressionStyle = 0
        self.KeyQuotum      = 0
        self.KeyPrediction  = 0.0
        self.TrackTime      = 0.0
        self.AnimRate       = 0.0
        self.StartBone      = 0
        self.FirstRawFrame  = 0
        self.NumRawFrames   = 0
        
    def dump(self):
        return pack('64s64siiiifffiii', str.encode(self.Name), str.encode(self.Group), self.TotalBones, self.RootInclude, self.KeyCompressionStyle, self.KeyQuotum, self.KeyPrediction, self.TrackTime, self.AnimRate, self.StartBone, self.FirstRawFrame, self.NumRawFrames)

class VChunkHeader:

    def __init__(self, name, type_size):
        self.ChunkID        = str.encode(name)  # length=20
        self.TypeFlag       = 1999801           # special value
        self.DataSize       = type_size
        self.DataCount      = 0
        
    def dump(self):
        return pack('20siii', self.ChunkID, self.TypeFlag, self.DataSize, self.DataCount)

class VMaterial:

    def __init__(self):
        self.MaterialName   = ""    # length=64
        self.TextureIndex   = 0
        self.PolyFlags      = 0     # DWORD
        self.AuxMaterial    = 0
        self.AuxFlags       = 0     # DWORD
        self.LodBias        = 0
        self.LodStyle       = 0
        
    def dump(self):
        #print("DATA MATERIAL:",self.MaterialName)
        return pack('64siLiLii', str.encode(self.MaterialName), self.TextureIndex, self.PolyFlags, self.AuxMaterial, self.AuxFlags, self.LodBias, self.LodStyle)

class VBone:

    def __init__(self):
        self.Name           = ""    # length = 64
        self.Flags          = 0     # DWORD
        self.NumChildren    = 0
        self.ParentIndex    = 0
        self.BonePos        = VJointPos()
        
    def dump(self):
        return pack('64sLii', str.encode(self.Name), self.Flags, self.NumChildren, self.ParentIndex) + self.BonePos.dump()

#same as above - whatever - this is how Epic does it...  
class FNamedBoneBinary:

    def __init__(self):
        self.Name           = ""    # length = 64
        self.Flags          = 0     # DWORD
        self.NumChildren    = 0
        self.ParentIndex    = 0
        self.BonePos        = VJointPos()
        self.IsRealBone     = 0     # this is set to 1 when the bone is actually a bone in the mesh and not a dummy
        
    def dump(self):
        return pack('64sLii', str.encode(self.Name), self.Flags, self.NumChildren, self.ParentIndex) + self.BonePos.dump()

class VRawBoneInfluence:

    def __init__(self):
        self.Weight         = 0.0
        self.PointIndex     = 0
        self.BoneIndex      = 0
        
    def dump(self):
        return pack('fii', self.Weight, self.PointIndex, self.BoneIndex)

class VQuatAnimKey:

    def __init__(self):
        self.Position       = FVector()
        self.Orientation    = FQuat()
        self.Time           = 0.0
        
    def dump(self):
        return self.Position.dump() + self.Orientation.dump() + pack('f', self.Time)

class VVertex(object):

    def __init__(self):
        self.PointIndex     = 0     # WORD
        self.U              = 0.0
        self.V              = 0.0
        self.MatIndex       = 0     # BYTE
        self.Reserved       = 0     # BYTE
        self.SmoothGroup    = 0 
        
    def dump(self):
        return pack('HHffBBH', self.PointIndex, 0, self.U, self.V, self.MatIndex, self.Reserved, 0)
        
    def __cmp__(self, other):
        return cmp(self.PointIndex, other.PointIndex) \
            or cmp(self.U, other.U) \
            or cmp(self.V, other.V) \
            or cmp(self.MatIndex, other.MatIndex) \
            or cmp(self.Reserved, other.Reserved) \
            or cmp(self.SmoothGroup, other.SmoothGroup ) 
    
    def _key(self):
        return (type(self).__name__, self.PointIndex, self.U, self.V, self.MatIndex, self.Reserved)
        
    def __hash__(self):
        return hash(self._key())
        
    def __eq__(self, other):
        if not hasattr(other, '_key'):
            return False
        return self._key() == other._key()

class VPointSimple:

    def __init__(self):
        self.Point = FVector()

    def __cmp__(self, other):
        return cmp(self.Point, other.Point)
        
    def __hash__(self):
        return hash(self._key())

    def _key(self):
        return (type(self).__name__, self.Point)

    def __eq__(self, other):
        if not hasattr(other, '_key'):
            return False
        return self._key() == other._key()

class VPoint(object):

    def __init__(self):
        self.Point = FVector()
        self.SmoothGroup = 0 
        
    def dump(self):
        return self.Point.dump()
        
    def __cmp__(self, other):
        return cmp(self.Point, other.Point) \
            or cmp(self.SmoothGroup, other.SmoothGroup) 
    
    def _key(self):
        return (type(self).__name__, self.Point, self.SmoothGroup)
    
    def __hash__(self):
        return hash(self._key()) \
            ^ hash(self.SmoothGroup) 
        
    def __eq__(self, other):
        if not hasattr(other, '_key'):
            return False
        return self._key() == other._key() 

class VTriangle:

    def __init__(self):
        self.WedgeIndex0    = 0     # WORD
        self.WedgeIndex1    = 0     # WORD
        self.WedgeIndex2    = 0     # WORD
        self.MatIndex       = 0     # BYTE
        self.AuxMatIndex    = 0     # BYTE
        self.SmoothingGroups = 0    # DWORD
        
    def dump(self):
        return pack('HHHBBL', self.WedgeIndex0, self.WedgeIndex1, self.WedgeIndex2, self.MatIndex, self.AuxMatIndex, self.SmoothingGroups)

# END UNREAL DATA STRUCTS
#===========================================================================

#===========================================================================
# RG - helper class to handle the normal way the UT files are stored 
# as sections consisting of a header and then a list of data structures
#===========================================================================
class FileSection:
    
    def __init__(self, name, type_size):
        self.Header = VChunkHeader(name, type_size)
        self.Data   = []    # list of datatypes
    
    def dump(self):
        data = self.Header.dump()
        for i in range(len(self.Data)):
            data = data + self.Data[i].dump()
        return data
    
    def UpdateHeader(self):
        self.Header.DataCount = len(self.Data)

#===========================================================================
# PSK
#===========================================================================
class PSKFile:
    
    def __init__(self):
        self.GeneralHeader  = VChunkHeader("ACTRHEAD", 0)
        self.Points         = FileSection("PNTS0000", SIZE_VPOINT)              # VPoint
        self.Wedges         = FileSection("VTXW0000", SIZE_VVERTEX)             # VVertex
        self.Faces          = FileSection("FACE0000", SIZE_VTRIANGLE)           # VTriangle
        self.Materials      = FileSection("MATT0000", SIZE_VMATERIAL)           # VMaterial
        self.Bones          = FileSection("REFSKELT", SIZE_VBONE)               # VBone
        self.Influences     = FileSection("RAWWEIGHTS", SIZE_VRAWBONEINFLUENCE) # VRawBoneInfluence
        
        #RG - this mapping is not dumped, but is used internally to store the new point indices 
        # for vertex groups calculated during the mesh dump, so they can be used again
        # to dump bone influences during the armature dump
        #
        # the key in this dictionary is the VertexGroup/Bone Name, and the value
        # is a list of tuples containing the new point index and the weight, in that order
        #
        # Layout:
        # { groupname : [ (index, weight), ... ], ... }
        #
        # example: 
        # { 'MyVertexGroup' : [ (0, 1.0), (5, 1.0), (3, 0.5) ] , 'OtherGroup' : [(2, 1.0)] }
        
        self.VertexGroups = {} 
        
    def AddPoint(self, p):
        self.Points.Data.append(p)
        
    def AddWedge(self, w):
        self.Wedges.Data.append(w)
    
    def AddFace(self, f):
        self.Faces.Data.append(f)
        
    def AddMaterial(self, m):
        self.Materials.Data.append(m)
        
    def AddBone(self, b):
        self.Bones.Data.append(b)
        
    def AddInfluence(self, i):
        self.Influences.Data.append(i)
        
    def UpdateHeaders(self):
        self.Points.UpdateHeader()
        self.Wedges.UpdateHeader()
        self.Faces.UpdateHeader()
        self.Materials.UpdateHeader()
        self.Bones.UpdateHeader()
        self.Influences.UpdateHeader()
        
    def dump(self):
        self.UpdateHeaders()
        data = self.GeneralHeader.dump() + self.Points.dump() + self.Wedges.dump() + self.Faces.dump() + self.Materials.dump() + self.Bones.dump() + self.Influences.dump()
        return data
        
    def GetMatByIndex(self, mat_index):
        if mat_index >= 0 and len(self.Materials.Data) > mat_index:
            return self.Materials.Data[mat_index]
        else:
            m = VMaterial()
            # modified by VendorX
            m.MaterialName = MaterialName[mat_index]
            self.AddMaterial(m)
            return m
        
    def PrintOut(self):
        print( "{:>16} {:}".format( "Points", len(self.Points.Data) ) )
        print( "{:>16} {:}".format( "Wedges", len(self.Wedges.Data) ) )
        print( "{:>16} {:}".format( "Faces", len(self.Faces.Data) ) )
        print( "{:>16} {:}".format( "Materials", len(self.Materials.Data) ) )
        print( "{:>16} {:}".format( "Bones", len(self.Bones.Data) ) )
        print( "{:>16} {:}".format( "Influences", len(self.Influences.Data) ) )

#===========================================================================
# PSA
#
# Notes from UDN:
#   The raw key array holds all the keys for all the bones in all the specified sequences, 
#   organized as follows:
#   For each AnimInfoBinary's sequence there are [Number of bones] times [Number of frames keys] 
#   in the VQuatAnimKeys, laid out as tracks of [numframes] keys for each bone in the order of 
#   the bones as defined in the array of FnamedBoneBinary in the PSA. 
#
#   Once the data from the PSK (now digested into native skeletal mesh) and PSA (digested into 
#   a native animation object containing one or more sequences) are associated together at runtime, 
#   bones are linked up by name. Any bone in a skeleton (from the PSK) that finds no partner in 
#   the animation sequence (from the PSA) will assume its reference pose stance ( as defined in 
#   the offsets & rotations that are in the VBones making up the reference skeleton from the PSK)
#===========================================================================
class PSAFile:

    def __init__(self):
        self.GeneralHeader  = VChunkHeader("ANIMHEAD", 0)
        self.Bones          = FileSection("BONENAMES", SIZE_FNAMEDBONEBINARY)   #FNamedBoneBinary
        self.Animations     = FileSection("ANIMINFO", SIZE_ANIMINFOBINARY)      #AnimInfoBinary
        self.RawKeys        = FileSection("ANIMKEYS", SIZE_VQUATANIMKEY)        #VQuatAnimKey
        # this will take the format of key=Bone Name, value = (BoneIndex, Bone Object)
        # THIS IS NOT DUMPED
        self.BoneLookup = {} 

    def AddBone(self, b):
        self.Bones.Data.append(b)
        
    def AddAnimation(self, a):
        self.Animations.Data.append(a)
        
    def AddRawKey(self, k):
        self.RawKeys.Data.append(k)
        
    def UpdateHeaders(self):
        self.Bones.UpdateHeader()
        self.Animations.UpdateHeader()
        self.RawKeys.UpdateHeader()
        
    def GetBoneByIndex(self, bone_index):
        if bone_index >= 0 and len(self.Bones.Data) > bone_index:
            return self.Bones.Data[bone_index]
    
    def IsEmpty(self):
        return (len(self.Bones.Data) == 0 or len(self.Animations.Data) == 0)
    
    def StoreBone(self, b):
        self.BoneLookup[b.Name] = [-1, b]
                    
    def UseBone(self, bone_name):
        if bone_name in self.BoneLookup:
            bone_data = self.BoneLookup[bone_name]
            
            if bone_data[0] == -1:
                bone_data[0] = len(self.Bones.Data)
                self.AddBone(bone_data[1])
                #self.Bones.Data.append(bone_data[1])
            
            return bone_data[0]
            
    def GetBoneByName(self, bone_name):
        if bone_name in self.BoneLookup:
            bone_data = self.BoneLookup[bone_name]
            return bone_data[1]
        
    def GetBoneIndex(self, bone_name):
        if bone_name in self.BoneLookup:
            bone_data = self.BoneLookup[bone_name]
            return bone_data[0]
        
    def dump(self):
        self.UpdateHeaders()
        return self.GeneralHeader.dump() + self.Bones.dump() + self.Animations.dump() + self.RawKeys.dump()
        
    def PrintOut(self):
        print( "{:>16} {:}".format( "Bones", len(self.Bones.Data) ) )
        print( "{:>16} {:}".format( "Animations", len(self.Animations.Data) ) )
        print( "{:>16} {:}".format( "Raw keys", len(self.RawKeys.Data) ) )

#===========================================================================
# Helpers to create bone structs
#===========================================================================
def make_vbone( name, parent_index, child_count, orientation_quat, position_vect ):
    bone                        = VBone()
    bone.Name                   = name
    bone.ParentIndex            = parent_index
    bone.NumChildren            = child_count
    bone.BonePos.Orientation    = orientation_quat
    bone.BonePos.Position.X     = position_vect.x
    bone.BonePos.Position.Y     = position_vect.y
    bone.BonePos.Position.Z     = position_vect.z
    #these values seem to be ignored?
    #bone.BonePos.Length = tail.length
    #bone.BonePos.XSize = tail.x
    #bone.BonePos.YSize = tail.y
    #bone.BonePos.ZSize = tail.z
    return bone

def make_namedbonebinary( name, parent_index, child_count, orientation_quat, position_vect, is_real ):
    bone                        = FNamedBoneBinary()
    bone.Name                   = name
    bone.ParentIndex            = parent_index
    bone.NumChildren            = child_count
    bone.BonePos.Orientation    = orientation_quat
    bone.BonePos.Position.X     = position_vect.x
    bone.BonePos.Position.Y     = position_vect.y
    bone.BonePos.Position.Z     = position_vect.z
    bone.IsRealBone             = is_real
    return bone 

def make_fquat( bquat ):
    quat    = FQuat()
    #flip handedness for UT = set x,y,z to negative (rotate in other direction)
    quat.X  = -bquat.x
    quat.Y  = -bquat.y
    quat.Z  = -bquat.z
    quat.W  = bquat.w
    return quat
    
def make_fquat_default( bquat ):
    quat    = FQuat()
    #print(dir(bquat))
    quat.X  = bquat.x
    quat.Y  = bquat.y
    quat.Z  = bquat.z
    quat.W  = bquat.w
    return quat

#===========================================================================
#RG - check to make sure face isnt a line
#===========================================================================
def is_1d_face( face, mesh ):
    #ID Vertex of id point
    v0 = face.vertices[0]
    v1 = face.vertices[1]
    v2 = face.vertices[2]
    
    return (mesh.vertices[v0].co == mesh.vertices[v1].co \
        or mesh.vertices[v1].co == mesh.vertices[v2].co \
        or mesh.vertices[v2].co == mesh.vertices[v0].co)
    return False

#===========================================================================
# Smoothing group
# (renamed to seperate it from VVertex.SmoothGroup)
#===========================================================================
class SmoothingGroup:
    
    static_id = 1
    
    def __init__(self):
        self.faces              = []
        self.neighboring_faces  = []
        self.neighboring_groups = []
        self.id                 = -1
        self.local_id           = SmoothingGroup.static_id
        SmoothingGroup.static_id += 1
    
    def __cmp__(self, other):
        if isinstance(other, SmoothingGroup):
            return cmp( self.local_id, other.local_id )
        return -1
    
    def __hash__(self):
        return hash(self.local_id)

    # searches neighboring faces to determine which smoothing group ID can be used
    def get_valid_smoothgroup_id(self):
        temp_id = 1
        for group in self.neighboring_groups:
            if group != None and group.id == temp_id:
                if temp_id < 0x80000000:
                    temp_id = temp_id << 1
                else:
                    raise Error("Smoothing Group ID Overflowed, Smoothing Group evidently has more than 31 neighboring groups")
        
        self.id = temp_id
        return self.id
        
    def make_neighbor(self, new_neighbor):
        if new_neighbor not in self.neighboring_groups:
            self.neighboring_groups.append( new_neighbor )

    def contains_face(self, face):
        return (face in self.faces)
        
    def add_neighbor_face(self, face):
        if not face in self.neighboring_faces:
            self.neighboring_faces.append( face )
            
    def add_face(self, face):
        if not face in self.faces:
            self.faces.append( face )

def determine_edge_sharing( mesh ):
    
    edge_sharing_list = dict()
    
    for edge in mesh.edges:
        edge_sharing_list[edge.key] = []
    
    for face in mesh.tessfaces:
        for key in face.edge_keys:
            if not face in edge_sharing_list[key]:
                edge_sharing_list[key].append(face) # mark this face as sharing this edge
    
    return edge_sharing_list

def find_edges( mesh, key ):
    """ Temp replacement for mesh.findEdges().
        This is painfully slow.
    """
    for edge in mesh.edges:
        v = edge.vertices
        if key[0] == v[0] and key[1] == v[1]:
            return edge.index

def add_face_to_smoothgroup( mesh, face, edge_sharing_list, smoothgroup ):
    
    if face in smoothgroup.faces:
        return

    smoothgroup.add_face(face)
    
    for key in face.edge_keys:
        
        edge_id = find_edges(mesh, key)
        
        if edge_id != None:
            
            # not sharp
            if not( mesh.edges[edge_id].use_edge_sharp):
                
                for shared_face in edge_sharing_list[key]:
                    if shared_face != face:
                        # recursive
                        add_face_to_smoothgroup( mesh, shared_face, edge_sharing_list, smoothgroup )
            # sharp
            else:
                for shared_face in edge_sharing_list[key]:
                    if shared_face != face:
                        smoothgroup.add_neighbor_face( shared_face )

def determine_smoothgroup_for_face( mesh, face, edge_sharing_list, smoothgroup_list ):
    
    for group in smoothgroup_list:
        if (face in group.faces):
            return
    
    smoothgroup = SmoothingGroup();
    add_face_to_smoothgroup( mesh, face, edge_sharing_list, smoothgroup )
    
    if not smoothgroup in smoothgroup_list:
        smoothgroup_list.append( smoothgroup )

def build_neighbors_tree( smoothgroup_list ):

    for group in smoothgroup_list:
        for face in group.neighboring_faces:
            for neighbor_group in smoothgroup_list:
                if neighbor_group.contains_face( face ) and neighbor_group not in group.neighboring_groups:
                    group.make_neighbor( neighbor_group )
                    neighbor_group.make_neighbor( group )

#===========================================================================
# parse_smooth_groups
#===========================================================================
def parse_smooth_groups( mesh ):
    
    print("Parsing smooth groups...")
    
    t                   = time.clock()
    smoothgroup_list    = []
    edge_sharing_list   = determine_edge_sharing(mesh)
    #print("faces:",len(mesh.tessfaces))
    interval =  math.floor(len(mesh.tessfaces) / 100)
    if interval == 0: #if the faces are few do this
        interval =  math.floor(len(mesh.tessfaces) / 10)    
    #print("FACES:",len(mesh.tessfaces),"//100 =" "interval:",interval)
    for face in mesh.tessfaces:
        #print(dir(face))
        determine_smoothgroup_for_face(mesh, face, edge_sharing_list, smoothgroup_list)
        # progress indicator, writes to console without scrolling
        if face.index > 0 and (face.index % interval) == 0:
            print("Processing... {}%\r".format( int(face.index / len(mesh.tessfaces) * 100) ), end='')
            sys.stdout.flush()
    print("Completed" , ' '*20)
    
    verbose("len(smoothgroup_list)={}".format(len(smoothgroup_list)))
    
    build_neighbors_tree(smoothgroup_list)
    
    for group in smoothgroup_list:
        group.get_valid_smoothgroup_id()
    
    print("Smooth group parsing completed in {:.2f}s".format(time.clock() - t))
    return smoothgroup_list

#===========================================================================
# http://en.wikibooks.org/wiki/Blender_3D:_Blending_Into_Python/Cookbook#Triangulate_NMesh
# blender 2.50 format using the Operators/command convert the mesh to tri mesh
#===========================================================================
def triangulate_mesh( object ):
    
    verbose(header("triangulateNMesh"))
    #print(type(object))
    scene = bpy.context.scene
    
    me_ob       = object.copy()
    me_ob.data = object.to_mesh(bpy.context.scene, True, 'PREVIEW') #write data object
    bpy.context.scene.objects.link(me_ob)
    bpy.context.scene.update()
    bpy.ops.object.mode_set(mode='OBJECT')
    for i in scene.objects:
        i.select = False # deselect all objects
    
    me_ob.select            = True
    scene.objects.active    = me_ob
    
    print("Copy and Convert mesh just incase any way...")
    
    bpy.ops.object.mode_set(mode='EDIT')
    bpy.ops.mesh.select_all(action='SELECT')# select all the face/vertex/edge
    bpy.ops.object.mode_set(mode='EDIT')
    bpy.ops.mesh.quads_convert_to_tris()
    bpy.context.scene.update()
    
    bpy.ops.object.mode_set(mode='OBJECT')
        
    bpy.context.scene.udk_option_triangulate = True
        
    verbose("Triangulated mesh")
        
    me_ob.data = me_ob.to_mesh(bpy.context.scene, True, 'PREVIEW') #write data object
    bpy.context.scene.update()
    return me_ob

#copy mesh data and then merge them into one object
def meshmerge(selectedobjects):
    bpy.ops.object.mode_set(mode='OBJECT') #object mode and not edit mode
    cloneobjects = [] #object holder for copying object data
    if len(selectedobjects) > 1:
        print("selectedobjects:",len(selectedobjects)) #print select object
        count = 0 #reset count
        for count in range(len( selectedobjects)): 
            #print("Index:",count)
            if selectedobjects[count] != None:
                me_da = selectedobjects[count].data.copy() #copy data
                me_ob = selectedobjects[count].copy() #copy object
                #note two copy two types else it will use the current data or mesh
                me_ob.data = me_da #assign the data
                bpy.context.scene.objects.link(me_ob)#link the object to the scene #current object location
                print("Index:",count,"clone object",me_ob.name) #print clone object
                cloneobjects.append(me_ob) #add object to the array
        for i in bpy.data.objects: i.select = False #deselect all objects
        count = 0 #reset count
        #begin merging the mesh together as one
        for count in range(len( cloneobjects)):
            if count == 0:
                bpy.context.scene.objects.active = cloneobjects[count]
                print("Set Active Object:",cloneobjects[count].name)
            cloneobjects[count].select = True
        bpy.ops.object.join() #join object together
        if len(cloneobjects) > 1:
            bpy.types.Scene.udk_copy_merge = True
    return cloneobjects[0]
    
#sort the mesh center top list and not center at the last array. Base on order while select to merge mesh to make them center.
def sortmesh(selectmesh):
    print("MESH SORTING...")
    centermesh = []
    notcentermesh = []
    for countm in range(len(selectmesh)):
        #if object are center add here
        if selectmesh[countm].location.x == 0 and selectmesh[countm].location.y == 0 and selectmesh[countm].location.z == 0:
            centermesh.append(selectmesh[countm])
        else:#if not add here for not center
            notcentermesh.append(selectmesh[countm])
    selectmesh = []
    #add mesh object in order for merge object 
    for countm in range(len(centermesh)):
        selectmesh.append(centermesh[countm])
    for countm in range(len(notcentermesh)):
        selectmesh.append(notcentermesh[countm])
    if len(selectmesh) == 1: #if there one mesh just do some here
        return selectmesh[0] #return object mesh
    else:
        return meshmerge(selectmesh) #return merge object mesh

#===========================================================================
# parse_mesh
#===========================================================================
def parse_mesh( mesh, psk ):
    #bpy.ops.object.mode_set(mode='OBJECT')
    #error ? on commands for select object?
    print(header("MESH", 'RIGHT'))
    print("Mesh object:", mesh.name)
    scene = bpy.context.scene
    for i in scene.objects: i.select = False # deselect all objects