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
  34 static const float DELTA = .0001;
  35
  36 bool
  37 Collision::intersects(const Rect& r1, const Rect& r2)
  38 {
  39   if(r1.p2.x < r2.p1.x || r1.p1.x > r2.p2.x)
  40     return false;
  41   if(r1.p2.y < r2.p1.y || r1.p1.y > r2.p2.y)
  42     return false;
  43
  44   return true;
  45 }
  46
  47 bool
  48 Collision::rectangle_rectangle(CollisionHit& hit, const Rect& r1,
  49     const Vector& movement, const Rect& r2)
  50 {
  51   if(r1.p2.x < r2.p1.x || r1.p1.x > r2.p2.x)
  52     return false;
  53   if(r1.p2.y < r2.p1.y || r1.p1.y > r2.p2.y)
  54     return false;
  55
  56   if(movement.x > DELTA) {
  57     hit.depth = r1.p2.x - r2.p1.x;
  58     hit.time = hit.depth / movement.x;
  59     hit.normal.x = -1;
  60     hit.normal.y = 0;
  61   } else if(movement.x < -DELTA) {
  62     hit.depth = r2.p2.x - r1.p1.x;
  63     hit.time = hit.depth / -movement.x;
  64     hit.normal.x = 1;
  65     hit.normal.y = 0;
  66   } else {
  67     if(movement.y > -DELTA && movement.y < DELTA) {
  68       hit.time = 0;
  69       hit.depth = 0;
  70       hit.normal.x = 1;
  71       hit.normal.y = 0;
  72       return true;
  73     }
  74     hit.time = FLT_MAX;
  75   }
  76
  77   if(movement.y > DELTA) {
  78     float ydepth = r1.p2.y - r2.p1.y;
  79     float yt = ydepth / movement.y;
  80     if(yt < hit.time) {
  81       hit.depth = ydepth;
  82       hit.time = yt;
  83       hit.normal.x = 0;
  84       hit.normal.y = -1;
  85     }
  86   } else if(movement.y < -DELTA) {
  87     float ydepth = r2.p2.y - r1.p1.y;
  88     float yt = ydepth / -movement.y;
  89     if(yt < hit.time) {
  90       hit.depth = ydepth;
  91       hit.time = yt;
  92       hit.normal.x = 0;
  93       hit.normal.y = 1;
  94     }
  95   }
  96
  97   return true;
  98 }
  99
 100 //---------------------------------------------------------------------------
 101
 102 static void makePlane(const Vector& p1, const Vector& p2, Vector& n, float& c)
 103 {
 104   n = Vector(p2.y-p1.y, p1.x-p2.x);
 105   c = -(p2 * n);
 106   float nval = n.norm();
 107   n /= nval;
 108   c /= nval;
 109 }
 110
 111 bool
 112 Collision::rectangle_aatriangle(CollisionHit& hit, const Rect& rect,
 113     const Vector& movement, const AATriangle& triangle)
 114 {
 115   if(!rectangle_rectangle(hit, rect, movement, (const Rect&) triangle))
 116     return false;
 117
 118   Vector normal;
 119   float c;
 120   Vector p1;
 121   Vector tp1, tp2;
 122   switch(triangle.dir & AATriangle::DEFORM_MASK) {
 123     case 0:
 124       tp1 = triangle.p1;
 125       tp2 = triangle.p2;
 126       break;
 127     case AATriangle::DEFORM1:
 128       tp1 = Vector(triangle.p1.x, triangle.p1.y + triangle.get_height()/2);
 129       tp2 = triangle.p2;
 130       break;
 131     case AATriangle::DEFORM2:
 132       tp1 = triangle.p1;
 133       tp2 = Vector(triangle.p2.x, triangle.p1.y + triangle.get_height()/2);
 134       break;
 135     case AATriangle::DEFORM3:
 136       tp1 = triangle.p1;
 137       tp2 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p2.y);
 138       break;
 139     case AATriangle::DEFORM4:
 140       tp1 = Vector(triangle.p1.x + triangle.get_width()/2, triangle.p1.y);
 141       tp2 = triangle.p2;
 142       break;
 143     default:
 144       assert(false);
 145   }
 146
 147   switch(triangle.dir & AATriangle::DIRECTION_MASK) {
 148     case AATriangle::SOUTHWEST:
 149       p1 = Vector(rect.p1.x, rect.p2.y);
 150       makePlane(tp1, tp2, normal, c);
 151       break;
 152     case AATriangle::NORTHEAST:
 153       p1 = Vector(rect.p2.x, rect.p1.y);
 154       makePlane(tp2, tp1, normal, c);
 155       break;
 156     case AATriangle::SOUTHEAST:
 157       p1 = rect.p2;
 158       makePlane(Vector(tp1.x, tp2.y),
 159           Vector(tp2.x, tp1.y), normal, c);
 160       break;
 161     case AATriangle::NORTHWEST:
 162       p1 = rect.p1;
 163       makePlane(Vector(tp2.x, tp1.y),
 164           Vector(tp1.x, tp2.y), normal, c);
 165       break;
 166     default:
 167       assert(false);
 168   }
 169
 170   float n_p1 = -(normal * p1);
 171   float depth = n_p1 - c;
 172   if(depth < 0)
 173     return false;
 174   float time = depth / -(normal * movement);
 175   if(time < hit.time) {
 176     hit.depth = depth;
 177     hit.time = time;
 178     hit.normal = normal;
 179   }
 180
 181   return true;
 182 }
 183