任意阶拼图游戏及自动求解算法

附送一份3D模型切割算法，方便制作3D版拼图游戏：

//========================================================
//  @Date:     2016.05
//  @File:     Include/Render/ReproductMesh.h
//  @Brief:     ReproductMesh
//  @Author:     LouLei
//  @Email:  twopointfive@163.com
//  @Copyright (Crapell) - All Rights Reserved
//========================================================

#pragma once

#ifndef  __ReproductMesh__H__
#define  __ReproductMesh__H__

//#include "Math/Mathlib.h"
#include "Render/RendDriver.h"
#include 

class TopoSegment;
class TopoVertex;
class TopoFace;
class TopoVertexSet;
class TopoVertexPtrSet;
class TopoFaceSet;
class Sloid;
class TVertex;

class Box;

//typedef unsigned int IndexInt;
static const float   _ModellerEpsilon    = 0.001f;//1e-6f;

class TVertex
{
public:
	float u;
	float v;
	float w;
	float r;
	float g;
	float b;
};

class Line3D
{
public:
	Line3D();
	Line3D(TopoFace * face1, TopoFace * face2);
	Line3D(const vec3 & direction, const vec3 & point);

	//!到参考点的有向距离
	float getPointToPointDistance(const vec3 & otherPoint);
	//!线段交点
	vec3  getLineIntersection(Line3D * otherLine);
	//!线面相交
	vec3  getPlaneIntersection(const vec3 & normal, const vec3 & planePoint, bool & bResult);

	void  perturbDirection();

	vec3 m_pos;
	vec3 m_dir;
};

class TopoSegment
{
public:
	TopoSegment();
	TopoSegment(Line3D & line, TopoFace & face, int sign1, int sign2, int sign3);

	enum Status
	{
		VERTEX = 1,
		FACE = 2,
		EDGE = 3,
	};
	//!起点状态：在面的端点上还是边上或面上
	int startType;
	//!中段状态：在面的边上或面上
	int middleType;
	//!结束点状态
	int endType;

	/** nearest vertex from the starting point */
	TopoVertex * startVertex;
	TopoVertex * endVertex; 

	//!两个面的交线
	vec3 startPos;
	vec3 endPos;
	//!两个面的交线
	Line3D line;
	//
	int endsNum;

	/** distance from the segment starting point to the point defining the plane */
	float startDist;
	float endDist;

	bool intersect(const TopoSegment & segment);

private:
	bool setVertex(TopoVertex * vertex);
	bool setEdge(TopoVertex * vertex1, TopoVertex * vertex2);
	void swapEnds();
};


class TopoVertex
{
public:
	enum Status
	{
		UNKNOWN = 1,
		INSIDE = 2,
		OUTSIDE = 3,
		BOUNDARY = 4,
	};

	TopoVertex();
	TopoVertex(const TopoVertex & v);
	TopoVertex(const vec3 & position, const TVertex & tVertex, Status eStatus);
	virtual ~TopoVertex();
	TopoVertex & operator=(const TopoVertex & v);

	bool equals(TopoVertex * vertex);
	void addAdjacentVertex(TopoVertex * adjacentVertex);

	void mark(Status eStatus);
	TopoVertexPtrSet * m_adjacentVertices;	

	vec3     pos;
	TVertex  tVertex;
	Status   status;
	
};

class TopoFace
{
public:
	enum Status
	{
		UNKNOWN     = 1,
		INSIDE      = 2,//被切割sloid的面 包含于 切割sloid的内部
		OUTSIDE     = 3,//外部
		SAME        = 4,//被切割sloid的面 共面于 切割sloid的某个面
		OPPOSITE    = 5,//被切割sloid的面 反共面于 切割sloid的某个面
	};
	TopoFace();
	TopoFace(const TopoFace & v);
	TopoFace(TopoVertex * v1, TopoVertex * v2, TopoVertex * v3);
	~TopoFace();
	TopoFace& operator=(const TopoFace & face);
	bool  equals_pointersmatch(TopoFace * pFace);
	bool  equals(TopoFace * pOtherObject);
	//!预计算提高速度，不会失效
	Box*  getBound();
	vec3& getNormal();
	float getArea();

	void invert();

	bool simpleClassify();
	void rayTraceClassify(Sloid & object);

	//!判断点在面内
	bool hasPoint(const vec3 & point);

	Status status;
	Box*   bound;
	vec3   normal;
	TopoVertex * v1;
	TopoVertex * v2;
	TopoVertex * v3;
};


class TopoVertexPtrSet
{
public:
	TopoVertexPtrSet();
	virtual ~TopoVertexPtrSet();

	TopoVertex * GetTopoVertexPtr(int nIndex);
	void AddTopoVertexPtr(TopoVertex * pPointer);
	int  GetTopoVertexPtrNum();
	void ClearTopoVertexPtr();
	TopoVertex* operator[](int index);

private:
	typedef std::vector Vertices;
	Vertices m_pPointers;
};

class TopoVertexSet
{
public:
	TopoVertexSet();
	virtual ~TopoVertexSet();

	TopoVertex * GetTopoVertex(int nIndex);
	TopoVertex * AddTopoVertex(const TopoVertex & vertex);
	int GetTopoVertexNum();

	TopoVertex& operator[](int index);

	bool HasTopoVertex(TopoVertex * pVertex);
	int  IndexOfTopoVertex(TopoVertex * pVertex);
	void ClearTopoVertex();

private:
	typedef std::vector Vertices;
	Vertices m_pVertices;
};

class TopoFaceSet
{
public:
	TopoFaceSet();
	virtual ~TopoFaceSet();

	TopoFace * GetTopoFace(int i);
	void       SetTopoFace(int i, TopoFace & vFace);
	TopoFace * AddTopoFace(TopoFace & vFace);
	TopoFace * InsertTopoFace(int i, TopoFace & vFace);
	void       RemoveTopoFace(int i);

	int  GetTopoFaceNum();
	void ClearTopoFace();

private:

	TopoFace * m_pFaces;
	int m_nMaxSize;
	int m_nSize;
};


//==================^_^==================^_^==================^_^==================^_^

class Sloid
{
public:
	Sloid();
	virtual ~Sloid();

	//!使用object来切分自身
	void SplitFaces(Sloid * pObject);
	void Translate(const vec3 & t);
	void Render();
	void RefMesh(RendSys::Mesh* mesh);

//private:

	TopoFace*   AddTopoFace(TopoVertex * v1, TopoVertex * v2, TopoVertex * v3);
	TopoVertex* AddTopoVertex(const vec3 & pos, const TVertex & tVertex, int status);

	float ComputeDistance(TopoVertex & vertex, TopoFace & face);

	void SplitFace(int faceIndex, TopoSegment & segment1, TopoSegment & segment2);
	  
	//插值纹理坐标
	void CalTopoVertexTex(TopoVertex * v1, TopoVertex * v2,const vec3 & pos, TopoVertex * result);
	void CalTopoVertexTex(TopoVertex * v1, TopoVertex * v2,TopoVertex * v3,const vec3 & pos, TopoVertex * result);

	//一个三角形切割为2、3、4、5个
	void BreakFaceInTwo(int faceIndex, const vec3 & newPos, int splitEdge);
	void BreakFaceInTwo(int faceIndex, const vec3 & newPos, TopoVertex & endVertex);
	void BreakFaceInThree(int faceIndex, const vec3 & newPos1, const vec3 & newPos2, TopoVertex & startVertex, TopoVertex & endVertex);
	void BreakFaceInThree(int faceIndex, const vec3 & newPos1, const vec3 & newPos2, int splitEdge);
	void BreakFaceInThree(int faceIndex, const vec3 & newPos, TopoVertex & endVertex);
	void BreakFaceInThree(int faceIndex, const vec3 & newPos);
	void BreakFaceInFour (int faceIndex, const vec3 & newPos1, const vec3 & newPos2, TopoVertex & endVertex);
	void BreakFaceInFive (int faceIndex, const vec3 & newPos1, const vec3 & newPos2, int linedVertex);
	
	//!标记面在切割sloid的内部还是外部..
	void ClassifyFaces(Sloid & pObject);
	//!反转内部面，减法使用
	void InvertInsideFaces();

	void GenTopologyFromRend();
	void GenRendFromTopology();
	void Free();
	TopoVertexSet * m_topoVertexs;
	TopoFaceSet *   m_topoFaces;
	Box *           m_bound;


	int m_indexNum;
	int m_vVertexNum;
	int m_tVertexNum;

	//Vertex*  m_vVertexs;
	//TVertex* m_tVertexs;
	//Trigon*  m_trigons;

	IndexInt* m_indexs;
	vec3*     m_vertexs;
	TVertex*  m_tVertexs;

};

//==================^_^==================^_^==================^_^==================^_^
//!注意所有面逆时针顺序要统一
class BooleanModeller
{
public:
	Sloid * m_pSloid1;
	Sloid * m_pSloid2;
	//!注意初始化后原来的solid topology已经被分割了，可能需要重新GenTopologyData
	BooleanModeller(Sloid * solid1, Sloid * solid2);

	Sloid * GetUnion();
	Sloid * GetIntersection();
	Sloid * GetDifference();

private:
	void    MergeSloid(Sloid* pSrcSloid, Sloid* pDstSloid, int faceStatus1, int faceStatus2);
	void    PreMergeSloid(Sloid* pSrcSloid, Sloid* pDstSloid, int faceStatus1, int faceStatus2);
};

#endif

//========================================================
//  @Date:     2016.05
//  @File:     SourceLib/Render/ReproductMesh.cpp
//  @Brief:     ReproductMesh
//  @Author:     LouLei
//  @Email:  twopointfive@163.com
//  @Copyright (Crapell) - All Rights Reserved
//========================================================
 
#include "General/Pch.h"
#include "General/General.h"
#include "Render/MC_Misc.h"
#include "Render/MC_MovieClip.h"
#include "Render/MC_Boolean.h"
#include "Math/MathLibAdvance.h"
#include "Ozcollide/box.h"
#include "General/Pce.h"

//constructive solid geometry modeller

#pragma warning(disable : 4244)
#pragma warning(disable: 4305)

Line3D::Line3D()
{
	m_pos = vec3(0,0,0);
	m_dir = vec3(1,0,0);
}

