
#ifndef __read_skl_h__
#include "read_skl.h"
#endif

#ifndef __skelmodel_h__
#include "skelmodel.h"
#endif

#ifndef __skelanim_h__
#include "skelanim.h"
#endif

#ifndef __memalign_h__
#include "memalign.h"
#endif

#include "formatters.h"

#include <XError.h>


#include "vec3.h"
#include <ctype.h>
#include <string.h>

#define MAXBONES 250
#define MAXVERTWEIGHTS 10
#define MAXVERTS 4000
#define MAXTRIS (MAXVERTS * 2)
#define MAXFRAMES 500
#define MAXVTRI 64
#define MAXBONEWEIGHTS MAXVERTS
#define MAXVGROUPS MAXVTRI
#define NOCOLLAPSE_ERROR 100000000.0f

struct skl_weight {
	short bone;
	short pos_index;
	short norm_index;
	float w;
	vec3 pos;
	vec3 norm;
};

struct skl_bone {
	char name[256];
	vec3 offset;
	bool tagbone;
	float m[3][3];
	float q[4];
	float bounds[3][2];
	short number;
	short parent;
	short used_count;
	short weight_count;
	float weight_data[MAXBONEWEIGHTS][4];
};

static skl_bone bones[MAXBONES];
static int bone_count;
static int used_bone_count;

struct skl_vertsmooth {
	unsigned group_mask;
	short tcount;
	short tri[MAXVTRI];
};

struct skl_vert {
	short number;
	short collapse_to;
	vec3 pos;
	short weight_count;
	short group_count;
	short superposition_group;
	short next_in_superposition_group;
	short used_count;
	short used_by[MAXVTRI];
	bool no_reduce;
	skl_weight weights[MAXVERTWEIGHTS];
	skl_vertsmooth groups[MAXVGROUPS];
	
	// only used after we duplicate vertices
	vec3 norm;
	float s, t;
};

static skl_vert verts[MAXVERTS];
static int vert_count;

struct skl_tri {
	short collapse_at;
	bool npatch_fill_only;
	short v[3];
	float s[3];
	float t[3];
	vec3 norm;
	float area;
};

static skl_tri tris[MAXTRIS];
static int tri_count;


struct skl_bonepos {
	vec3 pos;
	float m[3][3];
};

static skl_bonepos frames[MAXFRAMES][MAXBONES];
static int frame_count;
float frame_rate;

static short collapse_rounded_counts[MAXVERTS];
static short collapse_order[MAXVERTS];
static int collapse_count;

static int irreducible_vert_count;
static int used_vert_count;


#if 1 || defined(macintosh)

#define check_smooth_tri() ((void)0)
#define assert(A) ((void)0)

#else
#define enter_debugger() __asm {int 3}
#define assert(expr) if (!(expr)) { enter_debugger(); /* exit(-1); */ }


void check_smooth_tri()
{
	int i, j, k, m, n;
	skl_vert *v;
	skl_vertsmooth *s;
	skl_tri *t;
	
	for (i = 0; i < vert_count; ++i)
	{
		v = &(verts[i]);
		if (v->number < 0) continue;
		assert( v->group_count >= 0 && v->group_count < MAXVTRI );
		for (j = 0; j < v->group_count; ++j)
		{
			s = &(v->groups[j]);
			assert( s->tcount >= 1 && s->tcount <= MAXVTRI );
			//assert( s->group_mask );
			for (k = 0; k < v->group_count; ++k)
			{
				if (k == j) continue;
				assert( (s->group_mask & v->groups[k].group_mask) == 0 );
			}
			for (k = 0; k < s->tcount; ++k)
			{
				assert( s->tri[k] >= 0 && s->tri[k] < tri_count );
				t = &(tris[s->tri[k]]);
				n = 0;
				for (m = 0; m < 3; ++m)
				{
					if (t->v[m] == i) ++n;
				}
				assert( n == 1 );
			}
		}
	}
	
	for (i = 0; i < tri_count; ++i)
	{
		t = &(tris[i]);
		for (j = 0; j < 3; ++j)
		{
			assert( t->v[j] >= 0 && t->v[j] < vert_count );
			v = &(verts[t->v[j]]);
			assert( v->number >= 0 );
			n = 0;
			for (k = 0; k < v->group_count; ++k)
			{
				s = &(v->groups[k]);
				for (m = 0; m < s->tcount; ++m)
				{
					if (s->tri[m] == i) ++n;
				}
			}
			assert( n == 1 );
		}
	}
}
#endif


void MatToQuat( float destQuat[ 4 ], const float srcMatrix[ 3 ][ 3 ] )
	
	{
	double  	trace, s;
	int     	i, j, k;
	static int 	next[3] = {1, 2, 0};

	trace = srcMatrix[0][0] + srcMatrix[1][1]+ srcMatrix[2][2];

	if (trace > 0.0)
		{
		s = sqrt(trace + 1.0);
		destQuat[3] = s * 0.5;
		s = 0.5 / s;
    
		destQuat[0] = (srcMatrix[2][1] - srcMatrix[1][2]) * s;
		destQuat[1] = (srcMatrix[0][2] - srcMatrix[2][0]) * s;
		destQuat[2] = (srcMatrix[1][0] - srcMatrix[0][1]) * s;
		} 
	else 
		{
		i = 0;
		if (srcMatrix[1][1] > srcMatrix[0][0])
			i = 1;
		if (srcMatrix[2][2] > srcMatrix[i][i])
			i = 2;
		j = next[i];  
		k = next[j];
    
		s = sqrt( (srcMatrix[i][i] - (srcMatrix[j][j]+srcMatrix[k][k])) + 1.0 );
		destQuat[i] = s * 0.5;
    
		s = 0.5 / s;
    
		destQuat[3] = (srcMatrix[k][j] - srcMatrix[j][k]) * s;
		destQuat[j] = (srcMatrix[j][i] + srcMatrix[i][j]) * s;
		destQuat[k] = (srcMatrix[k][i] + srcMatrix[i][k]) * s;
		}
	
#if 0
	float temp[3][3];
	QuatToMat( temp, destQuat );
	float test1[3], test2[3];
	
	// check unitary
	for (i = 0; i < 3; ++i) {
		test1[i] = test2[i] = 0.0f;
		for (j = 0; j < 3; ++j) {
			test1[i] += srcMatrix[i][j] * srcMatrix[i][j];
			test2[i] += srcMatrix[j][i] * srcMatrix[j][i];
		}
	}
	for (i = 0; i < 3; ++i) {
		if (fabs( test1[i] - 1.0f ) > 0.01f || fabs( test2[i] - 1.0f ) > 0.01f) {
			test1[i] = test1[i];
			break;
		}
	}
	
	// check dots
	for (i = 0; i < 3; ++i) {
		for (j = 0; j < 3; ++j) {
			if (i == j) continue;
			test1[j] = test2[j] = 0.0f;
			for (k = 0; k < 3; ++k) {
				test1[j] += srcMatrix[i][k] * srcMatrix[j][k];
				test2[j] += srcMatrix[k][i] * srcMatrix[k][j];
			}
			if (fabs(test1[j]) > 0.01f || fabs(test2[j]) > 0.01f) {
				test1[i] = test1[i];
				break;
			}
		}
	}
	
	// check inverse
	for (i = 0; i < 3; ++i) {
		test1[i] = test2[i] = 0.0f;
		for (j = 0; j < 3; ++j) {
			test1[i] += temp[i][j] * srcMatrix[i][j];
			test2[i] += temp[j][i] * srcMatrix[j][i];
		}
	}
	for (i = 0; i < 3; ++i) {
		if (fabs( test1[i] - 1.0f ) > 0.01f || fabs( test2[i] - 1.0f ) > 0.01f) {
			test1[i] = test1[i];
			break;
		}
	}
	
#endif
	}

void QuatToMat
	(
	float m[ 3 ][ 3 ],
	const float q[ 4 ]
	)

	{
	float wx, wy, wz;
	float xx, yy, yz;
	float xy, xz, zz;
	float x2, y2, z2;

	x2 = q[0] + q[0];
	y2 = q[1] + q[1];
	z2 = q[2] + q[2];

	xx = q[0] * x2;
	xy = q[0] * y2;
	xz = q[0] * z2;

	yy = q[1] * y2;
	yz = q[1] * z2;
	zz = q[2] * z2;

	wx = q[3] * x2;
	wy = q[3] * y2;
	wz = q[3] * z2;

	m[ 0 ][ 0 ] = 1.0f - ( yy + zz );
	m[ 0 ][ 1 ] = xy - wz;
	m[ 0 ][ 2 ] = xz + wy;

	m[ 1 ][ 0 ] = xy + wz;
	m[ 1 ][ 1 ] = 1.0f - ( xx + zz );
	m[ 1 ][ 2 ] = yz - wx;

	m[ 2 ][ 0 ] = xz - wy;
	m[ 2 ][ 1 ] = yz + wx;
	m[ 2 ][ 2 ] = 1.0f - ( xx + yy );
}

void QuatMult( float out[ 4 ], const float q1[ 4 ], const float q2[ 4 ] )
{
	float x, y, z, w;
	x = q1[3] * q2[0] + q2[3] * q1[0] + q1[1] * q2[2] - q1[2] * q2[1];
	y = q1[3] * q2[1] + q2[3] * q1[1] + q1[2] * q2[0] - q1[0] * q2[2];
	z = q1[3] * q2[2] + q2[3] * q1[2] + q1[0] * q2[1] - q1[1] * q2[0];
	w = q1[3] * q2[3] - q1[0] * q2[0] - q1[1] * q2[1] - q1[2] * q2[2];
	out[0] = x;
	out[1] = y;
	out[2] = z;
	out[3] = w;
}

#define DELTA 1e-6

