VMF Planes to Mesh

// ===========
// objects.h
// ===========

// Vector and Plane may not even be necessary anymore since I'm
// using Armadillo libraries. I may get rid of all these classes later.

#ifndef OBJECTS_H_INCLUDED
#define OBJECTS_H_INCLUDED

#include <iostream>
using namespace std;

class Vector
{
public:
    float x, y, z, d;
    Vector (const float& = 0, const float& = 0, const float& = 0);
    bool operator == (const Vector&);
    Vector operator + (const Vector&);
    Vector operator - (const Vector&);
    Vector operator * (const float&);
    Vector operator / (const float&);
    Vector operator ^ (const Vector&);
    float operator * (const Vector&);
};

class Plane
{
public:
    Vector a, b, c, n;
    Plane (const Vector&, const Vector&, const Vector&);

private:
    void getNormal ();
};

ostream& operator << (ostream&, const Vector&);
bool operator < (const Vector&, const Vector&);
Vector norm (Vector&);

#endif // OBJECTS_H_INCLUDED





// =============
// objects.cpp
// =============

#include <cmath>
#include "objects.h"
using namespace std;

// With a Vector type, you can initialize, compare, add and subtract
// other Vectors, multiply and divide by scalars, do a cross product (^)
// and dot product (*) between two Vectors, normalize a Vector, and
// print out a Vector directly to the console.

Vector::Vector (const float& a, const float& b, const float& c) {
    x = a; y = b; z = c; }

bool Vector::operator == (const Vector& param) {
    return (x == param.x) && (y == param.y) && (z == param.z); }

ostream& operator << (ostream& out, const Vector& param) {
    return out << "(" << param.x << ", " << param.y << ", " << param.z << ")"; }

Vector Vector::operator + (const Vector& param) {
    return Vector (x + param.x, y + param.y, z + param.z); }

Vector Vector::operator - (const Vector& param) {
    return Vector (x - param.x, y - param.y, z - param.z); }

Vector Vector::operator * (const float& param) {
    return Vector (x * param, y * param, z * param); }

Vector Vector::operator / (const float& param) {
    return Vector (x / param, y / param, z / param); }

float Vector::operator * (const Vector& param) {
    return (x * param.x) + (y * param.y) + (z * param.z); }

Vector Vector::operator ^ (const Vector& param)
{
    Vector temp;
    temp.x = (y * param.z) - (z * param.y);
    temp.y = (z * param.x) - (x * param.z);
    temp.z = (x * param.y) - (y * param.x);
    return temp;
}

bool operator < (const Vector& a, const Vector& b)
{
    if (a.x != b.x) return (a.x < b.x);
    else if (a.y != b.y) return (a.y < b.y);
    else return (a.z < b.z);
}

Vector norm (Vector& param) {
    return param / sqrt (param * param); }

// A Plane type holds the Vectors of three points that make up
// the Plane. It then calculates its normal and assigns that to d.

Plane::Plane (const Vector& d, const Vector& e, const Vector& f)
{
    a = d; b = e; c = f;
    getNormal ();
}

void Plane::getNormal ()
{
    Vector temp (
    Vector (b.x - a.x, b.y - a.y, b.z - a.z) ^
    Vector (c.x - b.x, c.y - b.y, c.z - b.z));

    n = norm (temp);
    n.d = n * a;
}





// ==========
// main.cpp
// ==========

// Using the Armadillo library.
// http://arma.sourceforge.net/

#include <map>
#include <set>
#include <armadillo>
#include "objects.h"

#define SMALL_NUM 0.0001

using namespace std;
using namespace arma;

// Get the intersection point of three planes if there is one.
// http://www.gamedev.net/topic/304411-three-plane-intersection-point/

void plane3Int (const Vector& i, const Vector& j, const Vector& k, mat& result, bool& success)
{
    success = false;
    static mat abc(3, 3);
    static vec d(3);

    abc(0, 0) = i.x; abc(0, 1) = i.y; abc(0, 2) = i.z;
    abc(1, 0) = j.x; abc(1, 1) = j.y; abc(1, 2) = j.z;
    abc(2, 0) = k.x; abc(2, 1) = k.y; abc(2, 2) = k.z;
    d[0] = i.d; d[1] = j.d; d[2] = k.d;

    if (det(abc) != 0) { success = true; result = solve(abc, d); }
}

int main()
{
    size_t planeSize = sizeof(plane) / sizeof(plane[0]);
    map<int, vector<Vector>> face;

    for (int i = 0; i < planeSize; ++i) {
        for (int j = i + 1; j < planeSize; ++j) {
            for (int k = j + 1; k < planeSize; ++k)
            {
                // If all three planes are parallel, move to next plane.
                // This also prevents use from running unnecessary matrix operations.
                // I may need to add more optimizing comparisons, either within K or J.

                if (fabs(plane[i].n * (plane[j].n ^ plane[k].n)) <= SMALL_NUM) continue;

                // Find the intersection of planes I, J, and K.
                // http://www.gamedev.net/topic/304411-three-plane-intersection-point/

                bool success;
                static vec temp(3);

                plane3Int(plane[i].n, plane[j].n, plane[k].n, temp, success);
                if (!success) continue;
                Vector result (temp(0), temp(1), temp(2));

                // Figure out if each vertex is part of the solid. Run a line from
                // plane I to our vertex. If there is an intersection, discard the vertex.
                // Algorithm for plane/line segment intersection from
                // http://math.stackexchange.com/questions/47594/plane-intersecting-line-segment

                for (int l = 0; l < planeSize; ++l)
                {
                    success = true;
                    if (l == i || l == j || l == k) continue;

                    Vector midpoint = (((plane[i].a + plane[i].b) / 2) + plane[i].c) / 2;
                    float distV1 = plane[l].n * (midpoint - plane[l].b);
                    float distV2 = plane[l].n * (result - plane[l].b);

                    if (distV1 * distV2 <= -SMALL_NUM) { success = false; break; }
                }

                // If our vertex is not discarded, we put it in faces I, J, and K.

                if (success)
                {
                    face[i].push_back(result);
                    face[j].push_back(result);
                    face[k].push_back(result);
                }
            }
        }
    }

    // Finally, we remove the duplicate points from each face. Thanks Jag!
    // Source: http://stackoverflow.com/questions/12200486/

    for (auto& vertices : face)
    {
        set<Vector> verticesCopy(vertices.second.begin(), vertices.second.end());
        vertices.second.assign(verticesCopy.begin(), verticesCopy.end());
    }

    return 0;
}