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
  23 namespace collision {
  24
  25 bool intersects(const Rect& r1, const Rect& r2)
  26 {
  27   if(r1.p2.x < r2.p1.x || r1.p1.x > r2.p2.x)
  28     return false;
  29   if(r1.p2.y < r2.p1.y || r1.p1.y > r2.p2.y)
  30     return false;
  31
  32   return true;
  33 }
  34
  35 //---------------------------------------------------------------------------
  36
  37 namespace {
  38 inline void makePlane(const Vector& p1, const Vector& p2, Vector& n, float& c)
  39 {
  40   n = Vector(p2.y-p1.y, p1.x-p2.x);
  41   c = -(p2 * n);
  42   float nval = n.norm();
  43   n /= nval;
  44   c /= nval;
  45 }
  46
  47 }
  48
  49 bool rectangle_aatriangle(Constraints* constraints, const Rect& rect,
  50                           const AATriangle& triangle, const Vector& addl_ground_movement)
  51 {
  52   if(!intersects(rect, (const Rect&) triangle))
  53     return false;
  54
  55   Vector normal;
  56   float c;
  57   Vector p1;
  58   Rect area;
  59   switch(triangle.dir & AATriangle::DEFORM_MASK) {
  60     case 0:
  61       area.p1 = triangle.p1;
  62       area.p2 = triangle.p2;
  63       break;
  64     case AATriangle::DEFORM1:
  65       area.p1 = Vector(triangle.p1.x, triangle.p1.y + triangle.get_height()/2);
  66       area.p2 = triangle.p2;
  67       break;
  68     case AATriangle::DEFORM2:
  69       area.p1 = triangle.p1;
  70       area.p2 = Vector(triangle.p2.x, triangle.p1.y + triangle.get_height()/2);
  71       break;
  72     case AATriangle::DEFORM3:
  73       area.p1 = triangle.p1;
  74       area.p2 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p2.y);
  75       break;
  76     case AATriangle::DEFORM4:
  77       area.p1 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p1.y);
  78       area.p2 = triangle.p2;
  79       break;
  80     default:
  81       assert(false);
  82   }
  83
  84   switch(triangle.dir & AATriangle::DIRECTION_MASK) {
  85     case AATriangle::SOUTHWEST:
  86       p1 = Vector(rect.p1.x, rect.p2.y);
  87       makePlane(area.p1, area.p2, normal, c);
  88       break;
  89     case AATriangle::NORTHEAST:
  90       p1 = Vector(rect.p2.x, rect.p1.y);
  91       makePlane(area.p2, area.p1, normal, c);
  92       break;
  93     case AATriangle::SOUTHEAST:
  94       p1 = rect.p2;
  95       makePlane(Vector(area.p1.x, area.p2.y),
  96                 Vector(area.p2.x, area.p1.y), normal, c);
  97       break;
  98     case AATriangle::NORTHWEST:
  99       p1 = rect.p1;
 100       makePlane(Vector(area.p2.x, area.p1.y),
 101                 Vector(area.p1.x, area.p2.y), normal, c);
 102       break;
 103     default:
 104       assert(false);
 105   }
 106
 107   float n_p1 = -(normal * p1);
 108   float depth = n_p1 - c;
 109   if(depth < 0)
 110     return false;
 111
 112 #if 0
 113   std::cout << "R: " << rect << " Tri: " << triangle << "\n";
 114   std::cout << "Norm: " << normal << " Depth: " << depth << "\n";
 115 #endif
 116
 117   Vector outvec = normal * (depth + 0.2f);
 118
 119   const float RDELTA = 3;
 120   if(p1.x < area.p1.x - RDELTA || p1.x > area.p2.x + RDELTA
 121      || p1.y < area.p1.y - RDELTA || p1.y > area.p2.y + RDELTA) {
 122     set_rectangle_rectangle_constraints(constraints, rect, area);
 123     constraints->hit.left = false;
 124     constraints->hit.right = false;
 125   } else {
 126     if(outvec.x < 0) {
 127       constraints->right = rect.get_right() + outvec.x;
 128     } else {
 129       constraints->left = rect.get_left() + outvec.x;
 130     }
 131
 132     if(outvec.y < 0) {
 133       constraints->bottom = rect.get_bottom() + outvec.y;
 134       constraints->hit.bottom = true;
 135       constraints->ground_movement += addl_ground_movement;
 136     } else {
 137       constraints->top = rect.get_top() + outvec.y;
 138       constraints->hit.top = true;
 139     }
 140     constraints->hit.slope_normal = normal;
 141   }
 142
 143   return true;
 144 }
 145
 146 void set_rectangle_rectangle_constraints(Constraints* constraints,
 147                                          const Rect& r1, const Rect& r2, const Vector& addl_ground_movement)
 148 {
 149   float itop = r1.get_bottom() - r2.get_top();
 150   float ibottom = r2.get_bottom() - r1.get_top();
 151   float ileft = r1.get_right() - r2.get_left();
 152   float iright = r2.get_right() - r1.get_left();
 153
 154   float vert_penetration = std::min(itop, ibottom);
 155   float horiz_penetration = std::min(ileft, iright);
 156   if(vert_penetration < horiz_penetration) {
 157     if(itop < ibottom) {
 158       constraints->bottom = std::min(constraints->bottom, r2.get_top());
 159       constraints->hit.bottom = true;
 160       constraints->ground_movement += addl_ground_movement;
 161     } else {
 162       constraints->top = std::max(constraints->top, r2.get_bottom());
 163       constraints->hit.top = true;
 164     }
 165   } else {
 166     if(ileft < iright) {
 167       constraints->right = std::min(constraints->right, r2.get_left());
 168       constraints->hit.right = true;
 169     } else {
 170       constraints->left = std::max(constraints->left, r2.get_right());
 171       constraints->hit.left = true;
 172     }
 173   }
 174 }
 175
 176 }
 177
 178 /* EOF */