From 5dc3e727e0fc470d344da8b18c3588104585496f Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sat, 26 Dec 2009 03:19:49 +0100 Subject: Added collision detection --- src/BSPTree.cpp | 6 ++-- src/CMakeLists.txt | 3 +- src/Collision.cpp | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/Collision.h | 41 +++++++++++++++++++++++ src/Game.cpp | 95 +++++++++++++++++++++++++++++++++++++++++++++++++--- src/Game.h | 5 +++ src/MathUtil.cpp | 6 ++-- src/MathUtil.h | 42 ++++++++++++----------- src/zoom.cpp | 3 -- 9 files changed, 265 insertions(+), 33 deletions(-) create mode 100644 src/Collision.cpp create mode 100644 src/Collision.h 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 *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 *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 + * + * 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 . + */ + +#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 + * + * 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 . + */ + +#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 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::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::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::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; 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 - - #ifdef _WIN32 #else #include -- cgit v1.2.3