KCL (File Format)

From Custom Mario Kart
Jump to navigation Jump to search

KCL Files are collision files used in Mario Kart Wii and many other games. They have been used since at least Mario Kart DS. The documentation here is specifically for the Mario Kart Wii implementation, although other implementations are likely to be similar.
The KCL files contain simplified versions of model files in order to allow rapid collision detection. They use an octree for efficient spatial indexing, as well as storing the actual triangles of the models in a more rapidly accessible format.

File Format

The basic file format consists of a header, and four data sections.

Header

The header is a 0x38 or 0x3c byte structure as follows.

Offset Type Name Description
0x00 u32 pos_data_offset 0-indexed offset to pool of position vectors.
0x04 u32 nrm_data_offset 0-indexed offset to pool of normal vectors.
0x08 u32 prism_data_offset 1-indexed offset to pool of triangular prisms.
0x0c u32 block_data_offset Offset to collision octree.
0x10 f32 prism_thickness Depth of a triangular prism along its normal vector.
0x14 Vec3 area_min_pos Spatial grid first coordinate.
0x20 u32 area_x_width_mask X mask.
0x24 u32 area_y_width_mask Y mask.
0x28 u32 area_z_width_mask Z mask.
0x2c u32 block_width_shift Coordinate shift.
0x30 u32 area_x_blocks_shift Y shift.
0x34 u32 area_xy_blocks_shift Z shift.
0x38 f32 OPTIONAL[ sphere_radius ] Maximum radius of a sphere that can be collided with this file. This field must be used when computing the octree; e.g., to consider which triangles are inside an octree 32x32 block, it is insufficient to just consider a 32x32 cube since it would miss prisms a player could hit while being on the edge of the box. Therefore, it is necessary to consider a distance field with constant distance of sphere_radius. From analysis of official files, this is not just a larger cube, but actually a curvy, beveled figure (especially noticeable with small cubes where sphere_radius > width). Official tools will only include prisms that are actually reachable in leaf nodes which produces more efficient files than homebrew. This field is not provided by KCL files from Super Mario Galaxy/other platformers. Therefore, using those tools for KCL may be problematic as Mario Kart Wii expects this value.

All offsets are relative to the start of the file.
The meaning of the shift and mask values is explained in section 4.

An official KCL generation algorithm can be observed in Super Mario Galaxy's DynamicCollisionObj::updateCollisionHeader(). A decompilation is provided below:

void DynamicCollisionObj::updateCollisionHeader()
{
  Vec min, max, extent;
  int masks[3];
  int extent_int_x, extent_int_y, extent_int_z;
  int max_entropy = 0, component = 0, component_ = 0, bits_sel, mask_sel, i, v8, bit_shift, area_y_width_mask, area_z_width_mask;

  // Compute bounding box and extent
  MR::createBoundingBox(this->mVertices, this->mNumVertices, &min, &max);
  JGeometry::TVec3<f>::TVec3<f>(&extent, &max);
  JGeometry::TVec3<f>::__ami(&extent, &min);

  // Initialize masks with extent
  extent_int_x = (int)extent.x;
  extent_int_y = (int)extent.y;
  extent_int_z = (int)extent.z;
  masks[0] = extent_int_x;
  masks[1] = extent_int_y;
  masks[2] = extent_int_z;
  if ( !extent_int_x ) masks[0] = 1;
  if ( !masks[1] ) masks[1] = 1;
  if ( !masks[2] ) masks[2] = 1;

  // Find highest number of bits to shift
  for (component = 0; component < 3; ++component)
  {
    bits_sel = 0x80000000;
    mask_sel = 0xFFFFFFFF;
    i = 0;
    v8 = 32;
    while ( (masks[component] & bits_sel) == 0 )
    {
      bits_sel >>= 1;
      mask_sel >>= 1;
      ++i;
      if ( !--v8 )
        goto CONTINUE;
    }
    masks[component] = ~mask_sel;
    if ( max_entropy < i )
      max_entropy = i;
    CONTINUE:;
  }

  // Update header fields
  bit_shift = 33 - max_entropy;
  area_y_width_mask = masks[1];
  this->mpHeader->area_x_width_mask = masks[0];
  area_z_width_mask = masks[2];
  this->mpHeader->area_y_width_mask = area_y_width_mask;
  this->mpHeader->area_z_width_mask = area_z_width_mask;
  this->mpHeader->block_width_shift = bit_shift;
  JGeometry::TVec3<f>::__as(&this->mpHeader->area_min_pos, &min);
}

Section 1 - Position Vectors

Section 1 is simply a large array of position vectors, stored as 3 successive floats for X, Y and Z. The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 2 from the start of Section 1; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the prisms list and keep track of the highest position index.

Section 2 - Normals

Section 2 is much the same as section 1, in that it is a large array of normal vectors. Again the values are stored as 3 successive floats for X, Y and Z. The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 3 from the start of Section 2; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the prisms list and keep track of the highest normal index across every field (face normals + edge normals).

Section 3 - Triangular Prisms

The third section is a pool of triangular prisms encoded as face normal vectors and a height. The offset to this section is stored as 0x10 less than the actual location of the data because this section is one indexed in section 4. The structure of each entry in this section is a 0x10 byte structure given below.

The length of this array is not stored. Do not compute the size of this section by subtracting the address of Section 4 from the start of Section 3; these sections may appear in any order. You may compute an upper bound by sorting a list containing all section offsets and the filesize; to actually determine the size of this section, though, you must parse the octree and keep track of the highest prism index.

