TriangleList getSurroundingTriangles(QPointF *points, quint32 size, quint32 layers,
Vertex v, QPointF *centerPtr) {
	TriangleList result;
	if (!v.layer) {
		for (quint32 i = 0; i < size; ++i)
			result.append(TRIANGLE(0, i, 0));
		return result;
	}
	// inner part
	result.append(TRIANGLE(v.layer - 1, v.sector, 2 * v.index));
	if (v.index) {
		result.append(TRIANGLE(v.layer - 1, v.sector, 2 * v.index - 1));
		result.append(TRIANGLE(v.layer - 1, v.sector, 2 * v.index - 2));
	} else
		result.append(TRIANGLE(v.layer - 1, (v.sector + size - 1) % size, 2 * v.layer - 2));
	// outer part
	if (v.layer < layers) {
		result.append(TRIANGLE(v.layer, v.sector, 2 * v.index));
		result.append(TRIANGLE(v.layer, v.sector, 2 * v.index + 1));
		if (v.index) {
			result.append(TRIANGLE(v.layer, v.sector, 2 * v.index - 1));
		} else {
			result.append(TRIANGLE(v.layer, (v.sector + size - 1) % size, 2 * v.layer - 1));
			result.append(TRIANGLE(v.layer, (v.sector + size - 1) % size, 2 * v.layer));
		}
	}
	return result;
}

// groupedSliders are in the upper set of sliders
void TriangleDensityWidget::groupedSliderChangedSlot(int value)
{
	TriangleList triangles = triangleScene->triangles();
	double norm = getNorm();
	triangles.at(grouped_slider_idx)->xform()->density
		= (double)value / 1000. * norm;
	resetSliders(norm);
	emit dataChanged();
}

double phiFunction(QPointF *points, quint32 size, quint32 layers,
QPointF point, quint32 vertexNumber, QPointF *centerPtr) {
	Vertex vertex = getVertex(size, vertexNumber);
	TriangleList triangles = getSurroundingTriangles(points, size,
		layers, vertex, centerPtr);
	for (int i = 0; i < triangles.size(); ++i) {
		if (pointInTriangle(point, triangles.at(i)))
			return phiFunction(point, triangles.at(i),
			getPoint(points, size, layers, vertex, centerPtr));
	}
	return 0;
}

Deform::Deform(const float *P_data, int P_Num, const AdjList &adj_list, const TriangleList &triangle_list)
    :at(ORIGIN_HARD),
    P_data(P_data), 
    P_Num(P_Num), 
    max_iter(10), 
    min_tol(1e-3), 
    lambda(5), 
    adj_list(adj_list)
{

    for (size_t i = 0, i_end = triangle_list.size(); i < i_end; ++ i)
    {
        std::vector<int> face = triangle_list[i];
        std::sort(face.begin(), face.end());
        assert(face.size() == 3);
        face_list.push_back(Eigen::Vector3i(face[0], face[1], face[2]));
    }

    P.resize(3, P_Num);
    for (int i = 0; i != P_Num; ++i) {P.col(i) << P_data[3*i], P_data[3*i+1], P_data[3*i+2];}
    P_Prime = P;
    R = vector<Matrix3f>(P_Num, Matrix3f::Identity());

    // Weight
    build_weight_matrix();
}

