TriColl

[snake-biscuits]

What is TriColl?

Triangle Collision data, for non-brushwork surfaces.
TriColl lumps are used in respawn.titanfall & respawn.titanfall2 (deprecated in apex_legends)
Presumably compiled from patches, misc_model & other non-brush geo
In Titanfall, most Tricoll is used for terrain, other examples include curved building exteriors on Runoff
In Titanfall 2, maps are mostly made of TriColl (curved surfaces, more terrain. complex bespoke geo)

Porting

Attempting to port Titanfall maps to Titanfall 2, we have found crashes when players touch TriColl geo
The logs indicate some out of bounds indexing
All we know for sure if that the lumps have changed.

Lumps

TRICOLL_TRIANGLES = 0x0042
TRICOLL_NODES = 0x0044
TRICOLL_HEADERS = 0x0045
TRICOLL_BEVEL_STARTS = 0x0060
TRICOLL_BEVEL_INDICES = 0x0061

Connections

              /-> TextureData
             /-> Vertices
TricollHeader -> TricollTriangle -> Vertices
            \--> TricollNode -> TricollNode? / ???
             \-> TricollBevelIndices? -?> ?

TricollBevelStarts is parallel w/ TricollTriangles

[snake-biscuits]

RoyalBlue in the Northstar Discord recently figured out TricollTriangles & how they index vertices

struct TricollTriangle {
  uint32_t A: 10;  // indexes header.first_vertex + A
  uint32_t B: 7;   // indexes header.first_vertex + A + B
  uint32_t C: 7;   // indexes header.first_vertex + A + C
  uint32_t flags: 8;  // tracks a lot of state. e.g. longest axis, orientation
}

Flags will probably take lots of visualising & cataloguing to pin down

[snake-biscuits]

Coliseum TriCollTriangles visualised

IIRC the top cylinder is a static prop

[snake-biscuits]

Filtering by TricollTriangle.flags
1<<5 set

1<<4 set

[snake-biscuits]

All screenshots were posted by RoyalBlue to the Northstar Discord's map research thread

[snake-biscuits]

@r-ex provided structs a while back identifying TricollHeader¹ & TricollNode²
These have since moved to bsp_tool_examples³

TricollHeader

struct TricollHeader {
  int16_t flags;  // always 0?
  int16_t texture_flags;  // copy of flags from indexed TextureData
  int16_t texture_data;  // TextureData; surfaceproperty for sounds & texture for decals / impact fx
  int16_t num_vertices;  // number of Vertices
  int16_t num_triangles;  // number of TricollTriangles
  int16_t num_bevel_indices;  // number of TricollBevelIndices (unsure of format & purpose)
  int32_t first_vertex;  // added TricollTriangle.A etc. to calculate indices into Vertices
  int32_t first_triangle;  // first TricollTriangle
  int32_t first_node;  // first TricollNode; search the tree until it terminates?
  int32_t first_bevel_index;  // first TricollBevelIndex
  Vector  origin;  // ??? copied from misc_model?
  float   scale;  // ??? copied from misc_model?
};

TricollNode

struct TricollNode {
  struct { int16_t x, y, z; } mins;
  struct { int16_t x, y, z; } maxs;  // doesn't look like origin & extents
  int16_t unknown[2];  // indexed children w/ -ve indices for leaves/triangles?
};

size derived from TricollHeader indices into the lump
IDK how TricollNode is stepped
unsure of how it's split, seems to use +ve/-ve as a switch to indicate indexed type (another node / terminating leaf)
rexx' structs do also include TricollLeaf, could index triangles?
no TricollLeaf lump exists, but lump 0043 (67) could've been TricollLeaf in pre-release Titanfall

Footnotes

1. bsp_tool_examples on GitHub: dtricollheader_t ↩

2. bsp_tool_examples on GitHub: dtricollnode_t ↩

3. bsp_tool_examples on GitHub: structs_r1.h ↩

[snake-biscuits]

pre-release Titanfall

Just remembered that while we do have Titanfall 2's Tech Test archived, we don't have Titanfall 1's

[snake-biscuits]

Interesting Patterns

The first TricollHeader will start at first_vertex=1; probably because VERTICES[0] is always <0, 0, 0>
Tricoll Vertex positions are the first emitted (after <0, 0, 0>)
Mesh order seems unrelated (meshes are sorted for transparency reasons so not unusual)

When looking for a Mesh w/ the same tris as a TricollHeader, I noticed not every MaterialSort is indexed by Meshes

>>> sorted({m.material_sort for m in box.MESHES})
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 27, 28]
>>> len(box.MATERIAL_SORT)
29

NVM I found some

>>> box.TRICOLL_HEADERS[0].texture_data, box.TEXTURE_DATA_STRING_DATA[box.TEXTURE_DATA[11].name_index]
(11, 'WORLD\\DEV\\WEAPON_RANGE_TARGET')
>>> [i for i, ms in enumerate(box.MATERIAL_SORT) if ms.texture_data == 11]
[9, 10]
>>> [i for i, m in enumerate(box.MESHES) if m.material_sort in (9, 10)]
[9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27]

[snake-biscuits]

I can see these matching some TricollHeaders

>>> {print(f"{i:02d}", sorted({v.position_index for v in box.vertices_of_mesh(i)})) for i in range(9, 28)}
09 [57, 58, 59, 60]
10 [25, 26, 27, 28]
11 [37, 38, 39, 40]
12 [533, 534, 563, 564]
13 [1, 2, 3, 4]
14 [13, 14, 15, 16]
15 [9, 10, 11, 12]
16 [5, 6, 7, 8]
17 [21, 22, 23, 24]
18 [17, 18, 19, 20]
19 [29, 30, 31, 32]
20 [61, 62, 63, 64]
21 [33, 34, 35, 36]
22 [45, 46, 47, 48]
23 [65, 66, 67, 68]
24 [41, 42, 43, 44]
25 [53, 54, 55, 56]
26 [69, 70, 71, 72]
27 [49, 50, 51, 52]

