mesh.cpp

此代码主要用于汽车车身的优化

//  implementation of the Mesh class.
//Mesh.cpp:网格类的执行
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Subdiv.h"
#include "Mesh.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
#include "Vertex.h"
#include "Face.h"
#include <afx.h>
#include <iostream>
//#include <stdio.h>
//#include <stdlib.h>
#include <io.h>

Mesh::Mesh()
{
	m_pVertexes = new VERTEXSET;
	m_pSubdivVertexes = NULL;
}

Mesh::~Mesh()
{
	reset();
	delete m_pVertexes;
	// 
}

void Mesh::reset()
{
	if(m_pVertexes)
	{
		FOR_EACH_VERTEX(itr)
		{
			itr->reset();
		}
		m_pVertexes->clear();
	}
	if(m_pSubdivVertexes)	// be sure that whenever a new subdiv-mesh is made 
	{						// and vertexes is moved, set m_pSubdivVertexes = NULL
		FOR_EACH_SUBVERTEX(itr)
		{
			itr->reset();
		}
		m_pSubdivVertexes->clear();
		delete m_pSubdivVertexes;
		m_pSubdivVertexes = NULL;
	}
	FOR_EACH_EDGE(eitr)
	{
		eitr->reset();
	}
	m_edges.clear();
	FOR_EACH_FACE(fitr)
	{
		fitr->reset();
	}
	m_faces.clear();
}


inline int Mesh::addVertex(double x, double y, double z)
{
	Vertex v(x,y,z, m_pVertexes->size());
	m_pVertexes->push_back( v );
	return m_pVertexes->size()-1;
}

inline int Mesh::addVertex(Vector3d & d)
{
	Vertex v(d, m_pVertexes->size());
	m_pVertexes->push_back( v );
	return m_pVertexes->size()-1;
}


inline int Mesh::addSubdivVertex(Vector3d & d)
{
	Vertex v(d, m_pSubdivVertexes->size());
	m_pSubdivVertexes->push_back( v );
	return (m_pSubdivVertexes->size()-1);

}
// 对每个面只能调用一次。否则会多加
int Mesh::addFace(vector<int> & faceVertexsIdx)//增加面
{
	Mesh::EDGEPOS vp;
	Vector3d fedgevec1, fedgevec2;
	int fi = m_faces.size();		// index of the face to insert添加面的索引
	Face f(faceVertexsIdx, fi);
	int bvidx, evidx;
	int vnum = faceVertexsIdx.size();
	for(int i = 0; i < vnum; i ++)	// for each vertex of face
	{
		bvidx = faceVertexsIdx[i];
		evidx = faceVertexsIdx[(i+1)%vnum];
		
		//		cout << "faceVertexsIdx:" << bvidx << " " << evidx << endl;
		//		cout << "m_pVertexes:" << (*m_pVertexes).size() << endl;
		vp = findAndInsertEdgePos(bvidx, evidx);
		vp->addAdjFace(fi);								// add adj face for edge
		f.addEdge(vp);									// add edge for face
		// 保存的边的idx对应face中的idx的点，是出边。
		// 这样沿着面和这个点的idx对应的棱找出的邻面是按顺时针方向（法向向内）

		(*m_pVertexes)[bvidx].addAdjEdge(vp);			// add adj edge for vertex
		(*m_pVertexes)[evidx].addAdjEdge(vp);			// not add the reverse edge!! get rid of the edge-repetition check!
		
		// if ((*m_pVertexes)[bvidx].m_adjFaceIdx.size() > 1 ) ..
		(*m_pVertexes)[bvidx].addAdjFace(fi);			// add adj face for vertex
		//(*m_pVertexes)[bvidx].dump();
	}

	// calc face normal:计算法向量
	fedgevec1 = (*m_pVertexes)[faceVertexsIdx[1]].m_v - (*m_pVertexes)[faceVertexsIdx[0]].m_v;
	fedgevec2 = (*m_pVertexes)[faceVertexsIdx[2]].m_v - (*m_pVertexes)[faceVertexsIdx[1]].m_v;
	f.m_normal = Cross(fedgevec1, fedgevec2).normalize();//
	m_faces.push_back(f);	// as 
	return fi;
}

Mesh::EDGEPOS Mesh::findAndInsertEdgePos(int bgVertexIdx, int edVertexIdx)//查找和插入边
{
//	m_edges.find()
	Edge e(bgVertexIdx, edVertexIdx);
	return m_edges.insert(e).first;	// if not exist, insert it.
}

inline Vertex& Mesh::getVertex(int idx)//获取点的索引
{
	return (*m_pVertexes)[idx];
}

