/*
===========================================================================
maya2q3 - export .md3 files from maya
Copyright (C) 2005 HermitWorks Entertainment Corporation
Portions of this file Copyright (C) Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
===========================================================================
*/

#include "common.h"

/*
	bsp-patches.cpp

	Collapses any patch surfaces down into triangle soup.

	Most of this code is snipped right out of the Quake 3
	render code. This *should* be the same as Q3's patch
	rendering code, minus the dynamic Lod, of course.
*/

namespace q3
{

const uint MAX_GRID_SIZE = 65;
const uint MAX_PATCH_SIZE = 32;

static vec_t VectorNormalize( vec3_t &v )
{
	float len = length( v );

	if( len )
	{
		float iLen = 1.0F / len;

		v.x *= iLen;
		v.y *= iLen;
		v.z *= iLen;
	}
		
	return len;
}

static float VectorNormalize2( const vec3_t &v, vec3_t &out )
{
	float len = length( v );

	if( len )
	{
		float iLen = 1.0F / len;
		out.x = v.x * iLen;
		out.y = v.y * iLen;
		out.z = v.z * iLen;
	}
	else
	{
		out = vec3c( 0 );
	}
		
	return len;
}

/*
	Everything in this namespace originally comes from tr_curve.c.
	The only differences are names and data types. The algorithms
	are identical.
*/

static drawVert_t LerpDrawVert( const drawVert_t &a, const drawVert_t &b )
{
	drawVert_t out;

	out.xyz = (a.xyz + b.xyz) * 0.5F;
	out.st = (a.st + b.st) * 0.5F;
	out.lightmap = (a.lightmap + b.lightmap) * 0.5F;

	out.color[0] = (a.color[0] + b.color[0]) >> 1;
	out.color[1] = (a.color[1] + b.color[1]) >> 1;
	out.color[2] = (a.color[2] + b.color[2]) >> 1;
	out.color[3] = (a.color[3] + b.color[3]) >> 1;

	return out;
}

static void Transpose( int width, int height, drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE] )
{
	int		i, j;
	drawVert_t	temp;

	if ( width > height ) {
		for ( i = 0 ; i < height ; i++ ) {
			for ( j = i + 1 ; j < width ; j++ ) {
				if ( j < height ) {
					// swap the value
					temp = ctrl[j][i];
					ctrl[j][i] = ctrl[i][j];
					ctrl[i][j] = temp;
				} else {
					// just copy
					ctrl[j][i] = ctrl[i][j];
				}
			}
		}
	} else {
		for ( i = 0 ; i < width ; i++ ) {
			for ( j = i + 1 ; j < height ; j++ ) {
				if ( j < width ) {
					// swap the value
					temp = ctrl[i][j];
					ctrl[i][j] = ctrl[j][i];
					ctrl[j][i] = temp;
				} else {
					// just copy
					ctrl[i][j] = ctrl[j][i];
				}
			}
		}
	}

}

