Function insertConstraint

TheForceEngine/TFE_Polygon/polygon.cpp:596–645

	}

	bool insertConstraint(Polygon* poly, const Edge* constraint, Triangle* tri, s32 startIndex)
	{
		// *If* the constraint intersects an edge of *this* triangle, it must
		// be the opposite edge.
		s32 e0 = (startIndex + 1) % 3;
		s32 e1 = (e0 + 1) % 3;
		s32 i0 = tri->idx[e0];
		s32 i1 = tri->idx[e1];
		const Vec2f* c0 = &s_vertices[constraint->i0];
		const Vec2f* c1 = &s_vertices[constraint->i1];

		const Vec2f* v0 = &s_vertices[i0];
		const Vec2f* v1 = &s_vertices[i1];

		// Compute the intersection between line segment c0->c1 and v0->v1
		f32 constInter, triEdgeInter;
		if (!TFE_Math::lineSegmentIntersect(c0, c1, v0, v1, &constInter, &triEdgeInter))
		{
			return false;
		}
		// Make sure it is worth the hassle...
		if (constInter <= FLT_EPSILON || constInter >= 1.0f - FLT_EPSILON)
		{
			return false;
		}

		// *If* the intersection exists, *AND* it is before the end of the segment, recurse into the adjoining triangle.
		// Store the adjacency and edge indices for later.
		const s32 adj = tri->adj[e0];
		const s32 S = tri->idx[startIndex];
		
		// Delete triangle.
		deleteTriangle(tri);

		// Add two new triangles:
		// startIndex -> iEdge -> newVtx
		// startIndex -> newVtx -> iEdge + 1
		s32 N = (s32)s_vertices.size();
		Vec2f it = { v0->x + triEdgeInter * (v1->x - v0->x), v0->z + triEdgeInter * (v1->z - v0->z) };
		s_vertices.push_back(it);
		addTriangle(S, i0, N);
		addTriangle(S, N, i1);

		// Move on to the next triangle.
		if (adj >= 0 && s_triangles[adj].allocated && constInter <= 1.0f - eps)
		{
			constraintSplit(i0, i1, N, &s_triangles[adj], it, c0, c1, constInter);
		}
		return true;
	}

	// Compute a valid triangulation for the polygon.
	// Polygons may be complex, self-intersecting, and even be incomplete.