Line3D::Line3D(const vec3 & directioni, const vec3 & pointi)
{
	m_dir = directioni;
	m_dir.Normalize();
	m_pos = pointi;
}

Line3D::Line3D(TopoFace * face1, TopoFace * face2)
{
	vec3 normalFace1 = face1->getNormal();
	vec3 normalFace2 = face2->getNormal();

	m_dir = Cross(normalFace1, normalFace2);

	//m_direction长度为0，则两个面平行
	if (!(m_dir.Length()<_ModellerEpsilon))
	{
		//getting a line point, zero is set to a coordinate whose direction 
		//component isn't zero (line intersecting its origin plan)
		float d1 = -normalFace1.Dot(face1->v1->pos);
		float d2 = -normalFace2.Dot(face2->v1->pos);
		if(fabs(m_dir.x)>_ModellerEpsilon)
		{
			m_pos.x = 0;
			m_pos.y = (d2*normalFace1.z - d1*normalFace2.z)/m_dir.x;
			m_pos.z = (d1*normalFace2.y - d2*normalFace1.y)/m_dir.x;
		}
		else if(fabs(m_dir.y)>_ModellerEpsilon)
		{
			m_pos.x = (d1*normalFace2.z - d2*normalFace1.z)/m_dir.y;
			m_pos.y = 0;
			m_pos.z = (d2*normalFace1.x - d1*normalFace2.x)/m_dir.y;
		}
		else
		{
			m_pos.x = (d2*normalFace1.y - d1*normalFace2.y)/m_dir.z;
			m_pos.y = (d1*normalFace2.x - d2*normalFace1.x)/m_dir.z;
			m_pos.z = 0;
		}
	}
	m_dir.Normalize();
}

//到参考点的有向距离
float Line3D::getPointToPointDistance(const vec3 & otherPoint)
{
	vec3 dif = otherPoint - m_pos;
	float distance = dif.Length();
	if ((dif.Dot(m_dir))<0)
	{
		return -distance;			
	}
	else
	{
		return distance;
	}
}

//线段交点
vec3 Line3D::getLineIntersection(Line3D * otherLine)
{
	//x = x1 + a1*t = x2 + b1*s
	//y = y1 + a2*t = y2 + b2*s
	//z = z1 + a3*t = z2 + b3*s
	vec3 linePos = otherLine->m_pos; 
	vec3 lineDir = otherLine->m_dir;
	float t;
	if(fabs(m_dir.y*lineDir.x-m_dir.x*lineDir.y)>_ModellerEpsilon)
	{
		t = (-m_pos.y*lineDir.x+linePos.y*lineDir.x+lineDir.y*m_pos.x-lineDir.y*linePos.x)/(m_dir.y*lineDir.x-m_dir.x*lineDir.y);
	}
	else if (fabs(-m_dir.x*lineDir.z+m_dir.z*lineDir.x)>_ModellerEpsilon)
	{
		t=-(-lineDir.z*m_pos.x+lineDir.z*linePos.x+lineDir.x*m_pos.z-lineDir.x*linePos.z)/(-m_dir.x*lineDir.z+m_dir.z*lineDir.x);
	}
	else if (fabs(-m_dir.z*lineDir.y+m_dir.y*lineDir.z)>_ModellerEpsilon)
	{
		t = (m_pos.z*lineDir.y-linePos.z*lineDir.y-lineDir.z*m_pos.y+lineDir.z*linePos.y)/(-m_dir.z*lineDir.y+m_dir.y*lineDir.z);
	}
	else
	{
		return vec3(0,0,0);
	}

	vec3 vResult = m_pos + m_dir * t;
	return vResult;
}
//线面相交
vec3 Line3D::getPlaneIntersection(const vec3 & normal, const vec3 & planePoint, bool & bResult)
{
	bResult = true;
	//Ax + By + Cz + D = 0
	//x = x0 + t(x1 ?x0)
	//y = y0 + t(y1 ?y0)
	//z = z0 + t(z1 ?z0)
	//(x1 - x0) = dx, (y1 - y0) = dy, (z1 - z0) = dz
	//t = -(A*x0 + B*y0 + C*z0 )/(A*dx + B*dy + C*dz)
	float A = normal.x;
	float B = normal.y;
	float C = normal.z;
	float D = (normal.Dot(planePoint)) * -1.0f;

	float numerator = (normal.Dot(m_pos)) + D;
	float denominator = (normal.Dot(m_dir));

	//线面平行
	if(fabs(denominator)<_ModellerEpsilon)
	{
		//线在面上
		if(fabs(numerator)<_ModellerEpsilon)
		{
			return m_pos;
		}
		else
		{
			//平行 分离
			bResult = false;
			return vec3(0,0,0);
		}
	}
	//线面相交
	else
	{
		float t = -numerator/denominator;
		vec3 resultPoint = m_pos + m_dir * t;
		return resultPoint;
	}
}

float LineRandomNum()
{
	int nRand = Rand() % 10000;
	float fRand = (float)nRand;
	fRand *= 0.0001f;
	fRand *= 2.0f;
	fRand -= 1.0f;
	return fRand;
}

void Line3D::perturbDirection()
{
	//direction.x += LineRandomNum();			
	//direction.y += LineRandomNum();			
	//direction.z += LineRandomNum();
	m_dir.x += LineRandomNum() * 0.001f;			
	m_dir.y += LineRandomNum() * 0.001f;			
	m_dir.z += LineRandomNum() * 0.001f;
	//direction.Normalise();
}



TopoSegment::TopoSegment()
{
}

TopoSegment::TopoSegment(Line3D & line, TopoFace & face, int sign1, int sign2, int sign3)
{
	(*this).line = line;
	endsNum = 0;
	
	if(sign1 == 0)
	{
		//点1在面上（距离为0）
		setVertex(face.v1);
		//点2 3同侧 - 只有一个点相交 VERTEX-VERTEX VERTEX
		if(sign2 == sign3)
		{
			setVertex(face.v1);
		}
	}

	if(sign2 == 0)
	{
		setVertex(face.v2);
		if(sign1 == sign3)
		{
			setVertex(face.v2);
		}
	}
	
	if(sign3 == 0)
	{
		setVertex(face.v3);
		if(sign1 == sign2)
		{
			setVertex(face.v3);
		}
	}
	
	//切割边
	if(endsNum != 2)
	{
		//点1 2异侧
		if((sign1==1 && sign2==-1)||(sign1==-1 && sign2==1))
		{
			setEdge(face.v1, face.v2);
		}
		if((sign2==1 && sign3==-1)||(sign2==-1 && sign3==1))
		{
			setEdge(face.v2, face.v3);
		}
		if((sign3==1 && sign1==-1)||(sign3==-1 && sign1==1))
		{
			setEdge(face.v3, face.v1);
		}
	}
}


bool TopoSegment::intersect(const TopoSegment & segment)
{
	if(endDistpos);
	 	startPos = startVertex->pos;
	 	endsNum++;
	 	return true;
	}

	if(endsNum == 1)
	{
		//终点
		endVertex = vertex;
		endType = VERTEX;
		endDist = line.getPointToPointDistance(vertex->pos);
		endPos = endVertex->pos;
		endsNum++;
		
		//defining middle based on the starting point
		//VERTEX-VERTEX-VERTEX
		//if(startVertex.equals(endVertex)) // Need close-enough-to...
		if(true)
		{
			middleType = VERTEX;
		}
		//VERTEX-EDGE-VERTEX
		else if(startType==VERTEX)
		{
			middleType = EDGE;
		}
		
		//the ending point distance should be smaller than  starting point distance 
		if(startDist>endDist)
		{
			swapEnds();
		}
		
		return true;
	}
	else
	{
		return false;
	}
}

/**
 * @param vertex1 one of the vertices of the intercepted edge 
 * @param vertex2 one of the vertices of the intercepted edge
 * @return false if all ends were already defined, true otherwise
 */
bool TopoSegment::setEdge(TopoVertex * vertex1, TopoVertex * vertex2)
{
	vec3 point1 = vertex1->pos;
	vec3 point2 = vertex2->pos;

	vec3 edgeDirection(point2.x - point1.x, point2.y - point1.y, point2.z - point1.z);
	Line3D edgeLine(edgeDirection, point1);
	
	if(endsNum==0)
	{
		startVertex = vertex1;
		startType = EDGE;
		startPos = line.getLineIntersection(&edgeLine);
		startDist = line.getPointToPointDistance(startPos);
		middleType = FACE;
		endsNum++;
		return true;		
	}
	else if(endsNum==1)
	{
		endVertex = vertex1;
		endType = EDGE;
		endPos = line.getLineIntersection(&edgeLine);
		endDist = line.getPointToPointDistance(endPos);
		middleType = FACE;
		endsNum++;
		
		//the ending point distance should be smaller than  starting point distance 
		if(startDist>endDist)
		{
		  	swapEnds();
		}
		
		return true;
	}
	else
	{
		return false;
	}
}

/** Swaps the starting point and the ending point */	
void TopoSegment::swapEnds()
{
	float distTemp = startDist;
	startDist = endDist;
	endDist = distTemp;
	
	int typeTemp = startType;
	startType = endType;
	endType = typeTemp;
	
	TopoVertex * vertexTemp = startVertex;
	startVertex = endVertex;
	endVertex = vertexTemp;
	
	vec3 posTemp = startPos;
	startPos = endPos;
	endPos = posTemp;		
}


//==================^_^==================^_^==================^_^==================^_^
TopoVertex::TopoVertex()
{
	m_adjacentVertices = new TopoVertexPtrSet();
	status = UNKNOWN;
}

TopoVertex::TopoVertex(const vec3 & position, const TVertex & tVertex_, Status status)
{
	tVertex = tVertex_;
	pos = position;
	m_adjacentVertices = new TopoVertexPtrSet();
	status = status;
}

TopoVertex::TopoVertex(const TopoVertex & v)
{
	tVertex = v.tVertex;
	pos = v.pos;
	m_adjacentVertices = new TopoVertexPtrSet();
	status = v.status;
}
TopoVertex & TopoVertex::operator=(const TopoVertex & v)
{
	tVertex = v.tVertex;
	pos = v.pos;
	m_adjacentVertices = new TopoVertexPtrSet();
	status = v.status;
	return *this;
}
TopoVertex::~TopoVertex()
{
	SafeDelete(m_adjacentVertices);
}

