neo/cm/CollisionModel_trace.cpp

   1 /*
   2 ===========================================================================
   3
   4 Doom 3 GPL Source Code
   5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
   6
   7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
   8
   9 Doom 3 Source Code is free software: you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation, either version 3 of the License, or
  12 (at your option) any later version.
  13
  14 Doom 3 Source Code is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with Doom 3 Source Code.  If not, see <http://www.gnu.org/licenses/>.
  21
  22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code.  If not, please request a copy in writing from id Software at the address below.
  23
  24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  25
  26 ===========================================================================
  27 */
  28
  29 /*
  30 ===============================================================================
  31
  32         Trace model vs. polygonal model collision detection.
  33
  34 ===============================================================================
  35 */
  36
  37 #include "../idlib/precompiled.h"
  38 #pragma hdrstop
  39
  40 #include "CollisionModel_local.h"
  41
  42 /*
  43 ===============================================================================
  44
  45 Trace through the spatial subdivision
  46
  47 ===============================================================================
  48 */
  49
  50 /*
  51 ================
  52 idCollisionModelManagerLocal::TraceTrmThroughNode
  53 ================
  54 */
  55 void idCollisionModelManagerLocal::TraceTrmThroughNode( cm_traceWork_t *tw, cm_node_t *node ) {
  56         cm_polygonRef_t *pref;
  57         cm_brushRef_t *bref;
  58
  59         // position test
  60         if ( tw->positionTest ) {
  61                 // if already stuck in solid
  62                 if ( tw->trace.fraction == 0.0f ) {
  63                         return;
  64                 }
  65                 // test if any of the trm vertices is inside a brush
  66                 for ( bref = node->brushes; bref; bref = bref->next ) {
  67                         if ( idCollisionModelManagerLocal::TestTrmVertsInBrush( tw, bref->b ) ) {
  68                                 return;
  69                         }
  70                 }
  71                 // if just testing a point we're done
  72                 if ( tw->pointTrace ) {
  73                         return;
  74                 }
  75                 // test if the trm is stuck in any polygons
  76                 for ( pref = node->polygons; pref; pref = pref->next ) {
  77                         if ( idCollisionModelManagerLocal::TestTrmInPolygon( tw, pref->p ) ) {
  78                                 return;
  79                         }
  80                 }
  81         }
  82         else if ( tw->rotation ) {
  83                 // rotate through all polygons in this leaf
  84                 for ( pref = node->polygons; pref; pref = pref->next ) {
  85                         if ( idCollisionModelManagerLocal::RotateTrmThroughPolygon( tw, pref->p ) ) {
  86                                 return;
  87                         }
  88                 }
  89         }
  90         else {
  91                 // trace through all polygons in this leaf
  92                 for ( pref = node->polygons; pref; pref = pref->next ) {
  93                         if ( idCollisionModelManagerLocal::TranslateTrmThroughPolygon( tw, pref->p ) ) {
  94                                 return;
  95                         }
  96                 }
  97         }
  98 }
  99
 100 /*
 101 ================
 102 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r
 103 ================
 104 */
 105 //#define NO_SPATIAL_SUBDIVISION
 106
 107 void idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( cm_traceWork_t *tw, cm_node_t *node, float p1f, float p2f, idVec3 &p1, idVec3 &p2) {
 108         float           t1, t2, offset;
 109         float           frac, frac2;
 110         float           idist;
 111         idVec3          mid;
 112         int                     side;
 113         float           midf;
 114
 115         if ( !node ) {
 116                 return;
 117         }
 118
 119         if ( tw->quickExit ) {
 120                 return;         // stop immediately
 121         }
 122
 123         if ( tw->trace.fraction <= p1f ) {
 124                 return;         // already hit something nearer
 125         }
 126
 127         // if we need to test this node for collisions
 128         if ( node->polygons || (tw->positionTest && node->brushes) ) {
 129                 // trace through node with collision data
 130                 idCollisionModelManagerLocal::TraceTrmThroughNode( tw, node );
 131         }
 132         // if already stuck in solid
 133         if ( tw->positionTest && tw->trace.fraction == 0.0f ) {
 134                 return;
 135         }
 136         // if this is a leaf node
 137         if ( node->planeType == -1 ) {
 138                 return;
 139         }
 140 #ifdef NO_SPATIAL_SUBDIVISION
 141         idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[0], p1f, p2f, p1, p2 );
 142         idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[1], p1f, p2f, p1, p2 );
 143         return;
 144 #endif
 145         // distance from plane for trace start and end
 146         t1 = p1[node->planeType] - node->planeDist;
 147         t2 = p2[node->planeType] - node->planeDist;
 148         // adjust the plane distance appropriately for mins/maxs
 149         offset = tw->extents[node->planeType];
 150         // see which sides we need to consider
 151         if ( t1 >= offset && t2 >= offset ) {
 152                 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[0], p1f, p2f, p1, p2 );
 153                 return;
 154         }
 155
 156         if ( t1 < -offset && t2 < -offset ) {
 157                 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[1], p1f, p2f, p1, p2 );
 158                 return;
 159         }
 160
 161         if ( t1 < t2 ) {
 162                 idist = 1.0f / (t1-t2);
 163                 side = 1;
 164                 frac2 = (t1 + offset) * idist;
 165                 frac = (t1 - offset) * idist;
 166         } else if (t1 > t2) {
 167                 idist = 1.0f / (t1-t2);
 168                 side = 0;
 169                 frac2 = (t1 - offset) * idist;
 170                 frac = (t1 + offset) * idist;
 171         } else {
 172                 side = 0;
 173                 frac = 1.0f;
 174                 frac2 = 0.0f;
 175         }
 176
 177         // move up to the node
 178         if ( frac < 0.0f ) {
 179                 frac = 0.0f;
 180         }
 181         else if ( frac > 1.0f ) {
 182                 frac = 1.0f;
 183         }
 184
 185         midf = p1f + (p2f - p1f)*frac;
 186
 187         mid[0] = p1[0] + frac*(p2[0] - p1[0]);
 188         mid[1] = p1[1] + frac*(p2[1] - p1[1]);
 189         mid[2] = p1[2] + frac*(p2[2] - p1[2]);
 190
 191         idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[side], p1f, midf, p1, mid );
 192
 193
 194         // go past the node
 195         if ( frac2 < 0.0f ) {
 196                 frac2 = 0.0f;
 197         }
 198         else if ( frac2 > 1.0f ) {
 199                 frac2 = 1.0f;
 200         }
 201
 202         midf = p1f + (p2f - p1f)*frac2;
 203
 204         mid[0] = p1[0] + frac2*(p2[0] - p1[0]);
 205         mid[1] = p1[1] + frac2*(p2[1] - p1[1]);
 206         mid[2] = p1[2] + frac2*(p2[2] - p1[2]);
 207
 208         idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, node->children[side^1], midf, p2f, mid, p2 );
 209 }
 210
 211 /*
 212 ================
 213 idCollisionModelManagerLocal::TraceThroughModel
 214 ================
 215 */
 216 void idCollisionModelManagerLocal::TraceThroughModel( cm_traceWork_t *tw ) {
 217         float d;
 218         int i, numSteps;
 219         idVec3 start, end;
 220         idRotation rot;
 221
 222         if ( !tw->rotation ) {
 223                 // trace through spatial subdivision and then through leafs
 224                 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, tw->model->node, 0, 1, tw->start, tw->end );
 225         }
 226         else {
 227                 // approximate the rotation with a series of straight line movements
 228                 // total length covered along circle
 229                 d = tw->radius * DEG2RAD( tw->angle );
 230                 // if more than one step
 231                 if ( d > CIRCLE_APPROXIMATION_LENGTH ) {
 232                         // number of steps for the approximation
 233                         numSteps = (int) (CIRCLE_APPROXIMATION_LENGTH / d);
 234                         // start of approximation
 235                         start = tw->start;
 236                         // trace circle approximation steps through the BSP tree
 237                         for ( i = 0; i < numSteps; i++ ) {
 238                                 // calculate next point on approximated circle
 239                                 rot.Set( tw->origin, tw->axis, tw->angle * ((float) (i+1) / numSteps) );
 240                                 end = start * rot;
 241                                 // trace through spatial subdivision and then through leafs
 242                                 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, tw->model->node, 0, 1, start, end );
 243                                 // no need to continue if something was hit already
 244                                 if ( tw->trace.fraction < 1.0f ) {
 245                                         return;
 246                                 }
 247                                 start = end;
 248                         }
 249                 }
 250                 else {
 251                         start = tw->start;
 252                 }
 253                 // last step of the approximation
 254                 idCollisionModelManagerLocal::TraceThroughAxialBSPTree_r( tw, tw->model->node, 0, 1, start, tw->end );
 255         }
 256 }