void MeshMender::FindNeighbors(Triangle* tri,
				   TriangleList&possibleNeighbors,
				   Triangle** neighbor1,
				   Triangle** neighbor2,
				   std::vector< Vertex >& theVerts)
{
	*neighbor1 = NULL;
	*neighbor2 = NULL;

	std::vector<Triangle*> theNeighbors;
	for(unsigned int n = 0; n < possibleNeighbors.size(); ++n)
	{
		TriID tID = possibleNeighbors[n];
		Triangle* possible =&(m_Triangles[ tID]);
		if(possible != tri ) //check for myself
		{
			if( SharesEdge(tri, possible, theVerts)  )
			{
				theNeighbors.push_back(possible);

			}
		}
	}

	if(theNeighbors.size()>0)
		*neighbor1 = theNeighbors[0];
	if(theNeighbors.size()>1)
		*neighbor2 = theNeighbors[1];
}

  void KDTree::generateEventList( TriangleList& triList, AABB& parentBox )
  {
    //Start with an empty event list
    eventList.clear();

    //Go through all the triangles passed in.
    for(unsigned i = 0; i < triList.size(); ++i)
    {
      //Clip the triangle to the parent box
      Triangle tri = triList[i];
      clipTriToParentBox(tri, parentBox);

      //And the box be the AABB of this event
      AABB* pBox = &parentBox;

      //Grab the minimum and maximum points of the triangle as per this split axis
      float pMin = GeometryLibrary::minPos(tri, curAxis);
      float pMax = GeometryLibrary::maxPos(tri, curAxis);

      //If the maximum and minimum points are the same, we have a coplanar event
      if(pMax == pMin)
        eventList.push_back(KDEvent(Coplanar, &tri, pMin, pBox));
      //Otherwise start at the minimum and end at the maximum on this axis
      else
      {
        eventList.push_back(KDEvent(Starting, &tri, pMin, pBox));
        eventList.push_back(KDEvent(Ending, &tri, pMax, pBox));
      }
    }

    //Sort according to the operator < provided so that the events are in ascending order
    std::sort(eventList.begin(), eventList.end());
  }

bool Triangulator::check_triangle(Vertex *first, TriangleList &triangles) {
	// path is a dot
	if (first->next == first)
		return true;

	// path is a two lines
	if (first->next->next == first)
		return true;

	// path is triangle
	if (first->next->next->next == first) {
		triangles.push_back(first->index);
		triangles.push_back(first->next->index);
		triangles.push_back(first->next->next->index);
		return true;
	}

	return false;
}

void TriangleDensityWidget::reset()
{
	TriangleList triangles = triangleScene->triangles();

	// make more sliders if necessary
	while (sliders.size() < triangles.size())
	{
		GroupedSlider* s
			= new GroupedSlider(Qt::Horizontal, this, sliders.size());
		QLabel* name = new QLabel(QString::number(sliders.size() + 1));
		QHBoxLayout* hl = new QHBoxLayout();
		hl->addWidget(name);
		hl->addWidget(s);
		dynamic_cast<QVBoxLayout*>
			(m_scrollAreaWidgetContents->layout())->insertLayout(-1,hl,0);
		s->setRange(0, 1000);
		s->setVisible(false);
		sliders.append(s);
		slider_names.append(name);
		connect(s, SIGNAL(valueChanged(int)), this, SLOT(groupedSliderChangedSlot(int)));
		connect(s, SIGNAL(sliderPressed()), this, SLOT(groupedSliderPressedSlot()));
		connect(s, SIGNAL(undoStateSignal()), this, SIGNAL(undoStateSignal()));
	}
	// hide non-used sliders
	for (int n = triangles.size() ; n < sliders.size() ; n++)
	{
		sliders.at(n)->setVisible(false);
		slider_names.at(n)->setVisible(false);
	}
	resetSliders(getNorm());

	QStringList items;
	items << tr("None");
	for (int n = 1 ; n <= genome->size() ; n++)
		items << QString::number(n);
	int n = m_crossComboBox->currentIndex();
	m_crossComboBox->blockSignals(true);
	m_crossComboBox->clear();
	m_crossComboBox->addItems(items);
	m_crossComboBox->setCurrentIndex(n);
	m_crossComboBox->blockSignals(false);
}

