Commits

Anonymous committed 43ef17f

added Geometry classes + tests; (still broken but tests work)

  • Participants
  • Parent commits 5882f14
  • Branches collision

Comments (0)

Files changed (6)

src/GameObjects/Geometry.cpp

+/*
+ * Geometry.cpp
+ *
+ *  Created on: Sep 28, 2010
+ *      Author: crt
+ */
+
+#include "Geometry.h"
+
+namespace Game {
+
+
+/*------------------
+ * Face
+ *------------------*/
+
+Face::Face() : v1(0.0f, 0.0f), v2(0.0f, 0.0f), normal(0.0f, 0.0f)
+{ }
+
+Face::Face(const Ogre::Vector2& vector1, const Ogre::Vector2& vector2)
+	: v1(vector1), v2(vector2)
+{
+	// calculate right hand normal
+	Ogre::Vector2 direction = v2-v1;
+	normal.x = -direction.y;
+	normal.y = direction.x;
+	normal.normalise();
+}
+
+Face::Face(const Ogre::Vector2& vector1, const Ogre::Vector2& vector2, const Ogre::Vector2& normal)
+	: v1(vector1), v2(vector2), normal(normal)
+{
+	this->normal.normalise();
+}
+
+bool Face::operator==(const Face& face2) const {
+	// dont compare normal
+	return ( (v1 == face2.v1 && v2 == face2.v2) ||
+		     (v1 == face2.v2 && v2 == face2.v1) );
+}
+
+std::ostream& operator<< (std::ostream& os, const Face &face) {
+	os << "Face( " << face.v1 << "; " << face.v2 << "; " << face.normal << " )";
+	return os;
+}
+
+
+/*------------------
+ * Polygon
+ *------------------*/
+
+Polygon::Polygon() {
+}
+
+
+Polygon::Polygon(const Face& face) {
+	this->Points.push_back(face.v1);
+	this->Points.push_back(face.v2);
+}
+
+Polygon::Polygon(const Ogre::Rectangle& rect) {
+	Points.push_back(Ogre::Vector2(rect.left, rect.bottom));
+	Points.push_back(Ogre::Vector2(rect.right, rect.bottom));
+	Points.push_back(Ogre::Vector2(rect.right, rect.top));
+	Points.push_back(Ogre::Vector2(rect.left, rect.top));
+}
+
+Polygon::~Polygon() {
+}
+
+bool Polygon::operator==(const Polygon& poly2) const {
+	if (Points.size() != poly2.Points.size())
+		return false;
+	// search for each point of this in poly2
+	for (int i = 0; i < Points.size(); i++) {
+		if (std::find(poly2.Points.begin(), poly2.Points.end(), Points[i]) == poly2.Points.end())
+			return false;
+	}
+	return true;
+}
+
+void Polygon::AddPoint(const Ogre::Vector2& vector) {
+	if (std::find(Points.begin(), Points.end(), vector) == Points.end()) {
+		Points.push_back(vector);
+	}
+}
+
+void Polygon::RemovePoint(const Ogre::Vector2& vector) {
+	VectorList::iterator it = std::find(Points.begin(), Points.end(), vector);
+	if (it != Points.end())
+		Points.erase(it);
+}
+
+void Polygon::Clear() {
+	Points.clear();
+}
+
+int Polygon::FaceCount() const {
+	if (Points.size() == 2)
+		return 1;
+	else if (Points.size() > 2)
+		return Points.size();
+	else
+		return 0;
+}
+
+std::vector<Face> Polygon::GetFaces(bool NoNormals) const {
+	std::vector<Face> result;
+	if (Points.size() == 2) {
+		result.push_back(Face(Points[0], Points[1]));
+	} else if (Points.size() > 2) {
+		for (int i = 0; i < Points.size(); i++) {
+			if (i != Points.size()-1) {
+				if (NoNormals)
+					result.push_back(Face(Points[i], Points[i+1], Ogre::Vector2::ZERO));
+				else
+					result.push_back(Face(Points[i], Points[i+1]));
+			} else {
+				if (NoNormals)
+					result.push_back(Face(Points[i], Points[0], Ogre::Vector2::ZERO));
+				else
+					result.push_back(Face(Points[i], Points[0]));
+			}
+		}
+	}
+	return result;
+}
+
+void Polygon::Translate(const Ogre::Vector2& translation) {
+	// translate all points
+	for (VectorList::iterator it = Points.begin(); it != Points.end(); ++it) {
+		*it = *it + translation;
+	}
+}
+
+/** Performs separating axis test for a given axis and polygon
+@return Test Result; see Polygon::SATResult */
+SATResult Polygon::IsSeparatingAxis(const Polygon& polygon, const Ogre::Vector2& axis) const {
+	if (this->FaceCount() < 1 || polygon.FaceCount() < 1) {
+		return SATResult(true, 0.0f, 0.0f);
+	}
+
+	// get normal of axis
+	Ogre::Vector2 normal( -axis.y, axis.x);
+	normal.normalise();
+
+	// project this
+	float min1, max1; // projected intervall of this
+	float dp;
+	min1 = max1 = normal.dotProduct(Points[0]);
+	for (int i = 1; i < Points.size(); i++) {
+		dp = normal.dotProduct(Points[i]);
+		if (dp < min1) min1 = dp;
+		if (dp > max1) max1 = dp;
+	}
+
+	// project polygon2
+	float min2, max2; // projected intervall of polygon2
+	min2 = max2 = normal.dotProduct(polygon.Points[0]);
+	for (int i = 1; i < polygon.Points.size(); i++) {
+		dp = normal.dotProduct(polygon.Points[i]);
+		if (dp < min2) min2 = dp;
+		if (dp > max2) max2 = dp;
+	}
+
+
+	SATResult result;
+	result.IsSeparating = (min1 - max2 > 0) || (min2 - max1 > 0);
+
+	if (min2 < max1)
+		result.MinimumOverlap = min2 - max1;
+	else if (min1 < max2)
+		result.MinimumOverlap = max2 - min1;
+
+	if (min2 < max1)
+		result.MaximumOverlap = min1 - max2;
+	else if (min1 < max2)
+		result.MaximumOverlap = max1 - min2;
+
+	return result;
+}
+
+std::pair<bool, Ogre::Vector2> Polygon::SeparatingAxesTest(const Polygon& polygon, const std::vector<Face>& faces, float &minOverlap) const {
+	Ogre::Vector2 MTV(0,0); // minimum translation vector
+
+	bool FoundAxis = false;
+	for (int i = 0; i < faces.size(); i++) {
+		Ogre::Vector2 axis = faces[i].GetVector();
+		axis.normalise();
+		SATResult sat = this->IsSeparatingAxis(polygon, axis);
+		if (!sat.IsSeparating) {
+			if (fabs(minOverlap) > fabs(sat.MinimumOverlap)) {
+				minOverlap = sat.MinimumOverlap;
+				MTV = sat.MinimumOverlap * axis;
+			}
+		} else {
+			FoundAxis = true;
+		}
+	}
+
+	if (FoundAxis)
+		return std::pair<bool, Ogre::Vector2>(true, Ogre::Vector2::ZERO);
+	else
+		return std::pair<bool, Ogre::Vector2>(false, MTV);
+}
+
+/** Performs separating axis test for all axes parallel to any faces
+@return true if a separating axis was found
+        in case of intersection, also returns minimum translation vector */
+std::pair<bool, Ogre::Vector2> Polygon::SeparatingAxesTest(const Polygon& polygon) const {
+	float minOverlap = std::numeric_limits<float>::infinity();
+
+	// check all faces of this
+	std::vector<Face> faces = this->GetFaces(true);
+	std::pair<bool, Ogre::Vector2> SATRes = SeparatingAxesTest(polygon, faces, minOverlap);
+
+	// check all faces of polygon
+	faces = polygon.GetFaces(true);
+	float minOverlap2 = minOverlap;
+	std::pair<bool, Ogre::Vector2> SATRes2 = SeparatingAxesTest(polygon, faces, minOverlap2);
+
+	if (SATRes.first || SATRes2.first)
+		return std::pair<bool, Ogre::Vector2>(true, Ogre::Vector2::ZERO);
+	else {
+		if (fabs(minOverlap) <= fabs(minOverlap2))
+			return std::pair<bool, Ogre::Vector2>(false, SATRes.second);
+		else
+			return std::pair<bool, Ogre::Vector2>(false, SATRes2.second);
+	}
+}
+
+/** Checks for intersection when translating this by direction
+	@return false if no intersection occurs
+	        in case of intersection also returns maximum factor that a translation of factor*direction leads to no collision
+	        with 0 <= factor <= 1 */
+std::pair<bool, float> Polygon::TranslationIntersect(const Polygon& polygon, const Ogre::Vector2& direction) const {
+	Ogre::Vector2 dirNormal = direction;
+	float dirLength = dirNormal.normalise();
+	float factor = std::numeric_limits<float>::infinity();
+	bool bIntersection = false;
+
+	// check all rays in direction through all points of this
+	for (int i = 0; i < Points.size(); i++) {
+		Ray ray(Points[i], dirNormal);
+		std::pair<bool, float> intersection = ray.Intersects(polygon);
+		if (intersection.first && intersection.second > 0.0f && intersection.second <= dirLength) {
+			bIntersection = true;
+			if (factor > intersection.second) {
+				factor = intersection.second;
+			}
+		}
+	}
+
+	// check all rays in direction through all points of polygon
+	for (int i = 0; i < polygon.Points.size(); i++) {
+		Ray ray(polygon.Points[i], -dirNormal);
+		std::pair<bool, float> intersection = ray.Intersects(polygon);
+		if (intersection.first && intersection.second > 0.0f && intersection.second <= dirLength) {
+			bIntersection = true;
+			if (factor > intersection.second) {
+				factor = intersection.second;
+			}
+		}
+	}
+
+	return std::pair<bool, float>(bIntersection, factor / dirLength);
+}
+
+std::ostream& operator<< (std::ostream& os, const Polygon& polygon) {
+	os << "Polygon( NumFaces=" << polygon.FaceCount() << " )";
+	return os;
+}
+
+
+/*------------------
+ * Ray
+ *------------------*/
+
+Ray::Ray() : Origin(0.0f, 0.0f), Direction(0.0f, 0.0f)
+{}
+
+Ray::Ray(const Ogre::Vector2& origin, const Ogre::Vector2& direction) : Origin(origin)
+{
+	Direction = direction.normalisedCopy();
+}
+
+/** Checks for intersection with given ray
+@returns Second element indicates distance from origin of intersection point */
+std::pair<bool, float> Ray::Intersects(const Ray& ray) {
+	/*
+	 * Solve t*v1 + o1 = u*v2 + o2   <=>  t*v1 - u*v2 = o2 - o1
+	 * <=>  Ax = y  with  y=o2-o1,  A = (v1, -v2),  x = (t, u)^t
+	 * <=> x = A^-1 y
+	 * <=> t = A^-1[1,1] * y[1] + A^-1[1,2] * y[2]
+	 *
+	 */
+
+	// calculate A^-1 using Cramer's rule
+
+	// det(A) = a*d - b*c
+	float det =  -(this->Direction.x * ray.Direction.y) + (this->Direction.y * ray.Direction.x);
+
+	// if det(A) is 0 the rays are parallel
+	if (AlmostEqual(det, 0.0f))
+		return std::pair<bool, float>(false, 0.0f);
+
+	Ogre::Vector2 y = ray.Origin - this->Origin;
+
+	// first row of A^-1 is 1/det(A)*(d,-b)
+	float t = (1.0f / det) * ( - ray.Direction.y * y.x  + ray.Direction.x * y.y);
+
+	return std::pair<bool, float>(true, t);
+}
+
+/** Checks for intersection with given polygon
+@returns Second element indicates distance from origin of intersection point */
+std::pair<bool, float> Ray::Intersects(const Face& face) {
+	// construct ray through both points of face and check for intersection
+	Ogre::Vector2 faceDirection = face.v2 - face.v1;
+	Ray faceRay(face.v1, faceDirection);
+	std::pair<bool, float> rayIntersection = faceRay.Intersects(*this);
+
+	// check if intersection is between the two points of face
+	if (rayIntersection.first && rayIntersection.second >= 0.0f && rayIntersection.second <= faceDirection.length()) {
+		return this->Intersects(faceRay);
+	} else {
+		return std::pair<bool, float>(false, 0.0f);
+	}
+}
+
+/** Checks for intersection with given polygon
+@returns Second element indicates distance from origin of intersection point
+@remarks Returns intersection point which is closest to ray's origin*/
+std::pair<bool, float> Ray::Intersects(const Polygon& polygon) {
+	float nearestFactor = std::numeric_limits<float>::infinity();
+	bool bIntersection = false;
+
+	// check all faces of polygon for intersection; return the nearest
+	std::vector<Face> faces = polygon.GetFaces(true);
+	for (int i = 0; i < faces.size(); i++) {
+		std::pair<bool, float> intersection = this->Intersects(faces[i]);
+		if (intersection.first) {
+			bIntersection = true;
+			if (fabs(nearestFactor) > fabs(intersection.second))
+				nearestFactor = intersection.second;
+		}
+	}
+
+	return std::pair<bool, float>(bIntersection, nearestFactor);
+}
+
+}

src/GameObjects/Geometry.h

+/*
+ * Geometry.h
+ *
+ *  Created on: Sep 28, 2010
+ *      Author: crt
+ */
+
+#ifndef GEOMETRY_H_
+#define GEOMETRY_H_
+
+#include "Ogre.h"
+#include <vector>
+
+namespace Game {
+
+/** Maximum allowed absolute rounding error */
+const float TOLERANCE = 0.001f;
+
+/** Maximum allowed ULPs (Units of Least Precision) when comparing floats */
+const int MAX_ULPS = 10000;
+
+/** Check if two floats are almost equal
+Sources:
+* http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
+* http://stackoverflow.com/questions/17333/most-effective-way-for-float-and-double-comparison */
+/*inline bool AlmostEqual(float A, float B)
+{
+    // If A or B are infinity (positive or negative) then
+    // only return true if they are exactly equal to each other -
+    // that is, if they are both infinities of the same sign.
+    // This check is only needed if you will be generating
+    // infinities and you don't want them 'close' to numbers
+    // near FLT_MAX.
+    if (std::isinf(A) || std::isinf(B))
+        return A == B;
+
+    int aInt = *(int*)&A;
+    // Make aInt lexicographically ordered as a twos-complement int
+    if (aInt < 0)
+        aInt = 0x80000000 - aInt;
+    // Make bInt lexicographically ordered as a twos-complement int
+    int bInt = *(int*)&B;
+    if (bInt < 0)
+        bInt = 0x80000000 - bInt;
+
+    // Now we can compare aInt and bInt to find out how far apart A and B
+    // are.
+    int intDiff = abs(aInt - bInt);
+    if (intDiff <= MAX_ULPS)
+        return true;
+    return false;
+}
+*/
+inline bool AlmostEqual(float A, float B)
+{
+    if (A == B)
+        return true;
+
+    float relativeError;
+
+    if (fabs(B) > fabs(A))
+        relativeError = fabs((A - B) / B);
+    else
+        relativeError = fabs((A - B) / A);
+
+    if (relativeError <= TOLERANCE)
+        return true;
+    return false;
+}
+
+
+struct Face {
+	Ogre::Vector2 v1;
+	Ogre::Vector2 v2;
+	Ogre::Vector2 normal;
+
+	Face();
+	Face(const Ogre::Vector2& vector1, const Ogre::Vector2& vector2);
+	Face(const Ogre::Vector2& vector1, const Ogre::Vector2& vector2, const Ogre::Vector2& normal);
+	bool operator==(const Face& face2) const;
+	bool operator!=(const Face& face2) const { return !(*this == face2); }
+	Ogre::Vector2 GetVector() const { return v2 - v1; }
+};
+
+std::ostream& operator<< (std::ostream& os, const Face &face);
+
+/** Defines Result of a Separating Axes Test */
+struct SATResult {
+	/** True, if given Axis is separating */
+	bool IsSeparating;
+	/** Smallest translation along axis which resolves intersection (MinimumOverlap*axis)
+	 *  Undefined if IsSeparating==true*/
+	float MinimumOverlap;
+	/** Smallest translation along axis which resolves intersection in opposite direction of MinimumOverlap
+	 * Undefined if IsSeparating==true*/
+	float MaximumOverlap;
+
+	SATResult() : IsSeparating(true), MinimumOverlap(0.0f), MaximumOverlap(0.0f) {}
+	SATResult(bool isSeparating, float minOverlap, float maxOverlap)
+		: IsSeparating(isSeparating), MinimumOverlap(minOverlap), MaximumOverlap(maxOverlap) {}
+};
+
+/** Defines a Polygon in 2D Space */
+class Polygon {
+public:
+	/** Create empty Polygon */
+	Polygon();
+	/** Create Polygon from one Face */
+	Polygon(const Face& face);
+	/** Create Polygon from Rectangle */
+	Polygon(const Ogre::Rectangle& rect);
+	virtual ~Polygon();
+
+	bool operator==(const Polygon& poly2) const;
+	bool operator!=(const Polygon& poly2) const { return !(*this == poly2); }
+
+	/** Add Point to Polygon
+	@remarks Normals will be calculated wrong if points are not added counter-clockwise */
+	void AddPoint(const Ogre::Vector2& vector);
+	/** Remove Point from Polygon */
+	void RemovePoint(const Ogre::Vector2& vector);
+	/** Remove all Points */
+	void Clear();
+	/** Get Number of Faces */
+	int FaceCount() const;
+	/** Get all faces
+	@param NoNormals Set true to not calculate any normals (faster)
+	@see AddPoint */
+	std::vector<Face> GetFaces(bool NoNormals = false) const;
+	/** Moves all Points by translation */
+	void Translate(const Ogre::Vector2& translation);
+
+	/** Performs separating axis test for a given axis and polygon
+	@return Test Result; see Polygon::SATResult */
+	SATResult IsSeparatingAxis(const Polygon& polygon, const Ogre::Vector2& axis) const;
+
+	/** Performs separating axis test for all axes parallel to any faces
+	@return true if a separating axis was found
+	        in case of intersection, also returns minimum translation vector
+	@remarks Only works if polygon is convex */
+	std::pair<bool, Ogre::Vector2> SeparatingAxesTest(const Polygon& polygon) const;
+
+	/** Checks for intersection when translating this by direction
+	@return false if no intersection occurs
+	        in case of intersection also returns maximum factor that a translation of facter*direction leads to no collision */
+	std::pair<bool, float> TranslationIntersect(const Polygon& polygon, const Ogre::Vector2& direction) const;
+private:
+	typedef std::vector<Ogre::Vector2> VectorList;
+	VectorList Points;
+
+	std::pair<bool, Ogre::Vector2> SeparatingAxesTest(const Polygon& polygon, const std::vector<Face>& faces, float &minOverlap) const;
+};
+
+std::ostream& operator<< (std::ostream& os, const Polygon &polygon);
+
+/** Defines a Ray in 2D Space*/
+class Ray {
+public:
+	Ray();
+	Ray(const Ogre::Vector2& origin, const Ogre::Vector2& direction);
+
+	inline void SetOrigin(const Ogre::Vector2& origin) { Origin = origin; }
+	inline const Ogre::Vector2& GetOrigin() const { return Origin; }
+	inline void SetDirection(const Ogre::Vector2& direction) { Direction = direction.normalisedCopy(); }
+	inline const Ogre::Vector2& GetDirection() const { return Direction; }
+	inline Ogre::Vector2 GetPoint(float t) const { return Origin + t*Direction; }
+
+	/** Checks for intersection with given ray
+	@returns Second element indicates distance from origin of intersection point */
+	std::pair<bool, float> Intersects(const Ray& ray);
+
+	/** Checks for intersection with given polygon
+	@returns Second element indicates distance from origin of intersection point */
+	std::pair<bool, float> Intersects(const Face& face);
+
+	/** Checks for intersection with given polygon
+	@returns Second element indicates distance from origin of intersection point
+	@remarks Returns intersection point which is closest to ray's origin*/
+	std::pair<bool, float> Intersects(const Polygon& polygon);
+
+private:
+ 	Ogre::Vector2 Origin;
+ 	Ogre::Vector2 Direction;
+};
+
+}
+
+#endif /* GEOMETRY_H_ */

test/CCustomAABBObjectTest.cpp

 using namespace Game::GameObjects;
 using namespace std;
 
-BOOST_AUTO_TEST_SUITE(CustomAABBObjectTest);
+BOOST_AUTO_TEST_SUITE(LevelObjectTest);
 
 /** Test interset(Rectangle, Rectangle) function */
 BOOST_AUTO_TEST_CASE( intersect_test )
 	Vector3 position(0,0,0);
 	Vector3 size(2,2,2);
 
-	PCustomAABBObject cube(new CCustomAABBObject("", position));
+	PLevelObject cube(new CLevelObject(position));
 	cube->SetAABBSize(size);
 
 	// set collider to touch cube in (1/1)

test/CMakeLists.txt

 	TestState.h
 	TestStateFactory.h
 	../src/GameObjects/LevelObjects.h
-	../src/GameObjects/CLevelData.h
+#	../src/GameObjects/CLevelData.h
+	../src/GameObjects/Geometry.h
 )
 
 SET(TEST_SRCS
 	StateManagerTest.cpp
 	CCustomAABBObjectTest.cpp
 	SettingsManagerTest.cpp
-	CollisionTest.cpp
+#	CollisionTest.cpp
+	GeometryTest.cpp
 	../src/Core/CStateManager.cpp
 	../src/Core/CSettingsManager.cpp	
 	../src/GameObjects/LevelObjects.cpp
-	../src/GameObjects/CLevelData.cpp		
+#	../src/GameObjects/CLevelData.cpp	
+	../src/GameObjects/Geometry.cpp	
 )
  
 if (CMAKE_BUILD_TYPE STREQUAL "Debug")

