KCL (File Format)

From Custom Mario Kart
(Redirected from KCL)
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 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:

Retrieved from "https://wiki.tockdom.com/w/index.php?title=KCL_(File_Format)&oldid=439600"