Straddle groups

[snake-biscuits]

Rough Summary

A GeoSet contains a group of physics objects (Primitives)
The "grouping" is done with the common .first_X, .num_X system
Each Primitive appears only once, but GeoSets appear multiple times

NOTE: GeoSets can also embed a single Primitive within themselves

Grid & GridCells index GeoSets a few spans at a time
This means some GeoSets are duplicates
Each duplicate has the same straddle_group value
Seems to be an ID to aid with caching GeoSets
I haven't done any reverse engineering of engine .dlls to confirm this

Grid.num_straddle_groups matches the maximum straddle_group value + 1
A value of 0 is commonly used for GeoSets with no duplicates (unique to their parent GridCell)

NOTE: A map with a Grid.num_straddle_groups value that is too low will run in Northstar
-- spawned players are frozen in place without crashing

Lump Relationships

Grid -> GridCell -> GeoSet -> Primitive
                                                          
         /-> UniqueContents
Primitive -> .type -> Brush OR Tricoll OR StaticProp
                                                          
GeoSets can contain duplicates (use same .straddle_group)
GeoSets is parallel w/ GeoSetBounds
Primitives is parallel w/ PrimitiveBounds
PrimitiveBounds & GeoSetBounds use the same "Bounds" type

NOTE: TricollNodes also uses the same "Bounds" type (Oriented)
-- Brushes also use a .origin + .extents model to define their bounds (Axis-Aligned)

[snake-biscuits]

Afaik there's nothing in the bsp to say which GridCells each straddle group connects
Presumably each straddle group covers a unique combination of GridCells

It's worth noting that some maps use the Models[0] GridCell
This doesn't make much sense to me, as the base grid should cover all worldspawn geo

[F1F7Y]

From limited testing the Models[0] is used for the skybox which somewhat makes sense. The skubox is usually way larger than the map so including it in the grid would result in a lot of GridCells which only index the skybox.

[snake-biscuits]

Huh, makes sense, tho I wonder how they isolate skyboxes.
In my recent dig through r1 & r2 squirrel I noticed some dedicated sky_camera names:
skybox_cam_level, skybox_cam_intro & skybox_cam_intro2
intro & intro2 are marked as MILITIA & IMC in r1/scripts/vscripts/mp_outpost_207_shared.nut

AFAIK source build separate vis tree around world origin / the first indexed player spawn, then the sky cameras
visleaves would have flags for sky visibility which links the to some PVS in the skybox
You could do some stuff with a map in source where you teleport between disconnected rooms tho...

This'll probably come up again when I tackle skybox vis w/ portals in #84

[snake-biscuits]

You could do some stuff with a map in source where you teleport between disconnected rooms tho...

Maybe we should look at how Effect & Cause physics works
I know they leverage the minecraft chunk style-loading of gridcells for fast physics,
but what about vis and asset caching?
IIRC there's some .stbsp sampling bounds that stretch across both map instances
VIS could be interesting

[snake-biscuits]

Straddle group 0 might be just for Primitives & GeoSets contained to one GridCell, idk.
Unless other maps index GridCell[-1]

[F1F7Y]

GeoSets indexed by model GridCells use Straddle group 0. My best guess is that as the name implies a geosets which "straddle" accross multiple gridcells share the same straddle group.
Might try to test this theory today.

[snake-biscuits]

>>> bsp = maps["mp_glitch"]
>>> [i
...  for i, gc in enumerate(bsp.CM_GRID_CELLS)
...  for gs in bsp.CM_GEO_SETS[gc.first_geo_set:gc.first_geo_set+gc.num_geo_sets]
...  for p in bsp.CM_PRIMITIVES[gs.primitive.index:gs.primitive.index+gs.num_primitives]
...  if p.type.name == "PROP"][:4]
[559, 559, 559, 560]
>>> bsp.CM_GRID_CELLS[559]
<GridCell (first_geo_set: 74, num_geo_sets: 1)>
>>> bsp.CM_GEO_SETS[74]
GeoSet(
    straddle_group=242, num_primitives=4,
    primitive=<BitField (type: <PrimitiveType.BRUSH: 0>, index: 80, unique_contents: 6)>)
>>> bsp.CM_PRIMITIVES[80:80+4]
[<Primitive (type: <PrimitiveType.TRICOLL: 64>, index: 223, unique_contents: 6)>,
 <Primitive (type: <PrimitiveType.PROP: 96>, index: 29, unique_contents: 6)>,
 <Primitive (type: <PrimitiveType.PROP: 96>, index: 906, unique_contents: 6)>,
 <Primitive (type: <PrimitiveType.PROP: 96>, index: 905, unique_contents: 6)>]

that's a really cool GeoSet, captures a TriColl & 3 props