void triangle_tree(
  const Eigen::MatrixXd & V,
  const Eigen::MatrixXi & F,
  TriTree & tree,
  TriangleList & tlist)
{
  assert(F.cols() == 3);
  tlist.clear();

  // Loop over facets
  for(int f = 0;f<F.rows();f++)
  {
    Point3 a(V(F(f,0),0), V(F(f,0),1), V(F(f,0),2));
    Point3 b(V(F(f,1),0), V(F(f,1),1), V(F(f,1),2));
    Point3 c(V(F(f,2),0), V(F(f,2),1), V(F(f,2),2));
    tlist.push_back(Triangle3( a,b,c));
  }
  // constructs AABB tree
  tree.clear();
  tree.insert(tlist.begin(),tlist.end());
}

  void KDTree::splitTriList( TriangleList& l, TriangleList& r, TriangleList& p, float pos )
  {
    curAxis = splitAxis;
    unsigned left, right, coplanar, side;

    //Go through every triangle in the triangle list
    for(unsigned i = 0; i < p.size(); ++i)
    {
      Triangle& tri = p[i];
      left = right = coplanar = 0;
      CountVertPositions(tri, left, right, coplanar, splitAxis, pos);

      side = max(left, max(right, coplanar));

      if(side == left)
        l.push_back(tri);
      else if(side == right)
        r.push_back(tri);
      else if(side == coplanar)
        l.push_back(tri);
    }
  }

  void KDTree::findMinPlane(TriangleList& triList, AABB& parentBox)
  {
    unsigned Nl, Nr, Nc, Vs, Ve, Vc;
    Vs = Ve = Vc = 0;

    //Set minimum cost to infinite
    minCost = FLT_MAX;

    //For every possible axis,
    for(unsigned i = 0; i < NumAxes; ++i)
    {
      //Generate the event list for this axis
      curAxis = (SplitAxis)i;
      generateEventList(triList, parentBox);

      //All of the triangles are to our right.
      //These will remain through iterations on positions
      Nl = 0;
      Nr = triList.size();
      Nc = 0;

      //For every position
      for(unsigned j = 0; j < eventList.size(); )
      {
        float curPos = eventList[j].eventPos;
        Vs = Ve = Vc = 0;
        //Count the triangles starting, ending, and coplanar with this position
        //This will advance j to the next event position
        countTrisOfEvent(Vs, Ve, Vc, j, curPos);

        Nc  = Vc;
        Nr -= Ve + Vc;

        //The last index is the positions we care about.
        calcCostOfPlane(Nl, Nr, Nc, parentBox, curPos);

        Nl += Vs + Vc;

        //Update the lowest possible plane
        if(curCost < minCost)
        {
          minCost = curCost;

          //Save what axis and position we're going to cut at so far...
          splitPos = curPos;
          splitAxis = curAxis;
        }
      }
    }
  }

void MeshMender::UpdateIndices(const size_t oldIndex , const size_t newIndex , TriangleList& curGroup)
{
   //make any triangle that used the oldIndex use the newIndex instead

	for( size_t t = 0; t < curGroup.size(); ++t )
	{
		TriID tID = curGroup[ t ];
		for(size_t indx = 0 ; indx < 3 ; ++indx)
		{
			if(m_Triangles[tID].indices[indx] == oldIndex)
			{
				m_Triangles[tID].indices[indx] = newIndex;
			}
		}
	}

}

void Triangulator::triangulate(const Contour &contour, TriangleList &triangles, int index_offset) {
	Path path;
	build_path(contour, path, index_offset);
	triangles.reserve(triangles.size() + 3*(path.size() - 2));
	split_path(&path.front(), triangles);
}

