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 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 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.
0x0c	4	Offset to model list. Relative to start of file.
0x08	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
0x38	End of file header

Thereafter follows the model octree at the offset indicated. This appears to have format similar to that of the octree section (see section 4 below). This presumably allows the game to select one of the models to run collision detection against. 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 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
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
0x3c	End of model header

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 + 0x10 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	Unknown
0x14	Next triangle

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. mkw:KCL (File Format)