void SlerpQuaternion
	(
	float output[ 4 ],
	const float in_from[ 4 ],
	const float in_to[ 4 ],
	float t
	)

	{
	float		to1[ 4 ];
	double	omega, cosom, sinom, scale0, scale1;

	cosom = in_from[0] * in_to[0] + in_from[1] * in_to[1] + in_from[2] * in_to[2] + in_from[3] * in_to[3];
	if ( cosom < 0.0 )
		{
		cosom = -cosom;
		to1[0] = -in_to[0];
		to1[1] = -in_to[1];
		to1[2] = -in_to[2];
		to1[3] = -in_to[3];
		}
	else if 
      (
         ( in_from[0] == in_to[0] ) &&
         ( in_from[1] == in_to[1] ) &&
         ( in_from[2] == in_to[2] ) &&
         ( in_from[3] == in_to[3] ) 
      )
		{
      // equal case, early exit
	   output[0] = in_to[0];
	   output[1] = in_to[1];
	   output[2] = in_to[2];
	   output[3] = in_to[3];
      return;
      }
	else
		{
		to1[0] = in_to[0];
		to1[1] = in_to[1];
		to1[2] = in_to[2];
		to1[3] = in_to[3];
		}

	if ( ( 1.0 - cosom ) > DELTA )
		{
		omega = acos( cosom );
		sinom = sin( omega );
		scale0 = sin( ( 1.0 - t ) * omega ) / sinom;
		scale1 = sin( t * omega ) / sinom;
		}
	else
		{
		scale0 = 1.0 - t;
		scale1 = t;
		}

	output[0] = scale0 * in_from[0] + scale1 * to1[0];
	output[1] = scale0 * in_from[1] + scale1 * to1[1];
	output[2] = scale0 * in_from[2] + scale1 * to1[2];
	output[3] = scale0 * in_from[3] + scale1 * to1[3];
	}


inline void MatMult( float out[3][3], const float a[3][3], const float b[3][3] )
{
	float temp[3][3];
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			temp[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j] + a[i][2] * b[2][j];
		}
	}
	memcpy( out, temp, sizeof(temp) );
}


void TransposeMat( float out[3][3], const float in[3][3] )
{
	float temp[3][3];
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			temp[i][j] = in[j][i];
		}
	}
	memcpy( out, temp, sizeof(temp) );
}


inline vec3 transform( const float (*m)[3], const vec3 &v )
{
	vec3 o;
	o.x = v.x * m[0][0] + v.y * m[0][1] + v.z * m[0][2];
	o.y = v.x * m[1][0] + v.y * m[1][1] + v.z * m[1][2];
	o.z = v.x * m[2][0] + v.y * m[2][1] + v.z * m[2][2];
	return o;
}

inline vec3 inv_transform( const float (*m)[3], const vec3 &v )
{
	vec3 o;
	o.x = v.x * m[0][0] + v.y * m[1][0] + v.z * m[2][0];
	o.y = v.x * m[0][1] + v.y * m[1][1] + v.z * m[2][1];
	o.z = v.x * m[0][2] + v.y * m[1][2] + v.z * m[2][2];
	return o;
}


static int ReadInt( FILE *f )
{
	int d;
	fscanf( f, "%d", &d );
	return d;
}

static double ReadFloat( FILE *f )
{
	double d;
	fscanf( f, "%lf", &d );
	return d;
}

static unsigned ReadHex( FILE *f )
{
	unsigned h = 0;
	fscanf( f, "%x", &h );
	return h;
}

static char *ReadStr( FILE *f )
{
	enum { strcount = 4 };
	static char str[strcount][256];
	static int whichstr = 0;
	
	whichstr = (whichstr + 1) & (strcount-1);
	
	int c;
	for (;;) {
		c = getc(f);
		if (c == EOF || isgraph(c)) break;
	}
	
	int len = 0;
	if (c != EOF) {
		for (;;) {
			str[whichstr][len++] = c;
			if (len > 254) break;
			c = getc(f);
			if (c == EOF) break;
			if (!isgraph(c)) break;
		}
	}
	
	str[whichstr][len] = 0;
	return str[whichstr];
}

static char *ReadToEOL( FILE *f )
{
	enum { strcount = 4 };
	static char str[strcount][256];
	static int whichstr = 0;
	
	whichstr = (whichstr + 1) & (strcount-1);
	
	int c;
	for (;;) {
		c = getc(f);
		if (c == EOF || isgraph(c) || c == '\n' || c == '\r') break;
	}
	
	int len = 0;
	for (;;) {
		if (c == '\n' || c == '\r' || c == EOF) break;
		str[whichstr][len++] = c;
		if (len > 254) break;
		c = getc(f);
	}
	
	str[whichstr][len] = 0;
	int next = getc(f);
	if (next != EOF && (next != '\n' && next != '\r' || next == c)) {
		ungetc( next, f );
	}
	
	return str[whichstr];
}

static bool MatchStr( FILE *f, const char *str )
{
	for (;;) {
		char *s = ReadStr(f);
		if (!s[0]) return false;
		if (!strcmp( s, str )) return true;
	}
}


char *stristr(const char *Input, const char *SubStr)
{
	int Temp;
	Temp = ((byte *)Input)[0];		/* Get the first character */
	if (Temp) {						/* Do I even bother? */
		do {
			int i;
			int Temp2;
			i = 0;					/* Init the index */
			do {
				Temp2 = ((byte *)SubStr)[i];	/* Get the first char of the test string */
				if (!Temp2) {					/* Match? */
					return (char *)Input;		/* I matched here! */
				}
				Temp = ((byte *)Input)[i];		/* Get the source string */
				++i;							/* Ack the char */
				if (Temp2>='A' && Temp2<='Z') {	/* Convert to lower case */
					Temp2 += 32;
				}
				if (Temp>='A' && Temp<='Z') {	/* Convert to lower case */
					Temp += 32;
				}
			} while (Temp == Temp2);			/* Match? */
			++Input;							/* Next main string char */
			Temp = ((byte *)Input)[0];			/* Next entry */
		} while (Temp);							/* Source string still ok? */
	}
	return 0;		/* No string match */
}