inline Edge& Mesh::getEdge(Mesh::EDGEPOS ep)//获取边的索引
{
	return *ep;
}

inline Face& Mesh::getFace(int idx)//获取面的索引
{
	return m_faces[idx];
}

// get adjacent face of f, both of which have the same edge e
//  if edge only have one adj face, then return -1;
int Mesh::getAdjFace(int fidx, const Edge &e)//获取边的临界面
{
//	e.dump();

	ASSERT(e.m_adjFaceIdxSet.size() <= 2 && e.m_adjFaceIdxSet.size() >= 1);		// manifold? at least one adjacent?
	if( e.m_adjFaceIdxSet.size() == 1 )
	{
		ASSERT(e.m_adjFaceIdxSet[0] == fidx);			// at least one adjacent?
		return -1;
	}
	ASSERT(e.m_adjFaceIdxSet[0] == fidx || e.m_adjFaceIdxSet[1] == fidx);		// adjacent?
	
	return (e.m_adjFaceIdxSet[0] == fidx ? e.m_adjFaceIdxSet[1] : e.m_adjFaceIdxSet[0] );	
}
/*
Face* Mesh::getAdjFace(const Face &f, const Edge &e)
{
	ASSERT(e.m_adjFaceIdxSet.size() <= 2 && e.m_adjFaceIdxSet.size() >= 1);		// manifold? at least one adjacent?
	if( e.m_adjFaceIdxSet.size() == 1 )
	{
		ASSERT(e.m_adjFaceIdxSet[0] == f.m_index);			// at least one adjacent?
		return NULL;
	}
	ASSERT(e.m_adjFaceIdxSet[0] == f.m_index || e.m_adjFaceIdxSet[1] == f.m_index);		// adjacent?
	
	return (e.m_adjFaceIdxSet[0] == f.m_index ? &getFace(e.m_adjFaceIdxSet[1]) : &getFace(e.m_adjFaceIdxSet[0]) );	
}*/

//以中心为新顶点，n边的面划分为n个面
Mesh* Mesh::splitTriangleMesh()//分割成三角网格
{
	// split all faces into triangles
	// 1  find a face
	// 2  change the face into triangle
	// 3  add the left part of the face as triangls...
	// Simple solution:
	//   add all splited faces without deleting already exist info..
	//   then mark the be-splited faces entry to be no use...
	
	Mesh *p = new Mesh();
	
	// copy only the vertex position and index
	for( int i = 0; i < m_pVertexes->size(); i ++ )
	{
		Vertex v((*m_pVertexes)[i].m_v, (*m_pVertexes)[i].m_index);
		p->m_pVertexes->push_back(v);
	}

//	p->dump();
//	cout << endl;
	int fnum = m_faces.size();
	vector<int> newSplitFacesIdx;
	for ( int fi = 0; fi < fnum; fi ++ )
	{
		if( m_faces[fi].m_vertexIdxSet.size() > 3)
		{	// get central point first
			Vector3d v;
			int k = m_faces[fi].m_vertexIdxSet.size();
			for( int j = 0; j < k; j ++ )	// k vertices => k-2 triangles
				v += getVertex(m_faces[fi].m_vertexIdxSet[j]).m_v;
			v /= k;
			int centralvi = p->addVertex(v);
			// then split face into n faces with same vertex : the central point
			for( j = 0; j < k; j ++ )	// k vertices => k edges ==> k new faces
			{ 
				newSplitFacesIdx.push_back(centralvi);
				newSplitFacesIdx.push_back(m_faces[fi].m_vertexIdxSet[j]);
				newSplitFacesIdx.push_back(m_faces[fi].m_vertexIdxSet[(j+1) % k]);

				p->addFace(newSplitFacesIdx);
				newSplitFacesIdx.clear();
			}
		}
		else p->addFace(m_faces[fi].m_vertexIdxSet);
	}
	return p;
}

