Code:
typedef union
{
struct
{
float x, y, z;
};
float data[3];
} Vector3;
typedef union
{
struct
{
float x, y;
};
float data[2];
} Vector2;
class Mesh
{
public:
Vector3* vertices;
int* indices;
Vector3* vertexNormals;
Vector2* texCoords;
int vertexCount;
int indexCount;
};
void sub3(const Vector3* first, const Vector3* second, Vector3* result)
{
result->x = first->x - second->x;
result->y = first->y - second->y;
result->z = first->z - second->z;
}
float dot3(const Vector3* first, const Vector3* second)
{
int i;
float dot = 0;
for (i = 0; i < 3; ++i)
{
dot += first->data[i] * second->data[i];
}
return dot;
}
void lerp3(const Vector3* from, const Vector3* to, float t, Vector3* result)
{
result->x = from->x + t * (to->x - from->x);
result->y = from->y + t * (to->y - from->y);
result->z = from->z + t * (to->z - from->z);
}
float linePlaneCoefficient(const Vector3* linePoint, const Vector3* lineDir, const Vector3* planeNormal, const Vector3* planePoint)
{
Vector3 diff;
float dot1;
float dot2;
float result;
sub3(planePoint, linePoint, &diff);
dot1 = dot3(planeNormal, &diff);
dot2 = dot3(planeNormal, lineDir);
result = dot1 / dot2;
return result;
}
void rcTrimBoudaries(float minX, float minY, float maxX, float maxY)
{
Mesh *source = new Mesh;
Mesh *left = new Mesh;
Mesh *right = new Mesh;
Vector3 planePointA { maxX,maxY,0 };
Vector3 planePointB { minX,minY,0 };
Vector3 planeNormal1{ 1,1,0 };
Vector3 planeNormal2{ 1,-1,0 };
Vector3 planeNormal3{ -1,1,0 };
Vector3 planeNormal4{ -1,-1,0 };
rcCutMesh(source, left, right, planePointA, planeNormal1);
rcCutMesh(source, left, right, planePointA, planeNormal2);
rcCutMesh(source, left, right, planePointB, planeNormal3);
rcCutMesh(source, left, right, planePointB, planeNormal4);
}
void rcCutMesh(Mesh* source, Mesh* left, Mesh* right, Vector3 planePoint, Vector3 planeNormal)
{
int faceCount = source->indexCount / 3;
// The maximum number of vertices for the new meshes is vertexCount + faceCount * 2
// (two points of intersection for each face)
int newVertexCount = source->vertexCount;
int newVertexMax = source->vertexCount + faceCount * 2;
Vector3* newVertices = new Vector3[newVertexMax];
Vector3* newNormals = new Vector3[newVertexMax];
memcpy(newVertices, source->vertices, source->vertexCount * sizeof(Vector3));
memcpy(newNormals, source->vertexNormals, source->vertexCount * sizeof(Vector3));
// The maximum number of indices for the new meshes is indexCount + faceCount * 9
// (each face could be split up into three faces)
int newIndexCount = source->indexCount;
int newIndexMax = source->indexCount + faceCount * 9;
int leftIndexCount = 0;
int* leftIndices = new int[newIndexMax];
int rightIndexCount = 0;
int* rightIndices = new int[newIndexMax];
// Iterate through each face and decide which list to put it in and whether to divide it
for (int i = 0; i < faceCount; ++i)
{
int i1 = source->indices[i * 3 + 0];
int i2 = source->indices[i * 3 + 1];
int i3 = source->indices[i * 3 + 2];
Vector3* v1 = &source->vertices[i1];
Vector3* v2 = &source->vertices[i2];
Vector3* v3 = &source->vertices[i3];
// Check if each vertex is to the left of the plane
Vector3 v1ToPlane;
Vector3 v2ToPlane;
Vector3 v3ToPlane;
sub3(&planePoint, v1, &v1ToPlane);
sub3(&planePoint, v2, &v2ToPlane);
sub3(&planePoint, v3, &v3ToPlane);
bool v1Left = dot3(&v1ToPlane, &planeNormal) < 0;
bool v2Left = dot3(&v2ToPlane, &planeNormal) < 0;
bool v3Left = dot3(&v3ToPlane, &planeNormal) < 0;
int pointsToLeft = (v1Left ? 1 : 0) + (v2Left ? 1 : 0) + (v3Left ? 1 : 0);
// All vertices to left
if (pointsToLeft == 3)
{
// Add all vertices to left
leftIndices[leftIndexCount++] = i1;
leftIndices[leftIndexCount++] = i2;
leftIndices[leftIndexCount++] = i3;
}
// All vertices to right
else if (pointsToLeft == 0)
{
// Add all vertices to right
rightIndices[rightIndexCount++] = i1;
rightIndices[rightIndexCount++] = i2;
rightIndices[rightIndexCount++] = i3;
}
// One vertex to left
else if (pointsToLeft == 1)
{
if (v1Left)
{
Vector3 line1, line2;
Vector3 intersect1, intersect2;
int intersect1index, intersect2index;
float intersect1coeff, intersect2coeff;
int ia = i1;
int ib = i2;
int ic = i3;
const Vector3* a = &newVertices[ia];
const Vector3* b = &newVertices[ib];
const Vector3* c = &newVertices[ic];
sub3(b, a, &line1);
sub3(c, a, &line2);
// Calculate lerp coefficient for intersections
intersect1coeff = linePlaneCoefficient(a, &line1, &planeNormal, &planePoint);
intersect2coeff = linePlaneCoefficient(a, &line2, &planeNormal, &planePoint);
// Calculate intersections
lerp3(a, b, intersect1coeff, &intersect1);
lerp3(a, c, intersect2coeff, &intersect2);
intersect1index = newVertexCount++;
intersect2index = newVertexCount++;
// Save intersections as new vertices
newVertices[intersect1index] = intersect1;
newVertices[intersect2index] = intersect2;
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ib], intersect1coeff, &newNormals[intersect1index]);
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ic], intersect2coeff, &newNormals[intersect2index]);
// Add triangles
// Left
leftIndices[leftIndexCount++] = i1;
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = intersect2index;
// Right
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = i2;
rightIndices[rightIndexCount++] = i3;
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = i3;
rightIndices[rightIndexCount++] = intersect2index;
}
else if (v2Left)
{
Vector3 line1, line2;
Vector3 intersect1, intersect2;
int intersect1index, intersect2index;
float intersect1coeff, intersect2coeff;
int ia = i2;
int ib = i1;
int ic = i3;
const Vector3* a = &newVertices[ia];
const Vector3* b = &newVertices[ib];
const Vector3* c = &newVertices[ic];
sub3(b, a, &line1);
sub3(c, a, &line2);
// Calculate lerp coefficient for intersections
intersect1coeff = linePlaneCoefficient(a, &line1, &planeNormal, &planePoint);
intersect2coeff = linePlaneCoefficient(a, &line2, &planeNormal, &planePoint);
// Calculate intersections
lerp3(a, b, intersect1coeff, &intersect1);
lerp3(a, c, intersect2coeff, &intersect2);
intersect1index = newVertexCount++;
intersect2index = newVertexCount++;
// Save intersections as new vertices
newVertices[intersect1index] = intersect1;
newVertices[intersect2index] = intersect2;
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ib], intersect1coeff, &newNormals[intersect1index]);
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ic], intersect2coeff, &newNormals[intersect2index]);
// Add triangles
// Left
leftIndices[leftIndexCount++] = i2;
leftIndices[leftIndexCount++] = intersect2index;
leftIndices[leftIndexCount++] = intersect1index;
// Right
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = intersect2index;
rightIndices[rightIndexCount++] = i3;
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = i3;
rightIndices[rightIndexCount++] = i1;
}
else
{
Vector3 line1, line2;
Vector3 intersect1, intersect2;
int intersect1index, intersect2index;
float intersect1coeff, intersect2coeff;
int ia = i3;
int ib = i1;
int ic = i2;
const Vector3* a = &newVertices[ia];
const Vector3* b = &newVertices[ib];
const Vector3* c = &newVertices[ic];
sub3(b, a, &line1);
sub3(c, a, &line2);
// Calculate lerp coefficient for intersections
intersect1coeff = linePlaneCoefficient(a, &line1, &planeNormal, &planePoint);
intersect2coeff = linePlaneCoefficient(a, &line2, &planeNormal, &planePoint);
// Calculate intersections
lerp3(a, b, intersect1coeff, &intersect1);
lerp3(a, c, intersect2coeff, &intersect2);
intersect1index = newVertexCount++;
intersect2index = newVertexCount++;
// Save intersections as new vertices
newVertices[intersect1index] = intersect1;
newVertices[intersect2index] = intersect2;
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ib], intersect1coeff, &newNormals[intersect1index]);
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ic], intersect2coeff, &newNormals[intersect2index]);
// Add triangles
// Left
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = intersect2index;
leftIndices[leftIndexCount++] = i3;
// Right
rightIndices[rightIndexCount++] = i2;
rightIndices[rightIndexCount++] = intersect2index;
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = i2;
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = i1;
}
}
// Two vertices to left
else if (pointsToLeft == 2)
{
if (!v1Left)
{
Vector3 line1, line2;
Vector3 intersect1, intersect2;
int intersect1index, intersect2index;
float intersect1coeff, intersect2coeff;
int ia = i1;
int ib = i2;
int ic = i3;
const Vector3* a = &newVertices[ia];
const Vector3* b = &newVertices[ib];
const Vector3* c = &newVertices[ic];
sub3(b, a, &line1);
sub3(c, a, &line2);
// Calculate lerp coefficient for intersections
intersect1coeff = linePlaneCoefficient(a, &line1, &planeNormal, &planePoint);
intersect2coeff = linePlaneCoefficient(a, &line2, &planeNormal, &planePoint);
// Calculate intersections
lerp3(a, b, intersect1coeff, &intersect1);
lerp3(a, c, intersect2coeff, &intersect2);
intersect1index = newVertexCount++;
intersect2index = newVertexCount++;
// Save intersections as new vertices
newVertices[intersect1index] = intersect1;
newVertices[intersect2index] = intersect2;
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ib], intersect1coeff, &newNormals[intersect1index]);
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ic], intersect2coeff, &newNormals[intersect2index]);
// Add triangles
// Right
rightIndices[rightIndexCount++] = i1;
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = intersect2index;
// Left
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = i2;
leftIndices[leftIndexCount++] = i3;
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = i3;
leftIndices[leftIndexCount++] = intersect2index;
}
else if (!v2Left)
{
Vector3 line1, line2;
Vector3 intersect1, intersect2;
int intersect1index, intersect2index;
float intersect1coeff, intersect2coeff;
int ia = i2;
int ib = i1;
int ic = i3;
const Vector3* a = &newVertices[ia];
const Vector3* b = &newVertices[ib];
const Vector3* c = &newVertices[ic];
sub3(b, a, &line1);
sub3(c, a, &line2);
// Calculate lerp coefficient for intersections
intersect1coeff = linePlaneCoefficient(a, &line1, &planeNormal, &planePoint);
intersect2coeff = linePlaneCoefficient(a, &line2, &planeNormal, &planePoint);
// Calculate intersections
lerp3(a, b, intersect1coeff, &intersect1);
lerp3(a, c, intersect2coeff, &intersect2);
intersect1index = newVertexCount++;
intersect2index = newVertexCount++;
// Save intersections as new vertices
newVertices[intersect1index] = intersect1;
newVertices[intersect2index] = intersect2;
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ib], intersect1coeff, &newNormals[intersect1index]);
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ic], intersect2coeff, &newNormals[intersect2index]);
// Add triangles
// Right
rightIndices[rightIndexCount++] = i2;
rightIndices[rightIndexCount++] = intersect2index;
rightIndices[rightIndexCount++] = intersect1index;
// Left
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = intersect2index;
leftIndices[leftIndexCount++] = i3;
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = i3;
leftIndices[leftIndexCount++] = i1;
}
else if (!v3Left)
{
Vector3 line1, line2;
Vector3 intersect1, intersect2;
int intersect1index, intersect2index;
float intersect1coeff, intersect2coeff;
int ia = i3;
int ib = i1;
int ic = i2;
const Vector3* a = &newVertices[ia];
const Vector3* b = &newVertices[ib];
const Vector3* c = &newVertices[ic];
sub3(b, a, &line1);
sub3(c, a, &line2);
// Calculate lerp coefficient for intersections
intersect1coeff = linePlaneCoefficient(a, &line1, &planeNormal, &planePoint);
intersect2coeff = linePlaneCoefficient(a, &line2, &planeNormal, &planePoint);
// Calculate intersections
lerp3(a, b, intersect1coeff, &intersect1);
lerp3(a, c, intersect2coeff, &intersect2);
intersect1index = newVertexCount++;
intersect2index = newVertexCount++;
// Save intersections as new vertices
newVertices[intersect1index] = intersect1;
newVertices[intersect2index] = intersect2;
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ib], intersect1coeff, &newNormals[intersect1index]);
lerp3(&source->vertexNormals[ia], &source->vertexNormals[ic], intersect2coeff, &newNormals[intersect2index]);
// Add triangles
// Right
rightIndices[rightIndexCount++] = intersect1index;
rightIndices[rightIndexCount++] = intersect2index;
rightIndices[rightIndexCount++] = i3;
// Left
leftIndices[leftIndexCount++] = i2;
leftIndices[leftIndexCount++] = intersect2index;
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = i2;
leftIndices[leftIndexCount++] = intersect1index;
leftIndices[leftIndexCount++] = i1;
}
}
else
{
int j = 0;
}
}
delete left->vertices;
delete left->vertexNormals;
delete left->indices;
delete right->vertices;
delete right->vertexNormals;
delete right->indices;
left->vertices = new Vector3[newVertexCount];
left->vertexNormals = new Vector3[newVertexCount];
left->indices = new int[leftIndexCount];
left->vertexCount = newVertexCount;
left->indexCount = leftIndexCount;
memcpy(left->vertices, newVertices, left->vertexCount * sizeof(Vector3));
memcpy(left->vertexNormals, newNormals, left->vertexCount * sizeof(Vector3));
memcpy(left->indices, leftIndices, left->indexCount * sizeof(int));
right->vertices = new Vector3[newVertexCount];
right->vertexNormals = new Vector3[newVertexCount];
right->indices = new int[rightIndexCount];
right->vertexCount = newVertexCount;
right->indexCount = rightIndexCount;
memcpy(right->vertices, newVertices, right->vertexCount * sizeof(Vector3));
memcpy(right->vertexNormals, newNormals, right->vertexCount * sizeof(Vector3));
memcpy(right->indices, rightIndices, right->indexCount * sizeof(int));
delete newVertices;
delete newNormals;
delete leftIndices;
delete rightIndices;
}