[snake-biscuits]

R2 tricoll nodes have been visualised by RoyalBlue
Apparently r1 nodes do not render properly

[snake-biscuits]

2 * (T -(T + 3) % 6 + 3) / 3 where T is the number of triangles in a given TricollHeader is used to count the number of nodes
The math here seems similar to calculating lump sizes (rounding & snapping)
some variants use imul & 0xAAAAAAAAAAAAB (two thirds)

[snake-biscuits]

Tricoll crashes in ported maps (r1 -> r2) seems to happen in a function that looks up Tricoll bevels

[snake-biscuits]

Earls' Extreme SIMD References¹²

Footnotes

1. Efficient Ray Tracing Kernels for Modern GPU Architectures Fuetterling ↩

2. Fast and Robust Triangle-Triangle Overlap Test using Orientation Predicates Guigue & Devillers ↩

[snake-biscuits]

I definitely the tail end of the talk where he discusses triangle collision testing relates to Tricoll
stuff about falling in cracks¹ (bevels, could be related to r1o physics bugs)

The SIMD & branchless stuff also seems to line up w/ the arcane magicks in the tricoll funcs RoyalBlue located

Footnotes

1. 3kliksphillip on YouTube: Dust2's Black Hole Investigated ↩

[snake-biscuits]

Cleaned up snippet of a TricollBevelIndices function RoyalBlue shared a screenshot of:

// data collection
low_11_bits = v70 & 0x7FF;
bitsRead += 11;  bevelReadData.buffer = bevelReadData.buffer >> 11;
if (bitsRead >= 32) {  // need more data?
    bevelReadData.buffer |= static_cast<uint64_t>(lumpCursor->val) << (64 - bitsRead);
    bevelReadData.bitsReadFromBuffer = bitsRead - 32;
    lumpCursor++;  bevelReadData.fillBuffer = &lumpCursor->val;
}

high_11_bits = bevelReadData.buffer & 0x7FF;
bitsRead += 11;  bevelReadData.buffer = bevelReadData.buffer >> 11;
bevelReadData.bitsReadFromBuffer = bitsRead;
if (bitsRead >= 32) {  // need more data?
    bevelReadData.buffer |= static_cast<uint64_t>(lumpCursor->val) << (64 - bitsRead);
    bevelReadData.bitsReadFromBuffer = bitsRead - 32;
    lumpCursor++;  bevelReadData.fillBuffer = &lumpCursor.val;
}

// processing
full_22_bits = (high_11_bits << 11) | low_11_bits;
bevelCount   = full_22_bits & 0x7F;  //  7 from the bottom
tricollIndex = full_22_bits >> 7;    // 15 from the top
v85 = a1->tricollPointer[tricollIndex];
v86 = v85->num_triangles;
// get the node of our TricollTriangle
v87 = static_cast<TricollTriangle*>(v86 > 3 ? &v85->Nodes[(4 * (v86 - (v86 + 3) % 6 + 5)/ 2) / 3]
                                            : &v85->Nodes[0]);
if(!getBeveIndices(a6, a11, v87, v85, bevelCount, a7, v60, &bevelReadData)) {
    return;
}

v60 += bevelCount;
if (v85 == tricoll) { goto LABEL_80; }  // keep looking?
// resetting? setting up a jump back?
// probably reflects what these vars are used before where we start
v69 = static_cast<TricollBevelIndices*>(bevelReadData.fillBuffer);
v64 = bevelReadData.bitsReadFromBuffer;
v70 = bevelReadData.buffer;

So each bevel is a stream of 11-bit numbers, starting with a 22-bit header split into 15 & 7 bits
The getBevelIndices function apparently collects bevelCount 11-bit indices into TricollTriangles
v87 determines the TricollNodes index of the target triangle
IIRC the indices into TricollBevels start on 32-bit boundaries

Have yet to add a branch script method for parsing this data

[snake-biscuits]

Titanfall & Titanfall: Online use 10-bit bevel indices
Header is a 20-bit 13:7, order of index & count might also be flipped

[snake-biscuits]

Might be possible to treat TricollBevelIndices as a SpecialLumpClass
Calculating indices into the lump would be difficult though

[snake-biscuits]

Mostly have the formats & relations worked out now, but need to bring the relevant math / functions to python

             /-> TextureData
            /--> Vertices
TricollHeader -> TricollTriangle -> Vertices
            \--> TricollNode -> TricollNode / TricollTriangle
             \-> TricollBevelIndices -> TricollTriangle
                                    \-> TricollNode

TricollBevelStarts -> TricollBevelIndices

TricollBevelStarts is parallel w/ TricollTriangles

TricollBevel* system is for indexing abutting triangles, to handle "seams" caused by rounding errors

Also having trouble trying to port r1 Tricoll to r2, need to convert TricollBevelIndices

[snake-biscuits]

TricollHeader’s num_bevel_indices member seems to count the number of 10/11 bit numbers (r1/r2)
so to get the number of bytes needed, num_ / 3.2 for r1 & num_ / 2.91 (2 + 10/11) for r2

TricollBevelStarts appears to index the starting uint32_t of a given TriCollTriangles BevelIndices
As an offset from header.first_bevel_index (which indexes the lump as uint32_t)