static void MakeMeshNormals( int width, int height, drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE] )
{
	//handles all the complicated wrapping and degenerate cases

	int		i, j, k, dist;
	vec3_t	normal;
	vec3_t	sum;
	int		count = 0;
	vec3_t	base;
	vec3_t	delta;
	int		x, y;
	vec3_t		around[8], temp;
	bool	good[8];
	bool	wrapWidth, wrapHeight;
	float		len;

	static	int	neighbors[8][2] = {
	{0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}, {-1,0}, {-1,1}
	};

	wrapWidth = false;
	for( i = 0 ; i < height ; i++ )
	{
		delta = ctrl[i][0].xyz - ctrl[i][width-1].xyz;
		len = lengthsq( delta );
		if ( len > 1.0 ) {
			break;
		}
	}
	if ( i == height ) {
		wrapWidth = true;
	}

	wrapHeight = false;
	for( i = 0; i < width; i++ )
	{
		delta = ctrl[0][i].xyz - ctrl[height-1][i].xyz;
		len = lengthsq( delta );
		if ( len > 1.0 ) {
			break;
		}
	}
	if ( i == width) {
		wrapHeight = true;
	}


	for( i = 0; i < width; i++ )
	{
		for( j = 0; j < height; j++ )
		{
			count = 0;
			drawVert_t &dv = ctrl[j][i];
			base = dv.xyz;
			for( k = 0; k < 8; k++ )
			{
				around[k] = vec3c( 0 );
				good[k] = false;

				for( dist = 1 ; dist <= 3 ; dist++ ) {
					x = i + neighbors[k][0] * dist;
					y = j + neighbors[k][1] * dist;
					if ( wrapWidth ) {
						if ( x < 0 ) {
							x = width - 1 + x;
						} else if ( x >= width ) {
							x = 1 + x - width;
						}
					}
					if ( wrapHeight ) {
						if ( y < 0 ) {
							y = height - 1 + y;
						} else if ( y >= height ) {
							y = 1 + y - height;
						}
					}

					if ( x < 0 || x >= width || y < 0 || y >= height ) {
						break;					// edge of patch
					}
					temp = ctrl[y][x].xyz - base;
					if ( VectorNormalize2( temp, temp ) == 0 ) {
						continue;				// degenerate edge, get more dist
					} else {
						good[k] = true;
						around[k] = temp;
						break;					// good edge
					}
				}
			}

			sum = vec3c( 0 );
			for ( k = 0 ; k < 8 ; k++ ) {
				if ( !good[k] || !good[(k+1)&7] ) {
					continue;	// didn't get two points
				}
				normal = cross( around[(k+1)&7], around[k] );
				if ( VectorNormalize2( normal, normal ) == 0 ) {
					continue;
				}
				sum += normal;
				count++;
			}
			if ( count == 0 ) {
				//bad normal
				count = 1;
			}
			dv.normal = normalize( sum );
		}
	}
}

static void PutPointsOnCurve( drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE], 
							 int width, int height )
{
	int			i, j;
	drawVert_t	prev, next;

	for( i = 0; i < width; i++ )
	{
		for( j = 1; j < height; j += 2 )
		{
			prev = LerpDrawVert( ctrl[j][i], ctrl[j+1][i] );
			next = LerpDrawVert( ctrl[j][i], ctrl[j-1][i] );
			ctrl[j][i] = LerpDrawVert( prev, next );
		}
	}


	for( j = 0; j < height; j++ )
	{
		for( i = 1; i < width; i += 2 )
		{
			prev = LerpDrawVert( ctrl[j][i], ctrl[j][i+1] );
			next = LerpDrawVert( ctrl[j][i], ctrl[j][i-1] );
			ctrl[j][i] = LerpDrawVert( prev, next );
		}
	}
}

static Patch CreateSurfaceGridMesh( int width, int height, drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE],
	float errorTable[2][MAX_GRID_SIZE] )
{
	int i, j;
	Patch grid;

	grid.widthLodError.resize( width );
	memcpy( &grid.widthLodError[0], errorTable[0], width * sizeof( float ) );

	grid.heightLodError.resize( height );
	memcpy( &grid.heightLodError[0], errorTable[1], height * sizeof( float ) );

	grid.width = width;
	grid.height = height;

	vec3 boundMin = vec3c( 99999 );
	vec3 boundMax = vec3c( -99999 );

	grid.verts.resize( width * height );

	for( i = 0; i < width; i++ )
	{
		for ( j = 0; j < height; j++ )
		{
			const drawVert_t &vert = ctrl[j][i];

			grid.verts[j * width + i] = vert;

			boundMin = min( boundMin, vert.xyz );
			boundMax = max( boundMax, vert.xyz );
		}
	}

	// compute local origin and bounds
	grid.lodOrigin = (boundMin + boundMax) * 0.5F;
	grid.lodRadius = length( boundMin - grid.lodOrigin );

	grid.lodFixed = 0;
	grid.lodStitched = 0;

	return grid;
}

static drawVert_t ClearedDrawVert( void )
{
	drawVert_t ret;
	memset( &ret, 0, sizeof( ret ) );
	return ret;
}

Patch SubdividePatchToGrid( int width, int height, const drawVert_t points[] )
{
	int			i, j, k;
	drawVert_t prev = ClearedDrawVert();
	drawVert_t next = ClearedDrawVert();
	drawVert_t mid = ClearedDrawVert();
	float		len, maxLen;
	int			dir;
	int			t;
	drawVert_t	ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE];
	float		errorTable[2][MAX_GRID_SIZE];

	for ( i = 0 ; i < width ; i++ ) {
		for ( j = 0 ; j < height ; j++ ) {
			ctrl[j][i] = points[j*width+i];
		}
	}

	for ( dir = 0 ; dir < 2 ; dir++ ) {

		for ( j = 0 ; j < MAX_GRID_SIZE ; j++ ) {
			errorTable[dir][j] = 0;
		}

		// horizontal subdivisions
		for ( j = 0 ; j + 2 < width ; j += 2 ) {
			// check subdivided midpoints against control points

			// FIXME: also check midpoints of adjacent patches against the control points
			// this would basically stitch all patches in the same LOD group together.

			maxLen = 0;
			for ( i = 0 ; i < height ; i++ ) {
				vec3_t		midxyz;
				vec3_t		midxyz2;
				vec3_t		dir;
				vec3_t		projected;
				float		d;

				// calculate the point on the curve
				midxyz = (ctrl[i][j].xyz + ctrl[i][j + 1].xyz * 2 + ctrl[i][j + 2].xyz) * 0.25F;

				// see how far off the line it is
				// using dist-from-line will not account for internal
				// texture warping, but it gives a lot less polygons than
				// dist-from-midpoint
				midxyz -= ctrl[i][j].xyz;
				dir = normalize( ctrl[i][j + 2].xyz - ctrl[i][j].xyz );
				
				d = dot( midxyz, dir );
				projected = dir * d;
				midxyz2 = midxyz - projected;
				len = lengthsq( midxyz2 ); // we will do the sqrt later
				if( len > maxLen )
					maxLen = len;
			}

			maxLen = sqrtf( maxLen );

			// if all the points are on the lines, remove the entire columns
			if( maxLen < 0.1f )
			{
				errorTable[dir][j + 1] = 999;
				continue;
			}

			// see if we want to insert subdivided columns
			if( width + 2 > MAX_GRID_SIZE )
			{
				errorTable[dir][j + 1] = 1.0f / maxLen;
				continue;	// can't subdivide any more
			}

			if( maxLen <= 4 ) //4 = high quality value of r_subdivisions
			{
				errorTable[dir][j + 1] = 1.0f / maxLen;
				continue;	// didn't need subdivision
			}

			errorTable[dir][j+2] = 1.0f / maxLen;

			// insert two columns and replace the peak
			width += 2;
			for( i = 0; i < height; i++ )
			{
				prev = LerpDrawVert( ctrl[i][j], ctrl[i][j+1] );
				next = LerpDrawVert( ctrl[i][j+1], ctrl[i][j+2] );
				mid = LerpDrawVert( prev, next );

				for( k = width - 1; k > j + 3; k-- )
				{
					ctrl[i][k] = ctrl[i][k-2];
				}

				ctrl[i][j + 1] = prev;
				ctrl[i][j + 2] = mid;
				ctrl[i][j + 3] = next;
			}

			// back up and recheck this set again, it may need more subdivision
			j -= 2;

		}

		Transpose( width, height, ctrl );
		t = width;
		width = height;
		height = t;
	}


	// put all the aproximating points on the curve
	PutPointsOnCurve( ctrl, width, height );

	// cull out any rows or columns that are colinear
	for ( i = 1 ; i < width-1 ; i++ ) {
		if ( errorTable[0][i] != 999 ) {
			continue;
		}
		for ( j = i+1 ; j < width ; j++ ) {
			for ( k = 0 ; k < height ; k++ ) {
				ctrl[k][j-1] = ctrl[k][j];
			}
			errorTable[0][j-1] = errorTable[0][j];
		}
		width--;
	}

	for ( i = 1 ; i < height-1 ; i++ ) {
		if ( errorTable[1][i] != 999 ) {
			continue;
		}
		for ( j = i+1 ; j < height ; j++ ) {
			for ( k = 0 ; k < width ; k++ ) {
				ctrl[j-1][k] = ctrl[j][k];
			}
			errorTable[1][j-1] = errorTable[1][j];
		}
		height--;
	}

	// calculate normals
	MakeMeshNormals( width, height, ctrl );

	return CreateSurfaceGridMesh( width, height, ctrl, errorTable );
}