TriangleList getCommonTriangles(QPointF *points, quint32 size, quint32 layers,
Vertex v1, Vertex v2, QPointF *centerPtr) {
	TriangleList result;
	if (v1.layer > v2.layer)
		qSwap(v1, v2);
	if (!v2.layer)
		return result;
	if (v1.layer == 0 && v2.layer == 1) {
		result.append(TRIANGLE(0, v2.sector, 0));
		result.append(TRIANGLE(0, (v2.sector + size - 1) % size, 0));
	} else if (v1.sector == v2.sector) {
		if (v1.layer == v2.layer) {
			if (v2.index == v1.index + 1) {
				if (v1.layer < layers)
					result.append(TRIANGLE(v1.layer, v1.sector, v1.index * 2 + 1));
				result.append(TRIANGLE(v1.layer - 1, v1.sector, v1.index * 2));
			} else if (v2.index == v1.index - 1) {
				if (v1.layer < layers)
					result.append(TRIANGLE(v1.layer, v1.sector, v2.index * 2 + 1));
				result.append(TRIANGLE(v1.layer - 1, v1.sector, v2.index * 2));
			}
		}
		else if (v2.layer == v1.layer + 1) {
			if (v2.index == v1.index) {
				if (v1.index)
					result.append(TRIANGLE(v1.layer, v1.sector, v1.index * 2 - 1));
				else
					result.append(TRIANGLE(v1.layer, (v1.sector + size - 1) % size, v1.layer * 2));
				result.append(TRIANGLE(v1.layer, v1.sector, v1.index * 2));
			} else if (v2.index == v1.index + 1) {
				result.append(TRIANGLE(v1.layer, v1.sector, v1.index * 2));
				result.append(TRIANGLE(v1.layer, v1.sector, v1.index * 2 + 1));
			}
		}
	} else if ((v2.sector == (v1.sector + 1) % size)
	&& v1.index == v1.layer - 1 && v2.index == 0) {
		if (v1.layer == v2.layer) {
			result.append(TRIANGLE(v1.layer - 1, v1.sector, v1.index * 2));
			if (v1.layer < layers)
				result.append(TRIANGLE(v1.layer, v1.sector, v1.index * 2 + 1));
		} else if (v1.layer == v2.layer + 1) {
			result.append(TRIANGLE(v2.layer, v1.sector, v1.index * 2 - 1));
			result.append(TRIANGLE(v2.layer, v1.sector, v1.index * 2));
		}
	} else if ((v1.sector == (v2.sector + 1) % size)
	&& v2.index == v2.layer - 1 && v1.index == 0) {
		if (v1.layer == v2.layer) {
			result.append(TRIANGLE(v1.layer - 1, v2.sector, v2.index * 2));
			if (v1.layer < layers)
				result.append(TRIANGLE(v1.layer, v2.sector, v2.index * 2 + 1));
		} else if (v1.layer == v2.layer - 1) {
			result.append(TRIANGLE(v1.layer, v2.sector, v2.index * 2 - 1));
			result.append(TRIANGLE(v1.layer, v2.sector, v2.index * 2));
		}
	}
	return result;
}

void KDTree::Subdivide(KDTreeNode &node,TriangleList *triangles,aabb& box,int depth)
{
	if(!triangles)return ;
	int count = triangles->GetCount();
	if( count < minTrianglesPerleafNode ||(depth>=20&&count<=maxTrianglesPerleafNode))
	{
		node.SetTriangleList(triangles);
		node.Type = LEFT;
		node.box = box;
		return ;
	}

	
	aabb frontBox,backBox;
	real splitPosition;
	bool foundOptimalSplit = findOptimalSplitPositon(triangles,box,depth,splitPosition,frontBox, backBox);

	if(foundOptimalSplit == true)
	{
		
		node.Type = PATITION;
		node.SetAxis(depth%Dimension);
		node.SetSplitPosition(splitPosition);
		node.box = box;
		

		TriangleList *frontTriangles = new TriangleList();
		TriangleList *backTriangles =	new TriangleList();
		for( int i=0; i < count; i++)
		{
			//Determine on which side of the split each
			//triangle belongs.
		    TriangleNode * triangle= triangles->GetHead();
			triangles->DeleteHead();
			
			int position = partitionTriangle(triangle,depth,splitPosition);
			triangle->next = NULL;
			switch(position)
			{
			case kdBefore:
				frontTriangles->append(triangle);
				break;
			case kdAfter:
				backTriangles->append(triangle);
				break;
			case kdIntersection:
				//frontTriangles->append(triangle);
				backTriangles->append(triangle);
				break;
			}
			
		}
		node.m_lchild = new KDTreeNode();
		node.m_rchild = new KDTreeNode();
		Subdivide(*node.m_lchild,frontTriangles,frontBox,depth+1);
		Subdivide(*node.m_rchild,backTriangles,backBox,depth+1);
	}else
	{
		
		node.SetTriangleList(triangles);
		node.Type = LEFT;
		node.box = box;
	}

}

