source/psim/p_trace_bsp.cpp

   1 //**************************************************************************
   2 //**
   3 //**    ##   ##    ##    ##   ##   ####     ####   ###     ###
   4 //**    ##   ##  ##  ##  ##   ##  ##  ##   ##  ##  ####   ####
   5 //**     ## ##  ##    ##  ## ##  ##    ## ##    ## ## ## ## ##
   6 //**     ## ##  ########  ## ##  ##    ## ##    ## ##  ###  ##
   7 //**      ###   ##    ##   ###    ##  ##   ##  ##  ##       ##
   8 //**       #    ##    ##    #      ####     ####   ##       ##
   9 //**
  10 //**  Copyright (C) 1999-2006 Jānis Legzdiņš
  11 //**  Copyright (C) 2018-2023 Ketmar Dark
  12 //**
  13 //**  This program is free software: you can redistribute it and/or modify
  14 //**  it under the terms of the GNU General Public License as published by
  15 //**  the Free Software Foundation, version 3 of the License ONLY.
  16 //**
  17 //**  This program is distributed in the hope that it will be useful,
  18 //**  but WITHOUT ANY WARRANTY; without even the implied warranty of
  19 //**  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20 //**  GNU General Public License for more details.
  21 //**
  22 //**  You should have received a copy of the GNU General Public License
  23 //**  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  24 //**
  25 //**************************************************************************
  26 #include "../gamedefs.h"
  27 #include "p_trace_internal.h"
  28
  29
  30 static VCvarB dbg_bsp_trace_strict_flats("dbg_bsp_trace_strict_flats", false, "use strict checks for flats?", /*CVAR_Archive|*/CVAR_PreInit|CVAR_NoShadow);
  31
  32
  33 //**************************************************************************
  34 //
  35 // BSP raycasting
  36 //
  37 //**************************************************************************
  38
  39 //==========================================================================
  40 //
  41 //  PlaneFlagsToLineFlags
  42 //
  43 //==========================================================================
  44 /*
  45 static inline VVA_CHECKRESULT VVA_OKUNUSED unsigned PlaneFlagsToLineFlags (unsigned planeblockflags) {
  46   return
  47     ((planeblockflags&SPF_NOBLOCKING) ? ((ML_BLOCKING|ML_BLOCKEVERYTHING)|(planeblockflags&SPF_PLAYER ? ML_BLOCKPLAYERS : 0u)|(planeblockflags&SPF_MONSTER ? ML_BLOCKMONSTERS : 0u)) : 0u)|
  48     ((planeblockflags&SPF_NOBLOCKSIGHT) ? ML_BLOCKSIGHT : 0u)|
  49     ((planeblockflags&SPF_NOBLOCKSHOOT) ? ML_BLOCKHITSCAN : 0u);
  50   //ML_BLOCK_FLOATERS      = 0x00040000u,
  51   //ML_BLOCKPROJECTILE     = 0x01000000u,
  52 }
  53 */
  54
  55
  56 struct TBSPTrace {
  57 public:
  58   VLevel *Level;
  59   TVec Start;
  60   TVec End;
  61   TVec Delta;
  62   unsigned PlaneNoBlockFlags;
  63   // the following will be calculated from `PlaneNoBlockFlags`
  64   unsigned LineBlockFlags;
  65   // subsector we ended in (can be arbitrary if trace doesn't end in map boundaries)
  66   // valid only for `TraceLine()` call (i.e. BSP trace)
  67   subsector_t *EndSubsector;
  68   // the following fields are valid only if trace was failed (i.e. we hit something)
  69   TPlane HitPlane; // set both for a line and for a flat
  70   line_t *HitLine; // can be `nullptr` if we hit a floor/ceiling
  71   float HitTime; // will be 1.0f if nothing was hit
  72   TPlane LinePlane; // vertical plane for (Start,End), used only for line checks; may be undefined
  73   bool wantHitInfo;
  74 };
  75
  76
  77 //==========================================================================
  78 //
  79 //  CheckPlanes
  80 //
  81 //==========================================================================
  82 static bool CheckPlanes (TBSPTrace &trace, sector_t *sec, float tmin, float tmax) {
  83   TPlane hpl;
  84   float otime;
  85   if (!VLevel::CheckPassPlanes(sec, trace.Start, trace.End, trace.PlaneNoBlockFlags, nullptr, nullptr, nullptr, &hpl, &otime)) {
  86     if (otime <= tmin || otime >= tmax) return true;
  87     // hit floor or ceiling
  88     trace.HitPlane = hpl;
  89     trace.HitTime = otime;
  90     return false;
  91   }
  92   return true;
  93 }
  94
  95
  96 //==========================================================================
  97 //
  98 //  BSPCheckLine
  99 //
 100 //  returns `true` if the line isn't crossed
 101 //  returns `false` if the line blocked the ray
 102 //
 103 //==========================================================================
 104 static bool BSPCheckLine (TBSPTrace &trace, line_t *line, float tmin, float tmax) {
 105   if (!line) return true; // ignore minisegs, they cannot block anything
 106
 107   // allready checked other side?
 108   if (line->validcount == validcount) return true;
 109   line->validcount = validcount;
 110
 111   // signed distances from the line points to the trace line plane
 112   float dot1 = trace.LinePlane.PointDistance(*line->v1);
 113   float dot2 = trace.LinePlane.PointDistance(*line->v2);
 114
 115   // do not use multiplication to check: zero speedup, lost accuracy
 116   //if (dot1*dot2 >= 0) return true; // line isn't crossed
 117   if (dot1 < 0.0f && dot2 < 0.0f) return true; // didn't reached back side
 118   // if the line is parallel to the trace plane, ignore it
 119   if (dot1 >= 0.0f && dot2 >= 0.0f) return true; // didn't reached front side
 120
 121   // signed distances from the trace points to the line plane
 122   dot1 = line->PointDistance(trace.Start);
 123   dot2 = line->PointDistance(trace.End);
 124
 125   // do not use multiplication to check: zero speedup, lost accuracy
 126   //if (dot1*dot2 >= 0) return true; // line isn't crossed
 127   if (dot1 < 0.0f && dot2 < 0.0f) return true; // didn't reached back side
 128   // if the trace is parallel to the line plane, ignore it
 129   if (dot1 >= 0.0f && dot2 >= 0.0f) return true; // didn't reached front side
 130
 131   const bool backside = (dot1 < 0.0f);
 132
 133   polyobj_t *po = line->pobj();
 134   if (po && !po->Is3D()) po = nullptr;
 135
 136   // crosses a two sided line
 137   sector_t *front = (backside ? line->backsector : line->frontsector);
 138   if (!front) return true; // just in case
 139
 140   // intercept vector
 141   // no need to check if den == 0, because then planes are parallel
 142   // (they will never cross) or it's the same plane (also rejected)
 143   const float den = trace.Delta.dot(line->normal);
 144   if (den == 0.0f) return true; // ...but just in case
 145   const float num = line->dist-trace.Start.dot(line->normal);
 146   const float frac = num/den;
 147
 148   if (frac <= 0.0f || frac >= 1.0f) return true;
 149
 150   // if collision is not inside our time, unmark the line
 151   if (frac <= tmin || frac >= tmax) {
 152     line->validcount = 0;
 153     return true;
 154   }
 155
 156   // if the hit is further than current hit time, do nothing
 157   if (frac >= trace.HitTime) return true;
 158
 159   if (po) {
 160     const float pzbot = po->pofloor.minz;
 161     const float pztop = po->poceiling.maxz;
 162
 163     if (trace.Start.z <= pzbot && trace.End.z <= pzbot) return true; // fully under
 164     if (trace.Start.z >= pztop && trace.End.z >= pztop) return true; // fully over
 165
 166     const float hpz = trace.Start.z+frac*trace.Delta.z;
 167
 168     // easy case: hit pobj?
 169     if (hpz >= pzbot && hpz <= pztop) {
 170       trace.HitPlane = *line;
 171       trace.HitLine = line;
 172       trace.HitTime = frac;
 173       return false;
 174     }
 175
 176     // if we are entering the pobj, no need to check planes
 177     if (dot1 >= 0.0f) return true; // no hit
 178
 179     // check polyobject planes
 180     TPlane pplane;
 181     const float ptime = VLevel::CheckPObjPassPlanes(po, trace.Start, trace.End, nullptr, nullptr, &pplane);
 182     if (ptime <= tmin || ptime >= frac) return true; // no hit
 183
 184     // we have a winner!
 185     trace.HitPlane = pplane;
 186     trace.HitLine = nullptr;
 187     trace.HitTime = ptime;
 188     return false;
 189   }
 190
 191   if (!CheckPlanes(trace, front, tmin, frac)) return false;
 192
 193   if (!(line->flags&ML_TWOSIDED) || (line->flags&trace.LineBlockFlags)) {
 194     //trace.Flags |= TBSPTrace::SightEarlyOut;
 195   } else {
 196     if (!po && (line->flags&ML_TWOSIDED)) {
 197       // crossed a two sided line
 198       const TVec hitpoint = trace.Start+frac*trace.Delta;
 199       opening_t *open = trace.Level->LineOpenings(line, hitpoint, trace.PlaneNoBlockFlags&SPF_FLAG_MASK);
 200       if (dbg_bsp_trace_strict_flats) {
 201         while (open) {
 202           if (open->range > 0.0f && open->bottom < hitpoint.z && open->top > hitpoint.z) return true;
 203           open = open->next;
 204         }
 205       } else {
 206         while (open) {
 207           if (open->range > 0.0f && open->bottom <= hitpoint.z && open->top >= hitpoint.z) return true;
 208           open = open->next;
 209         }
 210       }
 211     }
 212   }
 213
 214   // hit line
 215   trace.HitPlane = *line;
 216   trace.HitLine = line;
 217   trace.HitTime = frac;
 218   return false;
 219 }
 220
 221
 222 //==========================================================================
 223 //
 224 //  BSPCrossSubsector
 225 //
 226 //  Returns true if trace crosses the given subsector successfully.
 227 //
 228 //==========================================================================
 229 static bool BSPCrossSubsector (TBSPTrace &trace, int num, float tmin, float tmax) {
 230   subsector_t *sub = &trace.Level->Subsectors[num];
 231   bool res = true;
 232
 233   if (sub->HasPObjs()) {
 234     // check the polyobjects in the subsector first
 235     for (auto &&it : sub->PObjFirst()) {
 236       polyobj_t *pobj = it.pobj();
 237       line_t **polyLines = pobj->lines;
 238       for (int polyCount = pobj->numlines; polyCount--; ++polyLines) {
 239         if (!BSPCheckLine(trace, *polyLines, tmin, tmax)) {
 240           res = false;
 241           trace.EndSubsector = sub;
 242           if (!trace.wantHitInfo) return false;
 243         }
 244       }
 245     }
 246   }
 247
 248   // check lines
 249   const seg_t *seg = &trace.Level->Segs[sub->firstline];
 250   for (int count = sub->numlines; count--; ++seg) {
 251     if (seg->linedef && !BSPCheckLine(trace, seg->linedef, tmin, tmax)) {
 252       res = false;
 253       trace.EndSubsector = sub;
 254       if (!trace.wantHitInfo) return false;
 255     }
 256   }
 257
 258   return res;
 259 }
 260
 261
 262 //==========================================================================
 263 //
 264 //  CrossBSPNode
 265 //
 266 //  Returns true if trace crosses the given node successfully.
 267 //
 268 //==========================================================================
 269 static bool CrossBSPNode (TBSPTrace &trace, int bspnum, float tmin, float tmax) {
 270   while (BSPIDX_IS_NON_LEAF(bspnum)) {
 271     const node_t *node = &trace.Level->Nodes[bspnum];
 272     //if (!node.containsBox2D(tr.swbbmin, tr.swbbmax)) return;
 273
 274     // decide which side the start point is on
 275     int side = node->PointOnSide2(trace.Start);
 276
 277     // cross the starting side
 278     if (!CrossBSPNode(trace, node->children[side&1], tmin, tmax)) return false;
 279
 280     if (side != 2 && side == node->PointOnSide2(trace.End)) return true;
 281
 282     // cross the ending side
 283     bspnum = node->children[(side&1)^1];
 284   }
 285   return BSPCrossSubsector(trace, BSPIDX_LEAF_SUBSECTOR(bspnum), tmin, tmax);
 286
 287 #if 0
 288   if (BSPIDX_IS_NON_LEAF(bspnum)) {
 289     const node_t *node = &trace.Level->Nodes[bspnum];
 290     // decide which side the start point is on
 291     #if 0
 292     const float denom = node->normal.dot(trace.Delta);
 293     const float dist = node->dist-node->normal.dot(trace.Start);
 294     unsigned nearIndex = (unsigned)(dist > 0.0f);
 295     // if denom is zero, ray runs parallel to the plane
 296     // in this case, just fall through to visit the near side (the one p lies on)
 297     if (denom != 0.0f) {
 298       const float t = dist/denom; // intersection time
 299       if (t > 0.0f && t <= tmax) {
 300         if (t >= tmin) {
 301           // visit near side first
 302           return
 303             !CrossBSPNode(trace, node->children[nearIndex], tmin, t)) ||
 304             // then visit the far side
 305             CrossBSPNode(trace, node->children[1u^nearIndex], t, tmax);
 306         } else {
 307           // 0 <= t < tmin, visit far side
 308           //nearIndex ^= 1u;
 309           return CrossBSPNode(trace, node->children[1u^nearIndex], t, tmax);
 310         }
 311       }
 312     }
 313     return CrossBSPNode(trace, node->children[nearIndex], tmin, tmax);
 314
 315     #else
 316
 317     /*
 318     const TVec dif = p1-p0;
 319     const float dv = normal.dot(dif);
 320     const float t = (fabsf(dv) > eps ? (dist-normal.dot(p0))/dv : 0.0f);
 321     return p0+(dif*t);
 322     */
 323     unsigned side = (unsigned)(trace.Start.dot(node->normal)-node->dist < 0.0f);
 324     if (!CrossBSPNode(trace, node->children[side], tmin, tmax)) return false;
 325     // then visit the far side
 326     return CrossBSPNode(trace, node->children[1u^side], tmin, tmax);
 327     #endif
 328     /*
 329     // if bit 1 is set (i.e. `(side&2) != 0`), the point lies on the plane
 330     const int side = node->PointOnSide2(trace.Start);
 331     // cross the starting side
 332     if (!CrossBSPNode(trace, node->children[side&1])) {
 333       // if on the plane, check other side
 334       if (side&2) (void)CrossBSPNode(trace, node->children[(side&1)^1]);
 335       // definitely blocked
 336       return false;
 337     }
 338     // the partition plane is crossed here
 339     // if not on the plane, and endpoint is on the same side, there's nothing more to do
 340     if (!(side&2) && side == node->PointOnSide2(trace.End)) return true; // the line doesn't touch the other side
 341     // cross the ending side
 342     return CrossBSPNode(trace, node->children[(side&1)^1]);
 343     */
 344   } else {
 345     return BSPCrossSubsector(trace, BSPIDX_LEAF_SUBSECTOR(bspnum), tmin, tmax);
 346   }
 347 #endif
 348 }
 349
 350
 351 //==========================================================================
 352 //
 353 //  CheckStartingPObj
 354 //
 355 //  check if starting point is inside any 3d pobj
 356 //  we have to do this to check pobj planes first
 357 //
 358 //  returns `true` if no obstacle was hit
 359 //  sets `trace.LineEnd` if something was hit (and returns `false`)
 360 //
 361 //==========================================================================
 362 static bool CheckStartingPObj (TBSPTrace &trace) {
 363   TVec hp;
 364   TPlane hpl;
 365   const float frc = trace.Level->CheckPObjPlanesPoint(trace.Start, trace.End, nullptr, &hp, nullptr, &hpl);
 366   if (frc < 0.0f || frc >= 1.0f) return true;
 367   trace.EndSubsector = trace.Level->PointInSubsector(trace.Start);
 368   trace.HitPlane = hpl;
 369   trace.HitTime = frc;
 370   return false;
 371 }
 372
 373
 374 //==========================================================================
 375 //
 376 //  FillLineTrace
 377 //
 378 //==========================================================================
 379 static void FillLineTrace (linetrace_t &trace, const TBSPTrace &btr) noexcept {
 380   trace.Start = btr.Start;
 381   trace.End = btr.End;
 382   trace.EndSubsector = btr.EndSubsector;
 383   trace.HitPlane = btr.HitPlane;
 384   trace.HitLine = btr.HitLine;
 385   trace.HitTime = btr.HitTime;
 386 }
 387
 388
 389 //==========================================================================
 390 //
 391 //  VLevel::TraceLine
 392 //
 393 //  returns `true` if the line is not blocked
 394 //  returns `false` if the line was blocked, and sets hit normal/point
 395 //
 396 //==========================================================================
 397 bool VLevel::TraceLine (linetrace_t &trace, const TVec &Start, const TVec &End, unsigned PlaneNoBlockFlags, unsigned moreLineBlockFlags) {
 398   TBSPTrace btr;
 399   btr.Level = this;
 400   btr.Start = Start;
 401   btr.End = End;
 402   btr.Delta = End-Start;
 403   btr.PlaneNoBlockFlags = PlaneNoBlockFlags;
 404   btr.HitLine = nullptr;
 405   btr.HitTime = 1.0f;
 406   btr.wantHitInfo = !!(PlaneNoBlockFlags&SPF_HITINFO);
 407   PlaneNoBlockFlags &= ~SPF_HITINFO;
 408
 409   if (PlaneNoBlockFlags&SPF_NOBLOCKING) {
 410     moreLineBlockFlags |= ML_BLOCKING|ML_BLOCKEVERYTHING;
 411     if (PlaneNoBlockFlags&SPF_PLAYER) moreLineBlockFlags |= ML_BLOCKPLAYERS;
 412     if (PlaneNoBlockFlags&SPF_MONSTER) moreLineBlockFlags |= ML_BLOCKMONSTERS;
 413     //ML_BLOCK_FLOATERS      = 0x00040000u,
 414     //ML_BLOCKPROJECTILE     = 0x01000000u,
 415   }
 416   if (PlaneNoBlockFlags&SPF_NOBLOCKSIGHT) moreLineBlockFlags |= ML_BLOCKSIGHT;
 417   if (PlaneNoBlockFlags&SPF_NOBLOCKSHOOT) moreLineBlockFlags |= ML_BLOCKHITSCAN;
 418
 419   btr.LineBlockFlags = moreLineBlockFlags;
 420
 421   //k8: HACK!
 422   if (btr.Delta.x == 0.0f && btr.Delta.y == 0.0f) {
 423     // this is vertical trace; end subsector is known
 424     btr.EndSubsector = PointInSubsector(End);
 425     //btr.Plane.SetPointNormal3D(Start, TVec(0.0f, 0.0f, (btr.Delta.z >= 0.0f ? 1.0f : -1.0f))); // arbitrary orientation
 426     // point cannot hit anything!
 427     if (fabsf(btr.Delta.z) <= 0.0001f) {
 428       // always succeed
 429       FillLineTrace(trace, btr);
 430       return true;
 431     }
 432     const bool pores = CheckStartingPObj(btr);
 433     const bool plres = CheckPlanes(btr, btr.EndSubsector->sector, 0.0f, 1.0f);
 434     FillLineTrace(trace, btr);
 435     return (pores && plres);
 436   } else {
 437     IncrementValidCount();
 438     btr.LinePlane.SetPointDirXY(Start, btr.Delta);
 439     // the head node is the last node output
 440     if (NumSubsectors > 1) {
 441       const bool pores = CheckStartingPObj(btr);
 442       const bool plres = CrossBSPNode(btr, NumNodes-1, 0.0f, 1.0f);
 443       FillLineTrace(trace, btr);
 444       return (pores && plres);
 445     } else if (NumSubsectors == 1) {
 446       btr.EndSubsector = &Subsectors[0];
 447       const bool pores = CheckStartingPObj(btr);
 448       const bool plres = BSPCrossSubsector(btr, 0, 0.0f, 1.0f);
 449       FillLineTrace(trace, btr);
 450       return (pores && plres);
 451     }
 452   }
 453   // we should never arrive here
 454   abort();
 455 }
 456
 457
 458 //==========================================================================
 459 //
 460 //  Script natives
 461 //
 462 //==========================================================================
 463 IMPLEMENT_FUNCTION(VLevel, BSPTraceLine) {
 464   TVec Start, End;
 465   TVec *HitPoint;
 466   TVec *HitNormal;
 467   VOptParamInt noBlockFlags(SPF_NOBLOCKING);
 468   vobjGetParamSelf(Start, End, HitPoint, HitNormal, noBlockFlags);
 469   linetrace_t trace;
 470   bool res = Self->TraceLine(trace, Start, End, noBlockFlags);
 471   if (!res && (noBlockFlags.value&SPF_HITINFO)) {
 472     if (HitPoint) *HitPoint = Start+(End-Start)*trace.HitTime;
 473     if (HitNormal) {
 474       *HitNormal = trace.HitPlane.normal;
 475       if (trace.HitLine && trace.HitLine->PointOnSide(Start)) *HitNormal = -trace.HitPlane.normal;
 476     }
 477   } else {
 478     if (HitPoint) *HitPoint = End;
 479     if (HitNormal) *HitNormal = TVec(0.0f, 0.0f, 1.0f); // arbitrary
 480   }
 481   RET_BOOL(res);
 482 }
 483
 484 IMPLEMENT_FUNCTION(VLevel, BSPTraceLineEx) {
 485   linetrace_t tracetmp;
 486   TVec Start, End;
 487   linetrace_t *tracep;
 488   VOptParamInt noBlockFlags(SPF_NOBLOCKING);
 489   vobjGetParamSelf(Start, End, tracep, noBlockFlags);
 490   if (!tracep) tracep = &tracetmp;
 491   RET_BOOL(Self->TraceLine(*tracep, Start, End, noBlockFlags));
 492 }