# This script is licensed as public domain.

bl_info = {
    "name": "Export Inter-Quake Model (.iqm/.iqe)",
    "author": "Lee Salzman",
    "version": (2019, 4, 24),
    "blender": (2, 80, 0),
    "location": "File > Export > Inter-Quake Model",
    "description": "Export to the Inter-Quake Model format (.iqm/.iqe)",
    "warning": "",
    "wiki_url": "",
    "tracker_url": "",
    "category": "Import-Export"}

import os, struct, math
import mathutils
import bpy
import bpy_extras.io_utils

IQM_POSITION     = 0
IQM_TEXCOORD     = 1
IQM_NORMAL       = 2
IQM_TANGENT      = 3
IQM_BLENDINDEXES = 4
IQM_BLENDWEIGHTS = 5
IQM_COLOR        = 6
IQM_CUSTOM       = 0x10

IQM_BYTE   = 0
IQM_UBYTE  = 1
IQM_SHORT  = 2
IQM_USHORT = 3
IQM_INT    = 4
IQM_UINT   = 5
IQM_HALF   = 6
IQM_FLOAT  = 7
IQM_DOUBLE = 8

IQM_LOOP = 1

IQM_HEADER      = struct.Struct('<16s27I')
IQM_MESH        = struct.Struct('<6I')
IQM_TRIANGLE    = struct.Struct('<3I')
IQM_JOINT       = struct.Struct('<Ii10f')
IQM_POSE        = struct.Struct('<iI20f')
IQM_ANIMATION   = struct.Struct('<3IfI')
IQM_VERTEXARRAY = struct.Struct('<5I')
IQM_BOUNDS      = struct.Struct('<8f')

MAXVCACHE = 32

class Vertex:
    def __init__(self, index, coord, normal, uv, weights, color):
        self.index   = index
        self.coord   = coord
        self.normal  = normal
        self.uv      = uv
        self.weights = weights
        self.color   = color

    def normalizeWeights(self):
        # renormalizes all weights such that they add up to 255
        # the list is chopped/padded to exactly 4 weights if necessary
        if not self.weights:
            self.weights = [ (0, 0), (0, 0), (0, 0), (0, 0) ]
            return
        self.weights.sort(key = lambda weight: weight[0], reverse=True)
        if len(self.weights) > 4: 
            del self.weights[4:]
        totalweight = sum([ weight for (weight, bone) in self.weights])
        if totalweight > 0:
            self.weights = [ (int(round(weight * 255.0 / totalweight)), bone) for (weight, bone) in self.weights]
            while len(self.weights) > 1 and self.weights[-1][0] <= 0:
                self.weights.pop()
        else:
            totalweight = len(self.weights)
            self.weights = [ (int(round(255.0 / totalweight)), bone) for (weight, bone) in self.weights]
        totalweight = sum([ weight for (weight, bone) in self.weights])
        while totalweight != 255:
            for i, (weight, bone) in enumerate(self.weights):
                if totalweight > 255 and weight > 0:
                    self.weights[i] = (weight - 1, bone)
                    totalweight -= 1
                elif totalweight < 255 and weight < 255:
                    self.weights[i] = (weight + 1, bone)
                    totalweight += 1
        while len(self.weights) < 4:
            self.weights.append((0, self.weights[-1][1]))

    def calcScore(self):
        if self.uses:
            self.score = 2.0 * pow(len(self.uses), -0.5)
            if self.cacherank >= 3:
                self.score += pow(1.0 - float(self.cacherank - 3)/MAXVCACHE, 1.5)
            elif self.cacherank >= 0:
                self.score += 0.75
        else:
            self.score = -1.0

    def neighborKey(self, other):
        if self.coord < other.coord:
            return (self.coord.x, self.coord.y, self.coord.z, other.coord.x, other.coord.y, other.coord.z, tuple(self.weights), tuple(other.weights))
        else:
            return (other.coord.x, other.coord.y, other.coord.z, self.coord.x, self.coord.y, self.coord.z, tuple(other.weights), tuple(self.weights)) 
        
    def __hash__(self):
        return self.index

    def __eq__(self, v):
        return self.coord == v.coord and self.normal == v.normal and self.uv == v.uv and self.weights == v.weights and self.color == v.color


