nuclear@0: /*
nuclear@0: ---------------------------------------------------------------------------
nuclear@0: Open Asset Import Library (assimp)
nuclear@0: ---------------------------------------------------------------------------
nuclear@0: 
nuclear@0: Copyright (c) 2006-2012, assimp team
nuclear@0: 
nuclear@0: All rights reserved.
nuclear@0: 
nuclear@0: Redistribution and use of this software in source and binary forms, 
nuclear@0: with or without modification, are permitted provided that the following 
nuclear@0: conditions are met:
nuclear@0: 
nuclear@0: * Redistributions of source code must retain the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer.
nuclear@0: 
nuclear@0: * Redistributions in binary form must reproduce the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer in the documentation and/or other
nuclear@0:   materials provided with the distribution.
nuclear@0: 
nuclear@0: * Neither the name of the assimp team, nor the names of its
nuclear@0:   contributors may be used to endorse or promote products
nuclear@0:   derived from this software without specific prior
nuclear@0:   written permission of the assimp team.
nuclear@0: 
nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0: ---------------------------------------------------------------------------
nuclear@0: */
nuclear@0: 
nuclear@0: /** @file  TriangulateProcess.cpp
nuclear@0:  *  @brief Implementation of the post processing step to split up
nuclear@0:  *    all faces with more than three indices into triangles.
nuclear@0:  *
nuclear@0:  *
nuclear@0:  *  The triangulation algorithm will handle concave or convex polygons.
nuclear@0:  *  Self-intersecting or non-planar polygons are not rejected, but
nuclear@0:  *  they're probably not triangulated correctly.
nuclear@0:  *
nuclear@0:  * DEBUG SWITCHES - do not enable any of them in release builds:
nuclear@0:  *
nuclear@0:  * AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
nuclear@0:  *   - generates vertex colors to represent the face winding order.
nuclear@0:  *     the first vertex of a polygon becomes red, the last blue.
nuclear@0:  * AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0:  *   - dump all polygons and their triangulation sequences to
nuclear@0:  *     a file
nuclear@0:  */
nuclear@0: 
nuclear@0: #include "AssimpPCH.h"
nuclear@0: 
nuclear@0: #ifndef ASSIMP_BUILD_NO_TRIANGULATE_PROCESS
nuclear@0: #include "TriangulateProcess.h"
nuclear@0: #include "ProcessHelper.h"
nuclear@0: #include "PolyTools.h"
nuclear@0: 
nuclear@0: //#define AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
nuclear@0: //#define AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0: 
nuclear@0: #define POLY_GRID_Y 40
nuclear@0: #define POLY_GRID_X 70
nuclear@0: #define POLY_GRID_XPAD 20
nuclear@0: #define POLY_OUTPUT_FILE "assimp_polygons_debug.txt"
nuclear@0: 
nuclear@0: using namespace Assimp;
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Constructor to be privately used by Importer
nuclear@0: TriangulateProcess::TriangulateProcess()
nuclear@0: {
nuclear@0: 	// nothing to do here
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Destructor, private as well
nuclear@0: TriangulateProcess::~TriangulateProcess()
nuclear@0: {
nuclear@0: 	// nothing to do here
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Returns whether the processing step is present in the given flag field.
nuclear@0: bool TriangulateProcess::IsActive( unsigned int pFlags) const
nuclear@0: {
nuclear@0: 	return (pFlags & aiProcess_Triangulate) != 0;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Executes the post processing step on the given imported data.
nuclear@0: void TriangulateProcess::Execute( aiScene* pScene)
nuclear@0: {
nuclear@0: 	DefaultLogger::get()->debug("TriangulateProcess begin");
nuclear@0: 
nuclear@0: 	bool bHas = false;
nuclear@0: 	for( unsigned int a = 0; a < pScene->mNumMeshes; a++)
nuclear@0: 	{
nuclear@0: 		if(	TriangulateMesh( pScene->mMeshes[a]))
nuclear@0: 			bHas = true;
nuclear@0: 	}
nuclear@0: 	if (bHas)DefaultLogger::get()->info ("TriangulateProcess finished. All polygons have been triangulated.");
nuclear@0: 	else     DefaultLogger::get()->debug("TriangulateProcess finished. There was nothing to be done.");
nuclear@0: }
nuclear@0: 
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Triangulates the given mesh.
nuclear@0: bool TriangulateProcess::TriangulateMesh( aiMesh* pMesh)
nuclear@0: {
nuclear@0: 	// Now we have aiMesh::mPrimitiveTypes, so this is only here for test cases
nuclear@0: 	if (!pMesh->mPrimitiveTypes)	{
nuclear@0: 		bool bNeed = false;
nuclear@0: 
nuclear@0: 		for( unsigned int a = 0; a < pMesh->mNumFaces; a++)	{
nuclear@0: 			const aiFace& face = pMesh->mFaces[a];
nuclear@0: 
nuclear@0: 			if( face.mNumIndices != 3)	{
nuclear@0: 				bNeed = true;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 		if (!bNeed)
nuclear@0: 			return false;
nuclear@0: 	}
nuclear@0: 	else if (!(pMesh->mPrimitiveTypes & aiPrimitiveType_POLYGON)) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Find out how many output faces we'll get
nuclear@0: 	unsigned int numOut = 0, max_out = 0;
nuclear@0: 	bool get_normals = true;
nuclear@0: 	for( unsigned int a = 0; a < pMesh->mNumFaces; a++)	{
nuclear@0: 		aiFace& face = pMesh->mFaces[a];
nuclear@0: 		if (face.mNumIndices <= 4) {
nuclear@0: 			get_normals = false;
nuclear@0: 		}
nuclear@0: 		if( face.mNumIndices <= 3) {
nuclear@0: 			numOut++;
nuclear@0: 
nuclear@0: 		}	
nuclear@0: 		else {
nuclear@0: 			numOut += face.mNumIndices-2;
nuclear@0: 			max_out = std::max(max_out,face.mNumIndices);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Just another check whether aiMesh::mPrimitiveTypes is correct
nuclear@0: 	assert(numOut != pMesh->mNumFaces);
nuclear@0: 
nuclear@0: 	aiVector3D* nor_out = NULL;
nuclear@0: 
nuclear@0: 	// if we don't have normals yet, but expect them to be a cheap side
nuclear@0: 	// product of triangulation anyway, allocate storage for them.
nuclear@0: 	if (!pMesh->mNormals && get_normals) {
nuclear@0: 		// XXX need a mechanism to inform the GenVertexNormals process to treat these normals as preprocessed per-face normals
nuclear@0: 	//	nor_out = pMesh->mNormals = new aiVector3D[pMesh->mNumVertices];
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// the output mesh will contain triangles, but no polys anymore
nuclear@0: 	pMesh->mPrimitiveTypes |= aiPrimitiveType_TRIANGLE;
nuclear@0: 	pMesh->mPrimitiveTypes &= ~aiPrimitiveType_POLYGON;
nuclear@0: 
nuclear@0: 	aiFace* out = new aiFace[numOut](), *curOut = out;
nuclear@0: 	std::vector<aiVector3D> temp_verts3d(max_out+2); /* temporary storage for vertices */
nuclear@0: 	std::vector<aiVector2D> temp_verts(max_out+2);
nuclear@0: 
nuclear@0: 	// Apply vertex colors to represent the face winding?
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
nuclear@0: 	if (!pMesh->mColors[0])
nuclear@0: 		pMesh->mColors[0] = new aiColor4D[pMesh->mNumVertices];
nuclear@0: 	else
nuclear@0: 		new(pMesh->mColors[0]) aiColor4D[pMesh->mNumVertices];
nuclear@0: 
nuclear@0: 	aiColor4D* clr = pMesh->mColors[0];
nuclear@0: #endif
nuclear@0: 
nuclear@0: 	
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0: 	FILE* fout = fopen(POLY_OUTPUT_FILE,"a");
nuclear@0: #endif
nuclear@0: 
nuclear@0: 	const aiVector3D* verts = pMesh->mVertices;
nuclear@0: 
nuclear@0: 	// use boost::scoped_array to avoid slow std::vector<bool> specialiations
nuclear@0: 	boost::scoped_array<bool> done(new bool[max_out]); 
nuclear@0: 	for( unsigned int a = 0; a < pMesh->mNumFaces; a++)	{
nuclear@0: 		aiFace& face = pMesh->mFaces[a];
nuclear@0: 
nuclear@0: 		unsigned int* idx = face.mIndices;
nuclear@0: 		int num = (int)face.mNumIndices, ear = 0, tmp, prev = num-1, next = 0, max = num;
nuclear@0: 
nuclear@0: 		// Apply vertex colors to represent the face winding?
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_COLOR_FACE_WINDING
nuclear@0: 		for (unsigned int i = 0; i < face.mNumIndices; ++i) {
nuclear@0: 			aiColor4D& c = clr[idx[i]];
nuclear@0: 			c.r = (i+1) / (float)max;
nuclear@0: 			c.b = 1.f - c.r;
nuclear@0: 		}
nuclear@0: #endif
nuclear@0: 
nuclear@0: 		aiFace* const last_face = curOut; 
nuclear@0: 
nuclear@0: 		// if it's a simple point,line or triangle: just copy it
nuclear@0: 		if( face.mNumIndices <= 3)
nuclear@0: 		{
nuclear@0: 			aiFace& nface = *curOut++;
nuclear@0: 			nface.mNumIndices = face.mNumIndices;
nuclear@0: 			nface.mIndices    = face.mIndices;
nuclear@0: 
nuclear@0: 			face.mIndices = NULL;
nuclear@0: 			continue;
nuclear@0: 		}  
nuclear@0: 		// optimized code for quadrilaterals
nuclear@0: 		else if ( face.mNumIndices == 4) {
nuclear@0: 
nuclear@0: 			// quads can have at maximum one concave vertex. Determine
nuclear@0: 			// this vertex (if it exists) and start tri-fanning from
nuclear@0: 			// it. 
nuclear@0: 			unsigned int start_vertex = 0;
nuclear@0: 			for (unsigned int i = 0; i < 4; ++i) {
nuclear@0: 				const aiVector3D& v0 = verts[face.mIndices[(i+3) % 4]];
nuclear@0: 				const aiVector3D& v1 = verts[face.mIndices[(i+2) % 4]];
nuclear@0: 				const aiVector3D& v2 = verts[face.mIndices[(i+1) % 4]];
nuclear@0: 
nuclear@0: 				const aiVector3D& v = verts[face.mIndices[i]];
nuclear@0: 
nuclear@0: 				aiVector3D left = (v0-v); 
nuclear@0: 				aiVector3D diag = (v1-v); 
nuclear@0: 				aiVector3D right = (v2-v); 
nuclear@0: 
nuclear@0: 				left.Normalize();
nuclear@0: 				diag.Normalize();
nuclear@0: 				right.Normalize();
nuclear@0: 
nuclear@0: 				const float angle = acos(left*diag) + acos(right*diag);
nuclear@0: 				if (angle > AI_MATH_PI_F) {
nuclear@0: 					// this is the concave point
nuclear@0: 					start_vertex = i;
nuclear@0: 					break;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			const unsigned int temp[] = {face.mIndices[0], face.mIndices[1], face.mIndices[2], face.mIndices[3]};
nuclear@0: 	
nuclear@0: 			aiFace& nface = *curOut++;
nuclear@0: 			nface.mNumIndices = 3;
nuclear@0: 			nface.mIndices = face.mIndices;
nuclear@0: 
nuclear@0: 			nface.mIndices[0] = temp[start_vertex];
nuclear@0: 			nface.mIndices[1] = temp[(start_vertex + 1) % 4];
nuclear@0: 			nface.mIndices[2] = temp[(start_vertex + 2) % 4];
nuclear@0: 
nuclear@0: 			aiFace& sface = *curOut++;
nuclear@0: 			sface.mNumIndices = 3;
nuclear@0: 			sface.mIndices = new unsigned int[3];
nuclear@0: 
nuclear@0: 			sface.mIndices[0] = temp[start_vertex];
nuclear@0: 			sface.mIndices[1] = temp[(start_vertex + 2) % 4];
nuclear@0: 			sface.mIndices[2] = temp[(start_vertex + 3) % 4];
nuclear@0: 		
nuclear@0: 			// prevent double deletion of the indices field
nuclear@0: 			face.mIndices = NULL;
nuclear@0: 			continue;
nuclear@0: 		} 
nuclear@0: 		else
nuclear@0: 		{
nuclear@0: 			// A polygon with more than 3 vertices can be either concave or convex.
nuclear@0: 			// Usually everything we're getting is convex and we could easily
nuclear@0: 			// triangulate by trifanning. However, LightWave is probably the only
nuclear@0: 			// modeling suite to make extensive use of highly concave, monster polygons ...
nuclear@0: 			// so we need to apply the full 'ear cutting' algorithm to get it right.
nuclear@0: 
nuclear@0: 			// RERQUIREMENT: polygon is expected to be simple and *nearly* planar.
nuclear@0: 			// We project it onto a plane to get a 2d triangle.
nuclear@0: 
nuclear@0: 			// Collect all vertices of of the polygon.
nuclear@0: 			for (tmp = 0; tmp < max; ++tmp) {
nuclear@0: 				temp_verts3d[tmp] = verts[idx[tmp]];
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// Get newell normal of the polygon. Store it for future use if it's a polygon-only mesh
nuclear@0: 			aiVector3D n;
nuclear@0: 			NewellNormal<3,3,3>(n,max,&temp_verts3d.front().x,&temp_verts3d.front().y,&temp_verts3d.front().z);
nuclear@0: 			if (nor_out) {
nuclear@0: 				 for (tmp = 0; tmp < max; ++tmp)
nuclear@0: 					 nor_out[idx[tmp]] = n;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// Select largest normal coordinate to ignore for projection
nuclear@0: 			const float ax = (n.x>0 ? n.x : -n.x);    
nuclear@0: 			const float ay = (n.y>0 ? n.y : -n.y);   
nuclear@0: 			const float az = (n.z>0 ? n.z : -n.z);    
nuclear@0: 
nuclear@0: 			unsigned int ac = 0, bc = 1; /* no z coord. projection to xy */
nuclear@0: 			float inv = n.z;
nuclear@0: 			if (ax > ay) {
nuclear@0: 				if (ax > az) { /* no x coord. projection to yz */
nuclear@0: 					ac = 1; bc = 2;
nuclear@0: 					inv = n.x;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			else if (ay > az) { /* no y coord. projection to zy */
nuclear@0: 				ac = 2; bc = 0;
nuclear@0: 				inv = n.y;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// Swap projection axes to take the negated projection vector into account
nuclear@0: 			if (inv < 0.f) {
nuclear@0: 				std::swap(ac,bc);
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			for (tmp =0; tmp < max; ++tmp) {
nuclear@0: 				temp_verts[tmp].x = verts[idx[tmp]][ac];
nuclear@0: 				temp_verts[tmp].y = verts[idx[tmp]][bc];
nuclear@0: 				done[tmp] = false;	
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0: 			// plot the plane onto which we mapped the polygon to a 2D ASCII pic
nuclear@0: 			aiVector2D bmin,bmax;
nuclear@0: 			ArrayBounds(&temp_verts[0],max,bmin,bmax);
nuclear@0: 
nuclear@0: 			char grid[POLY_GRID_Y][POLY_GRID_X+POLY_GRID_XPAD];
nuclear@0: 			std::fill_n((char*)grid,POLY_GRID_Y*(POLY_GRID_X+POLY_GRID_XPAD),' ');
nuclear@0: 
nuclear@0: 			for (int i =0; i < max; ++i) {
nuclear@0: 				const aiVector2D& v = (temp_verts[i] - bmin) / (bmax-bmin);
nuclear@0: 				const size_t x = static_cast<size_t>(v.x*(POLY_GRID_X-1)), y = static_cast<size_t>(v.y*(POLY_GRID_Y-1));
nuclear@0: 				char* loc = grid[y]+x;
nuclear@0: 				if (grid[y][x] != ' ') {
nuclear@0: 					for(;*loc != ' '; ++loc);
nuclear@0: 					*loc++ = '_';
nuclear@0: 				}
nuclear@0: 				*(loc+sprintf(loc,"%i",i)) = ' ';
nuclear@0: 			}
nuclear@0: 			
nuclear@0: 
nuclear@0: 			for(size_t y = 0; y < POLY_GRID_Y; ++y) {
nuclear@0: 				grid[y][POLY_GRID_X+POLY_GRID_XPAD-1] = '\0';
nuclear@0: 				fprintf(fout,"%s\n",grid[y]);
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			fprintf(fout,"\ntriangulation sequence: ");
nuclear@0: #endif
nuclear@0: 
nuclear@0: 			//
nuclear@0: 			// FIXME: currently this is the slow O(kn) variant with a worst case
nuclear@0: 			// complexity of O(n^2) (I think). Can be done in O(n).
nuclear@0: 			while (num > 3)	{
nuclear@0: 
nuclear@0: 				// Find the next ear of the polygon
nuclear@0: 				int num_found = 0;
nuclear@0: 				for (ear = next;;prev = ear,ear = next) {
nuclear@0: 				
nuclear@0: 					// break after we looped two times without a positive match
nuclear@0: 					for (next=ear+1;done[(next>=max?next=0:next)];++next);
nuclear@0: 					if (next < ear) {
nuclear@0: 						if (++num_found == 2) {
nuclear@0: 							break;
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 					const aiVector2D* pnt1 = &temp_verts[ear], 
nuclear@0: 						*pnt0 = &temp_verts[prev], 
nuclear@0: 						*pnt2 = &temp_verts[next];
nuclear@0: 			
nuclear@0: 					// Must be a convex point. Assuming ccw winding, it must be on the right of the line between p-1 and p+1.
nuclear@0: 					if (OnLeftSideOfLine2D(*pnt0,*pnt2,*pnt1)) {
nuclear@0: 						continue;
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					// and no other point may be contained in this triangle
nuclear@0: 					for ( tmp = 0; tmp < max; ++tmp) {
nuclear@0: 
nuclear@0: 						// We need to compare the actual values because it's possible that multiple indexes in 
nuclear@0: 						// the polygon are referring to the same position. concave_polygon.obj is a sample
nuclear@0: 						//
nuclear@0: 						// FIXME: Use 'epsiloned' comparisons instead? Due to numeric inaccuracies in
nuclear@0: 						// PointInTriangle() I'm guessing that it's actually possible to construct
nuclear@0: 						// input data that would cause us to end up with no ears. The problem is,
nuclear@0: 						// which epsilon? If we chose a too large value, we'd get wrong results
nuclear@0: 						const aiVector2D& vtmp = temp_verts[tmp]; 
nuclear@0: 						if ( vtmp != *pnt1 && vtmp != *pnt2 && vtmp != *pnt0 && PointInTriangle2D(*pnt0,*pnt1,*pnt2,vtmp)) {
nuclear@0: 							break;		
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 					if (tmp != max) {
nuclear@0: 						continue;
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					// this vertex is an ear
nuclear@0: 					break;
nuclear@0: 				}
nuclear@0: 				if (num_found == 2) {
nuclear@0: 					
nuclear@0: 					// Due to the 'two ear theorem', every simple polygon with more than three points must
nuclear@0: 					// have 2 'ears'. Here's definitely someting wrong ... but we don't give up yet.
nuclear@0: 					//
nuclear@0: 
nuclear@0: 					// Instead we're continuting with the standard trifanning algorithm which we'd
nuclear@0: 					// use if we had only convex polygons. That's life.
nuclear@0: 					DefaultLogger::get()->error("Failed to triangulate polygon (no ear found). Probably not a simple polygon?");
nuclear@0: 					
nuclear@0: 
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0: 					fprintf(fout,"critical error here, no ear found! ");
nuclear@0: #endif
nuclear@0: 					num = 0;
nuclear@0: 					break;
nuclear@0: 
nuclear@0: 					curOut -= (max-num); /* undo all previous work */
nuclear@0: 					for (tmp = 0; tmp < max-2; ++tmp) {
nuclear@0: 						aiFace& nface = *curOut++;
nuclear@0: 
nuclear@0: 						nface.mNumIndices = 3;
nuclear@0: 						if (!nface.mIndices)
nuclear@0: 							nface.mIndices = new unsigned int[3];
nuclear@0: 
nuclear@0: 						nface.mIndices[0] = 0;
nuclear@0: 						nface.mIndices[1] = tmp+1;
nuclear@0: 						nface.mIndices[2] = tmp+2;
nuclear@0: 
nuclear@0: 					}
nuclear@0: 					num = 0;
nuclear@0: 					break;
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				aiFace& nface = *curOut++;
nuclear@0: 				nface.mNumIndices = 3;
nuclear@0: 
nuclear@0: 				if (!nface.mIndices) {
nuclear@0: 					nface.mIndices = new unsigned int[3];
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				// setup indices for the new triangle ...
nuclear@0: 				nface.mIndices[0] = prev;
nuclear@0: 				nface.mIndices[1] = ear;
nuclear@0: 				nface.mIndices[2] = next;
nuclear@0: 
nuclear@0: 				// exclude the ear from most further processing
nuclear@0: 				done[ear] = true;
nuclear@0: 				--num;
nuclear@0: 			}
nuclear@0: 			if (num > 0) {
nuclear@0: 				// We have three indices forming the last 'ear' remaining. Collect them.
nuclear@0: 				aiFace& nface = *curOut++;
nuclear@0: 				nface.mNumIndices = 3;
nuclear@0: 				if (!nface.mIndices) {
nuclear@0: 					nface.mIndices = new unsigned int[3];
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				for (tmp = 0; done[tmp]; ++tmp);
nuclear@0: 				nface.mIndices[0] = tmp;
nuclear@0: 
nuclear@0: 				for (++tmp; done[tmp]; ++tmp);
nuclear@0: 				nface.mIndices[1] = tmp;
nuclear@0: 
nuclear@0: 				for (++tmp; done[tmp]; ++tmp);
nuclear@0: 				nface.mIndices[2] = tmp;
nuclear@0: 
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0: 		
nuclear@0: 		for(aiFace* f = last_face; f != curOut; ++f) {
nuclear@0: 			unsigned int* i = f->mIndices;
nuclear@0: 			fprintf(fout," (%i %i %i)",i[0],i[1],i[2]);
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		fprintf(fout,"\n*********************************************************************\n");
nuclear@0: 		fflush(fout);
nuclear@0: 		
nuclear@0: #endif
nuclear@0: 
nuclear@0: 		for(aiFace* f = last_face; f != curOut; ) {
nuclear@0: 			unsigned int* i = f->mIndices;
nuclear@0: 
nuclear@0: 			//  drop dumb 0-area triangles
nuclear@0: 			if (fabs(GetArea2D(temp_verts[i[0]],temp_verts[i[1]],temp_verts[i[2]])) < 1e-5f) {
nuclear@0: 				DefaultLogger::get()->debug("Dropping triangle with area 0");
nuclear@0: 				--curOut;
nuclear@0: 
nuclear@0: 				delete[] f->mIndices;
nuclear@0: 				f->mIndices = NULL;
nuclear@0: 
nuclear@0: 				for(aiFace* ff = f; ff != curOut; ++ff) {
nuclear@0: 					ff->mNumIndices = (ff+1)->mNumIndices;
nuclear@0: 					ff->mIndices = (ff+1)->mIndices;
nuclear@0: 					(ff+1)->mIndices = NULL;
nuclear@0: 				}
nuclear@0: 				continue;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			i[0] = idx[i[0]];
nuclear@0: 			i[1] = idx[i[1]];
nuclear@0: 			i[2] = idx[i[2]];
nuclear@0: 			++f;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		delete[] face.mIndices;
nuclear@0: 		face.mIndices = NULL; 
nuclear@0: 	}
nuclear@0: 
nuclear@0: #ifdef AI_BUILD_TRIANGULATE_DEBUG_POLYS
nuclear@0: 	fclose(fout);
nuclear@0: #endif
nuclear@0: 
nuclear@0: 	// kill the old faces
nuclear@0: 	delete [] pMesh->mFaces;
nuclear@0: 
nuclear@0: 	// ... and store the new ones
nuclear@0: 	pMesh->mFaces    = out;
nuclear@0: 	pMesh->mNumFaces = (unsigned int)(curOut-out); /* not necessarily equal to numOut */
nuclear@0: 	return true;
nuclear@0: }
nuclear@0: 
nuclear@0: #endif // !! ASSIMP_BUILD_NO_TRIANGULATE_PROCESS