vec Polygon::FastRandomPointInside(LCG &rng) const
{
	TriangleArray tris = Triangulate();
	if (tris.empty())
		return vec::nan;
	int i = rng.Int(0, (int)tris.size()-1);
	return TRIANGLE(tris[i]).RandomPointInside(rng);
}

void TriangleMesh::Set(const Polyhedron &polyhedron)
{
	TriangleArray tris = polyhedron.Triangulate();
	if (!tris.empty())
	{
		int alignment = (simdCapability == SIMD_AVX) ? 8 : ((simdCapability == SIMD_SSE41 || simdCapability == SIMD_SSE2) ? 4 : 1);
		vec degen = POINT_VEC_SCALAR(-FLOAT_INF);
		Triangle degent(degen, degen, degen);
		while(tris.size() % alignment != 0)
			tris.push_back(degent);
		Set((Triangle*)&tris[0], (int)tris.size());
	}
}

void lua_TriangleArray_AddPoint(lua_State* L,
              TriangleArray<IndexIntegerType, VertexCoordType, TexCoordType, NormalCoordType, textureCount, supportVertexVBOs, supportTexVBOs, supportNormalVBOs, VertexCoordinateCount, TexCoordCount>& array,
              const typename VertexArray<VertexCoordType, VertexCoordinateCount, supportVertexVBOs>::value_type& vertex,
              const object& lua_texcoords,
              const typename NormalArray<NormalCoordType, supportNormalVBOs>::value_type& normal)
{
	typedef TriangleArray<IndexIntegerType, VertexCoordType, TexCoordType, NormalCoordType, textureCount, supportVertexVBOs, supportTexVBOs, supportNormalVBOs, VertexCoordinateCount, TexCoordCount> array_t;
	typedef typename array_t::vertex_type   vertex_type;
	typedef typename array_t::texcoord_type texcoord_type;
	typedef typename array_t::normal_type   normal_type;

	luaL_checktype(L, 3, LUA_TTABLE);
	if (lua_objlen(L, 3) != textureCount)
	{
		const char *msg = lua_pushfstring(L, "list of %u texture coordinates expected, got %u",
		                                  static_cast<unsigned int>(textureCount), lua_objlen(L, 3));
		luaL_argerror(L, 3, msg);
		return;
	}

	boost::array<texcoord_type, textureCount> texcoords;
	typename boost::array<texcoord_type, textureCount>::iterator out_texcoords = texcoords.begin();

	for (iterator i(lua_texcoords), end; i != end; ++i)
	{
		assert(out_texcoords != texcoords.end());
		*out_texcoords++ = object_cast<texcoord_type>(*i);
	}

	array.AddPoint(vertex, texcoords.begin(), texcoords.end(), normal);
}

vec Polygon::ClosestPoint(const vec &point) const
{
	assume(IsPlanar());

	TriangleArray tris = Triangulate();
	vec closestPt = vec::nan;
	float closestDist = FLT_MAX;
	for(size_t i = 0; i < tris.size(); ++i)
	{
		vec pt = TRIANGLE(tris[i]).ClosestPoint(point);
		float d = pt.DistanceSq(point);
		if (d < closestDist)
		{
			closestPt = pt;
			closestDist = d;
		}
	}
	return closestPt;
}