class Mesh:
    def __init__(self, name, material, verts):
        self.name      = name
        self.material  = material
        self.verts     = [ None for v in verts ]
        self.vertmap   = {}
        self.tris      = []
   
    def calcTangents(self):
        # See "Tangent Space Calculation" at http://www.terathon.com/code/tangent.html
        for v in self.verts:
            v.tangent = mathutils.Vector((0.0, 0.0, 0.0))
            v.bitangent = mathutils.Vector((0.0, 0.0, 0.0))
        for (v0, v1, v2) in self.tris:
            dco1 = v1.coord - v0.coord
            dco2 = v2.coord - v0.coord
            duv1 = v1.uv - v0.uv
            duv2 = v2.uv - v0.uv
            tangent = dco2*duv1.y - dco1*duv2.y
            bitangent = dco2*duv1.x - dco1*duv2.x
            if dco2.cross(dco1).dot(bitangent.cross(tangent)) < 0:
                tangent.negate()
                bitangent.negate()
            v0.tangent += tangent
            v1.tangent += tangent
            v2.tangent += tangent
            v0.bitangent += bitangent
            v1.bitangent += bitangent
            v2.bitangent += bitangent
        for v in self.verts:    
            v.tangent = v.tangent - v.normal*v.tangent.dot(v.normal)
            v.tangent.normalize()
            if v.normal.cross(v.tangent).dot(v.bitangent) < 0:
                v.bitangent = -1.0
            else:
                v.bitangent = 1.0
        
    def optimize(self):
        # Linear-speed vertex cache optimization algorithm by Tom Forsyth
        for v in self.verts:
            if v:
                v.index = -1
                v.uses = []
                v.cacherank = -1
        for i, (v0, v1, v2) in enumerate(self.tris):
            v0.uses.append(i)
            v1.uses.append(i)
            v2.uses.append(i)
        for v in self.verts:
            if v:
                v.calcScore()

        besttri = -1
        bestscore = -42.0
        scores = []
        for i, (v0, v1, v2) in enumerate(self.tris): 
            scores.append(v0.score + v1.score + v2.score)
            if scores[i] > bestscore:
                besttri = i
                bestscore = scores[i]

        vertloads = 0 # debug info
        vertschedule = []
        trischedule = []
        vcache = []
        while besttri >= 0:
            tri = self.tris[besttri]
            scores[besttri] = -666.0
            trischedule.append(tri)
            for v in tri:
                if v.cacherank < 0: # debug info
                    vertloads += 1  # debug info
                if v.index < 0: 
                    v.index = len(vertschedule)
                    vertschedule.append(v)
                v.uses.remove(besttri)
                v.cacherank = -1
                v.score = -1.0
            vcache = [ v for v in tri if v.uses ] + [ v for v in vcache if v.cacherank >= 0 ]
            for i, v in enumerate(vcache):
                v.cacherank = i 
                v.calcScore()

            besttri = -1
            bestscore = -42.0
            for v in vcache:
                for i in v.uses:
                    v0, v1, v2 = self.tris[i]
                    scores[i] = v0.score + v1.score + v2.score
                    if scores[i] > bestscore:
                        besttri = i
                        bestscore = scores[i]
            while len(vcache) > MAXVCACHE:
                vcache.pop().cacherank = -1
            if besttri < 0:
                for i, score in enumerate(scores):
                    if score > bestscore:
                        besttri = i
                        bestscore = score

        print('%s: %d verts optimized to %d/%d loads for %d entry LRU cache' % (self.name, len(self.verts), vertloads, len(vertschedule), MAXVCACHE))
        #print('%s: %d verts scheduled to %d' % (self.name, len(self.verts), len(vertschedule)))
        self.verts = vertschedule
        # print('%s: %d tris scheduled to %d' % (self.name, len(self.tris), len(trischedule)))         
        self.tris = trischedule                 

    def meshData(self, iqm):
        return [ iqm.addText(self.name), iqm.addText(self.material), self.firstvert, len(self.verts), self.firsttri, len(self.tris) ]


