src/supertux/collision.cpp

   1 //  SuperTux
   2 //  Copyright (C) 2006 Matthias Braun <matze@braunis.de>
   3 //
   4 //  This program is free software: you can redistribute it and/or modify
   5 //  it under the terms of the GNU General Public License as published by
   6 //  the Free Software Foundation, either version 3 of the License, or
   7 //  (at your option) any later version.
   8 //
   9 //  This program is distributed in the hope that it will be useful,
  10 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 //  GNU General Public License for more details.
  13 //
  14 //  You should have received a copy of the GNU General Public License
  15 //  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 #include "supertux/collision.hpp"
  18
  19 #include <algorithm>
  20
  21 #include "math/aatriangle.hpp"
  22 #include "math/rect.hpp"
  23
  24 namespace collision {
  25
  26 bool intersects(const Rect& r1, const Rect& r2)
  27 {
  28   if(r1.p2.x < r2.p1.x || r1.p1.x > r2.p2.x)
  29     return false;
  30   if(r1.p2.y < r2.p1.y || r1.p1.y > r2.p2.y)
  31     return false;
  32
  33   return true;
  34 }
  35
  36 //---------------------------------------------------------------------------
  37
  38 namespace {
  39 inline void makePlane(const Vector& p1, const Vector& p2, Vector& n, float& c)
  40 {
  41   n = Vector(p2.y-p1.y, p1.x-p2.x);
  42   c = -(p2 * n);
  43   float nval = n.norm();
  44   n /= nval;
  45   c /= nval;
  46 }
  47
  48 }
  49
  50 bool rectangle_aatriangle(Constraints* constraints, const Rect& rect,
  51                           const AATriangle& triangle, const Vector& addl_ground_movement)
  52 {
  53   if(!intersects(rect, (const Rect&) triangle))
  54     return false;
  55
  56   Vector normal;
  57   float c;
  58   Vector p1;
  59   Rect area;
  60   switch(triangle.dir & AATriangle::DEFORM_MASK) {
  61     case 0:
  62       area.p1 = triangle.p1;
  63       area.p2 = triangle.p2;
  64       break;
  65     case AATriangle::DEFORM1:
  66       area.p1 = Vector(triangle.p1.x, triangle.p1.y + triangle.get_height()/2);
  67       area.p2 = triangle.p2;
  68       break;
  69     case AATriangle::DEFORM2:
  70       area.p1 = triangle.p1;
  71       area.p2 = Vector(triangle.p2.x, triangle.p1.y + triangle.get_height()/2);
  72       break;
  73     case AATriangle::DEFORM3:
  74       area.p1 = triangle.p1;
  75       area.p2 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p2.y);
  76       break;
  77     case AATriangle::DEFORM4:
  78       area.p1 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p1.y);
  79       area.p2 = triangle.p2;
  80       break;
  81     default:
  82       assert(false);
  83   }
  84
  85   switch(triangle.dir & AATriangle::DIRECTION_MASK) {
  86     case AATriangle::SOUTHWEST:
  87       p1 = Vector(rect.p1.x, rect.p2.y);
  88       makePlane(area.p1, area.p2, normal, c);
  89       break;
  90     case AATriangle::NORTHEAST:
  91       p1 = Vector(rect.p2.x, rect.p1.y);
  92       makePlane(area.p2, area.p1, normal, c);
  93       break;
  94     case AATriangle::SOUTHEAST:
  95       p1 = rect.p2;
  96       makePlane(Vector(area.p1.x, area.p2.y),
  97                 Vector(area.p2.x, area.p1.y), normal, c);
  98       break;
  99     case AATriangle::NORTHWEST:
 100       p1 = rect.p1;
 101       makePlane(Vector(area.p2.x, area.p1.y),
 102                 Vector(area.p1.x, area.p2.y), normal, c);
 103       break;
 104     default:
 105       assert(false);
 106   }
 107
 108   float n_p1 = -(normal * p1);
 109   float depth = n_p1 - c;
 110   if(depth < 0)
 111     return false;
 112
 113 #if 0
 114   std::cout << "R: " << rect << " Tri: " << triangle << "\n";
 115   std::cout << "Norm: " << normal << " Depth: " << depth << "\n";
 116 #endif
 117
 118   Vector outvec = normal * (depth + 0.2f);
 119
 120   const float RDELTA = 3;
 121   if(p1.x < area.p1.x - RDELTA || p1.x > area.p2.x + RDELTA
 122      || p1.y < area.p1.y - RDELTA || p1.y > area.p2.y + RDELTA) {
 123     set_rectangle_rectangle_constraints(constraints, rect, area);
 124     constraints->hit.left = false;
 125     constraints->hit.right = false;
 126   } else {
 127     if(outvec.x < 0) {
 128       constraints->right = rect.get_right() + outvec.x;
 129     } else {
 130       constraints->left = rect.get_left() + outvec.x;
 131     }
 132
 133     if(outvec.y < 0) {
 134       constraints->bottom = rect.get_bottom() + outvec.y;
 135       constraints->hit.bottom = true;
 136       constraints->ground_movement += addl_ground_movement;
 137     } else {
 138       constraints->top = rect.get_top() + outvec.y;
 139       constraints->hit.top = true;
 140     }
 141     constraints->hit.slope_normal = normal;
 142   }
 143
 144   return true;
 145 }
 146
 147 void set_rectangle_rectangle_constraints(Constraints* constraints,
 148                                          const Rect& r1, const Rect& r2, const Vector& addl_ground_movement)
 149 {
 150   float itop = r1.get_bottom() - r2.get_top();
 151   float ibottom = r2.get_bottom() - r1.get_top();
 152   float ileft = r1.get_right() - r2.get_left();
 153   float iright = r2.get_right() - r1.get_left();
 154
 155   float vert_penetration = std::min(itop, ibottom);
 156   float horiz_penetration = std::min(ileft, iright);
 157   if(vert_penetration < horiz_penetration) {
 158     if(itop < ibottom) {
 159       constraints->bottom = std::min(constraints->bottom, r2.get_top());
 160       constraints->hit.bottom = true;
 161       constraints->ground_movement += addl_ground_movement;
 162     } else {
 163       constraints->top = std::max(constraints->top, r2.get_bottom());
 164       constraints->hit.top = true;
 165     }
 166   } else {
 167     if(ileft < iright) {
 168       constraints->right = std::min(constraints->right, r2.get_left());
 169       constraints->hit.right = true;
 170     } else {
 171       constraints->left = std::max(constraints->left, r2.get_right());
 172       constraints->hit.left = true;
 173     }
 174   }
 175 }
 176
 177 }
 178
 179 /* EOF */