void Mesh::prepareLoopSubdivMesh()//以下是对新顶点位置的计算
{
	if(m_pSubdivVertexes)
	{
		m_pSubdivVertexes->clear();
		delete m_pSubdivVertexes;
	}
	m_pSubdivVertexes = new VERTEXSET;
	
	// for each vertex, calc a new Vertex对于每一个顶点产生一个新顶点
	double beta[20];
	for( int i = 1; i < 20; i ++ )
	{
		beta[i] = 1.0 / i * ( 5. / 8 - pow(3. / 8 + 1. / 4 * cos(2 * 3.1415926 / i), 2 ) );
	//beta[i] =(3-2*cos(2*3.1415/i))/9/i;
	}
	//proposed by Warren
/*	for( i = 3; i < 20; i ++ )
	{
		if(i == 3)
			beta[i] = 3. / 16;
		else 
			beta[i] = 3. / 8. / i;
	}*/
	FOR_EACH_VERTEX(vitr)//求新顶点
	{
		int k = vitr->m_adjEdgePosSet.size();
		ASSERT( k < 20 );//断言函数，返回一个布尔值
		if( ! vitr->isOnBoundary() )			// if not on boundary如果不是边界的话
		{
			Vector3d newV(vitr->m_v * ( 1. - k * beta[k]));
			for( int i = 0; i < k; i ++ )
			{
				int vi = getEdge(vitr->m_adjEdgePosSet[i]).getCounterVertex(vitr->m_index);
				newV += (getVertex(vi).m_v * beta[k]);
			}
			vitr->m_newVertexPointIdx = addSubdivVertex(newV);
		} 
		else if ( vitr->m_adjEdgePosSet.size() == 3 && vitr->m_adjFaceIdxSet.size() == 2 )
		{
			vitr->m_newVertexPointIdx = addSubdivVertex(vitr->m_v);
		}
		else if ( vitr->m_adjEdgePosSet.size() >= 2 )
		{
			// find the boundary edge:寻找边界边
			int benum = 0;
			Vector3d newV(vitr->m_v * 3. / 4);
			for (int i = 0; i < vitr->m_adjEdgePosSet.size(); i ++)
			{
				if (vitr->m_adjEdgePosSet[i]->isOnBoundary())
				{
					int vi = getEdge(vitr->m_adjEdgePosSet[i]).getCounterVertex(vitr->m_index);
					newV += (getVertex(vi).m_v / 8);
					benum ++;
				}
			}
			vitr->m_newVertexPointIdx = addSubdivVertex(newV);
			ASSERT(benum == 2);		// only two boundary edges connected to an extraordinary vertex
		}
		else 
		{
			cout << "Unused Vertex: ";
			vitr->dump();
		}
	}
	FOR_EACH_EDGE(vp)//求新边点
	{
		Vector3d newV = (getVertex(vp->m_bgVertexIdx).m_v + getVertex(vp->m_edVertexIdx).m_v) * 3. / 8.;//3/8(v0+v1)
		// find other two vertex on edge's two faces
		if ( vp->m_adjFaceIdxSet.size() == 2 )//如果邻接面有两个
		{
			Face &f = getFace(vp->m_adjFaceIdxSet[0]);
//			ASSERT(f.m_vertexIdxSet.size() == 3);
			for( int i = 0; i < f.m_edgePosSet.size(); i ++)
				if(vp == f.m_edgePosSet[i])		// vertex[i], vertex[i+1] is the index of the edge. vertex[i+2] is the point we search for
				{
					newV += ( getVertex(f.m_vertexIdxSet[(i+2) % f.m_vertexIdxSet.size()]).m_v / 8 );
					break;
				}
			Face &f2 = getFace(vp->m_adjFaceIdxSet[1]);
//			ASSERT(f2.m_vertexIdxSet.size() == 3);
			for( i = 0; i < f2.m_edgePosSet.size(); i ++)
				if(vp == f2.m_edgePosSet[i])		// vertex[i], vertex[i+1] is the index of the edge. vertex[i+2] is the point we search for
				{
					newV += ( getVertex(f2.m_vertexIdxSet[(i+2) % f2.m_vertexIdxSet.size()]).m_v / 8 );
					break;
				}
			vp->m_newEdgePointIdx = addSubdivVertex(newV);
		}
		else if ( vp->isOnBoundary() )//如果是边界边
		{	// extraordinary point
			 newV = getVertex(vp->m_bgVertexIdx).m_v + getVertex(vp->m_edVertexIdx).m_v;
			vp->m_newEdgePointIdx = addSubdivVertex(newV / 2);
		}
		else 
		{
			cout << "None manifold: ";
			vp->dump();
		}
	}

}

// 切分为三角片，再loop
Mesh* Mesh::calcLoopSubdivMesh(bool divBeforeLoop)
{
	if( divBeforeLoop )
	{
		FOR_EACH_FACE(fitr)
		{
			Mesh *p, *q;
			if(fitr->m_vertexIdxSet.size() > 3)
			{
				p = splitTriangleMesh();
//				p->dump();
				q = p->calcLoopSubdivMeshSep();
				p->reset();
				delete p;		// delete temp triangle-mesh删除临时的三角面片
				return q;
			}
		}
	}
	// fall through if no face to div:
	return calcLoopSubdivMeshSep();
}	
	