static Patch GridInsertColumn( const Patch &grid, int column, int row, vec3_t point, float loderror )
{
	int i, j;
	int width, height, oldwidth;
	drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE];
	float errorTable[2][MAX_GRID_SIZE];

	oldwidth = 0;
	width = grid.width + 1;

	assert( width <= MAX_GRID_SIZE, "Can't grow patch." );

	height = grid.height;
	for( i = 0; i < width; i++ )
	{
		if( i == column )
		{
			//insert new column
			for( j = 0; j < grid.height; j++ )
			{
				ctrl[j][i] = LerpDrawVert( grid.verts[j * grid.width + i-1], grid.verts[j * grid.width + i] );
				if( j == row )
					ctrl[j][i].xyz = point;
			}
			
			errorTable[0][i] = loderror;
			continue;
		}
		
		errorTable[0][i] = grid.widthLodError[oldwidth];
		for( j = 0; j < grid.height; j++ )
			ctrl[j][i] = grid.verts[j * grid.width + oldwidth];

		oldwidth++;
	}
	
	for( j = 0; j < grid.height; j++ )
		errorTable[1][j] = grid.heightLodError[j];

	// put all the aproximating points on the curve
	//PutPointsOnCurve( ctrl, width, height );
	// calculate normals
	MakeMeshNormals( width, height, ctrl );

	//create a new grid
	Patch ret = CreateSurfaceGridMesh( width, height, ctrl, errorTable );
	ret.lodRadius = grid.lodRadius;
	ret.lodOrigin = grid.lodOrigin;
	
	return ret;
}

static Patch GridInsertRow( const Patch &grid, int row, int column, vec3_t point, float loderror )
{
	int i, j;
	int width, height, oldheight;
	drawVert_t ctrl[MAX_GRID_SIZE][MAX_GRID_SIZE];
	float errorTable[2][MAX_GRID_SIZE];
	
	oldheight = 0;
	width = grid.width;
	height = grid.height + 1;

	assert( height <= MAX_GRID_SIZE, "Can't grow patch." );
		
	for( i = 0; i < height; i++ )
	{
		if( i == row )
		{
			//insert new row
			for( j = 0; j < grid.width; j++ )
			{
				ctrl[i][j] = LerpDrawVert( grid.verts[(i-1) * grid.width + j], grid.verts[i * grid.width + j] );
				if( j == column )
					ctrl[i][j].xyz = point;
			}
			errorTable[1][i] = loderror;
			continue;
		}

		errorTable[1][i] = grid.heightLodError[oldheight];
		for( j = 0; j < grid.width; j++ )
			ctrl[i][j] = grid.verts[oldheight * grid.width + j];

		oldheight++;
	}

	for( j = 0; j < grid.width; j++ )
		errorTable[0][j] = grid.widthLodError[j];
	// put all the aproximating points on the curve
	//PutPointsOnCurve( ctrl, width, height );
	// calculate normals
	MakeMeshNormals( width, height, ctrl );
	
	//create a new grid
	Patch ret = CreateSurfaceGridMesh( width, height, ctrl, errorTable );
	ret.lodRadius = grid.lodRadius;
	ret.lodOrigin = grid.lodOrigin;

	return ret;
}

/*
	Everything in this namespace originally comes from tr_bsp.c.
	The only differences are names and data types. The algorithms
	are identical.
*/

static bool MergedWidthPoints( const Patch & grid, int offset )
{
	int i, j;

	for( i = 1; i < grid.width-1; i++ )
	{
		for( j = i + 1; j < grid.width - 1; j++ )
		{
			if( !equal( grid.verts[i + offset].xyz, grid.verts[j + offset].xyz, 0.1F ) )
				continue;

			return true;
		}
	}

	return false;
}

static bool MergedHeightPoints( const Patch &grid, int offset )
{
	int i, j;

	for( i = 1; i < grid.height-1; i++ )
	{
		for( j = i + 1; j < grid.height-1; j++ )
		{
			if( !equal( grid.verts[grid.width * i + offset].xyz, grid.verts[grid.width * j + offset].xyz, 0.1F ) )
				continue;
			
			return true;
		}
	}

	return false;
}