void MeshMender::ProcessBinormals(TriangleList& possibleNeighbors,
								std::vector< Vertex >&    theVerts,
								std::vector< unsigned int >& mappingNewToOldVert,
								D3DXVECTOR3 workingPosition)
{
		NeighborGroupList neighborGroups;//a fresh group for each pass


		//reset each triangle to prepare for smoothing group building
		unsigned int i;
		for(i =0; i < possibleNeighbors.size(); ++i )
		{
			m_Triangles[ possibleNeighbors[i] ].Reset();
		}

		//now start building groups
		CanSmoothBinormalsChecker canSmoothBinormalsChecker;
		for(i =0; i < possibleNeighbors.size(); ++i )
		{
			Triangle* currTri = &(m_Triangles[ possibleNeighbors[i] ]);
			assert(currTri);
			if(!currTri->handled)
			{
				BuildGroups(currTri,possibleNeighbors,
							neighborGroups, theVerts,
							&canSmoothBinormalsChecker ,MinBinormalsCreaseCosAngle );
			}
		}


		std::vector<D3DXVECTOR3> groupBinormalVectors;


		for(i=0; i<neighborGroups.size(); ++i)
		{
			D3DXVECTOR3 gbinormal(0,0,0);
			for(unsigned int t = 0; t < neighborGroups[i].size(); ++t)//for each triangle in the group,
			{
				TriID tID = neighborGroups[i][t];
				gbinormal+=  m_Triangles[tID].binormal;
			}
			gbinormal = glm::normalize(gbinormal.GLMvec());//D3DXVec3Normalize( &gbinormal, &gbinormal );
			groupBinormalVectors.push_back(gbinormal);
		}

		//next step, ensure that triangles in different groups are not
		//sharing vertices. and give the shared vertex their new group vector
		std::set<size_t> otherGroupsIndices;
		for( i = 0; i < neighborGroups.size(); ++i )
		{
			TriangleList& curGroup = neighborGroups[ i ];
			std::set<size_t> thisGroupIndices;

			for( size_t t = 0; t < curGroup.size(); ++t ) //for each tri
			{
				TriID tID = curGroup[ t ];
				for(size_t indx = 0; indx < 3 ; ++indx)//for each vert in that tri
				{
					//if it is at the positions in question
					if( theVerts[ m_Triangles[tID].indices[indx] ].pos  == workingPosition)
					{
						//see if another group is already using this vert
						if(otherGroupsIndices.find( m_Triangles[tID].indices[indx] ) != otherGroupsIndices.end() )
						{
							//then we need to make a new vertex
							Vertex ov;
							ov = theVerts[ m_Triangles[tID].indices[indx] ];
							ov.binormal = groupBinormalVectors[i];
							size_t oldIndex = m_Triangles[tID].indices[indx];
							size_t newIndex = theVerts.size();
							theVerts.push_back(ov);
							AppendToMapping( oldIndex , m_originalNumVerts , mappingNewToOldVert);
							UpdateIndices(oldIndex,newIndex,curGroup);
						}
						else
						{
							//otherwise, just update it with the new vector
							theVerts[ m_Triangles[tID].indices[indx] ].binormal = groupBinormalVectors[i];
						}

						//store that we have used this index, so other groups can check
						thisGroupIndices.insert(m_Triangles[tID].indices[indx]);
					}
				}

			}

			for(std::set<size_t>::iterator it = thisGroupIndices.begin(); it!= thisGroupIndices.end() ; ++it)
			{
				otherGroupsIndices.insert(*it);
			}

		}

}

