/*
   model/map.cc
   This file is part of the Osirion project and is distributed under
   the terms of the GNU General Public License version 2
*/

#include "auxiliary/functions.h"
#include "filesystem/filesystem.h"
#include "math/mathlib.h"
#include "model/collisionmesh.h"
#include "model/mapfile.h"
#include "model/material.h"
#include "model/model.h"
#include "model/vertexarray.h"
#include "sys/sys.h"

#include <sstream>
#include <string>
#include <cstring>

namespace model
{

/**
 * @brief a two-dimensional array class
 * */
template <class T> class Matrix {
public:
	Matrix(size_t rows, size_t columns)
	{
		matrix_rows = rows;
		matrix_columns = columns;
		
		matrix_values = new T *[matrix_rows];
		
		for (size_t i = 0; i < matrix_rows; ++i)
		{
			matrix_values[i] = new T[columns];
		}
	}
	
	~Matrix()
	{
		for (size_t i = 0; i < matrix_rows; ++i)
		{
			delete[] matrix_values[i];
		}
		
		delete[] matrix_values;
	}
	
	T * operator[](size_t row)
	{
		return matrix_values[row];
	}
	
	const T * operator[](size_t row) const
	{
		return matrix_values[row];
	}
	
	
private:
	size_t matrix_rows;
	size_t matrix_columns;
	
	T **matrix_values;
};

// max geometry bounds
const float MAX_BOUNDS = 16384;

const float MIN_DELTA = 10e-10;

// from radiant tools/quake3/q3map2/map.c
math::Vector3f texture_baseaxis[18] = {
	// normal			texture plane
	math::Vector3f(0, 0, 1),	math::Vector3f(1, 0, 0), math::Vector3f(0, -1, 0),	// floor
	math::Vector3f(0, 0, -1),	math::Vector3f(1, 0, 0), math::Vector3f(0, -1, 0),	// ceiling
	math::Vector3f(1, 0, 0),	math::Vector3f(0, 1, 0), math::Vector3f(0, 0, -1),	// west wall
	math::Vector3f(-1, 0, 0),	math::Vector3f(0, 1, 0), math::Vector3f(0, 0, -1),	// east wall
	math::Vector3f(0, 1, 0),	math::Vector3f(1, 0, 0), math::Vector3f(0, 0, -1),	// south wall
	math::Vector3f(0, -1, 0),	math::Vector3f(1, 0, 0), math::Vector3f(0, 0, -1)	// north wall
};

// from radiant tools/quake3/q3map2/map.c
// determines best orthagonal axis to project a texture onto a wall (must be identical in radiant!)
void texture_axis_from_plane(const Face &face, math::Vector3f &xv, math::Vector3f &yv)
{
	size_t best_axis = 0;
	float dot = 0;
	float best = 0;

	math::Vector3f n(face.normal()* -1);
	n.normalize();

	for (size_t i = 0 ; i < 6 ; i++) {
		dot = math::dotproduct(n, texture_baseaxis[i *3]);
		if (dot > best + MIN_DELTA) {	/* ydnar: bug 637 fix, suggested by jmonroe */
			best = dot;
			best_axis = i;
		}
	}

	xv.assign(texture_baseaxis[best_axis*3+1]);
	yv.assign(texture_baseaxis[best_axis*3+2]);
}

// from radiant tools/quake3/q3map2/map.c
// creates world-to-texture mapping vecs for crappy quake plane arrangements
void face_texture_verts(Face &face, const math::Vector2f &tex_shift, const float tex_rotate, const math::Vector2f & tex_scale)
{
	math::Vector3f vecs[2];
	math::Vector2f scale(tex_scale);

	int		sv, tv;
	float ang, sinv, cosv;
	float ns, nt;
	int		i, j;

	texture_axis_from_plane(face, vecs[0], vecs[1]);

	if (!scale[0])
		scale[0] = 1;
	if (!scale[1])
		scale[1] = 1;

	// rotate axis
	if (tex_rotate == 0.0f) {
		sinv = 0.0f ;
		cosv = 1.0f;
	} else if (tex_rotate == 90.0f) {
		sinv = 1.0f ;
		cosv = 0.0f;
	} else if (tex_rotate == 180.0f) {
		sinv = 0.0f;
		cosv = -1.0f;
	} else if (tex_rotate == 270.0f) {
		sinv = -1.0f ;
		cosv = 0.0f;
	} else {
		ang = tex_rotate / 180.0f * M_PI;
		sinv = sinf(ang);
		cosv = cosf(ang);
	}

	if (vecs[0][0])
		sv = 0;
	else if (vecs[0][1])
		sv = 1;
	else
		sv = 2;

	if (vecs[1][0])
		tv = 0;
	else if (vecs[1][1])
		tv = 1;
	else
		tv = 2;

	for (i = 0 ; i < 2 ; i++) {
		ns = cosv * vecs[i][sv] - sinv * vecs[i][tv];
		nt = sinv * vecs[i][sv] +  cosv * vecs[i][tv];
		vecs[i][sv] = ns;
		vecs[i][tv] = nt;
	}

	for (i = 0 ; i < 2 ; i++)
		for (j = 0 ; j < 3 ; j++)
			face.get_tex_vec(i)[j] = vecs[i][j] / scale[i];

	face.get_tex_shift().assign(tex_shift);
}

// from radiant tools/quake3/q3map2/map.c
// project vertex into texture plane
const math::Vector2f map_texture_coords(Face *face, const math::Vector3f &v)
{
	return math::Vector2f(
		       (face->get_tex_shift().x() + math::dotproduct(face->tex_vec(0), v)) / face->material()->size().width(),
		       (face->get_tex_shift().y() + math::dotproduct(face->tex_vec(1), v))  / face->material()->size().height()
	       );
}

// function to test spawnflags
inline bool spawnflag_isset(unsigned int spawnflags, unsigned int flag)
{
	return ((spawnflags & flag) == flag);
}

MapFile::MapFile()
{
	mapfile_name.clear();
	map_brushes = 0;
	map_faces = 0;
	map_faces_detail = 0;
	
	map_load_clip = false;

	in_patchdef = false;
	warning_q2brush = false;
	class_engine = false;
	class_speed = 0;
	class_distance = 0;

	// the initial bounding box value is invalid: max and min are switched
	class_box.assign(MAX_BOUNDS, -MAX_BOUNDS);
	map_box.assign(MAX_BOUNDS, -MAX_BOUNDS);
}

MapFile::~MapFile()
{
	clear_materials();
	
	// delete bounds vertices
	for (std::vector<math::Vector3f *>::iterator bvit = map_bounds_vertices.begin(); bvit != map_bounds_vertices.end(); ++bvit) {
		delete (*bvit);
	}
	map_bounds_vertices.clear();
}

void MapFile::clear_materials()
{
	// delete primitives for each material
	for (Materials::iterator mit = map_materials.begin(); mit != map_materials.end(); ++mit) {
		// delete list of primitives
		delete(*mit).second;
	}
	map_materials.clear();
	
	map_collisiontriangles.clear();
	
	// delete origin vertices
	for (std::vector<math::Vector3f *>::iterator ovit = class_origin_vertices.begin(); ovit != class_origin_vertices.end(); ++ovit) {
		delete (*ovit);
	}
	class_origin_vertices.clear();
}

bool MapFile::open(std::string const & mapname)
{
	warning_q2brush = false;
	last_read_was_classname = false;
	last_read_was_key = false;
	key_current = "";
	value_current = "";
	classname_current = "";
	line_number = 0;
	parse_level = 0;

	clear_materials();

	mapfile_name.append(mapname);
	mapfile_name.append(".map");

	mapfile_ifs.open(mapfile_name);
	if (!mapfile_ifs.is_open()) {
		return false;
	}
	return true;
}


bool MapFile::got_classname() const
{
	return last_read_was_classname;
}

bool MapFile::got_classname(const char * classnamelabel) const
{
	return (last_read_was_classname && (classname_current.compare(classnamelabel) == 0));
}

bool MapFile::got_classend(const char * classnamelabel) const
{
	return (last_read_was_classend && (classname_current.compare(classnamelabel) == 0));
}

bool MapFile::read_patchdef()
{
	char data[1024];
	memset(data, 0, sizeof(data));
	size_t columns = 0;
	size_t rows = 0;
	std::string materialname;

	// first line: texture name
	if (!mapfile_ifs.getline(data, 1023)) {
		return false;
	} else {
		line_number++;
		
		std::istringstream linestream(data);
		if (!(linestream >> materialname)) {
			return false;
		}		
	}

	// second line: "( a b c d e )"
	// "( rows columns unknown unknown unknown )"
		
	if (!mapfile_ifs.getline(data, 1023)) {
		return false;
	} else {
		line_number++;
		
		std::istringstream linestream(data);
		std::string word;
		
		if (!(linestream >> word))
			return false;
		
		if (word.compare("(") != 0)
			return false;
		
		if (!(linestream >> rows >> columns))
			return false;
	}
	
	// leading line: "("
	if (!mapfile_ifs.getline(data, 1023)) {
		return false;
	} else {
		line_number++;
		
		std::istringstream linestream(data);
		std::string word;
		
		if (!(linestream >> word))
			return false;
		
		if (word.compare("(") != 0)
			return false;
	}

	// patch definitions: 
	// 'column' is the number of lines to be read
	// each line has 'row' vertices
	
	// sanity check
	if ((columns < 2) || (rows < 2) || (columns >= 1024) || (rows >= 1024)) {
		return false;
	}

	// clang doesn't like multidimensional arrays
	Matrix<math::Vector3f> patchvertices(rows, columns);
	Matrix<math::Vector2f> patchtexcoords(rows, columns);
	
	// read rows
	for (size_t r = 0; r < rows; r++) {
		if(!mapfile_ifs.getline(data, 1023)) {
			return false;
		}
		line_number++;
		
		std::istringstream linestream(data);
		std::string word;
		
		if (!(linestream >> word)) {
			//con_debug << "    Error reading row begin" << std::endl;
			return false;
		}
		
		if (word.compare("(") != 0) {
			//con_debug << "    Error reading row begin: word contains '" << word << "'" << std::endl;
			return false;
		}
		
		// read columns
		for (size_t c = 0; c < columns; c++) {
			float x, y, z, tx, ty;
			
			//con_debug << "    Reading patch row " << r << " column " << c << std::endl;
			
			if (!(linestream >> word)) {
				return false;
			}
			if (word.compare("(") != 0) {
				//con_debug << "    Error reading column begin: word contains '" << word << "'" << std::endl;
				return false;
			}
			
			if (!(linestream >> x >> y >> z >> tx >> ty)) {
				//con_debug << "    Error reading column data" << std::endl;
				return false;
			}
			
			if (!(linestream >> word)) {
				//con_debug << "    Error reading column end" << std::endl;
				return false;
			}		
			if (word.compare(")") != 0) {
				//con_debug << "    Error reading column end: word contains '" << word << "'" << std::endl;
				return false;
			}
			
			patchvertices[r][c].assign(x, y, z);
			patchtexcoords[r][c].assign(tx, ty);
		}
		
		if (!(linestream >> word)) {
			//con_debug << "    Error reading row end" << std::endl;
			return false;
		}
		if (word.compare(")") != 0) {
			//con_debug << "    Error reading row end: word contains '" << word << "'" << std::endl;
			return false;
		}
		
	}
	
	// trailing line: ")"
	if(!mapfile_ifs.getline(data, 1023)) {
		return false;
	} else {
		line_number++;
		
		std::istringstream linestream(data);
		std::string word;
		
		if (!(linestream >> word)) {
			//con_debug << "Error reading trailing line ')'" << std::endl;
			return false;
		}
		
		if (word.compare(")") != 0) {
			//con_debug << "No trailing line ')'" << std::endl;
			return false;
		}
	}
	
	// load the material for this patch
	Material *material = Material::load("textures/" + materialname);
					
	// find the primitives for the current material, 
	// allocate a new one if necessary
	Primitives *primitives = 0;

	Materials::iterator mit = map_materials.find(material);
	if (mit == map_materials.end()) {
		primitives = new Primitives(material);
		map_materials[material] = primitives;
	} else {
		primitives = (*mit).second;
	}
	
	// ignore materials with the 'Ignore' flag set
	if (material->has_flag_ignore()) {
		return true;
	}
	
	// load patch data into the model geometry
	// the patch is a set of quadratic B-splines with m = n = 2
	// see http://en.wikipedia.org/wiki/Bézier_surface
	// http://www.cc.gatech.edu/classes/AY2002/cs4451_spring/groups/group3/index.html#bpatches2
	//
	// patchvertices[][] are the control points as read from the .map file
	// mesh[][] is a subdivide X subdivide quad mesh calculated for each set of 9 control points in the patch
	
	// binomial coefficient
	const float binom[3] = {1.0f, 2.0f, 1.0f};
	const size_t subdivide_max = 4;
	
	size_t subdivide_u = 0;
	size_t subdivide_v = 0;
	
	Matrix<math::Vector3f> mesh(subdivide_max + 1, subdivide_max +1);
	Matrix<math::Vector3f> meshnormals(subdivide_max + 1, subdivide_max +1);
	Matrix<math::Vector2f> meshtexcoords(subdivide_max + 1, subdivide_max +1);
		
	for (size_t r = 0; r < rows-2; r +=2 ) {
		for (size_t c = 0; c < columns -2; c += 2) {
			
			// if columns are collinear, do not subdivide in u direction
			if (
				collinear(patchvertices[r][c], patchvertices[r+1][c], patchvertices[r+2][c]) &&
				collinear(patchvertices[r][c+1], patchvertices[r+1][c+1], patchvertices[r+2][c+1]) &&
				collinear(patchvertices[r][c+2], patchvertices[r+1][c+2], patchvertices[r+2][c+2])
			) {
				subdivide_u = 1;
			} else {
				subdivide_u = subdivide_max;
			}
			
			
			// if rows are collinear, do not subdivide in v direction
			if (
				collinear(patchvertices[r][c], patchvertices[r][c+1], patchvertices[r][c+2]) &&
				collinear(patchvertices[r+1][c], patchvertices[r+1][c+1], patchvertices[r+1][c+2]) &&
				collinear(patchvertices[r+2][c], patchvertices[r+2][c+1], patchvertices[r+2][c+2])
			) {
				subdivide_v = 1;
			} else {
				subdivide_v = subdivide_max;
			}



			for (size_t i = 0; i <= subdivide_u; i++) {
				const float u = (float) i / (float) subdivide_u;
				
				for (size_t j = 0; j <= subdivide_v; j++) {
					const float v = (float) j / (float) subdivide_v;
					math::Vector3f tan_u;
					math::Vector3f tan_v;
					
					// the surface normals aren't defined at the edges, 
					// we cheat and pull the edge points towards the middle
					float un = u;
					float vn = v;
					if ((i ==0) || (j==0) || (i == subdivide_u) || (j == subdivide_v)) {
						un = (u - 0.5f) * 0.95f + 0.5f;
						vn = (v - 0.5f) * 0.95f + 0.5f;
					}
					
					mesh[i][j].clear();
					
					for (size_t mi = 0; mi < 3; mi++) {
						for (size_t mj = 0; mj < 3; mj++) {
							mesh[i][j] +=
								patchvertices[r+mi][c+mj] * 
								binom[mi] * powf (u, (float) mi) * powf(1.0f - u, 2.0f - (float) mi) * 
								binom[mj] * powf (v, (float) mj) * powf(1.0f - v, 2.0f - (float) mj);
								
							tan_u +=
								patchvertices[r+mi][c+mj] * 
								binom[mi] * (
									((float) mi) * powf(un, (float) mi - 1.0f) * powf(1.0f - un, 2.0f - (float) mi) +
									((float) mi - 2.0f) * powf(un, (float) mi) * powf(1.0f - un, 1.0f - (float) mi)
								) *
								binom[mj] * powf (vn, (float) mj) * powf(1.0f - vn, 2.0f - (float) mj);
								
							tan_v +=
								patchvertices[r+mi][c+mj] * 
								binom[mi] * powf (un, (float) mi) * powf(1.0f - un, 2.0f - (float) mi) * 
								binom[mj] * (
									((float) mj) * powf(vn, (float) mj - 1.0f) * powf(1.0f - vn, 2.0f - (float) mj) +
									((float) mj - 2.0f) * powf(vn, (float) mj) * powf(1.0f - vn, 1.0f - (float) mj)
								);
						}
					}

					// assign normal
					meshnormals[i][j].assign(math::crossproduct(tan_u, tan_v));
					meshnormals[i][j].normalize();
					
					// calculate texture coordinates
					size_t tr = r;
					size_t tc = c;
					
					float tu = u;
					float tv = v;
					
					if (u >= 0.5f) {
						tr++;
						tu -= 0.5f;
					}
					if (v >= 0.5f) {
						tc++;
						tv -= 0.5f;
					}
					tu *= 2.0f;
					tv *= 2.0f;

					meshtexcoords[i][j] = (
						(patchtexcoords[tr+1][tc] * tu + patchtexcoords[tr][tc] * (1.0f - tu)) * (1.0f - tv) +
						(patchtexcoords[tr+1][tc+1] * tu + patchtexcoords[tr][tc+1] * (1.0f - tu)) * tv
					);

					class_box.expand(mesh[i][j] * SCALE);
				}
			}
			
			const math::Vector3f zero;
			for (size_t i = 0; i < subdivide_u; i++) {
				for (size_t j = 0; j < subdivide_v; j++) {
				
					if (material->has_flag_clip()) {
						
						// if the current material is clip, the patch needs to be converted to triangles
						if (map_load_clip) {
							Triangle *triangle = new Triangle(
								mesh[i+1][j+1] * SCALE,
								mesh[i][j+1] * SCALE,
								mesh[i][j] * SCALE);
							map_collisiontriangles.add(*triangle);
							
							triangle = new Triangle(
								mesh[i+1][j+1] * SCALE,
								mesh[i][j] * SCALE,
								mesh[i+1][j] * SCALE);
							map_collisiontriangles.add(*triangle);
						}
						
					} else {
						// not clip, convert to quads
						Quad *quad = new Quad(
								mesh[i+1][j+1] * SCALE,
								mesh[i][j+1] * SCALE,
								mesh[i][j] * SCALE,
								mesh[i+1][j] * SCALE,
								zero
						);
						
						quad->n0().assign(meshnormals[i+1][j+1]);
						quad->t0().assign(meshtexcoords[i+1][j+1]);
						
						quad->n1().assign(meshnormals[i][j+1]);
						quad->t1().assign(meshtexcoords[i][j+1]);
						
						quad->n2().assign(meshnormals[i][j]);
						quad->t2().assign(meshtexcoords[i][j]);
						
						quad->n3().assign(meshnormals[i+1][j]);
						quad->t3().assign(meshtexcoords[i+1][j]);
						
						primitives->add_quad(quad);
					}
				}
			}
		}
	}

	//con_debug << "  patchDef2 with " << columns << " columns " << rows << " rows" << std::endl;
	return true;
}

bool MapFile::getline()
{
	using math::Vector3f;

	last_read_was_classname = false;
	last_read_was_key = false;
	last_read_was_classend = false;

	key_current = "";
	value_current = "";

	if (!mapfile_ifs.is_open())
		return false;

	char data[1024];
	memset(data, 0, sizeof(data));

	if (mapfile_ifs.getline(data, 1023)) {
		line_number++;
		std::istringstream linestream(data);
		std::string firstword;

		if (linestream >> firstword) {
			if (!firstword.size()) {
				return true;

			} else if (firstword == "//") {
				return true;

			} else if (firstword == "{") {
				parse_level++;

				if ((parse_level == 3) && (in_patchdef)) {
					if (!read_patchdef()) {
						con_warn << name() << " error reading patchDef2 at line " << line_number << std::endl;
					}
				}

			} else if (firstword == "}") {

				if ((parse_level == 3) && (in_patchdef)) {
					// end-of-patchdef
					in_patchdef = false;

				} else if ((parse_level == 2) && (planes.size())) {
					// end-of-brush

					// for every face
					for (std::vector<Face *>::iterator face = planes.begin(); face != planes.end(); ++face) {
						make_brushface((*face));
					}

					// clean planes
					for (std::vector<Face *>::iterator it = planes.begin(); it != planes.end(); ++it) {
						delete(*it);
					}
					planes.clear();

					map_brushes++;

					value_current.clear();

				} else if (parse_level == 1) {
					// end-of-class
					last_read_was_classend  = true;
				}

				parse_level--;

			} else 	if (parse_level == 1) {

				if (firstword.compare("\"classname\"") == 0) {
					classname_current.clear();

					if (linestream >> classname_current) {
						if (classname_current.size() > 2) {
							classname_current.erase(0, 1);
							classname_current.erase(classname_current.size() - 1, 1);
							last_read_was_classname = true;
						} else {
							classname_current.clear();
						}
					}

				} else if ((firstword.size() > 2) && (firstword[0] == '\"') && (firstword[firstword.size()-1] == '\"')) {

					key_current.assign(firstword);
					key_current.erase(0, 1);
					key_current.erase(key_current.size() - 1, 1);

					value_current.clear();
					char c;
					while ((linestream.get(c)) && (c != '"'));
					while ((linestream.get(c)) && (c != '"'))
						value_current += c;

					last_read_was_key = true;
				}

			} else if (parse_level == 2) {

				if (firstword.compare("(") == 0) {
					// brush plane

					Vector3f p1, p2, p3;
					std::string tmp;
					std::string texture;
					int n = 0;

					linestream >> p1;  // first plane vertex x y z
					linestream >> tmp; // )
					linestream >> tmp; // (
					linestream >> p2; // second plane vertex x y z
					linestream >> tmp; // )
					linestream >> tmp; // (
					linestream >> p3; // third plane vertex x y z
					linestream >> tmp; // )

					Face *face = new Face(p1, p2, p3);

					// material
					linestream >> texture;
					aux::to_lowercase(texture);

					Material *material = Material::load("textures/" + texture);
					face->set_material(material);

					// texture alignment
					float tx, ty, tr, tsx, tsy;
					linestream >> tx >> ty;		// texture shift
					linestream >> tr;		// texture rotation angle
					linestream >> tsx >> tsy;	// texture scale

					// store the texture transformation for this face
					face_texture_verts((*face), math::Vector2f(tx, ty), tr, math::Vector2f(tsx, tsy));

					// content flags
					if (!(linestream >> n))
						n = 0;
					if (n > 0)
						face->set_detail();

					// surface flags
					if (!(linestream >> n)) {
						n = 0;
						warning_q2brush = true;
					}
					face->set_surface_flags(n);

					planes.push_back(face);

					value_current.clear();

				} else if (firstword.compare("patchDef2") == 0) {
					in_patchdef = true;
				}
			}
		}
	} else {

		return false;
	}

	return true;
}

void MapFile::make_brushface(Face *face)
{
	using math::Vector3f;

	// ignore materials with the 'Ignore' flag set
	if (face->material()->has_flag_ignore()) {
		return;
	}

	// statistics
	map_faces++;

	if (face->detail()) {
		map_faces_detail++;
	}

	// using suggestions from
	// http://www.flipcode.com/archives/Level_Editing.shtml

	// vertex list
	std::vector<math::Vector3f *> vl;

	// check if the face is x-axis oriented
	if ((fabsf(face->normal().x()) >= fabsf(face->normal().y())) && (fabsf(face->normal().x()) >=  fabsf(face->normal().z()))) {

		if (face->normal().x() > MIN_DELTA) {
			vl.push_back(new math::Vector3f(0, -MAX_BOUNDS, -MAX_BOUNDS));
			vl.push_back(new math::Vector3f(0, -MAX_BOUNDS, MAX_BOUNDS));
			vl.push_back(new math::Vector3f(0, MAX_BOUNDS, MAX_BOUNDS));
			vl.push_back(new math::Vector3f(0, MAX_BOUNDS, -MAX_BOUNDS));
		} else {
			vl.push_back(new math::Vector3f(0, MAX_BOUNDS, -MAX_BOUNDS));
			vl.push_back(new math::Vector3f(0, MAX_BOUNDS, MAX_BOUNDS));
			vl.push_back(new math::Vector3f(0, -MAX_BOUNDS, MAX_BOUNDS));
			vl.push_back(new math::Vector3f(0, -MAX_BOUNDS, -MAX_BOUNDS));
		}
		// calculate the x coordinate of each face vertex
		for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
			(*it)->get_x() = (-face->d() -
					  face->normal().z() * (*it)->z() -
					  face->normal().y() * (*it)->y()) /
					 face->normal().x();
		}
	}

