#include "stdafx.h"

#include <map>
#include <set>

#include "BaseMesh.h"

#include "../Algorithm/Geom3d.h"



namespace lib_geo
{


//! 全バッファをクリア
void BaseMesh::Clear(void)
{
	m_Verts.clear();
	m_Normals.clear();
	m_UVs.clear();
	m_Tangents.clear();

	m_Faces.clear();
	m_Edges.clear();
	m_Polylines.clear();

	m_Materials.clear();
}


//! 1頂点1法線となるように法線バッファを生成する
void BaseMesh::CreateNormalsEachVerts(bool resetSmooth)
{
	m_Normals.clear();
	m_Normals.resize(m_Verts.size());

	SyncFaceVidToNid();

	if (resetSmooth)
		UpdateNormal();
}

void BaseMesh::SyncFaceVidToNid(void)
{
	for (BaseFace& f : m_Faces)
	{
		f.m_NormIds = f.m_VertIds;
	}
}

void BaseMesh::SyncFaceVidToUVid(void)
{
	for (BaseFace& f : m_Faces)
	{
		f.m_UVIds = f.m_VertIds;
	}
}

void BaseMesh::CreateUVsEachVerts(void)
{
	m_UVs.assign(m_Verts.size(), lm::vec2f::get_zero());
	SyncFaceVidToUVid();
}

//! 法線を更新する
void BaseMesh::UpdateNormal(void)
{
	ResetNormalToZero();

	for (const BaseFace& f : m_Faces)
	{
		if (!f.HasNormal())
			continue;

		for (size_t j = 0; j < f.NumTriangles(); ++j)
		{
			lm::vec3f n = CalcFaceNormal(f, 0, j+1, j+2);

			m_Normals[f.m_NormIds[0  ]] += n;
			m_Normals[f.m_NormIds[j+1]] += n;
			m_Normals[f.m_NormIds[j+2]] += n;
		}
	}

	NormalizeNormal();
}

void BaseMesh::ResetNormalToZero(void)
{
	for (size_t i = 0; i < m_Normals.size(); ++i)
		m_Normals[i].set(0.0f, 0.0f, 0.0f);
}

void BaseMesh::NormalizeNormal(void)
{
	for (size_t i = 0; i < m_Normals.size(); ++i)
		m_Normals[i].normalize();
}


//! ポリゴンの構造からエッジバッファを生成する
void BaseMesh::CreateEdgeFromFace(void)
{
	m_Edges.clear();

	std::vector< std::set<int> > VertLinks(m_Verts.size());
	for (const BaseFace& f : m_Faces)
	{
		for( size_t j = 0 ; j < f.NumVertices() ; ++j )
		{
			int edge_vid0 = f.m_VertIds[ j ];
			int edge_vid1 = f.m_VertIds[ (j+1) % f.NumVertices() ];
			if( edge_vid0 > edge_vid1 )
				std::swap( edge_vid0 , edge_vid1 );

			VertLinks[edge_vid0].insert( edge_vid1 );
		}
	}

	for (size_t i = 0; i < VertLinks.size(); ++i)
	{
		for( std::set<int>::iterator iter = VertLinks[i].begin() ; iter != VertLinks[i].end() ; ++iter )
		{
			BaseEdge e;
			e.m_EdgeVids[0] = (int)i;
			e.m_EdgeVids[1] = *iter;
			m_Edges.push_back( e );
		}
	}
}

void BaseMesh::CreateTangentsByUV(void)
{
	m_Tangents.clear();
	m_Tangents.resize(m_UVs.size(), lm::vec3f::get_zero());

	for (size_t i = 0; i < m_Faces.size(); ++i)
	{
		const lib_geo::BaseFace& f = m_Faces[i];

		if( !f.HasUV() )
			continue;

		size_t polygon_size = f.m_UVIds.size();

		for(size_t j = 0; j < polygon_size; ++j)
		{
			size_t idx0 = j;
			size_t idx1 = (j+1) % polygon_size;

			int uvid0 = f.m_UVIds[idx0];
			int uvid1 = f.m_UVIds[idx1];
			int vid0 = f.m_VertIds[idx0];
			int vid1 = f.m_VertIds[idx1];
			int nid0 = f.m_NormIds[idx0];

			lm::vec3f& p0 = m_Verts[vid0];
			lm::vec3f& p1 = m_Verts[vid1];
			lm::vec2f& uv0 = m_UVs[uvid0];
			lm::vec2f& uv1 = m_UVs[uvid1];

			lm::vec2f d_2d = (uv1 - uv0).get_normalize();

			lm::vec3f& nrm_3d = m_Normals[nid0];
			lm::vec3f tan_3d = (p1 - p0).get_normalize();
			lm::vec3f bin_3d = lm::cross(tan_3d, nrm_3d).get_normalize();
			tan_3d = lm::cross(nrm_3d, bin_3d).get_normalize();

			lm::vec3f dst_t = tan_3d * d_2d.x + bin_3d * d_2d.y;

			m_Tangents[uvid0] += dst_t;
		}
	}

	for (size_t i = 0; i < m_UVs.size(); ++i)
	{
		m_Tangents[i].normalize();
	}
}

void BaseMesh::ClearAllAdjBuffer(void)
{
	m_VertAdj.clear();
	m_VertAdj.resize(m_Verts.size());

	for (BaseEdge& e : m_Edges)
	{
		e.ClearAdjBuffer();
	}

	for (BaseFace& f : m_Faces)
	{
		f.ClearAdjBuffer();
	}
}

//! 各種隣接情報の再生成
void BaseMesh::CreateAdjBuffers(void)
{
	ClearAllAdjBuffer();

	SetAdj_VtoF();

	if (!m_Edges.empty())
	{
		SetAdj_VtoE();
		SetAdj_EtoF();
	}

	UpdateAdjVertNormal();
}

void BaseMesh::SetAdj_VtoF(void)
{
	for (size_t i = 0; i < m_Faces.size(); ++i)
	{
		BaseFace& f = m_Faces[i];
		for (size_t j = 0; j < f.m_VertIds.size(); ++j)
		{
			VertAdj& va = m_VertAdj[f.m_VertIds[j]];
			va.m_AdjFids.push_back((int)i);
		}
	}
}

void BaseMesh::SetAdj_VtoE(void)
{
	for (size_t i = 0; i < m_Edges.size(); ++i)
	{
		BaseEdge& e = m_Edges[i];
		for (int j = 0; j < 2; ++j)
		{
			int avid = e.m_EdgeVids[j];
			if (avid < 0)
				continue;

			VertAdj& va = m_VertAdj[avid];
			va.m_AdjEids.push_back((int)i);
		}
	}
}

void BaseMesh::SetAdj_EtoF(void)
{
	std::vector< std::vector<BaseEdge*> > EidMap(m_Verts.size());
	for (size_t i = 0; i < m_Edges.size(); ++i)
	{
		BaseEdge& e = m_Edges[i];
		int eid = (int)i;

		int vid0 = e.m_EdgeVids[0];
		int vid1 = e.m_EdgeVids[1];
		if (vid0 > vid1)
			std::swap(vid0, vid1);

		EidMap[vid0].push_back(&e);
	}

	for (size_t i = 0; i < m_Faces.size(); ++i)
	{
		BaseFace& f = m_Faces[i];
		int fid = (int)i;

		size_t NumFVerts = f.m_VertIds.size();
		for (size_t j = 0; j < NumFVerts; ++j)
		{
			int vid0 = f.m_VertIds[j];
			int vid1 = f.m_VertIds[(j + 1) % NumFVerts];
			if(vid0 > vid1)
				std::swap(vid0, vid1);

			std::vector<BaseEdge*>& va_edges = EidMap[vid0];
			BaseEdge* adj_e = NULL;
			for (BaseEdge* ae : va_edges)
			{
				int ve0 = ae->m_EdgeVids[0];
				int ve1 = ae->m_EdgeVids[1];
				if (ve0 > ve1)
					std::swap(ve0, ve1);

				if (vid0 != ve0)
					continue;
				if (vid1 != ve1)
					continue;

				adj_e = ae;
				break;
			}

			if (adj_e == NULL)
				continue;

			int eid = adj_e - &m_Edges[0];

			f.m_AdjEids.push_back(eid);

			adj_e->m_AdjFids.push_back(fid);
		}
	}
}

void BaseMesh::UpdateAdjVertNormal(void)
{
	for (size_t i = 0; i < m_VertAdj.size(); ++i)
	{
		m_VertAdj[i].m_NormalAvg.set(0.0f, 0.0f, 0.0f);
	}

	for (const BaseFace& f : m_Faces)
	{
		for (size_t j = 0; j < f.NumTriangles(); ++j)
		{
			lm::vec3f n = CalcFaceNormal(f, 0, j+1, j+2);

			m_VertAdj[f.m_VertIds[0  ]].m_NormalAvg += n;
			m_VertAdj[f.m_VertIds[j+1]].m_NormalAvg += n;
			m_VertAdj[f.m_VertIds[j+2]].m_NormalAvg += n;
		}
	}

	for (size_t i = 0; i < m_VertAdj.size(); ++i)
	{
		lm::vec3f& n = m_VertAdj[i].m_NormalAvg;
		if (!n.is_zero())
			n.normalize();
	}
}

//! AABBを求める
lm::range3f BaseMesh::CalcAABB(void) const
{
	lm::range3f aabb;
	aabb.clear();

	for (size_t i = 0; i < m_Verts.size(); ++i)
	{
		aabb.expand(m_Verts[i]);
	}

	return aabb;
}


//! 全ポリゴンを三角化する.
void BaseMesh::Triangulate(void)
{
	size_t TotalTriangles = NumTriangles();
	if (TotalTriangles == m_Faces.size())
		return;

	std::vector<BaseFace> NewFaces;
	NewFaces.reserve(TotalTriangles);
	for (size_t i = 0; i < m_Faces.size(); ++i)
	{
		BaseFace& f = m_Faces[i];
		if (f.NumTriangles() == 1)
		{
			NewFaces.push_back(f);
			continue;
		}

		for (size_t j = 0 ; j < f.NumTriangles(); ++j)
		{
			int sub_vid0 = 0;
			int sub_vid1 = (int)j + 1;
			int sub_vid2 = (int)j + 2;

			BaseFace new_face;
			f.CopySubTriangle(new_face, sub_vid0, sub_vid1, sub_vid2);

			NewFaces.push_back(new_face);
		}
	}

	m_Faces.swap(NewFaces);

	if (HasEdge())
		CreateEdgeFromFace();

	if (HasVertAdj())
		CreateAdjBuffers();
}


//! 未使用頂点バッファを切り詰める.
void BaseMesh::RemoveNotReferencedVertex(void)
{
	// TODO : m_Tangentは未対応

	std::vector<bool> VertRef, NormalRef, UVRef;
	GetReferencedVertMap(VertRef, NormalRef, UVRef);

	size_t VidCount = 0;
	std::vector<int> NewVertIdx(m_Verts.size(), -1);
	for (size_t i = 0; i < VertRef.size(); ++i)
	{
		if( VertRef[i] )
			NewVertIdx[i] = (int)VidCount++;
	}

	size_t NidCount = 0;
	std::vector<int> NewNormalIdx(m_Normals.size(), -1);
	for (size_t i = 0; i < NormalRef.size(); ++i)
	{
		if (NormalRef[i])
			NewNormalIdx[i] = (int)NidCount++;
	}

	size_t UidCount = 0;
	std::vector<int> NewUVIdx( m_UVs.size() , -1 );
	for (size_t i = 0; i < UVRef.size(); ++i)
	{
		if (UVRef[i])
			NewUVIdx[i] = (int)UidCount++;
	}

	if (VidCount != m_Verts.size())
	{
		for (size_t i = 0; i < NewVertIdx.size(); ++i)
		{
			int idx = NewVertIdx[i];
			if (idx < 0 || (int)i == idx)
				continue;

			m_Verts[idx] = m_Verts[i];
		}
		m_Verts.resize(VidCount);
	}

	if (NidCount != m_Normals.size())
	{
		for (size_t i = 0; i < NewNormalIdx.size(); ++i)
		{
			int idx = NewNormalIdx[i];
			if (idx < 0 || (int)i == idx)
				continue;

			m_Normals[idx] = m_Normals[i];
		}
		m_Normals.resize(NidCount);
	}

	if (UidCount != m_UVs.size())
	{
		for (size_t i = 0; i < NewUVIdx.size(); ++i)
		{
			int idx = NewUVIdx[i];
			if (idx < 0 || (int)i == idx)
				continue;

			m_UVs[idx] = m_UVs[i];
		}
		m_UVs.resize(UidCount);
	}

	for (size_t i = 0; i < m_Faces.size(); ++i)
	{
		BaseFace& face = m_Faces[i];
		for (size_t j = 0; j < face.m_VertIds.size(); ++j)
		{
			face.m_VertIds[j] = NewVertIdx[face.m_VertIds[j]];
		}

		for (size_t j = 0; j < face.m_NormIds.size(); ++j)
		{
			face.m_NormIds[j] = NewNormalIdx[face.m_NormIds[j]];
		}

		for (size_t j = 0; j < face.m_UVIds.size(); ++j)
		{
			face.m_UVIds[j] = NewUVIdx[face.m_UVIds[j]];
		}
	}

	for (BaseEdge& edge : m_Edges)
	{
		edge.m_EdgeVids[0] = NewVertIdx[edge.m_EdgeVids[0]];
		edge.m_EdgeVids[1] = NewVertIdx[edge.m_EdgeVids[1]];
	}

	for (BasePolyline& pl : m_Polylines)
	{
		for (int& vid : pl.m_PLVids)
		{
			vid = NewVertIdx[vid];
		}
	}
}

// 修正前のメッシュで使用されていた頂点を求める
void BaseMesh::GetReferencedVertMap(std::vector<bool>& VertRef, std::vector<bool>& NormalRef, std::vector<bool>& UVRef) const
{
	VertRef.resize( m_Verts.size() , false );
	NormalRef.resize( m_Normals.size() , false );
	UVRef.resize( m_UVs.size() , false );

	for (const BaseFace& face : m_Faces)
	{
		for( size_t j = 0 ; j < face.m_VertIds.size() ; ++j )
		{
			VertRef[ face.m_VertIds[j] ] = true;
		}

		for( size_t j = 0 ; j < face.m_NormIds.size() ; ++j )
		{
			NormalRef[ face.m_NormIds[j] ] = true;
		}

		for( size_t j = 0 ; j < face.m_UVIds.size() ; ++j )
		{
			UVRef[ face.m_UVIds[j] ] = true;
		}
	}

	for (const BasePolyline& pl : m_Polylines)
	{
		for( size_t j = 0; j < pl.m_PLVids.size(); ++j )
		{
			VertRef[ pl.m_PLVids[j] ] = true;
		}
	}
}


//! 隣接頂点の結合
void BaseMesh::RemDoubleVertex(void)
{
	// 実装中	
}


void BaseMesh::Translate(const lm::vec3f& v)
{
	for (lm::vec3f& v : m_Verts)
	{
		v += v;
	}
}

void BaseMesh::Translate(float x , float y , float z)
{
	for (lm::vec3f& v : m_Verts)
	{
		v.set(v.x + x, v.y + y, v.z + z);
	}
}

void BaseMesh::Scale(float s)
{
	for (lm::vec3f& v : m_Verts)
	{
		v *= s;
	}
}

void BaseMesh::Scale(float sx , float sy , float sz)
{
	for (lm::vec3f& v : m_Verts)
	{
		v.set(v.x * sx, v.y * sy, v.z * sz);
	}
}

void BaseMesh::RotateX(float angle)
{
	for (lm::vec3f& v : m_Verts)
		v.rotate_x(angle);
}

void BaseMesh::RotateY(float angle)
{
	for (lm::vec3f& v : m_Verts)
		v.rotate_y(angle);
}

void BaseMesh::RotateZ(float angle)
{
	for (lm::vec3f& v : m_Verts)
		v.rotate_z(angle);
}

void BaseMesh::Rotate(const lm::vec3f& axis, float angle)
{
	for (lm::vec3f& v : m_Verts)
		v.rotate(angle, axis);
}


size_t BaseMesh::NumTriangles(void) const
{
	size_t n = 0;
	for (const BaseFace& f : m_Faces)
	{
		n += f.NumTriangles();
	}

	return n;
}


void BaseMesh::CalcNormalEachVerts(std::vector<lm::vec3f>& normals) const
{
	normals.clear();
	normals.resize( m_Verts.size() , lm::vec3f(0.0f, 0.0f, 0.0f) );

	for (const BaseFace& f : m_Faces)
	{
		for (size_t j = 0; j < f.NumTriangles(); ++j)
		{
			int vid0 = f.m_VertIds[0  ];
			int vid1 = f.m_VertIds[j+1];
			int vid2 = f.m_VertIds[j+2];
			const lm::vec3f& v0 = m_Verts[vid0];
			const lm::vec3f& v1 = m_Verts[vid1];
			const lm::vec3f& v2 = m_Verts[vid2];

			lm::vec3f n = cross(v1 - v0, v2 - v0);
			normals[vid0] += n;
			normals[vid1] += n;
			normals[vid2] += n;
		}
	}

	for( size_t i = 0 ; i < normals.size() ; ++i )
		normals[i].normalize();
}


lm::vec3f BaseMesh::GetFaceCenter(const size_t face_idx) const
{
	return GetFaceCenter(m_Faces[face_idx]);
}

lm::vec3f BaseMesh::GetFaceCenter(const BaseFace& f) const
{
	lm::vec3f c(0.0f, 0.0f, 0.0f);
	for (size_t j = 0; j < f.m_VertIds.size(); ++j)
	{
		c += m_Verts[f.m_VertIds[j]];
	}

	c /= (float)f.m_VertIds.size();

	return c;
}

lm::vec3f BaseMesh::GetFaceNormal(const BaseFace& f) const
{
	lm::vec3f n(0.0f, 0.0f, 0.0f);
	for (size_t i = 0; i < f.NumTriangles(); ++i)
	{
		n += CalcFaceNormal(f, 0, i + 1, i + 2);
	}

	return n.get_normalize();
}

lm::vec3f BaseMesh::CalcFaceNormal(const BaseFace& f, int lvid0, int lvid1, int lvid2) const
{
	const lm::vec3f& v0 = m_Verts[f.m_VertIds[lvid0]];
	const lm::vec3f& v1 = m_Verts[f.m_VertIds[lvid1]];
	const lm::vec3f& v2 = m_Verts[f.m_VertIds[lvid2]];

	return cross(v1 - v0, v2 - v0);
}


void BaseMesh::MergeLinkedPolylines(void)
{
	for(;;)
	{
		bool updated = false;

		for(size_t i = 0; i < m_Polylines.size(); ++i)
		{
			for(size_t j = i + 1; j < m_Polylines.size(); ++j)
			{
				BasePolyline& p0 = m_Polylines[i];
				BasePolyline& p1 = m_Polylines[j];

				if(p0.m_PLVids.back() == p1.m_PLVids.front())
				{
				}
				else if(p0.m_PLVids.back() == p1.m_PLVids.back())
				{
					std::reverse(p1.m_PLVids.begin(), p1.m_PLVids.end());
				}
				else if(p0.m_PLVids.front() == p1.m_PLVids.front())
				{
					std::reverse(p0.m_PLVids.begin(), p0.m_PLVids.end());
				}
				else if(p0.m_PLVids.front() == p1.m_PLVids.back())
				{
					std::reverse(p0.m_PLVids.begin(), p0.m_PLVids.end());
					std::reverse(p1.m_PLVids.begin(), p1.m_PLVids.end());
				}
				else
				{
					continue;
				}

				for(size_t k = 1; k < p1.m_PLVids.size(); ++k)
				{
					p0.m_PLVids.push_back(p1.m_PLVids[k]);
				}

				m_Polylines.back().Swap(p1);
				m_Polylines.pop_back();

				--j;
				updated = true;
			}
		}

		if(!updated)
			break;
	}
}


bool BaseMesh::GetClosestSubfacePos(const lm::vec3f& pos, SubfaceIdx& sf, lm::vec3f& close_pos) const
{
	sf.Reset();
	close_pos.set(0.0f, 0.0f, 0.0f);
	float close_dsq = (std::numeric_limits<float>::max)();

	for (size_t i = 0; i < m_Faces.size(); ++i)
	{
		const BaseFace& f = m_Faces[i];
		size_t num_t = f.NumTriangles();
		for (size_t j = 0; j < num_t; ++j)
		{
			const lm::vec3f& v0 = m_Verts[f.m_VertIds[0]];
			const lm::vec3f& v1 = m_Verts[f.m_VertIds[1 + j]];
			const lm::vec3f& v2 = m_Verts[f.m_VertIds[2 + j]];

			lm::vec3f cp = Geom3d::Closest_Triangle_Point(v0, v1, v2, pos);
			float dsq = (cp - pos).square_length();
			if (dsq < close_dsq)
			{
				close_dsq = dsq;
				sf.Set((int)i, (int)j);
				close_pos = cp;
			}
		}
	}

	return sf.IsValid();
}

bool BaseMesh::CalcBaryCoordMain(const lm::vec3f& pos, size_t fid, size_t subface, float& u, float& v, float& w) const
{
	assert(fid < m_Faces.size());
	if (fid > m_Faces.size())
		return false;

	const BaseFace& f = m_Faces[fid];
	assert(subface < f.NumTriangles());
	if (subface >= f.NumTriangles())
		return false;

	const lm::vec3f& v0 = m_Verts[f.m_VertIds[0]];
	const lm::vec3f& v1 = m_Verts[f.m_VertIds[subface + 1]];
	const lm::vec3f& v2 = m_Verts[f.m_VertIds[subface + 2]];

	lm::vec3f vp0 = pos - v0;
	lm::vec3f vp1 = pos - v1;
	lm::vec3f vp2 = pos - v2;
	lm::vec3f refN = cross(v1 - v0, v2 - v0).get_normalize();

	u = dot(cross(vp1, vp2), refN);
	v = dot(cross(vp2, vp0), refN);
	w = dot(cross(vp0, vp1), refN);

	float t = u + v + w;
	if (t <= 0.0f)
	{
		u = 1.0f / 3.0f;
		v = 1.0f / 3.0f;
		w = 1.0f / 3.0f;
	}
	else
	{
		u /= t;
		v /= t;
		w /= t;
	}

	return true;
}

bool BaseMesh::CalcBaryCoord(const lm::vec3f& pos, size_t fid, size_t subface, float& u, float& v, float& w) const
{
	return CalcBaryCoordMain(pos, fid, subface, u, v, w);
}

bool BaseMesh::CalcBaryCoord(const lm::vec3f& pos, size_t fid, size_t subface, lm::vec3f& bc) const
{
	return CalcBaryCoordMain(pos, fid, subface, bc.x, bc.y, bc.z);
}

bool BaseMesh::CalcBaryCoord(const lm::vec3f& pos, size_t fid, size_t subface, BaryCoord& bc) const
{
	bc.Reset();

	if (!CalcBaryCoordMain(pos, fid, subface, bc.Bary.x, bc.Bary.y, bc.Bary.z))
		return false;

	bc.Subface.Set((int)fid, (int)subface);

	return true;
}

lm::vec3f BaseMesh::GetPosFromBaryCoord(const BaryCoord& bc) const
{
	const BaseFace& f = m_Faces[bc.Subface.fid];

	const lm::vec3f& v0 = m_Verts[f.m_VertIds[0]];
	const lm::vec3f& v1 = m_Verts[f.m_VertIds[1 + bc.Subface.subface]];
	const lm::vec3f& v2 = m_Verts[f.m_VertIds[2 + bc.Subface.subface]];

	return v0 * bc.Bary.x + v1 * bc.Bary.y + v2 * bc.Bary.z;
}


void BaseMesh::CopySwap(BaseMesh& m)
{
	m_Verts     .swap( m.m_Verts     );
	m_Normals   .swap( m.m_Normals   );
	m_UVs       .swap( m.m_UVs       );
	m_Tangents  .swap( m.m_Tangents  );
	m_VertAdj   .swap( m.m_VertAdj   );
	m_Faces     .swap( m.m_Faces     );
	m_Edges     .swap( m.m_Edges     );
	m_Polylines .swap( m.m_Polylines );
	m_Materials .swap( m.m_Materials );
}

void BaseMesh::ApplyTransform(const lm::matrix4f& m)
{
	for (lm::vec3f& v : m_Verts)
	{
		v = v * m;
	}

	lm::vec3f to = lm::vec3f(0, 0, 0) * m;
	for (lm::vec3f& n : m_Normals)
	{
		n = n * m - to;
		n.normalize();
	}
}


}
