// ----------------------------------------------------------------------- // // // MODULE : ltworldcollide.h // // PURPOSE : Stops the camera walking through walls: a swept sphere against the // level's solid triangles, with gravity, sliding and step-up. // // ⚠️ WHY A TRIANGLE SOUP AND NOT THE BSP. The world ships a BSP -- the model // literally named `PhysicsBSP` -- and traversing it would be the engine's own // answer. But its node records are only partly understood: the 14-byte half is // read, the trailing 6-byte half is not, and `FORMATS.md` records that the // per-node count is `6*(nNodes - k)` for a `k` nobody has identified. Building // collision on a structure that is not fully decoded would put a subtle, // intermittent bug -- falling through one floor in twenty -- on top of an // unfinished parse. // // The triangles, by contrast, are completely known: every one of them passed // the boundary check AND the meaning checks before it was published. So the // collision uses the geometry that is certain and pays for it with a uniform // grid, which is a memory cost rather than a correctness risk. // // ⚠️ WHAT IT IS NOT: the game's physics. No stairs-as-ramps, no crouch, no // water, no moving platforms, no push-out of overlapping objects. It keeps a // sphere out of the walls and on the floor. // // ----------------------------------------------------------------------- // #ifndef __LT_WORLD_COLLIDE_H__ #define __LT_WORLD_COLLIDE_H__ #include #include class CLTWorld; class CLTWorldCollide { public: CLTWorldCollide(); // Gathers every solid triangle in the world and indexes it. Safe to call // on an empty world; Triangles() is then 0 and every move succeeds. void Build(const CLTWorld& world); // ⚠️ Doors move, so their triangles cannot live in the static grid: the // grid is built once from world-space positions. They are held separately // and tested brute force, which is affordable because a level has tens of // doors of a few polygons each -- M01S01's openable ones come to a few // hundred triangles against 9,189 static ones. // // Replaced wholesale rather than edited: the caller rebuilds this only on // frames where a door actually moved. void SetDynamic(const std::vector& tris); unsigned int DynamicTriangles() const { return (unsigned int)(m_Dyn.size() / 9); } // ...and WHOSE each one is (5dp): one owner handle per dynamic triangle, // in the same order -- the door's server record. A world touch on a door // then names the door, not the world. Optional: walk mode never sets it. // And its polygon (5dq): LTWorldPolyId of the door's own face, so a touch // reports the door's material as the donor does (MakeHPoly). void SetDynamicOwners(const std::vector& owners, const std::vector& polys) { m_DynOwner = owners; m_DynPoly = polys; } // ⚠️ THE DOOR TRIANGLES RAYS SEE, when that is not all of them (DEVIATIONS // E-008: rays pass through the power lines). Contact and ground tests keep // SetDynamic's list. Never set (walk mode) = the same list. void SetDynamicRay(const std::vector& tris); // ⚠️ A STATIC BRUSH OBJECT THAT IS GONE (5ds). The grid is built once, // but a destructible world model (M08S04's vent louvres, shot away) is // removed at run time; its triangles stayed, an invisible wall. The server // switches a model off when its object is no longer live and solid, and // every static test skips its triangles. nModel is the world-model index // LTWorldPolyId encodes. void SetModelOff(unsigned int nModel, bool bOff); // Names of the models to leave OUT of the static grid. void SetExcluded(const std::vector& names) { m_Excluded = names; } unsigned int Triangles() const { return (unsigned int)(m_Tris.size() / 9); } unsigned int Cells() const { return m_bBuilt ? (unsigned int)((size_t)m_Dim[0] * m_Dim[1] * m_Dim[2]) : 0u; } // Cells holding anything, triangle entries over all cells, and the bytes // the cell table takes (5es -- M14S02's 39.5M cells). void GridStats(unsigned int* pOccupied, size_t* pEntries, size_t* pBytes) const; // Moves a sphere from pos by delta, sliding along whatever it hits. // Writes the resolved centre back into pos. // // ⚠️ `bGround` reports whether the sphere ended the move resting on a // surface flat enough to stand on -- the caller needs it to decide whether // gravity keeps accelerating, and a mover that does not report it makes // the camera jitter permanently between falling and landing. void MoveSphere(float* pPos3, const float* pDelta3, float fRadius, bool* pbGround) const; // ...and WHAT IT HIT (5do): every push-out's normal in order (the first // kMaxNormals), and the LAST surface's polygon -- LTWorldPolyId, 0 for a // door triangle -- and contact point, as the donor's collision info keeps // "the last poly hit". The server turns these into a world touch. struct Contacts { enum { kMaxNormals = 16 }; int m_nHits = 0; float m_Normals[kMaxNormals][3]; float m_Point[3] = { 0, 0, 0 }; unsigned int m_nPoly = 0; void* m_pOwner = nullptr; // the last surface's door, or null }; void MoveSphere(float* pPos3, const float* pDelta3, float fRadius, bool* pbGround, Contacts* pContacts) const; // ⚠️ THE RAY, and it is what "use the door" and "shoot the guard" are made // of. `IntersectSegment` is how the game asks what is in front of the // player: DoActivate casts one to find what to operate (PlayerObj.cpp:3172) // and every weapon casts one to find what it hit. With it stubbed, E does // nothing and nothing can be shot -- the two are the same missing call. // // Returns the NEAREST hit between from and to. pNormal3 is the surface // normal, pT the fraction along the segment (0..1). bool RaySegment(const float* pFrom3, const float* pTo3, float* pPoint3, float* pNormal3, float* pT) const; // ...and WHICH POLYGON it hit: LTWorldPolyId() of it, or 0 for a door // triangle (doors answer through the brush module). The game asks for the // polygon's surface type -- shoot-through, impact effect, footstep sound. bool RaySegment(const float* pFrom3, const float* pTo3, float* pPoint3, float* pNormal3, float* pT, unsigned int* pPolyId) const; // True when a sphere at this position overlaps anything solid. Used to // decide whether a spawn point is inside geometry. bool Overlaps(const float* pPos3, float fRadius) const; private: void CellRange(const float* pMin3, const float* pMax3, int* pLo3, int* pHi3) const; void Gather(const float* pMin3, const float* pMax3, std::vector& out) const; // Deepest penetration of a sphere against one triangle. Returns false when // they do not touch. bool Contact(const float* pC3, float fRadius, int nTri, float* pNormal3, float* pDepth) const; bool ContactAny(const float* pC3, float fRadius, const float* pTris, int nTris, float* pNormal3, float* pDepth, int* pTri = 0) const; // The static half of RaySegment: the nearest static triangle the segment // (unit direction d, length fLen) crosses. bGrid walks only the cells the // segment passes through (5ee); false tests every triangle (the old way). // Both return the same triangle: nearest t, lowest index on a tie. bool RayStatic(const float* o, const float* d, float fLen, bool bGrid, float* pBest, float* pNormal3, unsigned int* pPoly) const; // ...and the door half: lowers *pBest when a door triangle is nearer and // returns true if one was. bCull skips a block of door triangles whose // box the segment misses (5ee); false tests every one (the old way). bool RayDynamic(const float* o, const float* d, bool bCull, float* pBest, float* pNormal3) const; std::vector m_Tris; // 9 floats per triangle std::vector m_TriPoly; // LTWorldPolyId, one per triangle std::vector m_TriFront; // a world model's: rays hit its front only (5dz) std::vector m_ModelOff; // per world model: switched off (5ds) unsigned int m_nModelsOff = 0; bool TriOff(size_t nTri) const { if (!m_nModelsOff || nTri >= m_TriPoly.size()) return false; const unsigned int m = (m_TriPoly[nTri] >> 20) - 1u; return m < m_ModelOff.size() && m_ModelOff[m] != 0; } std::vector m_Dyn; // doors, in world space, now std::vector m_DynOwner; // one per m_Dyn triangle, or empty std::vector m_DynPoly; // the same, its LTWorldPolyId std::vector m_DynRay; // the ones rays test, if m_bDynRay bool m_bDynRay = false; std::vector m_DynBox; // per kDynBlock of m_Dyn: min3 max3 (5ee) std::vector m_DynRayBox; // ...and of m_DynRay std::vector m_Excluded; // ⚠️ THE CELL TABLE IS TWO-LEVEL (5es). One std::vector per cell cost 24 // bytes for every EMPTY cell: M14S02's triangles span 145,000 units, its // 39.5M cells are 97% empty, and the table was 914 MB for 9 MB of indices. // Now: blocks of 8x8x8 cells; a block that holds nothing is one word, an // occupied one has kBlockCells+1 offsets into one flat array. Each cell // still lists the same triangles in the same (ascending) order, so every // ray and sphere move reads the same candidates as before. enum { kBlockBits = 3, kBlockSide = 1 << kBlockBits, kBlockCells = kBlockSide * kBlockSide * kBlockSide }; static constexpr unsigned int kNoBlock = 0xFFFFFFFFu; std::vector m_Block; // per block: its slot in m_BlockOff, or kNoBlock std::vector m_BlockOff; // per occupied block: kBlockCells+1 offsets into m_CellTris std::vector m_CellTris; // every cell's triangle indices, cell after cell int m_BDim[3]; // The OLD table, built only for LT_OLDGRID=1 (read instead) or // LT_GRIDCHECK=1 (compared cell by cell with the new one). std::vector > m_Cells; bool m_bOldTable = false; void CellTris(int x, int y, int z, const int*& pBegin, const int*& pEnd) const { if (m_bOldTable) { const std::vector& c = m_Cells[((size_t)z * m_Dim[1] + y) * m_Dim[0] + x]; pBegin = c.empty() ? 0 : &c[0]; pEnd = pBegin + c.size(); return; } const unsigned int b = m_Block[((size_t)(z >> kBlockBits) * m_BDim[1] + (y >> kBlockBits)) * m_BDim[0] + (x >> kBlockBits)]; if (b == kNoBlock) { pBegin = pEnd = 0; return; } const unsigned int* o = &m_BlockOff[(size_t)b * (kBlockCells + 1)]; const unsigned int l = ((((unsigned)z & (kBlockSide - 1)) << kBlockBits | ((unsigned)y & (kBlockSide - 1))) << kBlockBits) | ((unsigned)x & (kBlockSide - 1)); pBegin = m_CellTris.data() + o[l]; pEnd = m_CellTris.data() + o[l + 1]; } float m_TriMin[3]; // the triangles' own bounds (5ee) float m_TriMax[3]; unsigned int m_nSerial; // which Build, for the ray stamps float m_Min[3]; float m_CellSize; int m_Dim[3]; bool m_bBuilt; }; // ----------------------------------------------------------------------- // // THE SHARED INSTANCE // // ⚠️ ONE GRID PER LOADED WORLD, because the server and the client both need to // ask the same question and must get the same answer. NOLF drives the PLAYER // from the client (`CPlayerObj`: "m_dwFlags &= ~FLAG_GRAVITY; // This is // controlled by the client") and its AI from the server, so a port that built // collision on one side only moves half the game -- which is exactly what the // first version of the server physics did. // // ⚠️ The walk viewer keeps its OWN instance and is deliberately left alone. It // is the 102/102-worlds path, it is never live at the same time as the server, // and rewiring it to serve a newer module is a risk with no payoff. // // Build is idempotent per world pointer; Reset forgets it for a level change. // ----------------------------------------------------------------------- // CLTWorldCollide* LTGetWorldCollide(); void LTWorldCollide_BuildFor(const CLTWorld* pWorld); void LTWorldCollide_Reset(); bool LTWorldCollide_Ready(); // ⚠️ AN HPOLY THIS PORT HANDS OUT: ((world model index + 1) << 20) | polygon. // Never 0 (the game reads 0 as "no polygon") and never INVALID_HPOLY. inline unsigned int LTWorldPolyId(unsigned int nModel, unsigned int nPoly) { return ((nModel + 1u) << 20) | (nPoly & 0xFFFFFu); } inline bool LTWorldPolyDecode(unsigned int id, unsigned int* pModel, unsigned int* pPoly) { if (id == 0 || id == 0xFFFFFFFFu || (id >> 20) == 0) return false; *pModel = (id >> 20) - 1u; *pPoly = id & 0xFFFFFu; return true; } #endif // __LT_WORLD_COLLIDE_H__