	// check if the face is y-axis oriented
	else if ((fabsf(face->normal().y()) >= fabsf(face->normal().x())) && (fabsf(face->normal().y()) >=  fabsf(face->normal().z()))) {

		if (face->normal().y() > MIN_DELTA) {
			vl.push_back(new Vector3f(MAX_BOUNDS, 0, -MAX_BOUNDS));
			vl.push_back(new Vector3f(MAX_BOUNDS, 0, MAX_BOUNDS));
			vl.push_back(new Vector3f(-MAX_BOUNDS, 0, MAX_BOUNDS));
			vl.push_back(new Vector3f(-MAX_BOUNDS, 0, -MAX_BOUNDS));
		} else {
			vl.push_back(new Vector3f(-MAX_BOUNDS, 0, -MAX_BOUNDS));
			vl.push_back(new Vector3f(-MAX_BOUNDS, 0, MAX_BOUNDS));
			vl.push_back(new Vector3f(MAX_BOUNDS, 0, MAX_BOUNDS));
			vl.push_back(new Vector3f(MAX_BOUNDS, 0, -MAX_BOUNDS));
		}

		// calculate the x coordinate of each face vertex
		for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
			(*it)->get_y() = (-face->d() -
					  face->normal().z() * (*it)->z() -
					  face->normal().x() * (*it)->x()) /
					 face->normal().y();
		}
	}

	// face must be z-axis oriented
	else {

		if (face->normal().z() > MIN_DELTA) {
			vl.push_back(new Vector3f(-MAX_BOUNDS, -MAX_BOUNDS, 0));
			vl.push_back(new Vector3f(-MAX_BOUNDS, MAX_BOUNDS, 0));
			vl.push_back(new Vector3f(MAX_BOUNDS, MAX_BOUNDS, 0));
			vl.push_back(new Vector3f(MAX_BOUNDS, -MAX_BOUNDS, 0));
		} else {
			vl.push_back(new Vector3f(MAX_BOUNDS, -MAX_BOUNDS, 0));
			vl.push_back(new Vector3f(MAX_BOUNDS, MAX_BOUNDS, 0));
			vl.push_back(new Vector3f(-MAX_BOUNDS, MAX_BOUNDS, 0));
			vl.push_back(new Vector3f(-MAX_BOUNDS, -MAX_BOUNDS, 0));
		}

		// calculate the x coordinate of each face vertex
		for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
			(*it)->get_z() = (-face->d() -
					  face->normal().x() * (*it)->x() -
					  face->normal().y() * (*it)->y()) /
					 face->normal().z();
		}
	}


	// intersect the face with every plane
	for (std::vector<Face *>::iterator pit = planes.begin(); pit != planes.end(); ++pit) {

		Face *plane = (*pit);
		if (plane == face) {
			continue;
		}

		Vector3f fn = crossproduct(face->point(1) - face->point(0), face->point(2) - face->point(0));
		Vector3f pn = crossproduct(plane->point(1) - plane->point(0), plane->point(2) - plane->point(0));

		Vector3f t = crossproduct(fn, pn);
		if ((t.x() == 0)  && (t.y() == 0) && (t.z() == 0)) {
			continue;
		}

		// intersect face with plane
		for (int i = 0; vl.size() - i > 0; i++) {

			Vector3f v(*vl.at(i));

			Vector3f next;
			if (vl.size() - i > 1) {
				next = *vl.at(i + 1);
			} else {
				next = *vl.front();
			}

			Vector3f prev;
			if (i > 0) {
				prev = *vl.at(i - 1);
			} else {
				prev = *vl.back();
			}

			if ((v.x() * plane->normal().x() + v.y() * plane->normal().y() + v.z() * plane->normal().z() + plane->d()) < MIN_DELTA) {

				// find current
				std::vector<Vector3f *>::iterator vit = vl.begin();
				while ((*vit) != vl.at(i)) {
					++vit;
				}

				// check if prev - v intersects with plane
				if ((prev.x() * plane->normal().x() + prev.y() * plane->normal().y() + prev.z() * plane->normal().z() + plane->d()) > MIN_DELTA) {

					// calculate intersection
					float t1 = -plane->normal().x() * prev.x() - plane->normal().y() * prev.y() - plane->normal().z() * prev.z() - plane->d();
					float t2 = (plane->normal().x() * v.x() - plane->normal().x() * prev.x() +
						    plane->normal().y() * v.y() - plane->normal().y() * prev.y() +
						    plane->normal().z() * v.z() - plane->normal().z() * prev.z());

					Vector3f *s = new Vector3f;

					if (t2 == 0) {
						*s = v;
					} else {
						for (int j = 0; j < 3; j++)
							(*s)[j] = prev [j] + t1 * (v[j] - prev[j]) / t2;
					}

					vit = vl.insert(vit, s);
					++vit;
					i++;
				}

				// check if next - v intersects with plane
				if ((next.x() * plane->normal().x() +  next.y() * plane->normal().y() + next.z() * plane->normal().z() + plane->d()) > MIN_DELTA) {

					// calculate intersection
					float t1 = -plane->normal().x() * v.x() - plane->normal().y() * v.y() - plane->normal().z() * v.z() - plane->d();
					float t2 = (plane->normal().x() * next.x() - plane->normal().x() * v.x() +
						    plane->normal().y() * next.y() - plane->normal().y() * v.y() +
						    plane->normal().z() * next.z() - plane->normal().z() * v.z());

					Vector3f *s = new Vector3f;

					if (t2 == 0) {
						*s = v;
					} else {
						for (int j = 0; j < 3; j++)
							(*s)[j] = v [j] + t1 * (next[j] - v[j]) / t2;
					}

					vit = vl.insert(vit, s);
					++vit;
					i++;
				}

				// erase
				delete *vit;
				vl.erase(vit);
				i--;
			}

		}
	}

	if (vl.size() > 2) {

		// find the list if primitives for the current material, allocate a new one if necessary
		Primitives *primitives = 0;

		Materials::iterator mit = map_materials.find(face->material());
		if (mit == map_materials.end()) {
			primitives = new Primitives(face->material());
			map_materials[face->material()] = primitives;
		} else {
			primitives = (*mit).second;
		}

		if (face->material()->has_flag_origin()) {
			// add vertices to the origin list
			for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
				class_origin_vertices.push_back(new math::Vector3f((*(*it) * SCALE)));
			}
			
		} else if (face->material()->has_flag_bounds()) {
			// add vertices to the bounds list
			for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
				map_bounds_vertices.push_back(new math::Vector3f((*(*it) * SCALE)));
			}
		} else {
		
			// add vertices to the bounding box
			for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
				class_box.expand(*(*it) * SCALE);
			}

			// the actual polygon normal is on the other side
			Vector3f face_normal(face->normal()* -1);
			face_normal.normalize();

			// clip faces have to be triangulated and can not be split into quads
			if (!face->material()->has_flag_clip()) {
				
				// split polygon into quads
				while (vl.size() > 3) {
					std::vector<Vector3f *>::iterator v0 = vl.begin();
					std::vector<Vector3f *>::reverse_iterator vn = vl.rbegin();
					std::vector<Vector3f *>::reverse_iterator vn1 = vl.rbegin();
					++vn1;
					std::vector<Vector3f *>::reverse_iterator vn2 = vl.rbegin();
					++vn2;
					++vn2;

					Quad *quad = new Quad(*(*vn2) * SCALE, *(*vn1) * SCALE, *(*vn) * SCALE, *(*v0) * SCALE, face_normal, face->detail());
					primitives->add_quad(quad);

					quad->t0().assign(map_texture_coords(face, *(*vn2)));
					quad->t1().assign(map_texture_coords(face, *(*vn1)));
					quad->t2().assign(map_texture_coords(face, *(*vn)));
					quad->t3().assign(map_texture_coords(face, *(*v0)));

					delete(*vn);
					delete(*vn1);
					vl.pop_back();
					vl.pop_back();
				}
			}
			
			// split polygon into triangles
			while (vl.size() > 2) {
				std::vector<Vector3f *>::iterator v0 = vl.begin();
				std::vector<Vector3f *>::reverse_iterator vn = vl.rbegin();
				std::vector<Vector3f *>::reverse_iterator vn1 = vl.rbegin();
				++vn1;

				Triangle * triangle = new Triangle(*(*vn1) * SCALE, *(*vn) * SCALE, *(*v0) * SCALE, face_normal, face->detail());
				primitives->add_triangle(triangle);

				triangle->t0().assign(map_texture_coords(face, *(*vn1)));
				triangle->t1().assign(map_texture_coords(face, *(*vn)));
				triangle->t2().assign(map_texture_coords(face, *(*v0)));
				
				delete(*vn);
				vl.pop_back();
			}
		}
		
	} else {
		con_warn << name() << " unresolved brush face at line " << line() << std::endl;
	}

	// clean up the vertex list
	for (std::vector<Vector3f *>::iterator it = vl.begin(); it != vl.end(); ++it) {
		delete(*it);
	}

	vl.clear();
}