>>> {bsp.GAME_LUMP.sprp.model_names[bsp.GAME_LUMP.sprp.props[i].model_name] for i in (29, 906, 905)}
{'models/foliage/tree_cherry_blossom_large_01.mdl',
 'models/homestead/rock_cluster_basalt_01_wet_sm.mdl'}

>>> [i
...  for i, gc in enumerate(bsp.CM_GRID_CELLS)
...  if 74 in [*range(gc.first_geo_set,gc.first_geo_set+gc.num_geo_sets)]]
[559, 560, 561, 600]
>>> bsp.CM_GEO_SETS[74].straddle_group  # 1st geo set w/ props
242
>>> [i
...  for i, gc in enumerate(bsp.CM_GRID_CELLS)
...  for gs in bsp.CM_GEO_SETS[gc.first_geo_set:gc.first_geo_set+gc.num_geo_sets]
...  if gs.straddle_group == 242]
[559, 560, 561, 562,
      600, 601, 602, 603, 604,
           641, 642, 643, 644, 645,
                     683, 684, 685, 686,
                               725, 726, 727, 767, 768]

>>> bsp.CM_GRID_CELLS[601]
<GridCell (first_geo_set: 148, num_geo_sets: 3)>
>>> bsp.CM_GEO_SETS[148:148+3]
[GeoSet(straddle_group=242, num_primitives=4, ..., index: 80, unique_contents: 6),  # clone of 74
 GeoSet(straddle_group=312, num_primitives=4, ..., index: 100, unique_contents: 6),
 GeoSet(straddle_group=506, num_primitives=2, ..., index: 104, unique_contents: 1)]
 
>>> {gs for gs in bsp.CM_GEO_SETS if gs.straddle_group == 242}
{GeoSet(straddle_group=242, num_primitives=4, primitive=<BitField (type: <PrimitiveType.BRUSH: 0>, index: 80, unique_contents: 6)>)}

[snake-biscuits]

clearly straddle_group 242 is the same GeoSet
it gets copied for each GridCell that needs to index other GeoSets

in every single map, there is only 1 Primitive per static prop
so GeoSets need to grab a sequence of props that appear in roughly the same area

straddle_group 243 shares GridCell 767 w/ straddle_group 242

[snake-biscuits]

bsp_regen should try to use a similar system for grouping props

[snake-biscuits]

looking at r2 mp_glitch GridCell 6 (GeoSet 3244 / Straddle Group 432)

GeoSetBounds wraps the TriColl (568), while PrimitiveBounds (5999) is at a 45 degree angle
The triangular pocket this outlines is really tight, any ray test is highly unlikely to fail

bsp_regen is far lazier in it's approach, using an AABB for each level & wrapping the GeoSetBounds around it's child PrimitiveBounds

Idk what kind of algorithm respawn developed to get this combination of YOBBs to create such a tight hull, but it's very cool
When I first visualised the bounds I was confused by the PrimitiveBounds not being fully contained in GeoSetBounds

Also worth noting that Tricoll has it's own tree of TricollNodes to minimise the number of tests for a ray miss

[snake-biscuits]

"Graze" seems like a good word for near-hits
when the game engine gets partway through testing a BVH tree before recognising the miss

[snake-biscuits]

looks like really big GeoSets end up in the GridCell for Models[0] (worldspawn)

>>> import bsp_tool
>>> bsp = bsp_tool.load_bsp("E:/Mod/Titanfall2/maps/mp_glitch.bsp")
>>> bsp.grid_cell_primitives(1806)
[(<Primitive (type: <PrimitiveType.BRUSH: 0>, index: 12, unique_contents: 0)>,
  Bounds(origin=vec3(-6200.0, -1488.0, 1284.0), negative_cos=-32768, extents=vec3(2009.0, 4033.0, 1276.0), positive_sin=0)),
 (<Primitive (type: <PrimitiveType.BRUSH: 0>, index: 285, unique_contents: 0)>,
  Bounds(origin=vec3(5816.0, 1744.0, 1284.0), negative_cos=-32768, extents=vec3(2009.0, 4033.0, 1276.0), positive_sin=0)),
 (<Primitive (type: <PrimitiveType.BRUSH: 0>, index: 286, unique_contents: 0)>,
  Bounds(origin=vec3(2048.0, 4240.0, 1262.0), negative_cos=-32768, extents=vec3(1761.0, 1521.0, 1298.0), positive_sin=0)),
 (<Primitive (type: <PrimitiveType.PROP: 96>, index: 16182, unique_contents: 6)>,
  Bounds(origin=vec3(-1503.0, -3865.0, 5299.0), negative_cos=-31384, extents=vec3(4060.0, 7604.0, 5489.0), positive_sin=9423)),
 ...]

