KCL (File Format)
KCL Files are collision files used in Mario Kart 8 and many other games. They have been used since at least Mario Kart DS. The documentation here is specifically for the Mario Kart 8 implementation, which has certainly changed since the implmentation in Mario Kart Wii.
The KCL files contain simplified versions of the visual course model files in order to allow rapid collision detection. They use octrees for efficient spatial indexing, as well as storing the actual triangles of the models in a more rapidly accessible format.
File Format
The file begins with a header followed by a number of models. Each model describes the collision for a section of the map.
Header
The file begins with the following header.
| Offset | Size | Description |
|---|---|---|
| 0x00 | 4 | 0x02020000 file identifier. |
| 0x04 | 4 | Offset to octree. Relative to start of file. |
| 0x08 | 4 | Offset to model list. Relative to start of file. |
| 0x0c | 4 | Model count. |
| 0x10 | 12 | Minimal coordinate for all models. Stored as 3 floats; x, y and z. |
| 0x1c | 12 | Maximal coordinate for all models. Stored as 3 floats; x, y and z. |
| 0x28 | 4 | Coordinate shift |
| 0x2c | 4 | Y shift |
| 0x30 | 4 | Z shift |
| 0x34 | 4 | Unknown. Exporting it as 0 does not seem to cause issues. Values of Nintendo models can be found here. |
Global Model Octree
The collision files of Mario Kart 8 actually hold multiple "models" in the format of those found in Mario Kart Wii. This was either required because one of such models can only hold a maximum of 65535 polygons (due to how the triangles are indexed, s. below) and Mario Kart 8 collision models requiring more (though this only is the case with Dgc_YoshiCircuit, which contains 73885 triangles), or to further optimize collision detection due to the high-poly nature of Mario Kart 8 courses which store many small triangles very close to each other.
Instead of increasing the size used to store a triangle index (which was possibly not done due to how the collision code is optimized internally or to save space), multiple such models are stored, of which each represents the polygons available in one (or multiple) cubes of the whole course space. To divide the course space into such cubes referencing the models, a new "global" octree follows the header. It works similar like the octree of one of such models (see section 4 below), but instead of looking up polygons, models are looked up with it.
The global model octree consists of at least 8 integers, representing the octree node keys of the 8 cubes the course space is initially divided into. Depending on the flags set in the upper two bits of the key, either the remainder points to an index of a model in the model array which data will be used for this cube, divides the cube further into 8 subcubes, or denotes no data being available in this cube.
| Set Flags (0-based) | Remaining Data | Description |
|---|---|---|
| 31 | Model Index | The 0-based index to one of the models following in the file which holds the polygons for this part of space. The same model can be referenced multiple times if it spans multiple cubes (as it is the case for small tracks which only consist of 1 model, being referenced for all 8 initial cubes). |
| 31 & 30 | Unused (being 0) | No model is used for this cube, as no data is present in this part of space (e.g. there is nothing collidable in this section of course space). |
| else | Child Nodes Offset | Divides this cube into 8 more subcubes. The value is an offset in dwords (e.g. multiplied by 4 to get the byte offset), relative to the start of the current node, at which 8 child keys follow. |
Model octree of Baby Park, using only one model with no subdivisions. Also applies to Gu_Menu or Excite Bike Stadium.
Model octree of Mute City, having one subdivided cube.
Model octree of Yoshi Circuit, having two subdivided cubes, the highest amount of model octree subdivision found in the game.
This is then followed by the model list at an offset indiciated by the header. It is a list of offsets relative to the start of the file to each of the models as described below. The end of each model is aligned by 4 bytes, even if no models are following (making the file possibly end on 0 bytes). The length of the model is implicitly given by the distance to the next model (or the end of the file).
Model Format
Each model in the file has a format almost identical to KCL files in Mario Kart Wii. The changes are that section 3 is now 0 indexed, the triangle are now 0x14 bytes long and the octree lists are now 0xffff terminated. The Collision flags are also different. The model consists of a header, and four data sections.
Header
The header is a 0x3c byte structure as follows.
| Offset | Type | Description |
|---|---|---|
| 0x00 | u32 | Offset to section 1 |
| 0x04 | u32 | Offset to section 2 |
| 0x08 | u32 | Offset to section 3 |
| 0x0c | u32 | Offset to section 4 |
| 0x10 | single | Unknown. Always 30.0. |
| 0x14 | single3 | Spatial grid first coordinate |
| 0x20 | u32 | X mask |
| 0x24 | u32 | Y mask |
| 0x28 | u32 | Z mask |
| 0x2c | u32 | Coordinate shift |
| 0x30 | u32 | Y shift |
| 0x34 | u32 | Z shift |
| 0x38 | single | Unknown. Always 25.0. |
All offsets are relative to the start of the model.
The meaning of the shift and mask values is explained in section 4.
Section 1 - Vertices
Section 1 is simply a large array of vertices, stored as 3 successive singles for x, y and z. The length of this array is not stored, but can usually be calculated by subtracting the section 1 offset from the section 2 offset and dividing by 0xc.
Section 2 - Normals
Section 2 is much the same as section 1, in that it is a large array of normals. Again the values are stored as 3 successive singles for x, y and z. The length of this array is not stored, but can usually be calculated by subtracting the section 2 offset from the section 3 offset and dividing by 0xc.
Section 3 - Triangles
The third section is the section containing the actual model information. The structure of each entry in this section is a 0x14 byte structure given below.
| Offset | Type | Description |
|---|---|---|
| 0x00 | single | Length |
| 0x04 | u16 | Position index (0 based index into section 1) |
| 0x06 | u16 | Direction index (0 based index into section 2) |
| 0x08 | u16 | Normal A index (0 based index into section 2) |
| 0x0a | u16 | Normal B index (0 based index into section 2) |
| 0x0c | u16 | Normal C index (0 based index into section 2) |
| 0x0e | u16 | Collision flags |
| 0x10 | u32 | Global triangle index (spanning all models) |
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 exact manner in which the values are used for collision detection is unknown, however a method for converting this form of triangle to a set of three coordinates is outlined below. The coordinate system is right handed.
CrossA = Cross(NormalA,Direction) CrossB = Cross(NormalB,Direction) Vertex1 = Position Vertex2 = Position + CrossB * (Length / Dot(CrossB,NormalC)) Vertex3 = Position + CrossA * (Length / Dot(CrossA,NormalC))
A method for converting three vertices into the KCL form is given below. This method assumes the vertices are arranged anti clockwise when viewed from the collidable side.
Position = Vertex1 Direction = Unit( Cross( Vertex2 - Vertex1, Vertex3 - Vertex1 )) NormalA = Unit( Cross( Direction, Vertex3 - Vertex1 )) NormalB = Unit( -Cross( Direction, Vertex2 - Vertex1 )) NormalC = Unit( Cross( Direction, Vertex2 - Vertex3 )) Length = Dot( Vertex2 - Vertex1, NormalC )
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 gird 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, the 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 0 based index to section 3, which is a triangle that must be checked by an object at the original location. The list is 0xffff terminated. 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.
In Mario Kart 8, a single triangle list never contains more than ~512 triangles (with 499 being the longest list found in Gu_DossunIseki, followed by 492 and 421 triangle lists in Du_Hyrule). The average number of triangles in a list is 13. mkw:KCL (File Format)
Tools
The following tools can handle KCL files:
- io_scene_kcl: Blender Add-on by Ray Koopa (unable to export correctly).
- 010 Editor Binary Template: Can be used to fully parse KCL files and check them for errors in 010 Editor, or as a pseudo-code reference.