bool MapFile::got_key_string(const char * keylabel, std::string & valuestring)
{
	if (last_read_was_key && (key_current.compare(keylabel) == 0)) {
		valuestring.assign(value_current);
		return true;
	} else {
		return false;
	}
}

bool MapFile::got_key_vector3f(const char * keylabel, math::Vector3f & v)
{
	if (last_read_was_key && (key_current.compare(keylabel) == 0)) {
		std::istringstream is(value_current);
		float x, y, z;
		if ((is >> x) && (is >> y) && (is >> z)) {
			v = math::Vector3f(x, y, z);
		} else {
			v = math::Vector3f();
		}
		return true;
	} else {
		return false;
	}
}

bool MapFile::got_key_float(const char * keylabel, float & f)
{
	if (last_read_was_key && (key_current.compare(keylabel) == 0)) {
		std::istringstream is(value_current);
		if (!(is >> f)) {
			f = 0;
		}
		return true;
	} else {
		return false;
	}
}

bool MapFile::got_key_int(const char * keylabel, unsigned int & u)
{
	if (last_read_was_key && (key_current.compare(keylabel) == 0)) {
		std::istringstream is(value_current);
		if (!(is >> u)) {
			u = 0;
		}
		return true;
	} else {
		return false;
	}
}

bool MapFile::got_key(const char * keylabel)
{
	return (last_read_was_key && (key_current.compare(keylabel) == 0));
}