void read_skl( FILE *f )
{
	int i, j, k, m, n;
	MatchStr( f, "SKELETON" );
	MatchStr( f, "VERSION" );
	int version = ReadInt(f);
	
	MatchStr( f, "NUMMATERIALS" );
	int mat_count = ReadInt(f);
	for (i = 0; i < mat_count; ++i) {
		MatchStr( f, "MATERIAL" );
		int m_no = ReadInt(f);
		ReadToEOL( f );
	}
	
	
	MatchStr( f, "NUMBONES" );
	bone_count = ReadInt(f);
	for (i = 0; i < MAXBONES; ++i) {
		bones[i].number = -1;
		bones[i].used_count = 0;
		bones[i].tagbone = false;
	}
	if (bone_count > MAXBONES) bone_count = MAXBONES;
	for (i = 0; i < bone_count; ++i) {
		MatchStr( f, "BONE" );
		int b_no = ReadInt(f);
		bones[b_no].number = b_no;
		bones[b_no].parent = ReadInt(f);
		strcpy( bones[b_no].name, ReadToEOL(f) );
		const char *n = bones[b_no].name;
		if (stristr( n, "tag_" ) || stristr( n, "_tag" ) || stristr( n, "origin" ) || stristr( n, "attach" )) {
			bones[i].tagbone = true;
		}
	}
	for (i = 0; i < MAXVERTS; ++i) {
		verts[i].group_count = 0;
		verts[i].number = -1;
	}
	
	
	MatchStr( f, "NUMVERTS" );
	vert_count = ReadInt(f);
	if (vert_count > MAXVERTS) vert_count = MAXVERTS;
	for (i = 0; i < vert_count; ++i) {
		MatchStr( f, "VERT" );
		int v_no = ReadInt(f);
		if (version == 1)
		{
			MatchStr( f, "NORMAL" );
			verts[v_no].norm.x = ReadFloat(f);
			verts[v_no].norm.y = ReadFloat(f);
			verts[v_no].norm.z = ReadFloat(f);
		}
		MatchStr( f, "BONES" );
		int in_weight_count = ReadInt(f);
		int out_weight_count = 0;
		for (j = 0; j < in_weight_count; ++j) {
			MatchStr(f,"BONE");
			int in_b = ReadInt(f);
			float in_w = ReadFloat(f);
			float in_x = ReadFloat(f);
			float in_y = ReadFloat(f);
			float in_z = ReadFloat(f);
			if (in_w > 0.0f && !bones[in_b].tagbone) {
				for (k = 0; k < out_weight_count; ++k) {
					if (verts[v_no].weights[k].bone == in_b) {
						verts[v_no].weights[k].pos =
							(verts[v_no].weights[k].w * verts[v_no].weights[k].pos +
							 in_w * vec3(in_x, in_y, in_z)) / (verts[v_no].weights[k].w + in_w);
						verts[v_no].weights[k].w += in_w;
						break;
					}
				}
				if (k == out_weight_count) {
					++out_weight_count;
					assert( out_weight_count <= MAXVERTWEIGHTS );
					verts[v_no].weights[k].bone = in_b;
					verts[v_no].weights[k].w = in_w;
					verts[v_no].weights[k].pos.x = in_x;
					verts[v_no].weights[k].pos.y = in_y;
					verts[v_no].weights[k].pos.z = in_z;
				}
			}
		}
		verts[v_no].weight_count = out_weight_count;
		if (out_weight_count)
		{
			skl_vert &vi = verts[v_no];
			for (j = 0; j <= i; ++j)
			{
				skl_vert &vj = verts[j];
				if (vj.weight_count != vi.weight_count) goto next_samepos_search;
				for (k = 0; k < vj.weight_count; ++k)
				{
					for (m = 0; m < vi.weight_count; ++m)
					{
						if (vi.weights[m].bone != vj.weights[k].bone) continue;
						if (vi.weights[m].w != vj.weights[k].w) goto next_samepos_search;
						if (vi.weights[m].pos.x != vj.weights[k].pos.x) goto next_samepos_search;
						if (vi.weights[m].pos.y != vj.weights[k].pos.y) goto next_samepos_search;
						if (vi.weights[m].pos.z != vj.weights[k].pos.z) goto next_samepos_search;
						goto next_sameweight_search;
					}
					goto next_samepos_search;
			next_sameweight_search:;
				}
				vi.superposition_group = j;
				if (i == j) vi.number = v_no;
				
				break;
		next_samepos_search:;
			}
		}
		else
		{
			verts[v_no].superposition_group = -1;
			verts[v_no].number = i;
		}
	}
	
	
	MatchStr( f, "NUMFACES" );
	int in_tri_count = ReadInt(f);
	tri_count = 0;
	for (i = 0; i < in_tri_count; ++i) {
		MatchStr( f, "TRI" );
		int surface = ReadInt(f);
		for (j = 0; j < 3; ++j) {
			int v = ReadInt(f);
			float s = ReadFloat(f);
			float t = ReadFloat(f);
			v = verts[v].superposition_group;
			tris[tri_count].v[j] = v;
			tris[tri_count].s[j] = s;
			tris[tri_count].t[j] = t;
		}
		unsigned groups = (version == 1 ? 1 : ReadHex(f));
		if (tris[tri_count].v[0] == -1 || tris[tri_count].v[1] == -1 || tris[tri_count].v[2] == -1 ||
			tris[tri_count].v[0] == tris[tri_count].v[1] ||
			tris[tri_count].v[0] == tris[tri_count].v[2] ||
			tris[tri_count].v[1] == tris[tri_count].v[2]) continue;
		
		for (j = 0; j < 3; ++j) {
			int v = tris[tri_count].v[j];
			assert( verts[v].group_count < MAXVGROUPS );
			verts[v].groups[verts[v].group_count].group_mask = groups;
			verts[v].groups[verts[v].group_count].tcount = 1;
			verts[v].groups[verts[v].group_count].tri[0] = tri_count;
			++verts[v].group_count;
			bool need_remerge;
			do {
				need_remerge = false;
				k = 0;
				do {
					for (m = k + 1; m < verts[v].group_count; ++m)
					{
						if (verts[v].groups[k].group_mask & verts[v].groups[m].group_mask)
						{
							assert( verts[v].groups[k].tcount + verts[v].groups[m].tcount <= MAXVTRI );
							verts[v].groups[k].group_mask |= verts[v].groups[m].group_mask;
							for (n = 0; n < verts[v].groups[m].tcount; ++n)
							{
								verts[v].groups[k].tri[verts[v].groups[k].tcount++] = verts[v].groups[m].tri[n];
							}
							memmove( &(verts[v].groups[m]), &(verts[v].groups[m+1]), (verts[v].group_count - m - 1) * sizeof(skl_vertsmooth) );
							--verts[v].group_count;
							need_remerge = true;
						}
					}
					++k;
				} while (k < verts[v].group_count);
			} while (need_remerge);
		}
		
		tris[tri_count].npatch_fill_only = false;
		
		++tri_count;
	}
	
	MatchStr( f, "FRAMERATE" );
	frame_rate = ReadFloat(f);
	MatchStr( f, "NUMFRAMES" );
	frame_count = ReadInt(f);
	for (i = 0; i < frame_count; ++i) {
		MatchStr( f, "FRAME" );
		int f_no = ReadInt(f);
		for (j = 0; j < bone_count; ++j) {
			MatchStr( f, "BONE" );
			int fb_no = ReadInt(f);
			
			MatchStr( f, "OFFSET" );
			frames[f_no][fb_no].pos.x = ReadFloat(f);
			frames[f_no][fb_no].pos.y = ReadFloat(f);
			frames[f_no][fb_no].pos.z = ReadFloat(f);
			
			MatchStr( f, "X" );
			frames[f_no][fb_no].m[0][0] = ReadFloat(f);
			frames[f_no][fb_no].m[1][0] = ReadFloat(f);
			frames[f_no][fb_no].m[2][0] = ReadFloat(f);
			
			MatchStr( f, "Y" );
			frames[f_no][fb_no].m[0][1] = ReadFloat(f);
			frames[f_no][fb_no].m[1][1] = ReadFloat(f);
			frames[f_no][fb_no].m[2][1] = ReadFloat(f);
			
			MatchStr( f, "Z" );
			frames[f_no][fb_no].m[0][2] = ReadFloat(f);
			frames[f_no][fb_no].m[1][2] = ReadFloat(f);
			frames[f_no][fb_no].m[2][2] = ReadFloat(f);
		}
	}
	
	MatchStr( f, "END" );
}


static void normalize_weights( int v )
{
	int i;
	
	float total = 0.0f;
	for (i = 0; i < verts[v].weight_count; ++i) {
		float w = verts[v].weights[i].w;
		if (!(w > 0.0f)) {
			memcpy( &verts[v].weights[i], &verts[v].weights[verts[v].weight_count-1], sizeof(skl_weight) );
			--verts[v].weight_count;
			--i;
		} else {
			total += w;
		}
	}
	
	if (!(total > 0.0f)) return;
	
	total = 1.0f / total;
	for (i = 0; i < verts[v].weight_count; ++i) {
		verts[v].weights[i].w *= total;
	}
}

#if 0
void compute_shadows()
{
	int i,j;
	float ncount[MAXBONES], fcount[MAXBONES];
	
	for (i = 0; i < bone_count; ++i) {
		ncount[i] = 0.0f;
		fcount[i] = 0.0f;
		bones[i].shadow_width_near = 0.0f;
		bones[i].shadow_width_far = 0.0f;
		bones[i].shadow_near = 100000.0f;
		bones[i].shadow_far = -100000.0f;
	}
	
	for (i = 0; i < vert_count; ++i) {
		if (verts[i].used_count > 0) {
			for (j = 0; j < verts[i].weight_count; ++j) {
				vec3 &o = verts[i].weights[j].pos;
				float l = o.x;
				skl_bone &b = bones[verts[i].weights[j].bone];
				if (l < b.shadow_near) b.shadow_near = l;
				if (l > b.shadow_far) b.shadow_far = l;
			}
		}
	}
	
	for (i = 0; i < vert_count; ++i) {
		if (verts[i].used_count > 0) {
			for (j = 0; j < verts[i].weight_count; ++j) {
				vec3 &o = verts[i].weights[j].pos;
				float w = sqrtf((o.y * o.y) + (o.z * o.z));
				float l = o.x;
				skl_bone &b = bones[verts[i].weights[j].bone];
				l = (l - b.shadow_near) / (b.shadow_far - b.shadow_near);
				b.shadow_width_far += l * w;
				b.shadow_width_near += (1.0f - l) * w;
				ncount[verts[i].weights[j].bone] += (1.0f - l);
				fcount[verts[i].weights[j].bone] += l;
			}
		}
	}
	
	for (i = 0; i < bone_count; ++i) {
		if (ncount[i] > 0.0f) {
			bones[i].shadow_width_near /= ncount[i];
		}
		if (fcount[i] > 0.0f) {
			bones[i].shadow_width_far /= fcount[i];
		}
	}
}
#endif

inline void include_vertex_in_bounds( const vec3 &in_v, int bone )
{
	vec3 v = inv_transform( frames[0][bone].m, in_v - frames[0][bone].pos );
	for (int i = 0; i < 3; ++i)
	{
		if (v[i] < bones[bone].bounds[i][0]) bones[bone].bounds[i][0] = v[i];
		if (v[i] > bones[bone].bounds[i][1]) bones[bone].bounds[i][1] = v[i];
	}
}

void compute_bone_bounds()
{
	int i, j;
	
	for (i = 0; i < bone_count; ++i)
	{
		for (j = 0; j < 3; ++j)
		{
			bones[i].bounds[j][0] = 100000000000.0f;
			bones[i].bounds[j][1] = -100000000000.0f;
		}
	}
	
	for (i = 0; i < tri_count; ++i)
	{
		skl_tri &t = tris[i];
		for (int tv0 = 0, tv1 = 1, tv2 = 2; tv0 < 3; tv1 = tv2, tv2 = tv0++)
		{
			vec3 v0 = verts[tris[i].v[tv0]].pos;
			vec3 v01 = 0.5f * (verts[tris[i].v[tv0]].pos + verts[tris[i].v[tv1]].pos);
			vec3 v02 = 0.5f * (verts[tris[i].v[tv0]].pos + verts[tris[i].v[tv2]].pos);
			for (j = 0; j < verts[tv0].weight_count; ++j)
			{
				include_vertex_in_bounds( v0, verts[tris[i].v[tv0]].weights[j].bone );
				include_vertex_in_bounds( v01, verts[tris[i].v[tv0]].weights[j].bone );
				include_vertex_in_bounds( v02, verts[tris[i].v[tv0]].weights[j].bone );
			}
		}
	}
	
	for (i = 0; i < bone_count; ++i)
	{
		for (j = 0; j < 3; ++j)
		{
			if (bones[i].bounds[j][0] > bones[i].bounds[j][1])
			{
				bones[i].bounds[j][0] = bones[i].bounds[j][1] = 0.0f;
			}
		}
	}
}