int Sphere::Triangulate(vec *outPos, vec *outNormal, float2 *outUV, int numVertices, bool ccwIsFrontFacing) const
{
	assume(outPos);
	assume(numVertices >= 24 && "At minimum, sphere triangulation will contain at least 8 triangles, which is 24 vertices, but fewer were specified!");
	assume(numVertices % 3 == 0 && "Warning:: The size of output should be divisible by 3 (each triangle takes up 3 vertices!)");

#ifndef MATH_ENABLE_INSECURE_OPTIMIZATIONS
	if (!outPos)
		return 0;
#endif
	assume(this->r > 0.f);

	if (numVertices < 24)
		return 0;

#ifdef MATH_ENABLE_STL_SUPPORT
	TriangleArray temp;
#else
	Array<Triangle> temp;
#endif
	// Start subdividing from a diamond shape.
	vec xp = POINT_VEC(r,0,0);
	vec xn = POINT_VEC(-r, 0, 0);
	vec yp = POINT_VEC(0, r, 0);
	vec yn = POINT_VEC(0, -r, 0);
	vec zp = POINT_VEC(0, 0, r);
	vec zn = POINT_VEC(0, 0, -r);

	if (ccwIsFrontFacing)
	{
		temp.push_back(Triangle(yp,xp,zp));
		temp.push_back(Triangle(xp,yp,zn));
		temp.push_back(Triangle(yn,zp,xp));
		temp.push_back(Triangle(yn,xp,zn));
		temp.push_back(Triangle(zp,xn,yp));
		temp.push_back(Triangle(yp,xn,zn));
		temp.push_back(Triangle(yn,xn,zp));
		temp.push_back(Triangle(xn,yn,zn));
	}
	else
	{
		temp.push_back(Triangle(yp,zp,xp));
		temp.push_back(Triangle(xp,zn,yp));
		temp.push_back(Triangle(yn,xp,zp));
		temp.push_back(Triangle(yn,zn,xp));
		temp.push_back(Triangle(zp,yp,xn));
		temp.push_back(Triangle(yp,zn,xn));
		temp.push_back(Triangle(yn,zp,xn));
		temp.push_back(Triangle(xn,zn,yn));
	}

	int oldEnd = 0;
	while(((int)temp.size()-oldEnd+3)*3 <= numVertices)
	{
		Triangle cur = temp[oldEnd];
		vec a = ((cur.a + cur.b) * 0.5f).ScaledToLength(this->r);
		vec b = ((cur.a + cur.c) * 0.5f).ScaledToLength(this->r);
		vec c = ((cur.b + cur.c) * 0.5f).ScaledToLength(this->r);

		temp.push_back(Triangle(cur.a, a, b));
		temp.push_back(Triangle(cur.b, c, a));
		temp.push_back(Triangle(cur.c, b, c));
		temp.push_back(Triangle(a, c, b));

		++oldEnd;
	}
	// Check that we really did tessellate as many new triangles as possible.
	assert(((int)temp.size()-oldEnd)*3 <= numVertices && ((int)temp.size()-oldEnd)*3 + 9 > numVertices);

	for(size_t i = oldEnd, j = 0; i < temp.size(); ++i, ++j)
	{
		outPos[3*j] = this->pos + TRIANGLE(temp[i]).a;
		outPos[3*j+1] = this->pos + TRIANGLE(temp[i]).b;
		outPos[3*j+2] = this->pos + TRIANGLE(temp[i]).c;
	}

	if (outNormal)
		for(size_t i = oldEnd, j = 0; i < temp.size(); ++i, ++j)
		{
			outNormal[3*j] = TRIANGLE(temp[i]).a.Normalized();
			outNormal[3*j+1] = TRIANGLE(temp[i]).b.Normalized();
			outNormal[3*j+2] = TRIANGLE(temp[i]).c.Normalized();
		}

	if (outUV)
		for(size_t i = oldEnd, j = 0; i < temp.size(); ++i, ++j)
		{
			outUV[3*j] = float2(atan2(TRIANGLE(temp[i]).a.y, TRIANGLE(temp[i]).a.x) / (2.f * 3.141592654f) + 0.5f, (TRIANGLE(temp[i]).a.z + r) / (2.f * r));
			outUV[3*j+1] = float2(atan2(TRIANGLE(temp[i]).b.y, TRIANGLE(temp[i]).b.x) / (2.f * 3.141592654f) + 0.5f, (TRIANGLE(temp[i]).b.z + r) / (2.f * r));
			outUV[3*j+2] = float2(atan2(TRIANGLE(temp[i]).c.y, TRIANGLE(temp[i]).c.x) / (2.f * 3.141592654f) + 0.5f, (TRIANGLE(temp[i]).c.z + r) / (2.f * r));
		}

	return ((int)temp.size() - oldEnd) * 3;
}

/** The implementation of this function is based on the paper
	"Kong, Everett, Toussant. The Graham Scan Triangulates Simple Polygons."
	See also p. 772-775 of Geometric Tools for Computer Graphics.
	The running time of this function is O(n^2). */