//TopologyVertex & TopologyVertex::operator=(const TopologyVertex & v)
//{
//	for(int i = 0; i < v.m_adjacentVertices->length(); i++)
//	{
//		m_adjacentVertices->add(v.m_adjacentVertices->GetVertexPtr(i));
//	}
//
//	status = v.status;
//	color = v.color;
//	x = v.x;
//	y = v.y;
//	z = v.z;
//	return *this;
//}

//判断是否同一个点
bool TopoVertex::equals(TopoVertex * vertex)
{
	//float _ModellerEpsilon = 1.0f;
	float _ModellerEpsilon = 0.01f;
	bool bPositionMatch =
		(fabs(pos.x-vertex->pos.x)<_ModellerEpsilon &&
		fabs(pos.y-vertex->pos.y)<_ModellerEpsilon &&
		fabs(pos.z-vertex->pos.z)<_ModellerEpsilon);

	bool bColorMatch =
		(tVertex.r == vertex->tVertex.r) &&
		(tVertex.g == vertex->tVertex.g) &&
		(tVertex.b == vertex->tVertex.b);

	return bPositionMatch && bColorMatch;
}

void TopoVertex::addAdjacentVertex(TopoVertex * adjacentVertex)
{
	bool bAlready = false;
	for(int i = 0; i < m_adjacentVertices->GetTopoVertexPtrNum(); i++)
	{
		TopoVertex * pVertexI = m_adjacentVertices->GetTopoVertexPtr(i);
		//已经存在该指针
		if(pVertexI == adjacentVertex)
		{
			bAlready = true;
		}
	}
	if(!bAlready)
	{
		m_adjacentVertices->AddTopoVertexPtr(adjacentVertex);
	}
}

void TopoVertex::mark(Status status)
{
	status = status;
	//return;
	for(int i = 0; i < m_adjacentVertices->GetTopoVertexPtrNum(); i++)
	{
		TopoVertex * pVertexI = m_adjacentVertices->GetTopoVertexPtr(i);

		if(pVertexI->status==TopoVertex::UNKNOWN)
		{
			pVertexI->mark(status);
		}
	}
}

//==================^_^==================^_^==================^_^==================^_^

TopoVertexPtrSet::TopoVertexPtrSet()
{
}

TopoVertexPtrSet::~TopoVertexPtrSet()
{
	m_pPointers.clear();
}

TopoVertex * TopoVertexPtrSet::GetTopoVertexPtr(int nIndex)
{
	if(nIndex < 0) return 0;
	if(nIndex >= m_pPointers.size()) return 0;
	TopoVertex * pVertex = m_pPointers[nIndex];
	return pVertex;
}

int TopoVertexPtrSet::GetTopoVertexPtrNum()
{
	return m_pPointers.size();
}

void TopoVertexPtrSet::AddTopoVertexPtr(TopoVertex * pPointer)
{
	m_pPointers.push_back(pPointer);
}

TopoVertex* TopoVertexPtrSet::operator[](int index)
{
	if(index < 0) return 0;
	if(index >= m_pPointers.size()) return 0;
	TopoVertex * pVertex = m_pPointers[index];
	return pVertex;
}

void TopoVertexPtrSet::ClearTopoVertexPtr()
{
	m_pPointers.clear();
}

//==================^_^==================^_^==================^_^==================^_^

TopoVertexSet::TopoVertexSet()
{
}

TopoVertexSet::~TopoVertexSet()
{
	for(int i = 0; i < m_pVertices.size(); i++)
	{
		delete m_pVertices[i];
	}
	m_pVertices.clear();
}

TopoVertex * TopoVertexSet::GetTopoVertex(int nIndex)
{
	if(nIndex < 0) return 0;
	if(nIndex >= m_pVertices.size()) return 0;
	TopoVertex * pVertex = m_pVertices[nIndex];
	return pVertex;
}

int TopoVertexSet::GetTopoVertexNum()
{
	return m_pVertices.size();
}

TopoVertex * TopoVertexSet::AddTopoVertex(const TopoVertex & vertex)
{
	//if(m_nNumVertices >= m_nMaxVertices) return 0;
	m_pVertices.push_back(new TopoVertex(vertex));
	return m_pVertices[m_pVertices.size() - 1];
	//return &m_pVertices[m_nNumVertices - 1];
}

TopoVertex& TopoVertexSet::operator[](int index)
{
	TopoVertex * pVertex = GetTopoVertex(index);
	return *pVertex;
}

bool TopoVertexSet::HasTopoVertex(TopoVertex * pVertex)
{
	// Match pointers or content??
	for(int i = 0; i < GetTopoVertexNum(); i++)
	{
		TopoVertex * pOurVertex = GetTopoVertex(i);
		if(pOurVertex == pVertex)
		{
			return true;
		}
	}
	return false;
}

int TopoVertexSet::IndexOfTopoVertex(TopoVertex * pVertex)
{
	for(int i = 0; i < GetTopoVertexNum(); i++)
	{
		TopoVertex * pOurVertex = GetTopoVertex(i);

		if(pOurVertex == pVertex)
		{
			return i;
		}
	}
	return -1;
}

void TopoVertexSet::ClearTopoVertex()
{
	for(int i = 0; i < m_pVertices.size(); i++)
	{
		delete m_pVertices[i];
	}
	m_pVertices.clear();
}

//==================^_^==================^_^==================^_^==================^_^
TopoFace::TopoFace()
{
	v1 = 0;
	v2 = 0;
	v3 = 0;
	status = UNKNOWN;
	bound = new Box();


}
TopoFace::TopoFace(const TopoFace & face)
{
	status = face.status;
	v1 = face.v1;
	v2 = face.v2;
	v3 = face.v3;

	bound = new Box();
	bound->setFromPoints(v1->pos,v2->pos);
	bound->mergePoint(v3->pos);
	vec3 xy = v2->pos - v1->pos;
	vec3 xz = v3->pos - v1->pos;
	normal = Cross(xy, xz);
	normal.Normalize();
}
TopoFace::TopoFace(TopoVertex * v1i, TopoVertex * v2i, TopoVertex * v3i)
{
	v1 = v1i;
	v2 = v2i;
	v3 = v3i;
	status = UNKNOWN;

	bound = new Box();
	bound->setFromPoints(v1->pos,v2->pos);
	bound->mergePoint(v3->pos);
	vec3 xy = v2->pos - v1->pos;
	vec3 xz = v3->pos - v1->pos;
	normal = Cross(xy, xz);
	normal.Normalize();
}

TopoFace::~TopoFace()
{
	SafeDelete(bound);
}
TopoFace& TopoFace::operator=(const TopoFace & face)
{
	status = face.status;
	v1 = face.v1;
	v2 = face.v2;
	v3 = face.v3;

	if(bound==NULL)
	    bound = new Box();
	bound->setFromPoints(v1->pos,v2->pos);
	bound->mergePoint(v3->pos);
	vec3 xy = v2->pos - v1->pos;
	vec3 xz = v3->pos - v1->pos;
	normal = Cross(xy, xz);
	normal.Normalize();
	return *this;
}
bool TopoFace::equals_pointersmatch(TopoFace * pFace)
{
	TopoFace & face = *pFace;
	bool cond = v1 == face.v1 && v2 == face.v2 && v3 == face.v3;
	return cond;
}

bool TopoFace::equals(TopoFace * pFace)
{
	TopoFace & face = *pFace;
	bool cond1 = v1->equals(face.v1) && v2->equals(face.v2) && v3->equals(face.v3);
	bool cond2 = v1->equals(face.v2) && v2->equals(face.v3) && v3->equals(face.v1);
	bool cond3 = v1->equals(face.v3) && v2->equals(face.v1) && v3->equals(face.v2);
	return cond1 || cond2 || cond3;  	 			
}

Box* TopoFace::getBound()
{
	//只是加点而不减少点 也不改变点所以无需重新计算
#ifdef _DEBUG
	//Box old = *bound;
	//bound->setFromPoints(v1->pos,v2->pos);
	//bound->mergePoint(v3->pos);

	//if (old.min!=bound->min)
	//{
	//	MsgBox(0,"TopoFace::getBound","error",MB_OK);
	//}
	//if (old.max!=bound->max)
	//{
	//	MsgBox(0,"TopoFace::getBound","error",MB_OK);
	//}
#endif
	return bound;
}

vec3& TopoFace::getNormal()
{
#ifdef _DEBUG
	//vec3 xy = v2->pos - v1->pos;
	//vec3 xz = v3->pos - v1->pos;
	//vec3 newnormal = Cross(xy, xz);
	//newnormal.Normalize();
	//if (normal!=newnormal)
	//{
	//	MsgBox(0,"TopoFace::getBound","error",MB_OK);
	//}
#endif
	return normal;
}

float TopoFace::getArea()
{
	//area = (a * c * sen(B))/2
	vec3 xy = v2->pos - v1->pos;
	vec3 xz = v3->pos - v1->pos;
	vec3 yz = v3->pos - v2->pos;
	
	float a = xy.Length();
	float c = xz.Length();
	float b = yz.Length();
	float _ModellerEpsilon = 0.001f;
	if (a<_ModellerEpsilon||c<_ModellerEpsilon||b<_ModellerEpsilon)
	{
		//继续计算出来有误差
		return 0;
	}

	xy.Normalize();
	xz.Normalize();
	float fDot = xy.Dot(xz);
	float fAngle = SafeAcos(fDot);
	return (a * c * sin(fAngle))/2.0f;

	//float a = xy.LengthSq();
	//float c = xz.LengthSq();
	//xy.Normalize();
	//xz.Normalize();
	//float fDot = xy.Dot(xz);
	//return sqrt(a*c*(1-fDot*fDot))/2.0f;
}

void TopoFace::invert()
{
	TopoVertex * vertexTemp = v2;
	v2 = v1;
	v1 = vertexTemp;
}