void compact_mesh()
{
	int i, j;
	bool changes;
	
	do {
		changes = false;
		
		for (i = 0; i < vert_count; ++i) {
			verts[i].used_count = 0;
		}
		
		for (i = 0; i < tri_count; ++i) {
			for (j = 0; j < 3; ++j) {
				int v = tris[i].v[j];
				verts[v].used_by[verts[v].used_count++] = i;
				assert( verts[v].used_count <= MAXVTRI );
			}
		}
		
		int v_index = 0;
		for (i = 0; i < vert_count; ++i) {
			verts[i].number = -1;
			if (verts[i].used_count > 0) {
				if (0 && verts[i].weight_count > 1) {
					int hiweight = 0;
					for (j = 1; j < verts[i].weight_count; ++j) {
						if (verts[i].weights[j].w > verts[i].weights[hiweight].w) {
							verts[i].weights[hiweight].w = 0.0f;
							hiweight = j;
						} else {
							verts[i].weights[j].w = 0.0f;
						}
					}
					verts[i].weights[hiweight].w = 1.0f;
				}
				normalize_weights(i);
				for (j = 0; j < verts[i].weight_count; ++j) {
					if (verts[i].weights[j].w < 0.025f) {
						verts[i].weights[j].w = 0.0f;
						changes = true;
					}
				}
				if (verts[i].weight_count > 0) {
					verts[i].number = v_index++;
				} else {
					verts[i].used_count = 0;
					changes = true;
				}
			}
		}
		
		
		for (i = 0; i < tri_count; ++i) {
			int v0 = verts[tris[i].v[0]].number;
			int v1 = verts[tris[i].v[1]].number;
			int v2 = verts[tris[i].v[2]].number;
			if (v0 < 0 || v0 >= v_index || v1 < 0 || v1 >= v_index || v2 < 0 || v2 >= v_index || v0 == v1 || v0 == v2 || v1 == v2) {
				memcpy( &tris[i], &tris[tri_count-1], sizeof(skl_tri) );
				--i;
				--tri_count;
				changes = true;
			}
		}
	} while (changes);
}


void compact_bones()
{
	int i, j;
	bool changes;
	
	for (i = 0; i < bone_count; ++i) {
		bones[i].used_count = bones[i].tagbone ? 1 : 0;
	}
	for (i = 0; i < vert_count; ++i) {
		if (verts[i].number >= 0) {
			for (j = 0; j < verts[i].weight_count; ++j) {
				bones[verts[i].weights[j].bone].used_count += 1;
			}
		}
	}
	for (i = 0; i < bone_count; ++i) {
		if (bones[i].parent >= 0) {
			bones[bones[i].parent].used_count += 1;
		}
	}
	
	do {
		changes = false;
		
		used_bone_count = 0;
		for (i = 0; i < bone_count; ++i) {
			if (bones[i].used_count <= 0) {
				bones[i].number = -1;
				if (bones[i].parent >= 0) {
					bones[bones[i].parent].used_count -= 1;
					bones[i].parent = -1;
					changes = true;
				}
			} else {
				bones[i].number = used_bone_count++;
			}
		}
	} while (changes);
}


int add_weight_to_bone( int bone_index, float x, float y, float z, float w )
{
	skl_bone *b = &bones[bone_index];
	float dist_in = x*x + y*y + z*z;
	int i;
#if 0
	for (i = 0; i < b->weight_count; ++i)
	{
		if (x != b->weight_data[i][0]) continue;
		if (y != b->weight_data[i][1]) continue;
		if (z != b->weight_data[i][2]) continue;
		if (w != b->weight_data[i][3]) continue;
#if 0
		if (w > 0.0f)
		{
			if (!(b->weight_data[i][3] > 0.0f)) continue;
			if (fabs( w - b->weight_data[i][3] ) > 0.0005f) continue;
		}
		else
		{
			if (b->weight_data[i][3] > 0.0f) continue;
		}
		float dx = x - b->weight_data[i][0];
		float dy = y - b->weight_data[i][1];
		float dz = z - b->weight_data[i][2];
		float diff = sqrtf(dx*dx + dy*dy + dz*dz);
		float dist_test = sqrtf(b->weight_data[i][0]*b->weight_data[i][0] + b->weight_data[i][1]*b->weight_data[i][1] + b->weight_data[i][2]*b->weight_data[i][2]);
		if (diff > 0.0005f * (dist_in + dist_test)) continue;
#endif
		return i;
	}
#endif
	i = b->weight_count++;
	b->weight_data[i][0] = x;
	b->weight_data[i][1] = y;
	b->weight_data[i][2] = z;
	b->weight_data[i][3] = w;
	return i;
}


static void compact_weights( const short vert_order[], int max_vertices )
{
	int i, j;
	
	for (i = 0; i < bone_count; ++i) {
		bones[i].weight_count = 0;
	}
	for (i = 0; i < max_vertices; ++i) {
		int v = vert_order[i];
		for (j = 0; j < verts[v].weight_count; ++j) {
			skl_weight *w = &verts[v].weights[j];
			w->pos_index = add_weight_to_bone( w->bone, w->pos.x * w->w, w->pos.y * w->w, w->pos.z * w->w, w->w );
		}
		for (j = 0; j < verts[v].weight_count; ++j) {
			skl_weight *w = &verts[v].weights[j];
			w->norm_index = add_weight_to_bone( w->bone, w->norm.x * w->w, w->norm.y * w->w, w->norm.z * w->w, 0.0f );
		}
	}
}


void set_skl_to_frame( int f, bool normal )
{
	int i,j,k;
	if (normal) {
		for (i = 0; i < vert_count; ++i) {
			if (verts[i].number > -1) {
				vec3 p( 0.0f, 0.0f, 0.0f );
				vec3 n( 0.0f, 0.0f, 0.0f );
				for (j = 0; j < verts[i].weight_count; ++j) {
					skl_bonepos *b = frames[f] + verts[i].weights[j].bone;
					p += verts[i].weights[j].w * (b->pos + transform( b->m, verts[i].weights[j].pos ));
					n += verts[i].weights[j].w * transform( b->m, verts[i].weights[j].norm );
				}
				verts[i].pos = p;
				verts[i].norm = normalized(n);
			}
		}
	} else {
		for (i = 0; i < vert_count; ++i) {
			if (verts[i].number > -1) {
				vec3 p( 0.0f, 0.0f, 0.0f );
				for (j = 0; j < verts[i].weight_count; ++j) {
					skl_bonepos *b = frames[f] + verts[i].weights[j].bone;
					p += verts[i].weights[j].w * (b->pos + transform( b->m, verts[i].weights[j].pos ));
				}
				verts[i].pos = p;
			}
		}
	}
	
	for (i = 0; i < bone_count; ++i) {
		int parent = bones[i].parent;
		if (parent >= 0) {
			float (*bm)[3] = bones[i].m;
			const float (*fm)[3] = frames[f][i].m;
			const float (*pm)[3] = bones[parent].m;
			const float (*fpm)[3] = frames[f][parent].m;
			vec3 off = frames[f][i].pos - frames[f][parent].pos;
			bones[i].offset = inv_transform( fpm, off );
			//vec3 test = transform( fpm, bones[i].offset );
			float trans[3][3];
			TransposeMat( trans, fpm );
			MatMult( bm, trans, fm );
		} else {
			bones[i].offset = frames[f][i].pos;
			for (j = 0; j < 3; ++j) {
				for (k = 0; k < 3; ++k) {
					bones[i].m[j][k] = frames[f][i].m[j][k];
				}
			}
		}
		MatToQuat( bones[i].q, bones[i].m );
	}
}


void divide_smoothing()
{
	check_smooth_tri();
	for (int i = 0; i < vert_count; ++i)
	{
		while (verts[i].group_count > 1)
		{
			memcpy( &(verts[vert_count]), &(verts[i]), sizeof(skl_vert) );
			verts[i].group_count -= 1;
			verts[vert_count].group_count = 1;
			memcpy( &(verts[vert_count].groups[0]), &(verts[vert_count].groups[verts[i].group_count]), sizeof(skl_vertsmooth) );
			for (int j = 0; j < verts[vert_count].groups[0].tcount; ++j)
			{
				int t = verts[vert_count].groups[0].tri[j];
				for (int k = 0; k < 3; ++k)
				{
					if (tris[t].v[k] == i) tris[t].v[k] = vert_count;
				}
			}
			++vert_count;
			check_smooth_tri();
		}
		check_smooth_tri();
	}
}


void fix_normals( int init_frame )
{
	int i, j;
	divide_smoothing();
	set_skl_to_frame( init_frame, false );
	
	for (i = 0; i < vert_count; ++i) {
		verts[i].norm = vec3( 0, 0, 0 );
		if (verts[i].group_count != 1) continue;
		for (j = 0; j < verts[i].groups[0].tcount; ++j)
		{
			skl_tri &t = tris[verts[i].groups[0].tri[j]];
			verts[i].norm += cross( verts[t.v[1]].pos - verts[t.v[0]].pos, verts[t.v[2]].pos - verts[t.v[0]].pos );
		}
		verts[i].norm = normalized( verts[i].norm );
		for (j = 0; j < verts[i].weight_count; ++j)
		{
			verts[i].weights[j].norm = inv_transform( frames[init_frame][verts[i].weights[j].bone].m, verts[i].norm );
		}
	}
}


