BMS format object's collision about silkroaddoc

[DummkopfOfHachtenduden]

You can't use a single cell for an object of that size simply because the algorithm would break.

Assuming you only have a single cell which would be Cell0 in this case containing all edges. The algorithm on the client/server still excepts the outline lookup grid to cover the whole object. So a ray (red here) would entirely miss Cell0 as the 100x100 cell size is hardcoded. It would've practically not have hit any Cell and thus won't test any outline edges for intersection.

The outline edge has to be listed in every cell it overlaps with.
So yes, Edge 1 would be added to both Cell0 and Cell4.

[DummkopfOfHachtenduden]

All BMS collision is stored under https://github.com/DummkopfOfHachtenduden/SilkroadDoc/wiki/JMXVBMS#navmeshobj
The bounding boxes are not used for collision, they're also inaccurate. You'll have to check the flag of the edges you're intersecting with in a specific manner.

enum EdgeFlag : byte
{
    None = 0,
    BlockDst2Src = 1,
    BlockSrc2Dst = 2,
    Blocked = BlockDst2Src | BlockSrc2Dst,
    Internal = 4,
    Global = 8,
    Underpass = 16,
    Entrance = 32,  // Dungeon (obsolete?)
    Bit6 = 64,
    Siege = 128,    // Fortress War (attack passthrough)
}

This video shows how collision is found when raycasting from within the object (standing on NavMeshObj).
https://youtu.be/qxqx9wrCicU
Walkable edges are rendered in green.
Underpass edges are rendered in yellow. (they'll only be a collision from within)
Blocked edges are rendered in red.
Edges that have been checked for collision by the algorithm are highlighted blue.
The ray that is tested is rendered green when there is no collision found and red up until where the collision point has been found when colliding.

This video shows how collision is found when raycasting from outside the object (standing on NavMeshTerrain)
https://www.youtube.com/watch?v=4SgWcmloJ1U
Edges that have been checked for collision by the algorithm are highlighted YELLOW here.
OutlineLookupGrid cells that have been looked at by the algorithm are highlighted in magenta.
Blue circles are used to represent NavMesh changes (transition between graphs aka different terrain sections)
Magenta circles are used to represent possible intersection of which the closest will be the actual intersection point.

There are fully walkable objects in this game. You're raycasting algorithm needs to be able to transition from terrain into objects and vice versa so you can handle stuff like this

Is there some simple way to identify whether object has a collision or not? (checking some flag or offset)

If header.NavMeshOffset is 0 then the object has no collision. The only exception being ColObj's in a dungeon where the collision is defined by a circle radius as part of the object definition in the DOF.

[Andrej730]

Thanks for the detailed answer, it's really helpful.

What OutlineLookupGrid is used for and how do I generate it?
For example I have nav mesh from the screenshot - how do I derive LookupGrid from that? (btw this shape is w_cd_bigtortoise01.bms). Original bms grid has 16 cells each formed out of 1 or more outline edges.

Other thing I've noticed some .bms use for OutlineLookupGrid 1 cell formed out of all outline edges (like "rock_mt_house07_01.bms" from the screenshot below).
And the question is when that simple 1 cell grid is enough and when I need to go more complex?

[DummkopfOfHachtenduden]

The OutlineLookupGrid is an a grid based acceleration structure to reduce the amounts of tests you have to perform.

Every object has it's own grid and they look somewhat like this.
Every cell is 100x100 units so the width and height (in cells) is therefore determined by the NavMesh size.
Every cell stores the outline edges that overlap (intersecting/fully contained) with it.
If the object is small enough to fit into a single cell then it obviously contains all outline edges.

It's used when testing for collision with an object from outside (standing on NavMeshTerrain).
Instead of testing every outline edge of the object against your ray, you check which cells of the outline lookup grid your ray intersects with first. Then check those outline edges within the cells you intersected with for an intersection with your ray.

Joymax's cell test is rather inefficient on bigger objects as you can see here:

I'd suggest for a more optimized test like this:

To create the grid itself you'd just create an AABB based on all vertices and inflate it to the next multiple of 100 in both axis.
That way you can calculate the width and height in cells and also know the origin as it should be the AABBs min.

[Andrej730]

1. What if I just always use 1 cell even if object is 1000x1000? It won't be efficient since it's going to check all outline links all the time but it would work?
2. What about outline links that fall in multiple cells - they should be enlisted in all cells they intersect? Like edge 1 should be added to both cells 0 and 4.