Mesh* Mesh::calcLoopSubdivMeshSep()// loop细分开始
{
	prepareLoopSubdivMesh();
	bool blFound;
	Mesh *pSubMesh = new Mesh();
	// link(copy) vertexes data
	pSubMesh->m_pVertexes = this->m_pSubdivVertexes;

//	FOR_EACH_FACE(fitr)		// Faces may changes when looping
	int fnum = m_faces.size();
	for( int i = 0; i < fnum; i ++ )
	{
		vector<int> innerFaceVertex;//内部顶点
		vector<int> cornerFaceVertex;//

		int k = m_faces[i].m_vertexIdxSet.size();
		for( int j = 0; j < k; j ++)
		{
		
			innerFaceVertex.push_back( (m_faces[i].m_edgePosSet[j])->m_newEdgePointIdx );
			//连接三个新边点新边点
			
			cornerFaceVertex.push_back( getVertex(m_faces[i].m_vertexIdxSet[j]).m_newVertexPointIdx );//插入新顶点
			cornerFaceVertex.push_back( m_faces[i].m_edgePosSet[j]->m_newEdgePointIdx );
			cornerFaceVertex.push_back( m_faces[i].m_edgePosSet[(j+k-1) % k]->m_newEdgePointIdx );
			//角上的三个三角形
			pSubMesh->addFace(cornerFaceVertex);
			cornerFaceVertex.clear();
		}
		pSubMesh->addFace(innerFaceVertex);
		innerFaceVertex.clear();
	}
	
	this->m_pSubdivVertexes = NULL;
	pSubMesh->printMeshInfo();
	return pSubMesh;
}


/*
// two old edition of Catmull.  errors a lot in somewhere ...

// first calc all edge's middle point, face's central point
// then calc all new edge point, and new vertex point (face point is ready)
void Mesh::prepareCatmullSubdivData()
{
	if(m_pSubdivVertexes)
	{
		m_pSubdivVertexes->clear();
		delete m_pSubdivVertexes;
	}
	m_pSubdivVertexes = new VERTEXSET;

	// edge mid point:
	FOR_EACH_EDGE(vp)
	{
		vp->setMidPoint( (getVertex(vp->m_bgVertexIdx).getVertex3d() + 
							getVertex(vp->m_edVertexIdx).getVertex3d()) / 2 );
	}
	// face central point:
	FOR_EACH_FACE(fitr)
	{
		Vector3d v;
		for( int j = 0; j < fitr->m_vertexIdxSet.size(); j ++ )
			v += getVertex(fitr->m_vertexIdxSet[j]).getVertex3d();

		fitr->m_newFacePointIdx = addSubdivVertex(v / fitr->m_vertexIdxSet.size());
	}

	
	// new edgepoint: two adj face point + 2 * midpoint / 4
	Vector3d v2;
	for( vp = m_edges.begin(); vp != m_edges.end(); vp ++)
	{
		ASSERT(vp->m_adjFaceIdxSet.size() <= 2);		// deals with manifold only
		ASSERT(vp->m_adjFaceIdxSet.size() > 0);			// all edges are built from faces
		
		// view otherside as a very slim face, that is, a line covering the edge
		if( vp->m_adjFaceIdxSet.size() == 2 )	
		{
			Vector3d v;
			v =	(vp->m_midPoint * 2 + \
				 ( (*m_pSubdivVertexes)[ getFace( vp->m_adjFaceIdxSet[1] ).m_newFacePointIdx] ).m_v +
				 ( (*m_pSubdivVertexes)[ getFace( vp->m_adjFaceIdxSet[0] ).m_newFacePointIdx] ).m_v)  / 4;
			vp->m_newEdgePointIdx = addSubdivVertex(v);
		}
		else	// vp->m_adjFaceIdxSet.size() == 1
		{
			vp->m_newEdgePointIdx = addSubdivVertex(vp->m_midPoint);
		}
	}
	// new vertex point:  Beta/k * all edge + Gama/k * all anti vertex + (1-Beta-Gama)old vertex 
	//                     (Beta = 3/2k, Gama = 1/4k, Beta = 6 * Gama)
	// == all( face point / faceVertexNum * gama / Beta 
	//    + edge point * 2 * 5 / 4 / k
	//    + old vertex point * 1-(6+2+5/2)* gama / k

	for( i = 0; i < m_pVertexes->size(); i ++)
	{
		Vector3d q, r;	// initially zero
		int k = (*m_pVertexes)[i].m_adjFaceIdxSet.size();
*/