void fill_npatch_cracks()
{
	struct edge_info {
		short v0, v1;
		short g0, g1;
		float s0, s1, t0, t1;
	};
	edge_info edges[MAXTRIS*3];
	int edge_count = 0;
	int i, j, k, m;
	skl_tri *t;
	int old_tri_count = tri_count;
	for (i = 0; i < old_tri_count; ++i)
	{
		for (j = 0, m = 2; j < 3; m = j++)
		{
			int v0 = tris[i].v[j];
			int v1 = tris[i].v[m];
			int g0 = verts[v0].superposition_group;
			int g1 = verts[v1].superposition_group;
			float s0 = tris[i].s[j];
			float s1 = tris[i].s[m];
			float t0 = tris[i].t[j];
			float t1 = tris[i].t[m];
			for (k = 0; k < edge_count; ++k)
			{
				if (edges[k].g0 != g1 || edges[k].g1 != g0) continue;
				if (edges[k].v0 == v1)
				{
					if (edges[k].v1 == v0) goto next_edge;
					
					verts[v0].groups[0].tri[verts[v0].groups[0].tcount++] = tri_count;
					verts[v1].groups[0].tri[verts[v1].groups[0].tcount++] = tri_count;
					verts[edges[k].v1].groups[0].tri[verts[edges[k].v1].groups[0].tcount++] = tri_count;
					
					t = tris + tri_count++;
					
					t->npatch_fill_only = true;
					
					t->v[0] = v1;
					t->v[1] = v0;
					t->v[2] = edges[k].v1;
					
					t->s[0] = s1;
					t->s[1] = s0;
					t->s[2] = edges[k].s1;
					
					t->t[0] = t1;
					t->t[1] = t0;
					t->t[2] = edges[k].t1;
					
					check_smooth_tri();
					
					goto next_edge;
				}
				else
				{
					if (edges[k].v1 == v0)
					{
						verts[v0].groups[0].tri[verts[v0].groups[0].tcount++] = tri_count;
						verts[v1].groups[0].tri[verts[v1].groups[0].tcount++] = tri_count;
						verts[edges[k].v0].groups[0].tri[verts[edges[k].v0].groups[0].tcount++] = tri_count;
						
						t = tris + tri_count++;
						
						t->npatch_fill_only = true;
						
						t->v[0] = v1;
						t->v[1] = v0;
						t->v[2] = edges[k].v0;
						
						t->s[0] = s1;
						t->s[1] = s0;
						t->s[2] = edges[k].s0;
						
						t->t[0] = t1;
						t->t[1] = t0;
						t->t[2] = edges[k].t0;
						
						check_smooth_tri();
						
						goto next_edge;
					}
					else
					{
						verts[v0].groups[0].tri[verts[v0].groups[0].tcount++] = tri_count;
						verts[v1].groups[0].tri[verts[v1].groups[0].tcount++] = tri_count;
						verts[edges[k].v1].groups[0].tri[verts[edges[k].v1].groups[0].tcount++] = tri_count;
						
						t = tris + tri_count++;
						
						t->npatch_fill_only = true;
						
						t->v[0] = v1;
						t->v[1] = v0;
						t->v[2] = edges[k].v1;
						
						t->s[0] = s1;
						t->s[1] = s0;
						t->s[2] = edges[k].s1;
						
						t->t[0] = t1;
						t->t[1] = t0;
						t->t[2] = edges[k].t1;
						
						
						verts[v1].groups[0].tri[verts[v1].groups[0].tcount++] = tri_count;
						verts[edges[k].v0].groups[0].tri[verts[edges[k].v0].groups[0].tcount++] = tri_count;
						verts[edges[k].v1].groups[0].tri[verts[edges[k].v1].groups[0].tcount++] = tri_count;
						
						t = tris + tri_count++;
						
						t->npatch_fill_only = true;
						
						t->v[0] = v1;
						t->v[1] = edges[k].v1;
						t->v[2] = edges[k].v0;
						
						t->s[0] = s1;
						t->s[1] = edges[k].s1;
						t->s[2] = edges[k].s0;
						
						t->t[0] = t1;
						t->t[1] = edges[k].t1;
						t->t[2] = edges[k].t0;
						
						check_smooth_tri();
						
						goto next_edge;
					}
				}
			}
			
			edges[edge_count].v0 = v0;
			edges[edge_count].v1 = v1;
			edges[edge_count].g0 = g0;
			edges[edge_count].g1 = g1;
			edges[edge_count].s0 = s0;
			edges[edge_count].s1 = s1;
			edges[edge_count].t0 = t0;
			edges[edge_count].t1 = t1;
			++edge_count;
			
	next_edge:;
		}
	}
}


void divide_st()
{
	int i, j, k;
	const float st_epsilon = 1.0f / 2048.0f;
	
	for (i = 0; i < vert_count; ++i)
	{
		if (verts[i].group_count != 1) continue;
		bool split = false;
		skl_tri *t = &(tris[verts[i].groups[0].tri[0]]);
		for (j = 0; j < 3; ++j)
		{
			if (t->v[j] == i)
			{
				verts[i].s = t->s[j];
				verts[i].t = t->t[j];
				break;
			}
		}
		assert( j < 3 );
		for (j = 1; j < verts[i].groups[0].tcount; ++j)
		{
			t = &(tris[verts[i].groups[0].tri[j]]);
			for (k = 0; k < 3; ++k)
			{
				if (t->v[k] == i)
				{
					if (fabs(verts[i].s - t->s[k]) > st_epsilon || fabs(verts[i].t - t->t[k]) > st_epsilon)
					{
						if (!split)
						{
							memcpy( &(verts[vert_count]), &(verts[i]), sizeof(skl_vert) );
							verts[vert_count].groups[0].tcount = 0;
							split = true;
						}
						verts[vert_count].groups[0].tri[verts[vert_count].groups[0].tcount++] = verts[i].groups[0].tri[j];
						t->v[k] = vert_count;
						memmove( &(verts[i].groups[0].tri[j]), &(verts[i].groups[0].tri[j+1]), sizeof(short) * (verts[i].groups[0].tcount - j - 1) );
						--j;
						--verts[i].groups[0].tcount;
					}
					break;
				}
			}
			assert( k < 3 );
		}
		if (split)
		{
			++vert_count;
		}
		check_smooth_tri();
	}
}


inline int collapsed( int v )
{
	for (;;) {
		int c = verts[v].collapse_to;
		if (c < 0) return v;
		v = c;
	}
}


static int adjacent_list( int v, short *out )
{
	int count = 0;
	for (int i = 0; i < verts[v].used_count; ++i) {
		skl_tri *t = tris + verts[v].used_by[i];
		for (int j = 0; j < 3; ++j) {
			int nv = collapsed(t->v[j]);
			if (verts[nv].superposition_group != verts[v].superposition_group) {
				for (int k = 0; k < count; ++k) {
					if (out[k] == nv) goto skip_vert;
				}
				out[count++] = nv;
			}
	skip_vert:;
		}
	}
	
	return count;
}

static int adjacent_in_same_group( int v, int targ )
{
	int g = verts[targ].superposition_group;
	assert( verts[v].superposition_group != g );
	
	for (int i = 0; i < verts[v].used_count; ++i) {
		skl_tri *t = tris + verts[v].used_by[i];
		for (int j = 0; j < 3; ++j) {
			int nv = collapsed(t->v[j]);
			if (verts[nv].superposition_group == g) return nv;
		}
	}
	
	return targ;
}

#if 1
static int is_on_silhouette( int v, short *group_list )
{
	short other[MAXVTRI*2];
	vec3 other_norm[MAXVTRI*2];
	int other_count = 0;
	
	for (int scan_v = verts[v].superposition_group; scan_v != -1; scan_v = verts[scan_v].next_in_superposition_group)
	{
		short same[MAXVTRI*2];
		vec3 same_norm[MAXVTRI*2];
		int same_count = 0;
		int i, j, k;
		
		for (i = 0; i < verts[scan_v].used_count; ++i) {
			skl_tri *t = tris + verts[scan_v].used_by[i];
			for (j = 0; j < 3; ++j) {
				int nv = collapsed(t->v[j]);
				if (verts[nv].superposition_group != verts[v].superposition_group) {
					//nv = verts[nv].superposition_group;
					for (k = 0; k < same_count; ++k) {
						if (same[k] == nv) {
							if (dot( t->norm, same_norm[k] ) > -0.85f)
							{
								same[k] = same[--same_count];
								same_norm[k] = same_norm[same_count];
							}
							goto skip_vert;
						}
					}
					same_norm[same_count] = t->norm;
					same[same_count++] = nv;
				}
		skip_vert:;
			}
		}
		
		for (i = 0; i < same_count; ++i)
		{
			int group = verts[same[i]].superposition_group;
			for (j = 0; j < other_count; ++j)
			{
				if (other[j] == group)
				{
					if (dot(same_norm[i], other_norm[j]) > -0.85f)
					{
						other[j] = other[--other_count];
						other_norm[j] = other_norm[other_count];
					}
					same[i] = same[--same_count];
					same_norm[i] = same_norm[same_count];
					--i;
					goto skip_vert_2;
				}
			}
		skip_vert_2:;
		}
		
		for (i = 0; i < same_count; ++i)
		{
			other_norm[other_count] = same_norm[i];
			other[other_count++] = verts[same[i]].superposition_group;
		}
	}
	
	if (group_list)
	{
		memcpy( group_list, other, other_count * sizeof(other[0]) );
	}
	
	return other_count;
}

inline float dist_5d( int v0, int v1 )
{
	float dx = verts[v0].pos.x - verts[v1].pos.x;
	float dy = verts[v0].pos.y - verts[v1].pos.y;
	float dz = verts[v0].pos.z - verts[v1].pos.z;
	float ds = verts[v0].s - verts[v1].s;
	float dt = verts[v0].t - verts[v1].t;
	return sqrt( dx*dx + dy*dy + dz*dz + ds*ds + dt*dt );
}

static float collapse_error( int from, int to )
{
	float error = 0.0f;
	vec3 edgevec = verts[to].pos - verts[from].pos;
	int i;
	int scan_from;
	
	assert( verts[from].superposition_group != verts[to].superposition_group );
	
//	if (from == 64 && to == 63) enter_debugger();
	
	short s_edges[MAXVTRI*2];
	int s_edge_count = is_on_silhouette( from, s_edges );
	
	if (s_edge_count > 0)
	{
		if (s_edge_count != 2) return NOCOLLAPSE_ERROR;
		if (verts[to].superposition_group != s_edges[0] && verts[to].superposition_group != s_edges[1]) return NOCOLLAPSE_ERROR;
	#if 0
		if (verts[to].superposition_group == s_edges[0]) {
			s_edges[0] = to;
			s_edges[1] = adjacent_in_same_group( from, s_edges[1] );
		} else if (verts[to].superposition_group == s_edges[1]) {
			s_edges[0] = adjacent_in_same_group( from, s_edges[0] );
			s_edges[1] = to;
		} else {
			return NOCOLLAPSE_ERROR;
		}
	#endif
		
		int g_count = 0;
		for (scan_from = verts[from].superposition_group; scan_from != -1; scan_from = verts[scan_from].next_in_superposition_group)
		{
			int v0 = adjacent_in_same_group( scan_from, s_edges[0] );
			int v1 = adjacent_in_same_group( scan_from, s_edges[1] );
			error += dist_5d( scan_from, v0 ) + dist_5d( scan_from, v1 ) - dist_5d( v0, v1 );
			++g_count;
		}
		error = error * 40.0f / g_count;
	}
	else
	{
		for (scan_from = verts[from].superposition_group; scan_from != -1; scan_from = verts[scan_from].next_in_superposition_group)
		{
			for (i = 0; i < verts[scan_from].used_count; ++i) {
				skl_tri *t = tris + verts[scan_from].used_by[i];
				float height = fabs( dot( t->norm, verts[scan_from].pos ) - dot( t->norm, verts[to].pos ) );
				float volume = 0.5f * height * t->area;
				error += volume;
			}
			for (i = 0; i < vert_count; ++i) {
				if (verts[i].collapse_to == scan_from && verts[i].used_count > 0) {
					error += collapse_error( i, to );
				}
			}
		}
	}
	
	return error;
}