TriangleArray Polygon::Triangulate() const
{
	assume1(IsPlanar(), this->SerializeToString());

	TriangleArray t;
	// Handle degenerate cases.
	if (NumVertices() < 3)
		return t;
	if (NumVertices() == 3)
	{
		t.push_back(Triangle(Vertex(0), Vertex(1), Vertex(2)));
		return t;
	}
	std::vector<float2> p2d;
	std::vector<int> polyIndices;
	for(int v = 0; v < NumVertices(); ++v)
	{
		p2d.push_back(MapTo2D(v));
		polyIndices.push_back(v);
	}

	// Clip ears of the polygon until it has been reduced to a triangle.
	int i = 0;
	int j = 1;
	int k = 2;
	size_t numTries = 0; // Avoid creating an infinite loop.
	while(p2d.size() > 3 && numTries < p2d.size())
	{
		if (float2::OrientedCCW(p2d[i], p2d[j], p2d[k]) && IsAnEar(p2d, i, k))
		{
			// The vertex j is an ear. Clip it off.
			t.push_back(Triangle(p[polyIndices[i]], p[polyIndices[j]], p[polyIndices[k]]));
			p2d.erase(p2d.begin() + j);
			polyIndices.erase(polyIndices.begin() + j);

			// The previous index might now have become an ear. Move back one index to see if so.
			if (i > 0)
			{
				i = (i + (int)p2d.size() - 1) % p2d.size();
				j = (j + (int)p2d.size() - 1) % p2d.size();
				k = (k + (int)p2d.size() - 1) % p2d.size();
			}
			numTries = 0;
		}
		else
		{
			// The vertex at j is not an ear. Move to test next vertex.
			i = j;
			j = k;
			k = (k+1) % p2d.size();
			++numTries;
		}
	}

	assume3(p2d.size() == 3, (int)p2d.size(), (int)polyIndices.size(), (int)NumVertices());
	if (p2d.size() > 3) // If this occurs, then the polygon is NOT counter-clockwise oriented.
		return t;
/*
	{
		// For conveniency, create a copy that has the winding order fixed, and triangulate that instead.
		// (Causes a large performance hit!)
		Polygon p2 = *this;
		for(size_t i = 0; i < p2.p.size()/2; ++i)
			std::swap(p2.p[i], p2.p[p2.p.size()-1-i]);
		return p2.Triangulate();
	}
*/
	// Add the last poly.
	t.push_back(Triangle(p[polyIndices[0]], p[polyIndices[1]], p[polyIndices[2]]));

	return t;
}