void GeometryEngine::initGeometry(TriangleList triangles, QVector<QVector3D> lines, QVector<QVector3D> points)
{
    isTransparent = false;

    initializeOpenGLFunctions();

    glBlendFunc (GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);

    // Generate 2 VBOs
    arrayBuf.create();
    indexBuf.create();
    arrayBufLines.create();
    arrayBufPoints.create();

    std::vector<VertexData> vertices;
    std::vector<GLuint> indices;
    std::vector<GLuint> tmp(3);

    // iterate over all triangles
    for (uint i = 0; i < triangles.size(); i++) {
        // iterate over all vertices in triangle
        for (int j = 0; j < 3; j++) {
            // create vertex with texture coords
            VertexData vertex = {
                QVector3D(triangles[i][j][0], triangles[i][j][1], triangles[i][j][2]),
                QVector2D(abs(((j+1)%2)-1), abs(((j+1)%3)-1)) // tex coords (0,0),(1,1),(0,1)
            };

            // is vertex already in indices?
            GLuint idx = indexOf(vertices, vertex);
            if (idx >= vertices.size()) {
                // no, add it to the end of the list
                //idx = vertices.size();
                vertices.push_back(vertex);
            }
            // prime the index of current vertex for insertion
            tmp[j] = idx;
        }
        // insert vertex indices of current triangle
        indices.insert(indices.end(), tmp.begin(), tmp.end());

        // render both sides of triangles, for now as a #define option
#if TWO_SIDED
        std::reverse(tmp.begin(), tmp.end());
        indices.insert(indices.end(), tmp.begin(), tmp.end());
#endif
    }

#if DEBUG
    std::cout << "Vertices:" << std::endl << vertices.size() << std::endl;
    for (auto i = vertices.begin(); i != vertices.end(); ++i)
        std::cout << "(" << (*i).position[0] <<"," << (*i).position[1] <<"," << (*i).position[2] <<")" << ' ';
    std::cout << std::endl;

    std::cout << "Indices:" << std::endl << indices.size() << std::endl;
    for (auto i = indices.begin(); i != indices.end(); ++i)
        std::cout << *i << ' ';
    std::cout << std::endl;
#endif

    arrayBuf.bind();
    arrayBuf.allocate(&vertices[0], vertices.size() * sizeof(VertexData));

    indexBuf.bind();
    indexBuf.allocate(&indices[0], indices.size() * sizeof(GLuint));

    idxLen = indices.size();

    if (!lines.empty())
    {
        arrayBufLines.bind();
        arrayBufLines.allocate(&lines[0], lines.size() * sizeof(QVector3D));
    }

    if (!points.empty())
    {
        arrayBufPoints.bind();
        arrayBufPoints.allocate(&points[0], points.size() * sizeof(QVector3D));
    }
}

