KCL (File Format)

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 array of position vectors.
0x04	u32	nrm_data_offset	0-indexed offset to array of normal vectors.
0x08	u32	prism_data_offset	1-indexed offset to array of triangular prisms.
0x0c	u32	block_data_offset	Offset to collision octree blocks.
0x10	f32	prism_thickness	Depth of a triangular prism along its normal vector.
0x14	Vec3	area_min_pos	Smallest possible coordinate in the model
0x20	u32	area_x_width_mask	X mask. X coordinates with bits outside this mask are outside the model (See section 4)
0x24	u32	area_y_width_mask	Y mask. Y coordinates with bits outside this mask are outside the model (See section 4)
0x28	u32	area_z_width_mask	Z mask. Z coordinates with bits outside this mask are outside the model (See section 4)
0x2c	u32	block_width_shift	Octree leaf block size shift (size = 2^block_width_shift = 1 << block_width_shift)
0x30	u32	area_x_blocks_shift	Y shift. Used to form the index of the root block's children (See section 4 algorithm)
0x34	u32	area_xy_blocks_shift	Z shift. Used to form the index of the root block's children (See section 4 algorithm)
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	Triangle altitude from Vertex 1 to the opposite side.
0x04	u16	pos_i	Vertex 1 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

Offsets in this section are interpreted differently depending on if that offset represents a non-leaf or a leaf block. The first entry represents the root block which is not a leaf block and contains the entire model. Subsequent blocks are subdivisions of the root block until the leaf blocks are reached.

• In non-leaf blocks, the offset points to an array of 8 u32 offsets, which are the offsets of the block's children.
• In leaf blocks, the offset points to an array of u16 prism 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.

As an example, MKW's algorithm for finding the leaf block that contains a point is as follows

u16* KCollisionOctree::searchBlock(const EGG::Vector3f& point) {
  // Calculate the x, y, and z offsets of the point from the minimum
  // corner of the tree's bounding box.
  const int x = point.x - this->area_min_pos.x;

  // 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 & this->area_x_width_mask) != 0) {
    return 0;
  }

  const int y = point.y - this->area_min_pos.y;
  if ((y & this->area_y_width_mask) != 0) {
    return 0;
  }

  const int z = point.z - this->area_min_pos.z;
  if ((z & this->area_z_width_mask) != 0)
  {
    return 0;
  }

  // Initialize the current tree node to the root node of the tree.
  u32 shift = this->block_width_shift;
  u8* curBlock = this->block_data;
  s32 offset;

  // Traverse the tree to find the leaf node containing the input point.
  u32 index = 4 * (((u32)z >> shift) << this->area_xy_blocks_shift
        | ((u32)y >> shift) << this->area_x_blocks_shift
        | (u32)x >> shift);

  while (true) {
    // Get the offset of the current node's child node.
    offset = *(u32*)(curBlock + index);

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

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

    index = 4 * ((4 * ((u32)z >> shift)) & 4
        | (2 * ((u32)y >> shift)) & 2
        | (1 * ((u32)x >> shift)) & 1);
  }

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

Tools

The following tools can handle KCL files:

• Collision Tools, by Blank: object exporter and importer, designed for Super Mario Galaxy, but usable for Mario Kart Wii
• CTools, by Chadderz: editor
• SZS Modifier, by Chadderz: editor
• un-beancorner, by Atlas: allows lowering wall collision to prevent clipping over road with walls around them
• Wexos's Toolbox, by Wexos
• Wiimms SZS Tools, by Wiimm: 3D Tool-compatible exporter and importer (may create a KCL directly from an OBJ file). Wiimms SZS Tools are recommended for KCL creation; see Creating a KCL with Wiimms Tools for details.