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",
    "version": (2, 4),
    "blender": (2, 6, 2),
    "api": 36079,
    "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.5/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 os
import time
import bpy
import mathutils
import random
import operator
import sys

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 = int(len(mesh.tessfaces) / 100)
	#print("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 #bug in the code for face  to tessface
		#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
	
	#bpy.ops.object.mode_set(mode='OBJECT')
	
	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


#===========================================================================
# 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
	scene.objects.active	= mesh
	mesh = triangulate_mesh(mesh)
	#print("FACES----:",len(mesh.data.tessfaces))
	verbose("Working mesh object: {}".format(mesh.name))
	
	#collect a list of the material names
	print("Materials...")
	
	mat_slot_index = 0

	for slot in mesh.material_slots:

		print("  Material {} '{}'".format(mat_slot_index, slot.name))
		MaterialName.append(slot.name)
		#if slot.material.texture_slots[0] != None:
			#if slot.material.texture_slots[0].texture.image.filepath != None:
				#print("    Texture path {}".format(slot.material.texture_slots[0].texture.image.filepath)) 
		#create the current material
		v_material				= psk.GetMatByIndex(mat_slot_index)