bool MapFile::got_key_angle(const char * keylabel, float & f)
{
	if (last_read_was_key && (key_current.compare(keylabel) == 0)) {
		std::istringstream is(value_current);
		if ((is >> f)) {
			f = math::degrees360f(f);
		} else {
			f = 0;
		}
		return true;
	} else {
		return false;
	}
}

bool MapFile::got_key_color(const char * keylabel, math::Color & color)
{
	if (last_read_was_key && (key_current.compare(keylabel) == 0)) {
		std::istringstream is(value_current);
		float r, g, b;
		if ((is >> r) && (is >> g) && (is >> b)) {
			if ((r > 1) || (g > 1) || (b > 1)) {
				r /= 255;
				g /= 255;
				b /= 255;
			}
			color = math::Color(r, g, b);
		} else {
			color = math::Color();
		}
		return true;
	} else {
		return false;
	}
}

bool MapFile::got_key_axis(math::Axis &axis)
{
	float pitch, yaw, roll = 0.0f;
	
	if (got_key_float("angle", yaw)) {
				
		if (yaw == ANGLEUP) {
			axis.change_pitch(-90.0f);
		} else if (yaw == ANGLEDOWN) {
			axis.change_pitch(90.0f);
		} else {
			axis.change_direction(yaw);
		}		
		return true;
		
	} else if (got_key("angles")) {
		
		std::istringstream str(value());
		if (str >> pitch >> yaw >> roll) {
			axis.assign(yaw, pitch, roll);
		} else {
			unknown_value();
		}		
		return true;

	} else if (got_key_float("pitch", pitch)) {
		axis.change_pitch(-pitch);	
		return true;

	} else if (got_key_float("yaw", yaw)) {
		axis.change_direction(yaw);
		return true;

	} else if (got_key_float("roll", roll)) {
		axis.change_roll(-roll);
		return true;
	}
	
	return false;
}