static void FixSharedVertexLodError_r( std::vector< Patch > &patches, int start, Patch &grid1 )
{
	/*
		NOTE:	never sync LoD through grid edges with merged points!

		FIXME:	write generalized version that also avoids
				cracks between a patch and one that meets half way?
	*/

	for( uint j = start; j < patches.size(); j++ )
	{
		Patch &grid2 = patches[j];
		if( grid2.lodFixed == 2 )
			//LOD errors are already fixed for this patch
			continue;

		if( grid1.lodRadius != grid2.lodRadius )
			// grids in the same LOD group should have the exact same lod radius
			continue;

		if( grid1.lodOrigin != grid2.lodOrigin )
			//grids in the same LOD group should have the exact same lod origin
			continue;
		
		bool touch = false;
		for( int n = 0; n < 2; n++ )
		{
			int offset1 = n ? (grid1.height - 1) * grid1.width : 0;
			
			if( MergedWidthPoints( grid1, offset1 ) )
				continue;

			for( int k = 1; k < grid1.width - 1; k++ )
			{
				for( int m = 0; m < 2; m++ )
				{
					int offset2 = m ? (grid2.height - 1) * grid2.width : 0;
					
					if( MergedWidthPoints( grid2, offset2 ) )
						continue;

					for( int l = 1; l < grid2.width - 1; l++ )
					{
						if( !equal( grid1.verts[k + offset1].xyz, grid2.verts[l + offset2].xyz, 0.1F ) )
							continue;

						// ok the points are equal and should have the same lod error
						grid2.widthLodError[l] = grid1.widthLodError[k];
						touch = true;
					}
				}

				for( int m = 0; m < 2; m++ )
				{
					int offset2 = m ? grid2.width - 1 : 0;
					
					if( MergedHeightPoints( grid2, offset2 ) )
						continue;

					for( int l = 1; l < grid2.height - 1; l++ )
					{
						if( !equal( grid1.verts[k + offset1].xyz, grid2.verts[grid2.width * l + offset2].xyz, 0.1F ) )
							continue;
						
						// ok the points are equal and should have the same lod error
						grid2.heightLodError[l] = grid1.widthLodError[k];
						touch = true;
					}
				}
			}
		}
		for( int n = 0; n < 2; n++ )
		{
			int offset1 = n ? grid1.width - 1 : 0;

			if( MergedHeightPoints( grid1, offset1 ) )
				continue;

			for( int k = 1; k < grid1.height - 1; k++ )
			{
				for( int m = 0; m < 2; m++ )
				{
					int offset2 = m ? (grid2.height - 1) * grid2.width : 0;

					if( MergedWidthPoints( grid2, offset2 ) )
						continue;

					for( int l = 1; l < grid2.width - 1; l++)
					{
						if( !equal( grid1.verts[grid1.width * k + offset1].xyz, grid2.verts[l + offset2].xyz, 0.1F ) )
							continue;
						
						// ok the points are equal and should have the same lod error
						grid2.widthLodError[l] = grid1.heightLodError[k];
						touch = true;
					}
				}

				for( int m = 0; m < 2; m++ )
				{
					int offset2 = m ? grid2.width - 1 : 0;

					if( MergedHeightPoints( grid2, offset2 ) )
						continue;
					
					for( int l = 1; l < grid2.height - 1; l++ )
					{
						if( !equal( grid1.verts[grid1.width * k + offset1].xyz, grid2.verts[grid2.width * l + offset2].xyz, 0.1F ) )
							continue;
						
						// ok the points are equal and should have the same lod error
						grid2.heightLodError[l] = grid1.heightLodError[k];
						touch = true;
					}
				}
			}
		}

		if( touch )
		{
			grid2.lodFixed = 2;
			FixSharedVertexLodError_r( patches, start, grid2 );

			//NOTE: this would be correct but makes things really slow
			//grid2.lodFixed = 1;
		}
	}
}

void FixSharedVertexLodError( std::vector< Patch > &patches )
{
	/*
		This function assumes that all patches in one group are nicely stitched together for the highest LoD.
		If this is not the case this function will still do its job but won't fix the highest LoD cracks.
	*/
	for( uint i = 0; i < patches.size(); i++ )
	{
		Patch &grid1 = patches[i];
		
		if( grid1.lodFixed )
			continue;
		
		grid1.lodFixed = 2;
		
		//recursively fix other patches in the same LOD group
		FixSharedVertexLodError_r( patches, i + 1, grid1 );
	}
}