class Bone:
    def __init__(self, name, origname, index, parent, matrix):
        self.name = name
        self.origname = origname
        self.index = index
        self.parent = parent
        self.matrix = matrix
        self.localmatrix = matrix
        if self.parent:
            self.localmatrix = parent.matrix.inverted() @ self.localmatrix
        self.numchannels = 0
        self.channelmask = 0
        self.channeloffsets = [ 1.0e10, 1.0e10, 1.0e10, 1.0e10, 1.0e10, 1.0e10, 1.0e10, 1.0e10, 1.0e10, 1.0e10 ]
        self.channelscales = [ -1.0e10, -1.0e10, -1.0e10, -1.0e10, -1.0e10, -1.0e10, -1.0e10, -1.0e10, -1.0e10, -1.0e10 ]

    def jointData(self, iqm):
        if self.parent:
            parent = self.parent.index
        else:
            parent = -1
        pos = self.localmatrix.to_translation()
        orient = self.localmatrix.to_quaternion()
        orient.normalize()
        if orient.w > 0:
            orient.negate()
        scale = self.localmatrix.to_scale()
        scale.x = round(scale.x*0x10000)/0x10000
        scale.y = round(scale.y*0x10000)/0x10000
        scale.z = round(scale.z*0x10000)/0x10000
        return [ iqm.addText(self.name), parent, pos.x, pos.y, pos.z, orient.x, orient.y, orient.z, orient.w, scale.x, scale.y, scale.z ]
 
    def poseData(self, iqm):
        if self.parent:
            parent = self.parent.index
        else:
            parent = -1
        return [ parent, self.channelmask ] + self.channeloffsets + self.channelscales

    def calcChannelMask(self):
        for i in range(0, 10):
            self.channelscales[i] -= self.channeloffsets[i]
            if self.channelscales[i] >= 1.0e-10:
                self.numchannels += 1
                self.channelmask |= 1 << i
                self.channelscales[i] /= 0xFFFF
            else:
                self.channelscales[i] = 0.0
        return self.numchannels 