test/CollisionTest.cpp

 	Vector3 position(0,0,0);
 	Vector3 size(2,2,2);
 
-	PCustomAABBObject cube(new CCustomAABBObject("", position));
+	PLevelObject cube(new CLevelObject(position));
 	cube->SetAABBSize(size);
 
 	PLevelData leveldata(new CLevelData());

test/GeometryTest.cpp

+/*
+ * GeometryTest.cpp
+ *
+ *  Created on: Sep 28, 2010
+ *      Author: crt
+ */
+
+#include "../src/GameObjects/Geometry.h"
+#include "boost/test/unit_test.hpp"
+#include <math.h>
+
+using namespace Game;
+
+#define sign(x) (( x > 0 ) - ( x < 0 ))
+
+
+BOOST_AUTO_TEST_SUITE(Geometry);
+
+BOOST_AUTO_TEST_CASE( face_test )
+{
+	Face emptyFace;
+	BOOST_CHECK(emptyFace.v1 == Ogre::Vector2::ZERO);
+	BOOST_CHECK(emptyFace.v2 == Ogre::Vector2::ZERO);
+	BOOST_CHECK_EQUAL(emptyFace.normal, Ogre::Vector2::ZERO);
+
+	Face normalTest(Ogre::Vector2::UNIT_X, Ogre::Vector2::ZERO);
+	BOOST_CHECK(normalTest.v1 == Ogre::Vector2::UNIT_X);
+	BOOST_CHECK(normalTest.v2 == Ogre::Vector2::ZERO);
+	BOOST_CHECK_EQUAL(normalTest.normal, Ogre::Vector2::NEGATIVE_UNIT_Y);
+
+	normalTest = Face(Ogre::Vector2::ZERO, Ogre::Vector2::UNIT_X);
+	BOOST_CHECK(normalTest.v2 == Ogre::Vector2::UNIT_X);
+	BOOST_CHECK(normalTest.v1 == Ogre::Vector2::ZERO);
+	BOOST_CHECK_EQUAL(normalTest.normal, Ogre::Vector2::UNIT_Y);
+
+	BOOST_CHECK(normalTest != emptyFace);
+
+	emptyFace = Face(Ogre::Vector2::ZERO, Ogre::Vector2::UNIT_X);
+	BOOST_CHECK(normalTest == emptyFace);
+
+	emptyFace.normal = Ogre::Vector2(10, 5);
+	BOOST_CHECK(normalTest == emptyFace);
+}
+
+BOOST_AUTO_TEST_CASE( polygon_constructor_test )
+{
+	Game::Polygon polygon;
+
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 0);
+	BOOST_CHECK_EQUAL(polygon.GetFaces().size(), 0);
+
+	Face face(Ogre::Vector2::ZERO, Ogre::Vector2::UNIT_X);
+	polygon = Game::Polygon(face);
+
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 1);
+
+	std::vector<Face> faces = polygon.GetFaces();
+	BOOST_REQUIRE_EQUAL(faces.size(), 1);
+
+	BOOST_CHECK_EQUAL(faces[0].v1, Ogre::Vector2::ZERO);
+	BOOST_CHECK_EQUAL(faces[0].v2, Ogre::Vector2::UNIT_X);
+
+	Ogre::Rectangle rect;
+	rect.left = -1; rect.right = 1;
+	rect.bottom = -1; rect.top = 1;
+	polygon = Game::Polygon(rect);
+
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 4);
+
+	faces = polygon.GetFaces();
+	BOOST_REQUIRE_EQUAL(faces.size(), 4);
+
+	BOOST_CHECK_EQUAL(faces[0].v2, faces[1].v1);
+	BOOST_CHECK_EQUAL(faces[1].v2, faces[2].v1);
+	BOOST_CHECK_EQUAL(faces[2].v2, faces[3].v1);
+	BOOST_CHECK_EQUAL(faces[3].v2, faces[0].v1);
+
+	BOOST_CHECK_EQUAL(faces[0].v1, Ogre::Vector2(-1, -1));
+	BOOST_CHECK_EQUAL(faces[1].v1, Ogre::Vector2(1, -1));
+	BOOST_CHECK_EQUAL(faces[2].v1, Ogre::Vector2(1, 1));
+	BOOST_CHECK_EQUAL(faces[3].v1, Ogre::Vector2(-1, 1));
+}
+
+BOOST_AUTO_TEST_CASE( polygon_modifier_test )
+{
+	Game::Polygon polygon;
+
+	polygon.AddPoint(Ogre::Vector2::ZERO);
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 0);
+	BOOST_CHECK_NE(polygon, Game::Polygon());
+
+	polygon.AddPoint(Ogre::Vector2::UNIT_X);
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 1);
+
+	polygon.AddPoint(Ogre::Vector2::UNIT_X);
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 1);
+
+	polygon.AddPoint(Ogre::Vector2::UNIT_Y);
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 3);
+
+	polygon.RemovePoint(Ogre::Vector2::UNIT_X);
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 1);
+
+	polygon.Clear();
+	BOOST_CHECK_EQUAL(polygon.FaceCount(), 0);
+
+	BOOST_CHECK_EQUAL(polygon, Game::Polygon());
+
+	polygon.AddPoint(Ogre::Vector2::UNIT_X);
+	polygon.AddPoint(Ogre::Vector2::UNIT_Y);
+
+	Game::Polygon polygon2(Face(Ogre::Vector2::UNIT_Y, Ogre::Vector2::UNIT_X));
+
+	BOOST_CHECK_EQUAL(polygon, polygon2);
+
+	polygon2.RemovePoint(Ogre::Vector2::UNIT_Y);
+
+	BOOST_CHECK_NE(polygon, polygon2);
+
+	polygon.Translate(Ogre::Vector2::UNIT_X);
+	std::vector<Face> faces = polygon.GetFaces();
+
+	BOOST_CHECK_EQUAL(faces[0], Face(Ogre::Vector2(2.0f, 0.0f), Ogre::Vector2(1.0f, 1.0f)));
+}
+
+BOOST_AUTO_TEST_CASE( polygon_intersection_test )
+{
+	Ogre::Rectangle rect;
+	rect.left = rect.bottom = -1.0f;
+	rect.right = rect.top = 1.0f;
+
+	Game::Polygon poly1(rect);
+	Game::Polygon poly2 = poly1;
+
+	SATResult result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2::UNIT_X);
+	BOOST_CHECK_EQUAL(result.IsSeparating, false);
+	result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2::UNIT_Y);
+	BOOST_CHECK_EQUAL(result.IsSeparating, false);
+	std::pair<bool, Ogre::Vector2> result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, false);
+	BOOST_CHECK_EQUAL(result2.second.length(), 2.0f);
+
+	poly1.Translate(result2.second * (1.0f + TOLERANCE));
+	result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, true);
+
+	poly1 = Game::Polygon(rect);
+
+	poly1.Translate(Ogre::Vector2::UNIT_Y * (result.MinimumOverlap*(1.0f+TOLERANCE)));
+	result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, true);
+
+	poly1 = Game::Polygon(rect);
+	poly1.Translate(Ogre::Vector2::UNIT_Y * (result.MaximumOverlap*(1.0f+TOLERANCE)));
+	result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, true);
+
+	poly1 = Game::Polygon(rect);
+	poly2.Translate(Ogre::Vector2(3.0f, 0.0f));
+
+	result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2::UNIT_X);
+	BOOST_CHECK_EQUAL(result.IsSeparating, false);
+	result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2::UNIT_Y);
+	BOOST_CHECK_EQUAL(result.IsSeparating, true);
+	result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, true);
+
+	poly2 = Game::Polygon();
+	poly2.AddPoint(Ogre::Vector2(0.0f, -4.0f));
+	poly2.AddPoint(Ogre::Vector2(3.0f, -4.0f));
+	poly2.AddPoint(Ogre::Vector2(3.0f, 2.0f));
+
+	result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2::UNIT_X);
+	BOOST_CHECK_EQUAL(result.IsSeparating, false);
+	result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2::UNIT_Y);
+	BOOST_CHECK_EQUAL(result.IsSeparating, false);
+	result = poly1.IsSeparatingAxis(poly2, Ogre::Vector2(3.0f, 6.0f));
+	BOOST_CHECK_EQUAL(result.IsSeparating, true);
+	result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, true);
+
+	// translate triangle; should intersect now and MTV should have length of approx. 0.447
+	poly2.Translate(Ogre::Vector2(-1.0f, 0.0f));
+	result2 = poly1.SeparatingAxesTest(poly2);
+	BOOST_CHECK_EQUAL(result2.first, false);
+	BOOST_CHECK( AlmostEqual(result2.second.length(), 0.447f) );
+}
+
+BOOST_AUTO_TEST_CASE( polygon_intersection_test2 )
+{
+	Game::Polygon poly1, poly2;
+	poly1.AddPoint(Ogre::Vector2( 0.0f, 0.0f));
+	poly1.AddPoint(Ogre::Vector2( 0.0f, 2.0f));
+	poly1.AddPoint(Ogre::Vector2(-2.0f, 0.0f));
+
+	poly2.AddPoint(Ogre::Vector2( 1.0f, 0.0f));
+	poly2.AddPoint(Ogre::Vector2( 3.0f, 0.0f));
+	poly2.AddPoint(Ogre::Vector2( 3.0f, 2.0f));
+
+	std::pair<bool, float> result = poly2.TranslationIntersect(poly1, Ogre::Vector2(-2.0f, 0.0f));
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK( AlmostEqual(result.second, 0.5f) );
+
+	result = poly2.TranslationIntersect(poly1, Ogre::Vector2(-2.0f, 2.0f));
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK( AlmostEqual(result.second, 0.5f) );
+}
+
+BOOST_AUTO_TEST_CASE( ray_ray_intersection_test )
+{
+	Game::Ray ray1( Ogre::Vector2::ZERO, Ogre::Vector2::UNIT_Y );
+	Game::Ray ray2( Ogre::Vector2(1.0f, 1.0f), Ogre::Vector2::NEGATIVE_UNIT_X );
+
+	std::pair<bool, float> result = ray1.Intersects(ray2);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( result.second, 1.0f );
+
+	result = ray2.Intersects(ray1);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( result.second, 1.0f );
+
+	ray2 = ray1;
+	result = ray1.Intersects(ray2);
+	BOOST_CHECK_EQUAL(result.first, false);
+
+	ray2 = Game::Ray( Ogre::Vector2(1.0f, 0.0f), Ogre::Vector2::UNIT_Y );
+	result = ray1.Intersects(ray2);
+	BOOST_CHECK_EQUAL(result.first, false);
+	result = ray2.Intersects(ray1);
+	BOOST_CHECK_EQUAL(result.first, false);
+
+	ray1 = Game::Ray( Ogre::Vector2(2.0f, 5.0f), Ogre::Vector2(1.0f, 1.0f) );
+	ray2 = Game::Ray( Ogre::Vector2(2.0f, 5.0f), Ogre::Vector2(-1.0f, 3.0f) );
+	result = ray1.Intersects(ray2);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( result.second, 0.0f );
+	result = ray2.Intersects(ray1);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( result.second, 0.0f );
+
+	ray2.SetOrigin(Ogre::Vector2(1.0f, 4.0f));
+	// rays will intersect at 1.0f/4.0f
+	result = ray1.Intersects(ray2);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( AlmostEqual(result.second, -sqrt(2.0f)), true );
+	result = ray2.Intersects(ray1);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( AlmostEqual(result.second, 0.0f), true );
+}
+
+BOOST_AUTO_TEST_CASE( ray_face_intersection_test )
+{
+	Game::Ray ray(Ogre::Vector2::ZERO, Ogre::Vector2::UNIT_X);
+	Game::Face face(Ogre::Vector2(1.0f, 0.0f), Ogre::Vector2(1.0f, 1.0f));
+
+	std::pair<bool, float> result = ray.Intersects(face);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( AlmostEqual(result.second, 1.0f), true );
+
+	ray.SetOrigin(Ogre::Vector2(0.0f, 2.0f));
+	result = ray.Intersects(face);
+	BOOST_CHECK_EQUAL(result.first, false);
+
+	face = Game::Face(Ogre::Vector2(0.0f, 3.0f), Ogre::Vector2(1.0f, 2.0f));
+	result = ray.Intersects(face);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( AlmostEqual(result.second, 1.0f), true );
+
+	ray.SetDirection(Ogre::Vector2(1.0f, 1.0f));
+	result = ray.Intersects(face);
+	BOOST_CHECK_EQUAL(result.first, true);
+	BOOST_CHECK_EQUAL( AlmostEqual(result.second, sqrt(2.0f) / 2.0f), true );
+}
+
+BOOST_AUTO_TEST_SUITE_END();