#else

static bool is_on_silhouette( int v )
{
	short out[MAXVTRI*2];
	int count = 0;
	
	for (int i = 0; i < verts[v].used_count; ++i) {
		skl_tri *t = tris + verts[v].used_by[i];
		for (int j = 0; j < 3; ++j) {
			int nv = collapsed(t->v[j]);
			if (nv != v) {
				for (int k = 0; k < count; ++k) {
					if (out[k] == nv) {
						out[k] = out[--count];
						goto skip_vert;
					}
				}
				out[count++] = nv;
			}
	skip_vert:;
		}
	}
	
	return count;
}

static float collapse_error( int from, int to )
{
	float error = 0.0f;
	vec3 edgevec = verts[to].pos - verts[from].pos;
	for (int i = 0; i < verts[from].used_count; ++i) {
		skl_tri *t = tris + verts[from].used_by[i];
		float height = fabs( dot( t->norm, verts[from].pos ) - dot( t->norm, verts[to].pos ) );
		float volume = 0.5f * height * t->area;
		error += volume;
	}
	for (int i = 0; i < vert_count; ++i) {
		if (verts[i].used_count > 0 && verts[i].collapse_to == from) {
			error += collapse_error( i, to );
		}
	}
	return error;
}
#endif


void build_collapse_order()
{
	collapse_count = 0;
	used_vert_count = 0;
	irreducible_vert_count = 0;
	
	short *l_collapse_order = collapse_order;
	int *l_collapse_count = &collapse_count;
	
	int i, j, v0, v1, v2;
	
	for (i = 0; i < vert_count; ++i)
	{
		verts[i].used_count = 0;
	}
	for (i = 0; i < tri_count; ++i) {
		if (tris[i].npatch_fill_only)
		{
			tris[i].collapse_at = 0;
		}
		else
		{
			tris[i].collapse_at = MAXVERTS;
			v0 = tris[i].v[0];
			v1 = tris[i].v[1];
			v2 = tris[i].v[2];
			verts[v0].used_by[verts[v0].used_count++] = i;
			verts[v1].used_by[verts[v1].used_count++] = i;
			verts[v2].used_by[verts[v2].used_count++] = i;
		}
	}
	
	for (i = 0; i < vert_count; ++i) {
		verts[i].collapse_to = -2;
		if (verts[i].used_count > 0) {
			verts[i].collapse_to = -1;
			used_vert_count += 1;
			
			
			j = verts[i].superposition_group;
			verts[i].next_in_superposition_group = -1;
			assert( j <= i );
			if (j != i)
			{
				while (verts[j].next_in_superposition_group != -1)
				{
					j = verts[j].next_in_superposition_group;
					assert( j < i );
				}
				verts[j].next_in_superposition_group = i;
			}
		}
		
	}
	
	for (i = 0; i < vert_count; ++i)
	{
		verts[i].no_reduce = false; //is_on_silhouette( i, NULL ) && (verts[i].superposition_group != i || verts[i].next_in_superposition_group != -1);
	}
	
	collapse_rounded_counts[used_vert_count] = used_vert_count;
	
	int collapsed_on_pass = 0;
	for (;;) {
		for (i = 0; i < vert_count; ++i)
		{
			verts[i].used_count = 0;
		}
		for (i = 0; i < tri_count; ++i) {
			if (tris[i].collapse_at >= collapse_count) {
				v0 = collapsed(tris[i].v[0]);
				v1 = collapsed(tris[i].v[1]);
				v2 = collapsed(tris[i].v[2]);
				int g0 = verts[v0].superposition_group;
				int g1 = verts[v1].superposition_group;
				int g2 = verts[v2].superposition_group;
				if (g0 == g1 || g0 == g2 || g1 == g2) {
					tris[i].collapse_at = collapse_count - collapsed_on_pass;
					tris[i].norm = vec3(0.0f, 0.0f, 0.0f);
					tris[i].area = 0.0f;
				} else {
					assert( verts[v0].used_count < MAXVTRI );
					assert( verts[v1].used_count < MAXVTRI );
					assert( verts[v2].used_count < MAXVTRI );
					verts[v0].used_by[verts[v0].used_count++] = i;
					verts[v1].used_by[verts[v1].used_count++] = i;
					verts[v2].used_by[verts[v2].used_count++] = i;
					
					vec3 n = cross( verts[v2].pos - verts[v0].pos, verts[v1].pos - verts[v0].pos );
					tris[i].norm = n;
					float l = dot(n,n);
					if (l > 0.0f) {
						l = sqrtf(l);
						tris[i].area = 0.5f * l;
						tris[i].norm = n / l;
					} else {
						tris[i].norm = vec3( 0.0f, 0.0f, 0.0f );
						tris[i].area = 0.0f;
					}
				}
			}
		}
		for (i = 0; i < vert_count; ++i)
		{
			if (verts[i].used_count == 0 && verts[i].collapse_to == -1)
			{
				verts[i].collapse_to = i;
				collapse_order[collapse_count++] = i;
				++collapsed_on_pass;
			}
		}
		for (i = 0; i < collapsed_on_pass; ++i)
		{
			collapse_rounded_counts[used_vert_count - collapse_count + i] = used_vert_count - collapse_count;
		}
		
		float best_error = NOCOLLAPSE_ERROR;
		int best_from = -1, best_to;
		for (i = 0; i < vert_count; ++i) {
			if (verts[i].used_count && verts[i].collapse_to == -1 && !verts[i].no_reduce) {
				short adj[MAXVTRI*2];
				int count = adjacent_list( i, adj );
				for (j = 0; j < count; ++j) {
					float err = collapse_error( i, adj[j] );
					if (err < best_error) {
						best_error = err;
						best_from = i;
						best_to = adj[j];
					}
				}
			}
		}
		collapsed_on_pass = 0;
		if (best_from >= 0) {
			for (i = verts[best_from].superposition_group; i != -1; i = verts[i].next_in_superposition_group)
			{
				if (verts[i].used_count > 0)
				{
					verts[i].collapse_to = adjacent_in_same_group( i, best_to );
					assert( verts[i].collapse_to != -1 );
					collapse_order[collapse_count++] = i;
					++collapsed_on_pass;
				}
			}
		} else break;
	}
	
	for (i = 0; i < vert_count; ++i)
	{
		verts[i].used_count = 0;
	}
	for (i = 0; i < tri_count; ++i) {
		v0 = tris[i].v[0];
		v1 = tris[i].v[1];
		v2 = tris[i].v[2];
		verts[v0].used_by[verts[v0].used_count++] = i;
		verts[v1].used_by[verts[v1].used_count++] = i;
		verts[v2].used_by[verts[v2].used_count++] = i;
	}
	
	int reorder = 0;
	for (i = 0; i < vert_count; ++i) {
		if (verts[i].used_count > 0) {
			if (verts[i].collapse_to < 0) {
				verts[i].number = reorder++;
				verts[i].collapse_to = i;
			}
		} else {
			verts[i].number = -1;
		}
	}
	irreducible_vert_count = reorder;
	
	for (i = collapse_count - 1; i >= 0; --i) {
		verts[collapse_order[i]].number = reorder++;
	}
	for (i = 0; i < tri_count; ++i) {
		int when = tris[i].collapse_at;
		if (when > used_vert_count) {
			when = 0;
		} else {
			when = used_vert_count - when;
		}
		tris[i].collapse_at = when;
	}
}


static int optimize_triangle_order( int /*min_vertices*/, int max_vertices, bool include_npatch, short *out )
{
	short unused_tri[MAXTRIS];
	short v_time[MAXVERTS];
	int i;
	
	for (i = 0; i < vert_count; ++i)
	{
		v_time[i] = -1;
	}
	int unused_count = 0;
	for (i = 0; i < tri_count; ++i)
	{
		if ((include_npatch || !tris[i].npatch_fill_only) && tris[i].collapse_at <= max_vertices)
		{
			unused_tri[unused_count++] = i;
		}
	}
	
	
	int out_count = 0;
	while (unused_count)
	{
		short best_times[3] = { -2, -2, -2 };
		int best_tri = -1;
		for (i = 0; i < unused_count; ++i)
		{
			skl_tri &t = tris[unused_tri[i]];
			int t0 = v_time[t.v[0]];
			int t1 = v_time[t.v[1]];
			int t2 = v_time[t.v[2]];
			int temp;
			if (t1 > t0) { temp = t0; t0 = t1; t1 = temp; }
			if (t2 > t1) { temp = t1; t1 = t2; t2 = temp; }
			if (t1 > t0) { temp = t0; t0 = t1; t1 = temp; }
			assert( t0 >= t1 && t1 >= t2 );
			if (t0 > best_times[0] || t0 == best_times[0] && (t1 > best_times[1] || t1 == best_times[1] && t2 > best_times[2]))
			{
				best_times[0] = t0;
				best_times[1] = t1;
				best_times[2] = t2;
				best_tri = i;
			}
		}
		assert( best_tri >= 0 );
		skl_tri &best = tris[unused_tri[best_tri]];
		v_time[best.v[0]] = out_count;
		v_time[best.v[1]] = out_count;
		v_time[best.v[2]] = out_count;
		out[out_count++] = unused_tri[best_tri];
		unused_tri[best_tri] = unused_tri[--unused_count];
	}
	
	return out_count;
}


struct skmd_lod *make_skmd_lod( int min_vertices, int max_vertices, bool use_npatch )
{
	static short tri_order[MAXTRIS];
	static short vert_order[MAXVERTS];
	short vertices_before[MAXBONES];
	int outbones = used_bone_count;
	
	int i, j;
	for (i = 0; i < vert_count; ++i) {
		if (verts[i].used_count > 0 && verts[i].number < max_vertices) {
			assert( verts[i].number >= 0 );
			vert_order[verts[i].number] = i;
		}
	}
	
	compact_weights( vert_order, max_vertices );
	
	for (i = 0; i <= outbones; ++i) {
		vertices_before[i] = 0;
		for (j = 0; j < bone_count; ++j) {
			if (bones[j].number >= 0 && bones[j].number < i) {
				vertices_before[i] += (bones[j].weight_count + 3) & ~3;
			}
		}
	}
	int weighted_vert_count = vertices_before[outbones];
	
	int min_triangles = 0;
	int max_triangles = 0;
	for (i = 0; i < tri_count; ++i) {
		if (tris[i].collapse_at <= max_vertices && (use_npatch || !tris[i].npatch_fill_only)) {
			max_triangles += 1;
			if (tris[i].collapse_at <= min_vertices) {
				min_triangles += 1;
			}
		}
	}
	
	optimize_triangle_order( min_vertices, max_vertices, use_npatch, tri_order );
	
	int wrc = 0;
	for (i = 0; i < max_vertices; ++i) {
		skl_vert &v = verts[vert_order[i]];
		wrc += 2 * v.weight_count;
	}
	
	skmd_lod *lod;
	{
		skmd_lod *temp_lod = (skmd_lod *)alloc_align( sizeof(skmd_lod), 16 );
		temp_lod->weighted_vert_count = weighted_vert_count;
		temp_lod->min_triangles = min_triangles;
		temp_lod->max_triangles = max_triangles;
		temp_lod->weight_ref_count = wrc;
		unsigned lod_size = setup_skmd_lod_ptrs( bone_count, min_vertices, max_vertices, temp_lod );
		free_align( temp_lod );
		lod = (skmd_lod *)alloc_align( lod_size, 16 );
	}
	lod->weighted_vert_count = weighted_vert_count;
	lod->min_triangles = min_triangles;
	lod->max_triangles = max_triangles;
	lod->weight_ref_count = wrc;
	lod->flags = 0;
	setup_skmd_lod_ptrs( used_bone_count, min_vertices, max_vertices, lod );
	word *weights_per_bone = const_cast<word *>(lod->weights_per_bone);
	word *edge_collapse = const_cast<word *>(lod->edge_collapse);
	word *min_vertices_for_tri = const_cast<word *>(lod->min_vertices_for_tri);
	word *weight_refs = const_cast<word *>(lod->weight_refs);
	byte *weights_per_vertex = const_cast<byte *>(lod->weights_per_vertex);
	
	for (i = 0; i < bone_count; ++i) {
		weights_per_bone[i] = 0;
	}
	for (i = 0; i < bone_count; ++i) {
		if (bones[i].number >= 0) {
			weights_per_bone[bones[i].number] = bones[i].weight_count;
		}
	}
	
	for (i = min_vertices; i < max_vertices; ++i) {
		edge_collapse[i] = verts[verts[vert_order[i]].collapse_to].number;
	}
	
	for (i = 0; i < max_triangles; ++i) {
		min_vertices_for_tri[i] = tris[tri_order[i]].collapse_at;
	}
	
	
//	int floats_per_vert = sizeof(skmd_quadvert) / (4 * sizeof(float));
	for (i = 0; i < bone_count; ++i) {
		if (bones[i].number >= 0) {
			float (*out)[4] = lod->weights + vertices_before[bones[i].number];
			//int step = (weights_per_bone[bones[i].number] + 3) & ~3;
			for (j = 0; j < bones[i].weight_count; ++j) {
				out[j][0] = bones[i].weight_data[j][0];
				out[j][1] = bones[i].weight_data[j][1];
				out[j][2] = bones[i].weight_data[j][2];
				out[j][3] = bones[i].weight_data[j][3];
			}
		}
	}
	
	int vr_count = 0;
	for (i = 0; i < max_vertices; ++i) {
		skl_vert &v = verts[vert_order[i]];
		weights_per_vertex[i] = v.weight_count;
		for (j = 0; j < v.weight_count; ++j) {
			skl_weight &w = v.weights[j];
			skl_bone &b = bones[w.bone];
			weight_refs[vr_count++] = vertices_before[b.number] + w.pos_index;
		}
		for (j = 0; j < v.weight_count; ++j) {
			skl_weight &w = v.weights[j];
			skl_bone &b = bones[w.bone];
			weight_refs[vr_count++] = vertices_before[b.number] + w.norm_index;
		}
	}
	assert( lod->weight_ref_count == vr_count );
//	lod->weight_ref_count = vr_count;
	
	for (i = 0; i < max_triangles; ++i) {
		for (j = 0; j < 3; ++j) {
			int vnum = tris[tri_order[i]].v[j];
			while (verts[vnum].number >= max_vertices) {
				vnum = verts[vnum].collapse_to;
			}
			lod->triangles[i][j] = verts[vnum].number;
		}
	}
	
	return lod;
}



struct skmd_modelheader *make_skmd_modelheader()
{
	int head_len = sizeof(skmd_modelheader) +
					(used_bone_count - 1) * sizeof(skmd_bone) +
					15 + used_vert_count * (2 * sizeof(float)) +
					sizeof(skmd_complex_collision_box) * 0 +
					sizeof(skmd_complex_collision_tri) * 0 +
					sizeof(word) * (used_vert_count+1 - irreducible_vert_count);
	skmd_modelheader *mh = (skmd_modelheader * )alloc_align( head_len, 16 );
	memset( mh, 0, head_len );
	
	strcpy( mh->name, "" );
	mh->texture_stack = -1;
	mh->hard_min_vertices = irreducible_vert_count;
	mh->user_min_vertices = irreducible_vert_count;
	mh->max_vertices = used_vert_count;
	mh->lod_count = 0;
	mh->bone_count = used_bone_count;
	mh->bone_fixed_shift = 0;
	mh->anim_offset_scale = 1;
	mh->anim_offset_shift = 0;
	mh->model_scale = 1.0f;
	{
		float r = 0.0f;
		float top = 0.0f;
		for (int i = 0; i < vert_count; ++i)
		{
			if (verts[i].number >= 0)
			{
				float test_r = verts[i].pos.x * verts[i].pos.x + verts[i].pos.y * verts[i].pos.y;
				float test_top = verts[i].pos.z;
				if (test_r > r) r = test_r;
				if (test_top > top) top = test_top;
			}
		}
		r = sqrt( r );
		mh->collision_radius = r * WORLD_ONE;
		mh->collision_height0 = 0;
		mh->collision_height1 = top * WORLD_ONE;
	}
	mh->pick_radius = mh->collision_radius;
	mh->pick_height0 = 0;
	mh->pick_height1 = mh->collision_height1;
	mh->hilight_radius = mh->collision_radius;
	mh->hilight_height0 = 0;
	mh->hilight_height1 = mh->collision_height1;
	mh->complex_collision_tri_count = 0;
	mh->complex_collision_box_count = 0;
	memset( mh->padding, 0, sizeof(mh->padding) );
	mh->uv = 0;
	mh->complex_collision_tris = 0;
	mh->complex_collision_boxes = 0;
	mh->real_vertex_counts = 0;
	int setup_len = setup_skmd_modelheader_ptrs( mh );
	assert( setup_len <= head_len && setup_len >= head_len - 15);
	mh->complex_collision_tris = 0;
	mh->complex_collision_boxes = 0;
	
	for (int i = 0; i < bone_count; ++i) {
		const skl_bone &ib = bones[i];
		if (ib.number >= 0) {
			skmd_bone &ob = mh->bones[ib.number];
			strncpy( ob.name, ib.name, sizeof(ob.name) );
			ob.name[sizeof(ob.name)-1] = 0;
			ob.flags = (_skmd_bone_shadow_dimension_none << _skmd_bone_shadow_dimension_bit_0);
			if (ib.parent < 0) {
				ob.parent = -1;
			} else {
				ob.parent = bones[ib.parent].number;
			}
			ob.anim_bone = -1;
			
			ob.float_orient[0] = ib.q[0];
			ob.float_orient[1] = ib.q[1];
			ob.float_orient[2] = ib.q[2];
			ob.float_orient[3] = ib.q[3];
			ob.float_offset[0] = ib.offset.x;
			ob.float_offset[1] = ib.offset.y;
			ob.float_offset[2] = ib.offset.z;
			
			ob.fixed_orient[0] = float_to_clamped_short( ib.q[0] );
			ob.fixed_orient[1] = float_to_clamped_short( ib.q[1] );
			ob.fixed_orient[2] = float_to_clamped_short( ib.q[2] );
			ob.fixed_orient[3] = float_to_clamped_short( ib.q[3] );
			ob.fixed_offset[0] = 0;
			ob.fixed_offset[1] = 0;
			ob.fixed_offset[2] = 0;
			
			ob.attachment_index = -1;
			ob.attachment_id = -1;
			
			for (int j = 0; j < 3; ++j)
			{
				for (int k = 0; k < 3; ++k)
				{
					ob.bounds[j][k] = ib.bounds[j][k];
				}
			}
			
			ob.shadow_near = 0.0f;
			ob.shadow_far = 0.0f;
			ob.shadow_width = 0.0f;
			
			ob.custom_shadow_tag = -1;
			ob.custom_shadow_stack = -1;
			ob.custom_shadow_level = -1;
			ob.shadow_texture_entry_index = -1;
			
			ob.tree_mass = 1.0f;
			ob.tree_resistance = 1.0f;
			ob.tree_dampening = 1.0f;
		}
	}
	
