Commits

Anonymous committed 9af693b

fixed issue with floats close to zero

  • Participants
  • Parent commits 8814253

Comments (0)

Files changed (6)

File src/GameObjects/CLevelData.cpp

 	LevelObjectList results;
 	for (LevelObjectListItor it = list.begin(); it != list.end(); ++it) {
 		const PLevelObject& obj = *it;
-		if (Intersect(obj->GetBoundingRectangle(), rect))
+		if (Game::Intersect(obj->GetBoundingRectangle(), rect))
 			results.push_back(obj);
 	}
 	return results;
 
 Ogre::Vector2 CLevelData::ResolveCollision(PLevelObject object, const Ogre::Vector2& translation) {
 
+	// TODO: Make sure that length of resulting translation does not exceed the lenght of the translation
+	// TODO: Possible infinite loop if object is intersecting with two objects at the same time
+
 	bool bResolveFinished = false;
 
 	// get Rectangle and corresponding Polygon once; change manually if needed
 	Ogre::Vector2 currentTranslation = translation; // translation we are performing currently
 	Ogre::Vector2 result(0,0); 	// all performed translations until any given point
 
+	float maxLength = translation.length(); // maximum allowed transformation length
+
 	// stores translation vector for each face we already moved along
 	std::map<Game::Face, Ogre::Vector2> visitedFaces;
 
 
 	while (!bResolveFinished) {
 
-		if (approximatelyEqual(currentTranslation.x, 0.0f) && approximatelyEqual(currentTranslation.y, 0.0f)) {
+		if ( (approximatelyEqual(currentTranslation.x, 0.0f) && approximatelyEqual(currentTranslation.y, 0.0f))
+			 || approximatelyEqual(maxLength, 0.0f) || (maxLength <= 0.0f))  {
 			bResolveFinished = true;
 			continue;
 		}
 
+		// make sure not to move too far
+		float currentLength = currentTranslation.length();
+		if (currentLength > maxLength) {
+			currentTranslation = (maxLength / currentLength) * currentTranslation;
+		}
+
 		TEST_LOG("ResolveCollision: (" << rect.left << ", " << rect.top << ", " << rect.right << ", " << rect.bottom << ") "
 				 << currentTranslation);
 
 		// if no objects are in range, we will not collide
 		if (objects.empty()) {
 			result += currentTranslation;
+			maxLength -= currentTranslation.length();
 			currentTranslation = translation - result;
 			TEST_LOG("objects.empty()");
 			continue;
 			Game::Polygon objPolygon = obj->GetPolygon();
 
 			// check for intersection
-			if (Intersect(rect, boundingRect)) {
+			if (Game::Intersect(rect, boundingRect)) {
 				std::pair<bool, Ogre::Vector2> result = objPolygon.SeparatingAxesTest(objectPolygon);
 				if (!result.first) {
 					if (obj->HandleCollision(object, currentTranslation) == CLevelObject::ctBlocking) {
 			TEST_LOG("COLLISION");
 
 			const PLevelObject& obj = intersectingObjects[0];
+			Game::Polygon objPoly = obj->GetPolygon();
 
 			// get minimum translation vector
-			std::pair<bool, Ogre::Vector2> SATresult = objectPolygon.SeparatingAxesTest(obj->GetPolygon());
+			std::pair<bool, Ogre::Vector2> SATresult = objectPolygon.SeparatingAxesTest(objPoly);
 			Ogre::Vector2 translationResolve = SATresult.second * (1.0f + TOLERANCE);
 
-			/* TODO: only use MTV if it is very short, find better solution otherwise
+			float translationLength = translationResolve.length();
 
 			// always use MTV if it is _very_ short (usually a rounding error)
-			if (translationResolve.length() > 0.001f) {
-				// MTV is "big" - find solution in opposite moving direction
-				// ...?
+			if (translationLength > 0.01f) {
+				// find solution in opposite moving direction
+				Ogre::Vector2 currentTranslationDir = currentTranslation.normalisedCopy();
+				Game::SATResult SATres = objectPolygon.IsSeparatingAxis(objPoly, Ogre::Vector2(currentTranslationDir.y, -currentTranslationDir.x));
+				if (SATres.MinimumOverlap < 0.0f)
+					translationResolve = SATres.MinimumOverlap * currentTranslationDir;
+				else
+					translationResolve = SATres.MaximumOverlap * currentTranslationDir;
+				translationLength = translationResolve.length();
 			}
-			*/
-
-			TEST_LOG(translationResolve);
 
 			/*
 			// now translationResolve will resolve the collision
-			// perform this and repeat translation
+			// perform and repeat translation
 			*/
 
+			if (translationLength > maxLength) {
+				translationResolve = (maxLength / translationLength) * translationResolve;
+				maxLength = 0;
+			} else {
+				maxLength -= translationLength;
+			}
+
+			TEST_LOG(translationResolve);
+
 			rect.left = rect.left + translationResolve.x;
 			rect.right = rect.right + translationResolve.x;
 			rect.top = rect.top + translationResolve.y;
 		// no collision
 		if (collisionObjects.empty()) {
 			result += currentTranslation;
+			maxLength -= currentTranslation.length();
 			currentTranslation = translation - result;
 			TEST_LOG("collisionObjects.empty()");
 
 				// translate towards nearest object
 				Ogre::Vector2 maxTranslation = nearestFactor*currentTranslation*(1.0f - TOLERANCE);
 				result += maxTranslation;
+				maxLength -= maxTranslation.length();
 				objectPolygon.Translate(maxTranslation);
 				rect.left = rect.left + maxTranslation.x;
 				rect.right = rect.right + maxTranslation.x;
 		if (bNotFound) {
 			// no objects are blocking our way
 			result += currentTranslation;
+			maxLength -= currentTranslation.length();
 			currentTranslation = translation - result;
 			TEST_LOG("bNotFound=true");
 			continue;
 
 		TEST_LOG("remaining axes: " << separatingAxes.size());
 
-		// make separatingAxis face in same direction as currentTranslation
-		if (separatingAxis.dotProduct(currentTranslation) < 0.0f)
+		// make separatingAxis face in same direction as translation
+		if (separatingAxis.dotProduct(translation) < 0.0f)
 			separatingAxis = -separatingAxis;
 
 		// calculate maximum allowed translation along separatingAxis
 				// get minimum translation vector in direction of currentTranslation
 				Ogre::Vector2 axisNormal = LeftHandNormal(separatingAxes[i]);
 				Ogre::Vector2 MTV = satResult.MinimumOverlap * axisNormal;
-				if (MTV.dotProduct(currentTranslation) < 0)
+				if (MTV.dotProduct(translation) < 0)
 					MTV = satResult.MaximumOverlap * axisNormal;
 
 				float factor;
 			if (dp < 0) {
 				// cancel
 				TEST_LOG("dotProduct < 0");
-				return result;
+				bResolveFinished = true;
+				continue;
 			}
 		} else {
 			visitedFaces[nearestFace] = currentTranslation;

File src/GameObjects/CLevelData.h

 #ifndef LEVELDATA_H_
 #define LEVELDATA_H_
 
+#include "Geometry.h"
 #include "LevelObjects.h"
 #include "../testlog.h"
 #include "../Core/CLog.h"

File src/GameObjects/Geometry.h

 
 namespace Game {
 
-/** Maximum allowed absolute rounding error */
+/** Maximum allowed relative rounding error */
 const float TOLERANCE = 0.001f;
 
-/** Source: The Art of computer programming Vol 2 */
+/** Maximum allowed absolute rounding error*/
+const float TOLERANCE_ABS = 0.000001f;
+
+/** Source of float comparison functions: Knuth, The Art of computer programming Vol 2 */
 
 inline bool approximatelyEqual(float a, float b) {
+	// check absolute error first to be correctly compare numbers close to zero
+	if (fabs(a-b) <= TOLERANCE_ABS) return true;
     return fabs(a - b) <= ( (fabs(a) < fabs(b) ? fabs(b) : fabs(a)) * TOLERANCE);
 }
 
 	return Ogre::Vector2(v.y, -v.x).normalisedCopy();
 }
 
+/** Checks if two vectors are linearly dependent */
+inline bool LinearlyDependent(const Ogre::Vector2& v, const Ogre::Vector2& w) {
+	// check if a*v + b*w = 0 has a unique solution <=> det(v,w) = 0
+	float det = v.x*w.y - v.y*w.x;
+	return !approximatelyEqual(det, 0.0f);
+}
+
+/** Check if first rectangle contains the other one (fast) */
+inline bool Contains(const Ogre::Rectangle& r1, const Ogre::Rectangle& r2) {
+	return ((r2.left >= r1.left) && (r2.right <= r1.right) &&
+			(r2.top >= r1.top) && (r2.bottom <= r1.bottom));
+}
+
+/** Check if rectangles intersect (fast) */
+inline bool Intersect(const Ogre::Rectangle& r1, const Ogre::Rectangle& r2) {
+	return (r1.left < r2.right) &&
+		   (r1.right > r2.left) &&
+		   (r1.top > r2.bottom) &&
+		   (r1.bottom < r2.top);
+}
 
 struct Face {
 	Ogre::Vector2 v1;
 
 	/** 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 */
+	        in case of intersection also returns maximum factor that a translation of factor*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;
 	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 */
+	@return Second element indicates distance from origin of intersection point */
 	std::pair<bool, float> Intersects(const Ray& ray) const;
 
 	/** Checks for intersection with given polygon
-	@returns Second element indicates distance from origin of intersection point */
+	@return Second element indicates distance from origin of intersection point */
 	std::pair<bool, float> Intersects(const Face& face) const;
 
 	/** Checks for intersection with given polygon
-	@returns Second element indicates distance from origin of intersection point
+	@return 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) const;
 

File src/GameObjects/LevelObjects.cpp

 namespace Game {
 namespace GameObjects {
 
-bool Contains(const Ogre::Rectangle& r1, const Ogre::Rectangle& r2) {
-	return ((r2.left >= r1.left) && (r2.right <= r1.right) &&
-			(r2.top >= r1.top) && (r2.bottom <= r1.bottom));
-}
-
-bool Intersect(const Ogre::Rectangle& r1, const Ogre::Rectangle& r2) {
-	return (r1.left < r2.right) &&
-		   (r1.right > r2.left) &&
-		   (r1.top > r2.bottom) &&
-		   (r1.bottom < r2.top);
-}
-
 Ogre::Rectangle CLevelObject::GetBoundingRectangle() const {
 	Ogre::Rectangle rect;
 	rect.left = aabBounds.getMinimum().z;
 	boundingRect.right = aabBounds.getMaximum().z;
 
 	// check for collision
-	if (Contains(boundingRect, rect) || Intersect(boundingRect, rect)) {
+	if (::Game::Contains(boundingRect, rect) || ::Game::Intersect(boundingRect, rect)) {
 		// resolve collision in all directions
 		constraints.right = boundingRect.left - rect.right;
 		constraints.bottom = boundingRect.top - rect.bottom;

File test/CCustomAABBObjectTest.cpp

 	r2.left = -4; r2.top = 4;
 	r2.bottom = 0; r2.right = 0;
 
-	BOOST_CHECK( Intersect(r2, r1) );
+	BOOST_CHECK( Game::Intersect(r2, r1) );
 }
 
 /** Test CCube::GetConstraints */

File test/CollisionTest.cpp

 using namespace Game::GameObjects;
 using namespace std;
 
+class CTestLevelObject : public CLevelObject {
+public:
+	CTestLevelObject() {}
+	virtual ~CTestLevelObject() {}
+
+	void SetCollisionData(const Game::Polygon& polygon) { collisionData = polygon; }
+	virtual Game::Polygon GetPolygon() const { return collisionData; }
+
+private:
+	Game::Polygon collisionData;
+};
+
 BOOST_AUTO_TEST_SUITE(Collision);
 
 BOOST_AUTO_TEST_CASE( collision_test )
 	collider->SetPosition(Ogre::Vector3(0.0f, 1.0f, 1.0f));
 	collider->SetAABBSize(Ogre::Vector3(1.0f, 2.0f, 2.0f));
 	translation = leveldata->ResolveCollision(collider, Ogre::Vector2(1.0f, 0.0f));
-	FLOAT_CHECK_EQUAL(translation, Ogre::Vector2(1.0f, 0.0f));
+	FLOAT_CHECK_EQUAL(translation, Ogre::Vector2(-1.0f, 0.0f));
+
+	leveldata->ClearData();
+	CTestLevelObject* triangle = new CTestLevelObject();
+	Game::Polygon poly;
+	poly.AddPoint(Ogre::Vector2(0.0f, -2.0f));
+	poly.AddPoint(Ogre::Vector2(4.0f, -2.0f));
+	poly.AddPoint(Ogre::Vector2(4.0f,  2.0f));
+	triangle->SetCollisionData(poly);
+	triangle->SetBoundingBox(Ogre::AxisAlignedBox(0.0f, -2.0f, 0.0f, 0.0f, 2.0f, 4.0f));
+	PLevelObject trianglePtr(triangle);
+	leveldata->InsertObject(trianglePtr, CLevelData::otStatic);
+
+	collider->SetPosition(Ogre::Vector3(0.0f, 0.5f, 0.5f));
+	collider->SetAABBSize(Ogre::Vector3(1.0f, 1.0f, 1.0f));
+	translation = leveldata->ResolveCollision(collider, Ogre::Vector2(5.0f, 0.0f));
+	FLOAT_CHECK_EQUAL(translation, Ogre::Vector2(3.0f, 2.0f));
+
+	cube = PLevelObject(new CLevelObject());
+	cube->SetPosition(Ogre::Vector3(0.0f, 1.5f , 3.5f));
+	cube->SetAABBSize(Ogre::Vector3::UNIT_SCALE);
+	leveldata->InsertObject(cube, CLevelData::otStatic);
+	translation = leveldata->ResolveCollision(collider, Ogre::Vector2(5.0f, 0.0f));
+	FLOAT_CHECK_EQUAL(translation, Ogre::Vector2(2.0f, 1.0f));
+
 }
 
 BOOST_AUTO_TEST_SUITE_END();