void MapFile::close()
{
	mapfile_ifs.close();
}

void MapFile::clear_bbox()
{
	class_box.assign(MAX_BOUNDS, -MAX_BOUNDS);
	class_axis.clear();
	class_speed = 0;
	class_distance = 0;
	class_engine = false;
}

void MapFile::load_fragmentgroup(Model *model, const FragmentGroup::Type class_type)
{
	if (!map_materials.size())
		return;
		
	// expand bounding box
	map_box.expand(class_box);
	
	// special groups like func_door and func_group are re-centered	
	math::Vector3f translation((class_box.min() + class_box.max()) * 0.5f);
	
	FragmentGroup *group = new FragmentGroup();
	group->set_location(translation);
	group->set_type(class_type);
	
	// these fragmentgroups are on the same level as worldspawn (no submodels)
	// their rotation axis is always identity
	
	switch (class_type) {
		case FragmentGroup::None:
			break;
			
		case FragmentGroup::Rotate:
			if (class_speed == 0) {
				// default rotation speed 45 degrees per second
				class_speed = 45.0f;
			}
			group->set_speed(class_speed);
			group->set_engine(class_engine);
			group->set_movement(class_axis.forward());
			
			// origin bruhes override group center
			if (class_origin_vertices.size()) {
				math::Vector3f v;
				for (std::vector<math::Vector3f *>::iterator i = class_origin_vertices.begin(); i != class_origin_vertices.end(); ++i) {
					v += *(*i);
				}
				
				v /= (float) class_origin_vertices.size();
				translation.assign(v);
				group->set_location(translation);
			}
			break;
			
		case FragmentGroup::Move:
			group->set_speed(class_speed);
			group->set_distance(class_distance);
			group->set_engine(class_engine);
			group->set_movement(class_axis.forward());
			break;
			
		case FragmentGroup::Door:
			group->set_speed(class_speed);
			break;
	}

	for (Materials::iterator mit = map_materials.begin(); mit != map_materials.end(); ++mit) {
		// split the Primitives with this material into fragments
		Primitives *primitives = (*mit).second;

		// store triangles
		if (primitives->triangles().size()) {
			
			if (primitives->material()->has_flag_clip()) {
				
				if (map_load_clip) {
					// clip materials are loaded into the CollisionMesh
					for (Primitives::Triangles::iterator tris_it = primitives->triangles().begin(); tris_it != primitives->triangles().end(); ++tris_it) {
						Triangle *triangle = (*tris_it);
						//model->collisionmesh()->add_triangle(triangle->v0(), triangle->v1(), triangle->v2());
						map_collisiontriangles.add(*triangle);
					}
				}
				
			} else if (VertexArray::instance() && !VertexArray::instance()->overflow()) {
				
				Fragment *fragment = new Fragment(Fragment::Triangles, primitives->material());

				// add structural triangles to the fragment
				for (Primitives::Triangles::iterator tris_it = primitives->triangles().begin(); tris_it != primitives->triangles().end(); ++tris_it) {
					Triangle  *triangle = (*tris_it);
					if (!triangle->detail()) {
						size_t count = 0;
						count += fragment->add_vertex(triangle->v0() - translation, triangle->normal(), triangle->t0(), false);
						count += fragment->add_vertex(triangle->v1() - translation, triangle->normal(), triangle->t1(), false);
						count += fragment->add_vertex(triangle->v2() - translation, triangle->normal(), triangle->t2(), false);
						if (count == 3)
							model->model_tris_count++;
					}
				}

				// add detail triangles to the fragment
				for (Primitives::Triangles::iterator tris_it = primitives->triangles().begin(); tris_it != primitives->triangles().end(); ++tris_it) {
					Triangle  *triangle = (*tris_it);
					if (triangle->detail()) {
						size_t count = 0;
						count += fragment->add_vertex(triangle->v0() - translation, triangle->normal(), triangle->t0(), true);
						count += fragment->add_vertex(triangle->v1() - translation, triangle->normal(), triangle->t1(), true);
						count += fragment->add_vertex(triangle->v2() - translation, triangle->normal(), triangle->t2(), true);
						if (count == 3) {
							model->model_tris_count++;
							model->model_tris_detail_count++;
						}
					}
				}

				// add the fragment to the group
				group->add_fragment(fragment);
			}
		}

		// store quads
		if (primitives->quads().size()) {
			
			if (VertexArray::instance() && !VertexArray::instance()->overflow()) {
				
				Fragment *fragment = new Fragment(Fragment::Quads, primitives->material());

				// add structural quads to the fragment
				for (Primitives::Quads::iterator quad_it = primitives->quads().begin(); quad_it != primitives->quads().end(); ++quad_it) {
					Quad *quad = (*quad_it);
					if (!quad->detail()) {
						size_t count = 0;
						count += fragment->add_vertex(quad->v0() - translation, quad->n0(), quad->t0(), false);
						count += fragment->add_vertex(quad->v1() - translation, quad->n1(), quad->t1(), false);
						count += fragment->add_vertex(quad->v2() - translation, quad->n2(), quad->t2(), false);
						count += fragment->add_vertex(quad->v3() - translation, quad->n3(), quad->t3(), false);
						if (count == 4) {
							model->model_quad_count++;
						}
					}
				}

				// add detail quads to the fragment
				for (Primitives::Quads::iterator quad_it = primitives->quads().begin(); quad_it != primitives->quads().end(); ++quad_it) {
					Quad *quad = (*quad_it);
					if (quad->detail()) {
						size_t count = 0;
						count += fragment->add_vertex(quad->v0() - translation, quad->n0(), quad->t0(), true);
						count += fragment->add_vertex(quad->v1() - translation, quad->n1(), quad->t1(), true);
						count += fragment->add_vertex(quad->v2() - translation, quad->n2(), quad->t2(), true);
						count += fragment->add_vertex(quad->v3() - translation, quad->n3(), quad->t3(), true);
						if (count == 4) {
							model->model_quad_count++;
							model->model_quad_detail_count++;
						}
					}
				}

				// add the fragment to the group
				group->add_fragment(fragment);
			}
		}

	}

	// add the vertexgroup to the model
	model->add_group(group);
	
	// load collision triangles into a mesh
	if (map_load_clip) {	
		if (map_collisiontriangles.size()) {	
			CollisionMesh *collisionmesh = new CollisionMesh();
			
			// add clip triangles to collision mesh
			for (TriangleList::iterator it = map_collisiontriangles.begin(); it != map_collisiontriangles.end(); ++it) {
				Triangle *triangle = (*it);
				collisionmesh->add_triangle(triangle->v0() - translation, triangle->v1() - translation, triangle->v2() - translation);
			}

			// apply vertexgroup params to the collision mesh
			collisionmesh->set_location(translation);
			collisionmesh->set_type(class_type);
			
			// these fragmentgroups are on the same level as worldspawn (no submodels)
			// their rotation axis is always identity
			
			switch (class_type) {
				case FragmentGroup::None:
					break;
					
				case FragmentGroup::Rotate:
					if (class_speed == 0) {
						// default rotation speed 45 degrees per second
						class_speed = 45.0f;
					}
					collisionmesh->set_speed(class_speed);
					collisionmesh->set_movement(class_axis.forward());
					break;
					
				case FragmentGroup::Move:
					collisionmesh->set_speed(class_speed);
					collisionmesh->set_distance(class_distance);
					collisionmesh->set_movement(class_axis.forward());
					break;
					
				case FragmentGroup::Door:
					collisionmesh->set_speed(class_speed);
					break;
			}
			
			// add the collision mesh to the collision model
			model->collisionmodel()->add_mesh(collisionmesh);
		}
	}

}