class Animation:
    def __init__(self, name, frames, fps = 0.0, flags = 0):
        self.name = name
        self.frames = frames
        self.fps = fps
        self.flags = flags

    def calcFrameLimits(self, bones):
        for frame in self.frames:
            for i, bone in enumerate(bones):
                loc, quat, scale, mat = frame[i]
                bone.channeloffsets[0] = min(bone.channeloffsets[0], loc.x)
                bone.channeloffsets[1] = min(bone.channeloffsets[1], loc.y)
                bone.channeloffsets[2] = min(bone.channeloffsets[2], loc.z)
                bone.channeloffsets[3] = min(bone.channeloffsets[3], quat.x)
                bone.channeloffsets[4] = min(bone.channeloffsets[4], quat.y)
                bone.channeloffsets[5] = min(bone.channeloffsets[5], quat.z)
                bone.channeloffsets[6] = min(bone.channeloffsets[6], quat.w)
                bone.channeloffsets[7] = min(bone.channeloffsets[7], scale.x)
                bone.channeloffsets[8] = min(bone.channeloffsets[8], scale.y)
                bone.channeloffsets[9] = min(bone.channeloffsets[9], scale.z)
                bone.channelscales[0] = max(bone.channelscales[0], loc.x)
                bone.channelscales[1] = max(bone.channelscales[1], loc.y)
                bone.channelscales[2] = max(bone.channelscales[2], loc.z)
                bone.channelscales[3] = max(bone.channelscales[3], quat.x)
                bone.channelscales[4] = max(bone.channelscales[4], quat.y)
                bone.channelscales[5] = max(bone.channelscales[5], quat.z)
                bone.channelscales[6] = max(bone.channelscales[6], quat.w)
                bone.channelscales[7] = max(bone.channelscales[7], scale.x)
                bone.channelscales[8] = max(bone.channelscales[8], scale.y)
                bone.channelscales[9] = max(bone.channelscales[9], scale.z)

    def animData(self, iqm):
        return [ iqm.addText(self.name), self.firstframe, len(self.frames), self.fps, self.flags ]

    def frameData(self, bones): 
        data = b''
        for frame in self.frames:
            for i, bone in enumerate(bones):
                loc, quat, scale, mat = frame[i]
                if (bone.channelmask&0x7F) == 0x7F:
                    lx = int(round((loc.x - bone.channeloffsets[0]) / bone.channelscales[0]))
                    ly = int(round((loc.y - bone.channeloffsets[1]) / bone.channelscales[1]))
                    lz = int(round((loc.z - bone.channeloffsets[2]) / bone.channelscales[2]))
                    qx = int(round((quat.x - bone.channeloffsets[3]) / bone.channelscales[3]))
                    qy = int(round((quat.y - bone.channeloffsets[4]) / bone.channelscales[4]))
                    qz = int(round((quat.z - bone.channeloffsets[5]) / bone.channelscales[5]))
                    qw = int(round((quat.w - bone.channeloffsets[6]) / bone.channelscales[6]))
                    data += struct.pack('<7H', lx, ly, lz, qx, qy, qz, qw)
                else:
                    if bone.channelmask & 1:
                        data += struct.pack('<H', int(round((loc.x - bone.channeloffsets[0]) / bone.channelscales[0])))
                    if bone.channelmask & 2:
                        data += struct.pack('<H', int(round((loc.y - bone.channeloffsets[1]) / bone.channelscales[1])))
                    if bone.channelmask & 4:
                        data += struct.pack('<H', int(round((loc.z - bone.channeloffsets[2]) / bone.channelscales[2])))
                    if bone.channelmask & 8:
                        data += struct.pack('<H', int(round((quat.x - bone.channeloffsets[3]) / bone.channelscales[3])))
                    if bone.channelmask & 16:
                        data += struct.pack('<H', int(round((quat.y - bone.channeloffsets[4]) / bone.channelscales[4])))
                    if bone.channelmask & 32:
                        data += struct.pack('<H', int(round((quat.z - bone.channeloffsets[5]) / bone.channelscales[5])))
                    if bone.channelmask & 64:
                        data += struct.pack('<H', int(round((quat.w - bone.channeloffsets[6]) / bone.channelscales[6])))
                if bone.channelmask & 128:
                    data += struct.pack('<H', int(round((scale.x - bone.channeloffsets[7]) / bone.channelscales[7])))
                if bone.channelmask & 256:
                    data += struct.pack('<H', int(round((scale.y - bone.channeloffsets[8]) / bone.channelscales[8])))
                if bone.channelmask & 512:
                    data += struct.pack('<H', int(round((scale.z - bone.channeloffsets[9]) / bone.channelscales[9])))
        return data

    def frameBoundsData(self, bones, meshes, frame, invbase):
        bbmin = bbmax = None
        xyradius = 0.0
        radius = 0.0
        transforms = []
        for i, bone in enumerate(bones):
            loc, quat, scale, mat = frame[i]
            if bone.parent:
                mat = transforms[bone.parent.index] @ mat
            transforms.append(mat)
        for i, mat in enumerate(transforms):
            transforms[i] = mat @ invbase[i]
        for mesh in meshes:
            for v in mesh.verts:
                pos = mathutils.Vector((0.0, 0.0, 0.0))
                for (weight, bone) in v.weights:
                    if weight > 0:
                        pos += (transforms[bone] @ v.coord) * (weight / 255.0)
                if bbmin:
                    bbmin.x = min(bbmin.x, pos.x)
                    bbmin.y = min(bbmin.y, pos.y)
                    bbmin.z = min(bbmin.z, pos.z)
                    bbmax.x = max(bbmax.x, pos.x)
                    bbmax.y = max(bbmax.y, pos.y)
                    bbmax.z = max(bbmax.z, pos.z)
                else:
                    bbmin = pos.copy()
                    bbmax = pos.copy()
                pradius = pos.x*pos.x + pos.y*pos.y
                if pradius > xyradius:
                    xyradius = pradius
                pradius += pos.z*pos.z
                if pradius > radius:
                    radius = pradius
        if bbmin:
            xyradius = math.sqrt(xyradius)
            radius = math.sqrt(radius)
        else:
            bbmin = bbmax = mathutils.Vector((0.0, 0.0, 0.0))
        return IQM_BOUNDS.pack(bbmin.x, bbmin.y, bbmin.z, bbmax.x, bbmax.y, bbmax.z, xyradius, radius)
 
    def boundsData(self, bones, meshes):
        invbase = []
        for bone in bones:
            invbase.append(bone.matrix.inverted())
        data = b''
        for i, frame in enumerate(self.frames):
            print('Calculating bounding box for %s:%d' % (self.name, i))
            data += self.frameBoundsData(bones, meshes, frame, invbase)     
        return data
   
 
class IQMFile:
    def __init__(self):
        self.textoffsets = {}
        self.textdata = b''
        self.meshes = []
        self.meshdata = []
        self.numverts = 0
        self.numtris = 0
        self.joints = []
        self.jointdata = []
        self.numframes = 0
        self.framesize = 0
        self.anims = []
        self.posedata = []
        self.animdata = []
        self.framedata = []
        self.vertdata = []

    def addText(self, str):
        if not self.textdata:
            self.textdata += b'\x00'
            self.textoffsets[''] = 0
        try:
            return self.textoffsets[str]
        except:
            offset = len(self.textdata)
            self.textoffsets[str] = offset
            self.textdata += bytes(str, encoding="utf8") + b'\x00'
            return offset

    def addJoints(self, bones):
        for bone in bones:
            self.joints.append(bone)
            if self.meshes: