MCDV/convexPolytope.h

   1 #pragma once
   2 #include <iostream>
   3 #include <glad\glad.h>
   4 #include <GLFW\glfw3.h>
   5
   6 #include <glm\glm.hpp>
   7 #include <glm\gtc\matrix_transform.hpp>
   8 #include <glm\gtc\type_ptr.hpp>
   9
  10 #include <vector>
  11 #include <unordered_set>
  12
  13 #include "plane.h"
  14 #include "Mesh.hpp"
  15
  16 struct BrushPolygon {
  17         Plane plane;
  18         std::vector<glm::vec3> vertices;
  19
  20         BrushPolygon(Plane p) :
  21                 plane(p) {}
  22 };
  23
  24 namespace ray
  25 {
  26         bool IntersectNgon(glm::vec3 orig, glm::vec3 dir,
  27                 BrushPolygon polygon,
  28                 float* t)
  29         {
  30                 if (polygon.vertices.size() < 3)
  31                         return false;
  32
  33                 glm::vec3 N = polygon.plane.normal;
  34
  35                 //Find P
  36
  37                 //Check parralel
  38                 float NdotRayDir = glm::dot(N, dir);
  39                 if (glm::abs(NdotRayDir) < 1e-3)
  40                         return false;
  41
  42                 //Compute T
  43                 *t = -(glm::dot(N, orig) + polygon.plane.offset) / NdotRayDir;
  44                 //Check if triangle is behind the ray
  45                 if (*t < 0) return false;
  46
  47                 glm::vec3 P = orig + ((*t) * dir);
  48
  49                 glm::vec3 C, edge, vp;
  50
  51                 //Inside out testing
  52                 for (int i = 0; i < polygon.vertices.size(); i++)
  53                 {
  54                         glm::vec3 v0 = polygon.vertices[i];
  55                         glm::vec3 v1 = i + 1 == polygon.vertices.size() ? polygon.vertices[0] : polygon.vertices[i + 1];
  56
  57                         edge = v1 - v0;
  58                         vp = P - v0;
  59                         C = glm::cross(edge, vp);
  60                         if (glm::dot(N, C) < 0) {
  61                                 return false;
  62                         }
  63                 }
  64
  65                 return true;
  66         }
  67
  68
  69         bool IntersectTriangle(glm::vec3 orig, glm::vec3 dir,
  70                 glm::vec3 v0, glm::vec3 v1, glm::vec3 v2, glm::vec3 norm,
  71                 float* t)
  72         {
  73                 glm::vec3 N = norm;
  74
  75                 //Find P
  76
  77                 //Check parralel
  78                 float NdotRayDir = glm::dot(N, dir);
  79                 if (glm::abs(NdotRayDir) < 1e-4)
  80                         return false;
  81
  82                 float d = glm::dot(N, v0);
  83
  84                 //Compute T
  85                 *t = -(glm::dot(N, orig) + d) / NdotRayDir;
  86                 //Check if triangle is behind the ray
  87                 if (*t < 0) return false;
  88
  89                 glm::vec3 P = orig + ((*t) * dir);
  90
  91                 glm::vec3 C, edge, vp;
  92
  93                 //Inside out testing
  94                 edge = v1 - v0;
  95                 vp = P - v0;
  96                 C = glm::cross(edge, vp);
  97                 if (glm::dot(N, C) < 0) return false;
  98
  99                 edge = v2 - v1;
 100                 vp = P - v1;
 101                 C = glm::cross(edge, vp);
 102                 if (glm::dot(N, C) < 0) return false;
 103
 104                 edge = v0 - v2;
 105                 vp = P - v2;
 106                 C = glm::cross(edge, vp);
 107                 if (glm::dot(N, C) < 0) return false;
 108
 109                 return true;
 110         }
 111
 112         std::vector<float> IntersectMesh(glm::vec3 orig, glm::vec3 dir, Mesh* mesh)
 113         {
 114                 std::vector<float> ret;
 115                 for (int i = 0; i < mesh->vertices.size() / 18; i++)
 116                 {
 117                         glm::vec3 v0 = glm::vec3(mesh->vertices[i * 18 + 0], mesh->vertices[i * 18 + 1], mesh->vertices[i * 18 + 2]);
 118                         glm::vec3 n0 = glm::vec3(mesh->vertices[i * 18 + 3], mesh->vertices[i * 18 + 4], mesh->vertices[i * 18 + 5]);
 119                         glm::vec3 v1 = glm::vec3(mesh->vertices[i * 18 + 6], mesh->vertices[i * 18 + 7], mesh->vertices[i * 18 + 8]);
 120                         glm::vec3 n1 = glm::vec3(mesh->vertices[i * 18 + 9], mesh->vertices[i * 18 + 10], mesh->vertices[i * 18 + 11]);
 121                         glm::vec3 v2 = glm::vec3(mesh->vertices[i * 18 + 12], mesh->vertices[i * 18 + 13], mesh->vertices[i * 18 + 14]);
 122                         glm::vec3 n2 = glm::vec3(mesh->vertices[i * 18 + 15], mesh->vertices[i * 18 + 16], mesh->vertices[i * 18 + 17]);
 123
 124                         float dist;
 125                         if (ray::IntersectTriangle(orig, dir, v0, v1, v2, n0, &dist))
 126                                 if (dist > 0)
 127                                         ret.push_back(dist);
 128                 }
 129
 130                 return ret;
 131         }
 132 }
 133
 134 class Polytope {
 135 public:
 136         Mesh * GeneratedMesh;
 137         Mesh* ngonMesh;
 138         std::vector<BrushPolygon> ngons;
 139         std::vector<float> meshData;
 140
 141         glm::vec3 NWU;
 142         glm::vec3 SEL;
 143
 144         Polytope(std::vector<Plane> planes, bool gen_gl_mesh = true, bool dbg = false)
 145         {
 146                 std::vector<glm::vec3> intersecting;
 147
 148                 //Set up polygon structure
 149                 for (int i = 0; i < planes.size(); i++) {
 150                         this->ngons.push_back(BrushPolygon(planes[i]));
 151                 }
 152
 153                 // Do plane intersections
 154                 for (int i = 0; i < planes.size(); i++) {
 155                         for (int j = 0; j < planes.size(); j++) {
 156                                 for (int k = 0; k < planes.size(); k++) {
 157                                         if (i == j || i == k || j == k) continue; //Skip invalid checks
 158
 159                                         glm::vec3 p(0, 0, 0);
 160
 161                                         if (!Plane::FinalThreePlaneIntersection(planes[i], planes[j], planes[k], &p)) { continue; };
 162
 163                                         bool valid = true;
 164                                         //Check if point is outside object
 165                                         for (int m = 0; m < planes.size(); m++)
 166                                         {
 167                                                 if (Plane::EvalPointPolarity(planes[m], p) < -0.01f)
 168                                                 {
 169                                                         valid = false;
 170                                                         break;
 171                                                 }
 172                                         }
 173
 174                                         if (!valid) continue;
 175
 176                                         intersecting.push_back(p);
 177
 178                                         //Add verts
 179                                         this->ngons[i].vertices.push_back(p);
 180                                         this->ngons[j].vertices.push_back(p);
 181                                         this->ngons[k].vertices.push_back(p);
 182                                 }
 183                         }
 184                 }
 185
 186                 std::vector<float> generatedMesh;
 187
 188                 float x = this->ngons[0].vertices[0].x;
 189                 float _x = this->ngons[0].vertices[0].x;
 190                 float y = this->ngons[0].vertices[0].y;
 191                 float _y = this->ngons[0].vertices[0].y;
 192                 float z = this->ngons[0].vertices[0].z;
 193                 float _z = this->ngons[0].vertices[0].z;
 194
 195                 //Remove polygon vertex duplicates
 196                 for (int i = 0; i < this->ngons.size(); i++) {
 197
 198                         std::vector<glm::vec3> newlist;
 199
 200                         //Cleanup and find bounds
 201
 202                         for (int j = 0; j < this->ngons[i].vertices.size(); j++)
 203                         {
 204                                 bool found = false;
 205
 206                                 for (int k = 0; k < newlist.size(); k++)
 207                                 {
 208                                         if (glm::distance(newlist[k], this->ngons[i].vertices[j]) < 0.5f) //Throw out dupe points (within half a unit)
 209                                         {
 210                                                 found = true; break;
 211                                         }
 212                                 }
 213
 214                                 if (found) continue;
 215
 216                                 newlist.push_back(this->ngons[i].vertices[j]);
 217
 218                                 x = this->ngons[i].vertices[j].x > x ? this->ngons[i].vertices[j].x : x;
 219                                 _x = this->ngons[i].vertices[j].x < _x ? this->ngons[i].vertices[j].x : _x;
 220
 221                                 y = this->ngons[i].vertices[j].y > y ? this->ngons[i].vertices[j].y : y;
 222                                 _y = this->ngons[i].vertices[j].y < _y ? this->ngons[i].vertices[j].y : _y;
 223
 224                                 z = this->ngons[i].vertices[j].z > z ? this->ngons[i].vertices[j].z : z;
 225                                 _z = this->ngons[i].vertices[j].z < _z ? this->ngons[i].vertices[j].z : _z;
 226                         }
 227
 228                         this->ngons[i].vertices = newlist;
 229
 230                         //Reorder vertices
 231                         if (this->ngons[i].vertices.size() < 3)
 232                                 continue;
 233
 234                         std::vector<glm::vec3> points = Plane::OrderCoplanarClockWise(this->ngons[i].plane, this->ngons[i].vertices);
 235                         this->ngons[i].vertices = points;
 236                         for (int j = 0; j < points.size() - 2; j++) {
 237                                 glm::vec3 a = points[0];
 238                                 glm::vec3 b = points[j + 1];
 239                                 glm::vec3 c = points[j + 2];
 240
 241                                 generatedMesh.push_back(-a.x);
 242                                 generatedMesh.push_back(a.z);
 243                                 generatedMesh.push_back(a.y);
 244
 245                                 generatedMesh.push_back(this->ngons[i].plane.normal.x);
 246                                 generatedMesh.push_back(-this->ngons[i].plane.normal.z);
 247                                 generatedMesh.push_back(-this->ngons[i].plane.normal.y);
 248
 249
 250                                 generatedMesh.push_back(-b.x);
 251                                 generatedMesh.push_back(b.z);
 252                                 generatedMesh.push_back(b.y);
 253
 254                                 generatedMesh.push_back(this->ngons[i].plane.normal.x);
 255                                 generatedMesh.push_back(-this->ngons[i].plane.normal.z);
 256                                 generatedMesh.push_back(-this->ngons[i].plane.normal.y);
 257
 258
 259                                 generatedMesh.push_back(-c.x);
 260                                 generatedMesh.push_back(c.z);
 261                                 generatedMesh.push_back(c.y);
 262
 263                                 generatedMesh.push_back(this->ngons[i].plane.normal.x);
 264                                 generatedMesh.push_back(-this->ngons[i].plane.normal.z);
 265                                 generatedMesh.push_back(-this->ngons[i].plane.normal.y);
 266                         }
 267                 }
 268
 269                 NWU = glm::vec3(-_x, z, y);
 270                 SEL = glm::vec3(-x, _z, _y);
 271
 272                 this->meshData = generatedMesh;
 273
 274                 if (gen_gl_mesh)
 275                 {
 276                         Mesh* m = new Mesh(generatedMesh, MeshMode::POS_XYZ_NORMAL_XYZ);
 277                         this->GeneratedMesh = m;
 278                 }
 279         }
 280 };