ps1bsptools/face.cpp

#include "common.h"
#include "matrix.h"
#include "bsp.h"
#include "face.h"
#include "gpc.h"

// Heron's formula, yoinked from: https://www.cuemath.com/measurement/area-of-triangle/
static double face_triangleArea(Vec3 v0, Vec3 v1, Vec3 v2)
{
	double a = (v1 - v0).magnitude();
	double b = (v2 - v0).magnitude();
	double c = (v0 - v2).magnitude();
	double s = (a + b + c) * 0.5;

	double areaSqr = s * (s - a) * (s - b) * (s - c);
	if (areaSqr < FLT_EPSILON)	// Collapsed triangles can happen, prevent NaN in that situation
		return 0.0;

	return sqrt(areaSqr);
}

double face_computeArea(const world_t* world, const face_t* face)
{
	int i0, i1, i2;

	// Get the first edge so we can build a triangle fan
	int edgeIdx = world->edgeList[face->ledge_id];
	if (edgeIdx > 0)
	{
		i0 = world->edges[edgeIdx].vertex0;
		i1 = world->edges[edgeIdx].vertex1;
	}
	else
	{
		i0 = world->edges[-edgeIdx].vertex1;
		i1 = world->edges[-edgeIdx].vertex0;
	}

	// Triangulate the face, compute the area of each triangle and add them all together
	double totalArea = 0.0;
	for (int edgeListIdx = 1; edgeListIdx < face->ledge_num - 1; ++edgeListIdx)
	{
		int edgeIdx = world->edgeList[face->ledge_id + edgeListIdx];
		i2 = edgeIdx > 0 ? world->edges[edgeIdx].vertex0 : world->edges[-edgeIdx].vertex1;

		Vec3 v0 = world->vertices[i0].toVec();
		Vec3 v1 = world->vertices[i1].toVec();
		Vec3 v2 = world->vertices[i2].toVec();

		totalArea += face_triangleArea(v0, v1, v2);

		i1 = i2;
	}

	return totalArea;
}

std::vector<Vec3> face_optimizeGeometry(const std::vector<Vec3> faceVertices, Matrix4x4 textureTransform)
{
	std::vector<Vec3> result;

	// Some faces have redundant/degenerate vertices. We can optimize those by passing their polygons through GPC.
	gpc_polygon facePolygon = { 0 };
	gpc_vertex_list contour;
	contour.num_vertices = faceVertices.size();
	contour.vertex = (gpc_vertex*)malloc(contour.num_vertices * sizeof(gpc_vertex));
	if (contour.vertex == NULL)
		return result;

	int idx = 0;
	for (auto vertIter = faceVertices.cbegin(); vertIter != faceVertices.cend(); ++vertIter)
	{
		Vec3 st = textureTransform.TransformPoint(*vertIter);
		contour.vertex[idx++] = gpc_vertex{ st.x, st.y };
	}

	gpc_add_contour(&facePolygon, &contour, 0);

	// Intersect the face's polygon with itself. That should get rid of any redundant vertices.
	gpc_polygon optimized = { 0 };
	gpc_polygon_clip(GPC_INT, &facePolygon, &facePolygon, &optimized);

	if (optimized.num_contours < 1)
		return result;

	// Transform the optimized polygon back to world space
	textureTransform.Invert();

	gpc_vertex_list* newContour = &optimized.contour[0];
	for (int i = 0; i < newContour->num_vertices; ++i)
	{
		Vec3 st = Vec3(newContour->vertex[i].x, newContour->vertex[i].y, 0.0);
		Vec3 vert = textureTransform.TransformPoint(st);
		result.push_back(vert);
	}

	gpc_free_polygon(&optimized);
	gpc_free_polygon(&facePolygon);
	return result;
}