.CTR -- Terrain Octree Cube Tree

1. Architectural Role & Engine Purpose

The CTR (Collision Tree / Octree File) format stores spatial partitioning octrees and triangle collision boundaries for 3D structures, fences, guard towers, and buildings in Project I.G.I. 1.

CTR files accelerate line-of-sight raycasts, bullet penetration checks, and player collision queries from O(N) triangle tests to O(log N) hierarchical octree traversals. Nodes are stored as contiguous 32-byte structs (ctr_item_s).

2. Binary File Layout & Memory Map Diagram

A CTR file contains an octree descriptor header, followed by the node array and polygon triangle index lists:

3. Collision Raycast & Octree Traversal Pipeline Diagram

When checking whether an AI guard can see David Jones or when tracing bullet trajectories, the engine traverses the CTR tree:

4. Architectural Mechanics & Engine Implementation Details

The CTR octree architecture is designed for zero recursion overhead:

• Fixed-Depth Local Stack: Traversal uses a pre-allocated flat stack array of 32 node indices, eliminating recursive function call overhead on Intel Pentium III CPUs.
• 32-Byte Cache Alignment: Exactly two ctr_item_s node descriptors fit into a standard 64-byte CPU cache line, maximizing memory prefetching efficiency during rapid raycast testing.

5. C++ Struct Definitions

#pragma pack(push, 1)
struct CtrHeader {
    char     magic[4];       // "CTR "
    uint32_t version;        // Octree version
    uint32_t node_count;     // Total octree nodes
    uint32_t index_count;    // Total triangle references
    float    root_center[3]; // Bounding center of entire structure
    float    root_extents[3];// Half-sizes XYZ
};
static_assert(sizeof(CtrHeader) == 36, "CtrHeader must be 36 bytes");

// IGI 1 32-Byte Octree Node Descriptor
struct ctr_item_s {
    float    center[3];      // Center of this octree box
    float    extents[3];     // Half-size of this octree box
    int16_t  child_index;    // Index to first child (8 contiguous children), or -1
    uint16_t poly_offset;    // Offset in polygon index array
    uint16_t poly_count;     // Number of triangles in this leaf
    uint16_t flags;          // 0=Branch, 1=Leaf
};
static_assert(sizeof(ctr_item_s) == 32, "ctr_item_s must be 32 bytes");
#pragma pack(pop)