Offset Type name Description
0x00 f32 height Length.
0x04 u16 pos_i Position index (0 based index into section 1).
0x06 u16 fnrm_i Face normal vector index (0 based index into section 2).
0x08 u16 enrm1_i First edge normal vector (in counterclockwise order) -- Normal A index (0 based index into section 2).
0x0a u16 enrm2_i Second edge normal vector (in counterclockwise order) -- Normal B index (0 based index into section 2).
0x0c u16 enrm3_i Third edge normal vector (in counterclockwise order) -- Normal C index (0 based index into section 2).
0x0e u16 attribute Collision attribute. In Super Mario Galaxy, this is an attribute *index* into an Attribute Lookup Table. In Mario Kart Wii, the attribute is stored directly in prisms.

All indices in this section are 0 indexed. The position index is an index for section 1, and the others are indices to section 2. The coordinate system is right handed.

The decoding algorithm can be seen in Mario Kart 7's KDGndCol::PolygonMesh::parseModel(const KDGndCol::KColData&, bool). It is described below:

CrossA  = cross(enrm1, fnrm)
CrossB  = cross(enrm2, fnrm)
Vertex1 = pos
Vertex2 = pos + CrossB * (height / dot(CrossB, enrm3))
Vertex3 = pos + CrossA * (height / dot(CrossA, enrm3))

An encoding algorithm can be seen in Super Mario Galaxy's DynamicCollisionObj::updateTriangle(). A method for converting three vertices into the KCL form is given below. One approach is described below: (this assumes vertices are arranged counter-clockwise when viewed from their front side)

pos    = Vertex1
fnrm   = normalize(cross( Vertex2 - Vertex1, Vertex3 - Vertex1 ))
enrm1  = normalize(cross(fnrm, Vertex3 - Vertex1))
enrm2  = normalize(-cross(fnrm, Vertex2 - Vertex1))
enrm3  = normalize(cross(fnrm, Vertex2 - Vertex3))
Length = dot(Vertex2 - Vertex1, enrm3)

Section 4 - Spatial Index

Section 4 is a spatial index. It is a series of u32 values, followed by lists of u16s. It subdivides three dimensional space using an octree, and indicates which triangles from section 3, if any, appear in each cube of the space. Given a coordinate (x,y,z) in world space, in order to find which triangles are at in range of that location, the spatial grid first coordinate is subtracted from the coordinate. If the value is negative, it is not colliding. If the value is positive, it is rounded to a u32, and then each component is AND'ed with the mask. If the value is non-zero, it is also not colliding. If not, then the original u32 components are all shifted right by coordinate shift. The Y and Z coordinates are then shifted left by their shift values. The resulting components are OR'ed with each other to produce an index into the octree.

The octree is then to be followed until a triangle list is found. At each stage, if the top bit of the current u32 is set, then the remaining 31 bits are an offset to a list of u16 triangle indices. Each of these is a 1-based index to section 3, which is a triangle that must be checked by an object at the original location. The first entry of a list is always 0, which serves as a 0 termination for the previous list. If the top bit is not set, then the remaining 31 bits are an offset to 8 more of the u32s in the octree. The index into these 8 values is calculated by getting the next least significant bit in the u32 of each component, and then shifting Z left by 2, Y left by 1 and OR'ing them all together. The procedure then repeats with the value at that offset.

An algorithm is provided below:

// This function searches a tree structure to find the node containing
// the input point (x, y, z).
// The tree structure is stored in the 
// "Info" structure pointed to by "info".
u32 narrowAABB(Info *info, float *point) {
    // Calculate the x, y, and z offsets of the point from the minimum
    // corner of the tree's bounding box.
    u32 x = (u32)(point[0] - info->area_min_pos[0]);
    u32 y = (u32)(point[1] - info->area_min_pos[1]);
    u32 z = (u32)(point[2] - info->area_min_pos[2]);

    // Check if the point is outside the tree's bounding box in the x, y,
    // or z dimensions. If it is, return 0.
    if ((x & info->area_x_width_mask) != 0 ||
        (y & info->area_y_width_mask) != 0 ||
        (z & info->area_z_width_mask) != 0)
    {
        return 0;
    }

    // Initialize the current tree node to the root node of the tree.
    u32 curBlock - info->block_data_offset;

    // Traverse the tree to find the leaf node containing the input point.
    for (int i = 4 * ((x >> info->block_width_shift) |
                     (z >> info->block_width_shift << info->area_xy_blocks_shift) |
                     (y >> info->block_width_shift << info -> area_x_blocks_shift));
        ;
        i = 4 * ((x >> info->block_width_shift) & 1 |
                (2 * (y >> info->block_width_shift)) & 2 |
                (4 * (z >> info->block_width_shift)) & 4 & 0xFFFFFFFE) )
    {
        // Get the offset of the current node's child node.
        s32 offset = *(s32 *)(curBlock + 1);

        // If the offset is negative, the current node is a leaf node.
        if (offset < 0)
        {
            break;
        }

        // If the offset is non-negative, update the current node to be
        // the child node and continue traversing the tree.
        --info->block_width_shift;
        curBlock += offset;
    }

    // Return the address of the leaf node containing the input point.
    return curBlock + (offset & 0x7FFFFFFF);
}

Tools

The following tools can handle KCL files: