Added collision detection

9 files changed, 265 insertions, 33 deletions

diff --git a/src/BSPTree.cpp b/src/BSPTree.cpp
index 7b23e79..46079e0 100644
--- a/src/BSPTree.cpp
+++ b/src/BSPTree.cpp
@@ -27,7 +27,7 @@ void BSPTree::partition(const TriangleRecord &t, std::list<TriangleRecord> *fron
     if(plane.contains(t.getTriangle().getVertex(i))) {
       const vmml::vec3f *v[3] = {&t.getTriangle().getVertex(i), &t.getTriangle().getVertex((i+1)%3), &t.getTriangle().getVertex((i+2)%3)};
 
-      vmml::vec3f is = plane.intersection(*v[1], *v[2]-*v[1]);
+      vmml::vec3f is = plane.intersection(MathUtil::Ray(*v[1], *v[2]-*v[1]));
 
       if(plane.isInFront(*v[1])) {
         front->push_back(TriangleRecord(Triangle(*v[0], *v[1], is, t.getTriangle().getColor()), t.getData()));
@@ -47,8 +47,8 @@ void BSPTree::partition(const TriangleRecord &t, std::list<TriangleRecord> *fron
 
     if((plane.isInFront(*v[0]) && plane.isBehind(*v[1]) && plane.isBehind(*v[2]))
         || (plane.isBehind(*v[0]) && plane.isInFront(*v[1]) && plane.isInFront(*v[2]))) {
-      vmml::vec3f is1 = plane.intersection(*v[0], *v[1]-*v[0]);
-      vmml::vec3f is2 = plane.intersection(*v[0], *v[2]-*v[0]);
+      vmml::vec3f is1 = plane.intersection(MathUtil::Ray(*v[0], *v[1]-*v[0]));
+      vmml::vec3f is2 = plane.intersection(MathUtil::Ray(*v[0], *v[2]-*v[0]));
 
       if(plane.isInFront(*v[0])) {
         front->push_back(TriangleRecord(Triangle(*v[0], is1, is2, t.getTriangle().getColor()), t.getData()));
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 613e604..8718ba7 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -1,7 +1,8 @@
 add_executable(zoom
   BSPTree.cpp BSPTree.h
-  Game.cpp Game.h
+  Collision.cpp Collision.h
   config.h
+  Game.cpp Game.h
   gl.h
   Level.cpp Level.h
   MathUtil.cpp MathUtil.h
diff --git a/src/Collision.cpp b/src/Collision.cpp
new file mode 100644
index 0000000..7c72922
--- /dev/null
+++ b/src/Collision.cpp
@@ -0,0 +1,97 @@
+/*
+ * Collision.cpp
+ *
+ * Copyright (C) 2009 Matthias Schiffer <matthias@gamezock.de>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License along
+ * with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include "Collision.h"
+
+namespace Zoom {
+
+vmml::vec3f Collision::projectToEdge(const vmml::vec3f& p, const vmml::vec3f& v1, const vmml::vec3f& v2) {
+  vmml::vec3f pVec = p - v1;
+  vmml::vec3f edge = v2 - v1;
+
+  float lengthSq = edge.squared_length();
+  float edgeProj = vmml::dot(edge, pVec);
+
+  if(edgeProj < 0) return v1;
+  if(edgeProj > lengthSq) return v2;
+
+  return v1 + (edgeProj/lengthSq)*edge;
+}
+
+vmml::vec3f Collision::projectToNearestEdge(const vmml::vec3f& p, const Triangle &t) {
+  vmml::vec3f p1 = projectToEdge(p, t.getVertex(0), t.getVertex(1));
+  vmml::vec3f p2 = projectToEdge(p, t.getVertex(1), t.getVertex(2));
+  vmml::vec3f p3 = projectToEdge(p, t.getVertex(2), t.getVertex(0));
+
+  if(p.squared_distance(p1) < p.squared_distance(p2) && p.squared_distance(p1) < p.squared_distance(p3))
+    return p1;
+  else if(p.squared_distance(p2) < p.squared_distance(p3))
+    return p2;
+  else
+    return p3;
+}
+
+
+bool Collision::test(const Triangle &t, const MathUtil::Ray &ray, float *distance) {
+  vmml::vec3f edge1 = t.getVertex(1) - t.getVertex(0);
+  vmml::vec3f edge2 = t.getVertex(2) - t.getVertex(0);
+
+  vmml::vec3f pvec = ray.getDirection().cross(edge2);
+
+  float det = vmml::dot(edge1, pvec);
+  if(det < MathUtil::EPSILON)
+    return false;
+
+  vmml::vec3f tvec = ray.getVertex() - t.getVertex(0);
+  float u = vmml::dot(pvec, tvec);
+
+  if(u < 0 || u > det)
+    return false;
+
+  vmml::vec3f qvec = tvec.cross(edge1);
+  float v = vmml::dot(ray.getDirection(), qvec);
+  if(v < 0 || u+v > det)
+    return false;
+
+  if(distance)
+    *distance = vmml::dot(edge2, qvec) / det;
+
+  return true;
+}
+
+bool Collision::test(const Triangle &t, const vmml::vec3f &m, float r, const vmml::vec3f &move) {
+  float distance;
+
+  if(test(t, MathUtil::Ray(m - r*t.computeNormal(), move), &distance) && distance > -MathUtil::EPSILON) {
+    if(distance < 1)
+      return true;
+    else
+      return false;
+  }
+
+  vmml::vec3f collisionPoint = projectToNearestEdge(m, t);
+  vmml::vec3f movedPoint = projectToEdge(m, collisionPoint, collisionPoint - move);
+
+  if(m.squared_distance(movedPoint) < r*r)
+    return true;
+  else
+    return false;
+}
+
+}
diff --git a/src/Collision.h b/src/Collision.h
new file mode 100644
index 0000000..635a7d3
--- /dev/null
+++ b/src/Collision.h
@@ -0,0 +1,41 @@
+/*
+ * Collision.h
+ *
+ * Copyright (C) 2009 Matthias Schiffer <matthias@gamezock.de>
+ *
+ * This program is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as published by the
+ * Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ * See the GNU Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License along
+ * with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef ZOOM_COLLISION_H_
+#define ZOOM_COLLISION_H_
+
+#include "MathUtil.h"
+
+namespace Zoom {
+
+class Collision {
+  public:
+    static bool test(const Triangle &t, const MathUtil::Ray &ray, float *distance = 0);
+    static bool test(const Triangle &t, const vmml::vec3f &m, float r, const vmml::vec3f &move);
+
+  private:
+    Collision();
+
+    static vmml::vec3f projectToEdge(const vmml::vec3f& p, const vmml::vec3f& v1, const vmml::vec3f& v2);
+    static vmml::vec3f projectToNearestEdge(const vmml::vec3f& p, const Triangle &t);
+};
+
+}
+
+#endif /* COLLISION_H_ */
diff --git a/src/Game.cpp b/src/Game.cpp
index 604eb64..5b61da7 100644
--- a/src/Game.cpp
+++ b/src/Game.cpp
@@ -18,18 +18,21 @@
  */
 
 #include "Game.h"
-
-#include "gl.h"
-#include "BSPTree.h"
+#include "Collision.h"
 #include "Level.h"
 #include "Shader.h"
 #include "ShadowVolume.h"
 #include "Triangle.h"
 
+#include "gl.h"
+
 #include <algorithm>
 
 namespace Zoom {
 
+const float Game::PLAYER_SPEED = 10;
+const float Game::PLAYER_RADIUS = 0.3;
+
 Game::Game() : playerPos(vmml::vec3f::ZERO), playerRotY(vmml::mat4f::IDENTITY), playerRotX(0),
     input(0), lightPos(0) {
   glEnable(GL_DEPTH_TEST);
@@ -92,6 +95,15 @@ void Game::turn(float x, float y) {
     playerRotX = -M_PI_2;
 }
 
+bool Game::doesCollide(const vmml::vec3f &playerMove) const {
+  for(std::vector<TriangleRecord>::const_iterator t = triangles.begin(); t != triangles.end(); ++t) {
+    if(Collision::test(t->getTriangle(), playerPos, PLAYER_RADIUS-MathUtil::EPSILON, playerMove))
+      return true;
+  }
+
+  return false;
+}
+
 void Game::run(int delta) {
   lightPos += delta*0.5;
   lightPos = std::fmod(lightPos, 26000);
@@ -111,8 +123,59 @@ void Game::run(int delta) {
     playerMove += playerRotY*vmml::vec3f::UNIT_X;
   }
 
+  if(playerMove == vmml::vec3f::ZERO)
+    return;
+
   playerMove.normalize();
-  playerPos += playerMove*0.01*delta;
+  playerMove *= PLAYER_SPEED*delta/1000;
+
+  vmml::vec3f origMove = playerMove;
+
+  bool ok = false;
+
+  while(!ok) {
+    ok = true;
+
+    MathUtil::Plane nearestPlane;
+
+    for(std::vector<TriangleRecord>::iterator t = triangles.begin(); t != triangles.end(); ++t) {
+      if(Collision::test(t->getTriangle(), playerPos, PLAYER_RADIUS, playerMove)) {
+        vmml::vec3f normal = t->getTriangle().computeNormal();
+        MathUtil::Plane p(normal, vmml::dot(normal, t->getTriangle().getVertex(0)+PLAYER_RADIUS*normal));
+        if(p.isInFront(playerPos) || p.contains(playerPos)) {
+          if(ok || p.distance(playerPos) < nearestPlane.distance(playerPos)) {
+            ok = false;
+
+            nearestPlane = p;
+          }
+        }
+      }
+    }
+
+    if(!ok) {
+      vmml::vec3f move;
+
+      if(playerMove.dot(nearestPlane.getNormal()) == 0)
+        move = playerMove;
+      else
+        move = nearestPlane.intersection(MathUtil::Ray(playerPos, playerMove)) - playerPos;
+
+      if(move.dot(origMove) <= 0 && move.squared_length() > MathUtil::EPSILON) {
+        return;
+      }
+
+      if(doesCollide(move))
+        return;
+
+      playerPos += move;
+
+      vmml::vec3f restMove = playerMove - move;
+      playerMove = restMove - nearestPlane.getNormal() * (nearestPlane.getNormal().dot(restMove));
+    }
+  }
+
+  if(!doesCollide(playerMove))
+    playerPos += playerMove;
 }
 
 void Game::render() {
@@ -153,6 +216,30 @@ void Game::render() {
   glLoadMatrixf(inverse.array);
 
   renderer.render(triangles, light);
+
+  Shader::disable();
+  glDepthFunc(GL_LEQUAL);
+  glStencilFunc(GL_ALWAYS, 0, std::numeric_limits<GLuint>::max());
+  glBlendFunc(GL_ONE, GL_ZERO);
+
+  glDisable(GL_TEXTURE_2D);
+  glColor3f(1, 1, 1);
+
+  vmml::vec3f lightVec = playerPos-light;
+
+  vmml::vec3f axis1 = lightVec.cross(vmml::vec3f(0, 1, 0)), axis2 = lightVec.cross(axis1);
+  axis1.normalize();
+  axis2.normalize();
+
+  glBegin(GL_POLYGON);
+  for(int i = 0; i < 32; ++i) {
+    vmml::vec3f pos = light + axis1*std::cos(M_PI*i/16.0)*0.05 + axis2*std::sin(M_PI*i/16.0)*0.05;
+
+    glVertex3fv(pos.array);
+  }
+  glEnd();
+
+  glEnable(GL_TEXTURE_2D);
 }
 
 }
diff --git a/src/Game.h b/src/Game.h
index b5c7ee7..b0e11a1 100644
--- a/src/Game.h
+++ b/src/Game.h
@@ -49,11 +49,16 @@ class Game {
       this->input = input;
     }
 
+    bool doesCollide(const vmml::vec3f &move) const;
+
     void turn(float x, float y);
     void run(int delta);
     void render();
 
   private:
+    static const float PLAYER_SPEED;
+    static const float PLAYER_RADIUS;
+
     Renderer renderer;
 
     boost::shared_ptr<Level> level;
diff --git a/src/MathUtil.cpp b/src/MathUtil.cpp
index 8ea3599..4a93cb8 100644
--- a/src/MathUtil.cpp
+++ b/src/MathUtil.cpp
@@ -24,10 +24,10 @@ namespace Zoom {
 
 const float MathUtil::EPSILON = 1E-6;
 
-vmml::vec3f MathUtil::Plane::intersection(const vmml::vec3f &p, const vmml::vec3f &dir) const {
-  float r = (d - p.dot(normal))/dir.dot(normal);
+vmml::vec3f MathUtil::Plane::intersection(const Ray &ray) const {
+  float r = (d - ray.getVertex().dot(normal))/ray.getDirection().dot(normal);
 
-  return p + r*dir;
+  return ray.getVertex() + r*ray.getDirection();
 }
 
 
diff --git a/src/MathUtil.h b/src/MathUtil.h
index 892d5dc..3f7ba90 100644
--- a/src/MathUtil.h
+++ b/src/MathUtil.h
@@ -30,6 +30,24 @@ class MathUtil {
   public:
     static const float EPSILON;
 
+    class Ray {
+      public:
+        Ray() : vertex(vmml::vec3f::ZERO), dir(vmml::vec3f::ZERO) {}
+        Ray(const vmml::vec3f &v, const vmml::vec3f &d) : vertex(v), dir(d) {}
+
+        const vmml::vec3f& getVertex() const {
+          return vertex;
+        }
+
+        const vmml::vec3f& getDirection() const {
+          return dir;
+        }
+
+      private:
+        vmml::vec3f vertex;
+        vmml::vec3f dir;
+    };
+
     class Plane {
       public:
         Plane(const vmml::vec3f &n = vmml::vec3f::ZERO, float d0 = 0) : normal(n), d(d0) {}
@@ -76,35 +94,21 @@ class MathUtil {
         }
 
 
+        float distance(const vmml::vec3f &v) {
+          return (normal.dot(v) - d);
+        }
+
         const vmml::vec3f& getNormal() const {
           return normal;
         }
 
-        vmml::vec3f intersection(const vmml::vec3f &p, const vmml::vec3f &dir) const;
+        vmml::vec3f intersection(const Ray &ray) const;
 
       private:
         vmml::vec3f normal;
         float d;
     };
 
-    class Ray {
-      public:
-        Ray() : vertex(vmml::vec3f::ZERO), dir(vmml::vec3f::ZERO) {}
-        Ray(const vmml::vec3f &v, const vmml::vec3f &d) : vertex(v), dir(d) {}
-
-        const vmml::vec3f& getVertex() const {
-          return vertex;
-        }
-
-        const vmml::vec3f& getDirection() const {
-          return dir;
-        }
-
-      private:
-        vmml::vec3f vertex;
-        vmml::vec3f dir;
-    };
-
     static vmml::mat4f perspective(float fovy, float aspect, float zNear);
 
   private:
diff --git a/src/zoom.cpp b/src/zoom.cpp
index 8467816..aa085bf 100644
--- a/src/zoom.cpp
+++ b/src/zoom.cpp
@@ -22,9 +22,6 @@
 #include "config.h"
 #include "gl.h"
 
-#include <cstdio>
-
-
 #ifdef _WIN32
 #else
 #include <iostream>