terrCollision.cpp

Public Functions

calcInterceptNone(F32 , F32 , F32 )

calcInterceptV(F32 vStart, F32 invDeltaV, F32 intercept)

clrbuf(U32 * p, U32 s)

isOnPlane(Point3F & p, PlaneF & plane)

swap(U32 *& a, U32 *& b)

   1
   2//-----------------------------------------------------------------------------
   3// Copyright (c) 2012 GarageGames, LLC
   4//
   5// Permission is hereby granted, free of charge, to any person obtaining a copy
   6// of this software and associated documentation files (the "Software"), to
   7// deal in the Software without restriction, including without limitation the
   8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   9// sell copies of the Software, and to permit persons to whom the Software is
  10// furnished to do so, subject to the following conditions:
  11//
  12// The above copyright notice and this permission notice shall be included in
  13// all copies or substantial portions of the Software.
  14//
  15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  21// IN THE SOFTWARE.
  22//-----------------------------------------------------------------------------
  23
  24#include "platform/platform.h"
  25#include "terrain/terrCollision.h"
  26
  27#include "terrain/terrData.h"
  28#include "collision/abstractPolyList.h"
  29#include "collision/collision.h"
  30
  31
  32const F32 TerrainThickness = 0.5f;
  33static const U32 MaxExtent = 256;
  34#define MAX_FLOAT 1e20f
  35
  36
  37//----------------------------------------------------------------------------
  38
  39Convex sTerrainConvexList;
  40
  41// Number of vertices followed by point index
  42S32 sVertexList[5][5] = {
  43   { 3, 1,2,3 },  // 135 B
  44   { 3, 0,1,3 },  // 135 A
  45   { 3, 0,2,3 },  // 45 B
  46   { 3, 0,1,2 },  // 45 A
  47   { 4, 0,1,2,3 } // Convex square
  48};
  49
  50// Number of edges followed by edge index pairs
  51S32 sEdgeList45[16][11] = {
  52   { 0 },                  //
  53   { 0 },
  54   { 0 },
  55   { 1, 0,1 },             // 0-1
  56   { 0 },
  57   { 1, 0,1 },             // 0-2
  58   { 1, 0,1 },             // 1-2
  59   { 3, 0,1,1,2,2,0 },     // 0-1,1-2,2-0
  60   { 0 },
  61   { 0,},                  //
  62   { 0 },
  63   { 1, 0,1 },             // 0-1,
  64   { 0, },                 //
  65   { 1, 0,1 },             // 0-2,
  66   { 1, 0,1 },             // 1-2
  67   { 3, 0,1,1,2,0,2 },
  68};
  69
  70S32 sEdgeList135[16][11] = {
  71   { 0 },
  72   { 0 },
  73   { 0 },
  74   { 1, 0,1 },             // 0-1
  75   { 0 },
  76   { 0 },
  77   { 1, 0,1 },             // 1-2
  78   { 2, 0,1,1,2 },         // 0-1,1-2
  79   { 0 },
  80   { 0, },                 //
  81   { 1, 0,1 },             // 1-3
  82   { 2, 0,1,1,2 },         // 0-1,1-3,
  83   { 0 },                  //
  84   { 0 },                  //
  85   { 2, 0,1,2,0 },         // 1-2,3-1
  86   { 3, 0,1,1,2,1,3 },
  87};
  88
  89// On split squares, the FaceA diagnal is also removed
  90S32 sEdgeList45A[16][11] = {
  91   { 0 },                  //
  92   { 0 },
  93   { 0 },
  94   { 1, 0,1 },             // 0-1
  95   { 0 },
  96   { 0 },                  //
  97   { 1, 0,1 },             // 1-2
  98   { 2, 0,1,1,2 },         // 0-1,1-2
  99   { 0 },
 100   { 0,},                  //
 101   { 0 },
 102   { 1, 0,1 },             // 0-1
 103   { 0, },                 //
 104   { 0, 0,1 },             //
 105   { 1, 0,1 },             // 1-2
 106   { 3, 0,1,1,2 },
 107};
 108
 109S32 sEdgeList135A[16][11] = {
 110   { 0 },
 111   { 0 },
 112   { 0 },
 113   { 1, 0,1 },             // 0-1
 114   { 0 },
 115   { 0 },
 116   { 1, 0,1 },             // 1-2
 117   { 2, 0,1,1,2 },         // 0-1,1-2
 118   { 0 },
 119   { 0 },                  //
 120   { 0 },                  //
 121   { 1, 0,1 },             // 0-1
 122   { 0 },                  //
 123   { 0 },                  //
 124   { 1, 0,1 },             // 1-2
 125   { 3, 0,1,1,2 },
 126};
 127
 128
 129// Number of faces followed by normal index and vertices
 130S32 sFaceList45[16][9] = {
 131   { 0 },
 132   { 0 },
 133   { 0 },
 134   { 0 },
 135   { 0 },
 136   { 0 },
 137   { 0 },
 138   { 1, 0,0,1,2 },
 139   { 0 },
 140   { 0 },
 141   { 0 },
 142   { 0 },
 143   { 0 },
 144   { 1, 1,0,1,2 },
 145   { 0 },
 146   { 2, 0,0,1,2, 1,0,2,3 },
 147};
 148
 149S32 sFaceList135[16][9] = {
 150   { 0 },
 151   { 0 },
 152   { 0 },
 153   { 0 },
 154   { 0 },
 155   { 0 },
 156   { 0 },
 157   { 0 },
 158   { 0 },
 159   { 0 },
 160   { 0 },
 161   { 1, 0,0,1,2 },
 162   { 0 },
 163   { 0 },
 164   { 1, 1,0,1,2 },
 165   { 2, 0,0,1,3, 1,1,2,3 },
 166};
 167
 168
 169TerrainConvex::TerrainConvex() 
 170{
 171   mType = TerrainConvexType; 
 172}
 173
 174TerrainConvex::TerrainConvex( const TerrainConvex &cv ) 
 175{
 176   mType = TerrainConvexType;
 177
 178   // Only a partial copy...
 179   mObject = cv.mObject;
 180   split45 = cv.split45;
 181   squareId = cv.squareId;
 182   material = cv.material;
 183   point[0] = cv.point[0];
 184   point[1] = cv.point[1];
 185   point[2] = cv.point[2];
 186   point[3] = cv.point[3];
 187   normal[0] = cv.normal[0];
 188   normal[1] = cv.normal[1];
 189   box = cv.box;
 190}
 191
 192Box3F TerrainConvex::getBoundingBox() const
 193{
 194   return box;
 195}
 196
 197Box3F TerrainConvex::getBoundingBox(const MatrixF&, const Point3F& ) const
 198{
 199   // Function should not be called....
 200   return box;
 201}
 202
 203Point3F TerrainConvex::support(const VectorF& v) const
 204{
 205   S32 *vp;
 206   if (halfA)
 207      vp = square ? sVertexList[(split45 << 1) | 1]: sVertexList[4];
 208   else
 209      vp = square ? sVertexList[(split45 << 1)]    : sVertexList[4];
 210
 211   S32 *ve = vp + vp[0] + 1;
 212   const Point3F *bp = &point[vp[1]];
 213   F32 bd = mDot(*bp,v);
 214   for (vp += 2; vp < ve; vp++) {
 215      const Point3F* cp = &point[*vp];
 216      F32 dd = mDot(*cp,v);
 217      if (dd > bd) {
 218         bd = dd;
 219         bp = cp;
 220      }
 221   }
 222   return *bp;
 223}
 224
 225inline bool isOnPlane(Point3F& p,PlaneF& plane)
 226{
 227   F32 dist = mDot(plane,p) + plane.d;
 228   return dist < 0.1 && dist > -0.1;
 229}
 230
 231void TerrainConvex::getFeatures(const MatrixF& mat,const VectorF& n, ConvexFeature* cf)
 232{
 233   U32 i;
 234   cf->material = 0;
 235   cf->object = mObject;
 236
 237   // Plane is normal n + support point
 238   PlaneF plane;
 239   plane.set(support(n),n);
 240   S32 vertexCount = cf->mVertexList.size();
 241
 242   // Emit vertices on the plane
 243   S32* vertexListPointer;
 244   if (halfA)
 245      vertexListPointer = square ? sVertexList[(split45 << 1) | 1]: sVertexList[4];
 246   else
 247      vertexListPointer = square ? sVertexList[(split45 << 1)]    : sVertexList[4];
 248
 249   S32 pm = 0;
 250   S32 numVerts = *vertexListPointer;
 251   vertexListPointer += 1;
 252   for (i = 0; i < numVerts; i++)
 253   {
 254      Point3F& cp = point[vertexListPointer[i]];
 255      cf->mVertexList.increment();
 256      mat.mulP(cp,&cf->mVertexList.last());
 257      pm |= 1 << vertexListPointer[i];
 258   }
 259
 260   // Emit Edges
 261   S32* ep = (square && halfA)?
 262      (split45 ? sEdgeList45A[pm]: sEdgeList135A[pm]):
 263      (split45 ? sEdgeList45[pm]: sEdgeList135[pm]);
 264
 265   S32 numEdges = *ep;
 266   S32 edgeListStart = cf->mEdgeList.size();
 267   cf->mEdgeList.increment(numEdges);
 268   ep += 1;
 269   for (i = 0; i < numEdges; i++)
 270   {
 271      cf->mEdgeList[edgeListStart + i].vertex[0] = vertexCount + ep[i * 2 + 0];
 272      cf->mEdgeList[edgeListStart + i].vertex[1] = vertexCount + ep[i * 2 + 1];
 273   }
 274
 275   // Emit faces
 276   S32* fp = split45 ? sFaceList45[pm]: sFaceList135[pm];
 277   S32 numFaces = *fp;
 278   fp += 1;
 279   S32 faceListStart = cf->mFaceList.size();
 280   cf->mFaceList.increment(numFaces);
 281   for (i = 0; i < numFaces; i++)
 282   {
 283      ConvexFeature::Face& face = cf->mFaceList[faceListStart + i];
 284      face.normal = normal[fp[i * 4 + 0]];
 285      face.vertex[0] = vertexCount + fp[i * 4 + 1];
 286      face.vertex[1] = vertexCount + fp[i * 4 + 2];
 287      face.vertex[2] = vertexCount + fp[i * 4 + 3];
 288   }
 289}
 290
 291
 292void TerrainConvex::getPolyList(AbstractPolyList* list)
 293{
 294   list->setTransform(&mObject->getTransform(), mObject->getScale());
 295   list->setObject(mObject);
 296
 297   // Emit vertices
 298   U32 array[4];
 299   U32 curr = 0;
 300
 301   S32 numVerts;
 302   S32* vertsStart;
 303   if (halfA)
 304   {
 305      numVerts   = square ?  sVertexList[(split45 << 1) | 1][0] :  sVertexList[4][0];
 306      vertsStart = square ? &sVertexList[(split45 << 1) | 1][1] : &sVertexList[4][1];
 307   }
 308   else
 309   {
 310      numVerts   = square ?  sVertexList[(split45 << 1)][0] :  sVertexList[4][0];
 311      vertsStart = square ? &sVertexList[(split45 << 1)][1] : &sVertexList[4][1];
 312   }
 313
 314   S32 pointMask = 0;
 315   for (U32 i = 0; i < numVerts; i++) {
 316      const Point3F& cp = point[vertsStart[i]];
 317      array[curr++] = list->addPoint(cp);
 318      pointMask |= (1 << vertsStart[i]);
 319   }
 320
 321   S32  numFaces  = split45 ?  sFaceList45[pointMask][0] :  sFaceList135[pointMask][0];
 322   S32* faceStart = split45 ? &sFaceList45[pointMask][1] : &sFaceList135[pointMask][1];
 323   for (U32 j = 0; j < numFaces; j++) {
 324      S32 plane = faceStart[0];
 325      S32 v0    = faceStart[1];
 326      S32 v1    = faceStart[2];
 327      S32 v2    = faceStart[3];
 328
 329      list->begin(0, plane);
 330      list->vertex(array[v0]);
 331      list->vertex(array[v1]);
 332      list->vertex(array[v2]);
 333      list->plane(array[v0], array[v1], array[v2]);
 334      list->end();
 335
 336      faceStart += 4;
 337   }
 338}
 339
 340
 341//----------------------------------------------------------------------------
 342
 343void TerrainBlock::buildConvex(const Box3F& box,Convex* convex)
 344{
 345   PROFILE_SCOPE( TerrainBlock_buildConvex );
 346   
 347   sTerrainConvexList.collectGarbage();
 348
 349   // First check to see if the query misses the 
 350   // terrain elevation range.
 351   const Point3F &terrainPos = getPosition();
 352   if (  box.maxExtents.z - terrainPos.z < -TerrainThickness || 
 353         box.minExtents.z - terrainPos.z > fixedToFloat( mFile->getMaxHeight() ) )
 354      return;
 355
 356   // Transform the bounding sphere into the object's coord space.  Note that this
 357   // not really optimal.
 358   Box3F osBox = box;
 359   mWorldToObj.mul(osBox);
 360   AssertWarn(mObjScale == Point3F(1, 1, 1), "Error, handle the scale transform on the terrain");
 361
 362   S32 xStart = (S32)mFloor( osBox.minExtents.x / mSquareSize );
 363   S32 xEnd   = (S32)mCeil ( osBox.maxExtents.x / mSquareSize );
 364   S32 yStart = (S32)mFloor( osBox.minExtents.y / mSquareSize );
 365   S32 yEnd   = (S32)mCeil ( osBox.maxExtents.y / mSquareSize );
 366   S32 xExt = xEnd - xStart;
 367   if (xExt > MaxExtent)
 368      xExt = MaxExtent;
 369
 370   U16 heightMax = floatToFixed(osBox.maxExtents.z);
 371   U16 heightMin = (osBox.minExtents.z < 0)? 0: floatToFixed(osBox.minExtents.z);
 372
 373   const U32 BlockMask = mFile->mSize - 1;
 374
 375   for ( S32 y = yStart; y < yEnd; y++ ) 
 376   {
 377      S32 yi = y & BlockMask;
 378
 379      //
 380      for ( S32 x = xStart; x < xEnd; x++ ) 
 381      {
 382         S32 xi = x & BlockMask;
 383
 384         const TerrainSquare *sq = mFile->findSquare( 0, xi, yi );
 385
 386         if ( x != xi || y != yi )
 387            continue;
 388
 389         // holes only in the primary terrain block
 390         if (  ( ( sq->flags & TerrainSquare::Empty ) && x == xi && y == yi ) ||
 391               sq->minHeight > heightMax || 
 392               sq->maxHeight < heightMin )
 393            continue;
 394
 395         U32 sid = (x << 16) + (y & ((1 << 16) - 1));
 396         Convex *cc = 0;
 397
 398         // See if the square already exists as part of the working set.
 399         CollisionWorkingList& wl = convex->getWorkingList();
 400         for (CollisionWorkingList* itr = wl.wLink.mNext; itr != &wl; itr = itr->wLink.mNext)
 401            if (itr->mConvex->getType() == TerrainConvexType &&
 402                static_cast<TerrainConvex*>(itr->mConvex)->squareId == sid) {
 403               cc = itr->mConvex;
 404               break;
 405            }
 406
 407         if (cc)
 408            continue;
 409
 410         // Create a new convex.
 411         TerrainConvex* cp = new TerrainConvex;
 412         sTerrainConvexList.registerObject(cp);
 413         convex->addToWorkingList(cp);
 414         cp->halfA = true;
 415         cp->square = 0;
 416         cp->mObject = this;
 417         cp->squareId = sid;
 418         cp->material = mFile->getLayerIndex( xi, yi );
 419         cp->box.minExtents.set((F32)(x * mSquareSize), (F32)(y * mSquareSize), fixedToFloat( sq->minHeight ));
 420         cp->box.maxExtents.x = cp->box.minExtents.x + mSquareSize;
 421         cp->box.maxExtents.y = cp->box.minExtents.y + mSquareSize;
 422         cp->box.maxExtents.z = fixedToFloat( sq->maxHeight );
 423         mObjToWorld.mul(cp->box);
 424
 425         // Build points
 426         Point3F* pos = cp->point;
 427         for (S32 i = 0; i < 4 ; i++,pos++) {
 428            S32 dx = i >> 1;
 429            S32 dy = dx ^ (i & 1);
 430            pos->x = (F32)((x + dx) * mSquareSize);
 431            pos->y = (F32)((y + dy) * mSquareSize);
 432            pos->z = fixedToFloat( mFile->getHeight(xi + dx, yi + dy) );
 433         }
 434
 435         // Build normals, then split into two Convex objects if the
 436         // square is concave
 437         if ((cp->split45 = sq->flags & TerrainSquare::Split45) == true) {
 438            VectorF *vp = cp->point;
 439            mCross(vp[0] - vp[1],vp[2] - vp[1],&cp->normal[0]);
 440            cp->normal[0].normalize();
 441            mCross(vp[2] - vp[3],vp[0] - vp[3],&cp->normal[1]);
 442            cp->normal[1].normalize();
 443            if (mDot(vp[3] - vp[1],cp->normal[0]) > 0) {
 444               TerrainConvex* nc = new TerrainConvex(*cp);
 445               sTerrainConvexList.registerObject(nc);
 446               convex->addToWorkingList(nc);
 447               nc->halfA = false;
 448               nc->square = cp;
 449               cp->square = nc;
 450            }
 451         }
 452         else {
 453            VectorF *vp = cp->point;
 454            mCross(vp[3] - vp[0],vp[1] - vp[0],&cp->normal[0]);
 455            cp->normal[0].normalize();
 456            mCross(vp[1] - vp[2],vp[3] - vp[2],&cp->normal[1]);
 457            cp->normal[1].normalize();
 458            if (mDot(vp[2] - vp[0],cp->normal[0]) > 0) {
 459               TerrainConvex* nc = new TerrainConvex(*cp);
 460               sTerrainConvexList.registerObject(nc);
 461               convex->addToWorkingList(nc);
 462               nc->halfA = false;
 463               nc->square = cp;
 464               cp->square = nc;
 465            }
 466         }
 467      }
 468   }
 469}
 470
 471static inline void swap(U32*& a,U32*& b)
 472{
 473   U32* t = b;
 474   b = a;
 475   a = t;
 476}
 477
 478static void clrbuf(U32* p, U32 s)
 479{
 480   U32* e = p + s;
 481   while (p != e)
 482      *p++ = U32_MAX;
 483}
 484
 485bool TerrainBlock::buildPolyList(PolyListContext context, AbstractPolyList* polyList, const Box3F &box, const SphereF&)
 486{
 487   PROFILE_SCOPE( TerrainBlock_buildPolyList );
 488
 489   // First check to see if the query misses the 
 490   // terrain elevation range.
 491   const Point3F &terrainPos = getPosition();
 492   if (  box.maxExtents.z - terrainPos.z < -TerrainThickness || 
 493         box.minExtents.z - terrainPos.z > fixedToFloat( mFile->getMaxHeight() ) )
 494      return false;
 495
 496   // Transform the bounding sphere into the object's coord 
 497   // space.  Note that this is really optimal.
 498   Box3F osBox = box;
 499   mWorldToObj.mul(osBox);
 500   AssertWarn(mObjScale == Point3F::One, "Error, handle the scale transform on the terrain");
 501
 502   // Setup collision state data
 503   polyList->setTransform(&getTransform(), getScale());
 504   polyList->setObject(this);
 505
 506   S32 xStart = (S32)mFloor( osBox.minExtents.x / mSquareSize );
 507   S32 xEnd   = (S32)mCeil ( osBox.maxExtents.x / mSquareSize );
 508   S32 yStart = (S32)mFloor( osBox.minExtents.y / mSquareSize );
 509   S32 yEnd   = (S32)mCeil ( osBox.maxExtents.y / mSquareSize );
 510   if ( xStart < 0 )
 511      xStart = 0;
 512   S32 xExt = xEnd - xStart;
 513   if ( xExt > MaxExtent )
 514      xExt = MaxExtent;
 515   xEnd = xStart + xExt;
 516
 517   U32 heightMax = floatToFixed(osBox.maxExtents.z);
 518   U32 heightMin = (osBox.minExtents.z < 0.0f)? 0.0f: floatToFixed(osBox.minExtents.z);
 519
 520   // Index of shared points
 521   U32 bp[(MaxExtent + 1) * 2],*vb[2];
 522   vb[0] = &bp[0];
 523   vb[1] = &bp[xExt + 1];
 524   clrbuf(vb[1],xExt + 1);
 525
 526   const U32 BlockMask = mFile->mSize - 1;
 527
 528   bool emitted = false;
 529   for (S32 y = yStart; y < yEnd; y++) 
 530   {
 531      S32 yi = y & BlockMask;
 532
 533      swap(vb[0],vb[1]);
 534      clrbuf(vb[1],xExt + 1);
 535
 536      F32 wy1 = y * mSquareSize, wy2 = (y + 1) * mSquareSize;
 537      if(context == PLC_Navigation &&
 538         ((wy1 > osBox.maxExtents.y && wy2 > osBox.maxExtents.y) ||
 539          (wy1 < osBox.minExtents.y && wy2 < osBox.minExtents.y)))
 540         continue;
 541
 542      //
 543      for (S32 x = xStart; x < xEnd; x++) 
 544      {
 545         S32 xi = x & BlockMask;
 546         const TerrainSquare *sq = mFile->findSquare( 0, xi, yi );
 547
 548         F32 wx1 = x * mSquareSize, wx2 = (x + 1) * mSquareSize;
 549         if(context == PLC_Navigation &&
 550            ((wx1 > osBox.maxExtents.x && wx2 > osBox.maxExtents.x) ||
 551             (wx1 < osBox.minExtents.x && wx2 < osBox.minExtents.x)))
 552            continue;
 553
 554         if ( x != xi || y != yi )
 555            continue;
 556
 557         // holes only in the primary terrain block
 558         if (  ( ( sq->flags & TerrainSquare::Empty ) && x == xi && y == yi ) || 
 559               sq->minHeight > heightMax || 
 560               sq->maxHeight < heightMin )
 561            continue;
 562
 563         emitted = true;
 564
 565         // Add the missing points
 566         U32 vi[5];
 567         for (int i = 0; i < 4 ; i++) 
 568         {
 569            S32 dx = i >> 1;
 570            S32 dy = dx ^ (i & 1);
 571            U32* vp = &vb[dy][x - xStart + dx];
 572            if (*vp == U32_MAX) 
 573            {
 574               Point3F pos;
 575               pos.x = (F32)((x + dx) * mSquareSize);
 576               pos.y = (F32)((y + dy) * mSquareSize);
 577               pos.z = fixedToFloat( mFile->getHeight(xi + dx, yi + dy) );
 578               *vp = polyList->addPoint(pos);
 579            }
 580            vi[i] = *vp;
 581         }
 582
 583         U32* vp = &vi[0];
 584         if ( !( sq->flags & TerrainSquare::Split45 ) )
 585            vi[4] = vi[0], vp++;
 586
 587         BaseMatInstance *material = NULL; //getMaterialInst( xi, yi );
 588         U32 surfaceKey = ((xi << 16) + yi) << 1;
 589         polyList->begin(material,surfaceKey);
 590         polyList->vertex(vp[0]);
 591         polyList->vertex(vp[1]);
 592         polyList->vertex(vp[2]);
 593         polyList->plane(vp[0],vp[1],vp[2]);
 594         polyList->end();
 595         polyList->begin(material,surfaceKey + 1);
 596         polyList->vertex(vp[0]);
 597         polyList->vertex(vp[2]);
 598         polyList->vertex(vp[3]);
 599         polyList->plane(vp[0],vp[2],vp[3]);
 600         polyList->end();
 601      }
 602   }
 603
 604   return emitted;
 605}
 606
 607//----------------------------------------------------------------------------
 608
 609static F32 calcInterceptV(F32 vStart, F32 invDeltaV, F32 intercept)
 610{
 611   return (intercept - vStart) * invDeltaV;
 612}
 613
 614static F32 calcInterceptNone(F32, F32, F32)
 615{
 616   return MAX_FLOAT;
 617}
 618
 619static F32 (*calcInterceptX)(F32, F32, F32);
 620static F32 (*calcInterceptY)(F32, F32, F32);
 621
 622static U32 lineCount;
 623static Point3F lineStart, lineEnd;
 624
 625bool TerrainBlock::castRay(const Point3F &start, const Point3F &end, RayInfo *info)
 626{
 627   PROFILE_SCOPE( TerrainBlock_castRay );
 628
 629   if ( !castRayI(start, end, info, false) )
 630      return false;
 631      
 632   // Set intersection point.
 633   info->setContactPoint( start, end );
 634   getTransform().mulP( info->point );    // transform to world coordinates for getGridPos
 635
 636   // Set material at contact point.
 637   Point2I gridPos = getGridPos( info->point );
 638   U8 layer = mFile->getLayerIndex( gridPos.x, gridPos.y );
 639   info->material = mFile->getMaterialMapping( layer );
 640
 641   return true;
 642}
 643
 644bool TerrainBlock::castRayI(const Point3F &start, const Point3F &end, RayInfo *info, bool collideEmpty)
 645{
 646   lineCount = 0;
 647   lineStart = start;
 648   lineEnd = end;
 649
 650   info->object = this;
 651
 652   if(start.x == end.x && start.y == end.y)
 653   {
 654      if (end.z == start.z)
 655         return false;
 656
 657      F32 height;
 658      if(!getNormalAndHeight(Point2F(start.x, start.y), &info->normal, &height, true))
 659         return false;
 660
 661      F32 t = (height - start.z) / (end.z - start.z);
 662      if(t < 0 || t > 1)
 663         return false;
 664      info->t = t;
 665
 666      return true;
 667   }
 668
 669   F32 invBlockWorldSize = 1 / getWorldBlockSize();
 670
 671   Point3F pStart(start.x * invBlockWorldSize, start.y * invBlockWorldSize, start.z);
 672   Point3F pEnd(end.x * invBlockWorldSize, end.y * invBlockWorldSize, end.z);
 673
 674   S32 blockX = (S32)mFloor(pStart.x);
 675   S32 blockY = (S32)mFloor(pStart.y);
 676
 677   S32 dx, dy;
 678
 679   F32 invDeltaX;
 680   if(pEnd.x == pStart.x)
 681   {
 682      calcInterceptX = calcInterceptNone;
 683      invDeltaX = 0;
 684      dx = 0;
 685   }
 686   else
 687   {
 688      invDeltaX = 1 / (pEnd.x - pStart.x);
 689      calcInterceptX = calcInterceptV;
 690      if(pEnd.x < pStart.x)
 691         dx = -1;
 692      else
 693         dx = 1;
 694   }
 695
 696   F32 invDeltaY;
 697   if(pEnd.y == pStart.y)
 698   {
 699      calcInterceptY = calcInterceptNone;
 700      invDeltaY = 0;
 701      dy = 0;
 702   }
 703   else
 704   {
 705      invDeltaY = 1 / (pEnd.y - pStart.y);
 706      calcInterceptY = calcInterceptV;
 707      if(pEnd.y < pStart.y)
 708         dy = -1;
 709      else
 710         dy = 1;
 711   }
 712
 713   const U32 BlockSquareWidth = mFile->mSize;
 714   const U32 GridLevels = mFile->mGridLevels;
 715
 716   F32 startT = 0;
 717   for(;;)
 718   {
 719      F32 nextXInt = calcInterceptX(pStart.x, invDeltaX, (F32)(blockX + (dx == 1)));
 720      F32 nextYInt = calcInterceptY(pStart.y, invDeltaY, (F32)(blockY + (dy == 1)));
 721
 722      F32 intersectT = 1;
 723
 724      if(nextXInt < intersectT)
 725         intersectT = nextXInt;
 726      if(nextYInt < intersectT)
 727         intersectT = nextYInt;
 728
 729      if ( castRayBlock(   pStart, 
 730                           pEnd, 
 731                           Point2I( blockX * BlockSquareWidth, 
 732                                    blockY * BlockSquareWidth ), 
 733                           GridLevels, 
 734                           invDeltaX, 
 735                           invDeltaY, 
 736                           startT, 
 737                           intersectT, 
 738                           info, 
 739                           collideEmpty ) ) 
 740      {
 741         info->normal.z *= BlockSquareWidth * mSquareSize;
 742         info->normal.normalize();
 743         return true;
 744      }
 745
 746      startT = intersectT;
 747      if(intersectT >= 1)
 748         break;
 749      if(nextXInt < nextYInt)
 750         blockX += dx;
 751      else if(nextYInt < nextXInt)
 752         blockY += dy;
 753      else
 754      {
 755         blockX += dx;
 756         blockY += dy;
 757      }
 758   }
 759
 760   return false;
 761}
 762
 763struct TerrLOSStackNode
 764{
 765   F32 startT;
 766   F32 endT;
 767   Point2I blockPos;
 768   U32 level;
 769};
 770
 771bool TerrainBlock::castRayBlock( const Point3F &pStart, 
 772                                 const Point3F &pEnd, 
 773                                 const Point2I &aBlockPos, 
 774                                 U32 aLevel, 
 775                                 F32 invDeltaX, 
 776                                 F32 invDeltaY, 
 777                                 F32 aStartT, 
 778                                 F32 aEndT, 
 779                                 RayInfo *info, 
 780                                 bool collideEmpty )
 781{
 782   const U32 BlockSquareWidth = mFile->mSize;
 783   const U32 GridLevels = mFile->mGridLevels;
 784   const U32 BlockMask = mFile->mSize - 1;
 785
 786   F32 invBlockSize = 1 / F32( BlockSquareWidth );
 787
 788   static Vector<TerrLOSStackNode> stack;
 789   stack.setSize( GridLevels * 3 + 1 );
 790   U32 stackSize = 1;
 791
 792   stack[0].startT = aStartT;
 793   stack[0].endT = aEndT;
 794   stack[0].blockPos = aBlockPos;
 795   stack[0].level = aLevel;
 796   
 797   if( !aBlockPos.isZero() )
 798      return false;
 799
 800   while(stackSize--)
 801   {
 802      TerrLOSStackNode *sn = stack.address() + stackSize;
 803      U32 level  = sn->level;
 804      F32 startT = sn->startT;
 805      F32 endT   = sn->endT;
 806      Point2I blockPos = sn->blockPos;
 807
 808      const TerrainSquare *sq = mFile->findSquare( level, blockPos.x, blockPos.y );
 809
 810      F32 startZ = startT * (pEnd.z - pStart.z) + pStart.z;
 811      F32 endZ = endT * (pEnd.z - pStart.z) + pStart.z;
 812
 813      F32 minHeight = fixedToFloat(sq->minHeight);
 814      if(startZ <= minHeight && endZ <= minHeight)
 815         continue;
 816
 817      F32 maxHeight = fixedToFloat(sq->maxHeight);
 818      if(startZ >= maxHeight && endZ >= maxHeight)
 819         continue;
 820
 821      if (  !collideEmpty && ( sq->flags & TerrainSquare::Empty ) &&
 822           blockPos.x == ( blockPos.x & BlockMask ) && blockPos.y == ( blockPos.y & BlockMask ))
 823         continue;
 824
 825      if(level == 0)
 826      {
 827         F32 xs = blockPos.x * invBlockSize;
 828         F32 ys = blockPos.y * invBlockSize;
 829
 830         F32 zBottomLeft = fixedToFloat( mFile->getHeight(blockPos.x, blockPos.y) );
 831         F32 zBottomRight= fixedToFloat( mFile->getHeight(blockPos.x + 1, blockPos.y) );
 832         F32 zTopLeft =    fixedToFloat( mFile->getHeight(blockPos.x, blockPos.y + 1) );
 833         F32 zTopRight =   fixedToFloat( mFile->getHeight(blockPos.x + 1, blockPos.y + 1) );
 834
 835         PlaneF p1, p2;
 836         PlaneF divider;
 837         Point3F planePoint;
 838
 839         if(sq->flags & TerrainSquare::Split45)
 840         {
 841            p1.set(zBottomLeft - zBottomRight, zBottomRight - zTopRight, invBlockSize);
 842            p2.set(zTopLeft - zTopRight, zBottomLeft - zTopLeft, invBlockSize);
 843            planePoint.set(xs, ys, zBottomLeft);
 844            divider.x = 1;
 845            divider.y = -1;
 846            divider.z = 0;
 847         }
 848         else
 849         {
 850            p1.set(zTopLeft - zTopRight, zBottomRight - zTopRight, invBlockSize);
 851            p2.set(zBottomLeft - zBottomRight, zBottomLeft - zTopLeft, invBlockSize);
 852            planePoint.set(xs + invBlockSize, ys, zBottomRight);
 853            divider.x = 1;
 854            divider.y = 1;
 855            divider.z = 0;
 856         }
 857         p1.setPoint(planePoint);
 858         p2.setPoint(planePoint);
 859         divider.setPoint(planePoint);
 860
 861         F32 t1 = p1.intersect(pStart, pEnd);
 862         F32 t2 = p2.intersect(pStart, pEnd);
 863         F32 td = divider.intersect(pStart, pEnd);
 864
 865         F32 dStart = divider.distToPlane(pStart);
 866         F32 dEnd = divider.distToPlane(pEnd);
 867
 868         // see if the line crosses the divider
 869         if((dStart >= 0 && dEnd < 0) || (dStart < 0 && dEnd >= 0))
 870         {
 871            if(dStart < 0)
 872            {
 873               F32 temp = t1;
 874               t1 = t2;
 875               t2 = temp;
 876            }
 877            if(t1 >= startT && t1 && t1 <= td && t1 <= endT)
 878            {
 879               info->t = t1;
 880               info->normal = p1;
 881               return true;
 882            }
 883            if(t2 >= td && t2 >= startT && t2 <= endT)
 884            {
 885               info->t = t2;
 886               info->normal = p2;
 887               return true;
 888            }
 889         }
 890         else
 891         {
 892            F32 t;
 893            if(dStart >= 0) {
 894               t = t1;
 895               info->normal = p1;
 896            }
 897            else {
 898               t = t2;
 899               info->normal = p2;
 900            }
 901            if(t >= startT && t <= endT)
 902            {
 903               info->t = t;
 904               return true;
 905            }
 906         }
 907         continue;
 908      }
 909      S32 subSqWidth = 1 << (level - 1);
 910      F32 xIntercept = (blockPos.x + subSqWidth) * invBlockSize;
 911      F32 xInt = calcInterceptX(pStart.x, invDeltaX, xIntercept);
 912      F32 yIntercept = (blockPos.y + subSqWidth) * invBlockSize;
 913      F32 yInt = calcInterceptY(pStart.y, invDeltaY, yIntercept);
 914
 915      F32 startX = startT * (pEnd.x - pStart.x) + pStart.x;
 916      F32 startY = startT * (pEnd.y - pStart.y) + pStart.y;
 917
 918      if(xInt < startT)
 919         xInt = MAX_FLOAT;
 920      if(yInt < startT)
 921         yInt = MAX_FLOAT;
 922
 923      U32 x0 = (startX > xIntercept) * subSqWidth;
 924      U32 y0 = (startY > yIntercept) * subSqWidth;
 925      U32 x1 = subSqWidth - x0;
 926      U32 y1 = subSqWidth - y0;
 927      U32 nextLevel = level - 1;
 928
 929      // push the items on the stack in reverse order of processing
 930      if(xInt > endT && yInt > endT)
 931      {
 932         // only test the square the point started in:
 933         stack[stackSize].blockPos.set(blockPos.x + x0, blockPos.y + y0);
 934         stack[stackSize].level = nextLevel;
 935         stackSize++;
 936      }
 937      else if(xInt < yInt)
 938      {
 939         F32 nextIntersect = endT;
 940         if(yInt <= endT)
 941         {
 942            stack[stackSize].blockPos.set(blockPos.x + x1, blockPos.y + y1);
 943            stack[stackSize].startT = yInt;
 944            stack[stackSize].endT = endT;
 945            stack[stackSize].level = nextLevel;
 946            nextIntersect = yInt;
 947            stackSize++;
 948         }
 949         stack[stackSize].blockPos.set(blockPos.x + x1, blockPos.y + y0);
 950         stack[stackSize].startT = xInt;
 951         stack[stackSize].endT = nextIntersect;
 952         stack[stackSize].level = nextLevel;
 953
 954         stack[stackSize+1].blockPos.set(blockPos.x + x0, blockPos.y + y0);
 955         stack[stackSize+1].startT = startT;
 956         stack[stackSize+1].endT = xInt;
 957         stack[stackSize+1].level = nextLevel;
 958         stackSize += 2;
 959      }
 960      else if(yInt < xInt)
 961      {
 962         F32 nextIntersect = endT;
 963         if(xInt <= endT)
 964         {
 965            stack[stackSize].blockPos.set(blockPos.x + x1, blockPos.y + y1);
 966            stack[stackSize].startT = xInt;
 967            stack[stackSize].endT = endT;
 968            stack[stackSize].level = nextLevel;
 969            nextIntersect = xInt;
 970            stackSize++;
 971         }
 972         stack[stackSize].blockPos.set(blockPos.x + x0, blockPos.y + y1);
 973         stack[stackSize].startT = yInt;
 974         stack[stackSize].endT = nextIntersect;
 975         stack[stackSize].level = nextLevel;
 976
 977         stack[stackSize+1].blockPos.set(blockPos.x + x0, blockPos.y + y0);
 978         stack[stackSize+1].startT = startT;
 979         stack[stackSize+1].endT = yInt;
 980         stack[stackSize+1].level = nextLevel;
 981         stackSize += 2;
 982      }
 983      else
 984      {
 985         stack[stackSize].blockPos.set(blockPos.x + x1, blockPos.y + y1);
 986         stack[stackSize].startT = xInt;
 987         stack[stackSize].endT = endT;
 988         stack[stackSize].level = nextLevel;
 989
 990         stack[stackSize+1].blockPos.set(blockPos.x + x0, blockPos.y + y0);
 991         stack[stackSize+1].startT = startT;
 992         stack[stackSize+1].endT = xInt;
 993         stack[stackSize+1].level = nextLevel;
 994         stackSize += 2;
 995      }
 996   }
 997
 998   return false;
 999}
1000