static int StitchPatches( const Patch &grid1, Patch &grid2 )
{
	for( int n = 0; n < 2; n++ )
	{
		int offset1 = n ? (grid1.height - 1) * grid1.width : 0;
		
		if( MergedWidthPoints( grid1, offset1 ) )
			continue;

		for( int k = 0; k < grid1.width - 2; k += 2 )
		{
			for( int m = 0; m < 2; m++ )
			{
				if( grid2.width >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? (grid2.height - 1) * grid2.width : 0;
				for( int l = 0; l < grid2.width - 1; l++ )
				{
					if( !equal( grid1.verts[k + offset1].xyz, grid2.verts[l + offset2].xyz, 0.1F ) )
						continue;

					if( !equal( grid1.verts[k + 2 + offset1].xyz, grid2.verts[l + 1 + offset2].xyz, 0.1F ) )
						continue;

					if( equal( grid2.verts[l + offset2].xyz, grid2.verts[l + 1 + offset2].xyz, 0.01F ) )
						continue;
					
					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert column into grid2 right after after column l
					int row = m ? grid2.height - 1 : 0;
					
					grid2 = GridInsertColumn( grid2, l + 1, row, grid1.verts[k + 1 + offset1].xyz, grid1.widthLodError[k + 1] );
					grid2.lodStitched = false;

					return true;
				}
			}

			for( int m = 0; m < 2; m++ )
			{
				if( grid2.height >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? grid2.width - 1 : 0;
				
				for( int l = 0; l < grid2.height - 1; l++ )
				{
					if( !equal( grid1.verts[k + offset1].xyz, grid2.verts[grid2.width * l + offset2].xyz, 0.1F ) )
						continue;

					if( !equal( grid1.verts[k + 2 + offset1].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.1F ) )
						continue;

					if( equal( grid2.verts[grid2.width * l + offset2].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.01F ) )
						continue;
				
					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert row into grid2 right after after row l
					int column = m ? grid2.width - 1 : 0;

					grid2 = GridInsertRow( grid2, l+1, column, grid1.verts[k + 1 + offset1].xyz, grid1.widthLodError[k + 1] );
					grid2.lodStitched = false;
					
					return true;
				}
			}
		}
	}

	for( int n = 0; n < 2; n++ )
	{
		int offset1 = n ? grid1.width - 1 : 0;
		
		if( MergedHeightPoints( grid1, offset1 ) )
			continue;

		for( int k = 0; k < grid1.height - 2; k += 2 )
		{
			for( int m = 0; m < 2; m++ )
			{
				if( grid2.width >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? (grid2.height-1) * grid2.width : 0;
				
				for( int l = 0; l < grid2.width - 1; l++ )
				{
					if( !equal( grid1.verts[grid1.width * k + offset1].xyz, grid2.verts[l + offset2].xyz, 0.1F ) )
						continue;

					if( !equal( grid1.verts[grid1.width * (k + 2) + offset1].xyz, grid2.verts[l + 1 + offset2].xyz, 0.1F ) )
						continue;
					
					if( equal( grid2.verts[l + offset2].xyz, grid2.verts[(l + 1) + offset2].xyz, 0.01F ) )
						continue;
					
					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert column into grid2 right after after column l
					int row = m ? grid2.height - 1 : 0;
					
					grid2 = GridInsertColumn( grid2, l+1, row, grid1.verts[grid1.width * (k + 1) + offset1].xyz,
						grid1.heightLodError[k+1]);
					grid2.lodStitched = false;
					
					return true;
				}
			}

			for( int m = 0; m < 2; m++ )
			{

				if( grid2.height >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? grid2.width - 1 : 0;
				
				for( int l = 0; l < grid2.height - 1; l++ )
				{
					if( !equal( grid1.verts[grid1.width * k + offset1].xyz, grid2.verts[grid2.width * l + offset2].xyz, 0.1F ) )
						continue;
					
					if( !equal( grid1.verts[grid1.width * (k + 2) + offset1].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.1F ) )
						continue;

					if( equal( grid2.verts[grid2.width * l + offset2].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.01F ) )
						continue;
					
					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert row into grid2 right after after row l
					int column = m ? grid2.width - 1 : 0;
					grid2 = GridInsertRow( grid2, l+1, column, grid1.verts[grid1.width * (k + 1) + offset1].xyz, grid1.heightLodError[k+1]);
					grid2.lodStitched = false;

					return true;
				}
			}
		}
	}

	for( int n = 0; n < 2; n++ )
	{
		int offset1 = n ? (grid1.height-1) * grid1.width : 0;
		
		if( MergedWidthPoints(grid1, offset1) )
			continue;

		for( int k = grid1.width-1; k > 1; k -= 2 )
		{
			for( int m = 0; m < 2; m++ )
			{
				if( grid2.width >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? (grid2.height-1) * grid2.width : 0;

				for( int l = 0; l < grid2.width-1; l++ )
				{
					if( !equal( grid1.verts[k + offset1].xyz, grid2.verts[l + offset2].xyz, 0.1F ) )
						continue;
					
					if( !equal( grid1.verts[k - 2 + offset1].xyz, grid2.verts[l + 1 + offset2].xyz, 0.1F ) )
						continue;
					
					if( equal( grid2.verts[l + offset2].xyz, grid2.verts[(l + 1) + offset2].xyz, 0.01F ) )
						continue;

					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert column into grid2 right after after column l
					int row = m ? grid2.height - 1 : 0;
					grid2 = GridInsertColumn( grid2, l+1, row, grid1.verts[k - 1 + offset1].xyz, grid1.widthLodError[k+1]);
					grid2.lodStitched = false;
					
					return true;
				}
			}

			for( int m = 0; m < 2; m++ )
			{
				if( grid2.height >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? grid2.width - 1 : 0;

				for( int l = 0; l < grid2.height - 1; l++ )
				{
					if( !equal( grid1.verts[k + offset1].xyz, grid2.verts[grid2.width * l + offset2].xyz, 0.1F ) )
						continue;

					if( !equal( grid1.verts[k - 2 + offset1].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.1F ) )
						continue;

					if( equal( grid2.verts[grid2.width * l + offset2].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.01F ) )
						continue;

					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert row into grid2 right after after row l
					int column = m ? grid2.width - 1 : 0;
					grid2 = GridInsertRow( grid2, l+1, column, grid1.verts[k - 1 + offset1].xyz, grid1.widthLodError[k+1]);
					grid2.lodStitched = false;

					return true;
				}
			}
		}
	}

	for( int n = 0; n < 2; n++ )
	{
		int offset1 = n ? grid1.width-1 : 0;
		
		if( MergedHeightPoints( grid1, offset1 ) )
			continue;

		for( int k = grid1.height-1; k > 1; k -= 2)
		{
			for( int m = 0; m < 2; m++ )
			{
				if( grid2.width >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? (grid2.height - 1) * grid2.width : 0;

				for( int l = 0; l < grid2.width - 1; l++ )
				{
					if( !equal( grid1.verts[grid1.width * k + offset1].xyz, grid2.verts[l + offset2].xyz, 0.1F ) )
						continue;

					if( !equal( grid1.verts[grid1.width * (k - 2) + offset1].xyz, grid2.verts[l + 1 + offset2].xyz, 0.1F ) )
						continue;

					if( equal( grid2.verts[l + offset2].xyz, grid2.verts[(l + 1) + offset2].xyz, 0.01F ) )
						continue;

					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert column into grid2 right after after column l
					int row = m ? grid2.height - 1 : 0;
					grid2 = GridInsertColumn( grid2, l+1, row, grid1.verts[grid1.width * (k - 1) + offset1].xyz, grid1.heightLodError[k+1]);
					grid2.lodStitched = false;
					
					return true;
				}
			}

			for( int m = 0; m < 2; m++ )
			{

				if( grid2.height >= MAX_GRID_SIZE )
					break;

				int offset2 = m ? grid2.width - 1 : 0;

				for( int l = 0; l < grid2.height - 1; l++)
				{
					if( !equal( grid1.verts[grid1.width * k + offset1].xyz, grid2.verts[grid2.width * l + offset2].xyz, 0.1F ) )
						continue;

					if( !equal( grid1.verts[grid1.width * (k - 2) + offset1].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.1F ) )
						continue;

					if( equal( grid2.verts[grid2.width * l + offset2].xyz, grid2.verts[grid2.width * (l + 1) + offset2].xyz, 0.01F ) )
						continue;

					//ri.Printf( PRINT_ALL, "found highest LoD crack between two patches\n" );
					// insert row into grid2 right after after row l
					int column = m ? grid2.width - 1 : 0;
					grid2 = GridInsertRow( grid2, l+1, column, grid1.verts[grid1.width * (k - 1) + offset1].xyz, grid1.heightLodError[k+1]);
					grid2.lodStitched = false;

					return true;
				}
			}
		}
	}

	return false;
}

static int TryStitchingPatch( std::vector< Patch > &patches, int grid1num )
{
	/*
		This function will try to stitch patches in the same LoD group together for the highest LoD.

		Only single missing vertice cracks will be fixed.

		Vertices will be joined at the patch side a crack is first found, at the other side
		of the patch (on the same row or column) the vertices will not be joined and cracks
		might still appear at that side.
	*/
	int numstitches = 0;

	Patch &grid1 = patches[grid1num];

	for( uint j = 0; j < patches.size(); j++ )
	{
		Patch &grid2 = patches[j];
		
		if( grid1.lodRadius != grid2.lodRadius )
			// grids in the same LOD group should have the exact same lod radius
			continue;

		if( grid1.lodOrigin != grid2.lodOrigin )
			// grids in the same LOD group should have the exact same lod origin
			continue;

		while( StitchPatches( patches[grid1num], patches[j] ) )
			numstitches++;
	}

	return numstitches;
}

void StitchAllPatches( std::vector< Patch > &patches )
{
	int numstitches = 0;

	bool stitched = true;
	while( stitched )
	{
		stitched = false;
		for( uint i = 0; i < patches.size(); i++ )
		{
			Patch &grid1 = patches[i];
			
			if( grid1.lodStitched )
				continue;

			grid1.lodStitched = true;
			stitched = true;

			numstitches += TryStitchingPatch( patches, i );
		}
	}
}

void PatchToMesh( const Patch &patch, std::vector< q3::drawVert_t > &out_verts, std::vector< int > &out_indices )
{
	uint numVerts = (uint)(patch.width * patch.height);
	uint numQuads = (uint)((patch.width - 1) * (patch.height - 1));
	uint numIndices = numQuads * 2 * 3;

	out_verts.resize( numVerts );
	out_indices.resize( numIndices );

	for( uint i = 0; i < numVerts; i++ )
		out_verts[i] = patch.verts[i];

	uint outIdx = 0;
	for( uint i = 0; i < numQuads; i++ )
	{
		uint rowNum = i / (patch.width - 1);
		int indices[4];

		indices[0] = i + rowNum;
		indices[1] = i + rowNum + 1;
		indices[2] = indices[1] + patch.width;
		indices[3] = indices[0] + patch.width;

		/*
			First we find the best way to split the quad.
			
			In the case of a planar quad this is arbitrary.

			When a quad is non-planar we take the first triangle
			of each of the two possible splits and find the distance
			of the remaining point from the plane of the triangle.

			We choose the split that minimizes this distance
			(thus minimizing the angle of the folded edge).
		*/

		float d02, d13;
		vec3 e01, e02, e13, c;

		e01 = out_verts[indices[0]].xyz - out_verts[indices[1]].xyz;
		e02 = out_verts[indices[0]].xyz - out_verts[indices[2]].xyz;
		e13 = out_verts[indices[1]].xyz - out_verts[indices[3]].xyz;

		//try splitting along 0-2
		c = cross( e01, e02 );
		
		if( q3::VectorNormalize( c ) > 1e-6 )
			d02 = dot( c, e13 );
		else
			//degenerate or very small triangle, don't care about order
			d02 = 0;

		//try splitting along 1-3
		c = cross( e01, e13 );

		if( q3::VectorNormalize( c ) > 1e-6 )
			d13 = dot( c, e02 );
		else
			//degenerate or very small triangle, don't care about order
			d13 = 0;

		//generat the final indices
		if( d02 < d13 )
		{
			//split along 0-2
			out_indices[outIdx++] = indices[0];
			out_indices[outIdx++] = indices[2];
			out_indices[outIdx++] = indices[1];

			out_indices[outIdx++] = indices[2];
			out_indices[outIdx++] = indices[0];
			out_indices[outIdx++] = indices[3];
		}
		else
		{
			//split along 1-3
			out_indices[outIdx++] = indices[0];
			out_indices[outIdx++] = indices[3];
			out_indices[outIdx++] = indices[1];

			out_indices[outIdx++] = indices[2];
			out_indices[outIdx++] = indices[1];
			out_indices[outIdx++] = indices[3];
		}
	}
}

};