//.........这里部分代码省略.........
            d3dxMesh->UnlockVertexBuffer();
            d3dxMesh->Release();

            // Free our device
            pd3dDevice->Release();

            // Error!
            return false;
        }

        // This table pairs an index from the .X file to an index in the buffer that
        // holds the vertices for this subset
        XIndicesTable xIndicesTable;

        // For each of the indices in the strip, puts its vertex ID into the indices
        // table.  Use the counter to determine which vertex this is.
        {
            GeometryIndex vertexCounter = 0;
            for (DWORD e = 0; e < numStripIndices; ++e)
            {
                // Insert the entry [x-mesh index, subset index] into the table
                XIndicesTableInsertResult result = xIndicesTable.insert(XIndicesEntry(pXIndices[e], vertexCounter));

                // If the result was successful (this isn't a duplicated X-mesh index) increment the vertex counter
                if (result.second)
                    vertexCounter++;
            }
        }

        // Grab the number of vertices this geometry uses
        DWORD numVertices = (DWORD)xIndicesTable.size();

        // This buffer holds all of the triangles in this subset
        TriangleList triangles;

        // This list keeps track of locations in the strip where the winding order changes.  This is necessary
        // because this next part will remove degenerate triangles from the list.
        std::set<size_t> windingChanges;

        // Generate the list of triangles from the strip provided
        for (DWORD t = 0; t < numStripIndices - 2; ++t)
        {
            // Build the triangle that will be added to the buffer
            // CHANGED July 25, 2008:  the winding order is wrong here
            //Triangle tri = { pXIndices[t + 0], pXIndices[t + 1], pXIndices[t + 2] };
            Triangle tri = { pXIndices[t + 0], pXIndices[t + 2], pXIndices[t + 1] };



            // Convert the triangle into subset-indices by using the lookup table
            // we generated before.
            tri.index[0] = xIndicesTable.find(tri.index[0])->second;
            tri.index[1] = xIndicesTable.find(tri.index[1])->second;
            tri.index[2] = xIndicesTable.find(tri.index[2])->second;

            // Check to make sure this triangle isn't degenerate.  If it is, we can just skip
            // this triangle entirely to simplify the geometry.
            if (tri.index[0] == tri.index[1] || tri.index[1] == tri.index[2] || tri.index[0] == tri.index[2])
            {
                // Try to find the winding in the list
                std::set<size_t>::iterator currentWinding = windingChanges.find(triangles.size());

                // Add this to the winding change list, or remove the change if it's already there
                if (currentWinding != windingChanges.end())
                    windingChanges.erase(currentWinding);
                else

void Renderer::Render( void )
{
	for (unsigned i = 0; i < m_renderUnitList.size(); i++)
	{
		RenderUnit* renderUnit = m_renderUnitList[i];

		unsigned nVerts = renderUnit->m_vb->Size();
		unsigned nTriangles = renderUnit->m_ib->Size() / 3;

		VsOutList vsOuts(nVerts);
		TriangleList triangles;

		// 对每个顶点执行VS
		for (unsigned j = 0; j < nVerts; j++)
		{
			vsOuts[j] = renderUnit->m_vs->Main((*renderUnit->m_vb)[j]);
		}

		// triangle setup (trivial-rejection, clipping)
		for (unsigned j = 0; j < nTriangles; j++)
		{
			Triangle tri;
			tri.iV0 = (*renderUnit->m_ib)[3 * j + 0];
			tri.iV1 = (*renderUnit->m_ib)[3 * j + 1];
			tri.iV2 = (*renderUnit->m_ib)[3 * j + 2];

			if (TrivialReject(tri, vsOuts))
			{
				continue;
			}
			else if (RemoveBackface(tri, vsOuts, CULL_MODE_CCW))
			{
				continue;
			}
			else if (TrivialAccept(tri, vsOuts))
			{
				triangles.push_back(tri);
			}
			else
			{
				// TODO: do clipping here
				triangles.push_back(tri);
			}
		}

		int halfRtWidth = m_renderTarget->GetWidth() >> 1;
		int halfRtHeight = m_renderTarget->GetHeight() >> 1;

		for (unsigned j = 0; j < vsOuts.size(); j++)
		{
			Vector4& position = vsOuts[j].position;

			// perspective-divide
			position.x /= position.w; 
			position.y /= position.w;
			position.z /= position.w;

			// 转化到屏幕坐标
			position.x = ( position.x + 1.0f) * halfRtWidth;
			position.y = (-position.y + 1.0f) * halfRtHeight;
		}
		
		// 光栅化每个三角形
		for (unsigned j = 0; j < triangles.size(); j++)
		{
			VertexShaderOutput& v0 = vsOuts[triangles[j].iV0];
			VertexShaderOutput& v1 = vsOuts[triangles[j].iV1];
			VertexShaderOutput& v2 = vsOuts[triangles[j].iV2];

			if (renderUnit->m_wireFrame)	// fill mode: wireframe
			{
				int x0 = int(v0.position.x);
				int y0 = int(v0.position.y);
				int x1 = int(v1.position.x);
				int y1 = int(v1.position.y);
				int x2 = int(v2.position.x);
				int y2 = int(v2.position.y);

				DrawLine(x0, y0, x1, y1, 0xFFFFFFFF);
				DrawLine(x0, y0, x2, y2, 0xFFFFFFFF);
				DrawLine(x1, y1, x2, y2, 0xFFFFFFFF);
			}
			else	// fill mode: solid
			{
				VertexShaderOutput* sv;
				VertexShaderOutput* mv;
				VertexShaderOutput* ev;
				
				// 按Y值给三个顶点排序
				if (v0.position.y < v1.position.y)
				{
					sv = &v0;
					ev = &v1;
				}
				else
				{
					sv = &v1;
					ev = &v0;
				}

//.........这里部分代码省略.........

void ProgressiveTriangleGeometry::FindEdgeToCollapse(VertexList& /*org_vertex_list*/,
	TriangleList& /*org_triangle_list*/, VertexList& vertex_list, TriangleList& triangle_list, Edge& edge) {
	if (triangle_list.empty())
		return;

	float current_error = 0.0f;
	float current_max_error = 0.0f;

	edge.v1_ = 0;
	edge.v2_ = 0;
	edge.triangle_list_.clear();

	// Calculate mean error.
	VertexList::iterator v_iter;
	for (v_iter = vertex_list.begin();
	     v_iter != vertex_list.end();
	     ++v_iter) {
		if (v_iter == vertex_list.begin()) {
			current_max_error = (*v_iter)->error_;
		} else if((*v_iter)->error_ > current_max_error) {
			current_max_error = (*v_iter)->error_;
		}

		current_error += (*v_iter)->error_;
	}

	current_error /= (float)vertex_list.size();

	float min_error = 0.0f;
	float min_error1 = 0.0f;	// Temporary error value storage for _edge->v1_.
	float min_error2 = 0.0f;	// Temporary error value storage for _edge->v2_.
	bool first = true;

	// Test vertex collaps on all triangles.
	TriangleList::iterator tri_iter;
	for (tri_iter = triangle_list.begin();
	     tri_iter != triangle_list.end();
	     ++tri_iter) {
		Triangle* triangle = *tri_iter;
		vec3 diff1;
		vec3 diff2;
		Vertex mid;

		// Test V1 and V2.
		mid.x() = (triangle->v1_->x() + triangle->v2_->x()) * 0.5f;
		mid.y() = (triangle->v1_->y() + triangle->v2_->y()) * 0.5f;
		mid.z() = (triangle->v1_->z() + triangle->v2_->z()) * 0.5f;

		// Calculate the distance between the new, merged position,
		// and the original vertex position.
		diff1.Set(mid.x() - triangle->v1_->twin_->x(),
		            mid.y() - triangle->v1_->twin_->y(),
		            mid.z() - triangle->v1_->twin_->z());
		diff2.Set(mid.x() - triangle->v2_->twin_->x(),
		            mid.y() - triangle->v2_->twin_->y(),
		            mid.z() - triangle->v2_->twin_->z());

		float error1 = diff1.GetLength() + triangle->v1_->error_;
		float error2 = diff2.GetLength() + triangle->v2_->error_;
		float error = (error1 + error2 + current_error) / 3.0f;

		if (first == true || error < min_error) {
			edge.v1_ = triangle->v1_;
			edge.v2_ = triangle->v2_;
			min_error1 = error1;
			min_error2 = error2;
			min_error = error;
			first = false;
		}

		// Test V2 and V3.
		mid.x() = (triangle->v2_->x() + triangle->v3_->x()) * 0.5f;
		mid.y() = (triangle->v2_->y() + triangle->v3_->y()) * 0.5f;
		mid.z() = (triangle->v2_->z() + triangle->v3_->z()) * 0.5f;

		// Calculate the distance between the new, merged position,
		// and the original vertex position.
		diff1.Set(mid.x() - triangle->v2_->twin_->x(),
		            mid.y() - triangle->v2_->twin_->y(),
		            mid.z() - triangle->v2_->twin_->z());
		diff2.Set(mid.x() - triangle->v3_->twin_->x(),
		            mid.y() - triangle->v3_->twin_->y(),
		            mid.z() - triangle->v3_->twin_->z());

		error1 = diff1.GetLength() + triangle->v1_->error_;
		error2 = diff2.GetLength() + triangle->v2_->error_;
		error = (error1 + error2 + current_error) / 3.0f;

		if (error < min_error) {
			edge.v1_ = triangle->v1_;
			edge.v2_ = triangle->v2_;
			min_error = error;
			min_error1 = error1;
			min_error2 = error2;
		}

		// Test V3 and V1.
		mid.x() = (triangle->v3_->x() + triangle->v1_->x()) * 0.5f;
		mid.y() = (triangle->v3_->y() + triangle->v1_->y()) * 0.5f;
		mid.z() = (triangle->v3_->z() + triangle->v1_->z()) * 0.5f;
//.........这里部分代码省略.........