src/collision.cpp

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