void MapFile::unknown_value() const
{
	con_warn << name() << " unknown value '" << value() << "' for '" << classname() << ":" << key() << "' at line " << line() << std::endl;
}

void MapFile::unknown_key() const
{
	con_warn << name() << " unknown key '" << classname() << ":" << key() << "' at line " << line() << std::endl;
}

void MapFile::unknown_class() const
{
	con_warn << name() << " unknown class '" << classname() << "' at line " << line() << std::endl;
}

void MapFile::warn_depricated() const
{
	con_warn << name() << " depricated key '" << key() << "' for '" << classname() << "' at line " << line() << std::endl;
}

void MapFile::unknown_error(const char *text) const
{
	con_warn << name() << " " << (text && text[0] ? text : "unknown error") << " at line " << line() << std::endl;
}

void MapFile::unknown_error(const std::string &text) const
{
	con_warn << name() << " " << text << " at line " << line() << std::endl;
}


Model * MapFile::load(std::string const &name)
{
	// open the .map file
	MapFile mapfile;

	if (!mapfile.open(name)) {
		return 0;
	}

	Model *model = new Model(name);
	mapfile.clear_bbox();

	Slot *tag_slot = 0;
	Particles *tag_particles = 0;
	Flare *tag_flare = 0;
	Light *tag_light = 0;
	SubModel *tag_submodel = 0;
	Sound *tag_sound = 0;

	std::string modelname;
	math::Vector3f location;
	math::Color color;

	typedef std::list<SubModel *> SubModelList;
	SubModelList submodel_list;

	unsigned int u;
	float r, s;
	std::string str;
	
	// load clip into collision meshes
	// if the model has been loaded before (e.g. on r_restart), the collision model won't be reloaded 
	mapfile.map_collisionmodel = CollisionModel::find(name);
	if (!mapfile.map_collisionmodel) {
		mapfile.map_load_clip = true;		
		mapfile.map_collisionmodel = new CollisionModel(name);
		CollisionModel::add(mapfile.map_collisionmodel);
	} else {
		mapfile.map_load_clip = false;
	}
	model->set_collisionmodel(mapfile.map_collisionmodel);
	
	while (mapfile.getline()) {
		if (mapfile.got_classname("worldspawn")) {
			mapfile.clear_bbox();

		} else if (mapfile.got_classend("worldspawn")) {
			mapfile.load_fragmentgroup(model, FragmentGroup::None);
			mapfile.clear_materials();

		} else if (mapfile.in_class("worldspawn")) {

			// worldspawn attributes
			if (mapfile.got_key("name")) {
				//con_debug << "  model name '" << name << "'" << std::endl;
				continue;

			} else if (mapfile.got_key_int("enginesound", u)) {
				model->model_enginesound = u;
				continue;

			} else if (mapfile.got_key_int("impulsesound", u)) {
				model->model_impulsesound = u;
				continue;

			} else if (mapfile.got_key_color("enginecolor", model->model_enginecolor)) {
				continue;

			} else if (mapfile.got_key()) {
				mapfile.unknown_key();

			}

		} else if (mapfile.got_classname("func_door")) {
			mapfile.clear_bbox();

		} else if (mapfile.got_classend("func_door")) {
			mapfile.load_fragmentgroup(model, FragmentGroup::Door);
			mapfile.clear_materials();

		} else if (mapfile.in_class("func_door")) {

		} else if (mapfile.got_classname("func_group")) {
			mapfile.clear_bbox();

		} else if (mapfile.got_classend("func_group")) {
			mapfile.load_fragmentgroup(model, FragmentGroup::None);
			mapfile.clear_materials();

		} else if (mapfile.got_classname("func_move")) {
			mapfile.clear_bbox();
			
		} else if (mapfile.got_classend("func_move")) {
			mapfile.load_fragmentgroup(model, FragmentGroup::Move);
			mapfile.clear_materials();
			
		} else if (mapfile.in_class("func_move")) {

			if (mapfile.got_key_axis(mapfile.class_axis)) {
				continue;
						
			} else if (mapfile.got_key_int("spawnflags", u)) {
				mapfile.class_engine  = spawnflag_isset(u, 4);
				continue;
				
			} else if (mapfile.got_key_float("speed", s)) {
				mapfile.class_speed = s * SCALE;
				continue;
				
			} else if (mapfile.got_key_float("distance", s)) {
				mapfile.class_distance = s * SCALE;
				continue;

			} else if (mapfile.got_key()) {
				mapfile.unknown_key();
			}

		} else if (mapfile.got_classname("func_rotate")) {
			mapfile.clear_bbox();

		} else if (mapfile.got_classend("func_rotate")) {
			mapfile.load_fragmentgroup(model, FragmentGroup::Rotate);
			mapfile.clear_materials();

		} else if (mapfile.in_class("func_rotate")) {

			if (mapfile.got_key_axis(mapfile.class_axis)) {
				continue;
						
			} else if (mapfile.got_key_int("spawnflags", u)) {
				mapfile.class_engine  = spawnflag_isset(u, 4);
				continue;
				
			} else if (mapfile.got_key_float("speed", s)) {
				mapfile.class_speed = s;
				continue;

			} else if (mapfile.got_key()) {
				mapfile.unknown_key();
			}

		} else if (mapfile.got_classend()) {
			mapfile.clear_materials();

		} else if (mapfile.got_classname("light")) {

			// new light tag
			tag_light = new Light();
			model->add_light(tag_light);
			continue;

		} else if (mapfile.classname().compare("light") == 0) {

			// light attributes
			if (mapfile.got_key_vector3f("origin", location)) {
				tag_light->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_color("_color", color)) {
				tag_light->set_color(color);
				continue;

			} else if (mapfile.got_key_int("spawnflags", u)) {
				tag_light->set_strobe(spawnflag_isset(u, 1));
				tag_light->set_entity(spawnflag_isset(u, 2));
				tag_light->set_engine(spawnflag_isset(u, 4));
				tag_light->set_entity_second(spawnflag_isset(u, 8));
				continue;

			} else if (mapfile.got_key_float("light", r)) {
				tag_light->set_radius(r * SCALE);
				continue;

			} else if (mapfile.got_key_float("radius", r)) {
				tag_light->set_radius(r * SCALE);
				continue;

			} else if (mapfile.got_key_float("frequency", r)) {
				tag_light->set_frequency(r);
				continue;

			} else if (mapfile.got_key_float("offset", r)) {
				tag_light->set_offset(r);
				continue;

			} else if (mapfile.got_key_float("time", r)) {
				tag_light->set_time(r);
				continue;

			}  else if (mapfile.got_key_int("flare", u)) {
				tag_light->set_flare(u);
				continue;
				
			} else if (mapfile.got_key_string("info", str)) {
				tag_light->set_info(str);

			} else if (mapfile.got_key()) {
				mapfile.unknown_key();
				continue;

			}

		} else if (mapfile.got_classname("fx_flare")) {

			// new flare tag
			tag_flare = new Flare();
			model->add_flare(tag_flare);

		} else if (mapfile.classname().compare("fx_flare") == 0) {

			// flare attributes
			if (mapfile.got_key_axis(tag_flare->get_axis())) {
				continue;
				
			} else if (mapfile.got_key_vector3f("origin", location)) {
				tag_flare->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_color("_color", color)) {
				tag_flare->set_color(color);
				continue;

			} else if (mapfile.got_key_int("spawnflags", u)) {
				tag_flare->set_strobe(spawnflag_isset(u, 1));
				tag_flare->set_entity(spawnflag_isset(u, 2));
				tag_flare->set_engine(spawnflag_isset(u, 4));
				tag_flare->set_entity_second(spawnflag_isset(u, 8));

			} else if (mapfile.got_key_float("light", r)) {
				tag_flare->set_radius(r * SCALE);
				continue;

			} else if (mapfile.got_key_float("radius", r)) {
				tag_flare->set_radius(r * SCALE);
				continue;

			} else if (mapfile.got_key_float("frequency", r)) {
				tag_flare->set_frequency(r);
				continue;

			} else if (mapfile.got_key_float("offset", r)) {
				tag_flare->set_offset(r);
				continue;

			} else if (mapfile.got_key_float("time", r)) {
				tag_flare->set_time(r);
				continue;

			}  else if (mapfile.got_key_int("flare", u)) {
				tag_flare->set_flare(u);
				continue;

			} else if (mapfile.got_key_string("cull", str)) {

				aux::to_lowercase(str);
				if (str.compare("none") == 0) {
					tag_flare->set_cull(CullNone);
				} else if (str.compare("back") == 0) {
					tag_flare->set_cull(CullBack);
				} else if (str.compare("front") == 0) {
					tag_flare->set_cull(CullFront);
				} else {
					mapfile.unknown_value();
				}
				
			} else if (mapfile.got_key_string("info", str)) {
				tag_flare->set_info(str);

			} else if (mapfile.got_key()) {
				mapfile.unknown_key();
			}

		} else if (mapfile.got_classname("fx_particles")) {

			// new particle system tag
			tag_particles = new Particles();
			model->add_particles(tag_particles);

		} else if (mapfile.classname().compare("fx_particles") == 0) {

			// particle system attributes
			if (mapfile.got_key_axis(tag_particles->get_axis())) {
				continue;
				
			} else if (mapfile.got_key_vector3f("origin", location)) {
				tag_particles->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_color("_color", color)) {
				tag_particles->set_color(color);
				continue;
				
			}  else if (mapfile.got_key_string("script", str)) {
				tag_particles->set_script(str);
				continue;

			} else if (mapfile.got_key_int("spawnflags", u)) {
				tag_particles->set_entity(spawnflag_isset(u, 2));
				tag_particles->set_engine(spawnflag_isset(u, 4));
				tag_particles->set_entity_second(spawnflag_isset(u, 8));

			} else if (mapfile.got_key_float("scale", s)) {
				tag_particles->set_scale(s);
				
			} else if (mapfile.got_key_string("info", str)) {
				tag_particles->set_info(str);

			} else if (mapfile.got_key()) {
				mapfile.unknown_key();
			}

		} else if (mapfile.got_classname("fx_sound")) {
			
			// new sound tag
			tag_sound = new Sound();
			model->add_sound(tag_sound);

		} else if (mapfile.classname().compare("fx_sound") == 0) {

			// sound attributes
 			if (mapfile.got_key_vector3f("origin", location)) {
	        		tag_sound->get_location().assign(location * SCALE);
				continue;
				
			}  else if (mapfile.got_key_string("name", str)) {
				// remove sounds/ prefix
				if (str.substr(0, 7).compare("sounds/") == 0)
					str.erase(0, 7);
				// remove extension
				if (str[str.size()-4] == '.') {
					str.erase(str.size() - 4);
				}
				tag_sound->set_name(str);
				continue;
				
			}  else if (mapfile.got_key_string("noise", str)) {
				// remove sounds/ prefix
				if (str.substr(0, 7).compare("sounds/") == 0)
					str.erase(0, 7);
				// remove extension
				if (str[str.size()-4] == '.') {
					str.erase(str.size() - 4);
				}
				tag_sound->set_name(str);
				continue;
			
			} else if (mapfile.got_key("angle")) {
				continue;
				
			} else if (mapfile.got_key("angles")) {
				continue;
				
			} else if (mapfile.got_key_string("info", str)) {
				tag_sound->set_info(str);
				
			} else if (mapfile.got_key()) {
				mapfile.unknown_key();

			}

		} else if (mapfile.got_classname("misc_model")) {

			// new submodel tag
			tag_submodel = new SubModel();
			submodel_list.push_back(tag_submodel);

		} else if (mapfile.classname().compare("misc_model") == 0) {

			// submodel attributes
			if (mapfile.got_key_axis(tag_submodel->get_axis())) {
				continue;
				
			} else if (mapfile.got_key_vector3f("origin", location)) {
				tag_submodel->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_string("model", modelname)) {
				// remove extension
				if (modelname[modelname.size()-4] == '.') {
					modelname.erase(modelname.size() - 4);
				}
				tag_submodel->set_name(modelname);
				continue;

			} else if (mapfile.got_key_float("modelscale", s)) {
				if (s) {
					tag_submodel->set_scale(s);
				} else {
					tag_submodel->set_scale(1.0f);
				}
			
			} else if (mapfile.got_key_string("info", str)) {
				tag_submodel->set_info(str);
				
			} else if (mapfile.got_key()) {
				mapfile.unknown_key();

			}

		} else if (mapfile.got_classname("location_dock")) {

			// new docking location
			tag_slot = new Slot(Slot::Dock);
			model->add_slot(tag_slot);

		} else if (mapfile.classname().compare("location_dock") == 0) {

			// dock attributes
			if (mapfile.got_key_axis(tag_slot->get_axis())) {
				continue;
				
			} else if (mapfile.got_key_vector3f("origin", location)) {
				tag_slot->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_float("radius", r)) {
				tag_slot->set_radius(r * SCALE);
				continue;
			
			} else if (mapfile.got_key_string("info", str)) {
				tag_slot->set_info(str);
				
			} else if (mapfile.got_key()) {
				mapfile.unknown_key();

			}

		} else if (mapfile.got_classname("location_cannon")) {
			
			// new cannon slot
			tag_slot = new Slot(Slot::Cannon);
			model->add_slot(tag_slot);
			continue;

		} else if (mapfile.classname().compare("location_cannon") == 0) {

			// cannon options
			if (mapfile.got_key_axis(tag_slot->get_axis())) {
				continue;
				
			} else if (mapfile.got_key_vector3f("origin", location)) {
				tag_slot->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_float("cone", r)) {
				tag_slot->set_cone(r);
				continue;
				
			} else if (mapfile.got_key_string("info", str)) {
				tag_slot->set_info(str);
				
			} else if (mapfile.got_key()) {
				mapfile.unknown_key();

			}
			continue;

		} else if (mapfile.got_classname("location_turret")) {
			
			// new turret slot
			tag_slot = new Slot(Slot::Turret);
			model->add_slot(tag_slot);
			continue;

		} else if (mapfile.classname().compare("location_turret") == 0) {
			
			// turret options
			if (mapfile.got_key_axis(tag_slot->get_axis())) {
				continue;
				
			} else if (mapfile.got_key_vector3f("origin", location)) {
				tag_slot->get_location().assign(location * SCALE);
				continue;

			} else if (mapfile.got_key_float("cone", r)) {
				tag_slot->set_cone(r);
				continue;
				
			} else if (mapfile.got_key_string("info", str)) {
				tag_slot->set_info(str);
				
			} else if (mapfile.got_key()) {
				mapfile.unknown_key();

			}
			continue;

		} else if (mapfile.got_classname("location_cockpit")) {
			// TODO cockpit location
			continue;

		} else if (mapfile.classname().compare("location_cockpit") == 0) {
			// TODO cockpit options
			continue;

		} else if (mapfile.got_classname()) {

			mapfile.unknown_class();
		}
	}

	mapfile.close();

	for (SubModelList::iterator smit = submodel_list.begin(); smit != submodel_list.end(); ++smit) {
		tag_submodel = (*smit);
		Model *submodel_model = 0;

		if (tag_submodel->name().size()) {
			submodel_model = Model::load(tag_submodel->name());
		} else {
			con_warn << "  invalid misc_model '" << tag_submodel->name() << "'" << std::endl;
			continue;
		}

		if (submodel_model) {
			// skip empty submodels
			if (!submodel_model->groups().size()) {
				con_warn << "  ignoring empty misc_model '" << tag_submodel->name() << "'" << std::endl;
				continue;
			}
				
			// adjust the submodel bounding box to its origin
			const math::Vector3f min((submodel_model->model_box.min() - submodel_model->origin()) * tag_submodel->scale());
			const math::Vector3f max((submodel_model->model_box.max() - submodel_model->origin()) * tag_submodel->scale());
			
			math::Vector3f cube[8];
			cube[0].assign(min.x(), min.y(), min.z());
			cube[1].assign(min.x(), max.y(), min.z());
			cube[2].assign(max.x(), min.y(), min.z());
			cube[3].assign(max.x(), max.y(), min.z());
			
			cube[4].assign(min.x(), min.y(), max.z());
			cube[5].assign(min.x(), max.y(), max.z());
			cube[6].assign(max.x(), min.y(), max.z());
			cube[7].assign(max.x(), max.y(), max.z());
			
			for (size_t i = 0; i < 8; i++) {
				// rotate the bounding box around the submodel origin
				mapfile.map_box.expand(tag_submodel->location() + tag_submodel->axis() * cube[i]);
			}
			
			// copy fragmentgroups	
			for (Model::Groups::iterator git = submodel_model->groups().begin(); git != submodel_model->groups().end(); ++git) {
				FragmentGroup *groupsrc = (*git);
				FragmentGroup *groupdst = new FragmentGroup();
				
				groupdst->set_type(groupsrc->type());
				groupdst->set_scale(groupsrc->scale() * tag_submodel->scale());
				groupdst->set_engine(groupsrc->engine());
				groupdst->set_speed(groupsrc->speed());
				groupdst->set_movement(groupsrc->movement());
				groupdst->set_distance(groupsrc->distance());
								
				groupdst->set_location(tag_submodel->location() + tag_submodel->axis() * (groupsrc->location() - submodel_model->origin()) * tag_submodel->scale());				
				groupdst->set_axis(tag_submodel->axis() * groupsrc->axis());
				
				// copy fragments, this only copies the original fragment's pointer into the vertex array
				for (FragmentGroup::Fragments::const_iterator fit = groupsrc->fragments().begin(); fit != groupsrc->fragments().end(); ++fit) {
						
					Fragment *fragmentdst = new Fragment(*(*fit));
					groupdst->add_fragment(fragmentdst);
					
					switch (fragmentdst->type()) {
						case Fragment::Triangles:
							model->model_tris_count += (fragmentdst->structural_size() + fragmentdst->detail_size()) / 3;
							model->model_tris_detail_count  += fragmentdst->detail_size() / 3;
							break;
						case Fragment::Quads:
							model->model_quad_count += (fragmentdst->structural_size() + fragmentdst->detail_size()) / 4;
							model->model_quad_detail_count  += fragmentdst->detail_size() / 4;
							break;
					}
				}

				if (groupdst->size()) {
					model->add_group(groupdst);
				} else {
					delete groupdst;
				}
			}
			
			// import submodel collisionmodel meshes
			if (mapfile.map_load_clip && submodel_model->collisionmodel())  {
				for (CollisionModel::CollisionMeshes::iterator cmit = submodel_model->collisionmodel()->meshes().begin();
				     cmit != submodel_model->collisionmodel()->meshes().end(); ++cmit) {
					
					CollisionMesh *meshsrc = (*cmit);
					CollisionMesh *meshdst = new CollisionMesh(*meshsrc);
					
					meshdst->set_type(meshsrc->type());
					meshdst->set_scale(meshsrc->scale() * tag_submodel->scale());
									
					meshdst->set_location(tag_submodel->location() + tag_submodel->axis() * (meshsrc->location() - submodel_model->origin()) * tag_submodel->scale());				
					meshdst->set_axis(tag_submodel->axis() * meshsrc->axis());
					
					model->collisionmodel()->add_mesh(meshdst);
				}
			}

			// copy light tags
			for (Model::Lights::const_iterator lit = submodel_model->lights().begin(); lit != submodel_model->lights().end(); ++lit) {
				tag_light = new Light(*(*lit));
				tag_light->get_location().assign(tag_submodel->location() + tag_submodel->axis() * (tag_light->location() - submodel_model->origin()) * tag_submodel->scale());
				tag_light->set_radius(tag_light->radius() * tag_submodel->scale());
				model->add_light(tag_light);
			}

			// copy flare tags
			for (Model::Flares::const_iterator flit = submodel_model->flares().begin(); flit != submodel_model->flares().end(); ++flit) {
				tag_flare = new Flare(*(*flit));
				tag_flare->get_location().assign(tag_submodel->location() + tag_submodel->axis() * (tag_flare->location() - submodel_model->origin()) * tag_submodel->scale());
				tag_flare->set_axis(tag_submodel->axis() * tag_flare->axis());
				tag_flare->set_radius(tag_flare->radius() * tag_submodel->scale());
				model->add_flare(tag_flare);
			}

			// copy particle system tags
			for (Model::ParticleSystems::const_iterator pit = submodel_model->particles().begin(); pit != submodel_model->particles().end(); ++pit) {
				tag_particles = new Particles(*(*pit));
				tag_particles->get_location().assign(tag_submodel->location() + tag_submodel->axis() * (tag_particles->location() - submodel_model->origin()) * tag_submodel->scale());
				tag_particles->set_axis(tag_submodel->axis() * tag_particles->axis());
				tag_particles->set_scale(tag_particles->scale() * tag_submodel->scale());
				model->add_particles(tag_particles);
			}

			// copy sound tags
			for (Model::Sounds::const_iterator sit = submodel_model->sounds().begin(); sit != submodel_model->sounds().end(); ++sit) {
				tag_sound = new Sound(*(*sit));
				tag_sound->get_location().assign(tag_submodel->location() + tag_submodel->axis() * (tag_sound->location() - submodel_model->origin()) * tag_submodel->scale());
				model->add_sound(tag_sound);
			}
			
			// copy slot tags
			for (Model::Slots::const_iterator slit = submodel_model->slots().begin(); slit != submodel_model->slots().end(); ++slit) {
				tag_slot = new Slot(*(*slit));
				tag_slot->get_location().assign(tag_submodel->location() + tag_submodel->axis() * (tag_slot->location() - submodel_model->origin()) * tag_submodel->scale());
				tag_slot->set_axis(tag_submodel->axis() * tag_slot->axis());
				model->add_slot(tag_slot);
			}
		}
		
		delete tag_submodel;
	}		
	
	// center model around (0,0,0) and set the bounding box	
	if (mapfile.map_bounds_vertices.size()) {
		
		// bounds vertices override the calculated box
		mapfile.map_box.assign(MAX_BOUNDS, -MAX_BOUNDS);
		for (std::vector<math::Vector3f *>::iterator bvit = mapfile.map_bounds_vertices.begin(); bvit != mapfile.map_bounds_vertices.end(); ++bvit) {
			mapfile.map_box.expand(*(*bvit));
		}
	}
	
	math::Vector3f map_center = (mapfile.box().min() + mapfile.box().max()) * 0.5f;
	model->model_box.assign(
		mapfile.box().min() - map_center,
		mapfile.box().max() - map_center
	);

	model->set_radius(model->box().max().length());
	model->set_origin(map_center * -1.0f);
	
	// translate transformed vertex groups
	size_t frags = 0;
	for (Model::Groups::iterator git = model->groups().begin(); git != model->groups().end(); ++git) {
		FragmentGroup *fragmentgroup = (*git);
		fragmentgroup->set_location(fragmentgroup->location() - map_center);
		frags += fragmentgroup->size();
	}
	
	// set a sane radius if the mapfile is empty
	if (frags == 0) {
		const float r = SCALE;
		model->model_box.assign(
			math::Vector3f(-r, -r, -r), 
			math::Vector3f(r, r, r)

		);
		model->set_radius(model->box().max().length());
	}

	
	// translate tags
	for (Model::Lights::iterator lit = model->lights().begin(); lit != model->lights().end(); ++lit) {
		(*lit)->get_location() -= map_center;
	}

	for (Model::Flares::iterator flit = model->flares().begin(); flit != model->flares().end(); ++flit) {
		(*flit)->get_location() -= map_center;
	}

	for (Model::ParticleSystems::iterator pit = model->particles().begin(); pit != model->particles().end(); ++pit) {
		(*pit)->get_location() -= map_center;
	}

	for(Model::Sounds::iterator sit = model->sounds().begin(); sit != model->sounds().end(); ++sit) {
		(*sit)->get_location() -= map_center;
	}

	for (Model::Slots::iterator slit = model->slots().begin(); slit != model->slots().end(); ++slit) {
		(*slit)->get_location() -= map_center;
	}
		
	if (mapfile.warning_q2brush)
		con_warn <<  mapfile.name() << " quake2 style brushes detected" << std::endl;

	con_debug << "  " << mapfile.name() << " " << mapfile.map_brushes << " brushes " <<
		model->model_tris_count << " triangles " <<
		model->model_quad_count << " quads" << std::endl;

	if (mapfile.map_load_clip && model->collisionmodel() && model->collisionmodel()->meshes().size()) {
		size_t collision_tris_count = 0; // total number of triangles in the collision model
		size_t collision_mesh_count = 0; // number of meshes in the collision model
		
		for (CollisionModel::CollisionMeshes::const_iterator cmit = model->collisionmodel()->meshes().begin(); 
		     cmit != model->collisionmodel()->meshes().end(); ++cmit) {
			collision_tris_count += (*cmit)->size();
			collision_mesh_count++;
			
			// translate collision meshes
			(*cmit)->set_location((*cmit)->location() - map_center);
		}
		
		con_debug << "  " << mapfile.name() << " collision " << collision_tris_count << " triangles " << collision_mesh_count << " meshes" << std::endl;
	}
	
	return model;
}

}