bool TopoFace::simpleClassify()
{
	int status1 = v1->status;
	int status2 = v2->status;
	int status3 = v3->status;
		
	if(status1==TopoVertex::INSIDE)
	{
		status = INSIDE;
		return true; 
	}

	if(status1==TopoVertex::OUTSIDE)
	{
		status = OUTSIDE;
		return true; 
	}

	if(status2==TopoVertex::INSIDE)
	{
		status = INSIDE;
		return true;
	}

	if(status2==TopoVertex::OUTSIDE)
	{
		status = OUTSIDE;
		return true;
	}

	if(status3==TopoVertex::INSIDE)
	{
		status = INSIDE;
		return true;
	}

	if(status3==TopoVertex::OUTSIDE)
	{
		status = OUTSIDE;
		return true;
	}

	return false;
}

void TopoFace::rayTraceClassify(Sloid & sloid)
{
	//从面的重心沿法线发射线
	vec3 p0 = (v1->pos + v2->pos + v3->pos)/3.0f;

	Line3D ray(getNormal(),p0);
	
	bool success;
	float dotProduct, distance; 
	vec3 intersectPos;
	TopoFace * closestFace = 0;
	float closestDistance;
	//float TOL = 0.0001f;		
	do
	{
		success = true;
		closestDistance = 99999999.9f;
		//other solid...
		for(int i=0;iGetTopoFaceNum();i++)
		{
			TopoFace & otherFace = *(sloid.m_topoFaces->GetTopoFace(i));
			dotProduct = otherFace.getNormal().Dot(ray.m_dir); 
			bool bIntersect = false;
			intersectPos = ray.getPlaneIntersection(otherFace.getNormal(), otherFace.v1->pos, bIntersect);
			//相交
			if(bIntersect)
			{
				distance = ray.getPointToPointDistance(intersectPos);
				//整条线在面上..
				if(fabs(distance)<_ModellerEpsilon && fabs(dotProduct)<_ModellerEpsilon)
				{
					//disturb the ray in order to not lie into another plane ？
					ray.perturbDirection();
					success = false;
					break;
				}
				//只有起点在面上 
				else if(fabs(distance)<_ModellerEpsilon && fabs(dotProduct)>_ModellerEpsilon)
				{
					//如果射线和面相交，即交点在面上
					if(otherFace.hasPoint(intersectPos))
					{
						//此时起点距离最近为0
						closestFace = &otherFace;
						closestDistance = 0;
						break;
					}
				}
				//起点也不在面上 且正向相交distance>0
				else if(fabs(dotProduct)>_ModellerEpsilon && distance>_ModellerEpsilon)
				{
					//记录最近距离的分割面
					if(distancegetNormal().Dot(ray.m_dir);
		
		//distance = 0: 
		if(fabs(closestDistance)<_ModellerEpsilon)
		{
			if(dotProduct>_ModellerEpsilon)
			{
				//共面
				status = SAME;
			}
			else if(dotProduct<-_ModellerEpsilon)
			{
				//反共面
				status = OPPOSITE;
			}
		}
		else if(dotProduct>_ModellerEpsilon)
		{
			//正向相交，内部dot>0
			status = INSIDE;
		}
		else if(dotProduct<-_ModellerEpsilon)
		{
			status = OUTSIDE;
		}
	}
}

//判断点在面内
bool TopoFace::hasPoint(const vec3 &  point)
{
	vec3 u = v2->pos - v1->pos;
	vec3 v = v3->pos - v1->pos;
	vec3 w = point - v1->pos;

	float uu = u.Dot(u);
	float uv = u.Dot(v);
	float vv = v.Dot(v);
	float wu = w.Dot(u);
	float wv = w.Dot(v);
	float d = uv * uv - uu * vv;

	float invD = 1 / d;
	float s = (uv * wv - vv * wu) * invD;
	if (s < 0 || s > 1)
		return false;
	float t = (uv * wu - uu * wv) * invD;
	if (t < 0 || (s + t) > 1)
		return false;

	return true;
}


TopoFaceSet::TopoFaceSet()
{
	m_nMaxSize = 20000;
	m_nSize = 0;
	m_pFaces = new TopoFace[m_nMaxSize];
}

TopoFaceSet::~TopoFaceSet()
{
	delete [] m_pFaces;
}

int TopoFaceSet::GetTopoFaceNum()
{
	return m_nSize;
}

TopoFace * TopoFaceSet::GetTopoFace(int i)
{
	if(i < 0) return 0;
	if(i >= m_nSize) return 0;

	return &m_pFaces[i];
}

void TopoFaceSet::SetTopoFace(int i, TopoFace & vFace)
{
	if(i < 0) return;
	if(i >= m_nSize) return;
	m_pFaces[i] = vFace;
}

TopoFace * TopoFaceSet::AddTopoFace(TopoFace & vFace)
{
	if(m_nSize >= m_nMaxSize)
	{
		return 0;
	}
	m_pFaces[m_nSize] = vFace;
	m_nSize++;

	return &m_pFaces[m_nSize - 1];
}

TopoFace * TopoFaceSet::InsertTopoFace(int i, TopoFace & vFace)
{
	if(m_nSize >= m_nMaxSize)
	{
		return 0;
	}
	// Shift everything along
	for(int j = m_nSize; j >= i+1; j--)
	{
		m_pFaces[j] = m_pFaces[j-1];
	}

	m_pFaces[i] = vFace;
	m_nSize++;

	return &m_pFaces[i];
}

void TopoFaceSet::RemoveTopoFace(int i)
{
	if(m_nSize <= 0)
	{
		return;
	}
	for(int j = i; j < m_nSize-1; j++)
	{
		m_pFaces[j] = m_pFaces[j+1];
	}
	m_nSize--;
}

void TopoFaceSet::ClearTopoFace()
{
	m_nSize = 0;
}




//==================^_^==================^_^==================^_^==================^_^


Sloid::Sloid()
:m_vertexs(NULL)
,m_tVertexs(NULL)
,m_indexs(NULL)
{
	m_topoVertexs = new TopoVertexSet();
	m_topoFaces = new TopoFaceSet();
	m_bound = 0;
	m_indexNum = 0;
	m_vVertexNum = 0;
	m_tVertexNum = 0;
}

Sloid::~Sloid()
{
	Free();
	SafeDelete(m_topoVertexs) ;
	SafeDelete(m_topoFaces);
	SafeDelete(m_bound);
}
void Sloid::Free()
{
	SafeDeleteArray (m_vertexs);
	SafeDeleteArray (m_tVertexs);
	SafeDeleteArray (m_indexs);
}

TopoFace * Sloid::AddTopoFace(TopoVertex * v1, TopoVertex * v2, TopoVertex * v3)
{
	float _ModellerEpsilon = 0.1;
	if(!(v1->equals(v2)||v1->equals(v3)||v2->equals(v3)))
	{
		TopoFace face(v1, v2, v3);
		//不加面积很小的面
		if(face.getArea()<_ModellerEpsilon)
			return 0;
		TopoFace * pAddedFace = (*m_topoFaces).AddTopoFace(face);
		return pAddedFace;
	}
	else
	{
		return 0;
	}
}

TopoVertex * Sloid::AddTopoVertex(const vec3 & pos, const TVertex & tVertex, int status)
{
	int i;
	TopoVertex * pVertex;
	TopoVertex vertex(pos, tVertex, (TopoVertex::Status)status);
	for(i=0;iGetTopoVertexNum();i++)
	{
		//已经存在点
		pVertex = m_topoVertexs->GetTopoVertex(i);
		if(vertex.equals(pVertex)) 
		{
			pVertex->status = ((TopoVertex::Status)status);
			return pVertex;			
		}
	}

	pVertex = m_topoVertexs->AddTopoVertex(vertex);
	return pVertex;
}


//使用object来切分自身
void Sloid::SplitFaces(Sloid * sloid2)
{
	if(m_bound->isOverlap(*sloid2->m_bound)==false)
		return;

	Line3D line;
	TopoFace * face1;
	TopoFace * face2;
	TopoSegment segmentf1p2, segmentf2p1;

	float distFace1Vert1, distFace1Vert2, distFace1Vert3, distFace2Vert1, distFace2Vert2, distFace2Vert3;
	int signFace1Vert1, signFace1Vert2, signFace1Vert3, signFace2Vert1, signFace2Vert2, signFace2Vert3;
	int numFacesBefore = m_topoFaces->GetTopoFaceNum();
	int numFacesStart = m_topoFaces->GetTopoFaceNum();
	int facesIgnored = 0;
												
	//int faceNum1 = m_topologyFaces->GetSize();
	for(int i=0;iGetTopoFaceNum();i++)
	{
		face1 = m_topoFaces->GetTopoFace(i);
		TopoFace face1Orig = *face1;
		
		if(face1->getBound()->isOverlap(*sloid2->m_bound))
		{
			//遍历face2
			for(int j=0;jm_topoFaces->GetTopoFaceNum();j++)
			{
				face2 = sloid2->m_topoFaces->GetTopoFace(j);
				TopoFace face2Orig = *face2;
				if(face1->getBound()->isOverlap(*face2->getBound()))
				{
					//distance from the face1 vertices to the face2 plane
					distFace1Vert1 = ComputeDistance(*(face1->v1), *face2);
					distFace1Vert2 = ComputeDistance(*(face1->v2), *face2);
					distFace1Vert3 = ComputeDistance(*(face1->v3), *face2);
					
					//距离的正负
					signFace1Vert1 = (distFace1Vert1>_ModellerEpsilon? 1 :(distFace1Vert1<-_ModellerEpsilon? -1 : 0)); 
					signFace1Vert2 = (distFace1Vert2>_ModellerEpsilon? 1 :(distFace1Vert2<-_ModellerEpsilon? -1 : 0));
					signFace1Vert3 = (distFace1Vert3>_ModellerEpsilon? 1 :(distFace1Vert3<-_ModellerEpsilon? -1 : 0));
					
					//全0为共面coplanar
					//同号不相交，异号相交
					if (!(signFace1Vert1==signFace1Vert2 && signFace1Vert2==signFace1Vert3))
					{
						//distance from the face2 vertices to the face1 plane
						distFace2Vert1 = ComputeDistance(*(face2->v1), *face1);
						distFace2Vert2 = ComputeDistance(*(face2->v2), *face1);
						distFace2Vert3 = ComputeDistance(*(face2->v3), *face1);
						
						//距离的正负
						signFace2Vert1 = (distFace2Vert1>_ModellerEpsilon? 1 :(distFace2Vert1<-_ModellerEpsilon? -1 : 0)); 
						signFace2Vert2 = (distFace2Vert2>_ModellerEpsilon? 1 :(distFace2Vert2<-_ModellerEpsilon? -1 : 0));
						signFace2Vert3 = (distFace2Vert3>_ModellerEpsilon? 1 :(distFace2Vert3<-_ModellerEpsilon? -1 : 0));
					
						//全0为共面coplanar
						//同号不相交，异号相交
						if (!(signFace2Vert1==signFace2Vert2 && signFace2Vert2==signFace2Vert3))
						{
							line = Line3D(face1, face2);
					
							//face1、plane2 的相交线
							segmentf1p2 = TopoSegment(line, *face1, signFace1Vert1, signFace1Vert2, signFace1Vert3);
							segmentf2p1 = TopoSegment(line, *face2, signFace2Vert1, signFace2Vert2, signFace2Vert3);
														
							//线段相交时 两个面才相交
							if(segmentf1p2.intersect(segmentf2p1))
							{
								//PART II - SUBDIVIDING NON-COPLANAR POLYGONS
								int lastNumFaces = m_topoFaces->GetTopoFaceNum();
								SplitFace(i, segmentf1p2, segmentf2p1);													
								if(numFacesStart*20GetTopoFaceNum())
								{
									//可能死循环
									//return;
								}
						
								// "if the face in the position isn't the same, there was a break"

								//if(face1!=getFace(i)) 
								if(!(face1->equals_pointersmatch(&face1Orig)))
								{
									//if 拆分后没变化
									if(face1Orig.equals(m_topoFaces->GetTopoFace(m_topoFaces->GetTopoFaceNum()-1)))
									{
										//一般不会进入
										if(i!=(m_topoFaces->GetTopoFaceNum()-1))
										{
											m_topoFaces->RemoveTopoFace(m_topoFaces->GetTopoFaceNum()-1);
											m_topoFaces->InsertTopoFace(i, face1Orig);
										}
										else
										{
											continue;
										}
									}
									else
									{
										// This is because the whole face list was shunted down when the current face was removed, so
										// the next face is the face at the current position in the list.
										i--;
										break;
									}
								}
							}
						}
					}
				}
			}
		}
	}

}

/**
 * Computes closest distance from a vertex to a plane
 * 
 * @param vertex vertex used to compute the distance
 * @param face face representing the plane where it is contained
 * @return the closest distance from the vertex to the plane
 */
float Sloid::ComputeDistance(TopoVertex & vertex, TopoFace & face)
{
	vec3 normal = face.getNormal();
	return normal.Dot(vertex.pos) - normal.Dot(face.v1->pos);
}

/**
 * @param segment1 segment representing the intersection of the face with the plane
 * of another face
 * @return segment2 segment representing the intersection of other face with the
 * plane of the current face plane
 */	  
void Sloid::SplitFace(int faceIndex, TopoSegment & segment1, TopoSegment & segment2)
{
	TopoVertex startPosVertex, endPosVertex;
	vec3 startPos, endPos;
	int startType, endType, middleType;
	float startDist, endDist;
	
	TopoFace & face = *m_topoFaces->GetTopoFace(faceIndex);
	TopoVertex * startVertex = segment1.startVertex;
	TopoVertex * endVertex = segment1.endVertex;
	
	//starting point: deeper starting point 		
	if (segment2.startDist > segment1.startDist+_ModellerEpsilon)
	{
		startDist = segment2.startDist;
		startType = segment1.middleType;
		startPos = segment2.startPos;
	}
	else
	{
		startDist = segment1.startDist;
		startType = segment1.startType;
		startPos = segment1.startPos;
	}
	
	//ending point: deepest ending point
	if (segment2.endDist < segment1.endDist-_ModellerEpsilon)
	{
		endDist = segment2.endDist;
		endType = segment1.middleType;
		endPos = segment2.endPos;
	}
	else
	{
		endDist = segment1.endDist;
		endType = segment1.endType;
		endPos = segment1.endPos;
	}		
	middleType = segment1.middleType;
	
	//set vertex to BOUNDARY if it is start type		
	if (startType == TopoSegment::VERTEX)
	{
		startVertex->status=(TopoVertex::BOUNDARY);
	}
			
	//set vertex to BOUNDARY if it is end type
	if (endType == TopoSegment::VERTEX)
	{
		endVertex->status=(TopoVertex::BOUNDARY);
	}
	
	//VERTEX-_______-VERTEX 
	if (startType == TopoSegment::VERTEX && endType == TopoSegment::VERTEX)
	{
		return;
	}
	
	//______-EDGE-______
	else if (middleType == TopoSegment::EDGE)
	{
		//gets the edge 
		int splitEdge;
		if ((startVertex == face.v1 && endVertex == face.v2) || (startVertex == face.v2 && endVertex == face.v1))
		{
			splitEdge = 1;
		}
		else if ((startVertex == face.v2 && endVertex == face.v3) || (startVertex == face.v3 && endVertex == face.v2))
		{	  
			splitEdge = 2; 
		} 
		else
		{
			splitEdge = 3;
		} 
		
		//VERTEX-EDGE-EDGE
		if (startType == TopoSegment::VERTEX)
		{
			BreakFaceInTwo(faceIndex, endPos, splitEdge);
			return;
		}
		
		//EDGE-EDGE-VERTEX
		else if (endType == TopoSegment::VERTEX)
		{
			BreakFaceInTwo(faceIndex, startPos, splitEdge);
			return;
		}
    
		// EDGE-EDGE-EDGE
		else if (startDist == endDist)
		{
			BreakFaceInTwo(faceIndex, endPos, splitEdge);
		}
		else
		{
			if((startVertex == face.v1 && endVertex == face.v2) || (startVertex == face.v2 && endVertex == face.v3) || (startVertex == face.v3 && endVertex == face.v1))
			{
				BreakFaceInThree(faceIndex, startPos, endPos, splitEdge);
			}
			else
			{
				BreakFaceInThree(faceIndex, endPos, startPos, splitEdge);
			}
		}
		return;
	}
	
	//______-FACE-______
	
	//VERTEX-FACE-EDGE
	else if (startType == TopoSegment::VERTEX && endType == TopoSegment::EDGE)
	{
	    BreakFaceInTwo(faceIndex, endPos, *endVertex);//ori
		//BreakFaceInTwo(faceIndex, endPos, *startVertex);
	}
	//EDGE-FACE-VERTEX
	else if (startType == TopoSegment::EDGE && endType == TopoSegment::VERTEX)
	{
		BreakFaceInTwo(faceIndex, startPos, *startVertex);//ori
		//BreakFaceInTwo(faceIndex, startPos, *endVertex);
	}
	//VERTEX-FACE-FACE
	else if (startType == TopoSegment::VERTEX && endType == TopoSegment::FACE)
	{
		BreakFaceInThree(faceIndex, endPos, *startVertex);
	}
	//FACE-FACE-VERTEX
	else if (startType == TopoSegment::FACE && endType == TopoSegment::VERTEX)
	{
		BreakFaceInThree(faceIndex, startPos, *endVertex);
	}
	//EDGE-FACE-EDGE
	else if (startType == TopoSegment::EDGE && endType == TopoSegment::EDGE)
	{
		BreakFaceInThree(faceIndex, startPos, endPos, *startVertex, *endVertex);
	}
	//EDGE-FACE-FACE
	else if (startType == TopoSegment::EDGE && endType == TopoSegment::FACE)
	{
		BreakFaceInFour(faceIndex, startPos, endPos, *startVertex);
	}
	//FACE-FACE-EDGE
	else if (startType == TopoSegment::FACE && endType == TopoSegment::EDGE)
	{
		BreakFaceInFour(faceIndex, endPos, startPos, *endVertex);
	}
	//FACE-FACE-FACE
	else if (startType == TopoSegment::FACE && endType == TopoSegment::FACE)
	{
		vec3 segmentVector(startPos.x-endPos.x, startPos.y-endPos.y, startPos.z-endPos.z);
					
		//if the intersection segment is a point only...
		if (fabs(segmentVector.x)<_ModellerEpsilon && fabs(segmentVector.y)<_ModellerEpsilon && fabs(segmentVector.z)<_ModellerEpsilon)
		{
			BreakFaceInThree(faceIndex, startPos);
			return;
		}
		
		//gets the vertex more lined with the intersection segment
		int linedVertex;
		vec3 linedVertexPos;
		vec3 vertexVector = endPos - face.v1->pos;
		vertexVector.Normalize();
		float dot1 = fabs(segmentVector.Dot(vertexVector));
		vertexVector = endPos -face.v2->pos;

		vertexVector.Normalize();
		float dot2 = fabs(segmentVector.Dot(vertexVector));
		vertexVector =  endPos -face.v3->pos;
		vertexVector.Normalize();
		float dot3 = fabs(segmentVector.Dot(vertexVector));
		if (dot1 > dot2 && dot1 > dot3)
		{
		 	linedVertex = 1;
			linedVertexPos = face.v1->pos;
		}
		else if (dot2 > dot3 && dot2 > dot1)
		{
			linedVertex = 2;
			linedVertexPos = face.v2->pos;
		}
		else
		{
			linedVertex = 3;
			linedVertexPos = face.v3->pos;
		}
    
		// Now find which of the intersection endpoints is nearest to that vertex.
		if ((linedVertexPos - startPos).Length() > (linedVertexPos - endPos).Length())
		{
			BreakFaceInFive(faceIndex, startPos, endPos, linedVertex);
		}
		else
		{
			BreakFaceInFive(faceIndex, endPos, startPos, linedVertex);
		}
	}
}

void Sloid::CalTopoVertexTex(TopoVertex * v1, TopoVertex * v2,const vec3 & pos, TopoVertex * result)
{
	float rat = 0.5f;
	float len = (v2->pos-v1->pos).Length();
	if (len>0)
	{
		rat = (pos-v1->pos).Length()/len;
		if (rat>1)
		{
			rat=1;
		}
	}
	float invRat = 1-rat;
	result->tVertex.u = rat*v2->tVertex.u + v1->tVertex.u*invRat;
	result->tVertex.v = rat*v2->tVertex.v + v1->tVertex.v*invRat;
	result->tVertex.w = rat*v2->tVertex.w + v1->tVertex.w*invRat;
}
void Sloid::CalTopoVertexTex(TopoVertex * v1, TopoVertex * v2,TopoVertex * v3,const vec3 & pos, TopoVertex * result)
{
	vec2 res = GetUVOnTrigon(v1->pos,v2->pos,v3->pos,
		                     vec2(v1->tVertex.u,v1->tVertex.v),vec2(v2->tVertex.u,v2->tVertex.v),vec2(v3->tVertex.u,v3->tVertex.v),pos);
		
	result->tVertex.u = res.x;
	result->tVertex.v = res.y;
	result->tVertex.w = 1;
}

/**
分割线穿过一个顶点和邻边，一个三角形拆分为两个
 * Face breaker for VERTEX-EDGE-EDGE / EDGE-EDGE-VERTEX
 * @param faceIndex 待拆的面
 * @param newPos  拆边上的点
 * @param splitEdge 待拆的边
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2
 */		
void Sloid::BreakFaceInTwo(int faceIndex, const vec3 & newPos, int splitEdge)
{
	TopoFace & face = *m_topoFaces->GetTopoFace(faceIndex);
	TopoVertex * vertex = AddTopoVertex(newPos, face.v1->tVertex, TopoVertex::BOUNDARY);
					
	if (splitEdge == 1)
	{
		//分割线v1~p，p在邻边e1上
		AddTopoFace(face.v1, vertex, face.v3);
		AddTopoFace(vertex, face.v2, face.v3);
		CalTopoVertexTex(face.v1,face.v2,newPos,vertex);
	}
	else if (splitEdge == 2)
	{
		AddTopoFace(face.v2, vertex, face.v1);
		AddTopoFace(vertex, face.v3, face.v1);
		CalTopoVertexTex(face.v3,face.v2,newPos,vertex);
	}
	else
	{
		AddTopoFace(face.v3, vertex, face.v2);
		AddTopoFace(vertex, face.v1, face.v2);
		CalTopoVertexTex(face.v1,face.v3,newPos,vertex);
	}
	m_topoFaces->RemoveTopoFace(faceIndex);
}

/**
分割线穿过一个顶点和对边，一个三角形拆分为两个
 * Face breaker for VERTEX-FACE-EDGE / EDGE-FACE-VERTEX
 * @param faceIndex 待拆的面
 * @param newPos  拆边（对边）上的点
 * @param endVertex 经过的顶点
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2
 */		
void Sloid::BreakFaceInTwo(int faceIndex, const vec3 & newPos, TopoVertex & endVertex)
{
	TopoFace & face = *m_topoFaces->GetTopoFace(faceIndex);
	TopoVertex * vertex = AddTopoVertex(newPos, face.v1->tVertex, TopoVertex::BOUNDARY);
				
	if (endVertex.equals(face.v1))
	{
		//穿过点1，边2
		AddTopoFace(face.v1, vertex, face.v3);
		AddTopoFace(vertex, face.v2, face.v3);
		CalTopoVertexTex(face.v1,face.v2,newPos,vertex);
	}
	else if (endVertex.equals(face.v2))
	{
		AddTopoFace(face.v2, vertex, face.v1);
		AddTopoFace(vertex, face.v3, face.v1);
		CalTopoVertexTex(face.v3,face.v2,newPos,vertex);
	}
	else
	{
		AddTopoFace(face.v3, vertex, face.v2);
		AddTopoFace(vertex, face.v1, face.v2);
		CalTopoVertexTex(face.v1,face.v3,newPos,vertex);
	}

	m_topoFaces->RemoveTopoFace(faceIndex);
}
//???  my
//void Sloid::BreakFaceInTwo(int faceIndex, const vec3 & newPos, Vertex & startVertex)
//{
//	Face & face = *m_topologyFaces->GetFace(faceIndex);
//	Vertex * vertex = addVertex(newPos, face.v1->color, Vertex::BOUNDARY);
//
//	if (startVertex.equals(face.v3))
//	{
//		//穿过点1，边2
//		addFace(face.v1, vertex, face.v3);
//		addFace(vertex, face.v2, face.v3);
//	}
//	else if (startVertex.equals(face.v1))
//	{
//		addFace(face.v2, vertex, face.v1);
//		addFace(vertex, face.v3, face.v1);
//	}
//	else
//	{
//		addFace(face.v3, vertex, face.v2);
//		addFace(vertex, face.v1, face.v2);
//	}
//
//	m_topologyFaces->RemoveFace(faceIndex);
//}

/**
分割线包含于一条边，一个三角形拆分为3个
 * Face breaker for EDGE-EDGE-EDGE
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2	
 */
void Sloid::BreakFaceInThree(int faceIndex, const vec3 & newPos1, const vec3 & newPos2, int splitEdge)
{
	TopoFace & face = *(m_topoFaces->GetTopoFace(faceIndex));
	TopoVertex * vertex1 = AddTopoVertex(newPos1, face.v1->tVertex, TopoVertex::BOUNDARY);	
	TopoVertex * vertex2 = AddTopoVertex(newPos2, face.v1->tVertex, TopoVertex::BOUNDARY);
					
	if (splitEdge == 1)
	{
		AddTopoFace(face.v1, vertex1, face.v3);
		AddTopoFace(vertex1, vertex2, face.v3);
		AddTopoFace(vertex2, face.v2, face.v3);
		CalTopoVertexTex(face.v1,face.v2,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v2,newPos2,vertex2);
	}
	else if (splitEdge == 2)
	{
		AddTopoFace(face.v2, vertex1, face.v1);
		AddTopoFace(vertex1, vertex2, face.v1);
		AddTopoFace(vertex2, face.v3, face.v1);
		CalTopoVertexTex(face.v3,face.v2,newPos1,vertex1);
		CalTopoVertexTex(face.v3,face.v2,newPos2,vertex2);
	}
	else
	{
		AddTopoFace(face.v3, vertex1, face.v2);
		AddTopoFace(vertex1, vertex2, face.v2);
		AddTopoFace(vertex2, face.v1, face.v2);
		CalTopoVertexTex(face.v1,face.v3,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v3,newPos2,vertex2);
	}
	m_topoFaces->RemoveTopoFace(faceIndex);
}

/**
 * VERTEX-FACE-FACE / FACE-FACE-VERTEX
 分割线一个点在端点，一个点在面内部
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2	
 */
void Sloid::BreakFaceInThree(int faceIndex, const vec3 & newPos, TopoVertex & endVertex)
{
	TopoFace & face = *(m_topoFaces->GetTopoFace(faceIndex));
	TopoVertex * vertex = AddTopoVertex(newPos, face.v1->tVertex, TopoVertex::BOUNDARY);
					
	//if (endVertex.equals(face.v1))
	//{
	//	addFace(face.v1, face.v2, vertex);
	//	addFace(face.v2, face.v3, vertex);
	//	addFace(face.v3, face.v1, vertex);
	//}
	//else if (endVertex.equals(face.v2))
	//{
	//	addFace(face.v2, face.v3, vertex);
	//	addFace(face.v3, face.v1, vertex);
	//	addFace(face.v1, face.v2, vertex);
	//}
	//else
	{
		AddTopoFace(face.v3, face.v1, vertex);
		AddTopoFace(face.v1, face.v2, vertex);
		AddTopoFace(face.v2, face.v3, vertex);
		CalTopoVertexTex(face.v1,face.v2,face.v3,newPos,vertex);
	}
	m_topoFaces->RemoveTopoFace(faceIndex);
}

/**
 * Face breaker for EDGE-FACE-EDGE
  分割线切掉一个角
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2	
 */
void Sloid::BreakFaceInThree(int faceIndex, const vec3 & newPos1, const vec3 & newPos2, TopoVertex & startVertex, TopoVertex & endVertex)
{
	TopoFace & face = *(m_topoFaces->GetTopoFace(faceIndex));
	TopoVertex * vertex1 = AddTopoVertex(newPos1, face.v1->tVertex, TopoVertex::BOUNDARY);
	TopoVertex * vertex2 = AddTopoVertex(newPos2, face.v1->tVertex, TopoVertex::BOUNDARY);
					
	if (startVertex.equals(face.v1) && endVertex.equals(face.v2))
	{
		//切角2
		AddTopoFace(face.v1, vertex1, vertex2);
		AddTopoFace(face.v1, vertex2, face.v3);
		AddTopoFace(vertex1, face.v2, vertex2);
		CalTopoVertexTex(face.v1,face.v2,newPos1,vertex1);
		CalTopoVertexTex(face.v2,face.v3,newPos2,vertex2);
	}
	else if (startVertex.equals(face.v2) && endVertex.equals(face.v1))
	{
		//反切角2
		AddTopoFace(face.v1, vertex2, vertex1);
		AddTopoFace(face.v1, vertex1, face.v3);
		AddTopoFace(vertex2, face.v2, vertex1);
		CalTopoVertexTex(face.v1,face.v2,newPos1,vertex1);
		CalTopoVertexTex(face.v2,face.v3,newPos2,vertex2);
	}
	else if (startVertex.equals(face.v2) && endVertex.equals(face.v3))
	{
		//切角3
		AddTopoFace(face.v2, vertex1, vertex2);
		AddTopoFace(face.v2, vertex2, face.v1);
		AddTopoFace(vertex1, face.v3, vertex2);
		CalTopoVertexTex(face.v2,face.v3,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v3,newPos2,vertex2);
	}
	else if (startVertex.equals(face.v3) && endVertex.equals(face.v2))
	{
		AddTopoFace(face.v2, vertex2, vertex1);
		AddTopoFace(face.v2, vertex1, face.v1);
		AddTopoFace(vertex2, face.v3, vertex1);
		CalTopoVertexTex(face.v2,face.v3,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v3,newPos2,vertex2);
	}
	else if (startVertex.equals(face.v3) && endVertex.equals(face.v1))
	{
		//切角1
		AddTopoFace(face.v3, vertex1, vertex2);
		AddTopoFace(face.v3, vertex2, face.v2);
		AddTopoFace(vertex1, face.v1, vertex2);
		CalTopoVertexTex(face.v1,face.v3,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v2,newPos2,vertex2);
	}
	else
	{
		AddTopoFace(face.v3, vertex2, vertex1);
		AddTopoFace(face.v3, vertex1, face.v2);
		AddTopoFace(vertex2, face.v1, vertex1);
		CalTopoVertexTex(face.v1,face.v3,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v2,newPos2,vertex2);
	}

	m_topoFaces->RemoveTopoFace(faceIndex);
}

/**
 * Face breaker for FACE-FACE-FACE (a point only)
   分割线包含于面内？
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2	
 */
void Sloid::BreakFaceInThree(int faceIndex, const vec3 & newPos)
{
	TopoFace & face = *(m_topoFaces->GetTopoFace(faceIndex));
	TopoVertex * vertex = AddTopoVertex(newPos, face.v1->tVertex, TopoVertex::BOUNDARY);
			
	AddTopoFace(face.v1, face.v2, vertex);
	AddTopoFace(face.v2, face.v3, vertex);
	AddTopoFace(face.v3, face.v1, vertex);
	CalTopoVertexTex(face.v1,face.v3,face.v3,newPos,vertex);

	m_topoFaces->RemoveTopoFace(faceIndex);
}

/**
 * Face breaker for EDGE-FACE-FACE / FACE-FACE-EDGE
   分割线一个点在边上，一个点在面内部
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2	
 */	
void Sloid::BreakFaceInFour(int faceIndex, const vec3 & newPos1, const vec3 & newPos2, TopoVertex & endVertex)
{
	TopoFace & face = *(m_topoFaces->GetTopoFace(faceIndex));
	TopoVertex * vertex1 = AddTopoVertex(newPos1, face.v1->tVertex, TopoVertex::BOUNDARY);
	TopoVertex * vertex2 = AddTopoVertex(newPos2, face.v1->tVertex, TopoVertex::BOUNDARY);
	
	if (endVertex.equals(face.v1))
	{
		//vertex2在内部
		AddTopoFace(face.v1, vertex1, vertex2);
		AddTopoFace(vertex1, face.v2, vertex2);
		AddTopoFace(face.v2, face.v3, vertex2);
		AddTopoFace(face.v3, face.v1, vertex2);
		CalTopoVertexTex(face.v1,face.v2,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v2,face.v3,newPos2,vertex2);
	}
	else if (endVertex.equals(face.v2))
	{
		AddTopoFace(face.v2, vertex1, vertex2);
		AddTopoFace(vertex1, face.v3, vertex2);
		AddTopoFace(face.v3, face.v1, vertex2);
		AddTopoFace(face.v1, face.v2, vertex2);
		CalTopoVertexTex(face.v2,face.v3,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v2,face.v3,newPos2,vertex2);
	}
	else
	{
		AddTopoFace(face.v3, vertex1, vertex2);
		AddTopoFace(vertex1, face.v1, vertex2);
		AddTopoFace(face.v1, face.v2, vertex2);
		AddTopoFace(face.v2, face.v3, vertex2);
		CalTopoVertexTex(face.v3,face.v1,newPos1,vertex1);
		CalTopoVertexTex(face.v1,face.v2,face.v3,newPos2,vertex2);
	}

	m_topoFaces->RemoveTopoFace(faceIndex);
}

/**
 * Face breaker for FACE-FACE-FACE
  分割线一个点在面内部，另一个点也在面内部
                          v1
                          /\
						 /  \
					  e1/    \e3
					   /      \
				    v2/________\v3
					      e2	
 */		
void Sloid::BreakFaceInFive(int faceIndex, const vec3 & newPos1, const vec3 & newPos2, int linedVertex)
{
	TopoFace & face = *(m_topoFaces->GetTopoFace(faceIndex));	
	TopoVertex * vertex1 = AddTopoVertex(newPos1, face.v1->tVertex, TopoVertex::BOUNDARY);
	TopoVertex * vertex2 = AddTopoVertex(newPos2, face.v1->tVertex, TopoVertex::BOUNDARY);
	CalTopoVertexTex(face.v1,face.v2,face.v3,newPos1,vertex1);
	CalTopoVertexTex(face.v1,face.v2,face.v3,newPos2,vertex2);
	float cont = 0;
	if (linedVertex == 1)
	{
		AddTopoFace(face.v2, face.v3, vertex1);
		AddTopoFace(face.v2, vertex1, vertex2);
		AddTopoFace(face.v3, vertex2, vertex1);
		AddTopoFace(face.v2, vertex2, face.v1);
		AddTopoFace(face.v3, face.v1, vertex2);
	}
	else if(linedVertex == 2)
	{
		AddTopoFace(face.v3, face.v1, vertex1);
		AddTopoFace(face.v3, vertex1, vertex2);
		AddTopoFace(face.v1, vertex2, vertex1);
		AddTopoFace(face.v3, vertex2, face.v2);
		AddTopoFace(face.v1, face.v2, vertex2);
	}
	else
	{
		AddTopoFace(face.v1, face.v2, vertex1);
		AddTopoFace(face.v1, vertex1, vertex2);
		AddTopoFace(face.v2, vertex2, vertex1);
		AddTopoFace(face.v1, vertex2, face.v3);
		AddTopoFace(face.v2, face.v3, vertex2);
	}

	// Calling it at the end, because the java garbage collection won't destroy it until after the end of the function,
	// (when there is nothing referencing it anymore)
	m_topoFaces->RemoveTopoFace(faceIndex);
}


//标记面在切割sloid的内部还是外部..
void Sloid::ClassifyFaces(Sloid & sloid)
{
	//清空重建邻边拓补信息
	//for(int i=0;iGetSize();i++)
	//{
	//}
	//for(int i=0;iGetSize();i++)
	//{
	//	TopologyFace & face = *(m_topologyFaces->GetFace(i));
	//	face.v1->addAdjacentVertex(face.v2);
	//	face.v1->addAdjacentVertex(face.v3);
	//	face.v2->addAdjacentVertex(face.v1);
	//	face.v2->addAdjacentVertex(face.v3);
	//	face.v3->addAdjacentVertex(face.v1);
	//	face.v3->addAdjacentVertex(face.v2);
	//}
	//
	for(int i=0;iGetTopoFaceNum();i++)
	{
		TopoFace & face = *(m_topoFaces->GetTopoFace(i));
		//
		if(face.simpleClassify()==false)
		{
			face.rayTraceClassify(sloid);
			if(face.v1->status==TopoVertex::UNKNOWN) 
			{
				face.v1->mark((TopoVertex::Status)face.status);
			}
			if(face.v2->status==TopoVertex::UNKNOWN) 
			{
				face.v2->mark((TopoVertex::Status)face.status);
			}
			if(face.v3->status==TopoVertex::UNKNOWN) 
			{
				face.v3->mark((TopoVertex::Status)face.status);
			}
		}
	}
}

//反转内部面，减法使用
void Sloid::InvertInsideFaces()
{
	TopoFace * face = 0;
	for(int i=0;iGetTopoFaceNum();i++)
	{
		face = m_topoFaces->GetTopoFace(i);
		if(face->status==TopoFace::INSIDE)
		{
			face->invert();
		}
	}
}

void Sloid::GenTopologyFromRend()
{
	///后期拓补处理
	m_topoVertexs->ClearTopoVertex();
	m_topoFaces->ClearTopoFace();

	TopoVertex * v1 = 0;
	TopoVertex * v2 = 0;
	TopoVertex * v3 = 0;
	TopoVertex * topoVertex = 0;
	TopoVertexPtrSet * tmpTopoVertexPtrSet = new TopoVertexPtrSet();
	// 
	for(int i=0;iAddTopoVertexPtr(topoVertex); 
	}

	// faces
	for(int i=0; iGetTopoVertexPtr(m_indexs[i]);
		v2 = tmpTopoVertexPtrSet->GetTopoVertexPtr(m_indexs[i+1]);
		v3 = tmpTopoVertexPtrSet->GetTopoVertexPtr(m_indexs[i+2]);
		AddTopoFace(v1, v2, v3);
	}

	//create bound
	if (m_bound==NULL)
	{
		m_bound = new Box();
	}
	m_bound->setFromPoints(m_vertexs[0],m_vertexs[1]);
	for(int i=1;imergePoint(m_vertexs[i]);
	}

	delete tmpTopoVertexPtrSet;
}


void Sloid::GenRendFromTopology()
{
	//m_topologyVertexs->clear();
	//m_vertices->clear();

	//for(int i = 0; i < m_topoVertexs->GetNumVertices(); i++)
	//{
	//	TopoVertex * pVertex = m_topoVertexs->GetVertex(i);
	//	//m_vertexs.AddVector(pVertex->pos);
	//	m_vertexs.SetVector(i,pVertex->pos);
	//}

}

void Sloid::Translate(const vec3 & t)
{
	for(int i = 0; i < m_vVertexNum; i++)
	{
		vec3 v = m_vertexs[i];
		v = v + t;
		m_vertexs[i] = v;
	}
	GenTopologyFromRend();
}

void Sloid::Render()
{

	G_RendDriver->SetRenderStateEnable(RS_DEPTH_TEST,true);
	G_RendDriver->SetRenderStateEnable(RS_TEXTURE_2D,true);
	G_RendDriver->SetRenderStateEnable(RS_ALPHA_TEST,true);
	G_RendDriver->SetRenderStateEnable(RS_BLEND,true);
	G_RendDriver->BlendFunc(RS_SRC_ALPHA,RS_ONE_MINUS_SRC_ALPHA);
	G_RendDriver->AlphaFunc(RS_GREATER,0.0f);
	G_RendDriver->Color4f(1,1,1,1);

//		for (int i=0;i<8;i++)
//		{
//			G_RendDriver->SetSamplerState(i, SS_MINFILTER, TF_LINEAR);
//			G_RendDriver->SetSamplerState(i, SS_MAGFILTER, TF_LINEAR);
//		}

	G_RendDriver->RendBegin(RS_TRIANGLES);

	int nNumTriangles = m_indexNum / 3;

	for(int i = 0; i < nNumTriangles; i++)
	{
		int nIndex1 = m_indexs[i * 3 + 0];
		int nIndex2 = m_indexs[i * 3 + 1];
		int nIndex3 = m_indexs[i * 3 + 2];

		vec3 vP1 = m_vertexs[nIndex1];
		vec3 vP2 = m_vertexs[nIndex2];
		vec3 vP3 = m_vertexs[nIndex3];
		TVertex col1 = m_tVertexs[nIndex1];
		TVertex col2 = m_tVertexs[nIndex2];
		TVertex col3 = m_tVertexs[nIndex3];

		//glColor4f(col1.r, col1.g, col1.b, 255);
		G_RendDriver->TexCoord2f(col1.u, col1.v);
		G_RendDriver->Vertex3f(vP1.x, vP1.y, vP1.z);

		//glColor4f(col2.r, col2.g, col2.b, 255);
		G_RendDriver->TexCoord2f(col2.u, col2.v);
		G_RendDriver->Vertex3f(vP2.x, vP2.y, vP2.z);

		//glColor4f(col3.r, col3.g, col3.b, 255);
		G_RendDriver->TexCoord2f(col3.u, col3.v);
		G_RendDriver->Vertex3f(vP3.x, vP3.y, vP3.z);
	}

	G_RendDriver->RendEnd();

	//glLineWidth(1);
	//glDisable(GL_TEXTURE_2D);
	//glDisable (GL_DEPTH_TEST);

	//glBegin(GL_LINES);

	//for(int i = 0; i < nNumTriangles; i++)
	//{
	//	int nIndex1 = m_indexs[i * 3 + 0];
	//	int nIndex2 = m_indexs[i * 3 + 1];
	//	int nIndex3 = m_indexs[i * 3 + 2];

	//	vec3 vP1 = m_vertexs[nIndex1];
	//	vec3 vP2 = m_vertexs[nIndex2];
	//	vec3 vP3 = m_vertexs[nIndex3];

	//	TVertex col1 = m_tVertexs[nIndex1];
	//	TVertex col2 = m_tVertexs[nIndex2];
	//	TVertex col3 = m_tVertexs[nIndex3];

	//	glColor4ub(200,200,200, 255);

	//	glVertex3d(vP1.x, vP1.y, vP1.z);
	//	glVertex3d(vP2.x, vP2.y, vP2.z);

	//	glVertex3d(vP2.x, vP2.y, vP2.z);
	//	glVertex3d(vP3.x, vP3.y, vP3.z);

	//	glVertex3d(vP3.x, vP3.y, vP3.z);
	//	glVertex3d(vP1.x, vP1.y, vP1.z);
	//}

	//glEnd();

	//glLineWidth(1);
	//glColor4ub(255,255,255, 255);
}


void Sloid::RefMesh(RendSys::Mesh* mesh)
{
	Free();
	if (mesh)
	{
		//添加点面
		m_vVertexNum = mesh->m_vVertexNum;
		m_vertexs= new vec3[m_vVertexNum];

		for(int i = 0; i < m_vVertexNum; i++)
		{
			Mesh::Vertex& v =mesh->m_vVertexs[i];
			m_vertexs[i] = vec3(v.x,v.y,v.z);
		}

		//
		m_indexNum = mesh->m_trigonNum*3;
		m_indexs = new IndexInt[m_indexNum];
		for(int i = 0; i < mesh->m_trigonNum; i++)
		{
			Mesh::Trigon& f = mesh->m_trigons[i];
			m_indexs[i*3]   = f.vIndex[0];
			m_indexs[i*3+1] = f.vIndex[1];
			m_indexs[i*3+2] = f.vIndex[2];
		}

		//
		m_tVertexs = new TVertex[m_vVertexNum];
		TVertex col;
		float colorr = (Rand() % 255)/255.0f;
		float colorg = (Rand() % 255)/255.0f;
		float colorb = (Rand() % 255)/255.0f;
		for(int i = 0; i < m_vVertexNum; i++)
		{
			float colorr = (Rand() % 255)/255.0f;
			float colorg = (Rand() % 255)/255.0f;
			float colorb = (Rand() % 255)/255.0f;
			Mesh::TVertex& v =mesh->m_tVertexs[i];
			col.r = colorr;
			col.g =  colorg;
			col.b =  colorb;
			col.u =  v.u;
			col.v =  v.v;
			m_tVertexs[i] = (col);
		}
	}

	GenTopologyFromRend();
}



//==================^_^==================^_^==================^_^==================^_^

BooleanModeller::BooleanModeller(Sloid * solid1, Sloid * solid2)
{
	m_pSloid1 = solid1;
	m_pSloid2 = solid2;

	//切割
	m_pSloid1->SplitFaces(m_pSloid2);
	//模拟爆炸不做联合不补面时可以省略分割sloid2
    m_pSloid2->SplitFaces(m_pSloid1);

	//classify faces as being inside or outside the other solid
	m_pSloid1->ClassifyFaces(*m_pSloid2);
	m_pSloid2->ClassifyFaces(*m_pSloid1);
}

Sloid * BooleanModeller::GetUnion()
{
	Sloid *result = new Sloid();
	PreMergeSloid(m_pSloid1, result, TopoFace::OUTSIDE, TopoFace::SAME);
	PreMergeSloid(m_pSloid2, result, TopoFace::OUTSIDE, TopoFace::OUTSIDE);
	result->m_indexs = new IndexInt[result->m_indexNum];//肯比实际的多少许
	result->m_vertexs = new vec3[result->m_vVertexNum];
	result->m_tVertexs = new TVertex[result->m_tVertexNum];
	result->m_indexNum = 0;
	result->m_vVertexNum = 0;
	result->m_tVertexNum = 0;

	MergeSloid(m_pSloid1, result, TopoFace::OUTSIDE, TopoFace::SAME);
	MergeSloid(m_pSloid2, result, TopoFace::OUTSIDE, TopoFace::OUTSIDE);

	//拓扑的面依赖于点指针不遍即时加入
	//result->GenRendFromTopology();
	return result;
}

Sloid * BooleanModeller::GetIntersection()
{
	Sloid *result = new Sloid();
	PreMergeSloid(m_pSloid1, result, TopoFace::INSIDE, TopoFace::SAME);
	PreMergeSloid(m_pSloid2, result, TopoFace::INSIDE, TopoFace::INSIDE);
	result->m_indexs = new IndexInt[result->m_indexNum];//肯比实际的多少许
	result->m_vertexs = new vec3[result->m_vVertexNum];
	result->m_tVertexs = new TVertex[result->m_tVertexNum];
	result->m_indexNum = 0;
	result->m_vVertexNum = 0;
	result->m_tVertexNum = 0;
	
	MergeSloid(m_pSloid1, result, TopoFace::INSIDE, TopoFace::SAME);
	MergeSloid(m_pSloid2, result, TopoFace::INSIDE, TopoFace::INSIDE);
	//result->GenRendFromTopology();
	return result;
}

Sloid * BooleanModeller::GetDifference()
{
	m_pSloid2->InvertInsideFaces();
	Sloid *result = new Sloid();
	PreMergeSloid(m_pSloid1, result, TopoFace::OUTSIDE, TopoFace::OPPOSITE);
	PreMergeSloid(m_pSloid2, result, TopoFace::INSIDE, TopoFace::INSIDE);
	result->m_indexs = new IndexInt[result->m_indexNum];//肯比实际的多少许
	result->m_vertexs = new vec3[result->m_vVertexNum];
	result->m_tVertexs = new TVertex[result->m_tVertexNum];
	result->m_indexNum = 0;
	result->m_vVertexNum = 0;
	result->m_tVertexNum = 0;

	MergeSloid(m_pSloid1, result, TopoFace::OUTSIDE, TopoFace::OPPOSITE);
	MergeSloid(m_pSloid2, result, TopoFace::INSIDE, TopoFace::INSIDE);//减法：sloid的内部面作为补面，需要反转法线。



	//result->GenRendFromTopology();
	m_pSloid2->InvertInsideFaces();
	return result;
}

void BooleanModeller::MergeSloid(Sloid* pSrcSloid, Sloid* pDstSloid, int faceStatus1, int faceStatus2)
{
	for(int i=0;im_topoFaces->GetTopoFaceNum();i++)
	{
		TopoFace & face = *(pSrcSloid->m_topoFaces->GetTopoFace(i));
		if(face.status==faceStatus1 || face.status==faceStatus2)
		{
			TopoVertexPtrSet faceVerts;
			faceVerts.AddTopoVertexPtr(face.v1);
			faceVerts.AddTopoVertexPtr(face.v2);
			faceVerts.AddTopoVertexPtr(face.v3);

			for(int j=0;jm_topoVertexs->HasTopoVertex(faceVerts[j]))
				{
					pDstSloid->m_indexs[pDstSloid->m_indexNum] = pDstSloid->m_topoVertexs->IndexOfTopoVertex(faceVerts[j]);
					pDstSloid->m_indexNum++;
				}
				else
				{
					pDstSloid->m_indexs[pDstSloid->m_indexNum] = pDstSloid->m_topoVertexs->GetTopoVertexNum();
					pDstSloid->m_topoVertexs->AddTopoVertex(*faceVerts[j]);
					pDstSloid->m_vertexs[pDstSloid->m_vVertexNum] = faceVerts[j]->pos;
					pDstSloid->m_tVertexs[pDstSloid->m_tVertexNum] = faceVerts[j]->tVertex;
					pDstSloid->m_indexNum++;
					pDstSloid->m_vVertexNum++;
					pDstSloid->m_tVertexNum++;
				}
			}
		}
	}
}

void BooleanModeller::PreMergeSloid(Sloid* pSrcSloid, Sloid* pDstSloid, int faceStatus1, int faceStatus2)
{
	for(int i=0;im_topoFaces->GetTopoFaceNum();i++)
	{
		TopoFace & face = *(pSrcSloid->m_topoFaces->GetTopoFace(i));
		if(face.status==faceStatus1 || face.status==faceStatus2)
		{
			pDstSloid->m_indexNum+=3;
			pDstSloid->m_vVertexNum+=3;
			pDstSloid->m_tVertexNum+=3;
		}
	}
}

完