int main(int _argc, const char* _argv[])
{
	bx::CommandLine cmdLine(_argc, _argv);

	const char* filePath = cmdLine.findOption('f');
	if (NULL == filePath)
	{
		help("Input file name must be specified.");
		return EXIT_FAILURE;
	}

	const char* outFilePath = cmdLine.findOption('o');
	if (NULL == outFilePath)
	{
		help("Output file name must be specified.");
		return EXIT_FAILURE;
	}

	float scale = 1.0f;
	const char* scaleArg = cmdLine.findOption('s', "scale");
	if (NULL != scaleArg)
	{
		scale = (float)atof(scaleArg);
	}

	cmdLine.hasArg(s_obbSteps, '\0', "obb");
	s_obbSteps = bx::uint32_min(bx::uint32_max(s_obbSteps, 1), 90);

	uint32_t packNormal = 0;
	cmdLine.hasArg(packNormal, '\0', "packnormal");

	uint32_t packUv = 0;
	cmdLine.hasArg(packUv, '\0', "packuv");
	
	bool ccw = cmdLine.hasArg("ccw");
	bool flipV = cmdLine.hasArg("flipv");
	bool hasTangent = cmdLine.hasArg("tangent");

	FILE* file = fopen(filePath, "r");
	if (NULL == file)
	{
		printf("Unable to open input file '%s'.", filePath);
		exit(EXIT_FAILURE);
	}

	int64_t parseElapsed = -bx::getHPCounter();
	int64_t triReorderElapsed = 0;

	uint32_t size = (uint32_t)fsize(file);
	char* data = new char[size+1];
	size = (uint32_t)fread(data, 1, size, file);
	data[size] = '\0';
	fclose(file);

	// https://en.wikipedia.org/wiki/Wavefront_.obj_file

	Vector3Array positions;
	Vector3Array normals;
	Vector3Array texcoords;
	Index3Map indexMap;
	TriangleArray triangles;
	GroupArray groups;

	uint32_t num = 0;

	Group group;
	group.m_startTriangle = 0;
	group.m_numTriangles = 0;

	char commandLine[2048];
	uint32_t len = sizeof(commandLine);
	int argc;
	char* argv[64];
	const char* next = data;
	do
	{
		next = bx::tokenizeCommandLine(next, commandLine, len, argc, argv, BX_COUNTOF(argv), '\n');
		if (0 < argc)
		{
			if (0 == strcmp(argv[0], "#") )
			{
				if (2 < argc
				&&  0 == strcmp(argv[2], "polygons") )
				{
				}
			}
			else if (0 == strcmp(argv[0], "f") )
			{
				Triangle triangle;
				memset(&triangle, 0, sizeof(Triangle) );

				for (uint32_t edge = 0, numEdges = argc-1; edge < numEdges; ++edge)
				{
					Index3 index;
					index.m_texcoord = -1;
					index.m_normal = -1;
					index.m_vertexIndex = -1;

					char* vertex = argv[edge+1];
					char* texcoord = strchr(vertex, '/');
//.........这里部分代码省略.........

uint32_t objToBin(const uint8_t* _objData
                  , bx::WriterSeekerI* _writer
                  , uint32_t _packUv
                  , uint32_t _packNormal
                  , bool _ccw
                  , bool _flipV
                  , bool _hasTangent
                  , float _scale
                 )
{
    int64_t parseElapsed = -bx::getHPCounter();
    int64_t triReorderElapsed = 0;

    const int64_t begin = _writer->seek();

    Vector3Array positions;
    Vector3Array normals;
    Vector3Array texcoords;
    Index3Map indexMap;
    TriangleArray triangles;
    BgfxGroupArray groups;

    uint32_t num = 0;

    MeshGroup group;
    group.m_startTriangle = 0;
    group.m_numTriangles = 0;
    group.m_name = "";
    group.m_material = "";

    char commandLine[2048];
    uint32_t len = sizeof(commandLine);
    int argc;
    char* argv[64];
    const char* next = (const char*)_objData;
    do
    {
        next = bx::tokenizeCommandLine(next, commandLine, len, argc, argv, BX_COUNTOF(argv), '\n');
        if (0 < argc)
        {
            if (0 == strcmp(argv[0], "#") )
            {
                if (2 < argc
                        &&  0 == strcmp(argv[2], "polygons") )
                {
                }
            }
            else if (0 == strcmp(argv[0], "f") )
            {
                Triangle triangle;
                memset(&triangle, 0, sizeof(Triangle) );

                const int numNormals   = (int)normals.size();
                const int numTexcoords = (int)texcoords.size();
                const int numPositions = (int)positions.size();
                for (uint32_t edge = 0, numEdges = argc-1; edge < numEdges; ++edge)
                {
                    Index3 index;
                    index.m_texcoord = 0;
                    index.m_normal = 0;
                    index.m_vertexIndex = -1;

                    char* vertex = argv[edge+1];
                    char* texcoord = strchr(vertex, '/');
                    if (NULL != texcoord)
                    {
                        *texcoord++ = '\0';

                        char* normal = strchr(texcoord, '/');
                        if (NULL != normal)
                        {
                            *normal++ = '\0';
                            const int nn = atoi(normal);
                            index.m_normal = (nn < 0) ? nn+numNormals : nn-1;
                        }

                        const int tex = atoi(texcoord);
                        index.m_texcoord = (tex < 0) ? tex+numTexcoords : tex-1;
                    }

                    const int pos = atoi(vertex);
                    index.m_position = (pos < 0) ? pos+numPositions : pos-1;

                    uint64_t hash0 = index.m_position;
                    uint64_t hash1 = uint64_t(index.m_texcoord)<<20;
                    uint64_t hash2 = uint64_t(index.m_normal)<<40;
                    uint64_t hash = hash0^hash1^hash2;

                    CS_STL::pair<Index3Map::iterator, bool> result = indexMap.insert(CS_STL::make_pair(hash, index) );
                    if (!result.second)
                    {
                        Index3& oldIndex = result.first->second;
                        BX_UNUSED(oldIndex);
                        BX_CHECK(oldIndex.m_position == index.m_position
                                 && oldIndex.m_texcoord == index.m_texcoord
                                 && oldIndex.m_normal == index.m_normal
                                 , "Hash collision!"
                                );
                    }

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