author insilmaril Fri, 01 Feb 2008 15:28:35 +0000 changeset 662 9abdd5e6c3dc parent 661 6a5e2c27f8a4 child 663 827d334d55f1
 geometry.cpp file | annotate | diff | revisions geometry.h file | annotate | diff | revisions
```     1.1 --- a/geometry.cpp	Fri Feb 01 15:28:35 2008 +0000
1.2 +++ b/geometry.cpp	Fri Feb 01 15:28:35 2008 +0000
1.3 @@ -1,7 +1,10 @@
1.4  #include "geometry.h"
1.5
1.6  #include <math.h>
1.7 +#include <iostream>
1.8 +#include "misc.h"
1.9
1.10 +using namespace std;
1.11
1.12  QRectF addBBox(QRectF r1, QRectF r2)
1.13  {
1.14 @@ -44,8 +47,9 @@
1.15
1.16  QPointF normalize (const QPointF &p)
1.17  {
1.18 -	qreal n=sqrt ( p.x()*p.x() + p.y()*p.y() );
1.19 -	return QPointF (p.x()/n,p.y()/n);
1.20 +	if (p==QPointF(0,0)) return p;
1.21 +	qreal l=sqrt ( p.x()*p.x() + p.y()*p.y() );
1.22 +	return QPointF (p.x()/l,p.y()/l);
1.23  }
1.24
1.25  // Dot product of two vectors
1.26 @@ -54,19 +58,6 @@
1.27  	return a.x()*b.x() + a.y()*b.y();
1.28  }
1.29
1.30 -// Structure that stores the results of the PolygonCollision function
1.31 -class PolygonCollisionResult {
1.32 -public:
1.33 -    // Are the polygons going to intersect forward in time?
1.34 -    bool WillIntersect;
1.35 -
1.36 -    // Are the polygons currently intersecting?
1.37 -    bool Intersect;
1.38 -
1.39 -    // The translation to apply to the first polygon to push the polygons apart.
1.40 -    QPointF MinimumTranslationVector;
1.41 -};
1.42 -
1.43
1.44  /* Calculate the projection of a polygon on an axis
1.45     and returns it as a [min, max] interval
1.46 @@ -110,8 +101,8 @@
1.47  PolygonCollisionResult PolygonCollision(QPolygonF polygonA,
1.48                                QPolygonF polygonB, QPointF velocity) {
1.49      PolygonCollisionResult result;
1.50 -    result.Intersect = true;
1.51 -    result.WillIntersect = true;
1.52 +    result.intersect = true;
1.53 +    result.willIntersect = true;
1.54
1.55      int edgeCountA = polygonA.size();
1.56      int edgeCountB = polygonB.size();
1.57 @@ -119,14 +110,42 @@
1.58      QPointF translationAxis;
1.59      QPointF edge;
1.60
1.61 +	cout << "\nA: ";
1.62 +	for (int k=0; k<edgeCountA;k++)
1.63 +		cout <<polygonA.at(k);
1.64 +	cout << "\nB: ";
1.65 +	for (int k=0; k<edgeCountB;k++)
1.66 +		cout <<polygonB.at(k);
1.67 +
1.68 +
1.69      // Loop through all the edges of both polygons
1.70 -
1.71 -    for (int i=0; i < edgeCountA + edgeCountB; i++)
1.72 +	int i=0;
1.73 +	int j=0;
1.74 +	while (i<edgeCountA && j<edgeCountB)
1.75  	{
1.76          if (i< edgeCountA)
1.77 -            edge = polygonA.at(i);
1.78 -        else
1.79 -            edge = polygonB.at(i - edgeCountA);
1.80 +		{
1.81 +			if (i<edgeCountA - 1)
1.82 +				edge = QPointF (
1.83 +					polygonA.at(i+1).x()-polygonA.at(i).x(),
1.84 +					polygonA.at(i+1).y()-polygonA.at(i).y());
1.85 +			else
1.86 +				edge = QPointF (
1.87 +					polygonA.at(0).x()-polygonA.at(i).x(),
1.88 +					polygonA.at(0).y()-polygonA.at(i).y());
1.89 +			i++;
1.90 +        } else
1.91 +		{
1.92 +			if (i < edgeCountB -1)
1.93 +				edge = QPointF (
1.94 +					polygonB.at(j+1).x() - polygonA.at(i).x(),
1.95 +					polygonB.at(j+1).y() - polygonA.at(i).y());
1.96 +			else
1.97 +				edge = QPointF (
1.98 +					polygonB.at(0).x() - polygonA.at(i).x(),
1.99 +					polygonB.at(0).y() - polygonA.at(i).y());
1.100 +			j++;
1.101 +		}
1.102
1.103          // ===== 1. Find if the polygons are currently intersecting =====
1.104
1.105 @@ -134,7 +153,7 @@
1.106          // Find the axis perpendicular to the current edge
1.107
1.108          QPointF axis (-edge.y(), edge.x());
1.109 -        normalize(axis);
1.110 +        axis=normalize(axis);
1.111
1.112          // Find the projection of the polygon on the current axis
1.113
1.114 @@ -144,8 +163,10 @@
1.115
1.116          // Check if the polygon projections are currentlty intersecting
1.117
1.118 -        if (intervalDistance(minA, maxA, minB, maxB) > 0)\
1.119 -            result.Intersect = false;
1.120 +        if (intervalDistance(minA, maxA, minB, maxB) > 0)
1.121 +            result.intersect = false;
1.122 +		else
1.123 +            result.intersect = true;
1.124
1.125          // ===== 2. Now find if the polygons *will* intersect =====
1.126
1.127 @@ -156,42 +177,58 @@
1.128
1.129          // Get the projection of polygon A during the movement
1.130
1.131 -        if (velocityProjection < 0) {
1.132 +        if (velocityProjection < 0)
1.133              minA += velocityProjection;
1.134 -        } else {
1.135 +        else
1.136              maxA += velocityProjection;
1.137 -        }
1.138 +
1.139
1.140          // Do the same test as above for the new projection
1.141
1.142          qreal d = intervalDistance(minA, maxA, minB, maxB);
1.143 -        if (d > 0) result.WillIntersect = false;
1.144 +        if (d > 0) result.willIntersect = false;
1.145 +		/*
1.146 +		*/
1.147 +		cout <<"   ";
1.148 +		cout <<"minA="<<minA<<"  ";
1.149 +		cout <<"maxA="<<maxA<<"  ";
1.150 +		cout <<"minB="<<minB<<"  ";
1.151 +		cout <<"maxB="<<maxB<<"  ";
1.152 +		cout <<"  d="<<d<<"   ";
1.153 +		cout <<"minD="<<minIntervalDistance<<"  ";
1.154 +		cout <<"axis="<<axis<<"  ";
1.155 +		cout <<"int="<<result.intersect<<"  ";
1.156 +		cout <<"wint="<<result.willIntersect<<"  ";
1.157 +		//cout <<"velProj="<<velocityProjection<<"  ";
1.158 +		cout <<endl;
1.159
1.160 -        // If the polygons are not intersecting and won't intersect, exit the loop
1.161
1.162 -        if (!result.Intersect && !result.WillIntersect) break;
1.163 +
1.164 +        if (result.intersect || result.willIntersect)
1.165 +		{
1.166 +			// Check if the current interval distance is the minimum one. If so
1.167 +			// store the interval distance and the current distance.  This will
1.168 +			// be used to calculate the minimum translation vector
1.169
1.170 -        // Check if the current interval distance is the minimum one. If so store
1.171 -        // the interval distance and the current distance.
1.172 -        // This will be used to calculate the minimum translation vector
1.173 +			if (d<0) d=-d;
1.174 +			if (d < minIntervalDistance) {
1.175 +				minIntervalDistance = d;
1.176 +				translationAxis = axis;
1.177 +				cout << "tAxix="<<translationAxis<<endl;
1.178
1.179 -        if (d<0) d=-d;
1.180 -        if (d < minIntervalDistance) {
1.181 -            minIntervalDistance = d;
1.182 -            translationAxis = axis;
1.183 -
1.184 -            //QPointF t = polygonA.Center - polygonB.Center;
1.185 -            QPointF t = polygonA.at(0) - polygonB.at(0);
1.186 -            if (dotProduct(t,translationAxis) < 0)
1.187 -                translationAxis = -translationAxis;
1.188 -        }
1.189 +				//QPointF t = polygonA.Center - polygonB.Center;
1.190 +				QPointF t = polygonA.at(0) - polygonB.at(0);
1.191 +				if (dotProduct(t,translationAxis) < 0)
1.192 +					translationAxis = -translationAxis;
1.193 +			}
1.194 +		}
1.195      }
1.196
1.197      // The minimum translation vector
1.198      // can be used to push the polygons appart.
1.199
1.200 -    if (result.WillIntersect)
1.201 -        result.MinimumTranslationVector =
1.202 +    if (result.willIntersect)
1.203 +        result.minTranslation =
1.204                 translationAxis * minIntervalDistance;
1.205
1.206      return result;
1.207 @@ -208,7 +245,7 @@
1.208  if (r.WillIntersect)
1.209    // Move the polygon by its velocity, then move
1.210    // the polygons appart using the Minimum Translation Vector
1.211 -  polygonATranslation = velocity + r.MinimumTranslationVector;
1.212 +  polygonATranslation = velocity + r.minTranslation;
1.213  else
1.214    // Just move the polygon by its velocity
1.215    polygonATranslation = velocity;
```
```     2.1 --- a/geometry.h	Fri Feb 01 15:28:35 2008 +0000
2.2 +++ b/geometry.h	Fri Feb 01 15:28:35 2008 +0000
2.3 @@ -10,4 +10,25 @@
2.4
2.5  QPointF normalize (const QPointF &p);
2.6
2.7 +
2.8 +qreal dotProduct (const QPointF &a, const QPointF &b);
2.9 +
2.10 +class PolygonCollisionResult {
2.11 +public:
2.12 +    // Are the polygons going to intersect forward in time?
2.13 +    bool willIntersect;
2.14 +
2.15 +    // Are the polygons currently intersecting?
2.16 +    bool intersect;
2.17 +
2.18 +    // The translation to apply to the first polygon to push the polygons apart.
2.19 +    QPointF minTranslation;
2.20 +};
2.21 +
2.22 +
2.23 +void ProjectPolygon(QPointF axis, QPolygonF polygon, qreal &min, qreal &max) ;
2.24 +qreal intervalDistance(qreal minA, qreal maxA, qreal minB, qreal maxB);
2.25 +PolygonCollisionResult PolygonCollision(QPolygonF polygonA,
2.26 +                              QPolygonF polygonB, QPointF velocity);
2.27 +
2.28  #endif
```