	for (int i = 0; i < vert_count; ++i) {
		const skl_vert &iv = verts[i];
		int n = iv.number;
		if (n >= 0) {
			float *uv = mh->uv[n];
			uv[0] = iv.s;
			uv[1] = iv.t;
		}
	}
	
	memcpy( mh->real_vertex_counts + mh->hard_min_vertices,
			collapse_rounded_counts + mh->hard_min_vertices,
			sizeof(word) * (mh->max_vertices+1 - mh->hard_min_vertices) );
	
	return mh;
}



const char *get_bone_name( int index )
{
	if (index < 0 || index >= bone_count) return NULL;
	return bones[index].name;
}


void make_skan_base( int origin_bone_index, XGSDynArray<skan_bone_base> &all_out, int frame )
{
	int i, j;
	
	set_skl_to_frame( frame );
	int count = 0;
	all_out.DeleteAll();
	skan_bone_base out;
	for (i = 0; i < bone_count; ++i) {
		if (bones[i].used_count > 0 && i != origin_bone_index) {
			bones[i].number = count;
			strncpy( out.name, bones[i].name, sizeof(out.name) - 1 );
			out.name[sizeof(out.name)-1] = 0;
			vec3 off;
			if (bones[i].parent >= 0) {
				out.parent = bones[bones[i].parent].number;
				off = bones[i].offset;
				for (j = 0; j < 4; ++j) {
					out.quat[j] = bones[i].q[j];
				}
			} else {
				skl_bonepos &b = frames[frame][i];
				skl_bonepos &o = frames[frame][origin_bone_index];
				out.parent = -1;
				off = inv_transform( o.m, b.pos - o.pos );
				float m[3][3];
				TransposeMat( m, o.m );
				MatMult( m, m, b.m );
				MatToQuat( out.quat, m );
			}
			out.offset[0] = off.x;
			out.offset[1] = off.y;
			out.offset[2] = off.z;
			all_out += out;
			++count;
		}
	}
}


struct skan_anim_build_temp {
	vec3 o;
	float q[4];
	
	vec3 p;
	float m[3][3];
	
	float yaw;
};

int find_named_bone( const char *name )
{
	int i;
	for (i = 0; i < bone_count; ++i) {
		if (strcmp( bones[i].name, name ) == 0) return i;
	}
	return -1;
}

static void skan_anim_build_snapshot( int frameno, int origin_bone_index, const XGSDynArray<skan_bone_base> &base, skan_anim_build_temp *out, const int *offset_settings )
{
	int i, j;
	float m[3][3];
	
	if (origin_bone_index >= 0) {
		out[-1].p = frames[frameno][origin_bone_index].pos;
		for (i = 0; i < 3; ++i) {
			if (offset_settings[i] == 1) {
				out[-1].p[i] = 0.0f;
			}
		}
		memcpy( out[-1].m, frames[frameno][origin_bone_index].m, sizeof(out[-1].m) );
		out[-1].yaw = atan2( out[-1].m[0][1], out[-1].m[0][0] );
		
		if (offset_settings[3] == 1) {
			float c = cos(out[-1].yaw);
			float s = sin(out[-1].yaw);
			
			m[0][0] = c;
			m[0][1] = -s;
			m[0][2] = 0;
			
			m[1][0] = s;
			m[1][1] = c;
			m[1][2] = 0;
			
			m[2][0] = 0;
			m[2][1] = 0;
			m[2][2] = 1;
			
			MatMult( out[-1].m, m, out[-1].m );
			
			out[-1].yaw = 0.0f;
		}
	} else {
		out[-1].p = vec3( 0,0,0 );
		for (i = 0; i < 3; ++i) {
			for (j = 0; j < 3; ++j) {
				out[-1].m[i][j] = (i == j ? 1.0 : 0.0);
			}
		}
	}
	for (i = 0; i < base.Length(); ++i) {
		j = find_named_bone( base[i].name );
		if (j >= 0) {
			out[i].o = inv_transform( out[base[i].parent].m, frames[frameno][j].pos - out[base[i].parent].p );
			TransposeMat( m, out[base[i].parent].m );
			MatMult( m, m, frames[frameno][j].m );
			MatToQuat( out[i].q, m );
			
			out[i].p = frames[frameno][j].pos;
			memcpy( out[i].m, frames[frameno][j].m, sizeof(out[i].m) );
		} else {
			out[i].o.x = base[i].offset[0];
			out[i].o.y = base[i].offset[1];
			out[i].o.z = base[i].offset[2];
			out[i].q[0] = base[i].quat[0];
			out[i].q[1] = base[i].quat[1];
			out[i].q[2] = base[i].quat[2];
			out[i].q[3] = base[i].quat[3];
			QuatToMat( m, out[i].q );
			MatMult( out[i].m, out[base[i].parent].m, m );
			out[i].p = out[base[i].parent].p + transform( out[i].m, out[i].o );
		}
		
		out[i].yaw = atan2( m[0][0], m[0][1] );
	}
}


skan_animation *make_skan_animation( int origin_bone_index,
									const XGSDynArray<skan_bone_base> &base,
									const int *offset_settings,
									bool loopable )
{
	int i, j, k;
	
	if (frame_count < 2) loopable = false;
	
	int out_bone_count = base.Length();
	int out_frame_size = sizeof(skan_frame) + out_bone_count * sizeof(skan_bone_frame_pos);
	out_frame_size = (out_frame_size + 3) & ~3;
	int out_frame_count = (loopable ? frame_count - 1 : frame_count);
	int out_total_size = sizeof(skan_animation) + out_frame_count * out_frame_size;
	skan_animation *skan = (skan_animation *)malloc(out_total_size);
	memset( skan->name, 0, sizeof(skan->name) );
	skan->frame_count = out_frame_count;
	skan->flags = (loopable ? _skelanim_loopable_flag : 0);
	skan->fixed_fps = float_to_short_fixed(frame_rate);
	float big_offset = 0.1;
	skan_anim_build_temp *temp = new skan_anim_build_temp[base.Length()+1];
	++temp;
	
	for (i = 0; i < frame_count; ++i) {
		skan_anim_build_snapshot( i, origin_bone_index, base, temp, offset_settings );
		for (j = 0; j < base.Length(); ++j) {
			for (k = 0; k < 3; ++k) {
				if (fabs(temp[j].o[k]) > big_offset) {
					big_offset = fabs(temp[j].o[k]);
				}
			}
		}
	}
	
	skan->offset_shift = 0;
	float offset_scale = 1.0f;
	while (big_offset * offset_scale < 16383.0f)
	{
		offset_scale *= 2.0f;
		skan->offset_shift += 1;
	}
	while (big_offset * offset_scale > 32767.0f)
	{
		offset_scale *= 0.5f;
		skan->offset_shift -= 1;
	}
	
	skan->crossfade_in_time = 0.125;
	skan->crossfade_interrupted_time = 0.5;
	skan->crossfade_finished_time = 0.125;
	
	skan_frame *frame;
	vec3 basepos(0,0,0);
	float baseyaw = 0.0f;
	
	frame = (skan_frame *)(skan + 1);
	for (i = 0; i < out_frame_count; ++i) {
		skan_anim_build_snapshot( i, origin_bone_index, base, temp, offset_settings );
		vec3 origdelta = temp[-1].p - basepos;
		float yawdelta = fabs( (temp[-1].yaw - baseyaw) * 180.0 / 3.1415926535 );
		while (yawdelta > 180.0f) {
			yawdelta = fabs( 360.0f - yawdelta );
		}
		yawdelta *= (FULL_CIRCLE / 360.0);
		basepos = temp[-1].p;
		baseyaw = temp[-1].yaw;
		float dist = 0.0f;
		for (j = 0; j < 3; ++j) {
			if (offset_settings[j] != 2) {
				dist += (origdelta[j] * origdelta[j]);
			}
		}
		if (dist > 0.0f) {
			dist = sqrtf( dist );
		}
		dist += yawdelta / FIXED_ONE;
		frame->fixed_distance_delta = float_to_fixed(dist);
		frame->frame_action = 0;
		frame->action_tag_index = -1;
		frame->action_tag_id = -1;
		skan_bone_frame_pos *b = (skan_bone_frame_pos *)(frame + 1);
		for (j = 0; j < base.Length(); ++j) {
			for (k = 0; k < 3; ++k) {
				b->shortOffset[k] = temp[j].o[k] * offset_scale;
			}
			for (k = 0; k < 4; ++k) {
				b->shortQuat[k] = temp[j].q[k] * TIKI_BONE_QUAT_MULTIPLIER;
			}
			++b;
		}
		frame = (skan_frame *)((char *)frame + out_frame_size);
	}
	
	if (loopable) {
		frame = (skan_frame *)(skan + 1);
		for (i = 0; i < out_frame_count; ++i) {
			skan_frame *next_frame = (skan_frame *)((char *)frame + out_frame_size);
			if (i < out_frame_count - 1) {
				frame->fixed_distance_delta = next_frame->fixed_distance_delta;
			} else {
				skan_anim_build_snapshot( frame_count - 1, origin_bone_index, base, temp, offset_settings );
				vec3 origdelta = temp[-1].p - basepos;
				float yawdelta = fabs( (temp[-1].yaw - baseyaw) * 180.0 / 3.1415926535 );
				while (yawdelta > 180.0f) {
					yawdelta = fabs( 360.0f - yawdelta );
				}
				yawdelta *= (FULL_CIRCLE / 360.0);
				float dist = 0.0f;
				for (j = 0; j < 3; ++j) {
					if (offset_settings[j] != 2) {
						dist += (origdelta[j] * origdelta[j]);
					}
				}
				if (dist > 0.0f) {
					dist = sqrtf( dist );
				}
				dist += yawdelta / FIXED_ONE;
				frame->fixed_distance_delta = float_to_fixed(dist);
			}
			frame = next_frame;
		}
	}
	assert( (char *)frame == (char *)skan + out_total_size );
	
	--temp;
	delete[] temp;
	
	return skan;
}