the 1 prop:

>>> bsp.GAME_LUMP.sprp.props[16182]
StaticPropv13(
    origin=vec3(0.0, 0.0, 0.0), angles=<MappedArray (y: 0.0, z: 90.0, x: 0.0)>, scale=1.0,
    model_name=27, solid_mode=<StaticPropCollision.VPHYSICS: 6>, flags=<StaticPropFlags.NO_DRAW: 4>, skin=0, cubemap=1,
    forced_fade_scale=-1.0, lighting_origin=vec3(nan, 34.12068176269531, 16.043363571166992),
    cpu_level=<MappedArray (min: -1, max: -1)>, gpu_level=<MappedArray (min: -1, max: -1)>,
    diffuse_modulation=<RGBExponent (r: 0, g: 0, b: 0, exponent: 0)>, collision_flags=<MappedArray (add: 0, remove: 0)>)
>>> bsp.GAME_LUMP.sprp.model_names[27]
'models/levels_terrain/mp_glitch/glitch_godrays.mdl'

[snake-biscuits]

that nan in lighting_origin.x is concerning

[snake-biscuits]

Worth noting that the brush indices jump around a lot
GeoSets are definitely ordered by unique_contents within each GridCell

I initially thought that brushes were ordered by gridcell, but that was me misreading GeoSets
Since GeoSet.primitive looks like it's indexing brushes when it's actually indexing Primitives

[snake-biscuits]

>>> import bsp_tool
>>> bsp = bsp_tool.load_bsp("E:/Mod/Titanfall2/maps/mp_glitch.bsp")
>>> bsp.CM_GRID.count.x * bsp.CM_GRID.count.y
1806
>>> min([gs.first_geo_set for gs in bsp.CM_GRID_CELLS[:1806] if gs.num_geo_sets > 0])
0
>>> max([gs.first_geo_set + gs.num_geo_sets for gs in bsp.CM_GRID_CELLS[:1806] if gs.num_geo_sets > 0])
3246
>>> gridcell_geosets = set()
>>> for grid_cell in bsp.CM_GRID_CELLS[:1806]:
...    if grid_cell.num_geo_sets > 0:
...        start = grid_cell.first_geo_set
...        end = start + grid_cell.num_geo_sets
...        gridcell_geosets.update({*range(start, end)})
... 
>>> {*range(3246)}.difference(gridcell_geosets)
{3229, 3230, 3231, 3232, 3233, 3234, 3235, 3236, 3237, 3238, 3239, 3240, 3241, 3242, 3243}
>>> bsp.CM_GRID_CELLS[1806:]
[<GridCell (first_geo_set: 3229, num_geo_sets: 15)>]

[snake-biscuits]

mp_glitch GridCell[1806] has a bunch of big GeoSets, but those GeoSets aren't all after the main grid

[snake-biscuits]

notable:

>>> {gc.first_geo_set for gc in bsp.CM_GRID_CELLS if gc.num_geo_sets == 0}
{3244, 3245, 3246}

[snake-biscuits]

grid cells (+ indices) containing straddle_group 432:

[(gc, i)
 for i, gc in enumerate(bsp.CM_GRID_CELLS)
 if 432 in [
     gs.straddle_group
     for gs in bsp.CM_GEO_SETS[gc.first_geo_set:gc.first_geo_set+gc.num_geo_sets]]]

[snake-biscuits]

GeoSets always share the UniqueContents of their child Primitives in retail r1 & r2
Unlike r5 (afaik)

>>> import bsp_tool, os, fnmatch
>>> md = "E:/Mod/Titanfall/maps/"
>>> maps = {fn[:-4]: bsp_tool.load_bsp(os.path.join(md, fn)) for fn in fnmatch.filter(os.listdir(md), "*.bsp")}
>>> all({gs.primitive.unique_contents} == {p.unique_contents for p, b in bsp.geo_set_primitives(i)}
...     for bsp in maps.values()
...     for i, gs in enumerate(bsp.CM_GEO_SETS))
True
>>> md = "E:/Mod/Titanfall2/maps/"
>>> maps = {fn[:-4]: bsp_tool.load_bsp(os.path.join(md, fn)) for fn in fnmatch.filter(os.listdir(md), "*.bsp")}
>>> all({gs.primitive.unique_contents} == {p.unique_contents for p, b in bsp.geo_set_primitives(i)}
...     for bsp in maps.values()
...     for i, gs in enumerate(bsp.CM_GEO_SETS))
True

[snake-biscuits]

Mixing UniqueContents could cause issues when creating maps
The game engine could be making assumptions based on this pattern

This is important for bsp_regen & MRVN-Radiant